1.1 --- a/lemon/network_simplex.h Thu Nov 12 23:34:35 2009 +0100
1.2 +++ b/lemon/network_simplex.h Thu Nov 12 23:45:15 2009 +0100
1.3 @@ -164,7 +164,7 @@
1.4 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.5
1.6 typedef std::vector<int> IntVector;
1.7 - typedef std::vector<bool> BoolVector;
1.8 + typedef std::vector<char> CharVector;
1.9 typedef std::vector<Value> ValueVector;
1.10 typedef std::vector<Cost> CostVector;
1.11
1.12 @@ -212,8 +212,8 @@
1.13 IntVector _succ_num;
1.14 IntVector _last_succ;
1.15 IntVector _dirty_revs;
1.16 - BoolVector _forward;
1.17 - IntVector _state;
1.18 + CharVector _forward;
1.19 + CharVector _state;
1.20 int _root;
1.21
1.22 // Temporary data used in the current pivot iteration
1.23 @@ -221,6 +221,8 @@
1.24 int first, second, right, last;
1.25 int stem, par_stem, new_stem;
1.26 Value delta;
1.27 +
1.28 + const Value MAX;
1.29
1.30 public:
1.31
1.32 @@ -242,7 +244,7 @@
1.33 const IntVector &_source;
1.34 const IntVector &_target;
1.35 const CostVector &_cost;
1.36 - const IntVector &_state;
1.37 + const CharVector &_state;
1.38 const CostVector &_pi;
1.39 int &_in_arc;
1.40 int _search_arc_num;
1.41 @@ -294,7 +296,7 @@
1.42 const IntVector &_source;
1.43 const IntVector &_target;
1.44 const CostVector &_cost;
1.45 - const IntVector &_state;
1.46 + const CharVector &_state;
1.47 const CostVector &_pi;
1.48 int &_in_arc;
1.49 int _search_arc_num;
1.50 @@ -333,7 +335,7 @@
1.51 const IntVector &_source;
1.52 const IntVector &_target;
1.53 const CostVector &_cost;
1.54 - const IntVector &_state;
1.55 + const CharVector &_state;
1.56 const CostVector &_pi;
1.57 int &_in_arc;
1.58 int _search_arc_num;
1.59 @@ -406,7 +408,7 @@
1.60 const IntVector &_source;
1.61 const IntVector &_target;
1.62 const CostVector &_cost;
1.63 - const IntVector &_state;
1.64 + const CharVector &_state;
1.65 const CostVector &_pi;
1.66 int &_in_arc;
1.67 int _search_arc_num;
1.68 @@ -509,7 +511,7 @@
1.69 const IntVector &_source;
1.70 const IntVector &_target;
1.71 const CostVector &_cost;
1.72 - const IntVector &_state;
1.73 + const CharVector &_state;
1.74 const CostVector &_pi;
1.75 int &_in_arc;
1.76 int _search_arc_num;
1.77 @@ -631,9 +633,9 @@
1.78 /// but it is usually slower. Therefore it is disabled by default.
1.79 NetworkSimplex(const GR& graph, bool arc_mixing = false) :
1.80 _graph(graph), _node_id(graph), _arc_id(graph),
1.81 + MAX(std::numeric_limits<Value>::max()),
1.82 INF(std::numeric_limits<Value>::has_infinity ?
1.83 - std::numeric_limits<Value>::infinity() :
1.84 - std::numeric_limits<Value>::max())
1.85 + std::numeric_limits<Value>::infinity() : MAX)
1.86 {
1.87 // Check the value types
1.88 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
1.89 @@ -1020,9 +1022,9 @@
1.90 for (int i = 0; i != _arc_num; ++i) {
1.91 Value c = _lower[i];
1.92 if (c >= 0) {
1.93 - _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
1.94 + _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
1.95 } else {
1.96 - _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
1.97 + _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
1.98 }
1.99 _supply[_source[i]] -= c;
1.100 _supply[_target[i]] += c;
1.101 @@ -1214,7 +1216,7 @@
1.102 for (int u = first; u != join; u = _parent[u]) {
1.103 e = _pred[u];
1.104 d = _forward[u] ?
1.105 - _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
1.106 + _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
1.107 if (d < delta) {
1.108 delta = d;
1.109 u_out = u;
1.110 @@ -1225,7 +1227,7 @@
1.111 for (int u = second; u != join; u = _parent[u]) {
1.112 e = _pred[u];
1.113 d = _forward[u] ?
1.114 - (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
1.115 + (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
1.116 if (d <= delta) {
1.117 delta = d;
1.118 u_out = u;
1.119 @@ -1424,7 +1426,7 @@
1.120 while (pivot.findEnteringArc()) {
1.121 findJoinNode();
1.122 bool change = findLeavingArc();
1.123 - if (delta >= INF) return UNBOUNDED;
1.124 + if (delta >= MAX) return UNBOUNDED;
1.125 changeFlow(change);
1.126 if (change) {
1.127 updateTreeStructure();