Comprender el pseudocódigo en el algoritmo de Donald B. Johnson

Question

¿Alguien conoce el Donald B. Johnson's algorithm, que enumera todos los circuitos elementales (ciclos) en un dirigido gráfico?

Tengo el trabajo que publicó en 1975, pero no puedo entender el pseudocódigo.

Mi objetivo es implementar este algoritmo en Java.

Algunas preguntas que tengo, por ejemplo, es a qué se refiere la matriz A _k. En el pseudocódigo, se menciona que

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

¿Eso significa que tenga que implementar otro algoritmo que encuentra el _k matriz A?

Otra pregunta es ¿qué significa esto?

begin logical f; 

también lo hace la línea "logical procedure CIRCUIT (integer value v);" significa que el procedimiento devuelve un circuito variable lógica? En el pseudocódigo también tiene la línea "CIRCUIT := f;". ¿Qué significa esto?

Sería muy bueno si alguien podría traducirse pseudocódigo de este 1970 a un tipo más moderno de pseudocódigo para que pueda entenderlo

En caso de estar interesado para ayudar pero no se puede encontrar el documento, por favor envíeme un correo electrónico a pitelk @ hotmail.com y yo te enviaremos el documento.

Answer 1

El pseudo-código es una reminiscencia de Algol, Pascal o Ada.

¿Eso significa que tenga que implementar otro algoritmo que encuentra la A _k matriz?

A _k parece ser una lista de matrices de valores de entrada que tienen las propiedades especificadas. Puede estar relacionado con el adjacency matrix correspondiente, pero no está claro para mí. Supongo que algo como esto:

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

¿Qué significa logical f?

Esto declara una variable local que representa un valor true o false, similar a Java de boolean.

logical procedure CIRCUIT (integer value v);

Esto declara un subprograma llamado CIRCUIT que tiene un único parámetro entero v que se pasa por valor. El subprograma devuelve un resultado logical de true o false, y CIRCUIT := f asigna f como resultado.En Java,

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

Las palabras clave begin y end delimitan un ámbito de bloque que pueden anidarse, de modo CIRCUIT está anidado en el bloque principal y UNBLOCK está anidado dentro de CIRCUIT. := es asignación; ¬ es not; ∈ es un elemento; ∅ está vacío; ≠ es !=; stack y unstack sugieren push y pop.

Es solo el comienzo, pero espero que ayude.

Adición: En la reflexión, A y B debe ser isomorfo.

Aquí hay un esquema muy literal. No sé lo suficiente acerca de A, B & V para elegir una mejor estructura de datos que las matrices.

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

puede encontrar una implementación de Java de este algoritmo en github: https://github.com/1123/johnson. Utiliza la biblioteca de gráficos Jung2 java.