java - Java で二部グラフを実装するにはどうすればよいですか?

Question

アップデート

これまでのいくつかの回答では、隣接リストの使用が提案されています。隣接リストはJavaでどのように見えるでしょうか? ...ポインタはありません:)

---

ファイルからの情報を 2 つのグループに分類するために、Java で二部グラフを実装しようとしています。私はこの例を見つけました、そしてそれは実際に仕事をします:

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

しかし、私は自分のバージョンを実装したいと思っています...私の以前の投稿を見ると、なぜ私が自分でこれをやりたいのか理解できるでしょう。

そのため、頂点の数を簡単に取得できるファイルを読み取る必要がありますが、エッジの数はそれほど簡単ではありません。例の行は"PersonA PersonB"で、これは "PersonA say PersonB "と読むことができます。だから、これらの行を読んで...

"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"

... このグループ化を生成します。

{A,D,C} and {B,E}.

この二部グラフを実装するにはどうすればよいですか? このタスクに適したリソースは何ですか? BipartiteGraph クラスを作成するときに、どのようなこと (アルゴリズム) を考慮し、検討する必要がありますか?おそらくトラバース/ソートアルゴリズム?

Answer 1

隣接リストを使用して実装するのは非常に簡単です。無向2部グラフの場合は、接続行列を使用することをお勧めします。

したがって、ノードごとに、リンクリストの配列、または動的に割り当てられたリストの配列があります。これにより、エッジの追加がかなり自然になります。たとえば、例では、エッジがあります。

人物A->人物B

次に、Person Aに対応する配列インデックスに移動し、PersonaBに対応するインデックスをプッシュバックします。

[人物A]=人物B

その後、多分あなたは別のエッジを取得します

ペルソナA->ペルソナC

次に、そこにあるインデックスは次のようになります。

[ペルソナA]=人物B、人物C

最後の例として、これはサンプルグラフの隣接リストになります。

[A] B

[B] D

[C] B

[D] B

[E] A、C

各インデックスには、そのノードから到達可能なノードのリストがあります。

「BipartiteGraphクラスを作成するときに、どのようなこと（アルゴリズム）を検討および検討する必要がありますか...おそらくトラバース/ソートアルゴリズムですか？」

それは本当にあなたがグラフで何をしたいかに依存します...

参考：Sunフォーラムのコードに関する同様の質問

a-directed-weighted-graphの隣接リスト

Answer 2

これを試して： -

Bipartite.java

/*************************************************************************
 *  Compilation:  javac Bipartite.java
 *  Dependencies: Graph.java 
 *
 *  Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
 *  Runs in O(E + V) time.
 *
 *
 *************************************************************************/

/**
 *  The <tt>Bipartite</tt> class represents a data type for 
 *  determining whether an undirected graph is bipartite or whether
 *  it has an odd-length cycle.
 *  The <em>isBipartite</em> operation determines whether the graph is
 *  bipartite. If so, the <em>color</em> operation determines a
 *  bipartition; if not, the <em>oddCycle</em> operation determines a
 *  cycle with an odd number of edges.
 *  <p>
 *  This implementation uses depth-first search.
 *  The constructor takes time proportional to <em>V</em> + <em>E</em>
 *  (in the worst case),
 *  where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
 *  Afterwards, the <em>isBipartite</em> and <em>color</em> operations
 *  take constant time; the <em>oddCycle</em> operation takes time proportional
 *  to the length of the cycle.
 */
public class Bipartite {
    private boolean isBipartite;   // is the graph bipartite?
    private boolean[] color;       // color[v] gives vertices on one side of bipartition
    private boolean[] marked;      // marked[v] = true if v has been visited in DFS
    private int[] edgeTo;          // edgeTo[v] = last edge on path to v
    private Stack<Integer> cycle;  // odd-length cycle

    /**
     * Determines whether an undirected graph is bipartite and finds either a
     * bipartition or an odd-length cycle.
     * @param G the graph
     */
    public Bipartite(Graph G) {
        isBipartite = true;
        color  = new boolean[G.V()];
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];

        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
        assert check(G);
    }

    private void dfs(Graph G, int v) { 
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if odd-length cycle found
            if (cycle != null) return;

            // found uncolored vertex, so recur
            if (!marked[w]) {
                edgeTo[w] = v;
                color[w] = !color[v];
                dfs(G, w);
            } 

            // if v-w create an odd-length cycle, find it
            else if (color[w] == color[v]) {
                isBipartite = false;
                cycle = new Stack<Integer>();
                cycle.push(w);  // don't need this unless you want to include start vertex twice
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
            }
        }
    }

    /**
     * Is the graph bipartite?
     * @return <tt>true</tt> if the graph is bipartite, <tt>false</tt> otherwise
     */
    public boolean isBipartite() {
        return isBipartite;
    }

    /**
     * Returns the side of the bipartite that vertex <tt>v</tt> is on.
     * param v the vertex
     * @return the side of the bipartition that vertex <tt>v</tt> is on; two vertices
     *    are in the same side of the bipartition if and only if they have the same color
     * @throws UnsupportedOperationException if this method is called when the graph
     *    is not bipartite
     */
    public boolean color(int v) {
        if (!isBipartite)
            throw new UnsupportedOperationException("Graph is not bipartite");
        return color[v];
    }

    /**
     * Returns an odd-length cycle if the graph is not bipartite, and
     * <tt>null</tt> otherwise.
     * @return an odd-length cycle (as an iterable) if the graph is not bipartite
     *    (and hence has an odd-length cycle), and <tt>null</tt> otherwise
     */
    public Iterable<Integer> oddCycle() {
        return cycle; 
    }

    private boolean check(Graph G) {
        // graph is bipartite
        if (isBipartite) {
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (color[v] == color[w]) {
                        System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                        return false;
                    }
                }
            }
        }

        // graph has an odd-length cycle
        else {
            // verify cycle
            int first = -1, last = -1;
            for (int v : oddCycle()) {
                if (first == -1) first = v;
                last = v;
            }
            if (first != last) {
                System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                return false;
            }
        }

        return true;
    }

    /**
     * Unit tests the <tt>Bipartite</tt> data type.
     */
    public static void main(String[] args) {
        // create random bipartite graph with V vertices and E edges; then add F random edges
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        int F = Integer.parseInt(args[2]);

        Graph G = new Graph(V);
        int[] vertices = new int[V];
        for (int i = 0; i < V; i++) vertices[i] = i;
        StdRandom.shuffle(vertices);
        for (int i = 0; i < E; i++) {
            int v = StdRandom.uniform(V/2);
            int w = StdRandom.uniform(V/2);
            G.addEdge(vertices[v], vertices[V/2 + w]);
        }

        // add F extra edges
        for (int i = 0; i < F; i++) {
            int v = (int) (Math.random() * V);
            int w = (int) (Math.random() * V);
            G.addEdge(v, w);
        }

        StdOut.println(G);

        Bipartite b = new Bipartite(G);
        if (b.isBipartite()) {
            StdOut.println("Graph is bipartite");
            for (int v = 0; v < G.V(); v++) {
                StdOut.println(v + ": " + b.color(v));
            }
        }
        else {
            StdOut.print("Graph has an odd-length cycle: ");
            for (int x : b.oddCycle()) {
                StdOut.print(x + " ");
            }
            StdOut.println();
        }
    }
}

