NetworkX - 计算断开连接图中的最大匹配
NetworkX - Computing a maximum matching in a disconnected graph
我有两个二分图 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)
我有两个二分图 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)