Skip to content

Instantly share code, notes, and snippets.

@ziruihao
Last active August 15, 2021 16:34
Show Gist options
  • Save ziruihao/070e53c7886a010844bb35be909d4f21 to your computer and use it in GitHub Desktop.
Save ziruihao/070e53c7886a010844bb35be909d4f21 to your computer and use it in GitHub Desktop.
Solving course requirement matching via the Edmonds-Karp max flow algorithm.
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()
@ziruihao
Copy link
Author

ziruihao commented Aug 15, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment