Я пытаюсь написать на С# реализацию алгоритма Брона-Кербоша в теории графов, которая используется для поиска клик максимального размера в графах.
В идеале этот алгоритм должен создать список графов, где каждый из этих графов будет представлять максимальную клику из исходного входного графа. Мой код не дает ожидаемого результата, и я был бы признателен за некоторые рекомендации по написанию лучшего кода, который достигает этой реализации.
Класс графа, используемый в этом случае, является пользовательским классом, основанным на представлении графа в виде списка смежности.
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);
В этой ситуации я бы хотел, чтобы на выходе были два графика, ожидаемаяClique1 и ожидаемаяClique2, однако на самом деле на выходе четыре графика только с personA. Надеюсь это поможет!
--
ОБНОВЛЕНИЕ 2 Похоже, я нашел решение проблемы, хотя я не решаюсь закрыть дело, пока не проведу еще несколько тестов, чтобы подтвердить правильность моего решения. Будет обновлено, когда я смогу подтвердить, что мое решение адекватно.
