# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# 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]<actlevel) {
if(!_tol.less(fc, exc)) {
_flow->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]<actlevel) {
if(!_tol.less(fc, exc)) {
_flow->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]<mlevel) mlevel=(*_level)[v];
}
- _excess->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<GR,Item>::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<GR,Item>::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<Value>::max());
+ (*_pred)[_root] = INVALID;
+ (*_weight)[_root] = std::numeric_limits<Value>::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<bool> 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<Node> 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<bool> 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<int>());
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<std::list<int> >::iterator new_set =
_sets.insert(--_sets.end(), std::list<int>());
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<int>::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<bool> reached(_graph, false);
- reached.set(_source, true);
+ reached[_source] = true;
bool first_set = true;
@@ -540,7 +540,7 @@
_sets.push_front(std::list<int>());
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<std::list<int> >::iterator new_set =
_sets.insert(--_sets.end(), std::list<int>());
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<int>::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<Value, IntArcMap>::PRE_HEAP);
+ (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::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<Value, IntArcMap>::PRE_HEAP);
+ (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::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<Value>::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<Node> 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<Node> 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<bool> reached(_graph, false);
@@ -487,10 +487,10 @@
_level->initAddItem(_target);
std::vector<Node> 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<Node> 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<bool> 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<Node> 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<Edge> tree_edge_vec(5);