001/* Base class for all the analysis based on a Floyd-Warshall like computation.
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.strategy;
026
027import ptolemy.graph.Graph;
028
029///////////////////////////////////////////////////////////////////
030//// FloydWarshallAnalysis
031
032/**
033 Base class for all the analysis based on a floyd-warshall like computation.
034 This is an abstract class and cannot be instantiated.
035 <p>
036 @since Ptolemy II 4.0
037 @Pt.ProposedRating Red (shahrooz)
038 @Pt.AcceptedRating Red (ssb)
039 @author Shahrooz Shahparnia
040 @version $Id$
041 */
042abstract public class FloydWarshallStrategy extends CachedStrategy {
043    /** Construct an FloydWarshallStrategy.
044     *  @param graph The given graph.
045     */
046    public FloydWarshallStrategy(Graph graph) {
047        super(graph);
048    }
049
050    ///////////////////////////////////////////////////////////////////
051    ////                         protected methods                 ////
052
053    /** Basic computation performed by all the analysis implementing a
054     *  floyd-warshall like analysis on a given graph.
055     *  Derived classed need to override the (@link #_floydWarshallComputation}
056     *  method of this class to provide the correct functionality.
057     *  @return The analysis results.
058     */
059    @Override
060    protected Object _compute() {
061        int n = graph().nodeCount();
062        Object floydWarshallResult = null;
063
064        // Warshall's algorithm
065        for (int k = 0; k < n; k++) {
066            for (int i = 0; i < n; i++) {
067                for (int j = 0; j < n; j++) {
068                    _floydWarshallComputation(k, i, j);
069                }
070            }
071        }
072
073        return floydWarshallResult;
074    }
075
076    /** Derived classed need to override the _floydWarshallComputation method
077     *  of this class to provide the correct functionality.
078     *  @param k The counting parameter of the first loop of the Floyd-Warshall
079     *  computation.
080     *  @param i The counting parameter of the second loop of the Floyd-Warshall
081     *  computation.
082     *  @param j The counting parameter of the third and last loop of the
083     *  Floyd-Warshall computation.
084     */
085    protected void _floydWarshallComputation(int k, int i, int j) {
086    }
087}