member predicate 1

[misoijnr]

hi, help me put this predicate into perspective, was trying to make one to find path on the facts attached.

findpath(Dest,L) :-
find_route(node(NodeID), Dest, L.
findpath(S, Dest, Sol) :-
way(S, Dest, , Path),
invert(Path, Sol).

path( P, P, L, L).
path( Node, Goal, Path, Sol) :-
route( Node, WayID), not( way(WayID) ),
not( member( WayID, Path)),
path( WayID, Goal, [WayID | Path], Sol).

member(X,[X|Xs]).
member(X,[_|Ys]) :- member(X,Ys).

node(NodeID) :- member(NodeID, [lat,long]).
node_tag(NodeID) :- member(NodeID,[name,highway,add:street,crossing,crossing_ref]).
way(WayID) :- member(WayID, Nodelist).
way_tag(WayID):-member(WayID,[name,highway,foot,maxspeed,lanes,oneway,bridge])

 

[kahleen]

You have a lot of predicates that are not implemented or at least, are not described here, like 'find_route' or 'route'. Also, 'way' in my opinion is not well defined:

way(WayID) :- member(WayID, Nodelist).

Prolog will point Nodelist to be a singleton variable here, and he's right. Who is Nodelist, where does it come from?

 

[misoijnr]

can you help me restructure it, please. have been trying it for some time now. thanks kathleen

 

[kahleen]

You need to tell first what 'route', 'find_route' and 'way' do ... I see you have a 'way' call with 4 parameters, but then 'way' is implemented with only 1 parameter

 

[misoijnr]

hi,
i think they are redundant or does the same job,
my thinking was to get a predicate which give a path or route when you choose a starting point given the facts on the database. can you re-write the way you think is correct then i can try to see from your perspective.
Thanks kathleen for your support

 

[kahleen]

I'll take a look later when I return home because it's not quite clear for me what all your predicates are for. In the mean time, maybe you can take a look at this topic for a quick path search within a graph. This should be adapted to suit your needs

http://www.tek-tips.com/viewthread.cfm?qid=1607508&page=2

 

[misoijnr]

thanks, let me know what you come up with

 

[misoijnr]

you can download the attached file, it will give you an idea of what i had in mind.
thanks

 

[misoijnr]

hi kahleen,
did u manage to check my problem?
would appreciate your comment
thanks

 

[misoijnr]

i re-wrote the predicat to look like this, but somethng wrong somewhere
member(X,[X|Xs]).
member(X,[_|Ys]) :- member(X,Ys).

node(NodeID) :- member(NodeID, [lat,long]).
node_tag(NodeID) :- member(NodeID,[X,Y]]).
way(WayID) :- member(WayID, Nodelist).
way_tag(WayID):-member(WayID,[X1,Y1])

route(A,B):-node(NodeID,[lat,long]),node(NodeID,[Nodelist])way(WayID,[X,Y]),way_tag(WayID,[X1,Y1])
route(A,B,[A,B]) :- node(A,B).

route(A,B,[X1,Y1]) :-
travel(A,B,[A],Q),
reverse(Q,[X1,Y1]).

travel(A,B,P,[B|P]) :- way(A,B).

travel(A,B,Visited,[X1,Y1]) :-
way(A,C,X),
C \== B,
\+member(C,Visited),
travel(C,B,[C|Visited],[X1,Y1]).

 

[misoijnr]

hi kahleen,i have re-writen like below, any sugestion to optimise it?

member(X,[X|Xs]).
member(X,[_|Ys]) :- member(X,Ys).

node(NodeID) :- member(NodeID, [lat,long]).
node_tag(NodeID) :- member(NodeID,[X,Y]]).
way(WayID) :- member(WayID, NodeID).
way_tag(WayID):-member(WayID,[X1,Y1])

route(A,B):-node(NodeID),node_tag(NodeID),way(WayID,NodeID),way_tag(WayID).
route(A,B,[A,B]) :- node(A,B).

route(A,B,[WayID,NodeID]) :-
travel(A,B,[A],Q),
reverse(Q,[WayID,NodeID]).

