package Ġorg . eln 2 . data Ċ Ċ import Ġorg . eln 2 . debug . d println Ċ import Ġjava . lang . StringBuilder Ċ import Ġjava . util . Stack Ċ Ċ /** Ċ Ġ* ĠAn Ġedge Ġin Ġthe Ġ[ Component Graph ], Ġconnecting Ġtwo Ġvertices Ġbid irection ally . Ċ Ġ* Ċ Ġ* ĠNorm ally , Ġthese Ġare Ġconstructed Ġby Ġcalling Ġ[ Component Graph . Mutation Guard . connect ]. ĠA Ġsubclass Ġof ĠComponent Graph Ġcan Ġoverride Ġits Ġinternal Ġ[ Component Graph . connect ] Ġmethod Ġto , Ġe . g ., Ġreturn Ġa Ġsubclass Ġof ĠEdge . Ċ Ġ* Ċ Ġ* ĠThe Ġcurrent Ġimplementation Ġhas Ġno Ġconcept Ġof Ġdirected Ġedges Ġ( as Ġthat Ġwould Ġrequire Ġdis crimin ating Ġbetween Ġstrongly Ġand Ġweak ly Ġconnected Ġcomponents ), Ġbut Ġthe Ġordering Ġis Ġpreserved Ġfor Ġthe Ġlifetime Ġof Ġthis Ġobject . Ċ Ġ*/ Ċ open Ġclass ĠEdge ( val Ġa : ĠVertex , Ġval Ġb : ĠVertex ): ĠIterable < Vertex > Ġ{ Ċ ĉ override Ġfun Ġiterator () Ġ= ĠarrayOf ( a , Ġb ). iterator () Ċ } Ċ Ċ /** Ċ Ġ* ĠA Ġvertex Ġin Ġthe Ġ[ Component Graph ], Ġrepresenting Ġa Ġdiscrete Ġentity Ġthat Ġcan Ġbe Ġconnected Ġ( by Ġ[ Edge ] s ) Ġto Ġother Ġvertices . Ċ Ġ* Ċ Ġ* ĠThese Ġare Ġoften Ġconstructed Ġby Ġcalling Ġ[ Component Graph . Mutation Guard . new Vertex ]. ĠA ĠComponent Graph Ġsubclass Ġcan Ġoverride Ġthe Ġinternal Ġ[ Component Graph . new Vertex ] Ġmethod Ġto , Ġe . g ., Ġreturn Ġa Ġsubclass . Ċ Ġ* Ċ Ġ* ĠWhen Ġconstructed , Ġa Ġvertex Ġis Ġin Ġa Ġsingleton Ġ[ Connected Component ] Ġ( as Ġcreated Ġby Ġ[ Component Graph . construct Component ]). ĠThis Ġ_ does Ġnot Ġchange _ Ġduring ĠComponent Graph Ġmutation Ġuntil Ġthe Ġlast Ġoutstanding Ġ[ Component Graph . Mutation Guard ] Ġis Ġdropped , Ġat Ġwhich Ġpoint Ġthe Ġ[ Connected Component ] s Ġare Ġproperly Ġrealized . ĠSee Ġ[ Component Graph . mutate ] Ġfor Ġdetails . Ċ Ġ*/ Ċ open Ġclass ĠVertex ( val Ġgraph : ĠComponent Graph ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġ[ Connected Component ] Ġto Ġwhich Ġthis Ġvertex Ġbelongs . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġnot Ġup - to - date Ġuntil Ġthe Ġlast Ġ[ Component Graph . Mutation Guard ] Ġis Ġdropped . ĠSee Ġ[ Component Graph . mutate ] Ġfor Ġdetails . ĊĠĠĠĠ Ġ*/ Ċ ĉ var Ġcomponent Ġ= Ġgraph . construct Component ( this ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġ" inc idence Ġmap " Ġof Ġthis Ġvertex , Ġmapping Ġthe Ġdist al Ġvertex Ġto Ġan Ġ[ Edge ] Ġwhich Ġcontains Ġboth Ġvertices . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġincident : ĠMutable Map < Vertex , ĠEdge > Ġ= Ġmutable Map Of () Ċ } Ċ Ċ /** Ċ Ġ* ĠA Ġ( strong ly ) Ġ" connected Ġcomponent " Ġin Ġthe Ġ[ Component Graph ], Ġrepresenting Ġa Ġset Ġof Ġvertices Ġsuch Ġthat Ġthere Ġexists Ġa Ġpath Ġfrom Ġevery Ġvertex Ġin Ġthe Ġset Ġto Ġevery Ġother Ġvertex . Ċ Ġ* Ċ Ġ* ĠThe Ġuser Ġoften Ġdoesn 't Ġconstruct Ġthese ; Ġrather , Ġthe ĠComponent Graph Ġdoes Ġ( in Ġ[ Component Graph . assign Components ]). ĠThe Ġuser Ġcan Ġarrange Ġto Ġsee Ġthem Ġin Ġtheir Ġfully Ġconstructed Ġstate Ġby Ġadding Ġa Ġ[ Component Listener ] Ġand Ġob serving Ġits Ġ[ Component Listener . component Real ized ] Ġevents . Ċ Ġ*/ Ċ open Ġclass ĠConnected Component ( initial Vertex : ĠVertex ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġ( vertices )[ Vertex ] Ġwithin Ġthis Ġconnected Ġcomponent . ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġvertices : ĠMutable Set < Vertex > Ġ= Ġmutable Set Of ( initial Vertex ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġa Ġvertex Ġto Ġthis Ġcomponent . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġusually Ġonly Ġcalled Ġfrom Ġ[ Component Graph . assign Components ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġadd ( v : ĠVertex ) Ġ= Ġvertices . add ( v ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemove Ġa Ġvertex Ġfrom Ġthis Ġcomponent . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġshould Ġonly Ġbe Ġcalled Ġfrom Ġ[ Component Graph . assign Components ], Ġbut Ġthe Ġcurrent Ġnon - incremental Ġalgorithm Ġdoesn 't Ġyet Ġdo Ġthis . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġremove ( v : ĠVertex ) Ġ= Ġvertices . remove ( v ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemove Ġall Ġvertices Ġfrom Ġthis Ġcomponent . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġnormally Ġdone Ġonly Ġfrom Ġ[ Component Graph . assign Components ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġclear () Ġ= Ġvertices . clear () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠWhether Ġor Ġnot Ġthis Ġcomponent Ġhas Ġbeen Ġ" real ized " -- w hether Ġlisteners Ġ(" user Ġcode ") Ġhave Ġseen Ġthis Ġcomponent Ġin Ġits Ġconstructed Ġstate . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠSome Ġconnected Ġcomponents Ġare Ġtransient ly Ġconstructed , Ġsuch Ġas Ġthe Ġdefault Ġsingleton Ġbelong ing Ġto Ġevery Ġ[ Vertex ] Ġon Ġconstruction Ġ( see Ġ[ Vertex . component ]' s Ġdocumentation ). ĠSince Ġthis Ġis Ġnot Ġlikely Ġto Ġbe Ġvalid , Ġand Ġit Ġis Ġnot Ġefficient Ġto Ġcompute Ġthese Ġonline , Ġthe Ġ[ Component Graph ] Ġwaits Ġuntil Ġall Ġoutstanding Ġmutations Ġare Ġdone Ġto Ġ" real ize " Ġthe Ġ[ Connected Component ] s , Ġsetting Ġthis Ġfield Ġin Ġthe Ġprocess . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠConnected Ġcomponents Ġwhich Ġaren 't Ġrealized Ġhave Ġnot Ġbeen Ġw it nes sed Ġby Ġuser Ġcode , Ġand Ġcan Ġsafely Ġbe Ġdropped Ġwithout Ġbeing Ġun real ized . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠMod ification Ġof Ġa Ġrealized Ġcomponent Ġrequires Ġtwo Ġmore Ġcalls Ġinto Ġuser Ġcode , Ġbefore Ġand Ġafter Ġmodification Ġ([ Component Listener . real ized Component Modification Started ] Ġand Ġ[ Component Listener . real ized Component Modification Finished ]), Ġto Ġallow Ġusers Ġto Ġsynchronize Ġstate . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġvar Ġrealized Ġ= Ġfalse ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAn Ġinternal Ġcallback Ġfor Ġwhen Ġthis Ġconnected Ġcomponent Ġis Ġ[ real ized ], Ġto Ġbe Ġoverridden Ġin Ġsubclasses . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġinternal Ġopen Ġfun Ġrealize () Ġ{} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAn Ġinternal Ġcallback Ġfor Ġwhen Ġthis Ġcomponent Ġis Ġun [ real ized ], Ġto Ġbe Ġover rid en Ġin Ġsubclasses . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġun real ize () Ġ{} Ċ } Ċ Ċ /** Ċ Ġ* ĠAn Ġinterface Ġto Ġbe Ġimplemented Ġby Ġusers Ġinterested Ġin Ġevents Ġabout Ġ[ Connected Component ] s . Ċ Ġ*/ Ċ interface ĠComponent Listener Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġ[ Connected Component ] Ġis Ġrealized -- construct ed Ġand Ġwith Ġa Ġfinal Ġset Ġof Ġvertices . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠSee Ġ[ Connected Component . real ized ] Ġfor Ġmore Ġdetails . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġcomponent Real ized ( c : ĠConnected Component ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġ[ Connected Component ] Ġis Ġun real ized -- it Ġwill Ġno Ġlonger Ġbe Ġheld Ġby Ġthe Ġ[ Component Graph ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġcomponent Un real ized ( c : ĠConnected Component ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġrealized Ġ[ Connected Component ] Ġis Ġabout Ġto Ġbe Ġmodified . ĠThis Ġis Ġcalled Ġbefore Ġthe Ġset Ġof Ġvertices Ġchanges . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġrealized Component Modification Started ( c : ĠConnected Component ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġrealized Ġ[ Connected Component ] Ġhas Ġbeen Ġmodified . ĠThis Ġis Ġcalled Ġonce Ġthe Ġset Ġof Ġvertices Ġis Ġup - to - date Ġagain . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġrealized Component Modification Finished ( c : ĠConnected Component ) Ċ } Ċ Ċ /** Ċ Ġ* ĠAn Ġinterface Ġto Ġbe Ġimplemented Ġby Ġusers Ġinterested Ġin Ġevents Ġabout Ġ( vertices )[ Vertex ]. Ċ Ġ*/ Ċ interface ĠVertex Listener Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġ[ Vertex ] Ġis Ġadded Ġto Ġthe Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠIts Ġ[ Vertex . component ] Ġis Ġnot Ġyet Ġvalid -- wait Ġuntil Ġcomponents Ġare Ġrealized Ġ( via Ġ[ Component Listener . component Real ized ]) Ġfor Ġthat . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġvertex Added ( v : ĠVertex ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġa Ġ[ Vertex ] Ġis Ġremoved Ġfrom Ġthe Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠIts Ġ[ Vertex . component ] Ġmay Ġnot Ġbe Ġrepresentative Ġof Ġthe Ġactual Ġstate Ġof Ġthe Ġgraph Ġ( if Ġconnectivity Ġchanged Ġbefore Ġthis Ġremoval ), Ġbut Ġit Ġwill Ġdefinitely Ġbe Ġthe Ġsame Ġ[ Connected Component ] Ġit Ġwas Ġin Ġduring Ġthe Ġlast Ġreal ization . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġvertex Removed ( v : ĠVertex ) Ċ } Ċ Ċ /** Ċ Ġ* ĠAn Ġinterface Ġto Ġbe Ġimplemented Ġby Ġusers Ġinterested Ġin Ġevents Ġabout Ġ[ Edge ] s . Ċ Ġ*/ Ċ interface ĠEdge Listener Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġan Ġ[ Edge ] Ġis Ġadded Ġto Ġthe Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġlikely Ġchanged Ġconnectivity , Ġbut Ġthis Ġisn 't Ġyet Ġreflected Ġin Ġthe Ġ[ Connected Component ] s -- wait Ġfor Ġ[ Component Listener . real ized Component Modification Finished ] Ġfor Ġthat . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġedge Added ( e : ĠEdge ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalled Ġwhen Ġan Ġ[ Edge ] Ġis Ġremoved Ġfrom Ġthe Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmay Ġhave Ġchanged Ġconnectivity , Ġbut Ġthis Ġisn 't Ġyet Ġreflected Ġin Ġthe Ġ[ Connected Component ] s -- wait Ġfor Ġ[ Component Listener . real ized Component Modification Finished ] Ġfor Ġthat . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġedge Removed ( e : ĠEdge ) Ċ } Ċ Ċ /** Ċ Ġ* ĠThe ĠComponent ĠGraph , Ġthe Ġcore Ġabstraction Ġof Ġan Ġund irect ed Ġgraph Ġthat Ġkeeps Ġtrack Ġof Ġconnected Ġcomponents . Ċ Ġ* Ċ Ġ* ĠThe Ġvertices Ġand Ġedges Ġconsist Ġof Ġ[ Vertex ] Ġand Ġ[ Edge ] Ġinstances . ĠThe Ġoutput Ġof Ġthe Ġalgorithm Ġdetermining Ġthe Ġconnected Ġcomponents Ġresults Ġin Ġa Ġset Ġof Ġ[ Connected Component ] s . Ċ Ġ* Ċ Ġ* ĠMost Ġof Ġthese Ġdata Ġhave Ġreferences Ġto Ġ( or Ġcontainers Ġof Ġreferences Ġto ) Ġeach Ġother , Ġfor Ġease Ġof Ġuse , Ġbut Ġthis Ġdoes Ġmean Ġthat Ġcare less Ġuser Ġcode Ġcan Ġw itness Ġin variants Ġbe Ġbroken . ĠThis Ġis Ġespecially Ġthe Ġcase Ġbecause Ġthe Ġalgorithm Ġto Ġdetermine Ġthe Ġcomponents Ġis ĠO (( V + E ) Ġ* ĠL ) Ġ( for ĠV Ġvertices Ġand ĠE Ġedges ), Ġwith ĠL Ġthe Ġlookup Ġcost Ġfor Ġthe Ġsets Ġ( present ly Ġam ort ized Ġconstant ). ĠTo Ġavoid Ġboth Ġperformance Ġpen alt ies Ġand Ġthe Ġobservation Ġof Ġvariants , Ġmethods Ġfor Ġchanging Ġthe Ġgraph Ġare Ġinternal Ġ( and Ġcan Ġonly Ġbe Ġaccessed Ġpublicly Ġfrom Ġa Ġ[ Mutation Guard ]), Ġand Ġthe ĠComponent Graph Ġ" real izes " Ġ[ Connected Component ] s Ġonly Ġonce Ġa Ġ[ Mutation Guard ] Ġis Ġdropped Ġ( one Ġis Ġnormally Ġconstructed Ġand Ġscoped Ġvia Ġ[ mutate ]). ĠSee Ġ[ mutate ] Ġfor Ġmore Ġdetails . Ċ Ġ* Ċ Ġ* ĠThe ĠComponent Graph Ġcan Ġhave Ġany Ġnumber Ġof Ġ" listeners " -- user Ġobjects Ġimplementing Ġ[ Component Listener ], Ġ[ Vertex Listener ], Ġand Ġ[ Edge Listener ]. ĠOf Ġthe Ġthree , Ġthe Ġ[ Component Listener ] Ġis Ġpo ised Ġespecially Ġto Ġbe Ġused Ġfor Ġcollecting Ġthe Ġoutput Ġof Ġthe Ġconnected Ġcomponent Ġalgorithm , Ġbut Ġthe Ġother Ġtwo Ġare Ġuseful Ġfor Ġmiddleware Ġadapters . Ċ Ġ* Ċ Ġ* Ġ[ Component Graph ] Ġcan Ġbe Ġused Ġas - is , Ġand Ġwith Ġthe Ġdefault Ġ[ Vertex ], Ġ[ Edge ], Ġand Ġ[ Component Graph ] Ġclasses , Ġbut Ġit Ġ( and Ġall Ġof Ġthese ) Ġcan Ġalso Ġbe Ġsub cl assed . ĠThis Ġclass Ġcontains Ġconstruction Ġutility Ġmethods Ġ([ construct Vertex ], Ġ[ construct Edge ], Ġand Ġ[ construct Component ] Ġrespectively ) Ġthat Ġallows Ġsubclasses Ġto Ġsimply Ġoverride Ġthe Ġconstruction Ġprocess . Ċ Ġ*/ Ċ open Ġclass ĠComponent Graph Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġset Ġof Ġ( vertices )[ Vertex ] Ġwhich Ġare Ġconsidered Ġto Ġbe Ġin Ġthis Ġgraph . ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġvertices : ĠMutable Set < Vertex > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġset Ġof Ġ[ Edge ] s Ġconsidered Ġto Ġbe Ġin Ġthis Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠAs Ġan Ġinvariant , Ġthis Ġis Ġalways Ġthe Ġunion Ġof Ġall Ġ" incident Ġedges " Ġfrom Ġevery Ġvertex 's Ġ[ Vertex . incident ] Ġvalue Ġsets . ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġedges : ĠMutable Set < Edge > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġset Ġof Ġ[ Connected Component ] s Ġin Ġthis Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġonly Ġguaranteed Ġto Ġbe Ġvalid Ġand Ġup - to - date Ġwhen Ġthe Ġgraph Ġhas Ġno Ġoutstanding Ġ[ Mutation Guard ] s Ġ( when Ġ[ is Immutable ] Ġis Ġtrue ). ĊĠĠĠĠ Ġ*/ Ċ ĉ var Ġcomponents : ĠMutable Set < Connected Component > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġset Ġof Ġlisteners Ġfor Ġthis Ġgraph Ġimplementing Ġ[ Component Listener ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġcomponent Listeners : ĠMutable Set < Component Listener > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġset Ġof Ġlisteners Ġfor Ġthis Ġgraph Ġimplementing Ġ[ Vertex Listener ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġvertex Listeners : ĠMutable Set < Vertex Listener > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġset Ġof Ġlisteners Ġfor Ġthis Ġgraph Ġimplementing Ġ[ Edge Listener ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ val Ġedge Listeners : ĠMutable Set < Edge Listener > Ġ= Ġmutable Set Of () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġa Ġlistener Ġto Ġthis Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThe Ġlistener Ġ_ should _ Ġimplement Ġone Ġof Ġthe Ġ[ Component Listener ], Ġ[ Vertex Listener ], Ġor Ġ[ Edge Listener ] Ġinterfaces Ġ( this Ġis Ġa Ġno - op Ġif Ġit Ġdoesn 't ). ĠIt Ġwill Ġreceive Ġthe Ġproper Ġevents Ġfrom Ġnow Ġon , Ġbut Ġdo Ġnote Ġthat Ġmost Ġevent Ġinterfaces Ġconcern Ġ_ changes _ Ġin Ġstate , Ġso Ġany Ġobjects Ġlooking Ġto Ġ_ track _ Ġstate Ġwill Ġhave Ġto Ġinspect Ġthe Ġ_ current _ Ġstate Ġof Ġthe Ġgraph Ġ( which Ġis Ġonly Ġsafe Ġto Ġdo Ġoutside Ġof Ġmutation -- when Ġ[ is Immutable ] Ġis Ġtrue ). ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġadd Listener ( listener : ĠAny ) Ġ{ Ċĉ ĉ if ( listener Ġis ĠComponent Listener ) Ġcomponent Listeners . add ( listener ) Ċĉ ĉ if ( listener Ġis ĠVertex Listener ) Ġvertex Listeners . add ( listener ) Ċĉ ĉ if ( listener Ġis ĠEdge Listener ) Ġedge Listeners . add ( listener ) Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemove Ġa Ġlistener Ġfrom Ġthis Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠIf Ġthe Ġlistener Ġwas Ġadded Ġvia Ġ[ addListener ], Ġit Ġwill Ġbe Ġremoved . ĠIf Ġit Ġwas Ġalready Ġremoved , Ġor Ġnever Ġadded , Ġthis Ġis Ġa Ġno - op , Ġbut Ġotherwise Ġsafe . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġremove Listener ( listener : ĠAny ) Ġ{ Ċĉ ĉ component Listeners . remove ( listener ) Ċĉ ĉ vertex Listeners . remove ( listener ) Ċĉ ĉ edge Listeners . remove ( listener ) Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġ[ Connected Component ] Ġ( or Ġa Ġsubclass ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġintended Ġto Ġbe Ġoverridden Ġto Ġproduce Ġa Ġmore Ġspecific Ġsubclass Ġin Ġa Ġ[ Component Graph ] Ġsubclass . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġconstruct Component ( v : ĠVertex ) Ġ= ĠConnected Component ( v ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġ[ Vertex ] Ġ( or Ġa Ġsubclass ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġintended Ġto Ġbe Ġoverridden Ġto Ġproduce Ġa Ġmore Ġspecific Ġsubclass Ġin Ġa Ġ[ Component Graph ] Ġsubclass . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġopen Ġfun Ġconstruct Vertex () Ġ= ĠVertex ( this ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġan Ġ[ Edge ] Ġ( or Ġa Ġsubclass ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġintended Ġto Ġbe Ġoverridden Ġto Ġproduce Ġa Ġmore Ġspecific Ġsubclass Ġin Ġa Ġ[ Component Graph ] Ġsubclass . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThe Ġordering Ġof Ġarguments Ġis Ġpreserved Ġto Ġthe Ġ[ Edge ] Ġconstructor , Ġwhich Ġmight Ġbe Ġof Ġuse Ġfor Ġ" pseudo - oriented " Ġedges . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġinternal Ġopen Ġfun Ġconstruct Edge ( a : ĠVertex , Ġb : ĠVertex ) Ġ= ĠEdge ( a , Ġb ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġa Ġnew Ġvertex , Ġinternally . ĠThis Ġis Ġintended Ġto Ġbe Ġused Ġby Ġthe Ġ[ Mutation Guard ] Ġvia Ġ[ mutate ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġfun Ġnew Vertex () Ġ= Ġconstruct Vertex (). apply Ġ{ Ċĉ ĉ vertices . add ( this ) Ċĉ ĉ components . add ( component ) Ċĉ ĉ vertex Listeners . forEach Ġ{ Ġit . vertex Added ( this ) Ġ} Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemove Ġa Ġvertex , Ġinternally . ĠThis Ġis Ġintended Ġto Ġbe Ġused Ġby Ġthe Ġ[ Mutation Guard ] Ġvia Ġ[ mutate ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThe Ġ[ Component Graph ] Ġimplementation Ġis Ġsafely Ġide mpot ent , Ġbut Ġthis Ġinvokes Ġ[ Vertex Listener ] s , Ġwhich Ġmay Ġor Ġmay Ġnot Ġbe Ġsafely Ġide mpot ent . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġfun Ġremove Vertex ( v : ĠVertex ) Ġ{ Ċĉ ĉ vertex Listeners . forEach Ġ{ Ġit . vertex Removed ( v ) Ġ} Ċĉ ĉ disconnect ( v ) Ċĉ ĉ vertices . remove ( v ) Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConnect Ġtwo Ġ( vertices )[ Vertex ], Ġinternally , Ġreturning Ġan Ġ[ Edge ] Ġ( or Ġa Ġsubclass ). ĠThis Ġis Ġintended Ġto Ġbe Ġused Ġby Ġthe Ġ[ Mutation Guard ] Ġvia Ġ[ mutate ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThe Ġordering Ġof Ġarguments Ġis Ġpreserved Ġto Ġthe Ġ[ Edge ] Ġconstructor , Ġwhich Ġmight Ġbe Ġof Ġuse Ġfor Ġ" pseudo - oriented " Ġedges . ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġfun Ġconnect ( a : ĠVertex , Ġb : ĠVertex ): ĠEdge Ġ{ Ċĉ ĉ assert ( a . graph Ġ== Ġthis ) Ġ{ Ġ" CG . c : Ġvertex Ġa =$ a Ġnot Ġin Ġgraph Ġ$ this " Ġ} Ċĉ ĉ assert ( b . graph Ġ== Ġthis ) Ġ{ Ġ" CG . c : Ġvertex Ġb =$ b Ġnot Ġin Ġgraph Ġ$ this " Ġ} ĊĉĉĊĉ ĉ val Ġedge Ġ= Ġconstruct Edge ( a , Ġb ) Ċĉ ĉ edges . add ( edge ) Ċĉ ĉ a . incident [ b ] Ġ= Ġedge Ċĉ ĉ b . incident [ a ] Ġ= Ġedge ĊĊĉ ĉ edge Listeners . forEach Ġ{ Ġit . edge Added ( edge ) Ġ} ĊĉĉĊĉ ĉ return Ġedge Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDis connect Ġtwo Ġ( vertices )[ Vertex ], Ġinternally , Ġreturning Ġwhether Ġor Ġnot Ġany Ġchange Ġoccurred . ĠThis Ġis Ġintended Ġto Ġbe Ġused Ġby Ġthe Ġ[ Mutation Guard ] Ġvia Ġ[ mutate ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġfun Ġdisconnect ( a : ĠVertex , Ġb : ĠVertex ): ĠBoolean Ġ{ Ċĉ ĉ assert ( a . graph Ġ== Ġthis ) Ġ{ Ġ" CG . d : Ġvertex Ġa =$ a Ġnot Ġin Ġgraph Ġ$ this " Ġ} Ċĉ ĉ assert ( b . graph Ġ== Ġthis ) Ġ{ Ġ" Cg . d : Ġvertex Ġb =$ a Ġnot Ġin Ġgraph Ġ$ this " Ġ} ĊĉĉĊĉ ĉ val Ġedge Ġ= Ġa . incident [ b ] Ċĉ ĉ return Ġif ( edge Ġ!= Ġnull ) Ġ{ Ċĉĉ ĉ edge Listeners . forEach Ġ{ Ġit . edge Removed ( edge ) Ġ} ĊĉĉĉĊĉĉ ĉ a . incident . remove ( b ) Ċĉĉ ĉ b . incident . remove ( a ) Ċĉĉ ĉ edges . remove ( edge ) ĊĊĉĉ ĉ true Ċĉ ĉ } Ġelse Ġ{ Ċĉĉ ĉ false Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDis connect Ġa Ġ[ Vertex ] Ġfrom Ġall Ġincident Ġedges . ĠThis Ġis Ġintended Ġto Ġbe Ġused Ġby Ġthe Ġ[ Mutation Guard ] Ġvia Ġ[ mutate ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ internal Ġfun Ġdisconnect ( v : ĠVertex ) Ġ{ Ċĉ ĉ v . incident . keys . forEach Ġ{ Ċĉĉ ĉ disconnect ( v , Ġit ) Ċĉ ĉ } Ċĉ ĉ assert ( v . incident . isEmpty ()) Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġ" visit ation Ġqueue Ġentry " -- a Ġmember Ġof Ġthe Ġ" visit ation Ġstack " Ġused Ġby Ġ[ visit Depth First ]. ĠNot Ġintended Ġfor Ġpublic Ġuse . ĊĠĠĠĠ Ġ*/ Ċ ĉ protected Ġclass ĠVis itation ( val Ġvertex : ĠVertex , Ġval Ġphase : ĠPhase , Ġval Ġroot : ĠBoolean Ġ= Ġfalse ) Ġ{ Ċĉ ĉ enum Ġclass ĠPhase Ġ{ Ċĉĉ ĉ Down , ĠUp Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠVisit Ġthe Ġgraph Ġusing Ġa Ġdepth - first Ġsearch . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠStarting Ġfrom Ġthe Ġgiven Ġ[ start ] Ġ[ Vertex ], Ġthis Ġis Ġguaranteed Ġto Ġevaluate Ġboth Ġ[ down Phase ] Ġand Ġ[ up Phase ] Ġfor Ġ_ all _ Ġ[ vertices ] Ġin Ġthe Ġgraph . ĠOther Ġthan Ġ[ start ], Ġthese Ġother Ġ" roots " Ġare Ġchosen Ġar bitr arily . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ[ down Phase ] Ġis Ġcalled Ġwith Ġthe Ġfollowing Ġarguments , Ġin Ġorder : ĊĠĠĠĠ Ġ* ĠĊĠĠĠĠ Ġ* Ġ- Ġ` visited ` Ġ([ Vertex ]) Ġis Ġthe Ġ[ Vertex ] Ġbeing Ġvisited ; ĊĠĠĠĠ Ġ* Ġ- Ġ` depth ` Ġ( Int ) Ġis Ġthe Ġdepth Ġof Ġthis Ġvisit ation -- how Ġfar Ġthis Ġvisit Ġis Ġfrom Ġthe Ġroot Ġ( not Ġguaranteed Ġto Ġbe Ġthe Ġshortest Ġpath , Ġhowever ); ĊĠĠĠĠ Ġ* Ġ- Ġ` is Root ` Ġ( Boolean ) Ġis Ġwhether Ġor Ġnot Ġthis Ġ[ Vertex ] Ġwas Ġvisited Ġsp ont aneous ly -- not Ġbecause Ġit Ġwas Ġconnected Ġto Ġany Ġother Ġroot Ġ( e quivalent ly , Ġwhen Ġ` depth ` Ġis Ġ 0 ); ĊĠĠĠĠ Ġ* Ġ- Ġ` neighbors ` Ġ( Mutable Set <[ Vertex ] >) Ġis Ġthe Ġ_ mutable _ Ġset Ġof Ġincident Ġof Ġthe Ġcurrent Ġ` visited ` Ġ[ Vertex ] Ġ( user Ġcode Ġcan Ġchange Ġthis Ġset Ġto Ġcontrol Ġwhich Ġvertices Ġare Ġvisited ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ[ up Phase ] Ġis Ġcalled Ġwith Ġthe Ġfollowing Ġarguments , Ġin Ġorder : ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ- Ġ` visited ` Ġ([ Vertex ]) Ġis Ġthe Ġ[ Vertex ] Ġbeing Ġvisited ; ĊĠĠĠĠ Ġ* Ġ- Ġ` depth ` Ġ( Int ) Ġis Ġthe Ġdepth Ġof Ġthis Ġvisit ation , Ġas Ġabove . ĊĠĠĠĠ Ġ* ĠĊĠĠĠĠ Ġ* ĠThe Ġmost Ġimportant Ġuser Ġof Ġthis Ġis Ġ[ assign Components ]. ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġvisit Depth First ( Ċĉ ĉ down Phase : Ġ( visited : ĠVertex , Ġdepth : ĠInt , Ġis Root : ĠBoolean , Ġneighbors : ĠMutable Set < Vertex >) Ġ-> ĠUnit , Ċĉ ĉ up Phase : Ġ( visited : ĠVertex , Ġdepth : ĠInt ) Ġ-> ĠUnit , Ċĉ ĉ start : ĠVertex ? Ġ= Ġnull Ċ ĉ ) Ġ{ Ċĉ ĉ val Ġun visited Ġ= Ġvertices . to Mutable Set () Ġ Ġ// ĠXXX ĠR ely ing Ġon Ġthe Ġimplementation Ġdetail Ġof Ġa Ġcopy Ġhere ... Ċĉ ĉ var Ġdepth Ġ= Ġ 0 Ċĉ ĉ val Ġstack Ġ= ĠStack < Vis itation >() ĊĊĉ ĉ while ( un visited . isNotEmpty ()) Ġ{ Ċĉĉ ĉ if ( stack . isEmpty ()) Ġ{ Ċĉĉĉ ĉ d println (" adding Ġa Ġnew Ġroot ") Ċĉĉĉ ĉ stack . push ( Vis itation ( start Ġ?: Ġun visited . first (), ĠVis itation . Phase . Down , Ġtrue )) Ċĉĉ ĉ } ĊĊĉĉ ĉ val Ġvisit ation Ġ= Ġstack . pop () Ċĉĉ ĉ val Ġvertex Ġ= Ġvisit ation . vertex Ċĉĉ ĉ d println (" visit ing Ġ$ vertex Ġphase Ġ${ visit ation . phase } Ġroot Ġ${ visit ation . root }") ĊĊĉĉ ĉ when ( visit ation . phase ) Ġ{ Ċĉĉĉ ĉ Vis itation . Phase . Down Ġ-> Ġ{ Ċĉĉĉĉ ĉ un visited . remove ( vertex ) Ċĉĉĉĉ ĉ stack . push ( Vis itation ( vertex , ĠVis itation . Phase . Up )) ĊĊĉĉĉĉ ĉ val Ġneighbors Ġ= Ġvertex . incident . keys Ċĉĉĉĉ ĉ d println (" pre - down Ġneighbors : Ġ$ neighbors ") Ċĉĉĉĉ ĉ down Phase ( vertex , Ġdepth , Ġvisit ation . root , Ġneighbors ) Ċĉĉĉĉ ĉ d println (" post - down Ġneighbors : Ġ$ neighbors ") Ċĉĉĉĉ ĉ neighbors . forEach Ġ{ Ġif Ġ( it Ġin Ġun visited ) Ġstack . push ( Vis itation ( it , ĠVis itation . Phase . Down )) Ġ} Ċĉĉĉĉ ĉ depth ++ Ċĉĉĉ ĉ } Ċĉĉĉ ĉ Vis itation . Phase . Up Ġ-> Ġ{ Ċĉĉĉĉ ĉ depth -- Ċĉĉĉĉ ĉ up Phase ( vertex , Ġdepth ) Ċĉĉĉ ĉ } Ċĉĉ ĉ } Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAssign s Ġthe Ġ[ Connected Component ] s Ġof Ġthis Ġgraph . ĠWhen Ġthis Ġfinished Ġexecution , Ġthe Ġgraph 's Ġ[ components ] Ġare Ġup - to - date , Ġand Ġall Ġlisteners Ġ( espec ially Ġ[ Component Listener ]) Ġare Ġin formed . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġis Ġnormally Ġthe Ġlast Ġstep Ġcalled Ġafter Ġ[ mutate ] Ġbefore Ġ[ is Immutable ] Ġis Ġtrue . ĠSee Ġ[ mutate ] Ġfor Ġdetails . ĊĠĠĠĠ Ġ*/ Ċ ĉ // ĠFIXME : ĠThere Ġare Ġseveral Ġoptimizations Ġwhich Ġcan Ġbe Ġapplied Ġhere : Ċ ĉ // Ġ- ĠFind Ġb rid ges Ġ( non - bridge Ġedges Ġcan Ġbe Ġremoved Ġwithout Ġissue ) Ċ ĉ // Ġ- ĠMin imize Ġcomponent Ġchange over Ġ( don 't Ġjust Ġchoose Ġone Ġand Ġclear Ġit ) Ċ ĉ internal Ġfun Ġassign Components ( start : ĠVertex ? Ġ= Ġnull ) Ġ{ Ċĉ ĉ var Ġcurrent Component : ĠConnected Component ? Ġ= Ġnull Ċĉ ĉ val Ġnew Components : ĠMutable Set < Connected Component > Ġ= Ġmutable Set Of () ĊĠĠĠĠĠĠĠ Ġval Ġmodified Components : ĠMutable Set < Connected Component > Ġ= Ġmutable Set Of () ĊĊĉ ĉ visit Depth First ({ Ċĉĉ ĉ vertex , Ġ_, Ġis Root , Ġ_ Ġ-> Ċĉĉ ĉ d println (" visit ing Ġ$ vertex Ġroot =$ is Root ") Ċĉĉ ĉ if ( is Root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( vertex . component Ġin Ġnew Components ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd println (" for cing Ġnew Ġcomponent Ġonto Ġ$ vertex ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠDon 't Ġallow Ġa Ġvertex Ġto , Ġby Ġidentity , Ġshare Ġa Ġcomponent Ġalready Ġregistered Ġif Ġit Ġis Ġa Ġroot ; Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstate Ġmeans Ġthis Ġparticular Ġvertex Ġwas Ġformer ly Ġconnected , Ġbut Ġnow Ġis Ġnot . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvertex . component Ġ= Ġconstruct Component ( vertex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ċĉĉĉ ĉ current Component Ġ= Ġvertex . component ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd println (" current Ġcomponent Ġis Ġ$ current Component Ġrealized =${ current Component !!. real ized }") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( current Component !!. real ized ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd println (" component Ġ$ current Component Ġalready Ġrealized ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcomponent Listeners . forEach Ġ{ Ġlistener Ġ-> Ġlistener . real ized Component Modification Started ( current Component !! )} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmodified Components . add ( current Component !! ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ċĉĉĉ ĉ new Components . add ( current Component !! ) Ċĉĉĉ ĉ current Component !!. clear () Ċĉĉĉ ĉ current Component !!. add ( vertex ) Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ vertex . component Ġ= Ġcurrent Component !! Ċĉĉĉ ĉ current Component !!. add ( vertex ) Ċĉĉ ĉ } Ċĉ ĉ }, Ġ{ _, Ġ_ Ġ-> ĠUnit }, Ġstart ) ĊĊĉ ĉ d println (" old Ġcomponents Ġ$ components , Ġnew Ġcomponents Ġ$ new Components ") ĊĊĉ ĉ // ĠProcess Ġremoved Ġcomponents Ġwhich Ġwere Ġrealized Ċĉ ĉ ( components Ġ- Ġnew Components ). forEach Ġ{ Ċĉĉ ĉ if ( it . real ized ) Ġ{ Ċĉĉĉ ĉ component Listeners . forEach Ġ{ Ġlistener Ġ-> Ġlistener . component Un real ized ( it ) Ġ} Ċĉĉĉ ĉ it . un real ize () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . real ized Ġ= Ġfalse Ċĉĉ ĉ } Ċĉ ĉ } ĊĊĉ ĉ components Ġ= Ġnew Components ĊĉĉĊĉ ĉ // ĠReal ize Ġany Ġadded Ġcomponents ĊĠĠĠĠĠĠĠ Ġ( components Ġ- Ġmodified Components ). forEach Ġ{ Ċĉĉ ĉ if (! it . real ized ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . real ized Ġ= Ġtrue Ċĉĉĉ ĉ it . real ize () Ċĉĉĉ ĉ component Listeners . forEach Ġ{ Ġlistener Ġ-> Ġlistener . component Real ized ( it ) Ġ} Ċĉĉ ĉ } Ċĉ ĉ } ĊĊĠĠĠĠĠĠĠ Ġmodified Components . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomponent Listeners . forEach Ġ{ Ġlistener Ġ-> Ġlistener . real ized Component Modification Finished ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġnumber Ġof Ġoutstanding Ġ[ Mutation Guard ] s . ĊĠĠĠĠ Ġ* ĠĊĠĠĠĠ Ġ* ĠThe Ġgraph Ġis Ġ" immutable " Ġwhen Ġthis Ġis Ġ 0 . ĊĠĠĠĠ Ġ*/ Ċ ĉ var Ġoutstanding Gu ards Ġ= Ġ 0 Ċĉ ĉ protected Ġset ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠWhether Ġor Ġnot Ġ[ out standing Gu ards ] Ġis Ġ 0 Ġ( the Ġgraph Ġhas Ġno Ġoutstanding Ġ[ Mutation Guard ] s ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis Immutable ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġoutstanding Gu ards Ġ== Ġ 0 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġguard Ġthat Ġautomatically Ġupdates Ġthe Ġgraph Ġwhen Ġthe Ġlast Ġone Ġis Ġdropped . ĊĠĠĠĠ Ġ* ĠĊĠĠĠĠ Ġ* ĠThis Ġinteract s Ġwith Ġ[ out standing Gu ards ] Ġfor Ġcorrect ness . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġclass ' Ġsafety Ġcan Ġ_ only _ Ġbe Ġguaranteed Ġif Ġthe Ġfollowing Ġtwo Ġin variants Ġare Ġup held : ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ 1 . Ġ[ Mutation Guard . drop ] Ġis Ġcalled , Ġ_ in Ġevery Ġexecution Ġpath _, Ġwhen Ġthe Ġ[ Mutation Guard ] Ġis Ġno Ġlonger Ġin Ġuse . ĊĠĠĠĠ Ġ* Ġ 2 . ĠThis Ġinstance Ġis Ġ_ not _ Ġused Ġ( no Ġmethod Ġis Ġcalled ) Ġany Ġmore Ġafter Ġ[ Mutation Guard . drop ] Ġis Ġcalled . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠIt 's Ġnot Ġnecessary Ġto Ġdrop Ġthe Ġreference Ġafter Ġ( 2 ), Ġbut Ġit 's Ġmuch Ġeasier Ġto Ġup hold Ġthis Ġinvariant Ġif Ġthis Ġis Ġdone . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠUsually , Ġone Ġof Ġthese Ġis Ġconstructed Ġand Ġused Ġas Ġthe Ġ" context Ġobject " Ġin Ġ[ mutate ]. ĠSee Ġthat Ġfor Ġdetails . ĊĠĠĠĠ Ġ*/ Ċ ĉ inner Ġclass ĠMutation Guard Ġinternal Ġconstructor () Ġ{ ĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġvisit Ġroot Ġfirst Ġconsidered Ġafter Ġ( dro pping )[ drop ] Ġthis Ġguard . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġdefault Ġof Ġ` null ` Ġis Ġsafe , Ġbut Ġthis Ġcan Ġbe Ġused Ġto Ġinform Ġthe Ġalgorithm Ġabout Ġa Ġ[ Connected Component ] Ġthat Ġshould Ġbe Ġpreserved Ġ( having Ġalready Ġbeen Ġrealized ). ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġvar Ġvisit Root : ĠVertex ? Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprotected Ġset ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠSet Ġthe Ġ[ visit Root ]. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġcan Ġonly Ġbe Ġdone Ġonce Ġper Ġguard , Ġand Ġshould Ġonly Ġbe Ġdone Ġjust Ġbefore Ġreturning Ġfrom Ġa Ġ[ mutate ] Ġclosure . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠRemember Ġthat Ġthis Ġis Ġjust Ġa Ġhint , Ġand Ġcan 't Ġguarantee Ġhow Ġvisit ation Ġwill Ġoccur . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġset Root ( v : ĠVertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( visit Root Ġ== Ġnull ) Ġ{ Ġ" tri ed Ġto Ġset Ġvisit Ġroot Ġ$ v Ġwhen Ġalready Ġset Ġto Ġ$ visit Root " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisit Root Ġ= Ġv ĊĠĠĠĠĠĠĠ Ġ} ĊĊĉ ĉ init Ġ{ Ċĉĉ ĉ out standing Gu ards ++ Ċĉĉ ĉ d println (" beginning Ġmutation , Ġnest Ġlevel Ġ$ out standing Gu ards ") Ċĉ ĉ } ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠConnect Ġtwo Ġ( vertices )[ Vertex ]. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġorder Ġof Ġvertices Ġto Ġthe Ġ[ Edge ] Ġconstructor Ġis Ġpreserved . ĠThis Ġmay Ġbe Ġuseful Ġfor Ġ" pseudo - oriented " Ġedges . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġconnect ( a : ĠVertex , Ġb : ĠVertex ) Ġ= Ġthis @ Component Graph . connect ( a , Ġb ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDis connect Ġtwo Ġ( vertices )[ Vertex ], Ġreturning Ġwhether Ġor Ġnot Ġthe Ġgraph Ġactually Ġchanged Ġ( if Ġan Ġedge Ġwas Ġremoved ). ĊĠĠĠĠĠĠĠĠ Ġ*/ Ċĉ ĉ fun Ġdisconnect ( a : ĠVertex , Ġb : ĠVertex ) Ġ= Ġthis @ Component Graph . disconnect ( a , Ġb ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDis connect Ġevery Ġedge Ġincident Ġto Ġ[ Vertex ] Ġ[ v ]. ĊĠĠĠĠĠĠĠĠ Ġ*/ Ċĉ ĉ fun Ġdisconnect ( v : ĠVertex ) Ġ= Ġthis @ Component Graph . disconnect ( v ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠAdd Ġ( and Ġreturn ) Ġa Ġnew Ġ[ Vertex ] Ġto Ġthe Ġunderlying Ġ[ Component Graph ]. ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġnew Vertex () Ġ= Ġthis @ Component Graph . new Vertex () ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠRemove Ġ[ Vertex ] Ġ[ v ] Ġfrom Ġthe Ġgraph . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġbase Ġimplementation Ġis Ġsafely Ġide mpot ent , Ġbut Ġthe Ġlisteners Ġmight Ġnot Ġbe . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġremove Vertex ( v : ĠVertex ) Ġ= Ġthis @ Component Graph . remove Vertex ( v ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDrop Ġthis Ġ[ Mutation Guard ]. ĠNorm ally , Ġthis Ġdoes Ġnot Ġneed Ġto Ġbe Ġdone Ġexplicitly ; Ġ[ mutate ] Ġwill Ġdo Ġthis Ġautomatically . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠOnce Ġthis Ġis Ġdone , Ġit Ġis Ġ_ not Ġsafe _ Ġto Ġuse Ġany Ġother Ġmethod Ġon Ġthis Ġinstance . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġdrop () Ġ{ Ċĉĉ ĉ d println (" ending Ġmutation , Ġnest Ġlevel Ġ$ out standing Gu ards ") Ċĉĉ ĉ if (-- out standing Gu ards Ġ== Ġ 0 ) Ġ{ Ċĉĉĉ ĉ assign Components ( visit Root ) Ċĉĉ ĉ } Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠS af ely Ġmutate Ġthis Ġgraph . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġprovides Ġthe Ġclosure Ġwith Ġaccess Ġ( in Ġthe Ġcontext ) Ġto Ġa Ġ[ Mutation Guard ] Ġobject , Ġwhich Ġis Ġ( d ropped )[ Mutation Guard . drop ] Ġwhen Ġthe Ġclosure Ġreturns . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThe Ġreference Ġ_ can _, Ġbut Ġ_ should n 't _, Ġbe Ġstored Ġanywhere , Ġto Ġmaintain Ġthe Ġsecond Ġinvariant Ġof Ġthe Ġ[ Mutation Guard ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠMut ations Ġcan Ġsafely Ġbe Ġnested Ġ( it Ġis Ġsafe Ġto Ġcall Ġ[ mutate ], Ġdirectly Ġor Ġindirect ly , Ġfrom Ġanother Ġ[ mutate ] Ġclosure ). ĠOnly Ġwhen Ġthe Ġlast Ġ[ Mutation Guard ] Ġis Ġdropped Ġis Ġthe Ġgraph Ġstate Ġbrought Ġup - to - date Ġ( via Ġ[ assign Components ]). ĠAfter Ġthis Ġfinal Ġdrop Ġ( usually Ġat Ġthe Ġreturn Ġof Ġa Ġuser Ġclosure ), Ġ[ is Immutable ] Ġis Ġtrue Ġand Ġall Ġobservable Ġin variants Ġ( espec ially Ġthe Ġstate Ġof Ġ[ components ] Ġand Ġeach Ġ[ Vertex . component ]) Ġis Ġvalid . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun < T > Ġmutate ( body : ĠMutation Guard . () Ġ-> ĠT ): ĠT Ġ{ Ċĉ ĉ val Ġguard Ġ= ĠMutation Guard () Ċĉ ĉ try Ġ{ Ċĉĉ ĉ return Ġwith ( guard , Ġbody ) Ċĉ ĉ } Ġfinally Ġ{ Ċĉĉ ĉ guard . drop () Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthe Ġgraph Ġto Ġthe Ġsource Ġof Ġa ĠGraph Viz Ġfile . ĊĠĠĠĠ Ġ*/ Ċ ĉ fun Ġto Dot (): ĠString Ġ{ Ċĉ ĉ val Ġsb Ġ= ĠStringBuilder () Ċĉ ĉ sb . append (" graph Ġ{\ n ") ĊĊĉ ĉ val Ġvertex Names Ġ= Ġvertices . map Indexed Ġ{ Ġi , Ġv Ġ-> ĠPair ( v , Ġi ) Ġ}. toMap () Ċĉ ĉ val Ġcomponent Names Ġ= Ġcomponents . map Indexed Ġ{ Ġi , Ġc Ġ-> ĠPair ( c , Ġi ) Ġ}. toMap () ĊĊĉ ĉ sb . append ("\ t // ĠVert ices \ n ") Ċĉ ĉ sb . append ("\ t ver ror Ġ[ label =\" error Ġnode \" Ġcolor =\" magenta \" ]; \ n ") Ċĉ ĉ vertex Names . entries . forEach Ġ{( vertex , Ġname ) Ġ-> Ċĉĉ ĉ val Ġc name Ġ= Ġcomponent Names [ vertex . component ] Ċĉĉ ĉ val Ġcolor Ġ= Ġif ( cname Ġ!= Ġnull ) Ġ{ Ċĉĉĉ ĉ "/ spect ral 1 1 /${ cname Ġ% Ġ 1 1 Ġ+ Ġ 1 }" Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ " magenta " Ċĉĉ ĉ } Ċĉĉ ĉ sb . append ("\ tv $ name Ġ[ label =\" v $ name \\ nc $ cname \" Ġcolor =\" $ color \" ]; \ n ") Ċĉ ĉ } Ċĉ ĉ sb . append ("\ n ") ĊĊĉ ĉ sb . append ("\ t // ĠEd ges \ n ") Ċĉ ĉ edges . forEach Ġ{ Ċĉĉ ĉ val Ġva Ġ= Ġvertex Names [ it . a ]?. toString () Ġ?: Ġ" error " Ċĉĉ ĉ val Ġvb Ġ= Ġvertex Names [ it . b ]?. toString () Ġ?: Ġ" error " Ċĉĉ ĉ val Ġc name Ġ= Ġcomponent Names [ it . a . component ] Ċĉĉ ĉ val Ġcolor Ġ= Ġif ( cname Ġ!= Ġnull ) Ġ{ Ċĉĉĉ ĉ "/ spect ral 1 1 /${ cname Ġ% Ġ 1 1 Ġ+ Ġ 1 }" Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ " magenta " Ċĉĉ ĉ } Ċĉĉ ĉ sb . append ("\ tv $ va Ġ-- Ġv $ vb Ġ[ color Ġ= Ġ\"$ color \" ]; \ n ") Ċĉ ĉ } Ċĉ ĉ sb . append (" }\ n ") Ċĉ ĉ return Ġsb . toString () Ċ ĉ } Ċ } Ċ