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

我不知道我错过了什么连接。

谢谢。

Answer 1

问题是你的图形没有连接。例如，如果您查看节点1和18，它们可以属于这两个集合(只要它们不在同一集合内)。bipartite函数不考虑节点的bipartite属性。这在文档中突出显示。以下是(我自己强调的)最相关的部分：

NetworkX没有自定义的二分图类，但是图()或DiGraph()类可以用来表示二分图。但是，您必须跟踪每个节点所属的集合，并确保同一集合的节点之间没有边缘。NetworkX中使用的约定是使用值为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)