1.1 --- a/src/work/marci/experiment/graph_wrapper_st_ostream_op.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1653 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_GRAPH_WRAPPER_H
1.6 -#define LEMON_GRAPH_WRAPPER_H
1.7 -
1.8 -#include <invalid.h>
1.9 -#include <iter_map.h>
1.10 -
1.11 -namespace lemon {
1.12 -
1.13 - // Graph wrappers
1.14 -
1.15 - /// \addtogroup gwrappers
1.16 - /// A main parts of LEMON 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 source(const Edge& e) const {
1.173 - return Node(graph->source(static_cast<typename Graph::Edge>(e))); }
1.174 - Node target(const Edge& e) const {
1.175 - return Node(graph->target(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& source, const Node& target) const {
1.192 - return Edge(graph->addEdge(source, target)); }
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 source(const Edge& e) const {
1.279 - return GraphWrapper<Graph>::target(e); }
1.280 - Node target(const Edge& e) const {
1.281 - return GraphWrapper<Graph>::source(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->source(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->source(e); else
1.513 - return this->graph->target(e); }
1.514 - Node bNode(const OutEdgeIt& e) const {
1.515 - if (e.out_or_in) return this->graph->target(e); else
1.516 - return this->graph->source(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 source(Edge e) const {
1.731 - return ((e.forward) ? this->graph->source(e) : this->graph->target(e)); }
1.732 - Node target(Edge e) const {
1.733 - return ((e.forward) ? this->graph->target(e) : this->graph->source(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->source(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 source(const Edge& e) {
1.1048 - if (!(*(this->s_false_t_true_map))[this->graph->source(e)])
1.1049 - return Node(this->graph->source(e));
1.1050 - else
1.1051 - return Node(this->graph->target(e));
1.1052 - }
1.1053 - Node target(const Edge& e) {
1.1054 - if (!(*(this->s_false_t_true_map))[this->graph->source(e)])
1.1055 - return Node(this->graph->target(e));
1.1056 - else
1.1057 - return Node(this->graph->source(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 source(const Edge& e) const {
1.1476 - switch (e.spec) {
1.1477 - case 0:
1.1478 - return Node(this->graph->source(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 target(const Edge& e) const {
1.1490 - switch (e.spec) {
1.1491 - case 0:
1.1492 - return Node(this->graph->target(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 source(e); }
1.1513 - Node aNode(const InEdgeIt& e) const { return target(e); }
1.1514 - Node bNode(const OutEdgeIt& e) const { return target(e); }
1.1515 - Node bNode(const InEdgeIt& e) const { return source(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& source, const Node& target) const {
1.1522 -// return Edge(this->graph->addEdge(source, target)); }
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 lemon
1.1653 -
1.1654 -
1.1655 -#endif //LEMON_GRAPH_WRAPPER_H
1.1656 -