Implementación de C# del algoritmo Bron-Kerbosch

Question

Estoy intentando escribir una implementación de C# del Bron-Kerbosch algorithm en la teoría de grafos, que se usa para encontrar camarillas de tamaño máximo en gráficos.

Idealmente, este algoritmo produciría una lista de gráficos, donde cada uno de esos gráficos representaría una camarilla máxima desde el gráfico de entrada inicial. Mi código no está produciendo el resultado esperado, y agradecería alguna guía para escribir un código mejor que logre esta implementación.

La clase de gráfico utilizada en esta instancia es una clase personalizada basada en una representación de lista de adyacencia de un gráfico.

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

Cualquier ayuda proporcionada sería muy apreciada - quiero saber si puedo proporcionar ninguna información adicional.

-

ACTUALIZACIÓN 1 Un contexto de las entradas y salidas es un gráfico de tres personas - la persona A, la persona B y la persona C. código se proporciona a continuación para proporcionar detalle más precisa:

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

En esta situación, me gustaría que los resultados fueran los dos gráficos previstosClique1 y expectedClique2; sin embargo, la salida real es de cuatro gráficos con solo personA. ¡Espero que esto ayude!

-

ACTUALIZACIÓN 2 Parece que he encontrado una solución al problema, aunque estoy indeciso para cerrar el caso hasta que lo haga un poco más pruebas para confirmar que mi solución es correcta. Se actualizará cuando pueda confirmar que mi solución es adecuada.

Answer 1

Para ampliar el comentario de ananthonline, las estructuras de datos bien contenidas, como estas, son candidatas perfectas para las pruebas unitarias. Encienda su marco de prueba favorito y establezca sus resultados esperados, incluidas todas sus condiciones de frontera.

Comience de manera simple, hágalo verde y luego amplíe. Formalizar lo esperado lo ayudará a pensar en el algoritmo y podría encender una bombilla para usted.