algorithm - D. B. Johnson的 “elementary circuits”算法是否应该产生不同的结果？

Johnson's paper开始在有向图中描述不同的基本电路(简单周期):



我试图拼凑一些模糊不清的类似于伪代码的东西，这是对networkx和此Java implementation的严重欺骗。我显然没有得到明显的基本电路。

这是我的代码。它使用了goraph library，但是除了获得紧密连接的组件之外，实际上并没有做太多的事情。

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
            }
        }
    }

    if closed {
        unblock(thisNode)
    } else {
        adj = g.FindVertexByID(string(thisNode)).GetOutVertices().GetElements()
        for _, next := range adj {
            nextNode := node(next.(*gs.Vertex).ID)
            inB := false
            for _, v := range B[nextNode] {
                if v == thisNode {
                    inB = true
                }
            }
            if !inB {
                B[nextNode] = append(B[nextNode], thisNode)
            }
        }
    }
    path = path[:len(path)-1]
    return closed
}

func unblock(thisNode node) {
    stack := []node{thisNode}
    for len(stack) > 0 {
        n := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if blocked[n] {
            blocked[n] = false
            stack = append(stack, B[n]...)
            B[n] = []node{}
        }
    }
}

这是输出:

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

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

最佳答案

因为每个返回的排列的开始节点始终小于所有其余元素(按某种顺序排列)，所以冗余排列被滤除。

我怀疑问题出在这些步骤的缺失实现中:



和



这些步骤应确保每个排列的开始始终小于其余排列的开始，但是我看不到实现此目的的代码，相反，您似乎遍历了紧密连接的组件中的每个节点。