lemon/cycle_canceling.h
changeset 905 de428ebb47ab
parent 864 d3ea191c3412
child 919 e0cef67fe565
child 921 140c953ad5d1
equal deleted inserted replaced
7:d6f6c9a5527a 8:8e22680054e8
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   140     };
   140     };
   141 
   141 
   142   private:
   142   private:
   143 
   143 
   144     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   144     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   145     
   145 
   146     typedef std::vector<int> IntVector;
   146     typedef std::vector<int> IntVector;
   147     typedef std::vector<double> DoubleVector;
   147     typedef std::vector<double> DoubleVector;
   148     typedef std::vector<Value> ValueVector;
   148     typedef std::vector<Value> ValueVector;
   149     typedef std::vector<Cost> CostVector;
   149     typedef std::vector<Cost> CostVector;
   150     typedef std::vector<char> BoolVector;
   150     typedef std::vector<char> BoolVector;
   151     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   151     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   152 
   152 
   153   private:
   153   private:
   154   
   154 
   155     template <typename KT, typename VT>
   155     template <typename KT, typename VT>
   156     class StaticVectorMap {
   156     class StaticVectorMap {
   157     public:
   157     public:
   158       typedef KT Key;
   158       typedef KT Key;
   159       typedef VT Value;
   159       typedef VT Value;
   160       
   160 
   161       StaticVectorMap(std::vector<Value>& v) : _v(v) {}
   161       StaticVectorMap(std::vector<Value>& v) : _v(v) {}
   162       
   162 
   163       const Value& operator[](const Key& key) const {
   163       const Value& operator[](const Key& key) const {
   164         return _v[StaticDigraph::id(key)];
   164         return _v[StaticDigraph::id(key)];
   165       }
   165       }
   166 
   166 
   167       Value& operator[](const Key& key) {
   167       Value& operator[](const Key& key) {
   168         return _v[StaticDigraph::id(key)];
   168         return _v[StaticDigraph::id(key)];
   169       }
   169       }
   170       
   170 
   171       void set(const Key& key, const Value& val) {
   171       void set(const Key& key, const Value& val) {
   172         _v[StaticDigraph::id(key)] = val;
   172         _v[StaticDigraph::id(key)] = val;
   173       }
   173       }
   174 
   174 
   175     private:
   175     private:
   219     std::vector<IntPair> _arc_vec;
   219     std::vector<IntPair> _arc_vec;
   220     std::vector<Cost> _cost_vec;
   220     std::vector<Cost> _cost_vec;
   221     IntVector _id_vec;
   221     IntVector _id_vec;
   222     CostArcMap _cost_map;
   222     CostArcMap _cost_map;
   223     CostNodeMap _pi_map;
   223     CostNodeMap _pi_map;
   224   
   224 
   225   public:
   225   public:
   226   
   226 
   227     /// \brief Constant for infinite upper bounds (capacities).
   227     /// \brief Constant for infinite upper bounds (capacities).
   228     ///
   228     ///
   229     /// Constant for infinite upper bounds (capacities).
   229     /// Constant for infinite upper bounds (capacities).
   230     /// It is \c std::numeric_limits<Value>::infinity() if available,
   230     /// It is \c std::numeric_limits<Value>::infinity() if available,
   231     /// \c std::numeric_limits<Value>::max() otherwise.
   231     /// \c std::numeric_limits<Value>::max() otherwise.
   364       }
   364       }
   365       _supply[_node_id[s]] =  k;
   365       _supply[_node_id[s]] =  k;
   366       _supply[_node_id[t]] = -k;
   366       _supply[_node_id[t]] = -k;
   367       return *this;
   367       return *this;
   368     }
   368     }
   369     
   369 
   370     /// @}
   370     /// @}
   371 
   371 
   372     /// \name Execution control
   372     /// \name Execution control
   373     /// The algorithm can be executed using \ref run().
   373     /// The algorithm can be executed using \ref run().
   374 
   374 
   464       for (int j = limit; j != _res_arc_num; ++j) {
   464       for (int j = limit; j != _res_arc_num; ++j) {
   465         _lower[j] = 0;
   465         _lower[j] = 0;
   466         _upper[j] = INF;
   466         _upper[j] = INF;
   467         _cost[j] = 0;
   467         _cost[j] = 0;
   468         _cost[_reverse[j]] = 0;
   468         _cost[_reverse[j]] = 0;
   469       }      
   469       }
   470       _have_lower = false;
   470       _have_lower = false;
   471       return *this;
   471       return *this;
   472     }
   472     }
   473 
   473 
   474     /// \brief Reset the internal data structures and all the parameters
   474     /// \brief Reset the internal data structures and all the parameters
   506 
   506 
   507       _lower.resize(_res_arc_num);
   507       _lower.resize(_res_arc_num);
   508       _upper.resize(_res_arc_num);
   508       _upper.resize(_res_arc_num);
   509       _cost.resize(_res_arc_num);
   509       _cost.resize(_res_arc_num);
   510       _supply.resize(_res_node_num);
   510       _supply.resize(_res_node_num);
   511       
   511 
   512       _res_cap.resize(_res_arc_num);
   512       _res_cap.resize(_res_arc_num);
   513       _pi.resize(_res_node_num);
   513       _pi.resize(_res_node_num);
   514 
   514 
   515       _arc_vec.reserve(_res_arc_num);
   515       _arc_vec.reserve(_res_arc_num);
   516       _cost_vec.reserve(_res_arc_num);
   516       _cost_vec.reserve(_res_arc_num);
   552         int fi = _arc_idf[a];
   552         int fi = _arc_idf[a];
   553         int bi = _arc_idb[a];
   553         int bi = _arc_idb[a];
   554         _reverse[fi] = bi;
   554         _reverse[fi] = bi;
   555         _reverse[bi] = fi;
   555         _reverse[bi] = fi;
   556       }
   556       }
   557       
   557 
   558       // Reset parameters
   558       // Reset parameters
   559       resetParams();
   559       resetParams();
   560       return *this;
   560       return *this;
   561     }
   561     }
   562 
   562 
   661       _sum_supply = 0;
   661       _sum_supply = 0;
   662       for (int i = 0; i != _root; ++i) {
   662       for (int i = 0; i != _root; ++i) {
   663         _sum_supply += _supply[i];
   663         _sum_supply += _supply[i];
   664       }
   664       }
   665       if (_sum_supply > 0) return INFEASIBLE;
   665       if (_sum_supply > 0) return INFEASIBLE;
   666       
   666 
   667 
   667 
   668       // Initialize vectors
   668       // Initialize vectors
   669       for (int i = 0; i != _res_node_num; ++i) {
   669       for (int i = 0; i != _res_node_num; ++i) {
   670         _pi[i] = 0;
   670         _pi[i] = 0;
   671       }
   671       }
   672       ValueVector excess(_supply);
   672       ValueVector excess(_supply);
   673       
   673 
   674       // Remove infinite upper bounds and check negative arcs
   674       // Remove infinite upper bounds and check negative arcs
   675       const Value MAX = std::numeric_limits<Value>::max();
   675       const Value MAX = std::numeric_limits<Value>::max();
   676       int last_out;
   676       int last_out;
   677       if (_have_lower) {
   677       if (_have_lower) {
   678         for (int i = 0; i != _root; ++i) {
   678         for (int i = 0; i != _root; ++i) {
   768           _res_cap[ra] = 0;
   768           _res_cap[ra] = 0;
   769           _cost[a] = 0;
   769           _cost[a] = 0;
   770           _cost[ra] = 0;
   770           _cost[ra] = 0;
   771         }
   771         }
   772       }
   772       }
   773       
   773 
   774       return OPTIMAL;
   774       return OPTIMAL;
   775     }
   775     }
   776     
   776 
   777     // Build a StaticDigraph structure containing the current
   777     // Build a StaticDigraph structure containing the current
   778     // residual network
   778     // residual network
   779     void buildResidualNetwork() {
   779     void buildResidualNetwork() {
   780       _arc_vec.clear();
   780       _arc_vec.clear();
   781       _cost_vec.clear();
   781       _cost_vec.clear();
   827     // Execute the "Simple Cycle Canceling" method
   827     // Execute the "Simple Cycle Canceling" method
   828     void startSimpleCycleCanceling() {
   828     void startSimpleCycleCanceling() {
   829       // Constants for computing the iteration limits
   829       // Constants for computing the iteration limits
   830       const int BF_FIRST_LIMIT  = 2;
   830       const int BF_FIRST_LIMIT  = 2;
   831       const double BF_LIMIT_FACTOR = 1.5;
   831       const double BF_LIMIT_FACTOR = 1.5;
   832       
   832 
   833       typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
   833       typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
   834       typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
   834       typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
   835       typedef StaticVectorMap<StaticDigraph::Node, StaticDigraph::Arc> PredMap;
   835       typedef StaticVectorMap<StaticDigraph::Node, StaticDigraph::Arc> PredMap;
   836       typedef typename BellmanFord<ResDigraph, CostArcMap>
   836       typedef typename BellmanFord<ResDigraph, CostArcMap>
   837         ::template SetDistMap<CostNodeMap>
   837         ::template SetDistMap<CostNodeMap>
   838         ::template SetPredMap<PredMap>::Create BF;
   838         ::template SetPredMap<PredMap>::Create BF;
   839       
   839 
   840       // Build the residual network
   840       // Build the residual network
   841       _arc_vec.clear();
   841       _arc_vec.clear();
   842       _cost_vec.clear();
   842       _cost_vec.clear();
   843       for (int j = 0; j != _res_arc_num; ++j) {
   843       for (int j = 0; j != _res_arc_num; ++j) {
   844         _arc_vec.push_back(IntPair(_source[j], _target[j]));
   844         _arc_vec.push_back(IntPair(_source[j], _target[j]));
   924     void startMinMeanCycleCanceling() {
   924     void startMinMeanCycleCanceling() {
   925       typedef SimplePath<StaticDigraph> SPath;
   925       typedef SimplePath<StaticDigraph> SPath;
   926       typedef typename SPath::ArcIt SPathArcIt;
   926       typedef typename SPath::ArcIt SPathArcIt;
   927       typedef typename HowardMmc<StaticDigraph, CostArcMap>
   927       typedef typename HowardMmc<StaticDigraph, CostArcMap>
   928         ::template SetPath<SPath>::Create MMC;
   928         ::template SetPath<SPath>::Create MMC;
   929       
   929 
   930       SPath cycle;
   930       SPath cycle;
   931       MMC mmc(_sgr, _cost_map);
   931       MMC mmc(_sgr, _cost_map);
   932       mmc.cycle(cycle);
   932       mmc.cycle(cycle);
   933       buildResidualNetwork();
   933       buildResidualNetwork();
   934       while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
   934       while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
   947           int j = _id_vec[_sgr.id(a)];
   947           int j = _id_vec[_sgr.id(a)];
   948           _res_cap[j] -= delta;
   948           _res_cap[j] -= delta;
   949           _res_cap[_reverse[j]] += delta;
   949           _res_cap[_reverse[j]] += delta;
   950         }
   950         }
   951 
   951 
   952         // Rebuild the residual network        
   952         // Rebuild the residual network
   953         buildResidualNetwork();
   953         buildResidualNetwork();
   954       }
   954       }
   955     }
   955     }
   956 
   956 
   957     // Execute the "Cancel And Tighten" method
   957     // Execute the "Cancel And Tighten" method
  1141           MMC mmc(_sgr, _cost_map);
  1141           MMC mmc(_sgr, _cost_map);
  1142           mmc.findCycleMean();
  1142           mmc.findCycleMean();
  1143           epsilon = -mmc.cycleMean();
  1143           epsilon = -mmc.cycleMean();
  1144           Cost cycle_cost = mmc.cycleCost();
  1144           Cost cycle_cost = mmc.cycleCost();
  1145           int cycle_size = mmc.cycleSize();
  1145           int cycle_size = mmc.cycleSize();
  1146           
  1146 
  1147           // Compute feasible potentials for the current epsilon
  1147           // Compute feasible potentials for the current epsilon
  1148           for (int i = 0; i != int(_cost_vec.size()); ++i) {
  1148           for (int i = 0; i != int(_cost_vec.size()); ++i) {
  1149             _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost;
  1149             _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost;
  1150           }
  1150           }
  1151           BF bf(_sgr, _cost_map);
  1151           BF bf(_sgr, _cost_map);
  1153           bf.init(0);
  1153           bf.init(0);
  1154           bf.start();
  1154           bf.start();
  1155           for (int u = 0; u != _res_node_num; ++u) {
  1155           for (int u = 0; u != _res_node_num; ++u) {
  1156             pi[u] = static_cast<double>(_pi[u]) / cycle_size;
  1156             pi[u] = static_cast<double>(_pi[u]) / cycle_size;
  1157           }
  1157           }
  1158         
  1158 
  1159           iter = limit;
  1159           iter = limit;
  1160         }
  1160         }
  1161       }
  1161       }
  1162     }
  1162     }
  1163 
  1163