查找有向图 (networkx) 中的所有根

Question

假设我有创建有向图的代码：

dict = {1:['a1', 'a2', 'a3'], 2:['a4', 'a5','a7']}
graph = nx.from_dict_of_lists(dict)
digraph = nx.DiGraph(graph)

我怎样才能找到这个图中的所有根？此图的预期输出为 [1,2]

如果对您来说更方便一些，我已经将代码写在一个 google colab notebook 中，您可以在其中看到图表，希望对您有所帮助。

编辑：这在某种程度上与此有关question，不同之处在于post假设图形是连通的，因此只有一个根；在我的示例中并非如此。我可以 'divide' 我的图连接子图，然后在每个子图中搜索根吗？

Answer 1

我认为您并没有完全生成您在本示例中想到的图形，因为所有现有连接都具有双向边。可能您打算生成图表：

d = {1:['a1', 'a2', 'a3'], 2:['a4', 'a5','a7']}
G = nx.from_dict_of_lists(d, create_using=nx.DiGraph)
print(graph.edges())
# OutEdgeView([('1', 'a1'), ('1', 'a2'), ('1', 'a3'), ('2', 'a4'), ('2', 'a5'), ('2', 'a7')])

其中给出了二元图：

plt.subplots(figsize=(12,6))
nx.draw(G, with_labels=True, node_color='lightblue', node_size=500)

为了找到每个组件中的根节点，我们首先需要从现有的连接组件中生成导出子图，因为我们有 0 个中的 Graph.subgraph. Then, on each subgraph, the root node can be found by searching over all nodes, and keeping the one with an in_degree 个。

roots = []
for component in nx.weakly_connected_components(G):
    G_sub = G.subgraph(component)
    roots.extend([n for n,d in G_sub.in_degree() if d==0])

给出：

print(roots)
# [1, 2]

查找有向图 (networkx) 中的所有根

Finding all the roots inside a DiGraph (networkx)

python

graph

networkx