Durch Dictionaries iterieren

[MarcelF6]

Vielen Dank, BlackJack!

Also, damit ich den Algorithmus richtig verstehe. Du gehst also wie folgt vor, oder?
1.) Du nimmst einen Knoten, sagen wir a0.
2.) Du schaust, wie viele Kanten von diesem Knoten aus gehen und versuchst, im zweiten Graphen ebenfalls ein solcher Knoten zu finden.
3.) a) Falls ein solcher gefunden wurde, wiederhole 1.-3. mit dem nächsten Knoten von Graph A.
b) falls keine Entsprechung gefunden wurde --> kein Isomorphismus
c) falls alle Knoten behandelt wurden --> Isomorphismus und fertig.

Ah, und: Wie sieht das mit der Komplexität aus?
Wir haben ja einmal 2x for-Schleifen, d.h. O(n²) ?

[BlackJack]

@MarcelF6: Nein das ist zu einfach gedacht. Da könnte man die Knoten von beiden Graphen ja auch einfach nach Grad sortieren und dann linear, paarweise vergleichen ob die den gleichen Grad haben. Die Struktur des Graphen muss ja übereinstimmen. Also der Grad von zwei Knoten, *und* dann müssen noch die Grade von allen Nachbarknoten, und deren Nachbarknoten, usw. übereinstimmen. Das ist dann der rekursive Algorithmus.

[EyDu]

Wenn BlackJack eine Lösung in O(n²) gefunden hätte, dann hätte er vor lauter Vorträgen hier sicher keine Zeit zu schreiben. Das Isomorphieproblem ist NP-vollständig. Der bisher beste gefundene Algorithmus hat eine Komplexität von O(2^sqrt(n log n)).

[MarcelF6]

@BlackJack: Ah ok, jetzt ist's klar.
Vielen Dank!

@EyDu & BlackJack:
Ja stimmt, das habe ich gelesen.
Aber kann man die Komplexität dieses Algorithmus hier nicht abschätzen?

[EyDu]

Aber kann man die Komplexität dieses Algorithmus hier nicht abschätzen?

Das bekommst du selbst hin. Überlege dir mal, wie die schlimmsten zu testenden Graphen aussehen und was dann passieren muss.

[MarcelF6]

Ich bin nicht sicher, ob das stimmt. Ich würde aber sagen, dass:
Der schlimmste zu testende Graph hat bei jedem Knoten gleich viele Kanten. Dann gilt für die Rekursion nämlich T(n) = T(n²-1)+T(n²-2)+1, also T(n) = O(2^(n^2)).

Kann das sein?

Übrigens: Weisst du, ob igraph in python (man kann das Modul ja importieren) O(2^sqrt(n log n)) erreicht?

[MarcelF6]

Nochmals zum Algorithmus. Dieser hier wäre also korrekt, oder?
1.) Finde 2 Knoten mit demselben Grad.
2.) Stimmen die Grade der Nachbarsknoten überein?
3.) A) falls ja: wiederhole Schritt 2 mit den nächsten Nachbarsknoten
B) falls nein: kein Isomorphismus!
C) falls alle Knoten bearbeitet: Isomorphismus!

[BlackJack]

@MarcelF6: Für meinen Geschmack ist das noch zu schwammig und missverständlich formuliert. Ich glaube danach könnte niemand den Algorithmus implementieren, oder zumindest nur zufällig richtig.

Ich würde ja versuchen das als Pseudocode zu beschreiben und es auch in zwei Teilalgorithmen zu machen, so wie das ja auch umgesetzt ist. Also erst beschreiben was `_iso_search()` macht, und dann die man das benutzen kann um einen Isomorphismus zu finden. Bei der Beschreibung kann man sich auch etwas von der konkreten Umsetzung entfernen, denn was da zur Lösung hinzugefügt wird, ist semantisch ja auch etwas an anderer Stelle ”wegnehmen” oder ”verschieben”, das mache ich in der Implementierung nur deswegen nicht, weil ich die Graphdatenstrukturen nicht zerstören möchte. Das wäre irgendwie eine unschöne API.

[MarcelF6]

Ok, dann würde ich den Algorithmus so beschreiben (was nicht 1:1 der eigentlichen Implementierung entspricht, aber das muss ja nicht zwingend sein):

Der Isomorphismus-Check ist in zwei Teile aufgeteilt:
- find_isomorphismus:
Hier werden alle Fälle ausgeschlossen, bei welchen kein Isomorphismus vorliegen kann. D.h. es wird geprüft, ob bei beiden Graphen dieselbe Anzahl an Knoten und dieselbe Anzahl an Kanten vorliget. D.h. also, dass geprüft wird, ob eine Bijektion vorliegt.

- iso_search:
Hier wird versucht, die Knoten des einen Graphen jenen des anderen zuzuordnen. Das geschieht aber nur, wenn jeweils beide Knoten denselben Eingangs- und Ausgangsgrad haben.

Ausserdem fällt mir gerade auf, dass die Komplexität im schlechtesten Fall O((n+1)!) Zeit und O(n²) Platz benötigen würde...

[EyDu]

Ausserdem fällt mir gerade auf, dass die Komplexität im schlechtesten Fall O((n+1)!) Zeit und O(n²) Platz benötigen würde...

Genau, es liegt irgendwo bei O(n!), auf die Faktoren und Summanden um das n kommt es dabei nicht drauf an. Wenn alle Knoten gleich wären, würde man die Isomorphie sofort erkennen, da immer der erste Knoten matcht. "Nächstbester" Fall wäre also, dass immer genau zwei Knoten die gleiche Anzahl an Kanten haben, dann landet man bei O((0.5*n)!), darauf kommt es dann aber auch nicht mehr an.

Übrigens: Weisst du, ob igraph in python (man kann das Modul ja importieren) O(2^sqrt(n log n)) erreicht?

Ich kenne die Umsetzung in O(2^sqrt(n log n)) nicht, aber die Komplexität ist in der Praxis nicht immer relevant. Bestest beispiel dafür ist lineare Optimierung. Das Simplex-Verfahren hat auch eine exponentielle Laufzeit, ist den bekannten Verfahren in polynomialer Laufzeit aber deutlich überlegen.