lemon/cycle_canceling.h
branch1.3
changeset 1133 85d6e26096ef
parent 1092 dceba191c00d
parent 1110 c0c2f5c87aa6
equal deleted inserted replaced
20:1c34cb46888e 23:df3c8dbab35a
   193     int _res_node_num;
   193     int _res_node_num;
   194     int _res_arc_num;
   194     int _res_arc_num;
   195     int _root;
   195     int _root;
   196 
   196 
   197     // Parameters of the problem
   197     // Parameters of the problem
   198     bool _have_lower;
   198     bool _has_lower;
   199     Value _sum_supply;
   199     Value _sum_supply;
   200 
   200 
   201     // Data structures for storing the digraph
   201     // Data structures for storing the digraph
   202     IntNodeMap _node_id;
   202     IntNodeMap _node_id;
   203     IntArcMap _arc_idf;
   203     IntArcMap _arc_idf;
   276     /// of the algorithm.
   276     /// of the algorithm.
   277     ///
   277     ///
   278     /// \return <tt>(*this)</tt>
   278     /// \return <tt>(*this)</tt>
   279     template <typename LowerMap>
   279     template <typename LowerMap>
   280     CycleCanceling& lowerMap(const LowerMap& map) {
   280     CycleCanceling& lowerMap(const LowerMap& map) {
   281       _have_lower = true;
   281       _has_lower = true;
   282       for (ArcIt a(_graph); a != INVALID; ++a) {
   282       for (ArcIt a(_graph); a != INVALID; ++a) {
   283         _lower[_arc_idf[a]] = map[a];
   283         _lower[_arc_idf[a]] = map[a];
   284         _lower[_arc_idb[a]] = map[a];
       
   285       }
   284       }
   286       return *this;
   285       return *this;
   287     }
   286     }
   288 
   287 
   289     /// \brief Set the upper bounds (capacities) on the arcs.
   288     /// \brief Set the upper bounds (capacities) on the arcs.
   469         _lower[j] = 0;
   468         _lower[j] = 0;
   470         _upper[j] = INF;
   469         _upper[j] = INF;
   471         _cost[j] = 0;
   470         _cost[j] = 0;
   472         _cost[_reverse[j]] = 0;
   471         _cost[_reverse[j]] = 0;
   473       }
   472       }
   474       _have_lower = false;
   473       _has_lower = false;
   475       return *this;
   474       return *this;
   476     }
   475     }
   477 
   476 
   478     /// \brief Reset the internal data structures and all the parameters
   477     /// \brief Reset the internal data structures and all the parameters
   479     /// that have been given before.
   478     /// that have been given before.
   682       ValueVector excess(_supply);
   681       ValueVector excess(_supply);
   683 
   682 
   684       // Remove infinite upper bounds and check negative arcs
   683       // Remove infinite upper bounds and check negative arcs
   685       const Value MAX = std::numeric_limits<Value>::max();
   684       const Value MAX = std::numeric_limits<Value>::max();
   686       int last_out;
   685       int last_out;
   687       if (_have_lower) {
   686       if (_has_lower) {
   688         for (int i = 0; i != _root; ++i) {
   687         for (int i = 0; i != _root; ++i) {
   689           last_out = _first_out[i+1];
   688           last_out = _first_out[i+1];
   690           for (int j = _first_out[i]; j != last_out; ++j) {
   689           for (int j = _first_out[i]; j != last_out; ++j) {
   691             if (_forward[j]) {
   690             if (_forward[j]) {
   692               Value c = _cost[j] < 0 ? _upper[j] : _lower[j];
   691               Value c = _cost[j] < 0 ? _upper[j] : _lower[j];
   725       ValueArcMap cap(_graph), flow(_graph);
   724       ValueArcMap cap(_graph), flow(_graph);
   726       ValueNodeMap sup(_graph);
   725       ValueNodeMap sup(_graph);
   727       for (NodeIt n(_graph); n != INVALID; ++n) {
   726       for (NodeIt n(_graph); n != INVALID; ++n) {
   728         sup[n] = _supply[_node_id[n]];
   727         sup[n] = _supply[_node_id[n]];
   729       }
   728       }
   730       if (_have_lower) {
   729       if (_has_lower) {
   731         for (ArcIt a(_graph); a != INVALID; ++a) {
   730         for (ArcIt a(_graph); a != INVALID; ++a) {
   732           int j = _arc_idf[a];
   731           int j = _arc_idf[a];
   733           Value c = _lower[j];
   732           Value c = _lower[j];
   734           cap[a] = _upper[j] - c;
   733           cap[a] = _upper[j] - c;
   735           sup[_graph.source(a)] -= c;
   734           sup[_graph.source(a)] -= c;
   782       }
   781       }
   783 
   782 
   784       return OPTIMAL;
   783       return OPTIMAL;
   785     }
   784     }
   786 
   785 
   787     // Check if the upper bound is greater or equal to the lower bound
   786     // Check if the upper bound is greater than or equal to the lower bound
   788     // on each arc.
   787     // on each forward arc.
   789     bool checkBoundMaps() {
   788     bool checkBoundMaps() {
   790       for (int j = 0; j != _res_arc_num; ++j) {
   789       for (int j = 0; j != _res_arc_num; ++j) {
   791         if (_upper[j] < _lower[j]) return false;
   790         if (_forward[j] && _upper[j] < _lower[j]) return false;
   792       }
   791       }
   793       return true;
   792       return true;
   794     }
   793     }
   795 
   794 
   796     // Build a StaticDigraph structure containing the current
   795     // Build a StaticDigraph structure containing the current
   833         bf.init(0);
   832         bf.init(0);
   834         bf.start();
   833         bf.start();
   835       }
   834       }
   836 
   835 
   837       // Handle non-zero lower bounds
   836       // Handle non-zero lower bounds
   838       if (_have_lower) {
   837       if (_has_lower) {
   839         int limit = _first_out[_root];
   838         int limit = _first_out[_root];
   840         for (int j = 0; j != limit; ++j) {
   839         for (int j = 0; j != limit; ++j) {
   841           if (!_forward[j]) _res_cap[j] += _lower[j];
   840           if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
   842         }
   841         }
   843       }
   842       }
   844     }
   843     }
   845 
   844 
   846     // Execute the "Simple Cycle Canceling" method
   845     // Execute the "Simple Cycle Canceling" method