检查图是否包含给定的诱导子图

Question

我正在尝试检测一些具有随机二合字母属性的最小模式。也就是说，我有一个名为 patterns 的列表，其中包含各种大小的邻接矩阵。例如，我有 [0]（一个接收器），还有一个 [0100 0001 1000 0010]（大小为 4 的循环），[0100, 0010, 0001, 0000] 一个长度为 3 的路径，等等

当我生成有向图时，我会计算所有可能是新模式的集合。然而，在大多数情况下，这是我不关心的事情：例如，如果潜在的新模式是一个大小为 5 的循环，它不会教我任何东西，因为它有一个长度为 3 的循环作为诱导子图。

我想一种方法是这样的：

#D is the adjacency matrix of a possible new pattern
new_pattern = True

for pi in patterns:
    k = len(pi)
    induced_subgraphs = all_induced_subgraphs(D, k)
    for s in induced_subgraphs:
        if isomorphic(s, pi):
            new_pattern = False
            break

其中 all_induced_subgraphs(D,k) 给出所有可能的大小为 k 的 D 的导出子图，并且 isomorphic(s,pi)判断s和pi是否是同构有向字母

但是，检查有向图的所有导出子图似乎非常可怕。有什么妙招吗？

Answer 1

感谢@Stef，我了解到这个问题has a name 并且可以在 netwokx 上使用 this page.

中描述的函数来解决

我个人在我的项目中使用 igraph，所以我将使用 this。

检查图是否包含给定的诱导子图

Checking if a graph contain a given induced subgraph

python

graph-theory

isomorphism