001/* Analysis to check if a cyclic directed graph has a negative-length cycle.
002
003 Copyright (c) 2003-2014 The University of Maryland. All rights reserved.
004 Permission is hereby granted, without written agreement and without
005 license or royalty fees, to use, copy, modify, and distribute this
006 software and its documentation for any purpose, provided that the above
007 copyright notice and the following two paragraphs appear in all copies
008 of this software.
009
010 IN NO EVENT SHALL THE UNIVERSITY OF MARYLAND BE LIABLE TO ANY PARTY
011 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
012 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
013 THE UNIVERSITY OF MARYLAND HAS BEEN ADVISED OF THE POSSIBILITY OF
014 SUCH DAMAGE.
015
016 THE UNIVERSITY OF MARYLAND SPECIFICALLY DISCLAIMS ANY WARRANTIES,
017 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
018 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
019 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
020 MARYLAND HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
021 ENHANCEMENTS, OR MODIFICATIONS.
022
023
024 */
025package ptolemy.graph.analysis;
026
027import ptolemy.graph.Graph;
028import ptolemy.graph.analysis.analyzer.Analyzer;
029import ptolemy.graph.analysis.analyzer.NegativeLengthCycleAnalyzer;
030import ptolemy.graph.analysis.strategy.FloydWarshallNegativeLengthCycleStrategy;
031import ptolemy.graph.mapping.ToDoubleMapping;
032
033///////////////////////////////////////////////////////////////////
034//// NegativeLengthCycleAnalysis
035
036/**
037 Analysis to check if a cyclic directed graph has a negative-length cycle.
038 A negative-length cycle is a cycle in which the sum of all the values associated
039 with the edges of the cycle is negative. In a graph with multiple edges between
040 two nodes the one with the smallest associated value is being used to check for
041 the existence of negative cycles.
042 <p>
043
044 @since Ptolemy II 4.0
045 @Pt.ProposedRating Red (shahrooz)
046 @Pt.AcceptedRating Red (ssb)
047 @author Shahrooz Shahparnia
048 @version $Id$
049 */
050public class NegativeLengthCycleAnalysis extends Analysis {
051    /** Construct an instance of this class using a default analyzer.
052     *  The default analyzer runs in O(N^3) in which N is the number of nodes.
053     *
054     *  @param graph The given graph.
055     *  @param edgeLengths The lengths associated with the edges of the graph.
056     */
057    public NegativeLengthCycleAnalysis(Graph graph,
058            ToDoubleMapping edgeLengths) {
059        super(new FloydWarshallNegativeLengthCycleStrategy(graph, edgeLengths));
060    }
061
062    /** Construct an instance of this class using a given analyzer.
063     *
064     *  @param analyzer The given analyzer.
065     */
066    public NegativeLengthCycleAnalysis(NegativeLengthCycleAnalyzer analyzer) {
067        super(analyzer);
068    }
069
070    ///////////////////////////////////////////////////////////////////
071    ////                         public methods                    ////
072
073    /** Return true if a negative cycle exists in the graph under analysis.
074     *
075     *  @return True if the graph has a negative cycle.
076     */
077    public boolean hasNegativeLengthCycle() {
078        return ((NegativeLengthCycleAnalyzer) analyzer())
079                .hasNegativeLengthCycle();
080    }
081
082    /** Return a description of the analysis and the associated analyzer.
083     *
084     *  @return A description of the analysis and the associated analyzer.
085     */
086    @Override
087    public String toString() {
088        return "Negative-length cycle analysis using the following analyzer:\n"
089                + analyzer().toString();
090    }
091
092    /** Check if a given analyzer is compatible with this analysis.
093     *  In other words if it is possible to use it to compute the computation
094     *  associated with this analysis.
095     *
096     *  @param analyzer The given analyzer.
097     *  @return True if the given analyzer is valid for this analysis.
098     */
099    @Override
100    public boolean validAnalyzerInterface(Analyzer analyzer) {
101        return analyzer instanceof NegativeLengthCycleAnalyzer;
102    }
103}