Topological course prerequisites in Python
We want to figure out the sequence we can take university courses in, and some of the courses may have prerequisite courses. In other words, we want a topological sort of the courses.
For this example, we can just ignore any courses that are impossible to take because they depend on non-existent courses, or have a circular dependency.
The input data is like this:
{'C3': {'C2', 'C1'}, 'C2': {'C1'}, 'C1': {}}
And the desired output is like this:
['C1', 'C2', 'C3']
The solution algorithm could work like this:
def prerequisite_courses(course_prs: Dict[str, Set[str]]) -> List[str]:
course_order = []
while course_prs:
to_take = [c for c in course_prs if not course_prs[c]]
if not to_take:
break
while to_take:
taken = to_take.pop()
course_order.append(taken)
for c in course_prs:
if taken in course_prs[c]:
course_prs[c].remove(taken)
if not course_prs[c]:
to_take.append(c)
course_prs = {c: prs for c, prs in course_prs.items() if prs}
return course_order
In a loop, we find courses that we can take because they have no prerequisites.
We then iterate through those independent courses, adding them to the final result ordering.
As we add each one to the result, we also remove it from the prerequisite lists of the remaining courses (on the basis that we’ve already taken it so it’s no longer an outstanding dependency for the other courses).
If we find that another course now has no prerequisites left, we also add that one to the list of courses to take next and keep iterating. We also remove that independent course from the whole set of courses (we have to do this by filtering separately, otherwise Python will complain about altering a dictionary while iterating on it).
That solves the topological course prerequisite course in what I think is $O (n + e)$, as you have to iterate all the nodes and all the “edges”, i.e. dependencies between them.