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的评论，包含这些数据结构，这些都是单元测试的最佳候选。启动您最喜爱的测试框架并列出您的预期输出结果，包括您的所有边界条件。

从简单开始，将其变为绿色然后展开。形式化你的预期将帮助你思考这个算法，并可能为你开启一个灯泡。