lemon-main: comparison lemon/network

equal deleted inserted replaced

-:e623f11c9e8f
+:e2bc0f061520
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 typedef std::vector<int> IntVector;
-typedef std::vector<char> CharVector;
 typedef std::vector<Value> ValueVector;
 typedef std::vector<Cost> CostVector;
+typedef std::vector<char> BoolVector;
+// Note: vector<char> is used instead of vector<bool> for efficiency reasons
 // State constants for arcs
 enum ArcStateEnum {
 STATE_UPPER = -1,
 STATE_TREE  =  0,
 IntVector _thread;
 IntVector _rev_thread;
 IntVector _succ_num;
 IntVector _last_succ;
 IntVector _dirty_revs;
-CharVector _forward;
+BoolVector _forward;
-CharVector _state;
+BoolVector _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;
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const CharVector &_state;
+const BoolVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 {}
 // Find next entering arc
 bool findEnteringArc() {
 Cost c;
-for (int e = _next_arc; e < _search_arc_num; ++e) {
+for (int e = _next_arc; e != _search_arc_num; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < 0) {
 _in_arc = e;
 _next_arc = e + 1;
 return true;
 }
 }
-for (int e = 0; e < _next_arc; ++e) {
+for (int e = 0; e != _next_arc; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < 0) {
 _in_arc = e;
 _next_arc = e + 1;
 return true;
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const CharVector &_state;
+const BoolVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 public:
 {}
 // Find next entering arc
 bool findEnteringArc() {
 Cost c, min = 0;
-for (int e = 0; e < _search_arc_num; ++e) {
+for (int e = 0; e != _search_arc_num; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < min) {
 min = c;
 _in_arc = e;
 }
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const CharVector &_state;
+const BoolVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 _next_arc(0)
 {
 // The main parameters of the pivot rule
-const double BLOCK_SIZE_FACTOR = 0.5;
+const double BLOCK_SIZE_FACTOR = 1.0;
 const int MIN_BLOCK_SIZE = 10;
 _block_size = std::max( int(BLOCK_SIZE_FACTOR *
 std::sqrt(double(_search_arc_num))),
 MIN_BLOCK_SIZE );
 // Find next entering arc
 bool findEnteringArc() {
 Cost c, min = 0;
 int cnt = _block_size;
 int e;
-for (e = _next_arc; e < _search_arc_num; ++e) {
+for (e = _next_arc; e != _search_arc_num; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < min) {
 min = c;
 _in_arc = e;
 }
 if (--cnt == 0) {
 if (min < 0) goto search_end;
 cnt = _block_size;
 }
 }
-for (e = 0; e < _next_arc; ++e) {
+for (e = 0; e != _next_arc; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < min) {
 min = c;
 _in_arc = e;
 }
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const CharVector &_state;
+const BoolVector &_state;
 const CostVector &_pi;
 int &_in_arc;
 int _search_arc_num;
 // Pivot rule data
 }
 // Major iteration: build a new candidate list
 min = 0;
 _curr_length = 0;
-for (e = _next_arc; e < _search_arc_num; ++e) {
+for (e = _next_arc; e != _search_arc_num; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < 0) {
 _candidates[_curr_length++] = e;
 if (c < min) {
 min = c;
 _in_arc = e;
 }
 if (_curr_length == _list_length) goto search_end;
 }
 }
-for (e = 0; e < _next_arc; ++e) {
+for (e = 0; e != _next_arc; ++e) {
 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (c < 0) {
 _candidates[_curr_length++] = e;
 if (c < min) {
 min = c;
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
 const CostVector &_cost;
-const CharVector &_state;
+const BoolVector &_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;
-for (int i = 0; i < _curr_length; ++i) {
+for (int i = 0; i != _curr_length; ++i) {
 e = _candidates[i];
 _cand_cost[e] = _state[e] *
 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (_cand_cost[e] >= 0) {
 _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) {
+for (e = _next_arc; e != _search_arc_num; ++e) {
 _cand_cost[e] = _state[e] *
 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (_cand_cost[e] < 0) {
 _candidates[_curr_length++] = e;
 }
 if (_curr_length > limit) goto search_end;
 limit = 0;
 cnt = _block_size;
 }
 }
-for (e = 0; e < _next_arc; ++e) {
+for (e = 0; e != _next_arc; ++e) {
 _cand_cost[e] = _state[e] *
 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 if (_cand_cost[e] < 0) {
 _candidates[_curr_length++] = e;
 }
 _thread[old_rev_thread] = right;
 _rev_thread[right] = old_rev_thread;
 }
 // Update _rev_thread using the new _thread values
-for (int i = 0; i < int(_dirty_revs.size()); ++i) {
+for (int i = 0; i != int(_dirty_revs.size()); ++i) {
 u = _dirty_revs[i];
 _rev_thread[_thread[u]] = u;
 }
 // Update _pred, _forward, _last_succ and _succ_num for the
 // 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;
 }
+}
+// Heuristic initial pivots
+bool initialPivots() {
+Value curr, total = 0;
+std::vector<Node> supply_nodes, demand_nodes;
+for (NodeIt u(_graph); u != INVALID; ++u) {
+curr = _supply[_node_id[u]];
+if (curr > 0) {
+total += curr;
+supply_nodes.push_back(u);
+}
+else if (curr < 0) {
+demand_nodes.push_back(u);
+}
+}
+if (_sum_supply > 0) total -= _sum_supply;
+if (total <= 0) return true;
+IntVector arc_vector;
+if (_sum_supply >= 0) {
+if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
+// Perform a reverse graph search from the sink to the source
+typename GR::template NodeMap<bool> reached(_graph, false);
+Node s = supply_nodes[0], t = demand_nodes[0];
+std::vector<Node> stack;
+reached[t] = true;
+stack.push_back(t);
+while (!stack.empty()) {
+Node u, v = stack.back();
+stack.pop_back();
+if (v == s) break;
+for (InArcIt a(_graph, v); a != INVALID; ++a) {
+if (reached[u = _graph.source(a)]) continue;
+int j = _arc_id[a];
+if (_cap[j] >= total) {
+arc_vector.push_back(j);
+reached[u] = true;
+stack.push_back(u);
+}
+}
+}
+} else {
+// Find the min. cost incomming arc for each demand node
+for (int i = 0; i != int(demand_nodes.size()); ++i) {
+Node v = demand_nodes[i];
+Cost c, min_cost = std::numeric_limits<Cost>::max();
+Arc min_arc = INVALID;
+for (InArcIt a(_graph, v); a != INVALID; ++a) {
+c = _cost[_arc_id[a]];
+if (c < min_cost) {
+min_cost = c;
+min_arc = a;
+}
+}
+if (min_arc != INVALID) {
+arc_vector.push_back(_arc_id[min_arc]);
+}
+}
+}
+} else {
+// Find the min. cost outgoing arc for each supply node
+for (int i = 0; i != int(supply_nodes.size()); ++i) {
+Node u = supply_nodes[i];
+Cost c, min_cost = std::numeric_limits<Cost>::max();
+Arc min_arc = INVALID;
+for (OutArcIt a(_graph, u); a != INVALID; ++a) {
+c = _cost[_arc_id[a]];
+if (c < min_cost) {
+min_cost = c;
+min_arc = a;
+}
+}
+if (min_arc != INVALID) {
+arc_vector.push_back(_arc_id[min_arc]);
+}
+}
+}
+// Perform heuristic initial pivots
+for (int i = 0; i != int(arc_vector.size()); ++i) {
+in_arc = arc_vector[i];
+if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -
+_pi[_target[in_arc]]) >= 0) continue;
+findJoinNode();
+bool change = findLeavingArc();
+if (delta >= MAX) return false;
+changeFlow(change);
+if (change) {
+updateTreeStructure();
+updatePotential();
+}
+}
+return true;
 }
 // Execute the algorithm
 ProblemType start(PivotRule pivot_rule) {
 // Select the pivot rule implementation
 template <typename PivotRuleImpl>
 ProblemType start() {
 PivotRuleImpl pivot(*this);
+// Perform heuristic initial pivots
+if (!initialPivots()) return UNBOUNDED;
 // Execute the Network Simplex algorithm
 while (pivot.findEnteringArc()) {
 findJoinNode();
 bool change = findLeavingArc();
 if (delta >= MAX) return UNBOUNDED;

changeset 839	f3bc4e9b5f3a
parent 812	4b1b378823dc
child 840	2914b6f0fde0