Verständnis der Pseudocode in der Donald B. Johnson-Algorithmus

Question

Kennt jemand die Donald B. Johnson's algorithm, die alle elementaren Schaltungen (Zyklen) in einem gerichteten Graphen zählt?

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, zum Beispiel ist, was ist die Matrix A _k es bezieht sich auf. In der Pseudo-Code, erwähnt sie, dass

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

Heißt das, ich habe einen anderen Algorithmus implementieren, die die A _k Matrix findet?

Eine andere Frage ist, was das Folgende bedeutet?

begin logical f; 

Hat auch die Linie "logical procedure CIRCUIT (integer value v);" bedeutet, dass die Schaltung vor, um eine logische Variable gibt? Im Pseudocode hat auch die Zeile "CIRCUIT := f;". Was bedeutet das?

Es wäre toll, wenn jemand dies 1970 Pseudo-Code zu einer moderneren Art von Pseudo-Code übersetzen könnte, damit ich es

Bei verstehen kann Sie daran interessiert sind zu helfen, aber man kann das Papier nicht finden Sie mir bitte an pitelk E-Mail @ hotmail.com und ich werde dir das Papier schicken.

Answer 1

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

Heißt das, ich einen anderen Algorithmus zu implementieren, die die A _k Matrix findet?

A _k erscheint eine Liste von Anordnungen von Eingangswerten die angegebenen Eigenschaften zu sein. Es kann mit dem entsprechenden adjacency matrix verwandt sein, aber es ist mir nicht klar. Ich vermute, so etwas wie dieses:

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

Was bedeutet logical f bedeuten?

Dies erklärt eine lokale Variable boolean einen true oder false Wert, ähnlich wie Java darstellt.

logical procedure CIRCUIT (integer value v);

Dies erklärt ein Unterprogramm CIRCUIT mit einem einzigen Integer-Parametern namens v, die von Wert übergeben wird. Das Unterprogramm liefert als Ergebnis ein logical Ergebnis von true oder false, und CIRCUIT := f weist f zu.In Java

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

Die Schlüsselwörter begin und end begrenzen einen Block Umfang, die verschachtelt werden können, so ist CIRCUIT im Hauptblock verschachtelt und UNBLOCK innerhalb von CIRCUIT verschachtelt. := ist Zuweisung; ¬ ist not; ∈ ist Element; ∅ ist leer; ≠ ist !=; stack und unstack schlagen push und pop vor.

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

Nachtrag: Nach der Reflexion müssen A und B isomorph sein.

Hier ist ein sehr wörtlich Gliederung. Ich weiß nicht genug über A, B & V, um eine bessere Datenstruktur als Arrays zu 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; 
      } 
     } 
    } 
} 

Answer 2

Sie können eine Java-Implementierung dieses Algorithmus auf Github finden: https://github.com/1123/johnson. Es verwendet die Jung2-Java-Graph-Bibliothek.