Блог

Учитывая большой граф G типа nx.MultiDiGraph() , как мне наиболее эффективным способом найти все связанные узлы?

У меня есть список из N узлов, в котором я хочу найти все узлы, подключенные к нему.

 list_of_nodes = [Node1,Node2,Node3,Node4,...]
  

Я знаю один способ сделать это, который использует bfs_tree

 all_nodes = list(G.nodes())
find_all_connected_edges= []
[find_all_connected_edges.extend(nx.bfs_tree(G, x, reverse=False).edges()) for x in all_nodes]
 
  

Это работает, но довольно медленно для большого числа N, есть ли лучший способ найти все ребра, подключенные к набору из N узлов в сети?

Это зависит от того, какой тип «соединенных узлов» вы хотите. Если вы хотите, чтобы все узлы имели путь в обоих направлениях (u-> v и v-> u), вы можете использовать концепцию сильно связанных компонентов. Если вас не волнует направление ребер, вы можете использовать слабо связанные компоненты.

Если эти концепции соответствуют вашему варианту использования, вы можете использовать либо strongly_connected_components , либо weakly_connected_components для извлечения соответствующих компонентов всех узлов. Затем вы можете создать объединение всех компонентов, в которых находится хотя бы один узел, для получения желаемого набора узлов.