/* Ċ Ġ* ĠLicensed Ġto Ġthe ĠApache ĠSoftware ĠFoundation Ġ( ASF ) Ġunder Ġone Ċ Ġ* Ġor Ġmore Ġcontributor Ġlicense Ġagreements . Ġ ĠSee Ġthe ĠNOTICE Ġfile Ċ Ġ* Ġdistributed Ġwith Ġthis Ġwork Ġfor Ġadditional Ġinformation Ċ Ġ* Ġregarding Ġcopyright Ġownership . Ġ ĠThe ĠASF Ġlicenses Ġthis Ġfile Ċ Ġ* Ġto Ġyou Ġ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 Ċ Ġ* Ċ Ġ* Ġhttp :// 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 Ġorg . apache . t inker pop 4 . gre mlin . process . computer . traversal Ċ Ċ import Ġorg . apache . commons . configuration 2 . Configuration Ċ Ċ /** Ċ Ġ* Ġ` Traversal Vertex Program ` Ġenables Ġthe Ġevaluation Ġof Ġa Ġ[ Traversal ] Ġon Ġa Ġ[ Graph Computer ]. Ċ Ġ* ĠAt Ġthe Ġstart Ġof Ġthe Ġcomputation , Ġeach Ġ[ Vertex ] Ġ( or Ġ[ Edge ]) Ġis Ġassigned Ġa Ġsingle Ġ[ Tra verser ]. Ċ Ġ* ĠFor Ġeach Ġtra verser Ġthat Ġis Ġlocal Ġto Ġthe Ġvertex , Ġthe Ġvertex Ġlooks Ġup Ġits Ġcurrent Ġlocation Ġin Ġthe Ġtraversal Ġand Ċ Ġ* Ġprocesses Ġthat Ġstep . ĠIf Ġthe Ġoutput ted Ġtra verser Ġof Ġthe Ġstep Ġreferences Ġa Ġlocal Ġstructure Ġon Ġthe Ġvertex Ġ( e . g . Ġthe Ċ Ġ* Ġvertex , Ġan Ġincident Ġedge , Ġits Ġproperties , Ġor Ġan Ġarbitrary Ġobject ), Ġthen Ġthe Ġvertex Ġcontinues Ġto Ġcompute Ġthe Ġnext Ċ Ġ* Ġtra verser . ĠIf Ġthe Ġtra verser Ġreferences Ġanother Ġlocation Ġin Ġthe Ġgraph , Ġthen Ġthe Ġtra verser Ġis Ġsent Ġto Ġthat Ġlocation Ċ Ġ* Ġin Ġthe Ġgraph Ġvia Ġa Ġmessage . ĠThe Ġmessages Ġof ĠTra versal Vertex Program Ġare Ġtra vers ers . ĠThis Ġcontinues Ġuntil Ġall Ċ Ġ* Ġtra vers ers Ġin Ġthe Ġcomputation Ġhave Ġhal ted . Ċ Ġ* Ċ Ġ* Ġ@ author ĠMark o ĠA . ĠRod rig ue z Ġ( http :// mark or od rig ue z . com ) Ċ Ġ*/ Ċ class ĠTra versal Vertex Program Ġprivate Ġconstructor () Ġ: ĠVertex Program < Tra verser Set < Object ?> ?> Ġ{ ĊĠĠĠ Ġprivate Ġvar Ġmemory Compute Keys : ĠSet < Memory Compute Key > Ġ= ĠHashSet () ĊĠĠĠ Ġprivate Ġvar Ġtraversal : ĠPure Traversal < *, Ġ* >? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġtraversal Matrix : ĠTra versal Matrix < *, Ġ* >? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġval Ġmap Reducers : ĠSet < Map Reduce > Ġ= ĠHashSet () ĊĠĠĠ Ġprivate Ġvar Ġhal ted Tra vers ers : ĠTr aver ser Set < Object >? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġreturn Hal ted Tra vers ers Ġ= Ġfalse ĊĠĠĠ Ġprivate Ġvar Ġhal ted Tra verser Strategy : ĠHal ted Tra verser Strategy ? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġprofile Ġ= Ġfalse ĊĊĠĠĠ Ġ// Ġhandle Ġcurrent Ġprofile Ġmetrics Ġif Ġprofile Ġis Ġtrue ĊĠĠĠ Ġprivate Ġvar Ġiteration Metrics : ĠMutable Metrics ? Ġ= Ġnull ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġ[ Pure Traversal ] Ġassociated Ġwith Ġthe Ġcurrent Ġinstance Ġof Ġthe Ġ[ Traversal Vertex Program ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġpure Ġtraversal Ġof Ġthe Ġinstantiated Ġprogram ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget Traversal (): ĠPure Traversal < *, Ġ*> Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġtraversal ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġload State ( graph : ĠGraph ?, Ġconfiguration : ĠConfiguration ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! configuration . containsKey ( TRA VERSAL )) Ġthrow ĠIllegalArgumentException (" The Ġconfiguration Ġdoes Ġnot Ġhave Ġa Ġtraversal : Ġ" Ġ+ ĠTR A VERSAL ) ĊĠĠĠĠĠĠĠ Ġtraversal Ġ= ĠPure Traversal . load State ( configuration , ĠTR A VERSAL , Ġgraph ) ĊĠĠĠĠĠĠĠ Ġif Ġ(! traversal . get (). is Locked ()) Ġtraversal . get (). apply Str ategies () ĊĠĠĠĠĠĠĠ Ġ/// Ġtraversal Ġis Ġcompiled Ġand Ġready Ġto Ġbe Ġint rospect ed ĊĠĠĠĠĠĠĠ Ġtraversal Matrix Ġ= ĠTra versal Matrix ( traversal . get ()) ĊĠĠĠĠĠĠĠ Ġ// Ġget Ġany Ġmaster - traversal Ġhal ted Ġtra vers ers ĊĠĠĠĠĠĠĠ Ġhal ted Tra vers ers Ġ= Ġload Hal ted Tra vers ers < Any >( configuration ) ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġresults Ġwill Ġbe Ġserialized Ġout , Ġdon 't Ġsave Ġhal ted Ġtra vers ers Ġacross Ġthe Ġcluster ĊĠĠĠĠĠĠĠ Ġreturn Hal ted Tra vers ers Ġ= Ġtraversal . get (). getParent (). as Step () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. getNext Step () Ġis ĠComputer Result Step Ġ|| Ġ Ġ// Ġif Ġits Ġjust Ġgoing Ġto Ġstream Ġit Ġout , Ġdon 't Ġdistribute ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). getParent (). as Step () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. getNext Step () Ġis ĠEmpty Step Ġ|| Ġ Ġ// Ġsame Ġas Ġabove , Ġbut Ġif Ġusing ĠTra versal Vertex Program Step Ġdirectly ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). getParent (). as Step () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. getNext Step () Ġis ĠProfile Step Ġ&& Ġ Ġ// Ġsame Ġas Ġabove , Ġbut Ġneeded Ġfor Ġprofiling ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). getParent (). as Step (). getNext Step (). getNext Step () Ġis ĠComputer Result Step ĊĊĠĠĠĠĠĠĠ Ġ// Ġdetermine Ġhow Ġto Ġstore Ġhal ted Ġtra vers ers ĊĠĠĠĠĠĠĠ Ġval Ġit ty : ĠIterator < *> Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ ĠIterator Utils . filter ( traversal . get (). get Str ategies ()) Ġ{ Ġstrategy Ġ-> Ġstrategy Ġis ĠHal ted Tra verser Strategy Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. iterator () ĊĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( it ty . hasNext ()) Ġit ty . next () Ġas ĠHal ted Tra verser Strategy ? Ġelse ĠHal ted Tra verser Strategy . reference () ĊĊĠĠĠĠĠĠĠ Ġ// Ġregister Ġtraversal Ġside - effects Ġin Ġmemory ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . addAll ( Memory Traversal Side Effects . get Memory Compute Keys ( traversal . get ())) ĊĠĠĠĠĠĠĠ Ġ// Ġregister ĠMap Reducer Ġmemory Ġcompute Ġkeys ĊĠĠĠĠĠĠĠ Ġfor Ġ( map Reducer Ġin ĠTra versal Helper . get Steps Of Assignable Class Re cursively ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMap Reducer :: class . java , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get () ĊĠĠĠĠĠĠĠ Ġ)) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmap Reducers . add ( map Reducer . getMap Reduce ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMemory Compute Key . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap Reducer . getMap Reduce (). get Memory Key (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOperator . assign , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġregister Ġmemory Ġcomputing Ġsteps Ġthat Ġuse Ġmemory Ġcompute Ġkeys ĊĠĠĠĠĠĠĠ Ġfor Ġ( memory Comp uting Ġin ĠTra versal Helper . get Steps Of Assignable Class Re cursively ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMemory Comp uting :: class . java , Ġtraversal . get () ĊĠĠĠĠĠĠĠ Ġ)) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( memory Comp uting . get Memory Compute Key ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġregister Ġprofile Ġsteps Ġ( TODO : Ġtry Ġto Ġhide Ġthis ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( profile Step Ġin ĠTra versal Helper . get Steps Of Assignable Class Re cursively ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠProfile Step :: class . java , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get () ĊĠĠĠĠĠĠĠ Ġ)) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). get Side Effects (). register ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprofile Step . getId (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMutable Metrics Supplier ( profile Step . get Previous Step ()), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠProfile Step . Profile Bi Operator . instance () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġregister ĠTra versal Vertex Program Ġspecific Ġmemory Ġcompute Ġkeys ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( Memory Compute Key . of ( V OTE _ TO _ HAL T , ĠOperator . and , Ġfalse , Ġtrue )) ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( Memory Compute Key . of ( HAL TED _ TRA VER SER S , ĠOperator . addAll , Ġfalse , Ġfalse )) ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( Memory Compute Key . of ( ACTIVE _ TRA VER SER S , ĠOperator . addAll , Ġtrue , Ġtrue )) ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( Memory Compute Key . of ( MUT ATED _ MEMORY _ KEYS , ĠOperator . addAll , Ġfalse , Ġtrue )) ĊĠĠĠĠĠĠĠ Ġmemory Compute Keys . add ( Memory Compute Key . of ( COMPLETED _ BAR RI ERS , ĠOperator . addAll , Ġtrue , Ġtrue )) ĊĊĠĠĠĠĠĠĠ Ġ// Ġdoes Ġthe Ġtraversal Ġneed Ġprofile Ġinformation ĊĠĠĠĠĠĠĠ Ġprofile Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ! Traversal Helper . get Steps Of Assignable Class Re cursively ( Profile Step :: class . java , Ġtraversal . get ()). isEmpty () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġstore State ( configuration : ĠConfiguration ) Ġ{ ĊĠĠĠĠĠĠĠ Ġsuper @ Vertex Program . store State ( configuration ) ĊĠĠĠĠĠĠĠ Ġtraversal . store State ( configuration , ĠTR A VERSAL ) ĊĠĠĠĠĠĠĠ Ġstore Hal ted Tra vers ers < Any >( configuration , Ġhal ted Tra vers ers ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġsetup ( memory : ĠMemory ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġmemory Ġis Ġlocal ĊĠĠĠĠĠĠĠ ĠMemory Traversal Side Effects . set Memory Side Effects ( traversal . get (), Ġmemory , ĠProgram Phase . SETUP ) ĊĠĠĠĠĠĠĠ Ġ( traversal . get (). get Side Effects () Ġas ĠMemory Traversal Side Effects ). store Side Effects InMemory () ĊĠĠĠĠĠĠĠ Ġmemory . set ( V OTE _ TO _ HAL T , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġmemory . set ( MUT ATED _ MEMORY _ KEYS , ĠHashSet ()) ĊĠĠĠĠĠĠĠ Ġmemory . set ( COMPLETED _ BAR RI ERS , ĠHashSet ()) ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġhal ted Ġtra vers ers Ġare Ġbeing Ġsent Ġfrom Ġa Ġprevious ĠVertex Program Ġin Ġan ĠO LAP Ġchain Ġ( non - distributed Ġtra vers ers ), Ġget Ġthem Ġinto Ġthe Ġflow ĊĠĠĠĠĠĠĠ Ġif Ġ(! hal ted Tra vers ers . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġto Process Tra vers ers : ĠTr aver ser Set < Object > Ġ= ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠIterator Utils . remove On Next ( hal ted Tra vers ers . iterator ()). forEach Remaining Ġ{ Ġtra verser Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtra verser . set Step Id ( traversal . get (). getStart Step (). getId ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġto Process Tra vers ers . add ( tra verser ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( hal ted Tra vers ers . isEmpty ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġremote Active Tra vers ers : ĠIndexed Tra verser Set < Object , ĠVertex > Ġ= ĠVertex Indexed Tra verser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMaster Executor . process Tra vers ers ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Matrix , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġto Process Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremote Active Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( HAL TED _ TRA VER SER S , Ġhal ted Tra vers ers ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( ACTIVE _ TRA VER SER S , Ġremote Active Tra vers ers ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( HAL TED _ TRA VER SER S , ĠTr aver ser Set ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( ACTIVE _ TRA VER SER S , ĠVertex Indexed Tra verser Set ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġlocal Ġvariable Ġwill Ġno Ġlonger Ġbe Ġused Ġso Ġnull Ġit Ġfor ĠGC ĊĠĠĠĠĠĠĠ Ġhal ted Tra vers ers Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġdoes Ġthe Ġtraversal Ġneed Ġprofile Ġinformation ĊĠĠĠĠĠĠĠ Ġprofile Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ! Traversal Helper . get Steps Of Assignable Class Re cursively ( Profile Step :: class . java , Ġtraversal . get ()). isEmpty () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun ĠgetMessage Scopes ( memory : ĠMemory ?): ĠSet < Message Scope > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠMESSAGE _ SCOPES ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġexecute ( vertex : ĠVertex , Ġmess enger : ĠMess enger < Tra verser Set < Object ?> ?> ?, Ġmemory : ĠMemory ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġany Ġglobal Ġhal ted Ġtra vers ers , Ġsimply Ġdon 't Ġuse Ġthem Ġas Ġthey Ġwere Ġhandled Ġby Ġmaster Ġsetup () ĊĠĠĠĠĠĠĠ Ġ// Ġthese Ġhal ted Ġtra vers ers Ġare Ġtypically Ġfrom Ġa Ġprevious ĠO LAP Ġjob Ġthat Ġy ielded Ġtra vers ers Ġat Ġthe Ġmaster Ġtraversal ĊĠĠĠĠĠĠĠ Ġif Ġ( null Ġ!= Ġhal ted Tra vers ers ) Ġhal ted Tra vers ers Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġmemory Ġis Ġdistributed ĊĠĠĠĠĠĠĠ ĠMemory Traversal Side Effects . set Memory Side Effects ( traversal . get (), Ġmemory , ĠProgram Phase . EXECUTE ) ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġa Ġbarrier Ġwas Ġcompleted Ġin Ġanother Ġworker , Ġit Ġis Ġalso Ġcompleted Ġhere Ġ( ensure Ġdistributed Ġbar riers Ġare Ġsynchronized ) ĊĠĠĠĠĠĠĠ Ġval Ġcompleted Bar riers : ĠSet < String > Ġ= Ġmemory . get ( COMPLETED _ BAR RI ERS ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( step Id Ġin Ġcompleted Bar riers ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġstep : ĠStep < *, Ġ*> Ġ= Ġtraversal Matrix . get Step ById ( step Id ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( step Ġis ĠBar rier ) Ġ( traversal Matrix . get Step ById ( step Id ) Ġas ĠBar rier ). done () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġdefine Ġhal ted Ġtra vers ers ĊĠĠĠĠĠĠĠ Ġval Ġproperty : ĠVertex Property < Tra verser Set < Object >> Ġ= Ġvertex . property ( HAL TED _ TRA VER SER S ) ĊĠĠĠĠĠĠĠ Ġval Ġhal ted Tra vers ers : ĠTr aver ser Set < Object > ĊĠĠĠĠĠĠĠ Ġif Ġ( property . isPresent ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers Ġ= Ġproperty . value () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers Ġ= ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvertex . property ( Vertex Property . Cardinality . single , ĠHAL TED _ TRA VER SER S , Ġhal ted Tra vers ers ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// //////////////// ĊĠĠĠĠĠĠĠ Ġif Ġ( memory . is Initial Iteration ()) Ġ{ ĠĠĠ Ġ// ĠI TER ATION Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġactive Tra vers ers : ĠTr aver ser Set < Object > Ġ= ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġhal ted Ġtra vers ers Ġare Ġbeing Ġsent Ġfrom Ġa Ġprevious ĠVertex Program Ġin Ġan ĠO LAP Ġchain Ġ( distributed Ġtra vers ers ), Ġget Ġthem Ġinto Ġthe Ġflow ĊĠĠĠĠĠĠĠĠĠĠĠ ĠIterator Utils . remove On Next ( hal ted Tra vers ers . iterator ()). forEach Remaining Ġ{ Ġtra verser Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtra verser . set Step Id ( traversal . get (). getStart Step (). getId ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Tra vers ers . add ( tra verser ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( hal ted Tra vers ers . isEmpty ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfor Ġg . V ()/ E () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( traversal . get (). getStart Step () Ġis ĠGraph Step ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġgraph Step : ĠGraph Step < Element , ĠElement > Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). getStart Step () Ġas ĠGraph Step < Element , ĠElement > ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Step . reset () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Tra vers ers . forEach Ġ{ Ġtra verser Ġ-> Ġgraph Step . add Start ( tra verser Ġas ĠTr aver ser . Admin ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Tra vers ers . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( graph Step . returns Vertex ()) Ġgraph Step . set Iterator Supplier Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( Element Helper . id Exists ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvertex . id (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Step . get Ids () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĠIterator Utils . of ( vertex ) Ġelse ĠEmpty Iterator . instance () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġgraph Step . set Iterator Supplier Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠIterator Utils . filter ( vertex . edges ( Direction . OUT )) Ġ{ Ġedge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠElement Helper . id Exists ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġedge . id (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Step . get Ids () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph Step . forEach Remaining Ġ{ Ġtra verser Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( tra verser . is Hal ted ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( return Hal ted Tra vers ers ) Ġmemory . add ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHAL TED _ TRA VER SER S , ĠTr aver ser Set ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy . halt ( tra verser ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġelse Ġhal ted Tra vers ers . add ( tra verser . detach () Ġas ĠTr aver ser . Admin ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġactive Tra vers ers . add ( tra verser Ġas ĠTr aver ser . Admin ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . add ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠV OTE _ TO _ HAL T , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġactive Tra vers ers . isEmpty () Ġ|| ĠWorker Executor . execute ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvertex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSingle Messenger ( messenger , Ġactive Tra vers ers ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Matrix , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmemory , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Hal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ Ġ// ĠI TER ATION Ġ 1 + ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . add ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠV OTE _ TO _ HAL T , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠWorker Executor . execute ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvertex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmess enger , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Matrix , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmemory , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Hal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ// Ġsave Ġspace Ġby Ġnot Ġhaving Ġan Ġempty Ġhal ted Ġtra vers ers Ġproperty ĊĠĠĠĠĠĠĠ Ġif Ġ( return Hal ted Tra vers ers Ġ|| Ġhal ted Tra vers ers . isEmpty ()) Ġvertex .< ĠTr aver ser Set Ġ> Ġproperty Ġ< ĠTr aver ser Set Ġ? Ġ> ĠHAL TED _ TRA VER SER S . remove () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġterminate ( memory : ĠMemory ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġmemory Ġis Ġlocal ĊĠĠĠĠĠĠĠ ĠMemory Traversal Side Effects . set Memory Side Effects ( traversal . get (), Ġmemory , ĠProgram Phase . TERMIN ATE ) ĊĠĠĠĠĠĠĠ Ġval Ġvote To H alt : ĠBoolean Ġ= Ġmemory .< ĠBoolean Ġ> Ġget Ġ< ĠBoolean Ġ? Ġ> ĠV OTE _ TO _ HAL T ĊĠĠĠĠĠĠĠ Ġmemory . set ( V OTE _ TO _ HAL T , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġmemory . set ( ACTIVE _ TRA VER SER S , ĠVertex Indexed Tra verser Set ()) ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( vote To H alt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġlocal Ġtra verser Ġsets Ġto Ġprocess ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġto Process Tra vers ers : ĠTr aver ser Set < Object > Ġ= ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġtra vers ers Ġthat Ġneed Ġto Ġbe Ġsent Ġback Ġto Ġthe Ġworkers Ġ( no Ġlonger Ġcan Ġbe Ġprocessed Ġlocally Ġby Ġthe Ġmaster Ġtraversal ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġremote Active Tra vers ers : ĠIndexed Tra verser Set < Object , ĠVertex > Ġ= ĠVertex Indexed Tra verser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġhal ted Ġtra vers ers Ġthat Ġhave Ġcompleted Ġtheir Ġjourney ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhal ted Tra vers ers : ĠTr aver ser Set < Object > Ġ= Ġmemory . get ( HAL TED _ TRA VER SER S ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġget Ġall Ġbarrier Ġtra vers ers ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcompleted Bar riers : ĠSet < String > Ġ= ĠHashSet () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMaster Executor . process Memory ( traversal Matrix , Ġmemory , Ġto Process Tra vers ers , Ġcompleted Bar riers ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġprocess Ġall Ġresults Ġfrom Ġbar riers Ġlocally Ġand Ġwhen Ġelements Ġare Ġtouched , Ġput Ġthem Ġin Ġremote Active Tra vers ers ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMaster Executor . process Tra vers ers ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Matrix , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġto Process Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremote Active Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra verser Strategy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġtell Ġparallel Ġbar riers Ġthat Ġmight Ġnot Ġhave Ġbeen Ġactive Ġin Ġthe Ġlast Ġround Ġthat Ġthey Ġare Ġno Ġlonger Ġactive ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( COMPLETED _ BAR RI ERS , Ġcompleted Bar riers ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! remote Active Tra vers ers . isEmpty () Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcompleted Bar riers . stream (). map ( traversal Matrix :: get Step ById ). filter Ġ{ Ġstep Ġ-> Ġstep Ġis ĠLocal Barrier Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. find Any (). isPresent () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsend Ġactive Ġtra vers ers Ġback Ġto Ġworkers ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( ACTIVE _ TRA VER SER S , Ġremote Active Tra vers ers ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfinalize Ġlocally Ġwith Ġany Ġlast Ġtra vers ers Ġd angling Ġin Ġthe Ġlocal Ġtraversal ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġend Step : ĠStep < *, ĠObject > Ġ= Ġtraversal . get (). getEnd Step () Ġas ĠStep < *, ĠObject > ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( end Step . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhal ted Tra vers ers . add ( hal ted Tra verser Strategy . halt ( end Step . next ())) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġresult Ġof Ġa ĠTra versal Vertex Program Ġare Ġthe Ġhal ted Ġtra vers ers ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmemory . set ( HAL TED _ TRA VER SER S , Ġhal ted Tra vers ers ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfinalize Ġprofile Ġside - effect Ġsteps . Ġ( todo : Ġtry Ġand Ġhide Ġthis ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( profile Step Ġin ĠTra versal Helper . get Steps Of Assignable Class Re cursively ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠProfile Side Effect Step :: class . java , Ġtraversal . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ)) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). get Side Effects (). set ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprofile Step . get Side Effect Key (), Ġprofile Step . generate Final Result ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). get Side Effects (). get ( profile Step . get Side Effect Key ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġworker Iteration Start ( memory : ĠMemory ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġstart Ġcollecting Ġprofile Ġmetrics ĊĠĠĠĠĠĠĠ Ġif Ġ( profile ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiteration Metrics Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMutable Metrics (" iteration " Ġ+ Ġmemory . get Iteration (), Ġ" Worker ĠIteration Ġ" Ġ+ Ġmemory . get Iteration ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiteration Metrics . start () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġworker Iteration End ( memory : ĠMemory ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġstore Ġprofile Ġmetrics Ġin Ġproper ĠProfile Step Ġmetrics ĊĠĠĠĠĠĠĠ Ġif Ġ( profile ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprofile Steps : ĠList < Profile Step > Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTra versal Helper . get Steps Of Assignable Class Re cursively ( Profile Step :: class . java , Ġtraversal . get ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġguess Ġthe Ġprofile Ġstep Ġto Ġstore Ġdata ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġprofile Step Index : ĠInt Ġ= Ġmemory . get Iteration () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġwe Ġguess Ġwrong ly Ġwrite Ġtiming Ġinto Ġlast Ġstep ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprofile Step Index Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( profile Step Index Ġ>= Ġprofile Steps . size ()) Ġprofile Steps . size () Ġ- Ġ 1 Ġelse Ġprofile Step Index ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiteration Metrics . finish ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreset Ġcounts ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiteration Metrics . set Count ( Traversal Metrics . TRA VER SER _ COUNT _ ID , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( null Ġ!= ĠMemory Traversal Side Effects . get Memory Side Effects Phase ( traversal . get ())) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get (). get Side Effects (). add ( profile Steps [ profile Step Index ]. getId (), Ġiteration Metrics ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiteration Metrics Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ get : Override ĊĠĠĠ Ġval Ġvertex Compute Keys : ĠSet < Any > ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠV ERT EX _ COMPUTE _ KEYS ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġget Memory Compute Keys (): ĠSet < Memory Compute Key > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġmemory Compute Keys ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġget Map Reducers (): ĠSet < Map Reduce > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġmap Reducers ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ get : Override ĊĠĠĠ Ġval Ġmessage Combin er : ĠOptional < Message Combin er < Tra verser Set < Object >>> ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠTra versal Vertex Program Message Combin er . instance () Ġas ĠOptional ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġfun Ġclone (): ĠTra versal Vertex Program Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġclone Ġ= Ġsuper . clone () Ġas ĠTra versal Vertex Program ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclone . traversal Ġ= Ġtraversal . clone () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! clone . traversal . get (). is Locked ()) Ġclone . traversal . get (). apply Str ategies () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclone . traversal Matrix Ġ= ĠTra versal Matrix ( clone . traversal . get ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclone . memory Compute Keys Ġ= ĠHashSet () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( memory Compute Key Ġin Ġmemory Compute Keys ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġclone . memory Compute Keys . add ( memory Compute Key . clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclone ĊĠĠĠĠĠĠĠ Ġ} Ġcatch Ġ( e : ĠClone NotSupportedException ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalStateException ( e . getMessage (), Ġe ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ get : Override ĊĠĠĠ Ġval Ġpreferred Result Graph : ĠResult Graph ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠGraph Computer . Result Graph . ORIGIN AL ĊĊĠĠĠ Ġ@ get : Override ĊĠĠĠ Ġval Ġpreferred Persist : ĠPers ist ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠGraph Computer . Persist . NOTH ING ĊĊĠĠĠ Ġ@ Override ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtraversal String : ĠString Ġ= Ġtraversal . get (). toString (). substring ( 1 ) ĊĠĠĠĠĠĠĠ Ġreturn ĠString Factory . vertex Program String ( this , Ġtraversal String . substring ( 0 , Ġtraversal String . length () Ġ- Ġ 1 )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ get : Override ĊĠĠĠ Ġval Ġfeatures : ĠFeatures ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġobject Ġ: ĠFeatures () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Override ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġrequires Global Message Scopes (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Override ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġrequires Vertex Property Addition (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠBuilder Ġ: ĠAbstract Vertex Program Builder < Builder ? >( ĊĠĠĠĠĠĠĠ ĠTra versal Vertex Program :: class . java ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġhal ted Tra vers ers ( hal ted Tra vers ers : ĠTr aver ser Set < Object >? ): ĠBuilder Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstore Hal ted Tra vers ers < Any >( this . configuration , Ġhal ted Tra vers ers ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġthis ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġtraversal ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Source : ĠTra versal Source ?, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġscript Engine : ĠString ?, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Script : ĠString ?, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar arg Ġbindings : ĠObject ? ĊĠĠĠĠĠĠĠ Ġ): ĠBuilder Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġthis . traversal ( Script Traversal ( traversal Source , Ġscript Engine , Ġtraversal Script , Ġbindings )) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġtraversal ( traversal : ĠTra versal . Admin < *, Ġ* >): ĠBuilder Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthis Ġis Ġnecessary Ġif Ġthe Ġjob Ġwas Ġsubmitted Ġvia ĠTra versal Vertex Program . build () Ġinstead Ġof ĠTra versal Vertex Program Step . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġtraversal : ĠTra versal . Admin < *, Ġ*> Ġ= Ġtraversal ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( traversal . getParent () Ġ! is ĠTra versal Vertex Program Step ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmemory Traversal Side Effects Ġ= ĠMemory Traversal Side Effects ( traversal . get Side Effects ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġparent Traversal : ĠTra versal . Admin < *, Ġ*> Ġ= ĠDefault Traversal () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . get Graph (). if Present ( parent Traversal :: set Graph ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġstrategies : ĠTra versal Str ategies Ġ= Ġtraversal . get Str ategies (). clone () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstrategies . add Str ategies ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠComputer Final ization Strategy . instance (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠComputer Verification Strategy . instance (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠVertex Program Strategy ( Computer . compute ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent Traversal . set Str ategies ( str ategies ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . set Str ategies ( str ategies ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent Traversal . set Side Effects ( memory Traversal Side Effects ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent Traversal . add Step ( Traversal Vertex Program Step ( parent Traversal , Ġtraversal )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal Ġ= Ġ( parent Traversal . getStart Step () Ġas ĠTra versal Vertex Program Step ). getGlobal Children (). get ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraversal . set Side Effects ( memory Traversal Side Effects ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPure Traversal . store State ( this . configuration , ĠTR A VERSAL , Ġtraversal ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġthis ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠTR A VERSAL Ġ= Ġ" gre mlin . traversal Vertex Program . traversal " ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠHAL TED _ TRA VER SER S Ġ= Ġ" gre mlin . traversal Vertex Program . hal ted Tra vers ers " ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠACT IVE _ TRA VER SER S Ġ= Ġ" gre mlin . traversal Vertex Program . active Tra vers ers " ĊĠĠĠĠĠĠĠ Ġprotected Ġconst Ġval ĠMUT ATED _ MEMORY _ KEYS Ġ= Ġ" gre mlin . traversal Vertex Program . mut ated Memory Keys " ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠV OTE _ TO _ HAL T Ġ= Ġ" gre mlin . traversal Vertex Program . vote To H alt " ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠCOMP LETED _ BAR RI ERS Ġ= Ġ" gre mlin . traversal Vertex Program . completed Bar riers " ĊĊĠĠĠĠĠĠĠ Ġ// ĠTODO : Ġif Ġnot Ġan Ġadjacent Ġtraversal , Ġuse ĠLocal Ġmessage Ġscope Ġ-- Ġa Ġdual Ġmessaging Ġsystem . ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠMESSAGE _ SCOPES : ĠSet < Message Scope > Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ ĠHashSet ( Collections . singletonList ( Message Scope . Global . instance ())) ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠV ERT EX _ COMPUTE _ KEYS : ĠSet < Vertex Compute Key > Ġ= ĠHashSet ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠArrays . asList ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠVertex Compute Key . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHAL TED _ TRA VER SER S , Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĠVertex Compute Key . of ( ACTIVE _ TRA VER SER S , Ġtrue ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġfun Ġ< R > Ġload Hal ted Tra vers ers ( configuration : ĠConfiguration ): ĠTr aver ser Set < R > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! configuration . containsKey ( HAL TED _ TRA VER SER S )) Ġreturn ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ` object `: ĠObject Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( configuration . getProperty ( HAL TED _ TRA VER SER S ) Ġis ĠString ) ĠVertex Program Helper . deserialize ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconfiguration , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHAL TED _ TRA VER SER S ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġelse Ġconfiguration . getProperty ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHAL TED _ TRA VER SER S ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(` object ` Ġis ĠTr aver ser . Admin ) ĠTr aver ser Set (` object ` Ġas ĠTr aver ser . Admin < R >) Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtra verser Set : ĠTr aver ser Set < R > Ġ= ĠTr aver ser Set () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtra verser Set . addAll (` object ` Ġas ĠCollection ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtra verser Set ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġ< R > Ġstore Hal ted Tra vers ers ( configuration : ĠConfiguration , Ġhal ted Tra vers ers : ĠTr aver ser Set < R > ?) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( null Ġ!= Ġhal ted Tra vers ers Ġ&& Ġ! hal ted Tra vers ers . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠVertex Program Helper . serialize ( hal ted Tra vers ers , Ġconfiguration , ĠHAL TED _ TRA VER SER S ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġcatch Ġ( e : ĠException ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconfiguration . setProperty ( HAL TED _ TRA VER SER S , Ġhal ted Tra vers ers ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// //////// //// ĊĠĠĠĠĠĠĠ Ġfun Ġbuild (): ĠBuilder Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠBuilder () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }