Einfacher Algorithmus zur Kanonisierung von Graphen

8

Ich suche nach einem Algorithmus, der eine kanonische Zeichenfolge für ein bestimmtes farbiges Diagramm bereitstellt . Dh. Ein Algorithmus, der eine Zeichenfolge für ein Diagramm zurückgibt, sodass zwei Diagramme genau dann dieselbe Zeichenfolge erhalten, wenn sie isomorph sind.

Insbesondere suche ich nach einem einfachen Algorithmus, der mit einer angemessenen Leistung auf den meisten Graphen einfach zu implementieren ist (natürlich im schlimmsten Fall Superpolynom). Ich erwarte kleine Grafiken, daher muss die Leistung nicht herausragend sein, sondern nur gut genug.

Leider sind die meisten Dinge, die ich gefunden habe, sehr komplex und mehr daran interessiert, tiefe mathematische Zusammenhänge auszudrücken, als nur den Algorithmus zu beschreiben. Ich fürchte, ich habe nicht die Zeit, so tief zu tauchen. Kann mir jemand eine Abkürzung geben?

Ich hoffe auf so etwas wie den Floyd-Warshall-Algorithmus. Nicht optimal, aber gut genug und einfach zu implementieren.

algorithms graph-theory combinatorics Peter
quelle
Sind die Grafiken konsistent beschriftet? Wenn ja, schreiben Sie einfach alle Kanten auf und sortieren Sie die Liste.
AdrianN
Ah, tut mir leid. Die Eckpunkte und Kanten sind beschriftet, jedoch nicht eindeutig. Jedes Etikett kann mehrfach vorkommen. Ich denke, die mathematische Phrase ist eher "farbig" als beschriftet. Ich werde die Frage bearbeiten.
Peter
"Worst-Case-NP natürlich" - nur damit wir uns klar sind: Es gibt einen bekannten (deterministischen) Polynom-Zeit-Algorithmus für den Graph-Isomorphismus. Das Beste, was Sie erwarten können, ist eine Super-Polynom-Lösung. Und ja, das Problem liegt in NP. Sehen Sie hier für Details zu diesen Begriffen.
Raphael
@ Raphael Sie haben Recht, ungenauere Terminologie. Der schlimmste Fall ist das Superpolynom. Es gibt jedoch Polynomalgorithmen für den Durchschnittsfall, so dass dies zumindest erreichbar sein sollte.
Peter
@ Raphael Das Beste, was Sie erwarten können, ist ein schneller Algorithmus, der für die meisten Grafiken funktioniert.
Yuval Filmus

Antworten:

3

Brendan McKay und Adolfo Piperno haben 2013 ein Umfragepapier zu dieser Frage verfasst. Sie präsentieren mehrere effiziente Computerprogramme, die viele Grafiken schneller kanonisieren können, als Sie sich vorstellen können. Es ist nicht notwendig (und sinnlos), diese Algorithmen selbst zu implementieren - sie sind online verfügbar, sogar als Quellcode.

Yuval Filmus
quelle
Es gibt eine Verringerung zwischen farbigem GI und GI (mit konstantem multiplikativem Aufblasen bei einer konstanten Anzahl von Farben), oder vielleicht könnten die Algorithmen selbst modifiziert werden.
Yuval Filmus
Können Sie hier eine beschreiben, um eine vollständige Antwort zu geben?
Raphael
3
Fügen Sie für jede Farbe einen zusätzlichen Scheitelpunkt hinzu. Verbinden Sie jeden ursprünglichen Scheitelpunkt mit dem Scheitelpunkt, der seine Farbe darstellt, indem Sie eine Kante hinzufügen. Stellen Sie sicher, dass die Grade der "Farb" -Scheitelpunkte eindeutig sind. Wenn dies nicht der Fall ist, fügen Sie Schleifen oder andere falsche Kanten hinzu. Übrigens bin ich über das McKay / Piperno-Umfragepapier weniger als glücklich - es ist eine Umfrage ihrer eigenen Forschung, und die Vergleiche, die sie mit anderen Tools anstellen, entsprechen den Benchmarks, die sie für interessant halten. Sie lassen wichtige aktuelle Entwicklungen und fast alle Benchmarks aus nicht-theoretischen Anwendungen aus, was sich auf empirische Ergebnisse auswirkt.
Igor Markov
2

Am Ende habe ich den Nauty-Algorithmus implementiert, aber dabei eine Antwort auf meine eigene Frage gefunden. Nauty erweitert diesen grundlegenden Algorithmus um viele komplizierte Heuristiken:

Bei kleinen Graphen G der Länge n:

  1. n!
  2. Generieren Sie jeweils eine Zeichenfolgendarstellung (eins zu eins).
  3. Definieren Sie eine kanonische Reihenfolge der Zeichenfolgen und merken Sie sich die kleinste gefundene Zeichenfolge.

Ö(n!)

Nauty erweitert diesen Algorithmus hauptsächlich, indem der Suchraum von zu berücksichtigenden Graphen beschnitten wird, wenn nach dem mit der kleinsten Zeichenfolgendarstellung gesucht wird.

Peter
quelle
1
fünfzehn!1012
1
@ DavidRicherby Auf jeden Fall. Es gibt jedoch Anwendungsfälle wie die Motivanalyse, in denen diese Operation nur für Diagramme der Größe 3 oder 4 ausgeführt wird. Tatsächlich weiß ich nicht, ob das Auffinden eines kanonischen isomorphen Teilgraphen für Diagramme in angemessener Zeit überhaupt erreicht werden kann über 15 Knoten (auch wenn bekannt ist, dass der Subgraph-Isomorphismus selbst jetzt sehr nahe am Polynom liegt)
Peter