networkx: trova in modo efficiente il percorso più lungo nel digramma

Question

Voglio che networkx trovi il percorso assoluto più lungo nel mio grafico aciclico diretto, .

Conosco Bellman-Ford, quindi ho annullato le lunghezze dei grafici. Il problema: bellman_ford() di networkx richiede un nodo di origine. Voglio trovare il assoluto percorso più lungo (o il percorso più breve dopo la negazione), non il percorso più lungo da un determinato nodo.

Ovviamente, potrei eseguire bellman_ford() su ciascun nodo nel grafico e ordinamento , ma esiste un metodo più efficiente?

Da quello che ho letto (per esempio, http://en.wikipedia.org/wiki/Longest_path_problem) Mi rendo conto che ci realtà non può essere un metodo più efficiente, ma chiedevo se qualcuno avesse tutte le idee (e/o aveva dimostrato P = NP (ghigno)).

MODIFICA: tutte le lunghezze del bordo nel mio grafico sono +1 (o -1 dopo la negazione), quindi funzionerebbe anche un metodo che visita semplicemente la maggior parte dei nodi. In generale, non sarà possibile visitare TUTTI i nodi, naturalmente.

MODIFICA: OK, ho appena realizzato che potrei aggiungere un nodo aggiuntivo che si connette semplicemente a tutti gli altri nodi nel grafico e quindi eseguire bellman_ford da quel nodo. Qualche altro suggerimento?

Answer 1

C'è un algoritmo di tempo lineare accennato http://en.wikipedia.org/wiki/Longest_path_problem

Ecco un (molto leggermente testato) implementazione

EDIT, questo è chiaramente sbagliato, vedi sotto. +1 per il futuro test più leggera prima di pubblicare

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: corretto versione (uso a proprio rischio e vi prego di segnalare i bug)

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

risposta rivisto Aric è una buona e ho trovato era stata adottata dalla libreria networkx link

Tuttavia, ho trovato un piccolo difetto in questo metodo.

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

perché coppie è un elenco di tuple di (int, nodetype). Quando si confrontano le tuple, python confronta il primo elemento e se sono uguali, elaborerà per confrontare il secondo elemento, che è nodetype. Tuttavia, nel mio caso il nodetype è una classe personalizzata il cui metodo di confronto non è definito. Python quindi buttare fuori un errore del tipo 'TypeError: tipi non ordinabile: xxx()> xxx()'

Per una possibile miglioramento, dico la linea

dist[node] = max(pairs) 

può essere sostituito da

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

Ci scusiamo per la formattazione poiché è la prima volta che pubblichi. Vorrei poter postare solo sotto la risposta di Aric come commento ma il sito web mi proibisce di farlo affermando che non ho abbastanza reputazione (bene ...)