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:


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

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

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

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

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

thanks, let me know what you come up with

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

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

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]).

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]).
 

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  

thanks kahleen. enjoy your trip

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

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:


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


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

'way' defines a sequence of nodes:


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

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

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


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


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':


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 :)

 

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.
 

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':


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.

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

It will work, just make get_path take 3 parameters (add Path also as the 3rd).

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.

i used this, but i get error below-
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

Well, if you look at the code, it's 'do_something' that you need to call, not 'start_algorithm'

'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

good, i have seen that.
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.

 
 

What nodes did you try? Because as I told you, your current algorithm does not take into account that edge(A, B, X) also means edge(B, A, X), so maybe some possibilities are not considered.

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:


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).

it is working but generates a lot of nodes continuously, i think there should be use cut, to give only the path from start node to end node through directly connected and in one way only. this is where it get complicated for me.
how do we avoid duplicates?
thanx

You don't need the cut. Those are only due to duplicated edges.

Go back to where you have defined the 'process' predicate and modify it like below:


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

hi, i have rerun the code above,
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?

Ok, try adding this code in the upper part of the file where you have 'start', 'create_db' and 'process':


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.

that has worked,
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
 

Ok, I didn't try on the large 'leuven.pl' file, so maybe it goes on forever because there are many results.

Do the following modification to the code, so that Prolog will stop after each solution and print it to you:


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.

do i need to define start_algorithm/1 as dynamic? check this error
% 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

Make sure you replaced your original code with the one I provided.

'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

i have replaced. where do i set the parameter values?
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

"and how do i replace the node Ids with name of node_tag?"


Come on, this is easy.


If the program expects user input (read(X)) and the user enters 'Kardinaal Mercierlaan', then X would take that value. So you should query:


... 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

Anyway, I suggest you rely on node IDs for the moment and not names. Let the user enter IDs. From what I see, most of the nodes in your 'leuven.pl' don't have a node_tag with name information.

i have tried but cant spot where i need to correct the error-
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).

'start_algorithm' ends with a comma. It should end with a dot. So probably Prolog won't even compile your code, you shouldn't try to run it when the compilation reports error, but rather try to fix those errors.

i have noted the error, thanks,

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

Well, I really think that you should try yourself taking little steps to fulfill your goal. Asking some random guy on a forum solve each and every step is neither appropriate for learning, nor rewarding. Rewarding is when you discover by yourself that using this or that condition helps in restricting the results to pedestrian paths or cyclist paths, for example.

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

hi kahleen,

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).

how should i avoid singleton variables from the above code, seems am getting that error