Пересечение графов в NetworkX

Question

У меня есть 2 графика, и я хотел бы получить граф с их пересекающимися ребрами. Например, если у нас есть:

import networkx as nx

graph1 = nx.barabasi_albert_graph(100, 3)
graph2 = nx.watts_strogatz_graph(100, 4, 0.15)
nx.draw_networkx(graph1, with_labels=True)
nx.draw_networkx(graph2, with_labels=True)

Как я могу найти их пересечение?

Answer 1

Ответ зависит от того, как вы действительно определяете пересечение . Если вы хотите сохранить все пересекающиеся ребра на обоих графиках, вы можете использовать nx.intersection, который, как упоминалось в документах, сохраняет все ребра, существующие на обоих графиках. Допустим, у вас есть следующие графики:

graph1 = nx.barabasi_albert_graph(100, 3)
graph2 = nx.watts_strogatz_graph(100, 4, 0.15)

, которые дают следующие графики:

pos = nx.spring_layout(graph1, scale=20, k=3/np.sqrt(graph1.order()))
nx.draw(graph1, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

pos = nx.spring_layout(graph2, scale=20, k=3/np.sqrt(graph2.order()))
nx.draw(graph2, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

Мы можем сгенерировать пересечение обоих графиков с помощью nx.intersection. Это требует, чтобы наборы узлов из обоих графиков были одинаковыми. Также пересекающиеся узлы не будут удалены. Для этого вы можете получить изолированные узлы с помощью nx.isolates и удалить их из графика:

g_int = nx.intersection(graph1, graph2)
g_int.remove_nodes_from(list(nx.isolates(g_int)))

pos = nx.spring_layout(g_int, scale=20, k=3/np.sqrt(g_int.order()))
nx.draw(g_int, pos=pos, with_labels=True, k=13.8, node_color='lightgreen', node_size=800)

Мы можем легко проверить, что это действительно пересечение ребер обоих графиков:

set_int = set(graph2.edges()).intersection(graph1.edges())
G_set_int = nx.from_edgelist(set_int)
list(nx.connected_components(G_set_int))
# [{1, 2, 3, 4, 6}, {48, 50}, {8, 9, 10, 72}, {76, 78}, {85, 87}, {53, 54}, 
#  {40, 38}, {28, 30}, {20, 21}]