NetworkX - 计算断开图中的最大匹配

Question

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

我不确定我在这里缺少什么连接。

谢谢。

Answer 1

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

\n

\n

NetworkX 没有自定义二分图类，但 Graph() 或 DiGraph() 类可用于表示二分图。但是，您必须跟踪每个节点属于哪个集合，并确保同一集合的节点之间没有边。NetworkX 中使用的约定是使用名为 bipartite 的节点属性（值为 0 或 1）来标识每个节点所属的集合。此约定在二分函数的源代码中并未强制执行，它\xe2\x80\x99s 只是一个建议。

\n

...

\n

但是，如果输入图未连接，则可能有不止一种着色。这就是为什么我们要求用户传递一个容器，其中包含一个二分节点集的所有节点作为大多数二分函数的参数。

\n

\n

但是，您可以明确声明属于一组的节点。使用参数top_nodes：

\n

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

\n