DB Johnson 的“基本电路”算法是否应该产生不同的结果？

Question

开始在有向图中描述不同的基本电路（简单循环）：

如果没有顶点但第一个和最后一个出现两次，则电路是基本的。如果一个不是另一个的循环置换，则两个基本电路是不同的。G中有c个不同的基本电路

我试图拼凑出一些类似于伪代码的东西，有点严重欺骗了networkx和这个Java 实现。我显然没有得到不同的基本电路。

这是我的代码。它使用goraph 库，但除了获得强连接组件之外，并没有真正用它做太多事情。

package main

import (

    "fmt"

    "github.com/gyuho/goraph/algorithm/scc/tarjan"

    "github.com/gyuho/goraph/graph/gs"

)

func main() {

    gr := gs.NewGraph()

    a := gr.CreateAndAddToGraph("A")

    b := gr.CreateAndAddToGraph("B")

    c := gr.CreateAndAddToGraph("C")

    d := gr.CreateAndAddToGraph("D")

    e := gr.CreateAndAddToGraph("E")

    f := gr.CreateAndAddToGraph("F")

    gr.Connect(a, b, 1)

    gr.Connect(b, c, 1)

    gr.Connect(c, a, 1)

    gr.Connect(d, e, 1)

    gr.Connect(e, f, 1)

    gr.Connect(f, d, 1)

    sccs := tarjan.SCC(gr) // returns [][]string

    for _, scc := range sccs {

        if len(scc) < 3 {

            continue

        }

        for _, v := range scc {

            n := node(v)

            circuit(n, n, gr)

        }

    }

    fmt.Println(result)

}

type node string

var blocked = make(map[node]bool)

var B = make(map[node][]node)

var path []node

var result [][]node

func circuit(thisNode node, startNode node, g *gs.Graph) bool {

    closed := false

    path = append(path, thisNode)

    blocked[thisNode] = true

    adj := g.FindVertexByID(string(thisNode)).GetOutVertices().GetElements()

    for _, next := range adj {

        nextNode := node(next.(*gs.Vertex).ID)

        if nextNode == startNode {

            cycle := []node{}

            cycle = append(cycle, path...)

            cycle = append(cycle, startNode)

            result = append(result, cycle)

            closed = true

        } else if !blocked[nextNode] {

            if circuit(nextNode, startNode, g) {

                closed = true

            }

        }

    }

这是输出：

[[C A B C] [B C A B] [A B C A] [F D E F] [E F D E] [D E F D]]

图论对我来说是一个充满魔力的幽灵般的黑暗森林，所以我不确定我错过了什么。我误读了报纸吗？是否暗示应该以其他方式过滤掉多余的排列？我搞砸了代码吗？

Answer 1

多余的排列被过滤掉，因为每个返回排列的起始节点总是小于所有剩余元素（在某种排序下）。我怀疑问题在于缺少这些步骤的实现：AK:=由{s,s+1,n}诱导的G子图中顶点最少的强分量K的邻接结构；和s := V 中的最小顶点；这些步骤应该确保每个排列的开始总是小于排列的其余部分，但我看不到实现这一点的代码，相反，您似乎遍历了强连接组件中的每个节点。