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

有谁知道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; 

还行"logical procedure CIRCUIT (integer value v);" 意味着电路程序返回一个逻辑变量? 在伪代码中也有“ CIRCUIT := f; ”行。 这是什么意思?

如果有人能将这个1970年代的伪代码翻译成更现代的伪代码,那将是很棒的,所以我能理解它

如果您有兴趣提供帮助,但找不到纸张,请发送电子邮件至pitelk@hotmail.com,我会将纸张发给您。

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

这是否意味着我必须实现另一种找到A k矩阵的算法?

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

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

logical f是什么意思?

这声明了一个表示truefalse值的局部变量,类似于Java的boolean

logical procedure CIRCUIT (integer value v);

这声明了一个名为CIRCUIT的子程序,它具有一个由值传递的整数参数v 。 子程序返回truefalselogical结果, CIRCUIT := f指定f作为结果。 在Java中

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

关键字beginend分隔可以嵌套的块作用域,因此CIRCUIT嵌套在主块中, UNBLOCK嵌套在CIRCUIT:=是作业; ¬ not ; 是元素; 是空的; != ; stackunstack stack建议pushpop

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

附录:经过反思, AB必须是同构的。

这是一个非常字面的轮廓。 我不太了解ABV选择比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 stack = new Stack(); 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; } } } } 

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