Поиск всех корней внутри DiGraph (networkx) - PullRequest
Новая
       51

Поиск всех корней внутри DiGraph (networkx)

1 голос
/ 19 июня 2020

Предположим, у меня есть этот код, который создает DiGraph: 

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

Как я могу найти все корни на этом графике? ожидаемый результат для этого графика: [1,2]

Если вам это более удобно, я написал код внутри блокнота google colab , где вы можете увидеть график, надеюсь это помогает.

РЕДАКТИРОВАТЬ: это как-то связано с этим вопросом разница в том, что в том сообщении было предположение, что граф связан, поэтому есть только один корень; в моем примере это не так. Могу ли я «разделить» свой график на связанные подграфы, а затем искать root в каждом из них?

1 Ответ

2 голосов
/ 19 июня 2020

Я думаю, что вы не совсем создаете граф, который имеете в виду в этом примере, поскольку все существующие соединения имеют двунаправленные края. Вероятно, вы хотели создать график: 

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)

enter image description here

По порядку чтобы найти root узлов в каждом компоненте, нам сначала нужно сгенерировать индуцированные подграфы из существующих связанных компонентов, для этого у нас есть Graph.subgraph. Затем на каждом подграфе узел root можно найти, выполнив поиск по всем узлам и сохранив узел с in_degree из 0. 

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]
...