logo标签列表

Donald B. Johnson算法中需要帮助，我无法理解伪代码（第二部分）。

algorithmgraphcyclepseudocode
8
我无法理解Donald Johnson发表的关于在图中找到循环（电路）的论文中的某一部分。更具体地说，我无法理解伪代码中以下行中提到的矩阵Ak是什么：
Ak：=由{s，s + 1，... n}诱导的G子图中具有最小顶点的强连通分量的邻接结构；
更糟糕的是，在几行之后，它提到“对于Vk中的i”，而没有声明Vk是什么......
据我所知，我们有以下内容： 1）一般来说，强连通分量是图的子图，在该子图的每个节点中，都存在一条到该子图的任何节点的路径（换句话说，您可以从该子图的任何其他节点访问该子图的任何节点） 2）由节点列表诱导的子图是包含所有这些节点以及连接这些节点的所有边的图。在本文中，数学定义为“如果W是V的子集且F =（W，{u，y）| u，y属于W且（u，y）属于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算法中的伪代码理解中找到。

提前感谢你。

4个回答
11

它起作用了！在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中最小的顶点实现为一种优化。这里展示了一种仅产生唯一循环的变体here。

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://dev59.com/M07Sa4cB1Zd3GeqP0AYe
 * @see https://dev59.com/TE7Sa4cB1Zd3GeqP0x5v
 * @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;
            }
        }
    }
}
@Trashgod: 我成功地使用我的结构在Java中实现了这个算法（我还是不敢相信！！）。我假设Vk是包含当前节点的强连通网络（在你的实现中是变量s）。你的代码并不总是有效。根据网络的不同，它可能会抛出空指针异常。无论如何...你的帮助是无价的，这个算法真的帮助我理解了（而且我也学到了关于堆栈的知识），如果可以的话，我希望能把你列入我的毕业论文项目的感谢名单中（当然需要你的名字.. :) ） 非常感谢 - C.LS
正如@Chitr在下面的回答中提到的那样，输出包含循环排列，例如0-1-0和1-0-1。这是因为步骤“强连通分量K的邻接结构与G的{s，s + 1，...，n}诱导子图中最小顶点；基本上意味着每个小于s的顶点都应该从那次运行的邻接列表中删除。这将删除包括这些顶点的循环，因此只保留不同的循环。 - Gedde
@Gedde：正确；如上所述，“优化仍然存在”；其中一种方法已被其所有者删除；如果您添加一个回答来扩展Chitr的观察，请告诉我。 - trashgod
@thrashgod：是的，这只是问题的关键部分，而且在我看来，这不仅是一种优化，而且是算法中非常重要的一步。如果没有这个部分，您将无法找到不同的基本电路，并且在运行后删除重复项相当昂贵。它真的降低了算法的效率。我会看看是否稍后添加答案。基本上，它只是修剪所有距离Ak小于s的顶点。 - Gedde
1
@Gedde：我已经添加了一个变体，并在上面引用了它；请注意修复代码在版本7中。 - trashgod
显示剩余6条评论
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://dev59.com/M07Sa4cB1Zd3GeqP0AYe
 * @see https://dev59.com/TE7Sa4cB1Zd3GeqP0x5v
 * @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
1
我向@trashgod的代码提交了一个编辑请求，以修复unblock()中抛出的异常。本质上，该算法规定要从列表中删除元素w（它不是索引）。上面的代码使用了list.remove(w)，将w视为索引。
我的编辑请求被拒绝了！不确定原因，因为我已经使用我的修改在一个包含20,000个节点和70,000条边的网络上进行了测试，并且没有崩溃。
我还修改了Johnson算法，使其更适应无向图。如果有人需要这些修改，请与我联系。
下面是我的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);
        }
    }
}
发现了这个问题，我已经更新了我的答案。编辑请求可能看起来像是为了规避评论阈值，但这是一个好的答案。 - trashgod
1
@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。
Johnson的论文解释了什么是循环： “如果一个基本电路不是另一个的循环置换，则两个基本电路是不同的。” 您还可以查看Wolfram页面：它也会输出相同输入的5个循环。

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接