package Ġdev . ef ant ini . maximum weighted matching Ċ Ċ import Ġkotlin . math . max Ċ Ċ object ĠMaximum Weighted Matching Ġ{ ĊĊĠĠĠ Ġval Ġdebug Mode Ġ= Ġfalse ĊĊĠĠĠ Ġfun Ġmax Weight Matching ( ĊĠĠĠĠĠĠĠ Ġedges : ĠList < Graph Edge >, ĊĠĠĠĠĠĠĠ Ġmax cardinality : ĠBoolean Ġ= Ġfalse ĊĠĠĠ Ġ): ĠList < Pair < Long , ĠLong >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġreturn Pairs Ġ= Ġmutable ListOf < Pair < Long , ĠLong >>() ĊĊĠĠĠĠĠĠĠ Ġval Ġm ate Ġ= Ġmax Weight Matching List ( edges , Ġmax cardinality ) ĊĊĠĠĠĠĠĠĠ Ġm ate . forEach Indexed Ġ{ Ġindex , Ġl Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( return Pairs . none Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( it . first Ġ== Ġl Ġ|| Ġit . second Ġ== Ġl ) Ġ&& Ġl . toInt () Ġ!= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Pairs . add ( Pair ( index . to Long (), Ġl )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġreturn Pairs ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmax Weight Matching List ( ĊĠĠĠĠĠĠĠ Ġedges : ĠList < Graph Edge >, ĊĠĠĠĠĠĠĠ Ġmax cardinality : ĠBoolean Ġ= Ġfalse ĊĠĠĠ Ġ): ĠMutable List < Long > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġif Ġ( edges . isEmpty ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġmutable ListOf () ĊĊĠĠĠĠĠĠĠ Ġval Ġn edges Ġ= Ġedges . count () ĊĠĠĠĠĠĠĠ Ġvar Ġn vertex Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġedges . forEach Ġ{ Ġgraph Edge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( graph Edge . node 1 Ġ>= Ġ 0 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Edge . node 2 Ġ>= Ġ 0 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Edge . node 1 Ġ!= Ġgraph Edge . node 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( graph Edge . node 1 Ġ>= Ġn vertex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn vertex Ġ= Ġ( graph Edge . node 1 Ġ+ Ġ 1 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( graph Edge . node 2 Ġ>= Ġn vertex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn vertex Ġ= Ġ( graph Edge . node 2 Ġ+ Ġ 1 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġmax weight Ġ= Ġmax ( 0 , Ġedges . max Of Ġ{ Ġit . weight Ġ}) ĊĊĠĠĠĠĠĠĠ Ġval Ġendpoint Ġ= Ġmutable ListOf < Long >() ĊĠĠĠĠĠĠĠ Ġedges . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġendpoint . add ( it . node 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġendpoint . add ( it . node 2 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġne ighb end Ġ= Ġmutable ListOf < Mutable List < Int >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( k Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġne ighb end . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġedges . forEach Indexed Ġ{ Ġk , Ġgraph Edge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġne ighb end [ graph Edge . node 1 . toInt ()]. add (( 2 Ġ* Ġk ) Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġne ighb end [ graph Edge . node 2 . toInt ()]. add ( 2 Ġ* Ġk ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġm ate Ġ= Ġmutable ListOf < Long >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm ate . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġlabel Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel . add ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel . add ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġlabel end Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġin b loss om Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġin b loss om . add ( i ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb loss omp arent Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb loss om child s Ġ= Ġmutable ListOf < Mutable List < Int >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb loss om base Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om base . add ( i ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om base . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb loss om end ps Ġ= Ġmutable ListOf < Mutable List < Int >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb ested ge Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge . add (- 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġb loss omb ested ges Ġ= Ġmutable ListOf < Mutable List < Int >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġun use db loss oms Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġn vertex Ġuntil Ġn vertex Ġ* Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġun use db loss oms . add ( i ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġdual var Ġ= Ġmutable ListOf < Long >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdual var . add ( max weight ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdual var . add ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġallow edge Ġ= Ġmutable ListOf < Boolean >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn edges ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge . add ( false ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= Ġmutable ListOf < Int >() ĊĊĠĠĠĠĠĠĠ Ġfun Ġslack ( k : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ edges [ k ]. node 1 . toInt ()] Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ edges [ k ]. node 2 . toInt ()] Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( 2 Ġ* Ġedges [ k ]. weight ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġb loss om Le aves ( b : ĠInt ): ĠMutable List < Int > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( b Ġ< Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable ListOf ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ]. flatMap Ġ{ Ġt Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ< Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable ListOf ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om Le aves ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ}. to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġassign Label ( w : ĠInt , Ġt : ĠInt , Ġp : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġassign Label ($ w ,$ t ,$ p )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġin b loss om [ w ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ w ] Ġ== Ġ 0 Ġ&& Ġlabel [ b ] Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ w ] Ġ= Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ b ] Ġ= Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ w ] Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ b ] Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ w ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . addAll ( b loss om Le aves ( b )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠP USH Ġ${ b loss om Le aves ( b )} ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( t Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbase Ġ= Ġb loss om base [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( mate [ base ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġendpoint [ mate [ base ]. toInt ()]. toInt (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ base ]. xor ( 1 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġscan B loss om ( par V : ĠInt , Ġpar W : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġscan B loss om ($ par V ,$ par W )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġv Ġ= Ġpar V ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġw Ġ= Ġpar W ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpath Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbase Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( v Ġ!= Ġ- 1 Ġ|| Ġw Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġin b loss om [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ b ]. and ( 4 ) Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbase Ġ= Ġb loss om base [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ b ] Ġ== Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath . add ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ b ] Ġ= Ġ 5 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ b ] Ġ== Ġm ate [ b loss om base [ b ]]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label end [ b ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġendpoint [ label end [ b ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġin b loss om [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ b ] Ġ== Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ b ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġendpoint [ label end [ b ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( w Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġw . also Ġ{ Ġw Ġ= Ġv Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ it ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġbase ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġadd B loss om ( base : ĠInt , Ġk : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġedges [ k ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġv Ġ= Ġedge . node 1 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġw Ġ= Ġedge . node 2 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbb Ġ= Ġin b loss om [ base ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbv Ġ= Ġin b loss om [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbw Ġ= Ġin b loss om [ w ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġun use db loss oms . remove Last () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġadd B loss om ($ base ,$ k ) Ġ( v =$ v Ġw =$ w ) Ġ-> Ġ$ b ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om base [ b ] Ġ= Ġbase ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent [ bb ] Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpath Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ] Ġ= Ġpath ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġend ps Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ] Ġ= Ġend ps ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( bv Ġ!= Ġbb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent [ bv ] Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath . add ( bv ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ps . add ( label end [ bv ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ bv ] Ġ== Ġ 2 Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( label [ bv ] Ġ== Ġ 1 Ġ&& Ġlabel end [ bv ] Ġ== Ġm ate [ b loss om base [ bv ]]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ bv ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġendpoint [ label end [ bv ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbv Ġ= Ġin b loss om [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath . add ( bb ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath . reverse () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġend ps . reverse () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġend ps . add ( 2 Ġ* Ġk ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( bw Ġ!= Ġbb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent [ bw ] Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath . add ( bw ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ps . add ( label end [ bw ]. xor ( 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ bw ] Ġ== Ġ 2 Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( label [ bw ] Ġ== Ġ 1 Ġ&& Ġlabel end [ bw ] Ġ== Ġm ate [ b loss om base [ bw ]]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ bw ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġw Ġ= Ġendpoint [ label end [ bw ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbw Ġ= Ġin b loss om [ w ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ bb ] Ġ== Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ b ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ b ] Ġ= Ġlabel end [ bb ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ b ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om Le aves ( b ). forEach Ġ{ Ġv Ins Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ in b loss om [ v Ins ]] Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( v Ins ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġin b loss om [ v Ins ] Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb ested get o Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested get o . add (- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested get o . add (- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnb lists : ĠMutable List < Mutable List < Int >> Ġ= Ġif Ġ( b loss omb ested ges [ it ]. isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable ListOf ( b loss omb ested ges [ it ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om Le aves ( it ). map Ġ{ Ġbl V Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġne ighb end [ bl V ]. map Ġ{ Ġne igh Bl V Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġne igh Bl V . floor Div ( 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ}. to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ}. to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnb lists . forEach Ġ{ Ġnb List Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnb List . forEach Ġ{ Ġint Nb List Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Nb Ġ= Ġedges [ int Nb List ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġedge Nb . node 1 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġedge Nb . node 2 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( in b loss om [ j ] Ġ== Ġb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġj . also Ġ{ Ġj Ġ= Ġi Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb j Ġ= Ġin b loss om [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( bj Ġ!= Ġb Ġ&& Ġlabel [ bj ] Ġ== Ġ 1 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( b ested get o [ bj ] Ġ== Ġ- 1 Ġ|| Ġslack ( int Nb List ) Ġ< Ġslack ( b ested get o [ bj ])) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested get o [ bj ] Ġ= Ġk ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges [ it ] Ġ= Ġmutable ListOf () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ it ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges [ b ] Ġ= Ġb ested get o . filter Ġ{ Ġit Ġ!= Ġ- 1 Ġ}. to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges [ b ]. forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b ested ge [ b ] Ġ== Ġ- 1 Ġ|| Ġslack ( it ) Ġ< Ġslack ( b ested ge [ b ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ b ] Ġ= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġb loss om child s [$ b ]= ${ b loss om child s [ b ]} ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġexpand B loss om ( b : ĠInt , Ġend stage : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" DEBUG : Ġexpand B loss om ($ b , ${ if Ġ( end stage ) Ġ 1 Ġelse Ġ 0 })" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" Ġ${ b loss om child s [ b ]}" ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ]. forEach Ġ{ Ġs Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omp arent [ s ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s Ġ< Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġin b loss om [ s ] Ġ= Ġs ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( end stage Ġ&& Ġdual var [ s ]. toInt () Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpand B loss om ( s , Ġend stage ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om Le aves ( s ). forEach Ġ{ Ġv Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġin b loss om [ v ] Ġ= Ġs ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! end stage Ġ&& Ġlabel [ b ] Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ b ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġentry child Ġ= Ġin b loss om [ endpoint [ label end [ b ]. xor ( 1 )]. toInt ()] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġb loss om child s [ b ]. indexOf ( entry child ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj step : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġend ptr ick : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( j . and ( 1 ) Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ-= Ġb loss om child s [ b ]. size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj step Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ptr ick Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj step Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ptr ick Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġp Ġ= Ġlabel end [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p . xor ( 1 ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ endpoint [ endpoint . last Index Ġ+ Ġ( p . xor ( 1 )) Ġ+ Ġ 1 ]. toInt ()] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ endpoint [ p . xor ( 1 )]. toInt ()] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġinner Label Index Ġ= Ġj Ġ- Ġend ptr ick ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( inner Label Index Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinner Label Index Ġ= Ġb loss om end ps [ b ]. last Index Ġ+ Ġ( j Ġ- Ġend ptr ick ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġouter Label Index Ġ= Ġb loss om end ps [ b ][ inner Label Index ]. xor ( end ptr ick ). xor ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( outer Label Index Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġouter Label Index Ġ= Ġendpoint . last Index Ġ+ Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ][ inner Label Index ]. xor ( end ptr ick ). xor ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ endpoint [ outer Label Index ]. toInt ()] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p . xor ( 1 ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( endpoint [ endpoint . last Index Ġ+ Ġ( p . xor ( 1 )) Ġ+ Ġ 1 ]. toInt (), Ġ 2 , Ġp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( endpoint [ p . xor ( 1 )]. toInt (), Ġ 2 , Ġp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge [ b loss om end ps [ b ][ inner Label Index ]. floor Div ( 2 )] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinner Label Index Ġ= Ġj Ġ- Ġend ptr ick ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( inner Label Index Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinner Label Index Ġ= Ġb loss om end ps [ b ]. last Index Ġ+ Ġ( j Ġ- Ġend ptr ick ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp Ġ= Ġb loss om end ps [ b ][ inner Label Index ]. xor ( end ptr ick ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge [ p . floor Div ( 2 )] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbv Ġ= Ġb loss om child s [ b ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ bv ] Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ endpoint [ p . xor ( 1 )]. toInt ()] Ġ= Ġlabel [ bv ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ endpoint [ p . xor ( 1 )]. toInt ()] Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ bv ] Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ bv ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpand Cycle @ Ġwhile Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( j Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ b loss om child s [ b ]. last Index Ġ+ Ġj Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ!= Ġentry child ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbv Ġ= Ġif Ġ( j Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ b loss om child s [ b ]. last Index Ġ+ Ġj Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ bv ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DE BU U : Ġ" Ġ+ Ġb loss om Le aves ( bv )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġb loss om Le aves ( bv ). first OrNull Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ it ] Ġ!= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġ?: Ġb loss om Le aves ( bv ). last () ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" LABEL ON Ġ= Ġ${ label [ v ]} ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ v ] Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ v ] Ġ== Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( in b loss om [ v ] Ġ== Ġbv ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ v ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ endpoint [ mate [ b loss om base [ bv ]]. toInt ()]. toInt ()] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( v , Ġ 2 , Ġlabel end [ v ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ b ] Ġ= Ġlabel end [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ] Ġ= Ġmutable ListOf () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ] Ġ= Ġb loss om end ps [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om base [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges [ b ] Ġ= Ġmutable ListOf () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ b ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġun use db loss oms . add ( b ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġaugment B loss om ( b : ĠInt , Ġv : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġaugment B loss om ($ b ,$ v )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġv ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj step : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġend ptr ick : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( b loss omp arent [ t ] Ġ!= Ġb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġb loss omp arent [ t ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ>= Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment B loss om ( t , Ġv ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġb loss om child s [ b ]. indexOf ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġb loss om child s [ b ]. indexOf ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i . and ( 1 ) Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ-= Ġb loss om child s [ b ]. size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj step Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ptr ick Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj step Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend ptr ick Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġif Ġ( j Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ b loss om child s [ b ]. last Index Ġ+ Ġj Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġif Ġ( j Ġ- Ġend ptr ick Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ][ b loss om child s [ b ]. last Index Ġ+ Ġ( j Ġ- Ġend ptr ick ) Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. xor ( end ptr ick ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ][ j Ġ- Ġend ptr ick ]. xor ( end ptr ick ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ>= Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment B loss om ( t , Ġendpoint [ p ]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġj step ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġif Ġ( j Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ b loss om child s [ b ]. last Index Ġ+ Ġj Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ>= Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment B loss om ( t , Ġendpoint [ p . xor ( 1 )]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ endpoint [ endpoint . last Index Ġ+ Ġp Ġ+ Ġ 1 ]. toInt ()] Ġ= Ġp . xor ( 1 ). to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ endpoint [ p ]. toInt ()] Ġ= Ġp . xor ( 1 ). to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p . xor ( 1 ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ endpoint [ endpoint . last Index Ġ+ Ġ( p . xor ( 1 )) Ġ+ Ġ 1 ]. toInt ()] Ġ= Ġp . to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ endpoint [ p . xor ( 1 )]. toInt ()] Ġ= Ġp . to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" DEBUG : ĠPA IR Ġ" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"${ if Ġ( p Ġ< Ġ 0 ) Ġendpoint [ endpoint . last Index Ġ+ Ġp Ġ+ Ġ 1 ] Ġelse Ġendpoint [ p ]}" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" Ġ" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"${ if Ġ( p . xor ( 1 ) Ġ< Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġendpoint [ endpoint . last Index Ġ+ Ġ( p . xor ( 1 )) Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġendpoint [ p . xor ( 1 )] }" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" Ġ( k =${ ( p Ġ/ Ġ 2 )}) " ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ] Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ]. slice ( i Ġuntil Ġb loss om child s [ b ]. size ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om child s [ b ]. slice ( 0 Ġuntil Ġi ). to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ). to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ] Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ]. slice ( i Ġuntil Ġb loss om end ps [ b ]. size ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om end ps [ b ]. slice ( 0 Ġuntil Ġi ). to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ). to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb loss om base [ b ] Ġ= Ġb loss om base [ b loss om child s [ b ][ 0 ]] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( b loss om base [ b ] Ġ== Ġv ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġaugment Matching ( k : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġedges [ k ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġedge . node 1 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġw Ġ= Ġedge . node 2 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġaugment Matching ($ k ) Ġ( v =$ v Ġw =$ w )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠPA IR Ġ$ v Ġ$ w Ġ( k =$ k )") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlist Pair Ġ= ĠlistOf ( Pair ( v , Ġ 2 Ġ* Ġk Ġ+ Ġ 1 ), ĠPair ( w , Ġ 2 Ġ* Ġk )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlist Pair . forEach Ġ{ Ġ( ls , Ġlp ) Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġs Ġ= Ġls ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġp Ġ= Ġlp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbs Ġ= Ġin b loss om [ s ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ bs ] Ġ== Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ bs ] Ġ== Ġm ate [ b loss om base [ bs ]]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( bs Ġ>= Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment B loss om ( bs , Ġs ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ s ] Ġ= Ġp . to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label end [ bs ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġendpoint [ label end [ bs ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbt Ġ= Ġin b loss om [ t ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ bt ] Ġ== Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label end [ bt ] Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Ġ= Ġendpoint [ label end [ bt ]]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġendpoint [ label end [ bt ]. xor ( 1 )]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( b loss om base [ bt ] Ġ== Ġt ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( bt Ġ>= Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment B loss om ( bt , Ġj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ j ] Ġ= Ġlabel end [ bt ]. to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp Ġ= Ġlabel end [ bt ]. xor ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠPA IR Ġ$ s Ġ$ t Ġ( k =${ ( p Ġ/ Ġ 2 )}) ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġverify Opt imum () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTODO ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfun Ġcheck Delta 2 () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTODO ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfun Ġcheck Delta 3 () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTODO ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġmain Loop (): ĠMutable List < Long > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( t Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠST AGE Ġ$ t ") ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel . add ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel . add ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge . add (- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge . add (- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges . remove Last () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb loss omb ested ges . add ( mutable ListOf ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn edges ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge . add ( false ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . clear () ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mate [ v ]. toInt () Ġ== Ġ- 1 Ġ&& Ġlabel [ in b loss om [ v ]] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( v , Ġ 1 , Ġ- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġaugment ed Ġ= Ġfalse ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠSUB STAGE ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( queue . isNotEmpty () Ġ&& Ġ! augment ed ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġqueue . remove Last () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠPOP Ġv =$ v ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ in b loss om [ v ]] Ġ== Ġ 1 ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrun Ġwhile Cycle @{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġne ighb end [ v ]. forEach Ġne ighb end Cycle @{ Ġp Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġ( p Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġw Ġ= Ġendpoint [ p ]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk slack Ġ= Ġslack ( k ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( in b loss om [ v ] Ġ== Ġin b loss om [ w ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn @ ne ighb end Cycle ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! allow edge [ k ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( k slack Ġ<= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge [ k ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( allow edge [ k ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ in b loss om [ w ]] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassign Label ( w , Ġ 2 , Ġp . xor ( 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ in b loss om [ w ]] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbase Ġ= Ġscan B loss om ( v , Ġw ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( base Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd B loss om ( base , Ġk ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment Matching ( k ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaugment ed Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn @ while Cycle ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ w ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ in b loss om [ w ]] Ġ== Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ w ] Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel end [ w ] Ġ= Ġp . xor ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ in b loss om [ w ]] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġin b loss om [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b ested ge [ b ] Ġ== Ġ- 1 Ġ|| Ġk slack Ġ< Ġslack ( b ested ge [ b ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ b ] Ġ= Ġk ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ w ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b ested ge [ w ] Ġ== Ġ- 1 Ġ|| Ġk slack Ġ< Ġslack ( b ested ge [ w ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ested ge [ w ] Ġ= Ġk ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( augment ed ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġdelt atype Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġdelta Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġdelta edge Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġdelt ab loss om Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! max cardinality ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt atype Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta Ġ= Ġdual var . take ( n vertex ). min Of Ġ{ Ġit Ġ}. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ in b loss om [ v ]] Ġ== Ġ 0 Ġ&& Ġb ested ge [ v ] Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġslack ( b ested ge [ v ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( delt atype Ġ== Ġ- 1 Ġ|| Ġd . toInt () Ġ< Ġdelta ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta Ġ= Ġd . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt atype Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta edge Ġ= Ġb ested ge [ v ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( b Ġin Ġ 0 Ġuntil Ġ( 2 Ġ* Ġn vertex )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b loss omp arent [ b ] Ġ== Ġ- 1 Ġ&& Ġlabel [ b ] Ġ== Ġ 1 Ġ&& Ġb ested ge [ b ] Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk slack Ġ= Ġslack ( b ested ge [ b ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert (( k slack Ġ% Ġ 2 ) Ġ== Ġ 0 . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġk slack Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( delt atype Ġ== Ġ- 1 Ġ|| Ġd Ġ< Ġdelta ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta Ġ= Ġd . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt atype Ġ= Ġ 3 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta edge Ġ= Ġb ested ge [ b ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( b Ġin Ġn vertex Ġuntil Ġ( 2 Ġ* Ġn vertex )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b loss om base [ b ] Ġ>= Ġ 0 Ġ&& Ġb loss omp arent [ b ] Ġ== Ġ- 1 Ġ&& Ġlabel [ b ] Ġ== Ġ 2 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( delt atype Ġ== Ġ- 1 Ġ|| Ġdual var [ b ] Ġ< Ġdelta ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta Ġ= Ġdual var [ b ]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt atype Ġ= Ġ 4 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt ab loss om Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( delt atype Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( max cardinality ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelt atype Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelta Ġ= Ġmax ( 0 , Ġdual var . take ( n vertex ). min Of Ġ{ Ġit Ġ}. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ in b loss om [ v ]] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ v ] Ġ= Ġdual var [ v ] Ġ- Ġdelta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ in b loss om [ v ]] Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ v ] Ġ= Ġdual var [ v ] Ġ+ Ġdelta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( b Ġin Ġn vertex Ġuntil Ġ( 2 Ġ* Ġn vertex )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b loss om base [ b ] Ġ>= Ġ 0 Ġ&& Ġb loss omp arent [ b ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ b ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ b ] Ġ= Ġdual var [ b ] Ġ+ Ġdelta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( label [ b ] Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdual var [ b ] Ġ= Ġdual var [ b ] Ġ- Ġdelta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : Ġdelta $ delt atype =$ delta . 0 0 0 0 0 0 ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( delt atype Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( delt atype Ġ== Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge [ delta edge ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġedges [ delta edge ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġedge . node 1 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġedge . node 2 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( label [ in b loss om [ i ]] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġj . also Ġ{ Ġj Ġ= Ġi Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ in b loss om [ i ]] Ġ== Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( i ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( delt atype Ġ== Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġallow edge [ delta edge ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġedges [ delta edge ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġedge . node 1 . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( label [ in b loss om [ i ]] Ġ== Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( i ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( delt atype Ġ== Ġ 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpand B loss om ( delt ab loss om , Ġfalse ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! augment ed ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( b Ġin Ġn vertex Ġuntil Ġ( 2 Ġ* Ġn vertex )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b loss omp arent [ b ] Ġ== Ġ- 1 Ġ&& Ġb loss om base [ b ] Ġ>= Ġ 0 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlabel [ b ] Ġ== Ġ 1 Ġ&& Ġdual var [ b ]. toInt () Ġ== Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpand B loss om ( b , Ġtrue ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mate [ v ] Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm ate [ v ] Ġ= Ġendpoint [ mate [ v ]. toInt ()] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġn vertex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( mate [ v ]. toInt () Ġ== Ġ- 1 Ġ|| Ġm ate [ mate [ v ]. toInt ()]. toInt () Ġ== Ġv ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( debug Mode ) Ġprintln (" DEBUG : ĠM ATE Ġ= Ġ$ mate ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm ate ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġmain Loop () ĊĠĠĠ Ġ} Ċ } Ċ