CODEWITHSUNDEEP
algorithmgraphgograph-theorygraph-algorithm
Greg
Greg

Reputation: 7922

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

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?

Upvotes: 2

Views: 1164

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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.

Upvotes: 2

Related Questions