BipartiteMatching.py

"""BipartiteMatching.py

Hopcroft-Karp bipartite maximum-cardinality matching and maximum
independent set for bipartite graphs.

D. Eppstein, April 2002.
"""

from StrongConnectivity import StronglyConnectedComponents

def matching(graph):
    """
    Find maximum cardinality matching of a bipartite graph (U,V,E).
    The input format is a dictionary mapping members of U to lists
    of their neighbors in V.  The output is a triple (M,A,B) where M is a
    dictionary mapping members of V to their matches in U, A is the part
    of the maximum independent set in U, and B is the part of the MIS in V.
    The same object may occur in both U and V, and is treated as two
    distinct vertices if this happens.
    """

    # initialize greedy matching (redundant, but faster than full search)
    matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break

    while True:
        # structure residual graph into layers
        # pred[u] gives the neighbor in the previous layer for u in U
        # preds[v] gives a list of neighbors in the previous layer for v in V
        # unmatched gives a list of unmatched vertices in final layer of V,
        # and is also used as a flag value for pred[u] when u is in the first layer
        preds = {}
        unmatched = []
        pred = {u:unmatched for u in graph}
        for v in matching:
            del pred[matching[v]]
        layer = list(pred)

        # repeatedly extend layering structure by another pair of layers
        while layer and not unmatched:
            newLayer = {}
            for u in layer:
                for v in graph[u]:
                    if v not in preds:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(v)

        # did we finish layering without finding any alternating paths?
        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (matching,list(pred),list(unlayered))

        # recursively search backward through layers to find alternating paths
        # recursion returns true if found path, false otherwise
        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return True
            return False

        for v in unmatched: recurse(v)

def imperfections(graph):
    """
    Find edges that do not belong to any perfect matching of G.
    The input format is the same as for matching(), and the output
    is a subgraph of the input graph in the same format.
    
    For each edge v->w in the output subgraph, imperfections[v][w]
    is itself a subgraph of the input, induced by a set of
    vertices that must be matched to each other, including w but
    not including v.
    """
    M,A,B = matching(graph)
    if len(M) != len(graph):
        return graph    # whole graph is imperfect

    orientation = {}
    for v in graph:
        orientation[v,True]=[]
        for w in graph[v]:
            if M[w] == v:
                orientation[w,False]=[(v,True)]
            else:
                orientation[v,True].append((w,False))

    components = {}
    for C in StronglyConnectedComponents(orientation):
        induced = {v:{w for w,bit2 in C[v,bit]} for v,bit in C if bit}
        for v,bit in C:
            if not bit:   # don't forget the matched edges!
                induced.setdefault(M[v],set()).add(v)
        for v in C:
            components[v] = induced

    imperfections = {}
    for v in graph:
        imperfections[v] = {w:components[w,False] for w in graph[v]
                                 if M[w] != v and
                                 components[v,True] != components[w,False]}
    
    return imperfections