1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/experiment/graph_wrapper_st_ostream_op.h Tue Apr 27 13:53:27 2004 +0000
1.3 @@ -0,0 +1,1653 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_GRAPH_WRAPPER_H
1.6 +#define HUGO_GRAPH_WRAPPER_H
1.7 +
1.8 +#include <invalid.h>
1.9 +#include <iter_map.h>
1.10 +
1.11 +namespace hugo {
1.12 +
1.13 + // Graph wrappers
1.14 +
1.15 + /// \addtogroup gwrappers
1.16 + /// A main parts of HUGOlib are the different graph structures,
1.17 + /// generic graph algorithms, graph concepts which couple these, and
1.18 + /// graph wrappers. While the previous ones are more or less clear, the
1.19 + /// latter notion needs further explanation.
1.20 + /// Graph wrappers are graph classes which serve for considering graph
1.21 + /// structures in different ways. A short example makes the notion much
1.22 + /// clearer.
1.23 + /// Suppose that we have an instance \c g of a directed graph
1.24 + /// type say \c ListGraph and an algorithm
1.25 + /// \code template<typename Graph> int algorithm(const Graph&); \endcode
1.26 + /// is needed to run on the reversely oriented graph.
1.27 + /// It may be expensive (in time or in memory usage) to copy
1.28 + /// \c g with the reverse orientation.
1.29 + /// Thus, a wrapper class
1.30 + /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.31 + /// The code looks as follows
1.32 + /// \code
1.33 + /// ListGraph g;
1.34 + /// RevGraphWrapper<ListGraph> rgw(g);
1.35 + /// int result=algorithm(rgw);
1.36 + /// \endcode
1.37 + /// After running the algorithm, the original graph \c g
1.38 + /// remains untouched. Thus the graph wrapper used above is to consider the
1.39 + /// original graph with reverse orientation.
1.40 + /// This techniques gives rise to an elegant code, and
1.41 + /// based on stable graph wrappers, complex algorithms can be
1.42 + /// implemented easily.
1.43 + /// In flow, circulation and bipartite matching problems, the residual
1.44 + /// graph is of particular importance. Combining a wrapper implementing
1.45 + /// this, shortest path algorithms and minimum mean cycle algorithms,
1.46 + /// a range of weighted and cardinality optimization algorithms can be
1.47 + /// obtained. For lack of space, for other examples,
1.48 + /// the interested user is referred to the detailed documentation of graph
1.49 + /// wrappers.
1.50 + /// The behavior of graph wrappers can be very different. Some of them keep
1.51 + /// capabilities of the original graph while in other cases this would be
1.52 + /// meaningless. This means that the concepts that they are a model of depend
1.53 + /// on the graph wrapper, and the wrapped graph(s).
1.54 + /// If an edge of \c rgw is deleted, this is carried out by
1.55 + /// deleting the corresponding edge of \c g. But for a residual
1.56 + /// graph, this operation has no sense.
1.57 + /// Let we stand one more example here to simplify your work.
1.58 + /// wrapper class
1.59 + /// \code template<typename Graph> class RevGraphWrapper; \endcode
1.60 + /// has constructor
1.61 + /// <tt> RevGraphWrapper(Graph& _g)</tt>.
1.62 + /// This means that in a situation,
1.63 + /// when a <tt> const ListGraph& </tt> reference to a graph is given,
1.64 + /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
1.65 + /// \code
1.66 + /// int algorithm1(const ListGraph& g) {
1.67 + /// RevGraphWrapper<const ListGraph> rgw(g);
1.68 + /// return algorithm2(rgw);
1.69 + /// }
1.70 + /// \endcode
1.71 +
1.72 + /// \addtogroup gwrappers
1.73 + /// @{
1.74 +
1.75 + ///Base type for the Graph Wrappers
1.76 +
1.77 + ///This is the base type for the Graph Wrappers.
1.78 + ///\todo Some more docs...
1.79 +
1.80 + template<typename Graph>
1.81 + class GraphWrapper {
1.82 + protected:
1.83 + Graph* graph;
1.84 +
1.85 + public:
1.86 + typedef Graph BaseGraph;
1.87 + typedef Graph ParentGraph;
1.88 +
1.89 +// GraphWrapper() : graph(0) { }
1.90 + GraphWrapper(Graph& _graph) : graph(&_graph) { }
1.91 +// void setGraph(Graph& _graph) { graph=&_graph; }
1.92 +// Graph& getGraph() const { return *graph; }
1.93 +
1.94 +// typedef typename Graph::Node Node;
1.95 + class Node : public Graph::Node {
1.96 + friend class GraphWrapper<Graph>;
1.97 + public:
1.98 + Node() { }
1.99 + Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
1.100 + Node(const Invalid& i) : Graph::Node(i) { }
1.101 + };
1.102 + class NodeIt {
1.103 + friend class GraphWrapper<Graph>;
1.104 + typename Graph::NodeIt n;
1.105 + public:
1.106 + NodeIt() { }
1.107 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.108 + NodeIt(const Invalid& i) : n(i) { }
1.109 + NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
1.110 + operator Node() const { return Node(typename Graph::Node(n)); }
1.111 + };
1.112 +// typedef typename Graph::Edge Edge;
1.113 + class Edge : public Graph::Edge {
1.114 + friend class GraphWrapper<Graph>;
1.115 + public:
1.116 + Edge() { }
1.117 + Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
1.118 + Edge(const Invalid& i) : Graph::Edge(i) { }
1.119 + };
1.120 + class OutEdgeIt {
1.121 + friend class GraphWrapper<Graph>;
1.122 + typename Graph::OutEdgeIt e;
1.123 + public:
1.124 + OutEdgeIt() { }
1.125 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.126 + OutEdgeIt(const Invalid& i) : e(i) { }
1.127 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.128 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.129 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.130 + };
1.131 + class InEdgeIt {
1.132 + friend class GraphWrapper<Graph>;
1.133 + typename Graph::InEdgeIt e;
1.134 + public:
1.135 + InEdgeIt() { }
1.136 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.137 + InEdgeIt(const Invalid& i) : e(i) { }
1.138 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1.139 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.140 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.141 + };
1.142 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.143 + class EdgeIt {
1.144 + friend class GraphWrapper<Graph>;
1.145 + typename Graph::EdgeIt e;
1.146 + public:
1.147 + EdgeIt() { }
1.148 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.149 + EdgeIt(const Invalid& i) : e(i) { }
1.150 + EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
1.151 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.152 + };
1.153 +
1.154 + NodeIt& first(NodeIt& i) const {
1.155 + i=NodeIt(*this); return i;
1.156 + }
1.157 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.158 + i=OutEdgeIt(*this, p); return i;
1.159 + }
1.160 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.161 + i=InEdgeIt(*this, p); return i;
1.162 + }
1.163 + EdgeIt& first(EdgeIt& i) const {
1.164 + i=EdgeIt(*this); return i;
1.165 + }
1.166 +
1.167 + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.168 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1.169 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1.170 + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1.171 +
1.172 + Node tail(const Edge& e) const {
1.173 + return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1.174 + Node head(const Edge& e) const {
1.175 + return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1.176 +
1.177 + bool valid(const Node& n) const {
1.178 + return graph->valid(static_cast<typename Graph::Node>(n)); }
1.179 + bool valid(const Edge& e) const {
1.180 + return graph->valid(static_cast<typename Graph::Edge>(e)); }
1.181 +
1.182 + int nodeNum() const { return graph->nodeNum(); }
1.183 + int edgeNum() const { return graph->edgeNum(); }
1.184 +
1.185 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.186 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1.187 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.188 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1.189 +
1.190 + Node addNode() const { return Node(graph->addNode()); }
1.191 + Edge addEdge(const Node& tail, const Node& head) const {
1.192 + return Edge(graph->addEdge(tail, head)); }
1.193 +
1.194 + void erase(const Node& i) const { graph->erase(i); }
1.195 + void erase(const Edge& i) const { graph->erase(i); }
1.196 +
1.197 + void clear() const { graph->clear(); }
1.198 +
1.199 + template<typename T> class NodeMap : public Graph::template NodeMap<T> {
1.200 + typedef typename Graph::template NodeMap<T> Parent;
1.201 + public:
1.202 + NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
1.203 + NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
1.204 + };
1.205 +
1.206 + template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
1.207 + typedef typename Graph::template EdgeMap<T> Parent;
1.208 + public:
1.209 + EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
1.210 + EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
1.211 + };
1.212 + };
1.213 +
1.214 + /// A graph wrapper which reverses the orientation of the edges.
1.215 +
1.216 + /// A graph wrapper which reverses the orientation of the edges.
1.217 + template<typename Graph>
1.218 + class RevGraphWrapper : public GraphWrapper<Graph> {
1.219 + public:
1.220 +
1.221 + RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.222 +
1.223 + typedef typename GraphWrapper<Graph>::Node Node;
1.224 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.225 + //If Graph::OutEdgeIt is not defined
1.226 + //and we do not want to use RevGraphWrapper::InEdgeIt,
1.227 + //the typdef techinque does not work.
1.228 + //Unfortunately all the typedefs are instantiated in templates.
1.229 + //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
1.230 + //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
1.231 +
1.232 + class OutEdgeIt {
1.233 + friend class GraphWrapper<Graph>;
1.234 + friend class RevGraphWrapper<Graph>;
1.235 + typename Graph::InEdgeIt e;
1.236 + public:
1.237 + OutEdgeIt() { }
1.238 + OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.239 + OutEdgeIt(const Invalid& i) : e(i) { }
1.240 + OutEdgeIt(const RevGraphWrapper<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 {
1.245 + friend class GraphWrapper<Graph>;
1.246 + friend class RevGraphWrapper<Graph>;
1.247 + typename Graph::OutEdgeIt e;
1.248 + public:
1.249 + InEdgeIt() { }
1.250 + InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.251 + InEdgeIt(const Invalid& i) : e(i) { }
1.252 + InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
1.253 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.254 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.255 + };
1.256 +
1.257 + using GraphWrapper<Graph>::first;
1.258 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.259 + i=OutEdgeIt(*this, p); return i;
1.260 + }
1.261 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.262 + i=InEdgeIt(*this, p); return i;
1.263 + }
1.264 +
1.265 + using GraphWrapper<Graph>::next;
1.266 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.267 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.268 +
1.269 + Node aNode(const OutEdgeIt& e) const {
1.270 + return Node(this->graph->aNode(e.e)); }
1.271 + Node aNode(const InEdgeIt& e) const {
1.272 + return Node(this->graph->aNode(e.e)); }
1.273 + Node bNode(const OutEdgeIt& e) const {
1.274 + return Node(this->graph->bNode(e.e)); }
1.275 + Node bNode(const InEdgeIt& e) const {
1.276 + return Node(this->graph->bNode(e.e)); }
1.277 +
1.278 + Node tail(const Edge& e) const {
1.279 + return GraphWrapper<Graph>::head(e); }
1.280 + Node head(const Edge& e) const {
1.281 + return GraphWrapper<Graph>::tail(e); }
1.282 +
1.283 + };
1.284 +
1.285 + /// Wrapper for hiding nodes and edges from a graph.
1.286 +
1.287 + /// This wrapper shows a graph with filtered node-set and
1.288 + /// edge-set. The quick brown fox iterator jumps over
1.289 + /// the lazy dog nodes or edges if the values for them are false
1.290 + /// in the bool maps.
1.291 + template<typename Graph, typename NodeFilterMap,
1.292 + typename EdgeFilterMap>
1.293 + class SubGraphWrapper : public GraphWrapper<Graph> {
1.294 + protected:
1.295 + NodeFilterMap* node_filter_map;
1.296 + EdgeFilterMap* edge_filter_map;
1.297 + public:
1.298 +
1.299 + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.300 + EdgeFilterMap& _edge_filter_map) :
1.301 + GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.302 + edge_filter_map(&_edge_filter_map) { }
1.303 +
1.304 + typedef typename GraphWrapper<Graph>::Node Node;
1.305 + class NodeIt {
1.306 + friend class GraphWrapper<Graph>;
1.307 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.308 + typename Graph::NodeIt n;
1.309 + public:
1.310 + NodeIt() { }
1.311 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.312 + NodeIt(const Invalid& i) : n(i) { }
1.313 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.314 + n(*(_G.graph)) {
1.315 + while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.316 + _G.graph->next(n);
1.317 + }
1.318 + operator Node() const { return Node(typename Graph::Node(n)); }
1.319 + };
1.320 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.321 + class OutEdgeIt {
1.322 + friend class GraphWrapper<Graph>;
1.323 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.324 + typename Graph::OutEdgeIt e;
1.325 + public:
1.326 + OutEdgeIt() { }
1.327 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.328 + OutEdgeIt(const Invalid& i) : e(i) { }
1.329 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.330 + const Node& _n) :
1.331 + e(*(_G.graph), typename Graph::Node(_n)) {
1.332 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.333 + _G.graph->next(e);
1.334 + }
1.335 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.336 + };
1.337 + class InEdgeIt {
1.338 + friend class GraphWrapper<Graph>;
1.339 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.340 + typename Graph::InEdgeIt e;
1.341 + public:
1.342 + InEdgeIt() { }
1.343 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.344 + InEdgeIt(const Invalid& i) : e(i) { }
1.345 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.346 + const Node& _n) :
1.347 + e(*(_G.graph), typename Graph::Node(_n)) {
1.348 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.349 + _G.graph->next(e);
1.350 + }
1.351 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.352 + };
1.353 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.354 + class EdgeIt {
1.355 + friend class GraphWrapper<Graph>;
1.356 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.357 + typename Graph::EdgeIt e;
1.358 + public:
1.359 + EdgeIt() { }
1.360 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.361 + EdgeIt(const Invalid& i) : e(i) { }
1.362 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.363 + e(*(_G.graph)) {
1.364 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.365 + _G.graph->next(e);
1.366 + }
1.367 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.368 + };
1.369 +
1.370 + NodeIt& first(NodeIt& i) const {
1.371 + i=NodeIt(*this); return i;
1.372 + }
1.373 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.374 + i=OutEdgeIt(*this, p); return i;
1.375 + }
1.376 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.377 + i=InEdgeIt(*this, p); return i;
1.378 + }
1.379 + EdgeIt& first(EdgeIt& i) const {
1.380 + i=EdgeIt(*this); return i;
1.381 + }
1.382 +
1.383 + NodeIt& next(NodeIt& i) const {
1.384 + this->graph->next(i.n);
1.385 + while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
1.386 + this->graph->next(i.n); }
1.387 + return i;
1.388 + }
1.389 + OutEdgeIt& next(OutEdgeIt& i) const {
1.390 + this->graph->next(i.e);
1.391 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.392 + this->graph->next(i.e); }
1.393 + return i;
1.394 + }
1.395 + InEdgeIt& next(InEdgeIt& i) const {
1.396 + this->graph->next(i.e);
1.397 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.398 + this->graph->next(i.e); }
1.399 + return i;
1.400 + }
1.401 + EdgeIt& next(EdgeIt& i) const {
1.402 + this->graph->next(i.e);
1.403 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.404 + this->graph->next(i.e); }
1.405 + return i;
1.406 + }
1.407 +
1.408 + Node aNode(const OutEdgeIt& e) const {
1.409 + return Node(this->graph->aNode(e.e)); }
1.410 + Node aNode(const InEdgeIt& e) const {
1.411 + return Node(this->graph->aNode(e.e)); }
1.412 + Node bNode(const OutEdgeIt& e) const {
1.413 + return Node(this->graph->bNode(e.e)); }
1.414 + Node bNode(const InEdgeIt& e) const {
1.415 + return Node(this->graph->bNode(e.e)); }
1.416 +
1.417 + ///\todo
1.418 + ///Some doki, please.
1.419 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.420 + ///\todo
1.421 + ///Some doki, please.
1.422 + void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.423 +
1.424 + ///\todo
1.425 + ///Some doki, please.
1.426 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.427 + ///\todo
1.428 + ///Some doki, please.
1.429 + void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.430 +
1.431 + ///\todo
1.432 + ///Some doki, please.
1.433 + bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
1.434 + ///\todo
1.435 + ///Some doki, please.
1.436 + bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
1.437 + };
1.438 +
1.439 + /// A wrapper for forgetting the orientation of a graph.
1.440 +
1.441 + /// A wrapper for getting an undirected graph by forgetting
1.442 + /// the orientation of a directed one.
1.443 + template<typename Graph>
1.444 + class UndirGraphWrapper : public GraphWrapper<Graph> {
1.445 + public:
1.446 + typedef typename GraphWrapper<Graph>::Node Node;
1.447 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.448 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.449 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.450 +
1.451 + UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.452 +
1.453 + class OutEdgeIt {
1.454 + friend class UndirGraphWrapper<Graph>;
1.455 + bool out_or_in; //true iff out
1.456 + typename Graph::OutEdgeIt out;
1.457 + typename Graph::InEdgeIt in;
1.458 + public:
1.459 + OutEdgeIt() { }
1.460 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.461 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.462 + out_or_in=true; _G.graph->first(out, _n);
1.463 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.464 + }
1.465 + operator Edge() const {
1.466 + if (out_or_in) return Edge(out); else return Edge(in);
1.467 + }
1.468 + };
1.469 +
1.470 +//FIXME InEdgeIt
1.471 + typedef OutEdgeIt InEdgeIt;
1.472 +
1.473 + using GraphWrapper<Graph>::first;
1.474 +// NodeIt& first(NodeIt& i) const {
1.475 +// i=NodeIt(*this); return i;
1.476 +// }
1.477 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.478 + i=OutEdgeIt(*this, p); return i;
1.479 + }
1.480 +//FIXME
1.481 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.482 +// i=InEdgeIt(*this, p); return i;
1.483 +// }
1.484 +// EdgeIt& first(EdgeIt& i) const {
1.485 +// i=EdgeIt(*this); return i;
1.486 +// }
1.487 +
1.488 + using GraphWrapper<Graph>::next;
1.489 +// NodeIt& next(NodeIt& n) const {
1.490 +// GraphWrapper<Graph>::next(n);
1.491 +// return n;
1.492 +// }
1.493 + OutEdgeIt& next(OutEdgeIt& e) const {
1.494 + if (e.out_or_in) {
1.495 + typename Graph::Node n=this->graph->tail(e.out);
1.496 + this->graph->next(e.out);
1.497 + if (!this->graph->valid(e.out)) {
1.498 + e.out_or_in=false; this->graph->first(e.in, n); }
1.499 + } else {
1.500 + this->graph->next(e.in);
1.501 + }
1.502 + return e;
1.503 + }
1.504 + //FIXME InEdgeIt
1.505 +// EdgeIt& next(EdgeIt& e) const {
1.506 +// GraphWrapper<Graph>::next(n);
1.507 +// // graph->next(e.e);
1.508 +// return e;
1.509 +// }
1.510 +
1.511 + Node aNode(const OutEdgeIt& e) const {
1.512 + if (e.out_or_in) return this->graph->tail(e); else
1.513 + return this->graph->head(e); }
1.514 + Node bNode(const OutEdgeIt& e) const {
1.515 + if (e.out_or_in) return this->graph->head(e); else
1.516 + return this->graph->tail(e); }
1.517 + };
1.518 +
1.519 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.520 +
1.521 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.522 + template<typename Graph, typename Number,
1.523 + typename CapacityMap, typename FlowMap>
1.524 + class ResGraphWrapper : public GraphWrapper<Graph> {
1.525 + protected:
1.526 + const CapacityMap* capacity;
1.527 + FlowMap* flow;
1.528 + public:
1.529 +
1.530 + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.531 + FlowMap& _flow) :
1.532 + GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1.533 +
1.534 + class Edge;
1.535 + class OutEdgeIt;
1.536 + friend class Edge;
1.537 + friend class OutEdgeIt;
1.538 +
1.539 + typedef typename GraphWrapper<Graph>::Node Node;
1.540 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.541 + class Edge : public Graph::Edge {
1.542 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.543 + protected:
1.544 + bool forward; //true, iff forward
1.545 +// typename Graph::Edge e;
1.546 + public:
1.547 + Edge() { }
1.548 + Edge(const typename Graph::Edge& _e, bool _forward) :
1.549 + Graph::Edge(_e), forward(_forward) { }
1.550 + Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
1.551 +//the unique invalid iterator
1.552 + friend bool operator==(const Edge& u, const Edge& v) {
1.553 + return (v.forward==u.forward &&
1.554 + static_cast<typename Graph::Edge>(u)==
1.555 + static_cast<typename Graph::Edge>(v));
1.556 + }
1.557 + friend bool operator!=(const Edge& u, const Edge& v) {
1.558 + return (v.forward!=u.forward ||
1.559 + static_cast<typename Graph::Edge>(u)!=
1.560 + static_cast<typename Graph::Edge>(v));
1.561 + }
1.562 + };
1.563 +
1.564 + class OutEdgeIt {
1.565 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.566 + protected:
1.567 + typename Graph::OutEdgeIt out;
1.568 + typename Graph::InEdgeIt in;
1.569 + bool forward;
1.570 + public:
1.571 + OutEdgeIt() { }
1.572 + //FIXME
1.573 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.574 + OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.575 +//the unique invalid iterator
1.576 + OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.577 + forward=true;
1.578 + resG.graph->first(out, v);
1.579 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.580 + if (!resG.graph->valid(out)) {
1.581 + forward=false;
1.582 + resG.graph->first(in, v);
1.583 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.584 + }
1.585 + }
1.586 + operator Edge() const {
1.587 +// Edge e;
1.588 +// e.forward=this->forward;
1.589 +// if (this->forward) e=out; else e=in;
1.590 +// return e;
1.591 + if (this->forward)
1.592 + return Edge(out, this->forward);
1.593 + else
1.594 + return Edge(in, this->forward);
1.595 + }
1.596 + };
1.597 +
1.598 + class InEdgeIt {
1.599 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.600 + protected:
1.601 + typename Graph::OutEdgeIt out;
1.602 + typename Graph::InEdgeIt in;
1.603 + bool forward;
1.604 + public:
1.605 + InEdgeIt() { }
1.606 + //FIXME
1.607 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.608 + InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.609 +//the unique invalid iterator
1.610 + InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.611 + forward=true;
1.612 + resG.graph->first(in, v);
1.613 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.614 + if (!resG.graph->valid(in)) {
1.615 + forward=false;
1.616 + resG.graph->first(out, v);
1.617 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.618 + }
1.619 + }
1.620 + operator Edge() const {
1.621 +// Edge e;
1.622 +// e.forward=this->forward;
1.623 +// if (this->forward) e=out; else e=in;
1.624 +// return e;
1.625 + if (this->forward)
1.626 + return Edge(in, this->forward);
1.627 + else
1.628 + return Edge(out, this->forward);
1.629 + }
1.630 + };
1.631 +
1.632 + class EdgeIt {
1.633 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.634 + protected:
1.635 + typename Graph::EdgeIt e;
1.636 + bool forward;
1.637 + public:
1.638 + EdgeIt() { }
1.639 + EdgeIt(const Invalid& i) : e(i), forward(false) { }
1.640 + EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
1.641 + forward=true;
1.642 + resG.graph->first(e);
1.643 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.644 + if (!resG.graph->valid(e)) {
1.645 + forward=false;
1.646 + resG.graph->first(e);
1.647 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.648 + }
1.649 + }
1.650 + operator Edge() const {
1.651 + return Edge(e, this->forward);
1.652 + }
1.653 + };
1.654 +
1.655 + using GraphWrapper<Graph>::first;
1.656 +// NodeIt& first(NodeIt& i) const {
1.657 +// i=NodeIt(*this); return i;
1.658 +// }
1.659 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.660 + i=OutEdgeIt(*this, p); return i;
1.661 + }
1.662 +// FIXME not tested
1.663 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.664 + i=InEdgeIt(*this, p); return i;
1.665 + }
1.666 + EdgeIt& first(EdgeIt& i) const {
1.667 + i=EdgeIt(*this); return i;
1.668 + }
1.669 +
1.670 + using GraphWrapper<Graph>::next;
1.671 +// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.672 + OutEdgeIt& next(OutEdgeIt& e) const {
1.673 + if (e.forward) {
1.674 + Node v=this->graph->aNode(e.out);
1.675 + this->graph->next(e.out);
1.676 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.677 + this->graph->next(e.out); }
1.678 + if (!this->graph->valid(e.out)) {
1.679 + e.forward=false;
1.680 + this->graph->first(e.in, v);
1.681 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.682 + this->graph->next(e.in); }
1.683 + }
1.684 + } else {
1.685 + this->graph->next(e.in);
1.686 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.687 + this->graph->next(e.in); }
1.688 + }
1.689 + return e;
1.690 + }
1.691 +// FIXME Not tested
1.692 + InEdgeIt& next(InEdgeIt& e) const {
1.693 + if (e.forward) {
1.694 + Node v=this->graph->aNode(e.in);
1.695 + this->graph->next(e.in);
1.696 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.697 + this->graph->next(e.in); }
1.698 + if (!this->graph->valid(e.in)) {
1.699 + e.forward=false;
1.700 + this->graph->first(e.out, v);
1.701 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.702 + this->graph->next(e.out); }
1.703 + }
1.704 + } else {
1.705 + this->graph->next(e.out);
1.706 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.707 + this->graph->next(e.out); }
1.708 + }
1.709 + return e;
1.710 + }
1.711 + EdgeIt& next(EdgeIt& e) const {
1.712 + if (e.forward) {
1.713 + this->graph->next(e.e);
1.714 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.715 + this->graph->next(e.e); }
1.716 + if (!this->graph->valid(e.e)) {
1.717 + e.forward=false;
1.718 + this->graph->first(e.e);
1.719 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.720 + this->graph->next(e.e); }
1.721 + }
1.722 + } else {
1.723 + this->graph->next(e.e);
1.724 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.725 + this->graph->next(e.e); }
1.726 + }
1.727 + return e;
1.728 + }
1.729 +
1.730 + Node tail(Edge e) const {
1.731 + return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
1.732 + Node head(Edge e) const {
1.733 + return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
1.734 +
1.735 + Node aNode(OutEdgeIt e) const {
1.736 + return ((e.forward) ? this->graph->aNode(e.out) :
1.737 + this->graph->aNode(e.in)); }
1.738 + Node bNode(OutEdgeIt e) const {
1.739 + return ((e.forward) ? this->graph->bNode(e.out) :
1.740 + this->graph->bNode(e.in)); }
1.741 +
1.742 + Node aNode(InEdgeIt e) const {
1.743 + return ((e.forward) ? this->graph->aNode(e.in) :
1.744 + this->graph->aNode(e.out)); }
1.745 + Node bNode(InEdgeIt e) const {
1.746 + return ((e.forward) ? this->graph->bNode(e.in) :
1.747 + this->graph->bNode(e.out)); }
1.748 +
1.749 +// int nodeNum() const { return graph->nodeNum(); }
1.750 + //FIXME
1.751 + void edgeNum() const { }
1.752 + //int edgeNum() const { return graph->edgeNum(); }
1.753 +
1.754 +
1.755 +// int id(Node v) const { return graph->id(v); }
1.756 +
1.757 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.758 + bool valid(Edge e) const {
1.759 + return this->graph->valid(e);
1.760 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.761 + }
1.762 +
1.763 + void augment(const Edge& e, Number a) const {
1.764 + if (e.forward)
1.765 +// flow->set(e.out, flow->get(e.out)+a);
1.766 + flow->set(e, (*flow)[e]+a);
1.767 + else
1.768 +// flow->set(e.in, flow->get(e.in)-a);
1.769 + flow->set(e, (*flow)[e]-a);
1.770 + }
1.771 +
1.772 + Number resCap(const Edge& e) const {
1.773 + if (e.forward)
1.774 +// return (capacity->get(e.out)-flow->get(e.out));
1.775 + return ((*capacity)[e]-(*flow)[e]);
1.776 + else
1.777 +// return (flow->get(e.in));
1.778 + return ((*flow)[e]);
1.779 + }
1.780 +
1.781 +// Number resCap(typename Graph::OutEdgeIt out) const {
1.782 +// // return (capacity->get(out)-flow->get(out));
1.783 +// return ((*capacity)[out]-(*flow)[out]);
1.784 +// }
1.785 +
1.786 +// Number resCap(typename Graph::InEdgeIt in) const {
1.787 +// // return (flow->get(in));
1.788 +// return ((*flow)[in]);
1.789 +// }
1.790 +
1.791 + template <typename T>
1.792 + class EdgeMap {
1.793 + typename Graph::template EdgeMap<T> forward_map, backward_map;
1.794 + public:
1.795 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.796 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.797 + void set(Edge e, T a) {
1.798 + if (e.forward)
1.799 + forward_map.set(e.out, a);
1.800 + else
1.801 + backward_map.set(e.in, a);
1.802 + }
1.803 + T operator[](Edge e) const {
1.804 + if (e.forward)
1.805 + return forward_map[e.out];
1.806 + else
1.807 + return backward_map[e.in];
1.808 + }
1.809 +// T get(Edge e) const {
1.810 +// if (e.out_or_in)
1.811 +// return forward_map.get(e.out);
1.812 +// else
1.813 +// return backward_map.get(e.in);
1.814 +// }
1.815 + };
1.816 + };
1.817 +
1.818 + /// ErasingFirstGraphWrapper for blocking flows.
1.819 +
1.820 + /// ErasingFirstGraphWrapper for blocking flows.
1.821 + template<typename Graph, typename FirstOutEdgesMap>
1.822 + class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.823 + protected:
1.824 + FirstOutEdgesMap* first_out_edges;
1.825 + public:
1.826 + ErasingFirstGraphWrapper(Graph& _graph,
1.827 + FirstOutEdgesMap& _first_out_edges) :
1.828 + GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.829 +
1.830 + typedef typename GraphWrapper<Graph>::Node Node;
1.831 +// class NodeIt {
1.832 +// friend class GraphWrapper<Graph>;
1.833 +// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.834 +// typename Graph::NodeIt n;
1.835 +// public:
1.836 +// NodeIt() { }
1.837 +// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.838 +// NodeIt(const Invalid& i) : n(i) { }
1.839 +// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.840 +// n(*(_G.graph)) { }
1.841 +// operator Node() const { return Node(typename Graph::Node(n)); }
1.842 +// };
1.843 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.844 + class OutEdgeIt {
1.845 + friend class GraphWrapper<Graph>;
1.846 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.847 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.848 + typename Graph::OutEdgeIt e;
1.849 + public:
1.850 + OutEdgeIt() { }
1.851 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.852 + OutEdgeIt(const Invalid& i) : e(i) { }
1.853 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.854 + const Node& _n) :
1.855 + e((*_G.first_out_edges)[_n]) { }
1.856 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.857 + };
1.858 + class InEdgeIt {
1.859 + friend class GraphWrapper<Graph>;
1.860 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.861 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.862 + typename Graph::InEdgeIt e;
1.863 + public:
1.864 + InEdgeIt() { }
1.865 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.866 + InEdgeIt(const Invalid& i) : e(i) { }
1.867 + InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.868 + const Node& _n) :
1.869 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.870 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.871 + };
1.872 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.873 + class EdgeIt {
1.874 + friend class GraphWrapper<Graph>;
1.875 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.876 +// typedef typename Graph::EdgeIt GraphEdgeIt;
1.877 + typename Graph::EdgeIt e;
1.878 + public:
1.879 + EdgeIt() { }
1.880 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.881 + EdgeIt(const Invalid& i) : e(i) { }
1.882 + EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.883 + e(*(_G.graph)) { }
1.884 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.885 + };
1.886 +
1.887 + using GraphWrapper<Graph>::first;
1.888 +// NodeIt& first(NodeIt& i) const {
1.889 +// i=NodeIt(*this); return i;
1.890 +// }
1.891 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.892 + i=OutEdgeIt(*this, p); return i;
1.893 + }
1.894 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.895 + i=InEdgeIt(*this, p); return i;
1.896 + }
1.897 + EdgeIt& first(EdgeIt& i) const {
1.898 + i=EdgeIt(*this); return i;
1.899 + }
1.900 +
1.901 + using GraphWrapper<Graph>::next;
1.902 +// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.903 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.904 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.905 + EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1.906 +
1.907 + Node aNode(const OutEdgeIt& e) const {
1.908 + return Node(this->graph->aNode(e.e)); }
1.909 + Node aNode(const InEdgeIt& e) const {
1.910 + return Node(this->graph->aNode(e.e)); }
1.911 + Node bNode(const OutEdgeIt& e) const {
1.912 + return Node(this->graph->bNode(e.e)); }
1.913 + Node bNode(const InEdgeIt& e) const {
1.914 + return Node(this->graph->bNode(e.e)); }
1.915 +
1.916 + void erase(const OutEdgeIt& e) const {
1.917 + OutEdgeIt f=e;
1.918 + this->next(f);
1.919 + first_out_edges->set(this->tail(e), f.e);
1.920 + }
1.921 + };
1.922 +
1.923 + /// A wrapper for composing a bipartite graph.
1.924 + /// \c _graph have to be a reference to a graph of type \c Graph
1.925 + /// and \c _s_false_t_true_map is an \c IterableBoolMap
1.926 + /// reference containing the elements for the
1.927 + /// color classes S and T. \c _graph is to be referred to an undirected
1.928 + /// graph or a directed graph with edges oriented from S to T.
1.929 + template<typename Graph>
1.930 + class BipartiteGraphWrapper : public GraphWrapper<Graph> {
1.931 + typedef IterableBoolMap< typename Graph::template NodeMap<int> >
1.932 + SFalseTTrueMap;
1.933 + SFalseTTrueMap* s_false_t_true_map;
1.934 +
1.935 + public:
1.936 + //marci
1.937 + //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
1.938 + //static const bool S_CLASS=false;
1.939 + //static const bool T_CLASS=true;
1.940 +
1.941 + bool S_CLASS;
1.942 + bool T_CLASS;
1.943 +
1.944 + BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
1.945 + : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
1.946 + S_CLASS(false), T_CLASS(true) { }
1.947 + typedef typename GraphWrapper<Graph>::Node Node;
1.948 + //using GraphWrapper<Graph>::NodeIt;
1.949 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.950 + //using GraphWrapper<Graph>::EdgeIt;
1.951 + class ClassNodeIt;
1.952 + friend class ClassNodeIt;
1.953 + class OutEdgeIt;
1.954 + friend class OutEdgeIt;
1.955 + class InEdgeIt;
1.956 + friend class InEdgeIt;
1.957 + class ClassNodeIt {
1.958 + friend class BipartiteGraphWrapper<Graph>;
1.959 + protected:
1.960 + Node n;
1.961 + public:
1.962 + ClassNodeIt() { }
1.963 + ClassNodeIt(const Invalid& i) : n(i) { }
1.964 + ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
1.965 + _G.s_false_t_true_map->first(n, _class);
1.966 + }
1.967 + //FIXME needed in new concept, important here
1.968 + ClassNodeIt(const Node& _n) : n(_n) { }
1.969 + operator Node() const { return n; }
1.970 + };
1.971 +// class SNodeIt {
1.972 +// Node n;
1.973 +// public:
1.974 +// SNodeIt() { }
1.975 +// SNodeIt(const Invalid& i) : n(i) { }
1.976 +// SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
1.977 +// _G.s_false_t_true_map->first(n, false);
1.978 +// }
1.979 +// operator Node() const { return n; }
1.980 +// };
1.981 +// class TNodeIt {
1.982 +// Node n;
1.983 +// public:
1.984 +// TNodeIt() { }
1.985 +// TNodeIt(const Invalid& i) : n(i) { }
1.986 +// TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
1.987 +// _G.s_false_t_true_map->first(n, true);
1.988 +// }
1.989 +// operator Node() const { return n; }
1.990 +// };
1.991 + class OutEdgeIt {
1.992 + friend class BipartiteGraphWrapper<Graph>;
1.993 + protected:
1.994 + typename Graph::OutEdgeIt e;
1.995 + public:
1.996 + OutEdgeIt() { }
1.997 + OutEdgeIt(const Invalid& i) : e(i) { }
1.998 + OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.999 + if (!(*(_G.s_false_t_true_map))[_n])
1.1000 + e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.1001 + else
1.1002 + e=INVALID;
1.1003 + }
1.1004 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.1005 + };
1.1006 + class InEdgeIt {
1.1007 + friend class BipartiteGraphWrapper<Graph>;
1.1008 + protected:
1.1009 + typename Graph::InEdgeIt e;
1.1010 + public:
1.1011 + InEdgeIt() { }
1.1012 + InEdgeIt(const Invalid& i) : e(i) { }
1.1013 + InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1.1014 + if ((*(_G.s_false_t_true_map))[_n])
1.1015 + e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
1.1016 + else
1.1017 + e=INVALID;
1.1018 + }
1.1019 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.1020 + };
1.1021 +
1.1022 + using GraphWrapper<Graph>::first;
1.1023 + ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
1.1024 + n=ClassNodeIt(*this, _class) ; return n; }
1.1025 +// SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1.1026 +// TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1.1027 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1028 + i=OutEdgeIt(*this, p); return i;
1.1029 + }
1.1030 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1031 + i=InEdgeIt(*this, p); return i;
1.1032 + }
1.1033 +
1.1034 + using GraphWrapper<Graph>::next;
1.1035 + ClassNodeIt& next(ClassNodeIt& n) const {
1.1036 + this->s_false_t_true_map->next(n.n); return n;
1.1037 + }
1.1038 +// SNodeIt& next(SNodeIt& n) const {
1.1039 +// this->s_false_t_true_map->next(n); return n;
1.1040 +// }
1.1041 +// TNodeIt& next(TNodeIt& n) const {
1.1042 +// this->s_false_t_true_map->next(n); return n;
1.1043 +// }
1.1044 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.1045 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.1046 +
1.1047 + Node tail(const Edge& e) {
1.1048 + if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.1049 + return Node(this->graph->tail(e));
1.1050 + else
1.1051 + return Node(this->graph->head(e));
1.1052 + }
1.1053 + Node head(const Edge& e) {
1.1054 + if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1.1055 + return Node(this->graph->head(e));
1.1056 + else
1.1057 + return Node(this->graph->tail(e));
1.1058 + }
1.1059 +
1.1060 + Node aNode(const OutEdgeIt& e) const {
1.1061 + return Node(this->graph->aNode(e.e));
1.1062 + }
1.1063 + Node aNode(const InEdgeIt& e) const {
1.1064 + return Node(this->graph->aNode(e.e));
1.1065 + }
1.1066 + Node bNode(const OutEdgeIt& e) const {
1.1067 + return Node(this->graph->bNode(e.e));
1.1068 + }
1.1069 + Node bNode(const InEdgeIt& e) const {
1.1070 + return Node(this->graph->bNode(e.e));
1.1071 + }
1.1072 +
1.1073 + bool inSClass(const Node& n) const {
1.1074 + return !(*(this->s_false_t_true_map))[n];
1.1075 + }
1.1076 + bool inTClass(const Node& n) const {
1.1077 + return (*(this->s_false_t_true_map))[n];
1.1078 + }
1.1079 + };
1.1080 +
1.1081 +
1.1082 +
1.1083 +
1.1084 + /******************** S-T Graph Wrapper ********************/
1.1085 +
1.1086 +
1.1087 +
1.1088 +
1.1089 +
1.1090 + template<typename Graph> class stGraphWrapper;
1.1091 +
1.1092 + template<typename Graph>
1.1093 + inline
1.1094 + std::ostream&
1.1095 + operator<<(std::ostream& os,
1.1096 + typename stGraphWrapper<Graph>::Node const& i) {
1.1097 + os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1.1098 + return os;
1.1099 + }
1.1100 +
1.1101 + template<typename Graph>
1.1102 + inline
1.1103 + std::ostream&
1.1104 + operator<<(std::ostream& os,
1.1105 + typename stGraphWrapper<Graph>::Edge const& i) {
1.1106 + os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec
1.1107 + << " node: " << i.n << ")";
1.1108 + return os;
1.1109 + }
1.1110 +
1.1111 +
1.1112 + /// experimentral, do not try it.
1.1113 + /// It eats a bipartite graph, oriented from S to T.
1.1114 + /// Such one can be made e.g. by the above wrapper.
1.1115 + template<typename Graph>
1.1116 + class stGraphWrapper : public GraphWrapper<Graph> {
1.1117 + public:
1.1118 + class Node;
1.1119 + friend class Node;
1.1120 +//GN, int
1.1121 +//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1.1122 +//es a vege a false azaz (invalid, 3)
1.1123 + class NodeIt;
1.1124 + friend class NodeIt;
1.1125 +//GNI, int
1.1126 + class Edge;
1.1127 + friend class Edge;
1.1128 +//GE, int, GN
1.1129 +//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1.1130 +//invalid: (invalid, 3, invalid)
1.1131 + class OutEdgeIt;
1.1132 + friend class OutEdgeIt;
1.1133 +//GO, int, GNI
1.1134 +//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1.1135 +//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1.1136 +//t-bol (invalid, 3, invalid)
1.1137 + class InEdgeIt;
1.1138 + friend class InEdgeIt;
1.1139 +//GI, int, GNI
1.1140 +//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1.1141 +//s-be (invalid, 3, invalid)
1.1142 +//t-be (invalid, 2, first), ... (invalid, 3, invalid)
1.1143 + class EdgeIt;
1.1144 + friend class EdgeIt;
1.1145 +//(first, 0, invalid) ...
1.1146 +//(invalid, 1, vmi)
1.1147 +//(invalid, 2, vmi)
1.1148 +//invalid, 3, invalid)
1.1149 + template <typename T> class NodeMap;
1.1150 + template <typename T, typename Parent> class EdgeMap;
1.1151 +
1.1152 +// template <typename T> friend class NodeMap;
1.1153 +// template <typename T> friend class EdgeMap;
1.1154 +
1.1155 + const Node S_NODE;
1.1156 + const Node T_NODE;
1.1157 +
1.1158 + static const bool S_CLASS=false;
1.1159 + static const bool T_CLASS=true;
1.1160 +
1.1161 + stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1.1162 + S_NODE(INVALID, 1),
1.1163 + T_NODE(INVALID, 2) { }
1.1164 +
1.1165 +
1.1166 + class Node : public Graph::Node {
1.1167 + protected:
1.1168 + friend class GraphWrapper<Graph>;
1.1169 + friend class stGraphWrapper<Graph>;
1.1170 + template <typename T> friend class NodeMap;
1.1171 + friend class Edge;
1.1172 + friend class OutEdgeIt;
1.1173 + friend class InEdgeIt;
1.1174 + friend class EdgeIt;
1.1175 + int spec;
1.1176 + public:
1.1177 + Node() { }
1.1178 + Node(const typename Graph::Node& _n, int _spec=0) :
1.1179 + Graph::Node(_n), spec(_spec) { }
1.1180 + Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1.1181 + friend bool operator==(const Node& u, const Node& v) {
1.1182 + return (u.spec==v.spec &&
1.1183 + static_cast<typename Graph::Node>(u)==
1.1184 + static_cast<typename Graph::Node>(v));
1.1185 + }
1.1186 + friend bool operator!=(const Node& u, const Node& v) {
1.1187 + return (v.spec!=u.spec ||
1.1188 + static_cast<typename Graph::Node>(u)!=
1.1189 + static_cast<typename Graph::Node>(v));
1.1190 + }
1.1191 + friend std::ostream& operator<< <Graph>(std::ostream& os, const Node& i);
1.1192 + int getSpec() const { return spec; }
1.1193 + };
1.1194 +
1.1195 + class NodeIt {
1.1196 + friend class GraphWrapper<Graph>;
1.1197 + friend class stGraphWrapper<Graph>;
1.1198 + typename Graph::NodeIt n;
1.1199 + int spec;
1.1200 + public:
1.1201 + NodeIt() { }
1.1202 + NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1.1203 + n(_n), spec(_spec) { }
1.1204 + NodeIt(const Invalid& i) : n(i), spec(3) { }
1.1205 + NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1.1206 + if (!_G.graph->valid(n)) spec=1;
1.1207 + }
1.1208 + operator Node() const { return Node(n, spec); }
1.1209 + };
1.1210 +
1.1211 + typedef NodeIt NodeIt;
1.1212 + typedef Node Node;
1.1213 +
1.1214 + class Edge : public Graph::Edge {
1.1215 + friend class GraphWrapper<Graph>;
1.1216 + friend class stGraphWrapper<Graph>;
1.1217 + template <typename T, typename Parent> friend class EdgeMap;
1.1218 + int spec;
1.1219 + typename Graph::Node n;
1.1220 + public:
1.1221 + Edge() { }
1.1222 + Edge(const typename Graph::Edge& _e, int _spec,
1.1223 + const typename Graph::Node& _n) :
1.1224 + Graph::Edge(_e), spec(_spec), n(_n) {
1.1225 + }
1.1226 + Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1.1227 + friend bool operator==(const Edge& u, const Edge& v) {
1.1228 + return (u.spec==v.spec &&
1.1229 + static_cast<typename Graph::Edge>(u)==
1.1230 + static_cast<typename Graph::Edge>(v) &&
1.1231 + u.n==v.n);
1.1232 + }
1.1233 + friend bool operator!=(const Edge& u, const Edge& v) {
1.1234 + return (v.spec!=u.spec ||
1.1235 + static_cast<typename Graph::Edge>(u)!=
1.1236 + static_cast<typename Graph::Edge>(v) ||
1.1237 + u.n!=v.n);
1.1238 + }
1.1239 + friend std::ostream& operator<< <Graph>(std::ostream& os, const Edge& i);
1.1240 + int getSpec() const { return spec; }
1.1241 + };
1.1242 +
1.1243 + class OutEdgeIt {
1.1244 + friend class GraphWrapper<Graph>;
1.1245 + friend class stGraphWrapper<Graph>;
1.1246 + typename Graph::OutEdgeIt e;
1.1247 + int spec;
1.1248 + typename Graph::ClassNodeIt n;
1.1249 + public:
1.1250 + OutEdgeIt() { }
1.1251 + OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1.1252 + const typename Graph::ClassNodeIt& _n) :
1.1253 + e(_e), spec(_spec), n(_n) {
1.1254 + }
1.1255 + OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.1256 + OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1.1257 + switch (_n.spec) {
1.1258 + case 0 :
1.1259 + if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1.1260 + e=typename Graph::OutEdgeIt(*(_G.graph),
1.1261 + typename Graph::Node(_n));
1.1262 + spec=0;
1.1263 + n=INVALID;
1.1264 + if (!_G.graph->valid(e)) spec=3;
1.1265 + } else { //T, specko kiel van
1.1266 + e=INVALID;
1.1267 + spec=2;
1.1268 + n=_n;
1.1269 + }
1.1270 + break;
1.1271 + case 1:
1.1272 + e=INVALID;
1.1273 + spec=1;
1.1274 + _G.graph->first(n, S_CLASS); //s->vmi;
1.1275 + if (!_G.graph->valid(n)) spec=3; //Ha S ures
1.1276 + break;
1.1277 + case 2:
1.1278 + e=INVALID;
1.1279 + spec=3;
1.1280 + n=INVALID;
1.1281 + break;
1.1282 + }
1.1283 + }
1.1284 + operator Edge() const { return Edge(e, spec, n); }
1.1285 + };
1.1286 +
1.1287 + class InEdgeIt {
1.1288 + friend class GraphWrapper<Graph>;
1.1289 + friend class stGraphWrapper<Graph>;
1.1290 + typename Graph::InEdgeIt e;
1.1291 + int spec;
1.1292 + typename Graph::ClassNodeIt n;
1.1293 + public:
1.1294 + InEdgeIt() { }
1.1295 + InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1.1296 + const typename Graph::ClassNodeIt& _n) :
1.1297 + e(_e), spec(_spec), n(_n) {
1.1298 + }
1.1299 + InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.1300 + InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1.1301 + switch (_n.spec) {
1.1302 + case 0 :
1.1303 + if (_G.graph->inTClass(_n)) { //T, van normalis beel
1.1304 + e=typename Graph::InEdgeIt(*(_G.graph),
1.1305 + typename Graph::Node(_n));
1.1306 + spec=0;
1.1307 + n=INVALID;
1.1308 + if (!_G.graph->valid(e)) spec=3;
1.1309 + } else { //S, specko beel van
1.1310 + e=INVALID;
1.1311 + spec=1;
1.1312 + n=_n;
1.1313 + }
1.1314 + break;
1.1315 + case 1:
1.1316 + e=INVALID;
1.1317 + spec=3;
1.1318 + n=INVALID;
1.1319 + break;
1.1320 + case 2:
1.1321 + e=INVALID;
1.1322 + spec=2;
1.1323 + _G.graph->first(n, T_CLASS); //vmi->t;
1.1324 + if (!_G.graph->valid(n)) spec=3; //Ha T ures
1.1325 + break;
1.1326 + }
1.1327 + }
1.1328 + operator Edge() const { return Edge(e, spec, n); }
1.1329 + };
1.1330 +
1.1331 + class EdgeIt {
1.1332 + friend class GraphWrapper<Graph>;
1.1333 + friend class stGraphWrapper<Graph>;
1.1334 + typename Graph::EdgeIt e;
1.1335 + int spec;
1.1336 + typename Graph::ClassNodeIt n;
1.1337 + public:
1.1338 + EdgeIt() { }
1.1339 + EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1.1340 + const typename Graph::ClassNodeIt& _n) :
1.1341 + e(_e), spec(_spec), n(_n) { }
1.1342 + EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1.1343 + EdgeIt(const stGraphWrapper<Graph>& _G) :
1.1344 + e(*(_G.graph)), spec(0), n(INVALID) {
1.1345 + if (!_G.graph->valid(e)) {
1.1346 + spec=1;
1.1347 + _G.graph->first(n, S_CLASS);
1.1348 + if (!_G.graph->valid(n)) { //Ha S ures
1.1349 + spec=2;
1.1350 + _G.graph->first(n, T_CLASS);
1.1351 + if (!_G.graph->valid(n)) { //Ha T ures
1.1352 + spec=3;
1.1353 + }
1.1354 + }
1.1355 + }
1.1356 + }
1.1357 + operator Edge() const { return Edge(e, spec, n); }
1.1358 + };
1.1359 +
1.1360 + NodeIt& first(NodeIt& i) const {
1.1361 + i=NodeIt(*this); return i;
1.1362 + }
1.1363 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1364 + i=OutEdgeIt(*this, p); return i;
1.1365 + }
1.1366 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.1367 + i=InEdgeIt(*this, p); return i;
1.1368 + }
1.1369 + EdgeIt& first(EdgeIt& i) const {
1.1370 + i=EdgeIt(*this); return i;
1.1371 + }
1.1372 +
1.1373 + NodeIt& next(NodeIt& i) const {
1.1374 + switch (i.spec) {
1.1375 + case 0:
1.1376 + this->graph->next(i.n);
1.1377 + if (!this->graph->valid(i.n)) {
1.1378 + i.spec=1;
1.1379 + }
1.1380 + break;
1.1381 + case 1:
1.1382 + i.spec=2;
1.1383 + break;
1.1384 + case 2:
1.1385 + i.spec=3;
1.1386 + break;
1.1387 + }
1.1388 + return i;
1.1389 + }
1.1390 + OutEdgeIt& next(OutEdgeIt& i) const {
1.1391 + typename Graph::Node v;
1.1392 + switch (i.spec) {
1.1393 + case 0: //normal edge
1.1394 + v=this->graph->aNode(i.e);
1.1395 + this->graph->next(i.e);
1.1396 + if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1.1397 + if (this->graph->inSClass(v)) { //S, nincs kiel
1.1398 + i.spec=3;
1.1399 + i.n=INVALID;
1.1400 + } else { //T, van kiel
1.1401 + i.spec=2;
1.1402 + i.n=v;
1.1403 + }
1.1404 + }
1.1405 + break;
1.1406 + case 1: //s->vmi
1.1407 + this->graph->next(i.n);
1.1408 + if (!this->graph->valid(i.n)) i.spec=3;
1.1409 + break;
1.1410 + case 2: //vmi->t
1.1411 + i.spec=3;
1.1412 + i.n=INVALID;
1.1413 + break;
1.1414 + }
1.1415 + return i;
1.1416 + }
1.1417 + InEdgeIt& next(InEdgeIt& i) const {
1.1418 + typename Graph::Node v;
1.1419 + switch (i.spec) {
1.1420 + case 0: //normal edge
1.1421 + v=this->graph->aNode(i.e);
1.1422 + this->graph->next(i.e);
1.1423 + if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1.1424 + if (this->graph->inTClass(v)) { //S, nincs beel
1.1425 + i.spec=3;
1.1426 + i.n=INVALID;
1.1427 + } else { //S, van beel
1.1428 + i.spec=1;
1.1429 + i.n=v;
1.1430 + }
1.1431 + }
1.1432 + break;
1.1433 + case 1: //s->vmi
1.1434 + i.spec=3;
1.1435 + i.n=INVALID;
1.1436 + break;
1.1437 + case 2: //vmi->t
1.1438 + this->graph->next(i.n);
1.1439 + if (!this->graph->valid(i.n)) i.spec=3;
1.1440 + break;
1.1441 + }
1.1442 + return i;
1.1443 + }
1.1444 +
1.1445 + EdgeIt& next(EdgeIt& i) const {
1.1446 + switch (i.spec) {
1.1447 + case 0:
1.1448 + this->graph->next(i.e);
1.1449 + if (!this->graph->valid(i.e)) {
1.1450 + i.spec=1;
1.1451 + this->graph->first(i.n, S_CLASS);
1.1452 + if (!this->graph->valid(i.n)) {
1.1453 + i.spec=2;
1.1454 + this->graph->first(i.n, T_CLASS);
1.1455 + if (!this->graph->valid(i.n)) i.spec=3;
1.1456 + }
1.1457 + }
1.1458 + break;
1.1459 + case 1:
1.1460 + this->graph->next(i.n);
1.1461 + if (!this->graph->valid(i.n)) {
1.1462 + i.spec=2;
1.1463 + this->graph->first(i.n, T_CLASS);
1.1464 + if (!this->graph->valid(i.n)) i.spec=3;
1.1465 + }
1.1466 + break;
1.1467 + case 2:
1.1468 + this->graph->next(i.n);
1.1469 + if (!this->graph->valid(i.n)) i.spec=3;
1.1470 + break;
1.1471 + }
1.1472 + return i;
1.1473 + }
1.1474 +
1.1475 + Node tail(const Edge& e) const {
1.1476 + switch (e.spec) {
1.1477 + case 0:
1.1478 + return Node(this->graph->tail(e));
1.1479 + break;
1.1480 + case 1:
1.1481 + return S_NODE;
1.1482 + break;
1.1483 + case 2:
1.1484 + default:
1.1485 + return Node(e.n);
1.1486 + break;
1.1487 + }
1.1488 + }
1.1489 + Node head(const Edge& e) const {
1.1490 + switch (e.spec) {
1.1491 + case 0:
1.1492 + return Node(this->graph->head(e));
1.1493 + break;
1.1494 + case 1:
1.1495 + return Node(e.n);
1.1496 + break;
1.1497 + case 2:
1.1498 + default:
1.1499 + return T_NODE;
1.1500 + break;
1.1501 + }
1.1502 + }
1.1503 +
1.1504 + bool valid(const Node& n) const { return (n.spec<3); }
1.1505 + bool valid(const Edge& e) const { return (e.spec<3); }
1.1506 +
1.1507 + int nodeNum() const { return this->graph->nodeNum()+2; }
1.1508 + int edgeNum() const {
1.1509 + return this->graph->edgeNum()+this->graph->nodeNum();
1.1510 + }
1.1511 +
1.1512 + Node aNode(const OutEdgeIt& e) const { return tail(e); }
1.1513 + Node aNode(const InEdgeIt& e) const { return head(e); }
1.1514 + Node bNode(const OutEdgeIt& e) const { return head(e); }
1.1515 + Node bNode(const InEdgeIt& e) const { return tail(e); }
1.1516 +
1.1517 + void addNode() const { }
1.1518 + void addEdge() const { }
1.1519 +
1.1520 +// Node addNode() const { return Node(this->graph->addNode()); }
1.1521 +// Edge addEdge(const Node& tail, const Node& head) const {
1.1522 +// return Edge(this->graph->addEdge(tail, head)); }
1.1523 +
1.1524 +// void erase(const Node& i) const { this->graph->erase(i); }
1.1525 +// void erase(const Edge& i) const { this->graph->erase(i); }
1.1526 +
1.1527 +// void clear() const { this->graph->clear(); }
1.1528 +
1.1529 + template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1.1530 + typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
1.1531 + T s_value, t_value;
1.1532 + public:
1.1533 + NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1.1534 + s_value(),
1.1535 + t_value() { }
1.1536 + NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1.1537 + s_value(a),
1.1538 + t_value(a) { }
1.1539 + T operator[](const Node& n) const {
1.1540 + switch (n.spec) {
1.1541 + case 0:
1.1542 + return Parent::operator[](n);
1.1543 + break;
1.1544 + case 1:
1.1545 + return s_value;
1.1546 + break;
1.1547 + case 2:
1.1548 + default:
1.1549 + return t_value;
1.1550 + break;
1.1551 + }
1.1552 + }
1.1553 + void set(const Node& n, T t) {
1.1554 + switch (n.spec) {
1.1555 + case 0:
1.1556 + GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1.1557 + break;
1.1558 + case 1:
1.1559 + s_value=t;
1.1560 + break;
1.1561 + case 2:
1.1562 + default:
1.1563 + t_value=t;
1.1564 + break;
1.1565 + }
1.1566 + }
1.1567 + };
1.1568 +
1.1569 + template<typename T,
1.1570 + typename Parent=
1.1571 + typename GraphWrapper<Graph>::template EdgeMap<T> >
1.1572 + class EdgeMap : public Parent {
1.1573 + //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1.1574 + typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1.1575 + public:
1.1576 + EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1.1577 + node_value(_G) { }
1.1578 + EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1.1579 + node_value(_G, a) { }
1.1580 + T operator[](const Edge& e) const {
1.1581 + switch (e.spec) {
1.1582 + case 0:
1.1583 + return Parent::operator[](e);
1.1584 + break;
1.1585 + case 1:
1.1586 + return node_value[e.n];
1.1587 + break;
1.1588 + case 2:
1.1589 + default:
1.1590 + return node_value[e.n];
1.1591 + break;
1.1592 + }
1.1593 + }
1.1594 + void set(const Edge& e, T t) {
1.1595 + switch (e.spec) {
1.1596 + case 0:
1.1597 + Parent::set(e, t);
1.1598 + break;
1.1599 + case 1:
1.1600 + node_value.set(e.n, t);
1.1601 + break;
1.1602 + case 2:
1.1603 + default:
1.1604 + node_value.set(e.n, t);
1.1605 + break;
1.1606 + }
1.1607 + }
1.1608 + };
1.1609 +
1.1610 +// template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1.1611 +// typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1.1612 +// typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1.1613 +// public:
1.1614 +// EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1.1615 +// node_value(_G) { }
1.1616 +// EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1.1617 +// node_value(_G, a) { }
1.1618 +// T operator[](const Edge& e) const {
1.1619 +// switch (e.spec) {
1.1620 +// case 0:
1.1621 +// return Parent::operator[](e);
1.1622 +// break;
1.1623 +// case 1:
1.1624 +// return node_value[e.n];
1.1625 +// break;
1.1626 +// case 2:
1.1627 +// default:
1.1628 +// return node_value[e.n];
1.1629 +// break;
1.1630 +// }
1.1631 +// }
1.1632 +// void set(const Edge& e, T t) {
1.1633 +// switch (e.spec) {
1.1634 +// case 0:
1.1635 +// GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
1.1636 +// break;
1.1637 +// case 1:
1.1638 +// node_value.set(e.n, t);
1.1639 +// break;
1.1640 +// case 2:
1.1641 +// default:
1.1642 +// node_value.set(e.n, t);
1.1643 +// break;
1.1644 +// }
1.1645 +// }
1.1646 +// };
1.1647 +
1.1648 + };
1.1649 +
1.1650 + ///@}
1.1651 +
1.1652 +} //namespace hugo
1.1653 +
1.1654 +
1.1655 +#endif //HUGO_GRAPH_WRAPPER_H
1.1656 +