Понимание псевдокода в алгоритме Дональда Б. Джонсона

Question

Кто-нибудь знает Donald B. Johnson's algorithm, который перечисляет все элементарные схемы (циклы) в ??

У меня есть документ, который он опубликовал в 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 _к матрицы?

Другой вопрос: что означает следующее?

begin logical f; 

ли также линии "logical procedure CIRCUIT (integer value v);" означает, что процедура схема возвращает логическую переменную? В псевдокоде также есть строка «CIRCUIT := f;». Что это значит?

Было бы здорово, если бы кто-то мог бы перевести этот 1970-х годов псевдокод на более современный тип псевдокоде, так что я могу понять это

В случае, если вы заинтересованы, чтобы помочь, но вы не можете найти бумагу, пожалуйста, напишите мне на pitelk @ hotmail.com, и я пришлю вам статью.

Answer 1

Псевдокод напоминает Алгол, Паскаль или Аду.

Означает ли это, что я должен реализовать другой алгоритм, который находит A _к матрицы?

_к, как представляется, список массивов входных значений, имеющих указанные свойства. Он может быть связан с соответствующим adjacency matrix, но мне это непонятно.

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, который передается по значению. Подпрограмма возвращает logical результат true или false, а CIRCUIT := f присваивает f результат.В Java

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

Ключевые слова begin и end ограничивают объем блока, которые могут быть вложенными, так CIRCUIT вложен в главном блоке и UNBLOCK вложен внутрь CIRCUIT. := - присвоение; ¬ - not; ∈ - элемент; ∅ пуст; ≠ - !=; stack и unstack предлагают push и pop.

Это только начало, но я надеюсь, что это поможет.

Приложение: при отражении A и B должны быть изоморфными.

Вот очень буквально контур. Я не знаю достаточно о A, B & V, чтобы выбрать лучшую структуру данных, чем массивы.

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

Вы можете найти реализацию Java этого алгоритма на GitHub: https://github.com/1123/johnson. Он использует библиотеку java-диаграммы Jung2.