The pseudo-code is reminiscent of Algol, Pascal or Ada.
Does that mean I have to implement another algorithm that finds the Ak matrix?
Ak 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;
}
}
}
}
