7

我正在尝试在图论中编写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看来我已经找到了解决问题的方法，但我很犹豫要不要结案，直到我进行更多测试以确认我的解决方案是正确的。当我能够确认我的解决方案足够时将更新。

4

1 回答 1

2

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

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

于 2012-07-16T20:31:50.947 回答