ptolemy.graph.analysis.strategy
Class CachedStrategy

java.lang.Object
  ptolemy.graph.analysis.strategy.Strategy
      ptolemy.graph.analysis.strategy.CachedStrategy

All Implemented Interfaces:

Analyzer, GraphAnalyzer

Direct Known Subclasses:

AllEdgeSingleSourceLongestPathStrategy, ClusterNodesTransformerStrategy, FloydWarshallCycleExistenceStrategy, FloydWarshallNegativeLengthCycleStrategy, FloydWarshallStrategy, FloydWarshallZeroLengthCycleStrategy, KarpCycleMeanStrategy, MirrorTransformerStrategy, ParhiMaximumProfitToCostRatioStrategy, SelfLoopStrategy, SinkNodeStrategy, SourceNodeStrategy

public abstract class CachedStrategy
extends Strategy
implements GraphAnalyzer

A base class for cached analyzers on graphs. To facilitate demand-driven and incremental recomputation (e.g., see [1]) of analyzers, analyzer results are cached internally (see getCachedResult()), and are recomputed only when the graph has changed since the last request (via _result()) for the strategy result. The status of the cache content can be queried with the obsolete() method to determine if a subsequent invocation of _result() by the derived classes will trigger recomputation of the analysis.

The graph changes tracked by an analyzer are restricted to changes in the graph topology (the set of nodes and edges). For example, changes to edge/node weights that may affect the result of an analysis are not tracked, since analyzers have no specific knowledge of weights. In such cases, it is the responsibility of the client (or derived analyzer class) to invalidate the cached result (see reset()) when changes to graph weights or other non-topology information render the cached result obsolete. For this reason, some caution is generally required when using analyzers whose results depend on more than just the graph topology.

In these cases the client should check for data consistency (through the Analyzer.valid() method) as well as changes in them and calling the reset() method in case of data changes.

[1] G. Ramalingam. Bounded Incremental Computation. PhD thesis, University of Wisconsin at Madison, August 1993.

Since:

Ptolemy II 4.0

Version:

$Id: CachedStrategy.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shuvra S. Bhattacharyya, Ming Yung Ko and Shahrooz Shahparnia

Accepted Rating:

Red (cxh)

Proposed Rating:

Red (cxh)

Field Summary

private java.lang.Object	_cachedResult
private boolean	_cachingEnabled
private Graph	_graph
private long	_lastComputation

Constructor Summary

CachedStrategy(Graph graph)
No instance of this object can be created as it is abstract.

Method Summary

protected java.lang.Object	_compute() Perform the graph analysis and return the resulting value.
protected java.lang.Object	_convertResult(java.lang.Object result) Convert the cached result (getCachedResult()) to a form that is suitable for the client to access (via _result()).
private void	_registerComputation() Notify the analyzer that the associated computation has been performed.
protected java.lang.Object	_result() Return the result (cached value) of the analyzer on the associated graph.
boolean	cachingStatus() Return the caching status of the strategy.
void	disableCaching() Disable caching.
void	enableCaching() Enable caching.
java.lang.Object	getCachedResult() The result of the most recent cached computation of the analysis, as determined by _compute(), and without conversion by _convertResult(Object).
Graph	graph() The graph associated with the Strategy.
boolean	obsolete() Test whether or not the cached result of the analyzer is obsolete relative to the associated graph.
void	reset() Reset the analyzer to invalidate any cached value (i.e., to force recomputation the next time a result of the computation is needed).
void	setCachedResult(CachedStrategy cacher) Set the cached value of this analyzer to the cached value of another analyzer.
java.lang.String	toString() Return a description of the strategy.

Methods inherited from class java.lang.Object

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

Methods inherited from interface ptolemy.graph.analysis.analyzer.Analyzer

valid

Field Detail

_cachedResult

private java.lang.Object _cachedResult

_graph

private Graph _graph

_lastComputation

private long _lastComputation

_cachingEnabled

private boolean _cachingEnabled

Constructor Detail

CachedStrategy

public CachedStrategy(Graph graph)

No instance of this object can be created as it is abstract. The derived classes will use it to initialize its internal data structures.

Parameters:

graph - The graph which the analyzer is using to compute its result.

Method Detail

cachingStatus

public boolean cachingStatus()

Return the caching status of the strategy.

Returns:

True if caching is enabled (default on instantiation)

disableCaching

public void disableCaching()

Disable caching.

enableCaching

public void enableCaching()

Enable caching.

getCachedResult

public java.lang.Object getCachedResult()

The result of the most recent cached computation of the analysis, as determined by _compute(), and without conversion by _convertResult(Object).

Returns:

The result of the most recent cached computation.

See Also:

setCachedResult(CachedStrategy)

graph

public Graph graph()

The graph associated with the Strategy. This association is made when the Strategy is constructed.

Specified by:

graph in interface GraphAnalyzer

Returns:

The input graph.

obsolete

public boolean obsolete()

Test whether or not the cached result of the analyzer is obsolete relative to the associated graph. In other words, test if the graph has changed since the last time the analyzer was executed with an enabled cache (i.e., since the most recent invocation of _result()). If the cached result is obsolete and the cache is enabled, then a subsequent invocation of _result() will trigger recomputation of the analysis.

Returns:

True if the cached result is obsolete relative to the associated graph.

reset

public void reset()

Reset the analyzer to invalidate any cached value (i.e., to force recomputation the next time a result of the computation is needed).

setCachedResult

public void setCachedResult(CachedStrategy cacher)

Set the cached value of this analyzer to the cached value of another analyzer.

Parameters:

cacher - The other analyzer.

See Also:

getCachedResult()

toString

public java.lang.String toString()

Return a description of the strategy.

Specified by:

toString in interface Analyzer

Overrides:

toString in class java.lang.Object

Returns:

Return a description of the strategy.

_compute

protected java.lang.Object _compute()

Perform the graph analysis and return the resulting value. Upon entry, getCachedResult() provides the result of the previous invocation of the analysis; this value can be used, for example, to facilitate incremental analyses. This method just returns null, and will typically be overridden in each derived class to perform the appropriate graph analysis.

Returns:

The results of the graph analysis. In this base class, null is returned.

_convertResult

protected java.lang.Object _convertResult(java.lang.Object result)

Convert the cached result (getCachedResult()) to a form that is suitable for the client to access (via _result()). This base class method just returns a reference to the cached result. However, it may be appropriate for derived classes to override this method. For example, if the object returned by the analyzer is mutable, one may wish to override this method to copy the cached value (or convert it to some other form) before returning it. Then changes made by the client to the returned value will not affect the cached value in the analysis. This consideration is important for incremental analyzers that use the cached value across successive invocations of the analyzer.

Parameters:

result - The cached result to be converted.

Returns:

The form suitable for access via _result().

_result

protected final java.lang.Object _result()

Return the result (cached value) of the analyzer on the associated graph. The cached value is updated, through recomputation of the analysis (using _compute()), if the graph has changed since the last time _result() was invoked. Otherwise, the cache value is simply returned (in O(1) time).

Returns:

The result of the analysis.

_registerComputation

private void _registerComputation()

Notify the analyzer that the associated computation has been performed. This method should be called immediately after any invocation of the computation, if caching is enabled and the graph is changed.