×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

#### Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

# Find path between two nodes in graph

## Find path between two nodes in graph

(OP)
I am newie in Prolog, could you please someone help me?
Assignment:

At entry is given a discontinuous/disjointed graph with list of their evaluated edges. Write a program in Prolog, which detects all paths and their evaluation between two given nodes of a graph.

I want to find path between node 0 and 3

oh (0, 1, 1).
oh (1, 2, 3).
oh (1, 3, 3).
oh (2, 3, 3).
oh (4, 5, 3).

Output should be something like this:
first path - 0, 1, 2, 3 with evaluation 6
second path - 0, 1, 3 with evaluation 4

### RE: Find path between two nodes in graph

You have to write the predicate that compute one way with its cost, and use bagog/3 to gather all the ways.

### RE: Find path between two nodes in graph

(OP)
I'm really a newbie and I would appreciate specific information...something like curtie7 in thread "Print graphs nodes"...

BUT THANK YOU ANYWAY ;)

### RE: Find path between two nodes in graph

try this:
oh(0, 1, 1).
oh(1, 2, 3).
oh(1, 3, 3).
oh(2, 3, 3).
oh(4, 5, 3).

path(A, B, [A, B], X) :-
oh(A, B, X).
path(A, B, PathAB, Length) :-
oh(A, C, X),
path(C, B, PathCB, LengthCB),
PathAB = [A | PathCB],
Length is X + LengthCB.

find_paths(A, B) :-
path(A, B, Path, Length),
printPath(Path),
writef(' with evaluation %d\n', [Length]),
fail.

printPath([]).
printPath([X]) :-
!, write(X).
printPath([X|T]) :-
write(X),
write(', '),
printPath(T).

you launch everything by calling: find_paths(0, 3) ... or whatever pair of nodes you want

### RE: Find path between two nodes in graph

Be careful of cycles !

### RE: Find path between two nodes in graph

valid observation ...

here is the cycle-aware code:

#### CODE

oh(0, 1, 1).
oh(1, 2, 3).
oh(1, 3, 3).
oh(2, 3, 3).
oh(4, 5, 3).

path([B | Rest], B, [B | Rest], Length, Length).
path([A | Rest], B, Path, CurrentLength, Length) :-
oh(A, C, X),
\+member(C, [A | Rest]),
NewLength is CurrentLength + X,
path([C, A | Rest], B, Path, NewLength, Length).

find_paths(A, B) :-
path([A], B, Path, 0, Length),
reverse(Path, DirectPath),
printPath(DirectPath),
writef(' with evaluation %d\n', [Length]),
fail.

printPath([]).
printPath([X]) :-
!, write(X).
printPath([X|T]) :-
write(X),
write(', '),
printPath(T).

### RE: Find path between two nodes in graph

(OP)
The first tip was better, but it is not complete solution...chart is in attachment (url) and it´s obvious that has 2 solutions. The path No. 1 is - 0, 1, 2, 3 with length 7. The second path is - 0, 1, 3 with length 4.

But program says:
find_paths(0, 3)
0", "1", "3Unknown clause found writef(" with evaluation %d\n",[4])
Execution terminated
No solutions

Any idea?

kahleen, thanks a lot for your help!

### RE: Find path between two nodes in graph

replace the writef call

this one:

#### CODE

writef(' with evaluation %d\n', [Length]),

#### CODE

write(' with evaluation '),
write(Length),
nl,

maybe you are not using SWI-Prolog but some other flavour?
or maybe you didn't write the code as it is in the example above ...

### RE: Find path between two nodes in graph

help me with this
Basic Program
Write an itinerary planner that, given a map consisting of roads and junctions between roads, can
provide the user with a textual description of an itinerary between two roads on the map (you
don't need to take into account house numbers). In addition, the planner should support the
following functionality:
· It does not suffice to present an itinerary to the user in the form of e.g. a simple path of
roads to follow. The planner should provide detailed info on what to do at each junction.
For example, at a road junction, it should be able to specify "turn left" or "turn right". At
a roundabout, the planner could report "at the next roundabout, take the 2nd exit". When
leaving a motorway, the planner can report e.g. "take highway exit 23".
· The planner should be able to calculate the total travel time of the itinerary and the total
distance travelled. Sometimes you will have to approximate the distance of a road and the
time it takes (based on speed limits, for example).
· It must be possible to optimize the search for an itinerary based on different criteria.
Examples are "prefer the fastest route" or "prefer the shortest route".
· Your planner should take one-way streets into account when appropriate (e.g. one-way
streets don't usually count for pedestrians).
· It should be possible to add additional constraints to the itinerary. For example, the user
could indicate that he/she does not want to drive on highways, or that he/she wants to
avoid a certain place because of e.g. roadworks or traffic jams. Implement at least one
The Prolog-version of the map represents nodes as the triple node(id,latitude,longitude) and ways
as a tuple way(id,list-of-node-ids). Node attributes are given as node_tag(id,key,value) and way
attributes as way_tag(id,key,value). Note that this OpenStreetMap (OSM) data is still very lowlevel.
It's up to you to write some Prolog predicates to create more useful and expressive data
abstractions out of the more primitive OSM facts.
Possible extensions
To gain extra points, you can further extend your project with the following requirements:
· Make it possible to advise your planner what kind of user you are (e.g. pedestrian, cyclist,
car driver, ...). The planner should take this information into account when constructing
an appropriate route. For example, a cyclist cannot use a highway.
· Make it possible to ask for an itinerary between a departure and an arrival address which
explicitly visits a number of user-specified places (i.e. the user can specify that he wants
to go from A to C via B).
· Make it possible to ask the planner for information such as "At what time do I have to
leave Egmontstraat,Brussel to get to Pleinlaan,Brussel at 10:00AM?".
· Create a human language interface such that the user can interact with the shell using
input like:
o how do I get from Martelarenplein, Leuven to Pleinlaan, Brussel
o how long does it take to go from Grote Markt, Brussel to 'Generaal Jacqueslaan',
Brussel as a cyclist
o how do I get from Louisalaan, Brussel to Pleinlaan, Brussel preferring the shortest
o how do I get from E40, Aalst to E314, Lummen avoiding R0
o how do I get from Gent to Antwerpen avoiding highways
o ...
o Make your planner calculate the approximate cost of the trip (in terms of fuel
and/or toll).
· Add a pretty-printer that nicely prints out the itinerary with duration and distance
information between each junction.
· Enable other preferred routes other than "fastest" and "shortest".
which will of course be highly appreciated. Have a look at itinerary planners on the web
to gain some inspiration for additional features.

### RE: Find path between two nodes in graph

hey, I am trying to find the cost or the length of the path by the following code. This program finds the correct path.
Can anyone help me that how to find the cost/length of that path in the following code.
the input is in the form of
path(1,5,P).
which gives
P = [1,4,5];
P = [1,3,4,5]; and so on.

path(1,5,P,N) -> i want to find N which is the cost. so that the output is like this.
P = [1,4,5]
N = 15

Code starts here:

path(A,B,[A,B]) :- edge(A,B).

path(A,B,Path) :-
travel(A,B,[A],Q),
reverse(Q,Path).

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

travel(A,B,Visited,Path) :-
edge(A,C,X),
C \== B,
\+member(C,Visited),
travel(C,B,[C|Visited],Path).

### RE: Find path between two nodes in graph

But you have an example of computing path lengths right above, I believe it's the 6th post in this topic

#### Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

#### Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Close Box

# Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!