Find path between two nodes in graph

[Al1H]

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

Thanks for any advice.

 

[joel76]

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

 

[Al1H]

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

BUT THANK YOU ANYWAY

 

[kahleen]

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

 

[joel76]

Be careful of cycles !

 

[kahleen]

valid observation ...

here is the cycle-aware 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).

 

[Al1H]

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!

 

[kahleen]

replace the writef call

this one:

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

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

 

[misoijnr]

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
road
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”.
· Next to roads and junctions, you could enrich your map with additional points of interest.
· Use your imagination and your creativity to increase the functionality of your program,
which will of course be highly appreciated. Have a look at itinerary planners on the web
to gain some inspiration for additional features.

 

[CJKJohn]

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

 

[kahleen]

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