Enumerating all walks in a graph

Question

Given a term representation of an edge of a graph, i.e.:

edge(a, b).
edge(b, c).

I would like to construct a predicate path/1 which succeeds iff its sole argument is a valid path in this graph (that is, for every two adjacent terms X, Y, edge(X, Y) holds). Given a variable, it should enumerate all walks (which could have repeated nodes). My first try:

path([X, Y]) :- edge(X, Y).
path([X, Y, Z | T]) :-
  path([Y, Z | T]),
  edge(X, Y).

It works as intended except for the case where it is supplied an acyclic graph - path finds all solutions and then halts, unable to construct any other path. On the other hand, swapping first and second term will result in many walks being skipped, due to the DFS nature of Prolog resolution.

My second attempt:

path(P) :- length(P, L), L >= 2, (path(P, L) *-> true ; (!, fail)).

path([X, Y], 2) :- edge(X, Y).
path([X, Y, Z | T], L) :-
  L >= 3,
  L1 is L - 1,
  edge(X, Y),
  path([Y, Z | T], L1).

It works as intended, but using a soft cut feels a bit forced. I was wondering if there was an easier way to accomplish this, perhaps a simpler simulation of a soft cut is possible in this particular scenario?

You need to remember the paths visited and not visit the visited paths. — Guy Coder, May 31 '19 at 17:05
See [this](https://stackoverflow.com/q/26946133/772868) for a general solution. — false, May 31 '19 at 20:10

score 0 · Answer 1 · answered May 31 '19 at 17:10

Testing your first solution, after finding three paths ([a,b],[a,c],[a,b,c]), it loops. One super quick way to avoid this is to use tabling wich is available in XSB, SWI and YAP. In case of SWI just add :- table path/1. as first directive to avoid loops. Otherwise you need to remember all path and there are plenty of answers you can look at (like this).

Nicholas Carey · Answer 2 · 2019-05-31T23:49:44.277

0

Given your graph definition:

edge(a, b).
edge(b, c).

Something like ought to do you:

path(P) :-
  node(X),
  walk(X,_,P)
  .

walk(A,B,P) :-
  walk(A,B,[],V),
  reverse(V,R),
  P = [A|R]
  .               

walk( A, B, T, V ) :-
  edge(A,X),              
  not( member(X,T) ),
  (
    ( B = X , V = [B|T] )
  ;
    walk( X, B, [A|T], V )
  )
  . 

%
% enumerate the distinct nodes in edge/2 via backtracking
%
node(N) :-
  setof( X , edge(X,_);edge(_,X) , Ns ),
  node( Ns , N )
  .

node( [N|_] , N ).
node( [_|Ns] , N ) :- ( Ns , N ).

edited May 31 '19 at 23:49

answered May 31 '19 at 23:40

Nicholas Carey

71,308
16
93
135

I assume `node( [_|Ns] , N ) :- ( Ns , N ).` was supposed to be `node( [_|Ns] , N ) :- node( Ns , N ).`. It doesn't work as intended, try it with `edge(a, b). edge(b, c)`. One of the answers is `[a, a, c]` – shooqie Jun 01 '19 at 09:00

Enumerating all walks in a graph

2 Answers2