Durch Dictionaries iterieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Dienstag 20. Mai 2014, 21:22

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

Re: Durch Dictionaries iterieren

Beitragvon BlackJack » Dienstag 20. Mai 2014, 22:16

@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
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Re: Durch Dictionaries iterieren

Beitragvon EyDu » Dienstag 20. Mai 2014, 22:20

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)).
Das Leben ist wie ein Tennisball.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Dienstag 20. Mai 2014, 23:30

@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
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Re: Durch Dictionaries iterieren

Beitragvon EyDu » Mittwoch 21. Mai 2014, 09:01

MarcelF6 hat geschrieben: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.
Das Leben ist wie ein Tennisball.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Mittwoch 21. Mai 2014, 09:52

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
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Mittwoch 21. Mai 2014, 10:22

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

Re: Durch Dictionaries iterieren

Beitragvon BlackJack » Mittwoch 21. Mai 2014, 10:38

@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
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Mittwoch 21. Mai 2014, 11:43

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
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Re: Durch Dictionaries iterieren

Beitragvon EyDu » Mittwoch 21. Mai 2014, 15:42

MarcelF6 hat geschrieben: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.

MarcelF6 hat geschrieben:Ü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.
Das Leben ist wie ein Tennisball.

Wer ist online?

Mitglieder in diesem Forum: Sirius3