图的模式匹配

Question

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

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

请告诉我搜索的方向。

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

Answer 1

这不是Subgraph isomorphism problem吗？如果是，Wikipedia页面包含一个关于算法的部分。

Answer 2

图形模式匹配是graph rewrite tools的核心功能，它们提供了预先实现的功能。

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

Answer 3

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

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