mocgraph.analysis.strategy
Class FloydWarshallCycleExistenceStrategy

java.lang.Object
  mocgraph.analysis.strategy.Strategy
      mocgraph.analysis.strategy.CachedStrategy
          mocgraph.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.

Version:

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

Author:

Shahrooz Shahparnia

See Also:

graph.analysis.CycleExistenceAnalysis

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

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.