C# implementacja algorytmu Bron-Kerboscha

Question

Próbuję napisać implementację C# z Bron-Kerbosch algorithm w teorii grafów, która służy do znajdowania kliknięć o maksymalnym rozmiarze na wykresach.

Idealnie, ten algorytm tworzy listę wykresów, gdzie każdy z tych wykresów reprezentowałby maksymalną klikę z początkowego wykresu wejściowego. Mój kod nie przynosi oczekiwanych rezultatów i byłbym wdzięczny za wskazówki dotyczące pisania lepszego kodu, który osiąga tę implementację.

Klasa wykresów użytych w tej instancji jest niestandardową klasą opartą na reprezentacji wykresu na stronie sąsiadującej.

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

Każda pomoc udzielona zostanie bardzo doceniona - daj mi znać, jeśli mogę podać jakiekolwiek dodatkowe informacje.

-

aktualizacji 1 jednym kontekście wejść i wyjść wykres trzech osób - osobie, osoba B i C Osoba Code przedstawiono poniżej w celu zapewnienia bardziej dokładnych szczegółów:

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

W tej sytuacji chciałbym, aby dane wyjściowe były dwoma wykresami, których można się spodziewaćClique1 i expectedClique2 - jednak faktycznym wynikiem są cztery wykresy z tylko personA. Mam nadzieję że to pomoże!

-

UPDATE 2 Wydaje się, że znalazłem rozwiązanie problemu, choć jestem niezdecydowany, aby zamknąć sprawę, dopóki nie zrobić trochę więcej badań, aby potwierdzić, że moje rozwiązanie jest poprawne. Zaktualizuje się, gdy będę mógł potwierdzić, że moje rozwiązanie jest odpowiednie.

Answer 1

Aby rozwinąć komentarz ananthonline, dobrze zapamiętywane struktury danych, takie jak te, są idealnymi kandydatami do testów jednostkowych. Uruchom swoje ulubione ramy testowe i określ oczekiwane wyniki, w tym wszystkie warunki brzegowe.

Rozpocznij prosty, pobierz zielony, a następnie rozwiń. Sformalizowanie oczekiwanych pomoże ci przemyśleć algorytm i może włączyć żarówkę.