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?