package Ġio . github . sh ah riv ari . jack rabbit Ċ Ċ import Ġit . un imi . ds i . fast util . long s . Long 2 Object Open HashMap Ċ import Ġmu . Kotlin Logging Ċ import Ġjava . io . FileWriter Ċ import Ġjava . nio . file . Files Ċ import Ġjava . nio . file . Paths Ċ import Ġjava . util .* Ċ Ċ private Ġval Ġlogger Ġ= ĠKotlin Logging . logger Ġ{} ĊĊ Ċ class ĠLong Graph ( edges : ĠIterator < Long Edge >) Ġ: ĠIterable < Long Edge > Ġ{ ĊĠĠĠ Ġval Ġnodes : ĠLong Array Ġget ĊĠĠĠ Ġprivate Ġval Ġadj List Ġ= ĠLong 2 Object Open HashMap < Long Ad jacency >() ĊĠĠĠ Ġprivate Ġval Ġreporter Ġ= ĠProgress Reporter ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger , Ġ 1 _ 0 0 0 _ 0 0 0 ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Reading Ġedges ..." Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( e Ġin Ġedges ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġe . nodes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadj List . get Or Put ( v ) Ġ{ ĠLong Ad jacency ( v ) Ġ}. add Edge ( e ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreporter . progress () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Sorting Ġnodes ..." Ġ} ĊĠĠĠĠĠĠĠ Ġnodes Ġ= Ġadj List . keys . to Long Array () ĊĠĠĠĠĠĠĠ Ġnodes . sort () ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Optim izing Ġad jac encies ..." Ġ} ĊĠĠĠĠĠĠĠ Ġadj List . values . forEach Ġ{ Ġit . sort And Trim () Ġ} ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Graph Ġis Ġbuilt : Ġ# nodes :${ nodes . size } Ġ, Ġ# edges :${ edge Count () }" Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġconstructor ( edges : ĠIterable < Long Edge >) Ġ: Ġthis ( edges . iterator ()) ĊĊĠĠĠ Ġconstructor ( path : ĠString ) Ġ: Ġthis ( Files . lines ( Paths . get ( path )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġ! it . startsWith ("# ") Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġit Ġ-> ĠLong Edge . parse ( it ) Ġ}. iterator ()) ĊĊĠĠĠ Ġfun Ġedge Count () Ġ= Ġadj List . values . map Ġ{ Ġit . ins . size Ġ}. sum () ĊĊĊĠĠĠ Ġfun Ġhas Edge ( src : ĠLong , Ġdest : ĠLong ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġadj Ġ= Ġadj List [ src ] Ġ?: Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġreturn ĠArrays . binary Search ( adj . outs . elements (), Ġdest ) Ġ>= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġad jacency ( v : ĠLong ): ĠLong Ad jacency Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġadj Ġ= Ġadj List [ v ] ĊĠĠĠĠĠĠĠ Ġrequire ( adj Ġ!= Ġnull ) Ġ{ Ġ" The Ġnode Ġis Ġnot Ġpresent : Ġ$ v " Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġadj ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġneighbors ( v : ĠLong ): ĠLong Array Ġ= Ġad jacency ( v ). ne igh s . elements () ĊĊĠĠĠ Ġoverride Ġfun Ġiterator (): ĠIterator < Long Edge > Ġ= ĠEdge Iterator () ĊĊĠĠĠ Ġfun Ġsave As Text ( path : ĠString ) Ġ= ĠFile Writer ("/ tmp / a . txt "). use Ġ{ Ġwriter Ġ-> ĊĠĠĠĠĠĠĠ Ġthis . forEach Ġ{ Ġwriter . write ("${ it . src }\ t ${ it . dst }\ n ") Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġinner Ġclass ĠEdge Iterator Ġ: ĠIterator < Long Edge > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġv Iter Ġ= Ġnodes . iterator () ĊĠĠĠĠĠĠĠ Ġvar Ġadj Ġ= Ġif Ġ( v Iter . hasNext ()) Ġadj List [ v Iter . next ()] Ġelse Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġw Iter Ġ= Ġif Ġ( adj Ġ!= Ġnull ) Ġadj !!. outs . iterator () Ġelse Ġnull ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġhas Next (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( adj Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! w Iter !!. hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! v Iter . hasNext ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadj Ġ= Ġadj List [ v Iter . next ()] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġw Iter Ġ= Ġadj !!. outs . iterator () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġnext (): ĠLong Edge Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrequire ( hasNext ()) Ġ{ Ġ" There Ġis Ġno Ġelement Ġnext !" Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠLong Edge ( adj !!. node , Ġw Iter !!. next Long ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ} Ċ Ċ } Ċ