travel(A,B,P,[B|P]) :- way(A,B).

travel(A,B,Visited,[WayID,NodeID]) :-
way(A,C,X),
C \== B,
\+member(C,Visited),
travel(C,B,[C|Visited],[WayID,NodeID]).

 

[kahleen]

Sorry, I'm abroad since yesterday and for the next three days, I don't have much online time as I just check e-mails. I'll take a look when I'll be back in my office

 

[misoijnr]

thanks kahleen. enjoy your trip

 

[misoijnr]

kahleen, what did u make of the above re-written predicates?
do u have a different version of writing it?
thanks

 

[kahleen]

First of all, let me ask something about semantics. You have a lot of 'node', 'node_tag', 'way' and 'way_tag' in your file.

'node' defines a node on the map:

node(16424219, 50.8693195, 4.7078038).

16424219 is a unique ID for the node
2nd parameter is the latitude
3rd parameter is the longitude


'node_tag' defines additional information about a particular node

node_tag(16424219, 'crossing', 'traffic_signals').
node_tag(16424219, 'highway', 'traffic_signals').

These facts refer to node with ID = 16424219 defined earlier.

'way' defines a sequence of nodes:

way(81522744, [836447062, 925764645, 241151642, 851664000, 924451067]).

81522744 is a unique ID for the way
2nd parameter is the list of nodes that are part of the way

'way_tag' defines additional information about a particular way

way_tag(81522744, 'highway', 'residential').
way_tag(81522744, 'lit', 'yes').
way_tag(81522744, 'maxspeed', 30).
way_tag(81522744, 'name', 'Tiensevest').
way_tag(81522744, 'oneway', 'yes').
way_tag(81522744, 'width', 6).

These facts refer to way with ID = 81522744 defined earlier.

OK, now exactly what do you need to do with these facts? It's not quite clear to me

 

[misoijnr]

This is what i intend to make the predicates do:
-Find the neighbouring nodes for any node
- look at the waylists and find those nodes next to it in the list.
-If a node is not on a waylist, then there is no way connected to this node, hence it is (in theory) unreachable.

-calculate distance using euclidean distance. (e.g can choose between calculating the distance between the begin node and the end node)- or calculate the distance between all nodes on a way

-pre-process the data and come up with some clauses that will be used in my computations.
-i want to use less asserts so that it doesnt bloat the internal search tree of prolog.
- Save these preprocessed results to a file and consult this file at startup.
-If possible, it should be possible to preprocess for new files, other than leuven.pl that i have attached.
-Finally, i would want the predicates take in user inputs like start point name, and end point name, and output the route for the user.
mostly, node_tag and way should be used to preprocess these, but just point me in the right direction with few lines of code, then i can practise more

thanks kahleen

 

[kahleen]

For simplicity, let's assume that we have 'leuven.pl' containing this information:

node(1, 14, 22).
node(2, 25, 13).
node(3, 50, 4).
node(4, 7, 21).
node(5, 18, 32).
node(6, 60, 12).
node(7, 31, 11).
node(8, 12, 19).

way(1, [2, 4, 5, 8]).
way(2, [1, 3, 4]).
way(3, [5, 8, 7, 6]).

Let's start with a simple predicate that computes Euclidean distance between 2 nodes, provided that we know their IDs

distance(AId, BId, D) :-
    node(AId, XA, YA),
    node(BId, XB, YB),
    DSquare is (XB - XA) * (XB - XA) + (YB - YA) * (YB - YA),
    D is sqrt(DSquare).

For example:
?- distance(2, 4, X).
... will return X = 19.6977

If I got it right, what you need to do is process all ways and as soon as you find a pair of nodes X and Y such that X and Y are neighbors in some list, you need to create a fact edge(X, Y, Dxy) where Dxy is the euclidean distance between X and Y. For example, because 2 and 4 are neighbors in one of the lists, you will generate edge(2, 4, 19.6977). You also want the generation of edges to occur in another file, not in 'leuven.pl' because it's already too large.

