001/* An interface to the analyzers used for the computation of transitive closure
002 of a directed graph.
003
004 Copyright (c) 2003-2005 The University of Maryland.
005 All rights reserved.
006 Permission is hereby granted, without written agreement and without
007 license or royalty fees, to use, copy, modify, and distribute this
008 software and its documentation for any purpose, provided that the above
009 copyright notice and the following two paragraphs appear in all copies
010 of this software.
011
012 IN NO EVENT SHALL THE UNIVERSITY OF MARYLAND BE LIABLE TO ANY PARTY
013 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
014 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
015 THE UNIVERSITY OF MARYLAND HAS BEEN ADVISED OF THE POSSIBILITY OF
016 SUCH DAMAGE.
017
018 THE UNIVERSITY OF MARYLAND SPECIFICALLY DISCLAIMS ANY WARRANTIES,
019 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
020 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
021 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
022 MARYLAND HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
023 ENHANCEMENTS, OR MODIFICATIONS.
024
025 */
026package ptolemy.graph.analysis.analyzer;
027
028import ptolemy.graph.Node;
029
030//////////////////////////////////////////////////////////////////////////
031//// TransitiveClosureAnalyzer
032
033/**
034 An interface to the analyzers for the computation of transitive closure
035 of a directed graph.
036 <p>
037 @see ptolemy.graph.analysis.TransitiveClosureAnalysis
038 @since Ptolemy II 4.0
039 @Pt.ProposedRating Red (shahrooz)
040 @Pt.AcceptedRating Red (ssb)
041 @author Shahrooz Shahparnia
042 @version $Id$
043 */
044public interface TransitiveClosureAnalyzer extends GraphAnalyzer {
045    /** Check if there exist a path between a starting node "startNode" and an
046     *  ending node "endNode" on the graph under analysis.
047     *
048     *  @param startNode The starting node.
049     *  @param endNode The ending node.
050     *  @return True if such a path exists.
051     */
052    public boolean pathExistence(Node startNode, Node endNode);
053
054    /** Return the transitive closure of the graph under analysis in the
055     *  form of two dimensional array. The first dimension represents
056     *  source node label while the second one represents sink node label.
057     *  Assume i and j are labels of two nodes.
058     *  The value of {@link #transitiveClosureMatrix()}[i][j] is true if there
059     *  is a path on the graph from "i" to "j".
060     *
061     *  @see ptolemy.graph.Graph#nodeLabel
062     *  @return The transitive closure in the form of 2D array.
063     */
064    public boolean[][] transitiveClosureMatrix();
065}