MCBM Python implementation refactored from https://www.geeksforgeeks.org/maximum-bipartite-matching/

mcbm_geek_rename.py

# This is the original algorithm with some renaming for clarity.

# DFS recursive function returns true if a matching for a_index is possible
def mcbm_can_match(graph, a_index, matches, seen):
    # Try every resource one by one
    for r_index in range(len(graph[0])):
        # If resource at r_index can do assignment and assignment is not seen
        if graph[a_index][r_index] and seen[r_index] == False:
            # Mark resource as visited
            seen[r_index] = True

            # If resource at r_index is not matched to an assignment
            # OR the assignment has an alternate match available.
            # As r_index is marked as seen above this call won't match it again.
            if matches[r_index] == -1 or mcbm_can_match(graph, matches[r_index], matches, seen):
                matches[r_index] = a_index
                return True
    return False

# Macimum Cardinality Bipartite [graph] Matches
# Returns maximum number of matches
def mcbm(graph):
    n_resources = len(graph[0])
    n_assignments = len(graph)
    # An array to keep track of the resources matched to assignments
    matches = [-1] * n_resources

    # Count of resources matched to assignments
    cardinality = 0
    for a_index in range(n_assignments):
        # Mark all resources as not seen for next assignment
        seen = [False] * n_resources
        # Find if the assignment at a_index has a matching resource
        if mcbm_can_match(graph, a_index, matches, seen):
            cardinality += 1
    return cardinality


graph = [[0, 1, 1, 0, 0, 0],
         [1, 0, 0, 1, 0, 0],
         [0, 0, 1, 0, 0, 0],
         [0, 0, 1, 1, 0, 0],
         [0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 1]]

graph = [[1, 0, 0],
         [0, 1, 1],
         [1, 1, 0]]


print(mcbm(graph))

mcbm_geek_transpose.py

# Algorithm changed to accept a list of resources and graph of assignments,
# rather than a binary flag "Edmond's Matrix".
# This is format is easier to generate by grouping in a database.

# DFS recursive function returns true if a matching for a_index is possible
def mcbm_can_match(resources, graph, a_index, matches, seen):
    # Try every resource one by one
    for r_index in range(len(resources)):
        # If resource at r_index can do assignment and assignment is not seen
        if (resources[r_index] in graph[a_index]) and seen[r_index] == False:
            # Mark resource as visited
            seen[r_index] = True

            # If resource at r_index is not matched to an assignment
            # OR the assignment has an alternate match available.
            # As r_index is marked as seen above this call won't match it again.
            if matches[r_index] == -1 or mcbm_can_match(assignments, graph, matches[r_index], matches, seen):
                matches[r_index] = a_index
                return True
    return False

# Macimum Cardinality Bipartite [graph] Matches
# Returns maximum number of matches
def mcbm(resources, graph):
    n_resources = len(resources)
    n_assignments = len(graph)
    # An array to keep track of the resources matched to assignments
    matches = [-1] * n_resources

    # Count of resources matched to assignments
    cardinality = 0
    for a_index in range(n_assignments):
        # Mark all resources as not seen for next assignment
        seen = [False] * n_resources
        # Find if the assignment at a_index has a matching resource
        if mcbm_can_match(assignments, graph, a_index, matches, seen):
            cardinality = cardinality + 1

    return cardinality


resources = [1, 2, 3, 4, 5, 6]
graph =[[2, 3],
        [1, 4],
        [3],
        [3, 4],
        [5]]

resources = [11, 22, 33]
graph =[[11],
        [22, 33],
        [11, 22]]


print(mcbm(resources, graph))

mcbm_geek_transpose_value.py

# Algorithm changed to accept a list of resources and graph of assignments,
# (as in prior version) but now doesn't rely on mutation of arrays.
# This makes porting to Postgres possible as PL/pgSQL passes by value (copy).

# DFS recursive function returns true if a matching for a_index is possible
def mcbm_can_match(resources, graph, a_index, matches, seen):
    # Try every resource one by one
    for r_index in range(len(resources)):
        # If resource at r_index can do assignment and assignment is not seen
        if (resources[r_index] in graph[a_index]) and seen[r_index] == False:
            # Mark resource as visited
            seen[r_index] = True

            # If resource at r_index is not matched to an assignment
            # OR the assignment has an alternate match available.
            # As r_index is marked as seen above this call won't match it again.
            if matches[r_index] == -1:
                matches[r_index] = a_index
                return True, matches, seen
            result, matches, seen = mcbm_can_match(resources, graph, matches[r_index], matches[:], seen[:])
            if result:
                matches[r_index] = a_index
                return True, matches, seen
    return False, matches, seen

# Macimum Cardinality Bipartite [graph] Matches
# Returns maximum number of matches
def mcbm(resources, graph):
    n_resources = len(resources)
    n_assignments = len(graph)
    # An array to keep track of the resources matched to assignments
    matches = [-1] * n_resources

    # Count of resources matched to assignments
    cardinality = 0
    for a_index in range(n_assignments):
        # Mark all resources as not seen for next assignment
        seen = [False] * n_resources
        # Find if the assignment at a_index has a matching resource
        result, matches, seen = mcbm_can_match(resources, graph, a_index, matches, seen)
        if result:
            cardinality = cardinality + 1
    return cardinality


resources = [1, 2, 3, 4, 5, 6]
graph =[[2, 3],
        [1, 4],
        [3],
        [3, 4],
        [5]]

resources = [11, 22, 33]
graph =[[11],
        [22, 33],
        [11, 22]]


print(mcbm(resources, graph))