Solving course requirement matching via the Edmonds-Karp max flow algorithm.

course_requirement_matcher.py

from typing import Deque

# standard degree requirements
DEGREE_REQS = set(['LIT', 'ART', 'SCI', 'TMV', 'TAS', 'INT'])

# course name followed by requirements that it satisfies
courses = {
  'COSC_1': set(['TAS', 'SCI']),
  'GOVT_30': set(['INT', 'TMV']),
  'ENGL_16': set(['LIT', 'INT']),
  'MUSI_80': set(['ART']),
  'PHIL_4': set(['TMV']),
  'BIOL_2': set(['SCI']),
  'ENGS_15': set(['TAS'])
}

def generate_graph(courses: dict[str, set[str]]) -> dict[str, set[str]]:
  '''
  Constructs a map of set graph for given courses.
  Creates associated flow, capacity, and residual graphs.
  '''
  graph = dict()
  # add courses to graph
  for course in courses:
    graph[course] = courses[course]
  # add source
  graph['SOURCE'] = set([course for course in courses])
  # add sink
  graph['SINK'] = set([])
  # add reqs to graph
  for req in DEGREE_REQS:
    graph[req] = set(['SINK'])

  # set up flow, capacities, and residual capacities
  flow = {}
  cap = {}
  res_cap = {}
  for u in graph:
    flow[u] = dict()
    cap[u] = dict()
    res_cap[u] = dict()
    for v in graph:
      cap[u][v] = 1 if v in graph[u] else 0
      flow[u][v] = 0
      res_cap[u][v] = cap[u][v] - flow[u][v]
  
  return graph, flow, cap, res_cap

def find_augmenting_path(res_cap: dict[str, dict[str, int]]) -> list[str]:
  '''
  Scopes out the next augmenting path with a breadth search approach.
  '''
  to_visit = Deque([('SOURCE', [])])
  while len(to_visit):
    (curr, path) = to_visit.popleft()
    path.append(curr)
    if curr == 'SINK':
      return path
    # find next nodes with positive residual capacity
    nexts = [(next, path.copy()) for next in res_cap[curr] if (res_cap[curr][next] > 0 and next not in path)]
    to_visit.extend(nexts)
  return None

def fill_requirements(courses: dict[str, set[str]]):
  '''
  Given a set of courses and degree requirements, returns an optimal allocation.
  '''
  matching = { req: None for req in DEGREE_REQS }
  graph, flow, cap, res_cap = generate_graph(courses)
  
  while True:
    # get next path
    next_path = find_augmenting_path(res_cap)
    if next_path is None:
      break
    # compute lowest flow allowed on path
    min_flow_on_path = min([res_cap[next_path[i]][next_path[i + 1]] for i in range(len(next_path) - 1)])
    # augment flow for each edge on path
    for i in range(len(next_path) - 1):
      u = next_path[i]
      v = next_path[i + 1]
      flow[u][v] += min_flow_on_path
      flow[v][u] = -flow[u][v]
      res_cap[u][v] = cap[u][v] - flow[u][v]
      res_cap[v][u] = cap[v][u] - flow[v][u]
      # save a course-requirement allocation
      if u in courses and v in DEGREE_REQS:
        matching[v] = u
  return matching

def run():
  for course in courses:
    print(course + ' gives ' + ', '.join(courses[course]))

  print('\ncomputing...\n')

  matching = (fill_requirements(courses))

  for req in matching:
    print(req + ' fulfilled by ' + str(matching[req]))

run()

Log:

COSC_1 gives TAS, SCI
GOVT_30 gives INT, TMV
ENGL_16 gives LIT, INT
MUSI_80 gives ART
PHIL_4 gives TMV
BIOL_2 gives SCI
ENGS_15 gives TAS

computing...

LIT fulfilled by ENGL_16
ART fulfilled by MUSI_80
TMV fulfilled by PHIL_4
INT fulfilled by GOVT_30
SCI fulfilled by COSC_1
TAS fulfilled by ENGS_15