Package ptolemy.graph.analysis.strategy

Class FloydWarshallNegativeLengthCycleStrategy

java.lang.Object

ptolemy.graph.analysis.strategy.CachedStrategy

ptolemy.graph.analysis.strategy.FloydWarshallNegativeLengthCycleStrategy

All Implemented Interfaces:

Analyzer, GraphAnalyzer, NegativeLengthCycleAnalyzer

public class FloydWarshallNegativeLengthCycleStrategy
extends CachedStrategy
implements NegativeLengthCycleAnalyzer

Analyzer to check if a given directed graph has a negative cycle using the Floyd-Warshall all pair shortest path algorithm. The complexity of this algorithm is O(N^3), where N is the number of nodes.

Since:

Ptolemy II 4.0

Version:

$Id$

Author:

Shahrooz Shahparnia

See Also:

NegativeLengthCycleAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

Constructor	Description
FloydWarshallNegativeLengthCycleStrategy(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	hasNegativeLengthCycle()	Return true if a negative 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

FloydWarshallNegativeLengthCycleStrategy

public FloydWarshallNegativeLengthCycleStrategy(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

hasNegativeLengthCycle

public boolean hasNegativeLengthCycle()

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

Specified by:

hasNegativeLengthCycle in interface NegativeLengthCycleAnalyzer

Returns:

True if the graph has a negative 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.