ext/OGDF/ogdf/module/ShortestPathModule.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of base class of shortest path algorithms
  11  *        including some useful functions dealing with
  12  *        shortest paths flow (generater, checker).
  13  *
  14  * \author Gunnar W. Klau
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45
  46 #ifdef _MSC_VER
  47 #pragma once
  48 #endif
  49
  50 #ifndef OGDF_SHORTEST_PATH_MODULE_H
  51 #define OGDF_SHORTEST_PATH_MODULE_H
  52
  53
  54 #include <ogdf/basic/Graph.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60 class OGDF_EXPORT ShortestPathModule
  61 {
  62 public:
  63         ShortestPathModule() { }
  64         virtual ~ShortestPathModule() {}
  65
  66         // computes shortest paths
  67         // Precond.:
  68         // returns true iff a feasible min-cost flow exists
  69         virtual bool call(
  70                 const Graph &G,                   // directed graph
  71                 const node s,                                     // source node
  72                 const EdgeArray<int> &length,     // length of an edge
  73                 NodeArray<int> &d,                                // contains shortest path distances after call
  74                 NodeArray<edge> &pi
  75         ) = 0;
  76
  77
  78
  79 protected:
  80         //
  81         // static functions
  82         //
  83
  84         // generates a shortest path problem instance with n nodes and m+n edges
  85         /*
  86         static void generateProblem(
  87                 Graph &G,
  88                 int n,
  89                 int m,
  90                 EdgeArray<int> &lowerBound,
  91                 EdgeArray<int> &upperBound,
  92                 EdgeArray<int> &cost,
  93                 NodeArray<int> &supply);
  94
  95
  96         // checks if a given min-cost flow problem instance satisfies
  97         // the preconditions
  98         //
  99         //    lowerBound[e] <= upperBound[e] for all edges e
 100         //    cost[e] >= 0 for all edges e
 101         //    sum over all supply[v] = 0
 102         static bool checkProblem(
 103                 const Graph &G,
 104                 const EdgeArray<int> &lowerBound,
 105                 const EdgeArray<int> &upperBound,
 106                 const EdgeArray<int> &cost,
 107                 const NodeArray<int> &supply);
 108
 109
 110
 111         // checks if a computed flow is a feasible solution to the given problem
 112         // instance, i.e., checks if
 113         //    lowerBound[e] <= flow[e] <= upperBound[e]
 114         //    sum flow[e], e is outgoing edge of v -
 115         //      sum flow[e], e is incoming edge of v = supply[v] for each v
 116         // returns true iff the solution is feasible and in value the value of
 117         //   the computed flow
 118         static bool checkComputedFlow(
 119                 Graph &G,
 120                 EdgeArray<int> &lowerBound,
 121                 EdgeArray<int> &upperBound,
 122                 EdgeArray<int> &cost,
 123                 NodeArray<int> &supply,
 124                 EdgeArray<int> &flow,
 125                 int &value);
 126
 127         static bool checkComputedFlow(
 128                 Graph &G,
 129                 EdgeArray<int> &lowerBound,
 130                 EdgeArray<int> &upperBound,
 131                 EdgeArray<int> &cost,
 132                 NodeArray<int> &supply,
 133                 EdgeArray<int> &flow)
 134         {
 135                 int value;
 136                 return checkComputedFlow(
 137                         G,lowerBound,upperBound,cost,supply,flow,value);
 138         }
 139         */
 140 };
 141
 142
 143 } // end namespace ogdf
 144
 145
 146 #endif