Find route in a system 1

[vbx]

Cann someone help me how to find path of a route in sistem,like: if i have a route from A to B i need to get all the cities that traverse from A to B ? how can thsi be done ? thanks

 

[kahleen]

Read this topic:

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

 

[vbx]

i have read it many times,but i dont understand it, oh(1,2,3) what that does numbers reprsent? and again the arguments of path what are representing? Hope you can explain your code that you post it there,I`ll apreciated.Thanks

 

[kahleen]

You have a graph with numeric nodes, and edges between nodes have a numeric value (length, cost, whatever)

oh(1, 2, 3) means there is an edge between nodes 1 and 2 with length 3

Such an information should be in every graph problem, you should adapt it to your own problem.

The main code is in the 'path' predicate. You should see the call:

path([A], B, Path, 0, Length)

1st parameter: CurrentPath = [A] (the starting point only)
2nd parameter: Target = B (the ending point)
3rd parameter: FinalPath = Path (here we will get the result)
4th parameter: CurrentLength = 0 (we are in the starting point)
5th parameter: FinalLength = Length (here we will get the length of the final path)

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

Here is the general case:
CurrentPath = [A | Rest]
Target = B (still the initial B, it didn't change)
FinalPath = Path (still the initial variable, unchanged)
CurrentLength = CurrentLength (this is the length of CurrentPath [A | Rest]
FinalLength = Length (still the initial variable, unchanged)

A is the last visited node, we should find somewhere to go from A, we do that by querying the 'oh' predicate which returns a node C and a length X from A to C, we test that C is not a node we already visited by using \+member (not member), we add X to the CurrentLength because we want to go in C so we obtain NewLength and we continue the algorithm from C, so:
CurrentPath = [C, A | Rest]
Target = B (the same)
FinalPath = Path (the same)
CurrentLength = NewLength (old CurrentLength + X)
FinalLength = Length (the same)

Everything stops when a call to 'path' is made with B as the last visited node, this is visible in the first 'path' rule

 

[vbx]

Can I ask why do you use for The first parameter,a list ? I am having dificults understanding that. Thanks

 

[kahleen]

Yes, a list ... The first parameter is the current path; being a path, we need a list to represent it. The outside call to the 'path' predicate is made with [A] as first parameter because the current path at the start contains only the starting node

 

[vbx]

Thank you,it works now,i didnt understand how to call path.i have one more question if you dont mind: how can i change this code to print only the shortest path ?

 

[kahleen]

That's more difficult. You either have to gather all results in a single list using findall (if they are not too many) or use the assert mechanism of Prolog to always store in your knowledge base the shortest path. When you discover a shorter one, you erase the old shortest one and reassert the new shortest one discovered.

Type help(findall) and help(assert) at the Prolog prompt to find out more about them.

 

[vbx]

I needed to print the path with the lenght less than a lenght i give,something like this:

short_path(X,Y,Len):-findall(L,path([X],Y,Path,0,Lenght),List), Lenght < Len.

But its not good how i wrote.Can you help me?

 

[kahleen]

Well, the result of findall is a list of L's. You need to use L in the goal of findall. It's something like this:

findall(L, some_goal(..., L, ...), List)

"findall values of L that satisfy some_goal(..., L, ...) and put them all in List"

Your second parameter of findall has nothing to do with L.

findall(L, path([X], Y, Path, 0, L), List)

Now you have in List all values of L that satisfy the path predicate. You need to select only those elements that are < Len

 

[vbx]

Sorry,I ment to put Lenght instead of L:

short_path(X,Y,Len):-findall(Lenght,path([X],Y,Path,0,Lenght),List), Lenght < Len.

Only one request of help i have,here is my code:

minn([H],H).
minn([H|T],Min) :- minn(T,Mum),(H < Mum -> Min = H; Min = Mum).

path(Ori,Dest,Len):-findall(Lenght,route([Ori],Dest,Path,0,Lenght),List),minn(List,M), M < Len,write(Ori),nl,write(Dest).
route([Dest | Rest], Dest, [Dest | Rest], Length, Length).
route([Ori | Rest], Dest, Path, CurrentLength, Length) :-
    link(Ori, C,_, X),
    \+member(C, [Ori | Rest]),
    NewLength is CurrentLength + X,
    route([C, Ori | Rest], Dest, Path, NewLength, Length).

Insted or writing Origin city and Destination,i want to print the path ? How can i modify this to show me the path ? Thanks

 

[kahleen]

Well, if there are 5 solutions to the 'route' predicate, your findall will gather in List their lengths ... so you will get 5 integer in List, you can compute the minimum or do whatever you want with them, but you will not have paths in there.

You need to modify your findall to generate not a list of lengths, but a list of pairs [Path, Length]

findall([Path, Length], route([Ori], Dest, Path, 0, Length), List)

Now your List will be something like this:

[ [Path1, Length1], [Path2, Length2], [Path3, Length3] ]

All the paths are lists of nodes.
All the lengths are integers.

You need to modify your minn predicate so that it can process lists of this particular form. It should return the pair that has minimum length. Give it a try, you are not very far from a solution.

Also, you can try the findall call at the Prolog prompt, see exactly what it returns

 

[vbx]

I tried all day but i really don`t have an ideea how to find minumum of a list of lists Some help please ?

 

