Search Paths on a Directed Graph

A directed graph with some nodes (from a to j) and some arcs connecting the nodes are defined.

This Prolog program can find out all paths between any two nodes. A path is a list of arcs that connects two nodes.

Source Code

---

/* Title : Directed Graph Searching Remarks : Define a directed graph and an algorithm to search routes between any two nodes in the graph. Reference : https://www.cpp.edu/~jrfisher/www/prolog_tutorial/2_15.html */ % define the arcs connecting the nodes % of a graph, the side(X,Y) is unidirectional % that is side(a,b) means a->b, but doesn't % automatically imply that b->a is true. side(a,b). side(a,d). side(b,e). side(b,c). side(d,c). side(e,f). side(c,h). side(c,g). side(f,g). side(f,i). side(i,g). side(g,h). side(g,j). side(h,j). side(d,h). % define the possible travelling % methods between any two nodes X and Y % 1. there is an arc connecting X and Y % directly. % 2. there is an arc connecting X and Z, % and there is a way to travel from % Z to Y. % Visited - the list for all visited nodes % Path - the list holding the sequence % of nodes from X to Y in a % reversed way. travel(X,Y,P,[Y|P]) :- side(X,Y). travel(X,Y,Visited,Path) :- side(X,Z), Z \== Y, \+member(Z,Visited), travel(Z,Y,[Z|Visited],Path). route(A,B,Path) :- travel(A,B,[A],PathReversed), reverse(PathReversed,Path). % print all items of a list, one item % for each line. printList([]) :- writeln(''). printList([H|T]) :- writeln(H), printList(T). % eg. % 1. To show all routes from a to i: % go(a,i). % 2. To find all routes that can go % to i: % go(X,i). % 3. To find all routes that can go % from a: % go(a,X). go(A,B) :- findall(P,route(A,B,P),PathList), printList(PathList).

Output

---

Run the script by swi-prolog, assume that the name of the script is graph02.pl.
# swipl graph02.pl /* find all paths from a to h */ ?- go(a,h). [a,b,e,f,g,h] [a,b,e,f,i,g,h] [a,b,c,h] [a,b,c,g,h] [a,d,h] [a,d,c,h] [a,d,c,g,h] true. /* find all paths that can go from e */ ?- go(e,X). [e,f] [e,f,g] [e,f,i] [e,f,g,h] [e,f,g,j] [e,f,g,h,j] [e,f,i,g] [e,f,i,g,h] [e,f,i,g,j] [e,f,i,g,h,j] true. /* find all paths that can go to g */ ?- go(X,g). [c,g] [f,g] [i,g] [a,b,e,f,g] [a,b,e,f,i,g] [a,b,c,g] [a,d,c,g] [b,e,f,g] [b,e,f,i,g] [b,c,g] [d,c,g] [e,f,g] [e,f,i,g] [f,i,g] true. ?-