Classes are back, at least in Brazil. And in this period of the year, the students are usually trying to figure out which courses they are going to take this semester. What a nice opportunity to learn about topological sort, isn’t it?

Course Scheduling

Let’s try to illustrate our learning with the Leetcode problem Course Scheduling (I or II, they are fairly similar).

In this problem, we are passed the number of courses n that we have to take to graduate, for example, and courses labelled as numbers in the interval [0, n - 1] and need to return a correct order in which to take the courses. For example, suppose we have this hypothetical list of courses and prerequisites (here conveniently represented as a graph).

Courses as graph

So there are different valid orders in which we could take the courses, for example:

  •  ["Calculus 1", "Calculus 2", "Physics 1", "Physics 2", 
     "Intro to Programming", "Algorithms", "Numerical Methods"]
    
  •  ["Intro to Programming", "Calculus 1", "Physics 1", 
     "Calculus 2", "Algorithms", "Physics 2", "Numerical Methods"]
    

And the list goes on and on. But how can we develop an algorithm that will always deliver a correct order for any valid given list of courses? Enter topological sort.

Topological Sort

According to Wikipedia topological sort of a directed graph is

a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

That is, "Calculus 1" should always come before "Calculus 2" and "Physics 1". "Algorithms" should aways come before "Numerical Methods" and after "Intro to Programming". So it is basically any valid order to take the courses. But graphs can be represented in a bunch of different ways, right? Here, we are going to fiddle with two of them: edge lists and adjacency lists.

Graph Representations

Edge Lists

The first one we are going to take a look is the edge list. An edge will be represented by the list of vertices that are endpoints to the said edge. In our example it would be:

[
    ["Calculus 2", "Calculus 1"],
    ["Physics 1", "Calculus 1"],
    ["Physics 2", "Physics 1"],
    ["Physics 2", "Calculus 2"],]
    ["Algorithms", "Intro to Programming"],
    ["Numerical Methods", "Algorithms"],
    ["Numerical Methods", "Calculus 2"]
]

And that’s how we are receiving the list of courses and prerequisites in the Leetcode problem, but that is not the best representation to solve the problem, an adjacency list would make our life easier.

Adjacency Lists

An adjacency list map the vertex (a course) to a list of vertices that are adjacent to it (their postconditions). So in our example, this would be our adjacency list representation.

Courses as adjacency list

In other words, we are mapping the ith course with the courses it is prerequisite to.

Solution

Firstly, let’s define how our adjacency list and edge list structures will be represented. We will use a dictionary that maps a number into a set, for the adjacency list and a matrix for the edge list, in which each row represents the tuple of vertices.

AdjacencyList = Dict[int, Set]
EdgeList = List[List[int]]

Then, we will create a method that receives the edge list and transforms it into an adjacency list. We will also extract another useful information: the number of prerequisites each course has (or the number of edges incoming into a vertex, in degrees).

def buildAdjacencyList(
  self, numCourses: int, prerequisites: EdgeList
) -> Tuple[AdjacencyList, Dict[int, int]]:
  adjacency: AdjacencyList = {}
  indegrees: Dict[int, int] = {i: 0 for i in range(numCourses)}

  for course, prerequisite in prerequisites:
    adjacency.setdefault(prerequisite, set()).add(course)
    indegrees[course] = indegrees.get(course, 0) + 1

  return adjacency, indegrees

Now we have our adjacency list and the number of prerequisites for each course. We then know that we can take any course from which we have 0 prerequisites. So we can start taking either "Calculus 1" or "Intro to Programming". Let’s insert all courses that have exaclty 0 prerequisites in a stack, and start to traverse the graph. In each iteration we pop a course from the stack (as if we are taking the course) and iterate in all the courses that had this one as a prerequisite, decreasing by one the number of prerequisites they need. If we have taken all prerequisites for a course we just add it to the stack.

def findOrder(self, numCourses: int, prerequisites: EdgeList) -> List[int]:
  coursesAfter, numOfPrerequisites = self.buildAdjacencyList(
    numCourses, prerequisites
  )

  stack = [i for i in range(numCourses) if numOfPrerequisites[i] == 0]
  result = []

  while stack:
    curr = stack.pop()
    result.append(curr)

    for course in coursesAfter.get(curr, []):
      numOfPrerequisites[course] -= 1
      if numOfPrerequisites[course] == 0:
        stack.append(course)

  if len(result) == numCourses:
    return result
  return []

There is a catch here. Notice we are only returning the result if the length of it is equal to numCourses. That’s because we could receive a cyclic graph as an input, in that case, it would be impossible to graduate and we should return an empty list. Imagine for example that "Calculus 1" has "Numerical Methods" as its prerequisite.

Cyclic courses

We would never be able to take "Calculus 1" and therefore graduate!

That’s it, hope you liked this solution! The complete code can be found here.