Directed Graph

DirectedGraph

1. DiGraph:
	1. Set of vertices connected pairwise by directed edges
		1. Problems
			1. Shortest Path
			2. Topological sort (all edges point upwards)
			3. Strong connectivities
			4. Transitive closure
			5. PageRank
		2. adjacency-list representation
2. Digraph search
	1. undirected graph is digraph in both directions
	2. DFS can be used directly
		1. Recheability
			1. examine program flow
			2. garbage collection
		2. Basis for difficult digraph problems in linear time
			1. 2-satisfiability
			2. Directed Euler Path
			3. Strongly-connected components
	3. BFS
		1. directly used
		2. find shortest path
		3. Multiple-source shortest path (find shortest path from any vertex in the set to each other vertex
			1. BFS with all sources
		4. Web-crawler
3. Topological Sort
	1. Precedence scheduling, find feasible schedule respect the sequence
	2. DAG: directed acyclic graph (no cycle)
	3. Redraw DAG so all edges point upwards
	4. DFS, return vertices in reverse postorder (once done on a node (no further path), return and put that node in a stack)
		1. the last one is bottom (starting) node and top one is leaf node (end node, up node)
	5. Reverse DFS Postorder of a DAG is a topological order
	6. Find cycle by using topological order
		1. find cyclic reference
4. Strong components
	1. Two DFS Kosaraju-Sharir algorithm
	2. v to w and w to v
	3. V strongly connected component in a DAG(V, E)
	4. linear-time DFS 
	5. Reverse graph: strong components in G are same as in G(reversed)
	6. Kernel DAG: contract each strong componennt into a single vertex (a sink link)
	7. Idea
		1. Computer topological order (reverse postorder) in kernel DAG
		2. run DFS, considering vertices in reverse topological order
		3. Phase 1: computer reverse postorder in G(R)
		4. phase 2: run DFS in G, visiting unmarked vertices in reverse postorder of G(R)
		5. time:proportional to E+V
		6. First top-down DFS second bottom-up DFS