Musteranpassung in Grafiken

Question

Ich versuche, Tool/Algorithmus für die Suche nach Abschnitten zu finden, die dem angegebenen Muster in orientiertem Diagramm entsprechen, z. B.:

A-> b-> c oder oder a <-> b-> c

Bitte schlagen Sie mir die Richtung meiner Suche vor.

Ich meine Musteranpassung. Ich muss alle Gruppe von Knoten und Kanten finden, das das angepasste Muster entspricht

Answer 1

Ist das nicht das Problem mit Subgraphisomorphismus? Wenn ja, enthält die Wikipedia -Seite einen Abschnitt über Algorithmen.

Answer 2

Graph -Muster -Matching ist die Funktionalität im Kern von Diagramm -Tools umschreiben, Sie bieten es vorab implementiert.

In EG Grgen schreiben Sie Ihr Beispielmuster als A: A -> B: B -> C: C auf, das Tool erzeugt dann einen Muster -Match für ihn, der an die Eigenschaften des Hostdiagramms angepasst ist (optimiert von durch Berücksichtigung von Statistiken über die Grafik).

Answer 3

In Bezug auf mögliche Bibliotheken finden Sie hier eine Antwort Python Graph Library.

Wenn Sie das Muster -Matching betrifft, müssen Sie nur das Diagramm durchqueren und die Pfade vergleichen, oder Sie können eine Funktion verwenden, um einen Pfad zwischen Knoten abzurufen und zu überprüfen, ob das Muster existiert.