有向无环图中从源到目标的所有路径*长度*

Question

我有一个带有邻接矩阵形状的图（adj_mat.shape=（40004000））。我当前的问题是找到从源（row=0）到目标（col=trans\u mat.shape[0]-1）的路径长度列表（节点顺序并不重要）。

我对寻找路径序列不感兴趣；我只对传播路径长度感兴趣。因此，这不同于找到所有简单的路径——这太慢了（即。找到从源到目标的所有路径；然后给每条路径打分）。有没有一种表演方法可以快速做到这一点？

建议将DFS作为一种可能的策略（此处注明）。我当前的实施（如下）根本不是最优的：

# create graph
G = nx.from_numpy_matrix(adj_mat, create_using=nx.DiGraph())

# initialize nodes
for node in G.nodes:
    G.nodes[node]['cprob'] = []

# set starting node value
G.nodes[0]['cprob'] = [0]

def propagate_prob(G, node):

    # find incoming edges to node
    predecessors = list(G.predecessors(node))
    curr_node_arr = []        

    for prev_node in predecessors:
        # get incoming edge weight
        edge_weight = G.get_edge_data(prev_node, node)['weight']

        # get predecessor node value
        if len(G.nodes[prev_node]['cprob']) == 0:                
            G.nodes[prev_node]['cprob'] = propagate_prob(G, prev_node)            
        prev_node_arr = G.nodes[prev_node]['cprob']   

        # add incoming edge weight to prev_node arr
        curr_node_arr = np.concatenate([curr_node_arr, np.array(edge_weight) + np.array(prev_node_arr)])

    # update current node array
    G.nodes[node]['cprob'] = curr_node_arr
    return G.nodes[node]['cprob']

# calculate all path lengths from source to sink 
part_func = propagate_prob(G, 4000)

Answer 1

使用igraph，我可以在~1秒内计算多达300个节点。我还发现访问相邻矩阵本身（而不是调用igraph的函数来检索边/顶点）也节省了时间。两个关键的瓶颈是1）以有效的方式追加一个长列表（同时保持内存）2）找到并行化的方法。这个时间指数增长超过~300个节点，我很想看看是否有人有更快的解决方案（同时也适合内存）。

import igraph

# create graph from adjacency matrix
G = igraph.Graph.Adjacency((trans_mat_pad > 0).tolist())

# add edge weights
G.es['weight'] = trans_mat_pad[trans_mat_pad.nonzero()]

# initialize nodes
for node in range(trans_mat_pad.shape[0]):
    G.vs[node]['cprob'] = []

# set starting node value
G.vs[0]['cprob'] = [0]

def propagate_prob(G, node, trans_mat_pad):

    # find incoming edges to node
    predecessors = trans_mat_pad[:, node].nonzero()[0] # G.get_adjlist(mode='IN')[node]
    curr_node_arr = []        

    for prev_node in predecessors:
        # get incoming edge weight
        edge_weight = trans_mat_pad[prev_node, node] # G.es[prev_node]['weight']

        # get predecessor node value
        if len(G.vs[prev_node]['cprob']) == 0:
            curr_node_arr = np.concatenate([curr_node_arr, np.array(edge_weight) + propagate_prob(G, prev_node, trans_mat_pad)])
        else: 
            curr_node_arr = np.concatenate([curr_node_arr, np.array(edge_weight) + np.array(G.vs[prev_node]['cprob'])])
    ## NB: If memory constraint, uncomment below
    # set max size
    # if len(curr_node_arr) > 100:
    #     curr_node_arr = np.sort(curr_node_arr)[:100]
    
    # update current node array
    G.vs[node]['cprob'] = curr_node_arr
    return G.vs[node]['cprob']

# calculate path lengths
path_len = propagate_prob(G, trans_mat_pad.shape[0]-1, trans_mat_pad)

Answer 2

我手头没有一个大的例子（例如：。

import networkx as nx

g = nx.DiGraph()

nx.add_path(g, range(7))

g.add_edge(0, 3)
g.add_edge(0, 5)
g.add_edge(1, 4)
g.add_edge(3, 6)

# first step retrieve topological sorting
sorted_nodes = nx.algorithms.topological_sort(g)

start = 0
target = 6

path_lengths = {start: [0]}

for node in sorted_nodes:
    if node == target:
        print(path_lengths[node])
        break

    if node not in path_lengths or g.out_degree(node) == 0:
        continue
    new_path_length = path_lengths[node]
    new_path_length = [i + 1 for i in new_path_length]
    for successor in g.successors(node):
        if successor in path_lengths:
            path_lengths[successor].extend(new_path_length)
        else:
            path_lengths[successor] = new_path_length.copy()

    if node != target:
        del path_lengths[node]

输出：[2,4,2,4,4,6]

如果您只对不同长度的路径数感兴趣，例如上面的例子中的{2:2，4:3，6:1}，您甚至可以将列表减少为dicts。

一些解释我在做什么（我希望对更大的例子也有效）。第一步是检索拓扑排序。为什么啊？然后我知道边在哪个“方向”流动，我可以简单地按照这个顺序处理节点，而不会像递归变体中的“丢失任何边”或任何“回溯”。之后，我用包含当前路径长度的列表初始化开始节点（[0]）。这个列表被复制到所有的后继者，同时更新路径长度（所有元素1）。目标是在每次迭代中计算从起始节点到所有处理节点的路径长度，并将其存储在path_lengths。循环在到达目标-节点后停止。