algorithm - D. B. Johnson 的 "elementary circuits"算法应该产生不同的结果吗？

Question

Johnson's paper首先在有向图中描述不同的基本电路(简单循环):

A circuit is elementary if no vertex but the first and last appears twice. Two elementary circuits are distinct if one is not a cyclic permutation of the other. There are c distinct elementary circuits in G

我试图拼凑出一些隐约类似于伪代码的东西，有点严重欺骗 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]]

图论对我来说是一个充满魔力的阴森、黑暗的森林，所以我不确定我错过了什么。我是不是看错报纸了？这是否意味着应该以其他方式过滤掉冗余排列？我是否搞砸了代码？

Answer 1

冗余排列被过滤掉，因为每个返回排列的起始节点始终小于所有剩余元素(在某种排序下)。

我怀疑问题在于缺少执行这些步骤:

AK:= adjacency structure of strong component K with least vertex in subgraph of G induced by {s, s+ 1, n};

和

s := least vertex in V;

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