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;           
    }
}   

如能提供任何帮助，我们将不胜感激 - 如果我可以提供任何其他信息，请告诉我。

--

更新 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 - 然而，实际输出是四个图，只有 personA。希望这对您有所帮助!

--

UPDATE 2 看来我已经找到了问题的解决方案，但在我进行更多测试以确认我的解决方案正确之前，我犹豫要不要关闭案例。当我能够确认我的解决方案足够时将更新。

Answer 1

为了扩展 ananthonline 的评论，包含良好的数据结构，例如这些是单元测试的完美候选者。启动您最喜欢的测试框架并设置您的预期输出，包括所有边界条件。

从简单开始，将其变为绿色，然后扩展。形式化您的期望将帮助您思考算法并可能为您打开灯泡。