Then I propose you create another file called 'generate.pl' and put it right next to 'leuven.pl' (in the same folder) and 'generate.pl' will generate the 'graph.pl' file that you need.

Put this code into 'generate.pl':

start :-
    tell('graph.pl'), % open 'graph.pl' as the new output
    create_db.        % this will create the 'edge' facts
start :-
    listing(node),    % list all nodes ... the result will go in 'graph.pl'
    listing(edge),    % list all edges ... the result will go in 'graph.pl'
    told.             % close 'graph.pl'

create_db :-
    consult('leuven.pl'), % we need 'leuven.pl' for nodes and ways
    way(_, ListOfNodes),  % get the first way
    process(ListOfNodes), % use ListOfNodes to generate edges
    fail.                 % return to the previous call to 'way' to get a new way

distance(AId, BId, D) :-
    node(AId, XA, YA),
    node(BId, XB, YB),
    DSquare is (XB - XA) * (XB - XA) + (YB - YA) * (YB - YA),
    D is sqrt(DSquare).

process([]).
process([_]).
process([A, B | Rest]) :-
    distance(A, B, Dab),      % compute distance A - B
    assert(edge(A, B, Dab)),  % create edge
    process([B | Rest]).      % continue processing with the other pairs

You just call 'start' and 'graph.pl' will be generated. It will contain all the nodes and direct edges between nodes, together with their length.

You can use the algorithm presented here:

http://www.tek-tips.com/viewthread.cfm?qid=1607508&page=2

... to compute paths between two non-adjacent nodes. Just take care that edge information is called 'oh' if you read the topic. For you, it's 'edge' (different names, but the same thing)

One problem with the code I gave you above is that you will get duplicate edges. If pair (2, 4) lies in more than one way, you will get the edge(2, 4, 19.6977) more than once. It's possible to get rid of duplicates, but that would complicate the code. Maybe when you understand it better, you could add code to remove duplicates yourself

 

[misoijnr]

thanx kahleen, i managed to create the file graph.pl
one more question,
i dont want to loose the names of places from leuven.pl,
how do i generate a new file like graph.pl but with edge as the way and contains names of lets call it destination?
last question, what is the code of accepting user input like- start position and destination then the output gives the shortest distance from the edges given?
if you help me on this, in two weeks i will give you a code with more extensions from the same, thanks so much.

 

[kahleen]

You don't need to generate so many in 'graph.pl'. In fact, it's a mistake that we generated nodes in 'graph.pl' because now you have nodes duplicated both in 'leuven.pl' and in 'graph.pl'. So take out the 'listing(node)' line from the above code. This way you will only generate edges in 'graph.pl' and nodes remain the ones in 'leuven.pl'.

Now if you want to run any graph algorithm, you write it in another file, let's call it 'algorithms.pl':

init :-
    consult('leuven.pl'),    % get the nodes and ways
    consult('graph.pl').     % get the edges that we generated earlier

do_something :-
    init,         % call init to consult the 2 files we need
    start_algorithm.

start_algorithm :-
    write('Enter start node ID: '),
    read(X),      % X is a value entered by the user
    write('Enter end node ID: '),
    read(Y),      % Y is a value entered by the user
    get_path(X, Y, Path),
    write(Path).

get_path(X, Y, Path) :-
    ............

I also put user input examples in the code above. Just make sure that when you are prompted for X and Y, you enter an integer followed by a dot (2. or 45.). That's what Prolog likes when reading values from the user.

In a more advanced version, you could present the user with a list of places taken from 'leuven.pl' so he doesn't have to enter node IDs. But for a start, node IDs are fine for the user to enter.

 

[misoijnr]

thanks for your quick reply,
for the getPath predicate, can this work?
get_path(A, B) :-
path([A], B, Path, 0, Length),
reverse(Path, DirectPath),
printPath(DirectPath),
nl,
fail.

i think i have enough information now to proceed, but will be coming back to ask few things, especially using list of places instead of IDs for user input.
thanks again