1.1 --- a/src/work/marci/experiment/graph_wrapper.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1707 +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 - typedef typename Graph::Node Node;
1.21 - class NodeIt : public Graph::NodeIt {
1.22 - public:
1.23 - NodeIt() { }
1.24 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.25 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.26 - NodeIt(const TrivGraphWrapper<Graph>& _G) :
1.27 - Graph::NodeIt(*(_G.graph)) { }
1.28 - };
1.29 - typedef typename Graph::Edge Edge;
1.30 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.31 - class OutEdgeIt : public Graph::OutEdgeIt {
1.32 - public:
1.33 - OutEdgeIt() { }
1.34 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.35 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.36 - OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.37 - Graph::OutEdgeIt(*(_G.graph), n) { }
1.38 - };
1.39 - //typedef typename Graph::InEdgeIt InEdgeIt;
1.40 - class InEdgeIt : public Graph::InEdgeIt {
1.41 - public:
1.42 - InEdgeIt() { }
1.43 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.44 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.45 - InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.46 - Graph::InEdgeIt(*(_G.graph), n) { }
1.47 - };
1.48 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.49 - //typedef typename Graph::EdgeIt EdgeIt;
1.50 - class EdgeIt : public Graph::EdgeIt {
1.51 - public:
1.52 - EdgeIt() { }
1.53 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.54 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.55 - EdgeIt(const TrivGraphWrapper<Graph>& _G) :
1.56 - Graph::EdgeIt(*(_G.graph)) { }
1.57 - };
1.58 -
1.59 - //TrivGraphWrapper() : graph(0) { }
1.60 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.61 -
1.62 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.63 -// Graph& getGraph() const { return (*graph); }
1.64 -
1.65 - NodeIt& first(NodeIt& i) const {
1.66 - i=NodeIt(*this);
1.67 - return i;
1.68 - }
1.69 - EdgeIt& first(EdgeIt& i) const {
1.70 - i=EdgeIt(*this);
1.71 - return i;
1.72 - }
1.73 -// template<typename I> I& first(I& i) const {
1.74 -// //return graph->first(i);
1.75 -// i=I(*this);
1.76 -// return i;
1.77 -// }
1.78 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.79 - i=OutEdgeIt(*this, p);
1.80 - return i;
1.81 - }
1.82 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.83 - i=InEdgeIt(*this, p);
1.84 - return i;
1.85 - }
1.86 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.87 -// //return graph->first(i, p);
1.88 -// i=I(*this, p);
1.89 -// return i;
1.90 -// }
1.91 -
1.92 -// template<typename I> I getNext(const I& i) const {
1.93 -// return graph->getNext(i); }
1.94 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.95 -
1.96 - template< typename It > It first() const {
1.97 - It e; first(e); return e; }
1.98 -
1.99 - template< typename It > It first(const Node& v) const {
1.100 - It e; first(e, v); return e; }
1.101 -
1.102 - Node target(const Edge& e) const { return graph->target(e); }
1.103 - Node source(const Edge& e) const { return graph->source(e); }
1.104 -
1.105 - template<typename I> bool valid(const I& i) const
1.106 - { return graph->valid(i); }
1.107 -
1.108 - //template<typename I> void setInvalid(const I &i);
1.109 - //{ return graph->setInvalid(i); }
1.110 -
1.111 - int nodeNum() const { return graph->nodeNum(); }
1.112 - int edgeNum() const { return graph->edgeNum(); }
1.113 -
1.114 - template<typename I> Node aNode(const I& e) const {
1.115 - return graph->aNode(e); }
1.116 - template<typename I> Node bNode(const I& e) const {
1.117 - return graph->bNode(e); }
1.118 -
1.119 - Node addNode() const { return graph->addNode(); }
1.120 - Edge addEdge(const Node& source, const Node& target) const {
1.121 - return graph->addEdge(source, target); }
1.122 -
1.123 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.124 -
1.125 - void clear() const { graph->clear(); }
1.126 -
1.127 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.128 - public:
1.129 - NodeMap(const TrivGraphWrapper<Graph>& _G) :
1.130 - Graph::NodeMap<T>(*(_G.graph)) { }
1.131 - NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.132 - Graph::NodeMap<T>(*(_G.graph), a) { }
1.133 - };
1.134 -
1.135 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.136 - public:
1.137 - EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.138 - Graph::EdgeMap<T>(*(_G.graph)) { }
1.139 - EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.140 - Graph::EdgeMap<T>(*(_G.graph), a) { }
1.141 - };
1.142 -
1.143 - template<typename Map, typename T> class NodeMapWrapper {
1.144 - protected:
1.145 - Map* map;
1.146 - public:
1.147 - NodeMapWrapper(Map& _map) : map(&_map) { }
1.148 - //template<typename T>
1.149 - void set(Node n, T a) { map->set(n, a); }
1.150 - //template<typename T>
1.151 - T get(Node n) const { return map->get(n); }
1.152 - };
1.153 -
1.154 - template<typename Map, typename T> class EdgeMapWrapper {
1.155 - protected:
1.156 - Map* map;
1.157 - public:
1.158 - EdgeMapWrapper(Map& _map) : map(&_map) { }
1.159 - //template<typename T>
1.160 - void set(Edge n, T a) { map->set(n, a); }
1.161 - //template<typename T>
1.162 - T get(Edge n) const { return map->get(n); }
1.163 - };
1.164 - };
1.165 -
1.166 - template<typename GraphWrapper>
1.167 - class GraphWrapper {
1.168 - protected:
1.169 - GraphWrapper gw;
1.170 -
1.171 - public:
1.172 - //typedef typename GraphWrapper::BaseGraph BaseGraph;
1.173 -
1.174 -// typedef typename GraphWrapper::Node Node;
1.175 -// typedef typename GraphWrapper::NodeIt NodeIt;
1.176 -
1.177 -// typedef typename GraphWrapper::Edge Edge;
1.178 -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.179 -// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.180 -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
1.181 -// typedef typename GraphWrapper::EdgeIt EdgeIt;
1.182 -
1.183 - typedef typename GraphWrapper::Node Node;
1.184 - class NodeIt : public GraphWrapper::NodeIt {
1.185 - public:
1.186 - NodeIt() { }
1.187 - NodeIt(const typename GraphWrapper::NodeIt& n) :
1.188 - GraphWrapper::NodeIt(n) { }
1.189 - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
1.190 - NodeIt(const GraphWrapper<GraphWrapper>& _G) :
1.191 - GraphWrapper::NodeIt(_G.gw) { }
1.192 - };
1.193 - typedef typename GraphWrapper::Edge Edge;
1.194 - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.195 - class OutEdgeIt : public GraphWrapper::OutEdgeIt {
1.196 - public:
1.197 - OutEdgeIt() { }
1.198 - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
1.199 - GraphWrapper::OutEdgeIt(e) { }
1.200 - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
1.201 - OutEdgeIt(const GraphWrapper<GraphWrapper>& _G, const Node& n) :
1.202 - GraphWrapper::OutEdgeIt(_G.gw, n) { }
1.203 - };
1.204 - //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.205 - class InEdgeIt : public GraphWrapper::InEdgeIt {
1.206 - public:
1.207 - InEdgeIt() { }
1.208 - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
1.209 - GraphWrapper::InEdgeIt(e) { }
1.210 - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
1.211 - InEdgeIt(const GraphWrapper<GraphWrapper>& _G, const Node& n) :
1.212 - GraphWrapper::InEdgeIt(_G.gw, n) { }
1.213 - };
1.214 - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
1.215 - //typedef typename GraphWrapper::EdgeIt EdgeIt;
1.216 - class EdgeIt : public GraphWrapper::EdgeIt {
1.217 - public:
1.218 - EdgeIt() { }
1.219 - EdgeIt(const typename GraphWrapper::EdgeIt& e) :
1.220 - GraphWrapper::EdgeIt(e) { }
1.221 - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
1.222 - EdgeIt(const GraphWrapper<GraphWrapper>& _G) :
1.223 - GraphWrapper::EdgeIt(_G.gw) { }
1.224 - };
1.225 -
1.226 -
1.227 - //GraphWrapper() : gw() { }
1.228 - GraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.229 -
1.230 - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
1.231 - //BaseGraph& getGraph() const { return gw.getGraph(); }
1.232 -
1.233 - template<typename I> I& first(I& i) const {
1.234 - i=I(*this);
1.235 - return i;
1.236 - }
1.237 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.238 - i=I(*this, p);
1.239 - return i;
1.240 - }
1.241 -
1.242 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.243 - template<typename I> I& next(I &i) const { gw.next(i); return i; }
1.244 -
1.245 - template< typename It > It first() const {
1.246 - It e; this->first(e); return e; }
1.247 -
1.248 - template< typename It > It first(const Node& v) const {
1.249 - It e; this->first(e, v); return e; }
1.250 -
1.251 - Node target(const Edge& e) const { return gw.target(e); }
1.252 - Node source(const Edge& e) const { return gw.source(e); }
1.253 -
1.254 - template<typename I> bool valid(const I& i) const { return gw.valid(i); }
1.255 -
1.256 - //template<typename I> void setInvalid(const I &i);
1.257 - //{ return graph->setInvalid(i); }
1.258 -
1.259 - int nodeNum() const { return gw.nodeNum(); }
1.260 - int edgeNum() const { return gw.edgeNum(); }
1.261 -
1.262 - template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
1.263 - template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
1.264 -
1.265 - Node addNode() const { return gw.addNode(); }
1.266 - Edge addEdge(const Node& source, const Node& target) const {
1.267 - return gw.addEdge(source, target); }
1.268 -
1.269 - template<typename I> void erase(const I& i) const { gw.erase(i); }
1.270 -
1.271 - void clear() const { gw.clear(); }
1.272 -
1.273 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.274 - public:
1.275 - NodeMap(const GraphWrapper<GraphWrapper>& _G) :
1.276 - GraphWrapper::NodeMap<T>(_G.gw) { }
1.277 - NodeMap(const GraphWrapper<GraphWrapper>& _G, T a) :
1.278 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.279 - };
1.280 -
1.281 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.282 - public:
1.283 - EdgeMap(const GraphWrapper<GraphWrapper>& _G) :
1.284 - GraphWrapper::EdgeMap<T>(_G.gw) { }
1.285 - EdgeMap(const GraphWrapper<GraphWrapper>& _G, T a) :
1.286 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.287 - };
1.288 - };
1.289 -
1.290 -// template<typename Graph>
1.291 -// class RevGraphWrapper
1.292 -// {
1.293 -// protected:
1.294 -// Graph* graph;
1.295 -
1.296 -// public:
1.297 -// typedef Graph BaseGraph;
1.298 -
1.299 -// typedef typename Graph::Node Node;
1.300 -// typedef typename Graph::NodeIt NodeIt;
1.301 -
1.302 -// typedef typename Graph::Edge Edge;
1.303 -// typedef typename Graph::OutEdgeIt InEdgeIt;
1.304 -// typedef typename Graph::InEdgeIt OutEdgeIt;
1.305 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.306 -// typedef typename Graph::EdgeIt EdgeIt;
1.307 -
1.308 -// //RevGraphWrapper() : graph(0) { }
1.309 -// RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.310 -
1.311 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.312 -// Graph& getGraph() const { return (*graph); }
1.313 -
1.314 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.315 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.316 -// return graph->first(i, p); }
1.317 -
1.318 -// template<typename I> I getNext(const I& i) const {
1.319 -// return graph->getNext(i); }
1.320 -// template<typename I> I& next(I &i) const { return graph->next(i); }
1.321 -
1.322 -// template< typename It > It first() const {
1.323 -// It e; first(e); return e; }
1.324 -
1.325 -// template< typename It > It first(const Node& v) const {
1.326 -// It e; first(e, v); return e; }
1.327 -
1.328 -// Node target(const Edge& e) const { return graph->source(e); }
1.329 -// Node source(const Edge& e) const { return graph->target(e); }
1.330 -
1.331 -// template<typename I> bool valid(const I& i) const
1.332 -// { return graph->valid(i); }
1.333 -
1.334 -// //template<typename I> void setInvalid(const I &i);
1.335 -// //{ return graph->setInvalid(i); }
1.336 -
1.337 -// template<typename I> Node aNode(const I& e) const {
1.338 -// return graph->aNode(e); }
1.339 -// template<typename I> Node bNode(const I& e) const {
1.340 -// return graph->bNode(e); }
1.341 -
1.342 -// Node addNode() const { return graph->addNode(); }
1.343 -// Edge addEdge(const Node& source, const Node& target) const {
1.344 -// return graph->addEdge(source, target); }
1.345 -
1.346 -// int nodeNum() const { return graph->nodeNum(); }
1.347 -// int edgeNum() const { return graph->edgeNum(); }
1.348 -
1.349 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.350 -
1.351 -// void clear() const { graph->clear(); }
1.352 -
1.353 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.354 -// public:
1.355 -// NodeMap(const RevGraphWrapper<Graph>& _G) :
1.356 -// Graph::NodeMap<T>(_G.getGraph()) { }
1.357 -// NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.358 -// Graph::NodeMap<T>(_G.getGraph(), a) { }
1.359 -// };
1.360 -
1.361 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.362 -// public:
1.363 -// EdgeMap(const RevGraphWrapper<Graph>& _G) :
1.364 -// Graph::EdgeMap<T>(_G.getGraph()) { }
1.365 -// EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.366 -// Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.367 -// };
1.368 -// };
1.369 -
1.370 -// template<typename /*Graph*/GraphWrapper
1.371 -// /*=typename GraphWrapper< TrivGraphWrapper<Graph>*/ >
1.372 -// class RevGraphWrapper :
1.373 -// public GraphWrapper/*GraphWrapper< TrivGraphWrapper<Graph> >*/ {
1.374 -// protected:
1.375 -// //Graph* graph;
1.376 -
1.377 -// public:
1.378 -// //typedef Graph BaseGraph;
1.379 -
1.380 -// //typedef typename Graph::Node Node;
1.381 -// //typedef typename Graph::NodeIt NodeIt;
1.382 -
1.383 -// //typedef typename Graph::Edge Edge;
1.384 -// typedef typename GraphWrapper/*typename GraphWrapper< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
1.385 -// typedef typename GraphWrapper/*typename GraphWrapper< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
1.386 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.387 -// //typedef typename Graph::EdgeIt EdgeIt;
1.388 -
1.389 -// //RevGraphWrapper() : graph(0) { }
1.390 -// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapper< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
1.391 -
1.392 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.393 -// //Graph& getGraph() const { return (*graph); }
1.394 -
1.395 -// //template<typename I> I& first(I& i) const { return graph->first(i); }
1.396 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
1.397 -// // return graph->first(i, p); }
1.398 -
1.399 -// //template<typename I> I getNext(const I& i) const {
1.400 -// // return graph->getNext(i); }
1.401 -// //template<typename I> I& next(I &i) const { return graph->next(i); }
1.402 -
1.403 -// //template< typename It > It first() const {
1.404 -// // It e; first(e); return e; }
1.405 -
1.406 -// //template< typename It > It first(const Node& v) const {
1.407 -// // It e; first(e, v); return e; }
1.408 -
1.409 -// //Node target(const Edge& e) const { return graph->source(e); }
1.410 -// //Node source(const Edge& e) const { return graph->target(e); }
1.411 -
1.412 -// //template<typename I> bool valid(const I& i) const
1.413 -// // { return graph->valid(i); }
1.414 -
1.415 -// //template<typename I> void setInvalid(const I &i);
1.416 -// //{ return graph->setInvalid(i); }
1.417 -
1.418 -// //template<typename I> Node aNode(const I& e) const {
1.419 -// // return graph->aNode(e); }
1.420 -// //template<typename I> Node bNode(const I& e) const {
1.421 -// // return graph->bNode(e); }
1.422 -
1.423 -// //Node addNode() const { return graph->addNode(); }
1.424 -// //Edge addEdge(const Node& source, const Node& target) const {
1.425 -// // return graph->addEdge(source, target); }
1.426 -
1.427 -// //int nodeNum() const { return graph->nodeNum(); }
1.428 -// //int edgeNum() const { return graph->edgeNum(); }
1.429 -
1.430 -// //template<typename I> void erase(const I& i) const { graph->erase(i); }
1.431 -
1.432 -// //void clear() const { graph->clear(); }
1.433 -
1.434 -// template<typename T> class NodeMap :
1.435 -// public GraphWrapper/*< TrivGraphWrapper<Graph> >*/::NodeMap<T>
1.436 -// {
1.437 -// public:
1.438 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.439 -// GraphWrapper/*< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
1.440 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.441 -// GraphWrapper/*< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
1.442 -// };
1.443 -
1.444 -// template<typename T> class EdgeMap :
1.445 -// public GraphWrapper/*< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
1.446 -// public:
1.447 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.448 -// GraphWrapper/*< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
1.449 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.450 -// GraphWrapper/*< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
1.451 -// };
1.452 -// };
1.453 -
1.454 - template<typename GraphWrapper>
1.455 - class RevGraphWrapper : public GraphWrapper<GraphWrapper> {
1.456 - public:
1.457 - typedef typename GraphWrapper<GraphWrapper>::Node Node;
1.458 - typedef typename GraphWrapper<GraphWrapper>::Edge Edge;
1.459 - //FIXME
1.460 - //If GraphWrapper::OutEdgeIt is not defined
1.461 - //and we do not want to use RevGraphWrapper::InEdgeIt,
1.462 - //this won't work, because of typedef
1.463 - //OR
1.464 - //graphs have to define their non-existing iterators to void
1.465 - //Unfortunately all the typedefs are instantiated in templates,
1.466 - //unlike other stuff
1.467 - typedef typename GraphWrapper<GraphWrapper>::OutEdgeIt InEdgeIt;
1.468 - typedef typename GraphWrapper<GraphWrapper>::InEdgeIt OutEdgeIt;
1.469 -
1.470 - RevGraphWrapper(GraphWrapper _gw) :
1.471 - GraphWrapper<GraphWrapper>(_gw) { }
1.472 -
1.473 - Node target(const Edge& e) const
1.474 - { return GraphWrapper<GraphWrapper>::source(e); }
1.475 - Node source(const Edge& e) const
1.476 - { return GraphWrapper<GraphWrapper>::target(e); }
1.477 - };
1.478 -
1.479 - //Subgraph on the same node-set and partial edge-set
1.480 - template<typename GraphWrapper, typename EdgeFilterMap>
1.481 - class SubGraphWrapper : public GraphWrapper<GraphWrapper> {
1.482 - protected:
1.483 - EdgeFilterMap* filter_map;
1.484 - public:
1.485 - typedef typename GraphWrapper<GraphWrapper>::Node Node;
1.486 - typedef typename GraphWrapper<GraphWrapper>::NodeIt NodeIt;
1.487 - typedef typename GraphWrapper<GraphWrapper>::Edge Edge;
1.488 - typedef typename GraphWrapper<GraphWrapper>::EdgeIt EdgeIt;
1.489 - typedef typename GraphWrapper<GraphWrapper>::InEdgeIt InEdgeIt;
1.490 - typedef typename GraphWrapper<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.491 -
1.492 - SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
1.493 - GraphWrapper<GraphWrapper>(_gw), filter_map(&_filter_map) { }
1.494 -
1.495 - template<typename I> I& first(I& i) const {
1.496 - gw.first(i);
1.497 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.498 - return i;
1.499 - }
1.500 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.501 - gw.first(i, p);
1.502 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.503 - return i;
1.504 - }
1.505 -
1.506 - //template<typename I> I getNext(const I& i) const {
1.507 - // return gw.getNext(i);
1.508 - //}
1.509 - template<typename I> I& next(I &i) const {
1.510 - gw.next(i);
1.511 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.512 - return i;
1.513 - }
1.514 -
1.515 - template< typename It > It first() const {
1.516 - It e; this->first(e); return e; }
1.517 -
1.518 - template< typename It > It first(const Node& v) const {
1.519 - It e; this->first(e, v); return e; }
1.520 - };
1.521 -
1.522 -// template<typename GraphWrapper>
1.523 -// class UndirGraphWrapper {
1.524 -// protected:
1.525 -// //Graph* graph;
1.526 -// GraphWrapper gw;
1.527 -
1.528 -// public:
1.529 -// typedef GraphWrapper BaseGraph;
1.530 -
1.531 -// typedef typename GraphWrapper::Node Node;
1.532 -// typedef typename GraphWrapper::NodeIt NodeIt;
1.533 -
1.534 -// //typedef typename Graph::Edge Edge;
1.535 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.536 -// //typedef typename Graph::InEdgeIt InEdgeIt;
1.537 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.538 -// //typedef typename Graph::EdgeIt EdgeIt;
1.539 -
1.540 -// //private:
1.541 -// typedef typename GraphWrapper::Edge GraphEdge;
1.542 -// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.543 -// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.544 -// //public:
1.545 -
1.546 -// //UndirGraphWrapper() : graph(0) { }
1.547 -// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.548 -
1.549 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.550 -// //Graph& getGraph() const { return (*graph); }
1.551 -
1.552 -// class Edge {
1.553 -// friend class UndirGraphWrapper<GraphWrapper>;
1.554 -// bool out_or_in; //true iff out
1.555 -// GraphOutEdgeIt out;
1.556 -// GraphInEdgeIt in;
1.557 -// public:
1.558 -// Edge() : out_or_in(), out(), in() { }
1.559 -// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.560 -// operator GraphEdge() const {
1.561 -// if (out_or_in) return(out); else return(in);
1.562 -// }
1.563 -// friend bool operator==(const Edge& u, const Edge& v) {
1.564 -// if (v.out_or_in)
1.565 -// return (u.out_or_in && u.out==v.out);
1.566 -// else
1.567 -// return (!u.out_or_in && u.in==v.in);
1.568 -// }
1.569 -// friend bool operator!=(const Edge& u, const Edge& v) {
1.570 -// if (v.out_or_in)
1.571 -// return (!u.out_or_in || u.out!=v.out);
1.572 -// else
1.573 -// return (u.out_or_in || u.in!=v.in);
1.574 -// }
1.575 -// };
1.576 -
1.577 -// class OutEdgeIt : public Edge {
1.578 -// friend class UndirGraphWrapper<GraphWrapper>;
1.579 -// public:
1.580 -// OutEdgeIt() : Edge() { }
1.581 -// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.582 -// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.583 -// : Edge() {
1.584 -// out_or_in=true;
1.585 -// _G.gw.first(out, n);
1.586 -// if (!(_G.gw.valid(out))) {
1.587 -// out_or_in=false;
1.588 -// _G.gw.first(in, n);
1.589 -// }
1.590 -// }
1.591 -// };
1.592 -
1.593 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.594 -// e.out_or_in=true;
1.595 -// gw.first(e.out, n);
1.596 -// if (!(gw.valid(e.out))) {
1.597 -// e.out_or_in=false;
1.598 -// gw.first(e.in, n);
1.599 -// }
1.600 -// return e;
1.601 -// }
1.602 -
1.603 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.604 -// if (e.out_or_in) {
1.605 -// Node n=gw.source(e.out);
1.606 -// gw.next(e.out);
1.607 -// if (!gw.valid(e.out)) {
1.608 -// e.out_or_in=false;
1.609 -// gw.first(e.in, n);
1.610 -// }
1.611 -// } else {
1.612 -// gw.next(e.in);
1.613 -// }
1.614 -// return e;
1.615 -// }
1.616 -
1.617 -// Node aNode(const OutEdgeIt& e) const {
1.618 -// if (e.out_or_in) return gw.source(e); else return gw.target(e); }
1.619 -// Node bNode(const OutEdgeIt& e) const {
1.620 -// if (e.out_or_in) return gw.target(e); else return gw.source(e); }
1.621 -
1.622 -// typedef OutEdgeIt InEdgeIt;
1.623 -
1.624 -// template<typename I> I& first(I& i) const { return gw.first(i); }
1.625 -// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.626 -// // return graph->first(i, p); }
1.627 -
1.628 -// template<typename I> I getNext(const I& i) const {
1.629 -// return gw.getNext(i); }
1.630 -// template<typename I> I& next(I &i) const { return gw.next(i); }
1.631 -
1.632 -// template< typename It > It first() const {
1.633 -// It e; first(e); return e; }
1.634 -
1.635 -// template< typename It > It first(const Node& v) const {
1.636 -// It e; first(e, v); return e; }
1.637 -
1.638 -// Node target(const Edge& e) const { return gw.target(e); }
1.639 -// Node source(const Edge& e) const { return gw.source(e); }
1.640 -
1.641 -// template<typename I> bool valid(const I& i) const
1.642 -// { return gw.valid(i); }
1.643 -
1.644 -// //template<typename I> void setInvalid(const I &i);
1.645 -// //{ return graph->setInvalid(i); }
1.646 -
1.647 -// int nodeNum() const { return gw.nodeNum(); }
1.648 -// int edgeNum() const { return gw.edgeNum(); }
1.649 -
1.650 -// // template<typename I> Node aNode(const I& e) const {
1.651 -// // return graph->aNode(e); }
1.652 -// // template<typename I> Node bNode(const I& e) const {
1.653 -// // return graph->bNode(e); }
1.654 -
1.655 -// Node addNode() const { return gw.addNode(); }
1.656 -// // FIXME: ez igy nem jo, mert nem
1.657 -// // Edge addEdge(const Node& source, const Node& target) const {
1.658 -// // return graph->addEdge(source, target); }
1.659 -
1.660 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.661 -
1.662 -// void clear() const { gw.clear(); }
1.663 -
1.664 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.665 -// public:
1.666 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.667 -// GraphWrapper::NodeMap<T>(_G.gw) { }
1.668 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.669 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.670 -// };
1.671 -
1.672 -// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.673 -// public:
1.674 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.675 -// GraphWrapper::EdgeMap<T>(_G.gw) { }
1.676 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.677 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.678 -// };
1.679 -// };
1.680 -
1.681 -
1.682 - template<typename GraphWrapper>
1.683 - class UndirGraphWrapper : public GraphWrapper<GraphWrapper> {
1.684 - protected:
1.685 -// GraphWrapper gw;
1.686 -
1.687 - public:
1.688 - //typedef GraphWrapper BaseGraph;
1.689 -
1.690 - typedef typename GraphWrapper<GraphWrapper>::Node Node;
1.691 - typedef typename GraphWrapper<GraphWrapper>::NodeIt NodeIt;
1.692 -
1.693 - //private:
1.694 - //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
1.695 - //legyenek, at kell irni
1.696 - typedef typename /*GraphWrapper<GraphWrapper>*/
1.697 - GraphWrapper::Edge GraphEdge;
1.698 - typedef typename /*GraphWrapper<GraphWrapper>*/
1.699 - GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.700 - typedef typename /*GraphWrapper<GraphWrapper>*/
1.701 - GraphWrapper::InEdgeIt GraphInEdgeIt;
1.702 - //public:
1.703 -
1.704 - //UndirGraphWrapper() : graph(0) { }
1.705 - UndirGraphWrapper(GraphWrapper _gw) :
1.706 - GraphWrapper<GraphWrapper>(_gw) { }
1.707 -
1.708 - //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.709 -
1.710 - //void setGraph(Graph& _graph) { graph = &_graph; }
1.711 - //Graph& getGraph() const { return (*graph); }
1.712 -
1.713 - class Edge {
1.714 - friend class UndirGraphWrapper<GraphWrapper>;
1.715 - protected:
1.716 - bool out_or_in; //true iff out
1.717 - GraphOutEdgeIt out;
1.718 - GraphInEdgeIt in;
1.719 - public:
1.720 - Edge() : out_or_in(), out(), in() { }
1.721 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.722 - operator GraphEdge() const {
1.723 - if (out_or_in) return(out); else return(in);
1.724 - }
1.725 -//FIXME
1.726 -//2 edges are equal if they "refer" to the same physical edge
1.727 -//is it good?
1.728 - friend bool operator==(const Edge& u, const Edge& v) {
1.729 - if (v.out_or_in)
1.730 - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.731 - //return (u.out_or_in && u.out==v.out);
1.732 - else
1.733 - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.734 - //return (!u.out_or_in && u.in==v.in);
1.735 - }
1.736 - friend bool operator!=(const Edge& u, const Edge& v) {
1.737 - if (v.out_or_in)
1.738 - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
1.739 - //return (!u.out_or_in || u.out!=v.out);
1.740 - else
1.741 - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
1.742 - //return (u.out_or_in || u.in!=v.in);
1.743 - }
1.744 - };
1.745 -
1.746 - class OutEdgeIt : public Edge {
1.747 - friend class UndirGraphWrapper<GraphWrapper>;
1.748 - public:
1.749 - OutEdgeIt() : Edge() { }
1.750 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.751 - OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.752 - : Edge() {
1.753 - out_or_in=true; _G.gw.first(out, n);
1.754 - if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
1.755 - }
1.756 - };
1.757 -
1.758 - typedef OutEdgeIt InEdgeIt;
1.759 -
1.760 - class EdgeIt : public Edge {
1.761 - friend class UndirGraphWrapper<GraphWrapper>;
1.762 - protected:
1.763 - NodeIt v;
1.764 - public:
1.765 - EdgeIt() : Edge() { }
1.766 - EdgeIt(const Invalid& i) : Edge(i) { }
1.767 - EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
1.768 - : Edge() {
1.769 - out_or_in=true;
1.770 - //Node v;
1.771 - _G.first(v);
1.772 - if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
1.773 - while (_G.valid(v) && !_G.gw.valid(out)) {
1.774 - _G.gw.next(v);
1.775 - if (_G.valid(v)) _G.gw.first(out);
1.776 - }
1.777 - }
1.778 - };
1.779 -
1.780 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.781 - e.out_or_in=true; gw.first(e.out, n);
1.782 - if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
1.783 - return e;
1.784 - }
1.785 -
1.786 - EdgeIt& first(EdgeIt& e) const {
1.787 - e.out_or_in=true;
1.788 - //NodeIt v;
1.789 - first(e.v);
1.790 - if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
1.791 - while (valid(e.v) && !gw.valid(e.out)) {
1.792 - gw.next(e.v);
1.793 - if (valid(e.v)) gw.first(e.out, e.v);
1.794 - }
1.795 - return e;
1.796 - }
1.797 -
1.798 - template<typename I> I& first(I& i) const { gw.first(i); return i; }
1.799 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.800 - gw.first(i, p); return i; }
1.801 -
1.802 - OutEdgeIt& next(OutEdgeIt& e) const {
1.803 - if (e.out_or_in) {
1.804 - Node n=gw.source(e.out);
1.805 - gw.next(e.out);
1.806 - if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
1.807 - } else {
1.808 - gw.next(e.in);
1.809 - }
1.810 - return e;
1.811 - }
1.812 -
1.813 - EdgeIt& next(EdgeIt& e) const {
1.814 - //NodeIt v=source(e);
1.815 - gw.next(e.out);
1.816 - while (valid(e.v) && !gw.valid(e.out)) {
1.817 - next(e.v);
1.818 - if (valid(e.v)) gw.first(e.out, e.v);
1.819 - }
1.820 - return e;
1.821 - }
1.822 -
1.823 - template<typename I> I& next(I &i) const { return gw.next(i); }
1.824 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.825 -
1.826 - template< typename It > It first() const {
1.827 - It e; first(e); return e; }
1.828 -
1.829 - template< typename It > It first(const Node& v) const {
1.830 - It e; first(e, v); return e; }
1.831 -
1.832 -// Node target(const Edge& e) const { return gw.target(e); }
1.833 -// Node source(const Edge& e) const { return gw.source(e); }
1.834 -
1.835 -// template<typename I> bool valid(const I& i) const
1.836 -// { return gw.valid(i); }
1.837 -
1.838 -// int nodeNum() const { return gw.nodeNum(); }
1.839 -// int edgeNum() const { return gw.edgeNum(); }
1.840 -
1.841 -// template<typename I> Node aNode(const I& e) const {
1.842 -// return graph->aNode(e); }
1.843 -// template<typename I> Node bNode(const I& e) const {
1.844 -// return graph->bNode(e); }
1.845 -
1.846 - Node aNode(const OutEdgeIt& e) const {
1.847 - if (e.out_or_in) return gw.source(e); else return gw.target(e); }
1.848 - Node bNode(const OutEdgeIt& e) const {
1.849 - if (e.out_or_in) return gw.target(e); else return gw.source(e); }
1.850 -
1.851 -// Node addNode() const { return gw.addNode(); }
1.852 -
1.853 -// FIXME: ez igy nem jo, mert nem
1.854 -// Edge addEdge(const Node& source, const Node& target) const {
1.855 -// return graph->addEdge(source, target); }
1.856 -
1.857 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.858 -
1.859 -// void clear() const { gw.clear(); }
1.860 -
1.861 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.862 -// public:
1.863 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.864 -// GraphWrapper::NodeMap<T>(_G.gw) { }
1.865 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.866 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.867 -// };
1.868 -
1.869 -// template<typename T> class EdgeMap :
1.870 -// public GraphWrapper<GraphWrapper>::EdgeMap<T> {
1.871 -// public:
1.872 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.873 -// GraphWrapper<GraphWrapper>::EdgeMap<T>(_G.gw) { }
1.874 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.875 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.876 -// };
1.877 - };
1.878 -
1.879 -
1.880 -
1.881 -
1.882 -
1.883 -// template<typename Graph>
1.884 -// class SymGraphWrapper
1.885 -// {
1.886 -// Graph* graph;
1.887 -
1.888 -// public:
1.889 -// typedef Graph BaseGraph;
1.890 -
1.891 -// typedef typename Graph::Node Node;
1.892 -// typedef typename Graph::Edge Edge;
1.893 -
1.894 -// typedef typename Graph::NodeIt NodeIt;
1.895 -
1.896 -// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.897 -// //iranyitatlant, ami van
1.898 -// //mert csak 1 dolgot lehet be typedef-elni
1.899 -// typedef typename Graph::OutEdgeIt SymEdgeIt;
1.900 -// //typedef typename Graph::InEdgeIt SymEdgeIt;
1.901 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.902 -// typedef typename Graph::EdgeIt EdgeIt;
1.903 -
1.904 -// int nodeNum() const { return graph->nodeNum(); }
1.905 -// int edgeNum() const { return graph->edgeNum(); }
1.906 -
1.907 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.908 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.909 -// return graph->first(i, p); }
1.910 -// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.911 -// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.912 -
1.913 -// template< typename It > It first() const {
1.914 -// It e; first(e); return e; }
1.915 -
1.916 -// template< typename It > It first(Node v) const {
1.917 -// It e; first(e, v); return e; }
1.918 -
1.919 -// Node target(const Edge& e) const { return graph->target(e); }
1.920 -// Node source(const Edge& e) const { return graph->source(e); }
1.921 -
1.922 -// template<typename I> Node aNode(const I& e) const {
1.923 -// return graph->aNode(e); }
1.924 -// template<typename I> Node bNode(const I& e) const {
1.925 -// return graph->bNode(e); }
1.926 -
1.927 -// //template<typename I> bool valid(const I i);
1.928 -// //{ return graph->valid(i); }
1.929 -
1.930 -// //template<typename I> void setInvalid(const I &i);
1.931 -// //{ return graph->setInvalid(i); }
1.932 -
1.933 -// Node addNode() { return graph->addNode(); }
1.934 -// Edge addEdge(const Node& source, const Node& target) {
1.935 -// return graph->addEdge(source, target); }
1.936 -
1.937 -// template<typename I> void erase(const I& i) { graph->erase(i); }
1.938 -
1.939 -// void clear() { graph->clear(); }
1.940 -
1.941 -// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.942 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.943 -
1.944 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.945 -// Graph& getGraph() { return (*graph); }
1.946 -
1.947 -// //SymGraphWrapper() : graph(0) { }
1.948 -// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.949 -// };
1.950 -
1.951 -
1.952 - template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1.953 - class ResGraphWrapper : public GraphWrapper<GraphWrapper>{
1.954 - public:
1.955 - //typedef Graph BaseGraph;
1.956 - //typedef TrivGraphWrapper<const Graph> GraphWrapper;
1.957 - typedef typename GraphWrapper<GraphWrapper>::Node Node;
1.958 - typedef typename GraphWrapper<GraphWrapper>::NodeIt NodeIt;
1.959 - private:
1.960 - typedef typename /*GraphWrapper<GraphWrapper>*/
1.961 - GraphWrapper::OutEdgeIt OldOutEdgeIt;
1.962 - typedef typename /*GraphWrapper<GraphWrapper>*/
1.963 - GraphWrapper::InEdgeIt OldInEdgeIt;
1.964 - protected:
1.965 - //const Graph* graph;
1.966 - //GraphWrapper gw;
1.967 - FlowMap* flow;
1.968 - const CapacityMap* capacity;
1.969 - public:
1.970 -
1.971 - ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
1.972 - const CapacityMap& _capacity) :
1.973 - GraphWrapper<GraphWrapper>(_gw),
1.974 - flow(&_flow), capacity(&_capacity) { }
1.975 -
1.976 - //void setGraph(const Graph& _graph) { graph = &_graph; }
1.977 - //const Graph& getGraph() const { return (*graph); }
1.978 -
1.979 - class Edge;
1.980 - class OutEdgeIt;
1.981 - friend class Edge;
1.982 - friend class OutEdgeIt;
1.983 -
1.984 - class Edge {
1.985 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.986 - protected:
1.987 - bool out_or_in; //true, iff out
1.988 - OldOutEdgeIt out;
1.989 - OldInEdgeIt in;
1.990 - public:
1.991 - Edge() : out_or_in(true) { }
1.992 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.993 -// bool valid() const {
1.994 -// return out_or_in && out.valid() || in.valid(); }
1.995 - friend bool operator==(const Edge& u, const Edge& v) {
1.996 - if (v.out_or_in)
1.997 - return (u.out_or_in && u.out==v.out);
1.998 - else
1.999 - return (!u.out_or_in && u.in==v.in);
1.1000 - }
1.1001 - friend bool operator!=(const Edge& u, const Edge& v) {
1.1002 - if (v.out_or_in)
1.1003 - return (!u.out_or_in || u.out!=v.out);
1.1004 - else
1.1005 - return (u.out_or_in || u.in!=v.in);
1.1006 - }
1.1007 - };
1.1008 -
1.1009 -
1.1010 - class OutEdgeIt : public Edge {
1.1011 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1012 - public:
1.1013 - OutEdgeIt() { }
1.1014 - //FIXME
1.1015 - OutEdgeIt(const Edge& e) : Edge(e) { }
1.1016 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1017 - protected:
1.1018 - OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1019 - resG.gw.first(out, v);
1.1020 - while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1021 - if (!resG.gw.valid(out)) {
1.1022 - out_or_in=0;
1.1023 - resG.gw.first(in, v);
1.1024 - while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1025 - }
1.1026 - }
1.1027 -// public:
1.1028 -// OutEdgeIt& operator++() {
1.1029 -// if (out_or_in) {
1.1030 -// Node v=/*resG->*/G->aNode(out);
1.1031 -// ++out;
1.1032 -// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1033 -// if (!out.valid()) {
1.1034 -// out_or_in=0;
1.1035 -// G->first(in, v);
1.1036 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1037 -// }
1.1038 -// } else {
1.1039 -// ++in;
1.1040 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1041 -// }
1.1042 -// return *this;
1.1043 -// }
1.1044 - };
1.1045 -
1.1046 - //FIXME This is just for having InEdgeIt
1.1047 - typedef void InEdgeIt;
1.1048 -
1.1049 - class EdgeIt : public Edge {
1.1050 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1051 - NodeIt v;
1.1052 - public:
1.1053 - EdgeIt() { }
1.1054 - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1055 - EdgeIt(const Invalid& i) : Edge(i) { }
1.1056 - EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1057 - resG.gw.first(v);
1.1058 - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
1.1059 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1060 - while (resG.gw.valid(v) && !resG.gw.valid(out)) {
1.1061 - resG.gw.next(v);
1.1062 - if (resG.gw.valid(v)) resG.gw.first(out, v);
1.1063 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1064 - }
1.1065 - if (!resG.gw.valid(out)) {
1.1066 - out_or_in=0;
1.1067 - resG.gw.first(v);
1.1068 - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
1.1069 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1070 - while (resG.gw.valid(v) && !resG.gw.valid(in)) {
1.1071 - resG.gw.next(v);
1.1072 - if (resG.gw.valid(v)) resG.gw.first(in, v);
1.1073 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1074 - }
1.1075 - }
1.1076 - }
1.1077 -// EdgeIt& operator++() {
1.1078 -// if (out_or_in) {
1.1079 -// ++out;
1.1080 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1081 -// while (v.valid() && !out.valid()) {
1.1082 -// ++v;
1.1083 -// if (v.valid()) G->first(out, v);
1.1084 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1085 -// }
1.1086 -// if (!out.valid()) {
1.1087 -// out_or_in=0;
1.1088 -// G->first(v);
1.1089 -// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1.1090 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1091 -// while (v.valid() && !in.valid()) {
1.1092 -// ++v;
1.1093 -// if (v.valid()) G->first(in, v);
1.1094 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1095 -// }
1.1096 -// }
1.1097 -// } else {
1.1098 -// ++in;
1.1099 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1100 -// while (v.valid() && !in.valid()) {
1.1101 -// ++v;
1.1102 -// if (v.valid()) G->first(in, v);
1.1103 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1104 -// }
1.1105 -// }
1.1106 -// return *this;
1.1107 -// }
1.1108 - };
1.1109 -
1.1110 - NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
1.1111 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.1112 - e=OutEdgeIt(*this, v);
1.1113 - return e;
1.1114 - }
1.1115 - EdgeIt& first(EdgeIt& e) const {
1.1116 - e=EdgeIt(*this);
1.1117 - return e;
1.1118 - }
1.1119 -
1.1120 - NodeIt& next(NodeIt& n) const { return gw.next(n); }
1.1121 -
1.1122 - OutEdgeIt& next(OutEdgeIt& e) const {
1.1123 - if (e.out_or_in) {
1.1124 - Node v=gw.aNode(e.out);
1.1125 - gw.next(e.out);
1.1126 - while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1127 - if (!gw.valid(e.out)) {
1.1128 - e.out_or_in=0;
1.1129 - gw.first(e.in, v);
1.1130 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1131 - }
1.1132 - } else {
1.1133 - gw.next(e.in);
1.1134 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1135 - }
1.1136 - return e;
1.1137 - }
1.1138 -
1.1139 - EdgeIt& next(EdgeIt& e) const {
1.1140 - if (e.out_or_in) {
1.1141 - gw.next(e.out);
1.1142 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1143 - while (gw.valid(e.v) && !gw.valid(e.out)) {
1.1144 - gw.next(e.v);
1.1145 - if (gw.valid(e.v)) gw.first(e.out, e.v);
1.1146 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1147 - }
1.1148 - if (!gw.valid(e.out)) {
1.1149 - e.out_or_in=0;
1.1150 - gw.first(e.v);
1.1151 - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
1.1152 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1153 - while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1154 - gw.next(e.v);
1.1155 - if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1156 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1157 - }
1.1158 - }
1.1159 - } else {
1.1160 - gw.next(e.in);
1.1161 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1162 - while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1163 - gw.next(e.v);
1.1164 - if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1165 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1166 - }
1.1167 - }
1.1168 - return e;
1.1169 - }
1.1170 -
1.1171 -
1.1172 - template< typename It >
1.1173 - It first() const {
1.1174 - It e;
1.1175 - first(e);
1.1176 - return e;
1.1177 - }
1.1178 -
1.1179 - template< typename It >
1.1180 - It first(Node v) const {
1.1181 - It e;
1.1182 - first(e, v);
1.1183 - return e;
1.1184 - }
1.1185 -
1.1186 - Node source(Edge e) const {
1.1187 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1188 - Node target(Edge e) const {
1.1189 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1190 -
1.1191 - Node aNode(OutEdgeIt e) const {
1.1192 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1193 - Node bNode(OutEdgeIt e) const {
1.1194 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1195 -
1.1196 - int nodeNum() const { return gw.nodeNum(); }
1.1197 - //FIXME
1.1198 - //int edgeNum() const { return gw.edgeNum(); }
1.1199 -
1.1200 -
1.1201 - int id(Node v) const { return gw.id(v); }
1.1202 -
1.1203 - bool valid(Node n) const { return gw.valid(n); }
1.1204 - bool valid(Edge e) const {
1.1205 - return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1.1206 -
1.1207 - void augment(const Edge& e, Number a) const {
1.1208 - if (e.out_or_in)
1.1209 - flow->set(e.out, flow->get(e.out)+a);
1.1210 - else
1.1211 - flow->set(e.in, flow->get(e.in)-a);
1.1212 - }
1.1213 -
1.1214 - Number resCap(const Edge& e) const {
1.1215 - if (e.out_or_in)
1.1216 - return (capacity->get(e.out)-flow->get(e.out));
1.1217 - else
1.1218 - return (flow->get(e.in));
1.1219 - }
1.1220 -
1.1221 - Number resCap(OldOutEdgeIt out) const {
1.1222 - return (capacity->get(out)-flow->get(out));
1.1223 - }
1.1224 -
1.1225 - Number resCap(OldInEdgeIt in) const {
1.1226 - return (flow->get(in));
1.1227 - }
1.1228 -
1.1229 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.1230 -// public:
1.1231 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
1.1232 -// : GraphWrapper::NodeMap<T>(_G.gw) { }
1.1233 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
1.1234 -// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.1235 -// };
1.1236 -
1.1237 -// template <typename T>
1.1238 -// class NodeMap {
1.1239 -// typename Graph::NodeMap<T> node_map;
1.1240 -// public:
1.1241 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1.1242 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1.1243 -// void set(Node nit, T a) { node_map.set(nit, a); }
1.1244 -// T get(Node nit) const { return node_map.get(nit); }
1.1245 -// };
1.1246 -
1.1247 - template <typename T>
1.1248 - class EdgeMap {
1.1249 - typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1.1250 - public:
1.1251 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1.1252 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1.1253 - void set(Edge e, T a) {
1.1254 - if (e.out_or_in)
1.1255 - forward_map.set(e.out, a);
1.1256 - else
1.1257 - backward_map.set(e.in, a);
1.1258 - }
1.1259 - T get(Edge e) {
1.1260 - if (e.out_or_in)
1.1261 - return forward_map.get(e.out);
1.1262 - else
1.1263 - return backward_map.get(e.in);
1.1264 - }
1.1265 - };
1.1266 - };
1.1267 -
1.1268 - //Subgraph on the same node-set and partial edge-set
1.1269 - template<typename GraphWrapper, typename FirstOutEdgesMap>
1.1270 - class ErasingFirstGraphWrapper : public GraphWrapper<GraphWrapper> {
1.1271 - protected:
1.1272 - FirstOutEdgesMap* first_out_edges;
1.1273 - public:
1.1274 - typedef typename GraphWrapper<GraphWrapper>::Node Node;
1.1275 - typedef typename GraphWrapper<GraphWrapper>::NodeIt NodeIt;
1.1276 - typedef typename GraphWrapper<GraphWrapper>::Edge Edge;
1.1277 - typedef typename GraphWrapper<GraphWrapper>::EdgeIt EdgeIt;
1.1278 - typedef typename GraphWrapper<GraphWrapper>::InEdgeIt InEdgeIt;
1.1279 - typedef typename GraphWrapper<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.1280 -
1.1281 - ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
1.1282 - GraphWrapper<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
1.1283 -
1.1284 - template<typename I> I& first(I& i) const {
1.1285 - gw.first(i);
1.1286 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1287 - return i;
1.1288 - }
1.1289 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1290 - e=first_out_edges->get(n);
1.1291 - return e;
1.1292 - }
1.1293 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.1294 - gw.first(i, p);
1.1295 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1296 - return i;
1.1297 - }
1.1298 -
1.1299 - //template<typename I> I getNext(const I& i) const {
1.1300 - // return gw.getNext(i);
1.1301 - //}
1.1302 - template<typename I> I& next(I &i) const {
1.1303 - gw.next(i);
1.1304 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1305 - return i;
1.1306 - }
1.1307 -
1.1308 - template< typename It > It first() const {
1.1309 - It e; this->first(e); return e; }
1.1310 -
1.1311 - template< typename It > It first(const Node& v) const {
1.1312 - It e; this->first(e, v); return e; }
1.1313 -
1.1314 - void erase(const OutEdgeIt& e) const {
1.1315 - OutEdgeIt f=e;
1.1316 - this->next(f);
1.1317 - first_out_edges->set(this->source(e), f);
1.1318 - }
1.1319 - };
1.1320 -
1.1321 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1322 -// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1323 -// protected:
1.1324 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1325 -// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1326 -// public:
1.1327 -// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1328 -// const CapacityMap& _capacity) :
1.1329 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1.1330 -// first_out_edges(*this) /*, dist(*this)*/ {
1.1331 -// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1.1332 -// OutEdgeIt e;
1.1333 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1334 -// first_out_edges.set(n, e);
1.1335 -// }
1.1336 -// }
1.1337 -
1.1338 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1339 -// //Graph& getGraph() const { return (*graph); }
1.1340 -
1.1341 -// //TrivGraphWrapper() : graph(0) { }
1.1342 -// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1343 -
1.1344 -// //typedef Graph BaseGraph;
1.1345 -
1.1346 -// //typedef typename Graph::Node Node;
1.1347 -// //typedef typename Graph::NodeIt NodeIt;
1.1348 -
1.1349 -// //typedef typename Graph::Edge Edge;
1.1350 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1351 -// //typedef typename Graph::InEdgeIt InEdgeIt;
1.1352 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1353 -// //typedef typename Graph::EdgeIt EdgeIt;
1.1354 -
1.1355 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1356 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1357 -
1.1358 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1359 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1360 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1361 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1362 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1363 -
1.1364 -// NodeIt& first(NodeIt& n) const {
1.1365 -// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1366 -// }
1.1367 -
1.1368 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1369 -// e=first_out_edges.get(n);
1.1370 -// return e;
1.1371 -// }
1.1372 -
1.1373 -// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1.1374 -// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1.1375 -// // return first(i, p); }
1.1376 -
1.1377 -// //template<typename I> I getNext(const I& i) const {
1.1378 -// // return gw.getNext(i); }
1.1379 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1380 -
1.1381 -// template< typename It > It first() const {
1.1382 -// It e; first(e); return e; }
1.1383 -
1.1384 -// template< typename It > It first(const Node& v) const {
1.1385 -// It e; first(e, v); return e; }
1.1386 -
1.1387 -// //Node target(const Edge& e) const { return gw.target(e); }
1.1388 -// //Node source(const Edge& e) const { return gw.source(e); }
1.1389 -
1.1390 -// //template<typename I> bool valid(const I& i) const
1.1391 -// // { return gw.valid(i); }
1.1392 -
1.1393 -// //int nodeNum() const { return gw.nodeNum(); }
1.1394 -// //int edgeNum() const { return gw.edgeNum(); }
1.1395 -
1.1396 -// //template<typename I> Node aNode(const I& e) const {
1.1397 -// // return gw.aNode(e); }
1.1398 -// //template<typename I> Node bNode(const I& e) const {
1.1399 -// // return gw.bNode(e); }
1.1400 -
1.1401 -// //Node addNode() const { return gw.addNode(); }
1.1402 -// //Edge addEdge(const Node& source, const Node& target) const {
1.1403 -// // return gw.addEdge(source, target); }
1.1404 -
1.1405 -// //void erase(const OutEdgeIt& e) {
1.1406 -// // first_out_edge(this->source(e))=e;
1.1407 -// //}
1.1408 -// void erase(const Edge& e) {
1.1409 -// OutEdgeIt f(e);
1.1410 -// next(f);
1.1411 -// first_out_edges.set(this->source(e), f);
1.1412 -// }
1.1413 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1414 -
1.1415 -// //void clear() const { gw.clear(); }
1.1416 -
1.1417 -// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1418 -// public:
1.1419 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1420 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1421 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1422 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1423 -// };
1.1424 -
1.1425 -// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1426 -// public:
1.1427 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1428 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1429 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1430 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1431 -// };
1.1432 -// };
1.1433 -
1.1434 -// template<typename GraphWrapper>
1.1435 -// class FilterGraphWrapper {
1.1436 -// };
1.1437 -
1.1438 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1439 -// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1440 -
1.1441 -// //Graph* graph;
1.1442 -
1.1443 -// public:
1.1444 -// //typedef Graph BaseGraph;
1.1445 -
1.1446 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1447 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1448 -
1.1449 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1450 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1451 -// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1452 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1453 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1454 -
1.1455 -// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1456 -
1.1457 -// public:
1.1458 -// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1459 -// const CapacityMap& _capacity) :
1.1460 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1.1461 -// }
1.1462 -
1.1463 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1464 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1465 -// while (valid(e) && (dist.get(source(e))/*+1!=*/>=dist.get(target(e))))
1.1466 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1467 -// return e;
1.1468 -// }
1.1469 -
1.1470 -// NodeIt& next(NodeIt& e) const {
1.1471 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1472 -// }
1.1473 -
1.1474 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.1475 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1476 -// while (valid(e) && (dist.get(source(e))/*+1!*/>=dist.get(target(e))))
1.1477 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1478 -// return e;
1.1479 -// }
1.1480 -
1.1481 -// NodeIt& first(NodeIt& n) const {
1.1482 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1483 -// }
1.1484 -
1.1485 -// void erase(const Edge& e) {
1.1486 -// OutEdgeIt f(e);
1.1487 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1488 -// while (valid(f) && (dist.get(source(f))/*+1!=*/>=dist.get(target(f))))
1.1489 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1490 -// first_out_edges.set(this->source(e), f);
1.1491 -// }
1.1492 -
1.1493 -// //TrivGraphWrapper() : graph(0) { }
1.1494 -// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1495 -
1.1496 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1497 -// //Graph& getGraph() const { return (*graph); }
1.1498 -
1.1499 -// //template<typename I> I& first(I& i) const { return gw.first(i); }
1.1500 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
1.1501 -// // return gw.first(i, p); }
1.1502 -
1.1503 -// //template<typename I> I getNext(const I& i) const {
1.1504 -// // return gw.getNext(i); }
1.1505 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1506 -
1.1507 -// template< typename It > It first() const {
1.1508 -// It e; first(e); return e; }
1.1509 -
1.1510 -// template< typename It > It first(const Node& v) const {
1.1511 -// It e; first(e, v); return e; }
1.1512 -
1.1513 -// //Node target(const Edge& e) const { return gw.target(e); }
1.1514 -// //Node source(const Edge& e) const { return gw.source(e); }
1.1515 -
1.1516 -// //template<typename I> bool valid(const I& i) const
1.1517 -// // { return gw.valid(i); }
1.1518 -
1.1519 -// //template<typename I> void setInvalid(const I &i);
1.1520 -// //{ return gw.setInvalid(i); }
1.1521 -
1.1522 -// //int nodeNum() const { return gw.nodeNum(); }
1.1523 -// //int edgeNum() const { return gw.edgeNum(); }
1.1524 -
1.1525 -// //template<typename I> Node aNode(const I& e) const {
1.1526 -// // return gw.aNode(e); }
1.1527 -// //template<typename I> Node bNode(const I& e) const {
1.1528 -// // return gw.bNode(e); }
1.1529 -
1.1530 -// //Node addNode() const { return gw.addNode(); }
1.1531 -// //Edge addEdge(const Node& source, const Node& target) const {
1.1532 -// // return gw.addEdge(source, target); }
1.1533 -
1.1534 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1535 -
1.1536 -// //void clear() const { gw.clear(); }
1.1537 -
1.1538 -// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1539 -// public:
1.1540 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1541 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1542 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1543 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1544 -// };
1.1545 -
1.1546 -// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1547 -// public:
1.1548 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1549 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1550 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1551 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1552 -// };
1.1553 -
1.1554 -// public:
1.1555 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1556 -
1.1557 -// };
1.1558 -
1.1559 -
1.1560 -
1.1561 -// // FIXME: comparison should be made better!!!
1.1562 -// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.1563 -// class ResGraphWrapper
1.1564 -// {
1.1565 -// Graph* graph;
1.1566 -
1.1567 -// public:
1.1568 -// typedef Graph BaseGraph;
1.1569 -
1.1570 -// typedef typename Graph::Node Node;
1.1571 -// typedef typename Graph::Edge Edge;
1.1572 -
1.1573 -// typedef typename Graph::NodeIt NodeIt;
1.1574 -
1.1575 -// class OutEdgeIt {
1.1576 -// public:
1.1577 -// //Graph::Node n;
1.1578 -// bool out_or_in;
1.1579 -// typename Graph::OutEdgeIt o;
1.1580 -// typename Graph::InEdgeIt i;
1.1581 -// };
1.1582 -// class InEdgeIt {
1.1583 -// public:
1.1584 -// //Graph::Node n;
1.1585 -// bool out_or_in;
1.1586 -// typename Graph::OutEdgeIt o;
1.1587 -// typename Graph::InEdgeIt i;
1.1588 -// };
1.1589 -// typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1590 -// typedef typename Graph::EdgeIt EdgeIt;
1.1591 -
1.1592 -// int nodeNum() const { return gw.nodeNum(); }
1.1593 -// int edgeNum() const { return gw.edgeNum(); }
1.1594 -
1.1595 -// Node& first(Node& n) const { return gw.first(n); }
1.1596 -
1.1597 -// // Edge and SymEdge is missing!!!!
1.1598 -// // Edge <-> In/OutEdgeIt conversion is missing!!!!
1.1599 -
1.1600 -// //FIXME
1.1601 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1.1602 -// {
1.1603 -// e.n=n;
1.1604 -// gw.first(e.o,n);
1.1605 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1606 -// gw.goNext(e.o);
1.1607 -// if(!gw.valid(e.o)) {
1.1608 -// gw.first(e.i,n);
1.1609 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1610 -// gw.goNext(e.i);
1.1611 -// }
1.1612 -// return e;
1.1613 -// }
1.1614 -// /*
1.1615 -// OutEdgeIt &goNext(OutEdgeIt &e)
1.1616 -// {
1.1617 -// if(gw.valid(e.o)) {
1.1618 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1619 -// gw.goNext(e.o);
1.1620 -// if(gw.valid(e.o)) return e;
1.1621 -// else gw.first(e.i,e.n);
1.1622 -// }
1.1623 -// else {
1.1624 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1625 -// gw.goNext(e.i);
1.1626 -// return e;
1.1627 -// }
1.1628 -// }
1.1629 -// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1.1630 -// */
1.1631 -// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1.1632 -
1.1633 -// //FIXME
1.1634 -// InEdgeIt& first(InEdgeIt& e, const Node& n) const
1.1635 -// {
1.1636 -// e.n=n;
1.1637 -// gw.first(e.i,n);
1.1638 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1639 -// gw.goNext(e.i);
1.1640 -// if(!gw.valid(e.i)) {
1.1641 -// gw.first(e.o,n);
1.1642 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1643 -// gw.goNext(e.o);
1.1644 -// }
1.1645 -// return e;
1.1646 -// }
1.1647 -// /*
1.1648 -// InEdgeIt &goNext(InEdgeIt &e)
1.1649 -// {
1.1650 -// if(gw.valid(e.i)) {
1.1651 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1652 -// gw.goNext(e.i);
1.1653 -// if(gw.valid(e.i)) return e;
1.1654 -// else gw.first(e.o,e.n);
1.1655 -// }
1.1656 -// else {
1.1657 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1658 -// gw.goNext(e.o);
1.1659 -// return e;
1.1660 -// }
1.1661 -// }
1.1662 -// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1.1663 -// */
1.1664 -// //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1.1665 -
1.1666 -// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1.1667 -// //template<typename I> I next(const I i); { return gw.goNext(i); }
1.1668 -
1.1669 -// template< typename It > It first() const {
1.1670 -// It e; first(e); return e; }
1.1671 -
1.1672 -// template< typename It > It first(Node v) const {
1.1673 -// It e; first(e, v); return e; }
1.1674 -
1.1675 -// Node target(const Edge& e) const { return gw.target(e); }
1.1676 -// Node source(const Edge& e) const { return gw.source(e); }
1.1677 -
1.1678 -// template<typename I> Node aNode(const I& e) const {
1.1679 -// return gw.aNode(e); }
1.1680 -// template<typename I> Node bNode(const I& e) const {
1.1681 -// return gw.bNode(e); }
1.1682 -
1.1683 -// //template<typename I> bool valid(const I i);
1.1684 -// //{ return gw.valid(i); }
1.1685 -
1.1686 -// //template<typename I> void setInvalid(const I &i);
1.1687 -// //{ return gw.setInvalid(i); }
1.1688 -
1.1689 -// Node addNode() { return gw.addNode(); }
1.1690 -// Edge addEdge(const Node& source, const Node& target) {
1.1691 -// return gw.addEdge(source, target); }
1.1692 -
1.1693 -// template<typename I> void erase(const I& i) { gw.erase(i); }
1.1694 -
1.1695 -// void clear() { gw.clear(); }
1.1696 -
1.1697 -// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1.1698 -// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1.1699 -
1.1700 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.1701 -// Graph& getGraph() { return (*graph); }
1.1702 -
1.1703 -// //ResGraphWrapper() : graph(0) { }
1.1704 -// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1705 -// };
1.1706 -
1.1707 -} //namespace lemon
1.1708 -
1.1709 -#endif //LEMON_GRAPH_WRAPPER_H
1.1710 -