Question? Leave a message!




Disjoint sets

Disjoint sets
ECE 250 Algorithms and Data Structures Disjoint sets Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Disjoint sets 2 Outline In this topic, we will cover disjoint sets, including: – A review of equivalence relations – The definition of a Disjoint Set – An efficient data structure • A general tree – An optimization which results in • Worst case O(ln(n)) height • Average case O(a(n))) height • Best case Q(1) height – A few examples and applicationsDisjoint sets 3 Definitions Recall the properties of an equivalence relation: – a a for all a – a b if and only if b a – If a b and b c, it follows that a c An equivalence relation partitions a set into distinct equivalence classes Each equivalence class may be represented by a single object: the representative object – Another descriptive term for the sets in such a partition is disjoint setsDisjoint sets 4 Implicitly Defined Relations For example, bigQ defines an equivalence class of functions which grow at the same rate – We choose a single function to represent the class 2 e.g., we represent all functions with quadratic growth with n Another example: partition the numbers from 1 to 20 according to the relation a b if a and b share the same factors of 2: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 6, 10, 14, 18, 4, 12, 20, 8, 16 These equivalence relations are implicitly defined by the relationDisjoint sets 5 Explicitly Defined Disjoint Sets Alternatively, a partition or collection of disjoint sets may be used to explicitly define an equivalence relation: – a b if and only if a and b are in the same partition For example, the 10 numerals 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 can be partitioned into the three sets 1, 2, 3, 5, 7, 4, 6, 9, 0 , 8 Therefore, 1 2, 2 3, etc.Disjoint sets 6 Explicitly Defined Disjoint Sets Consider simulating a device and tracking the connected components in a circuit This forms an equivalence relation: a b if a and b are connected http://www.morphet.org.uk/ferro/s6mono.htmlDisjoint sets 7 Operations on Disjoint Sets There are two operations we would like to perform on disjoint sets: – Determine if two elements are in the same disjoint set, and – Take the union of two disjoint sets creating a single set We will determine if two objects are in the same disjoint set by defining a function which finds the representative object of one of the disjoint sets – If the representative objects are the same, the objects are in the same disjoint setDisjoint sets 8 Implementation Given two elements a and b, they are in the same set if find( a ) == find( b ) What find returns is irrelevant so long as: – If a and b are in the same set, find( a ) == find( b ) – If a and b are not in the same set, find( a ) = find( b ) We will have find return an integerDisjoint sets 9 Implementation Here is a poor implementation: – Have two arrays and the second array stores the representative object – Finding the representative object isQ(1) – However, taking the union of two sets is Q(n) • It would be necessary to check each array entry Disjoint sets 10 Implementation As an alternate implementation, let each disjoint set be represented by a general tree – The root of the tree is the representative object To take the union of two such sets, we will simply attach one tree to the root of the other Find and union are now both O(h)Disjoint sets 11 Implementation Normally, a node points to its children: We are only interested in the root; therefore, our interest is in storing the parentDisjoint sets 12 Implementation For simplicity, we will assume we are creating disjoint sets the n integers 0, 1, 2, ..., n– 1 We will define an array parent = new sizetn; for ( int i = 0; i n; ++i ) parenti = i; If parenti == i, then i is a root node – Initially, each integer is in its own setDisjoint sets 13 Implementation We will define the function sizet Disjointset::find( sizet i ) const while( parenti = i ) i = parenti; T (n) = O(h) find return i; Disjoint sets 14 Implementation Initially, you will note that find( i ) = find( j ) for i = j, and therefore, we begin with each integer being in its own set We must next look at the union operation – how to join two disjoint sets into a single setDisjoint sets 15 Implementation This function is also easy to define: void setunion( sizet i, sizet j ) i = find( i ); j = find( j ); T (n) = 2T (n) + Q(1) setunion find = O(h) if ( i = j ) // slightly suboptimal... parentj = i; The keyword union is reserved in C++Disjoint sets 16 Example Consider the following disjoint set on the ten decimal digits:Disjoint sets 17 Example If we take the union of the sets containing 1 and 3 setunion(1, 3); we perform a find on both entries and update the second Disjoint sets 18 Example Now, find(1) and find(3) will both return the integer 1Disjoint sets 19 Example Next, take the union of the sets containing 3 and 5, setunion(3, 5); we perform a find on both entries and update the second Disjoint sets 20 Example Now, if we take the union of the sets containing 5 and 7 setunion(5, 7); we update the value stored in find(7) with the value find(5):Disjoint sets 21 Example Taking the union of the sets containing 6 and 8 setunion(6, 8); we update the value stored in find(8) with the value find(6):Disjoint sets 22 Example Taking the union of the sets containing 8 and 9 setunion(8, 9); we update the value stored in find(8) with the value find(9):Disjoint sets 23 Example Taking the union of the sets containing 4 and 8 setunion(4, 8); we update the value stored in find(8) with the value find(4):Disjoint sets 24 Example Finally, if we take the union of the sets containing 5 and 6 setunion(5, 6); we update the entry of find(6) with the value of find(5):Disjoint sets 25 Optimizations To optimize both find and setunion, we must minimize the height of the tree – Therefore, point the root of the shorter tree to the root of the taller tree – The height of the taller will increase if and only if the trees are equal in heightDisjoint sets 26 WorstCase Scenario Let us consider creating the worstcase disjoint set As we are always attaching the tree with less height to the root of the tree with greater height, the worst case must occur when both trees are equal in heightDisjoint sets 27 WorstCase Scenario Thus, building on this, we take the union of two sets with one element – We will keep track of the number of nodes at each depth 1 1Disjoint sets 28 WorstCase Scenario Next, we take the union of two sets, that is, we join two worstcase sets of height 1: 1 2 1Disjoint sets 29 WorstCase Scenario And continue, taking the union of two worstcase trees of height 2: 1 3 3 1Disjoint sets 30 WorstCase Scenario Taking the union of two worstcase trees of height 3: 1 4 6 4 1Disjoint sets 31 WorstCase Scenario And of four: 1 5 10 10 5 1Disjoint sets 32 WorstCase Scenario And finally, take the union of two worstcase trees of height 5: – These are binomial trees 1 6 15 20 15 6 1Disjoint sets 33 WorstCase Scenario From the construction, it should be clear that this would define Pascal’s triangle – The binomial coefficients 1 m 0 or m n  1 n   1  nn  11    m 0mn 1 6    mm1   1 5 1 4 15 n  1 3 10 m nm  1 2 6 20 1 3 10 1 4 15 1 5 1 6 1 1Disjoint sets 34 WorstCase Scenario Thus, suppose we have a worstcase tree of height h – We need the number of nodes and the average depth of a node – Using Maple sum( binomial( h, k ), k = 0..h ); sum( kbinomial( h, k ), k = 0..h ); we get: h h h  h  h1 h kh2   2n     k k   k0 k0 – Therefore, the average depth is h1 h2 h lg(n)  h 2 2 2 – The height and average depth of the worst case are O(ln(n))Disjoint sets 35 BestCase Scenario In the best case, all elements point to the same entry with a resulting height of Q(1):Disjoint sets 36 AverageCase Scenario What is the average case Could it be any better than O(ln(n)) – is there something better To answer this, I created a program which, given the integers from 0 n to 2 – 1 continued to randomly choose numbers until all entries were in a single large set – For each n, I did this multiple times and found the mean (average) heightDisjoint sets 37 AverageCase Scenario The resulting graph shows the average height of a randomly n generated disjoint set data structure with 2 elements 15 2 =32768 This suggests that the average height of such a tree is o(ln(n)) – See reference 1 for a detailed analysisDisjoint sets 38 AverageCase Scenario The actual asymptotic behaviour is O(a(n)) where a(n) is the inverse of the function A(n, n) where A(m, n) is the Ackermann function: n1 if m 0   A(m,n) A(m1,1) if m 0 and n 0   A(m1,A(m,n1)) if m 0 and n 0  The first values are: A(0, 0) = 1, A(1, 1) =3, A(2, 2) = 7, A(3, 3) = 61Disjoint sets 39 AverageCase Scenario A(3, 4) However, A(4, 4) = 2– 3 where A(3,4) is the 19729decimaldigit number A(3, 4) = 200352993040684646497907235156025575044782547556975141926501697371089405955631145308950613088093334810103823434290726318182294938211881266886950636476154702916504187191635158796634721944293092798208430910485599057015931895963952486337236720300291696959215610876494888925409080591145703767520850020667156370236612635974714480711177481588091413574272096719015183628256061809 14588526998261414250301233911082736038437678764490432059603791244909057075603140350761625624760318637931264847037437829549756137 7098160461441330869211810248595915238019533103029216280016056867010565164675056803874152946384224484529253736144253361437372908830379460127472495841486491593064725201515569392262818069165079638106413227530726714399815850881129262890113423778270556742108007006528396332215507783121428855167555407334510721311242739956298271976915005488390522380435704584819795639315785351001899200002414196370681355984046403947219401606951769015611972698233789001764151719005113346630689814021938 34814354263873065395529696913880241581618595611006403621197961018595348027871672001226046424923851113934004643516238675670787452 5946467090388654774348321789701276445552940909202195958575162297333357615955239488529757995402847194352991354376370598692891375715374000198639433246489005254310662966916524341917469138963247656028941519977547770313806478134230959619096065459130089018888758808473362595606544488850144733570605881709016210849971452956834406197969056546981363116205357936979140323632849623304642106613620022017578785185740916205048971178182040018728293994344618622432800983732376493181478984811945 27130074402207656809103762039992034920239066262644919091679854615157788390603977207592793788522412943010174580868622633692847258 5140303961555856433038545068865221311481363840838477826379045960718687672850976347127198889068047824323039471865052566097815072986114143030581692792497140916105941718535227588750447759221830115878070197553572224140001954810200566177358978149953232520858975346354700778669040642901676380816174055040511767009367320280454933902799249186730653993164072049223847481528061916690093380573212081635070763435166986962502096902316285935007187419057916124153689751480826190484794657173660 10058924766554458408383347905441448176842553272073155863493476051374197795251903650321980201087647383686825310251833775339088614 2618480037400808223810407646887847164755294532694766170042446106331123802113458869453220011656407632702307429242605158281107038701834532456763562595143003203743274078087905628366340696503084422585596703927186946115851379338647569974856867007982396060439347885086164926030494506174341236582835214480672667684180708375486221140823657980296120002744132443843240233125740354501935242877643088023285085588608996277445816468085787511580701474376386797695504999164399828435729041537814 34388473034842619033888414940313661398542576355771053355802066221855770600825512888933322264362819848386132395706761914096385338 3237434375883085923372228464428799624560547693242899843265267737837317328806321075321123868060467470842805116648870908477029120816110491255559832236624486855665140268464120969498259056551921618810434122683899628307165486852553691485029953967550395493837185340590009618748947399288043249637316575380367358671017578399481847179849824694806053208199606618343401247609663951977802144119975254670408060849934417825628509272652370989865153946219300460736450792621297591769829389236701 51709920915315678144397912484757062378046000099182933213068805700465914583872080880168874458355579262584651247630871485663135289 3416611749061752667149267217612833084527393646924458289257138887783905630048248379983969202922221548614590237347822268252163995744080172714414617955922617508388902007416992623830028228624928418267124340575142418856999427233160699871298688277182061721445314257494401506613946316919762918150657974552623619122484806389003366907436598922634956411466550306296596019972063620260352191777674066877746354937531889958786628212546979710206574723272137291814466665942187200347450894283091 15351892711142871083761592223802766053278233516615551493693757784666701457179719012271178127804502400263847587883393968179629506 9079881712169068692953824852983002347606845411417813911064856023654975422749723100761513187002405391051091381784372179142252858743209852495787803468370333781842144401713868812424998441861812927119853331538256732187042153063119774853521467095533462633661086466733229240987984925669110951614361860154890974024191350962304361219612816595051866602203071561368473236466086890501426391390651506390819937885231836505989729912540447944342516677429965981184923315155527288327402835268844 24087528112832899806259126736995462473415433335001472314306127503903073971352520693381738433229507010490618675394331307847980156 5513038475815568523621801041965025559618193498631591323303609646190599023611268119602344184336333459492763194610171665291382371718239429921627253846177606569454229787707138319881703696458868981186321097690035573588462446483570629145305275710127887202796536447972402540544813274839179412882642383517194919720979714593688753719872913083173803391101612854741537737771595172808411162759718638492422280237344192546999198367219213128703558530796694271341639103388275431861364349010094 31974090473310144762998617254244233556122374357158259333828049862438924982227807159517627578471094751190334822414120251826887137 2819310425347819612844017647953150505711072297431456991522345164312184865757578652819756484350895838472292353455946452121583165775147129870822590929265563883665112068194383690411625266871004456024370420066370900194118555716047204464369693285006004692814050711906926139399390273553454556747031490388602202463994826050176243196930564066636662609020704888743889890749815286544438186291738290105182086993638266186830391527326458128678280660133750009659336462514609172318031293034787 74212346791184547913111098977946482169225056293999567934838016991574397005375421344858745868560472867510654233418938390991105864 6559511364606105515683854121745980180713316361257307961116834386376766730735458349478978831633012924080083635682593915711313097803051644171668251834657367593419808495894794098329250008638977856349469321247342610306271374507728615692259662857385790553324064184901845132828463270926975383086730840914224765947443997334813081098639941737978965701068702673416196719659159958853783482298827012560584236558953969030647496558414798131099715754204325639577607048510088157829140825077773 85597901291294073094627859445058594122731948127532251523248015034665190482289614066468903051025109162377704484862302294889667113 8055560795662073244937337402783676730020301161522700892184351565212137921574820685935692079021450227713309998772945959695281704458218195608096581170279806266989120506156074232568684227130629500986442185347081040712891764690655083612991669477802382250278966784348919940965736170458678624255400694251669397929262471452494540885842272615375526007190433632919637577750217600519580069384763578958687848953687212289855780682651819270363209948015587445557517531273647142129553649408438 55866152080121150790750685533444892586932838596530132720469706945715469593536585717888948623332924652027358531885333709484554033 3656535698817258252891805663548836374379334841184558016833182767683464629199560551347003914787680864032262961664156066750815371064672310846196424753749055374480531822600271021640098058449752602303564003808347205314994117296573678506642140084269649710324191918212121320693976914392336837470922826773870813223668008692470349158684099115309831541206356612318750430546753698323082796645741762080659317726568584168183796610614496343254411170694170022265781735835125982108076910196105 22292638797450490192543119006205619065774524161919131875339840493439768233102984658933183730158095925228292068208622303325852801 1926649631444131644277300323779227471233069641714994553226103547514563129066885434542686978844774298177749371011761465162418361668025481529633530849084994300676365480610294009469375060984558855804397048591444958444507997849704558355068540874516331646411808312307970438984919050658758642581073842242059119194167418249045270028826398305795005734171148703118714283418449915345670291528010448514517605530697144176136858238410278765932466268997841831962031226242117739147720800488357 83335692045339359532545648970285585897355057512351295365405028420810227852487766035742463666731486802794860524457826736262308529 7826505711462484659591421027812278894144816399497388188462276824485162205181707672216986326570165431691974265123004175732990447353767253684579275436541282655358185804684006936771860502007054724754840080553042495185449526724726134731817474218007857469346544713603697588411802940803961674694628854067917213860122541950381970453841726800639882065632879283958270851091995883944829777564715202613287108952616341770715164289948795356485455355314875497813400996485449863582484769059003 31169613037661279234643231297066284113074270462020320133683503854253603136367635752126047074253112092334028374829494531047274189 6928727557202761527226828337674139342565265328306846999759709775000556088993268502504921288406827413988163154045649035077587168007405568572402175868543905322813377070741583075626962831695568742406052772648585305061135638485196591896864959633556821697543762143077866593473045016482243296489127070989807667662567151726906205881554966638257382927418208227896068448822298339481667098403902428351430681376725346012600726926296946867275079434619043999661897961192875051944235640264430 32717373415912814960561683539881885694840453423114246135599252723300648816274667235237512343118934421188850850793581638489944875 4475633168921386967557430273795378526254232902488104718193903722066689470220425883689584093999845356094886994683385257967516188215941098162491874181336472696512398067756194791255795744647142786862405375057610420426714936608498023827468057598259133100691994190465190653117190892607794911921794640735512963386452303567334558803331319708036545718479155043265489955970586288828686660661802188224860214499997312216413817065348017551043840662441282280361664890425737764095632648282525 84076690456084394903252905263375323165090876813366142423983095308065496618793819491200339194894940651323988166420800883955549422 3709673484007264270570116508907519615537018626479745638118785617545711340047381076276301495330973517418065547911266093803431137853253288353335202493436597912934128485497094682632907583019307266533778255931433111096384805394085928398890779621047984791968687653998747709591278872747587443980677982496827827220092644994455938041460877064194181044075826980568803894965461658798390466058764534181028990719429302177451997610449504319684150345551404482092893337865736305283061999007774 87269229986082790531716918765788609089418170579934048902184415597910926768627965975839524839267348836347456516870161662406424242 4122896111801061568234253939218005248345472377921991122859591419187749179382334001007812832650671028178139602912091472010094787875255126337288422235386949006792766451163475810119387531965724212147603828477477457170457861041738574791130190858387789015233434301300528279703858035981518292960030568261209195094373732545417105638388704752895056396102984364136093564163258940813798151169333861979733982167076100460798009601602482309694304380695662012321365014054958625061528258803302 29083858124784693157203232336018994694376477267218793768264318283826035645206994686302160488745284243635935586223335062359450028 9055858161127534178375045593612613085264082805121387317749020024955273873458595640516083058305377073253397155262044470542957353836111367752316997274029294167420442324811387507563131907827218886405337469421384216992886294047963530515056078812636620649723125757901959887304119562622734372890051656111109411174527796548279047125058199907749806382155937688554649882293898540829132512907647838632249478101675349169348928810420301561028338614382737816094634133538357834076531432141715 06558775478202524547806573013422774706167442419689526131642741046954746214837562882997718041867850845469656191509086958742511844 3583730659095146098045124740941137389992782249298336779601101538709612974970556630163730720275073475992294379239382442742118615823616131788639255309511718842129850830723825972914414225157940388301135908333165185823496722125962181250705811375949552502274727467436988713192667076929919908446716122873885845758462272657333075373557282395161696417519867501268174542932373829414382481437713986190671665757294580780482055951188168718807521297183263644215533678775127476694079011705750 98195750845635652173895441798750745238544552001335720333323798950743939053129182122552598337909094636302021853538488548250628977 1561696386071238277172562131346054940177041358173193176337013633225281912754719144345092071184883836681817426334294961187009150304916533946476371776643912079834749462739782217150209067019030246976215127852195614207080646163137323651785397629209202550028896201297014137964003805573494926907353514596120867479654773369295877362863566014376796403843079686413856344780132826128458918489852804804884418082163942397401436290348166545811445436646003249061876303950235640204453074821024 13668951966442213392007574791286838051751506346625693919377402835120756662608298904918772878338521785227920457718469658552787904 4756219266399200840930207567392536373562839082981757790215320210640961737328359849406665214119818381088451545977289516457213189779790749194101314836854463961690460703010759681893374121757598816512700076126278916951040631585763753478742007022205107089125761236165802680681585849985263146587808661680073326467683020639169720306489440562819540619068524200305346315662189132730906968735318164109451428803660599522024824888671155442910472192913424834643870536850864874909917881267056 56653871910497218200423714927401644609434598453925367061322106165330856620211889682340057526754861014769936887382095845522115719 2347968688816085363161586288015039594941852948922707441082820716930338781808493620401825522227101098565344481720747075601924591559943107294957819787859057894005254012286751714251118435643718405356302418122547326609330271039796809106493927272268303541046763259135527968383770501985523462122285841055711992173171796980433931770775075562705604783177984444763756025463703336924711422081551997369137197516324130274871219986340454824852457011855334267526471597831073124566342980522145 54941562527240289153333543493412178620370072603152798707718724912344944771479095207347613854254853115527733010303424768358654960 9372232400715451812973269208105842409055772564580368146223449318970813889714329983134761779967971245378231070373915147387869211918756670031932128189680332269659445928621060743882741691946516226763254066507088107103039417886056489376981673415902592519461182364294565266937220315550470021359884629275801252771542201662995486313032491231102962792372389976641680349714122652793190763632613681414551637665655983978848938173308266877990196288693229659737995193162118721545528739417024 36698855938887933167445333631195415184040882838151934212341228200309503133410507047601599879854725291906652224793197154403317948 3683737322082188577334162385644138070054191353024594391350255453188645479625226025176292837433046510236105758351455073944333961021622967546141578112719700173861149427950141125328062125477581051297208846526315809480663368767014731073354071771087661593585681409821296773075919738297344144525668877085532457088895832099382343210271822411476373279135756861542125284965790333509315277692550584564401055219264450531207375628774499816364633283581614033017581396735942732769044892036188 03867549557518068900585329272014939235005258451467069826285482578832673987352204572282392902071448222198855871028969919358730742 7781515975762076402395124386020203259659625021257834995771008562638611823381331850901468657706401067627861758377277289589274603940393033727187385053691295712671506689668849388088514294360996201296675907922508227531381284985152690293170026313632894209579757795932763553116206675348865131732387243874806351331451264488996758982881292548007642518658649024111112730135719718138160258317850693224400799865663537154408845486639318170839573578079905973083909488180406093595919090747396 09044101505163217496814121007657191774837673557510007336169223865374290794578032000423374528075661530429290144957806296341383835 5178359976470885134900485697369796523869584599459559209070905895689145114141268450546211794502661175016692826025095077077821195043261738322356243760177679936279609936897519139496503335850715541843645685261667424368892037103749532842592713161053783498074073915863381796765842525803673720646935124865223848134166380806150570482905989069645193644001859712042572300731641000991698752426037736217776343062161674488493081092990100951797454156425120482208671458684925513244426677712786 37282113315362243010918243912433802140462422233491535595168908162884879899882736304453724321742802157557779670216663170479697281 7248339284101564227450727177926939992974030807277039501358154514249404902653610582540937311465310494338248437971860693721444460082679800247122948940576185389220342560830269705287662137737359439422411470707407290272546130735854174569141944648762435768239706570318416846754073346634629367398362000404140071405427763248013274220268539369886978760700959004868465062677136307097982100655728510130660101078063374334477307347865388174268123074376606664331277535646657860371519292276844 04582732832438082128412187761320424604649008010547314267492608269221556374054862417170310279199969426456209556198164545476620450 2241144940474934983220680719135276798674781345820385957041346617793722853494003163159954409368408957253343870298671782977037333280680176463950209002394193149911500910527682111951099906316615031158558283558260717941005252858361136996130344279017381178741206128818206202326384986151565645123004779296756361834576810504334176954306753804111392855379252924134733948105053202570872818630729115891133594201476187266429156403637192760230628384065042544174233546454998705531872688792642 41021473636986254637471597443549434438997300517425251108773578863909468120966734281525859199248576404880550713298142993599114632 3991911395992675257635900744657281019180584180734222773472139772321823177171691640010882611254909336118678057572239101818616854910850088527227437421208652485237245624869766224538481929867112945294551549703058591930719849710541418163696897613112674402700964866754593456705993699546450055892162804797636568613331656390739570327203438917541526750091501119885687270884819553167693168127289214303137681801644547736751835349785792427646335416243360112596025210950161226411034608346564 82355979342740568688492244587454937767521203247038030354911575448312952758919398936808763276854387695576948814228443119985957007 2752139317683783177033913042306095899913731468456901042209516196707050642025673387344611565527617599272715187766001023894476053978951694570880272873622512107622409181006670088347473760515628553394356584375627124124445765166306408593950794755092046393224520253546363444479175566172596218719927918657549085785295001284022903506151493731010700944615101161371242376142672254173205595920278212932572594714641722497732131638184532655527960427054187149623658525245864893325414506264233 78856514646706042985647819684615936632889542997807225422647904006160197519750074605451500602918066382714970161109879513366337713 78434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156733 Thus, A(4, 4) – 3, in binary, is 1 followed by this many zeros.... http://xkcd.com/207/Disjoint sets 40 AverageCase Scenario Therefore, we (as engineers) can, in clear conscience, state that the average runtime is Q(1) as there are no physical circumstances where the average depth could by anything more than 4Disjoint sets 41 Optimizations Another optimization is that, whenever find is called, update the object to point to the root sizet Disjointset::find( sizet n ) if ( parentn == n ) return n; else parentn = find( parentn ); return parentn; The next call to find(n) is Q(1); the cost is O(h) memoryDisjoint sets 42 Lotto 6/49 problem How do you randomly select 6 numbers from 149 without ever selecting the same number twice int array49 = 1, 2, 3, 4, ..., 49; for ( int i = 0; i 6; ++i ) sizet index = mrand48() (49 i); std::cout arrayindex; arrayindex = array49 i 1; Disjoint sets 43 Lotto 6/49 problem Let’s play Lotto 2/20: Pick a random number from 0 to 19, say 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Move the object in the last entry to its 1 2 3 4 5 6 7 20 9 10 11 12 13 14 15 16 17 18 19 20 Now pick a random number from 0 to 18, and so onDisjoint sets 44 Lotto 6/49 problem This is an easy way to randomly permute a list: – The randomly chosen entry is moved to the last position int arrayN; for ( sizet i = 0; i N; ++i ) arrayi = i; for ( sizet rng = N; rng = 2; rng ) // pick an entry from 0 to rng 1 sizet index = mrand48() rng; // swap it and the last entryit's okay if index == rng 1 std::swap( arrayindex, arrayrng 1 ); Disjoint sets 45 Implementation Summary We now have two exceptionally fast operations: both find and union will run in Q(1) time on average, and O(ln(n)) in the worstcase scenarioDisjoint sets 46 Application: Image Processing One common application is in image processing Suppose you are attempting to recognize similar features within an image Within a photograph, the same object may be separated by an obstruction; e.g., a road may be split by – a telephone pole in an image – an overpass on an aerial photographDisjoint sets 47 Application: Image Processing Consider the following image of the author climbing up the Niagara Escarpment at Rattlesnake Point Suppose we have a program which recognizes skin tonesDisjoint sets 48 Application: Image Processing A first algorithm may make an initial pass and recognize five different regions which are recognized as exposed skin – the left arm and hand are separated by a watch Each region would be represented by a separate disjoint setDisjoint sets 49 Application: Image Processing Next, a second algorithm may take sets which are close in proximity and attempt to determine if they are from the same person In this case, the algorithm takes the union of: – the red and yellow regions, and – the dark and light blue regionsDisjoint sets 50 Application: Image Processing Finally, a third algorithm may take more distant sets and, depending on skin tone and other properties, may determine that they come from the same individual In this example, the third pass may, if successful, take the union of the red, blue, and green regionsDisjoint sets 51 Application: Maze Generation Another fun application is in the generation of mazes Impress your (nonengineering) friends – They’ll never guess how easy this is...Disjoint sets 52 Application: Maze Generation Here we have a maze which spans a 500 × 500 grid of squares where: – There is one unique solution – Each point can be reached by one unique path from the start Ref: Lance Hampton http://littlebadwolf.com/mazes/Disjoint sets 53 Application: Maze Generation Zooming in on the maze, you will note that it is rather complex and seemingly random Ref: Lance Hampton http://littlebadwolf.com/mazes/Disjoint sets 54 Application: Maze Generation Finding the solution is a problem for a different lecture – Backtracking algorithms We will look at creating the maze using disjoint sets Ref: Lance Hampton http://littlebadwolf.com/mazes/Disjoint sets 55 Application: Maze Generation What we will do is the following: – Start with the entire grid subdivided into squares – Represent each square as a separate disjoint set – Repeat the following algorithm: • Randomly choose a wall • If that wall connects two disjoint set of cells, then remove the wall and union the two sets – To ensure that you do not randomly remove the same wall twice, we can have an array of unchecked wallsDisjoint sets 56 Application: Maze Generation Let us begin with an entrance, an exit, and a disjoint set of 20 squares and 31 interior wallsDisjoint sets 57 Application: Maze Generation First, we select 6 which joins cells B and G – Both have height 0Disjoint sets 58 Application: Maze Generation Next we select wall 18 which joins regions J and ODisjoint sets 59 Application: Maze Generation Next we select wall 9 which joins the disjoint sets E and J – The disjoint set containing E has height 0, and therefore it is attached to J Disjoint sets 60 Application: Maze Generation Next we select wall 11 which joins the sets identified by B and H – H has height 0 and therefore we attach it to B Disjoint sets 61 Application: Maze Generation Next we select wall 20 which joins disjoint sets L and M – Both are height 0Disjoint sets 62 Application: Maze Generation Next we select wall 17 which joins disjoint sets I and N – Both are height 0Disjoint sets 63 Application: Maze Generation Next we select wall 7 which joins the disjoint set C and the disjoint set identified by B – C has height 0 and thus we attach it to BDisjoint sets 64 Application: Maze Generation Next we select wall 19 which joins the disjoint set K to the disjoint sent identified by L – Because K has height 0, we attach it to LDisjoint sets 65 Application: Maze Generation Next we select wall 23 and join the disjoint set Q with the set identified by L – Again, Q has height 0 so we attach it to LDisjoint sets 66 Application: Maze Generation Next we select wall 12 which joints the disjoint sets identified by B and I – They both have the same height, but B has more nodes, so we add I to the node BDisjoint sets 67 Application: Maze Generation Selecting wall 15 joints the sets identified by B and L – The tree B has height 2 while L has height 1 and therefore we attach L to BDisjoint sets 68 Application: Maze Generation Next we select wall 5 which joins disjoint sets A and F – Both are height 0Disjoint sets 69 Application: Maze Generation Selecting wall 30 also joins two disjoint sets R and SDisjoint sets 70 Application: Maze Generation Selecting wall 4 joints the disjoint set D and the disjoint set identified by J – D has height 0, J has height 1, and thus we add D to JDisjoint sets 71 Application: Maze Generation Next we select wall 10 which joins the sets identified by A and B – A has height 1 while B has height 2, so we attach A to B Disjoint sets 72 Application: Maze Generation Selecting wall 31, we union the sets identified by R and T – T has height 0 so we attach it to IDisjoint sets 73 Application: Maze Generation Selecting wall 27 joins the disjoint sets identified by J and R – They both have height 1, but J has more elements, so we add R to JDisjoint sets 74 Application: Maze Generation Selecting wall 8 joins sets identified by B and J – They both have height 2 so we note that J has fewer nodes than B, so we add J to BDisjoint sets 75 Application: Maze Generation Finally we select wall 23 which joins the disjoint set P and the disjoint set identified by B – P has height 0, so we attach it to BDisjoint sets 76 Application: Maze Generation Thus we have a (rather trivial) maze where: – there is one unique solution, and – you can reach any square by a unique path from the starting pointDisjoint sets 77 Application: Maze Generation You may also note that the average depth is 1.6 whereas the average depth of the worstcase disjoint tree is 2:Disjoint sets 78 Application: Maze Generation For fun, the following C code generates mazes of arbitrary length: char M2,A,Z,E=40,J40,T40;main(C)for(J=A=scanf("d",C); E; J E =T E = E) printf("."); for(;(A=Z=Z) (printf("\n" ) , A = 39 ,C ) ; Z printf (M ))MZ=ZA(E =AJZ)C A == T A 627rand()CZJTE=TA=E,JTA=AZ=A,".":" "; It does not use disjoint sets...Disjoint sets 79 Application: Maze Generation gcc maze.c maze.c: In function ‘main’: maze.c:1: warning: incompatible implicit declaration of builtin function ‘scanf’ maze.c:3: warning: incompatible implicit declaration of builtin function ‘printf’ ./a.out 30 ....................................... .. . . ... . . . . . ..... . . . .. ... .. . . . ....... ... . . .... . . . . . .. .. . . . . . ... ... . ... . . . . .. ... . .. . . ... . . .. . . . . . .. ... ... . . .. .. . . . .. .. ... . . . .. .. . .. .. .. . .. . . . . .. . .. . .. . ... .. . .. .. .. ......... ... .. .... . . . . . ... . ..... . ... . . ... . . .. . .... .. . ... . . .. . .. .. . .. . . . . . .. .... . . . .. . .. .. . ... .. . . .. .. . . . . . . . . . . ... . ..... ...... . . . . . .. . . .. .. . . . .. . . .... .. . . ... . . . . .. . . . .. .. .. .... . ... .. .. . .. . . . .... . .. .. . . .... .... . . .. . .. . . . . .... ... . . ... .. .. . . . . . . .... . .. . . . . ... . .. . . . . . .... . . . . . .. .. .. . .. . . .... . .... .. . ... ... . .. . . . . . .... . . . . . ... . ... . . .. . . . . . .. .. ... . . . . ... . .. .. .. . .... ... .. . . . . .. ... .. . . . ... . . .... .. . .. ........ . . .. ... . . .. ... .. .. . . . .. .... ... .. . . .. ... . ................................Disjoint sets 80 Application: Maze Generation The ECE 250 web site has a Q(mn) algorithm for generating an m× n maze: http://ece.uwaterloo.ca/dwharder/aads/Algorithms/Mazegeneration The actual maze generation code is quite short: Disjointsets rooms( mn ); int numberofwalls = 2mn m n; bool iswallnumberofwalls; Permutation untestedwalls( numberofwalls ); for ( int i = 0; i numberofwalls; ++i ) iswalli = true; while ( rooms.disjointsets() 1 ) int wall = untestedwalls.next(); int room2; findadjacentrooms( room, wall, n ); if ( rooms.find( room0 ) = rooms.find( room1 ) ) iswallwall = false; rooms.setunion( room0, room1 ); Disjoint sets 81 Summary In this topic, we have covered disjoint sets – Equivalence relations and the definition of a disjoint set – An efficient data structure • A general tree – An optimization which results in • Worst case O(ln(n)) height • Average and best cases Q(1) height – A few examples and applicationsDisjoint sets 82 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, Ch.22, pp.440461. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, Ch.8, pp.315337.Disjoint sets 83 References Wikipedia, http://en.wikipedia.org/wiki/Disjointset(datastructure) 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, Ch.22, pp.440 461. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, Ch.8, pp.315 337. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017