help in the Donalds B. Johnson's algorithm, i cannot understand the pseudo code

Question

Hi , does anyone know the Donald B. Johnson's algorithm which enumerates all the elementary circuits (cycles) in a Directed graph? link text

I have the paper he had published in 1975 but I cannot understand the pseudo-code.

My goal is to implement this algorithm in Java.

Some questions I have is for example what is the matrix Ak it refers to. In the pseudo code mentions that

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

Does that mean I have to implement another algorithm that finds the Ak matrix?

Another question is what the following means?

begin logical f; 

Does also the line "logical procedure CIRCUIT (integer value v);" means that the circuit procedure returns a logical variable. In the pseudo code also has the line "CIRCUIT := f;" . Does this mean?

It would be great if someone could translate this 1970's pseudo code to a more modern type of pseudo code so I can understand it

in case you are interested to help but you cannot find the paper please email me at [email protected] and I will send you the paper.

Thanks in advance

Answer 1

The pseudo-code is reminiscent of Algol, Pascal or Ada.

Does that mean I have to implement another algorithm that finds the A_k matrix?

A_k appears to be a list of arrays of input values having the specified properties. It may be related to the corresponding adjacency matrix, but it's not clear to me. I'm guessing something like this:

int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;

What does logical f mean?

This declares a local variable representing a true or false value, similar to Java's boolean.

logical procedure CIRCUIT (integer value v);

This declares a subprogram named CIRCUIT having a single integer parameter v that is passed by value. The subprogram returns a logical result of true or false, and CIRCUIT := f assigns f as the result. In Java,

boolean circuit(int v) {
    boolean f;
    ...
    f = false;
    ...
    return f;
}

The keywords begin and end delimit a block scope that may be nested, so CIRCUIT is nested in the main block and UNBLOCK is nested inside of CIRCUIT. := is assignment; ¬ is not; ∈ is element; ∅ is empty; ≠ is !=; stack and unstack suggest push and pop.

It's only a start, but I hope it helps.

Addendum: On reflection, A and B must be isomorphic.

Here's a very literal outline. I don't know enough about A, B & V to choose a better data structure than arrays.

import java.util.Stack;

public final class CircuitFinding {
    static int k, n;
    int[][] a = new int[k][n];
    int[][] b = new int[k][n];
    boolean[] blocked = new boolean[n];
    int[] v = new int[k];
    int s = 1;
    Stack<Integer> stack = new Stack<Integer>();

    private void unblock(int u) {
        blocked[u] = false;
        for (int w : b[u]) {
            //delete w from B(u)
            if (blocked[w]) {
                unblock(w);
            }
        }
    }

    private boolean circuit(int v) {
        boolean f = false;
        stack.push(v);
        blocked[v] = true;
        L1:
        for (int w : a[v]) {
            if (w == s) {
                //output circuit composed of stack followed by s;
                f = true;
            } else if (!blocked[w]) {
                if (circuit(w)) {
                    f = true;
                }
            }
        }
        L2:
        if (f) {
            unblock(v);
        } else {
            for (int w : a[v]) {
                //if (v∉B(w)) put v on B(w);
            }
        }
        v = stack.pop();
        return f;
    }

    public void main() {
        while (s < n) {
            //A:= adjacency structure of strong component K with least
            //vertex in subgraph of G induced by {s, s+ 1, n};
            if (a[k] != null) {
                //s := least vertex in V;
                for (int i : v) {
                    blocked[i] = false;
                    b[i] = null;
                }
                L3:
                circuit(s);
                s++;
            } else {
                s = n;
            }
        }
    }
}