a10_a_bipartite_matching.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
""""
Bipartite graph matching algorithm
"""

import collections


class Graph(object):
    """
    Simple graph model.
    """

    def __init__(self, num_nodes):
        self.edges = collections.defaultdict(dict)
        self.num_nodes = num_nodes

    def make_edge(self, from_, to, value):
        self.edges[from_][to] = value


class BipartiteGraph(object):
    """
    Bipartite undirected graph model.
    """

    def __init__(self):
        self.edges = set()
        self.num_u = 0
        self.num_v = 0

    def make_edge(self, u, v):
        self.edges.add((u, v))
        self.num_u = max(self.num_u, u + 1)
        self.num_v = max(self.num_v, v + 1)

    def to_graph(self):
        g = Graph(self.num_u + self.num_v)
        edges = [(u, v + self.num_u) for u, v in self.edges]

        for from_, to in edges:
            g.make_edge(from_, to, 1)
        return g


def bipartite_matching(bipartite_graph):
    """
    Returns one of the combinations for the maximum bipartite matching
    """

    # Convert to normal graph.
    g = bipartite_graph.to_graph()

    def dfs(v):
        used.add(v)
        for u in g.edges[v]:
            w = match.get(u)
            if w is None or w not in used and dfs(w):
                match[v] = u
                match[u] = v
                return True
        return False

    ret = 0  # maximum number of matching
    match = {}  # result of matching

    for v in xrange(g.num_nodes):
        if not v in match:
            used = set()
            if dfs(v):
                ret += 1

    # Put back to bipartite graph's index.
    return [(u, v - bipartite_graph.num_u) for u, v in match.items() if u < bipartite_graph.num_u]


if __name__ == '__main__':
    a = BipartiteGraph()
    for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)]:
        a.make_edge(p, q)

    #
    #    0   0
    #      X
    #    1 - 1
    #      X
    #    2   2
    #

    b = BipartiteGraph()
    for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2)]:
        b.make_edge(p, q)

    #
    #    0   0
    #      X
    #    1 - 1
    #      X
    #    2 - 2
    #

    c = BipartiteGraph()
    for p, q in [(1, 0), (1, 2)]:
        c.make_edge(p, q)

    #
    #    0   0
    #      /
    #    1   1
    #      \
    #        2
    #

    d = BipartiteGraph()
    for p, q in [(0, 1), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (3, 4), (4, 3)]:
        d.make_edge(p, q)

    #
    #    0   0
    #      X
    #    1 - 1
    #      /
    #    2 - 2
    #      X
    #    3   3
    #      X
    #    4   4
    #

    for g in a, b, c, d:
        print bipartite_matching(g)