C#实现了Bron-Kerbosch算法

Question

我试图在图论中编写Bron-Kerbosch算法的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的图形.希望这可以帮助!

-

更新2似乎我已经找到了解决问题的方法,但是在我做更多测试以确认我的解决方案是正确的之前我不愿意结案.当我能够确认我的解决方案是足够的时候会更新.

Answer 1

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

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