Как разделить несвязанный граф networkx на несколько взаимно непересекающихся графов, которые связаны между собой? - PullRequest
Новая
       51

Как разделить несвязанный граф networkx на несколько взаимно непересекающихся графов, которые связаны между собой?

0 голосов
/ 01 мая 2020

У меня есть networkx.Graph объект, представляющий граф , чьи узлы представляют слова Engli sh, а чьи ребра между двумя узлами означают, что два слова, которые представляют эти узлы, имеют по крайней мере один общий когнитивный синоним между их synsets (то есть непустое пересечение ). Я надеюсь, что это интересный или полезный фон для кого-то, но моя проблема является более широко применимой, касающейся графов networkx и Python.

Множество индуцированных подграфов (ребро -индуцированные или индуцированные вершинами) этого графа и ребро не пересекаются, и вершина не пересекаются , и я хотел бы разделить эти подграфы на их собственные networkx.Graph объекты, так что они связаны и взаимно не пересекаются , Возможно, я просто использую неправильные условия поиска для networkx документации, но Я не увидел ничего перспективного, связанного с "дизъюнктом" . Вот несколько примеров из крошечной части графика.

enter image description here

Я просмотрел результаты поиска для [networkx] disjoint на Переполнение стека и не увидел, что я искал. Например, один результат говорил о получении индуцированного подграфа, когда уже есть ребро, установленное для индуцирования из . Или в другом посте говорилось о попытке нарисовать два непересекающихся графика , но это при условии, что они у вас уже есть. Связанный с аспектом теории графов мой вопрос, но не аспект networkx, заключается в том, что, очевидно, существует такая вещь, как алгоритм заполнения потока, который может решить часть моего вопроса .

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

import networkx as nx

g = nx.fast_gnp_random_graph(10, 0.3)

while nx.is_connected(g):
    g = nx.fast_gnp_random_graph(10, 0.3)

На данный момент у нас есть график g. То, о чем я думаю, - это что-то вроде ниже, где я занимаю список графиков, которые должны быть взаимно непересекающимися. Мне нужно не только добавить больше графиков, поскольку я oop над узлами, но и обновить графики как I go. Я подумал, что, возможно, объединения индуцированных графов могут работать, но nx.disjoint_union_all и nx.union либо заставят графы не пересекаться с помощью перемаркировки (я не хочу этого), либо ожидаем, что графы уже не пересекаются. 

graphs = []

for node in g.nodes(): # same 'g' we made above
    if graphs:
        pass
    else:
        graphs.append(g.subgraph([i for i in g.neighbors(node)] +\
                                 [node]).copy())

Как разделить несвязанный граф networkx на несколько взаимно непересекающихся графов, которые связаны между собой?

1 Ответ

1 голос
/ 01 мая 2020

Кажется, вы ищете подключенные компоненты.
Рассмотрите следующий график.

enter image description here

components = [g.subgraph(c).copy() for c in nx.connected_components(g)]
for idx,g in enumerate(components,start=1):
    print(f"Component {idx}: Nodes: {g.nodes()} Edges: {g.edges()}")

Вывод: 

Component 1: Nodes: [0, 1, 2, 5, 6, 7, 8, 9] Edges: [(0, 2), (0, 6), (1, 2), (1, 5), (1, 7), (1, 8), (2, 5), (5, 7), (6, 8), (7, 9), (8, 9)]
Component 2: Nodes: [3, 4] Edges: [(3, 4)]
...