7

グラフで最大サイズのクリークを見つけるために使用されるグラフ理論で、ブロン-ケルボッシュ アルゴリズムの C# 実装を作成しようとしています。

理想的には、このアルゴリズムはグラフのリストを生成し、これらのグラフのそれぞれが最初の入力グラフからの最大クリークを表します。私のコードは期待した結果を生成していません。この実装を実現するより良いコードを作成するためのガイダンスをいただければ幸いです。

このインスタンスで使用されるグラフ クラスは、グラフの隣接リスト表現に基づくカスタム クラスです。

public class BronKerbosch
{
    public List<Graph<Person>> Run(Graph<Person> R, Graph<Person> P, Graph<Person> X, List<Graph<Person>> maximalCliques)
    {
        // if P and X are both empty, and the size of R is greater than 1 (implies clique):
        if (!P.Nodes.Any() && !X.Nodes.Any() && R.Nodes.Count() > 1)
            // report R as a maximal clique
            maximalCliques.Add(R);

        else
        {
            // Copy P's nodes for traversal
            List<GraphNode<Person>> nodesCopy = P.Nodes.ToList();

            // For each node v in P:
            foreach (GraphNode<Person> v in nodesCopy)
            {

                // Make graph with just v
                Graph<Person> vGraph = new Graph<Person>(new NodeList<Person>());
                vGraph.AddNode(v);

                // Make graph with just v's neighbors
                Graph<Person> neighborGraph = new Graph<Person>(v.Neighbors);

                // Move v to X
                P.Remove(v.Value);

                // BronKerbosch(R U {v}, P INTERSECT N(v), X INTERSECT N(v)))
                maximalCliques = Run(R.Union(vGraph), P.Intersect(neighborGraph), X.Intersect(neighborGraph), maximalCliques);

                X = X.Union(vGraph);
            }
        }
        return maximalCliques;           
    }
}

提供されたヘルプは大歓迎です。追加情報を提供できる場合はお知らせください。

--

更新 1入力と出力の 1 つのコンテキストは、3 人の人物 (人物 A、人物 B、人物 C) のグラフです。より正確な詳細を提供するために、コードを以下に示します。

graphR = new Graph<Person>(new NodeList<Person>());
graphP = new Graph<Person>(new NodeList<Person>());
graphX = new Graph<Person>(new NodeList<Person>());

Person personA = new Person() {FirstName = "Person A"};
Person personB = new Person() {FirstName = "Person B"};
Person personC = new Person() {FirstName = "Person C"};

Anode = new GraphNode<Person>(personA);
Bnode = new GraphNode<Person>(personB);
Cnode = new GraphNode<Person>(personC);

graphP.AddNode(Anode);
graphP.AddNode(Bnode);
graphP.AddNode(Cnode);

graphP.AddUndirectedEdge(Anode, Bnode);
graphP.AddUndirectedEdge(Cnode, Anode);

expectedClique1 = new Graph<Person>(new NodeList<Person>());
expectedClique1.AddNode(Anode);
expectedClique1.AddNode(Bnode);
expectedClique1.AddUndirectedEdge(Anode, Bnode);

expectedClique2 = new Graph<Person>(new NodeList<Person>());
expectedClique2.AddNode(Cnode);
expectedClique2.AddNode(Anode);
expectedClique2.AddUndirectedEdge(Cnode, Anode);

maximalCliques = new List<Graph<Person>>();

bronKerbosch = new BronKerbosch();

bronKerbosch.Run(graphR, graphP, graphX, maximalCliques);

この状況では、出力を expectedClique1 と expectedClique2 の 2 つのグラフにしたいと思いますが、実際の出力は personA のみの 4 つのグラフです。お役に立てれば！

--

更新 2問題の解決策を見つけたようですが、解決策が正しいことを確認するためにさらにテストを行うまで、ケースを閉じることをためらっています。私のソリューションが適切であることを確認できたら更新します。

4

1 に答える 1

2

ananthonlineのコメントを拡張するには、これらのような十分に含まれているデータ構造が単体テストの完璧な候補です。お気に入りのテストフレームワークを起動し、すべての境界条件を含む期待される出力を設定します。

シンプルに始めて、グリーンにしてから拡張します。期待値を形式化すると、アルゴリズムを検討するのに役立ち、電球をオンにすることができます。

于 2012-07-16T20:31:50.947 に答える