二部图的所有可能的最大匹配 [英] All possible maximum matchings of a bipartite graph

问题描述

我正在使用 networkx 查找匹配的边在特定图形上不是唯一的.

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}或{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()

不幸的是

nx.bipartite.maximum_matching(G)

仅返回

{1: 2, 2: 1}

有没有办法我也可以得到其他组合?

Is there a way I can get the other combinations as well?

推荐答案

我已经阅读了Uno的著作，并试图提出一个实现.下面是我非常冗长的代码，带有一个有效的示例.在这种特殊情况下，有4个可行的"顶点(根据Uno的术语)，因此用已覆盖的顶点切换每个顶点时，您在一起2^4 = 16个不同的可能的最大匹配值.

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

我必须承认我对图论非常陌生，我并没有完全遵循Uno的过程，存在细微的差异，而且大多数情况下我没有尝试进行任何优化.我确实难以理解本文，因为我认为解释不够完美，并且其中的数字可能有误.因此，请谨慎使用，如果可以帮助优化它，那就太好了！

I've to admit that I'm very new to graph theory and I wasn't following Uno's processes exactly, there are minor differences and mostly I didn't attempt to do any optimizations. I did struggle in understanding the paper as I think the explanations are not quite perfect and the figures may have errors in them. So please do use with care and if you can help optimize it that will be real 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)

这篇关于二部图的所有可能的最大匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！