Question? Leave a message!




Depth-first search in digraphs

Depth-first search in digraphs
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms FOUR TH EDITION topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu4.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDirected graphs Digraph. Set of vertices connected pairwise by directed edges. outdegree = 4 indegree = 2 0 0 6 8 7 directed path 2 2 1 1 from 0 to 2 3 3 9 9 10 10 directed cycle 4 4 5 5 11 11 12 12 3Road network To see all the details that are visible on the screen,use the Address Holland Tunnel "Print" link next to the map. New York, NY 10013 Vertex = intersection; edge = oneway street. ©2008 Google Map data ©2008 Sanborn, NAVTEQ™ Terms of Use 4Political blogosphere graph Vertex = political blog; edge = link. The Political Blogosphere and the 2004 U.S. Election: Divided They Blog, Adamic and Glance, 2005 Figure 1: Community structure of political blogs (expanded set), shown using utilizing a GEM layout 11 in the GUESS3 visualization and analysis tool. The colors reflect political orientation, 5 red for conservative, and blue for liberal. Orange links go from liberal to conservative, and purple ones from conservative to liberal. The size of each blog reflects the number of other blogs that link to it. longer existed, or had moved to a different location. When looking at the front page of a blog we did not make a distinction between blog references made in blogrolls (blogroll links) from those made in posts (post citations). This had the disadvantage of not differentiating between blogs that were actively mentioned inapostonthatday, fromblogrolllinksthatremainstaticovermanyweeks10. Since posts usually contain sparse references to other blogs, and blogrolls usually contain dozens of blogs, we assumed that the network obtained by crawling the front page of each blog would strongly reflect blogroll links. 479 blogs had blogrolls through blogrolling.com, while many others simply maintained a list of links to their favorite blogs. We did not include blogrolls placed on a secondary page. We constructed a citation network by identifying whether a URL present on the page of one blog references another political blog. We called a link found anywhere on a blog’s page, a “page link” to distinguishitfroma“postcitation”,alinktoanotherblogthatoccursstrictlywithinapost. Figure1 shows the unmistakable division between the liberal and conservative political (blogo)spheres. In fact, 91 of the links originating within either the conservative or liberal communities stay within that community. An effect that may not be as apparent from the visualization is that even though we started with a balanced set of blogs, conservative blogs show a greater tendency to link. 84 of conservative blogs link to at least one other blog, and 82 receive a link. In contrast, 74 of liberal blogs link to another blog, while only 67 are linked to by another blog. So overall, we see a slightly higher tendency for conservative blogs to link. Liberal blogs linked to 13.6 blogs on average, while conservative blogs linked to an average of 15.1, and this difference is almost entirely due to the higher proportion of liberal blogs with no links at all. Although liberal blogs may not link as generously on average, the most popular liberal blogs, Daily Kos and Eschaton (atrios.blogspot.com), had 338 and 264 links from our singleday snapshot 4Overnight interbank loan graph Vertex = bank; edge = overnight loan. GSCC GWCC GIN GOUT DC Tendril " '( )+ ,). /012 ,1 34/56 7'8 799:; = "/ 02+ A1A/) A1541/8 The Topology of the Federal Funds Market, Bech and Atalay, 2008 B )".A1A/) A1541/8 3 "/ ./1+ A1A/) A1541/8 CD "/ "EA1541/8 FGH "/ 1/E A1541/; F /I". ) /I 0 JK 1). " /I 38 L9L 1). " /I CD8 :K 6 1). " FGH8 J9 1). " /I /)"+. ) 7 1). " )".A1A/) A1541/; "'( HI1).1,/012A64/"/"1)"/1A1++A/"11,)".M1"/./.A++))".A1A/) A1541/.8"" "; HI 1). 0"/I" AI )".A1A/) A1541/ )1 1/ IN +"2. /1 1 ,15 1). " 1/I A1541/8 ";;8 """" " " " ' ", ( ; HI A1541/ 0"/I /I +./ 56 1, 1). ". ,) /1 . /I ) +",. /'"/"0 /'12'" O=P; C 1/I 01).8 /I = ". /I +./ A1541/ 1, /I /012 " 0I"AI ++ 1). A1A/ /1 AI 1/I N" )"A/) 4/I.; HI 5"" )".A1A/) A1541/. OB.P .5++ A1541/. ,1 0I"AI /I .5 ". /; C 54""A+ ./)". /I = ". 1,/ ,1) /1 6 .N+ 1). 1, 5"/) + /I 1, /I B. O. Q1) " 3 O7999PP; HI = A1."./. 1, ) 45'). /'"/"0 /'12'" O3P8 ) '67/'12'" OFGHP8 ) 7/'12'" OCDP ) "054 O. " 'P; HI 3 A154".. ++ 1). /I/ A AI N 1/I 1) " /I 3 /I1I )"A/) 4/I; R 1) ". " /I FGH ", "/ I. 4/I ,15 /I 3 6/ 1/ /1 /I 3; C A1/./8 1) ". " /I CD ", "/ I. 4/I /1 /I 3 6/ 1/ ,15 "/; R S9 1) ". " /)"+ ", "/ )1. 1/ .") 1 )"A/) 4/I /1 1 ,15 /I 3; 4/644'( C/I/0121,45/../1N)0"+T)6315U2" " 3 O799:P8 /I3 ". /I +./ A1541/; F N8 +51./ ' 1, /I 1). " /I/ /012 6+1 /1 /I 3; C A1/./8 /I 3 ". 5AI .5++ ,1 /I ,)+ ,). /012; C 799:8 1+ (') (' 1, /I 1). 6+1 /1 /I". A1541/; Q , /I +./ A1541/ ". /I CD; C 799:8 )'))' 1, /I 1). 0 " /I". A1541/; HI FGH A1/") (') +' 1, ++ 1). 4 )8 0I"+ /I 0 (+') ,' 1, SS /I 1). +1A/) " /I /)"+.; V.. /I ') (' 1, /I 1). 0 " /I 5"" )".A1A/) A1541/. O. H6+ JP; S9 HI /)"+. 5 +.1 6 )"W/"/) "/1 /I .6A1541/.( ./ 1, 1). /I/ 1 4/I 5/" ,15 CD8 ./ 1, 1). /I/ 1 4/I +)" /1 FGH8 ) ./ 1, 1). /I/ 1 4/I /I/ 6". " CD ) ). " FGH; SS " 1, 1). 0 " X,15ECDY /)"+.8 1, 1). 0 " /I X/1EFGHY /)"+. ) " 1, 1). 0 " X/6.Y ,15 CD /1 FGH; S7Uber taxi graph Vertex = taxi pickup; edge = taxi ride. http://blog.uber.com/2012/01/09/uberdatasanfranciscomics/ 7Implication graph Vertex = variable; edge = logical implication. if x5 is true, then x0 is true x x 2 0 x x x 6 4 3 x x x x 5 1 1 5 x x x 3 4 6 x x 0 2 8Combinational circuit Vertex = logical gate; edge = wire. 9WordNet graph Vertex = synset; edge = hypernym relationship. event happening occurrence occurrent naturalevent miracle act humanac on humanac vity change altera on modi ca on miracle groupac on damage harm .. impairment transi on increase forfeit forfeiture ac on resistance opposi on transgression leap jump salta on jump leap change demo on varia on mo on movement move locomo on travel descent run running jump parachu ng http://wordnet.princeton.edu dash sprint 10 Digraph applications digraph vertex directed edge street intersection oneway street transportation web page hyperlink web species predatorprey relationship food web synset hypernym WordNet task precedence constraint scheduling bank transaction financial person placed call cell phone person infection infectious disease board position legal move game journal article citation citation object pointer object graph class inherits from inheritance hierarchy code block jump control flow 11Some digraph problems problem description s→t path Is there a path from s to t shortest s→t path What is the shortest path from s to t directed cycle Is there a directed cycle in the graph topological sort Can the digraph be drawn so that all edges point upwards strong connectivity Is there a directed path between all pairs of vertices transitive closure For which vertices v and w is there a directed path from v to w PageRank What is the importance of a web page 124.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDigraph API Almost identical to Graph API. public class Digraph public class Digraph Digraph(int V) Digraph(int V) create an empty digraph with V vertices Digraph(In in) Digraph(In in) create a digraph from input stream void addEdge(int v, int w) addEdge(int v, int w) add a directed edge v→w IterableInteger adj(int v) adj(int v) vertices pointing from v int V() V() number of vertices int E() E() number of edges Digraph reverse() reverse() reverse of this digraph String toString() toString() string representation 14Digraph API java Digraph tinyDG.txt tinyDG.txt 5 1 05 V 13 E 01 22 4 2 20 adj 2 3 0 3 23 3 2 0 35 6 0 5 2 1 0 1 32 2 0 2 43 3 2 11 12 3 42 12 9 4 9 10 54 4 9 11 5 ⋮ 7 9 9 4 8 0 6 10 12 114 11 4 7 1112 4 3 6 9 8 129 3 5 9 6 8 6 8 6 10 5 4 ⋮ 11 10 11 0 5 6 4 12 6 9 12 In in = new In(args0); read digraph from 7 6 input stream Digraph G = new Digraph(in); 4 12 9 for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (once) StdOut.println(v + "" + w); 15Digraph representation: adjacency lists Maintain vertexindexed array of lists. tinyDG.txt 5 1 V 13 E 22 tinyDG.txt 4 2 5 1 V adj 2 3 0 3 13 E 3 2 0 22 6 0 1 5 2 0 1 4 2 2 0 2 adj 2 3 0 3 3 2 11 12 3 3 2 12 9 0 4 9 10 4 6 0 9 11 5 2 1 5 0 1 7 9 9 4 8 0 6 10 12 2 0 2 11 4 7 3 2 11 12 4 3 6 9 3 8 12 9 3 5 9 6 8 4 9 10 6 4 8 6 10 9 11 5 4 5 11 11 10 0 5 7 9 9 4 8 0 6 4 6 12 10 12 6 9 12 11 4 7 7 6 6 9 4 3 4 12 8 3 5 9 9 6 8 16 6 8 6 10 5 4 11 10 11 0 5 6 4 12 6 9 12 7 6 4 12 9Digraph representations In practice. Use adjacencylists representation. Algorithms based on iterating over vertices pointing from v. Realworld digraphs tend to be sparse. huge number of vertices, small average vertex degree insert edge edge from iterate over vertices representation space from v to w v to w pointing from v list of edges E 1 E E 2 † adjacency matrix V 1 1 V adjacency lists E + V 1 outdegree(v) outdegree(v) † disallows parallel edges 17Adjacencylists graph representation (review): Java implementation public class Graph private final int V; adjacency lists private final BagInteger adj; public Graph(int V) create empty graph with V vertices this.V = V; adj = (BagInteger) new BagV; for (int v = 0; v V; v++) adjv = new BagInteger(); add edge v–w public void addEdge(int v, int w) adjv.add(w); adjw.add(v); iterator for vertices public IterableInteger adj(int v) adjacent to v return adjv; 18Adjacencylists digraph representation: Java implementation public class Digraph private final int V; adjacency lists private final BagInteger adj; public Digraph(int V) create empty digraph with V vertices this.V = V; adj = (BagInteger) new BagV; for (int v = 0; v V; v++) adjv = new BagInteger(); add edge v→w public void addEdge(int v, int w) adjv.add(w); iterator for vertices public IterableInteger adj(int v) pointing from v return adjv; 194.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduReachability Problem. Find all vertices reachable from s along a directed path. s 21Depthfirst search in digraphs Same method as for undirected graphs. Every undirected graph is a digraph (with edges in both directions). DFS is a digraph algorithm. DFS (to visit a vertex v) Mark v as visited. Recursively visit all unmarked vertices w pointing from v. 22Depthfirst search demo 4→2 To visit a vertex v : 2→3 Mark vertex v as visited. 3→2 Recursively visit all unmarked vertices pointing from v. 6→0 0→1 2→0 0 0 11→12 12→9 6 8 7 9→10 9→11 2 2 1 1 8→9 10→12 11→4 3 3 9 9 10 10 4→3 3→5 4 4 6→8 8→6 5 5 5→4 11 11 12 12 0→5 6→4 6→9 a directed graph 7→6 23Depthfirst search demo To visit a vertex v : Mark vertex v as visited. Recursively visit all unmarked vertices pointing from v. 0 v marked edgeTo 6 8 7 0 T – 1 T 0 2 1 2 T 3 reachable from vertex 0 3 T 4 4 T 5 5 T 0 3 9 10 6 F – 7 F – 4 8 F – 9 F – 5 10 F – 11 12 11 F – 12 F – reachable from 0 24Depthfirst search (in undirected graphs) Recall code for undirected graphs. public class DepthFirstSearch true if connected to s private boolean marked; public DepthFirstSearch(Graph G, int s) constructor marks marked = new booleanG.V(); vertices connected to s dfs(G, s); recursive DFS does the work private void dfs(Graph G, int v) markedv = true; for (int w : G.adj(v)) if (markedw) dfs(G, w); client can ask whether any public boolean visited(int v) vertex is connected to s return markedv; 25Depthfirst search (in directed graphs) Code for directed graphs identical to undirected one. substitute Digraph for Graph public class DirectedDFS true if path from s private boolean marked; public DirectedDFS(Digraph G, int s) constructor marks marked = new booleanG.V(); vertices reachable from s dfs(G, s); recursive DFS does the work private void dfs(Digraph G, int v) markedv = true; for (int w : G.adj(v)) if (markedw) dfs(G, w); client can ask whether any public boolean visited(int v) vertex is reachable from s return markedv; 26Reachability application: program controlflow analysis Every program is a digraph. Vertex = basic block of instructions (straightline program). Edge = jump. Deadcode elimination. Find (and remove) unreachable code. Infiniteloop detection. Determine whether exit is unreachable. 27roots Reachability application: marksweep garbage collector Every data structure is a digraph. Vertex = object. Edge = reference. Roots. Objects known to be directly accessible by program (e.g., stack). Reachable objects. Objects indirectly accessible by program (starting at a root and following a chain of pointers). 28roots Reachability application: marksweep garbage collector Marksweep algorithm. McCarthy, 1960 Mark: mark all reachable objects. Sweep: if object is unmarked, it is garbage (so add to free list). Memory cost. Uses 1 extra mark bit per object (plus DFS stack). 29Depthfirst search in digraphs summary DFS enables direct solution of simple digraph problems. ✓ Reachability. Path finding. Topological sort. Directed cycle detection. Basis for solving difficult digraph problems. 2satisfiability. Directed Euler path. Stronglyconnected components. COMPUT. SIAM J. Vol. 1, No. 2, June 1972 DEPTHFIRST SEARCH AND LINEAR GRAPH ALGORITHMS ROBERT TARJAN" Abstract. The value of depthfirst search or "bacltracking" as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected of a directed and for the biconnected of an un components graph ar algorithm finding components direct graph are presented. The space and time requirements of both algorithms are bounded by k k forsomeconstants and k where Vis thenumber ofverticesandE is thenumber + d kl, k2, 1V a, k2E the ofedges of graph being examined. Key words. Algorithm, backtracking, biconnectivity, connectivity, depthfirst, graph, search, spanning tree, strongconnectivity. 30 1. of U and a Introduction. Consider a graph G, consisting of a set vertices g. set of are ordered edges The graph may either be directed (the edges pairs (v, w) of v is the tail and w is the head of the or undirected are vertices; edge) (the edges unordered of also as Graphs form a suitable pairs vertices, represented (v, w)). abstraction for problems in many areas; chemistry, electrical engineering, and sociology, for example. Thus it is important to have the most economical algo rithms for answering graphtheoretical questions. least few definitions. In studying graph algorithms we cannot avoid at a definitions are moreorless standard the literature. These in (See Harary 3, for IfG g) is a a path w in G is a ofvertices instance.) (, graph, p’v sequence and edges from v to w.A path is simple ifall its vertices are distinct.A path leading v is called a closed path. A closed path v is a cycle if all its edges are p’v p’v distinct and the only vertex to occur twice in p is v, which occurs exactly twice. be the Two cycles which are cyclic permutations of each other are considered to of is the formed same cycle. The undirected version a directed graph graph by each of the directed into an undirected and converting edge graph edge removing An undirected is connected if there is a between every duplicate edges. graph path of vertices. pair A tree T is a directed graph whose undirected version is (directed rooted) of connected, having one vertex which is the head no edges the (called root), the root are the head of one The and such that all vertices except exactly edge. relation is an of T" is denoted v w. The relation "There is a "(v, w) edge by from v tow in T" is denoted v w. Ifv v is the ofw andw is a path by w, father son of v. Ifv v is an ancestor ofw andw is a descendant of v. Every vertex is an w, ancestor and a descendant of itself. If v is a vertex in a tree T, T is the subtree ofT of G T having as vertices all the descendants v in T. If is a directed graph, a tree G if ofG T contains all the vertices of G. is a spanning tree of T is a subgraph and and S are R is the transitive closure of R1 is the IfR binary relations, R, inverse of and R, RS e w)lZlv((u,v)R (v, w) (u, S). and in revised form Received by the editors August 30, 1971, March 9, 1972. Department of Computer Science, Cornell University, Ithaca, New York 14850. This research and the National Science Foundation under Grant GJ992. was supported by the Hertz Foundation " 146Breadthfirst search in digraphs Same method as for undirected graphs. Every undirected graph is a digraph (with edges in both directions). BFS is a digraph algorithm. BFS (from source vertex s) Put s onto a FIFO queue, and mark s as visited. Repeat until the queue is empty: remove the least recently added vertex v for each unmarked vertex pointing from v: add to queue and mark as visited. Proposition. BFS computes shortest paths (fewest number of edges) from s to all other vertices in a digraph in time proportional to E + V. 31Directed breadthfirst search demo Repeat until queue is empty: Remove vertex v from queue. Add to queue all unmarked vertices pointing from v and mark them. tinyDG2.txt V 6 E 0 0 2 2 8 5 0 2 4 1 1 3 2 1 2 0 1 3 3 4 3 5 5 4 4 3 5 0 2 graph G 32Directed breadthfirst search demo Repeat until queue is empty: Remove vertex v from queue. Add to queue all unmarked vertices pointing from v and mark them. 0 2 v edgeTo distTo 0 – 0 1 0 1 1 2 0 1 3 4 3 4 2 2 3 5 3 4 5 4 done 33Multiplesource shortest paths tinyDG.txt 5 1 V Multiplesource shortest paths. Given a digraph and a set of source 13 E 22 vertices, find shortest path from any vertex in the set to each other vertex. 4 2 adj 2 3 0 3 3 2 Ex. S = 1, 7, 10 . 0 6 0 Shortest path to 4 is 7→6→4. 5 2 1 0 1 Shortest path to 5 is 7→6→0→5. 2 0 2 3 2 11 12 Shortest path to 12 is 10→12. 3 12 9 … 4 9 10 4 9 11 5 7 9 9 4 8 0 6 10 12 11 4 7 6 9 4 3 8 3 5 9 6 8 6 8 6 10 5 4 Q. How to implement multisource shortest paths algorithm 11 10 11 0 5 A. Use BFS, but initialize by enqueuing all source vertices. 6 4 12 6 9 12 34 7 6 4 12 9Breadthfirst search in digraphs application: web crawler Goal. Crawl web, starting from some root web page, say www.princeton.edu. 25 34 0 Solution. BFS with implicit digraph 7 Choose root web page as source s. 2 10 40 19 33 Maintain a Queue of websites to explore. 29 15 41 49 8 44 Maintain a SET of discovered websites. 45 28 Dequeue the next website and enqueue 1 14 48 22 websites to which it links 39 21 18 6 (provided you haven't done so before). 42 13 23 47 31 11 12 32 30 26 5 37 27 9 16 43 24 4 38 3 17 35 36 46 20 Q. Why not use DFS How many strong components are there in this digraph 35Barebones web crawler: Java implementation QueueString queue = new QueueString(); queue of websites to crawl set of marked websites SETString marked = new SETString(); String root = "http://www.princeton.edu"; queue.enqueue(root); start crawling from root website marked.add(root); while (queue.isEmpty()) String v = queue.dequeue(); read in raw html from next StdOut.println(v); website in queue In in = new In(v); String input = in.readAll(); String regexp = "http://(\\w+\\.)+(\\w+)"; Pattern pattern = Pattern.compile(regexp); use regular expression to find all URLs Matcher matcher = pattern.matcher(input); in website of form http://xxx.yyy.zzz while (matcher.find()) crude pattern misses relative URLs String w = matcher.group(); if (marked.contains(w)) marked.add(w); if unmarked, mark it and put queue.enqueue(w); on the queue 36Web crawler output BFS crawl DFS crawl http://www.princeton.edu http://www.princeton.edu http://www.w3.org http://deimos.apple.com http://ogp.me http://www.youtube.com http://giving.princeton.edu http://www.google.com http://www.princetonartmuseum.org http://news.google.com http://www.goprincetontigers.com http://csi.gstatic.com http://library.princeton.edu http://googlenewsblog.blogspot.com http://helpdesk.princeton.edu http://labs.google.com http://tigernet.princeton.edu http://groups.google.com http://alumni.princeton.edu http://img1.blogblog.com http://gradschool.princeton.edu http://feeds.feedburner.com http://vimeo.com http:/buttons.googlesyndication.com http://princetonusg.com http://fusion.google.com http://artmuseum.princeton.edu http://insidesearch.blogspot.com http://jobs.princeton.edu http://agoogleaday.com http://odoc.princeton.edu http://static.googleusercontent.com http://blogs.princeton.edu http://searchresearch1.blogspot.com http://www.facebook.com http://feedburner.google.com http://twitter.com http://www.dot.ca.gov http://www.youtube.com http://www.TahoeRoads.com http://deimos.apple.com http://www.LakeTahoeTransit.com http://qeprize.org http://www.laketahoe.com http://en.wikipedia.org http://ethel.tahoeguide.com ... ... 374.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduPrecedence scheduling Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks Digraph model. vertex = task; edge = precedence constraint. 0. Algorithms 0 1. Complexity Theory 2. Artificial Intelligence 2 5 1 3. Intro to CS 4. Cryptography 3 4 5. Scientific Computing 6 6. Advanced Programming tasks precedence constraint graph feasible schedule 39Topological sort DAG. Directed acyclic graph. Topological sort. Redraw DAG so all edges point upwards. 0 0→5 0→2 0→1 3→6 2 5 1 3→5 3→4 5→2 6→4 3 4 6→0 3→2 1→4 6 directed edges DAG Solution. DFS. What else topological order 40Topological sort demo Run depthfirst search. Return vertices in reverse postorder. tinyDAG7.txt 0 0 7 11 0 5 0 2 0 1 2 2 5 5 1 1 3 6 3 5 3 4 5 2 3 3 4 4 6 4 6 0 3 2 6 6 a directed acyclic graph 41Topological sort demo Run depthfirst search. Return vertices in reverse postorder. 0 0 postorder 4 1 2 5 0 6 3 2 2 5 5 1 1 topological order 3 6 0 5 2 1 4 3 3 4 4 6 6 done 42Depthfirst search order public class DepthFirstOrder private boolean marked; private StackInteger reversePostorder; public DepthFirstOrder(Digraph G) reversePostorder = new StackInteger(); marked = new booleanG.V(); for (int v = 0; v G.V(); v++) if (markedv) dfs(G, v); private void dfs(Digraph G, int v) markedv = true; for (int w : G.adj(v)) if (markedw) dfs(G, w); reversePostorder.push(v); returns all vertices in public IterableInteger reversePostorder() “reverse DFS postorder” return reversePostorder; 43Topological sort in a DAG: intuition Why does topological sort algorithm work First vertex in postorder has outdegree 0. Secondtolast vertex in postorder can only point to last vertex. ... 0 0 postorder 4 1 2 5 0 6 3 2 2 5 5 1 1 topological order 3 6 0 5 2 1 4 3 3 4 4 6 6 44Topological sort in a DAG: correctness proof Proposition. Reverse DFS postorder of a DAG is a topological order. Pf. Consider any edge v→w. When dfs(v) is called: dfs(0) dfs(1) dfs(4) Case 1: dfs(w) has already been called and returned. 4 done 1 done Thus, w was done before v. dfs(2) 2 done dfs(5) check 2 Case 2: dfs(w) has not yet been called. 5 done dfs(w) will get called directly or indirectly 0 done check 1 by dfs(v) and will finish before dfs(v). check 2 v = 3 dfs(3) Thus, w will be done before v. check 2 case 1 check 4 check 5 dfs(6) Case 3: dfs(w) has already been called, case 2 check 0 but has not yet returned. check 4 6 done Can’t happen in a DAG: function call stack contains 3 done check 4 path from w to v, so v→w would complete a cycle. check 5 check 6 all vertices pointing from 3 are done before 3 is done, done so they appear after 3 in topological order 45Directed cycle detection Proposition. A digraph has a topological order iff no directed cycle. Pf. If directed cycle, topological order impossible. If no directed cycle, DFSbased algorithm finds a topological order. marked edgeTo onStack 0 1 2 3 4 5 ... 0 1 2 3 4 5 ... 0 1 2 3 4 5 ... dfs(0) dfs(5) 1 0 0 0 0 0 0 1 0 0 0 0 0 dfs(4) 1 0 0 0 0 1 5 0 1 0 0 0 0 1 dfs(3) 1 0 0 0 1 1 4 5 0 1 0 0 0 1 1 check 5 1 0 0 1 1 1 4 5 0 1 0 0 1 1 1 a digraph with a directed cycle Finding a directed cycle in a digraph Goal. Given a digraph, find a directed cycle. Solution. DFS. What else See textbook. 46Directed cycle detection application: precedence scheduling Scheduling. Given a set of tasks to be completed with precedence constraints, in what order should we schedule the tasks http://xkcd.com/754 Remark. A directed cycle implies scheduling problem is infeasible. 47Directed cycle detection application: cyclic inheritance The Java compiler does cycle detection. public class A extends B javac A.java A.java:1: cyclic inheritance ... involving A public class A extends B 1 error public class B extends C ... public class C extends A ... 48Directed cycle detection application: spreadsheet recalculation Microsoft Excel does cycle detection (and has a circular reference toolbar) 49Depthfirst search orders Observation. DFS visits each vertex exactly once. The order in which it does so can be important. Orderings. Preorder: order in which dfs() is called. Postorder: order in which dfs() returns. Reverse postorder: reverse order in which dfs() returns. private void dfs(Graph G, int v) markedv = true; preorder.enqueue(v); for (int w : G.adj(v)) if (markedw) dfs(G, w); postorder.enqueue(v); reversePostorder.push(v); 504.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduStronglyconnected components Def. Vertices v and w are strongly connected if there is both a directed path from v to w and a directed path from w to v. Key property. Strong connectivity is an equivalence relation: v is strongly connected to v. If v is strongly connected to w, then w is strongly connected to v. If v is strongly connected to w and w to x, then v is strongly connected to x. Def. A strong component is a maximal subset of stronglyconnected vertices. 5 stronglyconnected components A digraph and its strong components 52Connected components vs. stronglyconnected components v and w are strongly connected if there is both a directed v and w are connected if there is path from v to w and a directed path from w to v a path between v and w A graph and its connected components A digraph and its strong components A digraph and its strong components 3 connected components 5 stronglyconnected components connected component id (easy to compute with DFS) stronglyconnected component id (how to compute) 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 id 0 0 0 0 0 0 1 1 1 2 2 2 2 id 1 0 1 1 1 1 3 4 3 2 2 2 2 public boolean connected(int v, int w) public boolean stronglyConnected(int v, int w) return idv == idw; return idv == idw; constanttime client connectivity query constanttime client strongconnectivity query 53Strong component application: ecological food webs Food web graph. Vertex = species; edge = from producer to consumer. http://www.twingroves.district96.k12.il.us/Wetlands/Salamander/SalGraphics/salfoodweb.gif Strong component. Subset of species with common energy flow. 54Strong component application: software modules Software module dependency graph. Vertex = software module. Edge: from module to dependency. Firefox Internet Explorer Strong component. Subset of mutually interacting modules. Approach 1. Package strong components together. Approach 2. Use to improve design 55Strong components algorithms: brief history 1960s: Core OR problem. Widely studied; some practical algorithms. Complexity not understood. 1972: lineartime DFS algorithm (Tarjan). Classic algorithm. Level of difficulty: Algs4++. Demonstrated broad applicability and importance of DFS. 1980s: easy twopass lineartime algorithm (KosarajuSharir). Forgot notes for lecture; developed algorithm in order to teach it Later found in Russian scientific literature (1972). 1990s: more easy lineartime algorithms. Gabow: fixed old OR algorithm. CheriyanMehlhorn: needed onepass algorithm for LEDA. 56KosarajuSharir algorithm: intuition R Reverse graph. Strong components in G are same as in G . Kernel DAG. Contract each strong component into a single vertex. how to compute Idea. Compute topological order (reverse postorder) in kernel DAG. Run DFS, considering vertices in reverse topological order. first vertex is a sink (has no edges pointing from it) E A B D C Kernel DAG in reverse topological order A digraph and its strong components digraph G and its strong components kernel DAG of G (topological order: A B C D E) 57KosarajuSharir algorithm demo R Phase 1. Compute reverse postorder in G . R Phase 2. Run DFS in G, visiting unmarked vertices in reverse postorder of G . 0 0 6 6 8 8 7 7 2 2 1 1 3 3 9 9 10 10 4 4 5 5 11 11 12 12 digraph G 58KosarajuSharir algorithm demo R Phase 1. Compute reverse postorder in G . 1 0 2 4 5 3 11 9 12 10 6 7 8 0 6 8 7 2 1 1 3 9 10 4 5 11 12 R reverse digraph G 59KosarajuSharir algorithm demo R Phase 2. Run DFS in G, visiting unmarked vertices in reverse postorder of G . 1 0 2 4 5 3 11 9 12 10 6 7 8 0 v id 6 8 7 0 1 1 0 2 1 2 1 3 1 4 1 5 1 3 9 10 6 3 7 4 4 8 3 9 2 5 10 2 11 12 11 2 12 2 done 60KosarajuSharir algorithm Simple (but mysterious) algorithm for computing strong components. R Phase 1: run DFS on G to compute reverse postorder. Phase 2: run DFS on G, considering vertices in order given by first DFS. R DFS in reverse digraph G check unmarked vertices in the order reverse postorder for use in second dfs() 0 1 2 3 4 5 6 7 8 9 10 11 12 1 0 2 4 5 3 11 9 12 10 6 7 8 dfs(0) dfs(6) dfs(8) check 6 8 done dfs(7) 7 done 6 done dfs(2) dfs(4) dfs(11) dfs(9) dfs(12) check 11 dfs(10) check 9 10 done 12 done check 7 check 6 9 done ... 61 11 done check 6 dfs(5) dfs(3) check 4 check 2 3 done check 0 5 done 4 done check 3 2 done 0 done dfs(1) check 0 1 done check 2 check 3 check 4 check 5 check 6 check 7 check 8 check 9 check 10 check 11 check 12KosarajuSharir algorithm Simple (but mysterious) algorithm for computing strong components. R Phase 1: run DFS on G to compute reverse postorder. Phase 2: run DFS on G, considering vertices in order given by first DFS. DFS in original digraph G check unmarked vertices in the order 1 0 2 4 5 3 11 9 12 10 6 7 8 dfs(1) dfs(0) dfs(11) dfs(6) dfs(7) 1 done dfs(5) check 4 check 9 check 6 dfs(4) dfs(12) check 4 check 9 dfs(3) dfs(9) dfs(8) 7 done check 5 check 11 check 6 check 8 dfs(2) dfs(10) 8 done check 0 check 12 check 0 check 3 10 done 6 done 2 done 9 done 3 done 12 done check 2 11 done 4 done check 9 5 done check 12 check 1 check 10 0 done check 2 check 4 check 5 check 3 62KosarajuSharir algorithm Proposition. KosarajuSharir algorithm computes the strong components of a digraph in time proportional to E + V. Pf. R Running time: bottleneck is running DFS twice (and computing G ). nd Correctness: tricky, see textbook (2 printing). Implementation: easy 63Connected components in an undirected graph (with DFS) public class CC private boolean marked; private int id; private int count; public CC(Graph G) marked = new booleanG.V(); id = new intG.V(); for (int v = 0; v G.V(); v++) if (markedv) dfs(G, v); count++; private void dfs(Graph G, int v) markedv = true; idv = count; for (int w : G.adj(v)) if (markedw) dfs(G, w); public boolean connected(int v, int w) return idv == idw; 64Strong components in a digraph (with two DFSs) public class KosarajuSharirSCC private boolean marked; private int id; private int count; public KosarajuSharirSCC(Digraph G) marked = new booleanG.V(); id = new intG.V(); DepthFirstOrder dfs = new DepthFirstOrder(G.reverse()); for (int v : dfs.reversePostorder()) if (markedv) dfs(G, v); count++; private void dfs(Digraph G, int v) markedv = true; idv = count; for (int w : G.adj(v)) if (markedw) dfs(G, w); public boolean stronglyConnected(int v, int w) return idv == idw; 65Digraphprocessing summary: algorithms of the day singlesource DFS reachability in a digraph topological sort DFS in a DAG 0 6 7 8 strong 1 2 KosarajuSharir 9 10 components DFS (twice) 3 4 in a digraph 11 12 5 66
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017