Den Pseudocode im Algorithmus von Donald B. Johnson verstehen - Java, Algorithmus, Graph, Zyklus, Pseudocode

Kennt jemand das Donald B. Johnsons Algorithmus, die alle Elementarschaltungen (Zyklen) in a auflistet gerichtet Graph?

Ich habe das Papier, das er 1975 veröffentlicht hatte, aber ich kann den Pseudocode nicht verstehen.

Mein Ziel ist es, diesen Algorithmus in Java zu implementieren.

Einige Fragen, die ich habe, sind zum Beispiel die Matrix A_k es bezieht sich auf. Im Pseudocode wird das erwähnt

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

Bedeutet das, dass ich einen anderen Algorithmus implementieren muss, der das A findet_k Matrix?

Eine andere Frage ist, was das Folgende bedeutet?

begin logical f;

Hat auch die Leitung "logical procedure CIRCUIT (integer value v);" bedeutet, dass die Schaltungsprozedur eine logische Variable zurückgibt? Im Pseudocode steht auch die Zeile "CIRCUIT := f;". Was bedeutet das?

Es wäre großartig, wenn jemand den Pseudocode der 1970er Jahre in einen moderneren Pseudocode-Typ übersetzen könnte, damit ich ihn verstehen kann

Falls Sie Interesse haben, das Papier nicht zu finden, senden Sie mir bitte eine E-Mail an pitelk@hotmail.com.

Antworten:

7 für die Antwort № 1

Der Pseudo-Code erinnert an Algol, Pascal oder Ada.

Bedeutet das, dass ich einen anderen Algorithmus implementieren muss, der das A findet_k Matrix?

EIN_k scheint eine Liste von Feldern von Eingabewerten zu sein, die die angegebenen Eigenschaften haben. Es kann sich auf das entsprechende beziehen Adjazenzmatrix, aber es ist mir nicht klar.

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

Was macht logical f bedeuten?

Dies deklariert eine lokale Variable, die a darstellt true oder false Wert, ähnlich wie bei Java boolean.

logical procedure CIRCUIT (integer value v);

Dies deklariert ein Unterprogramm namens CIRCUIT mit einem einzigen ganzzahligen Parameter v das wird von Wert übergeben. Das Unterprogramm gibt a zurück logical Ergebnis von true oder false, und CIRCUIT := f vergibt f als Ergebnis. In Java

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

Die Schlüsselwörter begin und end begrenzen Sie einen Blockbereich, der verschachtelt sein kann CIRCUIT ist im Hauptblock verschachtelt und UNBLOCK ist innerhalb von verschachtelt CIRCUIT. := ist eine Zuordnung; ¬ ist not; ∈ ist Element; ∅ ist leer; ≠ ist !=; stack und unstack vorschlagen push und pop.

Es ist nur ein Anfang, aber ich hoffe es hilft.

Nachtrag: Zum Nachdenken, A und B muss isomorph sein.

Hier ist ein sehr wörtlich Gliederung. Ich weiß nicht genug darüber A, B & V eine bessere Datenstruktur als Arrays wählen.

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

---

1 für die Antwort № 2

Eine Java-Implementierung dieses Algorithmus finden Sie auf github: https://github.com/1123/johnson. Es benutzt die Jung2 Java Graph Library.

---