com.bigdata.rdf.graph.analytics

Class SSSP

java.lang.Object

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

com.bigdata.rdf.graph.analytics.SSSP

All Implemented Interfaces:

IBindingExtractor<SSSP.VS,SSSP.ES,Integer>, IGASOptions<SSSP.VS,SSSP.ES,Integer>, IGASProgram<SSSP.VS,SSSP.ES,Integer>, IPredecessor<SSSP.VS,SSSP.ES,Integer>

public class SSSP
extends BaseGASProgram<SSSP.VS,SSSP.ES,Integer>
implements IPredecessor<SSSP.VS,SSSP.ES,Integer>

SSSP (Single Source, Shortest Path). This analytic computes the shortest path to each connected vertex in the graph starting from the given vertex. Only connected vertices are visited by this implementation (the frontier never leaves the connected component in which the starting vertex is located).

Author:

Bryan Thompson FIXME Add a reducer to report the actual minimum length paths. This is similar to a BFS tree, but the path lengths are not integer values so we need a different data structure to collect them (we need to store the predecesor when we run SSSP to do this).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	SSSP.Bindings Additional IBindingExtractor.IBinders exposed by SSSP.
static class	SSSP.ES Edge state is not used.
static class	SSSP.VS

Constructor Summary

Constructors

Constructor and Description
SSSP()

Method Summary

Methods

Modifier and Type	Method and Description
SSSP.VS	apply(IGASState<SSSP.VS,SSSP.ES,Integer> state, org.openrdf.model.Value u, Integer sum) NOP.
Integer	gather(IGASState<SSSP.VS,SSSP.ES,Integer> state, org.openrdf.model.Value u, org.openrdf.model.Statement e) src.dist + edge_length (1)
List<IBinder<SSSP.VS,SSSP.ES,Integer>>	getBinderList() Return a list of interfaces that may be used to extract variable bindings for the vertices visited by the algorithm.
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,SSSP.VS>	getVertexStateFactory() Return a factory for vertex state objects.
void	initVertex(IGASContext<SSSP.VS,SSSP.ES,Integer> ctx, IGASState<SSSP.VS,SSSP.ES,Integer> state, org.openrdf.model.Value u) Set the SSSP.VS.dist() to ZERO (0).
boolean	nextRound(IGASContext<SSSP.VS,SSSP.ES,Integer> ctx) Return true iff the algorithm should continue.
void	prunePaths(IGASContext<SSSP.VS,SSSP.ES,Integer> 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<SSSP.VS,SSSP.ES,Integer> state, IGASScheduler sch, org.openrdf.model.Value u, org.openrdf.model.Statement e) The remote vertex is scheduled the weighted edge from this vertex to the remote vertex plus the weight on this vertex is less than the weight on the remote vertex.
Integer	sum(IGASState<SSSP.VS,SSSP.ES,Integer> state, Integer left, Integer right) UNUSED.

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

before, getEdgeStateFactory, getSampleEdgesFilter, isChanged

Methods inherited from class java.lang.Object

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

Constructor Detail

SSSP

public SSSP()

Method Detail

getVertexStateFactory

public Factory<org.openrdf.model.Value,SSSP.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.

Specified by:

getVertexStateFactory in interface IGASOptions<SSSP.VS,SSSP.ES,Integer>

getInitialFrontierEnum

public FrontierEnum getInitialFrontierEnum()

Description copied from interface: IGASOptions

Return the nature of the initial frontier for this algorithm.

Specified by:

getInitialFrontierEnum in interface IGASOptions<SSSP.VS,SSSP.ES,Integer>

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<SSSP.VS,SSSP.ES,Integer>

Overrides:

getGatherEdges in class BaseGASProgram<SSSP.VS,SSSP.ES,Integer>

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<SSSP.VS,SSSP.ES,Integer>

Overrides:

getScatterEdges in class BaseGASProgram<SSSP.VS,SSSP.ES,Integer>

initVertex

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

Set the SSSP.VS.dist() to ZERO (0).

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<SSSP.VS,SSSP.ES,Integer>

Overrides:

initVertex in class BaseGASProgram<SSSP.VS,SSSP.ES,Integer>

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

gather

public Integer gather(IGASState<SSSP.VS,SSSP.ES,Integer> state,
             org.openrdf.model.Value u,
             org.openrdf.model.Statement e)

src.dist + edge_length (1)

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

Specified by:

gather in interface IGASProgram<SSSP.VS,SSSP.ES,Integer>

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 Integer sum(IGASState<SSSP.VS,SSSP.ES,Integer> state,
          Integer left,
          Integer right)

UNUSED.

Specified by:

sum in interface IGASProgram<SSSP.VS,SSSP.ES,Integer>

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 SSSP.VS apply(IGASState<SSSP.VS,SSSP.ES,Integer> state,
            org.openrdf.model.Value u,
            Integer sum)

NOP.

Specified by:

apply in interface IGASProgram<SSSP.VS,SSSP.ES,Integer>

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.

scatter

public void scatter(IGASState<SSSP.VS,SSSP.ES,Integer> state,
           IGASScheduler sch,
           org.openrdf.model.Value u,
           org.openrdf.model.Statement e)

The remote vertex is scheduled the weighted edge from this vertex to the remote vertex plus the weight on this vertex is less than the weight on the remote vertex.

Specified by:

scatter in interface IGASProgram<SSSP.VS,SSSP.ES,Integer>

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

e - The edge.

nextRound

public boolean nextRound(IGASContext<SSSP.VS,SSSP.ES,Integer> ctx)

Description copied from class: BaseGASProgram

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<SSSP.VS,SSSP.ES,Integer>

Overrides:

nextRound in class BaseGASProgram<SSSP.VS,SSSP.ES,Integer>

Parameters:

ctx - The evaluation context.

Returns:

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

getBinderList

public List<IBinder<SSSP.VS,SSSP.ES,Integer>> 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.

1

The shortest distance from the initial frontier to the vertex.

Specified by:

getBinderList in interface IBindingExtractor<SSSP.VS,SSSP.ES,Integer>

Overrides:

getBinderList in class BaseGASProgram<SSSP.VS,SSSP.ES,Integer>

prunePaths

public void prunePaths(IGASContext<SSSP.VS,SSSP.ES,Integer> ctx,
              org.openrdf.model.Value[] targetVertices)

Description copied from interface: IPredecessor

Remove any vertices from the visited set that do not line on path that leads to at least one of the target vertices.

Specified by:

prunePaths in interface IPredecessor<SSSP.VS,SSSP.ES,Integer>

Parameters:

ctx - The IGASContext.

targetVertices - An array of zero or more target vertices.