1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/graph_wrapper.h Fri Apr 02 14:53:05 2004 +0000
1.3 @@ -0,0 +1,1708 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_GRAPH_WRAPPER_H
1.6 +#define HUGO_GRAPH_WRAPPER_H
1.7 +
1.8 +#include <invalid.h>
1.9 +
1.10 +namespace hugo {
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 head(const Edge& e) const { return graph->head(e); }
1.103 + Node tail(const Edge& e) const { return graph->tail(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& tail, const Node& head) const {
1.121 + return graph->addEdge(tail, head); }
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 GraphWrapperSkeleton {
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 GraphWrapperSkeleton<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 GraphWrapperSkeleton<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 GraphWrapperSkeleton<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 GraphWrapperSkeleton<GraphWrapper>& _G) :
1.223 + GraphWrapper::EdgeIt(_G.gw) { }
1.224 + };
1.225 +
1.226 +
1.227 + //GraphWrapperSkeleton() : gw() { }
1.228 + GraphWrapperSkeleton(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 head(const Edge& e) const { return gw.head(e); }
1.252 + Node tail(const Edge& e) const { return gw.tail(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& tail, const Node& head) const {
1.267 + return gw.addEdge(tail, head); }
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 GraphWrapperSkeleton<GraphWrapper>& _G) :
1.276 + GraphWrapper::NodeMap<T>(_G.gw) { }
1.277 + NodeMap(const GraphWrapperSkeleton<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 GraphWrapperSkeleton<GraphWrapper>& _G) :
1.284 + GraphWrapper::EdgeMap<T>(_G.gw) { }
1.285 + EdgeMap(const GraphWrapperSkeleton<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 head(const Edge& e) const { return graph->tail(e); }
1.329 +// Node tail(const Edge& e) const { return graph->head(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& tail, const Node& head) const {
1.344 +// return graph->addEdge(tail, head); }
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 GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
1.372 +// class RevGraphWrapper :
1.373 +// public GraphWrapper/*GraphWrapperSkeleton< 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 GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
1.385 +// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< 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/*GraphWrapperSkeleton< 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 head(const Edge& e) const { return graph->tail(e); }
1.410 +// //Node tail(const Edge& e) const { return graph->head(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& tail, const Node& head) const {
1.425 +// // return graph->addEdge(tail, head); }
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/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
1.436 +// {
1.437 +// public:
1.438 +// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.439 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
1.440 +// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.441 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
1.442 +// };
1.443 +
1.444 +// template<typename T> class EdgeMap :
1.445 +// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
1.446 +// public:
1.447 +// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.448 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
1.449 +// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.450 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
1.451 +// };
1.452 +// };
1.453 +
1.454 +
1.455 + template<typename GraphWrapper>
1.456 + class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.457 + public:
1.458 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.459 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.460 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
1.461 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
1.462 +
1.463 + RevGraphWrapper(GraphWrapper _gw) :
1.464 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.465 +
1.466 + Node head(const Edge& e) const
1.467 + { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
1.468 + Node tail(const Edge& e) const
1.469 + { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
1.470 + };
1.471 +
1.472 + //Subgraph on the same node-set and partial edge-set
1.473 + template<typename GraphWrapper, typename EdgeFilterMap>
1.474 + class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.475 + protected:
1.476 + EdgeFilterMap* filter_map;
1.477 + public:
1.478 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.479 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.480 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.481 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
1.482 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
1.483 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.484 +
1.485 + SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
1.486 + GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
1.487 +
1.488 + template<typename I> I& first(I& i) const {
1.489 + gw.first(i);
1.490 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.491 + return i;
1.492 + }
1.493 + template<typename I, typename P> I& first(I& i, const P& p) const {
1.494 + gw.first(i, p);
1.495 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.496 + return i;
1.497 + }
1.498 +
1.499 + //template<typename I> I getNext(const I& i) const {
1.500 + // return gw.getNext(i);
1.501 + //}
1.502 + template<typename I> I& next(I &i) const {
1.503 + gw.next(i);
1.504 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.505 + return i;
1.506 + }
1.507 +
1.508 + template< typename It > It first() const {
1.509 + It e; this->first(e); return e; }
1.510 +
1.511 + template< typename It > It first(const Node& v) const {
1.512 + It e; this->first(e, v); return e; }
1.513 + };
1.514 +
1.515 +// template<typename GraphWrapper>
1.516 +// class UndirGraphWrapper {
1.517 +// protected:
1.518 +// //Graph* graph;
1.519 +// GraphWrapper gw;
1.520 +
1.521 +// public:
1.522 +// typedef GraphWrapper BaseGraph;
1.523 +
1.524 +// typedef typename GraphWrapper::Node Node;
1.525 +// typedef typename GraphWrapper::NodeIt NodeIt;
1.526 +
1.527 +// //typedef typename Graph::Edge Edge;
1.528 +// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.529 +// //typedef typename Graph::InEdgeIt InEdgeIt;
1.530 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.531 +// //typedef typename Graph::EdgeIt EdgeIt;
1.532 +
1.533 +// //private:
1.534 +// typedef typename GraphWrapper::Edge GraphEdge;
1.535 +// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.536 +// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.537 +// //public:
1.538 +
1.539 +// //UndirGraphWrapper() : graph(0) { }
1.540 +// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.541 +
1.542 +// //void setGraph(Graph& _graph) { graph = &_graph; }
1.543 +// //Graph& getGraph() const { return (*graph); }
1.544 +
1.545 +// class Edge {
1.546 +// friend class UndirGraphWrapper<GraphWrapper>;
1.547 +// bool out_or_in; //true iff out
1.548 +// GraphOutEdgeIt out;
1.549 +// GraphInEdgeIt in;
1.550 +// public:
1.551 +// Edge() : out_or_in(), out(), in() { }
1.552 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.553 +// operator GraphEdge() const {
1.554 +// if (out_or_in) return(out); else return(in);
1.555 +// }
1.556 +// friend bool operator==(const Edge& u, const Edge& v) {
1.557 +// if (v.out_or_in)
1.558 +// return (u.out_or_in && u.out==v.out);
1.559 +// else
1.560 +// return (!u.out_or_in && u.in==v.in);
1.561 +// }
1.562 +// friend bool operator!=(const Edge& u, const Edge& v) {
1.563 +// if (v.out_or_in)
1.564 +// return (!u.out_or_in || u.out!=v.out);
1.565 +// else
1.566 +// return (u.out_or_in || u.in!=v.in);
1.567 +// }
1.568 +// };
1.569 +
1.570 +// class OutEdgeIt : public Edge {
1.571 +// friend class UndirGraphWrapper<GraphWrapper>;
1.572 +// public:
1.573 +// OutEdgeIt() : Edge() { }
1.574 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.575 +// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.576 +// : Edge() {
1.577 +// out_or_in=true;
1.578 +// _G.gw.first(out, n);
1.579 +// if (!(_G.gw.valid(out))) {
1.580 +// out_or_in=false;
1.581 +// _G.gw.first(in, n);
1.582 +// }
1.583 +// }
1.584 +// };
1.585 +
1.586 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.587 +// e.out_or_in=true;
1.588 +// gw.first(e.out, n);
1.589 +// if (!(gw.valid(e.out))) {
1.590 +// e.out_or_in=false;
1.591 +// gw.first(e.in, n);
1.592 +// }
1.593 +// return e;
1.594 +// }
1.595 +
1.596 +// OutEdgeIt& next(OutEdgeIt& e) const {
1.597 +// if (e.out_or_in) {
1.598 +// Node n=gw.tail(e.out);
1.599 +// gw.next(e.out);
1.600 +// if (!gw.valid(e.out)) {
1.601 +// e.out_or_in=false;
1.602 +// gw.first(e.in, n);
1.603 +// }
1.604 +// } else {
1.605 +// gw.next(e.in);
1.606 +// }
1.607 +// return e;
1.608 +// }
1.609 +
1.610 +// Node aNode(const OutEdgeIt& e) const {
1.611 +// if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.612 +// Node bNode(const OutEdgeIt& e) const {
1.613 +// if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.614 +
1.615 +// typedef OutEdgeIt InEdgeIt;
1.616 +
1.617 +// template<typename I> I& first(I& i) const { return gw.first(i); }
1.618 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.619 +// // return graph->first(i, p); }
1.620 +
1.621 +// template<typename I> I getNext(const I& i) const {
1.622 +// return gw.getNext(i); }
1.623 +// template<typename I> I& next(I &i) const { return gw.next(i); }
1.624 +
1.625 +// template< typename It > It first() const {
1.626 +// It e; first(e); return e; }
1.627 +
1.628 +// template< typename It > It first(const Node& v) const {
1.629 +// It e; first(e, v); return e; }
1.630 +
1.631 +// Node head(const Edge& e) const { return gw.head(e); }
1.632 +// Node tail(const Edge& e) const { return gw.tail(e); }
1.633 +
1.634 +// template<typename I> bool valid(const I& i) const
1.635 +// { return gw.valid(i); }
1.636 +
1.637 +// //template<typename I> void setInvalid(const I &i);
1.638 +// //{ return graph->setInvalid(i); }
1.639 +
1.640 +// int nodeNum() const { return gw.nodeNum(); }
1.641 +// int edgeNum() const { return gw.edgeNum(); }
1.642 +
1.643 +// // template<typename I> Node aNode(const I& e) const {
1.644 +// // return graph->aNode(e); }
1.645 +// // template<typename I> Node bNode(const I& e) const {
1.646 +// // return graph->bNode(e); }
1.647 +
1.648 +// Node addNode() const { return gw.addNode(); }
1.649 +// // FIXME: ez igy nem jo, mert nem
1.650 +// // Edge addEdge(const Node& tail, const Node& head) const {
1.651 +// // return graph->addEdge(tail, head); }
1.652 +
1.653 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.654 +
1.655 +// void clear() const { gw.clear(); }
1.656 +
1.657 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.658 +// public:
1.659 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.660 +// GraphWrapper::NodeMap<T>(_G.gw) { }
1.661 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.662 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.663 +// };
1.664 +
1.665 +// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.666 +// public:
1.667 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.668 +// GraphWrapper::EdgeMap<T>(_G.gw) { }
1.669 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.670 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.671 +// };
1.672 +// };
1.673 +
1.674 +
1.675 + template<typename GraphWrapper>
1.676 + class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.677 + protected:
1.678 +// GraphWrapper gw;
1.679 +
1.680 + public:
1.681 + //typedef GraphWrapper BaseGraph;
1.682 +
1.683 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.684 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.685 +
1.686 + //private:
1.687 + //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
1.688 + //legyenek, at kell irni
1.689 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.690 + GraphWrapper::Edge GraphEdge;
1.691 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.692 + GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.693 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.694 + GraphWrapper::InEdgeIt GraphInEdgeIt;
1.695 + //public:
1.696 +
1.697 + //UndirGraphWrapper() : graph(0) { }
1.698 + UndirGraphWrapper(GraphWrapper _gw) :
1.699 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.700 +
1.701 + //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.702 +
1.703 + //void setGraph(Graph& _graph) { graph = &_graph; }
1.704 + //Graph& getGraph() const { return (*graph); }
1.705 +
1.706 + class Edge {
1.707 + friend class UndirGraphWrapper<GraphWrapper>;
1.708 + bool out_or_in; //true iff out
1.709 + GraphOutEdgeIt out;
1.710 + GraphInEdgeIt in;
1.711 + public:
1.712 + Edge() : out_or_in(), out(), in() { }
1.713 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.714 + operator GraphEdge() const {
1.715 + if (out_or_in) return(out); else return(in);
1.716 + }
1.717 +//FIXME
1.718 +//2 edges are equal if they "refer" to the same physical edge
1.719 +//is it good?
1.720 + friend bool operator==(const Edge& u, const Edge& v) {
1.721 + if (v.out_or_in)
1.722 + if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.723 + //return (u.out_or_in && u.out==v.out);
1.724 + else
1.725 + if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.726 + //return (!u.out_or_in && u.in==v.in);
1.727 + }
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 + };
1.737 +
1.738 + class OutEdgeIt : public Edge {
1.739 + friend class UndirGraphWrapper<GraphWrapper>;
1.740 + public:
1.741 + OutEdgeIt() : Edge() { }
1.742 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.743 + OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.744 + : Edge() {
1.745 + out_or_in=true; _G.gw.first(out, n);
1.746 + if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
1.747 + }
1.748 + };
1.749 +
1.750 + typedef OutEdgeIt InEdgeIt;
1.751 +
1.752 + class EdgeIt : public Edge {
1.753 + friend class UndirGraphWrapper<GraphWrapper>;
1.754 + protected:
1.755 + NodeIt v;
1.756 + public:
1.757 + EdgeIt() : Edge() { }
1.758 + EdgeIt(const Invalid& i) : Edge(i) { }
1.759 + EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
1.760 + : Edge() {
1.761 + out_or_in=true;
1.762 + //Node v;
1.763 + _G.first(v);
1.764 + if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
1.765 + while (_G.valid(v) && !_G.gw.valid(out)) {
1.766 + _G.gw.next(v);
1.767 + if (_G.valid(v)) _G.gw.first(out);
1.768 + }
1.769 + }
1.770 + };
1.771 +
1.772 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.773 + e.out_or_in=true; gw.first(e.out, n);
1.774 + if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
1.775 + return e;
1.776 + }
1.777 +
1.778 + EdgeIt& first(EdgeIt& e) const {
1.779 + e.out_or_in=true;
1.780 + //NodeIt v;
1.781 + first(e.v);
1.782 + if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
1.783 + while (valid(e.v) && !gw.valid(e.out)) {
1.784 + gw.next(e.v);
1.785 + if (valid(e.v)) gw.first(e.out, e.v);
1.786 + }
1.787 + return e;
1.788 + }
1.789 +
1.790 + template<typename I> I& first(I& i) const { gw.first(i); return i; }
1.791 + template<typename I, typename P> I& first(I& i, const P& p) const {
1.792 + gw.first(i, p); return i; }
1.793 +
1.794 + OutEdgeIt& next(OutEdgeIt& e) const {
1.795 + if (e.out_or_in) {
1.796 + Node n=gw.tail(e.out);
1.797 + gw.next(e.out);
1.798 + if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
1.799 + } else {
1.800 + gw.next(e.in);
1.801 + }
1.802 + return e;
1.803 + }
1.804 +
1.805 + EdgeIt& next(EdgeIt& e) const {
1.806 + //NodeIt v=tail(e);
1.807 + gw.next(e.out);
1.808 + while (valid(e.v) && !gw.valid(e.out)) {
1.809 + next(e.v);
1.810 + if (valid(e.v)) gw.first(e.out, e.v);
1.811 + }
1.812 + return e;
1.813 + }
1.814 +
1.815 + template<typename I> I& next(I &i) const { return gw.next(i); }
1.816 +// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.817 +
1.818 + template< typename It > It first() const {
1.819 + It e; first(e); return e; }
1.820 +
1.821 + template< typename It > It first(const Node& v) const {
1.822 + It e; first(e, v); return e; }
1.823 +
1.824 +// Node head(const Edge& e) const { return gw.head(e); }
1.825 +// Node tail(const Edge& e) const { return gw.tail(e); }
1.826 +
1.827 +// template<typename I> bool valid(const I& i) const
1.828 +// { return gw.valid(i); }
1.829 +
1.830 +// int nodeNum() const { return gw.nodeNum(); }
1.831 +// int edgeNum() const { return gw.edgeNum(); }
1.832 +
1.833 +// template<typename I> Node aNode(const I& e) const {
1.834 +// return graph->aNode(e); }
1.835 +// template<typename I> Node bNode(const I& e) const {
1.836 +// return graph->bNode(e); }
1.837 +
1.838 + Node aNode(const OutEdgeIt& e) const {
1.839 + if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.840 + Node bNode(const OutEdgeIt& e) const {
1.841 + if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.842 +
1.843 +// Node addNode() const { return gw.addNode(); }
1.844 +
1.845 +// FIXME: ez igy nem jo, mert nem
1.846 +// Edge addEdge(const Node& tail, const Node& head) const {
1.847 +// return graph->addEdge(tail, head); }
1.848 +
1.849 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.850 +
1.851 +// void clear() const { gw.clear(); }
1.852 +
1.853 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.854 +// public:
1.855 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.856 +// GraphWrapper::NodeMap<T>(_G.gw) { }
1.857 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.858 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.859 +// };
1.860 +
1.861 +// template<typename T> class EdgeMap :
1.862 +// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
1.863 +// public:
1.864 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.865 +// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
1.866 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.867 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.868 +// };
1.869 + };
1.870 +
1.871 +
1.872 +
1.873 +
1.874 +
1.875 +// template<typename Graph>
1.876 +// class SymGraphWrapper
1.877 +// {
1.878 +// Graph* graph;
1.879 +
1.880 +// public:
1.881 +// typedef Graph BaseGraph;
1.882 +
1.883 +// typedef typename Graph::Node Node;
1.884 +// typedef typename Graph::Edge Edge;
1.885 +
1.886 +// typedef typename Graph::NodeIt NodeIt;
1.887 +
1.888 +// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.889 +// //iranyitatlant, ami van
1.890 +// //mert csak 1 dolgot lehet be typedef-elni
1.891 +// typedef typename Graph::OutEdgeIt SymEdgeIt;
1.892 +// //typedef typename Graph::InEdgeIt SymEdgeIt;
1.893 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.894 +// typedef typename Graph::EdgeIt EdgeIt;
1.895 +
1.896 +// int nodeNum() const { return graph->nodeNum(); }
1.897 +// int edgeNum() const { return graph->edgeNum(); }
1.898 +
1.899 +// template<typename I> I& first(I& i) const { return graph->first(i); }
1.900 +// template<typename I, typename P> I& first(I& i, const P& p) const {
1.901 +// return graph->first(i, p); }
1.902 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.903 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.904 +
1.905 +// template< typename It > It first() const {
1.906 +// It e; first(e); return e; }
1.907 +
1.908 +// template< typename It > It first(Node v) const {
1.909 +// It e; first(e, v); return e; }
1.910 +
1.911 +// Node head(const Edge& e) const { return graph->head(e); }
1.912 +// Node tail(const Edge& e) const { return graph->tail(e); }
1.913 +
1.914 +// template<typename I> Node aNode(const I& e) const {
1.915 +// return graph->aNode(e); }
1.916 +// template<typename I> Node bNode(const I& e) const {
1.917 +// return graph->bNode(e); }
1.918 +
1.919 +// //template<typename I> bool valid(const I i);
1.920 +// //{ return graph->valid(i); }
1.921 +
1.922 +// //template<typename I> void setInvalid(const I &i);
1.923 +// //{ return graph->setInvalid(i); }
1.924 +
1.925 +// Node addNode() { return graph->addNode(); }
1.926 +// Edge addEdge(const Node& tail, const Node& head) {
1.927 +// return graph->addEdge(tail, head); }
1.928 +
1.929 +// template<typename I> void erase(const I& i) { graph->erase(i); }
1.930 +
1.931 +// void clear() { graph->clear(); }
1.932 +
1.933 +// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.934 +// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.935 +
1.936 +// void setGraph(Graph& _graph) { graph = &_graph; }
1.937 +// Graph& getGraph() { return (*graph); }
1.938 +
1.939 +// //SymGraphWrapper() : graph(0) { }
1.940 +// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.941 +// };
1.942 +
1.943 +
1.944 + template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1.945 + class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
1.946 + public:
1.947 + //typedef Graph BaseGraph;
1.948 + //typedef TrivGraphWrapper<const Graph> GraphWrapper;
1.949 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.950 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.951 + private:
1.952 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.953 + GraphWrapper::OutEdgeIt OldOutEdgeIt;
1.954 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.955 + GraphWrapper::InEdgeIt OldInEdgeIt;
1.956 +
1.957 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.958 + GraphWrapper::Edge OldEdge;
1.959 + protected:
1.960 + //const Graph* graph;
1.961 + //GraphWrapper gw;
1.962 + FlowMap* flow;
1.963 + const CapacityMap* capacity;
1.964 + public:
1.965 +
1.966 + ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
1.967 + const CapacityMap& _capacity) :
1.968 + GraphWrapperSkeleton<GraphWrapper>(_gw),
1.969 + flow(&_flow), capacity(&_capacity) { }
1.970 +
1.971 + //void setGraph(const Graph& _graph) { graph = &_graph; }
1.972 + //const Graph& getGraph() const { return (*graph); }
1.973 +
1.974 + class Edge;
1.975 + class OutEdgeIt;
1.976 + friend class Edge;
1.977 + friend class OutEdgeIt;
1.978 +
1.979 + class Edge {
1.980 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.981 + protected:
1.982 + bool out_or_in; //true, iff out
1.983 + OldOutEdgeIt out;
1.984 + OldInEdgeIt in;
1.985 + public:
1.986 + Edge() : out_or_in(true) { }
1.987 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.988 +// bool valid() const {
1.989 +// return out_or_in && out.valid() || in.valid(); }
1.990 + friend bool operator==(const Edge& u, const Edge& v) {
1.991 + if (v.out_or_in)
1.992 + return (u.out_or_in && u.out==v.out);
1.993 + else
1.994 + return (!u.out_or_in && u.in==v.in);
1.995 + }
1.996 + friend bool operator!=(const Edge& u, const Edge& v) {
1.997 + if (v.out_or_in)
1.998 + return (!u.out_or_in || u.out!=v.out);
1.999 + else
1.1000 + return (u.out_or_in || u.in!=v.in);
1.1001 + }
1.1002 + operator OldEdge() {
1.1003 + if(out_or_in)
1.1004 + return out;
1.1005 + else
1.1006 + return in;
1.1007 + }
1.1008 + };
1.1009 +
1.1010 +
1.1011 + class OutEdgeIt : public Edge {
1.1012 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1013 + public:
1.1014 + OutEdgeIt() { }
1.1015 + //FIXME
1.1016 + OutEdgeIt(const Edge& e) : Edge(e) { }
1.1017 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1018 + protected:
1.1019 + OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1020 + resG.gw.first(out, v);
1.1021 + while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1022 + if (!resG.gw.valid(out)) {
1.1023 + out_or_in=0;
1.1024 + resG.gw.first(in, v);
1.1025 + while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1026 + }
1.1027 + }
1.1028 +// public:
1.1029 +// OutEdgeIt& operator++() {
1.1030 +// if (out_or_in) {
1.1031 +// Node v=/*resG->*/G->aNode(out);
1.1032 +// ++out;
1.1033 +// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1034 +// if (!out.valid()) {
1.1035 +// out_or_in=0;
1.1036 +// G->first(in, v);
1.1037 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1038 +// }
1.1039 +// } else {
1.1040 +// ++in;
1.1041 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1042 +// }
1.1043 +// return *this;
1.1044 +// }
1.1045 + };
1.1046 +
1.1047 + //FIXME This is just for having InEdgeIt
1.1048 + typedef void InEdgeIt;
1.1049 +
1.1050 + class EdgeIt : public Edge {
1.1051 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1052 + NodeIt v;
1.1053 + public:
1.1054 + EdgeIt() { }
1.1055 + //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1056 + EdgeIt(const Invalid& i) : Edge(i) { }
1.1057 + EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1058 + resG.gw.first(v);
1.1059 + if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
1.1060 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1061 + while (resG.gw.valid(v) && !resG.gw.valid(out)) {
1.1062 + resG.gw.next(v);
1.1063 + if (resG.gw.valid(v)) resG.gw.first(out, v);
1.1064 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1065 + }
1.1066 + if (!resG.gw.valid(out)) {
1.1067 + out_or_in=0;
1.1068 + resG.gw.first(v);
1.1069 + if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
1.1070 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1071 + while (resG.gw.valid(v) && !resG.gw.valid(in)) {
1.1072 + resG.gw.next(v);
1.1073 + if (resG.gw.valid(v)) resG.gw.first(in, v);
1.1074 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1075 + }
1.1076 + }
1.1077 + }
1.1078 +// EdgeIt& operator++() {
1.1079 +// if (out_or_in) {
1.1080 +// ++out;
1.1081 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1082 +// while (v.valid() && !out.valid()) {
1.1083 +// ++v;
1.1084 +// if (v.valid()) G->first(out, v);
1.1085 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1086 +// }
1.1087 +// if (!out.valid()) {
1.1088 +// out_or_in=0;
1.1089 +// G->first(v);
1.1090 +// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1.1091 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1092 +// while (v.valid() && !in.valid()) {
1.1093 +// ++v;
1.1094 +// if (v.valid()) G->first(in, v);
1.1095 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1096 +// }
1.1097 +// }
1.1098 +// } else {
1.1099 +// ++in;
1.1100 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1101 +// while (v.valid() && !in.valid()) {
1.1102 +// ++v;
1.1103 +// if (v.valid()) G->first(in, v);
1.1104 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1105 +// }
1.1106 +// }
1.1107 +// return *this;
1.1108 +// }
1.1109 + };
1.1110 +
1.1111 + NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
1.1112 + OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.1113 + e=OutEdgeIt(*this, v);
1.1114 + return e;
1.1115 + }
1.1116 + EdgeIt& first(EdgeIt& e) const {
1.1117 + e=EdgeIt(*this);
1.1118 + return e;
1.1119 + }
1.1120 +
1.1121 + NodeIt& next(NodeIt& n) const { return gw.next(n); }
1.1122 +
1.1123 + OutEdgeIt& next(OutEdgeIt& e) const {
1.1124 + if (e.out_or_in) {
1.1125 + Node v=gw.aNode(e.out);
1.1126 + gw.next(e.out);
1.1127 + while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1128 + if (!gw.valid(e.out)) {
1.1129 + e.out_or_in=0;
1.1130 + gw.first(e.in, v);
1.1131 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1132 + }
1.1133 + } else {
1.1134 + gw.next(e.in);
1.1135 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1136 + }
1.1137 + return e;
1.1138 + }
1.1139 +
1.1140 + EdgeIt& next(EdgeIt& e) const {
1.1141 + if (e.out_or_in) {
1.1142 + gw.next(e.out);
1.1143 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1144 + while (gw.valid(e.v) && !gw.valid(e.out)) {
1.1145 + gw.next(e.v);
1.1146 + if (gw.valid(e.v)) gw.first(e.out, e.v);
1.1147 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1148 + }
1.1149 + if (!gw.valid(e.out)) {
1.1150 + e.out_or_in=0;
1.1151 + gw.first(e.v);
1.1152 + if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
1.1153 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1154 + while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1155 + gw.next(e.v);
1.1156 + if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1157 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1158 + }
1.1159 + }
1.1160 + } else {
1.1161 + gw.next(e.in);
1.1162 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1163 + while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1164 + gw.next(e.v);
1.1165 + if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1166 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1167 + }
1.1168 + }
1.1169 + return e;
1.1170 + }
1.1171 +
1.1172 +
1.1173 + template< typename It >
1.1174 + It first() const {
1.1175 + It e;
1.1176 + first(e);
1.1177 + return e;
1.1178 + }
1.1179 +
1.1180 + template< typename It >
1.1181 + It first(Node v) const {
1.1182 + It e;
1.1183 + first(e, v);
1.1184 + return e;
1.1185 + }
1.1186 +
1.1187 + Node tail(Edge e) const {
1.1188 + return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1189 + Node head(Edge e) const {
1.1190 + return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1191 +
1.1192 + Node aNode(OutEdgeIt e) const {
1.1193 + return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1194 + Node bNode(OutEdgeIt e) const {
1.1195 + return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1196 +
1.1197 + int nodeNum() const { return gw.nodeNum(); }
1.1198 + //FIXME
1.1199 + //int edgeNum() const { return gw.edgeNum(); }
1.1200 +
1.1201 +
1.1202 + int id(Node v) const { return gw.id(v); }
1.1203 +
1.1204 + bool valid(Node n) const { return gw.valid(n); }
1.1205 + bool valid(Edge e) const {
1.1206 + return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1.1207 +
1.1208 + void augment(const Edge& e, Number a) const {
1.1209 + if (e.out_or_in)
1.1210 + flow->set(e.out, flow->get(e.out)+a);
1.1211 + else
1.1212 + flow->set(e.in, flow->get(e.in)-a);
1.1213 + }
1.1214 +
1.1215 + Number resCap(const Edge& e) const {
1.1216 + if (e.out_or_in)
1.1217 + return (capacity->get(e.out)-flow->get(e.out));
1.1218 + else
1.1219 + return (flow->get(e.in));
1.1220 + }
1.1221 +
1.1222 + Number resCap(OldOutEdgeIt out) const {
1.1223 + return ( (*capacity)[out] - (*flow)[out]);
1.1224 + }
1.1225 +
1.1226 + Number resCap(OldInEdgeIt in) const {
1.1227 + return ( (*flow)[in] );
1.1228 + }
1.1229 +
1.1230 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.1231 +// public:
1.1232 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
1.1233 +// : GraphWrapper::NodeMap<T>(_G.gw) { }
1.1234 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
1.1235 +// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.1236 +// };
1.1237 +
1.1238 +// template <typename T>
1.1239 +// class NodeMap {
1.1240 +// typename Graph::NodeMap<T> node_map;
1.1241 +// public:
1.1242 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1.1243 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1.1244 +// void set(Node nit, T a) { node_map.set(nit, a); }
1.1245 +// T get(Node nit) const { return node_map.get(nit); }
1.1246 +// };
1.1247 +
1.1248 + template <typename T>
1.1249 + class EdgeMap {
1.1250 + typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1.1251 + public:
1.1252 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1.1253 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1.1254 + void set(Edge e, T a) {
1.1255 + if (e.out_or_in)
1.1256 + forward_map.set(e.out, a);
1.1257 + else
1.1258 + backward_map.set(e.in, a);
1.1259 + }
1.1260 + T get(Edge e) {
1.1261 + if (e.out_or_in)
1.1262 + return forward_map.get(e.out);
1.1263 + else
1.1264 + return backward_map.get(e.in);
1.1265 + }
1.1266 + };
1.1267 + };
1.1268 +
1.1269 + //Subgraph on the same node-set and partial edge-set
1.1270 + template<typename GraphWrapper, typename FirstOutEdgesMap>
1.1271 + class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.1272 + protected:
1.1273 + FirstOutEdgesMap* first_out_edges;
1.1274 + public:
1.1275 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.1276 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.1277 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.1278 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
1.1279 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
1.1280 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.1281 +
1.1282 + ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
1.1283 + GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
1.1284 +
1.1285 + template<typename I> I& first(I& i) const {
1.1286 + gw.first(i);
1.1287 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1288 + return i;
1.1289 + }
1.1290 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1291 + e=first_out_edges->get(n);
1.1292 + return e;
1.1293 + }
1.1294 + template<typename I, typename P> I& first(I& i, const P& p) const {
1.1295 + gw.first(i, p);
1.1296 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1297 + return i;
1.1298 + }
1.1299 +
1.1300 + //template<typename I> I getNext(const I& i) const {
1.1301 + // return gw.getNext(i);
1.1302 + //}
1.1303 + template<typename I> I& next(I &i) const {
1.1304 + gw.next(i);
1.1305 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1306 + return i;
1.1307 + }
1.1308 +
1.1309 + template< typename It > It first() const {
1.1310 + It e; this->first(e); return e; }
1.1311 +
1.1312 + template< typename It > It first(const Node& v) const {
1.1313 + It e; this->first(e, v); return e; }
1.1314 +
1.1315 + void erase(const OutEdgeIt& e) const {
1.1316 + OutEdgeIt f=e;
1.1317 + this->next(f);
1.1318 + first_out_edges->set(this->tail(e), f);
1.1319 + }
1.1320 + };
1.1321 +
1.1322 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1323 +// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1324 +// protected:
1.1325 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1326 +// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1327 +// public:
1.1328 +// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1329 +// const CapacityMap& _capacity) :
1.1330 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1.1331 +// first_out_edges(*this) /*, dist(*this)*/ {
1.1332 +// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1.1333 +// OutEdgeIt e;
1.1334 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1335 +// first_out_edges.set(n, e);
1.1336 +// }
1.1337 +// }
1.1338 +
1.1339 +// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1340 +// //Graph& getGraph() const { return (*graph); }
1.1341 +
1.1342 +// //TrivGraphWrapper() : graph(0) { }
1.1343 +// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1344 +
1.1345 +// //typedef Graph BaseGraph;
1.1346 +
1.1347 +// //typedef typename Graph::Node Node;
1.1348 +// //typedef typename Graph::NodeIt NodeIt;
1.1349 +
1.1350 +// //typedef typename Graph::Edge Edge;
1.1351 +// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1352 +// //typedef typename Graph::InEdgeIt InEdgeIt;
1.1353 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1354 +// //typedef typename Graph::EdgeIt EdgeIt;
1.1355 +
1.1356 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1357 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1358 +
1.1359 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1360 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1361 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1362 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1363 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1364 +
1.1365 +// NodeIt& first(NodeIt& n) const {
1.1366 +// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1367 +// }
1.1368 +
1.1369 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1370 +// e=first_out_edges.get(n);
1.1371 +// return e;
1.1372 +// }
1.1373 +
1.1374 +// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1.1375 +// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1.1376 +// // return first(i, p); }
1.1377 +
1.1378 +// //template<typename I> I getNext(const I& i) const {
1.1379 +// // return gw.getNext(i); }
1.1380 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1381 +
1.1382 +// template< typename It > It first() const {
1.1383 +// It e; first(e); return e; }
1.1384 +
1.1385 +// template< typename It > It first(const Node& v) const {
1.1386 +// It e; first(e, v); return e; }
1.1387 +
1.1388 +// //Node head(const Edge& e) const { return gw.head(e); }
1.1389 +// //Node tail(const Edge& e) const { return gw.tail(e); }
1.1390 +
1.1391 +// //template<typename I> bool valid(const I& i) const
1.1392 +// // { return gw.valid(i); }
1.1393 +
1.1394 +// //int nodeNum() const { return gw.nodeNum(); }
1.1395 +// //int edgeNum() const { return gw.edgeNum(); }
1.1396 +
1.1397 +// //template<typename I> Node aNode(const I& e) const {
1.1398 +// // return gw.aNode(e); }
1.1399 +// //template<typename I> Node bNode(const I& e) const {
1.1400 +// // return gw.bNode(e); }
1.1401 +
1.1402 +// //Node addNode() const { return gw.addNode(); }
1.1403 +// //Edge addEdge(const Node& tail, const Node& head) const {
1.1404 +// // return gw.addEdge(tail, head); }
1.1405 +
1.1406 +// //void erase(const OutEdgeIt& e) {
1.1407 +// // first_out_edge(this->tail(e))=e;
1.1408 +// //}
1.1409 +// void erase(const Edge& e) {
1.1410 +// OutEdgeIt f(e);
1.1411 +// next(f);
1.1412 +// first_out_edges.set(this->tail(e), f);
1.1413 +// }
1.1414 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1415 +
1.1416 +// //void clear() const { gw.clear(); }
1.1417 +
1.1418 +// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1419 +// public:
1.1420 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1421 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1422 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1423 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1424 +// };
1.1425 +
1.1426 +// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1427 +// public:
1.1428 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1429 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1430 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1431 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1432 +// };
1.1433 +// };
1.1434 +
1.1435 +// template<typename GraphWrapper>
1.1436 +// class FilterGraphWrapper {
1.1437 +// };
1.1438 +
1.1439 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1440 +// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1441 +
1.1442 +// //Graph* graph;
1.1443 +
1.1444 +// public:
1.1445 +// //typedef Graph BaseGraph;
1.1446 +
1.1447 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1448 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1449 +
1.1450 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1451 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1452 +// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1453 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1454 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1455 +
1.1456 +// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1457 +
1.1458 +// public:
1.1459 +// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1460 +// const CapacityMap& _capacity) :
1.1461 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1.1462 +// }
1.1463 +
1.1464 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1465 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1466 +// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1.1467 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1468 +// return e;
1.1469 +// }
1.1470 +
1.1471 +// NodeIt& next(NodeIt& e) const {
1.1472 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1473 +// }
1.1474 +
1.1475 +// OutEdgeIt& next(OutEdgeIt& e) const {
1.1476 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1477 +// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1.1478 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1479 +// return e;
1.1480 +// }
1.1481 +
1.1482 +// NodeIt& first(NodeIt& n) const {
1.1483 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1484 +// }
1.1485 +
1.1486 +// void erase(const Edge& e) {
1.1487 +// OutEdgeIt f(e);
1.1488 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1489 +// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1.1490 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1491 +// first_out_edges.set(this->tail(e), f);
1.1492 +// }
1.1493 +
1.1494 +// //TrivGraphWrapper() : graph(0) { }
1.1495 +// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1496 +
1.1497 +// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1498 +// //Graph& getGraph() const { return (*graph); }
1.1499 +
1.1500 +// //template<typename I> I& first(I& i) const { return gw.first(i); }
1.1501 +// //template<typename I, typename P> I& first(I& i, const P& p) const {
1.1502 +// // return gw.first(i, p); }
1.1503 +
1.1504 +// //template<typename I> I getNext(const I& i) const {
1.1505 +// // return gw.getNext(i); }
1.1506 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1507 +
1.1508 +// template< typename It > It first() const {
1.1509 +// It e; first(e); return e; }
1.1510 +
1.1511 +// template< typename It > It first(const Node& v) const {
1.1512 +// It e; first(e, v); return e; }
1.1513 +
1.1514 +// //Node head(const Edge& e) const { return gw.head(e); }
1.1515 +// //Node tail(const Edge& e) const { return gw.tail(e); }
1.1516 +
1.1517 +// //template<typename I> bool valid(const I& i) const
1.1518 +// // { return gw.valid(i); }
1.1519 +
1.1520 +// //template<typename I> void setInvalid(const I &i);
1.1521 +// //{ return gw.setInvalid(i); }
1.1522 +
1.1523 +// //int nodeNum() const { return gw.nodeNum(); }
1.1524 +// //int edgeNum() const { return gw.edgeNum(); }
1.1525 +
1.1526 +// //template<typename I> Node aNode(const I& e) const {
1.1527 +// // return gw.aNode(e); }
1.1528 +// //template<typename I> Node bNode(const I& e) const {
1.1529 +// // return gw.bNode(e); }
1.1530 +
1.1531 +// //Node addNode() const { return gw.addNode(); }
1.1532 +// //Edge addEdge(const Node& tail, const Node& head) const {
1.1533 +// // return gw.addEdge(tail, head); }
1.1534 +
1.1535 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1536 +
1.1537 +// //void clear() const { gw.clear(); }
1.1538 +
1.1539 +// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1540 +// public:
1.1541 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1542 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1543 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1544 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1545 +// };
1.1546 +
1.1547 +// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1548 +// public:
1.1549 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1550 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1551 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1552 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1553 +// };
1.1554 +
1.1555 +// public:
1.1556 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1557 +
1.1558 +// };
1.1559 +
1.1560 +
1.1561 +
1.1562 +// // FIXME: comparison should be made better!!!
1.1563 +// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.1564 +// class ResGraphWrapper
1.1565 +// {
1.1566 +// Graph* graph;
1.1567 +
1.1568 +// public:
1.1569 +// typedef Graph BaseGraph;
1.1570 +
1.1571 +// typedef typename Graph::Node Node;
1.1572 +// typedef typename Graph::Edge Edge;
1.1573 +
1.1574 +// typedef typename Graph::NodeIt NodeIt;
1.1575 +
1.1576 +// class OutEdgeIt {
1.1577 +// public:
1.1578 +// //Graph::Node n;
1.1579 +// bool out_or_in;
1.1580 +// typename Graph::OutEdgeIt o;
1.1581 +// typename Graph::InEdgeIt i;
1.1582 +// };
1.1583 +// class InEdgeIt {
1.1584 +// public:
1.1585 +// //Graph::Node n;
1.1586 +// bool out_or_in;
1.1587 +// typename Graph::OutEdgeIt o;
1.1588 +// typename Graph::InEdgeIt i;
1.1589 +// };
1.1590 +// typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1591 +// typedef typename Graph::EdgeIt EdgeIt;
1.1592 +
1.1593 +// int nodeNum() const { return gw.nodeNum(); }
1.1594 +// int edgeNum() const { return gw.edgeNum(); }
1.1595 +
1.1596 +// Node& first(Node& n) const { return gw.first(n); }
1.1597 +
1.1598 +// // Edge and SymEdge is missing!!!!
1.1599 +// // Edge <-> In/OutEdgeIt conversion is missing!!!!
1.1600 +
1.1601 +// //FIXME
1.1602 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1.1603 +// {
1.1604 +// e.n=n;
1.1605 +// gw.first(e.o,n);
1.1606 +// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1607 +// gw.goNext(e.o);
1.1608 +// if(!gw.valid(e.o)) {
1.1609 +// gw.first(e.i,n);
1.1610 +// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1611 +// gw.goNext(e.i);
1.1612 +// }
1.1613 +// return e;
1.1614 +// }
1.1615 +// /*
1.1616 +// OutEdgeIt &goNext(OutEdgeIt &e)
1.1617 +// {
1.1618 +// if(gw.valid(e.o)) {
1.1619 +// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1620 +// gw.goNext(e.o);
1.1621 +// if(gw.valid(e.o)) return e;
1.1622 +// else gw.first(e.i,e.n);
1.1623 +// }
1.1624 +// else {
1.1625 +// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1626 +// gw.goNext(e.i);
1.1627 +// return e;
1.1628 +// }
1.1629 +// }
1.1630 +// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1.1631 +// */
1.1632 +// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1.1633 +
1.1634 +// //FIXME
1.1635 +// InEdgeIt& first(InEdgeIt& e, const Node& n) const
1.1636 +// {
1.1637 +// e.n=n;
1.1638 +// gw.first(e.i,n);
1.1639 +// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1640 +// gw.goNext(e.i);
1.1641 +// if(!gw.valid(e.i)) {
1.1642 +// gw.first(e.o,n);
1.1643 +// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1644 +// gw.goNext(e.o);
1.1645 +// }
1.1646 +// return e;
1.1647 +// }
1.1648 +// /*
1.1649 +// InEdgeIt &goNext(InEdgeIt &e)
1.1650 +// {
1.1651 +// if(gw.valid(e.i)) {
1.1652 +// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1653 +// gw.goNext(e.i);
1.1654 +// if(gw.valid(e.i)) return e;
1.1655 +// else gw.first(e.o,e.n);
1.1656 +// }
1.1657 +// else {
1.1658 +// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1659 +// gw.goNext(e.o);
1.1660 +// return e;
1.1661 +// }
1.1662 +// }
1.1663 +// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1.1664 +// */
1.1665 +// //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1.1666 +
1.1667 +// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1.1668 +// //template<typename I> I next(const I i); { return gw.goNext(i); }
1.1669 +
1.1670 +// template< typename It > It first() const {
1.1671 +// It e; first(e); return e; }
1.1672 +
1.1673 +// template< typename It > It first(Node v) const {
1.1674 +// It e; first(e, v); return e; }
1.1675 +
1.1676 +// Node head(const Edge& e) const { return gw.head(e); }
1.1677 +// Node tail(const Edge& e) const { return gw.tail(e); }
1.1678 +
1.1679 +// template<typename I> Node aNode(const I& e) const {
1.1680 +// return gw.aNode(e); }
1.1681 +// template<typename I> Node bNode(const I& e) const {
1.1682 +// return gw.bNode(e); }
1.1683 +
1.1684 +// //template<typename I> bool valid(const I i);
1.1685 +// //{ return gw.valid(i); }
1.1686 +
1.1687 +// //template<typename I> void setInvalid(const I &i);
1.1688 +// //{ return gw.setInvalid(i); }
1.1689 +
1.1690 +// Node addNode() { return gw.addNode(); }
1.1691 +// Edge addEdge(const Node& tail, const Node& head) {
1.1692 +// return gw.addEdge(tail, head); }
1.1693 +
1.1694 +// template<typename I> void erase(const I& i) { gw.erase(i); }
1.1695 +
1.1696 +// void clear() { gw.clear(); }
1.1697 +
1.1698 +// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1.1699 +// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1.1700 +
1.1701 +// void setGraph(Graph& _graph) { graph = &_graph; }
1.1702 +// Graph& getGraph() { return (*graph); }
1.1703 +
1.1704 +// //ResGraphWrapper() : graph(0) { }
1.1705 +// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1706 +// };
1.1707 +
1.1708 +} //namespace hugo
1.1709 +
1.1710 +#endif //HUGO_GRAPH_WRAPPER_H
1.1711 +