CODEWITHSUNDEEP
c#.netalgorithmgraphgraph-algorithm
scottandrus
scottandrus

Reputation: 93

C# implementation of Bron-Kerbosch algorithm

I am attempting to write a C# implementation of the Bron-Kerbosch algorithm in graph theory, which is used to find cliques of maximal size in graphs.

Ideally, this algorithm would produce a list of graphs, where each of those graphs would represent a maximal clique from the initial input graph. My code is not producing the expected result, and I would appreciate some guidance to writing better code that achieves this implementation.

The graph class used in this instance is a custom class based on an adjacency-list representation of a graph.

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

Any help provided would be greatly appreciated - let me know if I can provide any additional information.

--

UPDATE 1 One context of the inputs and outputs is a graph of three people - Person A, Person B, and Person C. Code is provided below to provide more accurate detail:

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

In this situation, I would want the output to be the two graphs expectedClique1 and expectedClique2 - however, the actual output is four graphs with only personA. Hope this helps!

--

UPDATE 2 It appears that I have found a solution to the problem, though I am hesitant to close the case until I do some more testing to confirm that my solution is correct. Will update when I am able to confirm that my solution is adequate.

Upvotes: 7

Views: 1900

Answers (1)

Slugart
Slugart

Reputation: 4680

To expand on ananthonline's comment well contained data structures such as these are perfect candidates for unit testing. Fire up your favourite testing framework and set out your expected outputs including all your boundary conditions.

Start simple, get it green and then expand. Formalising your expected will help you think through the algorithm and might switch on a lightbulb for you.

Upvotes: 2

Related Questions