1.1 --- a/lemon/Makefile.am Mon Oct 30 16:26:13 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Oct 30 17:22:14 2006 +0000
1.3 @@ -76,7 +76,6 @@
1.4 lemon/matrix_maps.h \
1.5 lemon/max_matching.h \
1.6 lemon/min_cost_arborescence.h \
1.7 - lemon/min_cost_flow.h \
1.8 lemon/min_cut.h \
1.9 lemon/mip_glpk.h \
1.10 lemon/mip_cplex.h \
1.11 @@ -90,6 +89,7 @@
1.12 lemon/refptr.h \
1.13 lemon/simann.h \
1.14 lemon/smart_graph.h \
1.15 + lemon/ssp_min_cost_flow.h \
1.16 lemon/sub_graph.h \
1.17 lemon/suurballe.h \
1.18 lemon/tabu_search.h \
2.1 --- a/lemon/min_cost_flow.h Mon Oct 30 16:26:13 2006 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,262 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - *
2.6 - * This file is a part of LEMON, a generic C++ optimization library
2.7 - *
2.8 - * Copyright (C) 2003-2006
2.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 - *
2.12 - * Permission to use, modify and distribute this software is granted
2.13 - * provided that this copyright notice appears in all copies. For
2.14 - * precise terms see the accompanying LICENSE file.
2.15 - *
2.16 - * This software is provided "AS IS" with no warranty of any kind,
2.17 - * express or implied, and with no claim as to its suitability for any
2.18 - * purpose.
2.19 - *
2.20 - */
2.21 -
2.22 -#ifndef LEMON_MIN_COST_FLOW_H
2.23 -#define LEMON_MIN_COST_FLOW_H
2.24 -
2.25 -///\ingroup flowalgs
2.26 -///\file
2.27 -///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
2.28 -
2.29 -
2.30 -#include <lemon/dijkstra.h>
2.31 -#include <lemon/graph_adaptor.h>
2.32 -#include <lemon/maps.h>
2.33 -#include <vector>
2.34 -
2.35 -namespace lemon {
2.36 -
2.37 -/// \addtogroup flowalgs
2.38 -/// @{
2.39 -
2.40 - ///\brief Implementation of an algorithm for finding a flow of value \c k
2.41 - ///(for small values of \c k) having minimal total cost between 2 nodes
2.42 - ///
2.43 - ///
2.44 - /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an
2.45 - /// algorithm for finding a flow of value \c k having minimal total
2.46 - /// cost from a given source node to a given target node in a
2.47 - /// directed graph with a cost function on the edges. To
2.48 - /// this end, the edge-capacities and edge-costs have to be
2.49 - /// nonnegative. The edge-capacities should be integers, but the
2.50 - /// edge-costs can be integers, reals or of other comparable
2.51 - /// numeric type. This algorithm is intended to be used only for
2.52 - /// small values of \c k, since it is only polynomial in k, not in
2.53 - /// the length of k (which is log k): in order to find the minimum
2.54 - /// cost flow of value \c k it finds the minimum cost flow of value
2.55 - /// \c i for every \c i between 0 and \c k.
2.56 - ///
2.57 - ///\param Graph The directed graph type the algorithm runs on.
2.58 - ///\param LengthMap The type of the length map.
2.59 - ///\param CapacityMap The capacity map type.
2.60 - ///
2.61 - ///\author Attila Bernath
2.62 - template <typename Graph, typename LengthMap, typename CapacityMap>
2.63 - class MinCostFlow {
2.64 -
2.65 - typedef typename LengthMap::Value Length;
2.66 -
2.67 - //Warning: this should be integer type
2.68 - typedef typename CapacityMap::Value Capacity;
2.69 -
2.70 - typedef typename Graph::Node Node;
2.71 - typedef typename Graph::NodeIt NodeIt;
2.72 - typedef typename Graph::Edge Edge;
2.73 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.74 - typedef typename Graph::template EdgeMap<int> EdgeIntMap;
2.75 -
2.76 - typedef ResGraphAdaptor<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
2.77 - typedef typename ResGW::Edge ResGraphEdge;
2.78 -
2.79 - protected:
2.80 -
2.81 - const Graph& g;
2.82 - const LengthMap& length;
2.83 - const CapacityMap& capacity;
2.84 -
2.85 - EdgeIntMap flow;
2.86 - typedef typename Graph::template NodeMap<Length> PotentialMap;
2.87 - PotentialMap potential;
2.88 -
2.89 - Node s;
2.90 - Node t;
2.91 -
2.92 - Length total_length;
2.93 -
2.94 - class ModLengthMap {
2.95 - typedef typename Graph::template NodeMap<Length> NodeMap;
2.96 - const ResGW& g;
2.97 - const LengthMap &length;
2.98 - const NodeMap &pot;
2.99 - public :
2.100 - typedef typename LengthMap::Key Key;
2.101 - typedef typename LengthMap::Value Value;
2.102 -
2.103 - ModLengthMap(const ResGW& _g,
2.104 - const LengthMap &_length, const NodeMap &_pot) :
2.105 - g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
2.106 -
2.107 - Value operator[](typename ResGW::Edge e) const {
2.108 - if (g.forward(e))
2.109 - return length[e]-(pot[g.target(e)]-pot[g.source(e)]);
2.110 - else
2.111 - return -length[e]-(pot[g.target(e)]-pot[g.source(e)]);
2.112 - }
2.113 -
2.114 - }; //ModLengthMap
2.115 -
2.116 - ResGW res_graph;
2.117 - ModLengthMap mod_length;
2.118 - Dijkstra<ResGW, ModLengthMap> dijkstra;
2.119 -
2.120 - public :
2.121 -
2.122 - /*! \brief The constructor of the class.
2.123 -
2.124 - \param _g The directed graph the algorithm runs on.
2.125 - \param _length The length (cost) of the edges.
2.126 - \param _cap The capacity of the edges.
2.127 - \param _s Source node.
2.128 - \param _t Target node.
2.129 - */
2.130 - MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap,
2.131 - Node _s, Node _t) :
2.132 - g(_g), length(_length), capacity(_cap), flow(_g), potential(_g),
2.133 - s(_s), t(_t),
2.134 - res_graph(g, capacity, flow),
2.135 - mod_length(res_graph, length, potential),
2.136 - dijkstra(res_graph, mod_length) {
2.137 - reset();
2.138 - }
2.139 -
2.140 - /*! Tries to augment the flow between s and t by 1.
2.141 - The return value shows if the augmentation is successful.
2.142 - */
2.143 - bool augment() {
2.144 - dijkstra.run(s);
2.145 - if (!dijkstra.reached(t)) {
2.146 -
2.147 - //Unsuccessful augmentation.
2.148 - return false;
2.149 - } else {
2.150 -
2.151 - //We have to change the potential
2.152 - for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
2.153 - potential.set(n, potential[n]+dijkstra.distMap()[n]);
2.154 -
2.155 - //Augmenting on the shortest path
2.156 - Node n=t;
2.157 - ResGraphEdge e;
2.158 - while (n!=s){
2.159 - e = dijkstra.predEdge(n);
2.160 - n = dijkstra.predNode(n);
2.161 - res_graph.augment(e,1);
2.162 - //Let's update the total length
2.163 - if (res_graph.forward(e))
2.164 - total_length += length[e];
2.165 - else
2.166 - total_length -= length[e];
2.167 - }
2.168 -
2.169 - return true;
2.170 - }
2.171 - }
2.172 -
2.173 - /*! \brief Runs the algorithm.
2.174 -
2.175 - Runs the algorithm.
2.176 - Returns k if there is a flow of value at least k from s to t.
2.177 - Otherwise it returns the maximum value of a flow from s to t.
2.178 -
2.179 - \param k The value of the flow we are looking for.
2.180 -
2.181 - \todo May be it does make sense to be able to start with a nonzero
2.182 - feasible primal-dual solution pair as well.
2.183 -
2.184 - \todo If the actual flow value is bigger than k, then everything is
2.185 - cleared and the algorithm starts from zero flow. Is it a good approach?
2.186 - */
2.187 - int run(int k) {
2.188 - if (flowValue()>k) reset();
2.189 - while (flowValue()<k && augment()) { }
2.190 - return flowValue();
2.191 - }
2.192 -
2.193 - /*! \brief The class is reset to zero flow and potential.
2.194 - The class is reset to zero flow and potential.
2.195 - */
2.196 - void reset() {
2.197 - total_length=0;
2.198 - for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
2.199 - for (typename Graph::NodeIt n(g); n!=INVALID; ++n) potential.set(n, 0);
2.200 - }
2.201 -
2.202 - /*! Returns the value of the actual flow.
2.203 - */
2.204 - int flowValue() const {
2.205 - int i=0;
2.206 - for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e];
2.207 - for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e];
2.208 - return i;
2.209 - }
2.210 -
2.211 - /// Total cost of the found flow.
2.212 -
2.213 - /// This function gives back the total cost of the found flow.
2.214 - Length totalLength(){
2.215 - return total_length;
2.216 - }
2.217 -
2.218 - ///Returns a const reference to the EdgeMap \c flow.
2.219 -
2.220 - ///Returns a const reference to the EdgeMap \c flow.
2.221 - const EdgeIntMap &getFlow() const { return flow;}
2.222 -
2.223 - /*! \brief Returns a const reference to the NodeMap \c potential (the dual solution).
2.224 -
2.225 - Returns a const reference to the NodeMap \c potential (the dual solution).
2.226 - */
2.227 - const PotentialMap &getPotential() const { return potential;}
2.228 -
2.229 - /*! \brief Checking the complementary slackness optimality criteria.
2.230 -
2.231 - This function checks, whether the given flow and potential
2.232 - satisfy the complementary slackness conditions (i.e. these are optimal).
2.233 - This function only checks optimality, doesn't bother with feasibility.
2.234 - For testing purpose.
2.235 - */
2.236 - bool checkComplementarySlackness(){
2.237 - Length mod_pot;
2.238 - Length fl_e;
2.239 - for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
2.240 - //C^{\Pi}_{i,j}
2.241 - mod_pot = length[e]-potential[g.target(e)]+potential[g.source(e)];
2.242 - fl_e = flow[e];
2.243 - if (0<fl_e && fl_e<capacity[e]) {
2.244 - /// \todo better comparison is needed for real types, moreover,
2.245 - /// this comparison here is superfluous.
2.246 - if (mod_pot != 0)
2.247 - return false;
2.248 - }
2.249 - else {
2.250 - if (mod_pot > 0 && fl_e != 0)
2.251 - return false;
2.252 - if (mod_pot < 0 && fl_e != capacity[e])
2.253 - return false;
2.254 - }
2.255 - }
2.256 - return true;
2.257 - }
2.258 -
2.259 - }; //class MinCostFlow
2.260 -
2.261 - ///@}
2.262 -
2.263 -} //namespace lemon
2.264 -
2.265 -#endif //LEMON_MIN_COST_FLOW_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/ssp_min_cost_flow.h Mon Oct 30 17:22:14 2006 +0000
3.3 @@ -0,0 +1,260 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2006
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_MIN_COST_FLOW_H
3.23 +#define LEMON_MIN_COST_FLOW_H
3.24 +
3.25 +///\ingroup flowalgs
3.26 +///
3.27 +///\file \brief An algorithm for finding a flow of value \c k (for
3.28 +///small values of \c k) having minimal total cost
3.29 +
3.30 +
3.31 +#include <lemon/dijkstra.h>
3.32 +#include <lemon/graph_adaptor.h>
3.33 +#include <lemon/maps.h>
3.34 +#include <vector>
3.35 +
3.36 +namespace lemon {
3.37 +
3.38 + /// \addtogroup flowalgs
3.39 + /// @{
3.40 +
3.41 + /// \brief Implementation of an algorithm for finding a flow of
3.42 + /// value \c k (for small values of \c k) having minimal total cost
3.43 + /// between two nodes
3.44 + ///
3.45 + ///
3.46 + /// The \ref lemon::SspMinCostFlow "Successive Shortest Path Minimum
3.47 + /// Cost Flow" implements an algorithm for finding a flow of value
3.48 + /// \c k having minimal total cost from a given source node to a
3.49 + /// given target node in a directed graph with a cost function on
3.50 + /// the edges. To this end, the edge-capacities and edge-costs have
3.51 + /// to be nonnegative. The edge-capacities should be integers, but
3.52 + /// the edge-costs can be integers, reals or of other comparable
3.53 + /// numeric type. This algorithm is intended to be used only for
3.54 + /// small values of \c k, since it is only polynomial in k, not in
3.55 + /// the length of k (which is log k): in order to find the minimum
3.56 + /// cost flow of value \c k it finds the minimum cost flow of value
3.57 + /// \c i for every \c i between 0 and \c k.
3.58 + ///
3.59 + ///\param Graph The directed graph type the algorithm runs on.
3.60 + ///\param LengthMap The type of the length map.
3.61 + ///\param CapacityMap The capacity map type.
3.62 + ///
3.63 + ///\author Attila Bernath
3.64 + template <typename Graph, typename LengthMap, typename CapacityMap>
3.65 + class SspMinCostFlow {
3.66 +
3.67 + typedef typename LengthMap::Value Length;
3.68 +
3.69 + //Warning: this should be integer type
3.70 + typedef typename CapacityMap::Value Capacity;
3.71 +
3.72 + typedef typename Graph::Node Node;
3.73 + typedef typename Graph::NodeIt NodeIt;
3.74 + typedef typename Graph::Edge Edge;
3.75 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.76 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
3.77 +
3.78 + typedef ResGraphAdaptor<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
3.79 + typedef typename ResGW::Edge ResGraphEdge;
3.80 +
3.81 + protected:
3.82 +
3.83 + const Graph& g;
3.84 + const LengthMap& length;
3.85 + const CapacityMap& capacity;
3.86 +
3.87 + EdgeIntMap flow;
3.88 + typedef typename Graph::template NodeMap<Length> PotentialMap;
3.89 + PotentialMap potential;
3.90 +
3.91 + Node s;
3.92 + Node t;
3.93 +
3.94 + Length total_length;
3.95 +
3.96 + class ModLengthMap {
3.97 + typedef typename Graph::template NodeMap<Length> NodeMap;
3.98 + const ResGW& g;
3.99 + const LengthMap &length;
3.100 + const NodeMap &pot;
3.101 + public :
3.102 + typedef typename LengthMap::Key Key;
3.103 + typedef typename LengthMap::Value Value;
3.104 +
3.105 + ModLengthMap(const ResGW& _g,
3.106 + const LengthMap &_length, const NodeMap &_pot) :
3.107 + g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
3.108 +
3.109 + Value operator[](typename ResGW::Edge e) const {
3.110 + if (g.forward(e))
3.111 + return length[e]-(pot[g.target(e)]-pot[g.source(e)]);
3.112 + else
3.113 + return -length[e]-(pot[g.target(e)]-pot[g.source(e)]);
3.114 + }
3.115 +
3.116 + }; //ModLengthMap
3.117 +
3.118 + ResGW res_graph;
3.119 + ModLengthMap mod_length;
3.120 + Dijkstra<ResGW, ModLengthMap> dijkstra;
3.121 +
3.122 + public :
3.123 +
3.124 + /// \brief The constructor of the class.
3.125 + ///
3.126 + /// \param _g The directed graph the algorithm runs on.
3.127 + /// \param _length The length (cost) of the edges.
3.128 + /// \param _cap The capacity of the edges.
3.129 + /// \param _s Source node.
3.130 + /// \param _t Target node.
3.131 + SspMinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap,
3.132 + Node _s, Node _t) :
3.133 + g(_g), length(_length), capacity(_cap), flow(_g), potential(_g),
3.134 + s(_s), t(_t),
3.135 + res_graph(g, capacity, flow),
3.136 + mod_length(res_graph, length, potential),
3.137 + dijkstra(res_graph, mod_length) {
3.138 + reset();
3.139 + }
3.140 +
3.141 + /// \brief Tries to augment the flow between s and t by 1. The
3.142 + /// return value shows if the augmentation is successful.
3.143 + bool augment() {
3.144 + dijkstra.run(s);
3.145 + if (!dijkstra.reached(t)) {
3.146 +
3.147 + //Unsuccessful augmentation.
3.148 + return false;
3.149 + } else {
3.150 +
3.151 + //We have to change the potential
3.152 + for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
3.153 + potential.set(n, potential[n]+dijkstra.distMap()[n]);
3.154 +
3.155 + //Augmenting on the shortest path
3.156 + Node n=t;
3.157 + ResGraphEdge e;
3.158 + while (n!=s){
3.159 + e = dijkstra.predEdge(n);
3.160 + n = dijkstra.predNode(n);
3.161 + res_graph.augment(e,1);
3.162 + //Let's update the total length
3.163 + if (res_graph.forward(e))
3.164 + total_length += length[e];
3.165 + else
3.166 + total_length -= length[e];
3.167 + }
3.168 +
3.169 + return true;
3.170 + }
3.171 + }
3.172 +
3.173 + /// \brief Runs the algorithm.
3.174 + ///
3.175 + /// Runs the algorithm.
3.176 + /// Returns k if there is a flow of value at least k from s to t.
3.177 + /// Otherwise it returns the maximum value of a flow from s to t.
3.178 + ///
3.179 + /// \param k The value of the flow we are looking for.
3.180 + ///
3.181 + /// \todo May be it does make sense to be able to start with a
3.182 + /// nonzero feasible primal-dual solution pair as well.
3.183 + ///
3.184 + /// \todo If the actual flow value is bigger than k, then
3.185 + /// everything is cleared and the algorithm starts from zero
3.186 + /// flow. Is it a good approach?
3.187 + int run(int k) {
3.188 + if (flowValue()>k) reset();
3.189 + while (flowValue()<k && augment()) { }
3.190 + return flowValue();
3.191 + }
3.192 +
3.193 + /// \brief The class is reset to zero flow and potential. The
3.194 + /// class is reset to zero flow and potential.
3.195 + void reset() {
3.196 + total_length=0;
3.197 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
3.198 + for (typename Graph::NodeIt n(g); n!=INVALID; ++n) potential.set(n, 0);
3.199 + }
3.200 +
3.201 + /// \brief Returns the value of the actual flow.
3.202 + int flowValue() const {
3.203 + int i=0;
3.204 + for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e];
3.205 + for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e];
3.206 + return i;
3.207 + }
3.208 +
3.209 + /// \brief Total cost of the found flow.
3.210 + ///
3.211 + /// This function gives back the total cost of the found flow.
3.212 + Length totalLength(){
3.213 + return total_length;
3.214 + }
3.215 +
3.216 + /// \brief Returns a const reference to the EdgeMap \c flow.
3.217 + ///
3.218 + /// Returns a const reference to the EdgeMap \c flow.
3.219 + const EdgeIntMap &getFlow() const { return flow;}
3.220 +
3.221 + /// \brief Returns a const reference to the NodeMap \c potential
3.222 + /// (the dual solution).
3.223 + ///
3.224 + /// Returns a const reference to the NodeMap \c potential (the
3.225 + /// dual solution).
3.226 + const PotentialMap &getPotential() const { return potential;}
3.227 +
3.228 + /// \brief Checking the complementary slackness optimality criteria.
3.229 + ///
3.230 + /// This function checks, whether the given flow and potential
3.231 + /// satisfy the complementary slackness conditions (i.e. these are optimal).
3.232 + /// This function only checks optimality, doesn't bother with feasibility.
3.233 + /// For testing purpose.
3.234 + bool checkComplementarySlackness(){
3.235 + Length mod_pot;
3.236 + Length fl_e;
3.237 + for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.238 + //C^{\Pi}_{i,j}
3.239 + mod_pot = length[e]-potential[g.target(e)]+potential[g.source(e)];
3.240 + fl_e = flow[e];
3.241 + if (0<fl_e && fl_e<capacity[e]) {
3.242 + /// \todo better comparison is needed for real types, moreover,
3.243 + /// this comparison here is superfluous.
3.244 + if (mod_pot != 0)
3.245 + return false;
3.246 + }
3.247 + else {
3.248 + if (mod_pot > 0 && fl_e != 0)
3.249 + return false;
3.250 + if (mod_pot < 0 && fl_e != capacity[e])
3.251 + return false;
3.252 + }
3.253 + }
3.254 + return true;
3.255 + }
3.256 +
3.257 + }; //class SspMinCostFlow
3.258 +
3.259 + ///@}
3.260 +
3.261 +} //namespace lemon
3.262 +
3.263 +#endif //LEMON_MIN_COST_FLOW_H
4.1 --- a/lemon/suurballe.h Mon Oct 30 16:26:13 2006 +0000
4.2 +++ b/lemon/suurballe.h Mon Oct 30 17:22:14 2006 +0000
4.3 @@ -26,15 +26,15 @@
4.4
4.5 #include <lemon/maps.h>
4.6 #include <vector>
4.7 -#include <lemon/min_cost_flow.h>
4.8 +#include <lemon/ssp_min_cost_flow.h>
4.9
4.10 namespace lemon {
4.11
4.12 /// \addtogroup flowalgs
4.13 /// @{
4.14
4.15 - ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
4.16 - /// of minimal total length
4.17 + ///\brief Implementation of an algorithm for finding k edge-disjoint
4.18 + /// paths between 2 nodes of minimal total length
4.19 ///
4.20 /// The class \ref lemon::Suurballe implements
4.21 /// an algorithm for finding k edge-disjoint paths
4.22 @@ -49,7 +49,7 @@
4.23 ///\note It it questionable whether it is correct to call this method after
4.24 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
4.25 ///for finding minimum cost flows. In fact, this implementation just
4.26 - ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
4.27 + ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and
4.28 ///Edmonds-Karp published in 1972, therefore it is possibly right to
4.29 ///state that they are
4.30 ///independent results. Most frequently this special case is referred as
4.31 @@ -79,7 +79,7 @@
4.32 //This is the capacity map for the mincostflow problem
4.33 ConstMap const1map;
4.34 //This MinCostFlow instance will actually solve the problem
4.35 - MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
4.36 + SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
4.37
4.38 //Container to store found paths
4.39 std::vector< std::vector<Edge> > paths;
4.40 @@ -87,25 +87,24 @@
4.41 public :
4.42
4.43
4.44 - /*! \brief The constructor of the class.
4.45 -
4.46 - \param _G The directed graph the algorithm runs on.
4.47 - \param _length The length (weight or cost) of the edges.
4.48 - \param _s Source node.
4.49 - \param _t Target node.
4.50 - */
4.51 + /// \brief The constructor of the class.
4.52 + ///
4.53 + /// \param _G The directed graph the algorithm runs on.
4.54 + /// \param _length The length (weight or cost) of the edges.
4.55 + /// \param _s Source node.
4.56 + /// \param _t Target node.
4.57 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
4.58 G(_G), s(_s), t(_t), const1map(1),
4.59 min_cost_flow(_G, _length, const1map, _s, _t) { }
4.60
4.61 - ///Runs the algorithm.
4.62 -
4.63 - ///Runs the algorithm.
4.64 - ///Returns k if there are at least k edge-disjoint paths from s to t.
4.65 - ///Otherwise it returns the number of edge-disjoint paths found
4.66 - ///from s to t.
4.67 + /// \brief Runs the algorithm.
4.68 ///
4.69 - ///\param k How many paths are we looking for?
4.70 + /// Runs the algorithm.
4.71 + /// Returns k if there are at least k edge-disjoint paths from s to t.
4.72 + /// Otherwise it returns the number of edge-disjoint paths found
4.73 + /// from s to t.
4.74 + ///
4.75 + /// \param k How many paths are we looking for?
4.76 ///
4.77 int run(int k) {
4.78 int i = min_cost_flow.run(k);
4.79 @@ -144,46 +143,49 @@
4.80 }
4.81
4.82
4.83 - ///Returns the total length of the paths.
4.84 -
4.85 - ///This function gives back the total length of the found paths.
4.86 + /// \brief Returns the total length of the paths.
4.87 + ///
4.88 + /// This function gives back the total length of the found paths.
4.89 Length totalLength(){
4.90 return min_cost_flow.totalLength();
4.91 }
4.92
4.93 - ///Returns the found flow.
4.94 -
4.95 - ///This function returns a const reference to the EdgeMap \c flow.
4.96 + /// \brief Returns the found flow.
4.97 + ///
4.98 + /// This function returns a const reference to the EdgeMap \c flow.
4.99 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
4.100
4.101 - /// Returns the optimal dual solution
4.102 -
4.103 - ///This function returns a const reference to the NodeMap
4.104 - ///\c potential (the dual solution).
4.105 + /// \brief Returns the optimal dual solution
4.106 + ///
4.107 + /// This function returns a const reference to the NodeMap \c
4.108 + /// potential (the dual solution).
4.109 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
4.110
4.111 - ///Checks whether the complementary slackness holds.
4.112 -
4.113 - ///This function checks, whether the given solution is optimal.
4.114 - ///Currently this function only checks optimality,
4.115 - ///doesn't bother with feasibility.
4.116 - ///It is meant for testing purposes.
4.117 + /// \brief Checks whether the complementary slackness holds.
4.118 + ///
4.119 + /// This function checks, whether the given solution is optimal.
4.120 + /// Currently this function only checks optimality, doesn't bother
4.121 + /// with feasibility. It is meant for testing purposes.
4.122 bool checkComplementarySlackness(){
4.123 return min_cost_flow.checkComplementarySlackness();
4.124 }
4.125
4.126 - ///Read the found paths.
4.127 -
4.128 - ///This function gives back the \c j-th path in argument p.
4.129 - ///Assumes that \c run() has been run and nothing has changed since then.
4.130 - /// \warning It is assumed that \c p is constructed to
4.131 - ///be a path of graph \c G.
4.132 - ///If \c j is not less than the result of previous \c run,
4.133 - ///then the result here will be an empty path (\c j can be 0 as well).
4.134 + /// \brief Read the found paths.
4.135 ///
4.136 - ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
4.137 - ///\param p The path to put the result to.
4.138 - ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
4.139 + /// This function gives back the \c j-th path in argument p.
4.140 + /// Assumes that \c run() has been run and nothing has changed
4.141 + /// since then.
4.142 + ///
4.143 + /// \warning It is assumed that \c p is constructed to be a path
4.144 + /// of graph \c G. If \c j is not less than the result of
4.145 + /// previous \c run, then the result here will be an empty path
4.146 + /// (\c j can be 0 as well).
4.147 + ///
4.148 + /// \param Path The type of the path structure to put the result
4.149 + /// to (must meet lemon path concept).
4.150 + /// \param p The path to put the result to.
4.151 + /// \param j Which path you want to get from the found paths (in a
4.152 + /// real application you would get the found paths iteratively).
4.153 template<typename Path>
4.154 void getPath(Path& p, size_t j){
4.155
5.1 --- a/test/min_cost_flow_test.cc Mon Oct 30 16:26:13 2006 +0000
5.2 +++ b/test/min_cost_flow_test.cc Mon Oct 30 17:22:14 2006 +0000
5.3 @@ -19,7 +19,7 @@
5.4 #include <iostream>
5.5 #include "test_tools.h"
5.6 #include <lemon/list_graph.h>
5.7 -#include <lemon/min_cost_flow.h>
5.8 +#include <lemon/ssp_min_cost_flow.h>
5.9 //#include <path.h>
5.10 //#include <maps.h>
5.11
5.12 @@ -92,7 +92,7 @@
5.13 // ConstMap<Edge, int> const1map(1);
5.14 std::cout << "Mincostflows algorithm test..." << std::endl;
5.15
5.16 - MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.17 + SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.18 surb_test(graph, length, capacity, s, t);
5.19
5.20 int k=1;