ptolemy.graph.analysis.strategy
Class FloydWarshallZeroLengthCycleStrategy

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

All Implemented Interfaces:

Analyzer, GraphAnalyzer, ZeroLengthCycleAnalyzer

public class FloydWarshallZeroLengthCycleStrategy
extends CachedStrategy
implements ZeroLengthCycleAnalyzer

Analyzer to check if a given directed graph has a zero cycle using the Floyd-Warshall all pair shortest path algorithm.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia, Nimish Sane

See Also:

ZeroLengthCycleAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private ToDoubleMapping	_edgeLengths
private FloydWarshallAllPairShortestPathStrategy	_strategy

Constructor Summary

FloydWarshallZeroLengthCycleStrategy(Graph graph, ToDoubleMapping edgeLengths)
Constructs negative cycle detection analyzer for a given graph and given edge values.

Method Summary

protected java.lang.Object	_compute() The computation associated with the Floyd-Warshall algorithm.
boolean	hasZeroLengthCycle() Return true if a zero length cycle exists in the graph under analysis.
java.lang.String	toString() Return a description of the analyzer.
boolean	valid() Check for compatibility between the analysis and the given graph.

Methods inherited from class ptolemy.graph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

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

graph

Field Detail

_strategy

private FloydWarshallAllPairShortestPathStrategy _strategy

_edgeLengths

private ToDoubleMapping _edgeLengths

Constructor Detail

FloydWarshallZeroLengthCycleStrategy

public FloydWarshallZeroLengthCycleStrategy(Graph graph,
                                            ToDoubleMapping edgeLengths)

Constructs negative cycle detection analyzer for a given graph and given edge values.

Parameters:

graph - The given graph.

edgeLengths - The lengths associated with the given graph.

Method Detail

hasZeroLengthCycle

public boolean hasZeroLengthCycle()

Return true if a zero length cycle exists in the graph under analysis.

Specified by:

hasZeroLengthCycle in interface ZeroLengthCycleAnalyzer

Returns:

True if the graph has a zero length cycle.

toString

public java.lang.String toString()

Return a description of the analyzer.

Specified by:

toString in interface Analyzer

Overrides:

toString in class CachedStrategy

Returns:

Return a description of the analyzer..

valid

public boolean valid()

Check for compatibility between the analysis and the given graph. A graph needs to be an instance of a DirectedGraph in order to use this algorithm.

Specified by:

valid in interface Analyzer

Returns:

True if the graph is a directed and cyclic graph.

_compute

protected java.lang.Object _compute()

The computation associated with the Floyd-Warshall algorithm.

Overrides:

_compute in class CachedStrategy

Returns:

Return a true Boolean Object if the graph has a negative cycle.