NetworkX: skutecznie znaleźć absolutną najdłuższą ścieżkę w dwuznakiem

Question

chcę NetworkX znaleźć absolutną najdłuższą drogę w mojej reżyserii, graf acykliczny.

Wiem o Bellman-Ford, więc zanegowałem moje długości wykresów. Problem: networkx's bellman_ford() wymaga węzła źródłowego. Chcę znaleźć absolutną najdłuższą drogę (lub najkrótszą drogę po negacji), a nie najdłuższą ścieżkę od danego węzła.

Oczywiście mogłem uruchomić bellman_ford() na każdym węźle na wykresie i sortować , ale czy istnieje bardziej wydajna metoda?

Z tego co czytałem (np http://en.wikipedia.org/wiki/Longest_path_problem) Zdaję sobie sprawę, że rzeczywistości nie może być bardziej skuteczny sposób, ale zastanawiałem się, czy ktoś miał jakieś pomysły (i/lub okazały P = NP (uśmiech)).

Uwaga: Wszystkie długości krawędzi w moim wykresu są +1 (lub -1 po negacji), a zatem sposób, który po prostu odwiedza większość węzłów będzie działać. Ogólnie rzecz biorąc, nie będzie można oczywiście odwiedzić WSZYSTKICH węzłów.

EDIT: OK, po prostu sobie sprawę, że można dodać dodatkowy węzeł, który po prostu łączy się z każdym innym węzłem na wykresie, a następnie uruchomić bellman_ford z tego węzła. Jakieś inne sugestie?

Answer 1

Jest algorytm liniowy raz wspomniano w http://en.wikipedia.org/wiki/Longest_path_problem

Oto (bardzo lekko testowane) realizacja

EDIT, to wyraźnie źle, patrz poniżej. +1 dla przyszłości testowanie bardziej niż lekko przed wysłaniem

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: Poprawione wersję (Używaj na własne ryzyko i prosimy o zgłaszanie błędów)

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

Arie za zrewidowane odpowiedź jest dobra i znalazłem go został przyjęty przez NetworkX biblioteki link

jednak znalazłem mały błąd w tej metodzie.

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

ponieważ pary to lista krotek (int, nodetype). Porównując krotki, python porównuje pierwszy element i jeśli są one takie same, przetworzy proces porównywania drugiego elementu, który jest nodetype. Jednak w moim przypadku nodetype to klasa niestandardowa, której metoda porównywania nie jest zdefiniowana. Dlatego Python wyrzucić błąd typu 'Błąd typu: unorderable typy: xxx()> xxx()'

do ewentualnej poprawia, mówię linia

dist[node] = max(pairs) 

może być zastąpiony przez

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

Przepraszamy za formatowanie, ponieważ jest to moja pierwsza publikacja. Chciałbym po prostu zamieścić poniżej odpowiedź Arica jako komentarz, ale strona zabrania mi tego robić, stwierdzając, że nie mam wystarczającej reputacji (dobrze ...)