# HG changeset patch # User Peter Kovacs # Date 1239698138 -7200 # Node ID aa1804409f29bdd5a1a41e480897cec0b5e5df00 # Parent 2313edd0db0bc70d7c72eca4b0404f79ef22ea61 Exploit that the standard maps are reference maps (#190) diff -r 2313edd0db0b -r aa1804409f29 lemon/circulation.h --- a/lemon/circulation.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/circulation.h Tue Apr 14 10:35:38 2009 +0200 @@ -453,13 +453,13 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + (*_excess)[n] = (*_delta)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { _flow->set(e, (*_lo)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); + (*_excess)[_g.target(e)] += (*_flow)[e]; + (*_excess)[_g.source(e)] -= (*_flow)[e]; } // global relabeling tested, but in general case it provides @@ -482,23 +482,23 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + (*_excess)[n] = (*_delta)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { _flow->set(e, (*_up)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); + (*_excess)[_g.target(e)] += (*_up)[e]; + (*_excess)[_g.source(e)] -= (*_up)[e]; } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { _flow->set(e, (*_lo)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]); + (*_excess)[_g.target(e)] += (*_lo)[e]; + (*_excess)[_g.source(e)] -= (*_lo)[e]; } else { Value fc = -(*_excess)[_g.target(e)]; _flow->set(e, fc); - _excess->set(_g.target(e), 0); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); + (*_excess)[_g.target(e)] = 0; + (*_excess)[_g.source(e)] -= fc; } } @@ -537,16 +537,16 @@ if((*_level)[v]set(e, (*_flow)[e] + exc); - _excess->set(v, (*_excess)[v] + exc); + (*_excess)[v] += exc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); - _excess->set(act,0); + (*_excess)[act] = 0; _level->deactivate(act); goto next_l; } else { _flow->set(e, (*_up)[e]); - _excess->set(v, (*_excess)[v] + fc); + (*_excess)[v] += fc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); exc-=fc; @@ -561,16 +561,16 @@ if((*_level)[v]set(e, (*_flow)[e] - exc); - _excess->set(v, (*_excess)[v] + exc); + (*_excess)[v] += exc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); - _excess->set(act,0); + (*_excess)[act] = 0; _level->deactivate(act); goto next_l; } else { _flow->set(e, (*_lo)[e]); - _excess->set(v, (*_excess)[v] + fc); + (*_excess)[v] += fc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); exc-=fc; @@ -579,7 +579,7 @@ else if((*_level)[v]set(act, exc); + (*_excess)[act] = exc; if(!_tol.positive(exc)) _level->deactivate(act); else if(mlevel==_node_num) { _level->liftHighestActiveToTop(); diff -r 2313edd0db0b -r aa1804409f29 lemon/core.h --- a/lemon/core.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/core.h Tue Apr 14 10:35:38 2009 +0200 @@ -1315,27 +1315,27 @@ virtual void clear() { for(NodeIt n(_g);n!=INVALID;++n) { - _head.set(n, INVALID); + _head[n] = INVALID; } } void insert(Arc arc) { Node s = _g.source(arc); Node t = _g.target(arc); - _left.set(arc, INVALID); - _right.set(arc, INVALID); + _left[arc] = INVALID; + _right[arc] = INVALID; Arc e = _head[s]; if (e == INVALID) { - _head.set(s, arc); - _parent.set(arc, INVALID); + _head[s] = arc; + _parent[arc] = INVALID; return; } while (true) { if (t < _g.target(e)) { if (_left[e] == INVALID) { - _left.set(e, arc); - _parent.set(arc, e); + _left[e] = arc; + _parent[arc] = e; splay(arc); return; } else { @@ -1343,8 +1343,8 @@ } } else { if (_right[e] == INVALID) { - _right.set(e, arc); - _parent.set(arc, e); + _right[e] = arc; + _parent[arc] = e; splay(arc); return; } else { @@ -1357,27 +1357,27 @@ void remove(Arc arc) { if (_left[arc] == INVALID) { if (_right[arc] != INVALID) { - _parent.set(_right[arc], _parent[arc]); + _parent[_right[arc]] = _parent[arc]; } if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], _right[arc]); + _left[_parent[arc]] = _right[arc]; } else { - _right.set(_parent[arc], _right[arc]); + _right[_parent[arc]] = _right[arc]; } } else { - _head.set(_g.source(arc), _right[arc]); + _head[_g.source(arc)] = _right[arc]; } } else if (_right[arc] == INVALID) { - _parent.set(_left[arc], _parent[arc]); + _parent[_left[arc]] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], _left[arc]); + _left[_parent[arc]] = _left[arc]; } else { - _right.set(_parent[arc], _left[arc]); + _right[_parent[arc]] = _left[arc]; } } else { - _head.set(_g.source(arc), _left[arc]); + _head[_g.source(arc)] = _left[arc]; } } else { Arc e = _left[arc]; @@ -1387,38 +1387,38 @@ e = _right[e]; } Arc s = _parent[e]; - _right.set(_parent[e], _left[e]); + _right[_parent[e]] = _left[e]; if (_left[e] != INVALID) { - _parent.set(_left[e], _parent[e]); + _parent[_left[e]] = _parent[e]; } - _left.set(e, _left[arc]); - _parent.set(_left[arc], e); - _right.set(e, _right[arc]); - _parent.set(_right[arc], e); + _left[e] = _left[arc]; + _parent[_left[arc]] = e; + _right[e] = _right[arc]; + _parent[_right[arc]] = e; - _parent.set(e, _parent[arc]); + _parent[e] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], e); + _left[_parent[arc]] = e; } else { - _right.set(_parent[arc], e); + _right[_parent[arc]] = e; } } splay(s); } else { - _right.set(e, _right[arc]); - _parent.set(_right[arc], e); - _parent.set(e, _parent[arc]); + _right[e] = _right[arc]; + _parent[_right[arc]] = e; + _parent[e] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], e); + _left[_parent[arc]] = e; } else { - _right.set(_parent[arc], e); + _right[_parent[arc]] = e; } } else { - _head.set(_g.source(arc), e); + _head[_g.source(arc)] = e; } } } @@ -1430,17 +1430,17 @@ Arc me=v[m]; if (a < m) { Arc left = refreshRec(v,a,m-1); - _left.set(me, left); - _parent.set(left, me); + _left[me] = left; + _parent[left] = me; } else { - _left.set(me, INVALID); + _left[me] = INVALID; } if (m < b) { Arc right = refreshRec(v,m+1,b); - _right.set(me, right); - _parent.set(right, me); + _right[me] = right; + _parent[right] = me; } else { - _right.set(me, INVALID); + _right[me] = INVALID; } return me; } @@ -1452,46 +1452,46 @@ if (!v.empty()) { std::sort(v.begin(),v.end(),ArcLess(_g)); Arc head = refreshRec(v,0,v.size()-1); - _head.set(n, head); - _parent.set(head, INVALID); + _head[n] = head; + _parent[head] = INVALID; } - else _head.set(n, INVALID); + else _head[n] = INVALID; } } void zig(Arc v) { Arc w = _parent[v]; - _parent.set(v, _parent[w]); - _parent.set(w, v); - _left.set(w, _right[v]); - _right.set(v, w); + _parent[v] = _parent[w]; + _parent[w] = v; + _left[w] = _right[v]; + _right[v] = w; if (_parent[v] != INVALID) { if (_right[_parent[v]] == w) { - _right.set(_parent[v], v); + _right[_parent[v]] = v; } else { - _left.set(_parent[v], v); + _left[_parent[v]] = v; } } if (_left[w] != INVALID){ - _parent.set(_left[w], w); + _parent[_left[w]] = w; } } void zag(Arc v) { Arc w = _parent[v]; - _parent.set(v, _parent[w]); - _parent.set(w, v); - _right.set(w, _left[v]); - _left.set(v, w); + _parent[v] = _parent[w]; + _parent[w] = v; + _right[w] = _left[v]; + _left[v] = w; if (_parent[v] != INVALID){ if (_left[_parent[v]] == w) { - _left.set(_parent[v], v); + _left[_parent[v]] = v; } else { - _right.set(_parent[v], v); + _right[_parent[v]] = v; } } if (_right[w] != INVALID){ - _parent.set(_right[w], w); + _parent[_right[w]] = w; } } diff -r 2313edd0db0b -r aa1804409f29 lemon/elevator.h --- a/lemon/elevator.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/elevator.h Tue Apr 14 10:35:38 2009 +0200 @@ -76,7 +76,7 @@ void copy(Item i, Vit p) { - _where.set(*p=i,p); + _where[*p=i] = p; } void copy(Vit s, Vit p) { @@ -84,15 +84,15 @@ { Item i=*s; *p=i; - _where.set(i,p); + _where[i] = p; } } void swap(Vit i, Vit j) { Item ti=*i; Vit ct = _where[ti]; - _where.set(ti,_where[*i=*j]); - _where.set(*j,ct); + _where[ti] = _where[*i=*j]; + _where[*j] = ct; *j=ti; } @@ -226,7 +226,7 @@ void liftHighestActive() { Item it = *_last_active[_highest_active]; - _level.set(it,_level[it]+1); + ++_level[it]; swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); --_first[++_highest_active]; } @@ -249,7 +249,7 @@ --_last_active[l]; } copy(li,_first[new_level]); - _level.set(li,new_level); + _level[li] = new_level; _highest_active=new_level; } @@ -269,7 +269,7 @@ } copy(li,_first[_max_level]); --_last_active[_max_level]; - _level.set(li,_max_level); + _level[li] = _max_level; while(_highest_active>=0 && _last_active[_highest_active]<_first[_highest_active]) @@ -299,7 +299,7 @@ Item liftActiveOn(int level) { Item it =*_last_active[level]; - _level.set(it,_level[it]+1); + ++_level[it]; swap(_last_active[level]--, --_first[level+1]); if (level+1>_highest_active) ++_highest_active; } @@ -319,7 +319,7 @@ copy(--_first[l+1], _last_active[l]--); } copy(ai,_first[new_level]); - _level.set(ai,new_level); + _level[ai] = new_level; if (new_level>_highest_active) _highest_active=new_level; } @@ -339,7 +339,7 @@ } copy(ai,_first[_max_level]); --_last_active[_max_level]; - _level.set(ai,_max_level); + _level[ai] = _max_level; if (_highest_active==level) { while(_highest_active>=0 && @@ -370,7 +370,7 @@ copy(--_first[l+1],_last_active[l]--); } copy(i,_first[new_level]); - _level.set(i,new_level); + _level[i] = new_level; if(new_level>_highest_active) _highest_active=new_level; } @@ -382,7 +382,7 @@ ///only if you really know what it is for. ///\pre The item is on the top level. void dirtyTopButOne(Item i) { - _level.set(i,_max_level - 1); + _level[i] = _max_level - 1; } ///Lift all items on and above the given level to the top level. @@ -394,7 +394,7 @@ const Vit f=_first[l]; const Vit tl=_first[_max_level]; for(Vit i=f;i!=tl;++i) - _level.set(*i,_max_level); + _level[*i] = _max_level; for(int i=l;i<=_max_level;i++) { _first[i]=f; @@ -433,8 +433,8 @@ for(typename ItemSetTraits::ItemIt i(_g);i!=INVALID;++i) { *n=i; - _where.set(i,n); - _level.set(i,_max_level); + _where[i] = n; + _level[i] = _max_level; ++n; } } @@ -443,7 +443,7 @@ void initAddItem(Item i) { swap(_where[i],_init_num); - _level.set(i,_init_lev); + _level[i] = _init_lev; ++_init_num; } @@ -551,7 +551,7 @@ ///Activate item \c i. ///\pre Item \c i shouldn't be active before. void activate(Item i) { - _active.set(i, true); + _active[i] = true; int level = _level[i]; if (level > _highest_active) { @@ -560,16 +560,16 @@ if (_prev[i] == INVALID || _active[_prev[i]]) return; //unlace - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; if (_next[i] != INVALID) { - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; } else { _last[level] = _prev[i]; } //lace - _next.set(i, _first[level]); - _prev.set(_first[level], i); - _prev.set(i, INVALID); + _next[i] = _first[level]; + _prev[_first[level]] = i; + _prev[i] = INVALID; _first[level] = i; } @@ -579,23 +579,23 @@ ///Deactivate item \c i. ///\pre Item \c i must be active before. void deactivate(Item i) { - _active.set(i, false); + _active[i] = false; int level = _level[i]; if (_next[i] == INVALID || !_active[_next[i]]) goto find_highest_level; //unlace - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; if (_prev[i] != INVALID) { - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; } else { _first[_level[i]] = _next[i]; } //lace - _prev.set(i, _last[level]); - _next.set(_last[level], i); - _next.set(i, INVALID); + _prev[i] = _last[level]; + _next[_last[level]] = i; + _next[i] = INVALID; _last[level] = i; find_highest_level: @@ -685,21 +685,21 @@ void liftHighestActive() { Item i = _first[_highest_active]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; _last[_highest_active] = INVALID; } - _level.set(i, ++_highest_active); + _level[i] = ++_highest_active; if (_first[_highest_active] == INVALID) { _first[_highest_active] = i; _last[_highest_active] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[_highest_active], i); - _next.set(i, _first[_highest_active]); + _prev[_first[_highest_active]] = i; + _next[i] = _first[_highest_active]; _first[_highest_active] = i; } } @@ -714,20 +714,20 @@ void liftHighestActive(int new_level) { Item i = _first[_highest_active]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; _last[_highest_active] = INVALID; } - _level.set(i, _highest_active = new_level); + _level[i] = _highest_active = new_level; if (_first[_highest_active] == INVALID) { _first[_highest_active] = _last[_highest_active] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[_highest_active], i); - _next.set(i, _first[_highest_active]); + _prev[_first[_highest_active]] = i; + _next[i] = _first[_highest_active]; _first[_highest_active] = i; } } @@ -738,9 +738,9 @@ ///deactivate it. void liftHighestActiveToTop() { Item i = _first[_highest_active]; - _level.set(i, _max_level); + _level[i] = _max_level; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; @@ -774,20 +774,20 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, ++l); + _level[i] = ++l; if (_first[l] == INVALID) { _first[l] = _last[l] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[l], i); - _next.set(i, _first[l]); + _prev[_first[l]] = i; + _next[i] = _first[l]; _first[l] = i; } if (_highest_active < l) { @@ -803,20 +803,20 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, l = new_level); + _level[i] = l = new_level; if (_first[l] == INVALID) { _first[l] = _last[l] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[l], i); - _next.set(i, _first[l]); + _prev[_first[l]] = i; + _next[i] = _first[l]; _first[l] = i; } if (_highest_active < l) { @@ -832,13 +832,13 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, _max_level); + _level[i] = _max_level; if (l == _highest_active) { while (_highest_active >= 0 && activeFree(_highest_active)) --_highest_active; @@ -856,23 +856,23 @@ /// void lift(Item i, int new_level) { if (_next[i] != INVALID) { - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; } else { _last[new_level] = _prev[i]; } if (_prev[i] != INVALID) { - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; } else { _first[new_level] = _next[i]; } - _level.set(i, new_level); + _level[i] = new_level; if (_first[new_level] == INVALID) { _first[new_level] = _last[new_level] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[new_level], i); - _next.set(i, _first[new_level]); + _prev[_first[new_level]] = i; + _next[i] = _first[new_level]; _first[new_level] = i; } if (_highest_active < new_level) { @@ -888,7 +888,7 @@ ///only if you really know what it is for. ///\pre The item is on the top level. void dirtyTopButOne(Item i) { - _level.set(i, _max_level - 1); + _level[i] = _max_level - 1; } ///Lift all items on and above the given level to the top level. @@ -899,7 +899,7 @@ for (int i = l + 1; _first[i] != INVALID; ++i) { Item n = _first[i]; while (n != INVALID) { - _level.set(n, _max_level); + _level[n] = _max_level; n = _next[n]; } _first[i] = INVALID; @@ -937,23 +937,23 @@ _init_level = 0; for(typename ItemSetTraits::ItemIt i(_graph); i != INVALID; ++i) { - _level.set(i, _max_level); - _active.set(i, false); + _level[i] = _max_level; + _active[i] = false; } } ///Add an item to the current level. void initAddItem(Item i) { - _level.set(i, _init_level); + _level[i] = _init_level; if (_last[_init_level] == INVALID) { _first[_init_level] = i; _last[_init_level] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(i, _last[_init_level]); - _next.set(i, INVALID); - _next.set(_last[_init_level], i); + _prev[i] = _last[_init_level]; + _next[i] = INVALID; + _next[_last[_init_level]] = i; _last[_init_level] = i; } } diff -r 2313edd0db0b -r aa1804409f29 lemon/gomory_hu.h --- a/lemon/gomory_hu.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/gomory_hu.h Tue Apr 14 10:35:38 2009 +0200 @@ -143,11 +143,11 @@ _root = NodeIt(_graph); for (NodeIt n(_graph); n != INVALID; ++n) { - _pred->set(n, _root); - _order->set(n, -1); + (*_pred)[n] = _root; + (*_order)[n] = -1; } - _pred->set(_root, INVALID); - _weight->set(_root, std::numeric_limits::max()); + (*_pred)[_root] = INVALID; + (*_weight)[_root] = std::numeric_limits::max(); } @@ -164,22 +164,22 @@ fa.runMinCut(); - _weight->set(n, fa.flowValue()); + (*_weight)[n] = fa.flowValue(); for (NodeIt nn(_graph); nn != INVALID; ++nn) { if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { - _pred->set(nn, n); + (*_pred)[nn] = n; } } if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { - _pred->set(n, (*_pred)[pn]); - _pred->set(pn, n); - _weight->set(n, (*_weight)[pn]); - _weight->set(pn, fa.flowValue()); + (*_pred)[n] = (*_pred)[pn]; + (*_pred)[pn] = n; + (*_weight)[n] = (*_weight)[pn]; + (*_weight)[pn] = fa.flowValue(); } } - _order->set(_root, 0); + (*_order)[_root] = 0; int index = 1; for (NodeIt n(_graph); n != INVALID; ++n) { @@ -190,7 +190,7 @@ nn = (*_pred)[nn]; } while (!st.empty()) { - _order->set(st.back(), index++); + (*_order)[st.back()] = index++; st.pop_back(); } } @@ -309,9 +309,9 @@ } typename Graph::template NodeMap reached(_graph, false); - reached.set(_root, true); + reached[_root] = true; cutMap.set(_root, !s_root); - reached.set(rn, true); + reached[rn] = true; cutMap.set(rn, s_root); std::vector st; diff -r 2313edd0db0b -r aa1804409f29 lemon/hao_orlin.h --- a/lemon/hao_orlin.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/hao_orlin.h Tue Apr 14 10:35:38 2009 +0200 @@ -161,56 +161,56 @@ private: void activate(const Node& i) { - _active->set(i, true); + (*_active)[i] = true; int bucket = (*_bucket)[i]; if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; //unlace - _next->set((*_prev)[i], (*_next)[i]); + (*_next)[(*_prev)[i]] = (*_next)[i]; if ((*_next)[i] != INVALID) { - _prev->set((*_next)[i], (*_prev)[i]); + (*_prev)[(*_next)[i]] = (*_prev)[i]; } else { _last[bucket] = (*_prev)[i]; } //lace - _next->set(i, _first[bucket]); - _prev->set(_first[bucket], i); - _prev->set(i, INVALID); + (*_next)[i] = _first[bucket]; + (*_prev)[_first[bucket]] = i; + (*_prev)[i] = INVALID; _first[bucket] = i; } void deactivate(const Node& i) { - _active->set(i, false); + (*_active)[i] = false; int bucket = (*_bucket)[i]; if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; //unlace - _prev->set((*_next)[i], (*_prev)[i]); + (*_prev)[(*_next)[i]] = (*_prev)[i]; if ((*_prev)[i] != INVALID) { - _next->set((*_prev)[i], (*_next)[i]); + (*_next)[(*_prev)[i]] = (*_next)[i]; } else { _first[bucket] = (*_next)[i]; } //lace - _prev->set(i, _last[bucket]); - _next->set(_last[bucket], i); - _next->set(i, INVALID); + (*_prev)[i] = _last[bucket]; + (*_next)[_last[bucket]] = i; + (*_next)[i] = INVALID; _last[bucket] = i; } void addItem(const Node& i, int bucket) { (*_bucket)[i] = bucket; if (_last[bucket] != INVALID) { - _prev->set(i, _last[bucket]); - _next->set(_last[bucket], i); - _next->set(i, INVALID); + (*_prev)[i] = _last[bucket]; + (*_next)[_last[bucket]] = i; + (*_next)[i] = INVALID; _last[bucket] = i; } else { - _prev->set(i, INVALID); + (*_prev)[i] = INVALID; _first[bucket] = i; - _next->set(i, INVALID); + (*_next)[i] = INVALID; _last[bucket] = i; } } @@ -218,11 +218,11 @@ void findMinCutOut() { for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; } for (ArcIt a(_graph); a != INVALID; ++a) { - _flow->set(a, 0); + (*_flow)[a] = 0; } int bucket_num = 0; @@ -232,7 +232,7 @@ { typename Digraph::template NodeMap reached(_graph, false); - reached.set(_source, true); + reached[_source] = true; bool first_set = true; for (NodeIt t(_graph); t != INVALID; ++t) { @@ -240,7 +240,7 @@ _sets.push_front(std::list()); queue[qlast++] = t; - reached.set(t, true); + reached[t] = true; while (qfirst != qlast) { if (qsep == qfirst) { @@ -257,7 +257,7 @@ for (InArcIt a(_graph, n); a != INVALID; ++a) { Node u = _graph.source(a); if (!reached[u] && _tolerance.positive((*_capacity)[a])) { - reached.set(u, true); + reached[u] = true; queue[qlast++] = u; } } @@ -266,18 +266,18 @@ } ++bucket_num; - _bucket->set(_source, 0); + (*_bucket)[_source] = 0; _dormant[0] = true; } - _source_set->set(_source, true); + (*_source_set)[_source] = true; Node target = _last[_sets.back().back()]; { for (OutArcIt a(_graph, _source); a != INVALID; ++a) { if (_tolerance.positive((*_capacity)[a])) { Node u = _graph.target(a); - _flow->set(a, (*_capacity)[a]); - _excess->set(u, (*_excess)[u] + (*_capacity)[a]); + (*_flow)[a] = (*_capacity)[a]; + (*_excess)[u] += (*_capacity)[a]; if (!(*_active)[u] && u != _source) { activate(u); } @@ -318,14 +318,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] += excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -342,14 +342,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] -= excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -358,7 +358,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if ((*_next)[n] == INVALID) { @@ -376,16 +376,16 @@ } } else if (next_bucket == _node_num) { _first[(*_bucket)[n]] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; std::list >::iterator new_set = _sets.insert(--_sets.end(), std::list()); new_set->push_front(bucket_num); - _bucket->set(n, bucket_num); + (*_bucket)[n] = bucket_num; _first[bucket_num] = _last[bucket_num] = n; - _next->set(n, INVALID); - _prev->set(n, INVALID); + (*_next)[n] = INVALID; + (*_prev)[n] = INVALID; _dormant[bucket_num] = true; ++bucket_num; @@ -395,7 +395,7 @@ } } else { _first[*_highest] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; while (next_bucket != *_highest) { --_highest; @@ -409,10 +409,10 @@ } --_highest; - _bucket->set(n, *_highest); - _next->set(n, _first[*_highest]); + (*_bucket)[n] = *_highest; + (*_next)[n] = _first[*_highest]; if (_first[*_highest] != INVALID) { - _prev->set(_first[*_highest], n); + (*_prev)[_first[*_highest]] = n; } else { _last[*_highest] = n; } @@ -434,13 +434,13 @@ if ((*_excess)[target] < _min_cut) { _min_cut = (*_excess)[target]; for (NodeIt i(_graph); i != INVALID; ++i) { - _min_cut_map->set(i, true); + (*_min_cut_map)[i] = true; } for (std::list::iterator it = _sets.back().begin(); it != _sets.back().end(); ++it) { Node n = _first[*it]; while (n != INVALID) { - _min_cut_map->set(n, false); + (*_min_cut_map)[n] = false; n = (*_next)[n]; } } @@ -453,13 +453,13 @@ _last[(*_bucket)[target]] = (*_prev)[target]; new_target = (*_prev)[target]; } else { - _prev->set((*_next)[target], (*_prev)[target]); + (*_prev)[(*_next)[target]] = (*_prev)[target]; new_target = (*_next)[target]; } if ((*_prev)[target] == INVALID) { _first[(*_bucket)[target]] = (*_next)[target]; } else { - _next->set((*_prev)[target], (*_next)[target]); + (*_next)[(*_prev)[target]] = (*_next)[target]; } } else { _sets.back().pop_back(); @@ -475,9 +475,9 @@ new_target = _last[_sets.back().back()]; } - _bucket->set(target, 0); + (*_bucket)[target] = 0; - _source_set->set(target, true); + (*_source_set)[target] = true; for (OutArcIt a(_graph, target); a != INVALID; ++a) { Value rem = (*_capacity)[a] - (*_flow)[a]; if (!_tolerance.positive(rem)) continue; @@ -485,8 +485,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } for (InArcIt a(_graph, target); a != INVALID; ++a) { @@ -496,8 +496,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } target = new_target; @@ -517,11 +517,11 @@ void findMinCutIn() { for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; } for (ArcIt a(_graph); a != INVALID; ++a) { - _flow->set(a, 0); + (*_flow)[a] = 0; } int bucket_num = 0; @@ -531,7 +531,7 @@ { typename Digraph::template NodeMap reached(_graph, false); - reached.set(_source, true); + reached[_source] = true; bool first_set = true; @@ -540,7 +540,7 @@ _sets.push_front(std::list()); queue[qlast++] = t; - reached.set(t, true); + reached[t] = true; while (qfirst != qlast) { if (qsep == qfirst) { @@ -557,7 +557,7 @@ for (OutArcIt a(_graph, n); a != INVALID; ++a) { Node u = _graph.target(a); if (!reached[u] && _tolerance.positive((*_capacity)[a])) { - reached.set(u, true); + reached[u] = true; queue[qlast++] = u; } } @@ -566,18 +566,18 @@ } ++bucket_num; - _bucket->set(_source, 0); + (*_bucket)[_source] = 0; _dormant[0] = true; } - _source_set->set(_source, true); + (*_source_set)[_source] = true; Node target = _last[_sets.back().back()]; { for (InArcIt a(_graph, _source); a != INVALID; ++a) { if (_tolerance.positive((*_capacity)[a])) { Node u = _graph.source(a); - _flow->set(a, (*_capacity)[a]); - _excess->set(u, (*_excess)[u] + (*_capacity)[a]); + (*_flow)[a] = (*_capacity)[a]; + (*_excess)[u] += (*_capacity)[a]; if (!(*_active)[u] && u != _source) { activate(u); } @@ -618,14 +618,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] += excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -642,14 +642,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] -= excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -658,7 +658,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if ((*_next)[n] == INVALID) { @@ -676,16 +676,16 @@ } } else if (next_bucket == _node_num) { _first[(*_bucket)[n]] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; std::list >::iterator new_set = _sets.insert(--_sets.end(), std::list()); new_set->push_front(bucket_num); - _bucket->set(n, bucket_num); + (*_bucket)[n] = bucket_num; _first[bucket_num] = _last[bucket_num] = n; - _next->set(n, INVALID); - _prev->set(n, INVALID); + (*_next)[n] = INVALID; + (*_prev)[n] = INVALID; _dormant[bucket_num] = true; ++bucket_num; @@ -695,7 +695,7 @@ } } else { _first[*_highest] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; while (next_bucket != *_highest) { --_highest; @@ -708,10 +708,10 @@ } --_highest; - _bucket->set(n, *_highest); - _next->set(n, _first[*_highest]); + (*_bucket)[n] = *_highest; + (*_next)[n] = _first[*_highest]; if (_first[*_highest] != INVALID) { - _prev->set(_first[*_highest], n); + (*_prev)[_first[*_highest]] = n; } else { _last[*_highest] = n; } @@ -733,13 +733,13 @@ if ((*_excess)[target] < _min_cut) { _min_cut = (*_excess)[target]; for (NodeIt i(_graph); i != INVALID; ++i) { - _min_cut_map->set(i, false); + (*_min_cut_map)[i] = false; } for (std::list::iterator it = _sets.back().begin(); it != _sets.back().end(); ++it) { Node n = _first[*it]; while (n != INVALID) { - _min_cut_map->set(n, true); + (*_min_cut_map)[n] = true; n = (*_next)[n]; } } @@ -752,13 +752,13 @@ _last[(*_bucket)[target]] = (*_prev)[target]; new_target = (*_prev)[target]; } else { - _prev->set((*_next)[target], (*_prev)[target]); + (*_prev)[(*_next)[target]] = (*_prev)[target]; new_target = (*_next)[target]; } if ((*_prev)[target] == INVALID) { _first[(*_bucket)[target]] = (*_next)[target]; } else { - _next->set((*_prev)[target], (*_next)[target]); + (*_next)[(*_prev)[target]] = (*_next)[target]; } } else { _sets.back().pop_back(); @@ -774,9 +774,9 @@ new_target = _last[_sets.back().back()]; } - _bucket->set(target, 0); + (*_bucket)[target] = 0; - _source_set->set(target, true); + (*_source_set)[target] = true; for (InArcIt a(_graph, target); a != INVALID; ++a) { Value rem = (*_capacity)[a] - (*_flow)[a]; if (!_tolerance.positive(rem)) continue; @@ -784,8 +784,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } for (OutArcIt a(_graph, target); a != INVALID; ++a) { @@ -795,8 +795,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } target = new_target; diff -r 2313edd0db0b -r aa1804409f29 lemon/max_matching.h --- a/lemon/max_matching.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/max_matching.h Tue Apr 14 10:35:38 2009 +0200 @@ -282,20 +282,20 @@ Node base = (*_blossom_rep)[_blossom_set->find(node)]; while (base != nca) { - _ear->set(node, arc); + (*_ear)[node] = arc; Node n = node; while (n != base) { n = _graph.target((*_matching)[n]); Arc a = (*_ear)[n]; n = _graph.target(a); - _ear->set(n, _graph.oppositeArc(a)); + (*_ear)[n] = _graph.oppositeArc(a); } node = _graph.target((*_matching)[base]); _tree_set->erase(base); _tree_set->erase(node); _blossom_set->insert(node, _blossom_set->find(base)); - _status->set(node, EVEN); + (*_status)[node] = EVEN; _node_queue[_last++] = node; arc = _graph.oppositeArc((*_ear)[node]); node = _graph.target((*_ear)[node]); @@ -304,7 +304,7 @@ } } - _blossom_rep->set(_blossom_set->find(nca), nca); + (*_blossom_rep)[_blossom_set->find(nca)] = nca; { @@ -313,20 +313,20 @@ Node base = (*_blossom_rep)[_blossom_set->find(node)]; while (base != nca) { - _ear->set(node, arc); + (*_ear)[node] = arc; Node n = node; while (n != base) { n = _graph.target((*_matching)[n]); Arc a = (*_ear)[n]; n = _graph.target(a); - _ear->set(n, _graph.oppositeArc(a)); + (*_ear)[n] = _graph.oppositeArc(a); } node = _graph.target((*_matching)[base]); _tree_set->erase(base); _tree_set->erase(node); _blossom_set->insert(node, _blossom_set->find(base)); - _status->set(node, EVEN); + (*_status)[node] = EVEN; _node_queue[_last++] = node; arc = _graph.oppositeArc((*_ear)[node]); node = _graph.target((*_ear)[node]); @@ -335,7 +335,7 @@ } } - _blossom_rep->set(_blossom_set->find(nca), nca); + (*_blossom_rep)[_blossom_set->find(nca)] = nca; } @@ -344,11 +344,11 @@ Node base = _graph.source(a); Node odd = _graph.target(a); - _ear->set(odd, _graph.oppositeArc(a)); + (*_ear)[odd] = _graph.oppositeArc(a); Node even = _graph.target((*_matching)[odd]); - _blossom_rep->set(_blossom_set->insert(even), even); - _status->set(odd, ODD); - _status->set(even, EVEN); + (*_blossom_rep)[_blossom_set->insert(even)] = even; + (*_status)[odd] = ODD; + (*_status)[even] = EVEN; int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]); _tree_set->insert(odd, tree); _tree_set->insert(even, tree); @@ -362,30 +362,30 @@ int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]); - _matching->set(odd, _graph.oppositeArc(a)); - _status->set(odd, MATCHED); + (*_matching)[odd] = _graph.oppositeArc(a); + (*_status)[odd] = MATCHED; Arc arc = (*_matching)[even]; - _matching->set(even, a); + (*_matching)[even] = a; while (arc != INVALID) { odd = _graph.target(arc); arc = (*_ear)[odd]; even = _graph.target(arc); - _matching->set(odd, arc); + (*_matching)[odd] = arc; arc = (*_matching)[even]; - _matching->set(even, _graph.oppositeArc((*_matching)[odd])); + (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]); } for (typename TreeSet::ItemIt it(*_tree_set, tree); it != INVALID; ++it) { if ((*_status)[it] == ODD) { - _status->set(it, MATCHED); + (*_status)[it] = MATCHED; } else { int blossom = _blossom_set->find(it); for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom); jt != INVALID; ++jt) { - _status->set(jt, MATCHED); + (*_status)[jt] = MATCHED; } _blossom_set->eraseClass(blossom); } @@ -427,8 +427,8 @@ void init() { createStructures(); for(NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } } @@ -438,18 +438,18 @@ void greedyInit() { createStructures(); for (NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } for (NodeIt n(_graph); n != INVALID; ++n) { if ((*_matching)[n] == INVALID) { for (OutArcIt a(_graph, n); a != INVALID ; ++a) { Node v = _graph.target(a); if ((*_matching)[v] == INVALID && v != n) { - _matching->set(n, a); - _status->set(n, MATCHED); - _matching->set(v, _graph.oppositeArc(a)); - _status->set(v, MATCHED); + (*_matching)[n] = a; + (*_status)[n] = MATCHED; + (*_matching)[v] = _graph.oppositeArc(a); + (*_status)[v] = MATCHED; break; } } @@ -469,21 +469,21 @@ createStructures(); for (NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } for(EdgeIt e(_graph); e!=INVALID; ++e) { if (matching[e]) { Node u = _graph.u(e); if ((*_matching)[u] != INVALID) return false; - _matching->set(u, _graph.direct(e, true)); - _status->set(u, MATCHED); + (*_matching)[u] = _graph.direct(e, true); + (*_status)[u] = MATCHED; Node v = _graph.v(e); if ((*_matching)[v] != INVALID) return false; - _matching->set(v, _graph.direct(e, false)); - _status->set(v, MATCHED); + (*_matching)[v] = _graph.direct(e, false); + (*_status)[v] = MATCHED; } } return true; @@ -497,7 +497,7 @@ if ((*_status)[n] == UNMATCHED) { (*_blossom_rep)[_blossom_set->insert(n)] = n; _tree_set->insert(n); - _status->set(n, EVEN); + (*_status)[n] = EVEN; processSparse(n); } } @@ -512,7 +512,7 @@ if ((*_status)[n] == UNMATCHED) { (*_blossom_rep)[_blossom_set->insert(n)] = n; _tree_set->insert(n); - _status->set(n, EVEN); + (*_status)[n] = EVEN; processDense(n); } } @@ -1548,9 +1548,9 @@ int bi = (*_node_index)[base]; Value pot = (*_node_data)[bi].pot; - _matching->set(base, matching); + (*_matching)[base] = matching; _blossom_node_list.push_back(base); - _node_potential->set(base, pot); + (*_node_potential)[base] = pot; } else { Value pot = (*_blossom_data)[blossom].pot; @@ -1644,17 +1644,17 @@ createStructures(); for (ArcIt e(_graph); e != INVALID; ++e) { - _node_heap_index->set(e, BinHeap::PRE_HEAP); + (*_node_heap_index)[e] = BinHeap::PRE_HEAP; } for (NodeIt n(_graph); n != INVALID; ++n) { - _delta1_index->set(n, _delta1->PRE_HEAP); + (*_delta1_index)[n] = _delta1->PRE_HEAP; } for (EdgeIt e(_graph); e != INVALID; ++e) { - _delta3_index->set(e, _delta3->PRE_HEAP); + (*_delta3_index)[e] = _delta3->PRE_HEAP; } for (int i = 0; i < _blossom_num; ++i) { - _delta2_index->set(i, _delta2->PRE_HEAP); - _delta4_index->set(i, _delta4->PRE_HEAP); + (*_delta2_index)[i] = _delta2->PRE_HEAP; + (*_delta4_index)[i] = _delta4->PRE_HEAP; } int index = 0; @@ -1666,7 +1666,7 @@ max = (dualScale * _weight[e]) / 2; } } - _node_index->set(n, index); + (*_node_index)[n] = index; (*_node_data)[index].pot = max; _delta1->push(n, max); int blossom = @@ -2741,9 +2741,9 @@ int bi = (*_node_index)[base]; Value pot = (*_node_data)[bi].pot; - _matching->set(base, matching); + (*_matching)[base] = matching; _blossom_node_list.push_back(base); - _node_potential->set(base, pot); + (*_node_potential)[base] = pot; } else { Value pot = (*_blossom_data)[blossom].pot; @@ -2831,14 +2831,14 @@ createStructures(); for (ArcIt e(_graph); e != INVALID; ++e) { - _node_heap_index->set(e, BinHeap::PRE_HEAP); + (*_node_heap_index)[e] = BinHeap::PRE_HEAP; } for (EdgeIt e(_graph); e != INVALID; ++e) { - _delta3_index->set(e, _delta3->PRE_HEAP); + (*_delta3_index)[e] = _delta3->PRE_HEAP; } for (int i = 0; i < _blossom_num; ++i) { - _delta2_index->set(i, _delta2->PRE_HEAP); - _delta4_index->set(i, _delta4->PRE_HEAP); + (*_delta2_index)[i] = _delta2->PRE_HEAP; + (*_delta4_index)[i] = _delta4->PRE_HEAP; } int index = 0; @@ -2850,7 +2850,7 @@ max = (dualScale * _weight[e]) / 2; } } - _node_index->set(n, index); + (*_node_index)[n] = index; (*_node_data)[index].pot = max; int blossom = _blossom_set->insert(n, std::numeric_limits::max()); diff -r 2313edd0db0b -r aa1804409f29 lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/min_cost_arborescence.h Tue Apr 14 10:35:38 2009 +0200 @@ -293,7 +293,7 @@ minimum = (*_cost_arcs)[nodes[i]]; } } - _arc_order->set(minimum.arc, _dual_variables.size()); + (*_arc_order)[minimum.arc] = _dual_variables.size(); DualVariable var(_dual_node_list.size() - 1, _dual_node_list.size(), minimum.value); _dual_variables.push_back(var); @@ -335,7 +335,7 @@ minimum = (*_cost_arcs)[nodes[i]]; } } - _arc_order->set(minimum.arc, _dual_variables.size()); + (*_arc_order)[minimum.arc] = _dual_variables.size(); DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); _dual_variables.push_back(var); StackLevel level; @@ -364,7 +364,7 @@ while (!_heap->empty()) { Node source = _heap->top(); _heap->pop(); - _node_order->set(source, -1); + (*_node_order)[source] = -1; for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { if ((*_arc_order)[it] < 0) continue; Node target = _digraph->target(it); @@ -650,13 +650,13 @@ _heap->clear(); for (NodeIt it(*_digraph); it != INVALID; ++it) { (*_cost_arcs)[it].arc = INVALID; - _node_order->set(it, -3); - _heap_cross_ref->set(it, Heap::PRE_HEAP); + (*_node_order)[it] = -3; + (*_heap_cross_ref)[it] = Heap::PRE_HEAP; _pred->set(it, INVALID); } for (ArcIt it(*_digraph); it != INVALID; ++it) { _arborescence->set(it, false); - _arc_order->set(it, -1); + (*_arc_order)[it] = -1; } _dual_node_list.clear(); _dual_variables.clear(); diff -r 2313edd0db0b -r aa1804409f29 lemon/preflow.h --- a/lemon/preflow.h Tue Apr 14 10:34:12 2009 +0200 +++ b/lemon/preflow.h Tue Apr 14 10:35:38 2009 +0200 @@ -404,7 +404,7 @@ _phase = true; for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; } for (ArcIt e(_graph); e != INVALID; ++e) { @@ -417,10 +417,10 @@ _level->initAddItem(_target); std::vector queue; - reached.set(_source, true); + reached[_source] = true; queue.push_back(_target); - reached.set(_target, true); + reached[_target] = true; while (!queue.empty()) { _level->initNewLevel(); std::vector nqueue; @@ -429,7 +429,7 @@ for (InArcIt e(_graph, n); e != INVALID; ++e) { Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -444,7 +444,7 @@ Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + (*_capacity)[e]); + (*_excess)[u] += (*_capacity)[e]; if (u != _target && !_level->active(u)) { _level->activate(u); } @@ -478,7 +478,7 @@ excess -= (*_flow)[e]; } if (excess < 0 && n != _source) return false; - _excess->set(n, excess); + (*_excess)[n] = excess; } typename Digraph::template NodeMap reached(_graph, false); @@ -487,10 +487,10 @@ _level->initAddItem(_target); std::vector queue; - reached.set(_source, true); + reached[_source] = true; queue.push_back(_target); - reached.set(_target, true); + reached[_target] = true; while (!queue.empty()) { _level->initNewLevel(); std::vector nqueue; @@ -500,7 +500,7 @@ Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -508,7 +508,7 @@ for (OutArcIt e(_graph, n); e != INVALID; ++e) { Node v = _graph.target(e); if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); + reached[v] = true; _level->initAddItem(v); nqueue.push_back(v); } @@ -524,7 +524,7 @@ Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + rem); + (*_excess)[u] += rem; if (u != _target && !_level->active(u)) { _level->activate(u); } @@ -536,7 +536,7 @@ Node v = _graph.source(e); if ((*_level)[v] == _level->maxLevel()) continue; _flow->set(e, 0); - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; if (v != _target && !_level->active(v)) { _level->activate(v); } @@ -577,12 +577,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_1; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -600,12 +600,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_1; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -615,7 +615,7 @@ no_more_push_1: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { @@ -650,12 +650,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_2; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -673,12 +673,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_2; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -688,7 +688,7 @@ no_more_push_2: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { @@ -731,7 +731,7 @@ typename Digraph::template NodeMap reached(_graph); for (NodeIt n(_graph); n != INVALID; ++n) { - reached.set(n, (*_level)[n] < _level->maxLevel()); + reached[n] = (*_level)[n] < _level->maxLevel(); } _level->initStart(); @@ -739,7 +739,7 @@ std::vector queue; queue.push_back(_source); - reached.set(_source, true); + reached[_source] = true; while (!queue.empty()) { _level->initNewLevel(); @@ -749,7 +749,7 @@ for (OutArcIt e(_graph, n); e != INVALID; ++e) { Node v = _graph.target(e); if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); + reached[v] = true; _level->initAddItem(v); nqueue.push_back(v); } @@ -758,7 +758,7 @@ Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -792,12 +792,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -815,12 +815,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -830,7 +830,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { diff -r 2313edd0db0b -r aa1804409f29 test/kruskal_test.cc --- a/test/kruskal_test.cc Tue Apr 14 10:34:12 2009 +0200 +++ b/test/kruskal_test.cc Tue Apr 14 10:35:38 2009 +0200 @@ -99,16 +99,16 @@ check(kruskal(G, edge_cost_map, tree_map)==10, "Total cost should be 10"); - edge_cost_map.set(e1, -10); - edge_cost_map.set(e2, -9); - edge_cost_map.set(e3, -8); - edge_cost_map.set(e4, -7); - edge_cost_map.set(e5, -6); - edge_cost_map.set(e6, -5); - edge_cost_map.set(e7, -4); - edge_cost_map.set(e8, -3); - edge_cost_map.set(e9, -2); - edge_cost_map.set(e10, -1); + edge_cost_map[e1] = -10; + edge_cost_map[e2] = -9; + edge_cost_map[e3] = -8; + edge_cost_map[e4] = -7; + edge_cost_map[e5] = -6; + edge_cost_map[e6] = -5; + edge_cost_map[e7] = -4; + edge_cost_map[e8] = -3; + edge_cost_map[e9] = -2; + edge_cost_map[e10] = -1; vector tree_edge_vec(5);