python - 图中的模式匹配

Question

我正在尝试找到用于搜索与定向图中指定模式相对应的部分的工具/算法，例如：

A->B->C 或 或 A<->B->C

请建议我搜索的方向。

我的意思是模式匹配。我需要找到与指定模式匹配的所有节点和边组

Answer 1

这不是子图同构问题吗？如果是，维基百科页面包含关于算法的部分。

Answer 2

图形模式匹配是图形重写工具的核心功能，它们提供了预先实现的功能。

在例如 GrGen 中，您将示例模式写为 a:A --> b:B --> c:C，然后该工具为其生成一个模式匹配器，该匹配器适用于主机图的特征（通过优化考虑到有关图表的统计信息）。

Answer 3

关于可能的库，您可以在这里找到答案Python Graph Library。

至于模式匹配，如果您知道要搜索的模式，您只需要遍历图形并比较路径，或者您可以使用函数检索节点之间的路径并检查模式是否存在。