mocgraph.analysis.strategy
Class FloydWarshallZeroLengthCycleStrategy

java.lang.Object
  mocgraph.analysis.strategy.Strategy
      mocgraph.analysis.strategy.CachedStrategy
          mocgraph.analysis.strategy.FloydWarshallZeroLengthCycleStrategy

All Implemented Interfaces:

Analyzer, GraphAnalyzer, NegativeLengthCycleAnalyzer

public class FloydWarshallZeroLengthCycleStrategy
extends CachedStrategy
implements NegativeLengthCycleAnalyzer

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

Version:

$Id: FloydWarshallZeroLengthCycleStrategy.java,v 1.1 2007/04/07 14:01:56 ssb Exp $

Author:

Shahrooz Shahparnia

See Also:

graph.analysis.ZeroLengthCycleAnalysis

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	hasNegativeLengthCycle() 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 mocgraph.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 mocgraph.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

hasNegativeLengthCycle

public boolean hasNegativeLengthCycle()

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

Specified by:

hasNegativeLengthCycle in interface NegativeLengthCycleAnalyzer

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.