我正在寻找一种工具或算法,用来在有向图中查找与特定模式相对应的部分,比如:
A->B->C 或者 A<->B->C
请给我一些搜索的方向。
我说的是模式匹配。我需要找到所有符合特定模式的节点和边的组合。
关于可能用到的库,你可以在这里找到答案 Python图形库。
至于模式匹配,如果你知道自己要找的模式,只需要遍历图形,比较不同的路径,或者你可以使用一个函数来获取节点之间的路径,然后检查这个模式是否存在。
图模式匹配是图重写工具的核心功能,这些工具已经把这个功能做成了现成的。
比如在GrGen这个工具里,你可以把你的示例模式写成 a:A --> b:B --> c:C,之后这个工具会为你生成一个模式匹配器,这个匹配器会根据你所用的图的特点进行调整(它会考虑图的一些统计信息来进行优化)。
这不是所谓的子图同构问题吗?如果是的话,维基百科上有一部分专门讲算法。