ptolemy.graph.analysis
Class CycleExistenceAnalysis

java.lang.Object
  ptolemy.graph.analysis.Analysis
      ptolemy.graph.analysis.CycleExistenceAnalysis

public class CycleExistenceAnalysis
extends Analysis

Analyzes a directed graph and detects the existence of cycles. In other words, this analysis checks if a given directed graph has at least one cycle or not. The default analyzer runs in O(N^3) in which N is the number of nodes.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Constructor Summary

CycleExistenceAnalysis(CycleExistenceAnalyzer analyzer)
Construct an instance of this class with a given analyzer.

CycleExistenceAnalysis(Graph graph)
Construct an instance of this class for a given graph, using a default analyzer that runs in O(N^3) in which N is the number of nodes.

Method Summary

boolean	hasCycle() Check if the graph under analysis has at least one cycle.
java.lang.String	toString() Return a description of the analysis and the associated analyzer.
boolean	validAnalyzerInterface(Analyzer analyzer) Check if a given analyzer is compatible with this analysis.

Methods inherited from class ptolemy.graph.analysis.Analysis

analyzer, changeAnalyzer, graph, valid

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

CycleExistenceAnalysis

public CycleExistenceAnalysis(Graph graph)

Construct an instance of this class for a given graph, using a default analyzer that runs in O(N^3) in which N is the number of nodes.

Parameters:

graph - The given directed graph.

CycleExistenceAnalysis

public CycleExistenceAnalysis(CycleExistenceAnalyzer analyzer)

Construct an instance of this class with a given analyzer.

Parameters:

analyzer - The default Analyzer.

Method Detail

hasCycle

public boolean hasCycle()

Check if the graph under analysis has at least one cycle.

Returns:

True if the graph under analysis has at least one cycle.

toString

public java.lang.String toString()

Return a description of the analysis and the associated analyzer.

Overrides:

toString in class Analysis

Returns:

A description of the analysis and the associated analyzer.

validAnalyzerInterface

public boolean validAnalyzerInterface(Analyzer analyzer)

Check if a given analyzer is compatible with this analysis. In other words if it is possible to use it to compute the computation associated with this analysis.

Overrides:

validAnalyzerInterface in class Analysis

Parameters:

analyzer - The given analyzer.

Returns:

True if the given analyzer is valid for this analysis.