networkx: effizient finden absolut längsten Weg in Digraph

Question

Ich möchte NetzwerkX finden die absolut längste Weg in meiner gerichteten, azyklischen Grafik.

Ich weiß über Bellman-Ford, also negierte ich meine Graphenlängen. Das Problem: networkx bellman_ford() erfordert einen Quellknoten. Ich möchte den absoluten längsten Pfad (oder den kürzesten Pfad nach der Negation) finden, nicht den längsten Pfad von einem bestimmten Knoten.

Natürlich könnte ich bellman_ford() auf jedem Knoten in der Grafik und sortieren, aber gibt es eine effizientere Methode?

Von dem, was ich gelesen habe (zB http://en.wikipedia.org/wiki/Longest_path_problem) Ich weiß, dass es eigentlich nicht eine effizientere Methode sein kann, aber frage mich, ob jemand irgendwelche Ideen hatte (und/oder hatte P = NP (grins) bewiesen).

EDIT: alle Kantenlängen in meinem Graph sind +1 (oder -1 nach der Negation), so eine Methode, die einfach die meisten Knoten besucht, würde auch funktionieren. In der Regel wird es nicht möglich sein, ALLE Knoten zu besuchen.

EDIT: OK, ich erkannte gerade, dass ich einen zusätzlichen Knoten hinzufügen könnte, der einfach mit jedem anderen Knoten im Diagramm verbindet, und dann bellman_ford von diesem Knoten ausführen. Irgendwelche anderen Vorschläge?

Answer 1

Es gibt einen linear-Algorithmus bei http://en.wikipedia.org/wiki/Longest_path_problem erwähnt

Hier ist eine (sehr leicht getestet) Umsetzung

EDIT, dies ist eindeutig falsch, siehe unten. +1 für zukünftige Prüfungen weiter als leicht vor

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 Posting: Korrigierte Fassung (Nutzung auf eigene Gefahr und bitte melden Sie Fehler)

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) 

Answer 2

Antwort Aric berichtigten ist gut und ich fand es wurde von der networkx-Bibliothek übernommen link

Allerdings fand ich einen kleinen Fehler in dieser Methode.

weil pairs eine Liste von Tupeln von (int, nodetype) ist. Beim Vergleichen von Tupeln vergleicht Python das erste Element und wenn sie identisch sind, wird es zum Vergleich des zweiten Elements, das den Knotentyp darstellt, verarbeiten. In meinem Fall ist der Knotentyp jedoch eine benutzerdefinierte Klasse, deren Vergleichsmethode nicht definiert ist. Python daher einen Fehler wie werfen 'Typeerror: unorderable Typen: xxx()> xxx()'

Für eine mögliche Verbesserung, sage ich die Linie

dist[node] = max(pairs) 

kann durch

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

ersetzt werden

Entschuldigung für die Formatierung, da es das erste Mal ist, dass ich Beiträge posten kann. Ich wünschte, ich könnte nur unter Arics Antwort als Kommentar posten, aber die Website verbietet mir dies zu tun, indem ich behaupte, dass ich nicht genug Reputation habe (gut ...)