помочь в алгоритме Дональда Б. Джонсона, я не понимаю псевдокод (ЧАСТЬ II)

Question

Я не могу понять определенную часть статьи, опубликованной Дональдом Джонсоном, о нахождении циклов (схем) в графе.

Более конкретно, я не могу понять, что такое матрица Ak, которая упоминается в следующей строке псевдокода:

Ak: = структура смежности сильного компонента K с наименьшим вершина в подграфе G, индуцированная {s, s + 1, .... n};

чтобы все стало хуже после того, как «Мэнтинс в Вконтакте делает», не объявляя, что такое ВК ...

Насколько я понимаю, у нас есть следующее: 1) в общем случае сильный компонент - это подграф графа, в котором для каждого узла этого подграфа есть путь к любому узлу подграфа (другими словами, вы можете получить доступ к любому узлу подграф из любого другого узла подграфа) * ​​1009 *

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 - это множество узлов сильного компонента К.

Теперь к вопросу. Допустим, у нас есть граф 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 в соответствии с кодом?

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

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

заранее спасибо

Answer 1

Работает! В более ранней итерации алгоритма Джонсона я предполагал, что 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 := least vertex in 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;
            }
        }
    }
}

Answer 2

Следующий вариант дает уникальные циклы. На основании этого примера он адаптирован из ответа , предоставленного @ user1406062 .

Код:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @see https://en.wikipedia.org/wiki/Johnson%27s_algorithm
 * @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 Map<Integer, List<Integer>> a;
    final List<List<Integer>> b;
    final boolean[] blocked;
    final int n;
    Integer 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 = new HashMap<Integer, List<Integer>>(A.size());
        for (int i = 0; i < A.size(); i++) {
            this.a.put(i, new ArrayList<Integer>());
            for (int j : A.get(i)) {
                this.a.get(i).add(j);
            }
        }
        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() {
        s = 0;
        while (s < n) {
            if (!a.isEmpty()) {
                //s := least vertex in V;
                L3:
                for (int i : a.keySet()) {
                    b.get(i).clear();
                    blocked[i] = false;
                }
                circuit(s);
                a.remove(s);
                for (Integer j : a.keySet()) {
                    if (a.get(j).contains(s)) {
                        a.get(j).remove(s);
                    }
                }
                s++;
            } else {
                s = n;
            }
        }
    }
}

Выход:

0 1 0
0 1 2 0
0 2 0
0 2 1 0
1 2 1

Все циклы, для справки:

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

Answer 3

@ trashgod, ваш пример вывода содержит цикл, который является циклической перестановкой. Например, 0-1-0 и 1-0-1 одинаковы На самом деле выход должен содержать только 5 циклов, т.е. 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,

В статье Джонсона объясняется, что такое цикл: «Две элементарные схемы различны, если одна не является циклической перестановкой другой. ' Можно также проверить страницу wolfram: это также выдает 5 циклов для того же ввода.

http://demonstrations.wolfram.com/EnumeratingCyclesOfADirectedGraph/

Answer 4

Я отправил запрос edit на код @ trashgod, чтобы исправить исключение, выданное в unblock(). По сути, алгоритм утверждает, что элемент w (который является , а не индексом) должен быть удален из списка. Код выше использовал list.remove(w), который обрабатывает w как индекс.

Мой редактировать запрос был отклонен! Не знаю почему, потому что я протестировал вышеупомянутое с моей модификацией в сети из 20 000 узлов и 70000 ребер, и она не дает сбоя.

Я также изменил алгоритм Джонсона, чтобы он был более адаптирован к неориентированным графам. Если кому-то нужны эти модификации, пожалуйста, свяжитесь со мной.

Ниже мой код для unblock().

private void unblock(int u) {
    blocked[u] = false;
    List<Integer> list = b.get(u);
    int w;
    for (int iw=0; iw < list.size(); iw++) {
        w = Integer.valueOf(list.get(iw));
        //delete w from B(u);
        list.remove(iw);
        if (blocked[w]) {
            unblock(w);
        }
    }
}