Python的NetworkX中的最近公共祖先

Question

使用 NetworkX

我想在有向图中从节点1和节点11获取最近公共祖先。

以下是代码。

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

我在执行速度方面遇到了问题，所以我希望能够提高执行速度。

如果你有任何好的想法或算法，请告诉我。

对于我的英语表达不好，非常抱歉。

- kh_si0567

Answer 1

在循环中重新运行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])

现在我们从这两个节点中的每一个运行广度优先搜索：

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

在反向图中找到两个节点都可以到达的公共顶点很容易：

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

现在您可以轻松查询上述内容。例如，要查找可从两个顶点到达的公共顶点，并且最靠近1的是:

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

- Ami Tavory

Answer 2

您可以使用networkx.algorithms.lowest_common_ancestor中定义的函数来实现此操作。它有一个仅适用于树的更快版本，以及一个可以在任何有向无环图上工作的较慢版本。由于您的示例是DAG，因此我将使用后者。

# Same as in your example
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)])

# Compute the lowest common ancestor of 1 and 11. This will print 15.
print nx.algorithms.lowest_common_ancestor(G, 1, 11)

请注意，此计算定义了图源的最大距离作为最低公共祖先；按照这个定义，10和15都是(1,11)的最低公共祖先，并且结果为15。您原来的代码（以及之前的答案）还将从1和11到LCA的路径最小化，这会给出10（总距离为6）而不是15（总距离为7）。如果您也需要该属性，则此模块可能不适合。

使用此模块，查找单个节点对的LCA的运行时间与图的大小成O（n log（n））。查找所有节点对的LCA的运行时间为O（n ^ 3）。

- Alex

---

我已经澄清了我的答案，提供了更多的细节并且通过一个例子进行了演示。但请注意，原始问题明确要求使用我提供的库来完成。 - Alex