com.bigdata.rdf.graph.analytics

Class CC

java.lang.Object

com.bigdata.rdf.graph.impl.BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

com.bigdata.rdf.graph.analytics.CC

All Implemented Interfaces:

IBindingExtractor<CC.VS,CC.ES,org.openrdf.model.Value>, IGASOptions<CC.VS,CC.ES,org.openrdf.model.Value>, IGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

public class CC
extends BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

Connected components computes the distinct sets of non-overlapping subgraphs within a graph. All vertices within a connected component are connected along at least one path.

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 one-hop neighhor's labels. The algorithm halts when no vertex label has changed state in a given iteration.

init

All vertices are inserted into the initial frontier.

Gather

Report the source vertex label (not its identifier)

Apply

label = min(label,gatherLabel)

Scatter

iff the label has changed

FIXME CC : Implement version that pushes updates through the scatter function. Find an abstraction to support this pattern. It is used by both CC and SSSP. (We can initially implement this as a Gather (over all edges) plus a conditional Scatter (over all edges iff the vertex label has changed). We can then refactor both this class and SSSP to push the updates through a Scatter (what I think of as a Gather to a remote vertex).)

Author:

Bryan Thompson

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	CC.Bindings Additional IBindingExtractor.IBinders 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 Summary

Constructors

Constructor and Description
CC()

Method Summary

Methods

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

Methods inherited from class com.bigdata.rdf.graph.impl.BaseGASProgram

before, initVertex, nextRound

Methods inherited from class java.lang.Object

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

Constructor Detail

CC

public CC()

Method Detail

getVertexStateFactory

public Factory<org.openrdf.model.Value,CC.VS> getVertexStateFactory()

Description copied from interface: IGASOptions

Return a factory for vertex state objects.

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.

getEdgeStateFactory

public Factory<org.openrdf.model.Statement,CC.ES> getEdgeStateFactory()

Description copied from class: BaseGASProgram

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<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

getEdgeStateFactory in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

getInitialFrontierEnum

public FrontierEnum getInitialFrontierEnum()

Description copied from interface: IGASOptions

Return the nature of the initial frontier for this algorithm.

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

Specified by:

getSampleEdgesFilter in interface IGASOptions<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

getSampleEdgesFilter in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

getGatherEdges

public EdgesEnum getGatherEdges()

Description copied from class: BaseGASProgram

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<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

getGatherEdges in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

getScatterEdges

public EdgesEnum getScatterEdges()

Description copied from class: BaseGASProgram

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<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

getScatterEdges in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

gather

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)

GATHER is a map/reduce over the edges of the vertex. The SUM provides pair-wise reduction over the edges visited by the GATHER.

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

Returns:

The new edge state accumulant. FIXME DESIGN: The problem with pushing the ISPO onto the ES is that we are then forced to maintain edge state (for the purposes of accessing those ISPO references) even if the algorithm does not require any memory for the edge state!

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?

sum

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)

MIN

SUM is a pair-wise reduction that is applied during the GATHER.

left - An edge state accumulant.

right - Another edge state accumulant.

Returns:

Their "sum". TODO DESIGN: Rather than pair-wise reduction, why not use vectored reduction? That way we could use an array of primitives as well as objects. TODO DESIGN: This should be a reduced interface since we only need access to the comparator semantics while the [state] provides random access to vertex and edge state. The comparator is necessary for MIN semantics for the Value implementation of the backend. E.g., Value versus IV.

apply

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

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

Returns:

The new state for the vertex. TODO How to indicate if there is no state change? return the same object? This only matters with secondary storage for the vertex state. Alternative is to side-effect the vertex state, but then we can not manage the barriers (BFS versus asynchronous). Except for indicating that the state is dirty, we do not need a return value. [The pattern appears to be that a vertex leaves a marker on its vertex state object indicating whether or not it was changed and then tests that state when deciding whether or not to scatter]. TODO There could be a big win here if we are able to detect when a newly initialized vertex state does not "escape" and simply not store it. For some graphs, the vertexState map grows very rapidly when compared to either the frontier or the set of states that have been in the frontier during the computation.

isChanged

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

Specified by:

isChanged in interface IGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

isChanged in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

u - The vertex.

Returns:

scatter

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)

The remote vertex is scheduled for activation unless it has already been visited.

u - The vertex for which the scatter will being performed.

e - The edge.

getBinderList

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

The visited vertex itself.

The label associated with all of the vertices in the same subgraph. The label is a vertex identifier and can be used to jump into the subgraph.

Specified by:

getBinderList in interface IBindingExtractor<CC.VS,CC.ES,org.openrdf.model.Value>

Overrides:

getBinderList in class BaseGASProgram<CC.VS,CC.ES,org.openrdf.model.Value>

getConnectedComponents

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