lemon-1.3: comparison lemon/network

equal deleted inserted replaced

-:ab65107fbc11
+:955f5986005d
 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 typedef std::vector<int> IntVector;
 typedef std::vector<Value> ValueVector;
 typedef std::vector<Cost> CostVector;
-typedef std::vector<char> BoolVector;
+typedef std::vector<signed char> CharVector;
-// Note: vector<char> is used instead of vector<bool> for efficiency reasons
+// Note: vector<signed char> is used instead of vector<ArcState> and
+// vector<ArcDirection> for efficiency reasons
 // State constants for arcs
 enum ArcState {
 STATE_UPPER = -1,
 STATE_TREE  =  0,
 STATE_LOWER =  1
 };
-typedef std::vector<signed char> StateVector;
+// Direction constants for tree arcs
-// Note: vector<signed char> is used instead of vector<ArcState> for
+enum ArcDirection {
-// efficiency reasons
+DIR_DOWN = -1,
+DIR_UP   =  1
+};
 private:
 // Data related to the underlying digraph
 const GR &_graph;
 IntVector _pred;
 IntVector _thread;
 IntVector _rev_thread;
 IntVector _succ_num;
 IntVector _last_succ;
+CharVector _pred_dir;
+CharVector _state;
 IntVector _dirty_revs;
-BoolVector _forward;
-StateVector _state;
 int _root;
 // Temporary data used in the current pivot iteration
 int in_arc, join, u_in, v_in, u_out, v_out;
-int first, second, right, last;
-int stem, par_stem, new_stem;
 Value delta;
 const Value MAX;
 public:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const StateVector &_state;
