Niedrigste gemeinsamen Vorfahren in Python NetworkX

Question

NetworkX Mit

ich niedrigsten gemeinsamen Vorfahren von node1 und node11 in Digraph erhalten möchten.

Folgendes ist der Code.

import networkx as nx 

G = nx.DiGraph() #Directed graph 
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]) 
G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)]) 

ancestors1 = nx.ancestors(G, 1) 
ancestors2 = nx.ancestors(G, 11) 

src_set = set(ancestors1) 
tag_set = set(ancestors2) 
matched_list = list(src_set & tag_set) 

dic = {} 

for elem in matched_list: 
    print elem 
    length1 = nx.dijkstra_path_length(G, elem, 1) 
    path1 = nx.dijkstra_path(G, elem, 1) 
    dist1 = len(path1) 
    length2 = nx.dijkstra_path_length(G, elem, 11) 
    path2 = nx.dijkstra_path(G, elem, 11) 
    dist2 = len(path2) 
    dist_sum = dist1 + dist2 
    dic[elem] = dist_sum 

min_num = min(dic.values()) 
for k, v in sorted(dic.items(), key=lambda x:x[1]): 
    if v != min_num: 
     break 
    else: 
     print k, v 

Ich habe ein Problem mit einer Ausführungsgeschwindigkeit, also möchte ich schnellere Ausführungsgeschwindigkeit.

Wenn Sie eine gute Idee oder einen Algorithmus haben, bitte sagen Sie mir die Idee.

Sorry für das arme Englisch.

Answer 1

Dijkstra in einer Schleife zu wiederholen scheint in der Tat ein Overkill.

Sagen wir die digraph von Umkehren die Kanten erhalten bauen:

import networkx as nx 

G = nx.DiGraph() #Directed graph 
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]) 
edges = [(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)] 
G.add_edges_from([(e[1], e[0]) for e in edges]) 

Jetzt BFS laufen wir von jedem der beiden Knoten:

preds_1 = nx.bfs_predecessors(G, 1) 
preds_2 = nx.bfs_predecessors(G, 11) 

Suche nach der gemeinsamen Eckpunkte erreichbar von beiden Knoten in der umgekehrten Graphen ist einfach:

common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2])) 

Jetzt können Sie das oben genannte leicht abfragen. Um zum Beispiel den gemeinsamen, von beiden erreichbaren Vertex zu finden, der am nächsten bei 1 liegt, ist:

>>> min(common_preds, key=lambda n: preds_1[n]) 
10