title: All possible maximum matchings of a bipartite graph
body: <p>I am using <a href="https://networkx.github.io/" rel="noreferrer">networkx</a> to find the <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definition" rel="noreferrer">maximum cardinality matching</a> of a bipartite graph.</p>
  
  <p>The matched edges are not unique for the particular graph.</p>
  
  <p>Is there a way for me to find all the maximum matchings? </p>
  
  <p>For the following example, all edges below can be the maximum matching:</p>
  
  <p><code>{1: 2, 2: 1}</code> or <code>{1: 3, 3: 1}</code> or <code>{1: 4, 4: 1}</code></p>
  
  <pre><code>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()
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/hmNA6.png" rel="noreferrer"><img src="https://i.stack.imgur.com/hmNA6.png" alt="bipartite graph"></a></p>
  
  <p>Unfortunately, </p>
  
  <pre><code>nx.bipartite.maximum_matching(G)
  </code></pre>
  
  <p>only returns</p>
  
  <pre><code>{1: 2, 2: 1}
  </code></pre>
  
  <p>Is there a way I can get the other combinations as well?</p>