理解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
是什么意思?
这声明了一个表示true
或false
值的局部变量,类似于Java的boolean
。
logical procedure CIRCUIT (integer value v);
这声明了一个名为CIRCUIT
的子程序,它具有一个由值传递的整数参数v
。 子程序返回true
或false
的logical
结果, CIRCUIT := f
指定f
作为结果。 在Java中
boolean circuit(int v) { boolean f; ... f = false; ... return f; }
关键字begin
和end
分隔可以嵌套的块作用域,因此CIRCUIT
嵌套在主块中, UNBLOCK
嵌套在CIRCUIT
。 :=
是作业; ¬
not
; ∈
是元素; ∅
是空的; ≠
是!=
; stack
和unstack
stack
建议push
和pop
。
这只是一个开始,但我希望它有所帮助。
附录:经过反思, A
和B
必须是同构的。
这是一个非常字面的轮廓。 我不太了解A
, B
和V
选择比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图形库。