Aufzählen Graphen unter Kante und Symmetrie Constraints

Question

würde Ich mag die Menge aller gerichteten Graphen zu schaffen, mit n Vertices, wo jeder Knoten k direkten Nachfolger und k direkten Vorgänger hat. n und k wird nicht so groß sein, eher rund n = 8 und k = 3. Das Set enthält zyklische und azyklische Graphen. Jeder Graph wird wiederum als Vorlage für die Stichprobenauswahl einer großen Anzahl von gewichteten Graphen dienen.

Mein Interesse ist in der Rolle von Topologiemotiven, so will ich keine Gewichte für irgendwelche zwei Graphen, die symmetrisch zueinander sind, wo Symmetrie bedeutet, dass keine Permutation von Scheitelpunkten existiert in einem Graph, der es transformiert in den anderen.

A naive Lösung wäre, die 2^(n * ( n - 1)) zu betrachten Adjazenzmatrizen und alle diejenigen zu beseitigen (die meisten von ihnen), für die direkten Nachfolger oder Vorgänger Beschränkungen verletzt werden. Für n = 8, das sind immer noch ein paar Bits genug, um jede Matrix bequem innerhalb einer uint64_t darzustellen und einfach aufzuzählen.

Das Verfolgen der Zeilenanzahl und Spaltenanzahl wäre eine weitere Verbesserung, aber der eigentliche Engpass ist das Hinzufügen des Graphen zur Ergebnismenge. An diesem Punkt müssen wir die Symmetrie für jeden anderen Graphen testen. Für n = 8 wären das schon mehr als 40.000 Permutationen pro Einfügeoperation.

Könnte jemand mich auf einen Algorithmus verweisen, den ich lesen konnte, der alles auf eine klügere Weise tun kann? Gibt es eine Graphenbibliothek für C, C++, Java oder Python, die bereits einen solch umfassenden Graphengenerator implementiert? Gibt es ein Repository, in dem bereits alle Graphiken für vernünftige n und k "tabelliert" wurden?

Answer 1

Graph Isomorphie ist meiner Meinung nach nicht etwas, das Sie sich selbst überlegen sollten. Ich glaube, der aktuelle Stand der Technik ist Brendan McKays Nauty (und zugehörige Programme/Bibliotheken). Es ist ein bisschen wie ein Bär, mit dem man arbeiten kann, aber es kann sich lohnen, wenn man seinen eigenen, naiven Graphisomorphismus vermeidet. Außerdem ist es hauptsächlich auf ungerichtete Graphen ausgerichtet, kann aber auch Digraphen verwenden. Vielleicht möchten Sie die geng (die ungerichtete Graphen generiert) und directg (die Digraphen mit einem zugrunde liegenden Graphen generiert) Dienstprogramme, die mit Nauty kommen.

Answer 2

Dies ist eher ein Kommentar als eine Antwort, weil es scheint, als ob ich etwas in Ihrer Frage verpasst habe.

Erstens ist es möglich, dass ein solches Diagramm azyklisch ist?

Ich frage mich auch über Ihre Symmetrie Einschränkung. Sind damit nicht alle derartigen Graphen symmetrisch zueinander? Darf man Zeilen und Spalten der Verbindungsmatrix permutieren?

Wenn wir zum Beispiel Selbstverbindungen im Graphen zulassen, erfüllt die folgende Verbindungsmatrix Ihre Bedingungen?

1  1  0  0  0  0  0  1 
1  1  1  0  0  0  0  0 
0  1  1  1  0  0  0  0 
0  0  1  1  1  0  0  0 
0  0  0  1  1  1  0  0 
0  0  0  0  1  1  1  0 
0  0  0  0  0  1  1  1 
1  0  0  0  0  0  1  1 

aus dieser Matrix ausgehend, ist es dann nicht möglich, die Zeilen und Spalten davon permutieren alle solche Graphen zu erhalten, in der alle Zeilen und Spalten eine Summe von drei haben?

Ein Beispiel für eine solche Matrix kann aus der obigen Matrix A in der folgenden Weise (unter Verwendung von MATLAB) erhalten werden.

>> A(randperm(8),randperm(8)) 

ans = 

    0  1  0  0  0  1  1  0 
    0  0  1  0  1  0  1  0 
    1  1  0  1  0  0  0  0 
    1  1  0  0  0  1  0  0 
    1  0  0  1  0  0  0  1 
    0  0  1  1  0  0  0  1 
    0  0  1  0  1  0  0  1 
    0  0  0  0  1  1  1  0 

PS. In diesem Fall habe ich den Befehl einige Male wiederholt, um eine Matrix mit nur Nullen in der Diagonalen zu erhalten.:)

bearbeiten

Ah, ich Ihre Kommentare sehen, dass ich nicht richtig war. Natürlich muss der Permutationsindex für Zeilen und Spalten gleich sein. Ich hätte es zumindest bemerken sollen, als ich mit einem Graphen mit Selbstverbindungen anfing und einen ohne sie nach der Permutation erhielt.

Eine zufällige isomorph Permutation würde stattdessen wie folgt aussehen:

idx = randperm(8); 
A(idx,idx); 

, die alle Selbst Verbindungen zu halten.

Vielleicht könnte dies von Nutzen sein, wenn die Matrizen erzeugt werden, aber es ist überhaupt nicht so nützlich wie ich dachte, es wäre.