子图同构

Question

在igraph或networkx中,在稀疏有向图中找到长度为4的所有简单路径的最快方法是什么？一种方法是制作长度为4的简单路径的图形并使用子图同构vf2函数.这是最好/最快的方式吗？

我没有源节点,我想在整个图中存在长度为4的所有简单路径.

在我的数据中,可能很少有这样的路径,我希望能够有效地迭代它们.

Answer 1

使用这样的函数：

def simple_paths(start, length, visited=[]):
    if length==0:
        yield(visited + [start])
    else:
        for child in children(start):
            if child not in visited:
                for path in simple_paths(child, length-1, visited + [start]):
                    yield(path)

您可以通过调用列出长度为 4 的所有简单路径

for start in nodes():
    for path in simple_paths(start, 4):
        print path

上面假设nodes()返回图中所有节点的可迭代，并children(x)返回节点的子节点的可迭代x。

正确地将函数应用simple_paths()到上图会得到：

['5', '9', '3', '1', '0']
['6', '5', '9', '3', '1']
['6', '5', '3', '1', '0']
['9', '5', '3', '1', '0']

这表明该函数：

• 尊重有向边（例如，它不选择['6', '5', '1', '3', '9']）
• 只选择简单路径（例如它不选择['6', '5', '3', '1', '5']）