子图同构

Question

在igraph或networkx中，如何在稀疏有向图中找到所有长度为4的简单路径是最快的？一种方法是创建一个长度为4的简单路径图，并使用子图同构vf2函数。这是最好/最快的方法吗？

我没有源节点，希望找到整个图中存在的所有长度为4的简单路径。

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

- user2171391

---

“查找所有长度为4的简单路径”应该理解为“查找所有节点之间最短且长度为4的路径”吗？ - denz

Answer 1

Using a function like this:

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

- mitchus

---

对于networkx，您可以将children(start)替换为nx.neighbors(G, start)，将nodes()替换为nx.nodes(G)。我认为将children()重命名为neighbors()会更有意义，因为图不一定是树形结构。 - Luqmaan

我认为这个答案唯一的问题就是它使用了递归。这似乎不是最有效的选项。 - But I'm Not A Wrapper Class

我不了解igraph或networkx或图形是如何表示的，但如果它使用链表，那么在稀疏图中迭代给定长度的所有路径的这种方法非常高效，基本上是O(N)。 - Gigo

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];

这种构造的物理意义如下：
对于给定矩阵A的每个度数deg，A[i][j]存储从i到j长度为deg的路径数。在第一阶段邻接矩阵只存储长度为1的路径数量。当你将A^N乘以A时，你正在尝试将长度为N的路径扩展到N+1。

a[row][common]*a[common][col]可以解释为“从row到common有a[row][common]种长度为1的方式，而从common到col有a[common][col]种长度为1的方式。根据组合数学的乘法原理，从行到列的长度为1的方法数是a[row][common]*a[common][col]”。

现在有一个重要的修改。您想列出所有路径而不仅仅是计算它们的数量！因此，A[i][j]不是整数，而是整数的vector或ArrayList。将RES[row][col]+ = a[row][common]*a[common][col]替换为RES[row][col].push_back(cartesian_product(a[row][common],a[common][col]))。仅计算路径的复杂度为matrix multiplication*degree= N^3*degree。应用二进制指数运算，您可以获得N^3*log(degree)。在我们的情况下，degree=4，log(4)=2，2~4-无关紧要。但现在您不能只乘2个数字，而应该对长度为N的向量进行笛卡尔积 - 路径。因此，在常见情况下，复杂度增加到N，但在我们的情况下增加到4）。

如果您有任何问题，请随时联系。

- user2104560

---

我正在寻找简单路径。我认为你的矩阵平方方法计算任何路径。 - user2171391

Answer 3

如果你只需要长度为4的路径，那么你可以先找到所有长度为2的路径，然后将它们两两拼接起来以找到结果。理论上，你也可以用同样的方法找到任意长度的路径，但这会更加麻烦（你可能需要构建多个二次幂列表，然后将它们组合以得到其他长度的路径）。

我不太熟悉NetworkX或iGraph，但是对于由邻接列表指定的图（其中n1 [i]是一个可迭代对象，包含所有从节点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子句（在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中实现的图形库调用的解决方案可能会快几个（可能很大）常数因子。

- Blckknght

---

谢谢。一个高度较高的节点会严重减慢它的速度吗？ - Simd

我认为单个高度节点并不太糟糕，但如果你有四个节点的度数远高于平均水平，并且它们相互连接，那么你可能会得到比平均度数的四次方更糟糕的运行时间。我不确定它能否用平均度数的术语来重新表述。 - Blckknght

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文档

要修改它以生成没有“目标”截止的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()

---

希望这对你有用 :)

- Eiyrioü von Kauyf

---

这句话是“从源到目标在图G中生成所有简单路径”，但这不是我要找的。我的问题中没有源节点。 - user2171391

这是一个有向图，您可以将源设置为任何节点，将目标设置为任何其他节点。这比您需要的更具体；这从来不是问题。 - Eiyrioü von Kauyf

我的问题是找到所有长度为4的简单路径，而不是从某个特定节点开始的所有简单路径。 - user2171391

海报正在寻求任何简单路径，而不仅仅是最短路径。 - Gabor Csardi

所以新建两个节点，一个源节点和一个汇节点，并添加从它们到其他每个节点的边。然后请求源节点到汇节点长度为6的简单路径。不过，如果您关心速度，最好编写自己的遍历算法。 - David Eisenstat