python - All possible maximum matchings of a bipartite graph

Question

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?

Answer 1

The paper "Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs" by Takeaki Uno has an algorithm for this. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf

Theorem 2 says "Maximum matchings in a bipartite graph can be enumerated in O(mn^1/2+ nNm) time and O(m) space, where Nm is the number of maximum matchings in G."