1.1 --- a/NEWS Thu Apr 17 21:28:21 2008 +0000
1.2 +++ b/NEWS Thu Apr 17 21:46:06 2008 +0000
1.3 @@ -134,6 +134,7 @@
1.4 * removed "Type" suffix from typedefs
1.5 * lower case local variables
1.6 Removed
1.7 + - SspMinCostFlow
1.8 - template Map template parameter from InvertableMaps
1.9 - union-find Item template parameter
1.10 - strict checking
2.1 --- a/lemon/Makefile.am Thu Apr 17 21:28:21 2008 +0000
2.2 +++ b/lemon/Makefile.am Thu Apr 17 21:46:06 2008 +0000
2.3 @@ -119,7 +119,6 @@
2.4 lemon/refptr.h \
2.5 lemon/simann.h \
2.6 lemon/smart_graph.h \
2.7 - lemon/ssp_min_cost_flow.h \
2.8 lemon/static_graph.h \
2.9 lemon/steiner.h \
2.10 lemon/sub_graph.h \
3.1 --- a/lemon/ssp_min_cost_flow.h Thu Apr 17 21:28:21 2008 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,260 +0,0 @@
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-2008
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_SSP_MIN_COST_FLOW_H
3.23 -#define LEMON_SSP_MIN_COST_FLOW_H
3.24 -
3.25 -///\ingroup min_cost_flow
3.26 -///
3.27 -///\file
3.28 -///\brief An algorithm for finding a flow of value \c k (for
3.29 -///small values of \c k) having minimal total cost
3.30 -
3.31 -
3.32 -#include <lemon/dijkstra.h>
3.33 -#include <lemon/graph_adaptor.h>
3.34 -#include <lemon/maps.h>
3.35 -#include <vector>
3.36 -
3.37 -namespace lemon {
3.38 -
3.39 - /// \addtogroup min_cost_flow
3.40 - /// @{
3.41 -
3.42 - /// \brief Implementation of an algorithm for finding a flow of
3.43 - /// value \c k (for small values of \c k) having minimal total cost
3.44 - /// between two nodes
3.45 - ///
3.46 - ///
3.47 - /// The \ref lemon::SspMinCostFlow "Successive Shortest Path Minimum
3.48 - /// Cost Flow" implements an algorithm for finding a flow of value
3.49 - /// \c k having minimal total cost from a given source node to a
3.50 - /// given target node in a directed graph with a cost function on
3.51 - /// the edges. To this end, the edge-capacities and edge-costs have
3.52 - /// to be nonnegative. The edge-capacities should be integers, but
3.53 - /// the edge-costs can be integers, reals or of other comparable
3.54 - /// numeric type. This algorithm is intended to be used only for
3.55 - /// small values of \c k, since it is only polynomial in k, not in
3.56 - /// the length of k (which is log k): in order to find the minimum
3.57 - /// cost flow of value \c k it finds the minimum cost flow of value
3.58 - /// \c i for every \c i between 0 and \c k.
3.59 - ///
3.60 - ///\param Graph The directed graph type the algorithm runs on.
3.61 - ///\param LengthMap The type of the length map.
3.62 - ///\param CapacityMap The capacity map type.
3.63 - ///
3.64 - ///\author Attila Bernath
3.65 - template <typename Graph, typename LengthMap, typename CapacityMap>
3.66 - class SspMinCostFlow {
3.67 -
3.68 - typedef typename LengthMap::Value Length;
3.69 -
3.70 - //Warning: this should be integer type
3.71 - typedef typename CapacityMap::Value Capacity;
3.72 -
3.73 - typedef typename Graph::Node Node;
3.74 - typedef typename Graph::NodeIt NodeIt;
3.75 - typedef typename Graph::Edge Edge;
3.76 - typedef typename Graph::OutEdgeIt OutEdgeIt;
3.77 - typedef typename Graph::template EdgeMap<int> EdgeIntMap;
3.78 -
3.79 - typedef ResGraphAdaptor<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
3.80 - typedef typename ResGW::Edge ResGraphEdge;
3.81 -
3.82 - protected:
3.83 -
3.84 - const Graph& g;
3.85 - const LengthMap& length;
3.86 - const CapacityMap& capacity;
3.87 -
3.88 - EdgeIntMap flow;
3.89 - typedef typename Graph::template NodeMap<Length> PotentialMap;
3.90 - PotentialMap potential;
3.91 -
3.92 - Node s;
3.93 - Node t;
3.94 -
3.95 - Length total_length;
3.96 -
3.97 - class ModLengthMap {
3.98 - typedef typename Graph::template NodeMap<Length> NodeMap;
3.99 - const ResGW& g;
3.100 - const LengthMap &length;
3.101 - const NodeMap &pot;
3.102 - public :
3.103 - typedef typename LengthMap::Key Key;
3.104 - typedef typename LengthMap::Value Value;
3.105 -
3.106 - ModLengthMap(const ResGW& _g,
3.107 - const LengthMap &_length, const NodeMap &_pot) :
3.108 - g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
3.109 -
3.110 - Value operator[](typename ResGW::Edge e) const {
3.111 - if (g.forward(e))
3.112 - return length[e]-(pot[g.target(e)]-pot[g.source(e)]);
3.113 - else
3.114 - return -length[e]-(pot[g.target(e)]-pot[g.source(e)]);
3.115 - }
3.116 -
3.117 - }; //ModLengthMap
3.118 -
3.119 - ResGW res_graph;
3.120 - ModLengthMap mod_length;
3.121 - Dijkstra<ResGW, ModLengthMap> dijkstra;
3.122 -
3.123 - public :
3.124 -
3.125 - /// \brief The constructor of the class.
3.126 - ///
3.127 - /// \param _g The directed graph the algorithm runs on.
3.128 - /// \param _length The length (cost) of the edges.
3.129 - /// \param _cap The capacity of the edges.
3.130 - /// \param _s Source node.
3.131 - /// \param _t Target node.
3.132 - SspMinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap,
3.133 - Node _s, Node _t) :
3.134 - g(_g), length(_length), capacity(_cap), flow(_g), potential(_g),
3.135 - s(_s), t(_t),
3.136 - res_graph(g, capacity, flow),
3.137 - mod_length(res_graph, length, potential),
3.138 - dijkstra(res_graph, mod_length) {
3.139 - reset();
3.140 - }
3.141 -
3.142 - /// \brief Tries to augment the flow between s and t by 1. The
3.143 - /// return value shows if the augmentation is successful.
3.144 - bool augment() {
3.145 - dijkstra.run(s);
3.146 - if (!dijkstra.reached(t)) {
3.147 -
3.148 - //Unsuccessful augmentation.
3.149 - return false;
3.150 - } else {
3.151 -
3.152 - //We have to change the potential
3.153 - for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
3.154 - potential.set(n, potential[n]+dijkstra.distMap()[n]);
3.155 -
3.156 - //Augmenting on the shortest path
3.157 - Node n=t;
3.158 - ResGraphEdge e;
3.159 - while (n!=s){
3.160 - e = dijkstra.predEdge(n);
3.161 - n = dijkstra.predNode(n);
3.162 - res_graph.augment(e,1);
3.163 - //Let's update the total length
3.164 - if (res_graph.forward(e))
3.165 - total_length += length[e];
3.166 - else
3.167 - total_length -= length[e];
3.168 - }
3.169 -
3.170 - return true;
3.171 - }
3.172 - }
3.173 -
3.174 - /// \brief Runs the algorithm.
3.175 - ///
3.176 - /// Runs the algorithm.
3.177 - /// Returns k if there is a flow of value at least k from s to t.
3.178 - /// Otherwise it returns the maximum value of a flow from s to t.
3.179 - ///
3.180 - /// \param k The value of the flow we are looking for.
3.181 - ///
3.182 - /// \todo May be it does make sense to be able to start with a
3.183 - /// nonzero feasible primal-dual solution pair as well.
3.184 - ///
3.185 - /// \todo If the current flow value is bigger than k, then
3.186 - /// everything is cleared and the algorithm starts from zero
3.187 - /// flow. Is it a good approach?
3.188 - int run(int k) {
3.189 - if (flowValue()>k) reset();
3.190 - while (flowValue()<k && augment()) { }
3.191 - return flowValue();
3.192 - }
3.193 -
3.194 - /// \brief The 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 current 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_SSP_MIN_COST_FLOW_H