使用网络X
我想从有向图中的 node1 和 node11 获得最低共同祖先。
下面是代码。
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
我对执行速度有问题,所以我想要更快的执行速度。
如果你有什么好的想法或算法,请告诉我想法。
抱歉英语不好。
最佳答案
在循环中重新运行 Dijkstra 确实有点矫枉过正。
假设我们构建通过反转边获得的有向图:
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])
现在我们从两个节点中的每一个运行 BFS:
preds_1 = nx.bfs_predecessors(G, 1)
preds_2 = nx.bfs_predecessors(G, 11)
在反转图中找到从两个节点可达的公共(public)顶点很容易:
common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))
现在您可以轻松查询上述内容。例如,要找到从两者可达的公共(public)顶点,最接近 1,是:
>>> min(common_preds, key=lambda n: preds_1[n])
10
关于python - python 的 NetworkX 中的最低共同祖先,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39934721/