1.1 --- a/src/work/marci/experiment/graph_wrapper_1.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1348 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_GRAPH_WRAPPER_H
1.6 -#define LEMON_GRAPH_WRAPPER_H
1.7 -
1.8 -#include <invalid.h>
1.9 -
1.10 -namespace lemon {
1.11 -
1.12 - template<typename Graph>
1.13 - class TrivGraphWrapper {
1.14 - protected:
1.15 - Graph* graph;
1.16 -
1.17 - public:
1.18 - typedef Graph BaseGraph;
1.19 -
1.20 -// TrivGraphWrapper() : graph(0) { }
1.21 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.22 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.23 -// Graph& getGraph() const { return *graph; }
1.24 -
1.25 - typedef typename Graph::Node Node;
1.26 - class NodeIt : public Graph::NodeIt {
1.27 - public:
1.28 - NodeIt() { }
1.29 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.30 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.31 - NodeIt(const TrivGraphWrapper<Graph>& _G) :
1.32 - Graph::NodeIt(*(_G.graph)) { }
1.33 - };
1.34 - typedef typename Graph::Edge Edge;
1.35 - class OutEdgeIt : public Graph::OutEdgeIt {
1.36 - public:
1.37 - OutEdgeIt() { }
1.38 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.39 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.40 - OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.41 - Graph::OutEdgeIt(*(_G.graph), n) { }
1.42 - };
1.43 - class InEdgeIt : public Graph::InEdgeIt {
1.44 - public:
1.45 - InEdgeIt() { }
1.46 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.47 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.48 - InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.49 - Graph::InEdgeIt(*(_G.graph), n) { }
1.50 - };
1.51 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.52 - class EdgeIt : public Graph::EdgeIt {
1.53 - public:
1.54 - EdgeIt() { }
1.55 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.56 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.57 - EdgeIt(const TrivGraphWrapper<Graph>& _G) :
1.58 - Graph::EdgeIt(*(_G.graph)) { }
1.59 - };
1.60 -
1.61 - NodeIt& first(NodeIt& i) const {
1.62 - i=NodeIt(*this);
1.63 - return i;
1.64 - }
1.65 - EdgeIt& first(EdgeIt& i) const {
1.66 - i=EdgeIt(*this);
1.67 - return i;
1.68 - }
1.69 -// template<typename I> I& first(I& i) const {
1.70 -// i=I(*this);
1.71 -// return i;
1.72 -// }
1.73 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.74 - i=OutEdgeIt(*this, p);
1.75 - return i;
1.76 - }
1.77 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.78 - i=InEdgeIt(*this, p);
1.79 - return i;
1.80 - }
1.81 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.82 -// i=I(*this, p);
1.83 -// return i;
1.84 -// }
1.85 -
1.86 -// template<typename I> I getNext(const I& i) const {
1.87 -// return graph->getNext(i); }
1.88 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.89 -
1.90 - template< typename It > It first() const {
1.91 - It e; this->first(e); return e; }
1.92 -
1.93 - template< typename It > It first(const Node& v) const {
1.94 - It e; this->first(e, v); return e; }
1.95 -
1.96 - Node target(const Edge& e) const { return graph->target(e); }
1.97 - Node source(const Edge& e) const { return graph->source(e); }
1.98 -
1.99 - template<typename I> bool valid(const I& i) const {
1.100 - return graph->valid(i); }
1.101 -
1.102 - //template<typename I> void setInvalid(const I &i);
1.103 - //{ return graph->setInvalid(i); }
1.104 -
1.105 - int nodeNum() const { return graph->nodeNum(); }
1.106 - int edgeNum() const { return graph->edgeNum(); }
1.107 -
1.108 - template<typename I> Node aNode(const I& e) const {
1.109 - return graph->aNode(e); }
1.110 - template<typename I> Node bNode(const I& e) const {
1.111 - return graph->bNode(e); }
1.112 -
1.113 - Node addNode() const { return graph->addNode(); }
1.114 - Edge addEdge(const Node& source, const Node& target) const {
1.115 - return graph->addEdge(source, target); }
1.116 -
1.117 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.118 -
1.119 - void clear() const { graph->clear(); }
1.120 -
1.121 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.122 - public:
1.123 - NodeMap(const TrivGraphWrapper<Graph>& _G) :
1.124 - Graph::NodeMap<T>(*(_G.graph)) { }
1.125 - NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.126 - Graph::NodeMap<T>(*(_G.graph), a) { }
1.127 - };
1.128 -
1.129 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.130 - public:
1.131 - EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.132 - Graph::EdgeMap<T>(*(_G.graph)) { }
1.133 - EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.134 - Graph::EdgeMap<T>(*(_G.graph), a) { }
1.135 - };
1.136 -
1.137 - template<typename Map, typename T> class NodeMapWrapper {
1.138 - protected:
1.139 - Map* map;
1.140 - public:
1.141 - NodeMapWrapper(Map& _map) : map(&_map) { }
1.142 - void set(Node n, T a) { map->set(n, a); }
1.143 - T get(Node n) const { return map->get(n); }
1.144 - };
1.145 -
1.146 - template<typename Map, typename T> class EdgeMapWrapper {
1.147 - protected:
1.148 - Map* map;
1.149 - public:
1.150 - EdgeMapWrapper(Map& _map) : map(&_map) { }
1.151 - void set(Edge n, T a) { map->set(n, a); }
1.152 - T get(Edge n) const { return map->get(n); }
1.153 - };
1.154 - };
1.155 -
1.156 -
1.157 - template<typename Graph>
1.158 - class GraphWrapper {
1.159 - protected:
1.160 - Graph* graph;
1.161 -
1.162 - public:
1.163 - typedef Graph BaseGraph;
1.164 -
1.165 -// GraphWrapper() : graph(0) { }
1.166 - GraphWrapper(Graph& _graph) : graph(&_graph) { }
1.167 -// void setGraph(Graph& _graph) { graph=&_graph; }
1.168 -// Graph& getGraph() const { return *graph; }
1.169 -
1.170 - typedef typename Graph::Node Node;
1.171 - class NodeIt : public Graph::NodeIt {
1.172 - public:
1.173 - NodeIt() { }
1.174 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.175 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.176 - NodeIt(const GraphWrapper<Graph>& _G) :
1.177 - Graph::NodeIt(*(_G.graph)) { }
1.178 - };
1.179 - typedef typename Graph::Edge Edge;
1.180 - class OutEdgeIt : public Graph::OutEdgeIt {
1.181 - public:
1.182 - OutEdgeIt() { }
1.183 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.184 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.185 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
1.186 - Graph::OutEdgeIt(*(_G.graph), n) { }
1.187 - };
1.188 - class InEdgeIt : public Graph::InEdgeIt {
1.189 - public:
1.190 - InEdgeIt() { }
1.191 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.192 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.193 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
1.194 - Graph::InEdgeIt(*(_G.graph), n) { }
1.195 - };
1.196 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.197 - class EdgeIt : public Graph::EdgeIt {
1.198 - public:
1.199 - EdgeIt() { }
1.200 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.201 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.202 - EdgeIt(const GraphWrapper<Graph>& _G) :
1.203 - Graph::EdgeIt(*(_G.graph)) { }
1.204 - };
1.205 -
1.206 - NodeIt& first(NodeIt& i) const {
1.207 - i=NodeIt(*this);
1.208 - return i;
1.209 - }
1.210 - EdgeIt& first(EdgeIt& i) const {
1.211 - i=EdgeIt(*this);
1.212 - return i;
1.213 - }
1.214 -// template<typename I> I& first(I& i) const {
1.215 -// i=I(*this);
1.216 -// return i;
1.217 -// }
1.218 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.219 - i=OutEdgeIt(*this, p);
1.220 - return i;
1.221 - }
1.222 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.223 - i=InEdgeIt(*this, p);
1.224 - return i;
1.225 - }
1.226 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.227 -// i=I(*this, p);
1.228 -// return i;
1.229 -// }
1.230 -
1.231 -// template<typename I> I getNext(const I& i) const {
1.232 -// return gw.getNext(i); }
1.233 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.234 -
1.235 - template< typename It > It first() const {
1.236 - It e; this->first(e); return e; }
1.237 -
1.238 - template< typename It > It first(const Node& v) const {
1.239 - It e; this->first(e, v); return e; }
1.240 -
1.241 - Node target(const Edge& e) const { return graph->target(e); }
1.242 - Node source(const Edge& e) const { return graph->source(e); }
1.243 -
1.244 - template<typename I> bool valid(const I& i) const {
1.245 - return graph->valid(i); }
1.246 -
1.247 - //template<typename I> void setInvalid(const I &i);
1.248 - //{ return graph->setInvalid(i); }
1.249 -
1.250 - int nodeNum() const { return graph->nodeNum(); }
1.251 - int edgeNum() const { return graph->edgeNum(); }
1.252 -
1.253 - template<typename I> Node aNode(const I& e) const {
1.254 - return graph->aNode(e); }
1.255 - template<typename I> Node bNode(const I& e) const {
1.256 - return graph->bNode(e); }
1.257 -
1.258 - Node addNode() const { return graph->addNode(); }
1.259 - Edge addEdge(const Node& source, const Node& target) const {
1.260 - return graph->addEdge(source, target); }
1.261 -
1.262 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.263 -
1.264 - void clear() const { graph->clear(); }
1.265 -
1.266 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.267 - public:
1.268 - NodeMap(const GraphWrapper<Graph>& _G) :
1.269 - Graph::NodeMap<T>(*(_G.graph)) { }
1.270 - NodeMap(const GraphWrapper<Graph>& _G, T a) :
1.271 - Graph::NodeMap<T>(*(_G.graph), a) { }
1.272 - };
1.273 -
1.274 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.275 - public:
1.276 - EdgeMap(const GraphWrapper<Graph>& _G) :
1.277 - Graph::EdgeMap<T>(*(_G.graph)) { }
1.278 - EdgeMap(const GraphWrapper<Graph>& _G, T a) :
1.279 - Graph::EdgeMap<T>(*(_G.graph), a) { }
1.280 - };
1.281 - };
1.282 -
1.283 -
1.284 -// template<typename Graph>
1.285 -// class RevGraphWrapper
1.286 -// {
1.287 -// protected:
1.288 -// Graph* graph;
1.289 -
1.290 -// public:
1.291 -// typedef Graph BaseGraph;
1.292 -
1.293 -// typedef typename Graph::Node Node;
1.294 -// typedef typename Graph::NodeIt NodeIt;
1.295 -
1.296 -// typedef typename Graph::Edge Edge;
1.297 -// typedef typename Graph::OutEdgeIt InEdgeIt;
1.298 -// typedef typename Graph::InEdgeIt OutEdgeIt;
1.299 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.300 -// typedef typename Graph::EdgeIt EdgeIt;
1.301 -
1.302 -// //RevGraphWrapper() : graph(0) { }
1.303 -// RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.304 -
1.305 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.306 -// Graph& getGraph() const { return (*graph); }
1.307 -
1.308 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.309 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.310 -// return graph->first(i, p); }
1.311 -
1.312 -// template<typename I> I getNext(const I& i) const {
1.313 -// return graph->getNext(i); }
1.314 -// template<typename I> I& next(I &i) const { return graph->next(i); }
1.315 -
1.316 -// template< typename It > It first() const {
1.317 -// It e; first(e); return e; }
1.318 -
1.319 -// template< typename It > It first(const Node& v) const {
1.320 -// It e; first(e, v); return e; }
1.321 -
1.322 -// Node target(const Edge& e) const { return graph->source(e); }
1.323 -// Node source(const Edge& e) const { return graph->target(e); }
1.324 -
1.325 -// template<typename I> bool valid(const I& i) const
1.326 -// { return graph->valid(i); }
1.327 -
1.328 -// //template<typename I> void setInvalid(const I &i);
1.329 -// //{ return graph->setInvalid(i); }
1.330 -
1.331 -// template<typename I> Node aNode(const I& e) const {
1.332 -// return graph->aNode(e); }
1.333 -// template<typename I> Node bNode(const I& e) const {
1.334 -// return graph->bNode(e); }
1.335 -
1.336 -// Node addNode() const { return graph->addNode(); }
1.337 -// Edge addEdge(const Node& source, const Node& target) const {
1.338 -// return graph->addEdge(source, target); }
1.339 -
1.340 -// int nodeNum() const { return graph->nodeNum(); }
1.341 -// int edgeNum() const { return graph->edgeNum(); }
1.342 -
1.343 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.344 -
1.345 -// void clear() const { graph->clear(); }
1.346 -
1.347 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.348 -// public:
1.349 -// NodeMap(const RevGraphWrapper<Graph>& _G) :
1.350 -// Graph::NodeMap<T>(_G.getGraph()) { }
1.351 -// NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.352 -// Graph::NodeMap<T>(_G.getGraph(), a) { }
1.353 -// };
1.354 -
1.355 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.356 -// public:
1.357 -// EdgeMap(const RevGraphWrapper<Graph>& _G) :
1.358 -// Graph::EdgeMap<T>(_G.getGraph()) { }
1.359 -// EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.360 -// Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.361 -// };
1.362 -// };
1.363 -
1.364 -
1.365 - template<typename Graph>
1.366 - class RevGraphWrapper : public GraphWrapper<Graph> {
1.367 - public:
1.368 - typedef typename GraphWrapper<Graph>::Node Node;
1.369 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.370 - //FIXME
1.371 - //If Graph::OutEdgeIt is not defined
1.372 - //and we do not want to use RevGraphWrapper::InEdgeIt,
1.373 - //this won't work, because of typedef
1.374 - //OR
1.375 - //graphs have to define their non-existing iterators to void
1.376 - //Unfortunately all the typedefs are instantiated in templates,
1.377 - //unlike other stuff
1.378 - typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
1.379 - typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
1.380 -
1.381 -// RevGraphWrapper() : GraphWrapper<Graph>() { }
1.382 - RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.383 -
1.384 - Node target(const Edge& e) const
1.385 - { return GraphWrapper<Graph>::source(e); }
1.386 - Node source(const Edge& e) const
1.387 - { return GraphWrapper<Graph>::target(e); }
1.388 - };
1.389 -
1.390 - //Subgraph on the same node-set and partial edge-set
1.391 - template<typename Graph, typename EdgeFilterMap>
1.392 - class SubGraphWrapper : public GraphWrapper<Graph> {
1.393 - protected:
1.394 - EdgeFilterMap* filter_map;
1.395 - public:
1.396 - typedef typename GraphWrapper<Graph>::Node Node;
1.397 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.398 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.399 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.400 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1.401 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1.402 -
1.403 -// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
1.404 - SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
1.405 - GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
1.406 -
1.407 - template<typename I> I& first(I& i) const {
1.408 - graph->first(i);
1.409 - while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.410 - return i;
1.411 - }
1.412 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.413 - graph->first(i, p);
1.414 - while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.415 - return i;
1.416 - }
1.417 -
1.418 - //template<typename I> I getNext(const I& i) const {
1.419 - // return gw.getNext(i);
1.420 - //}
1.421 - template<typename I> I& next(I &i) const {
1.422 - graph->next(i);
1.423 - while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.424 - return i;
1.425 - }
1.426 -
1.427 - template< typename It > It first() const {
1.428 - It e; this->first(e); return e; }
1.429 -
1.430 - template< typename It > It first(const Node& v) const {
1.431 - It e; this->first(e, v); return e; }
1.432 - };
1.433 -
1.434 -// template<typename GraphWrapper>
1.435 -// class UndirGraphWrapper {
1.436 -// protected:
1.437 -// //Graph* graph;
1.438 -// GraphWrapper gw;
1.439 -
1.440 -// public:
1.441 -// typedef GraphWrapper BaseGraph;
1.442 -
1.443 -// typedef typename GraphWrapper::Node Node;
1.444 -// typedef typename GraphWrapper::NodeIt NodeIt;
1.445 -
1.446 -// //typedef typename Graph::Edge Edge;
1.447 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.448 -// //typedef typename Graph::InEdgeIt InEdgeIt;
1.449 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.450 -// //typedef typename Graph::EdgeIt EdgeIt;
1.451 -
1.452 -// //private:
1.453 -// typedef typename GraphWrapper::Edge GraphEdge;
1.454 -// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.455 -// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.456 -// //public:
1.457 -
1.458 -// //UndirGraphWrapper() : graph(0) { }
1.459 -// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.460 -
1.461 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.462 -// //Graph& getGraph() const { return (*graph); }
1.463 -
1.464 -// class Edge {
1.465 -// friend class UndirGraphWrapper<GraphWrapper>;
1.466 -// bool out_or_in; //true iff out
1.467 -// GraphOutEdgeIt out;
1.468 -// GraphInEdgeIt in;
1.469 -// public:
1.470 -// Edge() : out_or_in(), out(), in() { }
1.471 -// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.472 -// operator GraphEdge() const {
1.473 -// if (out_or_in) return(out); else return(in);
1.474 -// }
1.475 -// friend bool operator==(const Edge& u, const Edge& v) {
1.476 -// if (v.out_or_in)
1.477 -// return (u.out_or_in && u.out==v.out);
1.478 -// else
1.479 -// return (!u.out_or_in && u.in==v.in);
1.480 -// }
1.481 -// friend bool operator!=(const Edge& u, const Edge& v) {
1.482 -// if (v.out_or_in)
1.483 -// return (!u.out_or_in || u.out!=v.out);
1.484 -// else
1.485 -// return (u.out_or_in || u.in!=v.in);
1.486 -// }
1.487 -// };
1.488 -
1.489 -// class OutEdgeIt : public Edge {
1.490 -// friend class UndirGraphWrapper<GraphWrapper>;
1.491 -// public:
1.492 -// OutEdgeIt() : Edge() { }
1.493 -// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.494 -// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.495 -// : Edge() {
1.496 -// out_or_in=true;
1.497 -// _G.gw.first(out, n);
1.498 -// if (!(_G.gw.valid(out))) {
1.499 -// out_or_in=false;
1.500 -// _G.gw.first(in, n);
1.501 -// }
1.502 -// }
1.503 -// };
1.504 -
1.505 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.506 -// e.out_or_in=true;
1.507 -// gw.first(e.out, n);
1.508 -// if (!(gw.valid(e.out))) {
1.509 -// e.out_or_in=false;
1.510 -// gw.first(e.in, n);
1.511 -// }
1.512 -// return e;
1.513 -// }
1.514 -
1.515 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.516 -// if (e.out_or_in) {
1.517 -// Node n=gw.source(e.out);
1.518 -// gw.next(e.out);
1.519 -// if (!gw.valid(e.out)) {
1.520 -// e.out_or_in=false;
1.521 -// gw.first(e.in, n);
1.522 -// }
1.523 -// } else {
1.524 -// gw.next(e.in);
1.525 -// }
1.526 -// return e;
1.527 -// }
1.528 -
1.529 -// Node aNode(const OutEdgeIt& e) const {
1.530 -// if (e.out_or_in) return gw.source(e); else return gw.target(e); }
1.531 -// Node bNode(const OutEdgeIt& e) const {
1.532 -// if (e.out_or_in) return gw.target(e); else return gw.source(e); }
1.533 -
1.534 -// typedef OutEdgeIt InEdgeIt;
1.535 -
1.536 -// template<typename I> I& first(I& i) const { return gw.first(i); }
1.537 -// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.538 -// // return graph->first(i, p); }
1.539 -
1.540 -// template<typename I> I getNext(const I& i) const {
1.541 -// return gw.getNext(i); }
1.542 -// template<typename I> I& next(I &i) const { return gw.next(i); }
1.543 -
1.544 -// template< typename It > It first() const {
1.545 -// It e; first(e); return e; }
1.546 -
1.547 -// template< typename It > It first(const Node& v) const {
1.548 -// It e; first(e, v); return e; }
1.549 -
1.550 -// Node target(const Edge& e) const { return gw.target(e); }
1.551 -// Node source(const Edge& e) const { return gw.source(e); }
1.552 -
1.553 -// template<typename I> bool valid(const I& i) const
1.554 -// { return gw.valid(i); }
1.555 -
1.556 -// //template<typename I> void setInvalid(const I &i);
1.557 -// //{ return graph->setInvalid(i); }
1.558 -
1.559 -// int nodeNum() const { return gw.nodeNum(); }
1.560 -// int edgeNum() const { return gw.edgeNum(); }
1.561 -
1.562 -// // template<typename I> Node aNode(const I& e) const {
1.563 -// // return graph->aNode(e); }
1.564 -// // template<typename I> Node bNode(const I& e) const {
1.565 -// // return graph->bNode(e); }
1.566 -
1.567 -// Node addNode() const { return gw.addNode(); }
1.568 -// // FIXME: ez igy nem jo, mert nem
1.569 -// // Edge addEdge(const Node& source, const Node& target) const {
1.570 -// // return graph->addEdge(source, target); }
1.571 -
1.572 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.573 -
1.574 -// void clear() const { gw.clear(); }
1.575 -
1.576 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.577 -// public:
1.578 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.579 -// GraphWrapper::NodeMap<T>(_G.gw) { }
1.580 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.581 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.582 -// };
1.583 -
1.584 -// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.585 -// public:
1.586 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.587 -// GraphWrapper::EdgeMap<T>(_G.gw) { }
1.588 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.589 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.590 -// };
1.591 -// };
1.592 -
1.593 -
1.594 - template<typename Graph>
1.595 - class UndirGraphWrapper : public GraphWrapper<Graph> {
1.596 - protected:
1.597 - typedef typename Graph::Edge GraphEdge;
1.598 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.599 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.600 - public:
1.601 - typedef typename GraphWrapper<Graph>::Node Node;
1.602 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.603 -
1.604 -// UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.605 - UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.606 -
1.607 - class Edge {
1.608 - friend class UndirGraphWrapper<Graph>;
1.609 - protected:
1.610 - bool out_or_in; //true iff out
1.611 - GraphOutEdgeIt out;
1.612 - GraphInEdgeIt in;
1.613 - public:
1.614 - Edge() : out_or_in(), out(), in() { }
1.615 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.616 - operator GraphEdge() const {
1.617 - if (out_or_in) return(out); else return(in);
1.618 - }
1.619 -//FIXME
1.620 -//2 edges are equal if they "refer" to the same physical edge
1.621 -//is it good?
1.622 - friend bool operator==(const Edge& u, const Edge& v) {
1.623 - if (v.out_or_in)
1.624 - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.625 - //return (u.out_or_in && u.out==v.out);
1.626 - else
1.627 - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.628 - //return (!u.out_or_in && u.in==v.in);
1.629 - }
1.630 - friend bool operator!=(const Edge& u, const Edge& v) {
1.631 - if (v.out_or_in)
1.632 - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
1.633 - //return (!u.out_or_in || u.out!=v.out);
1.634 - else
1.635 - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
1.636 - //return (u.out_or_in || u.in!=v.in);
1.637 - }
1.638 - };
1.639 -
1.640 - class OutEdgeIt : public Edge {
1.641 - friend class UndirGraphWrapper<Graph>;
1.642 - public:
1.643 - OutEdgeIt() : Edge() { }
1.644 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.645 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
1.646 - : Edge() {
1.647 - out_or_in=true; _G.graph->first(out, n);
1.648 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
1.649 - }
1.650 - };
1.651 -
1.652 - typedef OutEdgeIt InEdgeIt;
1.653 -
1.654 - class EdgeIt : public Edge {
1.655 - friend class UndirGraphWrapper<Graph>;
1.656 - protected:
1.657 - NodeIt v;
1.658 - public:
1.659 - EdgeIt() : Edge() { }
1.660 - EdgeIt(const Invalid& i) : Edge(i) { }
1.661 - EdgeIt(const UndirGraphWrapper<Graph>& _G)
1.662 - : Edge() {
1.663 - out_or_in=true;
1.664 - //Node v;
1.665 - _G.first(v);
1.666 - if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
1.667 - while (_G.valid(v) && !_G.graph->valid(out)) {
1.668 - _G.graph->next(v);
1.669 - if (_G.valid(v)) _G.graph->first(out);
1.670 - }
1.671 - }
1.672 - };
1.673 -
1.674 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.675 - e.out_or_in=true; graph->first(e.out, n);
1.676 - if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
1.677 - return e;
1.678 - }
1.679 -
1.680 - EdgeIt& first(EdgeIt& e) const {
1.681 - e.out_or_in=true;
1.682 - //NodeIt v;
1.683 - first(e.v);
1.684 - if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
1.685 - while (valid(e.v) && !graph->valid(e.out)) {
1.686 - graph->next(e.v);
1.687 - if (valid(e.v)) graph->first(e.out, e.v);
1.688 - }
1.689 - return e;
1.690 - }
1.691 -
1.692 - template<typename I> I& first(I& i) const { graph->first(i); return i; }
1.693 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.694 - graph->first(i, p); return i; }
1.695 -
1.696 - OutEdgeIt& next(OutEdgeIt& e) const {
1.697 - if (e.out_or_in) {
1.698 - Node n=graph->source(e.out);
1.699 - graph->next(e.out);
1.700 - if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
1.701 - } else {
1.702 - graph->next(e.in);
1.703 - }
1.704 - return e;
1.705 - }
1.706 -
1.707 - EdgeIt& next(EdgeIt& e) const {
1.708 - //NodeIt v=source(e);
1.709 - graph->next(e.out);
1.710 - while (valid(e.v) && !graph->valid(e.out)) {
1.711 - next(e.v);
1.712 - if (valid(e.v)) graph->first(e.out, e.v);
1.713 - }
1.714 - return e;
1.715 - }
1.716 -
1.717 - template<typename I> I& next(I &i) const { return graph->next(i); }
1.718 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.719 -
1.720 - template< typename It > It first() const {
1.721 - It e; this->first(e); return e; }
1.722 -
1.723 - template< typename It > It first(const Node& v) const {
1.724 - It e; this->first(e, v); return e; }
1.725 -
1.726 -// Node target(const Edge& e) const { return gw.target(e); }
1.727 -// Node source(const Edge& e) const { return gw.source(e); }
1.728 -
1.729 -// template<typename I> bool valid(const I& i) const
1.730 -// { return gw.valid(i); }
1.731 -
1.732 -// int nodeNum() const { return gw.nodeNum(); }
1.733 -// int edgeNum() const { return gw.edgeNum(); }
1.734 -
1.735 -// template<typename I> Node aNode(const I& e) const {
1.736 -// return graph->aNode(e); }
1.737 -// template<typename I> Node bNode(const I& e) const {
1.738 -// return graph->bNode(e); }
1.739 -
1.740 - Node aNode(const OutEdgeIt& e) const {
1.741 - if (e.out_or_in) return graph->source(e); else return graph->target(e); }
1.742 - Node bNode(const OutEdgeIt& e) const {
1.743 - if (e.out_or_in) return graph->target(e); else return graph->source(e); }
1.744 -
1.745 -// Node addNode() const { return gw.addNode(); }
1.746 -
1.747 -// FIXME: ez igy nem jo, mert nem
1.748 -// Edge addEdge(const Node& source, const Node& target) const {
1.749 -// return graph->addEdge(source, target); }
1.750 -
1.751 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.752 -
1.753 -// void clear() const { gw.clear(); }
1.754 -
1.755 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.756 -// public:
1.757 -// NodeMap(const UndirGraphWrapper<Graph>& _G) :
1.758 -// Graph::NodeMap<T>(_G.gw) { }
1.759 -// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.760 -// Graph::NodeMap<T>(_G.gw, a) { }
1.761 -// };
1.762 -
1.763 -// template<typename T> class EdgeMap :
1.764 -// public GraphWrapper<Graph>::EdgeMap<T> {
1.765 -// public:
1.766 -// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
1.767 -// GraphWrapper<Graph>::EdgeMap<T>(_G.gw) { }
1.768 -// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.769 -// Graph::EdgeMap<T>(_G.gw, a) { }
1.770 -// };
1.771 - };
1.772 -
1.773 -
1.774 -
1.775 -
1.776 -
1.777 -// template<typename Graph>
1.778 -// class SymGraphWrapper
1.779 -// {
1.780 -// Graph* graph;
1.781 -
1.782 -// public:
1.783 -// typedef Graph BaseGraph;
1.784 -
1.785 -// typedef typename Graph::Node Node;
1.786 -// typedef typename Graph::Edge Edge;
1.787 -
1.788 -// typedef typename Graph::NodeIt NodeIt;
1.789 -
1.790 -// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.791 -// //iranyitatlant, ami van
1.792 -// //mert csak 1 dolgot lehet be typedef-elni
1.793 -// typedef typename Graph::OutEdgeIt SymEdgeIt;
1.794 -// //typedef typename Graph::InEdgeIt SymEdgeIt;
1.795 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.796 -// typedef typename Graph::EdgeIt EdgeIt;
1.797 -
1.798 -// int nodeNum() const { return graph->nodeNum(); }
1.799 -// int edgeNum() const { return graph->edgeNum(); }
1.800 -
1.801 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.802 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.803 -// return graph->first(i, p); }
1.804 -// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.805 -// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.806 -
1.807 -// template< typename It > It first() const {
1.808 -// It e; first(e); return e; }
1.809 -
1.810 -// template< typename It > It first(Node v) const {
1.811 -// It e; first(e, v); return e; }
1.812 -
1.813 -// Node target(const Edge& e) const { return graph->target(e); }
1.814 -// Node source(const Edge& e) const { return graph->source(e); }
1.815 -
1.816 -// template<typename I> Node aNode(const I& e) const {
1.817 -// return graph->aNode(e); }
1.818 -// template<typename I> Node bNode(const I& e) const {
1.819 -// return graph->bNode(e); }
1.820 -
1.821 -// //template<typename I> bool valid(const I i);
1.822 -// //{ return graph->valid(i); }
1.823 -
1.824 -// //template<typename I> void setInvalid(const I &i);
1.825 -// //{ return graph->setInvalid(i); }
1.826 -
1.827 -// Node addNode() { return graph->addNode(); }
1.828 -// Edge addEdge(const Node& source, const Node& target) {
1.829 -// return graph->addEdge(source, target); }
1.830 -
1.831 -// template<typename I> void erase(const I& i) { graph->erase(i); }
1.832 -
1.833 -// void clear() { graph->clear(); }
1.834 -
1.835 -// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.836 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.837 -
1.838 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.839 -// Graph& getGraph() { return (*graph); }
1.840 -
1.841 -// //SymGraphWrapper() : graph(0) { }
1.842 -// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.843 -// };
1.844 -
1.845 -
1.846 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.847 - class ResGraphWrapper : public GraphWrapper<Graph>{
1.848 - public:
1.849 - typedef typename GraphWrapper<Graph>::Node Node;
1.850 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.851 - protected:
1.852 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.853 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.854 - FlowMap* flow;
1.855 - const CapacityMap* capacity;
1.856 - public:
1.857 -
1.858 - ResGraphWrapper(Graph& _graph, FlowMap& _flow,
1.859 - const CapacityMap& _capacity) :
1.860 - GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
1.861 -
1.862 - class Edge;
1.863 - class OutEdgeIt;
1.864 - friend class Edge;
1.865 - friend class OutEdgeIt;
1.866 -
1.867 - class Edge {
1.868 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.869 - protected:
1.870 - bool out_or_in; //true, iff out
1.871 - OldOutEdgeIt out;
1.872 - OldInEdgeIt in;
1.873 - public:
1.874 - Edge() : out_or_in(true) { }
1.875 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.876 -// bool valid() const {
1.877 -// return out_or_in && out.valid() || in.valid(); }
1.878 - friend bool operator==(const Edge& u, const Edge& v) {
1.879 - if (v.out_or_in)
1.880 - return (u.out_or_in && u.out==v.out);
1.881 - else
1.882 - return (!u.out_or_in && u.in==v.in);
1.883 - }
1.884 - friend bool operator!=(const Edge& u, const Edge& v) {
1.885 - if (v.out_or_in)
1.886 - return (!u.out_or_in || u.out!=v.out);
1.887 - else
1.888 - return (u.out_or_in || u.in!=v.in);
1.889 - }
1.890 - };
1.891 -
1.892 -
1.893 - class OutEdgeIt : public Edge {
1.894 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.895 - public:
1.896 - OutEdgeIt() { }
1.897 - //FIXME
1.898 - OutEdgeIt(const Edge& e) : Edge(e) { }
1.899 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.900 - protected:
1.901 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.902 - resG.graph->first(out, v);
1.903 - while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.904 - if (!resG.graph->valid(out)) {
1.905 - out_or_in=0;
1.906 - resG.graph->first(in, v);
1.907 - while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.908 - }
1.909 - }
1.910 -// public:
1.911 -// OutEdgeIt& operator++() {
1.912 -// if (out_or_in) {
1.913 -// Node v=/*resG->*/G->aNode(out);
1.914 -// ++out;
1.915 -// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.916 -// if (!out.valid()) {
1.917 -// out_or_in=0;
1.918 -// G->first(in, v);
1.919 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.920 -// }
1.921 -// } else {
1.922 -// ++in;
1.923 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.924 -// }
1.925 -// return *this;
1.926 -// }
1.927 - };
1.928 -
1.929 - //FIXME This is just for having InEdgeIt
1.930 - typedef void InEdgeIt;
1.931 -
1.932 - class EdgeIt : public Edge {
1.933 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.934 - NodeIt v;
1.935 - public:
1.936 - EdgeIt() { }
1.937 - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.938 - EdgeIt(const Invalid& i) : Edge(i) { }
1.939 - EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.940 - resG.graph->first(v);
1.941 - if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1.942 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.943 - while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1.944 - resG.graph->next(v);
1.945 - if (resG.graph->valid(v)) resG.graph->first(out, v);
1.946 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.947 - }
1.948 - if (!resG.graph->valid(out)) {
1.949 - out_or_in=0;
1.950 - resG.graph->first(v);
1.951 - if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1.952 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.953 - while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1.954 - resG.graph->next(v);
1.955 - if (resG.graph->valid(v)) resG.graph->first(in, v);
1.956 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.957 - }
1.958 - }
1.959 - }
1.960 -// EdgeIt& operator++() {
1.961 -// if (out_or_in) {
1.962 -// ++out;
1.963 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.964 -// while (v.valid() && !out.valid()) {
1.965 -// ++v;
1.966 -// if (v.valid()) G->first(out, v);
1.967 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.968 -// }
1.969 -// if (!out.valid()) {
1.970 -// out_or_in=0;
1.971 -// G->first(v);
1.972 -// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1.973 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.974 -// while (v.valid() && !in.valid()) {
1.975 -// ++v;
1.976 -// if (v.valid()) G->first(in, v);
1.977 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.978 -// }
1.979 -// }
1.980 -// } else {
1.981 -// ++in;
1.982 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.983 -// while (v.valid() && !in.valid()) {
1.984 -// ++v;
1.985 -// if (v.valid()) G->first(in, v);
1.986 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.987 -// }
1.988 -// }
1.989 -// return *this;
1.990 -// }
1.991 - };
1.992 -
1.993 - NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
1.994 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.995 - e=OutEdgeIt(*this, v);
1.996 - return e;
1.997 - }
1.998 - EdgeIt& first(EdgeIt& e) const {
1.999 - e=EdgeIt(*this);
1.1000 - return e;
1.1001 - }
1.1002 -
1.1003 - NodeIt& next(NodeIt& n) const { return graph->next(n); }
1.1004 -
1.1005 - OutEdgeIt& next(OutEdgeIt& e) const {
1.1006 - if (e.out_or_in) {
1.1007 - Node v=graph->aNode(e.out);
1.1008 - graph->next(e.out);
1.1009 - while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1010 - if (!graph->valid(e.out)) {
1.1011 - e.out_or_in=0;
1.1012 - graph->first(e.in, v);
1.1013 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1014 - }
1.1015 - } else {
1.1016 - graph->next(e.in);
1.1017 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1018 - }
1.1019 - return e;
1.1020 - }
1.1021 -
1.1022 - EdgeIt& next(EdgeIt& e) const {
1.1023 - if (e.out_or_in) {
1.1024 - graph->next(e.out);
1.1025 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1026 - while (graph->valid(e.v) && !graph->valid(e.out)) {
1.1027 - graph->next(e.v);
1.1028 - if (graph->valid(e.v)) graph->first(e.out, e.v);
1.1029 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1030 - }
1.1031 - if (!graph->valid(e.out)) {
1.1032 - e.out_or_in=0;
1.1033 - graph->first(e.v);
1.1034 - if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1.1035 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1036 - while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1037 - graph->next(e.v);
1.1038 - if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1039 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1040 - }
1.1041 - }
1.1042 - } else {
1.1043 - graph->next(e.in);
1.1044 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1045 - while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1046 - graph->next(e.v);
1.1047 - if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1048 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1049 - }
1.1050 - }
1.1051 - return e;
1.1052 - }
1.1053 -
1.1054 -
1.1055 - template< typename It >
1.1056 - It first() const {
1.1057 - It e;
1.1058 - first(e);
1.1059 - return e;
1.1060 - }
1.1061 -
1.1062 - template< typename It >
1.1063 - It first(Node v) const {
1.1064 - It e;
1.1065 - first(e, v);
1.1066 - return e;
1.1067 - }
1.1068 -
1.1069 - Node source(Edge e) const {
1.1070 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1071 - Node target(Edge e) const {
1.1072 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1073 -
1.1074 - Node aNode(OutEdgeIt e) const {
1.1075 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1076 - Node bNode(OutEdgeIt e) const {
1.1077 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1078 -
1.1079 - int nodeNum() const { return graph->nodeNum(); }
1.1080 - //FIXME
1.1081 - //int edgeNum() const { return graph->edgeNum(); }
1.1082 -
1.1083 -
1.1084 - int id(Node v) const { return graph->id(v); }
1.1085 -
1.1086 - bool valid(Node n) const { return graph->valid(n); }
1.1087 - bool valid(Edge e) const {
1.1088 - return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1.1089 -
1.1090 - void augment(const Edge& e, Number a) const {
1.1091 - if (e.out_or_in)
1.1092 - flow->set(e.out, flow->get(e.out)+a);
1.1093 - else
1.1094 - flow->set(e.in, flow->get(e.in)-a);
1.1095 - }
1.1096 -
1.1097 - Number resCap(const Edge& e) const {
1.1098 - if (e.out_or_in)
1.1099 - return (capacity->get(e.out)-flow->get(e.out));
1.1100 - else
1.1101 - return (flow->get(e.in));
1.1102 - }
1.1103 -
1.1104 - Number resCap(OldOutEdgeIt out) const {
1.1105 - return (capacity->get(out)-flow->get(out));
1.1106 - }
1.1107 -
1.1108 - Number resCap(OldInEdgeIt in) const {
1.1109 - return (flow->get(in));
1.1110 - }
1.1111 -
1.1112 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.1113 -// public:
1.1114 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1.1115 -// : Graph::NodeMap<T>(_G.gw) { }
1.1116 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1.1117 -// T a) : Graph::NodeMap<T>(_G.gw, a) { }
1.1118 -// };
1.1119 -
1.1120 -// template <typename T>
1.1121 -// class NodeMap {
1.1122 -// typename Graph::NodeMap<T> node_map;
1.1123 -// public:
1.1124 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1.1125 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1.1126 -// void set(Node nit, T a) { node_map.set(nit, a); }
1.1127 -// T get(Node nit) const { return node_map.get(nit); }
1.1128 -// };
1.1129 -
1.1130 - template <typename T>
1.1131 - class EdgeMap {
1.1132 - typename Graph::EdgeMap<T> forward_map, backward_map;
1.1133 - public:
1.1134 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.1135 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.1136 - void set(Edge e, T a) {
1.1137 - if (e.out_or_in)
1.1138 - forward_map.set(e.out, a);
1.1139 - else
1.1140 - backward_map.set(e.in, a);
1.1141 - }
1.1142 - T get(Edge e) {
1.1143 - if (e.out_or_in)
1.1144 - return forward_map.get(e.out);
1.1145 - else
1.1146 - return backward_map.get(e.in);
1.1147 - }
1.1148 - };
1.1149 - };
1.1150 -
1.1151 - //ErasingFirstGraphWrapper for blocking flows
1.1152 - template<typename Graph, typename FirstOutEdgesMap>
1.1153 - class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.1154 - protected:
1.1155 - FirstOutEdgesMap* first_out_edges;
1.1156 - public:
1.1157 - typedef typename GraphWrapper<Graph>::Node Node;
1.1158 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.1159 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.1160 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.1161 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1.1162 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1.1163 -
1.1164 - ErasingFirstGraphWrapper(Graph& _graph,
1.1165 - FirstOutEdgesMap& _first_out_edges) :
1.1166 - GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.1167 -
1.1168 - template<typename I> I& first(I& i) const {
1.1169 - graph->first(i);
1.1170 - return i;
1.1171 - }
1.1172 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1173 - e=first_out_edges->get(n);
1.1174 - return e;
1.1175 - }
1.1176 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.1177 - graph->first(i, p);
1.1178 - return i;
1.1179 - }
1.1180 -
1.1181 - //template<typename I> I getNext(const I& i) const {
1.1182 - // return gw.getNext(i);
1.1183 - //}
1.1184 - template<typename I> I& next(I &i) const {
1.1185 - graph->next(i);
1.1186 - return i;
1.1187 - }
1.1188 -
1.1189 - template< typename It > It first() const {
1.1190 - It e; this->first(e); return e; }
1.1191 -
1.1192 - template< typename It > It first(const Node& v) const {
1.1193 - It e; this->first(e, v); return e; }
1.1194 -
1.1195 - void erase(const OutEdgeIt& e) const {
1.1196 - OutEdgeIt f=e;
1.1197 - this->next(f);
1.1198 - first_out_edges->set(this->source(e), f);
1.1199 - }
1.1200 - };
1.1201 -
1.1202 -// // FIXME: comparison should be made better!!!
1.1203 -// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.1204 -// class ResGraphWrapper
1.1205 -// {
1.1206 -// Graph* graph;
1.1207 -
1.1208 -// public:
1.1209 -// typedef Graph BaseGraph;
1.1210 -
1.1211 -// typedef typename Graph::Node Node;
1.1212 -// typedef typename Graph::Edge Edge;
1.1213 -
1.1214 -// typedef typename Graph::NodeIt NodeIt;
1.1215 -
1.1216 -// class OutEdgeIt {
1.1217 -// public:
1.1218 -// //Graph::Node n;
1.1219 -// bool out_or_in;
1.1220 -// typename Graph::OutEdgeIt o;
1.1221 -// typename Graph::InEdgeIt i;
1.1222 -// };
1.1223 -// class InEdgeIt {
1.1224 -// public:
1.1225 -// //Graph::Node n;
1.1226 -// bool out_or_in;
1.1227 -// typename Graph::OutEdgeIt o;
1.1228 -// typename Graph::InEdgeIt i;
1.1229 -// };
1.1230 -// typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1231 -// typedef typename Graph::EdgeIt EdgeIt;
1.1232 -
1.1233 -// int nodeNum() const { return gw.nodeNum(); }
1.1234 -// int edgeNum() const { return gw.edgeNum(); }
1.1235 -
1.1236 -// Node& first(Node& n) const { return gw.first(n); }
1.1237 -
1.1238 -// // Edge and SymEdge is missing!!!!
1.1239 -// // Edge <-> In/OutEdgeIt conversion is missing!!!!
1.1240 -
1.1241 -// //FIXME
1.1242 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1.1243 -// {
1.1244 -// e.n=n;
1.1245 -// gw.first(e.o,n);
1.1246 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1247 -// gw.goNext(e.o);
1.1248 -// if(!gw.valid(e.o)) {
1.1249 -// gw.first(e.i,n);
1.1250 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1251 -// gw.goNext(e.i);
1.1252 -// }
1.1253 -// return e;
1.1254 -// }
1.1255 -// /*
1.1256 -// OutEdgeIt &goNext(OutEdgeIt &e)
1.1257 -// {
1.1258 -// if(gw.valid(e.o)) {
1.1259 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1260 -// gw.goNext(e.o);
1.1261 -// if(gw.valid(e.o)) return e;
1.1262 -// else gw.first(e.i,e.n);
1.1263 -// }
1.1264 -// else {
1.1265 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1266 -// gw.goNext(e.i);
1.1267 -// return e;
1.1268 -// }
1.1269 -// }
1.1270 -// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1.1271 -// */
1.1272 -// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1.1273 -
1.1274 -// //FIXME
1.1275 -// InEdgeIt& first(InEdgeIt& e, const Node& n) const
1.1276 -// {
1.1277 -// e.n=n;
1.1278 -// gw.first(e.i,n);
1.1279 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1280 -// gw.goNext(e.i);
1.1281 -// if(!gw.valid(e.i)) {
1.1282 -// gw.first(e.o,n);
1.1283 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1284 -// gw.goNext(e.o);
1.1285 -// }
1.1286 -// return e;
1.1287 -// }
1.1288 -// /*
1.1289 -// InEdgeIt &goNext(InEdgeIt &e)
1.1290 -// {
1.1291 -// if(gw.valid(e.i)) {
1.1292 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1293 -// gw.goNext(e.i);
1.1294 -// if(gw.valid(e.i)) return e;
1.1295 -// else gw.first(e.o,e.n);
1.1296 -// }
1.1297 -// else {
1.1298 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1299 -// gw.goNext(e.o);
1.1300 -// return e;
1.1301 -// }
1.1302 -// }
1.1303 -// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1.1304 -// */
1.1305 -// //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1.1306 -
1.1307 -// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1.1308 -// //template<typename I> I next(const I i); { return gw.goNext(i); }
1.1309 -
1.1310 -// template< typename It > It first() const {
1.1311 -// It e; first(e); return e; }
1.1312 -
1.1313 -// template< typename It > It first(Node v) const {
1.1314 -// It e; first(e, v); return e; }
1.1315 -
1.1316 -// Node target(const Edge& e) const { return gw.target(e); }
1.1317 -// Node source(const Edge& e) const { return gw.source(e); }
1.1318 -
1.1319 -// template<typename I> Node aNode(const I& e) const {
1.1320 -// return gw.aNode(e); }
1.1321 -// template<typename I> Node bNode(const I& e) const {
1.1322 -// return gw.bNode(e); }
1.1323 -
1.1324 -// //template<typename I> bool valid(const I i);
1.1325 -// //{ return gw.valid(i); }
1.1326 -
1.1327 -// //template<typename I> void setInvalid(const I &i);
1.1328 -// //{ return gw.setInvalid(i); }
1.1329 -
1.1330 -// Node addNode() { return gw.addNode(); }
1.1331 -// Edge addEdge(const Node& source, const Node& target) {
1.1332 -// return gw.addEdge(source, target); }
1.1333 -
1.1334 -// template<typename I> void erase(const I& i) { gw.erase(i); }
1.1335 -
1.1336 -// void clear() { gw.clear(); }
1.1337 -
1.1338 -// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1.1339 -// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1.1340 -
1.1341 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.1342 -// Graph& getGraph() { return (*graph); }
1.1343 -
1.1344 -// //ResGraphWrapper() : graph(0) { }
1.1345 -// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1346 -// };
1.1347 -
1.1348 -} //namespace lemon
1.1349 -
1.1350 -#endif //LEMON_GRAPH_WRAPPER_H
1.1351 -