python - グラフでのパターン マッチング

Question

有向グラフで指定されたパターンに対応するセクションを検索するためのツール/アルゴリズムを見つけようとしています。

A->B->C または A<->B->C

私の検索の方向性を教えてください。

パターンマッチングのことです。指定されたパターンに一致するノードとエッジのすべてのグループを見つける必要があります

Answer 1

これはサブグラフの同型問題ではないでしょうか? はいの場合、ウィキペディアのページにはアルゴリズムに関するセクションが含まれています。

Answer 2

グラフ パターン マッチングは、グラフ書き換えツールの中核となる機能であり、事前に実装されています。

たとえば GrGen では、例のパターンを a:A --> b:B --> c:C として書き留めます。ツールは、ホスト グラフの特性に適合したパターン マッチャーを生成します (グラフに関する統計を考慮します)。

Answer 3

可能なライブラリについては、 Pythonグラフライブラリで答えを見つけることができます。

パターンマッチングについては、探しているパターンがわかっている場合は、グラフをトラバースしてパスを比較するか、関数を使用してノード間のパスを取得し、パターンが存在するかどうかを確認する必要があります。