com.bigdata.rdf.graph.impl

Class BaseGASProgram<VS,ES,ST>

java.lang.Object

com.bigdata.rdf.graph.impl.BaseGASProgram<VS,ES,ST>

Type Parameters:

VS -

ES -

ST -

All Implemented Interfaces:

IBindingExtractor<VS,ES,ST>, IGASOptions<VS,ES,ST>, IGASProgram<VS,ES,ST>

Direct Known Subclasses:

BFS, CC, PATHS, PR, SSSP

public abstract class BaseGASProgram<VS,ES,ST>
extends Object
implements IGASProgram<VS,ES,ST>

Abstract base class with some useful defaults.

Author:

Bryan Thompson

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	BaseGASProgram.Bindings Interface declares symbolic constants for the IBindingExtractor.IBinders reported by getBinderList().

Constructor Summary

Constructors

Constructor and Description
BaseGASProgram()

Method Summary

Methods

Modifier and Type	Method and Description
void	before(IGASContext<VS,ES,ST> ctx) One time initialization before the IGASProgram is executed.
List<IBinder<VS,ES,ST>>	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,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.
EdgesEnum	getSampleEdgesFilter() Return the type of edges that must exist when sampling the vertices of the graph.
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.
void	initVertex(IGASContext<VS,ES,ST> ctx, IGASState<VS,ES,ST> state, org.openrdf.model.Value u) Callback to initialize the state for each vertex in the initial frontier before the first iteration.
boolean	isChanged(IGASState<VS,ES,ST> state, org.openrdf.model.Value u) Return true iff the vertex should run its SCATTER phase.
boolean	nextRound(IGASContext<VS,ES,ST> ctx) Return true iff the algorithm should continue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.bigdata.rdf.graph.IGASProgram

apply, gather, scatter, sum

Methods inherited from interface com.bigdata.rdf.graph.IGASOptions

getInitialFrontierEnum, getVertexStateFactory

Constructor Detail

BaseGASProgram

public BaseGASProgram()

Method Detail

getSampleEdgesFilter

public EdgesEnum getSampleEdgesFilter()

Return the type of edges that must exist when sampling the vertices of the graph. If EdgesEnum.InEdges is specified, then each sampled vertex will have at least one in-edge. If EdgesEnum.OutEdges is specified, then each sampled vertex will have at least one out-edge. To sample all vertices regardless of their edges, specify . To require that each vertex has at least one in-edge and one out-edge, specify EdgesEnum.AllEdges. FIXME This should be moved into GASRunnerBase. The only class that customizes this is CC. (For CC we need to put all vertices into the frontier, even those without edges.)

The default implementation returns getGatherEdges() and the getScatterEdges() if getGatherEdges() returns . TODO This ignores IGASContext#isDirectedTraversal()

Specified by:

getSampleEdgesFilter in interface IGASOptions<VS,ES,ST>

getGatherEdges

public 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. 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 one-time property of the vertex program.

The default gathers on the EdgesEnum.InEdges.

Specified by:

getGatherEdges in interface IGASOptions<VS,ES,ST>

getScatterEdges

public 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. This will be interpreted based on the value reported by IGASContext#isDirectedTraversal().

The default scatters on the EdgesEnum.OutEdges.

Specified by:

getScatterEdges in interface IGASOptions<VS,ES,ST>

before

public void before(IGASContext<VS,ES,ST> ctx)

One time initialization before the IGASProgram is executed.

The default implementation populates the frontier IFF this is an FrontierEnum.AllVertices IGASProgram.

Specified by:

before in interface IGASProgram<VS,ES,ST>

Parameters:

ctx - The evaluation context.

initVertex

public void initVertex(IGASContext<VS,ES,ST> ctx,
              IGASState<VS,ES,ST> state,
              org.openrdf.model.Value u)

Callback to initialize the state for each vertex in the initial frontier before the first iteration. A typical use case is to set the distance of the starting vertex to ZERO (0).

The default is a NOP.

Specified by:

initVertex in interface IGASProgram<VS,ES,ST>

u - The vertex. TODO We do not need both the IGASContext and the IGASState. The latter is available from the former.

getEdgeStateFactory

public Factory<org.openrdf.model.Statement,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).

The default implementation returns null. Override this if the algorithm uses per-edge computation state.

Specified by:

getEdgeStateFactory in interface IGASOptions<VS,ES,ST>

isChanged

public boolean isChanged(IGASState<VS,ES,ST> state,
                org.openrdf.model.Value u)

Return true iff the vertex should run its SCATTER phase. This may be used to avoid visiting the edges if it is known (e.g., based on the APPLY) that the vertex has not changed. This can save a substantial amount of effort.

The default implementation returns true. Override this if you know whether or not the computation state of this vertex has changed.

Specified by:

isChanged in interface IGASProgram<VS,ES,ST>

u - The vertex.

Returns:

nextRound

public boolean nextRound(IGASContext<VS,ES,ST> ctx)

Return 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.

Specified by:

nextRound in interface IGASProgram<VS,ES,ST>

Parameters:

ctx - The evaluation context.

Returns:

true if the algorithm should continue (as long as the frontier is non-empty).

getBinderList

public List<IBinder<VS,ES,ST>> getBinderList()

Return a list of interfaces that may be used to extract variable bindings for the vertices visited by the algorithm.

The visited vertex itself.

Specified by:

getBinderList in interface IBindingExtractor<VS,ES,ST>