CODEWITHSUNDEEP
pythonnetworkxbipartite
monadoboi
monadoboi

Reputation: 1811

NetworkX - Computing a maximum matching in a disconnected graph

I have two bipartite graphs G and B, both of which have exactly the same nodes, but a different number of edges. When I try to run nx.bipartite.maximum_matching on G (with the lower number of edges), I get an error Disconnected graph: Ambiguous solution for bipartite sets., which is a similar one to what I have received before.

Here is the 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})]

which is identical to B.nodes(data='True'). As you can see, the colouring for the two sets of nodes is the same.

Here are the edges for 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)]

and the edges for 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)]

where G.edges is a subset of B.edges.

I would like to find the nx.bipartite.maximum_matching(G). I assumed G was unambiguously bipartite as its colouring is specified in its data. Every vertex is part of some edge.

I'm not sure what connectivity I'm missing here.

Thanks.

Upvotes: 4

Views: 4180

Answers (1)

busybear
busybear

Reputation: 10590

The issue is that your graph is not connected. If you look at the nodes 1 and 18, for instance, they can belong to either set (as long as they are not in the same set). The bipartite functions do not take into account the bipartite attribute of your nodes. This is highlighted in the documentation. Here are the most relevant parts (with my own emphasis):

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.

However, you can explicitly state the nodes that belong in one set. Use the parameter top_nodes:

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

Upvotes: 6

Related Questions