Учитывая, что у вас есть {5, 6} двудольный граф только с 10 ребрами, очень вероятно, что ваш граф будет отключен (он настолько мал, что у вас даже есть высокая вероятность наличия изолированных узлов).
import networkx as nx
import random
random.seed(0)
B = nx.bipartite.gnmk_random_graph(5,6,10)
isolated_nodes = set(B.nodes())
for (u, v) in B.edges():
isolated_nodes -= {u}
isolated_nodes -= {v}
print(isolated_nodes)
Покажет вам, что узел с id = 1 изолирован.Чтобы связать график, вы можете сохранить только его самый большой связанный компонент:
import networkx as nx
import random
random.seed(0)
B = nx.bipartite.gnmk_random_graph(5,6,11)
components = sorted(nx.connected_components(B), key=len, reverse=True)
largest_component = components[0]
C = B.subgraph(largest_component)
, который удалит только узел 1 (изолированный узел).
Теперь единственный вопросэто "как случайный этот новый граф".Другими словами, он выбирает любой граф из множества случайно связанных двудольных графов с 5-6 узлами и 10 ребрами с равной вероятностью.Пока я не уверен, но я думаю, что это выглядит прилично.
Конечно, то, что вы предлагаете (выбор графика, пока он не подключен), будет в порядке, но это может быть дорогостоящим (в зависимости от 3 параметровКонечно).
Редактировать Я тупой, это не может быть хорошо, так как новый граф не имеет правильного количества узлов / ребер.Но должно быть лучшее решение, чем просто повторить попытку, пока вы не получите хороший график.Хм, это интересно ...
2-е редактирование Возможно, этот ответ может помочь найти хорошее решение этой проблемы.
3-еотредактируйте и предложите
Как вы заметили в ответе на мой вопрос, принятый ответ не совсем корректен, поскольку сгенерированный график не выбран случайным образом равномерно в наборе ожидаемых графиков.Мы можем сделать что-то похожее здесь, чтобы найти первое достойное решение.Идея состоит в том, чтобы сначала создать связный двудольный граф с минимальным числом ребер, итеративно выбирая изолированные узлы и соединяя их с другой стороной двудольного графа.Для этого мы создадим два набора N и M, создадим первое ребро от N до M.Затем мы выберем случайный изолированный узел (из N или M) и соединим его со случайным неизолированным узлом с другой стороны.Как только у нас больше не будет изолированного узла, у нас будет ровно n + m-1 ребер, поэтому нам потребуется добавить k- (n + m-1) дополнительных ребер в граф, чтобы соответствовать исходным ограничениям.
Вот код, соответствующий этому алгоритму
import networkx as nx
import random
random.seed(0)
def biased_random_connected_bipartite(n, m, k):
G = nx.Graph()
# These will be the two components of the bipartite graph
N = set(range(n))
M = set(range(n, n+m))
G.add_nodes_from(N)
G.add_nodes_from(M)
# Create a first random edge
u = random.choice(tuple(N))
v = random.choice(tuple(M))
G.add_edge(u, v)
isolated_N = set(N-{u})
isolated_M = set(M-{v})
while isolated_N and isolated_M:
# Pick any isolated node:
isolated_nodes = isolated_N|isolated_M
u = random.choice(tuple(isolated_nodes))
# And connected it to the existing connected graph:
if u in isolated_N:
v = random.choice(tuple(M-isolated_M))
G.add_edge(u, v)
isolated_N.remove(u)
else:
v = random.choice(tuple(N-isolated_N))
G.add_edge(u, v)
isolated_M.remove(u)
# Add missing edges
for i in range(k-len(G.edges())):
u = random.choice(tuple(N))
v = random.choice(tuple(M))
G.add_edge(u, v)
return G
B = biased_random_connected_bipartite(5, 6, 11)
Но я повторяю, этот граф не выбран случайным образом равномерно в наборе всех возможных двудольных графов (с ограничениямимы определили на n, m и k).Как я уже говорил в другом посте, этот граф будет иметь некоторые узлы с более высокой степенью, чем другие.Это связано с тем, что мы соединяем изолированные узлы с подключенным компонентом один за другим, поэтому узлы, которые были добавлены раньше в процессе, будут иметь тенденцию привлекать больше узлов (преимущественное присоединение).Я задал вопрос по cstheory , чтобы посмотреть, появятся ли какие-нибудь яркие идеи.
edit Я добавил другое решение, чем представленное здесь, оно немного лучше, но все жене очень хороший