001/* Computation of cycle existence in directed graphs using an all pair shortest
002 path algorithm based on the Floyd-Warshall 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.CycleExistenceAnalyzer;
031
032///////////////////////////////////////////////////////////////////
033//// FloydWarshallCycleExistenceStrategy
034
035/**
036 Computation of cycle existence in directed graphs using an all pair shortest
037 path algorithm based on the Floyd-Warshall algorithm.
038 The complexity of this algorithm is O(N^3), where N is the number of nodes.
039 <p>
040 @see ptolemy.graph.analysis.CycleExistenceAnalysis
041 @since Ptolemy II 4.0
042 @Pt.ProposedRating Red (shahrooz)
043 @Pt.AcceptedRating Red (ssb)
044 @author Shahrooz Shahparnia
045 @version $Id$
046 */
047public class FloydWarshallCycleExistenceStrategy extends CachedStrategy
048        implements CycleExistenceAnalyzer {
049    /** Construct an instance of this analyzer for a given graph.
050     *
051     *  @param graph The given graph.
052     */
053    public FloydWarshallCycleExistenceStrategy(Graph graph) {
054        super(graph);
055        _strategy = new FloydWarshallTransitiveClosureStrategy(graph());
056    }
057
058    ///////////////////////////////////////////////////////////////////
059    ////                         public methods                    ////
060
061    /** Check acyclic property of the graph.
062     *
063     *  @return True if cyclic.
064     */
065    @Override
066    public boolean hasCycle() {
067        return ((Boolean) _result()).booleanValue();
068    }
069
070    /** Return a description of the analyzer.
071     *
072     *  @return Return a description of the analyzer.
073     */
074    @Override
075    public String toString() {
076        return "Cycle existence analyzer"
077                + " based on the Floyd-Warshall algorithm.";
078    }
079
080    /** Check for compatibility between the analysis and the given
081     *  graph. A graph needs to be an instance of a {@link DirectedGraph}
082     *  in order to use this algorithm.
083     *
084     *  @return True if the graph is a directed graph.
085     */
086    @Override
087    public boolean valid() {
088        return graph() instanceof DirectedGraph;
089    }
090
091    ///////////////////////////////////////////////////////////////////
092    ////                         protected methods                 ////
093
094    /** The computation associated with the Floyd-Warshall algorithm.
095     *
096     *  @return Return a true {@link Boolean} {@link Object} if the graph is
097     *  cyclic.
098     */
099    @Override
100    protected Object _compute() {
101        boolean cyclic = false;
102        boolean[][] transitiveClosure = _strategy.transitiveClosureMatrix();
103
104        for (int i = 0; i < transitiveClosure.length; i++) {
105            if (transitiveClosure[i][i] == true) {
106                cyclic = true;
107                break;
108            }
109        }
110
111        return Boolean.valueOf(cyclic);
112    }
113
114    ///////////////////////////////////////////////////////////////////
115    ////                         private variables                 ////
116    // The transitive closure analyzer used to check the existence of a cycle
117    // in the associated graph.
118    private FloydWarshallTransitiveClosureStrategy _strategy;
119}