+const CharVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const StateVector &_state;
+const CharVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 public:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const StateVector &_state;
+const CharVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const StateVector &_state;
+const CharVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const StateVector &_state;
+const CharVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 // Find next entering arc
 bool findEnteringArc() {
 // Check the current candidate list
 int e;
+Cost c;
 for (int i = 0; i != _curr_length; ++i) {
 e = _candidates[i];
-_cand_cost[e] = _state[e] *
+c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-(_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+if (c < 0) {
-if (_cand_cost[e] >= 0) {
+_cand_cost[e] = c;
+} else {
 _candidates[i--] = _candidates[--_curr_length];
 }
 }
 // Extend the list
 int cnt = _block_size;
 int limit = _head_length;
 for (e = _next_arc; e != _search_arc_num; ++e) {
-_cand_cost[e] = _state[e] *
+c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-(_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+if (c < 0) {
-if (_cand_cost[e] < 0) {
+_cand_cost[e] = c;
 _candidates[_curr_length++] = e;
 }
 if (--cnt == 0) {
 if (_curr_length > limit) goto search_end;
 limit = 0;
 _flow.resize(max_arc_num);
 _pi.resize(all_node_num);
 _parent.resize(all_node_num);
 _pred.resize(all_node_num);
-_forward.resize(all_node_num);
+_pred_dir.resize(all_node_num);
 _thread.resize(all_node_num);
 _rev_thread.resize(all_node_num);
 _succ_num.resize(all_node_num);
 _last_succ.resize(all_node_num);
 _state.resize(max_arc_num);
 _succ_num[u] = 1;
 _last_succ[u] = u;
 _cap[e] = INF;
 _state[e] = STATE_TREE;
 if (_supply[u] >= 0) {
-_forward[u] = true;
+_pred_dir[u] = DIR_UP;
 _pi[u] = 0;
 _source[e] = u;
 _target[e] = _root;
 _flow[e] = _supply[u];
 _cost[e] = 0;
 } else {
-_forward[u] = false;
+_pred_dir[u] = DIR_DOWN;
 _pi[u] = ART_COST;
 _source[e] = _root;
 _target[e] = u;
 _flow[e] = -_supply[u];
 _cost[e] = ART_COST;
 _thread[u] = u + 1;
 _rev_thread[u + 1] = u;
 _succ_num[u] = 1;
 _last_succ[u] = u;
 if (_supply[u] >= 0) {
-_forward[u] = true;
+_pred_dir[u] = DIR_UP;
 _pi[u] = 0;
 _pred[u] = e;
 _source[e] = u;
 _target[e] = _root;
 _cap[e] = INF;
 _flow[e] = _supply[u];
 _cost[e] = 0;
 _state[e] = STATE_TREE;
 } else {
-_forward[u] = false;
+_pred_dir[u] = DIR_DOWN;
 _pi[u] = ART_COST;
 _pred[u] = f;
 _source[f] = _root;
 _target[f] = u;
 _cap[f] = INF;
 _thread[u] = u + 1;
 _rev_thread[u + 1] = u;
 _succ_num[u] = 1;
 _last_succ[u] = u;
 if (_supply[u] <= 0) {
-_forward[u] = false;
+_pred_dir[u] = DIR_DOWN;
 _pi[u] = 0;
 _pred[u] = e;
 _source[e] = _root;
 _target[e] = u;
 _cap[e] = INF;
 _flow[e] = -_supply[u];
 _cost[e] = 0;
 _state[e] = STATE_TREE;
 } else {
-_forward[u] = true;
+_pred_dir[u] = DIR_UP;
 _pi[u] = -ART_COST;
 _pred[u] = f;
 _source[f] = u;
 _target[f] = _root;
 _cap[f] = INF;
 // Find the leaving arc of the cycle and returns true if the
 // leaving arc is not the same as the entering arc
 bool findLeavingArc() {
 // Initialize first and second nodes according to the direction
 // of the cycle
+int first, second;
 if (_state[in_arc] == STATE_LOWER) {
 first  = _source[in_arc];
 second = _target[in_arc];
 } else {
 first  = _target[in_arc];
 second = _source[in_arc];
 }
 delta = _cap[in_arc];
 int result = 0;
-Value d;
+Value c, d;
 int e;
-// Search the cycle along the path form the first node to the root
+// Search the cycle form the first node to the join node
 for (int u = first; u != join; u = _parent[u]) {
 e = _pred[u];
-d = _forward[u] ?
+d = _flow[e];
-_flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
+if (_pred_dir[u] == DIR_DOWN) {
+c = _cap[e];
+d = c >= MAX ? INF : c - d;
+}
 if (d < delta) {
 delta = d;
 u_out = u;
 result = 1;
 }
 }
-// Search the cycle along the path form the second node to the root
+// Search the cycle form the second node to the join node
 for (int u = second; u != join; u = _parent[u]) {
 e = _pred[u];
-d = _forward[u] ?
+d = _flow[e];
-(_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
+if (_pred_dir[u] == DIR_UP) {
+c = _cap[e];
+d = c >= MAX ? INF : c - d;
+}
 if (d <= delta) {
 delta = d;
 u_out = u;
 result = 2;
 }
 // Augment along the cycle
 if (delta > 0) {
 Value val = _state[in_arc] * delta;
 _flow[in_arc] += val;
 for (int u = _source[in_arc]; u != join; u = _parent[u]) {
-_flow[_pred[u]] += _forward[u] ? -val : val;
+_flow[_pred[u]] -= _pred_dir[u] * val;
 }
 for (int u = _target[in_arc]; u != join; u = _parent[u]) {
-_flow[_pred[u]] += _forward[u] ? val : -val;
+_flow[_pred[u]] += _pred_dir[u] * val;
 }
 }
 // Update the state of the entering and leaving arcs
 if (change) {
 _state[in_arc] = STATE_TREE;
 }
 }
 // Update the tree structure
 void updateTreeStructure() {
-int u, w;
 int old_rev_thread = _rev_thread[u_out];
 int old_succ_num = _succ_num[u_out];
 int old_last_succ = _last_succ[u_out];
 v_out = _parent[u_out];
-u = _last_succ[u_in];  // the last successor of u_in
+// Check if u_in and u_out coincide
-right = _thread[u];    // the node after it
+if (u_in == u_out) {
+// Update _parent, _pred, _pred_dir
-// Handle the case when old_rev_thread equals to v_in
+_parent[u_in] = v_in;
-// (it also means that join and v_out coincide)
+_pred[u_in] = in_arc;
-if (old_rev_thread == v_in) {
+_pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
-last = _thread[_last_succ[u_out]];
+// Update _thread and _rev_thread
+if (_thread[v_in] != u_out) {
+int after = _thread[old_last_succ];
+_thread[old_rev_thread] = after;
+_rev_thread[after] = old_rev_thread;
+after = _thread[v_in];
+_thread[v_in] = u_out;
+_rev_thread[u_out] = v_in;
+_thread[old_last_succ] = after;
+_rev_thread[after] = old_last_succ;
+}
 } else {
-last = _thread[v_in];
+// Handle the case when old_rev_thread equals to v_in
-}
+// (it also means that join and v_out coincide)
+int thread_continue = old_rev_thread == v_in ?
-// Update _thread and _parent along the stem nodes (i.e. the nodes
+_thread[old_last_succ] : _thread[v_in];
-// between u_in and u_out, whose parent have to be changed)
-_thread[v_in] = stem = u_in;
+// Update _thread and _parent along the stem nodes (i.e. the nodes
-_dirty_revs.clear();
+// between u_in and u_out, whose parent have to be changed)
-_dirty_revs.push_back(v_in);
+int stem = u_in;              // the current stem node
-par_stem = v_in;
+int par_stem = v_in;          // the new parent of stem
-while (stem != u_out) {
+int next_stem;                // the next stem node
-// Insert the next stem node into the thread list
+int last = _last_succ[u_in];  // the last successor of stem
-new_stem = _parent[stem];
+int before, after = _thread[last];
-_thread[u] = new_stem;
+_thread[v_in] = u_in;
-_dirty_revs.push_back(u);
+_dirty_revs.clear();
+_dirty_revs.push_back(v_in);
-// Remove the subtree of stem from the thread list
+while (stem != u_out) {
-w = _rev_thread[stem];
+// Insert the next stem node into the thread list
-_thread[w] = right;
+next_stem = _parent[stem];
-_rev_thread[right] = w;
+_thread[last] = next_stem;
+_dirty_revs.push_back(last);
-// Change the parent node and shift stem nodes
-_parent[stem] = par_stem;
+// Remove the subtree of stem from the thread list
-par_stem = stem;
+before = _rev_thread[stem];
-stem = new_stem;
+_thread[before] = after;
+_rev_thread[after] = before;
-// Update u and right
-u = _last_succ[stem] == _last_succ[par_stem] ?
+// Change the parent node and shift stem nodes
-_rev_thread[par_stem] : _last_succ[stem];
+_parent[stem] = par_stem;
-right = _thread[u];
+par_stem = stem;
-}
+stem = next_stem;
-_parent[u_out] = par_stem;
-_thread[u] = last;
+// Update last and after
-_rev_thread[last] = u;
+last = _last_succ[stem] == _last_succ[par_stem] ?
-_last_succ[u_out] = u;
+_rev_thread[par_stem] : _last_succ[stem];
+after = _thread[last];
-// Remove the subtree of u_out from the thread list except for
+}
-// the case when old_rev_thread equals to v_in
+_parent[u_out] = par_stem;
-// (it also means that join and v_out coincide)
+_thread[last] = thread_continue;
-if (old_rev_thread != v_in) {
+_rev_thread[thread_continue] = last;
-_thread[old_rev_thread] = right;
+_last_succ[u_out] = last;
-_rev_thread[right] = old_rev_thread;
-}
+// Remove the subtree of u_out from the thread list except for
+// the case when old_rev_thread equals to v_in
-// Update _rev_thread using the new _thread values
+if (old_rev_thread != v_in) {
-for (int i = 0; i != int(_dirty_revs.size()); ++i) {
+_thread[old_rev_thread] = after;
-u = _dirty_revs[i];
+_rev_thread[after] = old_rev_thread;
-_rev_thread[_thread[u]] = u;
+}
-}
+// Update _rev_thread using the new _thread values
-// Update _pred, _forward, _last_succ and _succ_num for the
+for (int i = 0; i != int(_dirty_revs.size()); ++i) {
-// stem nodes from u_out to u_in
+int u = _dirty_revs[i];
-int tmp_sc = 0, tmp_ls = _last_succ[u_out];
+_rev_thread[_thread[u]] = u;
-u = u_out;
+}
-while (u != u_in) {
-w = _parent[u];
+// Update _pred, _pred_dir, _last_succ and _succ_num for the
-_pred[u] = _pred[w];
+// stem nodes from u_out to u_in
-_forward[u] = !_forward[w];
+int tmp_sc = 0, tmp_ls = _last_succ[u_out];
-tmp_sc += _succ_num[u] - _succ_num[w];
+for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
-_succ_num[u] = tmp_sc;
+_pred[u] = _pred[p];
-_last_succ[w] = tmp_ls;
+_pred_dir[u] = -_pred_dir[p];
-u = w;
+tmp_sc += _succ_num[u] - _succ_num[p];
-}
+_succ_num[u] = tmp_sc;
-_pred[u_in] = in_arc;
+_last_succ[p] = tmp_ls;
-_forward[u_in] = (u_in == _source[in_arc]);
+}
-_succ_num[u_in] = old_succ_num;
+_pred[u_in] = in_arc;
+_pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
-// Set limits for updating _last_succ form v_in and v_out
+_succ_num[u_in] = old_succ_num;
-// towards the root
-int up_limit_in = -1;
-int up_limit_out = -1;
-if (_last_succ[join] == v_in) {
-up_limit_out = join;
-} else {
-up_limit_in = join;
 }
 // Update _last_succ from v_in towards the root
-for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
+int up_limit_out = _last_succ[join] == v_in ? join : -1;
-u = _parent[u]) {
+int last_succ_out = _last_succ[u_out];
-_last_succ[u] = _last_succ[u_out];
+for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
-}
+_last_succ[u] = last_succ_out;
+}
 // Update _last_succ from v_out towards the root
 if (join != old_rev_thread && v_in != old_rev_thread) {
-for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
+for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
 u = _parent[u]) {
 _last_succ[u] = old_rev_thread;
 }
-} else {
+}
-for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
+else if (last_succ_out != old_last_succ) {
+for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
 u = _parent[u]) {
-_last_succ[u] = _last_succ[u_out];
+_last_succ[u] = last_succ_out;
 }
 }
 // Update _succ_num from v_in to join
-for (u = v_in; u != join; u = _parent[u]) {
+for (int u = v_in; u != join; u = _parent[u]) {
 _succ_num[u] += old_succ_num;
 }
 // Update _succ_num from v_out to join
-for (u = v_out; u != join; u = _parent[u]) {
+for (int u = v_out; u != join; u = _parent[u]) {
 _succ_num[u] -= old_succ_num;
 }
 }
-// Update potentials
+// Update potentials in the subtree that has been moved
 void updatePotential() {
-Cost sigma = _forward[u_in] ?
+Cost sigma = _pi[v_in] - _pi[u_in] -
-_pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
+_pred_dir[u_in] * _cost[in_arc];
-_pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
-// Update potentials in the subtree, which has been moved
 int end = _thread[_last_succ[u_in]];
 for (int u = u_in; u != end; u = _thread[u]) {
 _pi[u] += sigma;
 }
 }

changeset 895	dca9eed2c375
parent 889	0bca98cbebbb
child 896	fb932bcfd803