networkx:有效地找到有向图的绝对最长路径 [英] networkx: efficiently find absolute longest path in digraph

问题描述

我希望networkx在我的指令中找到绝对最长的路径， 非循环图.

I want networkx to find the absolute longest path in my directed, acyclic graph.

我了解Bellman-Ford，因此否定了图形长度.问题: networkx的bellman_ford()需要一个源节点.我想找到 absolute 最长路径(或取反后的最短路径)，而不是 给定节点的最长路径.

I know about Bellman-Ford, so I negated my graph lengths. The problem: networkx's bellman_ford() requires a source node. I want to find the absolute longest path (or the shortest path after negation), not the longest path from a given node.

当然，我可以在图中的每个节点上运行bellman_ford()， 排序，但是有没有更有效的方法?

Of course, I could run bellman_ford() on each node in the graph and sort, but is there a more efficient method?

根据我所读的内容(例如， http://en.wikipedia.org/wiki/Longest_path_problem )我意识到 实际上可能不是一种更有效的方法，但想知道是否 任何人都有任何想法(和/或证明P = NP(咧嘴笑)).

From what I've read (eg, http://en.wikipedia.org/wiki/Longest_path_problem) I realize there actually may not be a more efficient method, but was wondering if anyone had any ideas (and/or had proved P=NP (grin)).

我图中的所有边长均为+1(或否定后为-1)，因此一种仅访问最多节点的方法也可以使用.通常，当然不可能访问所有节点.

all the edge lengths in my graph are +1 (or -1 after negation), so a method that simply visits the most nodes would also work. In general, it won't be possible to visit ALL nodes of course.

好的，我刚刚意识到我可以添加一个简单连接到图中每个其他节点的附加节点，然后从该节点运行bellman_ford.还有其他建议吗?

OK, I just realized I could add an additional node that simply connects to every other node in the graph, and then run bellman_ford from that node. Any other suggestions?

推荐答案

在 http://en.wikipedia.org/wiki/Longest_path_problem

这是一个(经过严格测试的)实现方式

Here is a (very lightly tested) implementation

编辑，这显然是错误的，请参阅下文. +1，以便以后发布之前进行更多测试

EDIT, this is clearly wrong, see below. +1 for future testing more than lightly before posting

import networkx as nx

def longest_path(G):
    dist = {} # stores [node, distance] pair
    for node in nx.topological_sort(G):
        pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node, max_dist  = max(dist.items())
    path = [node]
    while node in dist:
        node, length = dist[node]
        path.append(node)
    return list(reversed(path))

if __name__=='__main__':
    G = nx.DiGraph()
    G.add_path([1,2,3,4])
    print longest_path(G)

已更正版本(使用后果自负，请报告错误)

Corrected version (use at your own risk and please report bugs)

def longest_path(G):
    dist = {} # stores [node, distance] pair
    for node in nx.topological_sort(G):
        # pairs of dist,node for all incoming edges
        pairs = [(dist[v][0]+1,v) for v in G.pred[node]] 
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node,(length,_)  = max(dist.items(), key=lambda x:x[1])
    path = []
    while length > 0:
        path.append(node)
        length,node = dist[node]
    return list(reversed(path))

if __name__=='__main__':
    G = nx.DiGraph()
    G.add_path([1,2,3,4])
    G.add_path([1,20,30,31,32,4])
#    G.add_path([20,2,200,31])
    print longest_path(G)

这篇关于networkx:有效地找到有向图的绝对最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！