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$

Author:

Shahrooz Shahparnia

See Also:

CycleExistenceAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and 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.