1 Chapter 13 Graph AlgorithmsORD DFW SFO LAX 802 1743 1843 1233 337 Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++, Goodrich, Tamassia and Mount (Wiley 2004) and slides from Nancy M. Amato 1 1

2 Directed Graphs Shortest Path 12/7/2017 7:14 AM BOS ORD JFK SFO DFWMIA ORD LAX DFW SFO

3 Digraphs E A digraph is a graph whose edges are all directed DB D A digraph is a graph whose edges are all directed Short for “directed graph” Applications one-way streets flights task scheduling

4 Digraph Properties E D A graph 𝐺=(𝑉,𝐸) such that CB D A graph 𝐺=(𝑉,𝐸) such that Each edge goes in one direction: Edge (𝑎,𝑏) goes from 𝑎 to 𝑏, but not 𝑏 to 𝑎 If 𝐺 is simple, 𝑚 < 𝑛(𝑛−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

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

6 Directed DFS A C E B D 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 𝑠 determines the vertices reachable from 𝑠

7 Reachability DFS tree rooted at 𝑣: vertices reachable from 𝑣 via directed paths A C E D A C E B D F A C E B D F

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

9 Strong Connectivity AlgorithmPick a vertex 𝑣 in 𝐺 Perform a DFS from 𝑣 in 𝐺 If there’s a 𝑤 not visited, print “no” Let 𝐺’ be 𝐺 with edges reversed Perform a DFS from 𝑣 in 𝐺’ Else, print “yes” Running time: 𝑂(𝑛+𝑚) c d e b f a G’: g c d e b f

10 Strongly Connected ComponentsMaximal subgraphs such that each vertex can reach all other vertices in the subgraph Can also be done in 𝑂(𝑛+𝑚) time using DFS, but is more complicated (similar to biconnectivity). a d c b e f g { a , c , g } { f , d , e , b }

11 Transitive Closure B A D C E GGiven a digraph 𝐺, the transitive closure of 𝐺 is the digraph 𝐺 ∗ such that G* has the same vertices as G if 𝐺 has a directed path from 𝑢 to 𝑣 (𝑢  𝑣), 𝐺 ∗ has a directed edge from 𝑢 to 𝑣 The transitive closure provides reachability information about a digraph B A D C E G*

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 𝑂(𝑛(𝑛+𝑚)) Alternatively ... Use dynamic programming: The Floyd-Warshall Algorithm

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

14 Floyd-Warshall’s AlgorithmNumber vertices 𝑣 1 ,…, 𝑣 𝑛 Compute digraphs 𝐺 0 ,…, 𝐺 𝑛 𝐺 0 ←𝐺 𝐺 𝑘 has directed edge 𝑣 𝑖 , 𝑣 𝑗 if 𝐺 has a directed path from 𝑣 𝑖 to 𝑣 𝑗 We have that 𝐺 𝑛 = 𝐺 ∗ In phase 𝑘, digraph 𝐺 𝑘 is computed from 𝐺 𝑘−1 Running time: 𝑂 𝑛 3 , assuming 𝐺.areAdjacent 𝑣 𝑖 , 𝑣 𝑗 is 𝑂 1 (e.g., adjacency matrix) Algorithm FloydWarshall(𝐺) Input: Digraph 𝐺 Output: Transitive Closure 𝐺 ∗ of 𝐺 Name each vertex 𝑣∈𝐺.vertices( ) with 𝑖=1…𝑛 𝐺 0 ←𝐺 for 𝑘←1…𝑛 do 𝐺 𝑘 ← 𝐺 𝑘−1 for 𝑖←1…𝑛 | 𝑖≠𝑘 do for 𝑗←1…𝑛 | 𝑗≠𝑖,𝑘 do if 𝐺 𝑘−1 .areAdjacent 𝑣 𝑖 , 𝑣 𝑘 ∧ 𝐺 𝑘−1 .areAdjacent 𝑣 𝑘 , 𝑣 𝑗 ∧ ¬ 𝐺 𝑘 .areAdjacent 𝑣 𝑖 , 𝑣 𝑗 then 𝐺 𝑘 .insertDirectedEdge v i , v j return 𝐺 𝑛

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

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

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

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

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

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

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

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

23 DAGs and Topological OrderingB A D C E DAG G A directed acyclic graph (DAG) is a digraph that has no directed cycles A topological ordering of a digraph is a numbering 𝑣 1 ,…, 𝑣 𝑛 Of the vertices such that for every edge 𝑣 𝑖 , 𝑣 𝑗 , we have 𝑖<𝑗 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 A D C E Topological ordering of G v1 v2 v3 v4 v5

24 Exercise Topological Sortingwrite c.s. program play wake up eat nap study computer sci. more c.s. work out sleep dream about graphs A typical student day bake cookies Number vertices, so that 𝑢,𝑣 in 𝐸 implies 𝑢<𝑣

25 Exercise Topological Sortingwrite c.s. program play wake up eat nap study computer sci. more c.s. work out sleep dream about graphs A typical student day 1 2 3 4 5 6 7 8 9 10 11 bake cookies Number vertices, so that 𝑢,𝑣 in 𝐸 implies 𝑢<𝑣

26 Algorithm for Topological SortingNote: This algorithm is different than the one in the book Algorithm TopologicalSort 𝐺 𝐻←𝐺 𝑛←𝐺.numVertices while ¬𝐻.empty do Let 𝑣 be a vertex with no outgoing edges Label 𝑣←𝑛 𝑛←𝑛−1 𝐻.eraseVertex 𝑣

27 Implementation with DFSSimulate the algorithm by using depth-first search 𝑂(𝑛+𝑚) time. Algorithm topologicalDFS 𝐺 Input: DAG 𝐺 Output: Topological ordering of 𝑔 𝑛←𝐺.numVertices Initialize all vertices as 𝑈𝑁𝐸𝑋𝑃𝐿𝑂𝑅𝐸𝐷 for each vertex 𝑣∈𝐺.vertices do if 𝑣.getLabel =𝑈𝑁𝐸𝑋𝑃𝐿𝑂𝑅𝐸𝐷 then topologicalDFS 𝐺, 𝑣 Algorithm topologicalDFS 𝐺,𝑣 Input: DAG 𝐺, start vertex 𝑣 Output: Labeling of the vertices of 𝐺 in the connected component of 𝑣 𝑣.setLabel(𝑉𝐼𝑆𝐼𝑇𝐸𝐷) for each 𝑒∈𝑣.outEdges do 𝑤←𝑒.dest( ) if 𝑤.getLabel =𝑈𝑁𝐸𝑋𝑃𝐿𝑂𝑅𝐸𝐷 then //𝑒 is a discovery edge topologicalDFS 𝐺, 𝑤 else //𝑒 is a forward, cross, or back edge Label 𝑣 with topological number 𝑛 𝑛←𝑛−1

28 Topological Sorting Example

29 Topological Sorting Example9

30 Topological Sorting Example8 9

31 Topological Sorting Example7 8 9

32 Topological Sorting Example7 8 6 9

33 Topological Sorting Example7 8 5 6 9

34 Topological Sorting Example7 4 8 5 6 9

35 Topological Sorting Example7 4 8 5 6 3 9

36 Topological Sorting Example2 7 4 8 5 6 3 9

37 Topological Sorting Example2 7 4 8 5 6 1 3 9