Answer 3

これは C# の実装ですが、この概念は Java でも使用できます。グラフを表すために Adjacency Matrix を使用しました。グラフに奇数のサイクルがあるかどうかを確認します。

1,2,3,4,5,6の下の図を考慮すると、そのグラフにパーティションが存在する場合、グラフは二部と呼ばれます。 ,7 はグラフ G の頂点です。左側 (1,4,5,6) の頂点を U、右側 (2,3,7) の頂点を V と考えてみましょう。

現時点では、グラフに赤い接続がないことを考慮してください。無向グラフとして、u から v および v から u への接続があることがわかります。しかし、パーティションには接続がありません。それが私が使用するコンセプトです。

以下に示すグラフは、ツリー構造のように描かれていることを除いて、上記と同じグラフであると考えてください。この場合、代替レベル 1、3、5 に存在するノードを見ることができれば、一緒にパーティションを形成でき、2、4 が別のパーティションを形成できます。したがって、グラフは BiPartite であると簡単に言えます。同じレベルの要素間に赤い縁がある場合はどうなりますか? グラフは 2 部構成ではありません。BFS アルゴリズムを変更できる場合は、これを実現できます。

これがそのコードです。

   int[,] BPGraph = new int[7,7]{
                                    {0,1,0,1,0,0,0},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {0,1,0,1,0,0,1},
                                    {0,0,1,0,1,1,0}
                                };

    int[] BPArray = new int[7] { 0, 0, 0, 0, 0, 0, 0 };

    public Boolean BiPartite()
    {
        Queue<int> VertexQueue = new Queue<int>();
        int level = 0;
        int nextlevel=0;
        Boolean BPFlg = true;

        VertexQueue.Enqueue(0);

        while(VertexQueue.Count!=0)
        {
            int current = VertexQueue.Dequeue();
            level = BPArray[current];

            if (level == 0)
                level = 1;

            if (level == 2)
                nextlevel=1;
            else
                nextlevel=2;

            if(BPArray[current]==0) 
                BPArray[current] = level;

            for (int i = 0; i < 7; i++)
            {
                if (BPGraph[current, i] == 1)
                {
                    if (BPArray[i] == 0)
                    {
                        BPArray[i] = nextlevel;
                        VertexQueue.Enqueue(i);
                    }
                    else if (BPArray[i] == level)
                    {
                        BPFlg = false;
                        break;
                    }
                }
            }
            if (!BPFlg)
                break;
        }
        return BPFlg;

    }

Answer 4

有向グラフは、ノードAとBを接続するエッジに方向があるグラフです。AからBへのエッジがある場合、これはBからAへのエッジがあることを意味するものではありません。この例では、エッジに方向があります。（BからDは、BからDへのエッジとDからBへのエッジの2つのエッジになります。）

これを実装する1つの方法は、リンクリストと同様の方法であり、ノードは必要に応じて相互に参照します。例に戻ると、へnodeAの参照がありますがnodeB、その逆はありません。nodeEおよびなどへの参照がnodeAありnodeCます。あなたは実際に（一種の）データ構造を作成しています。これにはノードとおそらくエッジの概念があります。あなたがそれについて行くことができるいくつかの方法があります。

考えられるJava実装は、頂点とそれに隣接する頂点を含む と呼ばれるクラスを持つことAdjacencyListです。その後、マップ上で操作を実行する機能があります。Map<Vertex, List<Vertex>>AdjacencyList

アルゴリズムと覚えておくべきことについては、特にウィキペディアの2部グラフのプロパティを見てください。

• グラフに奇数サイクルが含まれていない場合に限り、グラフは2部グラフになります。したがって、2部グラフにサイズ3以上のクリークを含めることはできません。
• すべての木は2部グラフです。
• 頂点の数が偶数の閉路グラフは2部グラフです。

良いテストは、グラフが実際に2部グラフであることを確認するために、2色のアルゴリズムを実装することです。深さ優先探索、幅優先探索は、実装の優れた演習です。