1.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 30 17:47:51 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Wed Mar 31 15:50:21 2004 +0000
1.3 @@ -999,11 +999,11 @@
1.4 protected:
1.5 OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.6 resG.gw.first(out, v);
1.7 - while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1.8 + while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.9 if (!resG.gw.valid(out)) {
1.10 out_or_in=0;
1.11 resG.gw.first(in, v);
1.12 - while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1.13 + while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.14 }
1.15 }
1.16 // public:
1.17 @@ -1011,15 +1011,15 @@
1.18 // if (out_or_in) {
1.19 // Node v=/*resG->*/G->aNode(out);
1.20 // ++out;
1.21 -// while( out.valid() && !(Edge::free()>0) ) { ++out; }
1.22 +// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.23 // if (!out.valid()) {
1.24 // out_or_in=0;
1.25 // G->first(in, v);
1.26 -// while( in.valid() && !(Edge::free()>0) ) { ++in; }
1.27 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.28 // }
1.29 // } else {
1.30 // ++in;
1.31 -// while( in.valid() && !(Edge::free()>0) ) { ++in; }
1.32 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.33 // }
1.34 // return *this;
1.35 // }
1.36 @@ -1037,52 +1037,52 @@
1.37 EdgeIt(const Invalid& i) : Edge(i) { }
1.38 EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.39 resG.gw.first(v);
1.40 - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
1.41 - while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1.42 + if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
1.43 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.44 while (resG.gw.valid(v) && !resG.gw.valid(out)) {
1.45 resG.gw.next(v);
1.46 if (resG.gw.valid(v)) resG.gw.first(out, v);
1.47 - while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
1.48 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.49 }
1.50 if (!resG.gw.valid(out)) {
1.51 out_or_in=0;
1.52 resG.gw.first(v);
1.53 - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
1.54 - while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1.55 + if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
1.56 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.57 while (resG.gw.valid(v) && !resG.gw.valid(in)) {
1.58 resG.gw.next(v);
1.59 if (resG.gw.valid(v)) resG.gw.first(in, v);
1.60 - while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
1.61 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.62 }
1.63 }
1.64 }
1.65 // EdgeIt& operator++() {
1.66 // if (out_or_in) {
1.67 // ++out;
1.68 -// while (out.valid() && !(Edge::free()>0) ) { ++out; }
1.69 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.70 // while (v.valid() && !out.valid()) {
1.71 // ++v;
1.72 // if (v.valid()) G->first(out, v);
1.73 -// while (out.valid() && !(Edge::free()>0) ) { ++out; }
1.74 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.75 // }
1.76 // if (!out.valid()) {
1.77 // out_or_in=0;
1.78 // G->first(v);
1.79 // if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1.80 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
1.81 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.82 // while (v.valid() && !in.valid()) {
1.83 // ++v;
1.84 // if (v.valid()) G->first(in, v);
1.85 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
1.86 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.87 // }
1.88 // }
1.89 // } else {
1.90 // ++in;
1.91 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
1.92 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.93 // while (v.valid() && !in.valid()) {
1.94 // ++v;
1.95 // if (v.valid()) G->first(in, v);
1.96 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
1.97 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.98 // }
1.99 // }
1.100 // return *this;
1.101 @@ -1105,15 +1105,15 @@
1.102 if (e.out_or_in) {
1.103 Node v=gw.aNode(e.out);
1.104 gw.next(e.out);
1.105 - while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1.106 + while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.107 if (!gw.valid(e.out)) {
1.108 e.out_or_in=0;
1.109 gw.first(e.in, v);
1.110 - while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.111 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.112 }
1.113 } else {
1.114 gw.next(e.in);
1.115 - while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.116 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.117 }
1.118 return e;
1.119 }
1.120 @@ -1121,30 +1121,30 @@
1.121 EdgeIt& next(EdgeIt& e) const {
1.122 if (e.out_or_in) {
1.123 gw.next(e.out);
1.124 - while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1.125 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.126 while (gw.valid(e.v) && !gw.valid(e.out)) {
1.127 gw.next(e.v);
1.128 if (gw.valid(e.v)) gw.first(e.out, e.v);
1.129 - while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
1.130 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.131 }
1.132 if (!gw.valid(e.out)) {
1.133 e.out_or_in=0;
1.134 gw.first(e.v);
1.135 - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
1.136 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.137 + if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
1.138 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.139 while (gw.valid(e.v) && !gw.valid(e.in)) {
1.140 gw.next(e.v);
1.141 if (gw.valid(e.v)) gw.first(e.in, e.v);
1.142 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.143 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.144 }
1.145 }
1.146 } else {
1.147 gw.next(e.in);
1.148 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.149 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.150 while (gw.valid(e.v) && !gw.valid(e.in)) {
1.151 gw.next(e.v);
1.152 if (gw.valid(e.v)) gw.first(e.in, e.v);
1.153 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
1.154 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.155 }
1.156 }
1.157 return e;
1.158 @@ -1193,18 +1193,18 @@
1.159 flow->set(e.in, flow->get(e.in)-a);
1.160 }
1.161
1.162 - Number free(const Edge& e) const {
1.163 + Number resCap(const Edge& e) const {
1.164 if (e.out_or_in)
1.165 return (capacity->get(e.out)-flow->get(e.out));
1.166 else
1.167 return (flow->get(e.in));
1.168 }
1.169
1.170 - Number free(OldOutEdgeIt out) const {
1.171 + Number resCap(OldOutEdgeIt out) const {
1.172 return (capacity->get(out)-flow->get(out));
1.173 }
1.174
1.175 - Number free(OldInEdgeIt in) const {
1.176 + Number resCap(OldInEdgeIt in) const {
1.177 return (flow->get(in));
1.178 }
1.179
1.180 @@ -1247,6 +1247,59 @@
1.181 };
1.182 };
1.183
1.184 + //Subgraph on the same node-set and partial edge-set
1.185 + template<typename GraphWrapper, typename FirstOutEdgesMap>
1.186 + class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.187 + protected:
1.188 + FirstOutEdgesMap* first_out_edges;
1.189 + public:
1.190 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.191 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.192 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.193 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
1.194 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
1.195 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.196 +
1.197 + ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
1.198 + GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
1.199 +
1.200 + template<typename I> I& first(I& i) const {
1.201 + gw.first(i);
1.202 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.203 + return i;
1.204 + }
1.205 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.206 + e=first_out_edges->get(n);
1.207 + return e;
1.208 + }
1.209 + template<typename I, typename P> I& first(I& i, const P& p) const {
1.210 + gw.first(i, p);
1.211 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.212 + return i;
1.213 + }
1.214 +
1.215 + //template<typename I> I getNext(const I& i) const {
1.216 + // return gw.getNext(i);
1.217 + //}
1.218 + template<typename I> I& next(I &i) const {
1.219 + gw.next(i);
1.220 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.221 + return i;
1.222 + }
1.223 +
1.224 + template< typename It > It first() const {
1.225 + It e; this->first(e); return e; }
1.226 +
1.227 + template< typename It > It first(const Node& v) const {
1.228 + It e; this->first(e, v); return e; }
1.229 +
1.230 + void erase(const OutEdgeIt& e) const {
1.231 + OutEdgeIt f=e;
1.232 + this->next(f);
1.233 + first_out_edges->set(this->tail(e), f);
1.234 + }
1.235 + };
1.236 +
1.237 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.238 // class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.239 // protected: