source: lemon-0.x/src/lemon/graph_wrapper.h @ 986:e997802b855c

/* -*- C++ -*-
 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2004 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/map_defines.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) { }
    GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
 
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
   
    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); }
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
//       i=OutEdgeIt(*this, p); return i;
//     }
//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
//       i=InEdgeIt(*this, p); return i;
//     }
//     EdgeIt& first(EdgeIt& i) const { 
//       i=EdgeIt(*this); return i;
//     }

    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); }
//     Node source(const Edge& e) const { 
//       return Node(graph->source(static_cast<typename Graph::Edge>(e))); }
//     Node target(const Edge& e) const { 
//       return Node(graph->target(static_cast<typename Graph::Edge>(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); }
  };

  /// 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 GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    RevGraphWrapper() : GraphWrapper<Graph>() { }
  public:
    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
    //because this does not work is some of them are not defined in the 
    //original graph. The problem with this is that typedef-ed stuff 
    //are instantiated in c++.
    class OutEdgeIt : public Edge { 
      const RevGraphWrapper<Graph>* gw;
      friend class GraphWrapper<Graph>;
     public:
      OutEdgeIt() { }
      OutEdgeIt(Invalid i) : Edge(i) { }
      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
        Edge(e), gw(&_gw) { }
      OutEdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };
    class InEdgeIt : public Edge { 
      const RevGraphWrapper<Graph>* gw;
      friend class GraphWrapper<Graph>;
     public:
      InEdgeIt() { }
      InEdgeIt(Invalid i) : Edge(i) { }
      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
        Edge(e), gw(&_gw) { }
      InEdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };

    using GraphWrapper<Graph>::first;
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }

    Node source(const Edge& e) const { 
      return GraphWrapper<Graph>::target(e); }
    Node target(const Edge& e) const { 
      return GraphWrapper<Graph>::source(e); }

    //    KEEP_MAPS(Parent, RevGraphWrapper);

  };



  /*! \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
  1
  :-)
  1
  \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 GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent;
  protected:
    NodeFilterMap* node_filter_map;
    EdgeFilterMap* edge_filter_map;

    SubGraphWrapper() : GraphWrapper<Graph>(), 
                        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:
    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
                    EdgeFilterMap& _edge_filter_map) : 
      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
      edge_filter_map(&_edge_filter_map) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    class NodeIt : public Node { 
      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    public:
      NodeIt() { }
      NodeIt(Invalid i) : Node(i) { }
      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 
        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 
        while (*static_cast<Node*>(this)!=INVALID && 
               !(*(gw->node_filter_map))[*this]) 
          *(static_cast<Node*>(this))=
            ++(typename Graph::NodeIt(*(gw->graph), *this));
      }
      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
             const Node& n) : 
        Node(n), gw(&_gw) { }
      NodeIt& operator++() { 
        *(static_cast<Node*>(this))=
          ++(typename Graph::NodeIt(*(gw->graph), *this));
        while (*static_cast<Node*>(this)!=INVALID && 
               !(*(gw->node_filter_map))[*this]) 
          *(static_cast<Node*>(this))=
            ++(typename Graph::NodeIt(*(gw->graph), *this));
        return *this; 
      }
    };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt : public Edge { 
      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    public:
      OutEdgeIt() { }
      OutEdgeIt(Invalid i) : Edge(i) { }
      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
      }
      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
             const Edge& e) : 
        Edge(e), gw(&_gw) { }
      OutEdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };
    class InEdgeIt : public Edge { 
      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    public:
      InEdgeIt() { }
      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
      InEdgeIt(Invalid i) : Edge(i) { }
      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
      }
      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
             const Edge& e) : 
        Edge(e), gw(&_gw) { }
      InEdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };
    class EdgeIt : public Edge { 
      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    public:
      EdgeIt() { }
      EdgeIt(Invalid i) : Edge(i) { }
      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 
        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::EdgeIt(*(gw->graph), *this));
      }
      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
             const Edge& e) : 
        Edge(e), gw(&_gw) { }
      EdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::EdgeIt(*(gw->graph), *this));
        while (*static_cast<Edge*>(this)!=INVALID && 
               !(*(gw->edge_filter_map))[*this]) 
          *(static_cast<Edge*>(this))=
            ++(typename Graph::EdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };

    NodeIt& first(NodeIt& i) const { 
      i=NodeIt(*this); return i;
    }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return 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 
    /// \c Graph::NodeIt is defined.
    int nodeNum() const { 
      int i=0;
      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
      return i; 
    }

    /// \warning This is a linear time operation and works only if 
    /// \c Graph::EdgeIt is defined.
    int edgeNum() const { 
      int i=0;
      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
      return i; 
    }

    //    KEEP_MAPS(Parent, SubGraphWrapper);
  };


  /*! \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):
   9, 5--4->6
   8, 4--2->6
   7, 3--1->5
   6, 2--3->5
   5, 2--5->6
   4, 2--2->4
   3, 1--3->4
   2, 0--1->3
   1, 0--2->2
   0, 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:
   9, 5--4->6
   8, 4--2->6
   7, 3--1->5
   4, 2--2->4
   2, 0--1->3
   1, 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);
  };



  ///\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 GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    ForwardFilterMap* forward_filter;
    BackwardFilterMap* backward_filter;

    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
      forward_filter=&_forward_filter;
    }
    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
      backward_filter=&_backward_filter;
    }

  public:

    SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 
                         BackwardFilterMap& _backward_filter) : 
      GraphWrapper<Graph>(_graph), 
      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 
                         ForwardFilterMap, BackwardFilterMap>& gw) : 
      Parent(gw), 
      forward_filter(gw.forward_filter), 
      backward_filter(gw.backward_filter) { }

    class Edge; 
    class OutEdgeIt; 
    friend class Edge; 
    friend class OutEdgeIt; 

    template<typename T> class EdgeMap;

    typedef typename GraphWrapper<Graph>::Node Node;

    typedef typename Graph::Edge GraphEdge;
    /// SubBidirGraphWrapper<..., ..., ...>::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 SubBidirGraphWrapper<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));
      }
    };

    class OutEdgeIt : public Edge {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      const SubBidirGraphWrapper<Graph, 
                                 ForwardFilterMap, BackwardFilterMap>* gw;
    public:
      OutEdgeIt() { }
      OutEdgeIt(Invalid i) : Edge(i) { }
      OutEdgeIt(const SubBidirGraphWrapper<Graph, 
                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
        while (*static_cast<GraphEdge*>(this)!=INVALID && 
               !(*(gw->forward_filter))[*this]) 
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        if (*static_cast<GraphEdge*>(this)==INVALID) {
          *static_cast<Edge*>(this)=
            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        }
      }
      OutEdgeIt(const SubBidirGraphWrapper<Graph, 
                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
        Edge(e), gw(&_gw) { }
      OutEdgeIt& operator++() { 
        if (!this->backward) {
          Node n=gw->source(*this);
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->forward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
          if (*static_cast<GraphEdge*>(this)==INVALID) {
            *static_cast<Edge*>(this)=
              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
            while (*static_cast<GraphEdge*>(this)!=INVALID && 
                   !(*(gw->backward_filter))[*this]) 
              *(static_cast<GraphEdge*>(this))=
                ++(typename Graph::InEdgeIt(*(gw->graph), *this));
          }
        } else {
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        }
        return *this;
      }
    };

    class InEdgeIt : public Edge {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      const SubBidirGraphWrapper<Graph, 
                                 ForwardFilterMap, BackwardFilterMap>* gw;
    public:
      InEdgeIt() { }
      InEdgeIt(Invalid i) : Edge(i) { }
      InEdgeIt(const SubBidirGraphWrapper<Graph, 
               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
        while (*static_cast<GraphEdge*>(this)!=INVALID && 
               !(*(gw->forward_filter))[*this]) 
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
        if (*static_cast<GraphEdge*>(this)==INVALID) {
          *static_cast<Edge*>(this)=
            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        }
      }
      InEdgeIt(const SubBidirGraphWrapper<Graph, 
               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
        Edge(e), gw(&_gw) { }
      InEdgeIt& operator++() { 
        if (!this->backward) {
          Node n=gw->source(*this);
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->forward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
          if (*static_cast<GraphEdge*>(this)==INVALID) {
            *static_cast<Edge*>(this)=
              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
            while (*static_cast<GraphEdge*>(this)!=INVALID && 
                   !(*(gw->backward_filter))[*this]) 
              *(static_cast<GraphEdge*>(this))=
                ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
          }
        } else {
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        }
        return *this;
      }
    };

    class EdgeIt : public Edge {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      const SubBidirGraphWrapper<Graph, 
                                 ForwardFilterMap, BackwardFilterMap>* gw;
    public:
      EdgeIt() { }
      EdgeIt(Invalid i) : Edge(i) { }
      EdgeIt(const SubBidirGraphWrapper<Graph, 
             ForwardFilterMap, BackwardFilterMap>& _gw) : 
        Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 
        while (*static_cast<GraphEdge*>(this)!=INVALID && 
               !(*(gw->forward_filter))[*this]) 
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::EdgeIt(*(gw->graph), *this));
        if (*static_cast<GraphEdge*>(this)==INVALID) {
          *static_cast<Edge*>(this)=
            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::EdgeIt(*(gw->graph), *this));
        }
      }
      EdgeIt(const SubBidirGraphWrapper<Graph, 
             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
        Edge(e), gw(&_gw) { }
      EdgeIt& operator++() { 
        if (!this->backward) {
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::EdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->forward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::EdgeIt(*(gw->graph), *this));
          if (*static_cast<GraphEdge*>(this)==INVALID) {
            *static_cast<Edge*>(this)=
              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
            while (*static_cast<GraphEdge*>(this)!=INVALID && 
                   !(*(gw->backward_filter))[*this]) 
              *(static_cast<GraphEdge*>(this))=
                ++(typename Graph::EdgeIt(*(gw->graph), *this));
          }
        } else {
          *(static_cast<GraphEdge*>(this))=
            ++(typename Graph::EdgeIt(*(gw->graph), *this));
          while (*static_cast<GraphEdge*>(this)!=INVALID && 
                 !(*(gw->backward_filter))[*this]) 
            *(static_cast<GraphEdge*>(this))=
              ++(typename Graph::EdgeIt(*(gw->graph), *this));
        }
        return *this;
      }
    };

//     using GraphWrapper<Graph>::first;
//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
//       i=OutEdgeIt(*this, p); return i;
//     }
//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
//       i=InEdgeIt(*this, p); return i;
//     }
//     EdgeIt& first(EdgeIt& i) const { 
//       i=EdgeIt(*this); return 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.
    int edgeNum() const { 
      int i=0;
      for (EdgeIt e(*this); e!=INVALID; ++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 SubBidirGraphWrapper<..., ..., ...>::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 ValueType;
      typedef Edge KeyType;

      EdgeMap(const SubBidirGraphWrapper<Graph, 
              ForwardFilterMap, BackwardFilterMap>& g) : 
        forward_map(*(g.graph)), backward_map(*(g.graph)) { }

      EdgeMap(const SubBidirGraphWrapper<Graph, 
              ForwardFilterMap, BackwardFilterMap>& g, T a) : 
        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }

      template <typename TT>
      EdgeMap(const EdgeMap<TT>& copy) 
        : forward_map(copy.forward_map), backward_map(copy.backward_map) {}

      template <typename TT>
      EdgeMap& operator=(const EdgeMap<TT>& copy) {
        forward_map = copy.forward_map;
        backward_map = copy.backward_map;
        return *this;
      }
      
      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>::ConstReferenceType 
      operator[](Edge e) const { 
        if (!e.backward) 
          return forward_map[e]; 
        else 
          return backward_map[e]; 
      }

      typename Graph::template EdgeMap<T>::ReferenceType 
      operator[](Edge e) { 
        if (!e.backward) 
          return forward_map[e]; 
        else 
          return backward_map[e]; 
      }

      void update() { 
        forward_map.update(); 
        backward_map.update();
      }
    };


    //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);

  };


  ///\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);
  };


  /// \brief A bidirected graph template.
  ///
  ///\warning Graph wrappers are in even more experimental state than the other
  ///parts of the lib. Use them at you own risk.
  ///
  /// A bidirected graph template.
  /// Such a bidirected graph stores each pair of oppositely directed edges 
  /// ones in the memory, i.e. a directed graph of type 
  /// \c Graph is used for that.
  /// As the oppositely directed edges are logically different ones 
  /// the maps are able to attach different values for them.
  /// \ingroup graphs
  template<typename Graph>
  class BidirGraph : public BidirGraphWrapper<Graph> {
  public:
    typedef UndirGraphWrapper<Graph> Parent;
  protected:
    Graph gr;
  public:
    BidirGraph() : BidirGraphWrapper<Graph>() { 
      Parent::setGraph(gr); 
    }
    //    KEEP_MAPS(Parent, BidirGraph);
  };



  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 ValueType;
      typedef Edge KeyType;
      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);
  };


  /// 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 GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    FirstOutEdgesMap* first_out_edges;
  public:
    ErasingFirstGraphWrapper(Graph& _graph, 
                             FirstOutEdgesMap& _first_out_edges) : 
      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt : public Edge { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
      const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
    public:
      OutEdgeIt() { }
      OutEdgeIt(Invalid i) : Edge(i) { }
      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
                const Node& n) : 
        Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
                const Edge& e) : 
        Edge(e), gw(&_gw) { }
      OutEdgeIt& operator++() { 
        *(static_cast<Edge*>(this))=
          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
        return *this; 
      }
    };

//     using GraphWrapper<Graph>::first;
//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
//       i=OutEdgeIt(*this, p); return i;
//     }
    void erase(const Edge& e) const {
      Node n=source(e);
      typename Graph::OutEdgeIt f(*Parent::graph, n);
      ++f;
      first_out_edges->set(n, f);
    }

    //    KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
  };

  ///@}

} //namespace lemon

#endif //LEMON_GRAPH_WRAPPER_H