001/* Analyzer to check if a given directed graph has a zero length 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.ZeroLengthCycleAnalyzer;
031import ptolemy.graph.mapping.ToDoubleMapping;
032
033///////////////////////////////////////////////////////////////////
034//// FloydWarshallZeroLengthCycleStrategy
035
036/**
037 Analyzer to check if a given directed graph has a zero cycle using the
038 Floyd-Warshall all pair shortest path algorithm.
039 <p>
040 @see ptolemy.graph.analysis.ZeroLengthCycleAnalysis
041 @since Ptolemy II 4.0
042 @Pt.ProposedRating Red (shahrooz)
043 @Pt.AcceptedRating Red (ssb)
044 @author Shahrooz Shahparnia, Nimish Sane
045 @version $Id$
046 */
047public class FloydWarshallZeroLengthCycleStrategy extends CachedStrategy
048        implements ZeroLengthCycleAnalyzer {
049    /** Constructs negative cycle detection analyzer for a given graph and
050     *  given edge values.
051     *
052     *  @param graph The given graph.
053     *  @param edgeLengths The lengths associated with the given graph.
054     */
055    public FloydWarshallZeroLengthCycleStrategy(Graph graph,
056            ToDoubleMapping edgeLengths) {
057        super(graph);
058        _edgeLengths = edgeLengths;
059        _strategy = new FloydWarshallAllPairShortestPathStrategy(graph,
060                _edgeLengths);
061    }
062
063    ///////////////////////////////////////////////////////////////////
064    ////                         public methods                    ////
065
066    /** Return true if a zero length cycle exists in the graph under analysis.
067     *
068     *  @return True if the graph has a zero length cycle.
069     */
070    @Override
071    public boolean hasZeroLengthCycle() {
072        return ((Boolean) _result()).booleanValue();
073    }
074
075    /** Return a description of the analyzer.
076     *
077     *  @return Return a description of the analyzer..
078     */
079    @Override
080    public String toString() {
081        return "Zero Length analyzer"
082                + " based on the Floyd-Warshall algorithm.";
083    }
084
085    /** Check for compatibility between the analysis and the given
086     *  graph. A graph needs to be an instance of a DirectedGraph in order
087     *  to use this algorithm.
088     *
089     *  @return True if the graph is a directed and cyclic graph.
090     */
091    @Override
092    public boolean valid() {
093        return graph() instanceof DirectedGraph;
094    }
095
096    ///////////////////////////////////////////////////////////////////
097    ////                         protected methods                 ////
098
099    /** The computation associated with the Floyd-Warshall algorithm.
100     *
101     *  @return Return a true {@link Boolean} {@link Object} if the graph has
102     *  a negative cycle.
103     */
104    @Override
105    protected Object _compute() {
106        double[][] allPairShortestPath = _strategy.shortestPathMatrix();
107        boolean zeroCycle = false;
108        int n = graph().nodeCount();
109
110        for (int i = 0; i < n; i++) {
111            if (allPairShortestPath[i][i] == 0) {
112                zeroCycle = true;
113                break;
114            }
115        }
116
117        return Boolean.valueOf(zeroCycle);
118    }
119
120    ///////////////////////////////////////////////////////////////////
121    ////                         private variables                 ////
122    // The transitive closure analyzer used to check the existence of a zero
123    // length cycle in the associated graph.
124    private FloydWarshallAllPairShortestPathStrategy _strategy;
125
126    private ToDoubleMapping _edgeLengths;
127}