 2014-11-30 21:01

# D. 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()

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

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 {
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条回答默认 最新

• douzhangshao6369 2014-11-30 21:20
已采纳

The redundant permutations are filtered out because the start node of each returned permutation is always less than all the remaining elements (under some ordering).

I suspect the problem is in a missing implementation of these steps:

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

and

s := least vertex in V;

These steps should ensure that the start of each permutation (s) is always less than the rest of the permutation but I cannot see code to implement this, instead you seem to loop through every node in the strongly connected component.

点赞 评论