我有两个二分图 G 和 B,它们都具有完全相同的节点,但边数不同。当我尝试在 G 上运行 nx.bipartite.maximum_matching(边数较少)时,出现错误 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 和 18,它们可以属于任一集合(只要它们不在同一集合中)。 bipartite 函数不考虑节点的 bipartite 属性。这在 documentation 中突出显示.以下是最相关的部分(我自己强调):
NetworkX does not have a custom bipartite graph class but the Graph() or DiGraph() classes can be used to represent bipartite graphs. However, you have to keep track of which set each node belongs to, and make sure that there is no edge between nodes of the same set. The convention used in NetworkX is to use a node attribute named bipartite with values 0 or 1 to identify the sets each node belongs to. This convention is not enforced in the source code of bipartite functions, it’s only a recommendation.
...
However, if the input graph is not connected, there are more than one possible colorations. This is the reason why we require the user to pass a container with all nodes of one bipartite node set as an argument to most bipartite functions.
但是,您可以明确说明属于一组的节点。使用参数top_nodes:
u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
nx.bipartite.maximum_matching(G, top_nodes=u)
