ptolemy.graph.analysis.strategy
Class FloydWarshallNegativeLengthCycleStrategy

java.lang.Object
  ptolemy.graph.analysis.strategy.Strategy
      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: FloydWarshallNegativeLengthCycleStrategy.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shahrooz Shahparnia

See Also:

NegativeLengthCycleAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private ToDoubleMapping	_edgeLengths
private FloydWarshallAllPairShortestPathStrategy	_strategy

Constructor Summary

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

Field Detail

_strategy

private FloydWarshallAllPairShortestPathStrategy _strategy

_edgeLengths

private ToDoubleMapping _edgeLengths

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.