Context Navigation

← Previous Change
Next Change →

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

Timestamp:

02/23/05 23:00:05 (20 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

File:

: 1 copied

doc/gwrappers.dox (copied) (copied from src/lemon/graph_wrapper.h) (1 diff)

Legend:

: Unmodified
: Added
: Removed

doc/gwrappers.dox

-                      r1164
+                      r1172
+/* -*- C++ -*-
+ * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+#ifndef LEMON_GRAPH_WRAPPER_H
+#define LEMON_GRAPH_WRAPPER_H
+///\ingroup gwrappers
+///\file
+///\brief Several graph wrappers.
+///
+///This file contains several useful graph wrapper functions.
+///
+///\author Marton Makai
+#include <lemon/invalid.h>
+#include <lemon/maps.h>
+#include <lemon/iterable_graph_extender.h>
+#include <iostream>
+namespace lemon {
+  // Graph wrappers
+  /*! \addtogroup gwrappers
+    The main parts of LEMON are the different graph structures,
+    generic graph algorithms, graph concepts which couple these, and
+    graph wrappers. While the previous ones are more or less clear, the
+    latter notion needs further explanation.
+    Graph wrappers are graph classes which serve for considering graph
+    structures in different ways. A short example makes the notion much
+    clearer.
+    Suppose that we have an instance \c g of a directed graph
+    type say \c ListGraph and an algorithm
+    \code template<typename Graph> int algorithm(const Graph&); \endcode
+    is needed to run on the reversely oriented graph.
+    It may be expensive (in time or in memory usage) to copy
+    \c g with the reverse orientation.
+    Thus, a wrapper class
+    \code template<typename Graph> class RevGraphWrapper; \endcode is used.
+    The code looks as follows
+    \code
+    ListGraph g;
+    RevGraphWrapper<ListGraph> rgw(g);
+    int result=algorithm(rgw);
+    \endcode
+    After running the algorithm, the original graph \c g
+    remains untouched. Thus the graph wrapper used above is to consider the
+    original graph with reverse orientation.
+    This techniques gives rise to an elegant code, and
+    based on stable graph wrappers, complex algorithms can be
+    implemented easily.
+    In flow, circulation and bipartite matching problems, the residual
+    graph is of particular importance. Combining a wrapper implementing
+    this, shortest path algorithms and minimum mean cycle algorithms,
+    a range of weighted and cardinality optimization algorithms can be
+    obtained. For lack of space, for other examples,
+    the interested user is referred to the detailed documentation of graph
+    wrappers.
+    The behavior of graph wrappers can be very different. Some of them keep
+    capabilities of the original graph while in other cases this would be
+    meaningless. This means that the concepts that they are a model of depend
+    on the graph wrapper, and the wrapped graph(s).
+    If an edge of \c rgw is deleted, this is carried out by
+    deleting the corresponding edge of \c g. But for a residual
+    graph, this operation has no sense.
+    Let we stand one more example here to simplify your work.
+    wrapper class
+    \code template<typename Graph> class RevGraphWrapper; \endcode
+    has constructor
+    <tt> RevGraphWrapper(Graph& _g)</tt>.
+    This means that in a situation,
+    when a <tt> const ListGraph& </tt> reference to a graph is given,
+    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
+    \code
+    int algorithm1(const ListGraph& g) {
+    RevGraphWrapper<const ListGraph> rgw(g);
+    return algorithm2(rgw);
+    }
+    \endcode
+    \addtogroup gwrappers
+    @{
+    Base type for the Graph Wrappers
+    \warning Graph wrappers are in even more experimental state than the other
+    parts of the lib. Use them at you own risk.
+    This is the base type for most of LEMON graph wrappers.
+    This class implements a trivial graph wrapper i.e. it only wraps the
+    functions and types of the graph. The purpose of this class is to
+    make easier implementing graph wrappers. E.g. if a wrapper is
+    considered which differs from the wrapped graph only in some of its
+    functions or types, then it can be derived from GraphWrapper, and only the
+    differences should be implemented.
+    \author Marton Makai
+  */
+  template<typename _Graph>
+  class GraphWrapperBase {
+  public:
+    typedef _Graph Graph;
+    /// \todo Is it needed?
+    typedef Graph BaseGraph;
+    typedef Graph ParentGraph;
+  protected:
+    Graph* graph;
+    GraphWrapperBase() : graph(0) { }
+    void setGraph(Graph& _graph) { graph=&_graph; }
+  public:
+    GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+/**
+   @defgroup gwrappers Wrapper Classes for Graphs
+   \brief This group contains several wrapper classes for graphs
+   @ingroup graphs
+    void first(Node& i) const { graph->first(i); }
+    void first(Edge& i) const { graph->first(i); }
+    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
+    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
+    void next(Node& i) const { graph->next(i); }
+    void next(Edge& i) const { graph->next(i); }
+    void nextIn(Edge& i) const { graph->nextIn(i); }
+    void nextOut(Edge& i) const { graph->nextOut(i); }
+    Node source(const Edge& e) const { return graph->source(e); }
+    Node target(const Edge& e) const { return graph->target(e); }
+    int nodeNum() const { return graph->nodeNum(); }
+    int edgeNum() const { return graph->edgeNum(); }
+    Node addNode() const { return Node(graph->addNode()); }
+    Edge addEdge(const Node& source, const Node& target) const {
+      return Edge(graph->addEdge(source, target)); }
+    void erase(const Node& i) const { graph->erase(i); }
+    void erase(const Edge& i) const { graph->erase(i); }
+    void clear() const { graph->clear(); }
+    bool forward(const Edge& e) const { return graph->forward(e); }
+    bool backward(const Edge& e) const { return graph->backward(e); }
+    int id(const Node& v) const { return graph->id(v); }
+    int id(const Edge& e) const { return graph->id(e); }
+    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
+    template <typename _Value>
+    class NodeMap : public _Graph::template NodeMap<_Value> {
+    public:
+      typedef typename _Graph::template NodeMap<_Value> Parent;
+      NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
+      NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
+      : Parent(*gw.graph, value) { }
+    };
+    template <typename _Value>
+    class EdgeMap : public _Graph::template EdgeMap<_Value> {
+    public:
+      typedef typename _Graph::template EdgeMap<_Value> Parent;
+      EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
+      EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
+      : Parent(*gw.graph, value) { }
+    };
+  };
+  template <typename _Graph>
+  class GraphWrapper :
+    public IterableGraphExtender<GraphWrapperBase<_Graph> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
+  protected:
+    GraphWrapper() : Parent() { }
+  public:
+    GraphWrapper(Graph& _graph) { setGraph(_graph); }
+  };
+  template <typename _Graph>
+  class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphWrapperBase<_Graph> Parent;
+  protected:
+    RevGraphWrapperBase() : Parent() { }
+  public:
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    using Parent::first;
+    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
+    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
+    using Parent::next;
+    void nextIn(Edge& i) const { Parent::nextOut(i); }
+    void nextOut(Edge& i) const { Parent::nextIn(i); }
+    Node source(const Edge& e) const { return Parent::target(e); }
+    Node target(const Edge& e) const { return Parent::source(e); }
+  };
+  /// A graph wrapper which reverses the orientation of the edges.
+  ///\warning Graph wrappers are in even more experimental state than the other
+  ///parts of the lib. Use them at you own risk.
+  ///
+  /// Let \f$G=(V, A)\f$ be a directed graph and
+  /// suppose that a graph instange \c g of type
+  /// \c ListGraph implements \f$G\f$.
+  /// \code
+  /// ListGraph g;
+  /// \endcode
+  /// For each directed edge
+  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
+  /// reversing its orientation.
+  /// Then RevGraphWrapper implements the graph structure with node-set
+  /// \f$V\f$ and edge-set
+  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
+  /// reversing the orientation of its edges. The following code shows how
+  /// such an instance can be constructed.
+  /// \code
+  /// RevGraphWrapper<ListGraph> gw(g);
+  /// \endcode
+  ///\author Marton Makai
+  template<typename _Graph>
+  class RevGraphWrapper :
+    public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableGraphExtender<
+      RevGraphWrapperBase<_Graph> > Parent;
+  protected:
+    RevGraphWrapper() { }
+  public:
+    RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
+  };
+  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphWrapperBase<_Graph> Parent;
+  protected:
+    NodeFilterMap* node_filter_map;
+    EdgeFilterMap* edge_filter_map;
+    SubGraphWrapperBase() : Parent(),
+                            node_filter_map(0), edge_filter_map(0) { }
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
+      edge_filter_map=&_edge_filter_map;
+    }
+  public:
+//     SubGraphWrapperBase(Graph& _graph,
+//                      NodeFilterMap& _node_filter_map,
+//                      EdgeFilterMap& _edge_filter_map) :
+//       Parent(&_graph),
+//       node_filter_map(&node_filter_map),
+//       edge_filter_map(&edge_filter_map) { }
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    void first(Node& i) const {
+      Parent::first(i);
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
+    }
+    void first(Edge& i) const {
+      Parent::first(i);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
+    }
+    void firstIn(Edge& i, const Node& n) const {
+      Parent::firstIn(i, n);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
+    }
+    void firstOut(Edge& i, const Node& n) const {
+      Parent::firstOut(i, n);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
+    }
+    void next(Node& i) const {
+      Parent::next(i);
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
+    }
+    void next(Edge& i) const {
+      Parent::next(i);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
+    }
+    void nextIn(Edge& i) const {
+      Parent::nextIn(i);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
+    }
+    void nextOut(Edge& i) const {
+      Parent::nextOut(i);
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
+    }
+    /// This function hides \c n in the graph, i.e. the iteration
+    /// jumps over it. This is done by simply setting the value of \c n
+    /// to be false in the corresponding node-map.
+    void hide(const Node& n) const { node_filter_map->set(n, false); }
+    /// This function hides \c e in the graph, i.e. the iteration
+    /// jumps over it. This is done by simply setting the value of \c e
+    /// to be false in the corresponding edge-map.
+    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
+    /// The value of \c n is set to be true in the node-map which stores
+    /// hide information. If \c n was hidden previuosly, then it is shown
+    /// again
+     void unHide(const Node& n) const { node_filter_map->set(n, true); }
+    /// The value of \c e is set to be true in the edge-map which stores
+    /// hide information. If \c e was hidden previuosly, then it is shown
+    /// again
+    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
+    /// Returns true if \c n is hidden.
+    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
+    /// Returns true if \c n is hidden.
+    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
+    /// \warning This is a linear time operation and works only if s
+    /// \c Graph::NodeIt is defined.
+    /// \todo assign tags.
+    int nodeNum() const {
+      int i=0;
+      Node n;
+      for (first(n); n!=INVALID; next(n)) ++i;
+      return i;
+    }
+    /// \warning This is a linear time operation and works only if
+    /// \c Graph::EdgeIt is defined.
+    /// \todo assign tags.
+    int edgeNum() const {
+      int i=0;
+      Edge e;
+      for (first(e); e!=INVALID; next(e)) ++i;
+      return i;
+    }
+  };
+  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
+  \warning Graph wrappers are in even more experimental state than the other
+  parts of the lib. Use them at you own risk.
+  This wrapper shows a graph with filtered node-set and
+  edge-set.
+  Given a bool-valued map on the node-set and one on
+  the edge-set of the graph, the iterators show only the objects
+  having true value. We have to note that this does not mean that an
+  induced subgraph is obtained, the node-iterator cares only the filter
+  on the node-set, and the edge-iterators care only the filter on the
+  edge-set.
+  \code
+  typedef SmartGraph Graph;
+  Graph g;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+  Node u=g.addNode(); //node of id 0
+  Node v=g.addNode(); //node of id 1
+  Node e=g.addEdge(u, v); //edge of id 0
+  Node f=g.addEdge(v, u); //edge of id 1
+  Graph::NodeMap<bool> nm(g, true);
+  nm.set(u, false);
+  Graph::EdgeMap<bool> em(g, true);
+  em.set(e, false);
+  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
+  SubGW gw(g, nm, em);
+  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
+  std::cout << ":-)" << std::endl;
+  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
+  \endcode
+  The output of the above code is the following.
+  \code
+  :-)
+  \endcode
+  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
+  \c Graph::Node that is why \c g.id(n) can be applied.
+  For other examples see also the documentation of NodeSubGraphWrapper and
+  EdgeSubGraphWrapper.
+  \author Marton Makai
+  */
+  template<typename _Graph, typename NodeFilterMap,
+           typename EdgeFilterMap>
+  class SubGraphWrapper :
+    public IterableGraphExtender<
+    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableGraphExtender<
+      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
+  protected:
+    SubGraphWrapper() { }
+  public:
+    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
+                    EdgeFilterMap& _edge_filter_map) {
+      setGraph(_graph);
+      setNodeFilterMap(_node_filter_map);
+      setEdgeFilterMap(_edge_filter_map);
+    }
+  };
+  /*! \brief A wrapper for hiding nodes from a graph.
+  \warning Graph wrappers are in even more experimental state than the other
+  parts of the lib. Use them at you own risk.
+  A wrapper for hiding nodes from a graph.
+  This wrapper specializes SubGraphWrapper in the way that only the node-set
+  can be filtered. Note that this does not mean of considering induced
+  subgraph, the edge-iterators consider the original edge-set.
+  \author Marton Makai
+  */
+  template<typename Graph, typename NodeFilterMap>
+  class NodeSubGraphWrapper :
+    public SubGraphWrapper<Graph, NodeFilterMap,
+                           ConstMap<typename Graph::Edge,bool> > {
+  public:
+    typedef SubGraphWrapper<Graph, NodeFilterMap,
+                            ConstMap<typename Graph::Edge,bool> > Parent;
+  protected:
+    ConstMap<typename Graph::Edge, bool> const_true_map;
+  public:
+    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
+      Parent(), const_true_map(true) {
+      Parent::setGraph(_graph);
+      Parent::setNodeFilterMap(_node_filter_map);
+      Parent::setEdgeFilterMap(const_true_map);
+    }
+  };
+  /*! \brief A wrapper for hiding edges from a graph.
+  \warning Graph wrappers are in even more experimental state than the other
+  parts of the lib. Use them at you own risk.
+  A wrapper for hiding edges from a graph.
+  This wrapper specializes SubGraphWrapper in the way that only the edge-set
+  can be filtered. The usefulness of this wrapper is demonstrated in the
+  problem of searching a maximum number of edge-disjoint shortest paths
+  between
+  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
+  non-negative edge-lengths. Note that
+  the comprehension of the presented solution
+  need's some knowledge from elementary combinatorial optimization.
+  If a single shortest path is to be
+  searched between two nodes \c s and \c t, then this can be done easily by
+  applying the Dijkstra algorithm class. What happens, if a maximum number of
+  edge-disjoint shortest paths is to be computed. It can be proved that an
+  edge can be in a shortest path if and only if it is tight with respect to
+  the potential function computed by Dijkstra. Moreover, any path containing
+  only such edges is a shortest one. Thus we have to compute a maximum number
+  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
+  all the tight edges. The computation will be demonstrated on the following
+  graph, which is read from a dimacs file.
+  \dot
+  digraph lemon_dot_example {
+  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
+  n0 [ label="0 (s)" ];
+  n1 [ label="1" ];
+  n2 [ label="2" ];
+  n3 [ label="3" ];
+  n4 [ label="4" ];
+  n5 [ label="5" ];
+  n6 [ label="6 (t)" ];
+  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
+  n5 ->  n6 [ label="9, length:4" ];
+  n4 ->  n6 [ label="8, length:2" ];
+  n3 ->  n5 [ label="7, length:1" ];
+  n2 ->  n5 [ label="6, length:3" ];
+  n2 ->  n6 [ label="5, length:5" ];
+  n2 ->  n4 [ label="4, length:2" ];
+  n1 ->  n4 [ label="3, length:3" ];
+  n0 ->  n3 [ label="2, length:1" ];
+  n0 ->  n2 [ label="1, length:2" ];
+  n0 ->  n1 [ label="0, length:3" ];
+  }
+  \enddot
+  \code
+  Graph g;
+  Node s, t;
+  LengthMap length(g);
+  readDimacs(std::cin, g, length, s, t);
+  cout << "edges with lengths (of form id, source--length->target): " << endl;
+  for(EdgeIt e(g); e!=INVALID; ++e)
+    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
+         << length[e] << "->" << g.id(g.target(e)) << endl;
+  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
+  \endcode
+  Next, the potential function is computed with Dijkstra.
+  \code
+  typedef Dijkstra<Graph, LengthMap> Dijkstra;
+  Dijkstra dijkstra(g, length);
+  dijkstra.run(s);
+  \endcode
+  Next, we consrtruct a map which filters the edge-set to the tight edges.
+  \code
+  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
+    TightEdgeFilter;
+  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
+  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
+  SubGW gw(g, tight_edge_filter);
+  \endcode
+  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
+  with a max flow algorithm Preflow.
+  \code
+  ConstMap<Edge, int> const_1_map(1);
+  Graph::EdgeMap<int> flow(g, 0);
+  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
+    preflow(gw, s, t, const_1_map, flow);
+  preflow.run();
+  \endcode
+  Last, the output is:
+  \code
+  cout << "maximum number of edge-disjoint shortest path: "
+       << preflow.flowValue() << endl;
+  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
+       << endl;
+  for(EdgeIt e(g); e!=INVALID; ++e)
+    if (flow[e])
+      cout << " " << g.id(g.source(e)) << "--"
+           << length[e] << "->" << g.id(g.target(e)) << endl;
+  \endcode
+  The program has the following (expected :-)) output:
+  \code
+  edges with lengths (of form id, source--length->target):
+, 5--4->6
+, 4--2->6
+, 3--1->5
+, 2--3->5
+, 2--5->6
+, 2--2->4
+, 1--3->4
+, 0--1->3
+, 0--2->2
+, 0--3->1
+  s: 0 t: 6
+  maximum number of edge-disjoint shortest path: 2
+  edges of the maximum number of edge-disjoint shortest s-t paths:
+, 5--4->6
+, 4--2->6
+, 3--1->5
+, 2--2->4
+, 0--1->3
+, 0--2->2
+  \endcode
+  \author Marton Makai
+  */
+  template<typename Graph, typename EdgeFilterMap>
+  class EdgeSubGraphWrapper :
+    public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
+                           EdgeFilterMap> {
+  public:
+    typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
+                            EdgeFilterMap> Parent;
+  protected:
+    ConstMap<typename Graph::Node, bool> const_true_map;
+  public:
+    EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
+      Parent(), const_true_map(true) {
+      Parent::setGraph(_graph);
+      Parent::setNodeFilterMap(const_true_map);
+      Parent::setEdgeFilterMap(_edge_filter_map);
+    }
+  };
+  template<typename Graph>
+  class UndirGraphWrapper : public GraphWrapper<Graph> {
+  public:
+    typedef GraphWrapper<Graph> Parent;
+  protected:
+    UndirGraphWrapper() : GraphWrapper<Graph>() { }
+  public:
+    typedef typename GraphWrapper<Graph>::Node Node;
+    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+    typedef typename GraphWrapper<Graph>::Edge Edge;
+    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
+    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
+    class OutEdgeIt {
+      friend class UndirGraphWrapper<Graph>;
+      bool out_or_in; //true iff out
+      typename Graph::OutEdgeIt out;
+      typename Graph::InEdgeIt in;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const Invalid& i) : Edge(i) { }
+      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
+        out_or_in=true; _G.graph->first(out, _n);
+        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
+      }
+      operator Edge() const {
+        if (out_or_in) return Edge(out); else return Edge(in);
+      }
+    };
+    typedef OutEdgeIt InEdgeIt;
+    using GraphWrapper<Graph>::first;
+    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
+      i=OutEdgeIt(*this, p); return i;
+    }
+    using GraphWrapper<Graph>::next;
+    OutEdgeIt& next(OutEdgeIt& e) const {
+      if (e.out_or_in) {
+        typename Graph::Node n=this->graph->source(e.out);
+        this->graph->next(e.out);
+        if (!this->graph->valid(e.out)) {
+          e.out_or_in=false; this->graph->first(e.in, n); }
+      } else {
+        this->graph->next(e.in);
+      }
+      return e;
+    }
+    Node aNode(const OutEdgeIt& e) const {
+      if (e.out_or_in) return this->graph->source(e); else
+        return this->graph->target(e); }
+    Node bNode(const OutEdgeIt& e) const {
+      if (e.out_or_in) return this->graph->target(e); else
+        return this->graph->source(e); }
+    //    KEEP_MAPS(Parent, UndirGraphWrapper);
+  };
+//   /// \brief An undirected graph template.
+//   ///
+//   ///\warning Graph wrappers are in even more experimental state than the other
+//   ///parts of the lib. Use them at your own risk.
+//   ///
+//   /// An undirected graph template.
+//   /// This class works as an undirected graph and a directed graph of
+//   /// class \c Graph is used for the physical storage.
+//   /// \ingroup graphs
+  template<typename Graph>
+  class UndirGraph : public UndirGraphWrapper<Graph> {
+    typedef UndirGraphWrapper<Graph> Parent;
+  protected:
+    Graph gr;
+  public:
+    UndirGraph() : UndirGraphWrapper<Graph>() {
+      Parent::setGraph(gr);
+    }
+    //    KEEP_MAPS(Parent, UndirGraph);
+  };
+  template <typename _Graph,
+            typename ForwardFilterMap, typename BackwardFilterMap>
+  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphWrapperBase<_Graph> Parent;
+  protected:
+    ForwardFilterMap* forward_filter;
+    BackwardFilterMap* backward_filter;
+    SubBidirGraphWrapperBase() : Parent(),
+                                 forward_filter(0), backward_filter(0) { }
+    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
+      forward_filter=&_forward_filter;
+    }
+    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
+      backward_filter=&_backward_filter;
+    }
+  public:
+//     SubGraphWrapperBase(Graph& _graph,
+//                      NodeFilterMap& _node_filter_map,
+//                      EdgeFilterMap& _edge_filter_map) :
+//       Parent(&_graph),
+//       node_filter_map(&node_filter_map),
+//       edge_filter_map(&edge_filter_map) { }
+    typedef typename Parent::Node Node;
+    typedef typename _Graph::Edge GraphEdge;
+    template <typename T> class EdgeMap;
+    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
+    /// _Graph::Edge. It contains an extra bool flag which is true
+    /// if and only if the
+    /// edge is the backward version of the original edge.
+    class Edge : public _Graph::Edge {
+      friend class SubBidirGraphWrapperBase<
+        Graph, ForwardFilterMap, BackwardFilterMap>;
+      template<typename T> friend class EdgeMap;
+    protected:
+      bool backward; //true, iff backward
+    public:
+      Edge() { }
+      /// \todo =false is needed, or causes problems?
+      /// If \c _backward is false, then we get an edge corresponding to the
+      /// original one, otherwise its oppositely directed pair is obtained.
+      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
+        _Graph::Edge(e), backward(_backward) { }
+      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
+      bool operator==(const Edge& v) const {
+        return (this->backward==v.backward &&
+                static_cast<typename _Graph::Edge>(*this)==
+                static_cast<typename _Graph::Edge>(v));
+      }
+      bool operator!=(const Edge& v) const {
+        return (this->backward!=v.backward ||
+                static_cast<typename _Graph::Edge>(*this)!=
+                static_cast<typename _Graph::Edge>(v));
+      }
+    };
+    void first(Node& i) const {
+      Parent::first(i);
+    }
+    void first(Edge& i) const {
+      Parent::first(i);
+      i.backward=false;
+      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+             !(*forward_filter)[i]) Parent::next(i);
+      if (*static_cast<GraphEdge*>(&i)==INVALID) {
+        Parent::first(i);
+        i.backward=true;
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::next(i);
+      }
+    }
+    void firstIn(Edge& i, const Node& n) const {
+      Parent::firstIn(i, n);
+      i.backward=false;
+      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+             !(*forward_filter)[i]) Parent::nextOut(i);
+      if (*static_cast<GraphEdge*>(&i)==INVALID) {
+        Parent::firstOut(i, n);
+        i.backward=true;
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::nextOut(i);
+      }
+    }
+    void firstOut(Edge& i, const Node& n) const {
+      Parent::firstOut(i, n);
+      i.backward=false;
+      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+             !(*forward_filter)[i]) Parent::nextOut(i);
+      if (*static_cast<GraphEdge*>(&i)==INVALID) {
+        Parent::firstIn(i, n);
+        i.backward=true;
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::nextIn(i);
+      }
+    }
+    void next(Node& i) const {
+      Parent::next(i);
+    }
+    void next(Edge& i) const {
+      if (!(i.backward)) {
+        Parent::next(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*forward_filter)[i]) Parent::next(i);
+        if (*static_cast<GraphEdge*>(&i)==INVALID) {
+          Parent::first(i);
+          i.backward=true;
+          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+                 !(*backward_filter)[i]) Parent::next(i);
+        }
+      } else {
+        Parent::next(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::next(i);
+      }
+    }
+    void nextIn(Edge& i) const {
+      if (!(i.backward)) {
+        Node n=Parent::target(i);
+        Parent::nextIn(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*forward_filter)[i]) Parent::nextIn(i);
+        if (*static_cast<GraphEdge*>(&i)==INVALID) {
+          Parent::firstOut(i, n);
+          i.backward=true;
+          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+                 !(*backward_filter)[i]) Parent::nextOut(i);
+        }
+      } else {
+        Parent::nextOut(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::nextOut(i);
+      }
+    }
+    void nextOut(Edge& i) const {
+      if (!(i.backward)) {
+        Node n=Parent::source(i);
+        Parent::nextOut(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*forward_filter)[i]) Parent::nextOut(i);
+        if (*static_cast<GraphEdge*>(&i)==INVALID) {
+          Parent::firstIn(i, n);
+          i.backward=true;
+          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+                 !(*backward_filter)[i]) Parent::nextIn(i);
+        }
+      } else {
+        Parent::nextIn(i);
+        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
+               !(*backward_filter)[i]) Parent::nextIn(i);
+      }
+    }
+    Node source(Edge e) const {
+      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
+    Node target(Edge e) const {
+      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
+    /// Gives back the opposite edge.
+    Edge opposite(const Edge& e) const {
+      Edge f=e;
+      f.backward=!f.backward;
+      return f;
+    }
+    /// \warning This is a linear time operation and works only if
+    /// \c Graph::EdgeIt is defined.
+    /// \todo hmm
+    int edgeNum() const {
+      int i=0;
+      Edge e;
+      for (first(e); e!=INVALID; next(e)) ++i;
+      return i;
+    }
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
+    template <typename T>
+    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
+    /// _Graph::EdgeMap one for the forward edges and
+    /// one for the backward edges.
+    class EdgeMap {
+      template <typename TT> friend class EdgeMap;
+      typename _Graph::template EdgeMap<T> forward_map, backward_map;
+    public:
+      typedef T Value;
+      typedef Edge Key;
+      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
+              ForwardFilterMap, BackwardFilterMap>& g) :
+        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
+      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
+              ForwardFilterMap, BackwardFilterMap>& g, T a) :
+        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
+      void set(Edge e, T a) {
+        if (!e.backward)
+          forward_map.set(e, a);
+        else
+          backward_map.set(e, a);
+      }
+//       typename _Graph::template EdgeMap<T>::ConstReference
+//       operator[](Edge e) const {
+//      if (!e.backward)
+//        return forward_map[e];
+//      else
+//        return backward_map[e];
+//       }
+//      typename _Graph::template EdgeMap<T>::Reference
+      T operator[](Edge e) const {
+        if (!e.backward)
+          return forward_map[e];
+        else
+          return backward_map[e];
+      }
+      void update() {
+        forward_map.update();
+        backward_map.update();
+      }
+    };
+  };
+  ///\brief A wrapper for composing a subgraph of a
+  /// bidirected graph made from a directed one.
+  ///
+  /// A wrapper for composing a subgraph of a
+  /// bidirected graph made from a directed one.
+  ///
+  ///\warning Graph wrappers are in even more experimental state than the other
+  ///parts of the lib. Use them at you own risk.
+  ///
+  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
+  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
+  /// reversing its orientation. We are given moreover two bool valued
+  /// maps on the edge-set,
+  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
+  /// SubBidirGraphWrapper implements the graph structure with node-set
+  /// \f$V\f$ and edge-set
+  /// \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$.
+  /// The purpose of writing + instead of union is because parallel
+  /// edges can arise. (Similarly, antiparallel edges also can arise).
+  /// In other words, a subgraph of the bidirected graph obtained, which
+  /// is given by orienting the edges of the original graph in both directions.
+  /// As the oppositely directed edges are logically different,
+  /// the maps are able to attach different values for them.
+  ///
+  /// An example for such a construction is \c RevGraphWrapper where the
+  /// forward_filter is everywhere false and the backward_filter is
+  /// everywhere true. We note that for sake of efficiency,
+  /// \c RevGraphWrapper is implemented in a different way.
+  /// But BidirGraphWrapper is obtained from
+  /// SubBidirGraphWrapper by considering everywhere true
+  /// valued maps both for forward_filter and backward_filter.
+  /// Finally, one of the most important applications of SubBidirGraphWrapper
+  /// is ResGraphWrapper, which stands for the residual graph in directed
+  /// flow and circulation problems.
+  /// As wrappers usually, the SubBidirGraphWrapper implements the
+  /// above mentioned graph structure without its physical storage,
+  /// that is the whole stuff is stored in constant memory.
+  template<typename _Graph,
+           typename ForwardFilterMap, typename BackwardFilterMap>
+  class SubBidirGraphWrapper :
+    public IterableGraphExtender<
+    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableGraphExtender<
+      SubBidirGraphWrapperBase<
+      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
+  protected:
+    SubBidirGraphWrapper() { }
+  public:
+    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
+                         BackwardFilterMap& _backward_filter) {
+      setGraph(_graph);
+      setForwardFilterMap(_forward_filter);
+      setBackwardFilterMap(_backward_filter);
+    }
+  };
+  ///\brief A wrapper for composing bidirected graph from a directed one.
+  ///
+  ///\warning Graph wrappers are in even more experimental state than the other
+  ///parts of the lib. Use them at you own risk.
+  ///
+  /// A wrapper for composing bidirected graph from a directed one.
+  /// A bidirected graph is composed over the directed one without physical
+  /// storage. As the oppositely directed edges are logically different ones
+  /// the maps are able to attach different values for them.
+  template<typename Graph>
+  class BidirGraphWrapper :
+    public SubBidirGraphWrapper<
+    Graph,
+    ConstMap<typename Graph::Edge, bool>,
+    ConstMap<typename Graph::Edge, bool> > {
+  public:
+    typedef  SubBidirGraphWrapper<
+      Graph,
+      ConstMap<typename Graph::Edge, bool>,
+      ConstMap<typename Graph::Edge, bool> > Parent;
+  protected:
+    ConstMap<typename Graph::Edge, bool> cm;
+    BidirGraphWrapper() : Parent(), cm(true) {
+      Parent::setForwardFilterMap(cm);
+      Parent::setBackwardFilterMap(cm);
+    }
+  public:
+    BidirGraphWrapper(Graph& _graph) : Parent() {
+      Parent::setGraph(_graph);
+      Parent::setForwardFilterMap(cm);
+      Parent::setBackwardFilterMap(cm);
+    }
+    int edgeNum() const {
+      return 2*this->graph->edgeNum();
+    }
+    //    KEEP_MAPS(Parent, BidirGraphWrapper);
+  };
+  template<typename Graph, typename Number,
+           typename CapacityMap, typename FlowMap>
+  class ResForwardFilter {
+    //    const Graph* graph;
+    const CapacityMap* capacity;
+    const FlowMap* flow;
+  public:
+    ResForwardFilter(/*const Graph& _graph, */
+                     const CapacityMap& _capacity, const FlowMap& _flow) :
+      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
+    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
+    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
+    void setFlow(const FlowMap& _flow) { flow=&_flow; }
+    bool operator[](const typename Graph::Edge& e) const {
+      return (Number((*flow)[e]) < Number((*capacity)[e]));
+    }
+  };
+  template<typename Graph, typename Number,
+           typename CapacityMap, typename FlowMap>
+  class ResBackwardFilter {
+    const CapacityMap* capacity;
+    const FlowMap* flow;
+  public:
+    ResBackwardFilter(/*const Graph& _graph,*/
+                      const CapacityMap& _capacity, const FlowMap& _flow) :
+      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
+    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
+    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
+    void setFlow(const FlowMap& _flow) { flow=&_flow; }
+    bool operator[](const typename Graph::Edge& e) const {
+      return (Number(0) < Number((*flow)[e]));
+    }
+  };
+  /// A wrapper for composing the residual graph for directed flow and circulation problems.
+  ///\warning Graph wrappers are in even more experimental state than the other
+  ///parts of the lib. Use them at you own risk.
+  ///
+  /// A wrapper for composing the residual graph for directed flow and circulation problems.
+  template<typename Graph, typename Number,
+           typename CapacityMap, typename FlowMap>
+  class ResGraphWrapper :
+    public SubBidirGraphWrapper<
+    Graph,
+    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
+    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
+  public:
+    typedef SubBidirGraphWrapper<
+      Graph,
+      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
+      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
+  protected:
+    const CapacityMap* capacity;
+    FlowMap* flow;
+    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
+    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
+    ResGraphWrapper() : Parent(),
+                        capacity(0), flow(0) { }
+    void setCapacityMap(const CapacityMap& _capacity) {
+      capacity=&_capacity;
+      forward_filter.setCapacity(_capacity);
+      backward_filter.setCapacity(_capacity);
+    }
+    void setFlowMap(FlowMap& _flow) {
+      flow=&_flow;
+      forward_filter.setFlow(_flow);
+      backward_filter.setFlow(_flow);
+    }
+  public:
+    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
+                       FlowMap& _flow) :
+      Parent(), capacity(&_capacity), flow(&_flow),
+      forward_filter(/*_graph,*/ _capacity, _flow),
+      backward_filter(/*_graph,*/ _capacity, _flow) {
+      Parent::setGraph(_graph);
+      Parent::setForwardFilterMap(forward_filter);
+      Parent::setBackwardFilterMap(backward_filter);
+    }
+    typedef typename Parent::Edge Edge;
+    void augment(const Edge& e, Number a) const {
+      if (Parent::forward(e))
+        flow->set(e, (*flow)[e]+a);
+      else
+        flow->set(e, (*flow)[e]-a);
+    }
+    /// \brief Residual capacity map.
+    ///
+    /// In generic residual graphs the residual capacity can be obtained
+    /// as a map.
+    class ResCap {
+    protected:
+      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
+    public:
+      typedef Number Value;
+      typedef Edge Key;
+      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
+             _res_graph) : res_graph(&_res_graph) { }
+      Number operator[](const Edge& e) const {
+        if (res_graph->forward(e))
+          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
+        else
+          return (*(res_graph->flow))[e];
+      }
+    };
+    //    KEEP_MAPS(Parent, ResGraphWrapper);
+  };
+  template <typename _Graph, typename FirstOutEdgesMap>
+  class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphWrapperBase<_Graph> Parent;
+  protected:
+    FirstOutEdgesMap* first_out_edges;
+    ErasingFirstGraphWrapperBase() : Parent(),
+                                     first_out_edges(0) { }
+    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
+      first_out_edges=&_first_out_edges;
+    }
+  public:
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    void firstOut(Edge& i, const Node& n) const {
+      i=(*first_out_edges)[n];
+    }
+    void erase(const Edge& e) const {
+      Node n=source(e);
+      Edge f=e;
+      Parent::nextOut(f);
+      first_out_edges->set(n, f);
+    }
+  };
+  /// For blocking flows.
+  ///\warning Graph wrappers are in even more experimental state than the other
+  ///parts of the lib. Use them at you own risk.
+  ///
+  /// This graph wrapper is used for on-the-fly
+  /// Dinits blocking flow computations.
+  /// For each node, an out-edge is stored which is used when the
+  /// \code
+  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
+  /// \endcode
+  /// is called.
+  ///
+  /// \author Marton Makai
+  template <typename _Graph, typename FirstOutEdgesMap>
+  class ErasingFirstGraphWrapper :
+    public IterableGraphExtender<
+    ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
+  public:
+    typedef _Graph Graph;
+    typedef IterableGraphExtender<
+      ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
+    ErasingFirstGraphWrapper(Graph& _graph,
+                             FirstOutEdgesMap& _first_out_edges) {
+      setGraph(_graph);
+      setFirstOutEdgesMap(_first_out_edges);
+    }
+  };
+  ///@}
+} //namespace lemon
+#endif //LEMON_GRAPH_WRAPPER_H
+   The main parts of LEMON are the different graph structures,
+   generic graph algorithms, graph concepts which couple these, and
+   graph wrappers. While the previous ones are more or less clear, the
+   latter notion needs further explanation.
+   Graph wrappers are graph classes which serve for considering graph
+   structures in different ways. A short example makes the notion much
+   clearer.
+   Suppose that we have an instance \c g of a directed graph
+   type say \c ListGraph and an algorithm
+   \code template<typename Graph> int algorithm(const Graph&); \endcode
+   is needed to run on the reversely oriented graph.
+   It may be expensive (in time or in memory usage) to copy
+   \c g with the reverse orientation.
+   Thus, a wrapper class
+   \code template<typename Graph> class RevGraphWrapper; \endcode is used.
+   The code looks as follows
+   \code
+   ListGraph g;
+   RevGraphWrapper<ListGraph> rgw(g);
+   int result=algorithm(rgw);
+   \endcode
+   After running the algorithm, the original graph \c g
+   remains untouched. Thus the graph wrapper used above is to consider the
+   original graph with reverse orientation.
+   This techniques gives rise to an elegant code, and
+   based on stable graph wrappers, complex algorithms can be
+   implemented easily.
+   In flow, circulation and bipartite matching problems, the residual
+   graph is of particular importance. Combining a wrapper implementing
+   this, shortest path algorithms and minimum mean cycle algorithms,
+   a range of weighted and cardinality optimization algorithms can be
+   obtained. For lack of space, for other examples,
+   the interested user is referred to the detailed documentation of graph
+   wrappers.
+   The behavior of graph wrappers can be very different. Some of them keep
+   capabilities of the original graph while in other cases this would be
+   meaningless. This means that the concepts that they are a model of depend
+   on the graph wrapper, and the wrapped graph(s).
+   If an edge of \c rgw is deleted, this is carried out by
+   deleting the corresponding edge of \c g. But for a residual
+   graph, this operation has no sense.
+   Let we stand one more example here to simplify your work.
+   wrapper class
+   \code template<typename Graph> class RevGraphWrapper; \endcode
+   has constructor
+   <tt> RevGraphWrapper(Graph& _g)</tt>.
+   This means that in a situation,
+   when a <tt> const ListGraph& </tt> reference to a graph is given,
+   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
+   \code
+   int algorithm1(const ListGraph& g) {
+   RevGraphWrapper<const ListGraph> rgw(g);
+   return algorithm2(rgw);
+   }
+   \endcode
+*/

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

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

Legend:

doc/gwrappers.dox

Download in other formats: