我想从节点“a”和节点“o”获取所有LCA节点。在
在这个有向图中,节点“l”和节点“m”是LCA节点。在
下面是代码。在
import networkx as nx
def calc_length(Graph, node1, node2, elem):
length1 = nx.shortest_path_length(Graph, node1, elem)
length2 = nx.shortest_path_length(Graph, node1, elem)
length_sum = length1 + length2
return length_sum
G = nx.DiGraph() #Directed graph
G.add_nodes_from(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"])
edges = [("a","b"),("b","c"),("b","d"),("a","e"),("a","h"),("e","f"),("e","g"),("e","i"),("h","l"),("h","m"),("g","j"),("o","p"),("o","n"),("n","m"),("n","l"),("n","k"),("p","j"),]
G.add_edges_from([(e[0], e[1]) for e in edges])
preds_1 = nx.bfs_predecessors(G, "a")
preds_2 = nx.bfs_predecessors(G, "o")
common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))
common_preds = list(common_preds)
dic ={}
for elem in common_preds:
length_sum = calc_length(G, "a", "o", elem)
dic[elem] = length_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
我想要更快的执行速度。在
如果你有比前面提到的更好的方法来解决这个问题,请告诉我。在
我将非常感谢你的帮助。在
这里有几个问题,其中一些问题我已经在评论中指出。问题的一部分是命名法令人困惑:最低的共同祖先(as defined on wikipedia大概在计算机科学中)真的应该被命名为最低共同后代,以符合networkx(以及我所知道的任何理智的网络科学家)使用的命名法。因此,广度优先搜索应该真正遵循后代,而不是前辈。以下内容实现了这种LCA搜索:
相关问题 更多 >
编程相关推荐