All possible maximum matches of a bipartite graph

Question

I use networkx to find the maximum power of bipartite mapping .

Corresponding edges are not unique to a particular graph.

Is there a way to find all the maximum matches?

In the following example, all edges below can be the maximum match:

{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) 

returns

 {1: 2, 2: 1} 

Is there any way to get other combinations?

Answer 1

I read Uno's work and tried to come up with an implementation. Below is my very long code with a working example. In this particular case, there are 4 "admissible" vertices (according to Uno-terminology), therefore, switching each with a vertex already covered, you all together 2^4 = 16 different possible maximum matches.

I have to admit that I am very new to graph theory, and I definitely did not follow Uno processes, there are slight differences and basically I did not try to make any optimizations. I really tried to understand the document, because, in my opinion, the explanations are not entirely perfect, and the numbers may have errors in them. Therefore, please use with caution, and if you can help optimize it, it will be great!

 import networkx as nx from networkx import bipartite def plotGraph(graph): import matplotlib.pyplot as plt fig=plt.figure() ax=fig.add_subplot(111) pos=[(ii[1],ii[0]) for ii in graph.nodes()] pos_dict=dict(zip(graph.nodes(),pos)) nx.draw(graph,pos=pos_dict,ax=ax,with_labels=True) plt.show(block=False) return def formDirected(g,match): '''Form directed graph D from G and matching M. <g>: undirected bipartite graph. Nodes are separated by their 'bipartite' attribute. <match>: list of edges forming a matching of <g>. Return <d>: directed graph, with edges in <match> pointing from set-0 (bipartite attribute ==0) to set-1 (bipartite attrbiute==1), and the other edges in <g> but not in <matching> pointing from set-1 to set-0. ''' d=nx.DiGraph() for ee in g.edges(): if ee in match or (ee[1],ee[0]) in match: if g.node[ee[0]]['bipartite']==0: d.add_edge(ee[0],ee[1]) else: d.add_edge(ee[1],ee[0]) else: if g.node[ee[0]]['bipartite']==0: d.add_edge(ee[1],ee[0]) else: d.add_edge(ee[0],ee[1]) return d def enumMaximumMatching(g): '''Find all maximum matchings in an undirected bipartite graph. <g>: undirected bipartite graph. Nodes are separated by their 'bipartite' attribute. Return <all_matches>: list, each is a list of edges forming a maximum matching of <g>. ''' all_matches=[] #----------------Find one matching M---------------- match=bipartite.hopcroft_karp_matching(g) #---------------Re-orient match arcs--------------- match2=[] for kk,vv in match.items(): if g.node[kk]['bipartite']==0: match2.append((kk,vv)) match=match2 all_matches.append(match) #-----------------Enter recursion----------------- all_matches=enumMaximumMatchingIter(g,match,all_matches,None) return all_matches def enumMaximumMatchingIter(g,match,all_matches,add_e=None): '''Recurively search maximum matchings. <g>: undirected bipartite graph. Nodes are separated by their 'bipartite' attribute. <match>: list of edges forming one maximum matching of <g>. <all_matches>: list, each is a list of edges forming a maximum matching of <g>. Newly found matchings will be appended into this list. <add_e>: tuple, the edge used to form subproblems. If not None, will be added to each newly found matchings. Return <all_matches>: updated list of all maximum matchings. ''' #---------------Form directed graph D--------------- d=formDirected(g,match) #-----------------Find cycles in D----------------- cycles=list(nx.simple_cycles(d)) if len(cycles)==0: #---------If no cycle, find a feasible path--------- all_uncovered=set(g.node).difference(set([ii[0] for ii in match])) all_uncovered=all_uncovered.difference(set([ii[1] for ii in match])) all_uncovered=list(all_uncovered) #--------------If no path, terminiate-------------- if len(all_uncovered)==0: return all_matches #----------Find a length 2 feasible path---------- idx=0 uncovered=all_uncovered[idx] while True: if uncovered not in nx.isolates(g): paths=nx.single_source_shortest_path(d,uncovered,cutoff=2) len2paths=[vv for kk,vv in paths.items() if len(vv)==3] if len(len2paths)>0: reversed=False break #----------------Try reversed path---------------- paths_rev=nx.single_source_shortest_path(d.reverse(),uncovered,cutoff=2) len2paths=[vv for kk,vv in paths_rev.items() if len(vv)==3] if len(len2paths)>0: reversed=True break idx+=1 if idx>len(all_uncovered)-1: return all_matches uncovered=all_uncovered[idx] #-------------Create a new matching M'------------- len2path=len2paths[0] if reversed: len2path=len2path[::-1] len2path=zip(len2path[:-1],len2path[1:]) new_match=[] for ee in d.edges(): if ee in len2path: if g.node[ee[1]]['bipartite']==0: new_match.append((ee[1],ee[0])) else: if g.node[ee[0]]['bipartite']==0: new_match.append(ee) if add_e is not None: for ii in add_e: new_match.append(ii) all_matches.append(new_match) #---------------------Select e--------------------- e=set(len2path).difference(set(match)) e=list(e)[0] #-----------------Form subproblems----------------- g_plus=g.copy() g_minus=g.copy() g_plus.remove_node(e[0]) g_plus.remove_node(e[1]) g_minus.remove_edge(e[0],e[1]) add_e_new=[e,] if add_e is not None: add_e_new.extend(add_e) all_matches=enumMaximumMatchingIter(g_minus,match,all_matches,add_e) all_matches=enumMaximumMatchingIter(g_plus,new_match,all_matches,add_e_new) else: #----------------Find a cycle in D---------------- cycle=cycles[0] cycle.append(cycle[0]) cycle=zip(cycle[:-1],cycle[1:]) #-------------Create a new matching M'------------- new_match=[] for ee in d.edges(): if ee in cycle: if g.node[ee[1]]['bipartite']==0: new_match.append((ee[1],ee[0])) else: if g.node[ee[0]]['bipartite']==0: new_match.append(ee) if add_e is not None: for ii in add_e: new_match.append(ii) all_matches.append(new_match) #-----------------Choose an edge E----------------- e=set(match).intersection(set(cycle)) e=list(e)[0] #-----------------Form subproblems----------------- g_plus=g.copy() g_minus=g.copy() g_plus.remove_node(e[0]) g_plus.remove_node(e[1]) g_minus.remove_edge(e[0],e[1]) add_e_new=[e,] if add_e is not None: add_e_new.extend(add_e) all_matches=enumMaximumMatchingIter(g_plus,match,all_matches,add_e_new) all_matches=enumMaximumMatchingIter(g_minus,new_match,all_matches,add_e) return all_matches if __name__=='__main__': g=nx.Graph() edges=[ [(1,0), (0,0)], [(1,1), (0,0)], [(1,2), (0,2)], [(1,3), (0,2)], [(1,4), (0,3)], [(1,4), (0,5)], [(1,5), (0,2)], [(1,5), (0,4)], [(1,6), (0,1)], [(1,6), (0,4)], [(1,6), (0,6)] ] for ii in edges: g.add_node(ii[0],bipartite=0) g.add_node(ii[1],bipartite=1) g.add_edges_from(edges) plotGraph(g) all_matches=enumMaximumMatching(g) for mm in all_matches: g_match=nx.Graph() for ii in mm: g_match.add_edge(ii[0],ii[1]) plotGraph(g_match) 

