topological sort

Complete

Summary

Special cases

short trees have the topological orderings for a connected graph
1,5-complete bipartite or 5-star

how may ways to arrange the leaf nodes

an SLL has only one topological order
6-path

Concept

Topological ordering

only applicable to DAG
rearranging the graph such that the edges are only pointing in one direction
topological order is not unique

there is no general formula for the number of topological orderings

Postorder DFS

modified DFS with postorder append to an array
reverse the array once all have been visited

java

List<Integer> order;

void dfs_post(int u) {
	visited.set(u, true);
			
	for (int v : al.get(u))
		if (!visited.get(v)) // provided that the graph is a DAG, this is not needed
			dfs_post(v);
			
	order.add(u); // postorder
}

void dfs_sort() {
	for (int i = 0; i < visited.length(); i++)
		if (!visited.get(i))
			dfs_post(i);
			
	Collections.reverse(order);
}

works only if the graph is already verified to be a DAG

6 vertex DAG: dfs_sort()

Kahn’s algorithm

compute in-degrees of all vertices
modified BFS such that only verticies with no incoming edges(in-degree = 0) are enqueued
the vertex is also “deleted” after being dequeued

if there is a cycle -> one of the iterations will reach a case where there are no nodes with in-degree = 0, quiet failure

java

int[] indegree = new int[V];
List<Integer> order = new ArrayList<>();

void kahn() {
	// calculate in-degrees
	for (int u = 0; u < V; u++) 
		for (int v : AL.get(u)) 
			indegree[v]++; // increment for every incoming edge
	
	Queue<Integer> q = new LinkedList<>(); // can be stack O(1) or priority queue O(log n) also, order is not important
	
	// enqueue all verticies with in-degree = 0
	for (int u = 0; u < V; u++) 
		if (indegree[u] == 0) // invariant condition, only indegree = 0 in the queue
			q.offer(u);
		
	while (!q.isEmpty()) {
		int u = q.poll();
		order.add(u);
	
		for (int v : AL.get(u)) {
			indegree[v]--; // "delete" the edge
			if (indegree[v] == 0) // maintain the invariant
				q.offer(v);
		}
	}
}

6 vertex DAG: kahn()

curr | queue
_    | [ 3, 5 ]
3    | [ 5, 4 ]      // delete 3 frees 4
5    | [ 4, 0 ]      // delete 5 frees 0
4    | [ 0, 2 ]
0    | [ 2, 1 ]
2    | [ 1 ]
1    | [ ]

Kahn’s algorithm is easier to modify, ie. applying additional constrains on vertices with in-degree = 0

Valid topological orderings

naive solution

recursive traversal with elements from Kahn’s algorithm
if there are multiple nodes with in-degree = 0, each represent a possible ordering
reset visited state postorder, allowing recursion to revisit that vertex through another path

java

int[] indegree = new int[V];
List<List<Integer>> orders = new ArrayList<>();

void topoRecur(List<Integer> order) {
	boolean end = true;
	
	for (int u = 0; u < V; u++) 
		if (!visited.get(u) && indegree[u] == 0) { // at most V times
			visited.set(u, true);
			end = false; // means that there are other verticies left to visit
			List<Integer> curr = new ArrayList<>(order);
			curr.add(u); // add this to current ordering
			
			// "remove" current vertex
			for (int v : al.get(u)) // O(k) < O(V)
				indegree[v]--;
			
			// proceed with recursion
			topoRecur(curr); // V - 1
			
			// "add" the vertex back
			visited.set(u, false);
			for (int v : al.get(u)) 
				indegree[v]++;
		}
	
	if (end) // cycle or no more verticies, assuming DAG we extract a valid order
		orders.add(order);
}

void topoAll() {
	for (int u = 0; u < V; u++) 
		for (int v : al.get(v)) 
			indegree[v]++; // increment for every incoming edge
			
	topoRecur(new ArrayList<>());
}

Application

Kattis: Build Dependencies

dependency tree

java

static HashMap<String, List<String>> al;
static HashMap<String, Boolean> visited;
static List<String> order;

static void dfs_post(String u) {
	visited.put(u, true);

	for (String v : al.getOrDefault(u, new ArrayList<>())) // might not be in the al if it has no dependents
		if (!visited.get(v))
			dfs_post(v);

	order.add(u); // postorder
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	PrintWriter pw = new PrintWriter(System.out);

	int n = Integer.parseInt(br.readLine());

	al = new HashMap<>();
	visited = new HashMap<>();
	order = new ArrayList<>();

	StringTokenizer st;
	while (n-- > 0) {
		st = new StringTokenizer(br.readLine());
		String curr = st.nextToken();
		curr = curr.substring(0, curr.length() - 1);

		// al.put(curr, new ArrayList<>()); // we don't need to include files with no dependencies
		visited.put(curr, false);

		while (st.hasMoreTokens()) {
			String dep = st.nextToken();
			List<String> ns = al.getOrDefault(dep, new ArrayList<>());
			ns.add(curr);
			al.put(dep, ns);
		}
	}

	// input is non-cyclic so we can use postorder dfs
	dfs_post(br.readLine()); // nodes downstream need to be recompiled

	Collections.reverse(order);
	
	for (String s : order)
		pw.println(s);
	
	pw.close();
}

Leetcode: Minimum Number of Vertices to Reach All Nodes

find in-degrees

java

List<List<Integer>> AL = new ArrayList<>();
for (int i = 0; i < n; i++)
	AL.add(new ArrayList<>());

for (List<Integer> e : edges) 
	AL.get(e.get(0)).add(e.get(1));

// find nodes with in-degree = 0
int[] indegree = new int[n];

for (int u = 0; u < n; u++)
	for (int v : AL.get(u))
		indegree[v]++;

List<Integer> out = new ArrayList<>();

for (int u = 0; u < n; u++)
	if (indegree[u] == 0)
		out.add(u);

return out;

without AL construction, in-degree directly from EL

java

int[] indegree = new int[n];

for (List<Integer> e : edges) 
	indegree[e.get(1)]++;

List<Integer> out = new ArrayList<>();

for (int u = 0; u < n; u++)
	if (indegree[u] == 0)
		out.add(u);

return out;