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

Question

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

javaalgorithmgraphcyclepseudocode

7

有人知道唐纳德·约翰逊(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程序返回一个逻辑变量？在伪代码中还有一行“CIRCUIT：= f;”。这是什么意思？

如果有人能够将这个1970年代的伪代码翻译成更现代化的伪代码，那就太好了。

如果您有兴趣提供帮助，但找不到这篇论文，请给我发送电子邮件至pitelk@hotmail.com，我会把论文发给您。

- C.LS

你有没有尝试阅读你提供的那篇论文？它似乎有附带的解释和证明。 - Aryabhatta

是的，我有看过，但它并没有解释代码本身，只是提供了一般的想法。我无法理解的是伪代码。此外，如果第一个链接无法使用，我已经找到了另一个论文链接。 http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf - C.LS

感谢大家，你们关注了我的问题外观（使其看起来更好；纠正拼写错误并将我编写的代码更改为论文原始代码 -出于某种奇怪的原因，我无法直接复制-粘贴代码，所以我从头开始打字）。 - C.LS

AK 指的是顶点集 VK 的诱导子图的边缘列表。Mathematica演示（和源代码）可在此处找到：http://demonstrations.wolfram.com/EnumeratingCyclesOfADirectedGraph/。 - István Zachar

2个回答

1

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

- user152468

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trashgod · Accepted Answer

伪代码让人想起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分配为结果。在Java中，

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

关键字 begin 和 end 用于限定一个可能被嵌套的块级作用域，因此 CIRCUIT 嵌套在主块中，而 UNBLOCK 则嵌套在 CIRCUIT 中。 := 表示赋值; ¬ 表示 not; ∈ 表示元素; ∅ 表示空; ≠ 表示 !=; stack 和 unstack 暗示了 push 和 pop。

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

补充说明：经过反思，A 和 B 必须同构。

这是一个非常字面的概述。我对 A、B 和 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;
            }
        }
    }
}