Разработка алгоритма: найдите CC, содержащие определенные узлы, из большого списка ребер

Question

Дано: Большой список ребер, около 90-100 миллионов ребер, 2 миллиона узлов. Эти ребра составляют гигантский граф с тысячами компонент связности.

У меня также есть список интересных узлов. Я хочу извлечь края только CC, содержащих эти узлы.

Например, вот крошечный пример: рассмотрим небольшой график с 3 CC внутри него.

      edge_list = [(1,2), (3,2), (1,1), (4,5), (5,6), (4,6), (7,8), (8,9), (9,7)] #three CCs
## Below commands for visualization sake
G = nx.Graph() 
G.add_edges_from(edges)
nx.draw(G, with_labels=True)

И у меня есть интересные узлы: NOI = [1,5]

Мне нужна функция, которая делает следующее:

      CC_list = find_ccs(edge_list, NOI)
print(CC_list)
#output: [[(1,2), (3,2), (1,1)],
#          [(4,5), (5,6), (4,6)]]

Обратите внимание, что возвращаются только края двух CC, содержащих NOI. Я хочу делать это в массовом порядке.

Я открыт для любого решения, использующего Networkx, StellarGraph или, что наиболее предпочтительно, PySpark. Я могу читать список краев с помощью pyspark, и как только у меня есть отфильтрованный список краев, я могу преобразовать его в CC, используя любую библиотеку.

Answer 1

Выберите интересующий узел. Запустите BFS из него, чтобы найти связанный компонент, который его содержит. Каждый раз, когда вы добавляете узел в CC, проверяйте, является ли он интересующим вас узлом, и удаляйте его из набора, чтобы проверить, есть ли он. Повторяйте, пока не найдете все CC, содержащие интересующие узлы.

Время выполнения - O(V+E), где V и E - это узлы и ребра CC, которые содержат интересующие узлы, а не более крупный граф.