Package ptolemy.graph.analysis.strategy

Class FloydWarshallZeroLengthCycleStrategy

java.lang.Object

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$

Author:

Shahrooz Shahparnia, Nimish Sane

See Also:

ZeroLengthCycleAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
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

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.