了解 Donald B. Johnson 算法中的伪代码

Question

有谁知道 Donald B. Johnson 算法，它枚举了所有基本电路（循环） ）在有向图中？

我有他 1975 年发表的论文，但我看不懂伪代码。

我的目标是用 Java 实现这个算法。

例如，我有一些问题，它所指的矩阵 A_k 是什么。在伪代码中，它提到

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

这是否意味着我必须实现另一个算法来查找 A_k 矩阵？

还有一个问题就是下面这句话是什么意思？

begin logical f; 

“逻辑过程 CIRCUIT (整数值 v);”行是否也意味着电路过程返回一个逻辑变量？在伪代码中还有一行“CIRCUIT := f;”。这意味着什么？

如果有人可以将这个 1970 年代的伪代码翻译成更现代类型的伪代码，这样我就可以理解它，那就太好了。

如果您有兴趣提供帮助，但找不到这篇论文，请给我发电子邮件 [电子邮件受保护]，我会将论文发送给您。

Answer 1

伪代码让人想起 Algol、Pascal 或 Ada。

这是否意味着我必须实现另一种算法来查找 A_k 矩阵？

A_k 似乎是具有指定属性的输入值数组的列表。它可能与相应的邻接矩阵有关，但我不清楚。我猜是这样的：

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

逻辑f是什么意思？

这声明了一个代表 true 或 false 值的局部变量，类似于 Java 的 boolean。

逻辑过程CIRCUIT（整数值v）；

这声明了一个名为 CIRCUIT 的子程序，它具有按值传递的单个整数参数 v。子程序返回 true 或 false 的逻辑结果，并且 CIRCUIT := f 分配 f< /code> 作为结果。在Java中，

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

关键字begin和end界定了可以嵌套的块作用域，因此CIRCUIT嵌套在主块中，UNBLOCK 嵌套在 CIRCUIT 内部。 := 是赋值； Ø 是不是； ε 是元素； ∅ 为空； ≠是!=； stack和unstack建议push和pop。

这只是一个开始，但我希望它有所帮助。

附录：根据反思，A 和 B 必须是同构的。

这是一个非常字面的大纲。我对 A、B 和 A 的了解还不够。 V 选择比数组更好的数据结构。

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;
            }
        }
    }
}

Answer 2

您可以在 github 上找到该算法的 Java 实现：https://github.com/1123/johnson 。它使用 Jung2 java 图形库。