public class BFS extends BaseGASProgram<BFS.VS,BFS.ES,Void> implements IPredecessor<BFS.VS,BFS.ES,Void>
Modifier and Type  Class and Description 

static interface 
BFS.Bindings
Additional
IBindingExtractor.IBinder s exposed by BFS . 
static class 
BFS.ES
Edge state is not used.

static class 
BFS.VS 
Constructor and Description 

BFS() 
Modifier and Type  Method and Description 

BFS.VS 
apply(IGASState<BFS.VS,BFS.ES,Void> state,
org.openrdf.model.Value u,
Void sum)
NOP

Void 
gather(IGASState<BFS.VS,BFS.ES,Void> state,
org.openrdf.model.Value u,
org.openrdf.model.Statement e)
Not used.

List<IBinder<BFS.VS,BFS.ES,Void>> 
getBinderList()
Return a list of interfaces that may be used to extract variable bindings
for the vertices visited by the algorithm.

Factory<org.openrdf.model.Statement,BFS.ES> 
getEdgeStateFactory()
Return a factory for edge state objects or
null if the
IGASProgram does not use edge state (in which case the edge state
will not be allocated or maintained). 
EdgesEnum 
getGatherEdges()
Return the set of edges to which the GATHER is applied for a
directed graph or
EdgesEnum.NoEdges to skip the GATHER
phase. 
FrontierEnum 
getInitialFrontierEnum()
Return the nature of the initial frontier for this algorithm.

EdgesEnum 
getScatterEdges()
Return the set of edges to which the SCATTER is applied for a
directed graph or
EdgesEnum.NoEdges to skip the
SCATTER phase. 
Factory<org.openrdf.model.Value,BFS.VS> 
getVertexStateFactory()
Return a factory for vertex state objects.

void 
initVertex(IGASContext<BFS.VS,BFS.ES,Void> ctx,
IGASState<BFS.VS,BFS.ES,Void> state,
org.openrdf.model.Value u)
Not used.

boolean 
isChanged(IGASState<BFS.VS,BFS.ES,Void> state,
org.openrdf.model.Value u)
Returns
true . 
boolean 
nextRound(IGASContext<BFS.VS,BFS.ES,Void> ctx)
Return
true iff the algorithm should continue. 
void 
prunePaths(IGASContext<BFS.VS,BFS.ES,Void> ctx,
org.openrdf.model.Value[] targetVertices)
Remove any vertices from the visited set that do not line on path that
leads to at least one of the target vertices.

void 
scatter(IGASState<BFS.VS,BFS.ES,Void> state,
IGASScheduler sch,
org.openrdf.model.Value u,
org.openrdf.model.Statement e)
The remote vertex is scheduled for activation unless it has already been
visited.

Void 
sum(IGASState<BFS.VS,BFS.ES,Void> state,
Void left,
Void right)
Not used.

before, getSampleEdgesFilter
public Factory<org.openrdf.model.Value,BFS.VS> getVertexStateFactory()
IGASOptions
Note: A null
value may not be allowed in the visited vertex
map, so if the algorithm does not use vertex state, then the factory
should return a singleton instance each time it is invoked.
getVertexStateFactory
in interface IGASOptions<BFS.VS,BFS.ES,Void>
public Factory<org.openrdf.model.Statement,BFS.ES> getEdgeStateFactory()
BaseGASProgram
null
if the
IGASProgram
does not use edge state (in which case the edge state
will not be allocated or maintained).
The default implementation returns null
. Override this if
the algorithm uses peredge computation state.
getEdgeStateFactory
in interface IGASOptions<BFS.VS,BFS.ES,Void>
getEdgeStateFactory
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
public FrontierEnum getInitialFrontierEnum()
IGASOptions
getInitialFrontierEnum
in interface IGASOptions<BFS.VS,BFS.ES,Void>
public EdgesEnum getGatherEdges()
BaseGASProgram
EdgesEnum.NoEdges
to skip the GATHER
phase. This will be interpreted based on the value reported by
IGASContext#isDirectedTraversal()
.
TODO We may need to set dynamically when visting the vertex in the
frontier rather than having it be a onetime property of the vertex
program.
The default gathers on the EdgesEnum.InEdges
.
getGatherEdges
in interface IGASOptions<BFS.VS,BFS.ES,Void>
getGatherEdges
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
public EdgesEnum getScatterEdges()
BaseGASProgram
EdgesEnum.NoEdges
to skip the
SCATTER phase. This will be interpreted based on the value reported by
IGASContext#isDirectedTraversal()
.
The default scatters on the EdgesEnum.OutEdges
.
getScatterEdges
in interface IGASOptions<BFS.VS,BFS.ES,Void>
getScatterEdges
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
public void initVertex(IGASContext<BFS.VS,BFS.ES,Void> ctx, IGASState<BFS.VS,BFS.ES,Void> state, org.openrdf.model.Value u)
initVertex
in interface IGASProgram<BFS.VS,BFS.ES,Void>
initVertex
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
u
 The vertex.
