member predicate
member predicate
(OP)
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, [S], 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])
findpath(Dest,L) :-
find_route(node(NodeID), Dest, L.
findpath(S, Dest, Sol) :-
way(S, Dest, [S], 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])
RE: member predicate
CODE
Prolog will point Nodelist to be a singleton variable here, and he's right. Who is Nodelist, where does it come from?
RE: member predicate
RE: member predicate
RE: member predicate
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
RE: member predicate
h
RE: member predicate
RE: member predicate
thanks
RE: member predicate
did u manage to check my problem?
would appreciate your comment
thanks
RE: member predicate
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]).
RE: member predicate
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]).
RE: member predicate
RE: member predicate
RE: member predicate
do u have a different version of writing it?
thanks
RE: member predicate
'node' defines a node on the map:
CODE
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
CODE
node_tag(16424219, 'highway', 'traffic_signals').
These facts refer to node with ID = 16424219 defined earlier.
'way' defines a sequence of nodes:
CODE
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
RE: member predicate
-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
RE: member predicate
CODE
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
CODE
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':
CODE
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: h
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 :)
RE: member predicate
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.
RE: member predicate
Now if you want to run any graph algorithm, you write it in another file, let's call it 'algorithms.pl':
CODE
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.
RE: member predicate
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
RE: member predicate
Also make sure you take into account that edge(A, B, X) also means edge(B, A, X). So when you implement the algorithm and your current node is Z, find a neighbor either by calling edge(Z, Neighbor, D) or by calling edge(Neighbor, Z, D). Z could be in either place in your edge information.
RE: member predicate
get_path(X, Y, Path) :-
path([X], Y, Path, 0, Length),
reverse(Path, DirectPath),
printPath(DirectPath),
fail.
1 ?- start_algorithm.
Enter start node ID: 231994501.
Enter end node ID: 249394762.
ERROR: path/5: Undefined procedure: edge/3
2 ?-
whats the problem? thanks
RE: member predicate
'do_something' calls 'init' and then 'start_algorithm'
If you just call 'start_algorithm' directly, you won't be calling 'init', so your code won't find any 'edge' facts. 'init' does just that, consults files 'leuven.pl' and 'graph.pl' so that node, way and edge information is available for future use
RE: member predicate
i am trying to use this code, but seems something is wrong, it cant print the path after i enter start and end nodes:
path([B | Rest], B, [B | Rest], Length, Length).
path([A | Rest], B, Path, CurrentLength, Length) :-
edge(A, C, X),
\+member(C, [A | Rest]),
NewLength is CurrentLength + X,
path([C, A | Rest], B, Path, NewLength, Length).
get_path(A, B, Path) :-
path([A], B, Path, 0, Length),
reverse(Path, DirectPath),
printPath(DirectPath),
fail.
thank you so much for your support, i am now begining to see the power of prolog.
RE: member predicate
Make sure that you don't choose nodes that are not connected in your graph, or are connected but only if you consider edges to be bidirectional.
Also change printPath to this:
CODE
printPath([X]) :-
!, writeln(X).
printPath([X|T]) :-
write(X),
write(', '),
printPath(T).
It will help you see better by putting a newline after each solution.
Now you may get a lot of duplicate solutions because as I've told earlier, edges are not unique. It's not too complicated to make the generation process generate unique edges (you have to test at each edge generation that it doesn't exist already).
RE: member predicate
how do we avoid duplicates?
thanx
RE: member predicate
Go back to where you have defined the 'process' predicate and modify it like below:
CODE
process([_]).
process([A, B | Rest]) :-
distance(A, B, Dab), % compute distance A - B
\+edge(A, B, _), % verify that edge doesn't exist already
assert(edge(A, B, Dab)), % create edge
assert(edge(B, A, Dab)), % create the opposite edge
process([B | Rest]). % continue processing with the other pairs
process([A, B | Rest]) :-
distance(A, B, Dab), % compute distance A - B
edge(A, B, _), % if such an edge already exists
process([B | Rest]). % continue processing with the other pairs
This code should avoid generating duplicates (didn't test it though since it's late). You should clear the 'graph.pl' and rerun the generation predicate. I think it was called 'start' back then
RE: member predicate
but error
% leuven.pl compiled 4.31 sec, 2,000,216 bytes
ERROR: process/1: Undefined procedure: edge/3
Exception: (6) start ?
is it missing something while checking if duplicates exist? on the \+edge above?
RE: member predicate
CODE
This way you tell Prolog that it should expect to have some 'edge' clauses asserted dynamically, even though there are none defined explicitly, so it should stop complaining about not having 'edge' defined.
RE: member predicate
but still, when i enter start node and end node, it gives continous result nodes.
how do i limit only to nodes in the same e.g way(80362707, [937819764, 937819761, 937819774, 937819762, 937819764]).
from leuven.pl is a way with list of nodes within it.
so that it does not enter into a loop of so many nodes from the edges. i.e how do we generate edges of nodes in the same list of way[] from leuven.pl? so that when i enter 937819764 as start node and 937819764 as the end node, it gives me the nodes i have to go through to reach the last node with the total lenght, i.e nodes to arrive at 937819764, are 937819761 then 937819774 then 937819762
also way[wayId,[]], how can we link ways? so that we can generate paths that one can get from way1 to way2 before arriving at final node?
i know its alot of work, but am keenly following your advise. thanks
RE: member predicate
Do the following modification to the code, so that Prolog will stop after each solution and print it to you:
CODE
consult('leuven.pl'), % get the nodes and ways
consult('graph.pl'). % get the edges that we generated earlier
find_path(Path) :-
init, % call init to consult the 2 files we need
start_algorithm(Path).
start_algorithm(Path) :-
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),
get_path(X, Y, Path) :-
path([X], Y, ReversedPath, 0, Length),
reverse(ReversedPath, Path),
printPath(Path).
Run find_path(Path) and see what results you get for Path. After each result, press ';' to go to the next one. See if something interesting happens.
RE: member predicate
% leuven.pl compiled 5.02 sec, 2,000,452 bytes
% graph.pl compiled 0.23 sec, 1,506,752 bytes
ERROR: find_path/1: Undefined procedure: start_algorithm/1
and how do i improve the code to retunr the total distance between the start and end node.
thanks
RE: member predicate
'start_algorithm' should take 1 parameter, like in the last code snippet. The original version had 0 parameters, and that's what's causing the error
RE: member predicate
and how do i replace the node Ids with name of node_tag? i.e user enters the start name and laste name and the prolog program returns the nodes(name_tags) between the start and end nodes and also list the way names .i.e go from way1 then way2 and finally reach node last.
thanks
RE: member predicate
Come on, this is easy.
CODE
node_tag(16387325, 'name', 'Kardinaal Mercierlaan').
If the program expects user input (read(X)) and the user enters 'Kardinaal Mercierlaan', then X would take that value. So you should query:
CODE
... so the variable ID will be bound to 16387325 ...
Then you can go on with the normal algorithm using ID. The node_tag was only used to retrieve the ID from the value 'Kardinaal Mercierlaan'
You should easily find the error about not finding some predicate, if you look closer.
ERROR: find_path/1: Undefined procedure: start_algorithm/1
This error means that in the 'find_path' predicate that takes 1 parameter (find_path/1) you make a call to 'start_algorithm' also with 1 parameter. But where you defined 'start_algorithm' it doesn't take 1 parameter, hence the error. It should be easy to spot and fix
RE: member predicate
RE: member predicate
ERROR: find_path/1: Undefined procedure: start_algorithm/1
the code is this
find_path(Path) :-
init, % call init to consult the 2 files we need
start_algorithm(Path).
start_algorithm(Path) :-
% node_tag(ID, 'name', X),
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),
get_path(X, Y, Path) :-
path([X], Y, ReversedPath, 0, Length),
reverse(ReversedPath, Path),
printPath(Path).
RE: member predicate
RE: member predicate
if you have time, re-edit the code for me to do the following, then i can continue from there:
-Use leuven.pl to preprocess another file with- Node Id and Its names, way_tag with nodes, names and way with node id, way id, name of the way and edge with way name and distance calculated from euclidean.
and finally re-edit the code for me on the user input.
What i wanted this code to do is:
-A user enters its type like pedestrian, driver, or cyclist.
- then enters the name of where he is and where he wants to go.
-an itinerary is generated from the facts from leuven.pl
i.e, go from point A(name) to Point B, through point C etc and giving the shortest distance or route to take and the total distance from the euclidean algorithm we have used above.
If u can write for me a skeleton of this program that runs, then i continue learning.
i have really appreciated your support. I know i have consumed so much of your time on a simple problem to you, am really trying to learn prolog, it sounds an interesting language to learn.
cheerz kahleen
RE: member predicate
I suggest you build a smaller version of 'leuven.pl' that contains a sufficient collection of nodes and ways of interest for you, and at the same time it's small enough to comprehend, because a 800Kb version is far from comprehensible. Try every idea that you have on the smaller version, struggle to get the result that you want, if you don't succeed use the debugger to see what's wrong and how to correct it. I promise it would be fun, the problem is interesting and full of rewards if you take the time to try and solve it.
Good luck
RE: member predicate
i am re-writing the get_path predicate below to take into account iterative deepening also to avoid loop or for loop detection, also, am trying to include lenght as a cost to the search space. however, can i use the edge facts i generated earlier ? check the code below, it tries to analyse paths that have been visited so that it does not loop. advise.
% depth-first search with loop detection
get_path([Path|Rest],Visited,Path):-
path(Path).
get_path([Current|Rest],Visited,Path):-
node(X,Y),
add_path(Y,Rest,Visited,NewPaths),
get_path(NewPaths,[Current|Visited],Path).
add_path([],Paths,Visited,Paths).
add_path([X|Rest],OldPaths,Visited,[X|NewPath]):-
not edge(X,OldPaths),
not edge(X,Visited),
add_path(Rest,OldPaths,Visited,NewPaths).
add_path([X|Rest],OldPaths,Visited,NewPaths):-
edge(X,OldPaths),
add_path(Rest,Oldpaths,Visited,NewPaths).
add_path([X|Rest],OldPaths,Visited,NewPaths):-
edge(X,Visited),
add_path(Rest,OldPaths,Visited,NewPaths).
RE: member predicate