Все возможные максимальные совпадения двудольного графа

Question

Я использую networkx, чтобы найти maximum cardinality matching двухстороннего графа.

Соответствующие ребра не уникальны для конкретного графика.

Есть ли способ найти все максимальные соответствия?

В следующем примере, все ребра ниже, могут быть максимально соответствия:

{1: 2, 2: 1} или {1: 3, 3: 1} или {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() 

К сожалению,

только возвращает

{1: 2, 2: 1} 

Есть ли способ получить другие комбинации?

Answer 1

Я прочитал работу Uno и попытался придумать реализацию. Ниже приведен мой очень длинный код с рабочим примером. В этом конкретном случае есть 4 «допустимые» вершины (согласно терминологии Uno), поэтому, переключая каждый с уже покрытой вершиной, вы все вместе можете сопоставить 0 0 0 0 0 0 0 0 0 0 0 0

Я должен признать, что я очень новичок в теории графов, и я не следил за процессами Uno точно, есть незначительные различия и в основном я не пытался делать какие-либо оптимизации. Я действительно пытался понять документ, поскольку, по-моему, объяснения не совсем совершенны, и цифры могут иметь ошибки в них. Поэтому, пожалуйста, используйте с осторожностью, и если вы можете помочь оптимизировать его, это будет здорово!

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

Частичное решение:

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

Это решение, как представляется, работать гораздо больше, отбрасывая линии, которые были использованы уже для того, чтобы найти пары. Однако это не работает для всех из них, так как линии, которые могут соединяться несколько раз, например, в двунаправленном примере 2x3, удаляются перед этим.

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

я сейчас сделал это проверить каждую линию для нескольких пар, так что даже больше комбинаций пойманы. Однако я подозреваю, что достаточно большие наборы не будут полностью учтены. В функции checkAll() я уменьшил избыточность комбинаций, чтобы их было намного легче читать и считать. Надеюсь, это поможет!

Answer 3

В статье «Алгоритмы для перечисления всех совершенных, максимальных и максимальных совпадений в двудольных графах» у Takeaki Uno есть алгоритм для этого. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf

теорема 2 говорит «Максимальные паросочетания в двудольном графе могут быть перечислены в O (млн^1/2 + NNM) время и O (м) пространство, где Нм максимального количество паросочетаний в G. "