Alle einfachen Pfade von DiGraph in networkx effizient aufzählen

Question

Ich versuche, einige Graph-Analyse auf der Dewey Dezimalklassifikation zu machen, so dass ich einen Abstand zwischen zwei Büchern machen kann. Die DDC hat mehrere Beziehungen: "Hierarchie", "siehe auch", "Klasse-anderswo", hier stelle ich sie mit verschiedenen Farben dar. Da diese Beziehungen nicht symmetrisch sind, werden Sie feststellen, dass wir einen gerichteten Graphen haben. Unten ist ein Bild des Graphen aller Eckpunkte, maximal 4 Kanten entfernt von 394.1.

Die Distanzmetrik zwischen Einstufungen A und B, sollte der kürzeste Weg zwischen A und B sein, jedoch haben die Farben keinen inhärenten gewichteten Wert oder Präferenz. Aber der Benutzer wird einen geben. So gegeben ein Wörterbuch von Gewichten, Beispiel:

weights_dict_test = {'notational_hiearchy':1, 
       'see_reference':0.5, 
       'class_elsewhere':2} 

Ich möchte den gewichteten kürzesten Weg zurückgeben. Ich dachte, das wäre kein Problem, wenn ich alle einfachen Pfade zwischen den beiden Knoten vorverarbeiten könnte, und dann mit dem Gewichtungsdikk das Kürzeste finden würde. Allerdings enthält das Diagramm> 50.000 Knoten. Computing nx.all_simple_paths(G, a, b) wurde nach 24 Stunden der Berechnung nicht zurückgegeben. Gibt es Vorschläge zur Parallelisierung von ? Oder eine Technik, um den kürzesten Pfad zu berechnen, der die weights_dict, die keine Berechnung enthält, berechnet?

Answer 1

Dank @CorleyBrigman. Die Lösung besteht darin, einen neuen Graph W von G zu erstellen, der die Farben von G mit Gewichten ersetzt, die Sie wünschen. Dann können Sie effizient die nx.shortest_path und nx.shortest_path_length mit ihren typischen schnellen Laufzeiten verwenden.

In [23]: 

def update_weights(G, weights_dict):  
    W = nx.DiGraph() 

    for m in G.nodes(): 
     for n in G[m].iterkeys(): 
      relation = G[m][n]['rel'] 
      weight = weights_dict[relation]  
      W.add_edge(m, n, rel=weights_dict[relation])    
    return W 

In [41]: 

weights_dict_test = {'notational_hiearchy':50, 
       'see_reference':0.6, 
       'class_elsewhere':1} 

In [42]: 

W = update_weights(G, weights_dict_test) 

In [43]: 

print len(W) 
print len(G) 

43241  
43241 

In [45]: 

nx.shortest_path_length(W, '394.1', '341.33',weight='rel') 

Out[45]: 

52.2