@ file : Suppress (" Un stable Api Usage ") Ċ Ċ package Ġedu . wpi . in nd ie . util Ċ Ċ import Ġarrow . Kind 2 Ċ import Ġarrow . core . For Either Ċ import Ġarrow . core . Left Ċ import Ġarrow . core . Right Ċ import Ġcom . google . common . graph . Graph Ċ import Ġedu . wpi . in nd ie . logging . join With Indent Ċ Ċ /** Ċ Ġ* ĠChecks Ġif Ġthere Ġare Ġis lands Ġin Ġthis Ġgraph . Ċ Ġ* Ċ Ġ* Ġ@ return ĠTrue Ġif Ġthere Ġare Ġis lands . Ċ Ġ*/ Ċ fun Ġ< T Ġ: ĠAny > ĠGraph < T >. check Is lands (): ĠKind 2 < For Either , ĠString , ĠUnit > Ġ{ ĊĠĠĠ Ġval Ġall Nodes Ġ= Ġnodes () ĊĠĠĠ Ġif Ġ( all Nodes . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠCan 't Ġhave Ġis lands Ġwith Ġan Ġempty Ġgraph . ĊĠĠĠĠĠĠĠ Ġreturn ĠRight ( Unit ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠB FS Ġshould Ġfind Ġevery Ġnode Ġif Ġthere Ġis Ġonly Ġone Ġis land . ĠStarting Ġnode Ġdoes Ġnot Ġmatter . ĊĠĠĠ Ġ// ĠSup ply Ġa Ġcustom Ġnext Node Ġfunction Ġbecause Ġthe Ġdirection ĠB FS Ġmoves Ġin Ġis Ġir relevant , ĊĠĠĠ Ġ// Ġit Ġjust Ġhas Ġto Ġtouch Ġevery Ġnode Ġin Ġan Ġis land . ĊĠĠĠ Ġval Ġreachable Ġ= Ġb read th First Search ( all Nodes . first ()) Ġ{ Ġsuccess ors ( it ) Ġ+ Ġpre decess ors ( it ) Ġ} ĊĠĠĠ Ġreturn Ġif Ġ( reachable Ġ== Ġall Nodes ) Ġ{ ĊĠĠĠĠĠĠĠ ĠRight ( Unit ) ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠ ĠLeft ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ""" ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ| The Ġfollowing Ġnodes Ġare Ġnot Ġreachable : ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ| ${ ( all Nodes Ġ- Ġreachable ). join With Indent ("\ t ")} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ""" . trim Margin () ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠFinds Ġif Ġthere Ġare Ġany Ġcirc uits Ġstarting Ġfrom Ġ[ root ]. Ċ Ġ* Ċ Ġ* Ġ@ param Ġroot ĠThe Ġnode Ġto Ġstart Ġfrom . Ċ Ġ* Ġ@ param Ġvisited ĠThe Ġnodes Ġvisited Ġso Ġfar Ġ( used Ġin Ġthe Ġrecursive Ġcall ). Ċ Ġ* Ġ@ return ĠTrue Ġif Ġthere Ġare Ġcirc uits . Ċ Ġ*/ Ċ fun Ġ< T Ġ: ĠAny > ĠGraph < T >. has Circ uits ( ĊĠĠĠ Ġroot : ĠT , ĊĠĠĠ Ġvisited : ĠSet < T > Ġ= Ġempty Set () Ċ ): ĠBoolean Ġ{ ĊĠĠĠ Ġsuccess ors ( root ). forEach Ġ{ Ġnode Ġ-> ĊĠĠĠĠĠĠĠ Ġval Ġreachable Ġ= Ġb read th First Search ( node ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠFind ing Ġan Ġalready Ġvisited Ġnode Ġin Ġthe Ġnew Ġreachable Ġset Ġimplies Ġa Ġcircuit . ĠThe ĊĠĠĠĠĠĠĠ Ġ// Ġreachable Ġset Ġwill Ġstrictly Ġdecrease Ġfor Ġsuccess or Ġnodes Ġin Ġa ĠDAG . ĊĠĠĠĠĠĠĠ Ġif Ġ( visited Ġany In Ġreachable Ġ|| Ġhas Circ uits ( node , Ġvisited Ġ+ Ġnode )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġfalse Ċ } Ċ Ċ /** Ċ Ġ* ĠRuns Ġa Ġb read th Ġfirst Ġsearch Ġ( with Ġno Ġtarget Ġnode ) Ġstarting Ġat Ġ[ root ] Ġand Ġmoving Ġusing Ġthe Ċ Ġ* Ġ[ next Nodes ] Ġsuccess or Ġfunction . Ċ Ġ* Ċ Ġ* Ġ@ param Ġroot ĠThe Ġnode Ġto Ġstart Ġsearching Ġfrom . Ċ Ġ* Ġ@ param Ġnext Nodes ĠA Ġsuccess or Ġfunction . Ċ Ġ* Ġ@ return ĠAll Ġthe Ġvisited Ġnodes . Ċ Ġ*/ Ċ fun Ġ< T Ġ: ĠAny > ĠGraph < T >. bread th First Search ( ĊĠĠĠ Ġroot : ĠT , ĊĠĠĠ Ġnext Nodes : ĠGraph < T >. ( T ) Ġ-> ĠSet < T > Ġ= ĠGraph < T >:: success ors Ċ ): ĠSet < T > Ġ{ ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < T >() ĊĠĠĠ Ġval Ġqueue Ġ= Ġmutable ListOf < T >() ĊĊĠĠĠ Ġvisited Ġ+= Ġroot ĊĠĠĠ Ġqueue Ġ+= Ġroot ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġqueue . first () ĊĠĠĠĠĠĠĠ Ġqueue . remove ( node ) ĊĊĠĠĠĠĠĠĠ Ġnext Nodes ( node ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( it Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisited Ġ+= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue Ġ+= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġvisited Ċ } Ċ