1 Directed Graphs Directed Graphs Shortest Path 12/7/2017 7:10 AM BOSORD JFK SFO DFW LAX MIA Directed Graphs

2 Outline and Reading (§6.4)Reachability (§6.4.1) Directed DFS Strong connectivity Transitive closure (§6.4.2) The Floyd-Warshall Algorithm Directed Acyclic Graphs (DAG’s) (§6.4.4) Topological Sorting Directed Graphs

3 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

4 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 in-edges and out-edges in time proportional to their size. Directed Graphs

5 Digraph Application Scheduling: edge (a,b) means task a must be completed before b can be started ics21 ics22 ics23 ics51 ics53 ics52 ics161 ics131 ics141 ics121 ics171 The good life ics151 Directed Graphs

6 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 forward edges cross edges A directed DFS starting at a vertex s determines the vertices reachable from s E D C B A Directed Graphs

7 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

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

9 Strong Connectivity AlgorithmPick a vertex v in G. Perform a DFS from v in G. If there’s a w not visited, print “no”. Let G’ be G with edges reversed. Perform a DFS from v in G’. Else, print “yes”. Running time: O(n+m). a G: g c d e b f a G’: g c d e b f Directed Graphs

10 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 (similar to biconnectivity). a d c b e f g { a , c , g } { f , d , e , b } 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 dynamic programming: 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 AlgorithmFloyd-Warshall’s algorithm numbers the vertices of G as v1 , …, vn and computes a series of digraphs G0, …, Gn G0=G Gk has a directed edge (vi, vj) if G has a directed path from vi to vj with intermediate vertices in the set {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 Gk  Gk - 1 for i  1 to n (i  k) do for j  1 to n (j  i, k) do 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 DAGs and Topological OrderingA directed acyclic graph (DAG) is a 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 B C A DAG G v4 v5 D E v2 B v3 C v1 Topological ordering of G A Directed Graphs

24 Topological Sorting Number vertices, so that (u,v) in E implies u < v 1 A typical student day wake up 2 3 eat study computer sci. 4 5 nap more c.s. 7 play 8 write c.s. program 6 9 work out make cookies for professors 10 sleep 11 dream about graphs Directed Graphs

25 Algorithm for Topological SortingNote: This algorithm is different than the one in Goodrich-Tamassia Running time: O(n + m). How…? Method TopologicalSort1(G) H  G // Temporary copy of G n  G.numVertices() while H is not empty do Let v be a vertex with no outgoing edges Label v  n n  n - 1 Remove v from H Directed Graphs

26 Topological Sorting Algorithm using DFSSimulate the algorithm by using depth-first search O(n+m) time. Algorithm topologicalDFS(G, v) Input graph G and a start vertex v of G Output labeling of the vertices of G in the connected component of v setLabel(v, VISITED) for all e  G.incidentEdges(v) if getLabel(e) = UNEXPLORED w  opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) topologicalDFS(G, w) else {e is a forward or cross edge} Label v with topological number n n  n - 1 Algorithm topologicalDFS(G) Input dag G Output topological ordering of G n  G.numVertices() for all u  G.vertices() setLabel(u, UNEXPLORED) for all e  G.edges() setLabel(e, UNEXPLORED) for all v  G.vertices() if getLabel(v) = UNEXPLORED topologicalDFS(G, v) Directed Graphs

27 Topological Sorting ExampleDirected Graphs

28 Topological Sorting Example9 Directed Graphs

29 Topological Sorting Example8 9 Directed Graphs

30 Topological Sorting Example7 8 9 Directed Graphs

31 Topological Sorting Example6 7 8 9 Directed Graphs

32 Topological Sorting Example6 5 7 8 9 Directed Graphs

33 Topological Sorting Example4 6 5 7 8 9 Directed Graphs

34 Topological Sorting Example3 4 6 5 7 8 9 Directed Graphs

35 Topological Sorting Example2 3 4 6 5 7 8 9 Directed Graphs

36 Topological Sorting Example2 1 3 4 6 5 7 8 9 Directed Graphs

37 Algorithm for Topological SortingAnother algorithm, based on “BFS” labeling Running time: O(n + m). Method TopologicalSort2(G) H  G // Temporary copy of G i  0 while H is not empty do { Let v be a vertex with no incoming edges Label v  i i  i+1 Remove v from H } Directed Graphs

38 Topological Sorting ExampleDirected Graphs

39 Topological Sorting ExampleDirected Graphs

40 Topological Sorting Example1 Directed Graphs

41 Topological Sorting Example1 Directed Graphs

42 Topological Sorting Example1 2 Directed Graphs

43 Topological Sorting Example1 2 3 Directed Graphs

44 Topological Sorting Example1 2 3 4 Directed Graphs

45 Topological Sorting Example1 2 3 4 5 Directed Graphs

46 Topological Sorting Example1 2 3 4 5 6 Directed Graphs

47 Topological Sorting Example1 2 3 4 5 6 7 Directed Graphs

48 Topological Sorting Example1 2 3 4 5 6 7 8 Directed Graphs

49 Topological Sorting Example1 2 3 4 5 6 7 8 9 Directed Graphs