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 +
2.1 --- a/src/work/marci/graph_wrapper.h Thu May 06 16:54:54 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,985 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#ifndef HUGO_GRAPH_WRAPPER_H
2.6 -#define HUGO_GRAPH_WRAPPER_H
2.7 -
2.8 -///\ingroup gwrappers
2.9 -///\file
2.10 -///\brief Several graph wrappers.
2.11 -///
2.12 -///This file contains several useful graph wrapper functions.
2.13 -///
2.14 -///\author Marton Makai
2.15 -
2.16 -#include <hugo/invalid.h>
2.17 -//#include <iter_map.h>
2.18 -
2.19 -namespace hugo {
2.20 -
2.21 - // Graph wrappers
2.22 -
2.23 - /// \addtogroup gwrappers
2.24 - /// A main parts of HUGOlib are the different graph structures,
2.25 - /// generic graph algorithms, graph concepts which couple these, and
2.26 - /// graph wrappers. While the previous ones are more or less clear, the
2.27 - /// latter notion needs further explanation.
2.28 - /// Graph wrappers are graph classes which serve for considering graph
2.29 - /// structures in different ways. A short example makes the notion much
2.30 - /// clearer.
2.31 - /// Suppose that we have an instance \c g of a directed graph
2.32 - /// type say \c ListGraph and an algorithm
2.33 - /// \code template<typename Graph> int algorithm(const Graph&); \endcode
2.34 - /// is needed to run on the reversely oriented graph.
2.35 - /// It may be expensive (in time or in memory usage) to copy
2.36 - /// \c g with the reverse orientation.
2.37 - /// Thus, a wrapper class
2.38 - /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
2.39 - /// The code looks as follows
2.40 - /// \code
2.41 - /// ListGraph g;
2.42 - /// RevGraphWrapper<ListGraph> rgw(g);
2.43 - /// int result=algorithm(rgw);
2.44 - /// \endcode
2.45 - /// After running the algorithm, the original graph \c g
2.46 - /// remains untouched. Thus the graph wrapper used above is to consider the
2.47 - /// original graph with reverse orientation.
2.48 - /// This techniques gives rise to an elegant code, and
2.49 - /// based on stable graph wrappers, complex algorithms can be
2.50 - /// implemented easily.
2.51 - /// In flow, circulation and bipartite matching problems, the residual
2.52 - /// graph is of particular importance. Combining a wrapper implementing
2.53 - /// this, shortest path algorithms and minimum mean cycle algorithms,
2.54 - /// a range of weighted and cardinality optimization algorithms can be
2.55 - /// obtained. For lack of space, for other examples,
2.56 - /// the interested user is referred to the detailed documentation of graph
2.57 - /// wrappers.
2.58 - /// The behavior of graph wrappers can be very different. Some of them keep
2.59 - /// capabilities of the original graph while in other cases this would be
2.60 - /// meaningless. This means that the concepts that they are a model of depend
2.61 - /// on the graph wrapper, and the wrapped graph(s).
2.62 - /// If an edge of \c rgw is deleted, this is carried out by
2.63 - /// deleting the corresponding edge of \c g. But for a residual
2.64 - /// graph, this operation has no sense.
2.65 - /// Let we stand one more example here to simplify your work.
2.66 - /// wrapper class
2.67 - /// \code template<typename Graph> class RevGraphWrapper; \endcode
2.68 - /// has constructor
2.69 - /// <tt> RevGraphWrapper(Graph& _g)</tt>.
2.70 - /// This means that in a situation,
2.71 - /// when a <tt> const ListGraph& </tt> reference to a graph is given,
2.72 - /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
2.73 - /// \code
2.74 - /// int algorithm1(const ListGraph& g) {
2.75 - /// RevGraphWrapper<const ListGraph> rgw(g);
2.76 - /// return algorithm2(rgw);
2.77 - /// }
2.78 - /// \endcode
2.79 -
2.80 - /// \addtogroup gwrappers
2.81 - /// @{
2.82 -
2.83 - ///Base type for the Graph Wrappers
2.84 -
2.85 - ///This is the base type for the Graph Wrappers.
2.86 - ///\todo Some more docs...
2.87 - ///
2.88 - ///\author Marton Makai
2.89 -
2.90 - template<typename Graph>
2.91 - class GraphWrapper {
2.92 - protected:
2.93 - Graph* graph;
2.94 - GraphWrapper() : graph(0) { }
2.95 - void setGraph(Graph& _graph) { graph=&_graph; }
2.96 -
2.97 - public:
2.98 - typedef Graph BaseGraph;
2.99 - typedef Graph ParentGraph;
2.100 -
2.101 - GraphWrapper(Graph& _graph) : graph(&_graph) { }
2.102 -// Graph& getGraph() const { return *graph; }
2.103 -
2.104 -// typedef typename Graph::Node Node;
2.105 - class Node : public Graph::Node {
2.106 - friend class GraphWrapper<Graph>;
2.107 - public:
2.108 - Node() { }
2.109 - Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
2.110 - Node(const Invalid& i) : Graph::Node(i) { }
2.111 - };
2.112 - class NodeIt {
2.113 - friend class GraphWrapper<Graph>;
2.114 - typename Graph::NodeIt n;
2.115 - public:
2.116 - NodeIt() { }
2.117 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
2.118 - NodeIt(const Invalid& i) : n(i) { }
2.119 - NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
2.120 - operator Node() const { return Node(typename Graph::Node(n)); }
2.121 - };
2.122 -// typedef typename Graph::Edge Edge;
2.123 - class Edge : public Graph::Edge {
2.124 - friend class GraphWrapper<Graph>;
2.125 - public:
2.126 - Edge() { }
2.127 - Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
2.128 - Edge(const Invalid& i) : Graph::Edge(i) { }
2.129 - };
2.130 - class OutEdgeIt {
2.131 - friend class GraphWrapper<Graph>;
2.132 - typename Graph::OutEdgeIt e;
2.133 - public:
2.134 - OutEdgeIt() { }
2.135 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.136 - OutEdgeIt(const Invalid& i) : e(i) { }
2.137 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
2.138 - e(*(_G.graph), typename Graph::Node(_n)) { }
2.139 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.140 - };
2.141 - class InEdgeIt {
2.142 - friend class GraphWrapper<Graph>;
2.143 - typename Graph::InEdgeIt e;
2.144 - public:
2.145 - InEdgeIt() { }
2.146 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.147 - InEdgeIt(const Invalid& i) : e(i) { }
2.148 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
2.149 - e(*(_G.graph), typename Graph::Node(_n)) { }
2.150 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.151 - };
2.152 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.153 - class EdgeIt {
2.154 - friend class GraphWrapper<Graph>;
2.155 - typename Graph::EdgeIt e;
2.156 - public:
2.157 - EdgeIt() { }
2.158 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
2.159 - EdgeIt(const Invalid& i) : e(i) { }
2.160 - EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
2.161 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.162 - };
2.163 -
2.164 - NodeIt& first(NodeIt& i) const {
2.165 - i=NodeIt(*this); return i;
2.166 - }
2.167 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.168 - i=OutEdgeIt(*this, p); return i;
2.169 - }
2.170 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.171 - i=InEdgeIt(*this, p); return i;
2.172 - }
2.173 - EdgeIt& first(EdgeIt& i) const {
2.174 - i=EdgeIt(*this); return i;
2.175 - }
2.176 -
2.177 - NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
2.178 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
2.179 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
2.180 - EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
2.181 -
2.182 - Node tail(const Edge& e) const {
2.183 - return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
2.184 - Node head(const Edge& e) const {
2.185 - return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
2.186 -
2.187 - bool valid(const Node& n) const {
2.188 - return graph->valid(static_cast<typename Graph::Node>(n)); }
2.189 - bool valid(const Edge& e) const {
2.190 - return graph->valid(static_cast<typename Graph::Edge>(e)); }
2.191 -
2.192 - int nodeNum() const { return graph->nodeNum(); }
2.193 - int edgeNum() const { return graph->edgeNum(); }
2.194 -
2.195 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
2.196 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
2.197 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.198 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.199 -
2.200 - Node addNode() const { return Node(graph->addNode()); }
2.201 - Edge addEdge(const Node& tail, const Node& head) const {
2.202 - return Edge(graph->addEdge(tail, head)); }
2.203 -
2.204 - void erase(const Node& i) const { graph->erase(i); }
2.205 - void erase(const Edge& i) const { graph->erase(i); }
2.206 -
2.207 - void clear() const { graph->clear(); }
2.208 -
2.209 - template<typename T> class NodeMap : public Graph::template NodeMap<T> {
2.210 - typedef typename Graph::template NodeMap<T> Parent;
2.211 - public:
2.212 - NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
2.213 - NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
2.214 - };
2.215 -
2.216 - template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
2.217 - typedef typename Graph::template EdgeMap<T> Parent;
2.218 - public:
2.219 - EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
2.220 - EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
2.221 - };
2.222 - };
2.223 -
2.224 - /// A graph wrapper which reverses the orientation of the edges.
2.225 -
2.226 - /// A graph wrapper which reverses the orientation of the edges.
2.227 - ///
2.228 - ///\author Marton Makai
2.229 - template<typename Graph>
2.230 - class RevGraphWrapper : public GraphWrapper<Graph> {
2.231 - protected:
2.232 - RevGraphWrapper() : GraphWrapper<Graph>(0) { }
2.233 - public:
2.234 - RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
2.235 -
2.236 - typedef typename GraphWrapper<Graph>::Node Node;
2.237 - typedef typename GraphWrapper<Graph>::Edge Edge;
2.238 - //If Graph::OutEdgeIt is not defined
2.239 - //and we do not want to use RevGraphWrapper::InEdgeIt,
2.240 - //the typdef techinque does not work.
2.241 - //Unfortunately all the typedefs are instantiated in templates.
2.242 - //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
2.243 - //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
2.244 -
2.245 - class OutEdgeIt {
2.246 - friend class GraphWrapper<Graph>;
2.247 - friend class RevGraphWrapper<Graph>;
2.248 - typename Graph::InEdgeIt e;
2.249 - public:
2.250 - OutEdgeIt() { }
2.251 - OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.252 - OutEdgeIt(const Invalid& i) : e(i) { }
2.253 - OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
2.254 - e(*(_G.graph), typename Graph::Node(_n)) { }
2.255 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.256 - };
2.257 - class InEdgeIt {
2.258 - friend class GraphWrapper<Graph>;
2.259 - friend class RevGraphWrapper<Graph>;
2.260 - typename Graph::OutEdgeIt e;
2.261 - public:
2.262 - InEdgeIt() { }
2.263 - InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.264 - InEdgeIt(const Invalid& i) : e(i) { }
2.265 - InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
2.266 - e(*(_G.graph), typename Graph::Node(_n)) { }
2.267 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.268 - };
2.269 -
2.270 - using GraphWrapper<Graph>::first;
2.271 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.272 - i=OutEdgeIt(*this, p); return i;
2.273 - }
2.274 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.275 - i=InEdgeIt(*this, p); return i;
2.276 - }
2.277 -
2.278 - using GraphWrapper<Graph>::next;
2.279 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
2.280 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
2.281 -
2.282 - Node aNode(const OutEdgeIt& e) const {
2.283 - return Node(this->graph->aNode(e.e)); }
2.284 - Node aNode(const InEdgeIt& e) const {
2.285 - return Node(this->graph->aNode(e.e)); }
2.286 - Node bNode(const OutEdgeIt& e) const {
2.287 - return Node(this->graph->bNode(e.e)); }
2.288 - Node bNode(const InEdgeIt& e) const {
2.289 - return Node(this->graph->bNode(e.e)); }
2.290 -
2.291 - Node tail(const Edge& e) const {
2.292 - return GraphWrapper<Graph>::head(e); }
2.293 - Node head(const Edge& e) const {
2.294 - return GraphWrapper<Graph>::tail(e); }
2.295 -
2.296 - };
2.297 -
2.298 - /// Wrapper for hiding nodes and edges from a graph.
2.299 -
2.300 - /// This wrapper shows a graph with filtered node-set and
2.301 - /// edge-set. The quick brown fox iterator jumps over
2.302 - /// the lazy dog nodes or edges if the values for them are false
2.303 - /// in the bool maps.
2.304 - ///
2.305 - ///\author Marton Makai
2.306 - template<typename Graph, typename NodeFilterMap,
2.307 - typename EdgeFilterMap>
2.308 - class SubGraphWrapper : public GraphWrapper<Graph> {
2.309 - protected:
2.310 - NodeFilterMap* node_filter_map;
2.311 - EdgeFilterMap* edge_filter_map;
2.312 -
2.313 - SubGraphWrapper() : GraphWrapper<Graph>(0),
2.314 - node_filter_map(0), edge_filter_map(0) { }
2.315 - void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
2.316 - node_filter_map=&_node_filter_map;
2.317 - }
2.318 - void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
2.319 - edge_filter_map=&_edge_filter_map;
2.320 - }
2.321 -
2.322 - public:
2.323 -
2.324 - SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
2.325 - EdgeFilterMap& _edge_filter_map) :
2.326 - GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
2.327 - edge_filter_map(&_edge_filter_map) { }
2.328 -
2.329 - typedef typename GraphWrapper<Graph>::Node Node;
2.330 - class NodeIt {
2.331 - friend class GraphWrapper<Graph>;
2.332 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
2.333 - typename Graph::NodeIt n;
2.334 - public:
2.335 - NodeIt() { }
2.336 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
2.337 - NodeIt(const Invalid& i) : n(i) { }
2.338 - NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
2.339 - n(*(_G.graph)) {
2.340 - while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
2.341 - _G.graph->next(n);
2.342 - }
2.343 - operator Node() const { return Node(typename Graph::Node(n)); }
2.344 - };
2.345 - typedef typename GraphWrapper<Graph>::Edge Edge;
2.346 - class OutEdgeIt {
2.347 - friend class GraphWrapper<Graph>;
2.348 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
2.349 - typename Graph::OutEdgeIt e;
2.350 - public:
2.351 - OutEdgeIt() { }
2.352 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.353 - OutEdgeIt(const Invalid& i) : e(i) { }
2.354 - OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
2.355 - const Node& _n) :
2.356 - e(*(_G.graph), typename Graph::Node(_n)) {
2.357 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
2.358 - _G.graph->next(e);
2.359 - }
2.360 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.361 - };
2.362 - class InEdgeIt {
2.363 - friend class GraphWrapper<Graph>;
2.364 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
2.365 - typename Graph::InEdgeIt e;
2.366 - public:
2.367 - InEdgeIt() { }
2.368 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.369 - InEdgeIt(const Invalid& i) : e(i) { }
2.370 - InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
2.371 - const Node& _n) :
2.372 - e(*(_G.graph), typename Graph::Node(_n)) {
2.373 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
2.374 - _G.graph->next(e);
2.375 - }
2.376 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.377 - };
2.378 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.379 - class EdgeIt {
2.380 - friend class GraphWrapper<Graph>;
2.381 - friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
2.382 - typename Graph::EdgeIt e;
2.383 - public:
2.384 - EdgeIt() { }
2.385 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
2.386 - EdgeIt(const Invalid& i) : e(i) { }
2.387 - EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
2.388 - e(*(_G.graph)) {
2.389 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
2.390 - _G.graph->next(e);
2.391 - }
2.392 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.393 - };
2.394 -
2.395 - NodeIt& first(NodeIt& i) const {
2.396 - i=NodeIt(*this); return i;
2.397 - }
2.398 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.399 - i=OutEdgeIt(*this, p); return i;
2.400 - }
2.401 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.402 - i=InEdgeIt(*this, p); return i;
2.403 - }
2.404 - EdgeIt& first(EdgeIt& i) const {
2.405 - i=EdgeIt(*this); return i;
2.406 - }
2.407 -
2.408 - NodeIt& next(NodeIt& i) const {
2.409 - this->graph->next(i.n);
2.410 - while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
2.411 - this->graph->next(i.n); }
2.412 - return i;
2.413 - }
2.414 - OutEdgeIt& next(OutEdgeIt& i) const {
2.415 - this->graph->next(i.e);
2.416 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
2.417 - this->graph->next(i.e); }
2.418 - return i;
2.419 - }
2.420 - InEdgeIt& next(InEdgeIt& i) const {
2.421 - this->graph->next(i.e);
2.422 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
2.423 - this->graph->next(i.e); }
2.424 - return i;
2.425 - }
2.426 - EdgeIt& next(EdgeIt& i) const {
2.427 - this->graph->next(i.e);
2.428 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
2.429 - this->graph->next(i.e); }
2.430 - return i;
2.431 - }
2.432 -
2.433 - Node aNode(const OutEdgeIt& e) const {
2.434 - return Node(this->graph->aNode(e.e)); }
2.435 - Node aNode(const InEdgeIt& e) const {
2.436 - return Node(this->graph->aNode(e.e)); }
2.437 - Node bNode(const OutEdgeIt& e) const {
2.438 - return Node(this->graph->bNode(e.e)); }
2.439 - Node bNode(const InEdgeIt& e) const {
2.440 - return Node(this->graph->bNode(e.e)); }
2.441 -
2.442 - ///\todo
2.443 - ///Some doki, please.
2.444 - void hide(const Node& n) const { node_filter_map->set(n, false); }
2.445 - ///\todo
2.446 - ///Some doki, please.
2.447 - void hide(const Edge& e) const { edge_filter_map->set(e, false); }
2.448 -
2.449 - ///\todo
2.450 - ///Some doki, please.
2.451 - void unHide(const Node& n) const { node_filter_map->set(n, true); }
2.452 - ///\todo
2.453 - ///Some doki, please.
2.454 - void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
2.455 -
2.456 - ///\todo
2.457 - ///Some doki, please.
2.458 - bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
2.459 - ///\todo
2.460 - ///Some doki, please.
2.461 - bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
2.462 - };
2.463 -
2.464 - /// A wrapper for forgetting the orientation of a graph.
2.465 -
2.466 - /// A wrapper for getting an undirected graph by forgetting
2.467 - /// the orientation of a directed one.
2.468 - template<typename Graph>
2.469 - class UndirGraphWrapper : public GraphWrapper<Graph> {
2.470 - protected:
2.471 - UndirGraphWrapper() : GraphWrapper<Graph>() { }
2.472 -
2.473 - public:
2.474 - typedef typename GraphWrapper<Graph>::Node Node;
2.475 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
2.476 - typedef typename GraphWrapper<Graph>::Edge Edge;
2.477 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
2.478 -
2.479 - UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
2.480 -
2.481 - class OutEdgeIt {
2.482 - friend class UndirGraphWrapper<Graph>;
2.483 - bool out_or_in; //true iff out
2.484 - typename Graph::OutEdgeIt out;
2.485 - typename Graph::InEdgeIt in;
2.486 - public:
2.487 - OutEdgeIt() { }
2.488 - OutEdgeIt(const Invalid& i) : Edge(i) { }
2.489 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
2.490 - out_or_in=true; _G.graph->first(out, _n);
2.491 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
2.492 - }
2.493 - operator Edge() const {
2.494 - if (out_or_in) return Edge(out); else return Edge(in);
2.495 - }
2.496 - };
2.497 -
2.498 -//FIXME InEdgeIt
2.499 - typedef OutEdgeIt InEdgeIt;
2.500 -
2.501 - using GraphWrapper<Graph>::first;
2.502 -// NodeIt& first(NodeIt& i) const {
2.503 -// i=NodeIt(*this); return i;
2.504 -// }
2.505 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.506 - i=OutEdgeIt(*this, p); return i;
2.507 - }
2.508 -//FIXME
2.509 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.510 -// i=InEdgeIt(*this, p); return i;
2.511 -// }
2.512 -// EdgeIt& first(EdgeIt& i) const {
2.513 -// i=EdgeIt(*this); return i;
2.514 -// }
2.515 -
2.516 - using GraphWrapper<Graph>::next;
2.517 -// NodeIt& next(NodeIt& n) const {
2.518 -// GraphWrapper<Graph>::next(n);
2.519 -// return n;
2.520 -// }
2.521 - OutEdgeIt& next(OutEdgeIt& e) const {
2.522 - if (e.out_or_in) {
2.523 - typename Graph::Node n=this->graph->tail(e.out);
2.524 - this->graph->next(e.out);
2.525 - if (!this->graph->valid(e.out)) {
2.526 - e.out_or_in=false; this->graph->first(e.in, n); }
2.527 - } else {
2.528 - this->graph->next(e.in);
2.529 - }
2.530 - return e;
2.531 - }
2.532 - //FIXME InEdgeIt
2.533 -// EdgeIt& next(EdgeIt& e) const {
2.534 -// GraphWrapper<Graph>::next(n);
2.535 -// // graph->next(e.e);
2.536 -// return e;
2.537 -// }
2.538 -
2.539 - Node aNode(const OutEdgeIt& e) const {
2.540 - if (e.out_or_in) return this->graph->tail(e); else
2.541 - return this->graph->head(e); }
2.542 - Node bNode(const OutEdgeIt& e) const {
2.543 - if (e.out_or_in) return this->graph->head(e); else
2.544 - return this->graph->tail(e); }
2.545 - };
2.546 -
2.547 -
2.548 -
2.549 - /// An undirected graph template
2.550 - template<typename Graph>
2.551 - class UndirGraph : public UndirGraphWrapper<Graph> {
2.552 - typedef UndirGraphWrapper<Graph> Parent;
2.553 - protected:
2.554 - Graph gr;
2.555 - public:
2.556 - UndirGraph() : UndirGraphWrapper<Graph>() {
2.557 - Parent::setGraph(gr);
2.558 - }
2.559 - };
2.560 -
2.561 -
2.562 -
2.563 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
2.564 -
2.565 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
2.566 - template<typename Graph, typename Number,
2.567 - typename CapacityMap, typename FlowMap>
2.568 - class ResGraphWrapper : public GraphWrapper<Graph> {
2.569 - protected:
2.570 - const CapacityMap* capacity;
2.571 - FlowMap* flow;
2.572 -
2.573 - ResGraphWrapper() : GraphWrapper<Graph>(0),
2.574 - capacity(0), flow(0) { }
2.575 - void setCapacityMap(const CapacityMap& _capacity_map) {
2.576 - capacity_map=&_capacity_map;
2.577 - }
2.578 - void setFlowMap(FlowMap& _flow) {
2.579 - flow=&_flow;
2.580 - }
2.581 -
2.582 - public:
2.583 -
2.584 - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
2.585 - FlowMap& _flow) :
2.586 - GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
2.587 -
2.588 - class Edge;
2.589 - class OutEdgeIt;
2.590 - friend class Edge;
2.591 - friend class OutEdgeIt;
2.592 -
2.593 - typedef typename GraphWrapper<Graph>::Node Node;
2.594 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
2.595 - class Edge : public Graph::Edge {
2.596 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
2.597 - protected:
2.598 - bool forward; //true, iff forward
2.599 -// typename Graph::Edge e;
2.600 - public:
2.601 - Edge() { }
2.602 - Edge(const typename Graph::Edge& _e, bool _forward) :
2.603 - Graph::Edge(_e), forward(_forward) { }
2.604 - Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
2.605 -//the unique invalid iterator
2.606 - friend bool operator==(const Edge& u, const Edge& v) {
2.607 - return (v.forward==u.forward &&
2.608 - static_cast<typename Graph::Edge>(u)==
2.609 - static_cast<typename Graph::Edge>(v));
2.610 - }
2.611 - friend bool operator!=(const Edge& u, const Edge& v) {
2.612 - return (v.forward!=u.forward ||
2.613 - static_cast<typename Graph::Edge>(u)!=
2.614 - static_cast<typename Graph::Edge>(v));
2.615 - }
2.616 - };
2.617 -
2.618 - class OutEdgeIt {
2.619 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
2.620 - protected:
2.621 - typename Graph::OutEdgeIt out;
2.622 - typename Graph::InEdgeIt in;
2.623 - bool forward;
2.624 - public:
2.625 - OutEdgeIt() { }
2.626 - //FIXME
2.627 -// OutEdgeIt(const Edge& e) : Edge(e) { }
2.628 - OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
2.629 -//the unique invalid iterator
2.630 - OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
2.631 - forward=true;
2.632 - resG.graph->first(out, v);
2.633 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
2.634 - if (!resG.graph->valid(out)) {
2.635 - forward=false;
2.636 - resG.graph->first(in, v);
2.637 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
2.638 - }
2.639 - }
2.640 - operator Edge() const {
2.641 -// Edge e;
2.642 -// e.forward=this->forward;
2.643 -// if (this->forward) e=out; else e=in;
2.644 -// return e;
2.645 - if (this->forward)
2.646 - return Edge(out, this->forward);
2.647 - else
2.648 - return Edge(in, this->forward);
2.649 - }
2.650 - };
2.651 -
2.652 - class InEdgeIt {
2.653 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
2.654 - protected:
2.655 - typename Graph::OutEdgeIt out;
2.656 - typename Graph::InEdgeIt in;
2.657 - bool forward;
2.658 - public:
2.659 - InEdgeIt() { }
2.660 - //FIXME
2.661 -// OutEdgeIt(const Edge& e) : Edge(e) { }
2.662 - InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
2.663 -//the unique invalid iterator
2.664 - InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
2.665 - forward=true;
2.666 - resG.graph->first(in, v);
2.667 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
2.668 - if (!resG.graph->valid(in)) {
2.669 - forward=false;
2.670 - resG.graph->first(out, v);
2.671 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
2.672 - }
2.673 - }
2.674 - operator Edge() const {
2.675 -// Edge e;
2.676 -// e.forward=this->forward;
2.677 -// if (this->forward) e=out; else e=in;
2.678 -// return e;
2.679 - if (this->forward)
2.680 - return Edge(in, this->forward);
2.681 - else
2.682 - return Edge(out, this->forward);
2.683 - }
2.684 - };
2.685 -
2.686 - class EdgeIt {
2.687 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
2.688 - protected:
2.689 - typename Graph::EdgeIt e;
2.690 - bool forward;
2.691 - public:
2.692 - EdgeIt() { }
2.693 - EdgeIt(const Invalid& i) : e(i), forward(false) { }
2.694 - EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
2.695 - forward=true;
2.696 - resG.graph->first(e);
2.697 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
2.698 - if (!resG.graph->valid(e)) {
2.699 - forward=false;
2.700 - resG.graph->first(e);
2.701 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
2.702 - }
2.703 - }
2.704 - operator Edge() const {
2.705 - return Edge(e, this->forward);
2.706 - }
2.707 - };
2.708 -
2.709 - using GraphWrapper<Graph>::first;
2.710 -// NodeIt& first(NodeIt& i) const {
2.711 -// i=NodeIt(*this); return i;
2.712 -// }
2.713 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.714 - i=OutEdgeIt(*this, p); return i;
2.715 - }
2.716 -// FIXME not tested
2.717 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.718 - i=InEdgeIt(*this, p); return i;
2.719 - }
2.720 - EdgeIt& first(EdgeIt& i) const {
2.721 - i=EdgeIt(*this); return i;
2.722 - }
2.723 -
2.724 - using GraphWrapper<Graph>::next;
2.725 -// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
2.726 - OutEdgeIt& next(OutEdgeIt& e) const {
2.727 - if (e.forward) {
2.728 - Node v=this->graph->aNode(e.out);
2.729 - this->graph->next(e.out);
2.730 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
2.731 - this->graph->next(e.out); }
2.732 - if (!this->graph->valid(e.out)) {
2.733 - e.forward=false;
2.734 - this->graph->first(e.in, v);
2.735 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
2.736 - this->graph->next(e.in); }
2.737 - }
2.738 - } else {
2.739 - this->graph->next(e.in);
2.740 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
2.741 - this->graph->next(e.in); }
2.742 - }
2.743 - return e;
2.744 - }
2.745 -// FIXME Not tested
2.746 - InEdgeIt& next(InEdgeIt& e) const {
2.747 - if (e.forward) {
2.748 - Node v=this->graph->aNode(e.in);
2.749 - this->graph->next(e.in);
2.750 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
2.751 - this->graph->next(e.in); }
2.752 - if (!this->graph->valid(e.in)) {
2.753 - e.forward=false;
2.754 - this->graph->first(e.out, v);
2.755 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
2.756 - this->graph->next(e.out); }
2.757 - }
2.758 - } else {
2.759 - this->graph->next(e.out);
2.760 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
2.761 - this->graph->next(e.out); }
2.762 - }
2.763 - return e;
2.764 - }
2.765 - EdgeIt& next(EdgeIt& e) const {
2.766 - if (e.forward) {
2.767 - this->graph->next(e.e);
2.768 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
2.769 - this->graph->next(e.e); }
2.770 - if (!this->graph->valid(e.e)) {
2.771 - e.forward=false;
2.772 - this->graph->first(e.e);
2.773 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
2.774 - this->graph->next(e.e); }
2.775 - }
2.776 - } else {
2.777 - this->graph->next(e.e);
2.778 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
2.779 - this->graph->next(e.e); }
2.780 - }
2.781 - return e;
2.782 - }
2.783 -
2.784 - Node tail(Edge e) const {
2.785 - return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
2.786 - Node head(Edge e) const {
2.787 - return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
2.788 -
2.789 - Node aNode(OutEdgeIt e) const {
2.790 - return ((e.forward) ? this->graph->aNode(e.out) :
2.791 - this->graph->aNode(e.in)); }
2.792 - Node bNode(OutEdgeIt e) const {
2.793 - return ((e.forward) ? this->graph->bNode(e.out) :
2.794 - this->graph->bNode(e.in)); }
2.795 -
2.796 - Node aNode(InEdgeIt e) const {
2.797 - return ((e.forward) ? this->graph->aNode(e.in) :
2.798 - this->graph->aNode(e.out)); }
2.799 - Node bNode(InEdgeIt e) const {
2.800 - return ((e.forward) ? this->graph->bNode(e.in) :
2.801 - this->graph->bNode(e.out)); }
2.802 -
2.803 -// int nodeNum() const { return graph->nodeNum(); }
2.804 - //FIXME
2.805 - void edgeNum() const { }
2.806 - //int edgeNum() const { return graph->edgeNum(); }
2.807 -
2.808 -
2.809 -// int id(Node v) const { return graph->id(v); }
2.810 -
2.811 - bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
2.812 - bool valid(Edge e) const {
2.813 - return this->graph->valid(e);
2.814 - //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
2.815 - }
2.816 -
2.817 - bool forward(const Edge& e) const { return e.forward; }
2.818 - bool backward(const Edge& e) const { return !e.forward; }
2.819 -
2.820 - void augment(const Edge& e, Number a) const {
2.821 - if (e.forward)
2.822 -// flow->set(e.out, flow->get(e.out)+a);
2.823 - flow->set(e, (*flow)[e]+a);
2.824 - else
2.825 -// flow->set(e.in, flow->get(e.in)-a);
2.826 - flow->set(e, (*flow)[e]-a);
2.827 - }
2.828 -
2.829 - Number resCap(const Edge& e) const {
2.830 - if (e.forward)
2.831 -// return (capacity->get(e.out)-flow->get(e.out));
2.832 - return ((*capacity)[e]-(*flow)[e]);
2.833 - else
2.834 -// return (flow->get(e.in));
2.835 - return ((*flow)[e]);
2.836 - }
2.837 -
2.838 -// Number resCap(typename Graph::OutEdgeIt out) const {
2.839 -// // return (capacity->get(out)-flow->get(out));
2.840 -// return ((*capacity)[out]-(*flow)[out]);
2.841 -// }
2.842 -
2.843 -// Number resCap(typename Graph::InEdgeIt in) const {
2.844 -// // return (flow->get(in));
2.845 -// return ((*flow)[in]);
2.846 -// }
2.847 -
2.848 - template <typename T>
2.849 - class EdgeMap {
2.850 - typename Graph::template EdgeMap<T> forward_map, backward_map;
2.851 - public:
2.852 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
2.853 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
2.854 - void set(Edge e, T a) {
2.855 - if (e.forward)
2.856 - forward_map.set(e.out, a);
2.857 - else
2.858 - backward_map.set(e.in, a);
2.859 - }
2.860 - T operator[](Edge e) const {
2.861 - if (e.forward)
2.862 - return forward_map[e.out];
2.863 - else
2.864 - return backward_map[e.in];
2.865 - }
2.866 -// T get(Edge e) const {
2.867 -// if (e.out_or_in)
2.868 -// return forward_map.get(e.out);
2.869 -// else
2.870 -// return backward_map.get(e.in);
2.871 -// }
2.872 - };
2.873 - };
2.874 -
2.875 - /// ErasingFirstGraphWrapper for blocking flows.
2.876 -
2.877 - /// ErasingFirstGraphWrapper for blocking flows.
2.878 - ///
2.879 - ///\author Marton Makai
2.880 - template<typename Graph, typename FirstOutEdgesMap>
2.881 - class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
2.882 - protected:
2.883 - FirstOutEdgesMap* first_out_edges;
2.884 - public:
2.885 - ErasingFirstGraphWrapper(Graph& _graph,
2.886 - FirstOutEdgesMap& _first_out_edges) :
2.887 - GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
2.888 -
2.889 - typedef typename GraphWrapper<Graph>::Node Node;
2.890 -// class NodeIt {
2.891 -// friend class GraphWrapper<Graph>;
2.892 -// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
2.893 -// typename Graph::NodeIt n;
2.894 -// public:
2.895 -// NodeIt() { }
2.896 -// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
2.897 -// NodeIt(const Invalid& i) : n(i) { }
2.898 -// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
2.899 -// n(*(_G.graph)) { }
2.900 -// operator Node() const { return Node(typename Graph::Node(n)); }
2.901 -// };
2.902 - typedef typename GraphWrapper<Graph>::Edge Edge;
2.903 - class OutEdgeIt {
2.904 - friend class GraphWrapper<Graph>;
2.905 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
2.906 -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
2.907 - typename Graph::OutEdgeIt e;
2.908 - public:
2.909 - OutEdgeIt() { }
2.910 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.911 - OutEdgeIt(const Invalid& i) : e(i) { }
2.912 - OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
2.913 - const Node& _n) :
2.914 - e((*_G.first_out_edges)[_n]) { }
2.915 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.916 - };
2.917 - class InEdgeIt {
2.918 - friend class GraphWrapper<Graph>;
2.919 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
2.920 -// typedef typename Graph::InEdgeIt GraphInEdgeIt;
2.921 - typename Graph::InEdgeIt e;
2.922 - public:
2.923 - InEdgeIt() { }
2.924 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.925 - InEdgeIt(const Invalid& i) : e(i) { }
2.926 - InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
2.927 - const Node& _n) :
2.928 - e(*(_G.graph), typename Graph::Node(_n)) { }
2.929 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.930 - };
2.931 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.932 - class EdgeIt {
2.933 - friend class GraphWrapper<Graph>;
2.934 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
2.935 -// typedef typename Graph::EdgeIt GraphEdgeIt;
2.936 - typename Graph::EdgeIt e;
2.937 - public:
2.938 - EdgeIt() { }
2.939 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
2.940 - EdgeIt(const Invalid& i) : e(i) { }
2.941 - EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
2.942 - e(*(_G.graph)) { }
2.943 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.944 - };
2.945 -
2.946 - using GraphWrapper<Graph>::first;
2.947 -// NodeIt& first(NodeIt& i) const {
2.948 -// i=NodeIt(*this); return i;
2.949 -// }
2.950 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.951 - i=OutEdgeIt(*this, p); return i;
2.952 - }
2.953 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.954 - i=InEdgeIt(*this, p); return i;
2.955 - }
2.956 - EdgeIt& first(EdgeIt& i) const {
2.957 - i=EdgeIt(*this); return i;
2.958 - }
2.959 -
2.960 - using GraphWrapper<Graph>::next;
2.961 -// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
2.962 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
2.963 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
2.964 - EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
2.965 -
2.966 - Node aNode(const OutEdgeIt& e) const {
2.967 - return Node(this->graph->aNode(e.e)); }
2.968 - Node aNode(const InEdgeIt& e) const {
2.969 - return Node(this->graph->aNode(e.e)); }
2.970 - Node bNode(const OutEdgeIt& e) const {
2.971 - return Node(this->graph->bNode(e.e)); }
2.972 - Node bNode(const InEdgeIt& e) const {
2.973 - return Node(this->graph->bNode(e.e)); }
2.974 -
2.975 - void erase(const OutEdgeIt& e) const {
2.976 - OutEdgeIt f=e;
2.977 - this->next(f);
2.978 - first_out_edges->set(this->tail(e), f.e);
2.979 - }
2.980 - };
2.981 -
2.982 - ///@}
2.983 -
2.984 -} //namespace hugo
2.985 -
2.986 -
2.987 -#endif //HUGO_GRAPH_WRAPPER_H
2.988 -