Как получить двудольный граф дополнений в networkx/python?
У меня есть двудольный граф, и я хотел бы извлечь двудольное дополнение этого графа. Это график G, объясненный в этой ссылке:
Я попытался сделать это, используя алгоритм дополнения библиотеки Networkx, но получил ребра между моими вершинами A и B, которые не должны быть соединены, потому что в двудольном графе нет ребер между одной и той же группой вершин.
Вот код, который я пробовал:
from networkx.algorithms.operators.unary import complement
B = bipartite.random_graph(5, 7, 0.2)
B = complement(B)
Но у меня есть соединения в одну и ту же группу вершин. Есть ли функция networkx или функция Python, которая с этим справляется?
Ответы 2
Попробуй это:
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 возвращает не двудольное дополнение, а полное дополнение. Он содержит ребра между всеми парами, которые не были соединены в исходном графе.
Если я правильно понял ваш вопрос: вы можете сделать то же самое, что я показал, со своими шагами по созданию B. Вы должны быть осторожны, чтобы имена узлов в вашем B соответствовали именам в G. Есть способы переименовать узлы в G, если это необходимо.
использование * помогает нам импортировать все модули из пакета networkx. У нас есть функция, называемая дополнением в пакете networkx, я использовал ее в приведенном ниже коде.
from networkx import *
import networkx as nx
c=nx.complete_bipartite_graph(2,5)
cp=nx.complement(c)
nx.draw(cp)
Спасибо. Что делать, если я создаю двудольный граф с нуля и хочу преобразовать его в полный двудольный граф, чтобы изменить ситуацию?