increase the efficiency of a matching algorithm

Question

I'm trying to create an algorithm that will match one set of objects with another. Each of the objects from one group can be matched with some of the objects from another group. Once an item has been matched, it cannot be matched to another item. My current implementation iterates over each of the objects and attempts to find a solution where each object has a match. I've done this recursively, but this method quickly becomes unusable as the processing time increases exponentially. Here is a trivial example of what I've written:

def demo_match():
    possible_matches = {
        "x": {1, 2},
        "y": {2, 3},
        "z": {1, 2}
    }

    used_numbers = set()

    matched = {}

    def match_items(remaining_items_to_match):

        for letter in remaining_items_to_match:
            possible_numbers = possible_matches[letter]
            available_numbers = possible_numbers.difference(used_numbers)
            print(f"can match '{letter}' with {available_numbers}")
            if not available_numbers:
                raise ValueError(f"there are no possible matches for {letter}")
            for possible_match in available_numbers:
                try:
                    used_numbers.add(possible_match)
                    matched[letter] = possible_match
                    print(f"'{letter}' has been matched with {possible_match}")
                    if len(remaining_items_to_match) is 1:
                        return matched
                    # remove this item and process the remaining
                    next_remaining_items = remaining_items_to_match[1:]
                    return match_items(next_remaining_items)
                except ValueError:
                    print(f"***** found a dead end, unmatching '{letter}' and {possible_match} *****")
                    used_numbers.remove(possible_match)
                    del matched[letter]
            raise ValueError("ran out of available numbers to match")

    print(f"\nMatch Solution: {match_items(list(possible_matches.keys()))}")

The actual implementation assigns weights to the possible matches, meaning that matching 1 item would be preferred, but if it results in a dead end it tries the next match. I feel like there is a better implementation of this out there, maybe involving sets to find where items overlap and determining the critical path. I just haven't been able to come up with a decent alternative other than this exhaustive search.

------- Update ------

After researching the algorithms suggested in the answers I decided to go with the munkres algorithm. It allows weighting of items in the vertex.

It accepts a matrix of items, where the rows represent 1 item, the columns another, and where they intersect is the cost when those items are paired. The common example uses people and jobs as the items. This algorithm will find the pair of items with the least cost. To prevent an item from being paired, set the cost in the matrix to float('inf') eg:

         Janitor     Teacher     Doctor
Bob       9           5          1
Dick      1           4          6 
Sally     5           3          7

would be represented by:

[
[9,5,1],
[1,4,6],
[5,3,7]
]

and would return [0,1,2], [2,0,1] where the first list represents the row indices and the second list represents the index of columns that would be matched with the rows I ended up converting the two lists into a dictionary of people to their corresponding job via

>>> def match():
    from munkres import Munkres
    people = ["bob", "dick", "sally"]
    jobs = ["janitor", "teacher", "doctor"]
    matrix = [
               [9,5,1],
               [1,4,6],
               [5,3,7]
              ]

    m = Munkres()
    indexes = m.compute(matrix)

    matches = {}
    for p, j in indexes:
        person = people[p]
        job = jobs[j]
        matches[person] = job
    return matches

>>> match()
{'bob': 'doctor', 'dick': 'janitor', 'sally': 'teacher'}

matches will be a dictionary of people to their matched job

Answer 1

1. The Hopcroft–Karp algorithm

The problem you're trying to solve here is to find a maximum matching in an unweighted bipartite graph. This can be solved in \$O(\sqrt V E)\$ by the Hopcroft–Karp algorithm.

Here's a sketch of how the Hopcroft–Karp algorithm works. Suppose that we have a bipartite unweighted graph, like the one you use as an example in the post:

Because it's bipartite, there are two sets of vertices which we'll call \$U\$ and \$V\$:

The Hopcroft–Karp algorithm works by repeatedly augmenting the matching, increasing the number of edges in the matching by one. Suppose that we have added one edge to the matching so far, between \$y\$ and \$2\$, drawn as a red edge:

The algorithm now searches for an augmenting path. This is a path that starts at an unmatched vertex in \$U\$, crosses to \$V\$ on an unmatched (black) edge, crosses back to \$U\$ on a matched (red) edge, and so on, finally ending in \$V\$. Here's an augmenting path, starting at \$x\$, following an unmatched edge to \$2\$, following a matched edge to \$y\$, and following an unmatched edge to \$3\$:

An augmenting path has an odd number of edges (because it starts in \$U\$ and finishes in \$V\$) and the edges along the path alternate between unmatched and matched. This means that if we swap all the edges along the augmenting path (matched becoming unmatched and vice versa), we get a new matching with one more edge, like this:

Now carrying on with the algorithm, there is another augmenting path, \$z\$–\$2\$–\$x\$–\$1\$:

Swapping the edges along this path, we increase the matching again:

Now there are no more augmenting paths (because there are no unmatched vertices in \$U\$) and we are done.

How do we find the augmenting paths? Well, we use a combination of breadth-first search and depth-first search. At each stage we do a breadth-first search to divide the vertices into layers according to their shortest distance from an unmatched vertex along an augmenting path. Suppose we are at this stage of the algorithm, where \$y\$ has been matched with \$2\$:

Now the breadth-first search divides the vertices into the following layers:

Using this structure, an augmenting path can be found efficiently (linear time) by a depth-first search that only follows edges from lower-numbered layers to higher-numbered layers.

2. Implementation

This is a direct translation of the pseudocode from Wikipedia into Python. To help with book-keeping, this implementation introduces a distinguished node nil, with all vertices being artificially matched with nil to start with. When there are no more augmenting paths ending at nil then we know the matching is maximal.

from collections import deque

def maximum_matching(graph):
    """Find a maximum unweighted matching in a bipartite graph. The input
    must be a dictionary mapping vertices in one partition to sets of
    vertices in the other partition. Return a dictionary mapping
    vertices in one partition to their matched vertex in the other.

    """
    # The two partitions of the graph.
    U = set(graph.keys())
    V = set.union(*graph.values())

    # A distinguished vertex not belonging to the graph.
    nil = object()

    # Current pairing for vertices in each partition.
    pair_u = dict.fromkeys(U, nil)
    pair_v = dict.fromkeys(V, nil)

    # Distance to each vertex along augmenting paths.
    dist = {}
    inf = float('inf')

    def bfs():
        # Breadth-first search of the graph starting with unmatched
        # vertices in U and following "augmenting paths" alternating
        # between edges from U->V not in the matching and edges from
        # V->U in the matching. This partitions the vertexes into
        # layers according to their distance along augmenting paths.
        queue = deque()
        for u in U:
            if pair_u[u] is nil:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = inf
        dist[nil] = inf
        while queue:
            u = queue.pop()
            if dist[u] < dist[nil]:
                # Follow edges from U->V not in the matching.
                for v in graph[u]:
                    # Follow edge from V->U in the matching, if any.
                    uu = pair_v[v]
                    if dist[uu] == inf:
                        dist[uu] = dist[u] + 1
                        queue.append(uu)
        return dist[nil] is not inf

    def dfs(u):
        # Depth-first search along "augmenting paths" starting at
        # u. If we can find such a path that goes all the way from
        # u to nil, then we can swap matched/unmatched edges all
        # along the path, getting one additional matched edge
        # (since the path must have an odd number of edges).
        if u is not nil:
            for v in graph[u]:
                uu = pair_v[v]
                if dist[uu] == dist[u] + 1: # uu in next layer
                    if dfs(uu):
                        # Found augmenting path all the way to nil. In
                        # this path v was matched with uu, so after
                        # swapping v must now be matched with u.
                        pair_v[v] = u
                        pair_u[u] = v
                        return True
            dist[u] = inf
            return False
        return True

    while bfs():
        for u in U:
            if pair_u[u] is nil:
                dfs(u)
    return {u: v for u, v in pair_u.items() if v is not nil}

Answer 2

Right off the bat, this occurs to me:

• Build a frequency map of the possible match values:

  freqs = collections.Counter()
  
  for k,v in possible_matches.items():
      freqs.update(v)
  

• Weight the match keys by the sum of all possible replacements:

  weights = {k: sum(freqs[replacement] for replacement in v) 
                for k,v in possible_matches.items() }
  

• Use the weights to order the possible matches with the lowest weight first. These will be the matches with the fewest possibilities:

  order_to_try = sorted(possible_matches.keys(), key=lambda k: weights[k])
  

• Sort the remaining_items_to_match using the order above. This will tend to assign the hardest-to-fit replacements first, so it should prune early:

  ritm = sorted(remaining_items_to_match, key=lambda k: weights[k])
  

Note that technically, when you "allocate" a match you are changing the dynamics of the weighting. So you could pass a modified replacements table down recursively, so used replacement values were removed from the weight computations:

new_freqs = collections.Counter()
for k,v in possible_matches.items():
    new_freqs.update(v - used_numbers) # Discarding used numbers

And if it matters, you should be intersecting your possible_matches with the set of inputs (remaining_items_to_match) to make sure you're not carrying any extra baggage...