algorithm - 帮助 Donalds B. Johnson 的算法，我无法理解伪代码（第二部分）

Question

我无法理解 Donald Johnson 发表的关于在图中查找循环（​​电路）的论文的某个部分。

更具体地说，我无法理解伪代码以下行中提到的矩阵 Ak 是什么：

Ak:=由{s,s+1,....n}诱导的G子图中顶点最少的强分量K的邻接结构；

让事情变得更糟的是，在没有声明 Vk 是什么的情况下，在“for i in Vk do”之后的某些行中提及...

据我所知，我们有以下内容：1）通常，强组件是图的子图，其中对于该子图的每个节点，都有到子图的任何节点的路径（换句话说，您可以从子图的任何其他节点访问子图的任何节点）

2）由节点列表诱导的子图是包含所有这些节点以及连接这些节点的所有边的图。在论文中，数学定义是“如果 W 是 V 的子集并且 F = (W,{u,y)|u,y in W and (u,y) in E)}，则 F 是由 W 诱导的 G 的子图）其中 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 算法中的伪代码中

并且可以在 了解 Donald B. Johnson 算法中的伪代码中找到该论文

先感谢您

Answer 1

有用！在Johnson 算法的早期迭代中，我假设这是一个邻接矩阵。相反，它似乎代表一个邻接列表。在该示例中，在下面实现，顶点{a,b,c}编号为 {0,1,2}，产生以下电路。A

附录：正如在这个建议的编辑和有用的答案中指出的那样，算法指定unblock()应该删除具有value w的元素，而不是具有index 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 的代码提交了一个编辑unblock()请求，以修复. 本质上，该算法声明要从列表中删除元素w（不是索引）。上面的代码使用了list.remove(w)，它被视为w一个索引。

我的编辑请求被拒绝了！不知道为什么，因为我已经在一个由 20,000 个节点和 70,000 个边组成的网络上对上述内容进行了修改，并且它没有崩溃。

我还修改了约翰逊的算法，使其更适合无向图。如果有人想要这些修改，请与我联系。

下面是我的代码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);
        }
    }
}

Answer 4

@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/