ptolemy.graph.analysis.strategy
Class FloydWarshallCycleExistenceStrategy

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

All Implemented Interfaces:

Analyzer, CycleExistenceAnalyzer, GraphAnalyzer

public class FloydWarshallCycleExistenceStrategy
extends CachedStrategy
implements CycleExistenceAnalyzer

Computation of cycle existence in directed graphs using an all pair shortest path algorithm based on the Floyd-Warshall algorithm. The complexity of this algorithm is O(N^3), where N is the number of nodes.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia

See Also:

CycleExistenceAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private FloydWarshallTransitiveClosureStrategy

_strategy

Constructor Summary

FloydWarshallCycleExistenceStrategy(Graph graph)
Construct an instance of this analyzer for a given graph.

Method Summary

protected java.lang.Object	_compute() The computation associated with the Floyd-Warshall algorithm.
boolean	hasCycle() Check acyclic property of the graph.
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 FloydWarshallTransitiveClosureStrategy _strategy

Constructor Detail

FloydWarshallCycleExistenceStrategy

public FloydWarshallCycleExistenceStrategy(Graph graph)

Construct an instance of this analyzer for a given graph.

Parameters:

graph - The given graph.

Method Detail

hasCycle

public boolean hasCycle()

Check acyclic property of the graph.

Specified by:

hasCycle in interface CycleExistenceAnalyzer

Returns:

True if cyclic.

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 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 is cyclic.