[kahleen]

The same principle applies.

1st step - a list of one element would be something like this: [ [Path, Length] ] ... the minimum of such a list is [Path, Length]

In Prolog:

minimum([[Path, Length]], [Path, Length]).

2nd step - a list with more than one element would be something like this: [ [Path, Length] | Rest ] ... where [Path, Length] is the first element. Then we compute the minimum of Rest which should be something like [Path1, Length1]. Then the comparison between Length and Length1 will tell us who is the overall minimum

In Prolog:

minimum([[Path, Length] | Rest], [Path2, Length2]) :-
    minimum(Rest, [Path1, Length1]),
    Length < Length1,
    Path2 = Path,
    Length2 = Length.
minimum([[Path, Length] | Rest], [Path2, Length2]) :-
    minimum(Rest, [Path1, Length1]),
    Length >= Length1,
    Path2 = Path1,
    Length2 = Length1.

You can replace the two rules with a single one and make use of the conditional operator, but I think it's more easy to understand this way.

 

[vbx]

How do i use this predicate minimum? If i use it like this in querry,i get "false":

short(Ori,Dest,Min):-findall([Path,Lenght],route([Ori],Dest,Path,0,Lenght),List),
                     minimum(List,Min).

 

[kahleen]

The only thing I suspect besides a typo is the call to 'link' from the 'route' predicate'. You have something like this:

     link(Ori, C,_, X),

This is a call with 4 parameters. Do you have 'link' facts that take 4 parameters? Because I would say that 'link' should take 3 parameters: first node, second node and length

 

[vbx]

Yes,it takes 4 parameters,there is also Duration.

 

[kahleen]

Post the entire code then ... It works on my machine

 

[vbx]

link(timisoara,cluj,140,360).
link(timisoara,bucuresti,200,698).
link(timisoara,iasi,110,714).
link(craiova,timisoara,90,370).
link(brasov,craiova,185,399).
link(brasov,bucuresti,190,400).
link(bucuresti,galati,200,285).
link(bucuresti,sibiu,136,403).
link(bucuresti,iasi,195,360).
link(cluj,bucuresti,195,406).
link(cluj,iasi,200,369).
link(cluj,craiova,98,312).

minnn([[Path,Length] | Rest],[Path2,Length2]):-
        minnn(Rest,[Path1,Length1]),
        Length < Length1,
        Path2 = Path,
        Length2 = Length.
minnn([[Path,Length] | Rest],[Path2,Length2]):-
       minnn(Rest,[Path1,Length1]),
        Length >= Length1,
        Path2 = Path1,
        Length2 = Length1.

short(Ori,Dest,Min):-findall([Path,Lenght],route([Ori],Dest,Path,0,Lenght),List),
                     minnn(List,Min).

route([Dest | Rest], Dest, [Dest | Rest], Length, Length).
route([Ori | Rest], Dest, Path, CurrentLength, Length) :-
    link(Ori, C,_, X),
    \+member(C, [Ori | Rest]),
    NewLength is CurrentLength + X,
    route([C, Ori | Rest], Dest, Path, NewLength, Length).

 

[kahleen]

Well, you forgot one min rule. Read the previous post, you will find 3 min rules. 1st step and 2nd step are both mandatory, you only have 2nd step

PS: You're Romanian, so this means we're co-nationals