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

Answer 2

首先，让我们解决更简单的问题 - 计算长度为 4 的路径数。

1) 令 A 为给定图的邻接矩阵。A[i][j] = 1如果顶点 I 和 J 之间存在边，否则为 0。给出某个固定长度A^N的长度路径数.N

2）矩阵平方看起来像

init(RES,0);
for(row=1;N)
      for(col=1;N)
         for(common=1;N)
             RES[row][col] + = a[row][common]*a[common][col];

这种构造的物理意义如下：对于给定矩阵的
每个度数，存储长度 = from的路径数。在第一阶段，邻接矩阵只是存储长度=1的路径数。当你乘法时，你试图扩展长度的路径。degAA[i][j]degi to jA^N to AN to N+1

a[row][common]*a[common][col]可以输入为“ a[row][common]len=1 from rowtocommon和a[common][col]len=1 from commonto的方式col。根据组合乘法原理，len=1 from row to col 的方式数是a[row][common]*a[common][col]”。

现在重要的修改。您想列出所有路径，而不仅仅是计算它们！所以，A[i][j] 不是整数，而是整数的vectoror ArrayList。替换为仅计算路径的复杂度RES[row][col] + = a[row][common]*a[common][col]= N^3*degree。应用二进制取幂可以得到 N^3*log(degree)。在我们的例子中 degree=4, log(4) = 2, 2~4 - 没关系。但是现在你不能只乘以 2 个数字，你应该做向量的笛卡尔积 - len N 的路径。所以复杂性在常见情况下增加到 N，但在我们的例子中增加到 4）RES[row][col].push_back(cartesian_product(a[row][common],a[common][col]))matrix multiplication*degree

如果您有一些问题，欢迎您。

Answer 3

如果它只是您需要的长度正好为 4 的路径，您可以通过首先找到所有长度的两条路径，然后将它们对拼接在一起来轻松找到您的结果。从理论上讲，您可以对任意长度执行此操作，但这会更麻烦（您可能最终会构建几个二次幂列表，然后将它们组合以获得其他长度）。

我对 NetworkX 或 iGraph 不是很流利，但是对于由邻接列表指定的图，我将如何做到这一点（其中n1[i]是一个迭代，其中包含从 node 到它们的边缘的所有节点i）。我认为将其映射到适当的 API 应该很容易。

n1 = adjacency_lists()
n2 = [[(a, b) for a in x for b in n1[a] if i != b] for i, x in enumerate(n1)]
n4 = [[(a, b, c, d) for (a, b) in x for (c, d) in n2[b]
       if i != c and i != d and a != c and a != d]
      for (i, x) in enumerate(n2)]

列表推导中的if子句确保路径简单。我假设从节点到自身没有边。如果不是这样，请在n2列表推导中添加一个额外的if i != a子句（before for b in n1[a]）并添加a != b到现有if子句中。

您可以使用以下命令输出路径：

for i, paths in enumerate(n4):
    for a, b, c, d in paths:
        print("{}->{}->{}->{}->{}".format(i, a, b, c, d))

计算应该具有渐近运行时间O(N*D^4)，其中N是节点数，D是节点的最大度数（我认为这是你能做的最好的）。我怀疑纯 Python 中是否存在更快的解决方案。使用在 C 中实现的图形库调用的解决方案可能会快一个（可能很大）常数因子。

Answer 4

您可以在此处找到相关文档 :)

NetworkX 中的简单路径

本质上它只是某种树搜索

您可以使用节点列表并执行此操作

list_of_nodes = nodes(my_graph)
for mysource in list_of_nodes:
    for mytarget in list_of_nodes:
        if source != target:
             print all_simple_paths(my_graph,source=mysource,target=mytarget, cutoff=4)

如果你想要所有长度为 4 的最短路径，你可以使用``all_pairs_shortest_path_```

paths = all_pairs_shortest_path(my_graph,cutoff=4)
for k,v in paths:
    if len(paths[k][v]) == 4:
        print paths[k][v]

没有内置真正的命令来生成一定长度的所有简单路径，作为找到它的唯一方法是从每个节点生成一棵树，例如执行上面我的 for 循环的修改版本，因为它使用修改后的深度 -第一次搜索。

---

“没有重复顶点的路径称为简单路径” -维基百科

如果您想要论文引文。检查简单路径的唯一方法是从每个节点进行检查。如果您有一个包含 90000 个元素的图表；没有其他方法可以检查两个是否连接：/。“目标”实际上并不重要，因为它只是另一个截止点，但如果你有大量节点，它可以有所作为，所以你就在那里:)。

   " def _all_simple_paths_graph(G, source, target, cutoff=None):
        if cutoff < 1:
            return
        visited = [source]
        stack = [iter(G[source])]
        while stack:
            children = stack[-1]
            child = next(children, None)
            if child is None:
                stack.pop()
                visited.pop()
            elif len(visited) < cutoff:
                if child == target:
                    yield visited + [target]
                elif child not in visited:
                    visited.append(child)
                    stack.append(iter(G[child]))
            else: #len(visited) == cutoff:
                if child == target or target in children:
                    yield visited + [target]
                stack.pop()
                visited.pop()"

上面的代码来自networkx docs

修改它以生成没有“目标”截止的 DFS，您可以使用：

   def _all_simple_paths_graph(G, source, target, cutoff=None):
        if cutoff < 1:
            return
        visited = [source]
        stack = [iter(G[source])]
        while stack:
            children = stack[-1]
            child = next(children, None)
            if child is None:
                stack.pop()
                visited.pop()
            elif len(visited) < cutoff:
                #if child == target:
                #    yield visited + [target]
                #elif child not in visited:
                 if child not in visited:
                    visited.append(child)
                    stack.append(iter(G[child]))
            #else: #len(visited) == cutoff:
                #if child == target or target in children:
                #    yield visited + [target]
                #stack.pop()
                #visited.pop()

---

希望对你有用:)