public class PR extends BaseGASProgram<PR.VS,PR.ES,Double>
double
precision). Thus, page rank is
typically executed a specific number of iterations, e.g., 50 or 100. If
convergence is based on epsilon, then it is possible that the computation
will never converge, especially for smaller values of epsilon.
(fabs(oldnew) GT
epsilon)
; or (b) iterations LT limitModifier and Type  Class and Description 

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

class 
PR.PageRankReducer
Class reports a map containing the page rank associated with each visited
vertex.

static class 
PR.VS 
Modifier and Type  Field and Description 

protected static double 
DEFAULT_EPSILON 
protected static int 
DEFAULT_LIMIT 
protected static double 
DEFAULT_MIN_PAGE_RANK 
protected static double 
DEFAULT_RESET_PROB 
Constructor and Description 

PR() 
Modifier and Type  Method and Description 

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

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

List<IBinder<PR.VS,PR.ES,Double>> 
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,PR.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,PR.VS> 
getVertexStateFactory()
Return a factory for vertex state objects.

void 
initVertex(IGASContext<PR.VS,PR.ES,Double> ctx,
IGASState<PR.VS,PR.ES,Double> 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<PR.VS,PR.ES,Double> state,
org.openrdf.model.Value u)
Return
true iff the vertex should run its SCATTER phase. 
boolean 
nextRound(IGASContext<PR.VS,PR.ES,Double> ctx)
Return
true iff the algorithm should continue. 
void 
scatter(IGASState<PR.VS,PR.ES,Double> 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.

Double 
sum(IGASState<PR.VS,PR.ES,Double> state,
Double left,
Double right)
SUM

before, getSampleEdgesFilter
protected static final int DEFAULT_LIMIT
protected static final double DEFAULT_RESET_PROB
protected static final double DEFAULT_EPSILON
protected static final double DEFAULT_MIN_PAGE_RANK
public Factory<org.openrdf.model.Value,PR.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,PR.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<PR.VS,PR.ES,Double>
getEdgeStateFactory
in class BaseGASProgram<PR.VS,PR.ES,Double>
public FrontierEnum getInitialFrontierEnum()
IGASOptions
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<PR.VS,PR.ES,Double>
getGatherEdges
in class BaseGASProgram<PR.VS,PR.ES,Double>
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<PR.VS,PR.ES,Double>
getScatterEdges
in class BaseGASProgram<PR.VS,PR.ES,Double>
public void initVertex(IGASContext<PR.VS,PR.ES,Double> ctx, IGASState<PR.VS,PR.ES,Double> state, org.openrdf.model.Value u)
The default is a NOP.
Each vertex is initialized to the reset probability. FIXME We need to do this efficiently. E.g., using a scan to find all of the vertices together with their indegree or outdegree. That should be done to populate the frontier, initializing the #of outedges at the same time.
initVertex
in interface IGASProgram<PR.VS,PR.ES,Double>
initVertex
in class BaseGASProgram<PR.VS,PR.ES,Double>
u
 The vertex.
TODO We do not need both the IGASContext
and the
IGASState
. The latter is available from the former.public Double gather(IGASState<PR.VS,PR.ES,Double> state, org.openrdf.model.Value u, org.openrdf.model.Statement e)
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 Double sum(IGASState<PR.VS,PR.ES,Double> state, Double left, Double 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 PR.VS apply(IGASState<PR.VS,PR.ES,Double> state, org.openrdf.model.Value u, Double 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<PR.VS,PR.ES,Double> 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 last change was greater then epsilon.
isChanged
in interface IGASProgram<PR.VS,PR.ES,Double>
isChanged
in class BaseGASProgram<PR.VS,PR.ES,Double>
u
 The vertex.public void scatter(IGASState<PR.VS,PR.ES,Double> 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()
.
u
 The vertex for which the scatter will being performed.e
 The edge.public boolean nextRound(IGASContext<PR.VS,PR.ES,Double> ctx)
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
.
Continue unless the iteration limit has been reached.
nextRound
in interface IGASProgram<PR.VS,PR.ES,Double>
nextRound
in class BaseGASProgram<PR.VS,PR.ES,Double>
ctx
 The evaluation context.true
if the algorithm should continue (as long as
the frontier is nonempty).public List<IBinder<PR.VS,PR.ES,Double>> getBinderList()
getBinderList
in interface IBindingExtractor<PR.VS,PR.ES,Double>
getBinderList
in class BaseGASProgram<PR.VS,PR.ES,Double>
Copyright © 2006–2019 SYSTAP, LLC DBA Blazegraph. All rights reserved.