networkx: efficiently find absolute longest path in digraph

Question

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

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.

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

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)).

EDIT: 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.

EDIT: 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?

Answer 1

There is a linear-time algorithm mentioned at http://en.wikipedia.org/wiki/Longest_path_problem

Here is a (very lightly tested) implementation

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)

EDIT: 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)