1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Thu May 06 16:55:59 2004 +0000
1.3 @@ -0,0 +1,985 @@
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 <hugo/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 + GraphWrapper() : graph(0) { }
1.95 + void setGraph(Graph& _graph) { graph=&_graph; }
1.96 +
1.97 + public:
1.98 + typedef Graph BaseGraph;
1.99 + typedef Graph ParentGraph;
1.100 +
1.101 + GraphWrapper(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 + protected:
1.232 + RevGraphWrapper() : GraphWrapper<Graph>(0) { }
1.233 + public:
1.234 + RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.235 +
1.236 + typedef typename GraphWrapper<Graph>::Node Node;
1.237 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.238 + //If Graph::OutEdgeIt is not defined
1.239 + //and we do not want to use RevGraphWrapper::InEdgeIt,
1.240 + //the typdef techinque does not work.
1.241 + //Unfortunately all the typedefs are instantiated in templates.
1.242 + //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
1.243 + //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
1.244 +
1.245 + class OutEdgeIt {
1.246 + friend class GraphWrapper<Graph>;
1.247 + friend class RevGraphWrapper<Graph>;
1.248 + typename Graph::InEdgeIt e;
1.249 + public:
1.250 + OutEdgeIt() { }
1.251 + OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.252 + OutEdgeIt(const Invalid& i) : e(i) { }
1.253 + OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
1.254 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.255 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.256 + };
1.257 + class InEdgeIt {
1.258 + friend class GraphWrapper<Graph>;
1.259 + friend class RevGraphWrapper<Graph>;
1.260 + typename Graph::OutEdgeIt e;
1.261 + public:
1.262 + InEdgeIt() { }
1.263 + InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.264 + InEdgeIt(const Invalid& i) : e(i) { }
1.265 + InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
1.266 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.267 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.268 + };
1.269 +
1.270 + using GraphWrapper<Graph>::first;
1.271 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.272 + i=OutEdgeIt(*this, p); return i;
1.273 + }
1.274 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.275 + i=InEdgeIt(*this, p); return i;
1.276 + }
1.277 +
1.278 + using GraphWrapper<Graph>::next;
1.279 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.280 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.281 +
1.282 + Node aNode(const OutEdgeIt& e) const {
1.283 + return Node(this->graph->aNode(e.e)); }
1.284 + Node aNode(const InEdgeIt& e) const {
1.285 + return Node(this->graph->aNode(e.e)); }
1.286 + Node bNode(const OutEdgeIt& e) const {
1.287 + return Node(this->graph->bNode(e.e)); }
1.288 + Node bNode(const InEdgeIt& e) const {
1.289 + return Node(this->graph->bNode(e.e)); }
1.290 +
1.291 + Node tail(const Edge& e) const {
1.292 + return GraphWrapper<Graph>::head(e); }
1.293 + Node head(const Edge& e) const {
1.294 + return GraphWrapper<Graph>::tail(e); }
1.295 +
1.296 + };
1.297 +
1.298 + /// Wrapper for hiding nodes and edges from a graph.
1.299 +
1.300 + /// This wrapper shows a graph with filtered node-set and
1.301 + /// edge-set. The quick brown fox iterator jumps over
1.302 + /// the lazy dog nodes or edges if the values for them are false
1.303 + /// in the bool maps.
1.304 + ///
1.305 + ///\author Marton Makai
1.306 + template<typename Graph, typename NodeFilterMap,
1.307 + typename EdgeFilterMap>
1.308 + class SubGraphWrapper : public GraphWrapper<Graph> {
1.309 + protected:
1.310 + NodeFilterMap* node_filter_map;
1.311 + EdgeFilterMap* edge_filter_map;
1.312 +
1.313 + SubGraphWrapper() : GraphWrapper<Graph>(0),
1.314 + node_filter_map(0), edge_filter_map(0) { }
1.315 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
1.316 + node_filter_map=&_node_filter_map;
1.317 + }
1.318 + void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
1.319 + edge_filter_map=&_edge_filter_map;
1.320 + }
1.321 +
1.322 + public:
1.323 +
1.324 + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.325 + EdgeFilterMap& _edge_filter_map) :
1.326 + GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.327 + edge_filter_map(&_edge_filter_map) { }
1.328 +
1.329 + typedef typename GraphWrapper<Graph>::Node Node;
1.330 + class NodeIt {
1.331 + friend class GraphWrapper<Graph>;
1.332 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.333 + typename Graph::NodeIt n;
1.334 + public:
1.335 + NodeIt() { }
1.336 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.337 + NodeIt(const Invalid& i) : n(i) { }
1.338 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.339 + n(*(_G.graph)) {
1.340 + while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.341 + _G.graph->next(n);
1.342 + }
1.343 + operator Node() const { return Node(typename Graph::Node(n)); }
1.344 + };
1.345 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.346 + class OutEdgeIt {
1.347 + friend class GraphWrapper<Graph>;
1.348 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.349 + typename Graph::OutEdgeIt e;
1.350 + public:
1.351 + OutEdgeIt() { }
1.352 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.353 + OutEdgeIt(const Invalid& i) : e(i) { }
1.354 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.355 + const Node& _n) :
1.356 + e(*(_G.graph), typename Graph::Node(_n)) {
1.357 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.358 + _G.graph->next(e);
1.359 + }
1.360 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.361 + };
1.362 + class InEdgeIt {
1.363 + friend class GraphWrapper<Graph>;
1.364 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.365 + typename Graph::InEdgeIt e;
1.366 + public:
1.367 + InEdgeIt() { }
1.368 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.369 + InEdgeIt(const Invalid& i) : e(i) { }
1.370 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.371 + const Node& _n) :
1.372 + e(*(_G.graph), typename Graph::Node(_n)) {
1.373 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.374 + _G.graph->next(e);
1.375 + }
1.376 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.377 + };
1.378 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.379 + class EdgeIt {
1.380 + friend class GraphWrapper<Graph>;
1.381 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.382 + typename Graph::EdgeIt e;
1.383 + public:
1.384 + EdgeIt() { }
1.385 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.386 + EdgeIt(const Invalid& i) : e(i) { }
1.387 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.388 + e(*(_G.graph)) {
1.389 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.390 + _G.graph->next(e);
1.391 + }
1.392 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.393 + };
1.394 +
1.395 + NodeIt& first(NodeIt& i) const {
1.396 + i=NodeIt(*this); return i;
1.397 + }
1.398 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.399 + i=OutEdgeIt(*this, p); return i;
1.400 + }
1.401 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.402 + i=InEdgeIt(*this, p); return i;
1.403 + }
1.404 + EdgeIt& first(EdgeIt& i) const {
1.405 + i=EdgeIt(*this); return i;
1.406 + }
1.407 +
1.408 + NodeIt& next(NodeIt& i) const {
1.409 + this->graph->next(i.n);
1.410 + while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
1.411 + this->graph->next(i.n); }
1.412 + return i;
1.413 + }
1.414 + OutEdgeIt& next(OutEdgeIt& i) const {
1.415 + this->graph->next(i.e);
1.416 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.417 + this->graph->next(i.e); }
1.418 + return i;
1.419 + }
1.420 + InEdgeIt& next(InEdgeIt& i) const {
1.421 + this->graph->next(i.e);
1.422 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.423 + this->graph->next(i.e); }
1.424 + return i;
1.425 + }
1.426 + EdgeIt& next(EdgeIt& i) const {
1.427 + this->graph->next(i.e);
1.428 + while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.429 + this->graph->next(i.e); }
1.430 + return i;
1.431 + }
1.432 +
1.433 + Node aNode(const OutEdgeIt& e) const {
1.434 + return Node(this->graph->aNode(e.e)); }
1.435 + Node aNode(const InEdgeIt& e) const {
1.436 + return Node(this->graph->aNode(e.e)); }
1.437 + Node bNode(const OutEdgeIt& e) const {
1.438 + return Node(this->graph->bNode(e.e)); }
1.439 + Node bNode(const InEdgeIt& e) const {
1.440 + return Node(this->graph->bNode(e.e)); }
1.441 +
1.442 + ///\todo
1.443 + ///Some doki, please.
1.444 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.445 + ///\todo
1.446 + ///Some doki, please.
1.447 + void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.448 +
1.449 + ///\todo
1.450 + ///Some doki, please.
1.451 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.452 + ///\todo
1.453 + ///Some doki, please.
1.454 + void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.455 +
1.456 + ///\todo
1.457 + ///Some doki, please.
1.458 + bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
1.459 + ///\todo
1.460 + ///Some doki, please.
1.461 + bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
1.462 + };
1.463 +
1.464 + /// A wrapper for forgetting the orientation of a graph.
1.465 +
1.466 + /// A wrapper for getting an undirected graph by forgetting
1.467 + /// the orientation of a directed one.
1.468 + template<typename Graph>
1.469 + class UndirGraphWrapper : public GraphWrapper<Graph> {
1.470 + protected:
1.471 + UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.472 +
1.473 + public:
1.474 + typedef typename GraphWrapper<Graph>::Node Node;
1.475 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.476 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.477 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.478 +
1.479 + UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.480 +
1.481 + class OutEdgeIt {
1.482 + friend class UndirGraphWrapper<Graph>;
1.483 + bool out_or_in; //true iff out
1.484 + typename Graph::OutEdgeIt out;
1.485 + typename Graph::InEdgeIt in;
1.486 + public:
1.487 + OutEdgeIt() { }
1.488 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.489 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.490 + out_or_in=true; _G.graph->first(out, _n);
1.491 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.492 + }
1.493 + operator Edge() const {
1.494 + if (out_or_in) return Edge(out); else return Edge(in);
1.495 + }
1.496 + };
1.497 +
1.498 +//FIXME InEdgeIt
1.499 + typedef OutEdgeIt InEdgeIt;
1.500 +
1.501 + using GraphWrapper<Graph>::first;
1.502 +// NodeIt& first(NodeIt& i) const {
1.503 +// i=NodeIt(*this); return i;
1.504 +// }
1.505 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.506 + i=OutEdgeIt(*this, p); return i;
1.507 + }
1.508 +//FIXME
1.509 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.510 +// i=InEdgeIt(*this, p); return i;
1.511 +// }
1.512 +// EdgeIt& first(EdgeIt& i) const {
1.513 +// i=EdgeIt(*this); return i;
1.514 +// }
1.515 +
1.516 + using GraphWrapper<Graph>::next;
1.517 +// NodeIt& next(NodeIt& n) const {
1.518 +// GraphWrapper<Graph>::next(n);
1.519 +// return n;
1.520 +// }
1.521 + OutEdgeIt& next(OutEdgeIt& e) const {
1.522 + if (e.out_or_in) {
1.523 + typename Graph::Node n=this->graph->tail(e.out);
1.524 + this->graph->next(e.out);
1.525 + if (!this->graph->valid(e.out)) {
1.526 + e.out_or_in=false; this->graph->first(e.in, n); }
1.527 + } else {
1.528 + this->graph->next(e.in);
1.529 + }
1.530 + return e;
1.531 + }
1.532 + //FIXME InEdgeIt
1.533 +// EdgeIt& next(EdgeIt& e) const {
1.534 +// GraphWrapper<Graph>::next(n);
1.535 +// // graph->next(e.e);
1.536 +// return e;
1.537 +// }
1.538 +
1.539 + Node aNode(const OutEdgeIt& e) const {
1.540 + if (e.out_or_in) return this->graph->tail(e); else
1.541 + return this->graph->head(e); }
1.542 + Node bNode(const OutEdgeIt& e) const {
1.543 + if (e.out_or_in) return this->graph->head(e); else
1.544 + return this->graph->tail(e); }
1.545 + };
1.546 +
1.547 +
1.548 +
1.549 + /// An undirected graph template
1.550 + template<typename Graph>
1.551 + class UndirGraph : public UndirGraphWrapper<Graph> {
1.552 + typedef UndirGraphWrapper<Graph> Parent;
1.553 + protected:
1.554 + Graph gr;
1.555 + public:
1.556 + UndirGraph() : UndirGraphWrapper<Graph>() {
1.557 + Parent::setGraph(gr);
1.558 + }
1.559 + };
1.560 +
1.561 +
1.562 +
1.563 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.564 +
1.565 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.566 + template<typename Graph, typename Number,
1.567 + typename CapacityMap, typename FlowMap>
1.568 + class ResGraphWrapper : public GraphWrapper<Graph> {
1.569 + protected:
1.570 + const CapacityMap* capacity;
1.571 + FlowMap* flow;
1.572 +
1.573 + ResGraphWrapper() : GraphWrapper<Graph>(0),
1.574 + capacity(0), flow(0) { }
1.575 + void setCapacityMap(const CapacityMap& _capacity_map) {
1.576 + capacity_map=&_capacity_map;
1.577 + }
1.578 + void setFlowMap(FlowMap& _flow) {
1.579 + flow=&_flow;
1.580 + }
1.581 +
1.582 + public:
1.583 +
1.584 + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.585 + FlowMap& _flow) :
1.586 + GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1.587 +
1.588 + class Edge;
1.589 + class OutEdgeIt;
1.590 + friend class Edge;
1.591 + friend class OutEdgeIt;
1.592 +
1.593 + typedef typename GraphWrapper<Graph>::Node Node;
1.594 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.595 + class Edge : public Graph::Edge {
1.596 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.597 + protected:
1.598 + bool forward; //true, iff forward
1.599 +// typename Graph::Edge e;
1.600 + public:
1.601 + Edge() { }
1.602 + Edge(const typename Graph::Edge& _e, bool _forward) :
1.603 + Graph::Edge(_e), forward(_forward) { }
1.604 + Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
1.605 +//the unique invalid iterator
1.606 + friend bool operator==(const Edge& u, const Edge& v) {
1.607 + return (v.forward==u.forward &&
1.608 + static_cast<typename Graph::Edge>(u)==
1.609 + static_cast<typename Graph::Edge>(v));
1.610 + }
1.611 + friend bool operator!=(const Edge& u, const Edge& v) {
1.612 + return (v.forward!=u.forward ||
1.613 + static_cast<typename Graph::Edge>(u)!=
1.614 + static_cast<typename Graph::Edge>(v));
1.615 + }
1.616 + };
1.617 +
1.618 + class OutEdgeIt {
1.619 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.620 + protected:
1.621 + typename Graph::OutEdgeIt out;
1.622 + typename Graph::InEdgeIt in;
1.623 + bool forward;
1.624 + public:
1.625 + OutEdgeIt() { }
1.626 + //FIXME
1.627 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.628 + OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.629 +//the unique invalid iterator
1.630 + OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.631 + forward=true;
1.632 + resG.graph->first(out, v);
1.633 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.634 + if (!resG.graph->valid(out)) {
1.635 + forward=false;
1.636 + resG.graph->first(in, v);
1.637 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.638 + }
1.639 + }
1.640 + operator Edge() const {
1.641 +// Edge e;
1.642 +// e.forward=this->forward;
1.643 +// if (this->forward) e=out; else e=in;
1.644 +// return e;
1.645 + if (this->forward)
1.646 + return Edge(out, this->forward);
1.647 + else
1.648 + return Edge(in, this->forward);
1.649 + }
1.650 + };
1.651 +
1.652 + class InEdgeIt {
1.653 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.654 + protected:
1.655 + typename Graph::OutEdgeIt out;
1.656 + typename Graph::InEdgeIt in;
1.657 + bool forward;
1.658 + public:
1.659 + InEdgeIt() { }
1.660 + //FIXME
1.661 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.662 + InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1.663 +//the unique invalid iterator
1.664 + InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.665 + forward=true;
1.666 + resG.graph->first(in, v);
1.667 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.668 + if (!resG.graph->valid(in)) {
1.669 + forward=false;
1.670 + resG.graph->first(out, v);
1.671 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.672 + }
1.673 + }
1.674 + operator Edge() const {
1.675 +// Edge e;
1.676 +// e.forward=this->forward;
1.677 +// if (this->forward) e=out; else e=in;
1.678 +// return e;
1.679 + if (this->forward)
1.680 + return Edge(in, this->forward);
1.681 + else
1.682 + return Edge(out, this->forward);
1.683 + }
1.684 + };
1.685 +
1.686 + class EdgeIt {
1.687 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.688 + protected:
1.689 + typename Graph::EdgeIt e;
1.690 + bool forward;
1.691 + public:
1.692 + EdgeIt() { }
1.693 + EdgeIt(const Invalid& i) : e(i), forward(false) { }
1.694 + EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
1.695 + forward=true;
1.696 + resG.graph->first(e);
1.697 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.698 + if (!resG.graph->valid(e)) {
1.699 + forward=false;
1.700 + resG.graph->first(e);
1.701 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.702 + }
1.703 + }
1.704 + operator Edge() const {
1.705 + return Edge(e, this->forward);
1.706 + }
1.707 + };
1.708 +
1.709 + using GraphWrapper<Graph>::first;
1.710 +// NodeIt& first(NodeIt& i) const {
1.711 +// i=NodeIt(*this); return i;
1.712 +// }
1.713 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.714 + i=OutEdgeIt(*this, p); return i;
1.715 + }
1.716 +// FIXME not tested
1.717 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.718 + i=InEdgeIt(*this, p); return i;
1.719 + }
1.720 + EdgeIt& first(EdgeIt& i) const {
1.721 + i=EdgeIt(*this); return i;
1.722 + }
1.723 +
1.724 + using GraphWrapper<Graph>::next;
1.725 +// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.726 + OutEdgeIt& next(OutEdgeIt& e) const {
1.727 + if (e.forward) {
1.728 + Node v=this->graph->aNode(e.out);
1.729 + this->graph->next(e.out);
1.730 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.731 + this->graph->next(e.out); }
1.732 + if (!this->graph->valid(e.out)) {
1.733 + e.forward=false;
1.734 + this->graph->first(e.in, v);
1.735 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.736 + this->graph->next(e.in); }
1.737 + }
1.738 + } else {
1.739 + this->graph->next(e.in);
1.740 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.741 + this->graph->next(e.in); }
1.742 + }
1.743 + return e;
1.744 + }
1.745 +// FIXME Not tested
1.746 + InEdgeIt& next(InEdgeIt& e) const {
1.747 + if (e.forward) {
1.748 + Node v=this->graph->aNode(e.in);
1.749 + this->graph->next(e.in);
1.750 + while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.751 + this->graph->next(e.in); }
1.752 + if (!this->graph->valid(e.in)) {
1.753 + e.forward=false;
1.754 + this->graph->first(e.out, v);
1.755 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.756 + this->graph->next(e.out); }
1.757 + }
1.758 + } else {
1.759 + this->graph->next(e.out);
1.760 + while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.761 + this->graph->next(e.out); }
1.762 + }
1.763 + return e;
1.764 + }
1.765 + EdgeIt& next(EdgeIt& e) const {
1.766 + if (e.forward) {
1.767 + this->graph->next(e.e);
1.768 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.769 + this->graph->next(e.e); }
1.770 + if (!this->graph->valid(e.e)) {
1.771 + e.forward=false;
1.772 + this->graph->first(e.e);
1.773 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.774 + this->graph->next(e.e); }
1.775 + }
1.776 + } else {
1.777 + this->graph->next(e.e);
1.778 + while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.779 + this->graph->next(e.e); }
1.780 + }
1.781 + return e;
1.782 + }
1.783 +
1.784 + Node tail(Edge e) const {
1.785 + return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
1.786 + Node head(Edge e) const {
1.787 + return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
1.788 +
1.789 + Node aNode(OutEdgeIt e) const {
1.790 + return ((e.forward) ? this->graph->aNode(e.out) :
1.791 + this->graph->aNode(e.in)); }
1.792 + Node bNode(OutEdgeIt e) const {
1.793 + return ((e.forward) ? this->graph->bNode(e.out) :
1.794 + this->graph->bNode(e.in)); }
1.795 +
1.796 + Node aNode(InEdgeIt e) const {
1.797 + return ((e.forward) ? this->graph->aNode(e.in) :
1.798 + this->graph->aNode(e.out)); }
1.799 + Node bNode(InEdgeIt e) const {
1.800 + return ((e.forward) ? this->graph->bNode(e.in) :
1.801 + this->graph->bNode(e.out)); }
1.802 +
1.803 +// int nodeNum() const { return graph->nodeNum(); }
1.804 + //FIXME
1.805 + void edgeNum() const { }
1.806 + //int edgeNum() const { return graph->edgeNum(); }
1.807 +
1.808 +
1.809 +// int id(Node v) const { return graph->id(v); }
1.810 +
1.811 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.812 + bool valid(Edge e) const {
1.813 + return this->graph->valid(e);
1.814 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.815 + }
1.816 +
1.817 + bool forward(const Edge& e) const { return e.forward; }
1.818 + bool backward(const Edge& e) const { return !e.forward; }
1.819 +
1.820 + void augment(const Edge& e, Number a) const {
1.821 + if (e.forward)
1.822 +// flow->set(e.out, flow->get(e.out)+a);
1.823 + flow->set(e, (*flow)[e]+a);
1.824 + else
1.825 +// flow->set(e.in, flow->get(e.in)-a);
1.826 + flow->set(e, (*flow)[e]-a);
1.827 + }
1.828 +
1.829 + Number resCap(const Edge& e) const {
1.830 + if (e.forward)
1.831 +// return (capacity->get(e.out)-flow->get(e.out));
1.832 + return ((*capacity)[e]-(*flow)[e]);
1.833 + else
1.834 +// return (flow->get(e.in));
1.835 + return ((*flow)[e]);
1.836 + }
1.837 +
1.838 +// Number resCap(typename Graph::OutEdgeIt out) const {
1.839 +// // return (capacity->get(out)-flow->get(out));
1.840 +// return ((*capacity)[out]-(*flow)[out]);
1.841 +// }
1.842 +
1.843 +// Number resCap(typename Graph::InEdgeIt in) const {
1.844 +// // return (flow->get(in));
1.845 +// return ((*flow)[in]);
1.846 +// }
1.847 +
1.848 + template <typename T>
1.849 + class EdgeMap {
1.850 + typename Graph::template EdgeMap<T> forward_map, backward_map;
1.851 + public:
1.852 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.853 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.854 + void set(Edge e, T a) {
1.855 + if (e.forward)
1.856 + forward_map.set(e.out, a);
1.857 + else
1.858 + backward_map.set(e.in, a);
1.859 + }
1.860 + T operator[](Edge e) const {
1.861 + if (e.forward)
1.862 + return forward_map[e.out];
1.863 + else
1.864 + return backward_map[e.in];
1.865 + }
1.866 +// T get(Edge e) const {
1.867 +// if (e.out_or_in)
1.868 +// return forward_map.get(e.out);
1.869 +// else
1.870 +// return backward_map.get(e.in);
1.871 +// }
1.872 + };
1.873 + };
1.874 +
1.875 + /// ErasingFirstGraphWrapper for blocking flows.
1.876 +
1.877 + /// ErasingFirstGraphWrapper for blocking flows.
1.878 + ///
1.879 + ///\author Marton Makai
1.880 + template<typename Graph, typename FirstOutEdgesMap>
1.881 + class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.882 + protected:
1.883 + FirstOutEdgesMap* first_out_edges;
1.884 + public:
1.885 + ErasingFirstGraphWrapper(Graph& _graph,
1.886 + FirstOutEdgesMap& _first_out_edges) :
1.887 + GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.888 +
1.889 + typedef typename GraphWrapper<Graph>::Node Node;
1.890 +// class NodeIt {
1.891 +// friend class GraphWrapper<Graph>;
1.892 +// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.893 +// typename Graph::NodeIt n;
1.894 +// public:
1.895 +// NodeIt() { }
1.896 +// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.897 +// NodeIt(const Invalid& i) : n(i) { }
1.898 +// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.899 +// n(*(_G.graph)) { }
1.900 +// operator Node() const { return Node(typename Graph::Node(n)); }
1.901 +// };
1.902 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.903 + class OutEdgeIt {
1.904 + friend class GraphWrapper<Graph>;
1.905 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.906 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.907 + typename Graph::OutEdgeIt e;
1.908 + public:
1.909 + OutEdgeIt() { }
1.910 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.911 + OutEdgeIt(const Invalid& i) : e(i) { }
1.912 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.913 + const Node& _n) :
1.914 + e((*_G.first_out_edges)[_n]) { }
1.915 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.916 + };
1.917 + class InEdgeIt {
1.918 + friend class GraphWrapper<Graph>;
1.919 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.920 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.921 + typename Graph::InEdgeIt e;
1.922 + public:
1.923 + InEdgeIt() { }
1.924 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.925 + InEdgeIt(const Invalid& i) : e(i) { }
1.926 + InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.927 + const Node& _n) :
1.928 + e(*(_G.graph), typename Graph::Node(_n)) { }
1.929 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.930 + };
1.931 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.932 + class EdgeIt {
1.933 + friend class GraphWrapper<Graph>;
1.934 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.935 +// typedef typename Graph::EdgeIt GraphEdgeIt;
1.936 + typename Graph::EdgeIt e;
1.937 + public:
1.938 + EdgeIt() { }
1.939 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.940 + EdgeIt(const Invalid& i) : e(i) { }
1.941 + EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.942 + e(*(_G.graph)) { }
1.943 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.944 + };
1.945 +
1.946 + using GraphWrapper<Graph>::first;
1.947 +// NodeIt& first(NodeIt& i) const {
1.948 +// i=NodeIt(*this); return i;
1.949 +// }
1.950 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.951 + i=OutEdgeIt(*this, p); return i;
1.952 + }
1.953 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.954 + i=InEdgeIt(*this, p); return i;
1.955 + }
1.956 + EdgeIt& first(EdgeIt& i) const {
1.957 + i=EdgeIt(*this); return i;
1.958 + }
1.959 +
1.960 + using GraphWrapper<Graph>::next;
1.961 +// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.962 + OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.963 + InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.964 + EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1.965 +
1.966 + Node aNode(const OutEdgeIt& e) const {
1.967 + return Node(this->graph->aNode(e.e)); }
1.968 + Node aNode(const InEdgeIt& e) const {
1.969 + return Node(this->graph->aNode(e.e)); }
1.970 + Node bNode(const OutEdgeIt& e) const {
1.971 + return Node(this->graph->bNode(e.e)); }
1.972 + Node bNode(const InEdgeIt& e) const {
1.973 + return Node(this->graph->bNode(e.e)); }
1.974 +
1.975 + void erase(const OutEdgeIt& e) const {
1.976 + OutEdgeIt f=e;
1.977 + this->next(f);
1.978 + first_out_edges->set(this->tail(e), f.e);
1.979 + }
1.980 + };
1.981 +
1.982 + ///@}
1.983 +
1.984 +} //namespace hugo
1.985 +
1.986 +
1.987 +#endif //HUGO_GRAPH_WRAPPER_H
1.988 +