org.shared.parallel

Class LimitedMemoryPolicy<V extends Traversable<V,E>,E extends Edge<V>>

java.lang.Object

org.shared.parallel.LimitedMemoryPolicy<V,E>

Type Parameters:

V - the node type.

E - the edge type.

All Implemented Interfaces:

TraversalPolicy<V,E>

public class LimitedMemoryPolicy<V extends Traversable<V,E>,E extends Edge<V>>
extends Object
implements TraversalPolicy<V,E>

An implementation of TraversalPolicy that attempts to conserve memory usage during parallel execution.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	LimitedMemoryPolicy.PolicyNode An Engine.EngineNode proxy class that aids in the computation of traversal orderings.

Constructor Summary

Constructors

Constructor and Description
LimitedMemoryPolicy() Default constructor.

Method Summary

Methods

Modifier and Type	Method and Description
int	assign(V root) Makes a total ordering and depth assignment to all nodes reachable from the given node.
protected int	assignDepthFirst(LimitedMemoryPolicy.PolicyNode node, Set<LimitedMemoryPolicy.PolicyNode> partiallyVisited, Set<LimitedMemoryPolicy.PolicyNode> completelyVisited, int dfsCtr) A recursive subroutine for assigning traversal orders while traversing the LimitedMemoryPolicy.PolicyNode graph in a depth-first manner.
protected LimitedMemoryPolicy.PolicyNode	longestPath(Traversable<V,E> curr, Map<Traversable<V,E>,LimitedMemoryPolicy.PolicyNode> visitedMap) Sorts a LimitedMemoryPolicy.PolicyNode's children in decreasing order of maximum distance from the source.

Methods inherited from class java.lang.Object

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

Constructor Detail

LimitedMemoryPolicy

public LimitedMemoryPolicy()

Default constructor.

Method Detail

assign

public int assign(V root)

Description copied from interface: TraversalPolicy

Makes a total ordering and depth assignment to all nodes reachable from the given node.

Specified by:

assign in interface TraversalPolicy<V extends Traversable<V,E>,E extends Edge<V>>

Parameters:

root - the given node.

Returns:

the number of nodes visited.

longestPath

protected final LimitedMemoryPolicy.PolicyNode longestPath(Traversable<V,E> curr,
                                         Map<Traversable<V,E>,LimitedMemoryPolicy.PolicyNode> visitedMap)

Sorts a LimitedMemoryPolicy.PolicyNode's children in decreasing order of maximum distance from the source.

assignDepthFirst

protected final int assignDepthFirst(LimitedMemoryPolicy.PolicyNode node,
                   Set<LimitedMemoryPolicy.PolicyNode> partiallyVisited,
                   Set<LimitedMemoryPolicy.PolicyNode> completelyVisited,
                   int dfsCtr)

A recursive subroutine for assigning traversal orders while traversing the LimitedMemoryPolicy.PolicyNode graph in a depth-first manner.