从顶点到所有其他可达节点的所有简单路径

Question

我对 Prolog 完全陌生，正在研究图表。我在网上发现一个问题，要求我指定一个节点，然后列出从该节点可达的所有简单路径。没有目标节点，只需尝试所有可能性和 return 所有这些路径。

我将图形表示为路径 (X, Y)，表示从 X 到 Y 的有向边。

我建立了这个循环的简单知识库：

path(a, b).
path(b, c).
path(c, d).
path(d, a).
path(d, e).
path(d, f).
path(f, g).

如果我查询 all_paths(a, P)，那么 P 应该是（假设 ; 是垃圾邮件，直到所有选项都用完）。

P = [a].
P = [a, b].
P = [a, b, c].
P = [a, b, c, d].
P = [a, b, c, d, e].
P = [a, b, c, d, f].
P = [a, b, c, d, f, g].

作为开场白我写了类似的东西：

all_paths(Source, P) :- all_paths(Source, P, []).
all_paths(_, [], _).
all_paths(Source, [Source | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Node | Visited]).

好的，稍微修改一下，现在我回来了：

X = [] ? ;
X = [a] ? ;
X = [a,b] ? ;
X = [a,b,c] ? ;
X = [a,b,c,d] ? ; <- Here it does not pick up e
X = [a,b,c,d] ? ;
X = [a,b,c,d] ? ;
X = [a,b,c,d,f] ? ;

有人可以帮忙弄清楚如何正确获取所有路径吗？

Answer 1

无需重新发明轮子！

首先，我们将您的谓词 path/2 重命名为 edge/2:

edge(a, b).
edge(b, c).
edge(c, d).
edge(d, a).
edge(d, e).
edge(d, f).
edge(f, g).

然后，我们将meta-predicate path/4与edge/2结合使用：

?- path(edge,Path,From,To).
  Path = [To],          From = To
; Path = [a,b],         From = a, To = b
; Path = [a,b,c],       From = a, To = c
; Path = [a,b,c,d],     From = a, To = d
; Path = [a,b,c,d,e],   From = a, To = e
; Path = [a,b,c,d,f],   From = a, To = f
; Path = [a,b,c,d,f,g], From = a, To = g
; Path = [b,c],         From = b, To = c
; Path = [b,c,d],       From = b, To = d
; Path = [b,c,d,a],     From = b, To = a
; Path = [b,c,d,e],     From = b, To = e
; Path = [b,c,d,f],     From = b, To = f
; Path = [b,c,d,f,g],   From = b, To = g
; Path = [c,d],         From = c, To = d
; Path = [c,d,a],       From = c, To = a
; Path = [c,d,a,b],     From = c, To = b
; Path = [c,d,e],       From = c, To = e
; Path = [c,d,f],       From = c, To = f
; Path = [c,d,f,g],     From = c, To = g
; Path = [d,a],         From = d, To = a
; Path = [d,a,b],       From = d, To = b
; Path = [d,a,b,c],     From = d, To = c
; Path = [d,e],         From = d, To = e
; Path = [d,f],         From = d, To = f
; Path = [d,f,g],       From = d, To = g
; Path = [f,g],         From = f, To = g
; false.

编辑

如果我们只对从 a 开始的路径感兴趣，我们只需写：

?- path(edge,Path,a,To).
  Path = [a],                To = a
; Path = [a, b],             To = b
; Path = [a, b, c],          To = c
; Path = [a, b, c, d],       To = d
; Path = [a, b, c, d, e],    To = e
; Path = [a, b, c, d, f],    To = f
; Path = [a, b, c, d, f, g], To = g
; false.

Answer 2

'swapping' 节点和来源

all_paths(_, [], _).
all_paths(Source, [Node | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Source | Visited]).

产量

?- all_paths(a, P).
P = [] ;
P = [b] ;
P = [b, c] ;
P = [b, c, d] ;
P = [b, c, d, e] ;
P = [b, c, d, f] ;
P = [b, c, d, f, g] ;
false.

它缺少起始节点，我只需在 'driver' 谓词中添加：

all_paths(Source, [Source|P]) :- all_paths(Source, P, []).

产量

?- all_paths(a, P).
P = [a] ;
P = [a, b] ;
P = [a, b, c] ;
P = [a, b, c, d] ;
P = [a, b, c, d, e] ;
P = [a, b, c, d, f] ;
P = [a, b, c, d, f, g] ;
false.

风格说明：如果我们遵循一些关于 IO 参数的规则，代码将更具可读性。输出参数应该在输入参数之后。好吧，这并不总是适用...

从顶点到所有其他可达节点的所有简单路径

All simple paths from a vertex to all other reachable nodes

prolog

graph-theory

transitive-closure

编辑