networkx: efficiently find absolute longest path in digraph -

i want networkx find absolute longest path in directed, acyclic graph.

i know bellman-ford, negated graph lengths. problem: networkx's bellman_ford() requires source node. want find absolute longest path (or shortest path after negation), not longest path given node.

of course, run bellman_ford() on each node in graph , sort, there more efficient method?

from i've read (eg, http://en.wikipedia.org/wiki/longest_path_problem) realize there may not more efficient method, wondering if had ideas (and/or had proved p=np (grin)).

edit: edge lengths in graph +1 (or -1 after negation), method visits nodes work. in general, won't possible visit nodes of course.

edit: ok, realized add additional node connects every other node in graph, , run bellman_ford node. other suggestions?

there linear-time algorithm mentioned @ http://en.wikipedia.org/wiki/longest_path_problem

here (very lightly tested) implementation

edit, wrong, see below. +1 future testing more lightly before posting

import networkx nx  def longest_path(g):     dist = {} # stores [node, distance] pair     node in nx.topological_sort(g):         pairs = [[dist[v][0]+1,v] 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) 

edit: corrected version (use @ own risk , please report bugs)

def longest_path(g):     dist = {} # stores [node, distance] pair     node in nx.topological_sort(g):         # pairs of dist,node incoming edges         pairs = [(dist[v][0]+1,v) 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)