search

fujaba / org.fujaba.graphengine

This project's aim is to build a graph engine, that is able to build and compare graphs - and to match patterns and apply actions on the graph, to effectively use it as a graph-transformation framework.
BSD 3-Clause "New" or "Revised" License
1 stars 0 forks source link

implement methods to check for isomorphic graph and isomorphic subgraphs #6

Closed hoechp closed 7 years ago

hoechp commented 7 years ago

Graphen sollen auf Isomorphie (sozusagen Gleichheit) und isomorphen Teilgraph (sozusagen enthalten eines Graphen) testbar sein - dafür sollen Methoden implementiert werden, evtl. im Fall der direkten Isomorphie auch als Override von compareTo. Siehe auch #3

hoechp commented 7 years ago

Ein Vergleich eines Graphen mit m Knoten auf einen isomorphen Teilgraphen mit n Knoten hat meiner Einschätzung nach eine Laufzeit von etwa O(m! * n) - zumindest scheint meine Implementierung mindestens so schlecht zu skalieren.

hoechp commented 7 years ago

Die worst-case Zeitkomplexität von ~O(m! * n) scheint in der Praxis zwar eher unrealistisch, da sich in den allermeisten Fällen sehr viel optimieren lässt, aber große Graphen werden trotzdem wohl schnell schwer zu handhaben - wobei es sehr auf den speziellen Graphen ankommt.

hoechp commented 7 years ago

Im Großen und Ganzen funktioniert die Überprüfung auf einen isomorphen Teilgraphen bereits - in seltenen Fällen treten Fehler auf, aber ich werde die Implementierung ohnehin abändern, denke ich. Mit den geplanten Änderungen sollte sich auch der Speicherbedarf deutlich verbessern.

Grundsätzlich ist mein Algorithmus in etwa wie folgt:

  1. Es wird für jeden Knoten im Sub-Graphen ermittelt, welche Knoten im Basis-Graphen jeweils dazu passen, wenn man schon nur die Attribute und die Anzahl und Namen ausgehender Kanten betrachtet. Findet man für einen Knoten keinen Kanditaten, dann ist es kein isomorpher Teilgraph.
  2. Es wird eine Zuordnung von jedem Knoten aus dem Sub-Graphen auf einen 'geeigneten' Knoten aus dem Basis-Graphen vorgenommen. Dann wird für jeden (Quell-)Knoten aus dem Sub-Graphen und seine ausgehenden Kanten überprüft, ob jeweils der zugeordnete (Quell-)Knoten ebenfalls diese Kante zu dem Ziel-Knoten hat, auf den der Ziel-Knoten aus dem Sub-Graphen zugeordnet ist. Falls nicht, wird die nächstmögliche Zuordnung der Reihe nach überprüft, bis alle Varianten durchgespielt sind. Wird eine Zuordnung gefunden, ist der isomorphe Teilgraph bestätigt und die Zuordnung wird zurückgegeben - wird bis zum Ende keine Zuordnung gefunden, dann ist es kein isomorpher Teilgraph. (eine Variante wäre auch, alle möglichen Zuordnungen zu finden und zurückzugeben)

Für die Überprüfung, ob zwei Graphen isomorph sind, wird die selbe Überprüfung genutzt und dann in Rückrichtung der zurückgegebenen Zuordnung überprüft, ob ebenfalls jeweils alle Attribute und Kanten passen.

hoechp commented 7 years ago

Ist jetzt einfacher, performanter, speicherschonender und - soweit ich sehe - frei von Bugs :)