Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations bkrike on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Find route in a system 1

Status
Not open for further replies.
vbx

vbx

Programmer
Dec 12, 2010
18
RO
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
 
Sort by date Sort by votes
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
 
Upvote 0 Downvote
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:

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

Code: 
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
 
Upvote 0 Downvote
Can I ask why do you use for The first parameter,a list ? I am having dificults understanding that. Thanks
 
Upvote 0 Downvote
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
 
Upvote 0 Downvote
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 ?
 
Upvote 0 Downvote
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.
 
Upvote 0 Downvote
I needed to print the path with the lenght less than a lenght i give,something like this:

Code: 
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?
 
Upvote 0 Downvote
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:

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

Code: 
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
 
Upvote 0 Downvote
Sorry,I ment to put Lenght instead of L:
Code: 
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:
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
 
Upvote 0 Downvote
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]

Code: 
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
 
Upvote 0 Downvote
I tried all day but i really don`t have an ideea how to find minumum of a list of lists :( Some help please ?
 
Upvote 0 Downvote
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:

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

Code: 
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.
 
Upvote 0 Downvote
How do i use this predicate minimum? If i use it like this in querry,i get "false":
Code: 
short(Ori,Dest,Min):-findall([Path,Lenght],route([Ori],Dest,Path,0,Lenght),List),
                     minimum(List,Min).

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

Code: 
     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
 
Upvote 0 Downvote
Yes,it takes 4 parameters,there is also Duration.
 
Upvote 0 Downvote
Code: 
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).
 
Upvote 0 Downvote
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 :)
 
Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

S.K
  • Locked
  • Question
Compress a list that contains segments of continuous numbers to a list which contains list of range
Replies
0
Views
594
S.K
S.K
E.saadallah
  • Locked
  • Question
DFS vs BFS search in prolog
Replies
0
Views
418
E.saadallah
E.saadallah
prologuser8
  • Locked
  • Question
Sorting a list of tupples - Maze exercise
Replies
0
Views
424
prologuser8
prologuser8
3sir
  • Locked
  • Question
find the shortest path
Replies
0
Views
340
3sir
3sir
VinnieCFC
  • Locked
  • Question
Prolog DFS method implementation for a tree
Replies
0
Views
378
VinnieCFC
VinnieCFC

Part and Inventory Search

Sponsor

Back
Top