1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/graph_wrapper.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,1227 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_GRAPH_WRAPPER_H
1.21 +#define LEMON_GRAPH_WRAPPER_H
1.22 +
1.23 +///\ingroup gwrappers
1.24 +///\file
1.25 +///\brief Several graph wrappers.
1.26 +///
1.27 +///This file contains several useful graph wrapper functions.
1.28 +///
1.29 +///\author Marton Makai
1.30 +
1.31 +#include <lemon/invalid.h>
1.32 +#include <lemon/maps.h>
1.33 +#include <lemon/map_defines.h>
1.34 +#include <iostream>
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 + // Graph wrappers
1.39 +
1.40 + /// \addtogroup gwrappers
1.41 + /// A main parts of LEMON are the different graph structures,
1.42 + /// generic graph algorithms, graph concepts which couple these, and
1.43 + /// graph wrappers. While the previous ones are more or less clear, the
1.44 + /// latter notion needs further explanation.
1.45 + /// Graph wrappers are graph classes which serve for considering graph
1.46 + /// structures in different ways. A short example makes the notion much
1.47 + /// clearer.
1.48 + /// Suppose that we have an instance \c g of a directed graph
1.49 + /// type say \c ListGraph and an algorithm
1.50 + /// \code template<typename Graph> int algorithm(const Graph&); \endcode
1.51 + /// is needed to run on the reversely oriented graph.
1.52 + /// It may be expensive (in time or in memory usage) to copy
1.53 + /// \c g with the reverse orientation.
1.54 + /// Thus, a wrapper class
1.55 + /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.56 + /// The code looks as follows
1.57 + /// \code
1.58 + /// ListGraph g;
1.59 + /// RevGraphWrapper<ListGraph> rgw(g);
1.60 + /// int result=algorithm(rgw);
1.61 + /// \endcode
1.62 + /// After running the algorithm, the original graph \c g
1.63 + /// remains untouched. Thus the graph wrapper used above is to consider the
1.64 + /// original graph with reverse orientation.
1.65 + /// This techniques gives rise to an elegant code, and
1.66 + /// based on stable graph wrappers, complex algorithms can be
1.67 + /// implemented easily.
1.68 + /// In flow, circulation and bipartite matching problems, the residual
1.69 + /// graph is of particular importance. Combining a wrapper implementing
1.70 + /// this, shortest path algorithms and minimum mean cycle algorithms,
1.71 + /// a range of weighted and cardinality optimization algorithms can be
1.72 + /// obtained. For lack of space, for other examples,
1.73 + /// the interested user is referred to the detailed documentation of graph
1.74 + /// wrappers.
1.75 + /// The behavior of graph wrappers can be very different. Some of them keep
1.76 + /// capabilities of the original graph while in other cases this would be
1.77 + /// meaningless. This means that the concepts that they are a model of depend
1.78 + /// on the graph wrapper, and the wrapped graph(s).
1.79 + /// If an edge of \c rgw is deleted, this is carried out by
1.80 + /// deleting the corresponding edge of \c g. But for a residual
1.81 + /// graph, this operation has no sense.
1.82 + /// Let we stand one more example here to simplify your work.
1.83 + /// wrapper class
1.84 + /// \code template<typename Graph> class RevGraphWrapper; \endcode
1.85 + /// has constructor
1.86 + /// <tt> RevGraphWrapper(Graph& _g)</tt>.
1.87 + /// This means that in a situation,
1.88 + /// when a <tt> const ListGraph& </tt> reference to a graph is given,
1.89 + /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
1.90 + /// \code
1.91 + /// int algorithm1(const ListGraph& g) {
1.92 + /// RevGraphWrapper<const ListGraph> rgw(g);
1.93 + /// return algorithm2(rgw);
1.94 + /// }
1.95 + /// \endcode
1.96 +
1.97 + /// \addtogroup gwrappers
1.98 + /// @{
1.99 +
1.100 + ///Base type for the Graph Wrappers
1.101 +
1.102 + ///\warning Graph wrappers are in even more experimental state than the other
1.103 + ///parts of the lib. Use them at you own risk.
1.104 + ///
1.105 + ///This is the base type for the Graph Wrappers.
1.106 + ///\todo Some more docs...
1.107 + ///
1.108 + ///\author Marton Makai
1.109 + template<typename Graph>
1.110 + class GraphWrapper {
1.111 + protected:
1.112 + Graph* graph;
1.113 + GraphWrapper() : graph(0) { }
1.114 + void setGraph(Graph& _graph) { graph=&_graph; }
1.115 +
1.116 + public:
1.117 + typedef Graph BaseGraph;
1.118 + typedef Graph ParentGraph;
1.119 +
1.120 + GraphWrapper(Graph& _graph) : graph(&_graph) { }
1.121 + GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
1.122 +
1.123 + typedef typename Graph::Node Node;
1.124 + class NodeIt : public Node {
1.125 + const GraphWrapper<Graph>* gw;
1.126 + friend class GraphWrapper<Graph>;
1.127 + public:
1.128 + NodeIt() { }
1.129 + NodeIt(Invalid i) : Node(i) { }
1.130 + NodeIt(const GraphWrapper<Graph>& _gw) :
1.131 + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
1.132 + NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
1.133 + Node(n), gw(&_gw) { }
1.134 + NodeIt& operator++() {
1.135 + *(static_cast<Node*>(this))=
1.136 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.137 + return *this;
1.138 + }
1.139 + };
1.140 + typedef typename Graph::Edge Edge;
1.141 + class OutEdgeIt : public Edge {
1.142 + const GraphWrapper<Graph>* gw;
1.143 + friend class GraphWrapper<Graph>;
1.144 + public:
1.145 + OutEdgeIt() { }
1.146 + OutEdgeIt(Invalid i) : Edge(i) { }
1.147 + OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
1.148 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.149 + OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
1.150 + Edge(e), gw(&_gw) { }
1.151 + OutEdgeIt& operator++() {
1.152 + *(static_cast<Edge*>(this))=
1.153 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.154 + return *this;
1.155 + }
1.156 + };
1.157 + class InEdgeIt : public Edge {
1.158 + const GraphWrapper<Graph>* gw;
1.159 + friend class GraphWrapper<Graph>;
1.160 + public:
1.161 + InEdgeIt() { }
1.162 + InEdgeIt(Invalid i) : Edge(i) { }
1.163 + InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
1.164 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.165 + InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
1.166 + Edge(e), gw(&_gw) { }
1.167 + InEdgeIt& operator++() {
1.168 + *(static_cast<Edge*>(this))=
1.169 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.170 + return *this;
1.171 + }
1.172 + };
1.173 + class EdgeIt : public Edge {
1.174 + const GraphWrapper<Graph>* gw;
1.175 + friend class GraphWrapper<Graph>;
1.176 + public:
1.177 + EdgeIt() { }
1.178 + EdgeIt(Invalid i) : Edge(i) { }
1.179 + EdgeIt(const GraphWrapper<Graph>& _gw) :
1.180 + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
1.181 + EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
1.182 + Edge(e), gw(&_gw) { }
1.183 + EdgeIt& operator++() {
1.184 + *(static_cast<Edge*>(this))=
1.185 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.186 + return *this;
1.187 + }
1.188 + };
1.189 +
1.190 + NodeIt& first(NodeIt& i) const {
1.191 + i=NodeIt(*this); return i;
1.192 + }
1.193 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.194 + i=OutEdgeIt(*this, p); return i;
1.195 + }
1.196 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.197 + i=InEdgeIt(*this, p); return i;
1.198 + }
1.199 + EdgeIt& first(EdgeIt& i) const {
1.200 + i=EdgeIt(*this); return i;
1.201 + }
1.202 +
1.203 + Node tail(const Edge& e) const {
1.204 + return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1.205 + Node head(const Edge& e) const {
1.206 + return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1.207 +
1.208 + int nodeNum() const { return graph->nodeNum(); }
1.209 + int edgeNum() const { return graph->edgeNum(); }
1.210 +
1.211 + Node addNode() const { return Node(graph->addNode()); }
1.212 + Edge addEdge(const Node& tail, const Node& head) const {
1.213 + return Edge(graph->addEdge(tail, head)); }
1.214 +
1.215 + void erase(const Node& i) const { graph->erase(i); }
1.216 + void erase(const Edge& i) const { graph->erase(i); }
1.217 +
1.218 + void clear() const { graph->clear(); }
1.219 +
1.220 + bool forward(const Edge& e) const { return graph->forward(e); }
1.221 + bool backward(const Edge& e) const { return graph->backward(e); }
1.222 +
1.223 + int id(const Node& v) const { return graph->id(v); }
1.224 + int id(const Edge& e) const { return graph->id(e); }
1.225 +
1.226 + Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
1.227 +
1.228 +
1.229 + IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
1.230 + IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
1.231 +
1.232 +
1.233 + };
1.234 +
1.235 +
1.236 +
1.237 + /// A graph wrapper which reverses the orientation of the edges.
1.238 +
1.239 + ///\warning Graph wrappers are in even more experimental state than the other
1.240 + ///parts of the lib. Use them at you own risk.
1.241 + ///
1.242 + /// A graph wrapper which reverses the orientation of the edges.
1.243 + /// Thus \c Graph have to be a directed graph type.
1.244 + ///
1.245 + ///\author Marton Makai
1.246 + template<typename Graph>
1.247 + class RevGraphWrapper : public GraphWrapper<Graph> {
1.248 + public:
1.249 + typedef GraphWrapper<Graph> Parent;
1.250 + protected:
1.251 + RevGraphWrapper() : GraphWrapper<Graph>() { }
1.252 + public:
1.253 + RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.254 + RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
1.255 +
1.256 + typedef typename GraphWrapper<Graph>::Node Node;
1.257 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.258 + //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
1.259 + //because this does not work is some of them are not defined in the
1.260 + //original graph. The problem with this is that typedef-ed stuff
1.261 + //are instantiated in c++.
1.262 + class OutEdgeIt : public Edge {
1.263 + const RevGraphWrapper<Graph>* gw;
1.264 + friend class GraphWrapper<Graph>;
1.265 + public:
1.266 + OutEdgeIt() { }
1.267 + OutEdgeIt(Invalid i) : Edge(i) { }
1.268 + OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
1.269 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.270 + OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
1.271 + Edge(e), gw(&_gw) { }
1.272 + OutEdgeIt& operator++() {
1.273 + *(static_cast<Edge*>(this))=
1.274 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.275 + return *this;
1.276 + }
1.277 + };
1.278 + class InEdgeIt : public Edge {
1.279 + const RevGraphWrapper<Graph>* gw;
1.280 + friend class GraphWrapper<Graph>;
1.281 + public:
1.282 + InEdgeIt() { }
1.283 + InEdgeIt(Invalid i) : Edge(i) { }
1.284 + InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
1.285 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.286 + InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
1.287 + Edge(e), gw(&_gw) { }
1.288 + InEdgeIt& operator++() {
1.289 + *(static_cast<Edge*>(this))=
1.290 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.291 + return *this;
1.292 + }
1.293 + };
1.294 +
1.295 + using GraphWrapper<Graph>::first;
1.296 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.297 + i=OutEdgeIt(*this, p); return i;
1.298 + }
1.299 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.300 + i=InEdgeIt(*this, p); return i;
1.301 + }
1.302 +
1.303 + Node tail(const Edge& e) const {
1.304 + return GraphWrapper<Graph>::head(e); }
1.305 + Node head(const Edge& e) const {
1.306 + return GraphWrapper<Graph>::tail(e); }
1.307 +
1.308 + // KEEP_MAPS(Parent, RevGraphWrapper);
1.309 +
1.310 + };
1.311 +
1.312 +
1.313 +
1.314 + /// A graph wrapper for hiding nodes and edges from a graph.
1.315 +
1.316 + ///\warning Graph wrappers are in even more experimental state than the other
1.317 + ///parts of the lib. Use them at you own risk.
1.318 + ///
1.319 + /// This wrapper shows a graph with filtered node-set and
1.320 + /// edge-set. Given a bool-valued map on the node-set and one on
1.321 + /// the edge-set of the graphs, the iterators show only the objects
1.322 + /// having true value.
1.323 + /// The quick brown fox iterators jump over
1.324 + /// the lazy dog nodes or edges if their values for are false in the
1.325 + /// corresponding bool maps.
1.326 + ///
1.327 + ///\author Marton Makai
1.328 + template<typename Graph, typename NodeFilterMap,
1.329 + typename EdgeFilterMap>
1.330 + class SubGraphWrapper : public GraphWrapper<Graph> {
1.331 + public:
1.332 + typedef GraphWrapper<Graph> Parent;
1.333 + protected:
1.334 + NodeFilterMap* node_filter_map;
1.335 + EdgeFilterMap* edge_filter_map;
1.336 +
1.337 + SubGraphWrapper() : GraphWrapper<Graph>(),
1.338 + node_filter_map(0), edge_filter_map(0) { }
1.339 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
1.340 + node_filter_map=&_node_filter_map;
1.341 + }
1.342 + void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
1.343 + edge_filter_map=&_edge_filter_map;
1.344 + }
1.345 +
1.346 + public:
1.347 + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.348 + EdgeFilterMap& _edge_filter_map) :
1.349 + GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.350 + edge_filter_map(&_edge_filter_map) { }
1.351 +
1.352 + typedef typename GraphWrapper<Graph>::Node Node;
1.353 + class NodeIt : public Node {
1.354 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.355 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.356 + public:
1.357 + NodeIt() { }
1.358 + NodeIt(Invalid i) : Node(i) { }
1.359 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.360 + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
1.361 + while (*static_cast<Node*>(this)!=INVALID &&
1.362 + !(*(gw->node_filter_map))[*this])
1.363 + *(static_cast<Node*>(this))=
1.364 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.365 + }
1.366 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.367 + const Node& n) :
1.368 + Node(n), gw(&_gw) { }
1.369 + NodeIt& operator++() {
1.370 + *(static_cast<Node*>(this))=
1.371 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.372 + while (*static_cast<Node*>(this)!=INVALID &&
1.373 + !(*(gw->node_filter_map))[*this])
1.374 + *(static_cast<Node*>(this))=
1.375 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.376 + return *this;
1.377 + }
1.378 + };
1.379 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.380 + class OutEdgeIt : public Edge {
1.381 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.382 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.383 + public:
1.384 + OutEdgeIt() { }
1.385 + OutEdgeIt(Invalid i) : Edge(i) { }
1.386 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.387 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
1.388 + while (*static_cast<Edge*>(this)!=INVALID &&
1.389 + !(*(gw->edge_filter_map))[*this])
1.390 + *(static_cast<Edge*>(this))=
1.391 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.392 + }
1.393 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.394 + const Edge& e) :
1.395 + Edge(e), gw(&_gw) { }
1.396 + OutEdgeIt& operator++() {
1.397 + *(static_cast<Edge*>(this))=
1.398 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.399 + while (*static_cast<Edge*>(this)!=INVALID &&
1.400 + !(*(gw->edge_filter_map))[*this])
1.401 + *(static_cast<Edge*>(this))=
1.402 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.403 + return *this;
1.404 + }
1.405 + };
1.406 + class InEdgeIt : public Edge {
1.407 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.408 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.409 + public:
1.410 + InEdgeIt() { }
1.411 + // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
1.412 + InEdgeIt(Invalid i) : Edge(i) { }
1.413 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.414 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
1.415 + while (*static_cast<Edge*>(this)!=INVALID &&
1.416 + !(*(gw->edge_filter_map))[*this])
1.417 + *(static_cast<Edge*>(this))=
1.418 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.419 + }
1.420 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.421 + const Edge& e) :
1.422 + Edge(e), gw(&_gw) { }
1.423 + InEdgeIt& operator++() {
1.424 + *(static_cast<Edge*>(this))=
1.425 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.426 + while (*static_cast<Edge*>(this)!=INVALID &&
1.427 + !(*(gw->edge_filter_map))[*this])
1.428 + *(static_cast<Edge*>(this))=
1.429 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.430 + return *this;
1.431 + }
1.432 + };
1.433 + class EdgeIt : public Edge {
1.434 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.435 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.436 + public:
1.437 + EdgeIt() { }
1.438 + EdgeIt(Invalid i) : Edge(i) { }
1.439 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.440 + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
1.441 + while (*static_cast<Edge*>(this)!=INVALID &&
1.442 + !(*(gw->edge_filter_map))[*this])
1.443 + *(static_cast<Edge*>(this))=
1.444 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.445 + }
1.446 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.447 + const Edge& e) :
1.448 + Edge(e), gw(&_gw) { }
1.449 + EdgeIt& operator++() {
1.450 + *(static_cast<Edge*>(this))=
1.451 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.452 + while (*static_cast<Edge*>(this)!=INVALID &&
1.453 + !(*(gw->edge_filter_map))[*this])
1.454 + *(static_cast<Edge*>(this))=
1.455 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.456 + return *this;
1.457 + }
1.458 + };
1.459 +
1.460 + NodeIt& first(NodeIt& i) const {
1.461 + i=NodeIt(*this); return i;
1.462 + }
1.463 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.464 + i=OutEdgeIt(*this, p); return i;
1.465 + }
1.466 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.467 + i=InEdgeIt(*this, p); return i;
1.468 + }
1.469 + EdgeIt& first(EdgeIt& i) const {
1.470 + i=EdgeIt(*this); return i;
1.471 + }
1.472 +
1.473 + /// This function hides \c n in the graph, i.e. the iteration
1.474 + /// jumps over it. This is done by simply setting the value of \c n
1.475 + /// to be false in the corresponding node-map.
1.476 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.477 +
1.478 + /// This function hides \c e in the graph, i.e. the iteration
1.479 + /// jumps over it. This is done by simply setting the value of \c e
1.480 + /// to be false in the corresponding edge-map.
1.481 + void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.482 +
1.483 + /// The value of \c n is set to be true in the node-map which stores
1.484 + /// hide information. If \c n was hidden previuosly, then it is shown
1.485 + /// again
1.486 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.487 +
1.488 + /// The value of \c e is set to be true in the edge-map which stores
1.489 + /// hide information. If \c e was hidden previuosly, then it is shown
1.490 + /// again
1.491 + void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.492 +
1.493 + /// Returns true if \c n is hidden.
1.494 + bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.495 +
1.496 + /// Returns true if \c n is hidden.
1.497 + bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.498 +
1.499 + /// \warning This is a linear time operation and works only if
1.500 + /// \c Graph::NodeIt is defined.
1.501 + int nodeNum() const {
1.502 + int i=0;
1.503 + for (NodeIt n(*this); n!=INVALID; ++n) ++i;
1.504 + return i;
1.505 + }
1.506 +
1.507 + /// \warning This is a linear time operation and works only if
1.508 + /// \c Graph::EdgeIt is defined.
1.509 + int edgeNum() const {
1.510 + int i=0;
1.511 + for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1.512 + return i;
1.513 + }
1.514 +
1.515 + // KEEP_MAPS(Parent, SubGraphWrapper);
1.516 + };
1.517 +
1.518 +
1.519 +
1.520 + template<typename Graph>
1.521 + class UndirGraphWrapper : public GraphWrapper<Graph> {
1.522 + public:
1.523 + typedef GraphWrapper<Graph> Parent;
1.524 + protected:
1.525 + UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.526 +
1.527 + public:
1.528 + typedef typename GraphWrapper<Graph>::Node Node;
1.529 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.530 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.531 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.532 +
1.533 + UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
1.534 +
1.535 + class OutEdgeIt {
1.536 + friend class UndirGraphWrapper<Graph>;
1.537 + bool out_or_in; //true iff out
1.538 + typename Graph::OutEdgeIt out;
1.539 + typename Graph::InEdgeIt in;
1.540 + public:
1.541 + OutEdgeIt() { }
1.542 + OutEdgeIt(const Invalid& i) : Edge(i) { }
1.543 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
1.544 + out_or_in=true; _G.graph->first(out, _n);
1.545 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
1.546 + }
1.547 + operator Edge() const {
1.548 + if (out_or_in) return Edge(out); else return Edge(in);
1.549 + }
1.550 + };
1.551 +
1.552 + typedef OutEdgeIt InEdgeIt;
1.553 +
1.554 + using GraphWrapper<Graph>::first;
1.555 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.556 + i=OutEdgeIt(*this, p); return i;
1.557 + }
1.558 +
1.559 + using GraphWrapper<Graph>::next;
1.560 +
1.561 + OutEdgeIt& next(OutEdgeIt& e) const {
1.562 + if (e.out_or_in) {
1.563 + typename Graph::Node n=this->graph->tail(e.out);
1.564 + this->graph->next(e.out);
1.565 + if (!this->graph->valid(e.out)) {
1.566 + e.out_or_in=false; this->graph->first(e.in, n); }
1.567 + } else {
1.568 + this->graph->next(e.in);
1.569 + }
1.570 + return e;
1.571 + }
1.572 +
1.573 + Node aNode(const OutEdgeIt& e) const {
1.574 + if (e.out_or_in) return this->graph->tail(e); else
1.575 + return this->graph->head(e); }
1.576 + Node bNode(const OutEdgeIt& e) const {
1.577 + if (e.out_or_in) return this->graph->head(e); else
1.578 + return this->graph->tail(e); }
1.579 +
1.580 + // KEEP_MAPS(Parent, UndirGraphWrapper);
1.581 +
1.582 + };
1.583 +
1.584 +// /// \brief An undirected graph template.
1.585 +// ///
1.586 +// ///\warning Graph wrappers are in even more experimental state than the other
1.587 +// ///parts of the lib. Use them at your own risk.
1.588 +// ///
1.589 +// /// An undirected graph template.
1.590 +// /// This class works as an undirected graph and a directed graph of
1.591 +// /// class \c Graph is used for the physical storage.
1.592 +// /// \ingroup graphs
1.593 + template<typename Graph>
1.594 + class UndirGraph : public UndirGraphWrapper<Graph> {
1.595 + typedef UndirGraphWrapper<Graph> Parent;
1.596 + protected:
1.597 + Graph gr;
1.598 + public:
1.599 + UndirGraph() : UndirGraphWrapper<Graph>() {
1.600 + Parent::setGraph(gr);
1.601 + }
1.602 +
1.603 + // KEEP_MAPS(Parent, UndirGraph);
1.604 + };
1.605 +
1.606 +
1.607 +
1.608 + ///\brief A wrapper for composing a subgraph of a
1.609 + /// bidirected graph made from a directed one.
1.610 + ///
1.611 + /// A wrapper for composing a subgraph of a
1.612 + /// bidirected graph made from a directed one.
1.613 + ///
1.614 + ///\warning Graph wrappers are in even more experimental state than the other
1.615 + ///parts of the lib. Use them at you own risk.
1.616 + ///
1.617 + /// Suppose that for a directed graph $G=(V, A)$,
1.618 + /// two bool valued maps on the edge-set,
1.619 + /// $forward_filter$, and $backward_filter$
1.620 + /// is given, and we are dealing with the directed graph
1.621 + /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
1.622 + /// The purpose of writing + instead of union is because parallel
1.623 + /// edges can arose.
1.624 + /// In other words, a subgraph of the bidirected graph obtained, which
1.625 + /// is given by orienting the edges of the original graph in both directions.
1.626 + /// An example for such a construction is the \c RevGraphWrapper where the
1.627 + /// forward_filter is everywhere false and the backward_filter is
1.628 + /// everywhere true. We note that for sake of efficiency,
1.629 + /// \c RevGraphWrapper is implemented in a different way.
1.630 + /// But BidirGraphWrapper is obtained from
1.631 + /// SubBidirGraphWrapper by considering everywhere true
1.632 + /// valued maps both for forward_filter and backward_filter.
1.633 + /// Finally, one of the most important applications of SubBidirGraphWrapper
1.634 + /// is ResGraphWrapper, which stands for the residual graph in directed
1.635 + /// flow and circulation problems.
1.636 + /// As wrappers usually, the SubBidirGraphWrapper implements the
1.637 + /// above mentioned graph structure without its physical storage,
1.638 + /// that is the whole stuff eats constant memory.
1.639 + /// As the oppositely directed edges are logically different,
1.640 + /// the maps are able to attach different values for them.
1.641 + template<typename Graph,
1.642 + typename ForwardFilterMap, typename BackwardFilterMap>
1.643 + class SubBidirGraphWrapper : public GraphWrapper<Graph> {
1.644 + public:
1.645 + typedef GraphWrapper<Graph> Parent;
1.646 + protected:
1.647 + ForwardFilterMap* forward_filter;
1.648 + BackwardFilterMap* backward_filter;
1.649 +
1.650 + SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
1.651 + void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
1.652 + forward_filter=&_forward_filter;
1.653 + }
1.654 + void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
1.655 + backward_filter=&_backward_filter;
1.656 + }
1.657 +
1.658 + public:
1.659 +
1.660 + SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
1.661 + BackwardFilterMap& _backward_filter) :
1.662 + GraphWrapper<Graph>(_graph),
1.663 + forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
1.664 + SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
1.665 + ForwardFilterMap, BackwardFilterMap>& gw) :
1.666 + Parent(gw),
1.667 + forward_filter(gw.forward_filter),
1.668 + backward_filter(gw.backward_filter) { }
1.669 +
1.670 + class Edge;
1.671 + class OutEdgeIt;
1.672 + friend class Edge;
1.673 + friend class OutEdgeIt;
1.674 +
1.675 + template<typename T> class EdgeMap;
1.676 +
1.677 + typedef typename GraphWrapper<Graph>::Node Node;
1.678 +
1.679 + typedef typename Graph::Edge GraphEdge;
1.680 + /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
1.681 + /// Graph::Edge. It contains an extra bool flag which is true
1.682 + /// if and only if the
1.683 + /// edge is the backward version of the original edge.
1.684 + class Edge : public Graph::Edge {
1.685 + friend class SubBidirGraphWrapper<Graph,
1.686 + ForwardFilterMap, BackwardFilterMap>;
1.687 + template<typename T> friend class EdgeMap;
1.688 + protected:
1.689 + bool backward; //true, iff backward
1.690 + public:
1.691 + Edge() { }
1.692 + /// \todo =false is needed, or causes problems?
1.693 + /// If \c _backward is false, then we get an edge corresponding to the
1.694 + /// original one, otherwise its oppositely directed pair is obtained.
1.695 + Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
1.696 + Graph::Edge(e), backward(_backward) { }
1.697 + Edge(Invalid i) : Graph::Edge(i), backward(true) { }
1.698 + bool operator==(const Edge& v) const {
1.699 + return (this->backward==v.backward &&
1.700 + static_cast<typename Graph::Edge>(*this)==
1.701 + static_cast<typename Graph::Edge>(v));
1.702 + }
1.703 + bool operator!=(const Edge& v) const {
1.704 + return (this->backward!=v.backward ||
1.705 + static_cast<typename Graph::Edge>(*this)!=
1.706 + static_cast<typename Graph::Edge>(v));
1.707 + }
1.708 + };
1.709 +
1.710 + class OutEdgeIt : public Edge {
1.711 + friend class SubBidirGraphWrapper<Graph,
1.712 + ForwardFilterMap, BackwardFilterMap>;
1.713 + protected:
1.714 + const SubBidirGraphWrapper<Graph,
1.715 + ForwardFilterMap, BackwardFilterMap>* gw;
1.716 + public:
1.717 + OutEdgeIt() { }
1.718 + OutEdgeIt(Invalid i) : Edge(i) { }
1.719 + OutEdgeIt(const SubBidirGraphWrapper<Graph,
1.720 + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
1.721 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
1.722 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.723 + !(*(gw->forward_filter))[*this])
1.724 + *(static_cast<GraphEdge*>(this))=
1.725 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.726 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.727 + *static_cast<Edge*>(this)=
1.728 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
1.729 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.730 + !(*(gw->backward_filter))[*this])
1.731 + *(static_cast<GraphEdge*>(this))=
1.732 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.733 + }
1.734 + }
1.735 + OutEdgeIt(const SubBidirGraphWrapper<Graph,
1.736 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.737 + Edge(e), gw(&_gw) { }
1.738 + OutEdgeIt& operator++() {
1.739 + if (!this->backward) {
1.740 + Node n=gw->tail(*this);
1.741 + *(static_cast<GraphEdge*>(this))=
1.742 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.743 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.744 + !(*(gw->forward_filter))[*this])
1.745 + *(static_cast<GraphEdge*>(this))=
1.746 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.747 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.748 + *static_cast<Edge*>(this)=
1.749 + Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
1.750 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.751 + !(*(gw->backward_filter))[*this])
1.752 + *(static_cast<GraphEdge*>(this))=
1.753 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.754 + }
1.755 + } else {
1.756 + *(static_cast<GraphEdge*>(this))=
1.757 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.758 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.759 + !(*(gw->backward_filter))[*this])
1.760 + *(static_cast<GraphEdge*>(this))=
1.761 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.762 + }
1.763 + return *this;
1.764 + }
1.765 + };
1.766 +
1.767 + class InEdgeIt : public Edge {
1.768 + friend class SubBidirGraphWrapper<Graph,
1.769 + ForwardFilterMap, BackwardFilterMap>;
1.770 + protected:
1.771 + const SubBidirGraphWrapper<Graph,
1.772 + ForwardFilterMap, BackwardFilterMap>* gw;
1.773 + public:
1.774 + InEdgeIt() { }
1.775 + InEdgeIt(Invalid i) : Edge(i) { }
1.776 + InEdgeIt(const SubBidirGraphWrapper<Graph,
1.777 + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
1.778 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
1.779 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.780 + !(*(gw->forward_filter))[*this])
1.781 + *(static_cast<GraphEdge*>(this))=
1.782 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.783 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.784 + *static_cast<Edge*>(this)=
1.785 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
1.786 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.787 + !(*(gw->backward_filter))[*this])
1.788 + *(static_cast<GraphEdge*>(this))=
1.789 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.790 + }
1.791 + }
1.792 + InEdgeIt(const SubBidirGraphWrapper<Graph,
1.793 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.794 + Edge(e), gw(&_gw) { }
1.795 + InEdgeIt& operator++() {
1.796 + if (!this->backward) {
1.797 + Node n=gw->tail(*this);
1.798 + *(static_cast<GraphEdge*>(this))=
1.799 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.800 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.801 + !(*(gw->forward_filter))[*this])
1.802 + *(static_cast<GraphEdge*>(this))=
1.803 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.804 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.805 + *static_cast<Edge*>(this)=
1.806 + Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
1.807 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.808 + !(*(gw->backward_filter))[*this])
1.809 + *(static_cast<GraphEdge*>(this))=
1.810 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.811 + }
1.812 + } else {
1.813 + *(static_cast<GraphEdge*>(this))=
1.814 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.815 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.816 + !(*(gw->backward_filter))[*this])
1.817 + *(static_cast<GraphEdge*>(this))=
1.818 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.819 + }
1.820 + return *this;
1.821 + }
1.822 + };
1.823 +
1.824 + class EdgeIt : public Edge {
1.825 + friend class SubBidirGraphWrapper<Graph,
1.826 + ForwardFilterMap, BackwardFilterMap>;
1.827 + protected:
1.828 + const SubBidirGraphWrapper<Graph,
1.829 + ForwardFilterMap, BackwardFilterMap>* gw;
1.830 + public:
1.831 + EdgeIt() { }
1.832 + EdgeIt(Invalid i) : Edge(i) { }
1.833 + EdgeIt(const SubBidirGraphWrapper<Graph,
1.834 + ForwardFilterMap, BackwardFilterMap>& _gw) :
1.835 + Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1.836 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.837 + !(*(gw->forward_filter))[*this])
1.838 + *(static_cast<GraphEdge*>(this))=
1.839 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.840 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.841 + *static_cast<Edge*>(this)=
1.842 + Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1.843 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.844 + !(*(gw->backward_filter))[*this])
1.845 + *(static_cast<GraphEdge*>(this))=
1.846 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.847 + }
1.848 + }
1.849 + EdgeIt(const SubBidirGraphWrapper<Graph,
1.850 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.851 + Edge(e), gw(&_gw) { }
1.852 + EdgeIt& operator++() {
1.853 + if (!this->backward) {
1.854 + *(static_cast<GraphEdge*>(this))=
1.855 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.856 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.857 + !(*(gw->forward_filter))[*this])
1.858 + *(static_cast<GraphEdge*>(this))=
1.859 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.860 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.861 + *static_cast<Edge*>(this)=
1.862 + Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1.863 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.864 + !(*(gw->backward_filter))[*this])
1.865 + *(static_cast<GraphEdge*>(this))=
1.866 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.867 + }
1.868 + } else {
1.869 + *(static_cast<GraphEdge*>(this))=
1.870 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.871 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.872 + !(*(gw->backward_filter))[*this])
1.873 + *(static_cast<GraphEdge*>(this))=
1.874 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.875 + }
1.876 + return *this;
1.877 + }
1.878 + };
1.879 +
1.880 + using GraphWrapper<Graph>::first;
1.881 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.882 + i=OutEdgeIt(*this, p); return i;
1.883 + }
1.884 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.885 + i=InEdgeIt(*this, p); return i;
1.886 + }
1.887 + EdgeIt& first(EdgeIt& i) const {
1.888 + i=EdgeIt(*this); return i;
1.889 + }
1.890 +
1.891 +
1.892 + Node tail(Edge e) const {
1.893 + return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.894 + Node head(Edge e) const {
1.895 + return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.896 +
1.897 + /// Gives back the opposite edge.
1.898 + Edge opposite(const Edge& e) const {
1.899 + Edge f=e;
1.900 + f.backward=!f.backward;
1.901 + return f;
1.902 + }
1.903 +
1.904 + /// \warning This is a linear time operation and works only if
1.905 + /// \c Graph::EdgeIt is defined.
1.906 + int edgeNum() const {
1.907 + int i=0;
1.908 + for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1.909 + return i;
1.910 + }
1.911 +
1.912 + bool forward(const Edge& e) const { return !e.backward; }
1.913 + bool backward(const Edge& e) const { return e.backward; }
1.914 +
1.915 +
1.916 + template <typename T>
1.917 + /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1.918 + /// Graph::EdgeMap one for the forward edges and
1.919 + /// one for the backward edges.
1.920 + class EdgeMap {
1.921 + template <typename TT> friend class EdgeMap;
1.922 + typename Graph::template EdgeMap<T> forward_map, backward_map;
1.923 + public:
1.924 + typedef T ValueType;
1.925 + typedef Edge KeyType;
1.926 +
1.927 + EdgeMap(const SubBidirGraphWrapper<Graph,
1.928 + ForwardFilterMap, BackwardFilterMap>& g) :
1.929 + forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1.930 +
1.931 + EdgeMap(const SubBidirGraphWrapper<Graph,
1.932 + ForwardFilterMap, BackwardFilterMap>& g, T a) :
1.933 + forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1.934 +
1.935 + template <typename TT>
1.936 + EdgeMap(const EdgeMap<TT>& copy)
1.937 + : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1.938 +
1.939 + template <typename TT>
1.940 + EdgeMap& operator=(const EdgeMap<TT>& copy) {
1.941 + forward_map = copy.forward_map;
1.942 + backward_map = copy.backward_map;
1.943 + return *this;
1.944 + }
1.945 +
1.946 + void set(Edge e, T a) {
1.947 + if (!e.backward)
1.948 + forward_map.set(e, a);
1.949 + else
1.950 + backward_map.set(e, a);
1.951 + }
1.952 +
1.953 + typename Graph::template EdgeMap<T>::ConstReferenceType
1.954 + operator[](Edge e) const {
1.955 + if (!e.backward)
1.956 + return forward_map[e];
1.957 + else
1.958 + return backward_map[e];
1.959 + }
1.960 +
1.961 + typename Graph::template EdgeMap<T>::ReferenceType
1.962 + operator[](Edge e) {
1.963 + if (!e.backward)
1.964 + return forward_map[e];
1.965 + else
1.966 + return backward_map[e];
1.967 + }
1.968 +
1.969 + void update() {
1.970 + forward_map.update();
1.971 + backward_map.update();
1.972 + }
1.973 + };
1.974 +
1.975 +
1.976 + // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1.977 +
1.978 + };
1.979 +
1.980 +
1.981 + ///\brief A wrapper for composing bidirected graph from a directed one.
1.982 + ///
1.983 + ///\warning Graph wrappers are in even more experimental state than the other
1.984 + ///parts of the lib. Use them at you own risk.
1.985 + ///
1.986 + /// A wrapper for composing bidirected graph from a directed one.
1.987 + /// A bidirected graph is composed over the directed one without physical
1.988 + /// storage. As the oppositely directed edges are logically different ones
1.989 + /// the maps are able to attach different values for them.
1.990 + template<typename Graph>
1.991 + class BidirGraphWrapper :
1.992 + public SubBidirGraphWrapper<
1.993 + Graph,
1.994 + ConstMap<typename Graph::Edge, bool>,
1.995 + ConstMap<typename Graph::Edge, bool> > {
1.996 + public:
1.997 + typedef SubBidirGraphWrapper<
1.998 + Graph,
1.999 + ConstMap<typename Graph::Edge, bool>,
1.1000 + ConstMap<typename Graph::Edge, bool> > Parent;
1.1001 + protected:
1.1002 + ConstMap<typename Graph::Edge, bool> cm;
1.1003 +
1.1004 + BidirGraphWrapper() : Parent(), cm(true) {
1.1005 + Parent::setForwardFilterMap(cm);
1.1006 + Parent::setBackwardFilterMap(cm);
1.1007 + }
1.1008 + public:
1.1009 + BidirGraphWrapper(Graph& _graph) : Parent() {
1.1010 + Parent::setGraph(_graph);
1.1011 + Parent::setForwardFilterMap(cm);
1.1012 + Parent::setBackwardFilterMap(cm);
1.1013 + }
1.1014 +
1.1015 + int edgeNum() const {
1.1016 + return 2*this->graph->edgeNum();
1.1017 + }
1.1018 + // KEEP_MAPS(Parent, BidirGraphWrapper);
1.1019 + };
1.1020 +
1.1021 +
1.1022 + /// \brief A bidirected graph template.
1.1023 + ///
1.1024 + ///\warning Graph wrappers are in even more experimental state than the other
1.1025 + ///parts of the lib. Use them at you own risk.
1.1026 + ///
1.1027 + /// A bidirected graph template.
1.1028 + /// Such a bidirected graph stores each pair of oppositely directed edges
1.1029 + /// ones in the memory, i.e. a directed graph of type
1.1030 + /// \c Graph is used for that.
1.1031 + /// As the oppositely directed edges are logically different ones
1.1032 + /// the maps are able to attach different values for them.
1.1033 + /// \ingroup graphs
1.1034 + template<typename Graph>
1.1035 + class BidirGraph : public BidirGraphWrapper<Graph> {
1.1036 + public:
1.1037 + typedef UndirGraphWrapper<Graph> Parent;
1.1038 + protected:
1.1039 + Graph gr;
1.1040 + public:
1.1041 + BidirGraph() : BidirGraphWrapper<Graph>() {
1.1042 + Parent::setGraph(gr);
1.1043 + }
1.1044 + // KEEP_MAPS(Parent, BidirGraph);
1.1045 + };
1.1046 +
1.1047 +
1.1048 +
1.1049 + template<typename Graph, typename Number,
1.1050 + typename CapacityMap, typename FlowMap>
1.1051 + class ResForwardFilter {
1.1052 + // const Graph* graph;
1.1053 + const CapacityMap* capacity;
1.1054 + const FlowMap* flow;
1.1055 + public:
1.1056 + ResForwardFilter(/*const Graph& _graph, */
1.1057 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.1058 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1.1059 + ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1.1060 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1.1061 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
1.1062 + bool operator[](const typename Graph::Edge& e) const {
1.1063 + return (Number((*flow)[e]) < Number((*capacity)[e]));
1.1064 + }
1.1065 + };
1.1066 +
1.1067 + template<typename Graph, typename Number,
1.1068 + typename CapacityMap, typename FlowMap>
1.1069 + class ResBackwardFilter {
1.1070 + const CapacityMap* capacity;
1.1071 + const FlowMap* flow;
1.1072 + public:
1.1073 + ResBackwardFilter(/*const Graph& _graph,*/
1.1074 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.1075 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1.1076 + ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1.1077 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1.1078 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
1.1079 + bool operator[](const typename Graph::Edge& e) const {
1.1080 + return (Number(0) < Number((*flow)[e]));
1.1081 + }
1.1082 + };
1.1083 +
1.1084 +
1.1085 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.1086 +
1.1087 + ///\warning Graph wrappers are in even more experimental state than the other
1.1088 + ///parts of the lib. Use them at you own risk.
1.1089 + ///
1.1090 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.1091 + template<typename Graph, typename Number,
1.1092 + typename CapacityMap, typename FlowMap>
1.1093 + class ResGraphWrapper :
1.1094 + public SubBidirGraphWrapper<
1.1095 + Graph,
1.1096 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.1097 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1.1098 + public:
1.1099 + typedef SubBidirGraphWrapper<
1.1100 + Graph,
1.1101 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.1102 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1.1103 + protected:
1.1104 + const CapacityMap* capacity;
1.1105 + FlowMap* flow;
1.1106 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1.1107 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1.1108 + ResGraphWrapper() : Parent(),
1.1109 + capacity(0), flow(0) { }
1.1110 + void setCapacityMap(const CapacityMap& _capacity) {
1.1111 + capacity=&_capacity;
1.1112 + forward_filter.setCapacity(_capacity);
1.1113 + backward_filter.setCapacity(_capacity);
1.1114 + }
1.1115 + void setFlowMap(FlowMap& _flow) {
1.1116 + flow=&_flow;
1.1117 + forward_filter.setFlow(_flow);
1.1118 + backward_filter.setFlow(_flow);
1.1119 + }
1.1120 + public:
1.1121 + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.1122 + FlowMap& _flow) :
1.1123 + Parent(), capacity(&_capacity), flow(&_flow),
1.1124 + forward_filter(/*_graph,*/ _capacity, _flow),
1.1125 + backward_filter(/*_graph,*/ _capacity, _flow) {
1.1126 + Parent::setGraph(_graph);
1.1127 + Parent::setForwardFilterMap(forward_filter);
1.1128 + Parent::setBackwardFilterMap(backward_filter);
1.1129 + }
1.1130 +
1.1131 + typedef typename Parent::Edge Edge;
1.1132 +
1.1133 + void augment(const Edge& e, Number a) const {
1.1134 + if (Parent::forward(e))
1.1135 + flow->set(e, (*flow)[e]+a);
1.1136 + else
1.1137 + flow->set(e, (*flow)[e]-a);
1.1138 + }
1.1139 +
1.1140 + /// \brief Residual capacity map.
1.1141 + ///
1.1142 + /// In generic residual graphs the residual capacity can be obtained
1.1143 + /// as a map.
1.1144 + class ResCap {
1.1145 + protected:
1.1146 + const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1.1147 + public:
1.1148 + typedef Number ValueType;
1.1149 + typedef Edge KeyType;
1.1150 + ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1.1151 + _res_graph) : res_graph(&_res_graph) { }
1.1152 + Number operator[](const Edge& e) const {
1.1153 + if (res_graph->forward(e))
1.1154 + return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1.1155 + else
1.1156 + return (*(res_graph->flow))[e];
1.1157 + }
1.1158 + };
1.1159 +
1.1160 + // KEEP_MAPS(Parent, ResGraphWrapper);
1.1161 + };
1.1162 +
1.1163 +
1.1164 + /// For blocking flows.
1.1165 +
1.1166 + ///\warning Graph wrappers are in even more experimental state than the other
1.1167 + ///parts of the lib. Use them at you own risk.
1.1168 + ///
1.1169 + /// This graph wrapper is used for on-the-fly
1.1170 + /// Dinits blocking flow computations.
1.1171 + /// For each node, an out-edge is stored which is used when the
1.1172 + /// \code
1.1173 + /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1.1174 + /// \endcode
1.1175 + /// is called.
1.1176 + ///
1.1177 + /// \author Marton Makai
1.1178 + template<typename Graph, typename FirstOutEdgesMap>
1.1179 + class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.1180 + public:
1.1181 + typedef GraphWrapper<Graph> Parent;
1.1182 + protected:
1.1183 + FirstOutEdgesMap* first_out_edges;
1.1184 + public:
1.1185 + ErasingFirstGraphWrapper(Graph& _graph,
1.1186 + FirstOutEdgesMap& _first_out_edges) :
1.1187 + GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.1188 +
1.1189 + typedef typename GraphWrapper<Graph>::Node Node;
1.1190 + typedef typename GraphWrapper<Graph>::Edge Edge;
1.1191 + class OutEdgeIt : public Edge {
1.1192 + friend class GraphWrapper<Graph>;
1.1193 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.1194 + const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1.1195 + public:
1.1196 + OutEdgeIt() { }
1.1197 + OutEdgeIt(Invalid i) : Edge(i) { }
1.1198 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1.1199 + const Node& n) :
1.1200 + Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1.1201 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1.1202 + const Edge& e) :
1.1203 + Edge(e), gw(&_gw) { }
1.1204 + OutEdgeIt& operator++() {
1.1205 + *(static_cast<Edge*>(this))=
1.1206 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.1207 + return *this;
1.1208 + }
1.1209 + };
1.1210 +
1.1211 + using GraphWrapper<Graph>::first;
1.1212 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.1213 + i=OutEdgeIt(*this, p); return i;
1.1214 + }
1.1215 + void erase(const Edge& e) const {
1.1216 + Node n=tail(e);
1.1217 + typename Graph::OutEdgeIt f(*Parent::graph, n);
1.1218 + ++f;
1.1219 + first_out_edges->set(n, f);
1.1220 + }
1.1221 +
1.1222 + // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1.1223 + };
1.1224 +
1.1225 + ///@}
1.1226 +
1.1227 +} //namespace lemon
1.1228 +
1.1229 +#endif //LEMON_GRAPH_WRAPPER_H
1.1230 +