package Ġcom . rev te kk . jun gle . graph . base Ċ Ċ import Ġjava . lang . IllegalArgumentException Ċ import Ġjava . util .* Ċ Ċ /** Ċ Ġ* ĠAd jacency - list Ġbased Ġdig raph Ġimplementation Ċ Ġ* Ċ Ġ* ĠThis Ġclass Ġimplements Ġthe Ġdig raph Ġmethods Ġusing Ġa Ġbacking Ġad jacency Ġlist Ċ Ġ* Ġrepresentation Ġ- Ġi . e . ĠA , Ġwhere Ġi -> j Ġexists Ġiff Ġ( j Ġin ĠA [ Ġi Ġ]) Ċ Ġ*/ Ċ internal Ġclass ĠAd j List Dig raph < W >: ĠDig raph < W > Ġ{ ĊĠĠĠ Ġprivate Ġval Ġmap Ġ= Ġmutable Map Of < Int , ĠMutable Set < Int >>() ĊĠĠĠ Ġprivate Ġval Ġedges Ġ= Ġmutable Map Of < Pair < Int , ĠInt >, ĠW >() ĊĊĠĠĠ Ġoverride Ġfun Ġadd Edge ( start : ĠInt , Ġend : ĠInt , Ġweight : ĠW ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= Ġmap . safe Get ( start ) ĊĠĠĠĠĠĠĠ Ġset . add ( end ) ĊĊĠĠĠĠĠĠĠ Ġedges [ start Ġto Ġend ] Ġ= Ġweight ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove Edge ( start : ĠInt , Ġend : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= Ġmap . safe Get ( start ) ĊĊĠĠĠĠĠĠĠ Ġval Ġres Ġ= Ġset . remove ( end ) ĊĠĠĠĠĠĠĠ Ġedges . remove ( start Ġto Ġend ) ĊĊĠĠĠĠĠĠĠ Ġreturn Ġres ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġhas Edge ( start : ĠInt , Ġend : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= Ġmap . safe Get ( start ) ĊĠĠĠĠĠĠĠ Ġreturn Ġend Ġin Ġset ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġget Weight ( start : ĠInt , Ġend : ĠInt ): ĠW Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġedges [ start Ġto Ġend ] Ġ?: Ġthrow ĠIllegalArgumentException (" no Ġedge Ġfrom Ġ$ start Ġto Ġ$ end ") ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġvertex Set (): ĠSet < Int > Ġ= Ġmap . keys ĊĠĠĠ Ġoverride Ġfun Ġout ( vertex : ĠInt ): ĠSet < Int > Ġ= Ġmap . safe Get ( vertex ) ĊĊĠĠĠ Ġoverride Ġfun Ġcopy ( weight Copy : Ġ(( W ) Ġ-> ĠW )? ): ĠDig raph < W > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcopy Ġ= ĠAd j List Dig raph < W >() ĊĊĠĠĠĠĠĠĠ Ġ// ĠCopy Ġthe Ġmap Ġentries ĊĠĠĠĠĠĠĠ Ġfor (( key , Ġvalue ) Ġin Ġmap ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Copy Ġ= Ġmutable Set Of < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġv Copy . addAll ( value ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcopy . map [ key ] Ġ= Ġv Copy ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠCopy Ġweight Ġmapping ĊĠĠĠĠĠĠĠ Ġif ( weight Copy Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( edge Ġin Ġedges ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcopy . edges [ edge . key . copy ()] Ġ= Ġweight Copy ( edge . value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcopy . edges . put All ( edges ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġcopy ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġb fs ( start : ĠInt , Ġapply : Ġ( vertex : ĠInt , Ġprev Map : ĠMap < Int , ĠInt >) Ġ-> ĠUnit ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Int >() ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Int >() ĊĊĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġmutable Map Of < Int , ĠInt >() ĊĠĠĠĠĠĠĠ Ġqueue . add ( start ) ĊĊĠĠĠĠĠĠĠ Ġwhile (! queue . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvertex Ġ= Ġqueue . remove () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( vertex Ġin Ġvisited ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMark Ġvertex Ġas Ġvisited ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisited . add ( vertex ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠPerform Ġcustom Ġaction ĊĠĠĠĠĠĠĠĠĠĠĠ Ġapply ( vertex , Ġprev ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAdd Ġall Ġthe Ġne ighbours ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġne igh Ġ= Ġmap . safe Get ( vertex ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . addAll ( ne igh ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUpdate Ġprev Ġmap ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( w Ġin Ġne igh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( w Ġ== Ġstart ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprev . put If Absent ( w , Ġvertex ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġdfs ( start : ĠInt , Ġapply : Ġ( vertex : ĠInt ) Ġ-> ĠUnit ) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdfs ( start , Ġmutable Set Of (), Ġapply ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInternal ĠDFS Ġimplementation Ġ( recursive ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġdfs ( start : ĠInt , Ġvisited : ĠMutable Set < Int >, Ġapply : Ġ( vertex : ĠInt ) Ġ-> ĠUnit ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif ( start Ġin Ġvisited ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĊĠĠĠĠĠĠĠ Ġ// ĠMark Ġvertex Ġas Ġvisited ĊĠĠĠĠĠĠĠ Ġvisited . add ( start ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠPerform Ġcustom Ġaction ĊĠĠĠĠĠĠĠ Ġapply ( start ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠPerform ĠDFS Ġstarting Ġat Ġeach Ġneighbour ĊĠĠĠĠĠĠĠ Ġfor ( ne igh Ġin Ġmap . safe Get ( start )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdfs ( ne igh , Ġvisited , Ġapply ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠPrivate Ġextension Ġfunction : Ġsafe Get () ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġcalls Ġthe ĠMutable Map # get Or Put () Ġmethod , Ġinserting Ġan Ġempty Ġmutable Ġset Ġif ĊĠĠĠĠ Ġ* Ġthe Ġmap Ġdoes Ġnot Ġhave Ġthe Ġprovided Ġkey . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġelim inates Ġhaving Ġthe Ġcode Ġduplication Ġof Ġmap . get Or Put ( key ) Ġ{ Ġmutable Set Of () Ġ} Ġfor ĊĠĠĠĠ Ġ* Ġeach Ġtime Ġthe Ġmap Ġlookup Ġis Ġrequired Ġ- Ġinstead Ġit Ġis Ġnow Ġreplaced Ġby Ġmap . safe Get ( key ) Ġwhich Ġis ĊĠĠĠĠ Ġ* Ġmuch Ġcleaner . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġ< K , ĠW > ĠMutable Map < K , ĠMutable Set < W >> . safe Get ( key : ĠK ): ĠMutable Set < W > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġget Or Put ( key ) Ġ{ Ġmutable Set Of () Ġ} ĊĠĠĠ Ġ} Ċ } Ċ