1.1 --- a/src/work/edmonds_karp.hh Thu Mar 04 15:13:43 2004 +0000
1.2 +++ b/src/work/edmonds_karp.hh Thu Mar 04 19:38:07 2004 +0000
1.3 @@ -245,303 +245,6 @@
1.4 };
1.5 };
1.6
1.7 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.8 - class ResGraphWrapper {
1.9 - public:
1.10 - typedef typename Graph::NodeIt NodeIt;
1.11 - typedef typename Graph::EachNodeIt EachNodeIt;
1.12 - private:
1.13 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.14 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.15 - const Graph* G;
1.16 - FlowMap* flow;
1.17 - const CapacityMap* capacity;
1.18 - public:
1.19 - ResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.20 - const CapacityMap& _capacity) :
1.21 - G(&_G), flow(&_flow), capacity(&_capacity) { }
1.22 -// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
1.23 -// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
1.24 - class EdgeIt;
1.25 - class OutEdgeIt;
1.26 - friend class EdgeIt;
1.27 - friend class OutEdgeIt;
1.28 -
1.29 - class EdgeIt {
1.30 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.31 - protected:
1.32 - //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
1.33 - const Graph* G;
1.34 - FlowMap* flow;
1.35 - const CapacityMap* capacity;
1.36 - //OldSymEdgeIt sym;
1.37 - OldOutEdgeIt out;
1.38 - OldInEdgeIt in;
1.39 - bool out_or_in; //true, iff out
1.40 - public:
1.41 - EdgeIt() : out_or_in(true) { }
1.42 - EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
1.43 - G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
1.44 - //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
1.45 - Number free() const {
1.46 - if (out_or_in) {
1.47 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.48 - } else {
1.49 - return (/*resG->*/flow->get(in));
1.50 - }
1.51 - }
1.52 - bool valid() const {
1.53 - return out_or_in && out.valid() || in.valid(); }
1.54 - void augment(Number a) const {
1.55 - if (out_or_in) {
1.56 - /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
1.57 - } else {
1.58 - /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
1.59 - }
1.60 - }
1.61 - void print() {
1.62 - if (out_or_in) {
1.63 - std::cout << "out ";
1.64 - if (out.valid())
1.65 - std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
1.66 - else
1.67 - std::cout << "invalid";
1.68 - }
1.69 - else {
1.70 - std::cout << "in ";
1.71 - if (in.valid())
1.72 - std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
1.73 - else
1.74 - std::cout << "invalid";
1.75 - }
1.76 - std::cout << std::endl;
1.77 - }
1.78 - };
1.79 -
1.80 - Number free(OldOutEdgeIt out) const {
1.81 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.82 - }
1.83 - Number free(OldInEdgeIt in) const {
1.84 - return (/*resG->*/flow->get(in));
1.85 - }
1.86 -
1.87 - class OutEdgeIt : public EdgeIt {
1.88 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.89 - public:
1.90 - OutEdgeIt() { }
1.91 - private:
1.92 - OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.93 - //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
1.94 - G->getFirst(out, v);
1.95 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.96 - if (!out.valid()) {
1.97 - out_or_in=0;
1.98 - //in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.99 - G->getFirst(in, v);
1.100 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.101 - }
1.102 - }
1.103 - public:
1.104 - OutEdgeIt& operator++() {
1.105 - if (out_or_in) {
1.106 - NodeIt v=/*resG->*/G->aNode(out);
1.107 - ++out;
1.108 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.109 - if (!out.valid()) {
1.110 - out_or_in=0;
1.111 - G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.112 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.113 - }
1.114 - } else {
1.115 - ++in;
1.116 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.117 - }
1.118 - return *this;
1.119 - }
1.120 - };
1.121 -
1.122 - class EachEdgeIt : public EdgeIt {
1.123 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.124 - typename Graph::EachNodeIt v;
1.125 - public:
1.126 - EachEdgeIt() { }
1.127 - //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
1.128 - EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.129 - out_or_in=true;
1.130 - G->getFirst(v);
1.131 - if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
1.132 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.133 - while (v.valid() && !out.valid()) {
1.134 - ++v;
1.135 - if (v.valid()) G->getFirst(out, v);
1.136 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.137 - }
1.138 - if (!out.valid()) {
1.139 - out_or_in=0;
1.140 - G->getFirst(v);
1.141 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.142 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.143 - while (v.valid() && !in.valid()) {
1.144 - ++v;
1.145 - if (v.valid()) G->getFirst(in, v);
1.146 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.147 - }
1.148 - }
1.149 - }
1.150 - EachEdgeIt& operator++() {
1.151 - if (out_or_in) {
1.152 - ++out;
1.153 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.154 - while (v.valid() && !out.valid()) {
1.155 - ++v;
1.156 - if (v.valid()) G->getFirst(out, v);
1.157 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.158 - }
1.159 - if (!out.valid()) {
1.160 - out_or_in=0;
1.161 - G->getFirst(v);
1.162 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.163 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.164 - while (v.valid() && !in.valid()) {
1.165 - ++v;
1.166 - if (v.valid()) G->getFirst(in, v);
1.167 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.168 - }
1.169 - }
1.170 - } else {
1.171 - ++in;
1.172 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.173 - while (v.valid() && !in.valid()) {
1.174 - ++v;
1.175 - if (v.valid()) G->getFirst(in, v);
1.176 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.177 - }
1.178 - }
1.179 - return *this;
1.180 - }
1.181 - };
1.182 -
1.183 - void getFirst(EachNodeIt& v) const { G->getFirst(v); }
1.184 - void getFirst(OutEdgeIt& e, NodeIt v) const {
1.185 - e=OutEdgeIt(*G, v, *flow, *capacity);
1.186 - }
1.187 - void getFirst(EachEdgeIt& e) const {
1.188 - e=EachEdgeIt(*G, *flow, *capacity);
1.189 - }
1.190 -
1.191 - EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
1.192 -
1.193 - OutEdgeIt& next(OutEdgeIt& e) const {
1.194 - if (e.out_or_in) {
1.195 - NodeIt v=G->aNode(e.out);
1.196 - ++(e.out);
1.197 - while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.198 - if (!G->valid(e.out)) {
1.199 - e.out_or_in=0;
1.200 - G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.201 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.202 - }
1.203 - } else {
1.204 - ++(e.in);
1.205 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.206 - }
1.207 - return e;
1.208 - }
1.209 -
1.210 - EachEdgeIt& next(EachEdgeIt& e) const {
1.211 - if (e.out_or_in) {
1.212 - ++(e.out);
1.213 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.214 - while (G->valid(e.v) && !G->valid(e.out)) {
1.215 - ++(e.v);
1.216 - if (G->valid(e.v)) G->getFirst(e.out, e.v);
1.217 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.218 - }
1.219 - if (!G->valid(e.out)) {
1.220 - e.out_or_in=0;
1.221 - G->getFirst(e.v);
1.222 - if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
1.223 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.224 - while (G->valid(e.v) && !G->valid(e.in)) {
1.225 - ++(e.v);
1.226 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.227 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.228 - }
1.229 - }
1.230 - } else {
1.231 - ++(e.in);
1.232 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.233 - while (G->valid(e.v) && !G->valid(e.in)) {
1.234 - ++(e.v);
1.235 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.236 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.237 - }
1.238 - }
1.239 - return e;
1.240 - }
1.241 -
1.242 -
1.243 - template< typename It >
1.244 - It first() const {
1.245 - It e;
1.246 - getFirst(e);
1.247 - return e;
1.248 - }
1.249 -
1.250 - template< typename It >
1.251 - It first(NodeIt v) const {
1.252 - It e;
1.253 - getFirst(e, v);
1.254 - return e;
1.255 - }
1.256 -
1.257 - NodeIt tail(EdgeIt e) const {
1.258 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.259 - NodeIt head(EdgeIt e) const {
1.260 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.261 -
1.262 - NodeIt aNode(OutEdgeIt e) const {
1.263 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.264 - NodeIt bNode(OutEdgeIt e) const {
1.265 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.266 -
1.267 - int id(NodeIt v) const { return G->id(v); }
1.268 -
1.269 - bool valid(NodeIt n) const { return G->valid(n); }
1.270 - bool valid(EdgeIt e) const {
1.271 - return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
1.272 -
1.273 - template <typename T>
1.274 - class NodeMap {
1.275 - typename Graph::NodeMap<T> node_map;
1.276 - public:
1.277 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
1.278 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
1.279 - void set(NodeIt nit, T a) { node_map.set(nit, a); }
1.280 - T get(NodeIt nit) const { return node_map.get(nit); }
1.281 - };
1.282 -
1.283 - template <typename T>
1.284 - class EdgeMap {
1.285 - typename Graph::EdgeMap<T> forward_map, backward_map;
1.286 - public:
1.287 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
1.288 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
1.289 - void set(EdgeIt e, T a) {
1.290 - if (e.out_or_in)
1.291 - forward_map.set(e.out, a);
1.292 - else
1.293 - backward_map.set(e.in, a);
1.294 - }
1.295 - T get(EdgeIt e) {
1.296 - if (e.out_or_in)
1.297 - return forward_map.get(e.out);
1.298 - else
1.299 - return backward_map.get(e.in);
1.300 - }
1.301 - };
1.302 -
1.303 - };
1.304
1.305 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.306 class MaxFlow {
1.307 @@ -758,105 +461,105 @@
1.308 };
1.309
1.310
1.311 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.312 - class MaxFlow2 {
1.313 - public:
1.314 - typedef typename Graph::NodeIt NodeIt;
1.315 - typedef typename Graph::EdgeIt EdgeIt;
1.316 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.317 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.318 - typedef typename Graph::InEdgeIt InEdgeIt;
1.319 - private:
1.320 - const Graph& G;
1.321 - std::list<NodeIt>& S;
1.322 - std::list<NodeIt>& T;
1.323 - FlowMap& flow;
1.324 - const CapacityMap& capacity;
1.325 - typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.326 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.327 - typedef typename AugGraph::EdgeIt AugEdgeIt;
1.328 - typename Graph::NodeMap<bool> SMap;
1.329 - typename Graph::NodeMap<bool> TMap;
1.330 - public:
1.331 - MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.332 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.333 - i!=S.end(); ++i) {
1.334 - SMap.set(*i, true);
1.335 - }
1.336 - for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.337 - i!=T.end(); ++i) {
1.338 - TMap.set(*i, true);
1.339 - }
1.340 - }
1.341 - bool augment() {
1.342 - AugGraph res_graph(G, flow, capacity);
1.343 - bool _augment=false;
1.344 - NodeIt reached_t_node;
1.345 +// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.346 +// class MaxFlow2 {
1.347 +// public:
1.348 +// typedef typename Graph::NodeIt NodeIt;
1.349 +// typedef typename Graph::EdgeIt EdgeIt;
1.350 +// typedef typename Graph::EachEdgeIt EachEdgeIt;
1.351 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.352 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.353 +// private:
1.354 +// const Graph& G;
1.355 +// std::list<NodeIt>& S;
1.356 +// std::list<NodeIt>& T;
1.357 +// FlowMap& flow;
1.358 +// const CapacityMap& capacity;
1.359 +// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.360 +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.361 +// typedef typename AugGraph::EdgeIt AugEdgeIt;
1.362 +// typename Graph::NodeMap<bool> SMap;
1.363 +// typename Graph::NodeMap<bool> TMap;
1.364 +// public:
1.365 +// MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.366 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.367 +// i!=S.end(); ++i) {
1.368 +// SMap.set(*i, true);
1.369 +// }
1.370 +// for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.371 +// i!=T.end(); ++i) {
1.372 +// TMap.set(*i, true);
1.373 +// }
1.374 +// }
1.375 +// bool augment() {
1.376 +// AugGraph res_graph(G, flow, capacity);
1.377 +// bool _augment=false;
1.378 +// NodeIt reached_t_node;
1.379
1.380 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.381 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.382 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.383 - i!=S.end(); ++i) {
1.384 - res_bfs.pushAndSetReached(*i);
1.385 - }
1.386 - //res_bfs.pushAndSetReached(s);
1.387 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.388 +// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.389 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.390 +// i!=S.end(); ++i) {
1.391 +// res_bfs.pushAndSetReached(*i);
1.392 +// }
1.393 +// //res_bfs.pushAndSetReached(s);
1.394
1.395 - typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.396 - //filled up with invalid iterators
1.397 +// typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.398 +// //filled up with invalid iterators
1.399
1.400 - typename AugGraph::NodeMap<Number> free(res_graph);
1.401 +// typename AugGraph::NodeMap<Number> free(res_graph);
1.402
1.403 - //searching for augmenting path
1.404 - while ( !res_bfs.finished() ) {
1.405 - AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.406 - if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.407 - NodeIt v=res_graph.tail(e);
1.408 - NodeIt w=res_graph.head(e);
1.409 - pred.set(w, e);
1.410 - if (pred.get(v).valid()) {
1.411 - free.set(w, std::min(free.get(v), e.free()));
1.412 - } else {
1.413 - free.set(w, e.free());
1.414 - }
1.415 - if (TMap.get(res_graph.head(e))) {
1.416 - _augment=true;
1.417 - reached_t_node=res_graph.head(e);
1.418 - break;
1.419 - }
1.420 - }
1.421 +// //searching for augmenting path
1.422 +// while ( !res_bfs.finished() ) {
1.423 +// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.424 +// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.425 +// NodeIt v=res_graph.tail(e);
1.426 +// NodeIt w=res_graph.head(e);
1.427 +// pred.set(w, e);
1.428 +// if (pred.get(v).valid()) {
1.429 +// free.set(w, std::min(free.get(v), e.free()));
1.430 +// } else {
1.431 +// free.set(w, e.free());
1.432 +// }
1.433 +// if (TMap.get(res_graph.head(e))) {
1.434 +// _augment=true;
1.435 +// reached_t_node=res_graph.head(e);
1.436 +// break;
1.437 +// }
1.438 +// }
1.439
1.440 - ++res_bfs;
1.441 - } //end of searching augmenting path
1.442 +// ++res_bfs;
1.443 +// } //end of searching augmenting path
1.444
1.445 - if (_augment) {
1.446 - NodeIt n=reached_t_node;
1.447 - Number augment_value=free.get(reached_t_node);
1.448 - while (pred.get(n).valid()) {
1.449 - AugEdgeIt e=pred.get(n);
1.450 - e.augment(augment_value);
1.451 - n=res_graph.tail(e);
1.452 - }
1.453 - }
1.454 +// if (_augment) {
1.455 +// NodeIt n=reached_t_node;
1.456 +// Number augment_value=free.get(reached_t_node);
1.457 +// while (pred.get(n).valid()) {
1.458 +// AugEdgeIt e=pred.get(n);
1.459 +// e.augment(augment_value);
1.460 +// n=res_graph.tail(e);
1.461 +// }
1.462 +// }
1.463
1.464 - return _augment;
1.465 - }
1.466 - void run() {
1.467 - while (augment()) { }
1.468 - }
1.469 - Number flowValue() {
1.470 - Number a=0;
1.471 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.472 - i!=S.end(); ++i) {
1.473 - for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.474 - a+=flow.get(e);
1.475 - }
1.476 - for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.477 - a-=flow.get(e);
1.478 - }
1.479 - }
1.480 - return a;
1.481 - }
1.482 - };
1.483 +// return _augment;
1.484 +// }
1.485 +// void run() {
1.486 +// while (augment()) { }
1.487 +// }
1.488 +// Number flowValue() {
1.489 +// Number a=0;
1.490 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.491 +// i!=S.end(); ++i) {
1.492 +// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.493 +// a+=flow.get(e);
1.494 +// }
1.495 +// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.496 +// a-=flow.get(e);
1.497 +// }
1.498 +// }
1.499 +// return a;
1.500 +// }
1.501 +// };
1.502
1.503
1.504
2.1 --- a/src/work/makefile Thu Mar 04 15:13:43 2004 +0000
2.2 +++ b/src/work/makefile Thu Mar 04 19:38:07 2004 +0000
2.3 @@ -1,7 +1,7 @@
2.4 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
2.5 CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
2.6
2.7 -BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2
2.8 +BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo
2.9
2.10 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
2.11 # ismert rendszeren :-) (Misi)
3.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Mar 04 15:13:43 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Mar 04 19:38:07 2004 +0000
3.3 @@ -5,6 +5,7 @@
3.4 #include <dimacs.hh>
3.5 #include <edmonds_karp.hh>
3.6 #include <time_measure.h>
3.7 +#include <graph_wrapper.h>
3.8
3.9 using namespace hugo;
3.10
3.11 @@ -57,6 +58,24 @@
3.12 NodeIt s, t;
3.13 ListGraph::EdgeMap<int> cap(G);
3.14 readDimacsMaxFlow(std::cin, G, s, t, cap);
3.15 +/*
3.16 + typedef TrivGraphWrapper<ListGraph> TGW;
3.17 + TGW gw(G);
3.18 + TGW::EachNodeIt sw;
3.19 + gw.getFirst(sw);
3.20 + std::cout << "p1:" << gw.nodeNum() << std::endl;
3.21 + gw.erase(sw);
3.22 + std::cout << "p2:" << gw.nodeNum() << std::endl;
3.23 +
3.24 + typedef const ListGraph cLG;
3.25 + typedef TrivGraphWrapper<const cLG> CTGW;
3.26 + CTGW cgw(G);
3.27 + CTGW::EachNodeIt csw;
3.28 + cgw.getFirst(csw);
3.29 + std::cout << "p1:" << cgw.nodeNum() << std::endl;
3.30 + //cgw.erase(csw);
3.31 + std::cout << "p2:" << cgw.nodeNum() << std::endl;
3.32 +*/
3.33
3.34 {
3.35 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
4.1 --- a/src/work/marci/graph_wrapper.h Thu Mar 04 15:13:43 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper.h Thu Mar 04 19:38:07 2004 +0000
4.3 @@ -12,44 +12,45 @@
4.4 typedef Graph BaseGraph;
4.5
4.6 typedef typename Graph::NodeIt NodeIt;
4.7 - typedef typename Graph::EdgeIt EdgeIt;
4.8 -
4.9 typedef typename Graph::EachNodeIt EachNodeIt;
4.10
4.11 + typedef typename Graph::EdgeIt EdgeIt;
4.12 typedef typename Graph::OutEdgeIt OutEdgeIt;
4.13 typedef typename Graph::InEdgeIt InEdgeIt;
4.14 - typedef typename Graph::SymEdgeIt SymEdgeIt;
4.15 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.16 typedef typename Graph::EachEdgeIt EachEdgeIt;
4.17 -
4.18 - int nodeNum() const { return graph->nodeNum(); }
4.19 - int edgeNum() const { return graph->edgeNum(); }
4.20
4.21 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.22 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.23 return graph->getFirst(i, p); }
4.24 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.25 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.26 +
4.27 + template<typename I> I getNext(const I& i) const {
4.28 + return graph->getNext(i); }
4.29 + template<typename I> I& next(I &i) const { return graph->next(i); }
4.30
4.31 template< typename It > It first() const {
4.32 It e; getFirst(e); return e; }
4.33
4.34 - template< typename It > It first(NodeIt v) const {
4.35 + template< typename It > It first(const NodeIt& v) const {
4.36 It e; getFirst(e, v); return e; }
4.37
4.38 NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.39 NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.40 +
4.41 + template<typename I> bool valid(const I& i) const
4.42 + { return graph->valid(i); }
4.43 +
4.44 + //template<typename I> void setInvalid(const I &i);
4.45 + //{ return graph->setInvalid(i); }
4.46 +
4.47 + int nodeNum() const { return graph->nodeNum(); }
4.48 + int edgeNum() const { return graph->edgeNum(); }
4.49
4.50 template<typename I> NodeIt aNode(const I& e) const {
4.51 return graph->aNode(e); }
4.52 template<typename I> NodeIt bNode(const I& e) const {
4.53 return graph->bNode(e); }
4.54
4.55 - //template<typename I> bool valid(const I& i)
4.56 - //{ return graph->valid(i); }
4.57 -
4.58 - //template<typename I> void setInvalid(const I &i);
4.59 - //{ return graph->setInvalid(i); }
4.60 -
4.61 NodeIt addNode() const { return graph->addNode(); }
4.62 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
4.63 return graph->addEdge(tail, head); }
4.64 @@ -57,91 +58,30 @@
4.65 template<typename I> void erase(const I& i) const { graph->erase(i); }
4.66
4.67 void clear() const { graph->clear(); }
4.68 -
4.69 +
4.70 template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.71 public:
4.72 - NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
4.73 - NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
4.74 + NodeMap(const TrivGraphWrapper<Graph>& _G) :
4.75 + Graph::NodeMap<T>(*(_G.G)) { }
4.76 + NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
4.77 + Graph::NodeMap<T>(*(_G.G), a) { }
4.78 };
4.79 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
4.80 -
4.81 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.82 + public:
4.83 + EdgeMap(const TrivGraphWrapper<Graph>& _G) :
4.84 + Graph::EdgeMap<T>(*(_G.G)) { }
4.85 + EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
4.86 + Graph::EdgeMap<T>(*(_G.G), a) { }
4.87 + };
4.88 +
4.89 void setGraph(Graph& _graph) { graph = &_graph; }
4.90 - Graph& getGraph() { return (*graph); }
4.91 + Graph& getGraph() const { return (*graph); }
4.92
4.93 //TrivGraphWrapper() : graph(0) { }
4.94 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.95 };
4.96
4.97 template<typename Graph>
4.98 - class ConstTrivGraphWrapper {
4.99 - const Graph* graph;
4.100 -
4.101 - public:
4.102 - typedef Graph BaseGraph;
4.103 -
4.104 - typedef typename Graph::NodeIt NodeIt;
4.105 - typedef typename Graph::EdgeIt EdgeIt;
4.106 -
4.107 - typedef typename Graph::EachNodeIt EachNodeIt;
4.108 -
4.109 - typedef typename Graph::OutEdgeIt OutEdgeIt;
4.110 - typedef typename Graph::InEdgeIt InEdgeIt;
4.111 - typedef typename Graph::SymEdgeIt SymEdgeIt;
4.112 - typedef typename Graph::EachEdgeIt EachEdgeIt;
4.113 -
4.114 - int nodeNum() const { return graph->nodeNum(); }
4.115 - int edgeNum() const { return graph->edgeNum(); }
4.116 -
4.117 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.118 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.119 - return graph->getFirst(i, p); }
4.120 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.121 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.122 -
4.123 - template< typename It > It first() const {
4.124 - It e; getFirst(e); return e; }
4.125 -
4.126 - template< typename It > It first(NodeIt v) const {
4.127 - It e; getFirst(e, v); return e; }
4.128 -
4.129 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.130 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.131 -
4.132 - template<typename I> NodeIt aNode(const I& e) const {
4.133 - return graph->aNode(e); }
4.134 - template<typename I> NodeIt bNode(const I& e) const {
4.135 - return graph->bNode(e); }
4.136 -
4.137 - //template<typename I> bool valid(const I& i)
4.138 - //{ return graph->valid(i); }
4.139 -
4.140 - //template<typename I> void setInvalid(const I &i);
4.141 - //{ return graph->setInvalid(i); }
4.142 -
4.143 - NodeIt addNode() const { return graph->addNode(); }
4.144 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
4.145 - return graph->addEdge(tail, head); }
4.146 -
4.147 - template<typename I> void erase(const I& i) const { graph->erase(i); }
4.148 -
4.149 - void clear() const { graph->clear(); }
4.150 -
4.151 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.152 - public:
4.153 - NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
4.154 - NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
4.155 - };
4.156 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
4.157 -
4.158 - void setGraph(const Graph& _graph) { graph = &_graph; }
4.159 - const Graph& getGraph() { return (*graph); }
4.160 -
4.161 - //ConstTrivGraphWrapper() : graph(0) { }
4.162 - ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }
4.163 - };
4.164 -
4.165 -
4.166 - template<typename Graph>
4.167 class RevGraphWrapper
4.168 {
4.169 Graph* graph;
4.170 @@ -149,129 +89,451 @@
4.171 public:
4.172 typedef Graph BaseGraph;
4.173
4.174 - typedef typename Graph::NodeIt NodeIt;
4.175 - typedef typename Graph::EdgeIt EdgeIt;
4.176 -
4.177 + typedef typename Graph::NodeIt NodeIt;
4.178 typedef typename Graph::EachNodeIt EachNodeIt;
4.179
4.180 + typedef typename Graph::EdgeIt EdgeIt;
4.181 typedef typename Graph::OutEdgeIt InEdgeIt;
4.182 typedef typename Graph::InEdgeIt OutEdgeIt;
4.183 - typedef typename Graph::SymEdgeIt SymEdgeIt;
4.184 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.185 typedef typename Graph::EachEdgeIt EachEdgeIt;
4.186 -
4.187 - int nodeNum() const { return graph->nodeNum(); }
4.188 - int edgeNum() const { return graph->edgeNum(); }
4.189
4.190 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.191 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.192 return graph->getFirst(i, p); }
4.193 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.194 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.195 +
4.196 + template<typename I> I getNext(const I& i) const {
4.197 + return graph->getNext(i); }
4.198 + template<typename I> I& next(I &i) const { return graph->next(i); }
4.199
4.200 template< typename It > It first() const {
4.201 It e; getFirst(e); return e; }
4.202
4.203 - template< typename It > It first(NodeIt v) const {
4.204 + template< typename It > It first(const NodeIt& v) const {
4.205 It e; getFirst(e, v); return e; }
4.206
4.207 NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
4.208 NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
4.209
4.210 + template<typename I> bool valid(const I& i) const
4.211 + { return graph->valid(i); }
4.212 +
4.213 + //template<typename I> void setInvalid(const I &i);
4.214 + //{ return graph->setInvalid(i); }
4.215 +
4.216 template<typename I> NodeIt aNode(const I& e) const {
4.217 return graph->aNode(e); }
4.218 template<typename I> NodeIt bNode(const I& e) const {
4.219 return graph->bNode(e); }
4.220 -
4.221 - //template<typename I> bool valid(const I i);
4.222 - //{ return graph->valid(i); }
4.223 -
4.224 - //template<typename I> void setInvalid(const I &i);
4.225 - //{ return graph->setInvalid(i); }
4.226 -
4.227 - NodeIt addNode() { return graph->addNode(); }
4.228 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.229 +
4.230 + NodeIt addNode() const { return graph->addNode(); }
4.231 + EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
4.232 return graph->addEdge(tail, head); }
4.233
4.234 - template<typename I> void erase(const I& i) { graph->erase(i); }
4.235 + int nodeNum() const { return graph->nodeNum(); }
4.236 + int edgeNum() const { return graph->edgeNum(); }
4.237
4.238 - void clear() { graph->clear(); }
4.239 + template<typename I> void erase(const I& i) const { graph->erase(i); }
4.240
4.241 - template<typename T> class NodeMap : public Graph::NodeMap<T> { };
4.242 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
4.243 -
4.244 + void clear() const { graph->clear(); }
4.245 +
4.246 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.247 + public:
4.248 + NodeMap(const RevGraphWrapper<Graph>& _G) :
4.249 + Graph::NodeMap<T>(*(_G.G)) { }
4.250 + NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
4.251 + Graph::NodeMap<T>(*(_G.G), a) { }
4.252 + };
4.253 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.254 + public:
4.255 + EdgeMap(const RevGraphWrapper<Graph>& _G) :
4.256 + Graph::EdgeMap<T>(*(_G.G)) { }
4.257 + EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
4.258 + Graph::EdgeMap<T>(*(_G.G), a) { }
4.259 + };
4.260 +
4.261 void setGraph(Graph& _graph) { graph = &_graph; }
4.262 - Graph& getGraph() { return (*graph); }
4.263 + Graph& getGraph() const { return (*graph); }
4.264
4.265 //RevGraphWrapper() : graph(0) { }
4.266 RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.267 };
4.268
4.269 - template<typename Graph>
4.270 - class SymGraphWrapper
4.271 - {
4.272 - Graph* graph;
4.273 +
4.274 +// template<typename Graph>
4.275 +// class SymGraphWrapper
4.276 +// {
4.277 +// Graph* graph;
4.278
4.279 +// public:
4.280 +// typedef Graph BaseGraph;
4.281 +
4.282 +// typedef typename Graph::NodeIt NodeIt;
4.283 +// typedef typename Graph::EdgeIt EdgeIt;
4.284 +
4.285 +// typedef typename Graph::EachNodeIt EachNodeIt;
4.286 +
4.287 +// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
4.288 +// //iranyitatlant, ami van
4.289 +// //mert csak 1 dolgot lehet be typedef-elni
4.290 +// typedef typename Graph::OutEdgeIt SymEdgeIt;
4.291 +// //typedef typename Graph::InEdgeIt SymEdgeIt;
4.292 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.293 +// typedef typename Graph::EachEdgeIt EachEdgeIt;
4.294 +
4.295 +// int nodeNum() const { return graph->nodeNum(); }
4.296 +// int edgeNum() const { return graph->edgeNum(); }
4.297 +
4.298 +// template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.299 +// template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.300 +// return graph->getFirst(i, p); }
4.301 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
4.302 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.303 +
4.304 +// template< typename It > It first() const {
4.305 +// It e; getFirst(e); return e; }
4.306 +
4.307 +// template< typename It > It first(NodeIt v) const {
4.308 +// It e; getFirst(e, v); return e; }
4.309 +
4.310 +// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.311 +// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.312 +
4.313 +// template<typename I> NodeIt aNode(const I& e) const {
4.314 +// return graph->aNode(e); }
4.315 +// template<typename I> NodeIt bNode(const I& e) const {
4.316 +// return graph->bNode(e); }
4.317 +
4.318 +// //template<typename I> bool valid(const I i);
4.319 +// //{ return graph->valid(i); }
4.320 +
4.321 +// //template<typename I> void setInvalid(const I &i);
4.322 +// //{ return graph->setInvalid(i); }
4.323 +
4.324 +// NodeIt addNode() { return graph->addNode(); }
4.325 +// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.326 +// return graph->addEdge(tail, head); }
4.327 +
4.328 +// template<typename I> void erase(const I& i) { graph->erase(i); }
4.329 +
4.330 +// void clear() { graph->clear(); }
4.331 +
4.332 +// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
4.333 +// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
4.334 +
4.335 +// void setGraph(Graph& _graph) { graph = &_graph; }
4.336 +// Graph& getGraph() { return (*graph); }
4.337 +
4.338 +// //SymGraphWrapper() : graph(0) { }
4.339 +// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.340 +// };
4.341 +
4.342 +
4.343 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.344 + class ResGraphWrapper {
4.345 public:
4.346 typedef Graph BaseGraph;
4.347 + typedef typename Graph::NodeIt NodeIt;
4.348 + typedef typename Graph::EachNodeIt EachNodeIt;
4.349 + private:
4.350 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
4.351 + typedef typename Graph::InEdgeIt OldInEdgeIt;
4.352 + const Graph* G;
4.353 + FlowMap* flow;
4.354 + const CapacityMap* capacity;
4.355 + public:
4.356 + ResGraphWrapper(const Graph& _G, FlowMap& _flow,
4.357 + const CapacityMap& _capacity) :
4.358 + G(&_G), flow(&_flow), capacity(&_capacity) { }
4.359 +// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
4.360 +// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
4.361 + class EdgeIt;
4.362 + class OutEdgeIt;
4.363 + friend class EdgeIt;
4.364 + friend class OutEdgeIt;
4.365
4.366 - typedef typename Graph::NodeIt NodeIt;
4.367 - typedef typename Graph::EdgeIt EdgeIt;
4.368 -
4.369 - typedef typename Graph::EachNodeIt EachNodeIt;
4.370 + class EdgeIt {
4.371 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.372 + protected:
4.373 + //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
4.374 + const Graph* G;
4.375 + FlowMap* flow;
4.376 + const CapacityMap* capacity;
4.377 + //OldSymEdgeIt sym;
4.378 + OldOutEdgeIt out;
4.379 + OldInEdgeIt in;
4.380 + bool out_or_in; //true, iff out
4.381 + public:
4.382 + EdgeIt() : out_or_in(true) { }
4.383 + EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
4.384 + G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
4.385 + //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
4.386 + Number free() const {
4.387 + if (out_or_in) {
4.388 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
4.389 + } else {
4.390 + return (/*resG->*/flow->get(in));
4.391 + }
4.392 + }
4.393 + bool valid() const {
4.394 + return out_or_in && out.valid() || in.valid(); }
4.395 + void augment(Number a) const {
4.396 + if (out_or_in) {
4.397 + /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
4.398 + } else {
4.399 + /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
4.400 + }
4.401 + }
4.402 + void print() {
4.403 + if (out_or_in) {
4.404 + std::cout << "out ";
4.405 + if (out.valid())
4.406 + std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
4.407 + else
4.408 + std::cout << "invalid";
4.409 + }
4.410 + else {
4.411 + std::cout << "in ";
4.412 + if (in.valid())
4.413 + std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
4.414 + else
4.415 + std::cout << "invalid";
4.416 + }
4.417 + std::cout << std::endl;
4.418 + }
4.419 + };
4.420 +
4.421 + Number free(OldOutEdgeIt out) const {
4.422 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
4.423 + }
4.424 + Number free(OldInEdgeIt in) const {
4.425 + return (/*resG->*/flow->get(in));
4.426 + }
4.427 +
4.428 + class OutEdgeIt : public EdgeIt {
4.429 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.430 + public:
4.431 + OutEdgeIt() { }
4.432 + private:
4.433 + OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
4.434 + //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
4.435 + G->getFirst(out, v);
4.436 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.437 + if (!out.valid()) {
4.438 + out_or_in=0;
4.439 + //in=/*resG->*/G->template first<OldInEdgeIt>(v);
4.440 + G->getFirst(in, v);
4.441 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.442 + }
4.443 + }
4.444 + public:
4.445 + OutEdgeIt& operator++() {
4.446 + if (out_or_in) {
4.447 + NodeIt v=/*resG->*/G->aNode(out);
4.448 + ++out;
4.449 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.450 + if (!out.valid()) {
4.451 + out_or_in=0;
4.452 + G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
4.453 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.454 + }
4.455 + } else {
4.456 + ++in;
4.457 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.458 + }
4.459 + return *this;
4.460 + }
4.461 + };
4.462 +
4.463 + class EachEdgeIt : public EdgeIt {
4.464 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.465 + typename Graph::EachNodeIt v;
4.466 + public:
4.467 + EachEdgeIt() { }
4.468 + //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
4.469 + EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
4.470 + out_or_in=true;
4.471 + G->getFirst(v);
4.472 + if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
4.473 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.474 + while (v.valid() && !out.valid()) {
4.475 + ++v;
4.476 + if (v.valid()) G->getFirst(out, v);
4.477 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.478 + }
4.479 + if (!out.valid()) {
4.480 + out_or_in=0;
4.481 + G->getFirst(v);
4.482 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
4.483 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.484 + while (v.valid() && !in.valid()) {
4.485 + ++v;
4.486 + if (v.valid()) G->getFirst(in, v);
4.487 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.488 + }
4.489 + }
4.490 + }
4.491 + EachEdgeIt& operator++() {
4.492 + if (out_or_in) {
4.493 + ++out;
4.494 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.495 + while (v.valid() && !out.valid()) {
4.496 + ++v;
4.497 + if (v.valid()) G->getFirst(out, v);
4.498 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.499 + }
4.500 + if (!out.valid()) {
4.501 + out_or_in=0;
4.502 + G->getFirst(v);
4.503 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
4.504 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.505 + while (v.valid() && !in.valid()) {
4.506 + ++v;
4.507 + if (v.valid()) G->getFirst(in, v);
4.508 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.509 + }
4.510 + }
4.511 + } else {
4.512 + ++in;
4.513 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.514 + while (v.valid() && !in.valid()) {
4.515 + ++v;
4.516 + if (v.valid()) G->getFirst(in, v);
4.517 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.518 + }
4.519 + }
4.520 + return *this;
4.521 + }
4.522 + };
4.523 +
4.524 + void getFirst(EachNodeIt& v) const { G->getFirst(v); }
4.525 + void getFirst(OutEdgeIt& e, NodeIt v) const {
4.526 + e=OutEdgeIt(*G, v, *flow, *capacity);
4.527 + }
4.528 + void getFirst(EachEdgeIt& e) const {
4.529 + e=EachEdgeIt(*G, *flow, *capacity);
4.530 + }
4.531 +
4.532 + EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
4.533 +
4.534 + OutEdgeIt& next(OutEdgeIt& e) const {
4.535 + if (e.out_or_in) {
4.536 + NodeIt v=G->aNode(e.out);
4.537 + ++(e.out);
4.538 + while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.539 + if (!G->valid(e.out)) {
4.540 + e.out_or_in=0;
4.541 + G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
4.542 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.543 + }
4.544 + } else {
4.545 + ++(e.in);
4.546 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.547 + }
4.548 + return e;
4.549 + }
4.550 +
4.551 + EachEdgeIt& next(EachEdgeIt& e) const {
4.552 + if (e.out_or_in) {
4.553 + ++(e.out);
4.554 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.555 + while (G->valid(e.v) && !G->valid(e.out)) {
4.556 + ++(e.v);
4.557 + if (G->valid(e.v)) G->getFirst(e.out, e.v);
4.558 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.559 + }
4.560 + if (!G->valid(e.out)) {
4.561 + e.out_or_in=0;
4.562 + G->getFirst(e.v);
4.563 + if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
4.564 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.565 + while (G->valid(e.v) && !G->valid(e.in)) {
4.566 + ++(e.v);
4.567 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
4.568 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.569 + }
4.570 + }
4.571 + } else {
4.572 + ++(e.in);
4.573 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.574 + while (G->valid(e.v) && !G->valid(e.in)) {
4.575 + ++(e.v);
4.576 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
4.577 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.578 + }
4.579 + }
4.580 + return e;
4.581 + }
4.582
4.583 - //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
4.584 - //iranyitatlant, ami van
4.585 - //mert csak 1 dolgot lehet be typedef-elni
4.586 - typedef typename Graph::OutEdgeIt SymEdgeIt;
4.587 - //typedef typename Graph::InEdgeIt SymEdgeIt;
4.588 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.589 - typedef typename Graph::EachEdgeIt EachEdgeIt;
4.590
4.591 - int nodeNum() const { return graph->nodeNum(); }
4.592 - int edgeNum() const { return graph->edgeNum(); }
4.593 -
4.594 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.595 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.596 - return graph->getFirst(i, p); }
4.597 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.598 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.599 + template< typename It >
4.600 + It first() const {
4.601 + It e;
4.602 + getFirst(e);
4.603 + return e;
4.604 + }
4.605
4.606 - template< typename It > It first() const {
4.607 - It e; getFirst(e); return e; }
4.608 + template< typename It >
4.609 + It first(NodeIt v) const {
4.610 + It e;
4.611 + getFirst(e, v);
4.612 + return e;
4.613 + }
4.614
4.615 - template< typename It > It first(NodeIt v) const {
4.616 - It e; getFirst(e, v); return e; }
4.617 + NodeIt tail(EdgeIt e) const {
4.618 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
4.619 + NodeIt head(EdgeIt e) const {
4.620 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
4.621
4.622 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.623 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.624 -
4.625 - template<typename I> NodeIt aNode(const I& e) const {
4.626 - return graph->aNode(e); }
4.627 - template<typename I> NodeIt bNode(const I& e) const {
4.628 - return graph->bNode(e); }
4.629 -
4.630 - //template<typename I> bool valid(const I i);
4.631 - //{ return graph->valid(i); }
4.632 -
4.633 - //template<typename I> void setInvalid(const I &i);
4.634 - //{ return graph->setInvalid(i); }
4.635 -
4.636 - NodeIt addNode() { return graph->addNode(); }
4.637 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.638 - return graph->addEdge(tail, head); }
4.639 -
4.640 - template<typename I> void erase(const I& i) { graph->erase(i); }
4.641 -
4.642 - void clear() { graph->clear(); }
4.643 -
4.644 - template<typename T> class NodeMap : public Graph::NodeMap<T> { };
4.645 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
4.646 -
4.647 - void setGraph(Graph& _graph) { graph = &_graph; }
4.648 - Graph& getGraph() { return (*graph); }
4.649 + NodeIt aNode(OutEdgeIt e) const {
4.650 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
4.651 + NodeIt bNode(OutEdgeIt e) const {
4.652 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
4.653
4.654 - //SymGraphWrapper() : graph(0) { }
4.655 - SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.656 + int id(NodeIt v) const { return G->id(v); }
4.657 +
4.658 + bool valid(NodeIt n) const { return G->valid(n); }
4.659 + bool valid(EdgeIt e) const {
4.660 + return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
4.661 +
4.662 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.663 + public:
4.664 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
4.665 + : Graph::NodeMap<T>(*(_G.G)) { }
4.666 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
4.667 + T a) : Graph::NodeMap<T>(*(_G.G), a) { }
4.668 + };
4.669 +
4.670 +// template <typename T>
4.671 +// class NodeMap {
4.672 +// typename Graph::NodeMap<T> node_map;
4.673 +// public:
4.674 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
4.675 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
4.676 +// void set(NodeIt nit, T a) { node_map.set(nit, a); }
4.677 +// T get(NodeIt nit) const { return node_map.get(nit); }
4.678 +// };
4.679 +
4.680 + template <typename T>
4.681 + class EdgeMap {
4.682 + typename Graph::EdgeMap<T> forward_map, backward_map;
4.683 + public:
4.684 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
4.685 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
4.686 + void set(EdgeIt e, T a) {
4.687 + if (e.out_or_in)
4.688 + forward_map.set(e.out, a);
4.689 + else
4.690 + backward_map.set(e.in, a);
4.691 + }
4.692 + T get(EdgeIt e) {
4.693 + if (e.out_or_in)
4.694 + return forward_map.get(e.out);
4.695 + else
4.696 + return backward_map.get(e.in);
4.697 + }
4.698 + };
4.699 +
4.700 };
4.701
4.702
4.703 @@ -422,158 +684,6 @@
4.704 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.705 // };
4.706
4.707 -
4.708 -// // FIXME: comparison should be made better!!!
4.709 -// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.710 -// class ConstResGraphWrapper
4.711 -// {
4.712 -// const Graph* graph;
4.713 -// const LowerMap* low;
4.714 -// FlowMap* flow;
4.715 -// const UpperMap* up;
4.716 -// public:
4.717 -// typedef Graph BaseGraph;
4.718 -
4.719 -// typedef typename Graph::NodeIt NodeIt;
4.720 -// typedef typename Graph::EdgeIt EdgeIt;
4.721 -
4.722 -// typedef typename Graph::EachNodeIt EachNodeIt;
4.723 -
4.724 -// class OutEdgeIt {
4.725 -// public:
4.726 -// //Graph::NodeIt n;
4.727 -// bool out_or_in;
4.728 -// typename Graph::SymEdgeIt sym;
4.729 -// };
4.730 -// class InEdgeIt {
4.731 -// public:
4.732 -// //Graph::NodeIt n;
4.733 -// bool out_or_in;
4.734 -// typename Graph::OutEdgeIt sym;
4.735 -// };
4.736 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.737 -// //typedef typename Graph::EachEdgeIt EachEdgeIt;
4.738 -
4.739 -// int nodeNum() const { return graph->nodeNum(); }
4.740 -// //int edgeNum() const { return graph->edgeNum(); }
4.741 -
4.742 -// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
4.743 -
4.744 -// // EachEdge and SymEdge is missing!!!!
4.745 -// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
4.746 -
4.747 -
4.748 -// //FIXME
4.749 -// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
4.750 -// {
4.751 -// e.n=n;
4.752 -// graph->getFirst(e.o,n);
4.753 -// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.754 -// graph->goNext(e.o);
4.755 -// if(!graph->valid(e.o)) {
4.756 -// graph->getFirst(e.i,n);
4.757 -// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.758 -// graph->goNext(e.i);
4.759 -// }
4.760 -// return e;
4.761 -// }
4.762 -// /*
4.763 -// OutEdgeIt &goNext(OutEdgeIt &e)
4.764 -// {
4.765 -// if(graph->valid(e.o)) {
4.766 -// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.767 -// graph->goNext(e.o);
4.768 -// if(graph->valid(e.o)) return e;
4.769 -// else graph->getFirst(e.i,e.n);
4.770 -// }
4.771 -// else {
4.772 -// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.773 -// graph->goNext(e.i);
4.774 -// return e;
4.775 -// }
4.776 -// }
4.777 -// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
4.778 -// */
4.779 -// //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
4.780 -
4.781 -// //FIXME
4.782 -// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
4.783 -// {
4.784 -// e.n=n;
4.785 -// graph->getFirst(e.i,n);
4.786 -// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.787 -// graph->goNext(e.i);
4.788 -// if(!graph->valid(e.i)) {
4.789 -// graph->getFirst(e.o,n);
4.790 -// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.791 -// graph->goNext(e.o);
4.792 -// }
4.793 -// return e;
4.794 -// }
4.795 -// /*
4.796 -// InEdgeIt &goNext(InEdgeIt &e)
4.797 -// {
4.798 -// if(graph->valid(e.i)) {
4.799 -// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.800 -// graph->goNext(e.i);
4.801 -// if(graph->valid(e.i)) return e;
4.802 -// else graph->getFirst(e.o,e.n);
4.803 -// }
4.804 -// else {
4.805 -// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.806 -// graph->goNext(e.o);
4.807 -// return e;
4.808 -// }
4.809 -// }
4.810 -// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
4.811 -// */
4.812 -// //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
4.813 -
4.814 -// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.815 -// //template<typename I> I next(const I i); { return graph->goNext(i); }
4.816 -
4.817 -// template< typename It > It first() const {
4.818 -// It e; getFirst(e); return e; }
4.819 -
4.820 -// template< typename It > It first(NodeIt v) const {
4.821 -// It e; getFirst(e, v); return e; }
4.822 -
4.823 -// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.824 -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.825 -
4.826 -// template<typename I> NodeIt aNode(const I& e) const {
4.827 -// return graph->aNode(e); }
4.828 -// template<typename I> NodeIt bNode(const I& e) const {
4.829 -// return graph->bNode(e); }
4.830 -
4.831 -// //template<typename I> bool valid(const I i);
4.832 -// //{ return graph->valid(i); }
4.833 -
4.834 -// //template<typename I> void setInvalid(const I &i);
4.835 -// //{ return graph->setInvalid(i); }
4.836 -
4.837 -// NodeIt addNode() { return graph->addNode(); }
4.838 -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.839 -// return graph->addEdge(tail, head); }
4.840 -
4.841 -// template<typename I> void erase(const I& i) { graph->erase(i); }
4.842 -
4.843 -// void clear() { graph->clear(); }
4.844 -
4.845 -// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
4.846 -// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
4.847 -
4.848 -// void setGraph(const Graph& _graph) { graph = &_graph; }
4.849 -// const Graph& getGraph() { return (*graph); }
4.850 -
4.851 -// //ConstResGraphWrapper() : graph(0) { }
4.852 -// ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
4.853 -// };
4.854 -
4.855 -
4.856 -
4.857 -
4.858 -
4.859 } //namespace hugo
4.860
4.861 #endif //GRAPH_WRAPPER_H
5.1 --- a/src/work/marci_graph_demo.cc Thu Mar 04 15:13:43 2004 +0000
5.2 +++ b/src/work/marci_graph_demo.cc Thu Mar 04 19:38:07 2004 +0000
5.3 @@ -245,7 +245,7 @@
5.4 std::cout<<std::endl;
5.5 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.6 }
5.7 -
5.8 +/*
5.9 {
5.10 std::list<NodeIt> S;
5.11 S.push_back(s); S.push_back(v3);
5.12 @@ -263,6 +263,6 @@
5.13 std::cout<<std::endl;
5.14 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.15 }
5.16 -
5.17 +*/
5.18 return 0;
5.19 }