dongyu2300
2014-11-30 21:01D. B. Johnson的“基本电路”算法是否应产生不同的结果?
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条回答
为你推荐
- D. B. Johnson的“基本电路”算法是否应产生不同的结果?
- algorithm
- graph
- 1个回答