1

I need a method that returns all the roads* used in a route between two points, here's the map I have:

Map image

Example, to point A to E, i need a list of roads used, like that:

route(a, e, R).
R = [1,5].

I'm having problems in marking the routes that i've already visited, and on top of that, register the number of the road used in a list.

So here's my code so far:

road(1,a,b).
road(2,a,d).
road(3,b,c).
road(4,c,d).
road(5,b,e).
road(6,c,f).
road(7,d,f).
road(8,e,f).

connected(A,B) :- road(_,A,B).

route(A, B, R) :- road(R, A, B), road(R, B, A).
route(A, B, [R2|R]) :- route(A, C, R2), route(C, B, R2).
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
RoxDan
  • 53
  • 1
  • 8
  • 1
    Not sure what you mean by "marking" the routes you've visited. Your first `route(A, B, R)` clause will always fail, won't it? There are no roads in your database with the same number that go both directions. Your second clause may have issues as well since you're requiring both routes to have the same number. If you want to generate a list, I would expect a base case or an initial predicate which has an empty list `[]`. – lurker Jun 08 '17 at 20:04
  • 3
    Do a search here on SO for something like, `[prolog] graph routes visited`. You'll find other questions related to this which will help get further. This sort of question has been covered many times here. – lurker Jun 08 '17 at 20:22
  • 1
    Your base case should be very simple. If there's already a road from `A` to `B`, then the route is a single element list consisting of the number for that road. – lurker Jun 08 '17 at 20:35
  • 1
    You might find [this question](https://stackoverflow.com/q/30328433/6101159) and the answers below interesting. – tas Jun 08 '17 at 23:25

2 Answers2

1

Thanks for the help! I did know the procedure, but i was finding difficult in appending the roads to the list, here's the final code:

road(1,a,b).
road(2,a,d).
road(3,b,c).
road(4,c,d).
road(5,b,e).
road(6,c,f).
road(7,d,f).
road(8,e,f).

route(X,Y,[R]) :- road(R,X,Y).
route(X,Y,[R1|R2]) :- road(R1,X,Z), route(Z,Y, R2).

Here's my desired output:

?- route(a,f,R).
R = [1, 3, 6] .

I was making a confusion in appending the list in the second definition of route, the examples helped me. Thanks for the help!!

RoxDan
  • 53
  • 1
  • 8
1

Your solution is still not resisting cycles in graph, here is once that keeps it in mind

route(A,A,R,R).
route(A,B,R,R2) :- road(Rx,A,C), \+ member(Rx,R) , route(C,B,[Rx|R],R2).
route(A,B,R) :- route(A,B,[],Rx), reverse(R,Rx).
Armatorix
  • 1,083
  • 10
  • 23