COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r978 r991  
    167167    typedef std::vector<Value> ValueVector;
    168168    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<char> BoolVector;
    170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     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
    171172
    172173    // State constants for arcs
     
    177178    };
    178179
    179     typedef std::vector<signed char> StateVector;
    180     // Note: vector<signed char> is used instead of vector<ArcState> for
    181     // efficiency reasons
     180    // Direction constants for tree arcs
     181    enum ArcDirection {
     182      DIR_DOWN = -1,
     183      DIR_UP   =  1
     184    };
    182185
    183186  private:
     
    218221    IntVector _succ_num;
    219222    IntVector _last_succ;
     223    CharVector _pred_dir;
     224    CharVector _state;
    220225    IntVector _dirty_revs;
    221     BoolVector _forward;
    222     StateVector _state;
    223226    int _root;
    224227
    225228    // Temporary data used in the current pivot iteration
    226229    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;
    229230    Value delta;
    230231
     
    251252      const IntVector  &_target;
    252253      const CostVector &_cost;
    253       const StateVector &_state;
     254      const CharVector &_state;
    254255      const CostVector &_pi;
    255256      int &_in_arc;
     
    303304      const IntVector  &_target;
    304305      const CostVector &_cost;
    305       const StateVector &_state;
     306      const CharVector &_state;
    306307      const CostVector &_pi;
    307308      int &_in_arc;
     
    342343      const IntVector  &_target;
    343344      const CostVector &_cost;
    344       const StateVector &_state;
     345      const CharVector &_state;
    345346      const CostVector &_pi;
    346347      int &_in_arc;
     
    415416      const IntVector  &_target;
    416417      const CostVector &_cost;
    417       const StateVector &_state;
     418      const CharVector &_state;
    418419      const CostVector &_pi;
    419420      int &_in_arc;
     
    518519      const IntVector  &_target;
    519520      const CostVector &_cost;
    520       const StateVector &_state;
     521      const CharVector &_state;
    521522      const CostVector &_pi;
    522523      int &_in_arc;
     
    571572        // Check the current candidate list
    572573        int e;
     574        Cost c;
    573575        for (int i = 0; i != _curr_length; ++i) {
    574576          e = _candidates[i];
    575           _cand_cost[e] = _state[e] *
    576             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    577           if (_cand_cost[e] >= 0) {
     577          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     578          if (c < 0) {
     579            _cand_cost[e] = c;
     580          } else {
    578581            _candidates[i--] = _candidates[--_curr_length];
    579582          }
     
    585588
    586589        for (e = _next_arc; e != _search_arc_num; ++e) {
    587           _cand_cost[e] = _state[e] *
    588             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    589           if (_cand_cost[e] < 0) {
     590          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     591          if (c < 0) {
     592            _cand_cost[e] = c;
    590593            _candidates[_curr_length++] = e;
    591594          }
     
    634637    ///
    635638    /// \param graph The digraph the algorithm runs on.
    636     /// \param arc_mixing Indicate if the arcs have to be stored in a
     639    /// \param arc_mixing Indicate if the arcs will be stored in a
    637640    /// mixed order in the internal data structure.
    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) :
     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) :
    641645      _graph(graph), _node_id(graph), _arc_id(graph),
    642646      _arc_mixing(arc_mixing),
     
    914918      _parent.resize(all_node_num);
    915919      _pred.resize(all_node_num);
    916       _forward.resize(all_node_num);
     920      _pred_dir.resize(all_node_num);
    917921      _thread.resize(all_node_num);
    918922      _rev_thread.resize(all_node_num);
     
    928932      if (_arc_mixing) {
    929933        // Store the arcs in a mixed order
    930         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     934        const int skip = std::max(_arc_num / _node_num, 3);
    931935        int i = 0, j = 0;
    932936        for (ArcIt a(_graph); a != INVALID; ++a) {
     
    934938          _source[i] = _node_id[_graph.source(a)];
    935939          _target[i] = _node_id[_graph.target(a)];
    936           if ((i += k) >= _arc_num) i = ++j;
     940          if ((i += skip) >= _arc_num) i = ++j;
    937941        }
    938942      } else {
     
    11171121          _state[e] = STATE_TREE;
    11181122          if (_supply[u] >= 0) {
    1119             _forward[u] = true;
     1123            _pred_dir[u] = DIR_UP;
    11201124            _pi[u] = 0;
    11211125            _source[e] = u;
     
    11241128            _cost[e] = 0;
    11251129          } else {
    1126             _forward[u] = false;
     1130            _pred_dir[u] = DIR_DOWN;
    11271131            _pi[u] = ART_COST;
    11281132            _source[e] = _root;
     
    11441148          _last_succ[u] = u;
    11451149          if (_supply[u] >= 0) {
    1146             _forward[u] = true;
     1150            _pred_dir[u] = DIR_UP;
    11471151            _pi[u] = 0;
    11481152            _pred[u] = e;
     
    11541158            _state[e] = STATE_TREE;
    11551159          } else {
    1156             _forward[u] = false;
     1160            _pred_dir[u] = DIR_DOWN;
    11571161            _pi[u] = ART_COST;
    11581162            _pred[u] = f;
     
    11851189          _last_succ[u] = u;
    11861190          if (_supply[u] <= 0) {
    1187             _forward[u] = false;
     1191            _pred_dir[u] = DIR_DOWN;
    11881192            _pi[u] = 0;
    11891193            _pred[u] = e;
     
    11951199            _state[e] = STATE_TREE;
    11961200          } else {
    1197             _forward[u] = true;
     1201            _pred_dir[u] = DIR_UP;
    11981202            _pi[u] = -ART_COST;
    11991203            _pred[u] = f;
     
    12381242      // Initialize first and second nodes according to the direction
    12391243      // of the cycle
     1244      int first, second;
    12401245      if (_state[in_arc] == STATE_LOWER) {
    12411246        first  = _source[in_arc];
     
    12471252      delta = _cap[in_arc];
    12481253      int result = 0;
    1249       Value d;
     1254      Value c, d;
    12501255      int e;
    12511256
    1252       // Search the cycle along the path form the first node to the root
     1257      // Search the cycle form the first node to the join node
    12531258      for (int u = first; u != join; u = _parent[u]) {
    12541259        e = _pred[u];
    1255         d = _forward[u] ?
    1256           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1260        d = _flow[e];
     1261        if (_pred_dir[u] == DIR_DOWN) {
     1262          c = _cap[e];
     1263          d = c >= MAX ? INF : c - d;
     1264        }
    12571265        if (d < delta) {
    12581266          delta = d;
     
    12611269        }
    12621270      }
    1263       // Search the cycle along the path form the second node to the root
     1271
     1272      // Search the cycle form the second node to the join node
    12641273      for (int u = second; u != join; u = _parent[u]) {
    12651274        e = _pred[u];
    1266         d = _forward[u] ?
    1267           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1275        d = _flow[e];
     1276        if (_pred_dir[u] == DIR_UP) {
     1277          c = _cap[e];
     1278          d = c >= MAX ? INF : c - d;
     1279        }
    12681280        if (d <= delta) {
    12691281          delta = d;
     
    12901302        _flow[in_arc] += val;
    12911303        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1292           _flow[_pred[u]] += _forward[u] ? -val : val;
     1304          _flow[_pred[u]] -= _pred_dir[u] * val;
    12931305        }
    12941306        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1295           _flow[_pred[u]] += _forward[u] ? val : -val;
     1307          _flow[_pred[u]] += _pred_dir[u] * val;
    12961308        }
    12971309      }
     
    13081320    // Update the tree structure
    13091321    void updateTreeStructure() {
    1310       int u, w;
    13111322      int old_rev_thread = _rev_thread[u_out];
    13121323      int old_succ_num = _succ_num[u_out];
     
    13141325      v_out = _parent[u_out];
    13151326
    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]];
     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        }
    13231345      } else {
    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;
     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;
    13981413      }
    13991414
    14001415      // Update _last_succ from v_in towards the root
    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       }
     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
    14051422      // Update _last_succ from v_out towards the root
    14061423      if (join != old_rev_thread && v_in != old_rev_thread) {
    1407         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1424        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14081425             u = _parent[u]) {
    14091426          _last_succ[u] = old_rev_thread;
    14101427        }
    1411       } else {
    1412         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     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;
    14131431             u = _parent[u]) {
    1414           _last_succ[u] = _last_succ[u_out];
     1432          _last_succ[u] = last_succ_out;
    14151433        }
    14161434      }
    14171435
    14181436      // Update _succ_num from v_in to join
    1419       for (u = v_in; u != join; u = _parent[u]) {
     1437      for (int u = v_in; u != join; u = _parent[u]) {
    14201438        _succ_num[u] += old_succ_num;
    14211439      }
    14221440      // Update _succ_num from v_out to join
    1423       for (u = v_out; u != join; u = _parent[u]) {
     1441      for (int u = v_out; u != join; u = _parent[u]) {
    14241442        _succ_num[u] -= old_succ_num;
    14251443      }
    14261444    }
    14271445
    1428     // Update potentials
     1446    // Update potentials in the subtree that has been moved
    14291447    void updatePotential() {
    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
     1448      Cost sigma = _pi[v_in] - _pi[u_in] -
     1449                   _pred_dir[u_in] * _cost[in_arc];
    14341450      int end = _thread[_last_succ[u_in]];
    14351451      for (int u = u_in; u != end; u = _thread[u]) {
Note: See TracChangeset for help on using the changeset viewer.