1.1 --- a/src/work/marci/graph_wrapper.h Thu Mar 04 15:13:43 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Thu Mar 04 19:38:07 2004 +0000
1.3 @@ -12,44 +12,45 @@
1.4 typedef Graph BaseGraph;
1.5
1.6 typedef typename Graph::NodeIt NodeIt;
1.7 - typedef typename Graph::EdgeIt EdgeIt;
1.8 -
1.9 typedef typename Graph::EachNodeIt EachNodeIt;
1.10
1.11 + typedef typename Graph::EdgeIt EdgeIt;
1.12 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.13 typedef typename Graph::InEdgeIt InEdgeIt;
1.14 - typedef typename Graph::SymEdgeIt SymEdgeIt;
1.15 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.16 typedef typename Graph::EachEdgeIt EachEdgeIt;
1.17 -
1.18 - int nodeNum() const { return graph->nodeNum(); }
1.19 - int edgeNum() const { return graph->edgeNum(); }
1.20
1.21 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.22 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.23 return graph->getFirst(i, p); }
1.24 - //template<typename I> I next(const I i); { return graph->goNext(i); }
1.25 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.26 +
1.27 + template<typename I> I getNext(const I& i) const {
1.28 + return graph->getNext(i); }
1.29 + template<typename I> I& next(I &i) const { return graph->next(i); }
1.30
1.31 template< typename It > It first() const {
1.32 It e; getFirst(e); return e; }
1.33
1.34 - template< typename It > It first(NodeIt v) const {
1.35 + template< typename It > It first(const NodeIt& v) const {
1.36 It e; getFirst(e, v); return e; }
1.37
1.38 NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.39 NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.40 +
1.41 + template<typename I> bool valid(const I& i) const
1.42 + { return graph->valid(i); }
1.43 +
1.44 + //template<typename I> void setInvalid(const I &i);
1.45 + //{ return graph->setInvalid(i); }
1.46 +
1.47 + int nodeNum() const { return graph->nodeNum(); }
1.48 + int edgeNum() const { return graph->edgeNum(); }
1.49
1.50 template<typename I> NodeIt aNode(const I& e) const {
1.51 return graph->aNode(e); }
1.52 template<typename I> NodeIt bNode(const I& e) const {
1.53 return graph->bNode(e); }
1.54
1.55 - //template<typename I> bool valid(const I& i)
1.56 - //{ return graph->valid(i); }
1.57 -
1.58 - //template<typename I> void setInvalid(const I &i);
1.59 - //{ return graph->setInvalid(i); }
1.60 -
1.61 NodeIt addNode() const { return graph->addNode(); }
1.62 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
1.63 return graph->addEdge(tail, head); }
1.64 @@ -57,91 +58,30 @@
1.65 template<typename I> void erase(const I& i) const { graph->erase(i); }
1.66
1.67 void clear() const { graph->clear(); }
1.68 -
1.69 +
1.70 template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.71 public:
1.72 - NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
1.73 - NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
1.74 + NodeMap(const TrivGraphWrapper<Graph>& _G) :
1.75 + Graph::NodeMap<T>(*(_G.G)) { }
1.76 + NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.77 + Graph::NodeMap<T>(*(_G.G), a) { }
1.78 };
1.79 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.80 -
1.81 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.82 + public:
1.83 + EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.84 + Graph::EdgeMap<T>(*(_G.G)) { }
1.85 + EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.86 + Graph::EdgeMap<T>(*(_G.G), a) { }
1.87 + };
1.88 +
1.89 void setGraph(Graph& _graph) { graph = &_graph; }
1.90 - Graph& getGraph() { return (*graph); }
1.91 + Graph& getGraph() const { return (*graph); }
1.92
1.93 //TrivGraphWrapper() : graph(0) { }
1.94 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.95 };
1.96
1.97 template<typename Graph>
1.98 - class ConstTrivGraphWrapper {
1.99 - const Graph* graph;
1.100 -
1.101 - public:
1.102 - typedef Graph BaseGraph;
1.103 -
1.104 - typedef typename Graph::NodeIt NodeIt;
1.105 - typedef typename Graph::EdgeIt EdgeIt;
1.106 -
1.107 - typedef typename Graph::EachNodeIt EachNodeIt;
1.108 -
1.109 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.110 - typedef typename Graph::InEdgeIt InEdgeIt;
1.111 - typedef typename Graph::SymEdgeIt SymEdgeIt;
1.112 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.113 -
1.114 - int nodeNum() const { return graph->nodeNum(); }
1.115 - int edgeNum() const { return graph->edgeNum(); }
1.116 -
1.117 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.118 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.119 - return graph->getFirst(i, p); }
1.120 - //template<typename I> I next(const I i); { return graph->goNext(i); }
1.121 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.122 -
1.123 - template< typename It > It first() const {
1.124 - It e; getFirst(e); return e; }
1.125 -
1.126 - template< typename It > It first(NodeIt v) const {
1.127 - It e; getFirst(e, v); return e; }
1.128 -
1.129 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.130 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.131 -
1.132 - template<typename I> NodeIt aNode(const I& e) const {
1.133 - return graph->aNode(e); }
1.134 - template<typename I> NodeIt bNode(const I& e) const {
1.135 - return graph->bNode(e); }
1.136 -
1.137 - //template<typename I> bool valid(const I& i)
1.138 - //{ return graph->valid(i); }
1.139 -
1.140 - //template<typename I> void setInvalid(const I &i);
1.141 - //{ return graph->setInvalid(i); }
1.142 -
1.143 - NodeIt addNode() const { return graph->addNode(); }
1.144 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
1.145 - return graph->addEdge(tail, head); }
1.146 -
1.147 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.148 -
1.149 - void clear() const { graph->clear(); }
1.150 -
1.151 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.152 - public:
1.153 - NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
1.154 - NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
1.155 - };
1.156 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.157 -
1.158 - void setGraph(const Graph& _graph) { graph = &_graph; }
1.159 - const Graph& getGraph() { return (*graph); }
1.160 -
1.161 - //ConstTrivGraphWrapper() : graph(0) { }
1.162 - ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }
1.163 - };
1.164 -
1.165 -
1.166 - template<typename Graph>
1.167 class RevGraphWrapper
1.168 {
1.169 Graph* graph;
1.170 @@ -149,129 +89,451 @@
1.171 public:
1.172 typedef Graph BaseGraph;
1.173
1.174 - typedef typename Graph::NodeIt NodeIt;
1.175 - typedef typename Graph::EdgeIt EdgeIt;
1.176 -
1.177 + typedef typename Graph::NodeIt NodeIt;
1.178 typedef typename Graph::EachNodeIt EachNodeIt;
1.179
1.180 + typedef typename Graph::EdgeIt EdgeIt;
1.181 typedef typename Graph::OutEdgeIt InEdgeIt;
1.182 typedef typename Graph::InEdgeIt OutEdgeIt;
1.183 - typedef typename Graph::SymEdgeIt SymEdgeIt;
1.184 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.185 typedef typename Graph::EachEdgeIt EachEdgeIt;
1.186 -
1.187 - int nodeNum() const { return graph->nodeNum(); }
1.188 - int edgeNum() const { return graph->edgeNum(); }
1.189
1.190 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.191 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.192 return graph->getFirst(i, p); }
1.193 - //template<typename I> I next(const I i); { return graph->goNext(i); }
1.194 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.195 +
1.196 + template<typename I> I getNext(const I& i) const {
1.197 + return graph->getNext(i); }
1.198 + template<typename I> I& next(I &i) const { return graph->next(i); }
1.199
1.200 template< typename It > It first() const {
1.201 It e; getFirst(e); return e; }
1.202
1.203 - template< typename It > It first(NodeIt v) const {
1.204 + template< typename It > It first(const NodeIt& v) const {
1.205 It e; getFirst(e, v); return e; }
1.206
1.207 NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
1.208 NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
1.209
1.210 + template<typename I> bool valid(const I& i) const
1.211 + { return graph->valid(i); }
1.212 +
1.213 + //template<typename I> void setInvalid(const I &i);
1.214 + //{ return graph->setInvalid(i); }
1.215 +
1.216 template<typename I> NodeIt aNode(const I& e) const {
1.217 return graph->aNode(e); }
1.218 template<typename I> NodeIt bNode(const I& e) const {
1.219 return graph->bNode(e); }
1.220 -
1.221 - //template<typename I> bool valid(const I i);
1.222 - //{ return graph->valid(i); }
1.223 -
1.224 - //template<typename I> void setInvalid(const I &i);
1.225 - //{ return graph->setInvalid(i); }
1.226 -
1.227 - NodeIt addNode() { return graph->addNode(); }
1.228 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
1.229 +
1.230 + NodeIt addNode() const { return graph->addNode(); }
1.231 + EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
1.232 return graph->addEdge(tail, head); }
1.233
1.234 - template<typename I> void erase(const I& i) { graph->erase(i); }
1.235 + int nodeNum() const { return graph->nodeNum(); }
1.236 + int edgeNum() const { return graph->edgeNum(); }
1.237
1.238 - void clear() { graph->clear(); }
1.239 + template<typename I> void erase(const I& i) const { graph->erase(i); }
1.240
1.241 - template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.242 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.243 -
1.244 + void clear() const { graph->clear(); }
1.245 +
1.246 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.247 + public:
1.248 + NodeMap(const RevGraphWrapper<Graph>& _G) :
1.249 + Graph::NodeMap<T>(*(_G.G)) { }
1.250 + NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.251 + Graph::NodeMap<T>(*(_G.G), a) { }
1.252 + };
1.253 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.254 + public:
1.255 + EdgeMap(const RevGraphWrapper<Graph>& _G) :
1.256 + Graph::EdgeMap<T>(*(_G.G)) { }
1.257 + EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.258 + Graph::EdgeMap<T>(*(_G.G), a) { }
1.259 + };
1.260 +
1.261 void setGraph(Graph& _graph) { graph = &_graph; }
1.262 - Graph& getGraph() { return (*graph); }
1.263 + Graph& getGraph() const { return (*graph); }
1.264
1.265 //RevGraphWrapper() : graph(0) { }
1.266 RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.267 };
1.268
1.269 - template<typename Graph>
1.270 - class SymGraphWrapper
1.271 - {
1.272 - Graph* graph;
1.273 +
1.274 +// template<typename Graph>
1.275 +// class SymGraphWrapper
1.276 +// {
1.277 +// Graph* graph;
1.278
1.279 +// public:
1.280 +// typedef Graph BaseGraph;
1.281 +
1.282 +// typedef typename Graph::NodeIt NodeIt;
1.283 +// typedef typename Graph::EdgeIt EdgeIt;
1.284 +
1.285 +// typedef typename Graph::EachNodeIt EachNodeIt;
1.286 +
1.287 +// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.288 +// //iranyitatlant, ami van
1.289 +// //mert csak 1 dolgot lehet be typedef-elni
1.290 +// typedef typename Graph::OutEdgeIt SymEdgeIt;
1.291 +// //typedef typename Graph::InEdgeIt SymEdgeIt;
1.292 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.293 +// typedef typename Graph::EachEdgeIt EachEdgeIt;
1.294 +
1.295 +// int nodeNum() const { return graph->nodeNum(); }
1.296 +// int edgeNum() const { return graph->edgeNum(); }
1.297 +
1.298 +// template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.299 +// template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.300 +// return graph->getFirst(i, p); }
1.301 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.302 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.303 +
1.304 +// template< typename It > It first() const {
1.305 +// It e; getFirst(e); return e; }
1.306 +
1.307 +// template< typename It > It first(NodeIt v) const {
1.308 +// It e; getFirst(e, v); return e; }
1.309 +
1.310 +// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.311 +// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.312 +
1.313 +// template<typename I> NodeIt aNode(const I& e) const {
1.314 +// return graph->aNode(e); }
1.315 +// template<typename I> NodeIt bNode(const I& e) const {
1.316 +// return graph->bNode(e); }
1.317 +
1.318 +// //template<typename I> bool valid(const I i);
1.319 +// //{ return graph->valid(i); }
1.320 +
1.321 +// //template<typename I> void setInvalid(const I &i);
1.322 +// //{ return graph->setInvalid(i); }
1.323 +
1.324 +// NodeIt addNode() { return graph->addNode(); }
1.325 +// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
1.326 +// return graph->addEdge(tail, head); }
1.327 +
1.328 +// template<typename I> void erase(const I& i) { graph->erase(i); }
1.329 +
1.330 +// void clear() { graph->clear(); }
1.331 +
1.332 +// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.333 +// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.334 +
1.335 +// void setGraph(Graph& _graph) { graph = &_graph; }
1.336 +// Graph& getGraph() { return (*graph); }
1.337 +
1.338 +// //SymGraphWrapper() : graph(0) { }
1.339 +// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.340 +// };
1.341 +
1.342 +
1.343 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.344 + class ResGraphWrapper {
1.345 public:
1.346 typedef Graph BaseGraph;
1.347 + typedef typename Graph::NodeIt NodeIt;
1.348 + typedef typename Graph::EachNodeIt EachNodeIt;
1.349 + private:
1.350 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.351 + typedef typename Graph::InEdgeIt OldInEdgeIt;
1.352 + const Graph* G;
1.353 + FlowMap* flow;
1.354 + const CapacityMap* capacity;
1.355 + public:
1.356 + ResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.357 + const CapacityMap& _capacity) :
1.358 + G(&_G), flow(&_flow), capacity(&_capacity) { }
1.359 +// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
1.360 +// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
1.361 + class EdgeIt;
1.362 + class OutEdgeIt;
1.363 + friend class EdgeIt;
1.364 + friend class OutEdgeIt;
1.365
1.366 - typedef typename Graph::NodeIt NodeIt;
1.367 - typedef typename Graph::EdgeIt EdgeIt;
1.368 -
1.369 - typedef typename Graph::EachNodeIt EachNodeIt;
1.370 + class EdgeIt {
1.371 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.372 + protected:
1.373 + //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
1.374 + const Graph* G;
1.375 + FlowMap* flow;
1.376 + const CapacityMap* capacity;
1.377 + //OldSymEdgeIt sym;
1.378 + OldOutEdgeIt out;
1.379 + OldInEdgeIt in;
1.380 + bool out_or_in; //true, iff out
1.381 + public:
1.382 + EdgeIt() : out_or_in(true) { }
1.383 + EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
1.384 + G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
1.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) { }
1.386 + Number free() const {
1.387 + if (out_or_in) {
1.388 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.389 + } else {
1.390 + return (/*resG->*/flow->get(in));
1.391 + }
1.392 + }
1.393 + bool valid() const {
1.394 + return out_or_in && out.valid() || in.valid(); }
1.395 + void augment(Number a) const {
1.396 + if (out_or_in) {
1.397 + /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
1.398 + } else {
1.399 + /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
1.400 + }
1.401 + }
1.402 + void print() {
1.403 + if (out_or_in) {
1.404 + std::cout << "out ";
1.405 + if (out.valid())
1.406 + std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
1.407 + else
1.408 + std::cout << "invalid";
1.409 + }
1.410 + else {
1.411 + std::cout << "in ";
1.412 + if (in.valid())
1.413 + std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
1.414 + else
1.415 + std::cout << "invalid";
1.416 + }
1.417 + std::cout << std::endl;
1.418 + }
1.419 + };
1.420 +
1.421 + Number free(OldOutEdgeIt out) const {
1.422 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.423 + }
1.424 + Number free(OldInEdgeIt in) const {
1.425 + return (/*resG->*/flow->get(in));
1.426 + }
1.427 +
1.428 + class OutEdgeIt : public EdgeIt {
1.429 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.430 + public:
1.431 + OutEdgeIt() { }
1.432 + private:
1.433 + OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.434 + //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
1.435 + G->getFirst(out, v);
1.436 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.437 + if (!out.valid()) {
1.438 + out_or_in=0;
1.439 + //in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.440 + G->getFirst(in, v);
1.441 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.442 + }
1.443 + }
1.444 + public:
1.445 + OutEdgeIt& operator++() {
1.446 + if (out_or_in) {
1.447 + NodeIt v=/*resG->*/G->aNode(out);
1.448 + ++out;
1.449 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.450 + if (!out.valid()) {
1.451 + out_or_in=0;
1.452 + G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.453 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.454 + }
1.455 + } else {
1.456 + ++in;
1.457 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.458 + }
1.459 + return *this;
1.460 + }
1.461 + };
1.462 +
1.463 + class EachEdgeIt : public EdgeIt {
1.464 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.465 + typename Graph::EachNodeIt v;
1.466 + public:
1.467 + EachEdgeIt() { }
1.468 + //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
1.469 + EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.470 + out_or_in=true;
1.471 + G->getFirst(v);
1.472 + if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
1.473 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.474 + while (v.valid() && !out.valid()) {
1.475 + ++v;
1.476 + if (v.valid()) G->getFirst(out, v);
1.477 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.478 + }
1.479 + if (!out.valid()) {
1.480 + out_or_in=0;
1.481 + G->getFirst(v);
1.482 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.483 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.484 + while (v.valid() && !in.valid()) {
1.485 + ++v;
1.486 + if (v.valid()) G->getFirst(in, v);
1.487 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.488 + }
1.489 + }
1.490 + }
1.491 + EachEdgeIt& operator++() {
1.492 + if (out_or_in) {
1.493 + ++out;
1.494 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.495 + while (v.valid() && !out.valid()) {
1.496 + ++v;
1.497 + if (v.valid()) G->getFirst(out, v);
1.498 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.499 + }
1.500 + if (!out.valid()) {
1.501 + out_or_in=0;
1.502 + G->getFirst(v);
1.503 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.504 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.505 + while (v.valid() && !in.valid()) {
1.506 + ++v;
1.507 + if (v.valid()) G->getFirst(in, v);
1.508 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.509 + }
1.510 + }
1.511 + } else {
1.512 + ++in;
1.513 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.514 + while (v.valid() && !in.valid()) {
1.515 + ++v;
1.516 + if (v.valid()) G->getFirst(in, v);
1.517 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.518 + }
1.519 + }
1.520 + return *this;
1.521 + }
1.522 + };
1.523 +
1.524 + void getFirst(EachNodeIt& v) const { G->getFirst(v); }
1.525 + void getFirst(OutEdgeIt& e, NodeIt v) const {
1.526 + e=OutEdgeIt(*G, v, *flow, *capacity);
1.527 + }
1.528 + void getFirst(EachEdgeIt& e) const {
1.529 + e=EachEdgeIt(*G, *flow, *capacity);
1.530 + }
1.531 +
1.532 + EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
1.533 +
1.534 + OutEdgeIt& next(OutEdgeIt& e) const {
1.535 + if (e.out_or_in) {
1.536 + NodeIt v=G->aNode(e.out);
1.537 + ++(e.out);
1.538 + while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.539 + if (!G->valid(e.out)) {
1.540 + e.out_or_in=0;
1.541 + G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.542 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.543 + }
1.544 + } else {
1.545 + ++(e.in);
1.546 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.547 + }
1.548 + return e;
1.549 + }
1.550 +
1.551 + EachEdgeIt& next(EachEdgeIt& e) const {
1.552 + if (e.out_or_in) {
1.553 + ++(e.out);
1.554 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.555 + while (G->valid(e.v) && !G->valid(e.out)) {
1.556 + ++(e.v);
1.557 + if (G->valid(e.v)) G->getFirst(e.out, e.v);
1.558 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.559 + }
1.560 + if (!G->valid(e.out)) {
1.561 + e.out_or_in=0;
1.562 + G->getFirst(e.v);
1.563 + if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
1.564 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.565 + while (G->valid(e.v) && !G->valid(e.in)) {
1.566 + ++(e.v);
1.567 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.568 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.569 + }
1.570 + }
1.571 + } else {
1.572 + ++(e.in);
1.573 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.574 + while (G->valid(e.v) && !G->valid(e.in)) {
1.575 + ++(e.v);
1.576 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.577 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.578 + }
1.579 + }
1.580 + return e;
1.581 + }
1.582
1.583 - //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.584 - //iranyitatlant, ami van
1.585 - //mert csak 1 dolgot lehet be typedef-elni
1.586 - typedef typename Graph::OutEdgeIt SymEdgeIt;
1.587 - //typedef typename Graph::InEdgeIt SymEdgeIt;
1.588 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.589 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.590
1.591 - int nodeNum() const { return graph->nodeNum(); }
1.592 - int edgeNum() const { return graph->edgeNum(); }
1.593 -
1.594 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.595 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.596 - return graph->getFirst(i, p); }
1.597 - //template<typename I> I next(const I i); { return graph->goNext(i); }
1.598 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.599 + template< typename It >
1.600 + It first() const {
1.601 + It e;
1.602 + getFirst(e);
1.603 + return e;
1.604 + }
1.605
1.606 - template< typename It > It first() const {
1.607 - It e; getFirst(e); return e; }
1.608 + template< typename It >
1.609 + It first(NodeIt v) const {
1.610 + It e;
1.611 + getFirst(e, v);
1.612 + return e;
1.613 + }
1.614
1.615 - template< typename It > It first(NodeIt v) const {
1.616 - It e; getFirst(e, v); return e; }
1.617 + NodeIt tail(EdgeIt e) const {
1.618 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.619 + NodeIt head(EdgeIt e) const {
1.620 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.621
1.622 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.623 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.624 -
1.625 - template<typename I> NodeIt aNode(const I& e) const {
1.626 - return graph->aNode(e); }
1.627 - template<typename I> NodeIt bNode(const I& e) const {
1.628 - return graph->bNode(e); }
1.629 -
1.630 - //template<typename I> bool valid(const I i);
1.631 - //{ return graph->valid(i); }
1.632 -
1.633 - //template<typename I> void setInvalid(const I &i);
1.634 - //{ return graph->setInvalid(i); }
1.635 -
1.636 - NodeIt addNode() { return graph->addNode(); }
1.637 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
1.638 - return graph->addEdge(tail, head); }
1.639 -
1.640 - template<typename I> void erase(const I& i) { graph->erase(i); }
1.641 -
1.642 - void clear() { graph->clear(); }
1.643 -
1.644 - template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.645 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.646 -
1.647 - void setGraph(Graph& _graph) { graph = &_graph; }
1.648 - Graph& getGraph() { return (*graph); }
1.649 + NodeIt aNode(OutEdgeIt e) const {
1.650 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.651 + NodeIt bNode(OutEdgeIt e) const {
1.652 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.653
1.654 - //SymGraphWrapper() : graph(0) { }
1.655 - SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.656 + int id(NodeIt v) const { return G->id(v); }
1.657 +
1.658 + bool valid(NodeIt n) const { return G->valid(n); }
1.659 + bool valid(EdgeIt e) const {
1.660 + return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
1.661 +
1.662 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.663 + public:
1.664 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1.665 + : Graph::NodeMap<T>(*(_G.G)) { }
1.666 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1.667 + T a) : Graph::NodeMap<T>(*(_G.G), a) { }
1.668 + };
1.669 +
1.670 +// template <typename T>
1.671 +// class NodeMap {
1.672 +// typename Graph::NodeMap<T> node_map;
1.673 +// public:
1.674 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
1.675 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
1.676 +// void set(NodeIt nit, T a) { node_map.set(nit, a); }
1.677 +// T get(NodeIt nit) const { return node_map.get(nit); }
1.678 +// };
1.679 +
1.680 + template <typename T>
1.681 + class EdgeMap {
1.682 + typename Graph::EdgeMap<T> forward_map, backward_map;
1.683 + public:
1.684 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
1.685 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
1.686 + void set(EdgeIt e, T a) {
1.687 + if (e.out_or_in)
1.688 + forward_map.set(e.out, a);
1.689 + else
1.690 + backward_map.set(e.in, a);
1.691 + }
1.692 + T get(EdgeIt e) {
1.693 + if (e.out_or_in)
1.694 + return forward_map.get(e.out);
1.695 + else
1.696 + return backward_map.get(e.in);
1.697 + }
1.698 + };
1.699 +
1.700 };
1.701
1.702
1.703 @@ -422,158 +684,6 @@
1.704 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.705 // };
1.706
1.707 -
1.708 -// // FIXME: comparison should be made better!!!
1.709 -// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.710 -// class ConstResGraphWrapper
1.711 -// {
1.712 -// const Graph* graph;
1.713 -// const LowerMap* low;
1.714 -// FlowMap* flow;
1.715 -// const UpperMap* up;
1.716 -// public:
1.717 -// typedef Graph BaseGraph;
1.718 -
1.719 -// typedef typename Graph::NodeIt NodeIt;
1.720 -// typedef typename Graph::EdgeIt EdgeIt;
1.721 -
1.722 -// typedef typename Graph::EachNodeIt EachNodeIt;
1.723 -
1.724 -// class OutEdgeIt {
1.725 -// public:
1.726 -// //Graph::NodeIt n;
1.727 -// bool out_or_in;
1.728 -// typename Graph::SymEdgeIt sym;
1.729 -// };
1.730 -// class InEdgeIt {
1.731 -// public:
1.732 -// //Graph::NodeIt n;
1.733 -// bool out_or_in;
1.734 -// typename Graph::OutEdgeIt sym;
1.735 -// };
1.736 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.737 -// //typedef typename Graph::EachEdgeIt EachEdgeIt;
1.738 -
1.739 -// int nodeNum() const { return graph->nodeNum(); }
1.740 -// //int edgeNum() const { return graph->edgeNum(); }
1.741 -
1.742 -// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
1.743 -
1.744 -// // EachEdge and SymEdge is missing!!!!
1.745 -// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
1.746 -
1.747 -
1.748 -// //FIXME
1.749 -// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
1.750 -// {
1.751 -// e.n=n;
1.752 -// graph->getFirst(e.o,n);
1.753 -// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.754 -// graph->goNext(e.o);
1.755 -// if(!graph->valid(e.o)) {
1.756 -// graph->getFirst(e.i,n);
1.757 -// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.758 -// graph->goNext(e.i);
1.759 -// }
1.760 -// return e;
1.761 -// }
1.762 -// /*
1.763 -// OutEdgeIt &goNext(OutEdgeIt &e)
1.764 -// {
1.765 -// if(graph->valid(e.o)) {
1.766 -// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.767 -// graph->goNext(e.o);
1.768 -// if(graph->valid(e.o)) return e;
1.769 -// else graph->getFirst(e.i,e.n);
1.770 -// }
1.771 -// else {
1.772 -// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.773 -// graph->goNext(e.i);
1.774 -// return e;
1.775 -// }
1.776 -// }
1.777 -// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1.778 -// */
1.779 -// //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
1.780 -
1.781 -// //FIXME
1.782 -// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
1.783 -// {
1.784 -// e.n=n;
1.785 -// graph->getFirst(e.i,n);
1.786 -// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.787 -// graph->goNext(e.i);
1.788 -// if(!graph->valid(e.i)) {
1.789 -// graph->getFirst(e.o,n);
1.790 -// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.791 -// graph->goNext(e.o);
1.792 -// }
1.793 -// return e;
1.794 -// }
1.795 -// /*
1.796 -// InEdgeIt &goNext(InEdgeIt &e)
1.797 -// {
1.798 -// if(graph->valid(e.i)) {
1.799 -// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.800 -// graph->goNext(e.i);
1.801 -// if(graph->valid(e.i)) return e;
1.802 -// else graph->getFirst(e.o,e.n);
1.803 -// }
1.804 -// else {
1.805 -// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.806 -// graph->goNext(e.o);
1.807 -// return e;
1.808 -// }
1.809 -// }
1.810 -// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1.811 -// */
1.812 -// //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
1.813 -
1.814 -// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.815 -// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.816 -
1.817 -// template< typename It > It first() const {
1.818 -// It e; getFirst(e); return e; }
1.819 -
1.820 -// template< typename It > It first(NodeIt v) const {
1.821 -// It e; getFirst(e, v); return e; }
1.822 -
1.823 -// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.824 -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.825 -
1.826 -// template<typename I> NodeIt aNode(const I& e) const {
1.827 -// return graph->aNode(e); }
1.828 -// template<typename I> NodeIt bNode(const I& e) const {
1.829 -// return graph->bNode(e); }
1.830 -
1.831 -// //template<typename I> bool valid(const I i);
1.832 -// //{ return graph->valid(i); }
1.833 -
1.834 -// //template<typename I> void setInvalid(const I &i);
1.835 -// //{ return graph->setInvalid(i); }
1.836 -
1.837 -// NodeIt addNode() { return graph->addNode(); }
1.838 -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
1.839 -// return graph->addEdge(tail, head); }
1.840 -
1.841 -// template<typename I> void erase(const I& i) { graph->erase(i); }
1.842 -
1.843 -// void clear() { graph->clear(); }
1.844 -
1.845 -// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1.846 -// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1.847 -
1.848 -// void setGraph(const Graph& _graph) { graph = &_graph; }
1.849 -// const Graph& getGraph() { return (*graph); }
1.850 -
1.851 -// //ConstResGraphWrapper() : graph(0) { }
1.852 -// ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
1.853 -// };
1.854 -
1.855 -
1.856 -
1.857 -
1.858 -
1.859 } //namespace hugo
1.860
1.861 #endif //GRAPH_WRAPPER_H