×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • 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.

Students Click Here

Find route in a system

Find route in a system

Find route in a system

(OP)
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
Replies continue below

Recommended for you

RE: Find route in a system

(OP)
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

RE: Find route in a system

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

RE: Find route in a system

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

RE: Find route in a system

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

RE: Find route in a system

(OP)
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 ?

RE: Find route in a system

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.

RE: Find route in a system

(OP)
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?

RE: Find route in a system

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

RE: Find route in a system

(OP)
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

RE: Find route in a system

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

RE: Find route in a system

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

RE: Find route in a system

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.

RE: Find route in a system

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

 

RE: Find route in a system

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

RE: Find route in a system

(OP)
Yes,it takes 4 parameters,there is also Duration.

RE: Find route in a system

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

RE: Find route in a system

(OP)

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

RE: Find route in a system

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

RE: Find route in a system

(OP)
Ohh yes,I completely forgot about that. It works now

PS: glad to be co-nationals :) Thanks for helping a beginer. I am done with the questions for now,sorry for the stress :)

RE: Find route in a system

Glad to help. Without that rule, recursivity doesn't end. Prolog will successively shorten the list and will arrive at an empty list and no rule will tell it how to get the minimum out of that list, so it will fail. We have to provide the answer manually when the list gets to be 1-element long, because it's easy for us to know the answer at that point, without relying on recursivity.

RE: Find route in a system

(OP)
I was used to C and C++ ,but i had to study prolog in the past 9 days for a school project,so i am not use to it :)

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.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login


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:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close