FloydWarshallCycleExistenceStrategy

java.lang.Object
- 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$

Author:

Shahrooz Shahparnia

See Also:

CycleExistenceAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors
Constructor Description

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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`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

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