COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r991 r978  
    167167    typedef std::vector<Value> ValueVector;
    168168    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<signed char> CharVector;
    170     // Note: vector<signed char> is used instead of vector<ArcState> and
    171     // vector<ArcDirection> for efficiency reasons
     169    typedef std::vector<char> BoolVector;
     170    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    172171
    173172    // State constants for arcs
     
    178177    };
    179178
    180     // Direction constants for tree arcs
    181     enum ArcDirection {
    182       DIR_DOWN = -1,
    183       DIR_UP   =  1
    184     };
     179    typedef std::vector<signed char> StateVector;
     180    // Note: vector<signed char> is used instead of vector<ArcState> for
     181    // efficiency reasons
    185182
    186183  private:
     
    221218    IntVector _succ_num;
    222219    IntVector _last_succ;
    223     CharVector _pred_dir;
    224     CharVector _state;
    225220    IntVector _dirty_revs;
     221    BoolVector _forward;
     222    StateVector _state;
    226223    int _root;
    227224
    228225    // Temporary data used in the current pivot iteration
    229226    int in_arc, join, u_in, v_in, u_out, v_out;
     227    int first, second, right, last;
     228    int stem, par_stem, new_stem;
    230229    Value delta;
    231230
     
    252251      const IntVector  &_target;
    253252      const CostVector &_cost;
    254       const CharVector &_state;
     253      const StateVector &_state;
    255254      const CostVector &_pi;
    256255      int &_in_arc;
     
    304303      const IntVector  &_target;
    305304      const CostVector &_cost;
    306       const CharVector &_state;
     305      const StateVector &_state;
    307306      const CostVector &_pi;
    308307      int &_in_arc;
     
    343342      const IntVector  &_target;
    344343      const CostVector &_cost;
    345       const CharVector &_state;
     344      const StateVector &_state;
    346345      const CostVector &_pi;
    347346      int &_in_arc;
     
    416415      const IntVector  &_target;
    417416      const CostVector &_cost;
    418       const CharVector &_state;
     417      const StateVector &_state;
    419418      const CostVector &_pi;
    420419      int &_in_arc;
     
    519518      const IntVector  &_target;
    520519      const CostVector &_cost;
    521       const CharVector &_state;
     520      const StateVector &_state;
    522521      const CostVector &_pi;
    523522      int &_in_arc;
     
    572571        // Check the current candidate list
    573572        int e;
    574         Cost c;
    575573        for (int i = 0; i != _curr_length; ++i) {
    576574          e = _candidates[i];
    577           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    578           if (c < 0) {
    579             _cand_cost[e] = c;
    580           } else {
     575          _cand_cost[e] = _state[e] *
     576            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     577          if (_cand_cost[e] >= 0) {
    581578            _candidates[i--] = _candidates[--_curr_length];
    582579          }
     
    588585
    589586        for (e = _next_arc; e != _search_arc_num; ++e) {
    590           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    591           if (c < 0) {
    592             _cand_cost[e] = c;
     587          _cand_cost[e] = _state[e] *
     588            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     589          if (_cand_cost[e] < 0) {
    593590            _candidates[_curr_length++] = e;
    594591          }
     
    637634    ///
    638635    /// \param graph The digraph the algorithm runs on.
    639     /// \param arc_mixing Indicate if the arcs will be stored in a
     636    /// \param arc_mixing Indicate if the arcs have to be stored in a
    640637    /// mixed order in the internal data structure.
    641     /// In general, it leads to similar performance as using the original
    642     /// arc order, but it makes the algorithm more robust and in special
    643     /// cases, even significantly faster. Therefore, it is enabled by default.
    644     NetworkSimplex(const GR& graph, bool arc_mixing = true) :
     638    /// In special cases, it could lead to better overall performance,
     639    /// but it is usually slower. Therefore it is disabled by default.
     640    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    645641      _graph(graph), _node_id(graph), _arc_id(graph),
    646642      _arc_mixing(arc_mixing),
     
    918914      _parent.resize(all_node_num);
    919915      _pred.resize(all_node_num);
    920       _pred_dir.resize(all_node_num);
     916      _forward.resize(all_node_num);
    921917      _thread.resize(all_node_num);
    922918      _rev_thread.resize(all_node_num);
     
    932928      if (_arc_mixing) {
    933929        // Store the arcs in a mixed order
    934         const int skip = std::max(_arc_num / _node_num, 3);
     930        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    935931        int i = 0, j = 0;
    936932        for (ArcIt a(_graph); a != INVALID; ++a) {
     
    938934          _source[i] = _node_id[_graph.source(a)];
    939935          _target[i] = _node_id[_graph.target(a)];
    940           if ((i += skip) >= _arc_num) i = ++j;
     936          if ((i += k) >= _arc_num) i = ++j;
    941937        }
    942938      } else {
     
    11211117          _state[e] = STATE_TREE;
    11221118          if (_supply[u] >= 0) {
    1123             _pred_dir[u] = DIR_UP;
     1119            _forward[u] = true;
    11241120            _pi[u] = 0;
    11251121            _source[e] = u;
     
    11281124            _cost[e] = 0;
    11291125          } else {
    1130             _pred_dir[u] = DIR_DOWN;
     1126            _forward[u] = false;
    11311127            _pi[u] = ART_COST;
    11321128            _source[e] = _root;
     
    11481144          _last_succ[u] = u;
    11491145          if (_supply[u] >= 0) {
    1150             _pred_dir[u] = DIR_UP;
     1146            _forward[u] = true;
    11511147            _pi[u] = 0;
    11521148            _pred[u] = e;
     
    11581154            _state[e] = STATE_TREE;
    11591155          } else {
    1160             _pred_dir[u] = DIR_DOWN;
     1156            _forward[u] = false;
    11611157            _pi[u] = ART_COST;
    11621158            _pred[u] = f;
     
    11891185          _last_succ[u] = u;
    11901186          if (_supply[u] <= 0) {
    1191             _pred_dir[u] = DIR_DOWN;
     1187            _forward[u] = false;
    11921188            _pi[u] = 0;
    11931189            _pred[u] = e;
     
    11991195            _state[e] = STATE_TREE;
    12001196          } else {
    1201             _pred_dir[u] = DIR_UP;
     1197            _forward[u] = true;
    12021198            _pi[u] = -ART_COST;
    12031199            _pred[u] = f;
     
    12421238      // Initialize first and second nodes according to the direction
    12431239      // of the cycle
    1244       int first, second;
    12451240      if (_state[in_arc] == STATE_LOWER) {
    12461241        first  = _source[in_arc];
     
    12521247      delta = _cap[in_arc];
    12531248      int result = 0;
    1254       Value c, d;
     1249      Value d;
    12551250      int e;
    12561251
    1257       // Search the cycle form the first node to the join node
     1252      // Search the cycle along the path form the first node to the root
    12581253      for (int u = first; u != join; u = _parent[u]) {
    12591254        e = _pred[u];
    1260         d = _flow[e];
    1261         if (_pred_dir[u] == DIR_DOWN) {
    1262           c = _cap[e];
    1263           d = c >= MAX ? INF : c - d;
    1264         }
     1255        d = _forward[u] ?
     1256          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12651257        if (d < delta) {
    12661258          delta = d;
     
    12691261        }
    12701262      }
    1271 
    1272       // Search the cycle form the second node to the join node
     1263      // Search the cycle along the path form the second node to the root
    12731264      for (int u = second; u != join; u = _parent[u]) {
    12741265        e = _pred[u];
    1275         d = _flow[e];
    1276         if (_pred_dir[u] == DIR_UP) {
    1277           c = _cap[e];
    1278           d = c >= MAX ? INF : c - d;
    1279         }
     1266        d = _forward[u] ?
     1267          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12801268        if (d <= delta) {
    12811269          delta = d;
     
    13021290        _flow[in_arc] += val;
    13031291        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1304           _flow[_pred[u]] -= _pred_dir[u] * val;
     1292          _flow[_pred[u]] += _forward[u] ? -val : val;
    13051293        }
    13061294        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1307           _flow[_pred[u]] += _pred_dir[u] * val;
     1295          _flow[_pred[u]] += _forward[u] ? val : -val;
    13081296        }
    13091297      }
     
    13201308    // Update the tree structure
    13211309    void updateTreeStructure() {
     1310      int u, w;
    13221311      int old_rev_thread = _rev_thread[u_out];
    13231312      int old_succ_num = _succ_num[u_out];
     
    13251314      v_out = _parent[u_out];
    13261315
    1327       // Check if u_in and u_out coincide
    1328       if (u_in == u_out) {
    1329         // Update _parent, _pred, _pred_dir
    1330         _parent[u_in] = v_in;
    1331         _pred[u_in] = in_arc;
    1332         _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
    1333 
    1334         // Update _thread and _rev_thread
    1335         if (_thread[v_in] != u_out) {
    1336           int after = _thread[old_last_succ];
    1337           _thread[old_rev_thread] = after;
    1338           _rev_thread[after] = old_rev_thread;
    1339           after = _thread[v_in];
    1340           _thread[v_in] = u_out;
    1341           _rev_thread[u_out] = v_in;
    1342           _thread[old_last_succ] = after;
    1343           _rev_thread[after] = old_last_succ;
    1344         }
     1316      u = _last_succ[u_in];  // the last successor of u_in
     1317      right = _thread[u];    // the node after it
     1318
     1319      // Handle the case when old_rev_thread equals to v_in
     1320      // (it also means that join and v_out coincide)
     1321      if (old_rev_thread == v_in) {
     1322        last = _thread[_last_succ[u_out]];
    13451323      } else {
    1346         // Handle the case when old_rev_thread equals to v_in
    1347         // (it also means that join and v_out coincide)
    1348         int thread_continue = old_rev_thread == v_in ?
    1349           _thread[old_last_succ] : _thread[v_in];
    1350 
    1351         // Update _thread and _parent along the stem nodes (i.e. the nodes
    1352         // between u_in and u_out, whose parent have to be changed)
    1353         int stem = u_in;              // the current stem node
    1354         int par_stem = v_in;          // the new parent of stem
    1355         int next_stem;                // the next stem node
    1356         int last = _last_succ[u_in];  // the last successor of stem
    1357         int before, after = _thread[last];
    1358         _thread[v_in] = u_in;
    1359         _dirty_revs.clear();
    1360         _dirty_revs.push_back(v_in);
    1361         while (stem != u_out) {
    1362           // Insert the next stem node into the thread list
    1363           next_stem = _parent[stem];
    1364           _thread[last] = next_stem;
    1365           _dirty_revs.push_back(last);
    1366 
    1367           // Remove the subtree of stem from the thread list
    1368           before = _rev_thread[stem];
    1369           _thread[before] = after;
    1370           _rev_thread[after] = before;
    1371 
    1372           // Change the parent node and shift stem nodes
    1373           _parent[stem] = par_stem;
    1374           par_stem = stem;
    1375           stem = next_stem;
    1376 
    1377           // Update last and after
    1378           last = _last_succ[stem] == _last_succ[par_stem] ?
    1379             _rev_thread[par_stem] : _last_succ[stem];
    1380           after = _thread[last];
    1381         }
    1382         _parent[u_out] = par_stem;
    1383         _thread[last] = thread_continue;
    1384         _rev_thread[thread_continue] = last;
    1385         _last_succ[u_out] = last;
    1386 
    1387         // Remove the subtree of u_out from the thread list except for
    1388         // the case when old_rev_thread equals to v_in
    1389         if (old_rev_thread != v_in) {
    1390           _thread[old_rev_thread] = after;
    1391           _rev_thread[after] = old_rev_thread;
    1392         }
    1393 
    1394         // Update _rev_thread using the new _thread values
    1395         for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    1396           int u = _dirty_revs[i];
    1397           _rev_thread[_thread[u]] = u;
    1398         }
    1399 
    1400         // Update _pred, _pred_dir, _last_succ and _succ_num for the
    1401         // stem nodes from u_out to u_in
    1402         int tmp_sc = 0, tmp_ls = _last_succ[u_out];
    1403         for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
    1404           _pred[u] = _pred[p];
    1405           _pred_dir[u] = -_pred_dir[p];
    1406           tmp_sc += _succ_num[u] - _succ_num[p];
    1407           _succ_num[u] = tmp_sc;
    1408           _last_succ[p] = tmp_ls;
    1409         }
    1410         _pred[u_in] = in_arc;
    1411         _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
    1412         _succ_num[u_in] = old_succ_num;
     1324        last = _thread[v_in];
     1325      }
     1326
     1327      // Update _thread and _parent along the stem nodes (i.e. the nodes
     1328      // between u_in and u_out, whose parent have to be changed)
     1329      _thread[v_in] = stem = u_in;
     1330      _dirty_revs.clear();
     1331      _dirty_revs.push_back(v_in);
     1332      par_stem = v_in;
     1333      while (stem != u_out) {
     1334        // Insert the next stem node into the thread list
     1335        new_stem = _parent[stem];
     1336        _thread[u] = new_stem;
     1337        _dirty_revs.push_back(u);
     1338
     1339        // Remove the subtree of stem from the thread list
     1340        w = _rev_thread[stem];
     1341        _thread[w] = right;
     1342        _rev_thread[right] = w;
     1343
     1344        // Change the parent node and shift stem nodes
     1345        _parent[stem] = par_stem;
     1346        par_stem = stem;
     1347        stem = new_stem;
     1348
     1349        // Update u and right
     1350        u = _last_succ[stem] == _last_succ[par_stem] ?
     1351          _rev_thread[par_stem] : _last_succ[stem];
     1352        right = _thread[u];
     1353      }
     1354      _parent[u_out] = par_stem;
     1355      _thread[u] = last;
     1356      _rev_thread[last] = u;
     1357      _last_succ[u_out] = u;
     1358
     1359      // Remove the subtree of u_out from the thread list except for
     1360      // the case when old_rev_thread equals to v_in
     1361      // (it also means that join and v_out coincide)
     1362      if (old_rev_thread != v_in) {
     1363        _thread[old_rev_thread] = right;
     1364        _rev_thread[right] = old_rev_thread;
     1365      }
     1366
     1367      // Update _rev_thread using the new _thread values
     1368      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
     1369        u = _dirty_revs[i];
     1370        _rev_thread[_thread[u]] = u;
     1371      }
     1372
     1373      // Update _pred, _forward, _last_succ and _succ_num for the
     1374      // stem nodes from u_out to u_in
     1375      int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1376      u = u_out;
     1377      while (u != u_in) {
     1378        w = _parent[u];
     1379        _pred[u] = _pred[w];
     1380        _forward[u] = !_forward[w];
     1381        tmp_sc += _succ_num[u] - _succ_num[w];
     1382        _succ_num[u] = tmp_sc;
     1383        _last_succ[w] = tmp_ls;
     1384        u = w;
     1385      }
     1386      _pred[u_in] = in_arc;
     1387      _forward[u_in] = (u_in == _source[in_arc]);
     1388      _succ_num[u_in] = old_succ_num;
     1389
     1390      // Set limits for updating _last_succ form v_in and v_out
     1391      // towards the root
     1392      int up_limit_in = -1;
     1393      int up_limit_out = -1;
     1394      if (_last_succ[join] == v_in) {
     1395        up_limit_out = join;
     1396      } else {
     1397        up_limit_in = join;
    14131398      }
    14141399
    14151400      // Update _last_succ from v_in towards the root
    1416       int up_limit_out = _last_succ[join] == v_in ? join : -1;
    1417       int last_succ_out = _last_succ[u_out];
    1418       for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
    1419         _last_succ[u] = last_succ_out;
    1420       }
    1421 
     1401      for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
     1402           u = _parent[u]) {
     1403        _last_succ[u] = _last_succ[u_out];
     1404      }
    14221405      // Update _last_succ from v_out towards the root
    14231406      if (join != old_rev_thread && v_in != old_rev_thread) {
    1424         for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1407        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14251408             u = _parent[u]) {
    14261409          _last_succ[u] = old_rev_thread;
    14271410        }
    1428       }
    1429       else if (last_succ_out != old_last_succ) {
    1430         for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1411      } else {
     1412        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14311413             u = _parent[u]) {
    1432           _last_succ[u] = last_succ_out;
     1414          _last_succ[u] = _last_succ[u_out];
    14331415        }
    14341416      }
    14351417
    14361418      // Update _succ_num from v_in to join
    1437       for (int u = v_in; u != join; u = _parent[u]) {
     1419      for (u = v_in; u != join; u = _parent[u]) {
    14381420        _succ_num[u] += old_succ_num;
    14391421      }
    14401422      // Update _succ_num from v_out to join
    1441       for (int u = v_out; u != join; u = _parent[u]) {
     1423      for (u = v_out; u != join; u = _parent[u]) {
    14421424        _succ_num[u] -= old_succ_num;
    14431425      }
    14441426    }
    14451427
    1446     // Update potentials in the subtree that has been moved
     1428    // Update potentials
    14471429    void updatePotential() {
    1448       Cost sigma = _pi[v_in] - _pi[u_in] -
    1449                    _pred_dir[u_in] * _cost[in_arc];
     1430      Cost sigma = _forward[u_in] ?
     1431        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
     1432        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
     1433      // Update potentials in the subtree, which has been moved
    14501434      int end = _thread[_last_succ[u_in]];
    14511435      for (int u = u_in; u != end; u = _thread[u]) {
Note: See TracChangeset for help on using the changeset viewer.