001/* An analysis for the computation of transitive closure of a directed graph.
002
003 Copyright (c) 2002-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.Node;
029import ptolemy.graph.analysis.analyzer.Analyzer;
030import ptolemy.graph.analysis.analyzer.TransitiveClosureAnalyzer;
031import ptolemy.graph.analysis.strategy.FloydWarshallTransitiveClosureStrategy;
032
033///////////////////////////////////////////////////////////////////
034//// TransitiveClosureAnalysis
035
036/**
037 An analysis for the computation of transitive closure of a directed graph.
038 While there is a path directed from node X to Y in the given graph,
039 there is an edge from X to Y in the transformed graph. Generally, transitive
040 closure is expressed in terms of square matrix with graph node labels as
041 indices.
042 <p>
043 The {@link #transitiveClosureMatrix()} method returns the transitive closure of
044 the graph in the form of a two dimensional array. The first dimension represents
045 source node label while the second one represents sink node label.
046 Assume i and j are labels of two nodes. Matrix[i][j] is true if there is a path
047 on the graph from "i" to "j".
048 <p>
049 @see ptolemy.graph.Graph#nodeLabel
050 @since Ptolemy II 2.0
051 @Pt.ProposedRating Red (shahrooz)
052 @Pt.AcceptedRating Red (ssb)
053 @author Shahrooz Shahparnia
054 @version $Id$
055 */
056public class TransitiveClosureAnalysis extends Analysis {
057    /** Construct an instance of this class for a given graph with
058     *  a default analyzer.
059     *  The complexity of the default algorithm is O(N^3), where N is the
060     *  number of nodes.
061     *
062     *  @param graph The given graph.
063     */
064    public TransitiveClosureAnalysis(Graph graph) {
065        super(new FloydWarshallTransitiveClosureStrategy(graph));
066    }
067
068    /** Construct an instance of this class with a given analyzer.
069     *
070     *  @param analyzer The given analyzer.
071     */
072    public TransitiveClosureAnalysis(TransitiveClosureAnalyzer analyzer) {
073        super(analyzer);
074    }
075
076    ///////////////////////////////////////////////////////////////////
077    ////                         public methods                    ////
078
079    /** Check if there exist a path between a starting node "startNode" and an
080     *  ending node "endNode" on the graph under analysis.
081     *
082     *  @param startNode The starting node.
083     *  @param endNode The ending node.
084     *  @return True if such a path exists.
085     */
086    public boolean pathExistence(Node startNode, Node endNode) {
087        return ((TransitiveClosureAnalyzer) analyzer()).pathExistence(startNode,
088                endNode);
089    }
090
091    /** Return a description of the analysis and the associated analyzer.
092     *
093     *  @return Return a description of the analysis and the associated
094     *  analyzer.
095     */
096    @Override
097    public String toString() {
098        return "Transitive closure analysis using the following analyzer:\n"
099                + analyzer().toString();
100    }
101
102    /** Compute the transitive closure of the graph under analysis in the
103     *  form of two dimensional array. The first dimension represents source
104     *  node label while the second one represents sink node label.
105     *
106     *  @see ptolemy.graph.Graph#nodeLabel
107     *  @return The transitive closure in the form of 2D array.
108     */
109    public boolean[][] transitiveClosureMatrix() {
110        return ((TransitiveClosureAnalyzer) analyzer())
111                .transitiveClosureMatrix();
112    }
113
114    /** Check if a given analyzer is compatible with this analysis.
115     *  In other words if it is possible to use it to compute the computation
116     *  associated with this analysis.
117     *
118     *  @param analyzer The given analyzer.
119     *  @return True if the given analyzer is valid for this analysis.
120     */
121    @Override
122    public boolean validAnalyzerInterface(Analyzer analyzer) {
123        return analyzer instanceof TransitiveClosureAnalyzer;
124    }
125}