1 Directed Graphs 12/7/2017 7:15 AM Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Directed Graphs BOS ORD JFK SFO DFW LAX MIA Directed Graphs

2 Digraphs A digraph is a graph whose edges are all directedShort for “directed graph” Applications one-way streets flights task scheduling A C E B D Directed Graphs

3 Digraph Properties A graph G=(V,E) such thatB D Digraph Properties A graph G=(V,E) such that Each edge goes in one direction: Edge (a,b) goes from a to b, but not b to a If G is simple, m < n(n - 1) If we keep in-edges and out-edges in separate adjacency lists we can perform listing of incoming edges and outgoing edges in time proportional to their size Directed Graphs

4 Digraph Application Scheduling: edge (a,b) means task a must be completed before b can be started cs21 cs22 cs46 cs51 cs53 cs52 cs161 cs131 cs141 cs121 cs171 The good life cs151 Directed Graphs

5 Directed DFS We can specialize the traversal algorithms (DFS and BFS) to digraphs by traversing edges only along their direction In the directed DFS algorithm, we have four types of edges discovery edges back edges (ancestors) forward edges (descendants) cross edges (neither) A directed DFS starting at a vertex s determines the vertices reachable from s E D C B A Directed Graphs

6 Reachability DFS tree rooted at v: vertices reachable from v via directed paths E D E D C A C F E D A B C F A B Directed Graphs

7 Strong Connectivity Each vertex can reach all other vertices a g c d eb e f g Directed Graphs

8 Weak Connectivity Replace all the directed edges with undirected edgesThe resulting undirected graph is connected Directed Graphs

9 Strongly Connected ComponentsMaximal subgraphs such that each vertex can reach all other vertices in the subgraph Can also be done in O(n+m) time using DFS, but is more complicated (alg. not discussed here). a d c b e f g { a , c , g } { f , d , e , b } Directed Graphs

10 Repeated queries of reachabilityE.g. Many people ask if one can fly from Melbourne to Hawaii Instead of using the original graph G Create a new graph G* that stores reachability information Ask G* Directed Graphs

11 Transitive Closure D E Given a digraph G, the transitive closure of G is the digraph G* such that G* has the same vertices as G if G has a directed path from u to v (u  v), G* has a directed edge from u to v The transitive closure provides reachability information about a digraph B G C A D E B C A G* Directed Graphs

12 Computing the Transitive ClosureIf there's a way to get from A to B and from B to C, then there's a way to get from A to C. We can perform DFS starting at each vertex O(n(n+m)) Alternatively ... Use the Floyd-Warshall Algorithm Directed Graphs

13 Floyd-Warshall Transitive ClosureIdea #1: Number the vertices 1, 2, …, n. Idea #2: Consider paths that use only vertices numbered 1, 2, …, k, as intermediate vertices: Uses only vertices numbered 1,…,k (add this edge if it’s not already in) i j Uses only vertices numbered 1,…,k-1 Uses only vertices numbered 1,…,k-1 k Directed Graphs

14 Floyd-Warshall’s AlgorithmNumber vertices v1 , …, vn Compute digraphs G0, …, Gn G0=G Gk has directed edge (vi, vj) if G has a directed path from vi to vj with intermediate vertices in {v1 , …, vk} We have that Gn = G* In phase k, digraph Gk is computed from Gk - 1 Running time: O(n3), assuming areAdjacent is O(1) (e.g., adjacency matrix) Algorithm FloydWarshall(G) Input digraph G Output transitive closure G* of G i  1 for all v  G.vertices() denote v as vi i  i + 1 G0  G for k  1 to n do // intermediate Gk  Gk - 1 for i  1 to n (i  k) do // source for j  1 to n (j  i, k) do //destination if Gk - 1.areAdjacent(vi, vk)  Gk - 1.areAdjacent(vk, vj) if Gk.areAdjacent(vi, vj) Gk.insertDirectedEdge(vi, vj , k) return Gn Directed Graphs

15 Floyd-Warshall ExampleBOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

16 Floyd-Warshall, Iteration 1BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

17 Floyd-Warshall, Iteration 2BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

18 Floyd-Warshall, Iteration 3BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

19 Floyd-Warshall, Iteration 4BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

20 Floyd-Warshall, Iteration 5BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

21 Floyd-Warshall, Iteration 6BOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

22 Floyd-Warshall, ConclusionBOS v ORD 4 JFK v 2 v 6 SFO DFW LAX v 3 v 1 MIA v 5 Directed Graphs

23 Use DFS from each of the n verticesTransitive Closure Use DFS from each of the n vertices Floyd-Warshall Time complexity O(n(n+m)) O(n3) m <= n2 Faster if the graph is sparse (not many edges) Directed Graphs

24 DAGs and Topological Orderingdirected acyclic graph (DAG) digraph that has no directed cycles A topological ordering of a digraph is a numbering v1 , …, vn of the vertices such that for every edge (vi , vj), we have i < j Example: in a task scheduling digraph, a topological ordering a task sequence that satisfies the precedence constraints Theorem A digraph admits a topological ordering if and only if it is a DAG D E B C A DAG G v4 v5 D E v2 B v3 C v1 Topological ordering of G A Directed Graphs

25 Topological Sorting Number vertices, so that (u,v) in E implies u < v 1 A typical student day wake up Output: a sequence of events that doesn’t violate the order of a pair of events 2 3 eat study computer sci. 4 5 nap more c.s. 7 play 8 write c.s. program 6 9 work out bake cookies 10 sleep 11 dream about graphs Directed Graphs

26 Algorithm for Topological SortingAlgorithm TopologicalSort(G) H  G // Temporary copy of G i  1 while H is not empty do Let v be a vertex with no incoming edges Label v to be i i  i + 1 Remove v from H Directed Graphs

27 Example Directed Graphs

28 Example (cont.) Directed Graphs

29 Example (cont.) Directed Graphs

30 Time Complexity ? n vertices m edges Directed Graphs

31 Time Complexity O(n + m) n vertices m edges Directed Graphs