Bron-KerboschアルゴリズムのC＃の実装

Question

Bron-Kerbosch algorithmの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;   
    } 
} 

私が追加情報を提供できるかどうか教えてください。

-

入力と出力のUPDATE 1つコンテキストは、三人のグラフである - 人物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つのグラフです。お役に立てれば！

-

UPDATE 2私が私が私の解決策が正しいことを確認するためにいくつかのより多くのテストを行うまで、ケースを閉じることを躊躇していますけれども、私は、問題の解決策を発見したことが表示されます。私のソリューションが適切であることを確認できると更新されます。

Answer 1

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

簡単に開始し、緑色にしてから展開します。あなたの予期されたことを公式化することは、あなたがアルゴリズムを通して考えることを助け、あなたのために電球をスイッチするかもしれません。