Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·March 26, 2008 8:41:55 AMDirected GraphsReferences: Algorithms in Java, Chapter 19 http://www.cs.princeton.edu/algs4/52directed‣digraph API‣digraph search‣transitive closure‣topological sort‣strong components2Directed graphsDigraph. Set of vertices connected pairwise by oriented edges.AddressHolland TunnelNew York, NY 10013©2008 Google - Map data ©2008 Sanborn, NAVTEQ™ - Terms of UseTo see all the details that are visible on the screen,use the"Print" link next to the map.Vertex = web page.Edge = hyperlink.Page ranks with histogram for a larger example18316421328324922451 1440487441041290391191230262146524374335473823163643 1727203415219 33258 0 .002 1 .017 2 .009 3 .003 4 .006 5 .016 6 .066 7 .021 8 .017 9 .040 10 .002 11 .028 12 .006 13 .045 14 .018 15 .026 16 .023 17 .005 18 .023 19 .026 20 .004 21 .034 22 .063 23 .043 24 .011 25 .005 26 .006 27 .008 28 .037 29 .003 30 .037 31 .023 32 .018 33 .013 34 .024 35 .019 36 .003 37 .031 38 .012 39 .023 40 .017 41 .021 42 .021 43 .016 44 .023 45 .006 46 .023 47 .024 48 .019 49 .0166 223Web graphVertex = synset.Edge = hypernym relationship.4WordNet graph5Digraph applicationsgraphvertexedgetransportationstreet intersectionone-way streetwebweb pagehyperlinkWordNetsynsethypernymschedulingtaskprecedence constraintfinancialstock, currencytransactionfood webspeciespredator-prey relationshipcell phonepersonplaced callinfectious diseasepersoninfectiongameboard positionlegal movecitationjournal articlecitationobject graphobjectpointerinheritance hierarchyclass inherits fromcontrol flowcode blockjump6Digraph terminology7Some digraph problemsPath. Is there a directed path from s to t?Shortest path. What is the shortest directed path from s and t?Strong connectivity. Are all vertices mutually reachable?Transitive closure. For which vertices v and w is there a path from v to w?Topological sort. Can you draw the digraph so that all edges pointfrom left to right?PERT/CPM. Given a set of tasks with precedence constraints,how can we best complete them all?PageRank. What is the importance of a web page?8‣digraph API‣digraph search‣transitive closure‣topological sort‣strong componentsVertices.•This lecture: use integers between 0 and V-1.•Real world: convert between names and integers with symbol table.Edges: four options. [same as undirected graph, but orientation matters]•List of vertex pairs.•Adjacency matrix.•Adjacency lists.•Adjacency sets.9Digraph representations064215371210911810Digraph API public class Digraphgraph data typeDigraph(int V)create an empty digraph with V verticesDigraph(In in)create a digraph from input streamvoidaddEdge(int v, int w)add an edge v-wIterable<Integer>adj(int v)return an iterator over the neighbors of vint V()return number of verticesStringtoString()return a string representation In in = new In(); Graph G = new Digraph(in); StdOut.println(G); for (int v = 0; v < G.V(); v++) for (int w : G.adj(v)) /* process edge v-w */11Set of edges representationStore a list of the edges (linked list or array).0642153712109118 0 1 0 2 0 5 0 6 4 3 5 3 5 4 6 4 7 8 9 10 9 11 9 12 11 12 9 10 9 11 9 1212Adjacency-matrix representationMaintain a two-dimensional V-by-V boolean array;for each edge v → w in the digraph: adj[v][w] = true.0642153712109118012345678910111201234567891011120110011000000100000000000000000000000000000000000000000100000000000011000000000000100000000000000001000000000001000000000000000111000000000000000000000000010000000000000fromtoMaintain vertex-indexed array of lists.13Adjacency-list representation5 2 1 63434810 11 1212same as undirected graph,but one entry for each edge06421537121091180:1:2:3:4:5:6:7:8:9:10:11:12:Maintain vertex-indexed array of sets.14Adjacency-set representation06421537121091180:1:2:3:4:5:6:7:8:9:10:11:12:{ 1 2 5 6 }{ }{ }{ }{ 3 }{ 3, 4 }{ 4 }{ 8 }{ }{ 10, 11, 12 }{ }{ 12 }{ }same as undirected graph,but one entry for each edgeSame as Graph, but only insert one copy of each edge.15Adjacency-set representation: Java implementationpublic class Digraph{ private final int V; private final SET<Integer>[] adj; public Digraph(int V) { this.V = V; adj = (SET<Integer>[]) new SET[V]; for (int v = 0; v < V; v++) adj[v] = new SET<Integer>(); } public void addEdge(int v, int w) { adj[v].add(w); } public Iterable<Integer> adj(int v) { return adj[v]; }}adjacency setscreate empty graph withV verticesadd edge from v to w(no parallel edges)iterator for v's neighborsDigraphs are abstract mathematical objects, but:•ADT implementation requires specific representation.•Efficiency depends on matching algorithms to representations.In practice: use adjacency-set (or adjacency-list) representation.•Real-world digraphs tend to be sparse.•Algs all based on iterating over edges incident to v.16Digraph representationsrepresentationspaceedge betweenv and w?iterate over edgesincident to v?list of edgesEEEadjacency matrixV21Vadjacency listE + Vdegree(v)degree(v)adjacency setE + Vlog (degree(v))degree(v)17Typical digraph application: Google's PageRank algorithmGoal. Determine which pages on web are important.Solution. Ignore keywords and content, focus on hyperlink structure.Random surfer model.•Start at random page.•With probability 0.85, randomly select a hyperlink to visit next;with probability 0.15, randomly select any page.•PageRank = proportion of time random surfer spends on each page.Solution 1. Simulate random surfer for a long time.Solution 2. Compute ranks directly until they converge.Solution 3. Compute eigenvalues of adjacency matrix!None feasible without sparse digraph representation.Page ranks with histogram for a larger example18316421328324922451 1440487441041290391191230262146524374335473823163643 1727203415219 33258 0 .002 1 .017 2 .009 3 .003 4 .006 5 .016 6 .066 7 .021 8 .017 9 .040 10 .002 11 .028 12 .006 13 .045 14 .018 15 .026 16 .023 17 .005 18 .023 19 .026 20 .004 21 .034 22 .063 23 .043 24 .011 25 .005 26 .006 27 .008 28 .037 29 .003 30 .037 31 .023 32 .018 33 .013 34 .024 35 .019 36 .003 37 .031 38 .012 39 .023 40 .017 41 .021
View Full Document
Unlocking...