1.1 --- a/lemon/hao_orlin.h Mon Dec 01 23:15:15 2008 +0100
1.2 +++ b/lemon/hao_orlin.h Tue Dec 02 08:21:47 2008 +0100
1.3 @@ -225,57 +225,47 @@
1.4 _flow->set(a, 0);
1.5 }
1.6
1.7 - int bucket_num = 1;
1.8 + int bucket_num = 0;
1.9 + std::vector<Node> queue(_node_num);
1.10 + int qfirst = 0, qlast = 0, qsep = 0;
1.11
1.12 {
1.13 typename Digraph::template NodeMap<bool> reached(_graph, false);
1.14
1.15 reached.set(_source, true);
1.16 -
1.17 bool first_set = true;
1.18
1.19 for (NodeIt t(_graph); t != INVALID; ++t) {
1.20 if (reached[t]) continue;
1.21 _sets.push_front(std::list<int>());
1.22 - _sets.front().push_front(bucket_num);
1.23 - _dormant[bucket_num] = !first_set;
1.24 -
1.25 - _bucket->set(t, bucket_num);
1.26 - _first[bucket_num] = _last[bucket_num] = t;
1.27 - _next->set(t, INVALID);
1.28 - _prev->set(t, INVALID);
1.29 -
1.30 - ++bucket_num;
1.31 -
1.32 - std::vector<Node> queue;
1.33 - queue.push_back(t);
1.34 +
1.35 + queue[qlast++] = t;
1.36 reached.set(t, true);
1.37
1.38 - while (!queue.empty()) {
1.39 - _sets.front().push_front(bucket_num);
1.40 - _dormant[bucket_num] = !first_set;
1.41 - _first[bucket_num] = _last[bucket_num] = INVALID;
1.42 + while (qfirst != qlast) {
1.43 + if (qsep == qfirst) {
1.44 + ++bucket_num;
1.45 + _sets.front().push_front(bucket_num);
1.46 + _dormant[bucket_num] = !first_set;
1.47 + _first[bucket_num] = _last[bucket_num] = INVALID;
1.48 + qsep = qlast;
1.49 + }
1.50
1.51 - std::vector<Node> nqueue;
1.52 - for (int i = 0; i < int(queue.size()); ++i) {
1.53 - Node n = queue[i];
1.54 - for (InArcIt a(_graph, n); a != INVALID; ++a) {
1.55 - Node u = _graph.source(a);
1.56 - if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.57 - reached.set(u, true);
1.58 - addItem(u, bucket_num);
1.59 - nqueue.push_back(u);
1.60 - }
1.61 + Node n = queue[qfirst++];
1.62 + addItem(n, bucket_num);
1.63 +
1.64 + for (InArcIt a(_graph, n); a != INVALID; ++a) {
1.65 + Node u = _graph.source(a);
1.66 + if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.67 + reached.set(u, true);
1.68 + queue[qlast++] = u;
1.69 }
1.70 }
1.71 - queue.swap(nqueue);
1.72 - ++bucket_num;
1.73 }
1.74 - _sets.front().pop_front();
1.75 - --bucket_num;
1.76 first_set = false;
1.77 }
1.78
1.79 + ++bucket_num;
1.80 _bucket->set(_source, 0);
1.81 _dormant[0] = true;
1.82 }
1.83 @@ -534,7 +524,9 @@
1.84 _flow->set(a, 0);
1.85 }
1.86
1.87 - int bucket_num = 1;
1.88 + int bucket_num = 0;
1.89 + std::vector<Node> queue(_node_num);
1.90 + int qfirst = 0, qlast = 0, qsep = 0;
1.91
1.92 {
1.93 typename Digraph::template NodeMap<bool> reached(_graph, false);
1.94 @@ -546,45 +538,34 @@
1.95 for (NodeIt t(_graph); t != INVALID; ++t) {
1.96 if (reached[t]) continue;
1.97 _sets.push_front(std::list<int>());
1.98 - _sets.front().push_front(bucket_num);
1.99 - _dormant[bucket_num] = !first_set;
1.100 -
1.101 - _bucket->set(t, bucket_num);
1.102 - _first[bucket_num] = _last[bucket_num] = t;
1.103 - _next->set(t, INVALID);
1.104 - _prev->set(t, INVALID);
1.105 -
1.106 - ++bucket_num;
1.107 -
1.108 - std::vector<Node> queue;
1.109 - queue.push_back(t);
1.110 +
1.111 + queue[qlast++] = t;
1.112 reached.set(t, true);
1.113
1.114 - while (!queue.empty()) {
1.115 - _sets.front().push_front(bucket_num);
1.116 - _dormant[bucket_num] = !first_set;
1.117 - _first[bucket_num] = _last[bucket_num] = INVALID;
1.118 + while (qfirst != qlast) {
1.119 + if (qsep == qfirst) {
1.120 + ++bucket_num;
1.121 + _sets.front().push_front(bucket_num);
1.122 + _dormant[bucket_num] = !first_set;
1.123 + _first[bucket_num] = _last[bucket_num] = INVALID;
1.124 + qsep = qlast;
1.125 + }
1.126
1.127 - std::vector<Node> nqueue;
1.128 - for (int i = 0; i < int(queue.size()); ++i) {
1.129 - Node n = queue[i];
1.130 - for (OutArcIt a(_graph, n); a != INVALID; ++a) {
1.131 - Node u = _graph.target(a);
1.132 - if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.133 - reached.set(u, true);
1.134 - addItem(u, bucket_num);
1.135 - nqueue.push_back(u);
1.136 - }
1.137 + Node n = queue[qfirst++];
1.138 + addItem(n, bucket_num);
1.139 +
1.140 + for (OutArcIt a(_graph, n); a != INVALID; ++a) {
1.141 + Node u = _graph.target(a);
1.142 + if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.143 + reached.set(u, true);
1.144 + queue[qlast++] = u;
1.145 }
1.146 }
1.147 - queue.swap(nqueue);
1.148 - ++bucket_num;
1.149 }
1.150 - _sets.front().pop_front();
1.151 - --bucket_num;
1.152 first_set = false;
1.153 }
1.154
1.155 + ++bucket_num;
1.156 _bucket->set(_source, 0);
1.157 _dormant[0] = true;
1.158 }
1.159 @@ -864,10 +845,10 @@
1.160
1.161 _node_num = countNodes(_graph);
1.162
1.163 - _first.resize(_node_num + 1);
1.164 - _last.resize(_node_num + 1);
1.165 + _first.resize(_node_num);
1.166 + _last.resize(_node_num);
1.167
1.168 - _dormant.resize(_node_num + 1);
1.169 + _dormant.resize(_node_num);
1.170
1.171 if (!_flow) {
1.172 _flow = new FlowMap(_graph);