NetworkX - вычисление максимального соответствия в отключенном графе - PullRequest
Новая
       36

NetworkX - вычисление максимального соответствия в отключенном графе

0 голосов
/ 25 февраля 2019

У меня есть два двудольных графа G и B, каждый из которых имеет одинаковые узлы, но разное число ребер.Когда я пытаюсь запустить nx.bipartite.maximum_matching на G (с меньшим числом ребер), я получаю ошибку Disconnected graph: Ambiguous solution for bipartite sets., которая аналогична той, что я получил раньше.

Вот G.nodes(data='True'): 

[(0, {'bipartite': 0}), (1, {'bipartite': 0}), (2, {'bipartite': 0}),
 (3, {'bipartite': 0}), (4, {'bipartite': 0}), (5, {'bipartite': 0}),
 (6, {'bipartite': 0}), (7, {'bipartite': 0}), (8, {'bipartite': 0}),
 (9, {'bipartite': 0}), (10, {'bipartite': 1}), (11, {'bipartite': 1}),
 (12, {'bipartite': 1}), (13, {'bipartite': 1}), (14, {'bipartite': 1}),
 (15, {'bipartite': 1}), (16, {'bipartite': 1}), (17, {'bipartite': 1}),
 (18, {'bipartite': 1}), (19, {'bipartite': 1})]

, идентичное B.nodes(data='True').Как видите, раскраска для двух наборов узлов одинакова.

Вот ребра для G: 

[(0, 18), (1, 12), (2, 15), (3, 16), (3, 10), (4, 19), (5, 17),
 (5, 13), (6, 10), (6, 11), (7, 15), (8, 14), (9, 14)]

и ребра для B: 

[(0, 18), (1, 12), (2, 12), (2, 15), (3, 16), (3, 10), (3, 18), (4, 19),
 (5, 17), (5, 13), (6, 10), (6, 11), (6, 18), (6, 13), (7, 18), (7, 19),
 (7, 15), (8, 10), (8, 14), (9, 14)]

где G.edges - это подмножество B.edges.

Я хотел бы найти nx.bipartite.maximum_matching(G).Я предположил, что G был однозначно двудольным, поскольку его окраска указана в его данных.Каждая вершина является частью некоторого ребра.

Я не уверен, что подключение здесь мне не хватает.

Спасибо.

1 Ответ

0 голосов
/ 26 февраля 2019

Проблема в том, что ваш график не подключен.Например, если вы посмотрите на узлы 1 и 18, они могут принадлежать к любому набору (если они не находятся в одном наборе).Функции bipartite не учитывают атрибут bipartite ваших узлов.Это выделено в документации .Вот наиболее важные части (с моим собственным акцентом):

NetworkX не имеет пользовательского класса двудольных графов, но классы Graph () или DiGraph () могут использоваться для представления двудольных графов.Однако вы должны отслеживать, к какому набору принадлежит каждый узел, и следить за тем, чтобы между узлами одного и того же набора не было ребра.Соглашение, используемое в NetworkX, заключается в использовании атрибута узла с именем bipartite со значениями 0 или 1 для идентификации наборов, к которым принадлежит каждый узел. Это соглашение не применяется в исходном коде двудольных функций , это всего лишь рекомендация.

...

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

Однако вы можете явно указать узлы, которые принадлежат одному набору.Используйте параметр top_nodes: 

u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
nx.bipartite.maximum_matching(G, top_nodes=u)
...