TODO We do not need both the IGASContext
and the
IGASState
. The latter is available from the former.public Void gather(IGASState<BFS.VS,BFS.ES,Void> state, org.openrdf.model.Value u, org.openrdf.model.Statement e)
gather
in interface IGASProgram<BFS.VS,BFS.ES,Void>
u
 The vertex for which the gather is being performed. The gather
will be invoked for each edge indident on u
(as
specified by IGASOptions.getGatherEdges()
).e
 An edge (s,p,o).Note: by lazily resolving the vertex and/or edge state in the GAS callback methods we avoid eagerly materializing data that we do not need. [Lazy resolution does not work on a cluster. The only available semantics there are lazy resolution of state that was materialized in order to support a gather() or scatter() for a vertex.]
Note: The state associated with the source/target vertex and the edge should all be immutable for the GATHER. The vertex state should only be mutable for the APPLY(). The target vertex state and/or edge state MAY be mutable for the SCATTER, but that depends on the algorithm. How can we get these constraints into the API?
public Void sum(IGASState<BFS.VS,BFS.ES,Void> state, Void left, Void right)
sum
in interface IGASProgram<BFS.VS,BFS.ES,Void>
left
 An edge state accumulant.right
 Another edge state accumulant.Value
implementation of the backend. E.g., Value versus IV.public BFS.VS apply(IGASState<BFS.VS,BFS.ES,Void> state, org.openrdf.model.Value u, Void sum)
apply
in interface IGASProgram<BFS.VS,BFS.ES,Void>
u
 The vertex.sum
 The aggregated accumulate across the edges as computed by
GATHER and SUM or null
if there is no
accumulant (this will happen if the GATHER did not find any
edges to visit).public boolean isChanged(IGASState<BFS.VS,BFS.ES,Void> state, org.openrdf.model.Value u)
true
.isChanged
in interface IGASProgram<BFS.VS,BFS.ES,Void>
isChanged
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
u
 The vertex.public void scatter(IGASState<BFS.VS,BFS.ES,Void> state, IGASScheduler sch, org.openrdf.model.Value u, org.openrdf.model.Statement e)
Note: We are scattering to outedges. Therefore, this vertex is
Statement.getSubject()
. The remote vertex is
Statement.getObject()
.
scatter
in interface IGASProgram<BFS.VS,BFS.ES,Void>
u
 The vertex for which the scatter will being performed.e
 The edge.public boolean nextRound(IGASContext<BFS.VS,BFS.ES,Void> ctx)
BaseGASProgram
true
iff the algorithm should continue. This is
invoked after every iteration, once the new frontier has been computed
and IGASState.round()
has been advanced. An implementation may
simply return true
, in which case the algorithm will
continue IFF the current frontier is not empty.
Note: While this can be used to make custom decisions concerning the
halting criteria, it can also be used as an opportunity to handshake with
a custom IGraphAccessor
in order to process a dynamic graph.
The default returns true
.
nextRound
in interface IGASProgram<BFS.VS,BFS.ES,Void>
nextRound
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
ctx
 The evaluation context.true
if the algorithm should continue (as long as
the frontier is nonempty).public List<IBinder<BFS.VS,BFS.ES,Void>> getBinderList()
getBinderList
in interface IBindingExtractor<BFS.VS,BFS.ES,Void>
getBinderList
in class BaseGASProgram<BFS.VS,BFS.ES,Void>
public void prunePaths(IGASContext<BFS.VS,BFS.ES,Void> ctx, org.openrdf.model.Value[] targetVertices)
IPredecessor
prunePaths
in interface IPredecessor<BFS.VS,BFS.ES,Void>
ctx
 The IGASContext
.targetVertices
 An array of zero or more target vertices.Copyright © 2006–2016 SYSTAP, LLC DBA Blazegraph. All rights reserved.