001/* Analyzer to check if a given directed graph has a negative cycle using the
002 Floyd-Warshall all pair shortest path algorithm.
003
004 Copyright (c) 2003-2014 The University of Maryland. All rights reserved.
005 Permission is hereby granted, without written agreement and without
006 license or royalty fees, to use, copy, modify, and distribute this
007 software and its documentation for any purpose, provided that the above
008 copyright notice and the following two paragraphs appear in all copies
009 of this software.
010
011 IN NO EVENT SHALL THE UNIVERSITY OF MARYLAND BE LIABLE TO ANY PARTY
012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
014 THE UNIVERSITY OF MARYLAND HAS BEEN ADVISED OF THE POSSIBILITY OF
015 SUCH DAMAGE.
016
017 THE UNIVERSITY OF MARYLAND SPECIFICALLY DISCLAIMS ANY WARRANTIES,
018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
021 MARYLAND HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
022 ENHANCEMENTS, OR MODIFICATIONS.
023
024
025 */
026package ptolemy.graph.analysis.strategy;
027
028import ptolemy.graph.DirectedGraph;
029import ptolemy.graph.Graph;
030import ptolemy.graph.analysis.analyzer.NegativeLengthCycleAnalyzer;
031import ptolemy.graph.mapping.ToDoubleMapping;
032
033///////////////////////////////////////////////////////////////////
034//// FloydWarshallNegativeLengthCycleStrategy
035
036/**
037 Analyzer to check if a given directed graph has a negative cycle using the
038 Floyd-Warshall all pair shortest path algorithm.
039 The complexity of this algorithm is O(N^3), where N is the number of nodes.
040 <p>
041 @see ptolemy.graph.analysis.NegativeLengthCycleAnalysis
042 @since Ptolemy II 4.0
043 @Pt.ProposedRating Red (shahrooz)
044 @Pt.AcceptedRating Red (ssb)
045 @author Shahrooz Shahparnia
046 @version $Id$
047 */
048public class FloydWarshallNegativeLengthCycleStrategy extends CachedStrategy
049        implements NegativeLengthCycleAnalyzer {
050    /** Constructs negative cycle detection analyzer for a given graph and
051     *  given edge values.
052     *
053     *  @param graph The given graph.
054     *  @param edgeLengths The lengths associated with the given graph.
055     */
056    public FloydWarshallNegativeLengthCycleStrategy(Graph graph,
057            ToDoubleMapping edgeLengths) {
058        super(graph);
059        _edgeLengths = edgeLengths;
060        _strategy = new FloydWarshallAllPairShortestPathStrategy(graph,
061                _edgeLengths);
062    }
063
064    ///////////////////////////////////////////////////////////////////
065    ////                         public methods                    ////
066
067    /** Return true if a negative cycle exists in the graph under analysis.
068     *
069     *  @return True if the graph has a negative cycle.
070     */
071    @Override
072    public boolean hasNegativeLengthCycle() {
073        return ((Boolean) _result()).booleanValue();
074    }
075
076    /** Return a description of the analyzer.
077     *
078     *  @return Return a description of the analyzer..
079     */
080    @Override
081    public String toString() {
082        return "Negative Length analyzer"
083                + " based on the Floyd-Warshall algorithm.";
084    }
085
086    /** Check for compatibility between the analysis and the given
087     *  graph. A graph needs to be an instance of a DirectedGraph in order
088     *  to use this algorithm.
089     *
090     *  @return True if the graph is a directed and cyclic graph.
091     */
092    @Override
093    public boolean valid() {
094        return graph() instanceof DirectedGraph;
095    }
096
097    ///////////////////////////////////////////////////////////////////
098    ////                         protected methods                 ////
099
100    /** The computation associated with the Floyd-Warshall algorithm.
101     *
102     *  @return Return a true {@link Boolean} {@link Object} if the graph has
103     *  a negative cycle.
104     */
105    @Override
106    protected Object _compute() {
107        double[][] allPairShortestPath = _strategy.shortestPathMatrix();
108        boolean negativeCycle = false;
109        int n = graph().nodeCount();
110
111        for (int i = 0; i < n; i++) {
112            if (allPairShortestPath[i][i] < 0) {
113                negativeCycle = true;
114                break;
115            }
116        }
117
118        return Boolean.valueOf(negativeCycle);
119    }
120
121    ///////////////////////////////////////////////////////////////////
122    ////                         private variables                 ////
123    // The transitive closure analyzer used to check the existence of a negative
124    // cycle in the associated graph.
125    private FloydWarshallAllPairShortestPathStrategy _strategy;
126
127    private ToDoubleMapping _edgeLengths;
128}