algorithm - Donalds B. Johnson のアルゴリズムのヘルプ、疑似コードを理解できない (PART II)

Question

グラフでサイクル (Circuits) を見つけることについて、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 および (u,y) in E) の場合、F は W によって誘導される G の部分グラフです})ここで、u、y はエッジ、E はグラフ内のすべてのエッジのセット、W はノードのセットです。

3) コード実装では、ノードは整数 1 ... n で名前が付けられます。

4) Vk は、強成分 K のノードの集合であると思われます。

今質問に。V = {1,2,3,4,5,6,7,8,9} のグラフ G= (V,E) があり、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

できます！ジョンソン アルゴリズムの以前の反復では、これは隣接行列であると想定していました。代わりに、隣接リストを表しているように見えます。以下に実装されたその例では、頂点{a, b, c}に {0, 1, 2} の番号が付けられ、次の回路が生成されます。A

補遺: この提案された編集と役立つ回答に記載されているように、アルゴリズムは、 indexを持つ要素ではなく、valueunblock()を持つ要素を削除する必要があることを指定します。 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 のコードに編集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);
        }
    }
}

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