Node-Overlap-Removal

FastNodeOverlapRemoval—AddendumTechnicalReport∗,January2006TimDwyer1,KimMarriott1,andPeterJ.Stuckey21SchoolofComp.Science&Soft.Eng.,MonashUniversity,Australia{tdwyer,marriott}@mail.csse.monash.edu.au2NICTAVictoriaLaboratoryDept.ofComp.Science&Soft.Eng.,UniversityofMelbourne,[e-mail]oversightinourrecentpaperonamethodfornodeoverlapremoval[1,2].Theerror,basedonanin-completedspecifiedinvariant,occursinthealgorithmsatisfyVPSCandleadstoararelyoccurringcasewherenotallconstraintsaresatisfied.Wegivetherequiredadditionstothealgorithmtoobtaincorrectbehaviour,revisetheworstcasecomplexitytheoremandreproducetheexperimen-talperformancedata.WhiletheworstcasecomplexityisO(n2)weshowthatfortypicalinputtheperformanceisO(nlogn)andthisisreflectedbythenewexperimentalresults.Keywords:graphlayout,constrainedoptimization,separationconstraints1IntroductionOurrecentpaper[1]detailsanalgorithmforremovingoverlapbetweenrect-angles,whileattemptingtodisplacetherectanglesbyaslittleaspossible.Thealgorithmisprimarilymotivatedbythenode-overlapremovalproblemingraphdrawing.Thatis,manygraphdrawingalgorithmstreatnodesaspointswithzerowidthandheightsothat,afteralayoutisfound,ifthenodeshavelabelsorassociatedgraphicsthelayoutmustbeadjustedtoremoveanyoverlaps.Theal-gorithmtreatsx-andy-dimensionsseparately,eachasaninstanceofthevariableplacementwithseparationconstraints(VPSC)problemasdetailedbelow.ThemethodforsolvingtheVPSCproblemtooptimalityisdescribedintwoparts.TheSatisfyVPSCprocedurefindsasolutioninwhichalloverlapisremoved,butwhichmaynotnecessarilybeoptimal.TheSolveVPSCalgorithmusesSat-isfyVPSCtofindaninitialfeasiblesolution,andthenrefinesthearrangementuntilanoptimalsolutionisfound.TheproblemdescribedandcorrectedinthispaperoccursinSatisfyVPSCwherethealgorithm,asoriginallydescribed,couldpotentiallyproduceinfeasiblesolutions.Theproblemstemsfromanerroneousassumptionthat,sincevariableswerebeingprocessedlefttoright(whilesolvinginthex-dimension)inapartialorderdeterminedbythedirectedacyclicgraphofseparationconstraints,onceavari-ablewasplacednoothervariablesuponwhichitsconstraintsweredependantwouldbemovedagain.Thealgorithmreliedonthisassumedinvarianttomain-tainheapdatastructuresofincomingconstraintstoblocksofvariables.Thatis,theheapsrequiredthattheorderofrelativeslacknessofincomingconstraintstoeachblockbepreservedsothatthetopmostconstraintoneachheapwouldalwaysbethemostviolated.Theactualsituationturnsouttobeslightlymorecomplicated.Therevisedinvariant,uponwhichthemodifiedalgorithmdepends,isstatedandprovenbelow.Thecomplete,correctsatisfyVPSCalgorithmisalsogivenandthestatementofcomplexitymodified.Finally,wecompareexperimen-talresultsforthenewversionofthealgorithmwiththosefromtheoriginalpaperandfindthatpracticalperformanceisnotadverselyaffected.2TheSatisfyVPSCAlgorithmIneachpassofthenode-overlapremovalprocesswemustsolvethefollowingconstrainedoptimizationproblemforeachdimension:Variableplacementwithseparationconstraints(VPSC)problem.Givennvariablesv1,...,vn,aweightvi.weight≥0andadesiredvaluevi.des1foreachvariableandasetofseparationconstraintsCoverthesevariablesfindanassignmenttothevariableswhichminimizesPni=1vi.weight×(vi−vi.des)2subjecttoC.WecantreatasetofseparationconstraintsCovervariablesVasaweighteddirectedgraphwithanodeforeachv∈Vandanedgeforeachc∈Cfromleft(c)toright(c)withweightgap(c).Wecallthistheconstraintgraph.Wedefineout(v)={c∈C|left(c)=v}andin(v)={c∈C|right(c)=v}.Notethatedgesinthisgrapharenottheedgesintheoriginalgraph.WerestrictattentiontoVPSCproblemsinwhichtheconstraintgraphisacyclicandforwhichthereisatmostoneedgebetweenanypairofvariables.ItispossibletotransformanarbitrarysatisfiableVPSCproblemintoaproblemofthisformandourgenerationalgorithmwillgenerateconstraintswiththisproperty.Sincetheconstraintgraphisacyclicitimposesapartialorderonthevari-ables:wedefineuCviffthereisa(directed)pathfromutovusingtheedgesinseparationconstraintsetC.Wewillmakeuseofthefunctionto-talorder(V,C)whichreturnsatotalorderingforthevariablesinV,i.e.itreturnsalist[v1,...,vn]s.t.forallji,vj6Cvi.Figure1liststhebasicalgorithmforfindingasolutiontotheVPSCproblemsuchthattheseparationconstraintsaresatisfiedandthevariableplacementis“close”tooptimal.IttakesasinputasetofseparationconstraintsCandasetofvariablesV.Thealgorithmworksbymergingvariablesintolargerandlarger“blocks”ofcontiguousvariablesconnectedbyaspanningtreeofactiveconstraints,whereaseparationconstraintu+a≤visactiveif,forthecurrentpositionforuandv,u+a=v.1vi.desissettox0viory0viforeachdimension,asusedingenerateCno{x|y}.2proceduresatisfyVPSC(V,C)timeCtr←0[v1,...,vn]←totalorder(V,C)fori∈1...ndomergeleft(block(vi))endforreturn[v1←posn(v1),...,vn←posn(vn)]procedureblock(v)letbbeanewblocks.t.b.vars←{v}b.nvars←1b.posn←v.desb.wposn←v.weight×v.desb.weight←v.weightb.active←∅b.in←newQueue()b.time←timeCtr←timeCtr+1forc∈in(v)dotime(c)←timeCtradd(b.in,c)endforblock[v]←boffset[v]←0returnbproceduremergeleft(b)whileviolation(top(b.in))0doc←top(b.in)removeTop(b.in)bl←block[left(c)]ifbl.in=nullthensetupinconstraints(bl)