Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Directed GraphsReference: Chapter 19, Algorithms in Java, 3rd Edition, Robert Sedgewick.2Directed GraphsDigraph. Set of objects with oriented pairwise connections.Ex. One-way street, hyperlink.3Digraph ApplicationsDigraph Vertex Edgefinancial stock, currency transactiontransportation street intersection, airport highway, airway routescheduling task precedence constraintcontrol flow code block jumpInternet web page hyperlinkgame board position legal movetelephone person placed callfood web species predator-prey relationinfectious disease person infectioncitation journal article citationobject graph object pointerinheritance hierarchy class inherits from4Ecological Food WebFood web graph.! Vertex = species.! Edge = from prey to predator.Reference: http://www.twingroves.district96.k12.il.us/Wetlands/Salamander/SalGraphics/salfoodweb.giff5Some Digraph ProblemsTransitive closure. Is there a directed path from v to w?Strong connectivity. Are all vertices mutually reachable?Topological sort. Can you draw the graph so that all of the edges pointfrom left to right?PERT/CPM. Given a set of tasks with precedence constraints, what isthe earliest that we can complete each task?Shortest path. Given a weighted graph, find best route from v to w?PageRank. What is the importance of a web page?6Digraph RepresentationVertex names.! This lecture: use integers between 0 and V-1.! Real world: convert between names and integers with symbol table.Orientation of edge matters.AGECBFDHMKJLI7Adjacency Matrix RepresentationAdjacency matrix representation.! Two-dimensional V ! V boolean array.! Edge v"w in graph: adj[v][w] = true. A B C D E F G H I J K L M 0 A 0 1 1 0 0 1 1 0 0 0 0 0 0 1 B 0 0 0 0 0 0 0 0 0 0 0 0 0 2 C 0 0 0 0 0 0 0 0 0 0 0 0 0 3 D 0 0 0 0 0 0 0 0 0 0 0 0 0 4 E 0 0 0 1 0 0 0 0 0 0 0 0 0 5 F 0 0 0 1 1 0 0 0 0 0 0 0 0 6 G 0 0 0 0 1 0 0 0 0 0 0 0 0 7 H 0 0 0 0 0 0 0 0 1 0 0 0 0 8 I 0 0 0 0 0 0 0 0 0 0 0 0 0 9 J 0 0 0 0 0 0 0 0 0 0 1 1 110 K 0 0 0 0 0 0 0 0 0 0 0 0 011 L 0 0 0 0 0 0 0 0 0 0 0 0 112 M 0 0 0 0 0 0 0 0 0 0 0 0 0AGECBFDHMKJLI8Adjacency List RepresentationVertex indexed array of lists.! Space proportional to number of edges.! One representation of each edge.A: F C B GB:C:D:E: DF: E DG: EH: II:J: K L MK:L: MM:AGECBFDHMKJLI9Adjacency List: Java ImplementationImplementation. Same as Graph, but only insert one copy of each edge.public class Digraph { private int V; private Sequence<Integer>[] adj; public Digraph(int V) { this.V = V; adj = (Sequence<Integer>[]) new Sequence[V]; for (int v = 0; v < V; v++) adj[v] = new Sequence<Integer>(); } public void insert(int v, int w) { adj[v].add(w); } public Iterable<Integer> adj(int v) { return adj[v]; }}10Digraph RepresentationsDigraphs are abstract mathematical objects.! ADT implementation requires specific representation.! Efficiency depends on matching algorithms to representations.Digraphs in practice. [use adjacency list representation]! Real world digraphs are sparse.! Bottleneck is iterating over edges leaving v.Representation SpaceAdjacency matrix#(V 2 )Adjacency list#(E + V)Edge fromv to w?#(1)O(outdeg(v))Enumerate edgesleaving v?#(V)#(outdeg(v))List of edges #(E + V ) O(E) #(E)Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Digraph Search12ReachabilityGoal. Find all vertices reachable from s along a directed path.Depth first search. To visit a vertex v:! Mark v as visited.! Recursively visit all unmarked vertices w adjacent to v.Running time. O(E) since each edge examined at most once.s13public class DFSearcher { private boolean[] marked; public DFSearcher(Digraph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) if (!marked[w]) dfs(G, w); } public boolean isReachable(int v) { return marked[v]; }}Depth First SearchRemark. Same as undirected version, except Digraph instead of Graph.14Control Flow GraphControl-flow graph.! Vertex = basic block (straight-line program).! Edge = jump.Dead code elimination. Find (and remove) code blocks that areunreachable during execution.Infinite loop detection. Exit block is unreachable from entry block.Caveat. Not all infinite loops are detectable.dead code might arise from compiler optimizations(or careless programmer)15Mark-Sweep Garbage CollectorRoots. Objects known to be accessible by program (e.g., stack).Live objects. Objects that the program could get to by starting at aroot and following a chain of pointers.Mark-sweep algorithm. [McCarthy 1960]! Mark: run DFS from roots to mark live objects.! Sweep: if object is unmarked, it is garbage, so add to free list.Extra memory. Uses 1 extra mark bit per object, plus DFS stack.easy to identify pointers in type-safe language16Depth First SearchDFS enables direct solution of simple digraph problems.! Reachability.! Cycle detection.! Topological sort.! Transitive closure.! Find path from s to t.Basis for solving difficult digraph problems.! Directed Euler path.! Strong connected components.17Breadth First SearchShortest path. Find the shortest directed path from s to t.BFS. Analogous to BFS in undirected graphs.st18Application: Web CrawlerWeb graph. Vertex = website, edge = hyperlink.Goal. Crawl Internet, starting from some root website.Solution. BFS with implicit graph.BFS.! Start at some root website, say http://www.princeton.edu.! Maintain a Queue of websites to explore.! Maintain a SET of discovered websites.! Dequeue the next website, and enqueue websites to which it links(provided you haven't done so before).Q. Why not use DFS?19Web Crawler: Java ImplementationQueue<String> q = new Queue<String>();SET<String> visited = new SET<String>();String s = "http://www.princeton.edu";q.enqueue(s);visited.add(s);while (!q.isEmpty()) { String v = q.dequeue(); System.out.println(v); In in = new In(v); String input = in.readAll(); String regexp = "http://(\\w+\\.)*(\\w+)"; Pattern pattern = Pattern.compile(regexp); Matcher matcher = pattern.matcher(input); while (matcher.find()) { String w = matcher.group(); if (!visited.contains(w)) { visited.add(w); q.enqueue(w); } }}read in raw htmlsearch using regular expressionif unvisited, mark as visitedand put on queuehttp://xxx.yyy.zzzstart crawling from
View Full Document
Unlocking...