Question? Leave a message!




Dynamic connectivity problem

Dynamic connectivity problem
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 1.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms FOUR TH EDITION improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSubtext of today’s lecture (and this course) Steps to developing a usable algorithm. Model the problem. Find an algorithm to solve it. Fast enough Fits in memory If not, figure out why not. Find a way to address the problem. Iterate until satisfied. The scientific method. Mathematical analysis. 21.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDynamic connectivity problem Given a set of N objects, support two operation: Connect two objects. Is there a path connecting the two objects connect 4 and 3 connect 3 and 8 0 1 2 3 4 connect 6 and 5 connect 9 and 4 connect 2 and 1 5 6 7 8 9 are 0 and 7 connected 𐄂 ✔ are 8 and 9 connected connect 5 and 0 connect 7 and 2 connect 6 and 1 connect 1 and 0 ✔ are 0 and 7 connected 4A larger connectivity example Q. Is there a path connecting p and q p q A. Yes. 5Modeling the objects Applications involve manipulating objects of all types. Pixels in a digital photo. Computers in a network. Friends in a social network. Transistors in a computer chip. Elements in a mathematical set. Variable names in a Fortran program. Metallic sites in a composite system. When programming, convenient to name objects 0 to N – 1. Use integers as array index. Suppress details not relevant to unionfind. can use symbol table to translate from site names to integers: stay tuned (Chapter 3) 6Modeling the connections We assume "is connected to" is an equivalence relation: Reflexive: p is connected to p. Symmetric: if p is connected to q, then q is connected to p. Transitive: if p is connected to q and q is connected to r, then p is connected to r. Connected component. Maximal set of objects that are mutually connected. 0 1 2 3 4 5 6 7 0 1 4 5 2 3 6 7 3 connected components 7Implementing the operations Find. In which component is object p Connected. Are objects p and q in the same component Union. Replace components containing objects p and q with their union. 0 1 2 0 1 2 3 3 union(2, 5) 4 5 6 4 5 6 7 7 0 1 4 5 2 3 6 7 0 1 2 3 4 5 6 7 3 connected components 2 connected components 8Unionfind data type (API) Goal. Design efficient data structure for unionfind. Number of objects N can be huge. Number of operations M can be huge. Union and find operations may be intermixed. public class public class public class UF UF UF initialize unionfind data structure UF(int N) with N singleton objects (0 to N – 1) void union(int p, int q) add connection between p and q int find(int p) component identifier for p (0 to N – 1) boolean connected(int p, int q) are p and q in the same component public boolean connected(int p, int q) return find(p) == find(q); 1line implementation of connected() 9Dynamicconnectivity client Read in number of objects N from standard input. Repeat: – read in pair of integers from standard input – if they are not yet connected, connect them and print out pair more tinyUF.txt public static void main(String args) 10 4 3 int N = StdIn.readInt(); 3 8 UF uf = new UF(N); 6 5 while (StdIn.isEmpty()) 9 4 2 1 int p = StdIn.readInt(); 8 9 int q = StdIn.readInt(); 5 0 if (uf.connected(p, q)) 7 2 already connected 6 1 uf.union(p, q); 1 0 StdOut.println(p + " " + q); 6 7 101.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduQuickfind eager approach Data structure. if and only if Integer array id of length N. Interpretation: idp is the id of the component containing p. 0 1 2 3 4 5 6 7 8 9 0, 5 and 6 are connected 1, 2, and 7 are connected id 0 1 1 8 8 0 0 1 8 8 3, 4, 8, and 9 are connected 0 1 2 3 4 5 6 7 8 9 12Quickfind eager approach Data structure. Integer array id of length N. Interpretation: idp is the id of the component containing p. 0 1 2 3 4 5 6 7 8 9 id 0 1 1 8 8 0 0 1 8 8 id6 = 0; id1 = 1 Find. What is the id of p 6 and 1 are not connected Connected. Do p and q have the same id Union. To merge components containing p and q, change all entries whose id equals idp to idq. 0 1 2 3 4 5 6 7 8 9 after union of 6 and 1 id 1 1 1 8 8 1 1 1 8 8 problem: many values can change 13Quickfind demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 0 1 2 3 4 5 6 7 8 9 14Quickfind demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 1 1 1 8 8 1 1 1 8 8Quickfind: Java implementation public class QuickFindUF private int id; public QuickFindUF(int N) id = new intN; set id of each object to itself for (int i = 0; i N; i++) (N array accesses) idi = i; return the id of p public int find(int p) (1 array access) return idp; public void union(int p, int q) int pid = idp; int qid = idq; change all entries with idp to idq for (int i = 0; i id.length; i++) (at most 2N + 2 array accesses) if (idi == pid) idi = qid; 16Quickfind is too slow Cost model. Number of array accesses (for read or write). algorithm initialize union find connected N N 1 1 quickfind order of growth of number of array accesses quadratic 2 Union is too expensive. It takes N array accesses to process a sequence of N union operations on N objects. 17Quadratic algorithms do not scale Rough standard (for now). a truism (roughly) 9 10 operations per second. since 1950 9 10 words of main memory. Touch all words in approximately 1 second. Ex. Huge problem for quickfind. 9 9 10 union commands on 10 objects. 18 Quickfind takes more than 10 operations. 30+ years of computer time time quadratic 64T Quadratic algorithms don't scale with technology. New computer may be 10x as fast. 32T But, has 10x as much memory ⇒ want to solve a problem that is 10x as big. 16T linearithmic With quadratic algorithm, takes 10x as long 8T linear size 1K 2K 4K 8K 181.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduQuickunion lazy approach Data structure. Integer array id of length N. keep going until it doesn’t change (algorithm ensures no cycles) Interpretation: idi is parent of i. Root of i is ididid...idi.... 0 1 9 6 7 8 0 1 2 3 4 5 6 7 8 9 2 4 5 id 0 1 9 4 9 6 6 7 8 9 3 parent of 3 is 4 root of 3 is 9 20Quickunion lazy approach Data structure. Integer array id of length N. Interpretation: idi is parent of i. Root of i is ididid...idi.... 0 1 9 6 7 8 0 1 2 3 4 5 6 7 8 9 q 2 4 5 id 0 1 9 4 9 6 6 7 8 9 p 3 root of 3 is 9 Find. What is the root of p root of 5 is 6 Connected. Do p and q have the same root 3 and 5 are not connected Union. To merge components containing p and q, 1 0 7 8 6 set the id of p's root to the id of q's root. 9 q 5 0 1 2 3 4 5 6 7 8 9 2 4 id 0 1 9 4 9 6 6 7 8 6 3 p only one value changes 21Quickunion demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 0 1 2 3 4 5 6 7 8 9 22Quickunion demo 8 1 3 9 0 2 7 4 5 0 1 2 3 4 5 6 7 8 9 id 1 8 1 8 3 0 5 1 8 8 6Quickunion: Java implementation public class QuickUnionUF private int id; public QuickUnionUF(int N) set id of each object to itself id = new intN; (N array accesses) for (int i = 0; i N; i++) idi = i; public int find(int i) chase parent pointers until reach root while (i = idi) i = idi; (depth of i array accesses) return i; public void union(int p, int q) int i = find(p); change root of p to point to root of q int j = find(q); (depth of p and q array accesses) idi = j; 24Quickunion is also too slow Cost model. Number of array accesses (for read or write). algorithm initialize union find connected N N 1 1 quickfind † N N N N worst case quickunion † includes cost of finding roots Quickfind defect. Union too expensive (N array accesses). Trees are flat, but too expensive to keep them flat. Quickunion defect. Trees can get tall. Find/connected too expensive (could be N array accesses). 251.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduImprovement 1: weighting Weighted quickunion. Modify quickunion to avoid tall trees. Keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree. reasonable alternatives: quickunion q union by height or "rank" smaller p tree smaller larger tree tree might put the larger larger tree lower tree weighted always chooses the p better alternative q smaller smaller larger larger tree tree tree tree Weighted quickunion 27 q p q pWeighted quickunion demo 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 id 0 1 2 3 4 5 6 7 8 9 28Weighted quickunion demo 6 4 0 2 5 3 8 9 1 7 0 1 2 3 4 5 6 7 8 9 id 6 2 6 4 6 6 6 2 4 4Quickunion and weighted quickunion example quickunion quickunion average distance to root: 5.11 weighted average distance to root: 5.11 weighted average distance to root: 1.52 average distance to root: 1.52 Quickunion and weighted quickunion (100 sites, 88 union() operations) Quickunion and weighted quickunion (100 sites, 88 union() operations) 30Weighted quickunion: Java implementation Data structure. Same as quickunion, but maintain extra array szi to count number of objects in the tree rooted at i. Find/connected. Identical to quickunion. Union. Modify quickunion to: Link root of smaller tree to root of larger tree. Update the sz array. int i = find(p); int j = find(q); if (i == j) return; if (szi szj) idi = j; szj += szi; else idj = i; szi += szj; 31Weighted quickunion analysis Running time. Find: takes time proportional to depth of p. Union: takes constant time, given roots. lg = base2 logarithm Proposition. Depth of any node x is at most lg N. 0 1 1 1 1 depth 2 2 2 2 x 3 N = 10 depth(x) = 3 ≤ lg N 32Weighted quickunion analysis Running time. Find: takes time proportional to depth of p. Union: takes constant time, given roots. lg = base2 logarithm Proposition. Depth of any node x is at most lg N. Pf. What causes the depth of object x to increase Increases by 1 when tree T containing x is merged into another tree T . 1 2 The size of the tree containing x at least doubles since T ≥ T . 2 1 Size of tree containing x can double at most lg N times. Why 1 2 4 T lg N 2 8 16 T 1 ⋮ x N 33Weighted quickunion analysis Running time. Find: takes time proportional to depth of p. Union: takes constant time, given roots. Proposition. Depth of any node x is at most lg N. algorithm initialize union find connected N N 1 1 quickfind † N N N N quickunion † N lg N lg N lg N weighted QU † includes cost of finding roots Q. Stop at guaranteed acceptable performance A. No, easy to improve further. 34Improvement 2: path compression Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root. root 0 1 2 3 4 5 6 7 p 9 8 x 10 11 12 35Improvement 2: path compression Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root. root 0 p 9 1 2 3 11 12 4 5 x 6 7 8 10 36Improvement 2: path compression Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root. root 0 p 9 6 1 2 3 11 12 8 x 4 5 7 10 37Improvement 2: path compression Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root. root 0 p 9 6 3 1 x 2 7 11 12 8 4 5 10 38Improvement 2: path compression Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root. x root 0 p 9 6 3 1 2 7 11 12 8 4 5 10 Bottom line. Now, find() has the side effect of compressing the tree. 39Path compression: Java implementation Twopass implementation: add second loop to find() to set the id of each examined node to the root. Simpler onepass variant (path halving): Make every other node in path point to its grandparent. public int find(int i) while (i = idi) only one extra line of code idi = ididi; i = idi; return i; In practice. No reason not to Keeps tree almost completely flat. 40Weighted quickunion with path compression: amortized analysis Proposition. HopcroftUlman, Tarjan Starting from an N lg N empty data structure, any sequence of M unionfind ops 1 0 on N objects makes ≤ c ( N + M lg N ) array accesses. 2 1 Analysis can be improved to N + M α(M, N). 4 2 Simple algorithm with fascinating mathematics. 16 3 65536 4 65536 2 5 iterated lg function Lineartime algorithm for M unionfind ops on N objects Cost within constant factor of reading in the data. In theory, WQUPC is not quite linear. In practice, WQUPC is linear. Amazing fact. FredmanSaks No lineartime algorithm exists. in "cellprobe" model of computation 41Summary Key point. Weighted quick union (and/or path compression) makes it possible to solve problems that could not otherwise be addressed. algorithm worstcase time M N quickfind M N quickunion N + M log N weighted QU N + M log N QU + path compression N + M lg N weighted QU + path compression order of growth for M unionfind operations on a set of N objects 9 9 Ex. 10 unions and finds with 10 objects WQUPC reduces time from 30 years to 6 seconds. Supercomputer won't help much; good algorithm enables solution. 421.5 UNIONFIND dynamic connectivity ‣ quick find ‣ quick union ‣ Algorithms improvements ‣ applications ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduUnionfind applications Percolation. Games (Go, Hex). Dynamic connectivity. ✓ Least common ancestor. Equivalence of finite state automata. HoshenKopelman algorithm in physics. HinleyMilner polymorphic type inference. Kruskal's minimum spanning tree algorithm. Compiling equivalence statements in Fortran. Morphological attribute openings and closings. Matlab's bwlabel() function in image processing. 44Percolation An abstract model for many physical systems: NbyN grid of sites. Each site is open with probability p (and blocked with probability 1 – p). System percolates iff top and bottom are connected by open sites. does not percolate percolates blocked site open site open site connected to top no open site connected to top N = 8 45Percolation An abstract model for many physical systems: NbyN grid of sites. Each site is open with probability p (and blocked with probability 1 – p). System percolates iff top and bottom are connected by open sites. model system vacant site occupied site percolates electricity material conductor insulated conducts fluid flow material empty blocked porous social interaction population person empty communicates 46Likelihood of percolation Depends on grid size N and site vacancy probability p. p low (0.4) p medium (0.6) p high (0.8) does not percolate percolates percolates 47Percolation phase transition When N is large, theory guarantees a sharp threshold p. p p: almost certainly percolates. p p: almost certainly does not percolate. Q. What is the value of p 1 percolation probability p 0 0 0.593 1 site vacancy probability p N = 100 48Monte Carlo simulation Initialize all sites in an NbyN grid to be blocked. Declare random sites open until top connected to bottom. Vacancy percentage estimates p. full open site (connected to top) empty open site (not connected to top) blocked site N = 20 49Dynamic connectivity solution to estimate percolation threshold Q. How to check whether an NbyN system percolates A. Model as a dynamic connectivity problem and use unionfind. N = 5 open site blocked site 50Dynamic connectivity solution to estimate percolation threshold Q. How to check whether an NbyN system percolates 2 Create an object for each site and name them 0 to N – 1. N = 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 open site blocked site 51Dynamic connectivity solution to estimate percolation threshold Q. How to check whether an NbyN system percolates 2 Create an object for each site and name them 0 to N – 1. Sites are in same component iff connected by open sites. N = 5 open site blocked site 52Dynamic connectivity solution to estimate percolation threshold Q. How to check whether an NbyN system percolates 2 Create an object for each site and name them 0 to N – 1. Sites are in same component iff connected by open sites. Percolates iff any site on bottom row is connected to any site on top row. 2 bruteforce algorithm: N calls to connected() top row N = 5 bottom row open site blocked site 53Dynamic connectivity solution to estimate percolation threshold Clever trick. Introduce 2 virtual sites (and connections to top and bottom). Percolates iff virtual top site is connected to virtual bottom site. more efficient algorithm: only 1 call to connected() virtual top site top row N = 5 bottom row open site virtual bottom site blocked site 54Dynamic connectivity solution to estimate percolation threshold Q. How to model opening a new site open this site N = 5 open site blocked site 55Dynamic connectivity solution to estimate percolation threshold Q. How to model opening a new site A. Mark new site as open; connect it to all of its adjacent open sites. up to 4 calls to union() open this site N = 5 open site blocked site 56Percolation threshold Q. What is percolation threshold p A. About 0.592746 for large square lattices. constant known only via simulation 1 percolation probability p 0 0 0.593 1 site vacancy probability p N = 100 Fast algorithm enables accurate answer to scientific question. 57Subtext of today’s lecture (and this course) Steps to developing a usable algorithm. Model the problem. Find an algorithm to solve it. Fast enough Fits in memory If not, figure out why. Find a way to address the problem. Iterate until satisfied. The scientific method. Mathematical analysis. 58
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.AlexanderTyler
User Type:
Teacher
Country:
India
Uploaded Date:
21-07-2017