dimanche 30 novembre 2014

Should D. B. Johnson's "elementary circuits" algorithm produce distinct results?


Vote count:

0




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"
"http://github.com/gyuho/goraph/algorithm/scc/tarjan"
"http://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, 20)
gr.Connect(b, c, 20)
gr.Connect(c, a, 20)

gr.Connect(d, e, 20)
gr.Connect(e, f, 20)
gr.Connect(f, d, 20)

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?



asked 1 min ago

Greg

3,254






Should D. B. Johnson's "elementary circuits" algorithm produce distinct results?

Aucun commentaire:

Enregistrer un commentaire