networkx: efficiently find absolute longest path i

问题:

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?

回答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)

回答2:

Aric's revised answer is a good one and I found it had been adopted by the networkx library link

However, I found a little flaw in this method.

if pairs:
    dist[node] = max(pairs)
else:
    dist[node] = (0, node)

because pairs is a list of tuples of (int,nodetype). When comparing tuples, python compares the first element and if they are the same, will process to compare the second element, which is nodetype. However, in my case the nodetype is a custom class whos comparing method is not defined. Python therefore throw out an error like 'TypeError: unorderable types: xxx() > xxx()'

For a possible improving, I say the line

dist[node] = max(pairs)

can be replaced by

dist[node] = max(pairs,key=lambda x:x[0])

Sorry about the formatting since it's my first time posting. I wish I could just post below Aric's answer as a comment but the website forbids me to do so stating I don't have enough reputation (fine...)