为图的指定节点打印图的所有循环，Prolog

Question

我是 Prolog 世界的新手。我正在尝试编写谓词以打印图形的指定节点的图形的所有循环，这是给定节点的元素。我的图表看起来像这样。

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

cycle(X) :-
    cycle(X, []).

cycle(Curr, Visited) :-
    member(Curr, Visited),
    !.
cycle(Curr, Visited) :-
    edge(Curr, Next),
    cycle(Next, [Curr|Visited]).

不幸的是，现在我找不到特定节点的循环。例如，我正在寻找节点 d.

的所有周期

Answer 1

我认为问题在于您 没有将任何逻辑写入 return 循环 。

源自节点的循环

这并不难，您已经使用了一个累加器，您只需要一种机制，一旦找到循环，return您的累加器就是循环。您可以通过向 cycle:

提供一个附加参数来做到这一点

cycle(Node,Cycle) :-
    cycle(Node,[],Cycle).

cycle(Curr,Visited,Cycle) :-
    member(Curr,Visited),
    !,
    reverse([Curr|Visited],Cycle).
cycle(Curr,Visited,Cycle) :-
    edge(Curr,Next),
    cycle(Next,[Curr|Visited],Cycle).

在此实现中，我使用了 reverse/2，因为这将为您提供正确的节点顺序 (edge-wise)。如果你对此不感兴趣（比如你只想分析循环，你可以反过来分析，你可以简单地将 cycle/3 第一个子句中的 Cycle 替换为 [Curr|Visited].

问题是，如果你调用这个谓词，它 returns:

?- cycle(d,Cycle).
Cycle = [d, c, b, a, e, d] ;
Cycle = [d, c, b, a, e, c] ;
Cycle = [d, a, e, d] ;
Cycle = [d, a, e, c, b, a].

因此，它不会搜索循环 ，其中 d 是循环 本身的一部分，它会搜索所有可以 源自 d。这可能不是你想要的。

给定节点的循环

但是您可以重写谓词：您将需要存储您的来源节点：

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

所以在这里我们寻找每个 edge/2 来自 Node 并且我们用初始 Node 调用 cycle/4 （检查我们何时找到一个循环）， Next 节点、已访问列表 [Node] 和 Cycle 参数到 return 找到的循环。

现在 cycle/4 有三个可能的选项：

我们到达了原节点，那么我们就找到了Node所在的环，我们做类似第一个版本的处理：
```
cycle(Curr,Curr,Visited,Cycle) :-
    !,
    reverse([Curr|Visited],Cycle).
```
我们到达一个我们已经访问过的节点：Curr是Visited的一个元素，那么我们需要中断搜索：否则我们将循环一个无限次数：
```
cycle(_,Curr,Visited,_) :-
    member(Curr,Visited),
    !,
    fail.
```
fail 是声明分支失败的谓词。这可能很有用，因为现在我们指定了失败的方式。

最后我们简单地访问了另一条边并试图找到下一个节点：

cycle(Node,Curr,Visited,Cycle) :-
    edge(Curr,Next),
    cycle(Node,Next,[Curr|Visited],Cycle).

完整版为：

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

cycle(Curr,Curr,Visited,Cycle) :-
    !,
    reverse([Curr|Visited],Cycle).
cycle(_,Curr,Visited,_) :-
    member(Curr,Visited),
    !,
    fail.
cycle(Node,Curr,Visited,Cycle) :-
    edge(Curr,Next),
    cycle(Node,Next,[Curr|Visited],Cycle).

生成：

?- cycle(d,Cycle).
Cycle = [d, c, b, a, e, d] ;
Cycle = [d, a, e, d] ;

因此都是从d开始，再次访问d的循环。我们可以通过在一个子句中压缩第二个和第三个场景来使代码更高效：

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

cycle(Curr,Curr,Visited,Cycle) :-
    !,
    reverse([Curr|Visited],Cycle).
cycle(Node,Curr,Visited,Cycle) :-
    \+ member(Curr,Visited),
    edge(Curr,Next),
    cycle(Node,Next,[Curr|Visited],Cycle).

其中 \+ 表示不是。

Answer 2

你要找的东西对我来说听起来像 transitive-closure...不需要重新发明轮子！

简单地建立在“Definition of a path/trail/walk”中显示的 tried-and-tested 代码之上并定义：

in_cycle(R_2, AZ, Path) :-                  % cf. "simple cycle"
   First = AZ,
   Last  = AZ,
   path(R_2, Path, First, ButLast),         % all "hops" but the last one ...
   call(R_2, ButLast, Last).                % ... and here comes the last one

示例查询 #1 使用 SICStus Prolog 4.3.2:

| ?- in_cycle(edge, d, Path).
Path = [d,c,b,a,e] ? ;
Path = [d,a,e] ? ;
no

在示例查询 #2 中，我们查看 edge/2 的 symmetric closure 的传递闭包：

| ?- in_cycle(symm(edge), d, Path).
Path = [d,c] ? ;
Path = [d,c,b,a] ? ;
Path = [d,c,b,a,e] ? ;
Path = [d,c,e] ? ;
Path = [d,c,e,a] ? ;
Path = [d,a] ? ;
Path = [d,a,e] ? ;
Path = [d,a,e,c] ? ;
Path = [d,a,b,c] ? ;
Path = [d,a,b,c,e] ? ;
Path = [d,e] ? ;
Path = [d,e,c] ? ;
Path = [d,e,c,b,a] ? ;
Path = [d,e,a] ? ;
Path = [d,e,a,b,c] ? ;
no

查询 #1 的所有解决方案也满足更一般的查询 #2 — 单调 Prolog^,2, 在工作： )

为图的指定节点打印图的所有循环，Prolog

Print all cycles of the graph for the specified node of the graph, Prolog

graph-theory

list

prolog

cycle

源自节点的循环

给定节点的循环