dongyu2300
dongyu2300
2014-11-30 21:01

D. B. Johnson的“基本电路”算法是否应产生不同的结果?

  • graph
  • algorithm

Johnson's paper starts out describing distinct elementary circuits (simple cycles) in a directed graph:

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

I tried to cobble together something vaguely resembling the pseudo code, kind of badly cheating off of networkx and this Java implementation. I am apparently not getting distinct elementary circuits.

This is my code. It uses the goraph library, but doesn't really do too much with it, besides getting strongly connected components.

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

This is the output:

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

Graph theory is a spooky, dark forest full of magic for me, so I'm not sure what I'm missing. Am I misreading the paper? Is it implied that redundant permutations should be filtered out some other way? Did I screw up the code?

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答