/* Ċ Ġ* ĠCopyright Ġ 2 0 1 9 ĠPeter ĠRes pon dek Ċ Ġ* Ċ Ġ* ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* ĠĠĠĠ Ġhttps :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ*/ Ċ Ċ package Ġcom . l any ard . library Ċ Ċ import Ġandroid . graphics . Point Ċ import Ġcom . l any ard . helpers . distance Ċ Ċ /** Ċ Ġ* ĠYour Ġbasic Ġtwo Ġdimensional Ġsp ac ial Ġgraph Ġwith Ġany Ġnumber Ġof Ġvertices Ġand Ġedges . ĠCan Ġfind Ġthe Ġshortest Ġdistance Ċ Ġ* Ġbetween Ġtwo Ġpoints Ġon Ġthe Ġgraph Ġusing ĠD ijk str as Ġalgorithm . Ċ Ġ* Ċ Ġ* Ġ@ author ĠPeter ĠRes pon dek Ċ Ġ*/ Ċ Ċ class ĠVertex < T > Ġ( Ġdata : ĠT , Ġposition : ĠPoint ) Ġ{ ĊĠĠĠ Ġcompanion Ġobject ĠFun ctor { ĊĠĠĠĠĠĠĠ Ġfun Ġ< T > Ġcompare Range Ġ( lhs : ĠVertex < T >, Ġrhs : ĠVertex < T >) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ( lhs . score Ġ< Ġrhs . score ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġvar Ġdata Ġ: ĠĠĠĠĠ ĠT ĊĠĠĠ Ġvar Ġposition Ġ= Ġ ĠPoint ( 0 , Ġ 0 ) ĊĠĠĠ Ġvar Ġscore Ġ= ĠĠĠĠ ĠFloat . MAX _ VALUE ĊĠĠĠ Ġvar Ġvisited Ġ= ĠĠ Ġfalse ĊĠĠĠ Ġvar Ġout Edges Ġ= Ġ Ġmutable Set Of < Edge < T >>() ĊĠĠĠ Ġvar Ġin Edges Ġ= ĠĠ Ġmutable Set Of < Edge < T >>() ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . data Ġ= Ġdata ĊĠĠĠĠĠĠĠ Ġthis . position Ġ= ĠPoint ( position ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġequals Ġ( other : ĠAny ?) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( other Ġis ĠVertex <* >) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġposition Ġ== Ġother . position ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġsuper . hashCode () ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġfun Ġget Edge Ġ( other : ĠVertex < T >) Ġ: ĠEdge < T >? Ġ{ ĊĠĠĠ Ġfor Ġ( Ġedge Ġin Ġthis . out Edges Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( Ġedge . next Ġ=== Ġother Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġedge ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġnull Ċ } ĊĊĊĊĠĠĠ Ġfun Ġlink Vertex ( other : ĠVertex < T >) ĊĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġedge Ġ= ĠEdge ( this , Ġ Ġother ) ĊĠĠĠĠĠĠĠ Ġedge . weight Ġ= Ġthis . position . distance ( other . position ). toFloat () ĊĠĠĠĠĠĠĠ Ġthis . out Edges . add ( edge ) ĊĠĠĠĠĠĠĠ Ġother . in Edges . add ( edge ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ class ĠEdge < T > Ġ( source : ĠVertex < T >, Ġtarget : ĠVertex < T >) Ġ{ ĊĠĠĠ Ġval Ġnext Ġ: ĠĠĠĠĠ ĠVertex < T > ĊĠĠĠ Ġval Ġsource Ġ: ĠĠĠ ĠVertex < T > ĊĠĠĠ Ġvar Ġweight Ġ: ĠĠĠ ĠFloat Ġ= Ġ 0 . 0 F ĊĠĠĠ Ġvar Ġrange Ġ: ĠĠĠĠ ĠFloat Ġ= Ġ 0 . 0 F ĊĊĠĠĠ Ġinit { ĊĠĠĠĠĠĠĠ Ġthis . next Ġ= Ġtarget ĊĠĠĠĠĠĠĠ Ġthis . source Ġ= Ġsource ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġsuper . hashCode () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġequals Ġ( other : ĠAny ?) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( Ġother Ġis ĠEdge < *> Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġthis . next . position Ġ== Ġother . next . position Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . source . position Ġ== Ġother . source . position ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse Ċ } Ċ Ċ } Ċ Ċ class ĠGraph < T > Ċ { ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġ< T > Ġget Route Distance ( route : ĠList < Edge < T >> Ġ) Ġ: ĠFloat ĊĠĠĠĠĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġdistance Ġ: ĠFloat Ġ= Ġ 0 . 0 F ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroute . forEach Ġ{ Ġdistance Ġ+= Ġit . weight Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġdistance ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfun Ġ< T > Ġget Route Positions Ġ( Ġpath : ĠList < Edge < T >> Ġ) Ġ: ĠList < Point > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpoints Ġ= ĠArrayList < Point >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoints . add ( Ġpath [ 0 ]. source . position Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoints . addAll ( path . map Ġ{ Ġsegment -> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsegment . next . position ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġpoints ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġvar Ġvertices Ġ: ĠArrayList < Vertex < T >> ĊĊĠĠĠ Ġenum Ġclass ĠAlgorithm Ġ{ ĊĠĠĠĠĠĠĠ ĠD ijk stra ĊĠĠĠ Ġ} ĊĠĠĠ Ġconstructor () Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . vertices Ġ= ĠArrayList < Vertex < T >>() ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġconstructor ( vertices : ĠArrayList < Vertex < T >>) Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . vertices Ġ= Ġvertices ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġget Route ( algorithm : ĠAlgorithm , Ġstart : ĠVertex < T >, Ġend : ĠVertex < T >) Ġ: ĠArrayList < Edge < T >> ĊĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( Ġvertex Ġin Ġvertices Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvertex . score Ġ= ĠFloat . MAX _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvertex . visited Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġwhen Ġ( algorithm ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠAlgorithm . Di jk stra Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprime Graph Dj ik stra ( start , Ġend ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġget Route Dj ik stra ( start , Ġend ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Route Dj ik stra ( Ġstart : ĠVertex < T >, Ġend : ĠVertex < T > Ġ) Ġ: ĠArrayList < Edge < T >> ĊĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġroute Ġ= ĠArrayList < Edge < T >>() ĊĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġend ; ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!== Ġstart ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġlink Ġ: ĠEdge < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( Ġedge Ġin Ġnode . in Edges Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . score Ġ> Ġedge . source . score ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġedge . source ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlink Ġ= Ġedge ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroute . add ( link !! ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġroute . reverse () ĊĠĠĠĠĠĠĠ Ġreturn Ġroute ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġprime Graph Dj ik stra Ġ( Ġstart : ĠVertex < T >, Ġend : ĠVertex < T > Ġ) ĊĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġqueue Ġ= ĠPriority Queue < Vertex < T >>( ĠVertex . Functor :: compare Range Ġ) ĊĠĠĠĠĠĠĠ Ġstart . score Ġ= Ġ 0 . 0 F ĊĠĠĠĠĠĠĠ Ġqueue . enqueue ( Ġstart Ġ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( Ġ! queue . isEmpty () Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtop Ġ= Ġqueue . peek () !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( Ġtop Ġ=== Ġend Ġ) Ġ{ Ġbreak Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . de queue () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( Ġtop . visited Ġ== Ġtrue Ġ) Ġ{ Ġcontinue Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( Ġedge Ġin Ġtop . out Edges Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( Ġedge . next . visited Ġ== Ġfalse Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( Ġedge . next . score Ġ> Ġ( top . score Ġ+ Ġedge . weight Ġ)) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġedge . next . score Ġ= Ġtop . score Ġ+ Ġedge . weight ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . enqueue ( Ġedge . next Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtop . visited Ġ= Ġtrue ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ }