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