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

Question

У меня есть двудольный граф, и я хотел бы извлечь двудольное дополнение этого графа. Это граф 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, которые ее обрабатывают?

Answer 1

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

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 возвращает не двудольное дополнение, а полное дополнение. Он содержит ребра между всеми парами, которые не были объединены в исходном графе.