Как получить двудольный дополнительный граф в networkx / python?

У меня двудольный граф, и я хотел бы извлечь двудольное дополнение этого графа. Это график G, объясненный по этой ссылке:

https://www.quora.com/Given-a-bipartite-graph-how-can-I-find-its-subgraph-that-is-a-complete-bipartite-graph-and-has-the-most-vertices

Я попытался сделать это, используя алгоритм дополнения библиотеки Networkx, но у меня были ребра между моими вершинами A и B, которые не должны быть соединены, потому что в двудольном графе нет ребер между одной и той же группой вершин.

Вот код, который я пробовал:

from networkx.algorithms.operators.unary import complement

B = bipartite.random_graph(5, 7, 0.2)
B = complement(B)

Но у меня есть связи в одной группе вершин. Есть ли функция networkx или функция Python, которая ее обрабатывает?


python graph networkx bipartite complement
person anthonya    schedule 29.05.2019    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Попробуй это:

import networkx as nx
B = nx.bipartite.random_graph(5, 7, 0.2)
G = nx.bipartite.complete_bipartite_graph(5,7)   #or use random_graph with probability 1
H = nx.difference(G,B)

Здесь используется разница, которая возвращает граф, ребра которого являются ребрами в G, но не B.

Проблема с тем, что вы делали, заключается в том, что complement возвращает не двудольное дополнение, а полное дополнение. Он содержит ребра между всеми парами, которые не были соединены в исходном графе.

person Joel    schedule 29.05.2019
comment
Спасибо. Что, если я создам двудольный граф с нуля и хочу преобразовать его в полный двудольный граф, чтобы изменить ситуацию? - person anthonya; 29.05.2019
comment
Если я правильно понял ваш вопрос: вы можете сделать то же самое, что я показал, с вашими собственными шагами по созданию B. Вы должны быть осторожны, чтобы имена узлов в вашем B соответствовали именам в G. При необходимости есть способы переименовать узлы в G. - person Joel; 29.05.2019

arrow_upward
0
arrow_downward

использование * помогает нам импортировать все модули из пакета networkx. У нас есть функция под названием дополнение в пакете networkx, я использовал ее в приведенном ниже коде.

from networkx import *
import networkx as nx
c=nx.complete_bipartite_graph(2,5)
cp=nx.complement(c)
nx.draw(cp)
person John Paul    schedule 20.08.2020