时间戳

首页 > 解决方案 > 有向无环图中从源到目标的所有路径*长度*

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

问题描述

我有一个具有邻接矩阵形状 ( adj_mat.shape = (4000, 4000)) 的图。我当前的问题涉及查找从源 ( ) 到目标 ( ) 的路径长度列表（节点序列不是那么重要）。row = 0 col = trans_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)

标签： graphnetworkxigraphdepth-first-searchbreadth-first-search

解决方案

我没有手动的大例子（例如> 300个节点），但我找到了一个非递归解决方案：

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}上面的例子，您甚至可以将列表减少为字典。

背景

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

推荐阅读