Package ptolemy.graph.analysis

Class 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$
    Author:
    Shahrooz Shahparnia
    Pt.AcceptedRating:
    Red (ssb)
    Pt.ProposedRating:
    Red (shahrooz)

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