public class CC extends BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
The implementation works by assigning a label to each vertex. The label is initially the vertex identifier for that vertex. The labels in the graph are then relaxed with each vertex taking the minimum of its onehop neighhor's labels. The algorithm halts when no vertex label has changed state in a given iteration.
Modifier and Type  Class and Description 

static interface 
CC.Bindings
Additional
IBindingExtractor.IBinder s exposed by CC . 
class 
CC.ConnectedComponentsReducer
Returns a map containing the labels assigned to each connected component
(which gives you a vertex in that connected component) and the #of
vertices in each connected component.

static class 
CC.ES
Edge state is not used.

static class 
CC.VS 
Constructor and Description 

CC() 
Modifier and Type  Method and Description 

CC.VS 
apply(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state,
org.openrdf.model.Value u,
org.openrdf.model.Value sum)
Apply the reduced aggregation computed by GATHER + SUM to the vertex.

org.openrdf.model.Value 
gather(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state,
org.openrdf.model.Value u,
org.openrdf.model.Statement e)
GATHER is a map/reduce over the edges of the vertex.

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

Map<org.openrdf.model.Value,AtomicInteger> 
getConnectedComponents(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state)
Returns a map containing the labels assigned to each connected component
(which gives you a vertex in that connected component) and the #of
vertices in each connected component.

Factory<org.openrdf.model.Statement,CC.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 
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. 
Factory<org.openrdf.model.Value,CC.VS> 
getVertexStateFactory()
Return a factory for vertex state objects.

boolean 
isChanged(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state,
org.openrdf.model.Value u)
Return
true iff the vertex should run its SCATTER phase. 
void 
scatter(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> 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.

org.openrdf.model.Value 
sum(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state,
org.openrdf.model.Value left,
org.openrdf.model.Value right)
MIN

before, initVertex, nextRound
public Factory<org.openrdf.model.Value,CC.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.
public Factory<org.openrdf.model.Statement,CC.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<CC.VS,CC.ES,org.openrdf.model.Value>
getEdgeStateFactory
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
public FrontierEnum getInitialFrontierEnum()
IGASOptions
public EdgesEnum getSampleEdgesFilter()
EdgesEnum.InEdges
is specified, then each sampled
vertex will have at least one inedge. If EdgesEnum.OutEdges
is
specified, then each sampled vertex will have at least one outedge. To
sample all vertices regardless of their edges, specify
. To require that each vertex has at least one
inedge and one outedge, 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 BaseGASProgram.getGatherEdges()
and the
BaseGASProgram.getScatterEdges()
if BaseGASProgram.getGatherEdges()
returns
.
TODO This ignores IGASContext#isDirectedTraversal()
Overridden to not impose any filter on the sampled vertices (it does not matter whether they have any connected edges since we need to put all vertices into the initial frontier).
getSampleEdgesFilter
in interface IGASOptions<CC.VS,CC.ES,org.openrdf.model.Value>
getSampleEdgesFilter
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
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<CC.VS,CC.ES,org.openrdf.model.Value>
getGatherEdges
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
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<CC.VS,CC.ES,org.openrdf.model.Value>
getScatterEdges
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
public org.openrdf.model.Value gather(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state, org.openrdf.model.Value u, org.openrdf.model.Statement e)
Return the label of the remote vertex.
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 org.openrdf.model.Value sum(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state, org.openrdf.model.Value left, org.openrdf.model.Value right)
SUM is a pairwise reduction that is applied during the GATHER.
left
 An edge state accumulant.right
 Another edge state accumulant.Value
implementation of the backend. E.g., Value versus IV.public CC.VS apply(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state, org.openrdf.model.Value u, org.openrdf.model.Value sum)
Compute the new value for this vertex, making a note of the last change for this vertex.
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<CC.VS,CC.ES,org.openrdf.model.Value> state, org.openrdf.model.Value u)
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.
Returns true
iff the label was changed in the current round.
isChanged
in interface IGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
isChanged
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
u
 The vertex.public void scatter(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state, IGASScheduler sch, org.openrdf.model.Value u, org.openrdf.model.Statement e)
u
 The vertex for which the scatter will being performed.e
 The edge.public List<IBinder<CC.VS,CC.ES,org.openrdf.model.Value>> getBinderList()
getBinderList
in interface IBindingExtractor<CC.VS,CC.ES,org.openrdf.model.Value>
getBinderList
in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>
public Map<org.openrdf.model.Value,AtomicInteger> getConnectedComponents(IGASState<CC.VS,CC.ES,org.openrdf.model.Value> state)
Copyright © 2006–2016 SYSTAP, LLC DBA Blazegraph. All rights reserved.