lemon/network_simplex.h
changeset 811 fe80a8145653
parent 788 c92296660262
child 812 4b1b378823dc
equal deleted inserted replaced
22:03a38fee3dad 23:1307e8c80f3e
   162   private:
   162   private:
   163 
   163 
   164     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   164     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   165 
   165 
   166     typedef std::vector<int> IntVector;
   166     typedef std::vector<int> IntVector;
   167     typedef std::vector<bool> BoolVector;
   167     typedef std::vector<char> CharVector;
   168     typedef std::vector<Value> ValueVector;
   168     typedef std::vector<Value> ValueVector;
   169     typedef std::vector<Cost> CostVector;
   169     typedef std::vector<Cost> CostVector;
   170 
   170 
   171     // State constants for arcs
   171     // State constants for arcs
   172     enum ArcStateEnum {
   172     enum ArcStateEnum {
   210     IntVector _thread;
   210     IntVector _thread;
   211     IntVector _rev_thread;
   211     IntVector _rev_thread;
   212     IntVector _succ_num;
   212     IntVector _succ_num;
   213     IntVector _last_succ;
   213     IntVector _last_succ;
   214     IntVector _dirty_revs;
   214     IntVector _dirty_revs;
   215     BoolVector _forward;
   215     CharVector _forward;
   216     IntVector _state;
   216     CharVector _state;
   217     int _root;
   217     int _root;
   218 
   218 
   219     // Temporary data used in the current pivot iteration
   219     // Temporary data used in the current pivot iteration
   220     int in_arc, join, u_in, v_in, u_out, v_out;
   220     int in_arc, join, u_in, v_in, u_out, v_out;
   221     int first, second, right, last;
   221     int first, second, right, last;
   222     int stem, par_stem, new_stem;
   222     int stem, par_stem, new_stem;
   223     Value delta;
   223     Value delta;
       
   224     
       
   225     const Value MAX;
   224 
   226 
   225   public:
   227   public:
   226   
   228   
   227     /// \brief Constant for infinite upper bounds (capacities).
   229     /// \brief Constant for infinite upper bounds (capacities).
   228     ///
   230     ///
   240 
   242 
   241       // References to the NetworkSimplex class
   243       // References to the NetworkSimplex class
   242       const IntVector  &_source;
   244       const IntVector  &_source;
   243       const IntVector  &_target;
   245       const IntVector  &_target;
   244       const CostVector &_cost;
   246       const CostVector &_cost;
   245       const IntVector  &_state;
   247       const CharVector &_state;
   246       const CostVector &_pi;
   248       const CostVector &_pi;
   247       int &_in_arc;
   249       int &_in_arc;
   248       int _search_arc_num;
   250       int _search_arc_num;
   249 
   251 
   250       // Pivot rule data
   252       // Pivot rule data
   292 
   294 
   293       // References to the NetworkSimplex class
   295       // References to the NetworkSimplex class
   294       const IntVector  &_source;
   296       const IntVector  &_source;
   295       const IntVector  &_target;
   297       const IntVector  &_target;
   296       const CostVector &_cost;
   298       const CostVector &_cost;
   297       const IntVector  &_state;
   299       const CharVector &_state;
   298       const CostVector &_pi;
   300       const CostVector &_pi;
   299       int &_in_arc;
   301       int &_in_arc;
   300       int _search_arc_num;
   302       int _search_arc_num;
   301 
   303 
   302     public:
   304     public:
   331 
   333 
   332       // References to the NetworkSimplex class
   334       // References to the NetworkSimplex class
   333       const IntVector  &_source;
   335       const IntVector  &_source;
   334       const IntVector  &_target;
   336       const IntVector  &_target;
   335       const CostVector &_cost;
   337       const CostVector &_cost;
   336       const IntVector  &_state;
   338       const CharVector &_state;
   337       const CostVector &_pi;
   339       const CostVector &_pi;
   338       int &_in_arc;
   340       int &_in_arc;
   339       int _search_arc_num;
   341       int _search_arc_num;
   340 
   342 
   341       // Pivot rule data
   343       // Pivot rule data
   404 
   406 
   405       // References to the NetworkSimplex class
   407       // References to the NetworkSimplex class
   406       const IntVector  &_source;
   408       const IntVector  &_source;
   407       const IntVector  &_target;
   409       const IntVector  &_target;
   408       const CostVector &_cost;
   410       const CostVector &_cost;
   409       const IntVector  &_state;
   411       const CharVector &_state;
   410       const CostVector &_pi;
   412       const CostVector &_pi;
   411       int &_in_arc;
   413       int &_in_arc;
   412       int _search_arc_num;
   414       int _search_arc_num;
   413 
   415 
   414       // Pivot rule data
   416       // Pivot rule data
   507 
   509 
   508       // References to the NetworkSimplex class
   510       // References to the NetworkSimplex class
   509       const IntVector  &_source;
   511       const IntVector  &_source;
   510       const IntVector  &_target;
   512       const IntVector  &_target;
   511       const CostVector &_cost;
   513       const CostVector &_cost;
   512       const IntVector  &_state;
   514       const CharVector &_state;
   513       const CostVector &_pi;
   515       const CostVector &_pi;
   514       int &_in_arc;
   516       int &_in_arc;
   515       int _search_arc_num;
   517       int _search_arc_num;
   516 
   518 
   517       // Pivot rule data
   519       // Pivot rule data
   629     /// mixed order in the internal data structure. 
   631     /// mixed order in the internal data structure. 
   630     /// In special cases, it could lead to better overall performance,
   632     /// In special cases, it could lead to better overall performance,
   631     /// but it is usually slower. Therefore it is disabled by default.
   633     /// but it is usually slower. Therefore it is disabled by default.
   632     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
   634     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
   633       _graph(graph), _node_id(graph), _arc_id(graph),
   635       _graph(graph), _node_id(graph), _arc_id(graph),
       
   636       MAX(std::numeric_limits<Value>::max()),
   634       INF(std::numeric_limits<Value>::has_infinity ?
   637       INF(std::numeric_limits<Value>::has_infinity ?
   635           std::numeric_limits<Value>::infinity() :
   638           std::numeric_limits<Value>::infinity() : MAX)
   636           std::numeric_limits<Value>::max())
       
   637     {
   639     {
   638       // Check the value types
   640       // Check the value types
   639       LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
   641       LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
   640         "The flow type of NetworkSimplex must be signed");
   642         "The flow type of NetworkSimplex must be signed");
   641       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
   643       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
  1018       // Remove non-zero lower bounds
  1020       // Remove non-zero lower bounds
  1019       if (_have_lower) {
  1021       if (_have_lower) {
  1020         for (int i = 0; i != _arc_num; ++i) {
  1022         for (int i = 0; i != _arc_num; ++i) {
  1021           Value c = _lower[i];
  1023           Value c = _lower[i];
  1022           if (c >= 0) {
  1024           if (c >= 0) {
  1023             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
  1025             _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
  1024           } else {
  1026           } else {
  1025             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
  1027             _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
  1026           }
  1028           }
  1027           _supply[_source[i]] -= c;
  1029           _supply[_source[i]] -= c;
  1028           _supply[_target[i]] += c;
  1030           _supply[_target[i]] += c;
  1029         }
  1031         }
  1030       } else {
  1032       } else {
  1212 
  1214 
  1213       // Search the cycle along the path form the first node to the root
  1215       // Search the cycle along the path form the first node to the root
  1214       for (int u = first; u != join; u = _parent[u]) {
  1216       for (int u = first; u != join; u = _parent[u]) {
  1215         e = _pred[u];
  1217         e = _pred[u];
  1216         d = _forward[u] ?
  1218         d = _forward[u] ?
  1217           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
  1219           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
  1218         if (d < delta) {
  1220         if (d < delta) {
  1219           delta = d;
  1221           delta = d;
  1220           u_out = u;
  1222           u_out = u;
  1221           result = 1;
  1223           result = 1;
  1222         }
  1224         }
  1223       }
  1225       }
  1224       // Search the cycle along the path form the second node to the root
  1226       // Search the cycle along the path form the second node to the root
  1225       for (int u = second; u != join; u = _parent[u]) {
  1227       for (int u = second; u != join; u = _parent[u]) {
  1226         e = _pred[u];
  1228         e = _pred[u];
  1227         d = _forward[u] ? 
  1229         d = _forward[u] ? 
  1228           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
  1230           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
  1229         if (d <= delta) {
  1231         if (d <= delta) {
  1230           delta = d;
  1232           delta = d;
  1231           u_out = u;
  1233           u_out = u;
  1232           result = 2;
  1234           result = 2;
  1233         }
  1235         }
  1422 
  1424 
  1423       // Execute the Network Simplex algorithm
  1425       // Execute the Network Simplex algorithm
  1424       while (pivot.findEnteringArc()) {
  1426       while (pivot.findEnteringArc()) {
  1425         findJoinNode();
  1427         findJoinNode();
  1426         bool change = findLeavingArc();
  1428         bool change = findLeavingArc();
  1427         if (delta >= INF) return UNBOUNDED;
  1429         if (delta >= MAX) return UNBOUNDED;
  1428         changeFlow(change);
  1430         changeFlow(change);
  1429         if (change) {
  1431         if (change) {
  1430           updateTreeStructure();
  1432           updateTreeStructure();
  1431           updatePotential();
  1433           updatePotential();
  1432         }
  1434         }