NetworkX - 计算不连通图中的最大匹配

Question

我有两个二分图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 是明确二分的，因为它的颜色在其数据中指定。每个顶点都是某些边的一部分。

我不确定我缺少什么连接。

谢谢。

- monadoboi

Answer 1

问题在于你的图不连通。例如，如果你看节点1和18，它们可以属于任一集合(只要它们不在同一集合中)。这些函数没有考虑到节点的属性。这在文档中有所强调。以下是最相关的部分（带有我的强调）：

引用：

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)

- busybear