2014-01-28 7 views
5

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.Alle einfachen Pfade von DiGraph in networkx effizient aufzählen

Sample Graph

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?

+0

Die Antwort auf Ihre Frage ist: ja, es gibt Techniken dafür, aber der Umfang ist zu breit für eine gute Antwort hier. Versuchen Sie, hier zu starten: http://en.wikipedia.org/wiki/Shortest_path – jonrsharpe

+0

Ich nehme auch genauer an, es würde eine von [gerichtete Graphen mit nichtnegativen Gewichtungen] (http://en.wikipedia.org/wiki/) Shortest_path # Directed_graphs_with_nonnegative_weights). – notconfusing

+0

Wie stellen Sie die verschiedenen Beziehungen dar? ist es nur, wenn die Kante dieses Attribut hat? Es würde wahrscheinlich nicht zu lange dauern, um ein Kantenattribut 'weight' basierend auf Attributen und dem Eingabediktat zu aktualisieren, und dann einfach den eingebauten' kürzesten_pfad' zu verwenden, der bereits Gewichtungen unterstützt. Außerdem ist networkx reines Python und der Code für den kürzesten Pfad ist verfügbar, wenn Sie ihn für diesen speziellen Fall ändern müssen. –

Antwort

0

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