Answer 2

Takeaki Uno has an algorithm in the paper "Algorithms for listing all perfect, maximum, and maximum matches in bipartite graphs." http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf

Theorem 2 says "The maximum correspondences in a bipartite graph can be listed in O (mn ^ 1/2 + nNm) and O (m), where Nm is the number of maximal matches in G."

Answer 3

Partial Solution:

 import networkx as nx import matplotlib.pyplot as plt G = nx.complete_bipartite_graph(2, 3) nx.draw(G, with_labels=True) edges = G.edges() A = [] maximum = len(nx.bipartite.eppstein_matching(G)) for x in range(len(edges)): b = nx.bipartite.eppstein_matching(G) if len(b) != maximum: break A+=[nx.bipartite.eppstein_matching(G)] G.remove_edge(*edges[x]) print(list(eval(x) for x in set(str(x) for x in A))) plt.show() 

This solution works much more by discarding lines that have already been used to find pairs. However, this does not work for all of them, since lines that can be connected several times, for example, in the 2x3 bidirectional example, are deleted before that.

EDIT:

 import networkx as nx import matplotlib.pyplot as plt G = nx.complete_bipartite_graph(2, 3) nx.draw(G, with_labels=True) def checkAll(G,m): b = nx.bipartite.eppstein_matching(G) # Finds first match c = list(b.keys()) for y in c[int(len(c)/2):]: # Reduces to one occurrence per line b.pop(y) if len(b) != m: # If new size, break return 0 return b # Add to list of possibilities edges = G.edges() A = [] m = len(nx.bipartite.eppstein_matching(G))/2 # Create an expected maximum for x in range(len(edges)): b = checkAll(G,m) if b: A += [b] else: break keys = list(b.keys()) cache = (keys[0],b[keys[0]]) removed = [] while 1: removed += [(keys[1],b[keys[1]])] G.remove_edge(keys[1],b[keys[1]]) # Remove first option b = checkAll(G,m) if b and cache == (keys[0],b[keys[0]]): A += [b] else: break G.add_edges_from(removed) G.remove_edge(*edges[x]) print(list(eval(x) for x in set(str(x) for x in A))) plt.show() 

Now I checked each line for several pairs, so even more combinations are caught. However, I suspect that sufficiently large sets will not be fully accounted for. In the checkAll() function, I reduced the redundancy of the combinations, so it’s much easier to read and read them. Hope this helps!