001/* Analyzes a directed graph and detects the existence of cycles.
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.CycleExistenceAnalyzer;
030import ptolemy.graph.analysis.strategy.FloydWarshallCycleExistenceStrategy;
031
032///////////////////////////////////////////////////////////////////
033//// CycleExistenceAnalysis
034
035/**
036 Analyzes a directed graph and detects the existence of cycles.
037 In other words, this analysis checks if a given directed graph has at least
038 one cycle or not. The default analyzer runs in O(N^3) in which N is the number
039 of nodes.
040
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 CycleExistenceAnalysis extends Analysis {
048    /** Construct an instance of this class for a given graph, using a
049     *  default analyzer that runs in O(N^3) in which N is the number of nodes.
050     *
051     *  @param graph The given directed graph.
052     */
053    public CycleExistenceAnalysis(Graph graph) {
054        super(new FloydWarshallCycleExistenceStrategy(graph));
055    }
056
057    /** Construct an instance of this class with a given analyzer.
058     *
059     *  @param analyzer The default Analyzer.
060     */
061    public CycleExistenceAnalysis(CycleExistenceAnalyzer analyzer) {
062        super(analyzer);
063    }
064
065    ///////////////////////////////////////////////////////////////////
066    ////                         public methods                    ////
067
068    /** Check if the graph under analysis has at least one cycle.
069     *
070     *  @return True if the graph under analysis has at least one cycle.
071     */
072    public boolean hasCycle() {
073        return ((CycleExistenceAnalyzer) analyzer()).hasCycle();
074    }
075
076    /** Return a description of the analysis and the associated analyzer.
077     *
078     *  @return A description of the analysis and the associated analyzer.
079     */
080    @Override
081    public String toString() {
082        return "Cyclic existence analysis using the following analyzer:\n"
083                + analyzer().toString();
084    }
085
086    /** Check if a given analyzer is compatible with this analysis.
087     *  In other words if it is possible to use it to compute the computation
088     *  associated with this analysis.
089     *
090     *  @param analyzer The given analyzer.
091     *  @return True if the given analyzer is valid for this analysis.
092     */
093    @Override
094    public boolean validAnalyzerInterface(Analyzer analyzer) {
095        return analyzer instanceof CycleExistenceAnalyzer;
096    }
097}