я не могу понять определенную часть работы, опубликованной Donald Johnson о нахождении циклов (Схемы) в графике.
Более конкретный я не могу понять то, что является матричным Ak, который упоминается в следующей строке псевдо кода:
Ak: = структура смежности сильного компонента K с наименьшим количеством вершины в подграфе G, вызванного {s, s+1.... n};
ко всем неприятностям некоторые строки после являются mentins, "поскольку я в Vk делаю", не объявляя, каков Vk...
Поскольку далеко я имею, понимают, что у нас есть следующее: 1) в целом сильный компонент является подграфом графика, в который для каждого узла этого подграфа существует путь к любому узлу подграфа (другими словами, можно получить доступ к любому узлу подграфа от любого другого узла подграфа),
2) подграф, вызванный списком узлов, является графиком, содержащим все эти узлы плюс все края, соединяющие эти узлы. в газете математическое определение "F, подграф G, вызванного W, если W является подмножеством V и F = (W, {u, y) |u, y в W и (u, y) в E)}), где u, y являются краями, E является набором всех краев в графике, W является рядом узлов.
3) в реализации кода узлы называют целые числа 1... n.
4) Я подозреваю, что Vk является набором узлов сильного компонента K.
теперь к вопросу. Позволяет говорят, что у нас есть график G = (V, E) с V = {1,2,3,4,5,6,7,8,9}, который он может быть разделен на 3 сильных компонента SC1 = {1,4,7,8} SC2 = {2,3,9} SC3 = {5,6} (и их края)
Кто-либо может дать мне пример для s =1, s = 2, s = 5 что при попытке быть Vk и Ak согласно коду?
Псевдо код находится в моем предыдущем вопросе в Понимании псевдокода в алгоритме Donald B. Johnson
и статья может быть найдена в Understanding псевдокод в алгоритме Donald B. Johnson
заранее спасибо
Это работает! В предыдущей итерации алгоритма Джонсона я предполагал, что A
- это матрица смежности. Вместо этого оказалось, что она представляет собой список смежности. В этом примере, реализованном ниже, вершины {a, b, c} пронумерованы {0, 1, 2}, что дает следующие схемы.
Дополнение: Как отмечено в этой предложенной правке и полезном ответе, алгоритм указывает, что unblock()
должен удалять элемент, имеющий значение w
, а не элемент, имеющий индекс w
.
list.remove(Integer.valueOf(w));
Пример вывода:
0 1 0 0 1 2 0 0 2 0 0 2 1 0 1 0 1 1 0 2 1 1 2 0 1 1 2 1 2 0 1 2 2 0 2 2 1 0 2 2 1 2
По умолчанию программа начинает с s = 0
; остается оптимизировать s := наименьшая вершина в V
. Вариант, который производит только уникальные циклы, показан здесь.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* @see http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
* @see https://stackoverflow.com/questions/2908575
* @see https://stackoverflow.com/questions/2939877
* @see http://en.wikipedia.org/wiki/Adjacency_matrix
* @see http://en.wikipedia.org/wiki/Adjacency_list
*/
public final class CircuitFinding {
final Stack<Integer> stack = new Stack<Integer>();
final List<List<Integer>> a;
final List<List<Integer>> b;
final boolean[] blocked;
final int n;
int s;
public static void main(String[] args) {
List<List<Integer>> a = new ArrayList<List<Integer>>();
a.add(new ArrayList<Integer>(Arrays.asList(1, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 1)));
CircuitFinding cf = new CircuitFinding(a);
cf.find();
}
/**
* @param a adjacency structure of strong component K with
* least vertex in subgraph of G induced by {s, s + 1, n};
*/
public CircuitFinding(List<List<Integer>> a) {
this.a = a;
n = a.size();
blocked = new boolean[n];
b = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
b.add(new ArrayList<Integer>());
}
}
private void unblock(int u) {
blocked[u] = false;
List<Integer> list = b.get(u);
for (int w : list) {
//delete w from B(u);
list.remove(Integer.valueOf(w));
if (blocked[w]) {
unblock(w);
}
}
}
private boolean circuit(int v) {
boolean f = false;
stack.push(v);
blocked[v] = true;
L1:
for (int w : a.get(v)) {
if (w == s) {
//output circuit composed of stack followed by s;
for (int i : stack) {
System.out.print(i + " ");
}
System.out.println(s);
f = true;
} else if (!blocked[w]) {
if (circuit(w)) {
f = true;
}
}
}
L2:
if (f) {
unblock(v);
} else {
for (int w : a.get(v)) {
//if (v∉B(w)) put v on B(w);
if (!b.get(w).contains(v)) {
b.get(w).add(v);
}
}
}
v = stack.pop();
return f;
}
public void find() {
while (s < n) {
if (a != null) {
//s := least vertex in V;
L3:
circuit(s);
s++;
} else {
s = n;
}
}
}
}