Finding a path along a Prolog path with a circular path
I am a complete newbie to Prolog. I am trying to figure out a problem where I need to check if a path exists between edges. I ended up with an acyclic graph code for a circular code that swaps an infinite loop.
path(Start, End) :- edge(Start, End).
path(Start, End) :- edge(Start, Z), path(Z, End).
I need to handle this case by setting a new predicate: new_path (Start, End, path) which should eliminate the infinite loop. Please let me know how to do this.
+3
source to share
2 answers
You need to keep track of which nodes you've visited as you walk through using the prologue list as a LIFO stack. Something like this:
path( A , Z , P ) :- % to find a path from A to Z
traverse( A , Z , [] , P ) , % take a walk, visiting A to see if we can get to Z, seeding the visited list with the empty string.
reverse(P,Path) % once we find a path, let reverse it, since it in LIFO order.
. % That all there is to it, really.
traverse( Z , Z , V , [Z|V] ) % if current node is the destination node, we've arrived.
. % - just push the destination vertice onto the visited list and unify that with the path
traverse( A , Z , V , P ) :- % Otherwise...
edge( A , Z ) , % - if the current node is directly connected to the destination node,
traverse( Z , Z , [A|V] , P) % - go visit the destination, marking the current node as visited
. %
traverse( A, Z , V , P ) :- % Otherwise...
A \= Z,
edge( A , B ) , % - if the current node is connected to a node
B \= Z , % - that is not the destination node, and
unvisited([A|V],B) , % - we have not yet visited that node,
traverse( B , Z , [A|V] , P ) % - go visit the intermediate node, marking the current node as visited.
. % Easy!
unvisited( [] , _ ) . % We succeed if the visited list is empty.
unvisited( [A|_] , A ) :- ! , fail . % We fail deterministically if we find the node in the visited list.
unvisited( [_|L] , A ) :- unvisited(L,A) . % otherwise, we keep looking.
+1
source to share