1.1 --- a/src/lemon/graph_wrapper.h Mon May 02 05:49:33 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1213 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/graph_wrapper.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_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/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 wrappers
1.40 -
1.41 - /*!
1.42 - \addtogroup gwrappers
1.43 - @{
1.44 - */
1.45 -
1.46 - /*!
1.47 - Base type for the Graph Wrappers
1.48 -
1.49 - \warning Graph wrappers 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 wrappers.
1.53 - This class implements a trivial graph wrapper 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 wrappers. E.g. if a wrapper 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 GraphWrapper, 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 GraphWrapperBase {
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 - GraphWrapperBase() : graph(0) { }
1.73 - void setGraph(Graph& _graph) { graph=&_graph; }
1.74 -
1.75 - public:
1.76 - GraphWrapperBase(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 GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
1.119 - NodeMap(const GraphWrapperBase<_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 GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
1.128 - EdgeMap(const GraphWrapperBase<_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 GraphWrapper :
1.136 - public IterableGraphExtender<GraphWrapperBase<_Graph> > {
1.137 - public:
1.138 - typedef _Graph Graph;
1.139 - typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
1.140 - protected:
1.141 - GraphWrapper() : Parent() { }
1.142 -
1.143 - public:
1.144 - GraphWrapper(Graph& _graph) { setGraph(_graph); }
1.145 - };
1.146 -
1.147 - template <typename _Graph>
1.148 - class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
1.149 - public:
1.150 - typedef _Graph Graph;
1.151 - typedef GraphWrapperBase<_Graph> Parent;
1.152 - protected:
1.153 - RevGraphWrapperBase() : 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 wrapper which reverses the orientation of the edges.
1.172 -
1.173 - ///\warning Graph wrappers 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 RevGraphWrapper 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 - /// RevGraphWrapper<ListGraph> gw(g);
1.192 - /// \endcode
1.193 - ///\author Marton Makai
1.194 - template<typename _Graph>
1.195 - class RevGraphWrapper :
1.196 - public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
1.197 - public:
1.198 - typedef _Graph Graph;
1.199 - typedef IterableGraphExtender<
1.200 - RevGraphWrapperBase<_Graph> > Parent;
1.201 - protected:
1.202 - RevGraphWrapper() { }
1.203 - public:
1.204 - RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
1.205 - };
1.206 -
1.207 -
1.208 - template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.209 - class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
1.210 - public:
1.211 - typedef _Graph Graph;
1.212 - typedef GraphWrapperBase<_Graph> Parent;
1.213 - protected:
1.214 - NodeFilterMap* node_filter_map;
1.215 - EdgeFilterMap* edge_filter_map;
1.216 - SubGraphWrapperBase() : 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 -// SubGraphWrapperBase(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 wrapper for hiding nodes and edges from a graph.
1.321 -
1.322 - \warning Graph wrappers 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 - SubGraphWrapper 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 - SubGraphWrapper<...>::NodeIt iterates
1.333 - on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
1.334 - SubGraphWrapper<...>::EdgeIt iterates
1.335 - on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
1.336 - SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::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 SubGraphWrapper<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 NodeSubGraphWrapper and
1.372 - EdgeSubGraphWrapper.
1.373 -
1.374 - \author Marton Makai
1.375 - */
1.376 - template<typename _Graph, typename NodeFilterMap,
1.377 - typename EdgeFilterMap>
1.378 - class SubGraphWrapper :
1.379 - public IterableGraphExtender<
1.380 - SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
1.381 - public:
1.382 - typedef _Graph Graph;
1.383 - typedef IterableGraphExtender<
1.384 - SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.385 - protected:
1.386 - SubGraphWrapper() { }
1.387 - public:
1.388 - SubGraphWrapper(_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 A wrapper for hiding nodes from a graph.
1.399 -
1.400 - \warning Graph wrappers 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 - A wrapper for hiding nodes from a graph.
1.404 - This wrapper specializes SubGraphWrapper 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 NodeSubGraphWrapper :
1.411 - public SubGraphWrapper<Graph, NodeFilterMap,
1.412 - ConstMap<typename Graph::Edge,bool> > {
1.413 - public:
1.414 - typedef SubGraphWrapper<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 - NodeSubGraphWrapper(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 A wrapper for hiding edges from a graph.
1.429 -
1.430 - \warning Graph wrappers 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 - A wrapper for hiding edges from a graph.
1.434 - This wrapper specializes SubGraphWrapper in the way that only the edge-set
1.435 - can be filtered. The usefulness of this wrapper 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 EdgeSubGraphWrapper<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 EdgeSubGraphWrapper :
1.556 - public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
1.557 - EdgeFilterMap> {
1.558 - public:
1.559 - typedef SubGraphWrapper<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 - EdgeSubGraphWrapper(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 UndirGraphWrapperBase :
1.574 - public UndirGraphExtender<GraphWrapperBase<_Graph> > {
1.575 - public:
1.576 - typedef _Graph Graph;
1.577 - typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
1.578 - protected:
1.579 - UndirGraphWrapperBase() : 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 UndirGraphWrapperBase<_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 UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
1.598 - forward_map(*(g->graph)), backward_map(*(g->graph)) { }
1.599 -
1.600 - EdgeMap(const UndirGraphWrapperBase<_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 UndirGraphWrapperBase<_Graph>& g) :
1.627 - map(*(g.graph)) { }
1.628 -
1.629 - UndirEdgeMap(const UndirGraphWrapperBase<_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 a wrapper
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 UndirGraphWrapper :
1.651 - public IterableUndirGraphExtender<
1.652 - UndirGraphWrapperBase<_Graph> > {
1.653 - public:
1.654 - typedef _Graph Graph;
1.655 - typedef IterableUndirGraphExtender<
1.656 - UndirGraphWrapperBase<_Graph> > Parent;
1.657 - protected:
1.658 - UndirGraphWrapper() { }
1.659 - public:
1.660 - UndirGraphWrapper(_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 SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
1.669 - public:
1.670 - typedef _Graph Graph;
1.671 - typedef GraphWrapperBase<_Graph> Parent;
1.672 - protected:
1.673 - ForwardFilterMap* forward_filter;
1.674 - BackwardFilterMap* backward_filter;
1.675 - SubBidirGraphWrapperBase() : 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 -// SubGraphWrapperBase(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 - /// SubBidirGraphWrapperBase<..., ..., ...>::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 SubBidirGraphWrapperBase<
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 SubBidirGraphWrapperBase<..., ..., ...>::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 SubBidirGraphWrapperBase<_Graph,
1.866 - ForwardFilterMap, BackwardFilterMap>& g) :
1.867 - forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1.868 -
1.869 - EdgeMap(const SubBidirGraphWrapperBase<_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 A wrapper for composing a subgraph of a
1.906 - /// bidirected graph made from a directed one.
1.907 - ///
1.908 - /// A wrapper for composing a subgraph of a
1.909 - /// bidirected graph made from a directed one.
1.910 - ///
1.911 - ///\warning Graph wrappers 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 - /// SubBidirGraphWrapper 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 RevGraphWrapper 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 RevGraphWrapper is implemented in a different way.
1.933 - /// But BidirGraphWrapper is obtained from
1.934 - /// SubBidirGraphWrapper by considering everywhere true
1.935 - /// valued maps both for forward_filter and backward_filter.
1.936 - ///
1.937 - /// The most important application of SubBidirGraphWrapper
1.938 - /// is ResGraphWrapper, which stands for the residual graph in directed
1.939 - /// flow and circulation problems.
1.940 - /// As wrappers usually, the SubBidirGraphWrapper 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 SubBidirGraphWrapper :
1.946 - public IterableGraphExtender<
1.947 - SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1.948 - public:
1.949 - typedef _Graph Graph;
1.950 - typedef IterableGraphExtender<
1.951 - SubBidirGraphWrapperBase<
1.952 - _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1.953 - protected:
1.954 - SubBidirGraphWrapper() { }
1.955 - public:
1.956 - SubBidirGraphWrapper(_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 A wrapper for composing bidirected graph from a directed one.
1.967 - ///
1.968 - ///\warning Graph wrappers 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 - /// A wrapper 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 BidirGraphWrapper :
1.977 - public SubBidirGraphWrapper<
1.978 - Graph,
1.979 - ConstMap<typename Graph::Edge, bool>,
1.980 - ConstMap<typename Graph::Edge, bool> > {
1.981 - public:
1.982 - typedef SubBidirGraphWrapper<
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 - BidirGraphWrapper() : Parent(), cm(true) {
1.990 - Parent::setForwardFilterMap(cm);
1.991 - Parent::setBackwardFilterMap(cm);
1.992 - }
1.993 - public:
1.994 - BidirGraphWrapper(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, BidirGraphWrapper);
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 A wrapper for composing the residual graph for directed flow and circulation problems.
1.1044 -
1.1045 - A wrapper 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 ResGraphWrapper, \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 RevGraphWrapper 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 wrapper 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 - ResGraphWrapper<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 ResGraphWrapper :
1.1078 - public SubBidirGraphWrapper<
1.1079 - Graph,
1.1080 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.1081 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1.1082 - public:
1.1083 - typedef SubBidirGraphWrapper<
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 - ResGraphWrapper() : 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 - ResGraphWrapper(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 ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1.1131 - public:
1.1132 - typedef Number Value;
1.1133 - typedef Edge Key;
1.1134 - ResCap(const ResGraphWrapper<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, ResGraphWrapper);
1.1145 - };
1.1146 -
1.1147 -
1.1148 -
1.1149 - template <typename _Graph, typename FirstOutEdgesMap>
1.1150 - class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1.1151 - public:
1.1152 - typedef _Graph Graph;
1.1153 - typedef GraphWrapperBase<_Graph> Parent;
1.1154 - protected:
1.1155 - FirstOutEdgesMap* first_out_edges;
1.1156 - ErasingFirstGraphWrapperBase() : 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 wrappers 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 wrapper 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 ErasingFirstGraphWrapper :
1.1197 - public IterableGraphExtender<
1.1198 - ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1.1199 - public:
1.1200 - typedef _Graph Graph;
1.1201 - typedef IterableGraphExtender<
1.1202 - ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1.1203 - ErasingFirstGraphWrapper(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_WRAPPER_H
1.1216 -