ptolemy.graph.analysis
Class NegativeLengthCycleAnalysis

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

public class NegativeLengthCycleAnalysis
extends Analysis

Analysis to check if a cyclic directed graph has a negative-length cycle. A negative-length cycle is a cycle in which the sum of all the values associated with the edges of the cycle is negative. In a graph with multiple edges between two nodes the one with the smallest associated value is being used to check for the existence of negative cycles.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Constructor Summary

NegativeLengthCycleAnalysis(Graph graph, ToDoubleMapping edgeLengths)
Construct an instance of this class using a default analyzer.

NegativeLengthCycleAnalysis(NegativeLengthCycleAnalyzer analyzer)
Construct an instance of this class using a given analyzer.

Method Summary

boolean	hasNegativeLengthCycle() Return true if a negative cycle exists in the graph under analysis.
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

NegativeLengthCycleAnalysis

public NegativeLengthCycleAnalysis(Graph graph,
                                   ToDoubleMapping edgeLengths)

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

Parameters:

graph - The given graph.

edgeLengths - The lengths associated with the edges of the graph.

NegativeLengthCycleAnalysis

public NegativeLengthCycleAnalysis(NegativeLengthCycleAnalyzer analyzer)

Construct an instance of this class using a given analyzer.

Parameters:

analyzer - The given analyzer.

Method Detail

hasNegativeLengthCycle

public boolean hasNegativeLengthCycle()

Return true if a negative cycle exists in the graph under analysis.

Returns:

True if the graph has a negative 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.