1.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 08 13:11:58 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Tue Apr 13 20:35:47 2004 +0000
1.3 @@ -6,156 +6,6 @@
1.4
1.5 namespace hugo {
1.6
1.7 -// template<typename Graph>
1.8 -// class TrivGraphWrapper {
1.9 -// protected:
1.10 -// Graph* graph;
1.11 -
1.12 -// public:
1.13 -// // typedef Graph BaseGraph;
1.14 -// typedef Graph ParentGraph;
1.15 -
1.16 -// // TrivGraphWrapper() : graph(0) { }
1.17 -// TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.18 -// // void setGraph(Graph& _graph) { graph = &_graph; }
1.19 -// // Graph& getGraph() const { return *graph; }
1.20 -
1.21 -// typedef typename Graph::Node Node;
1.22 -// class NodeIt : public Graph::NodeIt {
1.23 -// public:
1.24 -// NodeIt() { }
1.25 -// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.26 -// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.27 -// NodeIt(const TrivGraphWrapper<Graph>& _G) :
1.28 -// Graph::NodeIt(*(_G.graph)) { }
1.29 -// };
1.30 -// typedef typename Graph::Edge Edge;
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 -// class InEdgeIt : public Graph::InEdgeIt {
1.40 -// public:
1.41 -// InEdgeIt() { }
1.42 -// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.43 -// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.44 -// InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.45 -// Graph::InEdgeIt(*(_G.graph), n) { }
1.46 -// };
1.47 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.48 -// class EdgeIt : public Graph::EdgeIt {
1.49 -// public:
1.50 -// EdgeIt() { }
1.51 -// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.52 -// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.53 -// EdgeIt(const TrivGraphWrapper<Graph>& _G) :
1.54 -// Graph::EdgeIt(*(_G.graph)) { }
1.55 -// };
1.56 -
1.57 -// NodeIt& first(NodeIt& i) const {
1.58 -// i=NodeIt(*this);
1.59 -// return i;
1.60 -// }
1.61 -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.62 -// i=OutEdgeIt(*this, p);
1.63 -// return i;
1.64 -// }
1.65 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.66 -// i=InEdgeIt(*this, p);
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 -// // i=I(*this);
1.75 -// // return i;
1.76 -// // }
1.77 -// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.78 -// // i=I(*this, p);
1.79 -// // return i;
1.80 -// // }
1.81 -
1.82 -// // template<typename I> I getNext(const I& i) const {
1.83 -// // return graph->getNext(i); }
1.84 -
1.85 -// NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
1.86 -// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
1.87 -// InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
1.88 -// EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
1.89 -// // template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.90 -// template< typename It > It first() const {
1.91 -// It e; this->first(e); return e; }
1.92 -
1.93 -// template< typename It > It first(const Node& v) const {
1.94 -// It e; this->first(e, v); return e; }
1.95 -
1.96 -// Node head(const Edge& e) const { return graph->head(e); }
1.97 -// Node tail(const Edge& e) const { return graph->tail(e); }
1.98 -
1.99 -// template<typename I> bool valid(const I& i) const {
1.100 -// return graph->valid(i); }
1.101 -
1.102 -// //template<typename I> void setInvalid(const I &i);
1.103 -// //{ return graph->setInvalid(i); }
1.104 -
1.105 -// int nodeNum() const { return graph->nodeNum(); }
1.106 -// int edgeNum() const { return graph->edgeNum(); }
1.107 -
1.108 -// template<typename I> Node aNode(const I& e) const {
1.109 -// return graph->aNode(e); }
1.110 -// template<typename I> Node bNode(const I& e) const {
1.111 -// return graph->bNode(e); }
1.112 -
1.113 -// Node addNode() const { return graph->addNode(); }
1.114 -// Edge addEdge(const Node& tail, const Node& head) const {
1.115 -// return graph->addEdge(tail, head); }
1.116 -
1.117 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.118 -
1.119 -// void clear() const { graph->clear(); }
1.120 -
1.121 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.122 -// public:
1.123 -// NodeMap(const TrivGraphWrapper<Graph>& _G) :
1.124 -// Graph::NodeMap<T>(*(_G.graph)) { }
1.125 -// NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.126 -// Graph::NodeMap<T>(*(_G.graph), a) { }
1.127 -// };
1.128 -
1.129 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.130 -// public:
1.131 -// EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.132 -// Graph::EdgeMap<T>(*(_G.graph)) { }
1.133 -// EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.134 -// Graph::EdgeMap<T>(*(_G.graph), a) { }
1.135 -// };
1.136 -
1.137 -// // template<typename Map, typename T> class NodeMapWrapper {
1.138 -// // protected:
1.139 -// // Map* map;
1.140 -// // public:
1.141 -// // NodeMapWrapper(Map& _map) : map(&_map) { }
1.142 -// // void set(Node n, T a) { map->set(n, a); }
1.143 -// // T get(Node n) const { return map->get(n); }
1.144 -// // };
1.145 -
1.146 -// // template<typename Map, typename T> class EdgeMapWrapper {
1.147 -// // protected:
1.148 -// // Map* map;
1.149 -// // public:
1.150 -// // EdgeMapWrapper(Map& _map) : map(&_map) { }
1.151 -// // void set(Edge n, T a) { map->set(n, a); }
1.152 -// // T get(Edge n) const { return map->get(n); }
1.153 -// // };
1.154 -// };
1.155 -
1.156 -
1.157 template<typename Graph>
1.158 class GraphWrapper {
1.159 protected:
1.160 @@ -170,77 +20,100 @@
1.161 // void setGraph(Graph& _graph) { graph=&_graph; }
1.162 // Graph& getGraph() const { return *graph; }
1.163
1.164 - typedef typename Graph::Node Node;
1.165 - class NodeIt : public Graph::NodeIt {
1.166 - typedef typename Graph::NodeIt GraphNodeIt;
1.167 +// typedef typename Graph::Node Node;
1.168 + class Node : public Graph::Node {
1.169 + friend class GraphWrapper<Graph>;
1.170 public:
1.171 + Node() { }
1.172 + Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
1.173 + Node(const Invalid& i) : Graph::Node(i) { }
1.174 + };
1.175 + class NodeIt {
1.176 + friend class GraphWrapper<Graph>;
1.177 + typename Graph::NodeIt n;
1.178 + public:
1.179 NodeIt() { }
1.180 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.181 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.182 - NodeIt(const GraphWrapper<Graph>& _G) :
1.183 - Graph::NodeIt(*(_G.graph)) { }
1.184 -// operator Node() const {
1.185 -// std::cout << "ize" << std::endl;
1.186 -// return Node(this->GraphNodeIt);
1.187 -// }
1.188 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.189 + NodeIt(const Invalid& i) : n(i) { }
1.190 + NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
1.191 + operator Node() const { return Node(typename Graph::Node(n)); }
1.192 };
1.193 - typedef typename Graph::Edge Edge;
1.194 - class OutEdgeIt : public Graph::OutEdgeIt {
1.195 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.196 +// class Node : public Graph::Node {
1.197 +// public:
1.198 +// Node() { }
1.199 +// Node(const typename Graph::Node& n) : Graph::Node(n) { }
1.200 +// Node(const Invalid& i) : Graph::Node(i) { }
1.201 +// };
1.202 +// class NodeIt : public Graph::NodeIt {
1.203 +// typedef typename Graph::NodeIt GraphNodeIt;
1.204 +// public:
1.205 +// NodeIt() { }
1.206 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.207 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.208 +// NodeIt(const GraphWrapper<Graph>& _G) :
1.209 +// Graph::NodeIt(*(_G.graph)) { }
1.210 +// operator Node() const {
1.211 +// return Node(typename Graph::Node(
1.212 +// static_cast<typename Graph::NodeIt>(*this)
1.213 +// ));
1.214 +// }
1.215 +// };
1.216 +// typedef typename Graph::Edge Edge;
1.217 + class Edge : public Graph::Edge {
1.218 + friend class GraphWrapper<Graph>;
1.219 + public:
1.220 + Edge() { }
1.221 + Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
1.222 + Edge(const Invalid& i) : Graph::Edge(i) { }
1.223 + };
1.224 + class OutEdgeIt {
1.225 + friend class GraphWrapper<Graph>;
1.226 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.227 + typename Graph::OutEdgeIt e;
1.228 public:
1.229 OutEdgeIt() { }
1.230 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.231 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.232 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
1.233 - Graph::OutEdgeIt(*(_G.graph), n) { }
1.234 -// operator Edge() const {
1.235 -// std::cout << "ize" << std::endl;
1.236 -// return Edge(this->GraphOutEdgeIt);
1.237 -// }
1.238 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.239 + OutEdgeIt(const Invalid& i) : e(i) { }
1.240 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.241 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.242 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.243 };
1.244 - class InEdgeIt : public Graph::InEdgeIt {
1.245 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.246 + class InEdgeIt {
1.247 + friend class GraphWrapper<Graph>;
1.248 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.249 + typename Graph::InEdgeIt e;
1.250 public:
1.251 InEdgeIt() { }
1.252 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.253 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.254 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
1.255 - Graph::InEdgeIt(*(_G.graph), n) { }
1.256 -// operator Edge() const {
1.257 -// std::cout << "ize" << std::endl;
1.258 -// return Edge(this->InOutEdgeIt);
1.259 -// }
1.260 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.261 + InEdgeIt(const Invalid& i) : e(i) { }
1.262 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.263 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.264 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.265 };
1.266 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.267 - class EdgeIt : public Graph::EdgeIt {
1.268 - typedef typename Graph::EdgeIt GraphEdgeIt;
1.269 + class EdgeIt {
1.270 + friend class GraphWrapper<Graph>;
1.271 +// typedef typename Graph::EdgeIt GraphEdgeIt;
1.272 + typename Graph::EdgeIt e;
1.273 public:
1.274 EdgeIt() { }
1.275 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.276 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.277 - EdgeIt(const GraphWrapper<Graph>& _G) :
1.278 - Graph::EdgeIt(*(_G.graph)) { }
1.279 -// operator Edge() const {
1.280 -// std::cout << "ize" << std::endl;
1.281 -// return Edge(this->GraphEdgeIt);
1.282 -// }
1.283 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.284 + EdgeIt(const Invalid& i) : e(i) { }
1.285 + EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
1.286 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.287 };
1.288
1.289 NodeIt& first(NodeIt& i) const {
1.290 - i=NodeIt(*this);
1.291 - return i;
1.292 + i=NodeIt(*this); return i;
1.293 }
1.294 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.295 - i=OutEdgeIt(*this, p);
1.296 - return i;
1.297 + i=OutEdgeIt(*this, p); return i;
1.298 }
1.299 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.300 - i=InEdgeIt(*this, p);
1.301 - return i;
1.302 + i=InEdgeIt(*this, p); return i;
1.303 }
1.304 EdgeIt& first(EdgeIt& i) const {
1.305 - i=EdgeIt(*this);
1.306 - return i;
1.307 + i=EdgeIt(*this); return i;
1.308 }
1.309 // template<typename I> I& first(I& i) const {
1.310 // i=I(*this);
1.311 @@ -254,10 +127,10 @@
1.312 // template<typename I> I getNext(const I& i) const {
1.313 // return gw.getNext(i); }
1.314
1.315 - NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
1.316 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
1.317 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
1.318 - EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
1.319 + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.320 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1.321 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1.322 + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1.323 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.324 template< typename It > It first() const {
1.325 It e; this->first(e); return e; }
1.326 @@ -265,12 +138,18 @@
1.327 template< typename It > It first(const Node& v) const {
1.328 It e; this->first(e, v); return e; }
1.329
1.330 - Node head(const Edge& e) const { return graph->head(e); }
1.331 - Node tail(const Edge& e) const { return graph->tail(e); }
1.332 + Node head(const Edge& e) const {
1.333 + return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1.334 + Node tail(const Edge& e) const {
1.335 + return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1.336 // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); }
1.337
1.338 - template<typename I> bool valid(const I& i) const {
1.339 - return graph->valid(i); }
1.340 + bool valid(const Node& n) const {
1.341 + return graph->valid(static_cast<typename Graph::Node>(n)); }
1.342 + bool valid(const Edge& e) const {
1.343 + return graph->valid(static_cast<typename Graph::Edge>(e)); }
1.344 +// template<typename I> bool valid(const I& i) const {
1.345 +// return graph->valid(i); }
1.346
1.347 //template<typename I> void setInvalid(const I &i);
1.348 //{ return graph->setInvalid(i); }
1.349 @@ -278,16 +157,22 @@
1.350 int nodeNum() const { return graph->nodeNum(); }
1.351 int edgeNum() const { return graph->edgeNum(); }
1.352
1.353 - template<typename I> Node aNode(const I& e) const {
1.354 - return graph->aNode(e); }
1.355 - template<typename I> Node bNode(const I& e) const {
1.356 - return graph->bNode(e); }
1.357 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.358 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.359 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.360 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.361 +// template<typename I> Node aNode(const I& e) const {
1.362 +// return Node(graph->aNode(e.e)); }
1.363 +// template<typename I> Node bNode(const I& e) const {
1.364 +// return Node(graph->bNode(e.e)); }
1.365
1.366 - Node addNode() const { return graph->addNode(); }
1.367 + Node addNode() const { return Node(graph->addNode()); }
1.368 Edge addEdge(const Node& tail, const Node& head) const {
1.369 - return graph->addEdge(tail, head); }
1.370 -
1.371 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.372 + return Edge(graph->addEdge(tail, head)); }
1.373 +
1.374 + void erase(const Node& i) const { graph->erase(i); }
1.375 + void erase(const Edge& i) const { graph->erase(i); }
1.376 +// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.377
1.378 void clear() const { graph->clear(); }
1.379
1.380 @@ -297,6 +182,9 @@
1.381 Graph::NodeMap<T>(*(_G.graph)) { }
1.382 NodeMap(const GraphWrapper<Graph>& _G, T a) :
1.383 Graph::NodeMap<T>(*(_G.graph), a) { }
1.384 +// T operator[](const Node& n) const {
1.385 +// return Graph::NodeMap<T>::operator[](n);
1.386 +// }
1.387 };
1.388
1.389 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.390 @@ -429,80 +317,144 @@
1.391 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.392 edge_filter_map(&_edge_filter_map) { }
1.393
1.394 -
1.395 - typedef typename Graph::Node Node;
1.396 - class NodeIt : public Graph::NodeIt {
1.397 -// typedef typename Graph::NodeIt GraphNodeIt;
1.398 - public:
1.399 + typedef typename GraphWrapper<Graph>::Node Node;
1.400 + class NodeIt {
1.401 + friend class GraphWrapper<Graph>;
1.402 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.403 + typename Graph::NodeIt n;
1.404 + public:
1.405 NodeIt() { }
1.406 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.407 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.408 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.409 + NodeIt(const Invalid& i) : n(i) { }
1.410 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.411 - Graph::NodeIt(*(_G.graph)) {
1.412 - while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
1.413 - !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
1.414 - _G.graph->next((*this)/*.GraphNodeIt*/);
1.415 + n(*(_G.graph)) {
1.416 + while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.417 + _G.graph->next(n);
1.418 }
1.419 + operator Node() const { return Node(typename Graph::Node(n)); }
1.420 };
1.421 - typedef typename Graph::Edge Edge;
1.422 - class OutEdgeIt : public Graph::OutEdgeIt {
1.423 +// class NodeIt : public Graph::NodeIt {
1.424 +// // typedef typename Graph::NodeIt GraphNodeIt;
1.425 +// public:
1.426 +// NodeIt() { }
1.427 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.428 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.429 +// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.430 +// Graph::NodeIt(*(_G.graph)) {
1.431 +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
1.432 +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
1.433 +// _G.graph->next((*this)/*.GraphNodeIt*/);
1.434 +// }
1.435 +// };
1.436 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.437 + class OutEdgeIt {
1.438 + friend class GraphWrapper<Graph>;
1.439 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.440 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.441 + typename Graph::OutEdgeIt e;
1.442 public:
1.443 OutEdgeIt() { }
1.444 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.445 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.446 - OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
1.447 - _G, const Node& n) :
1.448 - Graph::OutEdgeIt(*(_G.graph), n) {
1.449 - while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
1.450 - !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
1.451 - _G.graph->next((*this)/*.GraphOutEdgeIt*/);
1.452 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.453 + OutEdgeIt(const Invalid& i) : e(i) { }
1.454 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.455 + const Node& _n) :
1.456 + e(*(_G.graph), typename Graph::Node(_n)) {
1.457 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.458 + _G.graph->next(e);
1.459 }
1.460 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.461 };
1.462 - class InEdgeIt : public Graph::InEdgeIt {
1.463 + class InEdgeIt {
1.464 + friend class GraphWrapper<Graph>;
1.465 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.466 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.467 + typename Graph::InEdgeIt e;
1.468 public:
1.469 InEdgeIt() { }
1.470 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.471 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.472 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.473 + InEdgeIt(const Invalid& i) : e(i) { }
1.474 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.475 - const Node& n) :
1.476 - Graph::InEdgeIt(*(_G.graph), n) {
1.477 - while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
1.478 - !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
1.479 - _G.graph->next((*this)/*.GraphInEdgeIt*/);
1.480 + const Node& _n) :
1.481 + e(*(_G.graph), typename Graph::Node(_n)) {
1.482 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.483 + _G.graph->next(e);
1.484 }
1.485 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.486 };
1.487 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.488 - class EdgeIt : public Graph::EdgeIt {
1.489 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.490 + class EdgeIt {
1.491 + friend class GraphWrapper<Graph>;
1.492 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.493 // typedef typename Graph::EdgeIt GraphEdgeIt;
1.494 + typename Graph::EdgeIt e;
1.495 public:
1.496 EdgeIt() { }
1.497 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.498 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.499 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.500 + EdgeIt(const Invalid& i) : e(i) { }
1.501 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.502 - Graph::EdgeIt(*(_G.graph)) {
1.503 - while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
1.504 - !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
1.505 - _G.graph->next((*this)/*.GraphEdgeIt*/);
1.506 + e(*(_G.graph)) {
1.507 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.508 + _G.graph->next(e);
1.509 }
1.510 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.511 };
1.512 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.513 +// };
1.514 +// class OutEdgeIt : public Graph::OutEdgeIt {
1.515 +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.516 +// public:
1.517 +// OutEdgeIt() { }
1.518 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.519 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.520 +// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
1.521 +// _G, const Node& n) :
1.522 +// Graph::OutEdgeIt(*(_G.graph), n) {
1.523 +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
1.524 +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
1.525 +// _G.graph->next((*this)/*.GraphOutEdgeIt*/);
1.526 +// }
1.527 +// };
1.528 +// class InEdgeIt : public Graph::InEdgeIt {
1.529 +// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.530 +// public:
1.531 +// InEdgeIt() { }
1.532 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.533 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.534 +// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.535 +// const Node& n) :
1.536 +// Graph::InEdgeIt(*(_G.graph), n) {
1.537 +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
1.538 +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
1.539 +// _G.graph->next((*this)/*.GraphInEdgeIt*/);
1.540 +// }
1.541 +// };
1.542 +// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.543 +// class EdgeIt : public Graph::EdgeIt {
1.544 +// // typedef typename Graph::EdgeIt GraphEdgeIt;
1.545 +// public:
1.546 +// EdgeIt() { }
1.547 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.548 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.549 +// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.550 +// Graph::EdgeIt(*(_G.graph)) {
1.551 +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
1.552 +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
1.553 +// _G.graph->next((*this)/*.GraphEdgeIt*/);
1.554 +// }
1.555 +// };
1.556
1.557 - NodeIt& first(NodeIt& i) const {
1.558 - i=NodeIt(*this);
1.559 - return i;
1.560 +
1.561 + NodeIt& first(NodeIt& i) const {
1.562 + i=NodeIt(*this); return i;
1.563 }
1.564 - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.565 - i=OutEdgeIt(*this, n);
1.566 - return i;
1.567 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.568 + i=OutEdgeIt(*this, p); return i;
1.569 }
1.570 - InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.571 - i=InEdgeIt(*this, n);
1.572 - return i;
1.573 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.574 + i=InEdgeIt(*this, p); return i;
1.575 }
1.576 - EdgeIt& first(EdgeIt& i) const {
1.577 - i=EdgeIt(*this);
1.578 - return i;
1.579 + EdgeIt& first(EdgeIt& i) const {
1.580 + i=EdgeIt(*this); return i;
1.581 }
1.582
1.583 // template<typename I> I& first(I& i) const {
1.584 @@ -519,26 +471,32 @@
1.585 // }
1.586
1.587 NodeIt& next(NodeIt& i) const {
1.588 - graph->next(i);
1.589 - while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
1.590 + graph->next(i.n);
1.591 + while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
1.592 return i;
1.593 }
1.594 OutEdgeIt& next(OutEdgeIt& i) const {
1.595 - graph->next(i);
1.596 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.597 + graph->next(i.e);
1.598 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
1.599 return i;
1.600 }
1.601 InEdgeIt& next(InEdgeIt& i) const {
1.602 - graph->next(i);
1.603 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.604 + graph->next(i.e);
1.605 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
1.606 return i;
1.607 }
1.608 EdgeIt& next(EdgeIt& i) const {
1.609 - graph->next(i);
1.610 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.611 + graph->next(i.e);
1.612 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
1.613 return i;
1.614 }
1.615
1.616 +
1.617 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.618 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.619 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.620 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.621 +
1.622 //template<typename I> I getNext(const I& i) const {
1.623 // return gw.getNext(i);
1.624 //}
1.625 @@ -556,6 +514,147 @@
1.626 It e; this->first(e, v); return e; }
1.627 };
1.628
1.629 +// //Subgraph on the same node-set and partial edge-set
1.630 +// template<typename Graph, typename NodeFilterMap,
1.631 +// typename EdgeFilterMap>
1.632 +// class SubGraphWrapper : public GraphWrapper<Graph> {
1.633 +// protected:
1.634 +// NodeFilterMap* node_filter_map;
1.635 +// EdgeFilterMap* edge_filter_map;
1.636 +// public:
1.637 +// // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
1.638 +// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.639 +// EdgeFilterMap& _edge_filter_map) :
1.640 +// GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.641 +// edge_filter_map(&_edge_filter_map) { }
1.642 +
1.643 +
1.644 +// typedef typename Graph::Node Node;
1.645 +// class NodeIt : public Graph::NodeIt {
1.646 +// // typedef typename Graph::NodeIt GraphNodeIt;
1.647 +// public:
1.648 +// NodeIt() { }
1.649 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.650 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.651 +// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.652 +// Graph::NodeIt(*(_G.graph)) {
1.653 +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
1.654 +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
1.655 +// _G.graph->next((*this)/*.GraphNodeIt*/);
1.656 +// }
1.657 +// };
1.658 +// typedef typename Graph::Edge Edge;
1.659 +// class OutEdgeIt : public Graph::OutEdgeIt {
1.660 +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.661 +// public:
1.662 +// OutEdgeIt() { }
1.663 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.664 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.665 +// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
1.666 +// _G, const Node& n) :
1.667 +// Graph::OutEdgeIt(*(_G.graph), n) {
1.668 +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
1.669 +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
1.670 +// _G.graph->next((*this)/*.GraphOutEdgeIt*/);
1.671 +// }
1.672 +// };
1.673 +// class InEdgeIt : public Graph::InEdgeIt {
1.674 +// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.675 +// public:
1.676 +// InEdgeIt() { }
1.677 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.678 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.679 +// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.680 +// const Node& n) :
1.681 +// Graph::InEdgeIt(*(_G.graph), n) {
1.682 +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
1.683 +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
1.684 +// _G.graph->next((*this)/*.GraphInEdgeIt*/);
1.685 +// }
1.686 +// };
1.687 +// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.688 +// class EdgeIt : public Graph::EdgeIt {
1.689 +// // typedef typename Graph::EdgeIt GraphEdgeIt;
1.690 +// public:
1.691 +// EdgeIt() { }
1.692 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.693 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.694 +// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.695 +// Graph::EdgeIt(*(_G.graph)) {
1.696 +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
1.697 +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
1.698 +// _G.graph->next((*this)/*.GraphEdgeIt*/);
1.699 +// }
1.700 +// };
1.701 +
1.702 +// NodeIt& first(NodeIt& i) const {
1.703 +// i=NodeIt(*this);
1.704 +// return i;
1.705 +// }
1.706 +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.707 +// i=OutEdgeIt(*this, n);
1.708 +// return i;
1.709 +// }
1.710 +// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.711 +// i=InEdgeIt(*this, n);
1.712 +// return i;
1.713 +// }
1.714 +// EdgeIt& first(EdgeIt& i) const {
1.715 +// i=EdgeIt(*this);
1.716 +// return i;
1.717 +// }
1.718 +
1.719 +// // template<typename I> I& first(I& i) const {
1.720 +// // graph->first(i);
1.721 +// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.722 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.723 +// // return i;
1.724 +// // }
1.725 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.726 +// // graph->first(i, p);
1.727 +// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.728 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.729 +// // return i;
1.730 +// // }
1.731 +
1.732 +// NodeIt& next(NodeIt& i) const {
1.733 +// graph->next(i);
1.734 +// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
1.735 +// return i;
1.736 +// }
1.737 +// OutEdgeIt& next(OutEdgeIt& i) const {
1.738 +// graph->next(i);
1.739 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.740 +// return i;
1.741 +// }
1.742 +// InEdgeIt& next(InEdgeIt& i) const {
1.743 +// graph->next(i);
1.744 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.745 +// return i;
1.746 +// }
1.747 +// EdgeIt& next(EdgeIt& i) const {
1.748 +// graph->next(i);
1.749 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.750 +// return i;
1.751 +// }
1.752 +
1.753 +// //template<typename I> I getNext(const I& i) const {
1.754 +// // return gw.getNext(i);
1.755 +// //}
1.756 +// // template<typename I> I& next(I &i) const {
1.757 +// // graph->next(i);
1.758 +// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
1.759 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.760 +// // return i;
1.761 +// // }
1.762 +
1.763 +// template< typename It > It first() const {
1.764 +// It e; this->first(e); return e; }
1.765 +
1.766 +// template< typename It > It first(const Node& v) const {
1.767 +// It e; this->first(e, v); return e; }
1.768 +// };
1.769 +
1.770 // template<typename GraphWrapper>
1.771 // class UndirGraphWrapper {
1.772 // protected:
1.773 @@ -718,109 +817,129 @@
1.774
1.775 template<typename Graph>
1.776 class UndirGraphWrapper : public GraphWrapper<Graph> {
1.777 - protected:
1.778 - typedef typename Graph::Edge GraphEdge;
1.779 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.780 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.781 +// protected:
1.782 +// typedef typename Graph::Edge GraphEdge;
1.783 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.784 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.785 public:
1.786 typedef typename GraphWrapper<Graph>::Node Node;
1.787 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.788 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.789 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.790
1.791 // UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.792 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.793
1.794 - class Edge {
1.795 +
1.796 +// class Edge {
1.797 +// friend class UndirGraphWrapper<Graph>;
1.798 +// protected:
1.799 +// bool out_or_in; //true iff out
1.800 +// GraphOutEdgeIt out;
1.801 +// GraphInEdgeIt in;
1.802 +// public:
1.803 +// Edge() : out_or_in(), out(), in() { }
1.804 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.805 +// operator GraphEdge() const {
1.806 +// if (out_or_in) return(out); else return(in);
1.807 +// }
1.808 +// //FIXME
1.809 +// //2 edges are equal if they "refer" to the same physical edge
1.810 +// //is it good?
1.811 +// friend bool operator==(const Edge& u, const Edge& v) {
1.812 +// if (v.out_or_in)
1.813 +// if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.814 +// //return (u.out_or_in && u.out==v.out);
1.815 +// else
1.816 +// if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.817 +// //return (!u.out_or_in && u.in==v.in);
1.818 +// }
1.819 +// friend bool operator!=(const Edge& u, const Edge& v) {
1.820 +// if (v.out_or_in)
1.821 +// if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
1.822 +// //return (!u.out_or_in || u.out!=v.out);
1.823 +// else
1.824 +// if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
1.825 +// //return (u.out_or_in || u.in!=v.in);
1.826 +// }
1.827 +// };
1.828 +
1.829 + class OutEdgeIt {
1.830 friend class UndirGraphWrapper<Graph>;
1.831 - protected:
1.832 bool out_or_in; //true iff out
1.833 - GraphOutEdgeIt out;
1.834 - GraphInEdgeIt in;
1.835 + typename Graph::OutEdgeIt out;
1.836 + typename Graph::InEdgeIt in;
1.837 public:
1.838 - Edge() : out_or_in(), out(), in() { }
1.839 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.840 - operator GraphEdge() const {
1.841 - if (out_or_in) return(out); else return(in);
1.842 - }
1.843 -//FIXME
1.844 -//2 edges are equal if they "refer" to the same physical edge
1.845 -//is it good?
1.846 - friend bool operator==(const Edge& u, const Edge& v) {
1.847 - if (v.out_or_in)
1.848 - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.849 - //return (u.out_or_in && u.out==v.out);
1.850 - else
1.851 - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.852 - //return (!u.out_or_in && u.in==v.in);
1.853 + OutEdgeIt() { }
1.854 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.855 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.856 + out_or_in=true; _G.graph->first(out, _n);
1.857 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.858 }
1.859 - friend bool operator!=(const Edge& u, const Edge& v) {
1.860 - if (v.out_or_in)
1.861 - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
1.862 - //return (!u.out_or_in || u.out!=v.out);
1.863 - else
1.864 - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
1.865 - //return (u.out_or_in || u.in!=v.in);
1.866 - }
1.867 - };
1.868 -
1.869 - class OutEdgeIt : public Edge {
1.870 - friend class UndirGraphWrapper<Graph>;
1.871 - public:
1.872 - OutEdgeIt() : Edge() { }
1.873 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.874 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
1.875 - : Edge() {
1.876 - out_or_in=true; _G.graph->first(out, n);
1.877 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
1.878 + operator Edge() const {
1.879 + if (out_or_in) return Edge(out); else return Edge(in);
1.880 }
1.881 };
1.882 +// class OutEdgeIt : public Edge {
1.883 +// friend class UndirGraphWrapper<Graph>;
1.884 +// public:
1.885 +// OutEdgeIt() : Edge() { }
1.886 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.887 +// OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
1.888 +// : Edge() {
1.889 +// out_or_in=true; _G.graph->first(out, n);
1.890 +// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
1.891 +// }
1.892 +// };
1.893
1.894 +//FIXME InEdgeIt
1.895 typedef OutEdgeIt InEdgeIt;
1.896
1.897 - class EdgeIt : public Edge {
1.898 - friend class UndirGraphWrapper<Graph>;
1.899 - protected:
1.900 - NodeIt v;
1.901 - public:
1.902 - EdgeIt() : Edge() { }
1.903 - EdgeIt(const Invalid& i) : Edge(i) { }
1.904 - EdgeIt(const UndirGraphWrapper<Graph>& _G)
1.905 - : Edge() {
1.906 - out_or_in=true;
1.907 - //Node v;
1.908 - _G.first(v);
1.909 - if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
1.910 - while (_G.valid(v) && !_G.graph->valid(out)) {
1.911 - _G.graph->next(v);
1.912 - if (_G.valid(v)) _G.graph->first(out);
1.913 - }
1.914 - }
1.915 - };
1.916 +// class EdgeIt : public Edge {
1.917 +// friend class UndirGraphWrapper<Graph>;
1.918 +// protected:
1.919 +// NodeIt v;
1.920 +// public:
1.921 +// EdgeIt() : Edge() { }
1.922 +// EdgeIt(const Invalid& i) : Edge(i) { }
1.923 +// EdgeIt(const UndirGraphWrapper<Graph>& _G)
1.924 +// : Edge() {
1.925 +// out_or_in=true;
1.926 +// //Node v;
1.927 +// _G.first(v);
1.928 +// if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
1.929 +// while (_G.valid(v) && !_G.graph->valid(out)) {
1.930 +// _G.graph->next(v);
1.931 +// if (_G.valid(v)) _G.graph->first(out);
1.932 +// }
1.933 +// }
1.934 +// };
1.935
1.936 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.937 - e.out_or_in=true; graph->first(e.out, n);
1.938 - if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
1.939 - return e;
1.940 + NodeIt& first(NodeIt& i) const {
1.941 + i=NodeIt(*this); return i;
1.942 }
1.943 -
1.944 - EdgeIt& first(EdgeIt& e) const {
1.945 - e.out_or_in=true;
1.946 - //NodeIt v;
1.947 - first(e.v);
1.948 - if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
1.949 - while (valid(e.v) && !graph->valid(e.out)) {
1.950 - graph->next(e.v);
1.951 - if (valid(e.v)) graph->first(e.out, e.v);
1.952 - }
1.953 - return e;
1.954 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.955 + i=OutEdgeIt(*this, p); return i;
1.956 + }
1.957 +//FIXME
1.958 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.959 +// i=InEdgeIt(*this, p); return i;
1.960 +// }
1.961 + EdgeIt& first(EdgeIt& i) const {
1.962 + i=EdgeIt(*this); return i;
1.963 }
1.964
1.965 template<typename I> I& first(I& i) const { graph->first(i); return i; }
1.966 template<typename I, typename P> I& first(I& i, const P& p) const {
1.967 graph->first(i, p); return i; }
1.968
1.969 + NodeIt& next(NodeIt& n) const {
1.970 + GraphWrapper<Graph>::next(n);
1.971 + return n;
1.972 + }
1.973 OutEdgeIt& next(OutEdgeIt& e) const {
1.974 if (e.out_or_in) {
1.975 - Node n=graph->tail(e.out);
1.976 + typename Graph::Node n=graph->tail(e.out);
1.977 graph->next(e.out);
1.978 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
1.979 } else {
1.980 @@ -828,18 +947,14 @@
1.981 }
1.982 return e;
1.983 }
1.984 -
1.985 + //FIXME InEdgeIt
1.986 EdgeIt& next(EdgeIt& e) const {
1.987 - //NodeIt v=tail(e);
1.988 - graph->next(e.out);
1.989 - while (valid(e.v) && !graph->valid(e.out)) {
1.990 - next(e.v);
1.991 - if (valid(e.v)) graph->first(e.out, e.v);
1.992 - }
1.993 + GraphWrapper<Graph>::next(n);
1.994 +// graph->next(e.e);
1.995 return e;
1.996 }
1.997
1.998 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.999 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.1000 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.1001
1.1002 template< typename It > It first() const {
1.1003 @@ -968,12 +1083,14 @@
1.1004 // };
1.1005
1.1006
1.1007 +
1.1008 +
1.1009 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1010 class ResGraphWrapper : public GraphWrapper<Graph> {
1.1011 protected:
1.1012 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.1013 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.1014 - typedef typename Graph::Edge GraphEdge;
1.1015 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.1016 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.1017 +// typedef typename Graph::Edge GraphEdge;
1.1018 FlowMap* flow;
1.1019 const CapacityMap* capacity;
1.1020 public:
1.1021 @@ -989,49 +1106,104 @@
1.1022
1.1023 typedef typename GraphWrapper<Graph>::Node Node;
1.1024 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.1025 - class Edge {
1.1026 + class Edge : public Graph::Edge {
1.1027 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1028 protected:
1.1029 - bool out_or_in; //true, iff out
1.1030 - GraphOutEdgeIt out;
1.1031 - GraphInEdgeIt in;
1.1032 + bool forward; //true, iff forward
1.1033 +// typename Graph::Edge e;
1.1034 public:
1.1035 - Edge() : out_or_in(true) { }
1.1036 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.1037 -// bool valid() const {
1.1038 -// return out_or_in && out.valid() || in.valid(); }
1.1039 + Edge() { }
1.1040 + Edge(const typename Graph::Edge& _e, bool _forward) :
1.1041 + Graph::Edge(_e), forward(_forward) { }
1.1042 + Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
1.1043 +//the unique invalid iterator
1.1044 friend bool operator==(const Edge& u, const Edge& v) {
1.1045 - if (v.out_or_in)
1.1046 - return (u.out_or_in && u.out==v.out);
1.1047 - else
1.1048 - return (!u.out_or_in && u.in==v.in);
1.1049 + return (v.forward==u.forward &&
1.1050 + static_cast<typename Graph::Edge>(u)==
1.1051 + static_cast<typename Graph::Edge>(v));
1.1052 }
1.1053 friend bool operator!=(const Edge& u, const Edge& v) {
1.1054 - if (v.out_or_in)
1.1055 - return (!u.out_or_in || u.out!=v.out);
1.1056 - else
1.1057 - return (u.out_or_in || u.in!=v.in);
1.1058 + return (v.forward!=u.forward ||
1.1059 + static_cast<typename Graph::Edge>(u)!=
1.1060 + static_cast<typename Graph::Edge>(v));
1.1061 }
1.1062 - operator GraphEdge() const {
1.1063 - if (out_or_in) return(out); else return(in);
1.1064 - }
1.1065 };
1.1066 - class OutEdgeIt : public Edge {
1.1067 +// class Edge {
1.1068 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1069 +// protected:
1.1070 +// bool out_or_in; //true, iff out
1.1071 +// GraphOutEdgeIt out;
1.1072 +// GraphInEdgeIt in;
1.1073 +// public:
1.1074 +// Edge() : out_or_in(true) { }
1.1075 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.1076 +// // bool valid() const {
1.1077 +// // return out_or_in && out.valid() || in.valid(); }
1.1078 +// friend bool operator==(const Edge& u, const Edge& v) {
1.1079 +// if (v.out_or_in)
1.1080 +// return (u.out_or_in && u.out==v.out);
1.1081 +// else
1.1082 +// return (!u.out_or_in && u.in==v.in);
1.1083 +// }
1.1084 +// friend bool operator!=(const Edge& u, const Edge& v) {
1.1085 +// if (v.out_or_in)
1.1086 +// return (!u.out_or_in || u.out!=v.out);
1.1087 +// else
1.1088 +// return (u.out_or_in || u.in!=v.in);
1.1089 +// }
1.1090 +// operator GraphEdge() const {
1.1091 +// if (out_or_in) return(out); else return(in);
1.1092 +// }
1.1093 +// };
1.1094 + class OutEdgeIt {
1.1095 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1096 + protected:
1.1097 + typename Graph::OutEdgeIt out;
1.1098 + typename Graph::InEdgeIt in;
1.1099 + bool forward;
1.1100 public:
1.1101 OutEdgeIt() { }
1.1102 //FIXME
1.1103 - OutEdgeIt(const Edge& e) : Edge(e) { }
1.1104 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1105 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1106 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.1107 + OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.1108 +//the unique invalid iterator
1.1109 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
1.1110 + forward=true;
1.1111 resG.graph->first(out, v);
1.1112 - while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1113 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.1114 if (!resG.graph->valid(out)) {
1.1115 - out_or_in=0;
1.1116 + forward=false;
1.1117 resG.graph->first(in, v);
1.1118 - while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1119 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.1120 }
1.1121 }
1.1122 + operator Edge() const {
1.1123 +// Edge e;
1.1124 +// e.forward=this->forward;
1.1125 +// if (this->forward) e=out; else e=in;
1.1126 +// return e;
1.1127 + if (this->forward)
1.1128 + return Edge(out, this->forward);
1.1129 + else
1.1130 + return Edge(in, this->forward);
1.1131 + }
1.1132 + };
1.1133 +// class OutEdgeIt : public Edge {
1.1134 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1135 +// public:
1.1136 +// OutEdgeIt() { }
1.1137 +// //FIXME
1.1138 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.1139 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1140 +// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1141 +// resG.graph->first(out, v);
1.1142 +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1143 +// if (!resG.graph->valid(out)) {
1.1144 +// out_or_in=0;
1.1145 +// resG.graph->first(in, v);
1.1146 +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1147 +// }
1.1148 +// }
1.1149 // public:
1.1150 // OutEdgeIt& operator++() {
1.1151 // if (out_or_in) {
1.1152 @@ -1049,39 +1221,95 @@
1.1153 // }
1.1154 // return *this;
1.1155 // }
1.1156 - };
1.1157 +// };
1.1158
1.1159 //FIXME This is just for having InEdgeIt
1.1160 // class InEdgeIt : public Edge { };
1.1161
1.1162 - class EdgeIt : public Edge {
1.1163 + class InEdgeIt {
1.1164 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1165 - NodeIt v;
1.1166 + protected:
1.1167 + typename Graph::OutEdgeIt out;
1.1168 + typename Graph::InEdgeIt in;
1.1169 + bool forward;
1.1170 + public:
1.1171 + InEdgeIt() { }
1.1172 + //FIXME
1.1173 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.1174 + InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.1175 +//the unique invalid iterator
1.1176 + InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
1.1177 + forward=true;
1.1178 + resG.graph->first(in, v);
1.1179 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.1180 + if (!resG.graph->valid(in)) {
1.1181 + forward=false;
1.1182 + resG.graph->first(out, v);
1.1183 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.1184 + }
1.1185 + }
1.1186 + operator Edge() const {
1.1187 +// Edge e;
1.1188 +// e.forward=this->forward;
1.1189 +// if (this->forward) e=out; else e=in;
1.1190 +// return e;
1.1191 + if (this->forward)
1.1192 + return Edge(in, this->forward);
1.1193 + else
1.1194 + return Edge(out, this->forward);
1.1195 + }
1.1196 + };
1.1197 +
1.1198 + class EdgeIt {
1.1199 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1200 + protected:
1.1201 + typename Graph::EdgeIt e;
1.1202 + bool forward;
1.1203 public:
1.1204 EdgeIt() { }
1.1205 - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1206 - EdgeIt(const Invalid& i) : Edge(i) { }
1.1207 - EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1208 - resG.graph->first(v);
1.1209 - if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1.1210 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1211 - while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1.1212 - resG.graph->next(v);
1.1213 - if (resG.graph->valid(v)) resG.graph->first(out, v);
1.1214 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1215 - }
1.1216 - if (!resG.graph->valid(out)) {
1.1217 - out_or_in=0;
1.1218 - resG.graph->first(v);
1.1219 - if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1.1220 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1221 - while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1.1222 - resG.graph->next(v);
1.1223 - if (resG.graph->valid(v)) resG.graph->first(in, v);
1.1224 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1225 - }
1.1226 + EdgeIt(const Invalid& i) : e(i), forward(false) { }
1.1227 + EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
1.1228 + forward=true;
1.1229 + resG.graph->first(e);
1.1230 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.1231 + if (!resG.graph->valid(e)) {
1.1232 + forward=false;
1.1233 + resG.graph->first(e);
1.1234 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.1235 }
1.1236 }
1.1237 + operator Edge() const {
1.1238 + return Edge(e, this->forward);
1.1239 + }
1.1240 + };
1.1241 +// class EdgeIt : public Edge {
1.1242 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1243 +// NodeIt v;
1.1244 +// public:
1.1245 +// EdgeIt() { }
1.1246 +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1247 +// EdgeIt(const Invalid& i) : Edge(i) { }
1.1248 +// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1249 +// resG.graph->first(v);
1.1250 +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1.1251 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1252 +// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1.1253 +// resG.graph->next(v);
1.1254 +// if (resG.graph->valid(v)) resG.graph->first(out, v);
1.1255 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1256 +// }
1.1257 +// if (!resG.graph->valid(out)) {
1.1258 +// out_or_in=0;
1.1259 +// resG.graph->first(v);
1.1260 +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1.1261 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1262 +// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1.1263 +// resG.graph->next(v);
1.1264 +// if (resG.graph->valid(v)) resG.graph->first(in, v);
1.1265 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1266 +// }
1.1267 +// }
1.1268 +// }
1.1269 // EdgeIt& operator++() {
1.1270 // if (out_or_in) {
1.1271 // ++out;
1.1272 @@ -1113,78 +1341,102 @@
1.1273 // }
1.1274 // return *this;
1.1275 // }
1.1276 - };
1.1277 +// };
1.1278
1.1279 NodeIt& first(NodeIt& i) const {
1.1280 - i=NodeIt(*this);
1.1281 - return i;
1.1282 + i=NodeIt(*this); return i;
1.1283 }
1.1284 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1285 - i=OutEdgeIt(*this, p);
1.1286 - return i;
1.1287 + i=OutEdgeIt(*this, p); return i;
1.1288 }
1.1289 - //FIXME Not yet implemented
1.1290 - //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1291 - //i=InEdgeIt(*this, p);
1.1292 - // return i;
1.1293 - //}
1.1294 - EdgeIt& first(EdgeIt& e) const {
1.1295 - e=EdgeIt(*this);
1.1296 - return e;
1.1297 +// FIXME not tested
1.1298 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1299 + i=InEdgeIt(*this, p); return i;
1.1300 + }
1.1301 + EdgeIt& first(EdgeIt& i) const {
1.1302 + i=EdgeIt(*this); return i;
1.1303 }
1.1304
1.1305 - NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1.1306 + NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.1307 OutEdgeIt& next(OutEdgeIt& e) const {
1.1308 - if (e.out_or_in) {
1.1309 + if (e.forward) {
1.1310 Node v=graph->aNode(e.out);
1.1311 graph->next(e.out);
1.1312 - while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1313 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1.1314 if (!graph->valid(e.out)) {
1.1315 - e.out_or_in=0;
1.1316 + e.forward=false;
1.1317 graph->first(e.in, v);
1.1318 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1319 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1.1320 }
1.1321 } else {
1.1322 graph->next(e.in);
1.1323 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1324 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1.1325 }
1.1326 return e;
1.1327 }
1.1328 - //FIXME Not yet implemented
1.1329 - //InEdgeIt& next(InEdgeIt& e) const {
1.1330 - // return e;
1.1331 - //}
1.1332 - EdgeIt& next(EdgeIt& e) const {
1.1333 - if (e.out_or_in) {
1.1334 +// FIXME Not tested
1.1335 + InEdgeIt& next(InEdgeIt& e) const {
1.1336 + if (e.forward) {
1.1337 + Node v=graph->aNode(e.in);
1.1338 + graph->next(e.in);
1.1339 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1.1340 + if (!graph->valid(e.in)) {
1.1341 + e.forward=false;
1.1342 + graph->first(e.out, v);
1.1343 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1.1344 + }
1.1345 + } else {
1.1346 graph->next(e.out);
1.1347 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1348 - while (graph->valid(e.v) && !graph->valid(e.out)) {
1.1349 - graph->next(e.v);
1.1350 - if (graph->valid(e.v)) graph->first(e.out, e.v);
1.1351 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1352 - }
1.1353 - if (!graph->valid(e.out)) {
1.1354 - e.out_or_in=0;
1.1355 - graph->first(e.v);
1.1356 - if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1.1357 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1358 - while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1359 - graph->next(e.v);
1.1360 - if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1361 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1362 - }
1.1363 - }
1.1364 - } else {
1.1365 - graph->next(e.in);
1.1366 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1367 - while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1368 - graph->next(e.v);
1.1369 - if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1370 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1371 - }
1.1372 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1.1373 + }
1.1374 + return e;
1.1375 + }
1.1376 + EdgeIt& next(EdgeIt& e) const {
1.1377 + if (e.forward) {
1.1378 + graph->next(e.e);
1.1379 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1.1380 + if (!graph->valid(e.e)) {
1.1381 + e.forward=false;
1.1382 + graph->first(e.e);
1.1383 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1.1384 }
1.1385 - return e;
1.1386 + } else {
1.1387 + graph->next(e.e);
1.1388 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1.1389 }
1.1390 + return e;
1.1391 + }
1.1392 +// EdgeIt& next(EdgeIt& e) const {
1.1393 +// if (e.out_or_in) {
1.1394 +// graph->next(e.out);
1.1395 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1396 +// while (graph->valid(e.v) && !graph->valid(e.out)) {
1.1397 +// graph->next(e.v);
1.1398 +// if (graph->valid(e.v)) graph->first(e.out, e.v);
1.1399 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1400 +// }
1.1401 +// if (!graph->valid(e.out)) {
1.1402 +// e.out_or_in=0;
1.1403 +// graph->first(e.v);
1.1404 +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1.1405 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1406 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1407 +// graph->next(e.v);
1.1408 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1409 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1410 +// }
1.1411 +// }
1.1412 +// } else {
1.1413 +// graph->next(e.in);
1.1414 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1415 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1416 +// graph->next(e.v);
1.1417 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1418 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1419 +// }
1.1420 +// }
1.1421 +// return e;
1.1422 +// }
1.1423
1.1424
1.1425 template< typename It >
1.1426 @@ -1202,53 +1454,55 @@
1.1427 }
1.1428
1.1429 Node tail(Edge e) const {
1.1430 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1431 + return ((e.forward) ? graph->tail(e) : graph->head(e)); }
1.1432 Node head(Edge e) const {
1.1433 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1434 + return ((e.forward) ? graph->head(e) : graph->tail(e)); }
1.1435
1.1436 Node aNode(OutEdgeIt e) const {
1.1437 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1438 + return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1439 Node bNode(OutEdgeIt e) const {
1.1440 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1441 + return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1442
1.1443 int nodeNum() const { return graph->nodeNum(); }
1.1444 //FIXME
1.1445 //int edgeNum() const { return graph->edgeNum(); }
1.1446
1.1447
1.1448 - int id(Node v) const { return graph->id(v); }
1.1449 +// int id(Node v) const { return graph->id(v); }
1.1450
1.1451 - bool valid(Node n) const { return graph->valid(n); }
1.1452 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.1453 bool valid(Edge e) const {
1.1454 - return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1.1455 + return graph->valid(e);
1.1456 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.1457 + }
1.1458
1.1459 void augment(const Edge& e, Number a) const {
1.1460 - if (e.out_or_in)
1.1461 + if (e.forward)
1.1462 // flow->set(e.out, flow->get(e.out)+a);
1.1463 - flow->set(e.out, (*flow)[e.out]+a);
1.1464 + flow->set(e, (*flow)[e]+a);
1.1465 else
1.1466 // flow->set(e.in, flow->get(e.in)-a);
1.1467 - flow->set(e.in, (*flow)[e.in]-a);
1.1468 + flow->set(e, (*flow)[e]-a);
1.1469 }
1.1470
1.1471 Number resCap(const Edge& e) const {
1.1472 - if (e.out_or_in)
1.1473 + if (e.forward)
1.1474 // return (capacity->get(e.out)-flow->get(e.out));
1.1475 - return ((*capacity)[e.out]-(*flow)[e.out]);
1.1476 + return ((*capacity)[e]-(*flow)[e]);
1.1477 else
1.1478 // return (flow->get(e.in));
1.1479 - return ((*flow)[e.in]);
1.1480 + return ((*flow)[e]);
1.1481 }
1.1482
1.1483 - Number resCap(GraphOutEdgeIt out) const {
1.1484 -// return (capacity->get(out)-flow->get(out));
1.1485 - return ((*capacity)[out]-(*flow)[out]);
1.1486 - }
1.1487 +// Number resCap(typename Graph::OutEdgeIt out) const {
1.1488 +// // return (capacity->get(out)-flow->get(out));
1.1489 +// return ((*capacity)[out]-(*flow)[out]);
1.1490 +// }
1.1491
1.1492 - Number resCap(GraphInEdgeIt in) const {
1.1493 -// return (flow->get(in));
1.1494 - return ((*flow)[in]);
1.1495 - }
1.1496 +// Number resCap(typename Graph::InEdgeIt in) const {
1.1497 +// // return (flow->get(in));
1.1498 +// return ((*flow)[in]);
1.1499 +// }
1.1500
1.1501 // template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.1502 // public:
1.1503 @@ -1275,13 +1529,13 @@
1.1504 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.1505 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.1506 void set(Edge e, T a) {
1.1507 - if (e.out_or_in)
1.1508 + if (e.forward)
1.1509 forward_map.set(e.out, a);
1.1510 else
1.1511 backward_map.set(e.in, a);
1.1512 }
1.1513 T operator[](Edge e) const {
1.1514 - if (e.out_or_in)
1.1515 + if (e.forward)
1.1516 return forward_map[e.out];
1.1517 else
1.1518 return backward_map[e.in];
1.1519 @@ -1295,6 +1549,336 @@
1.1520 };
1.1521 };
1.1522
1.1523 +
1.1524 +
1.1525 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1526 +// class ResGraphWrapper : public GraphWrapper<Graph> {
1.1527 +// protected:
1.1528 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.1529 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.1530 +// typedef typename Graph::Edge GraphEdge;
1.1531 +// FlowMap* flow;
1.1532 +// const CapacityMap* capacity;
1.1533 +// public:
1.1534 +
1.1535 +// ResGraphWrapper(Graph& _graph, FlowMap& _flow,
1.1536 +// const CapacityMap& _capacity) :
1.1537 +// GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
1.1538 +
1.1539 +// class Edge;
1.1540 +// class OutEdgeIt;
1.1541 +// friend class Edge;
1.1542 +// friend class OutEdgeIt;
1.1543 +
1.1544 +// typedef typename GraphWrapper<Graph>::Node Node;
1.1545 +// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.1546 +// class Edge {
1.1547 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1548 +// protected:
1.1549 +// bool out_or_in; //true, iff out
1.1550 +// GraphOutEdgeIt out;
1.1551 +// GraphInEdgeIt in;
1.1552 +// public:
1.1553 +// Edge() : out_or_in(true) { }
1.1554 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.1555 +// // bool valid() const {
1.1556 +// // return out_or_in && out.valid() || in.valid(); }
1.1557 +// friend bool operator==(const Edge& u, const Edge& v) {
1.1558 +// if (v.out_or_in)
1.1559 +// return (u.out_or_in && u.out==v.out);
1.1560 +// else
1.1561 +// return (!u.out_or_in && u.in==v.in);
1.1562 +// }
1.1563 +// friend bool operator!=(const Edge& u, const Edge& v) {
1.1564 +// if (v.out_or_in)
1.1565 +// return (!u.out_or_in || u.out!=v.out);
1.1566 +// else
1.1567 +// return (u.out_or_in || u.in!=v.in);
1.1568 +// }
1.1569 +// operator GraphEdge() const {
1.1570 +// if (out_or_in) return(out); else return(in);
1.1571 +// }
1.1572 +// };
1.1573 +// class OutEdgeIt : public Edge {
1.1574 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1575 +// public:
1.1576 +// OutEdgeIt() { }
1.1577 +// //FIXME
1.1578 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.1579 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1580 +// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1581 +// resG.graph->first(out, v);
1.1582 +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1583 +// if (!resG.graph->valid(out)) {
1.1584 +// out_or_in=0;
1.1585 +// resG.graph->first(in, v);
1.1586 +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1587 +// }
1.1588 +// }
1.1589 +// // public:
1.1590 +// // OutEdgeIt& operator++() {
1.1591 +// // if (out_or_in) {
1.1592 +// // Node v=/*resG->*/G->aNode(out);
1.1593 +// // ++out;
1.1594 +// // while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1595 +// // if (!out.valid()) {
1.1596 +// // out_or_in=0;
1.1597 +// // G->first(in, v);
1.1598 +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1599 +// // }
1.1600 +// // } else {
1.1601 +// // ++in;
1.1602 +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1603 +// // }
1.1604 +// // return *this;
1.1605 +// // }
1.1606 +// };
1.1607 +
1.1608 +// //FIXME This is just for having InEdgeIt
1.1609 +// // class InEdgeIt : public Edge { };
1.1610 +
1.1611 +// class EdgeIt : public Edge {
1.1612 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.1613 +// NodeIt v;
1.1614 +// public:
1.1615 +// EdgeIt() { }
1.1616 +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1617 +// EdgeIt(const Invalid& i) : Edge(i) { }
1.1618 +// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1619 +// resG.graph->first(v);
1.1620 +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1.1621 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1622 +// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1.1623 +// resG.graph->next(v);
1.1624 +// if (resG.graph->valid(v)) resG.graph->first(out, v);
1.1625 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1.1626 +// }
1.1627 +// if (!resG.graph->valid(out)) {
1.1628 +// out_or_in=0;
1.1629 +// resG.graph->first(v);
1.1630 +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1.1631 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1632 +// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1.1633 +// resG.graph->next(v);
1.1634 +// if (resG.graph->valid(v)) resG.graph->first(in, v);
1.1635 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1.1636 +// }
1.1637 +// }
1.1638 +// }
1.1639 +// // EdgeIt& operator++() {
1.1640 +// // if (out_or_in) {
1.1641 +// // ++out;
1.1642 +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1643 +// // while (v.valid() && !out.valid()) {
1.1644 +// // ++v;
1.1645 +// // if (v.valid()) G->first(out, v);
1.1646 +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1647 +// // }
1.1648 +// // if (!out.valid()) {
1.1649 +// // out_or_in=0;
1.1650 +// // G->first(v);
1.1651 +// // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
1.1652 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1653 +// // while (v.valid() && !in.valid()) {
1.1654 +// // ++v;
1.1655 +// // if (v.valid()) G->first(in, v);
1.1656 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1657 +// // }
1.1658 +// // }
1.1659 +// // } else {
1.1660 +// // ++in;
1.1661 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1662 +// // while (v.valid() && !in.valid()) {
1.1663 +// // ++v;
1.1664 +// // if (v.valid()) G->first(in, v);
1.1665 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1666 +// // }
1.1667 +// // }
1.1668 +// // return *this;
1.1669 +// // }
1.1670 +// };
1.1671 +
1.1672 +// NodeIt& first(NodeIt& i) const {
1.1673 +// i=NodeIt(*this);
1.1674 +// return i;
1.1675 +// }
1.1676 +// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1677 +// i=OutEdgeIt(*this, p);
1.1678 +// return i;
1.1679 +// }
1.1680 +// //FIXME Not yet implemented
1.1681 +// //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1682 +// //i=InEdgeIt(*this, p);
1.1683 +// // return i;
1.1684 +// //}
1.1685 +// EdgeIt& first(EdgeIt& e) const {
1.1686 +// e=EdgeIt(*this);
1.1687 +// return e;
1.1688 +// }
1.1689 +
1.1690 +// NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1.1691 +// OutEdgeIt& next(OutEdgeIt& e) const {
1.1692 +// if (e.out_or_in) {
1.1693 +// Node v=graph->aNode(e.out);
1.1694 +// graph->next(e.out);
1.1695 +// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1696 +// if (!graph->valid(e.out)) {
1.1697 +// e.out_or_in=0;
1.1698 +// graph->first(e.in, v);
1.1699 +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1700 +// }
1.1701 +// } else {
1.1702 +// graph->next(e.in);
1.1703 +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1704 +// }
1.1705 +// return e;
1.1706 +// }
1.1707 +// //FIXME Not yet implemented
1.1708 +// //InEdgeIt& next(InEdgeIt& e) const {
1.1709 +// // return e;
1.1710 +// //}
1.1711 +// EdgeIt& next(EdgeIt& e) const {
1.1712 +// if (e.out_or_in) {
1.1713 +// graph->next(e.out);
1.1714 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1715 +// while (graph->valid(e.v) && !graph->valid(e.out)) {
1.1716 +// graph->next(e.v);
1.1717 +// if (graph->valid(e.v)) graph->first(e.out, e.v);
1.1718 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1.1719 +// }
1.1720 +// if (!graph->valid(e.out)) {
1.1721 +// e.out_or_in=0;
1.1722 +// graph->first(e.v);
1.1723 +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1.1724 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1725 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1726 +// graph->next(e.v);
1.1727 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1728 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1729 +// }
1.1730 +// }
1.1731 +// } else {
1.1732 +// graph->next(e.in);
1.1733 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1734 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
1.1735 +// graph->next(e.v);
1.1736 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
1.1737 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1.1738 +// }
1.1739 +// }
1.1740 +// return e;
1.1741 +// }
1.1742 +
1.1743 +
1.1744 +// template< typename It >
1.1745 +// It first() const {
1.1746 +// It e;
1.1747 +// first(e);
1.1748 +// return e;
1.1749 +// }
1.1750 +
1.1751 +// template< typename It >
1.1752 +// It first(Node v) const {
1.1753 +// It e;
1.1754 +// first(e, v);
1.1755 +// return e;
1.1756 +// }
1.1757 +
1.1758 +// Node tail(Edge e) const {
1.1759 +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1760 +// Node head(Edge e) const {
1.1761 +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1762 +
1.1763 +// Node aNode(OutEdgeIt e) const {
1.1764 +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1.1765 +// Node bNode(OutEdgeIt e) const {
1.1766 +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1.1767 +
1.1768 +// int nodeNum() const { return graph->nodeNum(); }
1.1769 +// //FIXME
1.1770 +// //int edgeNum() const { return graph->edgeNum(); }
1.1771 +
1.1772 +
1.1773 +// int id(Node v) const { return graph->id(v); }
1.1774 +
1.1775 +// bool valid(Node n) const { return graph->valid(n); }
1.1776 +// bool valid(Edge e) const {
1.1777 +// return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1.1778 +
1.1779 +// void augment(const Edge& e, Number a) const {
1.1780 +// if (e.out_or_in)
1.1781 +// // flow->set(e.out, flow->get(e.out)+a);
1.1782 +// flow->set(e.out, (*flow)[e.out]+a);
1.1783 +// else
1.1784 +// // flow->set(e.in, flow->get(e.in)-a);
1.1785 +// flow->set(e.in, (*flow)[e.in]-a);
1.1786 +// }
1.1787 +
1.1788 +// Number resCap(const Edge& e) const {
1.1789 +// if (e.out_or_in)
1.1790 +// // return (capacity->get(e.out)-flow->get(e.out));
1.1791 +// return ((*capacity)[e.out]-(*flow)[e.out]);
1.1792 +// else
1.1793 +// // return (flow->get(e.in));
1.1794 +// return ((*flow)[e.in]);
1.1795 +// }
1.1796 +
1.1797 +// Number resCap(GraphOutEdgeIt out) const {
1.1798 +// // return (capacity->get(out)-flow->get(out));
1.1799 +// return ((*capacity)[out]-(*flow)[out]);
1.1800 +// }
1.1801 +
1.1802 +// Number resCap(GraphInEdgeIt in) const {
1.1803 +// // return (flow->get(in));
1.1804 +// return ((*flow)[in]);
1.1805 +// }
1.1806 +
1.1807 +// // template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.1808 +// // public:
1.1809 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1.1810 +// // : Graph::NodeMap<T>(_G.gw) { }
1.1811 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1.1812 +// // T a) : Graph::NodeMap<T>(_G.gw, a) { }
1.1813 +// // };
1.1814 +
1.1815 +// // template <typename T>
1.1816 +// // class NodeMap {
1.1817 +// // typename Graph::NodeMap<T> node_map;
1.1818 +// // public:
1.1819 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1.1820 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1.1821 +// // void set(Node nit, T a) { node_map.set(nit, a); }
1.1822 +// // T get(Node nit) const { return node_map.get(nit); }
1.1823 +// // };
1.1824 +
1.1825 +// template <typename T>
1.1826 +// class EdgeMap {
1.1827 +// typename Graph::EdgeMap<T> forward_map, backward_map;
1.1828 +// public:
1.1829 +// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.1830 +// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.1831 +// void set(Edge e, T a) {
1.1832 +// if (e.out_or_in)
1.1833 +// forward_map.set(e.out, a);
1.1834 +// else
1.1835 +// backward_map.set(e.in, a);
1.1836 +// }
1.1837 +// T operator[](Edge e) const {
1.1838 +// if (e.out_or_in)
1.1839 +// return forward_map[e.out];
1.1840 +// else
1.1841 +// return backward_map[e.in];
1.1842 +// }
1.1843 +// // T get(Edge e) const {
1.1844 +// // if (e.out_or_in)
1.1845 +// // return forward_map.get(e.out);
1.1846 +// // else
1.1847 +// // return backward_map.get(e.in);
1.1848 +// // }
1.1849 +// };
1.1850 +// };
1.1851 +
1.1852 +
1.1853 //ErasingFirstGraphWrapper for blocking flows
1.1854 template<typename Graph, typename FirstOutEdgesMap>
1.1855 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.1856 @@ -1305,60 +1889,74 @@
1.1857 FirstOutEdgesMap& _first_out_edges) :
1.1858 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.1859
1.1860 - typedef typename Graph::Node Node;
1.1861 - class NodeIt : public Graph::NodeIt {
1.1862 - public:
1.1863 + typedef typename GraphWrapper<Graph>::Node Node;
1.1864 + class NodeIt {
1.1865 + friend class GraphWrapper<Graph>;
1.1866 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.1867 + typename Graph::NodeIt n;
1.1868 + public:
1.1869 NodeIt() { }
1.1870 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.1871 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.1872 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.1873 + NodeIt(const Invalid& i) : n(i) { }
1.1874 NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.1875 - Graph::NodeIt(*(_G.graph)) { }
1.1876 + n(*(_G.graph)) { }
1.1877 + operator Node() const { return Node(typename Graph::Node(n)); }
1.1878 };
1.1879 - typedef typename Graph::Edge Edge;
1.1880 - class OutEdgeIt : public Graph::OutEdgeIt {
1.1881 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.1882 + class OutEdgeIt {
1.1883 + friend class GraphWrapper<Graph>;
1.1884 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.1885 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.1886 + typename Graph::OutEdgeIt e;
1.1887 public:
1.1888 OutEdgeIt() { }
1.1889 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.1890 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.1891 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.1892 + OutEdgeIt(const Invalid& i) : e(i) { }
1.1893 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.1894 - const Node& n) :
1.1895 - Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
1.1896 + const Node& _n) :
1.1897 + e((*_G.first_out_edges)[_n]) { }
1.1898 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.1899 };
1.1900 - class InEdgeIt : public Graph::InEdgeIt {
1.1901 + class InEdgeIt {
1.1902 + friend class GraphWrapper<Graph>;
1.1903 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.1904 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.1905 + typename Graph::InEdgeIt e;
1.1906 public:
1.1907 InEdgeIt() { }
1.1908 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.1909 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.1910 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.1911 + InEdgeIt(const Invalid& i) : e(i) { }
1.1912 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.1913 - const Node& n) :
1.1914 - Graph::InEdgeIt(*(_G.graph), n) { }
1.1915 + const Node& _n) :
1.1916 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.1917 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.1918 };
1.1919 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1920 - class EdgeIt : public Graph::EdgeIt {
1.1921 + class EdgeIt {
1.1922 + friend class GraphWrapper<Graph>;
1.1923 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.1924 +// typedef typename Graph::EdgeIt GraphEdgeIt;
1.1925 + typename Graph::EdgeIt e;
1.1926 public:
1.1927 EdgeIt() { }
1.1928 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.1929 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.1930 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.1931 + EdgeIt(const Invalid& i) : e(i) { }
1.1932 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.1933 - Graph::EdgeIt(*(_G.graph)) { }
1.1934 + e(*(_G.graph)) { }
1.1935 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.1936 };
1.1937
1.1938 - NodeIt& first(NodeIt& i) const {
1.1939 - i=NodeIt(*this);
1.1940 - return i;
1.1941 + NodeIt& first(NodeIt& i) const {
1.1942 + i=NodeIt(*this); return i;
1.1943 }
1.1944 - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.1945 - i=OutEdgeIt(*this, n);
1.1946 -// i=(*first_out_edges)[n];
1.1947 - return i;
1.1948 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1949 + i=OutEdgeIt(*this, p); return i;
1.1950 }
1.1951 - InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.1952 - i=InEdgeIt(*this, n);
1.1953 - return i;
1.1954 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1955 + i=InEdgeIt(*this, p); return i;
1.1956 }
1.1957 - EdgeIt& first(EdgeIt& i) const {
1.1958 - i=EdgeIt(*this);
1.1959 - return i;
1.1960 + EdgeIt& first(EdgeIt& i) const {
1.1961 + i=EdgeIt(*this); return i;
1.1962 }
1.1963
1.1964 // template<typename I> I& first(I& i) const {
1.1965 @@ -1380,22 +1978,15 @@
1.1966 //}
1.1967
1.1968
1.1969 - NodeIt& next(NodeIt& i) const {
1.1970 - graph->next(i);
1.1971 - return i;
1.1972 - }
1.1973 - OutEdgeIt& next(OutEdgeIt& i) const {
1.1974 - graph->next(i);
1.1975 - return i;
1.1976 - }
1.1977 - InEdgeIt& next(InEdgeIt& i) const {
1.1978 - graph->next(i);
1.1979 - return i;
1.1980 - }
1.1981 - EdgeIt& next(EdgeIt& i) const {
1.1982 - graph->next(i);
1.1983 - return i;
1.1984 - }
1.1985 + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.1986 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1.1987 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1.1988 + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1.1989 +
1.1990 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.1991 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.1992 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.1993 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.1994
1.1995 // template<typename I> I& next(I &i) const {
1.1996 // graph->next(i);
1.1997 @@ -1411,10 +2002,131 @@
1.1998 void erase(const OutEdgeIt& e) const {
1.1999 OutEdgeIt f=e;
1.2000 this->next(f);
1.2001 - first_out_edges->set(this->tail(e), f);
1.2002 + first_out_edges->set(this->tail(e), f.e);
1.2003 }
1.2004 };
1.2005
1.2006 +// //ErasingFirstGraphWrapper for blocking flows
1.2007 +// template<typename Graph, typename FirstOutEdgesMap>
1.2008 +// class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.2009 +// protected:
1.2010 +// FirstOutEdgesMap* first_out_edges;
1.2011 +// public:
1.2012 +// ErasingFirstGraphWrapper(Graph& _graph,
1.2013 +// FirstOutEdgesMap& _first_out_edges) :
1.2014 +// GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.2015 +
1.2016 +// typedef typename Graph::Node Node;
1.2017 +// class NodeIt : public Graph::NodeIt {
1.2018 +// public:
1.2019 +// NodeIt() { }
1.2020 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.2021 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.2022 +// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.2023 +// Graph::NodeIt(*(_G.graph)) { }
1.2024 +// };
1.2025 +// typedef typename Graph::Edge Edge;
1.2026 +// class OutEdgeIt : public Graph::OutEdgeIt {
1.2027 +// public:
1.2028 +// OutEdgeIt() { }
1.2029 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.2030 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.2031 +// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.2032 +// const Node& n) :
1.2033 +// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
1.2034 +// };
1.2035 +// class InEdgeIt : public Graph::InEdgeIt {
1.2036 +// public:
1.2037 +// InEdgeIt() { }
1.2038 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.2039 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.2040 +// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.2041 +// const Node& n) :
1.2042 +// Graph::InEdgeIt(*(_G.graph), n) { }
1.2043 +// };
1.2044 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.2045 +// class EdgeIt : public Graph::EdgeIt {
1.2046 +// public:
1.2047 +// EdgeIt() { }
1.2048 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.2049 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.2050 +// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.2051 +// Graph::EdgeIt(*(_G.graph)) { }
1.2052 +// };
1.2053 +
1.2054 +// NodeIt& first(NodeIt& i) const {
1.2055 +// i=NodeIt(*this);
1.2056 +// return i;
1.2057 +// }
1.2058 +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.2059 +// i=OutEdgeIt(*this, n);
1.2060 +// // i=(*first_out_edges)[n];
1.2061 +// return i;
1.2062 +// }
1.2063 +// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.2064 +// i=InEdgeIt(*this, n);
1.2065 +// return i;
1.2066 +// }
1.2067 +// EdgeIt& first(EdgeIt& i) const {
1.2068 +// i=EdgeIt(*this);
1.2069 +// return i;
1.2070 +// }
1.2071 +
1.2072 +// // template<typename I> I& first(I& i) const {
1.2073 +// // graph->first(i);
1.2074 +// // return i;
1.2075 +// // }
1.2076 +// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.2077 +// // // e=first_out_edges->get(n);
1.2078 +// // e=(*first_out_edges)[n];
1.2079 +// // return e;
1.2080 +// // }
1.2081 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.2082 +// // graph->first(i, p);
1.2083 +// // return i;
1.2084 +// // }
1.2085 +
1.2086 +// //template<typename I> I getNext(const I& i) const {
1.2087 +// // return gw.getNext(i);
1.2088 +// //}
1.2089 +
1.2090 +
1.2091 +// NodeIt& next(NodeIt& i) const {
1.2092 +// graph->next(i);
1.2093 +// return i;
1.2094 +// }
1.2095 +// OutEdgeIt& next(OutEdgeIt& i) const {
1.2096 +// graph->next(i);
1.2097 +// return i;
1.2098 +// }
1.2099 +// InEdgeIt& next(InEdgeIt& i) const {
1.2100 +// graph->next(i);
1.2101 +// return i;
1.2102 +// }
1.2103 +// EdgeIt& next(EdgeIt& i) const {
1.2104 +// graph->next(i);
1.2105 +// return i;
1.2106 +// }
1.2107 +
1.2108 +// // template<typename I> I& next(I &i) const {
1.2109 +// // graph->next(i);
1.2110 +// // return i;
1.2111 +// // }
1.2112 +
1.2113 +// template< typename It > It first() const {
1.2114 +// It e; this->first(e); return e; }
1.2115 +
1.2116 +// template< typename It > It first(const Node& v) const {
1.2117 +// It e; this->first(e, v); return e; }
1.2118 +
1.2119 +// void erase(const OutEdgeIt& e) const {
1.2120 +// OutEdgeIt f=e;
1.2121 +// this->next(f);
1.2122 +// first_out_edges->set(this->tail(e), f);
1.2123 +// }
1.2124 +// };
1.2125 +
1.2126 +
1.2127 // // FIXME: comparison should be made better!!!
1.2128 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.2129 // class ResGraphWrapper