Bron-Kerbosch算法的C＃實現

Question

我試圖在圖論中編寫一個C＃實現的Bron-Kerbosch algorithm，它用於在圖中找到最大尺寸的派系。

理想情況下，該算法會生成一個圖表列表，其中每個圖表將表示來自初始輸入圖的最大集團。我的代碼沒有產生預期的結果，我希望能夠編寫更好的代碼來實現此實現。

此實例中使用的圖類是基於圖的鄰接列表表示的自定義類。

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，和Person 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 - 但是，實際輸出是四個只有personA的圖。希望這可以幫助！

-

更新2看來，我已經找到了解決問題的辦法，雖然我很猶豫，直到我做一些更多的測試，關閉的情況下，以確認我的解決方案是正確的。當我能夠確認我的解決方案已經足夠時將會更新。

Answer 1

爲了擴展ananthonline的評論，包含這些數據結構，這些都是單元測試的最佳候選。啓動您最喜愛的測試框架並列出您的預期輸出結果，包括您的所有邊界條件。

從簡單開始，將其變爲綠色然後展開。形式化你的預期將幫助你思考這個算法，並可能爲你開啓一個燈泡。