COIN-OR::LEMON - Graph Library

Changeset 1172:37338ae42a2b in lemon-0.x for doc


Ignore:
Timestamp:
02/23/05 23:00:05 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1578
Message:

graphwrapper dox. everybody is asked to read doxygen.log

Location:
doc
Files:
2 edited
1 copied

Legend:

Unmodified
Added
Removed
  • doc/Doxyfile

    r1170 r1172  
    459459                         graph_io.dox \
    460460                         dirs.dox \
     461                         gwrappers.dox \
    461462                         ../src/lemon \
    462463                         ../src/lemon/concept \
  • doc/groups.dox

    r1151 r1172  
    1010\brief Graph structures implemented in LEMON.
    1111
    12 LEMON provides several data structures to meet the diverging requirements
    13 of the possible users.
    14 In order to save on running time or on memory usage, some structures may
    15 fail to provide
    16 some graph features like edge or node deletion.
     12The implementation of combinatorial algorithms heavily relies on
     13efficient graph implementations. LEMON offers data structures which are
     14planned to be easily used in an experimental phase of implementation studies,
     15and thereafter the program code can be made efficient by small modifications.
    1716
    18 LEMON also offers special graphs that cannot be used alone but only
    19 in conjunction with other graph representation. The examples for this are
    20 \ref lemon::EdgeSet "EdgeSet", \ref lemon::NodeSet "NodeSet"
    21 and the large variety of \ref gwrappers "graph wrappers".
     17The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of
     18graph we require to handle, memory or time usage limitations or in
     19the set of operations through which the graph can be accessed.
     20LEMON provides several physical graph structures to meet the
     21diverging requirements of the possible users.
     22In order to save on running time or on memory usage, some structures may
     23fail to provide some graph features like edge or node deletion.
     24
     25Alteration of standard containers need a very limited number of
     26operations, these together satisfy the everyday requirements.
     27In the case of graph strutures, different operations are needed which do
     28not alter the physical graph, but gives an other view. If some nodes or
     29edges have to be hidden or the reverse oriented graph have to be used, then
     30this is the case. It also may happen that in a flow implemenation
     31the residual graph can be accessed by an other algorithm, or a node-set
     32is to be shrunk for an other algorithm.
     33LEMON also provides a variety of graphs for these requirements called
     34\ref gwrappers "graph wrappers". Wrappers cannot be used alone but only
     35in conjunction with other graph representation.
    2236
    2337You are free to use the graph structure that fit your requirements
    2438the best, most graph algorithms and auxiliary data structures can be used
    25 with any graph structures.
     39with any graph structures. 
    2640*/
    2741
     
    5165This group describes the tools that makes it easier to make graph maps that
    5266dynamically update with the graph changes.
    53 */
    54 
    55 /**
    56 @defgroup gwrappers Wrapper Classes for Graphs
    57 \brief This group contains several wrapper classes for graphs
    58 @ingroup graphs
    5967*/
    6068
  • doc/gwrappers.dox

    r1164 r1172  
    1 /* -*- C++ -*-
    2  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
    3  *
    4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Combinatorial Optimization Research Group, EGRES).
    6  *
    7  * Permission to use, modify and distribute this software is granted
    8  * provided that this copyright notice appears in all copies. For
    9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_GRAPH_WRAPPER_H
    18 #define LEMON_GRAPH_WRAPPER_H
    19 
    20 ///\ingroup gwrappers
    21 ///\file
    22 ///\brief Several graph wrappers.
    23 ///
    24 ///This file contains several useful graph wrapper functions.
    25 ///
    26 ///\author Marton Makai
    27 
    28 #include <lemon/invalid.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/iterable_graph_extender.h>
    31 #include <iostream>
    32 
    33 namespace lemon {
    34 
    35   // Graph wrappers
    36 
    37   /*! \addtogroup gwrappers
    38     The main parts of LEMON are the different graph structures,
    39     generic graph algorithms, graph concepts which couple these, and
    40     graph wrappers. While the previous ones are more or less clear, the
    41     latter notion needs further explanation.
    42     Graph wrappers are graph classes which serve for considering graph
    43     structures in different ways. A short example makes the notion much
    44     clearer.
    45     Suppose that we have an instance \c g of a directed graph
    46     type say \c ListGraph and an algorithm
    47     \code template<typename Graph> int algorithm(const Graph&); \endcode
    48     is needed to run on the reversely oriented graph.
    49     It may be expensive (in time or in memory usage) to copy
    50     \c g with the reverse orientation.
    51     Thus, a wrapper class
    52     \code template<typename Graph> class RevGraphWrapper; \endcode is used.
    53     The code looks as follows
    54     \code
    55     ListGraph g;
    56     RevGraphWrapper<ListGraph> rgw(g);
    57     int result=algorithm(rgw);
    58     \endcode
    59     After running the algorithm, the original graph \c g
    60     remains untouched. Thus the graph wrapper used above is to consider the
    61     original graph with reverse orientation.
    62     This techniques gives rise to an elegant code, and
    63     based on stable graph wrappers, complex algorithms can be
    64     implemented easily.
    65     In flow, circulation and bipartite matching problems, the residual
    66     graph is of particular importance. Combining a wrapper implementing
    67     this, shortest path algorithms and minimum mean cycle algorithms,
    68     a range of weighted and cardinality optimization algorithms can be
    69     obtained. For lack of space, for other examples,
    70     the interested user is referred to the detailed documentation of graph
    71     wrappers.
    72     The behavior of graph wrappers can be very different. Some of them keep
    73     capabilities of the original graph while in other cases this would be
    74     meaningless. This means that the concepts that they are a model of depend
    75     on the graph wrapper, and the wrapped graph(s).
    76     If an edge of \c rgw is deleted, this is carried out by
    77     deleting the corresponding edge of \c g. But for a residual
    78     graph, this operation has no sense.
    79     Let we stand one more example here to simplify your work.
    80     wrapper class
    81     \code template<typename Graph> class RevGraphWrapper; \endcode
    82     has constructor
    83     <tt> RevGraphWrapper(Graph& _g)</tt>.
    84     This means that in a situation,
    85     when a <tt> const ListGraph& </tt> reference to a graph is given,
    86     then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    87     \code
    88     int algorithm1(const ListGraph& g) {
    89     RevGraphWrapper<const ListGraph> rgw(g);
    90     return algorithm2(rgw);
    91     }
    92     \endcode
    93 
    94     \addtogroup gwrappers
    95     @{
    96 
    97     Base type for the Graph Wrappers
    98 
    99     \warning Graph wrappers are in even more experimental state than the other
    100     parts of the lib. Use them at you own risk.
    101  
    102     This is the base type for most of LEMON graph wrappers.
    103     This class implements a trivial graph wrapper i.e. it only wraps the
    104     functions and types of the graph. The purpose of this class is to
    105     make easier implementing graph wrappers. E.g. if a wrapper is
    106     considered which differs from the wrapped graph only in some of its
    107     functions or types, then it can be derived from GraphWrapper, and only the
    108     differences should be implemented.
    109  
    110     \author Marton Makai
    111   */
    112   template<typename _Graph>
    113   class GraphWrapperBase {
    114   public:
    115     typedef _Graph Graph;
    116     /// \todo Is it needed?
    117     typedef Graph BaseGraph;
    118     typedef Graph ParentGraph;
    119 
    120   protected:
    121     Graph* graph;
    122     GraphWrapperBase() : graph(0) { }
    123     void setGraph(Graph& _graph) { graph=&_graph; }
    124 
    125   public:
    126     GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
    127  
    128     typedef typename Graph::Node Node;
    129     typedef typename Graph::Edge Edge;
     1/**
     2   @defgroup gwrappers Wrapper Classes for Graphs
     3   \brief This group contains several wrapper classes for graphs
     4   @ingroup graphs
    1305   
    131     void first(Node& i) const { graph->first(i); }
    132     void first(Edge& i) const { graph->first(i); }
    133     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    134     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
    135 
    136     void next(Node& i) const { graph->next(i); }
    137     void next(Edge& i) const { graph->next(i); }
    138     void nextIn(Edge& i) const { graph->nextIn(i); }
    139     void nextOut(Edge& i) const { graph->nextOut(i); }
    140 
    141     Node source(const Edge& e) const { return graph->source(e); }
    142     Node target(const Edge& e) const { return graph->target(e); }
    143 
    144     int nodeNum() const { return graph->nodeNum(); }
    145     int edgeNum() const { return graph->edgeNum(); }
    146  
    147     Node addNode() const { return Node(graph->addNode()); }
    148     Edge addEdge(const Node& source, const Node& target) const {
    149       return Edge(graph->addEdge(source, target)); }
    150 
    151     void erase(const Node& i) const { graph->erase(i); }
    152     void erase(const Edge& i) const { graph->erase(i); }
    153  
    154     void clear() const { graph->clear(); }
    155    
    156     bool forward(const Edge& e) const { return graph->forward(e); }
    157     bool backward(const Edge& e) const { return graph->backward(e); }
    158 
    159     int id(const Node& v) const { return graph->id(v); }
    160     int id(const Edge& e) const { return graph->id(e); }
    161    
    162     Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
    163 
    164     template <typename _Value>
    165     class NodeMap : public _Graph::template NodeMap<_Value> {
    166     public:
    167       typedef typename _Graph::template NodeMap<_Value> Parent;
    168       NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
    169       NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
    170       : Parent(*gw.graph, value) { }
    171     };
    172 
    173     template <typename _Value>
    174     class EdgeMap : public _Graph::template EdgeMap<_Value> {
    175     public:
    176       typedef typename _Graph::template EdgeMap<_Value> Parent;
    177       EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
    178       EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
    179       : Parent(*gw.graph, value) { }
    180     };
    181 
    182   };
    183 
    184   template <typename _Graph>
    185   class GraphWrapper :
    186     public IterableGraphExtender<GraphWrapperBase<_Graph> > {
    187   public:
    188     typedef _Graph Graph;
    189     typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
    190   protected:
    191     GraphWrapper() : Parent() { }
    192 
    193   public:
    194     GraphWrapper(Graph& _graph) { setGraph(_graph); }
    195   };
    196 
    197   template <typename _Graph>
    198   class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
    199   public:
    200     typedef _Graph Graph;
    201     typedef GraphWrapperBase<_Graph> Parent;
    202   protected:
    203     RevGraphWrapperBase() : Parent() { }
    204   public:
    205     typedef typename Parent::Node Node;
    206     typedef typename Parent::Edge Edge;
    207 
    208     using Parent::first;
    209     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
    210     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
    211 
    212     using Parent::next;
    213     void nextIn(Edge& i) const { Parent::nextOut(i); }
    214     void nextOut(Edge& i) const { Parent::nextIn(i); }
    215 
    216     Node source(const Edge& e) const { return Parent::target(e); }
    217     Node target(const Edge& e) const { return Parent::source(e); }
    218   };
    219    
    220 
    221   /// A graph wrapper which reverses the orientation of the edges.
    222 
    223   ///\warning Graph wrappers are in even more experimental state than the other
    224   ///parts of the lib. Use them at you own risk.
    225   ///
    226   /// Let \f$G=(V, A)\f$ be a directed graph and
    227   /// suppose that a graph instange \c g of type
    228   /// \c ListGraph implements \f$G\f$.
    229   /// \code
    230   /// ListGraph g;
    231   /// \endcode
    232   /// For each directed edge
    233   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
    234   /// reversing its orientation.
    235   /// Then RevGraphWrapper implements the graph structure with node-set
    236   /// \f$V\f$ and edge-set
    237   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
    238   /// reversing the orientation of its edges. The following code shows how
    239   /// such an instance can be constructed.
    240   /// \code
    241   /// RevGraphWrapper<ListGraph> gw(g);
    242   /// \endcode
    243   ///\author Marton Makai
    244   template<typename _Graph>
    245   class RevGraphWrapper :
    246     public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
    247   public:
    248     typedef _Graph Graph;
    249     typedef IterableGraphExtender<
    250       RevGraphWrapperBase<_Graph> > Parent;
    251   protected:
    252     RevGraphWrapper() { }
    253   public:
    254     RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
    255   };
    256 
    257  
    258   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
    259   class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
    260   public:
    261     typedef _Graph Graph;
    262     typedef GraphWrapperBase<_Graph> Parent;
    263   protected:
    264     NodeFilterMap* node_filter_map;
    265     EdgeFilterMap* edge_filter_map;
    266     SubGraphWrapperBase() : Parent(),
    267                             node_filter_map(0), edge_filter_map(0) { }
    268 
    269     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
    270       node_filter_map=&_node_filter_map;
    271     }
    272     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
    273       edge_filter_map=&_edge_filter_map;
    274     }
    275 
    276   public:
    277 //     SubGraphWrapperBase(Graph& _graph,
    278 //                      NodeFilterMap& _node_filter_map,
    279 //                      EdgeFilterMap& _edge_filter_map) :
    280 //       Parent(&_graph),
    281 //       node_filter_map(&node_filter_map),
    282 //       edge_filter_map(&edge_filter_map) { }
    283 
    284     typedef typename Parent::Node Node;
    285     typedef typename Parent::Edge Edge;
    286 
    287     void first(Node& i) const {
    288       Parent::first(i);
    289       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
    290     }
    291     void first(Edge& i) const {
    292       Parent::first(i);
    293       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
    294     }
    295     void firstIn(Edge& i, const Node& n) const {
    296       Parent::firstIn(i, n);
    297       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
    298     }
    299     void firstOut(Edge& i, const Node& n) const {
    300       Parent::firstOut(i, n);
    301       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
    302     }
    303 
    304     void next(Node& i) const {
    305       Parent::next(i);
    306       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
    307     }
    308     void next(Edge& i) const {
    309       Parent::next(i);
    310       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
    311     }
    312     void nextIn(Edge& i) const {
    313       Parent::nextIn(i);
    314       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
    315     }
    316     void nextOut(Edge& i) const {
    317       Parent::nextOut(i);
    318       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
    319     }
    320 
    321     /// This function hides \c n in the graph, i.e. the iteration
    322     /// jumps over it. This is done by simply setting the value of \c n 
    323     /// to be false in the corresponding node-map.
    324     void hide(const Node& n) const { node_filter_map->set(n, false); }
    325 
    326     /// This function hides \c e in the graph, i.e. the iteration
    327     /// jumps over it. This is done by simply setting the value of \c e 
    328     /// to be false in the corresponding edge-map.
    329     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    330 
    331     /// The value of \c n is set to be true in the node-map which stores
    332     /// hide information. If \c n was hidden previuosly, then it is shown
    333     /// again
    334      void unHide(const Node& n) const { node_filter_map->set(n, true); }
    335 
    336     /// The value of \c e is set to be true in the edge-map which stores
    337     /// hide information. If \c e was hidden previuosly, then it is shown
    338     /// again
    339     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    340 
    341     /// Returns true if \c n is hidden.
    342     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    343 
    344     /// Returns true if \c n is hidden.
    345     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    346 
    347     /// \warning This is a linear time operation and works only if s
    348     /// \c Graph::NodeIt is defined.
    349     /// \todo assign tags.
    350     int nodeNum() const {
    351       int i=0;
    352       Node n;
    353       for (first(n); n!=INVALID; next(n)) ++i;
    354       return i;
    355     }
    356 
    357     /// \warning This is a linear time operation and works only if
    358     /// \c Graph::EdgeIt is defined.
    359     /// \todo assign tags.
    360     int edgeNum() const {
    361       int i=0;
    362       Edge e;
    363       for (first(e); e!=INVALID; next(e)) ++i;
    364       return i;
    365     }
    366 
    367 
    368   };
    369 
    370   /*! \brief A graph wrapper for hiding nodes and edges from a graph.
    371  
    372   \warning Graph wrappers are in even more experimental state than the other
    373   parts of the lib. Use them at you own risk.
    374  
    375   This wrapper shows a graph with filtered node-set and
    376   edge-set.
    377   Given a bool-valued map on the node-set and one on
    378   the edge-set of the graph, the iterators show only the objects
    379   having true value. We have to note that this does not mean that an
    380   induced subgraph is obtained, the node-iterator cares only the filter
    381   on the node-set, and the edge-iterators care only the filter on the
    382   edge-set.
    383   \code
    384   typedef SmartGraph Graph;
    385   Graph g;
    386   typedef Graph::Node Node;
    387   typedef Graph::Edge Edge;
    388   Node u=g.addNode(); //node of id 0
    389   Node v=g.addNode(); //node of id 1
    390   Node e=g.addEdge(u, v); //edge of id 0
    391   Node f=g.addEdge(v, u); //edge of id 1
    392   Graph::NodeMap<bool> nm(g, true);
    393   nm.set(u, false);
    394   Graph::EdgeMap<bool> em(g, true);
    395   em.set(e, false);
    396   typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    397   SubGW gw(g, nm, em);
    398   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    399   std::cout << ":-)" << std::endl;
    400   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
    401   \endcode
    402   The output of the above code is the following.
    403   \code
    404   1
    405   :-)
    406   1
    407   \endcode
    408   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
    409   \c Graph::Node that is why \c g.id(n) can be applied.
    410 
    411   For other examples see also the documentation of NodeSubGraphWrapper and
    412   EdgeSubGraphWrapper.
    413 
    414   \author Marton Makai
    415   */
    416   template<typename _Graph, typename NodeFilterMap,
    417            typename EdgeFilterMap>
    418   class SubGraphWrapper :
    419     public IterableGraphExtender<
    420     SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
    421   public:
    422     typedef _Graph Graph;
    423     typedef IterableGraphExtender<
    424       SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
    425   protected:
    426     SubGraphWrapper() { }
    427   public:
    428     SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
    429                     EdgeFilterMap& _edge_filter_map) {
    430       setGraph(_graph);
    431       setNodeFilterMap(_node_filter_map);
    432       setEdgeFilterMap(_edge_filter_map);
    433     }
    434   };
    435 
    436 
    437 
    438   /*! \brief A wrapper for hiding nodes from a graph.
    439 
    440   \warning Graph wrappers are in even more experimental state than the other
    441   parts of the lib. Use them at you own risk.
    442  
    443   A wrapper for hiding nodes from a graph.
    444   This wrapper specializes SubGraphWrapper in the way that only the node-set
    445   can be filtered. Note that this does not mean of considering induced
    446   subgraph, the edge-iterators consider the original edge-set.
    447   \author Marton Makai
    448   */
    449   template<typename Graph, typename NodeFilterMap>
    450   class NodeSubGraphWrapper :
    451     public SubGraphWrapper<Graph, NodeFilterMap,
    452                            ConstMap<typename Graph::Edge,bool> > {
    453   public:
    454     typedef SubGraphWrapper<Graph, NodeFilterMap,
    455                             ConstMap<typename Graph::Edge,bool> > Parent;
    456   protected:
    457     ConstMap<typename Graph::Edge, bool> const_true_map;
    458   public:
    459     NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
    460       Parent(), const_true_map(true) {
    461       Parent::setGraph(_graph);
    462       Parent::setNodeFilterMap(_node_filter_map);
    463       Parent::setEdgeFilterMap(const_true_map);
    464     }
    465   };
    466 
    467 
    468   /*! \brief A wrapper for hiding edges from a graph.
    469 
    470   \warning Graph wrappers are in even more experimental state than the other
    471   parts of the lib. Use them at you own risk.
    472  
    473   A wrapper for hiding edges from a graph.
    474   This wrapper specializes SubGraphWrapper in the way that only the edge-set
    475   can be filtered. The usefulness of this wrapper is demonstrated in the
    476   problem of searching a maximum number of edge-disjoint shortest paths
    477   between
    478   two nodes \c s and \c t. Shortest here means being shortest w.r.t.
    479   non-negative edge-lengths. Note that
    480   the comprehension of the presented solution
    481   need's some knowledge from elementary combinatorial optimization.
    482 
    483   If a single shortest path is to be
    484   searched between two nodes \c s and \c t, then this can be done easily by
    485   applying the Dijkstra algorithm class. What happens, if a maximum number of
    486   edge-disjoint shortest paths is to be computed. It can be proved that an
    487   edge can be in a shortest path if and only if it is tight with respect to
    488   the potential function computed by Dijkstra. Moreover, any path containing
    489   only such edges is a shortest one. Thus we have to compute a maximum number
    490   of edge-disjoint paths between \c s and \c t in the graph which has edge-set
    491   all the tight edges. The computation will be demonstrated on the following
    492   graph, which is read from a dimacs file.
    493  
    494   \dot
    495   digraph lemon_dot_example {
    496   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    497   n0 [ label="0 (s)" ];
    498   n1 [ label="1" ];
    499   n2 [ label="2" ];
    500   n3 [ label="3" ];
    501   n4 [ label="4" ];
    502   n5 [ label="5" ];
    503   n6 [ label="6 (t)" ];
    504   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    505   n5 ->  n6 [ label="9, length:4" ];
    506   n4 ->  n6 [ label="8, length:2" ];
    507   n3 ->  n5 [ label="7, length:1" ];
    508   n2 ->  n5 [ label="6, length:3" ];
    509   n2 ->  n6 [ label="5, length:5" ];
    510   n2 ->  n4 [ label="4, length:2" ];
    511   n1 ->  n4 [ label="3, length:3" ];
    512   n0 ->  n3 [ label="2, length:1" ];
    513   n0 ->  n2 [ label="1, length:2" ];
    514   n0 ->  n1 [ label="0, length:3" ];
    515   }
    516   \enddot
    517 
    518   \code
    519   Graph g;
    520   Node s, t;
    521   LengthMap length(g);
    522 
    523   readDimacs(std::cin, g, length, s, t);
    524 
    525   cout << "edges with lengths (of form id, source--length->target): " << endl;
    526   for(EdgeIt e(g); e!=INVALID; ++e)
    527     cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
    528          << length[e] << "->" << g.id(g.target(e)) << endl;
    529 
    530   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
    531   \endcode
    532   Next, the potential function is computed with Dijkstra.
    533   \code
    534   typedef Dijkstra<Graph, LengthMap> Dijkstra;
    535   Dijkstra dijkstra(g, length);
    536   dijkstra.run(s);
    537   \endcode
    538   Next, we consrtruct a map which filters the edge-set to the tight edges.
    539   \code
    540   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
    541     TightEdgeFilter;
    542   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
    543  
    544   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
    545   SubGW gw(g, tight_edge_filter);
    546   \endcode
    547   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
    548   with a max flow algorithm Preflow.
    549   \code
    550   ConstMap<Edge, int> const_1_map(1);
    551   Graph::EdgeMap<int> flow(g, 0);
    552 
    553   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
    554     preflow(gw, s, t, const_1_map, flow);
    555   preflow.run();
    556   \endcode
    557   Last, the output is:
    558   \code 
    559   cout << "maximum number of edge-disjoint shortest path: "
    560        << preflow.flowValue() << endl;
    561   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
    562        << endl;
    563   for(EdgeIt e(g); e!=INVALID; ++e)
    564     if (flow[e])
    565       cout << " " << g.id(g.source(e)) << "--"
    566            << length[e] << "->" << g.id(g.target(e)) << endl;
    567   \endcode
    568   The program has the following (expected :-)) output:
    569   \code
    570   edges with lengths (of form id, source--length->target):
    571    9, 5--4->6
    572    8, 4--2->6
    573    7, 3--1->5
    574    6, 2--3->5
    575    5, 2--5->6
    576    4, 2--2->4
    577    3, 1--3->4
    578    2, 0--1->3
    579    1, 0--2->2
    580    0, 0--3->1
    581   s: 0 t: 6
    582   maximum number of edge-disjoint shortest path: 2
    583   edges of the maximum number of edge-disjoint shortest s-t paths:
    584    9, 5--4->6
    585    8, 4--2->6
    586    7, 3--1->5
    587    4, 2--2->4
    588    2, 0--1->3
    589    1, 0--2->2
    590   \endcode
    591 
    592   \author Marton Makai
    593   */
    594   template<typename Graph, typename EdgeFilterMap>
    595   class EdgeSubGraphWrapper :
    596     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
    597                            EdgeFilterMap> {
    598   public:
    599     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
    600                             EdgeFilterMap> Parent;
    601   protected:
    602     ConstMap<typename Graph::Node, bool> const_true_map;
    603   public:
    604     EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
    605       Parent(), const_true_map(true) {
    606       Parent::setGraph(_graph);
    607       Parent::setNodeFilterMap(const_true_map);
    608       Parent::setEdgeFilterMap(_edge_filter_map);
    609     }
    610   };
    611 
    612 
    613   template<typename Graph>
    614   class UndirGraphWrapper : public GraphWrapper<Graph> {
    615   public:
    616     typedef GraphWrapper<Graph> Parent;
    617   protected:
    618     UndirGraphWrapper() : GraphWrapper<Graph>() { }
    619    
    620   public:
    621     typedef typename GraphWrapper<Graph>::Node Node;
    622     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    623     typedef typename GraphWrapper<Graph>::Edge Edge;
    624     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    625 
    626     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    627 
    628     class OutEdgeIt {
    629       friend class UndirGraphWrapper<Graph>;
    630       bool out_or_in; //true iff out
    631       typename Graph::OutEdgeIt out;
    632       typename Graph::InEdgeIt in;
    633     public:
    634       OutEdgeIt() { }
    635       OutEdgeIt(const Invalid& i) : Edge(i) { }
    636       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
    637         out_or_in=true; _G.graph->first(out, _n);
    638         if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
    639       }
    640       operator Edge() const {
    641         if (out_or_in) return Edge(out); else return Edge(in);
    642       }
    643     };
    644 
    645     typedef OutEdgeIt InEdgeIt;
    646 
    647     using GraphWrapper<Graph>::first;
    648     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    649       i=OutEdgeIt(*this, p); return i;
    650     }
    651 
    652     using GraphWrapper<Graph>::next;
    653 
    654     OutEdgeIt& next(OutEdgeIt& e) const {
    655       if (e.out_or_in) {
    656         typename Graph::Node n=this->graph->source(e.out);
    657         this->graph->next(e.out);
    658         if (!this->graph->valid(e.out)) {
    659           e.out_or_in=false; this->graph->first(e.in, n); }
    660       } else {
    661         this->graph->next(e.in);
    662       }
    663       return e;
    664     }
    665 
    666     Node aNode(const OutEdgeIt& e) const {
    667       if (e.out_or_in) return this->graph->source(e); else
    668         return this->graph->target(e); }
    669     Node bNode(const OutEdgeIt& e) const {
    670       if (e.out_or_in) return this->graph->target(e); else
    671         return this->graph->source(e); }
    672 
    673     //    KEEP_MAPS(Parent, UndirGraphWrapper);
    674 
    675   };
    676  
    677 //   /// \brief An undirected graph template.
    678 //   ///
    679 //   ///\warning Graph wrappers are in even more experimental state than the other
    680 //   ///parts of the lib. Use them at your own risk.
    681 //   ///
    682 //   /// An undirected graph template.
    683 //   /// This class works as an undirected graph and a directed graph of
    684 //   /// class \c Graph is used for the physical storage.
    685 //   /// \ingroup graphs
    686   template<typename Graph>
    687   class UndirGraph : public UndirGraphWrapper<Graph> {
    688     typedef UndirGraphWrapper<Graph> Parent;
    689   protected:
    690     Graph gr;
    691   public:
    692     UndirGraph() : UndirGraphWrapper<Graph>() {
    693       Parent::setGraph(gr);
    694     }
    695 
    696     //    KEEP_MAPS(Parent, UndirGraph);
    697   };
    698 
    699  
    700   template <typename _Graph,
    701             typename ForwardFilterMap, typename BackwardFilterMap>
    702   class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
    703   public:
    704     typedef _Graph Graph;
    705     typedef GraphWrapperBase<_Graph> Parent;
    706   protected:
    707     ForwardFilterMap* forward_filter;
    708     BackwardFilterMap* backward_filter;
    709     SubBidirGraphWrapperBase() : Parent(),
    710                                  forward_filter(0), backward_filter(0) { }
    711 
    712     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
    713       forward_filter=&_forward_filter;
    714     }
    715     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
    716       backward_filter=&_backward_filter;
    717     }
    718 
    719   public:
    720 //     SubGraphWrapperBase(Graph& _graph,
    721 //                      NodeFilterMap& _node_filter_map,
    722 //                      EdgeFilterMap& _edge_filter_map) :
    723 //       Parent(&_graph),
    724 //       node_filter_map(&node_filter_map),
    725 //       edge_filter_map(&edge_filter_map) { }
    726 
    727     typedef typename Parent::Node Node;
    728     typedef typename _Graph::Edge GraphEdge;
    729     template <typename T> class EdgeMap;
    730     /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
    731     /// _Graph::Edge. It contains an extra bool flag which is true
    732     /// if and only if the
    733     /// edge is the backward version of the original edge.
    734     class Edge : public _Graph::Edge {
    735       friend class SubBidirGraphWrapperBase<
    736         Graph, ForwardFilterMap, BackwardFilterMap>;
    737       template<typename T> friend class EdgeMap;
    738     protected:
    739       bool backward; //true, iff backward
    740     public:
    741       Edge() { }
    742       /// \todo =false is needed, or causes problems?
    743       /// If \c _backward is false, then we get an edge corresponding to the
    744       /// original one, otherwise its oppositely directed pair is obtained.
    745       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
    746         _Graph::Edge(e), backward(_backward) { }
    747       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
    748       bool operator==(const Edge& v) const {
    749         return (this->backward==v.backward &&
    750                 static_cast<typename _Graph::Edge>(*this)==
    751                 static_cast<typename _Graph::Edge>(v));
    752       }
    753       bool operator!=(const Edge& v) const {
    754         return (this->backward!=v.backward ||
    755                 static_cast<typename _Graph::Edge>(*this)!=
    756                 static_cast<typename _Graph::Edge>(v));
    757       }
    758     };
    759 
    760     void first(Node& i) const {
    761       Parent::first(i);
    762     }
    763 
    764     void first(Edge& i) const {
    765       Parent::first(i);
    766       i.backward=false;
    767       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    768              !(*forward_filter)[i]) Parent::next(i);
    769       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    770         Parent::first(i);
    771         i.backward=true;
    772         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    773                !(*backward_filter)[i]) Parent::next(i);
    774       }
    775     }
    776 
    777     void firstIn(Edge& i, const Node& n) const {
    778       Parent::firstIn(i, n);
    779       i.backward=false;
    780       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    781              !(*forward_filter)[i]) Parent::nextOut(i);
    782       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    783         Parent::firstOut(i, n);
    784         i.backward=true;
    785         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    786                !(*backward_filter)[i]) Parent::nextOut(i);
    787       }
    788     }
    789 
    790     void firstOut(Edge& i, const Node& n) const {
    791       Parent::firstOut(i, n);
    792       i.backward=false;
    793       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    794              !(*forward_filter)[i]) Parent::nextOut(i);
    795       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    796         Parent::firstIn(i, n);
    797         i.backward=true;
    798         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    799                !(*backward_filter)[i]) Parent::nextIn(i);
    800       }
    801     }
    802 
    803     void next(Node& i) const {
    804       Parent::next(i);
    805     }
    806 
    807     void next(Edge& i) const {
    808       if (!(i.backward)) {
    809         Parent::next(i);
    810         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    811                !(*forward_filter)[i]) Parent::next(i);
    812         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    813           Parent::first(i);
    814           i.backward=true;
    815           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    816                  !(*backward_filter)[i]) Parent::next(i);
    817         }
    818       } else {
    819         Parent::next(i);
    820         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    821                !(*backward_filter)[i]) Parent::next(i);
    822       }
    823     }
    824 
    825     void nextIn(Edge& i) const {
    826       if (!(i.backward)) {
    827         Node n=Parent::target(i);
    828         Parent::nextIn(i);
    829         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    830                !(*forward_filter)[i]) Parent::nextIn(i);
    831         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    832           Parent::firstOut(i, n);
    833           i.backward=true;
    834           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    835                  !(*backward_filter)[i]) Parent::nextOut(i);
    836         }
    837       } else {
    838         Parent::nextOut(i);
    839         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    840                !(*backward_filter)[i]) Parent::nextOut(i);
    841       }
    842     }
    843 
    844     void nextOut(Edge& i) const {
    845       if (!(i.backward)) {
    846         Node n=Parent::source(i);
    847         Parent::nextOut(i);
    848         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    849                !(*forward_filter)[i]) Parent::nextOut(i);
    850         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    851           Parent::firstIn(i, n);
    852           i.backward=true;
    853           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    854                  !(*backward_filter)[i]) Parent::nextIn(i);
    855         }
    856       } else {
    857         Parent::nextIn(i);
    858         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    859                !(*backward_filter)[i]) Parent::nextIn(i);
    860       }
    861     }
    862 
    863     Node source(Edge e) const {
    864       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
    865     Node target(Edge e) const {
    866       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
    867 
    868     /// Gives back the opposite edge.
    869     Edge opposite(const Edge& e) const {
    870       Edge f=e;
    871       f.backward=!f.backward;
    872       return f;
    873     }
    874 
    875     /// \warning This is a linear time operation and works only if
    876     /// \c Graph::EdgeIt is defined.
    877     /// \todo hmm
    878     int edgeNum() const {
    879       int i=0;
    880       Edge e;
    881       for (first(e); e!=INVALID; next(e)) ++i;
    882       return i;
    883     }
    884 
    885     bool forward(const Edge& e) const { return !e.backward; }
    886     bool backward(const Edge& e) const { return e.backward; }
    887 
    888     template <typename T>
    889     /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
    890     /// _Graph::EdgeMap one for the forward edges and
    891     /// one for the backward edges.
    892     class EdgeMap {
    893       template <typename TT> friend class EdgeMap;
    894       typename _Graph::template EdgeMap<T> forward_map, backward_map;
    895     public:
    896       typedef T Value;
    897       typedef Edge Key;
    898 
    899       EdgeMap(const SubBidirGraphWrapperBase<_Graph,
    900               ForwardFilterMap, BackwardFilterMap>& g) :
    901         forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    902 
    903       EdgeMap(const SubBidirGraphWrapperBase<_Graph,
    904               ForwardFilterMap, BackwardFilterMap>& g, T a) :
    905         forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    906      
    907       void set(Edge e, T a) {
    908         if (!e.backward)
    909           forward_map.set(e, a);
    910         else
    911           backward_map.set(e, a);
    912       }
    913 
    914 //       typename _Graph::template EdgeMap<T>::ConstReference
    915 //       operator[](Edge e) const {
    916 //      if (!e.backward)
    917 //        return forward_map[e];
    918 //      else
    919 //        return backward_map[e];
    920 //       }
    921 
    922 //      typename _Graph::template EdgeMap<T>::Reference
    923       T operator[](Edge e) const {
    924         if (!e.backward)
    925           return forward_map[e];
    926         else
    927           return backward_map[e];
    928       }
    929 
    930       void update() {
    931         forward_map.update();
    932         backward_map.update();
    933       }
    934     };
    935 
    936   };
    937 
    938 
    939   ///\brief A wrapper for composing a subgraph of a
    940   /// bidirected graph made from a directed one.
    941   ///
    942   /// A wrapper for composing a subgraph of a
    943   /// bidirected graph made from a directed one.
    944   ///
    945   ///\warning Graph wrappers are in even more experimental state than the other
    946   ///parts of the lib. Use them at you own risk.
    947   ///
    948   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
    949   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
    950   /// reversing its orientation. We are given moreover two bool valued
    951   /// maps on the edge-set,
    952   /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
    953   /// SubBidirGraphWrapper implements the graph structure with node-set
    954   /// \f$V\f$ and edge-set
    955   /// \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$.
    956   /// The purpose of writing + instead of union is because parallel
    957   /// edges can arise. (Similarly, antiparallel edges also can arise).
    958   /// In other words, a subgraph of the bidirected graph obtained, which
    959   /// is given by orienting the edges of the original graph in both directions.
    960   /// As the oppositely directed edges are logically different,
    961   /// the maps are able to attach different values for them.
    962   ///
    963   /// An example for such a construction is \c RevGraphWrapper where the
    964   /// forward_filter is everywhere false and the backward_filter is
    965   /// everywhere true. We note that for sake of efficiency,
    966   /// \c RevGraphWrapper is implemented in a different way.
    967   /// But BidirGraphWrapper is obtained from
    968   /// SubBidirGraphWrapper by considering everywhere true
    969   /// valued maps both for forward_filter and backward_filter.
    970   /// Finally, one of the most important applications of SubBidirGraphWrapper
    971   /// is ResGraphWrapper, which stands for the residual graph in directed
    972   /// flow and circulation problems.
    973   /// As wrappers usually, the SubBidirGraphWrapper implements the
    974   /// above mentioned graph structure without its physical storage,
    975   /// that is the whole stuff is stored in constant memory.
    976   template<typename _Graph,
    977            typename ForwardFilterMap, typename BackwardFilterMap>
    978   class SubBidirGraphWrapper :
    979     public IterableGraphExtender<
    980     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
    981   public:
    982     typedef _Graph Graph;
    983     typedef IterableGraphExtender<
    984       SubBidirGraphWrapperBase<
    985       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
    986   protected:
    987     SubBidirGraphWrapper() { }
    988   public:
    989     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
    990                          BackwardFilterMap& _backward_filter) {
    991       setGraph(_graph);
    992       setForwardFilterMap(_forward_filter);
    993       setBackwardFilterMap(_backward_filter);
    994     }
    995   };
    996 
    997 
    998 
    999   ///\brief A wrapper for composing bidirected graph from a directed one.
    1000   ///
    1001   ///\warning Graph wrappers are in even more experimental state than the other
    1002   ///parts of the lib. Use them at you own risk.
    1003   ///
    1004   /// A wrapper for composing bidirected graph from a directed one.
    1005   /// A bidirected graph is composed over the directed one without physical
    1006   /// storage. As the oppositely directed edges are logically different ones
    1007   /// the maps are able to attach different values for them.
    1008   template<typename Graph>
    1009   class BidirGraphWrapper :
    1010     public SubBidirGraphWrapper<
    1011     Graph,
    1012     ConstMap<typename Graph::Edge, bool>,
    1013     ConstMap<typename Graph::Edge, bool> > {
    1014   public:
    1015     typedef  SubBidirGraphWrapper<
    1016       Graph,
    1017       ConstMap<typename Graph::Edge, bool>,
    1018       ConstMap<typename Graph::Edge, bool> > Parent;
    1019   protected:
    1020     ConstMap<typename Graph::Edge, bool> cm;
    1021 
    1022     BidirGraphWrapper() : Parent(), cm(true) {
    1023       Parent::setForwardFilterMap(cm);
    1024       Parent::setBackwardFilterMap(cm);
    1025     }
    1026   public:
    1027     BidirGraphWrapper(Graph& _graph) : Parent() {
    1028       Parent::setGraph(_graph);
    1029       Parent::setForwardFilterMap(cm);
    1030       Parent::setBackwardFilterMap(cm);
    1031     }
    1032 
    1033     int edgeNum() const {
    1034       return 2*this->graph->edgeNum();
    1035     }
    1036     //    KEEP_MAPS(Parent, BidirGraphWrapper);
    1037   };
    1038 
    1039 
    1040   template<typename Graph, typename Number,
    1041            typename CapacityMap, typename FlowMap>
    1042   class ResForwardFilter {
    1043     //    const Graph* graph;
    1044     const CapacityMap* capacity;
    1045     const FlowMap* flow;
    1046   public:
    1047     ResForwardFilter(/*const Graph& _graph, */
    1048                      const CapacityMap& _capacity, const FlowMap& _flow) :
    1049       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    1050     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1051     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    1052     void setFlow(const FlowMap& _flow) { flow=&_flow; }
    1053     bool operator[](const typename Graph::Edge& e) const {
    1054       return (Number((*flow)[e]) < Number((*capacity)[e]));
    1055     }
    1056   };
    1057 
    1058   template<typename Graph, typename Number,
    1059            typename CapacityMap, typename FlowMap>
    1060   class ResBackwardFilter {
    1061     const CapacityMap* capacity;
    1062     const FlowMap* flow;
    1063   public:
    1064     ResBackwardFilter(/*const Graph& _graph,*/
    1065                       const CapacityMap& _capacity, const FlowMap& _flow) :
    1066       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    1067     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1068     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    1069     void setFlow(const FlowMap& _flow) { flow=&_flow; }
    1070     bool operator[](const typename Graph::Edge& e) const {
    1071       return (Number(0) < Number((*flow)[e]));
    1072     }
    1073   };
    1074 
    1075  
    1076   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    1077 
    1078   ///\warning Graph wrappers are in even more experimental state than the other
    1079   ///parts of the lib. Use them at you own risk.
    1080   ///
    1081   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    1082   template<typename Graph, typename Number,
    1083            typename CapacityMap, typename FlowMap>
    1084   class ResGraphWrapper :
    1085     public SubBidirGraphWrapper<
    1086     Graph,
    1087     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    1088     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
    1089   public:
    1090     typedef SubBidirGraphWrapper<
    1091       Graph,
    1092       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    1093       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
    1094   protected:
    1095     const CapacityMap* capacity;
    1096     FlowMap* flow;
    1097     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
    1098     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
    1099     ResGraphWrapper() : Parent(),
    1100                         capacity(0), flow(0) { }
    1101     void setCapacityMap(const CapacityMap& _capacity) {
    1102       capacity=&_capacity;
    1103       forward_filter.setCapacity(_capacity);
    1104       backward_filter.setCapacity(_capacity);
    1105     }
    1106     void setFlowMap(FlowMap& _flow) {
    1107       flow=&_flow;
    1108       forward_filter.setFlow(_flow);
    1109       backward_filter.setFlow(_flow);
    1110     }
    1111   public:
    1112     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
    1113                        FlowMap& _flow) :
    1114       Parent(), capacity(&_capacity), flow(&_flow),
    1115       forward_filter(/*_graph,*/ _capacity, _flow),
    1116       backward_filter(/*_graph,*/ _capacity, _flow) {
    1117       Parent::setGraph(_graph);
    1118       Parent::setForwardFilterMap(forward_filter);
    1119       Parent::setBackwardFilterMap(backward_filter);
    1120     }
    1121 
    1122     typedef typename Parent::Edge Edge;
    1123 
    1124     void augment(const Edge& e, Number a) const {
    1125       if (Parent::forward(e)) 
    1126         flow->set(e, (*flow)[e]+a);
    1127       else 
    1128         flow->set(e, (*flow)[e]-a);
    1129     }
    1130 
    1131     /// \brief Residual capacity map.
    1132     ///
    1133     /// In generic residual graphs the residual capacity can be obtained
    1134     /// as a map.
    1135     class ResCap {
    1136     protected:
    1137       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
    1138     public:
    1139       typedef Number Value;
    1140       typedef Edge Key;
    1141       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
    1142              _res_graph) : res_graph(&_res_graph) { }
    1143       Number operator[](const Edge& e) const {
    1144         if (res_graph->forward(e))
    1145           return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
    1146         else
    1147           return (*(res_graph->flow))[e];
    1148       }
    1149     };
    1150 
    1151     //    KEEP_MAPS(Parent, ResGraphWrapper);
    1152   };
    1153 
    1154 
    1155 
    1156   template <typename _Graph, typename FirstOutEdgesMap>
    1157   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
    1158   public:
    1159     typedef _Graph Graph;
    1160     typedef GraphWrapperBase<_Graph> Parent;
    1161   protected:
    1162     FirstOutEdgesMap* first_out_edges;
    1163     ErasingFirstGraphWrapperBase() : Parent(),
    1164                                      first_out_edges(0) { }
    1165 
    1166     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
    1167       first_out_edges=&_first_out_edges;
    1168     }
    1169 
    1170   public:
    1171 
    1172     typedef typename Parent::Node Node;
    1173     typedef typename Parent::Edge Edge;
    1174 
    1175     void firstOut(Edge& i, const Node& n) const {
    1176       i=(*first_out_edges)[n];
    1177     }
    1178 
    1179     void erase(const Edge& e) const {
    1180       Node n=source(e);
    1181       Edge f=e;
    1182       Parent::nextOut(f);
    1183       first_out_edges->set(n, f);
    1184     }   
    1185   };
    1186 
    1187 
    1188   /// For blocking flows.
    1189 
    1190   ///\warning Graph wrappers are in even more experimental state than the other
    1191   ///parts of the lib. Use them at you own risk.
    1192   ///
    1193   /// This graph wrapper is used for on-the-fly
    1194   /// Dinits blocking flow computations.
    1195   /// For each node, an out-edge is stored which is used when the
    1196   /// \code
    1197   /// OutEdgeIt& first(OutEdgeIt&, const Node&)
    1198   /// \endcode
    1199   /// is called.
    1200   ///
    1201   /// \author Marton Makai
    1202   template <typename _Graph, typename FirstOutEdgesMap>
    1203   class ErasingFirstGraphWrapper :
    1204     public IterableGraphExtender<
    1205     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
    1206   public:
    1207     typedef _Graph Graph;
    1208     typedef IterableGraphExtender<
    1209       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
    1210     ErasingFirstGraphWrapper(Graph& _graph,
    1211                              FirstOutEdgesMap& _first_out_edges) {
    1212       setGraph(_graph);
    1213       setFirstOutEdgesMap(_first_out_edges);
    1214     }
    1215 
    1216   };
    1217 
    1218   ///@}
    1219 
    1220 } //namespace lemon
    1221 
    1222 #endif //LEMON_GRAPH_WRAPPER_H
    1223 
     6   The main parts of LEMON are the different graph structures,
     7   generic graph algorithms, graph concepts which couple these, and
     8   graph wrappers. While the previous ones are more or less clear, the
     9   latter notion needs further explanation.
     10   Graph wrappers are graph classes which serve for considering graph
     11   structures in different ways. A short example makes the notion much
     12   clearer.
     13   Suppose that we have an instance \c g of a directed graph
     14   type say \c ListGraph and an algorithm
     15   \code template<typename Graph> int algorithm(const Graph&); \endcode
     16   is needed to run on the reversely oriented graph.
     17   It may be expensive (in time or in memory usage) to copy
     18   \c g with the reverse orientation.
     19   Thus, a wrapper class
     20   \code template<typename Graph> class RevGraphWrapper; \endcode is used.
     21   The code looks as follows
     22   \code
     23   ListGraph g;
     24   RevGraphWrapper<ListGraph> rgw(g);
     25   int result=algorithm(rgw);
     26   \endcode
     27   After running the algorithm, the original graph \c g
     28   remains untouched. Thus the graph wrapper used above is to consider the
     29   original graph with reverse orientation.
     30   This techniques gives rise to an elegant code, and
     31   based on stable graph wrappers, complex algorithms can be
     32   implemented easily.
     33   In flow, circulation and bipartite matching problems, the residual
     34   graph is of particular importance. Combining a wrapper implementing
     35   this, shortest path algorithms and minimum mean cycle algorithms,
     36   a range of weighted and cardinality optimization algorithms can be
     37   obtained. For lack of space, for other examples,
     38   the interested user is referred to the detailed documentation of graph
     39   wrappers.
     40   The behavior of graph wrappers can be very different. Some of them keep
     41   capabilities of the original graph while in other cases this would be
     42   meaningless. This means that the concepts that they are a model of depend
     43   on the graph wrapper, and the wrapped graph(s).
     44   If an edge of \c rgw is deleted, this is carried out by
     45   deleting the corresponding edge of \c g. But for a residual
     46   graph, this operation has no sense.
     47   Let we stand one more example here to simplify your work.
     48   wrapper class
     49   \code template<typename Graph> class RevGraphWrapper; \endcode
     50   has constructor
     51   <tt> RevGraphWrapper(Graph& _g)</tt>.
     52   This means that in a situation,
     53   when a <tt> const ListGraph& </tt> reference to a graph is given,
     54   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
     55   \code
     56   int algorithm1(const ListGraph& g) {
     57   RevGraphWrapper<const ListGraph> rgw(g);
     58   return algorithm2(rgw);
     59   }
     60   \endcode
     61*/
Note: See TracChangeset for help on using the changeset viewer.