グラフのパターンマッチング

Question

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

a-> b-> cまたはa <-> b-> c

検索の方向を提案してください。

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

Answer 1

これはそうではありません サブグラフ同型の問題？はいの場合、Wikipediaページにはアルゴリズムのセクションが含まれています。

Answer 2

グラフパターンマッチングは、 グラフはツールを書き直します, 、彼らはそれを事前に実装して提供します。

たとえば、a：a-> b：b-> c：cとして模範パターンを書き留めます。ツールは、ホストグラフの特性に適合したパターンマッチャーを生成します（最適化グラフに関する統計を考慮に入れます）。

Answer 3

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

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