I am trying to write a C # implementation of the Bron-Kerbosch algorithm in graph theory, which is used to search for maximum clicks in graphics.
Ideally, this algorithm will create a list of graphs, where each of these graphs will represent the maximum click from the initial input graph. My code does not give the expected result, and I would appreciate some advice on writing the best code that achieves this implementation.
The graph class used in this instance is a custom class based on the adjacency county representation.
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 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 neighbors Graph<Person> neighborGraph = new Graph<Person>(v.Neighbors); // Move v to X P.Remove(v.Value); // BronKerbosch(RU {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 further information.
-
UPDATE 1 One entry and exit context is a three-person graph â Person A, Person B, and Person C. The code below is for providing more accurate information:
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 like the output to have two graphs expectedClique1 and expectedClique2, however the actual output is four graphs with only personA. Hope this helps!
-
UPDATE 2 It seems that I have found a solution to the problem, although I do not dare to close this case until I do a few more tests to confirm that my solution is correct. Will be updated when I can confirm that my decision is adequate.