Notes from CS2040S Week 10 Lecture 2 on DAGs

cs2040s_w10_l2.md

CS2040s Week 10 Lecture 2

Notes from CS2040S Week 10 Lecture 2 on Directed Acyclic Graphs

Directed Acyclic Graphs

• Every edge has a direction between nodes
• No cycles in the graphs

Topological Ordering

• Ordering of nodes that respects the edges
  • Sequential total order of nodes
• Edges only point forward
  • Can't have an edge point from present to past
• Every directed graph does not have a topological order
  • If it contains cycles, it can't be ordered topologically
• Directed graph has a TO only if and only if it's acyclic

Using DFS for TO

• Almost right but not exactly
• Backtracking may not be in the right order
• Preorder DFS
  • Process each node when it is first visited
• We need a Postorder DFS
  • Process each node when last visited
• Time complexity is O(V + E) (same as DFS)
• TOs are not unique (if some nodes have the same priority / dependencies)
  • There can be many valid TOs for the same DAG

DFS(nodes):
	visited = new boolean[nodes.length]
	Arrays.fill(visited, false)
	
	for (v in nodes):
		if (!visited[v]):
			visited[v] = true
			DFS-visit(nodes, visited, v)
			PROCESSNODE(v) // do whatever to the node last

Ensure all nodes have good constraints for good TO

Kahn's Algorithm

Repeat:
	S = all nodes in G that have no incoming edge
	Add nodes in S to the order
	Remove all edges adjacent to nodes in S (edges to all children)
	Remove all nodes in S from the graph

• Time complexity of O(V + E)
• We can assume that there will always be a node without any incoming edges in a DAG
  • If it did, then there'd be cycles – can't use this algorithm

Maintain all nodes in priority queue
Keys are incoming edges
Remove min-degreee node u (usually the one with 0 incoming edges in a DAG)
For each outgoing edge (u, v)
	decrease-key of v by 1

• Time complexity of O(E log V) where E is the total number of edges
  • Maintain queue/stack of nodes with no incoming edges

Shortest Paths in Weighted DAGs

• Relax nodes in Postorder DFS
  • Topologically sort
• Time complexity is O(E) or O(V + E)

Longest path in DAG

• Negate all edges
  • shortest path in negated = longest path in regular
  • doesn't work in cyclic graph since we now have negative weight cycles
• Modify relax function