Decoding Topological Sort in Python + Golang Side by Side

LeetCode question #207 Course Schedule enters the chat

👋 Welcome

A warm welcome to the 6 new subscribers joining us this week.

Let me know what you think of this post in a comment, if it’s no trouble. If you prefer Twitter, drop me a DM.

Now, let’s get started with this issue.

---

Codecast is a reader supported publication, so if you’re reading this and want to read more software development articles on a weekly basis, subscribe (for FREE) as if you don’t, this post will also get lost in the sea of posts out there and you’ll never find it again 👇

---

Decoding Topological Sort in Python + Golang Side by Side

The lure of LeetCode algorithmic questions has never (even subconsciously) eluded me, so here I am, with a fun comparative commentary between what it’s like to solve a semi-popular Topological sorting question in both Python and Go with exactly the same approach.

Let’s get going!

Problem statement

The problem #207 Course Schedule is about the following:

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Setup data structures

So we have a graph data structure to construct that will keep track of all vertices along with the vertices that need to come before them.

This can be done as follows in Python and Go:

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    
    def insert_edge(self, from_node, to_node):
        self.graph[from_node].append(to_node)

and:

type Graph struct {
	Vertices int
	Edge     map[int][]int
}

func (graph Graph) createGraph(numCourses int, prerequisites [][]int) Graph {
	graph.Vertices = numCourses
	graph.Edge = make(map[int][]int)
	for _, prereq := range prerequisites {
		graph.Edge[prereq[1]] = append(graph.Edge[prereq[1]], prereq[0])
	}
	fmt.Println(graph.Vertices)
	return graph
}

The class in Python can be built as a struct type in Go and the vertices can be assigned as well as the edges can be created in a similar dict / map fashion with every vertex containing as reference a list of vertices that need to come before them.

Great, let’s move to the fun part.

Write the core algorithm

Following steps are needed to get to saying whether our list of lists (i.e. the course schedule provided) is valid or not:

1. Calculate in-degrees of each vertex in a new list or slice (list / slice is possible because vertices (courses) and indices are both integers. Otherwise, can also use a dict / map.

2. Make a queue of each vertex with in-degree of 0. This is the starting point which will allow us to start building the topology order.

3. Init a new visited int variable as 0.

4. While queue is not empty, go over every node's neighbour list, decrease in-degree of every neighbour by 1 and when it becomes zero, append it to the queue. And keep incrementing visited variable on each pop from the queue.

5. At last, return true if visited == num meaning we visited/are able to study every course or else false.

Here it is in action in Python:

def if_all_courses_complete(self):
        in_degree = [0] * self.V
        for node in self.graph:
            for prereq in self.graph[node]:
                in_degree[prereq] += 1
        
        queue = deque()
        for i, degree in enumerate(in_degree):
            if degree == 0 :
                queue.append(i)
        
        count_vis = 0
        
        while queue:
            node = queue.popleft()
            count_vis += 1
            
            for prereq in self.graph[node]:
                in_degree[prereq] -= 1
                if in_degree[prereq] == 0:
                    queue.append(prereq)
        
        if count_vis == self.V:
            return True
        else:
            return False


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if numCourses == 1:
            return True
        if prerequisites == []:
            return True
        
        graph = Graph(numCourses)
        
        for pre in prerequisites:
            graph.insert_edge(pre[1], pre[0])
        
        return graph.if_all_courses_complete()

and Go:

func (graph Graph) ifAllCoursesComplete() bool {
	inDegree := make([]int, graph.Vertices)
	for _, node := range graph.Edge {
		for _, prereq := range node {
			inDegree[prereq] += 1
		}
	}
	queue := make([]int, 0)
	for index, degree := range inDegree {
		if degree == 0 {
			queue = append(queue, index)
		}
	}
	countVis := 0

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		countVis += 1

		for _, prereq := range graph.Edge[node] {
			inDegree[prereq] -= 1
			if inDegree[prereq] == 0 {
				queue = append(queue, prereq)
			}
		}
	}
	fmt.Println(graph.Vertices, countVis)
	if countVis == graph.Vertices {
		return true
	} else {
		return false
	}
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	if numCourses == 1 {
		return true
	}
	if len(prerequisites) == 0 {
		return true
	}
	var graph Graph
	graph = graph.createGraph(numCourses, prerequisites)
	for _, i := range graph.Edge {
		fmt.Println(i)
	}
	return graph.ifAllCoursesComplete()
}

Perfect!

One great thing to note here is that we don’t need a special data structure like deque in Go because the regular slice already provides an easy way to handle queue-like FIFO behaviour.

---

Thank you for reading! Full code is also available as usual in my Go repository.

If you liked this article, feel free to share it with your friends! :)

See you in the next one. Keep in touch with me on Twitter.