It works! In an earlier iteration of the Johnson algorithm, I had supposed that A
was an adjacency matrix. Instead, it appears to represent an adjacency list. In that example, implemented below, the vertices {a, b, c} are numbered {0, 1, 2}, yielding the following circuits.
Addendum: As noted in this proposed edit and helpful answer, the algorithm specifies that unblock()
should remove the element having the value w
, not the element having the index w
.
list.remove(Integer.valueOf(w));
Sample output:
0 1 0 0 1 2 0 0 2 0 0 2 1 0 1 0 1 1 0 2 1 1 2 0 1 1 2 1 2 0 1 2 2 0 2 2 1 0 2 2 1 2
By default, the program starts with s = 0
; implementing s := least vertex in V
as an optimization remains. A variation that produces only unique cycles is shown here.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* @see http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
* @see https://stackoverflow.com/questions/2908575
* @see https://stackoverflow.com/questions/2939877
* @see http://en.wikipedia.org/wiki/Adjacency_matrix
* @see http://en.wikipedia.org/wiki/Adjacency_list
*/
public final class CircuitFinding {
final Stack<Integer> stack = new Stack<Integer>();
final List<List<Integer>> a;
final List<List<Integer>> b;
final boolean[] blocked;
final int n;
int s;
public static void main(String[] args) {
List<List<Integer>> a = new ArrayList<List<Integer>>();
a.add(new ArrayList<Integer>(Arrays.asList(1, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 1)));
CircuitFinding cf = new CircuitFinding(a);
cf.find();
}
/**
* @param a adjacency structure of strong component K with
* least vertex in subgraph of G induced by {s, s + 1, n};
*/
public CircuitFinding(List<List<Integer>> a) {
this.a = a;
n = a.size();
blocked = new boolean[n];
b = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
b.add(new ArrayList<Integer>());
}
}
private void unblock(int u) {
blocked[u] = false;
List<Integer> list = b.get(u);
for (int w : list) {
//delete w from B(u);
list.remove(Integer.valueOf(w));
if (blocked[w]) {
unblock(w);
}
}
}
private boolean circuit(int v) {
boolean f = false;
stack.push(v);
blocked[v] = true;
L1:
for (int w : a.get(v)) {
if (w == s) {
//output circuit composed of stack followed by s;
for (int i : stack) {
System.out.print(i + " ");
}
System.out.println(s);
f = true;
} else if (!blocked[w]) {
if (circuit(w)) {
f = true;
}
}
}
L2:
if (f) {
unblock(v);
} else {
for (int w : a.get(v)) {
//if (v∉B(w)) put v on B(w);
if (!b.get(w).contains(v)) {
b.get(w).add(v);
}
}
}
v = stack.pop();
return f;
}
public void find() {
while (s < n) {
if (a != null) {
//s := least vertex in V;
L3:
circuit(s);
s++;
} else {
s = n;
}
}
}
}