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