graph/kahn.go

// Kahn's algorithm computes a topological ordering of a directed acyclic graph (DAG).
// Time Complexity: O(V + E)
// Space Complexity: O(V + E)
// Reference: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
// see graph.go, topological.go, kahn_test.go

package graph

// Kahn's algorithm computes a topological ordering of a directed acyclic graph (DAG).
// `n` is the number of vertices,
// `dependencies` is a list of directed edges, where each pair [a, b] represents
// a directed edge from a to b (i.e. b depends on a).
// Vertices are assumed to be labelled 0, 1, ..., n-1.
// If the graph is not a DAG, the function returns nil.
func Kahn(n int, dependencies [][]int) []int {
	g := Graph{vertices: n, Directed: true}
	// track the in-degree (number of incoming edges) of each vertex
	inDegree := make([]int, n)

	// populate g with edges, increase the in-degree counts accordingly
	for _, d := range dependencies {
		// make sure we don't add the same edge twice
		if _, ok := g.edges[d[0]][d[1]]; !ok {
			g.AddEdge(d[0], d[1])
			inDegree[d[1]]++
		}
	}

	// queue holds all vertices with in-degree 0
	// these vertices have no dependency and thus can be ordered first
	queue := make([]int, 0, n)

	for i := 0; i < n; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	// order holds a valid topological order
	order := make([]int, 0, n)

	// process the dependency-free vertices
	// every time we process a vertex, we "remove" it from the graph
	for len(queue) > 0 {
		// pop the first vertex from the queue
		vtx := queue[0]
		queue = queue[1:]
		// add the vertex to the topological order
		order = append(order, vtx)
		// "remove" all the edges coming out of this vertex
		// every time we remove an edge, the corresponding in-degree reduces by 1
		// if all dependencies on a vertex is removed, enqueue the vertex
		for neighbour := range g.edges[vtx] {
			inDegree[neighbour]--
			if inDegree[neighbour] == 0 {
				queue = append(queue, neighbour)
			}
		}
	}

	// if the graph is a DAG, order should contain all the certices
	if len(order) != n {
		return nil
	}
	return order
}