python - 子图同构

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'])