Понимание псевдокода в алгоритме Donald B. Johnson
Кто-либо знает алгоритм Donald B. Johnson, который перечисляет все элементарные схемы (циклы) в ориентированном графе?
У меня есть работа, которую он опубликовал в 1975, но я не могу понять псевдокод.
Моя цель состоит в том, чтобы реализовать этот алгоритм в Java.
Некоторые вопросы, которые я имею, например, то, что является матричным Ak, к которому это относится. В псевдокоде это упоминает это
Ak:=adjacency structure of strong component K with least
vertex in subgraph of G induced by {s,s+1,....n};
Это означает, что я должен реализовать другой алгоритм, который находит матрицу Ak?
Другой вопрос что следующие средства?
begin logical f;
Делает также строку "logical procedure CIRCUIT (integer value v);" подразумевайте, что процедура схемы возвращает логическую переменную? В псевдокоде также имеет строку"CIRCUIT := f;". Что это означает?
Было бы замечательно, если кто-то мог бы перевести этот псевдокод 1970-х в более современный тип псевдокода, таким образом, я могу понять это
В случае, если Вам интересно помогать, но Вы не можете найти бумагу, пошлите мне по электронной почте по pitelk@hotmail.com, и я отправлю Вам бумагу.
1 ответ
Псевдокод напоминает Алгол, Паскаль или Аду.
Означает ли это, что мне нужно реализовать другой алгоритм, который находит матрицу A k ?
A k выглядит как список массивов входных значений с указанными свойствами . Это может быть связано с соответствующей матрицей смежности , но мне это не ясно. Я предполагаю что-то вроде этого:
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;
Что означает
логическое f?
Это объявляет локальную переменную, представляющую значение true или false , аналогичен логическому логическому в Java.
логическая процедура CIRCUIT (целочисленное значение v);
Объявляет подпрограмму с именем CIRCUIT , имеющую единственный целочисленный параметр v , который передается по значению. Подпрограмма возвращает логический результат истина или ложь , а CIRCUIT: = f назначает f как результат. В Java
boolean circuit(int v) {
boolean f;
...
f = false;
...
return f;
}
ключевые слова begin и end ограничивают область действия блока, которая может быть вложенной, поэтому CIRCUIT вложена в основной блок, а РАЗБЛОКИРОВКА вложена в ЦЕПЬ . : = - присвоение; ¬ равно не ; ∈ - элемент; ∅ пусто; ≠ равно ! = ; стек и 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;
}
}
}
}