1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/graph_adaptor.h Wed May 04 13:07:10 2005 +0000
1.3 @@ -0,0 +1,1213 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, 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_ADAPTOR_H
1.21 +#define LEMON_GRAPH_ADAPTOR_H
1.22 +
1.23 +///\ingroup graph_adaptors
1.24 +///\file
1.25 +///\brief Several graph adaptors.
1.26 +///
1.27 +///This file contains several useful graph adaptor 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/bits/iterable_graph_extender.h>
1.34 +#include <lemon/bits/undir_graph_extender.h>
1.35 +#include <iostream>
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 + // Graph adaptors
1.40 +
1.41 + /*!
1.42 + \addtogroup graph_adaptors
1.43 + @{
1.44 + */
1.45 +
1.46 + /*!
1.47 + Base type for the Graph Adaptors
1.48 +
1.49 + \warning Graph adaptors are in even more experimental state than the other
1.50 + parts of the lib. Use them at you own risk.
1.51 +
1.52 + This is the base type for most of LEMON graph adaptors.
1.53 + This class implements a trivial graph adaptor i.e. it only wraps the
1.54 + functions and types of the graph. The purpose of this class is to
1.55 + make easier implementing graph adaptors. E.g. if an adaptor is
1.56 + considered which differs from the wrapped graph only in some of its
1.57 + functions or types, then it can be derived from GraphAdaptor, and only the
1.58 + differences should be implemented.
1.59 +
1.60 + \author Marton Makai
1.61 + */
1.62 + template<typename _Graph>
1.63 + class GraphAdaptorBase {
1.64 + public:
1.65 + typedef _Graph Graph;
1.66 + /// \todo Is it needed?
1.67 + typedef Graph BaseGraph;
1.68 + typedef Graph ParentGraph;
1.69 +
1.70 + protected:
1.71 + Graph* graph;
1.72 + GraphAdaptorBase() : graph(0) { }
1.73 + void setGraph(Graph& _graph) { graph=&_graph; }
1.74 +
1.75 + public:
1.76 + GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
1.77 +
1.78 + typedef typename Graph::Node Node;
1.79 + typedef typename Graph::Edge Edge;
1.80 +
1.81 + void first(Node& i) const { graph->first(i); }
1.82 + void first(Edge& i) const { graph->first(i); }
1.83 + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
1.84 + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
1.85 +
1.86 + void next(Node& i) const { graph->next(i); }
1.87 + void next(Edge& i) const { graph->next(i); }
1.88 + void nextIn(Edge& i) const { graph->nextIn(i); }
1.89 + void nextOut(Edge& i) const { graph->nextOut(i); }
1.90 +
1.91 + Node source(const Edge& e) const { return graph->source(e); }
1.92 + Node target(const Edge& e) const { return graph->target(e); }
1.93 +
1.94 + int nodeNum() const { return graph->nodeNum(); }
1.95 + int edgeNum() const { return graph->edgeNum(); }
1.96 +
1.97 + Node addNode() const { return Node(graph->addNode()); }
1.98 + Edge addEdge(const Node& source, const Node& target) const {
1.99 + return Edge(graph->addEdge(source, target)); }
1.100 +
1.101 + void erase(const Node& i) const { graph->erase(i); }
1.102 + void erase(const Edge& i) const { graph->erase(i); }
1.103 +
1.104 + void clear() const { graph->clear(); }
1.105 +
1.106 + bool forward(const Edge& e) const { return graph->forward(e); }
1.107 + bool backward(const Edge& e) const { return graph->backward(e); }
1.108 +
1.109 + int id(const Node& v) const { return graph->id(v); }
1.110 + int id(const Edge& e) const { return graph->id(e); }
1.111 +
1.112 + Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
1.113 +
1.114 + template <typename _Value>
1.115 + class NodeMap : public _Graph::template NodeMap<_Value> {
1.116 + public:
1.117 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.118 + NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
1.119 + NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
1.120 + : Parent(*gw.graph, value) { }
1.121 + };
1.122 +
1.123 + template <typename _Value>
1.124 + class EdgeMap : public _Graph::template EdgeMap<_Value> {
1.125 + public:
1.126 + typedef typename _Graph::template EdgeMap<_Value> Parent;
1.127 + EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
1.128 + EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
1.129 + : Parent(*gw.graph, value) { }
1.130 + };
1.131 +
1.132 + };
1.133 +
1.134 + template <typename _Graph>
1.135 + class GraphAdaptor :
1.136 + public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
1.137 + public:
1.138 + typedef _Graph Graph;
1.139 + typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1.140 + protected:
1.141 + GraphAdaptor() : Parent() { }
1.142 +
1.143 + public:
1.144 + GraphAdaptor(Graph& _graph) { setGraph(_graph); }
1.145 + };
1.146 +
1.147 + template <typename _Graph>
1.148 + class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.149 + public:
1.150 + typedef _Graph Graph;
1.151 + typedef GraphAdaptorBase<_Graph> Parent;
1.152 + protected:
1.153 + RevGraphAdaptorBase() : Parent() { }
1.154 + public:
1.155 + typedef typename Parent::Node Node;
1.156 + typedef typename Parent::Edge Edge;
1.157 +
1.158 + // using Parent::first;
1.159 + void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
1.160 + void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
1.161 +
1.162 + // using Parent::next;
1.163 + void nextIn(Edge& i) const { Parent::nextOut(i); }
1.164 + void nextOut(Edge& i) const { Parent::nextIn(i); }
1.165 +
1.166 + Node source(const Edge& e) const { return Parent::target(e); }
1.167 + Node target(const Edge& e) const { return Parent::source(e); }
1.168 + };
1.169 +
1.170 +
1.171 + /// A graph adaptor which reverses the orientation of the edges.
1.172 +
1.173 + ///\warning Graph adaptors are in even more experimental state than the other
1.174 + ///parts of the lib. Use them at you own risk.
1.175 + ///
1.176 + /// Let \f$G=(V, A)\f$ be a directed graph and
1.177 + /// suppose that a graph instange \c g of type
1.178 + /// \c ListGraph implements \f$G\f$.
1.179 + /// \code
1.180 + /// ListGraph g;
1.181 + /// \endcode
1.182 + /// For each directed edge
1.183 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1.184 + /// reversing its orientation.
1.185 + /// Then RevGraphAdaptor implements the graph structure with node-set
1.186 + /// \f$V\f$ and edge-set
1.187 + /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
1.188 + /// reversing the orientation of its edges. The following code shows how
1.189 + /// such an instance can be constructed.
1.190 + /// \code
1.191 + /// RevGraphAdaptor<ListGraph> gw(g);
1.192 + /// \endcode
1.193 + ///\author Marton Makai
1.194 + template<typename _Graph>
1.195 + class RevGraphAdaptor :
1.196 + public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
1.197 + public:
1.198 + typedef _Graph Graph;
1.199 + typedef IterableGraphExtender<
1.200 + RevGraphAdaptorBase<_Graph> > Parent;
1.201 + protected:
1.202 + RevGraphAdaptor() { }
1.203 + public:
1.204 + RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
1.205 + };
1.206 +
1.207 +
1.208 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.209 + class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.210 + public:
1.211 + typedef _Graph Graph;
1.212 + typedef GraphAdaptorBase<_Graph> Parent;
1.213 + protected:
1.214 + NodeFilterMap* node_filter_map;
1.215 + EdgeFilterMap* edge_filter_map;
1.216 + SubGraphAdaptorBase() : Parent(),
1.217 + node_filter_map(0), edge_filter_map(0) { }
1.218 +
1.219 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
1.220 + node_filter_map=&_node_filter_map;
1.221 + }
1.222 + void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
1.223 + edge_filter_map=&_edge_filter_map;
1.224 + }
1.225 +
1.226 + public:
1.227 +// SubGraphAdaptorBase(Graph& _graph,
1.228 +// NodeFilterMap& _node_filter_map,
1.229 +// EdgeFilterMap& _edge_filter_map) :
1.230 +// Parent(&_graph),
1.231 +// node_filter_map(&node_filter_map),
1.232 +// edge_filter_map(&edge_filter_map) { }
1.233 +
1.234 + typedef typename Parent::Node Node;
1.235 + typedef typename Parent::Edge Edge;
1.236 +
1.237 + void first(Node& i) const {
1.238 + Parent::first(i);
1.239 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.240 + }
1.241 + void first(Edge& i) const {
1.242 + Parent::first(i);
1.243 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
1.244 + }
1.245 + void firstIn(Edge& i, const Node& n) const {
1.246 + Parent::firstIn(i, n);
1.247 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
1.248 + }
1.249 + void firstOut(Edge& i, const Node& n) const {
1.250 + Parent::firstOut(i, n);
1.251 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
1.252 + }
1.253 +
1.254 + void next(Node& i) const {
1.255 + Parent::next(i);
1.256 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.257 + }
1.258 + void next(Edge& i) const {
1.259 + Parent::next(i);
1.260 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
1.261 + }
1.262 + void nextIn(Edge& i) const {
1.263 + Parent::nextIn(i);
1.264 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
1.265 + }
1.266 + void nextOut(Edge& i) const {
1.267 + Parent::nextOut(i);
1.268 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
1.269 + }
1.270 +
1.271 + /// This function hides \c n in the graph, i.e. the iteration
1.272 + /// jumps over it. This is done by simply setting the value of \c n
1.273 + /// to be false in the corresponding node-map.
1.274 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.275 +
1.276 + /// This function hides \c e in the graph, i.e. the iteration
1.277 + /// jumps over it. This is done by simply setting the value of \c e
1.278 + /// to be false in the corresponding edge-map.
1.279 + void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.280 +
1.281 + /// The value of \c n is set to be true in the node-map which stores
1.282 + /// hide information. If \c n was hidden previuosly, then it is shown
1.283 + /// again
1.284 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.285 +
1.286 + /// The value of \c e is set to be true in the edge-map which stores
1.287 + /// hide information. If \c e was hidden previuosly, then it is shown
1.288 + /// again
1.289 + void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.290 +
1.291 + /// Returns true if \c n is hidden.
1.292 + bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.293 +
1.294 + /// Returns true if \c n is hidden.
1.295 + bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.296 +
1.297 + /// \warning This is a linear time operation and works only if s
1.298 + /// \c Graph::NodeIt is defined.
1.299 + /// \todo assign tags.
1.300 + int nodeNum() const {
1.301 + int i=0;
1.302 + Node n;
1.303 + for (first(n); n!=INVALID; next(n)) ++i;
1.304 + return i;
1.305 + }
1.306 +
1.307 + /// \warning This is a linear time operation and works only if
1.308 + /// \c Graph::EdgeIt is defined.
1.309 + /// \todo assign tags.
1.310 + int edgeNum() const {
1.311 + int i=0;
1.312 + Edge e;
1.313 + for (first(e); e!=INVALID; next(e)) ++i;
1.314 + return i;
1.315 + }
1.316 +
1.317 +
1.318 + };
1.319 +
1.320 + /*! \brief A graph adaptor for hiding nodes and edges from a graph.
1.321 +
1.322 + \warning Graph adaptors are in even more experimental state than the other
1.323 + parts of the lib. Use them at you own risk.
1.324 +
1.325 + SubGraphAdaptor shows the graph with filtered node-set and
1.326 + edge-set.
1.327 + Let \f$G=(V, A)\f$ be a directed graph
1.328 + and suppose that the graph instance \c g of type ListGraph implements
1.329 + \f$G\f$.
1.330 + Let moreover \f$b_V\f$ and
1.331 + \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
1.332 + SubGraphAdaptor<...>::NodeIt iterates
1.333 + on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
1.334 + SubGraphAdaptor<...>::EdgeIt iterates
1.335 + on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
1.336 + SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
1.337 + only on edges leaving and entering a specific node which have true value.
1.338 +
1.339 + We have to note that this does not mean that an
1.340 + induced subgraph is obtained, the node-iterator cares only the filter
1.341 + on the node-set, and the edge-iterators care only the filter on the
1.342 + edge-set.
1.343 + \code
1.344 + typedef ListGraph Graph;
1.345 + Graph g;
1.346 + typedef Graph::Node Node;
1.347 + typedef Graph::Edge Edge;
1.348 + Node u=g.addNode(); //node of id 0
1.349 + Node v=g.addNode(); //node of id 1
1.350 + Node e=g.addEdge(u, v); //edge of id 0
1.351 + Node f=g.addEdge(v, u); //edge of id 1
1.352 + Graph::NodeMap<bool> nm(g, true);
1.353 + nm.set(u, false);
1.354 + Graph::EdgeMap<bool> em(g, true);
1.355 + em.set(e, false);
1.356 + typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
1.357 + SubGW gw(g, nm, em);
1.358 + for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
1.359 + std::cout << ":-)" << std::endl;
1.360 + for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
1.361 + \endcode
1.362 + The output of the above code is the following.
1.363 + \code
1.364 + 1
1.365 + :-)
1.366 + 1
1.367 + \endcode
1.368 + Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
1.369 + \c Graph::Node that is why \c g.id(n) can be applied.
1.370 +
1.371 + For other examples see also the documentation of NodeSubGraphAdaptor and
1.372 + EdgeSubGraphAdaptor.
1.373 +
1.374 + \author Marton Makai
1.375 + */
1.376 + template<typename _Graph, typename NodeFilterMap,
1.377 + typename EdgeFilterMap>
1.378 + class SubGraphAdaptor :
1.379 + public IterableGraphExtender<
1.380 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
1.381 + public:
1.382 + typedef _Graph Graph;
1.383 + typedef IterableGraphExtender<
1.384 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.385 + protected:
1.386 + SubGraphAdaptor() { }
1.387 + public:
1.388 + SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
1.389 + EdgeFilterMap& _edge_filter_map) {
1.390 + setGraph(_graph);
1.391 + setNodeFilterMap(_node_filter_map);
1.392 + setEdgeFilterMap(_edge_filter_map);
1.393 + }
1.394 + };
1.395 +
1.396 +
1.397 +
1.398 + /*! \brief An adaptor for hiding nodes from a graph.
1.399 +
1.400 + \warning Graph adaptors are in even more experimental state than the other
1.401 + parts of the lib. Use them at you own risk.
1.402 +
1.403 + An adaptor for hiding nodes from a graph.
1.404 + This adaptor specializes SubGraphAdaptor in the way that only the node-set
1.405 + can be filtered. Note that this does not mean of considering induced
1.406 + subgraph, the edge-iterators consider the original edge-set.
1.407 + \author Marton Makai
1.408 + */
1.409 + template<typename Graph, typename NodeFilterMap>
1.410 + class NodeSubGraphAdaptor :
1.411 + public SubGraphAdaptor<Graph, NodeFilterMap,
1.412 + ConstMap<typename Graph::Edge,bool> > {
1.413 + public:
1.414 + typedef SubGraphAdaptor<Graph, NodeFilterMap,
1.415 + ConstMap<typename Graph::Edge,bool> > Parent;
1.416 + protected:
1.417 + ConstMap<typename Graph::Edge, bool> const_true_map;
1.418 + public:
1.419 + NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
1.420 + Parent(), const_true_map(true) {
1.421 + Parent::setGraph(_graph);
1.422 + Parent::setNodeFilterMap(_node_filter_map);
1.423 + Parent::setEdgeFilterMap(const_true_map);
1.424 + }
1.425 + };
1.426 +
1.427 +
1.428 + /*! \brief An adaptor for hiding edges from a graph.
1.429 +
1.430 + \warning Graph adaptors are in even more experimental state than the other
1.431 + parts of the lib. Use them at you own risk.
1.432 +
1.433 + An adaptor for hiding edges from a graph.
1.434 + This adaptor specializes SubGraphAdaptor in the way that only the edge-set
1.435 + can be filtered. The usefulness of this adaptor is demonstrated in the
1.436 + problem of searching a maximum number of edge-disjoint shortest paths
1.437 + between
1.438 + two nodes \c s and \c t. Shortest here means being shortest w.r.t.
1.439 + non-negative edge-lengths. Note that
1.440 + the comprehension of the presented solution
1.441 + need's some elementary knowledge from combinatorial optimization.
1.442 +
1.443 + If a single shortest path is to be
1.444 + searched between \c s and \c t, then this can be done easily by
1.445 + applying the Dijkstra algorithm. What happens, if a maximum number of
1.446 + edge-disjoint shortest paths is to be computed. It can be proved that an
1.447 + edge can be in a shortest path if and only if it is tight with respect to
1.448 + the potential function computed by Dijkstra. Moreover, any path containing
1.449 + only such edges is a shortest one. Thus we have to compute a maximum number
1.450 + of edge-disjoint paths between \c s and \c t in the graph which has edge-set
1.451 + all the tight edges. The computation will be demonstrated on the following
1.452 + graph, which is read from a dimacs file.
1.453 +
1.454 + \dot
1.455 + digraph lemon_dot_example {
1.456 + node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.457 + n0 [ label="0 (s)" ];
1.458 + n1 [ label="1" ];
1.459 + n2 [ label="2" ];
1.460 + n3 [ label="3" ];
1.461 + n4 [ label="4" ];
1.462 + n5 [ label="5" ];
1.463 + n6 [ label="6 (t)" ];
1.464 + edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.465 + n5 -> n6 [ label="9, length:4" ];
1.466 + n4 -> n6 [ label="8, length:2" ];
1.467 + n3 -> n5 [ label="7, length:1" ];
1.468 + n2 -> n5 [ label="6, length:3" ];
1.469 + n2 -> n6 [ label="5, length:5" ];
1.470 + n2 -> n4 [ label="4, length:2" ];
1.471 + n1 -> n4 [ label="3, length:3" ];
1.472 + n0 -> n3 [ label="2, length:1" ];
1.473 + n0 -> n2 [ label="1, length:2" ];
1.474 + n0 -> n1 [ label="0, length:3" ];
1.475 + }
1.476 + \enddot
1.477 +
1.478 + \code
1.479 + Graph g;
1.480 + Node s, t;
1.481 + LengthMap length(g);
1.482 +
1.483 + readDimacs(std::cin, g, length, s, t);
1.484 +
1.485 + cout << "edges with lengths (of form id, source--length->target): " << endl;
1.486 + for(EdgeIt e(g); e!=INVALID; ++e)
1.487 + cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
1.488 + << length[e] << "->" << g.id(g.target(e)) << endl;
1.489 +
1.490 + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.491 + \endcode
1.492 + Next, the potential function is computed with Dijkstra.
1.493 + \code
1.494 + typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.495 + Dijkstra dijkstra(g, length);
1.496 + dijkstra.run(s);
1.497 + \endcode
1.498 + Next, we consrtruct a map which filters the edge-set to the tight edges.
1.499 + \code
1.500 + typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.501 + TightEdgeFilter;
1.502 + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.503 +
1.504 + typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
1.505 + SubGW gw(g, tight_edge_filter);
1.506 + \endcode
1.507 + Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
1.508 + with a max flow algorithm Preflow.
1.509 + \code
1.510 + ConstMap<Edge, int> const_1_map(1);
1.511 + Graph::EdgeMap<int> flow(g, 0);
1.512 +
1.513 + Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.514 + preflow(gw, s, t, const_1_map, flow);
1.515 + preflow.run();
1.516 + \endcode
1.517 + Last, the output is:
1.518 + \code
1.519 + cout << "maximum number of edge-disjoint shortest path: "
1.520 + << preflow.flowValue() << endl;
1.521 + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.522 + << endl;
1.523 + for(EdgeIt e(g); e!=INVALID; ++e)
1.524 + if (flow[e])
1.525 + cout << " " << g.id(g.source(e)) << "--"
1.526 + << length[e] << "->" << g.id(g.target(e)) << endl;
1.527 + \endcode
1.528 + The program has the following (expected :-)) output:
1.529 + \code
1.530 + edges with lengths (of form id, source--length->target):
1.531 + 9, 5--4->6
1.532 + 8, 4--2->6
1.533 + 7, 3--1->5
1.534 + 6, 2--3->5
1.535 + 5, 2--5->6
1.536 + 4, 2--2->4
1.537 + 3, 1--3->4
1.538 + 2, 0--1->3
1.539 + 1, 0--2->2
1.540 + 0, 0--3->1
1.541 + s: 0 t: 6
1.542 + maximum number of edge-disjoint shortest path: 2
1.543 + edges of the maximum number of edge-disjoint shortest s-t paths:
1.544 + 9, 5--4->6
1.545 + 8, 4--2->6
1.546 + 7, 3--1->5
1.547 + 4, 2--2->4
1.548 + 2, 0--1->3
1.549 + 1, 0--2->2
1.550 + \endcode
1.551 +
1.552 + \author Marton Makai
1.553 + */
1.554 + template<typename Graph, typename EdgeFilterMap>
1.555 + class EdgeSubGraphAdaptor :
1.556 + public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
1.557 + EdgeFilterMap> {
1.558 + public:
1.559 + typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
1.560 + EdgeFilterMap> Parent;
1.561 + protected:
1.562 + ConstMap<typename Graph::Node, bool> const_true_map;
1.563 + public:
1.564 + EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
1.565 + Parent(), const_true_map(true) {
1.566 + Parent::setGraph(_graph);
1.567 + Parent::setNodeFilterMap(const_true_map);
1.568 + Parent::setEdgeFilterMap(_edge_filter_map);
1.569 + }
1.570 + };
1.571 +
1.572 + template <typename _Graph>
1.573 + class UndirGraphAdaptorBase :
1.574 + public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
1.575 + public:
1.576 + typedef _Graph Graph;
1.577 + typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1.578 + protected:
1.579 + UndirGraphAdaptorBase() : Parent() { }
1.580 + public:
1.581 + typedef typename Parent::UndirEdge UndirEdge;
1.582 + typedef typename Parent::Edge Edge;
1.583 +
1.584 + /// \bug Why cant an edge say that it is forward or not???
1.585 + /// By this, a pointer to the graph have to be stored
1.586 + /// The implementation
1.587 + template <typename T>
1.588 + class EdgeMap {
1.589 + protected:
1.590 + const UndirGraphAdaptorBase<_Graph>* g;
1.591 + template <typename TT> friend class EdgeMap;
1.592 + typename _Graph::template EdgeMap<T> forward_map, backward_map;
1.593 + public:
1.594 + typedef T Value;
1.595 + typedef Edge Key;
1.596 +
1.597 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
1.598 + forward_map(*(g->graph)), backward_map(*(g->graph)) { }
1.599 +
1.600 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
1.601 + forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
1.602 +
1.603 + void set(Edge e, T a) {
1.604 + if (g->forward(e))
1.605 + forward_map.set(e, a);
1.606 + else
1.607 + backward_map.set(e, a);
1.608 + }
1.609 +
1.610 + T operator[](Edge e) const {
1.611 + if (g->forward(e))
1.612 + return forward_map[e];
1.613 + else
1.614 + return backward_map[e];
1.615 + }
1.616 + };
1.617 +
1.618 + template <typename T>
1.619 + class UndirEdgeMap {
1.620 + template <typename TT> friend class UndirEdgeMap;
1.621 + typename _Graph::template EdgeMap<T> map;
1.622 + public:
1.623 + typedef T Value;
1.624 + typedef UndirEdge Key;
1.625 +
1.626 + UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
1.627 + map(*(g.graph)) { }
1.628 +
1.629 + UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
1.630 + map(*(g.graph), a) { }
1.631 +
1.632 + void set(UndirEdge e, T a) {
1.633 + map.set(e, a);
1.634 + }
1.635 +
1.636 + T operator[](UndirEdge e) const {
1.637 + return map[e];
1.638 + }
1.639 + };
1.640 +
1.641 + };
1.642 +
1.643 + /// \brief An undirected graph is made from a directed graph by an adaptor
1.644 + ///
1.645 + /// Undocumented, untested!!!
1.646 + /// If somebody knows nice demo application, let's polulate it.
1.647 + ///
1.648 + /// \author Marton Makai
1.649 + template<typename _Graph>
1.650 + class UndirGraphAdaptor :
1.651 + public IterableUndirGraphExtender<
1.652 + UndirGraphAdaptorBase<_Graph> > {
1.653 + public:
1.654 + typedef _Graph Graph;
1.655 + typedef IterableUndirGraphExtender<
1.656 + UndirGraphAdaptorBase<_Graph> > Parent;
1.657 + protected:
1.658 + UndirGraphAdaptor() { }
1.659 + public:
1.660 + UndirGraphAdaptor(_Graph& _graph) {
1.661 + setGraph(_graph);
1.662 + }
1.663 + };
1.664 +
1.665 +
1.666 + template <typename _Graph,
1.667 + typename ForwardFilterMap, typename BackwardFilterMap>
1.668 + class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.669 + public:
1.670 + typedef _Graph Graph;
1.671 + typedef GraphAdaptorBase<_Graph> Parent;
1.672 + protected:
1.673 + ForwardFilterMap* forward_filter;
1.674 + BackwardFilterMap* backward_filter;
1.675 + SubBidirGraphAdaptorBase() : Parent(),
1.676 + forward_filter(0), backward_filter(0) { }
1.677 +
1.678 + void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
1.679 + forward_filter=&_forward_filter;
1.680 + }
1.681 + void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
1.682 + backward_filter=&_backward_filter;
1.683 + }
1.684 +
1.685 + public:
1.686 +// SubGraphAdaptorBase(Graph& _graph,
1.687 +// NodeFilterMap& _node_filter_map,
1.688 +// EdgeFilterMap& _edge_filter_map) :
1.689 +// Parent(&_graph),
1.690 +// node_filter_map(&node_filter_map),
1.691 +// edge_filter_map(&edge_filter_map) { }
1.692 +
1.693 + typedef typename Parent::Node Node;
1.694 + typedef typename _Graph::Edge GraphEdge;
1.695 + template <typename T> class EdgeMap;
1.696 + /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
1.697 + /// _Graph::Edge. It contains an extra bool flag which is true
1.698 + /// if and only if the
1.699 + /// edge is the backward version of the original edge.
1.700 + class Edge : public _Graph::Edge {
1.701 + friend class SubBidirGraphAdaptorBase<
1.702 + Graph, ForwardFilterMap, BackwardFilterMap>;
1.703 + template<typename T> friend class EdgeMap;
1.704 + protected:
1.705 + bool backward; //true, iff backward
1.706 + public:
1.707 + Edge() { }
1.708 + /// \todo =false is needed, or causes problems?
1.709 + /// If \c _backward is false, then we get an edge corresponding to the
1.710 + /// original one, otherwise its oppositely directed pair is obtained.
1.711 + Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
1.712 + _Graph::Edge(e), backward(_backward) { }
1.713 + Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
1.714 + bool operator==(const Edge& v) const {
1.715 + return (this->backward==v.backward &&
1.716 + static_cast<typename _Graph::Edge>(*this)==
1.717 + static_cast<typename _Graph::Edge>(v));
1.718 + }
1.719 + bool operator!=(const Edge& v) const {
1.720 + return (this->backward!=v.backward ||
1.721 + static_cast<typename _Graph::Edge>(*this)!=
1.722 + static_cast<typename _Graph::Edge>(v));
1.723 + }
1.724 + };
1.725 +
1.726 + void first(Node& i) const {
1.727 + Parent::first(i);
1.728 + }
1.729 +
1.730 + void first(Edge& i) const {
1.731 + Parent::first(i);
1.732 + i.backward=false;
1.733 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.734 + !(*forward_filter)[i]) Parent::next(i);
1.735 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.736 + Parent::first(i);
1.737 + i.backward=true;
1.738 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.739 + !(*backward_filter)[i]) Parent::next(i);
1.740 + }
1.741 + }
1.742 +
1.743 + void firstIn(Edge& i, const Node& n) const {
1.744 + Parent::firstIn(i, n);
1.745 + i.backward=false;
1.746 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.747 + !(*forward_filter)[i]) Parent::nextIn(i);
1.748 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.749 + Parent::firstOut(i, n);
1.750 + i.backward=true;
1.751 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.752 + !(*backward_filter)[i]) Parent::nextOut(i);
1.753 + }
1.754 + }
1.755 +
1.756 + void firstOut(Edge& i, const Node& n) const {
1.757 + Parent::firstOut(i, n);
1.758 + i.backward=false;
1.759 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.760 + !(*forward_filter)[i]) Parent::nextOut(i);
1.761 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.762 + Parent::firstIn(i, n);
1.763 + i.backward=true;
1.764 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.765 + !(*backward_filter)[i]) Parent::nextIn(i);
1.766 + }
1.767 + }
1.768 +
1.769 + void next(Node& i) const {
1.770 + Parent::next(i);
1.771 + }
1.772 +
1.773 + void next(Edge& i) const {
1.774 + if (!(i.backward)) {
1.775 + Parent::next(i);
1.776 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.777 + !(*forward_filter)[i]) Parent::next(i);
1.778 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.779 + Parent::first(i);
1.780 + i.backward=true;
1.781 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.782 + !(*backward_filter)[i]) Parent::next(i);
1.783 + }
1.784 + } else {
1.785 + Parent::next(i);
1.786 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.787 + !(*backward_filter)[i]) Parent::next(i);
1.788 + }
1.789 + }
1.790 +
1.791 + void nextIn(Edge& i) const {
1.792 + if (!(i.backward)) {
1.793 + Node n=Parent::target(i);
1.794 + Parent::nextIn(i);
1.795 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.796 + !(*forward_filter)[i]) Parent::nextIn(i);
1.797 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.798 + Parent::firstOut(i, n);
1.799 + i.backward=true;
1.800 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.801 + !(*backward_filter)[i]) Parent::nextOut(i);
1.802 + }
1.803 + } else {
1.804 + Parent::nextOut(i);
1.805 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.806 + !(*backward_filter)[i]) Parent::nextOut(i);
1.807 + }
1.808 + }
1.809 +
1.810 + void nextOut(Edge& i) const {
1.811 + if (!(i.backward)) {
1.812 + Node n=Parent::source(i);
1.813 + Parent::nextOut(i);
1.814 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.815 + !(*forward_filter)[i]) Parent::nextOut(i);
1.816 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
1.817 + Parent::firstIn(i, n);
1.818 + i.backward=true;
1.819 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.820 + !(*backward_filter)[i]) Parent::nextIn(i);
1.821 + }
1.822 + } else {
1.823 + Parent::nextIn(i);
1.824 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
1.825 + !(*backward_filter)[i]) Parent::nextIn(i);
1.826 + }
1.827 + }
1.828 +
1.829 + Node source(Edge e) const {
1.830 + return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
1.831 + Node target(Edge e) const {
1.832 + return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
1.833 +
1.834 + /// Gives back the opposite edge.
1.835 + Edge opposite(const Edge& e) const {
1.836 + Edge f=e;
1.837 + f.backward=!f.backward;
1.838 + return f;
1.839 + }
1.840 +
1.841 + /// \warning This is a linear time operation and works only if
1.842 + /// \c Graph::EdgeIt is defined.
1.843 + /// \todo hmm
1.844 + int edgeNum() const {
1.845 + int i=0;
1.846 + Edge e;
1.847 + for (first(e); e!=INVALID; next(e)) ++i;
1.848 + return i;
1.849 + }
1.850 +
1.851 + bool forward(const Edge& e) const { return !e.backward; }
1.852 + bool backward(const Edge& e) const { return e.backward; }
1.853 +
1.854 + template <typename T>
1.855 + /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
1.856 + /// _Graph::EdgeMap one for the forward edges and
1.857 + /// one for the backward edges.
1.858 + class EdgeMap {
1.859 + template <typename TT> friend class EdgeMap;
1.860 + typename _Graph::template EdgeMap<T> forward_map, backward_map;
1.861 + public:
1.862 + typedef T Value;
1.863 + typedef Edge Key;
1.864 +
1.865 + EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1.866 + ForwardFilterMap, BackwardFilterMap>& g) :
1.867 + forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1.868 +
1.869 + EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1.870 + ForwardFilterMap, BackwardFilterMap>& g, T a) :
1.871 + forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1.872 +
1.873 + void set(Edge e, T a) {
1.874 + if (!e.backward)
1.875 + forward_map.set(e, a);
1.876 + else
1.877 + backward_map.set(e, a);
1.878 + }
1.879 +
1.880 +// typename _Graph::template EdgeMap<T>::ConstReference
1.881 +// operator[](Edge e) const {
1.882 +// if (!e.backward)
1.883 +// return forward_map[e];
1.884 +// else
1.885 +// return backward_map[e];
1.886 +// }
1.887 +
1.888 +// typename _Graph::template EdgeMap<T>::Reference
1.889 + T operator[](Edge e) const {
1.890 + if (!e.backward)
1.891 + return forward_map[e];
1.892 + else
1.893 + return backward_map[e];
1.894 + }
1.895 +
1.896 + void update() {
1.897 + forward_map.update();
1.898 + backward_map.update();
1.899 + }
1.900 + };
1.901 +
1.902 + };
1.903 +
1.904 +
1.905 + ///\brief An adaptor for composing a subgraph of a
1.906 + /// bidirected graph made from a directed one.
1.907 + ///
1.908 + /// An adaptor for composing a subgraph of a
1.909 + /// bidirected graph made from a directed one.
1.910 + ///
1.911 + ///\warning Graph adaptors are in even more experimental state than the other
1.912 + ///parts of the lib. Use them at you own risk.
1.913 + ///
1.914 + /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1.915 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1.916 + /// reversing its orientation. We are given moreover two bool valued
1.917 + /// maps on the edge-set,
1.918 + /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1.919 + /// SubBidirGraphAdaptor implements the graph structure with node-set
1.920 + /// \f$V\f$ and edge-set
1.921 + /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
1.922 + /// The purpose of writing + instead of union is because parallel
1.923 + /// edges can arise. (Similarly, antiparallel edges also can arise).
1.924 + /// In other words, a subgraph of the bidirected graph obtained, which
1.925 + /// is given by orienting the edges of the original graph in both directions.
1.926 + /// As the oppositely directed edges are logically different,
1.927 + /// the maps are able to attach different values for them.
1.928 + ///
1.929 + /// An example for such a construction is \c RevGraphAdaptor where the
1.930 + /// forward_filter is everywhere false and the backward_filter is
1.931 + /// everywhere true. We note that for sake of efficiency,
1.932 + /// \c RevGraphAdaptor is implemented in a different way.
1.933 + /// But BidirGraphAdaptor is obtained from
1.934 + /// SubBidirGraphAdaptor by considering everywhere true
1.935 + /// valued maps both for forward_filter and backward_filter.
1.936 + ///
1.937 + /// The most important application of SubBidirGraphAdaptor
1.938 + /// is ResGraphAdaptor, which stands for the residual graph in directed
1.939 + /// flow and circulation problems.
1.940 + /// As adaptors usually, the SubBidirGraphAdaptor implements the
1.941 + /// above mentioned graph structure without its physical storage,
1.942 + /// that is the whole stuff is stored in constant memory.
1.943 + template<typename _Graph,
1.944 + typename ForwardFilterMap, typename BackwardFilterMap>
1.945 + class SubBidirGraphAdaptor :
1.946 + public IterableGraphExtender<
1.947 + SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1.948 + public:
1.949 + typedef _Graph Graph;
1.950 + typedef IterableGraphExtender<
1.951 + SubBidirGraphAdaptorBase<
1.952 + _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1.953 + protected:
1.954 + SubBidirGraphAdaptor() { }
1.955 + public:
1.956 + SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1.957 + BackwardFilterMap& _backward_filter) {
1.958 + setGraph(_graph);
1.959 + setForwardFilterMap(_forward_filter);
1.960 + setBackwardFilterMap(_backward_filter);
1.961 + }
1.962 + };
1.963 +
1.964 +
1.965 +
1.966 + ///\brief An adaptor for composing bidirected graph from a directed one.
1.967 + ///
1.968 + ///\warning Graph adaptors are in even more experimental state than the other
1.969 + ///parts of the lib. Use them at you own risk.
1.970 + ///
1.971 + /// An adaptor for composing bidirected graph from a directed one.
1.972 + /// A bidirected graph is composed over the directed one without physical
1.973 + /// storage. As the oppositely directed edges are logically different ones
1.974 + /// the maps are able to attach different values for them.
1.975 + template<typename Graph>
1.976 + class BidirGraphAdaptor :
1.977 + public SubBidirGraphAdaptor<
1.978 + Graph,
1.979 + ConstMap<typename Graph::Edge, bool>,
1.980 + ConstMap<typename Graph::Edge, bool> > {
1.981 + public:
1.982 + typedef SubBidirGraphAdaptor<
1.983 + Graph,
1.984 + ConstMap<typename Graph::Edge, bool>,
1.985 + ConstMap<typename Graph::Edge, bool> > Parent;
1.986 + protected:
1.987 + ConstMap<typename Graph::Edge, bool> cm;
1.988 +
1.989 + BidirGraphAdaptor() : Parent(), cm(true) {
1.990 + Parent::setForwardFilterMap(cm);
1.991 + Parent::setBackwardFilterMap(cm);
1.992 + }
1.993 + public:
1.994 + BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1.995 + Parent::setGraph(_graph);
1.996 + Parent::setForwardFilterMap(cm);
1.997 + Parent::setBackwardFilterMap(cm);
1.998 + }
1.999 +
1.1000 + int edgeNum() const {
1.1001 + return 2*this->graph->edgeNum();
1.1002 + }
1.1003 + // KEEP_MAPS(Parent, BidirGraphAdaptor);
1.1004 + };
1.1005 +
1.1006 +
1.1007 + template<typename Graph, typename Number,
1.1008 + typename CapacityMap, typename FlowMap>
1.1009 + class ResForwardFilter {
1.1010 + // const Graph* graph;
1.1011 + const CapacityMap* capacity;
1.1012 + const FlowMap* flow;
1.1013 + public:
1.1014 + ResForwardFilter(/*const Graph& _graph, */
1.1015 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.1016 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1.1017 + ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1.1018 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1.1019 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
1.1020 + bool operator[](const typename Graph::Edge& e) const {
1.1021 + return (Number((*flow)[e]) < Number((*capacity)[e]));
1.1022 + }
1.1023 + };
1.1024 +
1.1025 + template<typename Graph, typename Number,
1.1026 + typename CapacityMap, typename FlowMap>
1.1027 + class ResBackwardFilter {
1.1028 + const CapacityMap* capacity;
1.1029 + const FlowMap* flow;
1.1030 + public:
1.1031 + ResBackwardFilter(/*const Graph& _graph,*/
1.1032 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.1033 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1.1034 + ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1.1035 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1.1036 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
1.1037 + bool operator[](const typename Graph::Edge& e) const {
1.1038 + return (Number(0) < Number((*flow)[e]));
1.1039 + }
1.1040 + };
1.1041 +
1.1042 +
1.1043 + /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1.1044 +
1.1045 + An adaptor for composing the residual graph for directed flow and circulation problems.
1.1046 + Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1.1047 + number type. Let moreover
1.1048 + \f$f,c:A\to F\f$, be functions on the edge-set.
1.1049 + In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1.1050 + and \f$c\f$ for a capacity function.
1.1051 + Suppose that a graph instange \c g of type
1.1052 + \c ListGraph implements \f$G\f$.
1.1053 + \code
1.1054 + ListGraph g;
1.1055 + \endcode
1.1056 + Then RevGraphAdaptor implements the graph structure with node-set
1.1057 + \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1.1058 + \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1.1059 + \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1.1060 + i.e. the so called residual graph.
1.1061 + When we take the union \f$A_{forward}\cup A_{backward}\f$,
1.1062 + multilicities are counted, i.e. if an edge is in both
1.1063 + \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1.1064 + appears twice.
1.1065 + The following code shows how
1.1066 + such an instance can be constructed.
1.1067 + \code
1.1068 + typedef ListGraph Graph;
1.1069 + Graph::EdgeMap<int> f(g);
1.1070 + Graph::EdgeMap<int> c(g);
1.1071 + ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1.1072 + \endcode
1.1073 + \author Marton Makai
1.1074 + */
1.1075 + template<typename Graph, typename Number,
1.1076 + typename CapacityMap, typename FlowMap>
1.1077 + class ResGraphAdaptor :
1.1078 + public SubBidirGraphAdaptor<
1.1079 + Graph,
1.1080 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.1081 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1.1082 + public:
1.1083 + typedef SubBidirGraphAdaptor<
1.1084 + Graph,
1.1085 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.1086 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1.1087 + protected:
1.1088 + const CapacityMap* capacity;
1.1089 + FlowMap* flow;
1.1090 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1.1091 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1.1092 + ResGraphAdaptor() : Parent(),
1.1093 + capacity(0), flow(0) { }
1.1094 + void setCapacityMap(const CapacityMap& _capacity) {
1.1095 + capacity=&_capacity;
1.1096 + forward_filter.setCapacity(_capacity);
1.1097 + backward_filter.setCapacity(_capacity);
1.1098 + }
1.1099 + void setFlowMap(FlowMap& _flow) {
1.1100 + flow=&_flow;
1.1101 + forward_filter.setFlow(_flow);
1.1102 + backward_filter.setFlow(_flow);
1.1103 + }
1.1104 + public:
1.1105 + ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1.1106 + FlowMap& _flow) :
1.1107 + Parent(), capacity(&_capacity), flow(&_flow),
1.1108 + forward_filter(/*_graph,*/ _capacity, _flow),
1.1109 + backward_filter(/*_graph,*/ _capacity, _flow) {
1.1110 + Parent::setGraph(_graph);
1.1111 + Parent::setForwardFilterMap(forward_filter);
1.1112 + Parent::setBackwardFilterMap(backward_filter);
1.1113 + }
1.1114 +
1.1115 + typedef typename Parent::Edge Edge;
1.1116 +
1.1117 + void augment(const Edge& e, Number a) const {
1.1118 + if (Parent::forward(e))
1.1119 + flow->set(e, (*flow)[e]+a);
1.1120 + else
1.1121 + flow->set(e, (*flow)[e]-a);
1.1122 + }
1.1123 +
1.1124 + /// \brief Residual capacity map.
1.1125 + ///
1.1126 + /// In generic residual graphs the residual capacity can be obtained
1.1127 + /// as a map.
1.1128 + class ResCap {
1.1129 + protected:
1.1130 + const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1.1131 + public:
1.1132 + typedef Number Value;
1.1133 + typedef Edge Key;
1.1134 + ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1.1135 + _res_graph) : res_graph(&_res_graph) { }
1.1136 + Number operator[](const Edge& e) const {
1.1137 + if (res_graph->forward(e))
1.1138 + return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1.1139 + else
1.1140 + return (*(res_graph->flow))[e];
1.1141 + }
1.1142 + };
1.1143 +
1.1144 + // KEEP_MAPS(Parent, ResGraphAdaptor);
1.1145 + };
1.1146 +
1.1147 +
1.1148 +
1.1149 + template <typename _Graph, typename FirstOutEdgesMap>
1.1150 + class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.1151 + public:
1.1152 + typedef _Graph Graph;
1.1153 + typedef GraphAdaptorBase<_Graph> Parent;
1.1154 + protected:
1.1155 + FirstOutEdgesMap* first_out_edges;
1.1156 + ErasingFirstGraphAdaptorBase() : Parent(),
1.1157 + first_out_edges(0) { }
1.1158 +
1.1159 + void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1.1160 + first_out_edges=&_first_out_edges;
1.1161 + }
1.1162 +
1.1163 + public:
1.1164 +
1.1165 + typedef typename Parent::Node Node;
1.1166 + typedef typename Parent::Edge Edge;
1.1167 +
1.1168 + void firstOut(Edge& i, const Node& n) const {
1.1169 + i=(*first_out_edges)[n];
1.1170 + }
1.1171 +
1.1172 + void erase(const Edge& e) const {
1.1173 + Node n=source(e);
1.1174 + Edge f=e;
1.1175 + Parent::nextOut(f);
1.1176 + first_out_edges->set(n, f);
1.1177 + }
1.1178 + };
1.1179 +
1.1180 +
1.1181 + /// For blocking flows.
1.1182 +
1.1183 + ///\warning Graph adaptors are in even more experimental state than the other
1.1184 + ///parts of the lib. Use them at you own risk.
1.1185 + ///
1.1186 + /// This graph adaptor is used for on-the-fly
1.1187 + /// Dinits blocking flow computations.
1.1188 + /// For each node, an out-edge is stored which is used when the
1.1189 + /// \code
1.1190 + /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1.1191 + /// \endcode
1.1192 + /// is called.
1.1193 + ///
1.1194 + /// \author Marton Makai
1.1195 + template <typename _Graph, typename FirstOutEdgesMap>
1.1196 + class ErasingFirstGraphAdaptor :
1.1197 + public IterableGraphExtender<
1.1198 + ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1.1199 + public:
1.1200 + typedef _Graph Graph;
1.1201 + typedef IterableGraphExtender<
1.1202 + ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1.1203 + ErasingFirstGraphAdaptor(Graph& _graph,
1.1204 + FirstOutEdgesMap& _first_out_edges) {
1.1205 + setGraph(_graph);
1.1206 + setFirstOutEdgesMap(_first_out_edges);
1.1207 + }
1.1208 +
1.1209 + };
1.1210 +
1.1211 + ///@}
1.1212 +
1.1213 +} //namespace lemon
1.1214 +
1.1215 +#endif //LEMON_GRAPH_ADAPTOR_H
1.1216 +