I am using networkx to find the maximum cardinality matching of a bipartite graph.
The matched edges are not unique for the particular graph.
Is there a way for me to find all the maximum matchings?
For the following example, all edges below can be the maximum matching:
{1: 2, 2: 1}
or {1: 3, 3: 1}
or {1: 4, 4: 1}
import networkx as nx
import matplotlib.pyplot as plt
G = nx.MultiDiGraph()
edges = [(1,3), (1,4), (1,2)]
nx.is_bipartite(G)
True
nx.draw(G, with_labels=True)
plt.show()
Unfortunately,
nx.bipartite.maximum_matching(G)
only returns
{1: 2, 2: 1}
Is there a way I can get the other combinations as well?
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…