source: lemon-0.x/src/hugo/graph_wrapper.h @ 661:d306e777117e

// -*- c++ -*-
#ifndef HUGO_GRAPH_WRAPPER_H
#define HUGO_GRAPH_WRAPPER_H

///\ingroup gwrappers
///\file
///\brief Several graph wrappers.
///
///This file contains several useful graph wrapper functions.
///
///\author Marton Makai

#include <hugo/invalid.h>
#include <hugo/maps.h>
//#include <iter_map.h>

namespace hugo {

  // Graph wrappers

  /// \addtogroup gwrappers
  /// A main parts of HUGOlib 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

  ///This is the base type for the Graph Wrappers.
  ///\todo Some more docs... 
  ///
  ///\author Marton Makai 
  template<typename Graph>
  class GraphWrapper {
  protected:
    Graph* graph;
    GraphWrapper() : graph(0) { }
    void setGraph(Graph& _graph) { graph=&_graph; }

  public:
    typedef Graph BaseGraph;
    typedef Graph ParentGraph;

    GraphWrapper(Graph& _graph) : graph(&_graph) { }
//     Graph& getGraph() const { return *graph; }
 
//    typedef typename Graph::Node Node;
    class Node : public Graph::Node {
      friend class GraphWrapper<Graph>;
    public:
      Node() { }
      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
      // /// \bug construction throughrthr multiple levels should be 
      // /// handled better
      // Node(const typename ParentGraph::ParentGraph::Node& _n) : 
      // Graph::Node(_n) { }
      Node(const Invalid& i) : Graph::Node(i) { }
    };
    class NodeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
//    typedef typename Graph::Edge Edge;
    class Edge : public Graph::Edge {
      friend class GraphWrapper<Graph>;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
      Edge(const Invalid& i) : Graph::Edge(i) { }
    };
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
   
    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;
    }

    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    

    Node tail(const Edge& e) const { 
      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    Node head(const Edge& e) const { 
      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }

    bool valid(const Node& n) const { 
      return graph->valid(static_cast<typename Graph::Node>(n)); }
    bool valid(const Edge& e) const { 
      return graph->valid(static_cast<typename Graph::Edge>(e)); }

    int nodeNum() const { return graph->nodeNum(); }
    int edgeNum() const { return graph->edgeNum(); }
  
    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
  
    Node addNode() const { return Node(graph->addNode()); }
    Edge addEdge(const Node& tail, const Node& head) const { 
      return Edge(graph->addEdge(tail, head)); }

    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 { graph->forward(e); }
    bool backward(const Edge& e) const { graph->backward(e); }
    
    Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }

    template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
      typedef typename Graph::template NodeMap<T> Parent;
    public:
      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    };

    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
      typedef typename Graph::template EdgeMap<T> Parent;
    public:
      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    };
  };



  /// A graph wrapper which reverses the orientation of the edges.

  /// A graph wrapper which reverses the orientation of the edges.
  /// Thus \c Graph have to be a directed graph type.
  ///
  ///\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) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //If Graph::OutEdgeIt is not defined
    //and we do not want to use RevGraphWrapper::InEdgeIt,
    //the typdef techinque does not work.
    //Unfortunately all the typedefs are instantiated in templates.
    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    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;
    }

    using GraphWrapper<Graph>::next;
    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

    Node aNode(const OutEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }

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

  };



  /// A graph wrapper for hiding nodes and edges from a graph.
  
  /// This wrapper shows a graph with filtered node-set and 
  /// edge-set. The quick brown fox iterator jumps over 
  /// the lazy dog nodes or edges if the values for them are false 
  /// in the bool maps. 
  ///
  ///\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 { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        n(*(_G.graph)) { 
        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
          _G.graph->next(n);
      }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
                const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        e(*(_G.graph)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    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;
    }
    
    NodeIt& next(NodeIt& i) const {
      this->graph->next(i.n); 
      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
        this->graph->next(i.n); }
      return i;
    }
    OutEdgeIt& next(OutEdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }
    InEdgeIt& next(InEdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }
    EdgeIt& next(EdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }

    Node aNode(const OutEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }

    /// 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]; }

    /// This is a linear time operation and works only if 
    /// NodeIt is defined.
    int nodeNum() const { 
      int i=0;
      NodeIt n;
      for (this->first(n); this->valid(n); this->next(n)) ++i;
      return i; 
    }

    /// This is a linear time operation and works only if 
    /// EdgeIt is defined.
    int edgeNum() const { 
      int i=0;
      EdgeIt e;
      for (this->first(e); this->valid(e); this->next(e)) ++i;
      return i; 
    }

  };



  /// \brief A wrapper for forgetting the orientation of a graph.
  ///
  /// A wrapper for getting an undirected graph by forgetting
  /// the orientation of a directed one.
  ///
  /// \author Marton Makai
  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); 
      }
    };

//FIXME InEdgeIt
    typedef OutEdgeIt InEdgeIt; 

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

    using GraphWrapper<Graph>::next;
//     NodeIt& next(NodeIt& n) const {
//       GraphWrapper<Graph>::next(n);
//       return n;
//     }
    OutEdgeIt& next(OutEdgeIt& e) const {
      if (e.out_or_in) {
        typename Graph::Node n=this->graph->tail(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;
    }
    //FIXME InEdgeIt
//     EdgeIt& next(EdgeIt& e) const {
//       GraphWrapper<Graph>::next(n);
// //      graph->next(e.e);
//       return e;
//     }

    Node aNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return this->graph->tail(e); else 
        return this->graph->head(e); }
    Node bNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return this->graph->head(e); else 
        return this->graph->tail(e); }
  };
  
  /// \brief An undirected graph template.
  ///
  /// 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); 
    }
  };



  ///\brief A wrapper for composing a subgraph of a 
  /// bidirected graph composed from a directed one. 
  /// experimental, for fezso's sake.
  ///
  /// A wrapper for composing a subgraps of a 
  /// bidirected graph composed from a directed one. 
  /// experimental, for fezso's sake.
  /// 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, 
           typename ForwardFilterMap, typename BackwardFilterMap>
  class SubBidirGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    //const CapacityMap* capacity;
    //FlowMap* flow;

    ForwardFilterMap* forward_filter;
    BackwardFilterMap* backward_filter;

    SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
                                                 capacity(0), flow(0)*/ { }
    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) { }

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

    //template<typename T> class NodeMap;    
    template<typename T> class EdgeMap;

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

    class Edge : public Graph::Edge {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
      ///\bug ez nem is kell
      //template<typename T> friend class NodeMap;
      template<typename T> friend class EdgeMap;
    protected:
      bool backward; //true, iff backward
//      typename Graph::Edge e;
    public:
      Edge() { }
      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
      Edge(const typename Graph::Edge& _e, bool _backward=false) : 
        Graph::Edge(_e), backward(_backward) { }
      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.backward==u.backward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.backward!=u.backward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };

    class OutEdgeIt {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      OutEdgeIt(const SubBidirGraphWrapper<Graph, 
                ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
        backward=false;
        _G.graph->first(out, v);
        while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
        if (!_G.graph->valid(out)) {
          backward=true;
          _G.graph->first(in, v);
          while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(in, this->backward); 
        else 
          return Edge(out, this->backward);
      }
    };

    class InEdgeIt {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      InEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      InEdgeIt(const SubBidirGraphWrapper<Graph, 
               ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
        backward=false;
        _G.graph->first(in, v);
        while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
        if (!_G.graph->valid(in)) {
          backward=true;
          _G.graph->first(out, v);
          while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(out, this->backward); 
        else 
          return Edge(in, this->backward);
      }
    };

    class EdgeIt {
      friend class SubBidirGraphWrapper<Graph, 
                                        ForwardFilterMap, BackwardFilterMap>;
    protected:
      typename Graph::EdgeIt e;
      bool backward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), backward(true) { }
      EdgeIt(const SubBidirGraphWrapper<Graph, 
             ForwardFilterMap, BackwardFilterMap>& _G) { 
        backward=false;
        _G.graph->first(e);
        while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
        if (!_G.graph->valid(e)) {
          backward=true;
          _G.graph->first(e);
          while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->backward);
      }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//    FIXME not tested
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
  
    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.out);
        this->graph->next(e.out);
        while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 
          this->graph->next(e.out); }
        if (!this->graph->valid(e.out)) {
          e.backward=true;
          this->graph->first(e.in, v); 
          while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
            this->graph->next(e.in); }
        }
      } else {
        this->graph->next(e.in);
        while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
          this->graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.in);
        this->graph->next(e.in);
        while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 
          this->graph->next(e.in); }
        if (!this->graph->valid(e.in)) {
          e.backward=true;
          this->graph->first(e.out, v); 
          while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
            this->graph->next(e.out); }
        }
      } else {
        this->graph->next(e.out);
        while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
          this->graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (!e.backward) {
        this->graph->next(e.e);
        while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 
          this->graph->next(e.e); }
        if (!this->graph->valid(e.e)) {
          e.backward=true;
          this->graph->first(e.e); 
          while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
            this->graph->next(e.e); }
        }
      } else {
        this->graph->next(e.e);
        while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
          this->graph->next(e.e); } 
      }
      return e;
    }

    Node tail(Edge e) const { 
      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
    Node head(Edge e) const { 
      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.out) : 
              this->graph->aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.out) : 
              this->graph->bNode(e.in)); }

    Node aNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.in) : 
              this->graph->aNode(e.out)); }
    Node bNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.in) : 
              this->graph->bNode(e.out)); }

    /// Gives back the opposite edge.
    Edge opposite(const Edge& e) const { 
      Edge f=e;
      f.backward=!f.backward;
      return f;
    }

//    int nodeNum() const { return graph->nodeNum(); }
    //FIXME
    void edgeNum() const { }
    //int edgeNum() const { return graph->edgeNum(); }


//    int id(Node v) const { return graph->id(v); }

    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    bool valid(Edge e) const { 
      return this->graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    bool forward(const Edge& e) const { return !e.backward; }
    bool backward(const Edge& e) const { return e.backward; }

//     void augment(const Edge& e, Number a) const {
//       if (!e.backward)  
// //   flow->set(e.out, flow->get(e.out)+a);
//      flow->set(e, (*flow)[e]+a);
//       else  
// //   flow->set(e.in, flow->get(e.in)-a);
//      flow->set(e, (*flow)[e]-a);
//     }

//     bool enabled(const Edge& e) const { 
//       if (!e.backward) 
// //   return (capacity->get(e.out)-flow->get(e.out)); 
//      //return ((*capacity)[e]-(*flow)[e]);
//      return true;
//       else 
// //   return (flow->get(e.in)); 
//      //return ((*flow)[e]); 
//      return true;
//     }

//     Number enabled(typename Graph::OutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number enabled(typename Graph::InEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

    template <typename T>
    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) { }
      void set(Edge e, T a) { 
        if (!e.backward) 
          forward_map.set(e/*.out*/, a); 
        else 
          backward_map.set(e/*.in*/, a); 
      }
      T operator[](Edge e) const { 
        if (!e.backward) 
          return forward_map[e/*.out*/]; 
        else 
          return backward_map[e/*.in*/]; 
      }
      void update() { 
        forward_map.update(); 
        backward_map.update();
      }
//       T get(Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map.get(e.out); 
//      else 
//        return backward_map.get(e.in); 
//       }
    };
  };



  ///\brief A wrapper for composing bidirected graph from a directed one. 
  /// experimental, for fezso's sake.
  ///
  /// A wrapper for composing bidirected graph from a directed one. 
  /// experimental, for fezso's sake.
  /// 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;
    //const CapacityMap* capacity;
    //FlowMap* flow;

    BidirGraphWrapper() : Parent(), cm(true) { 
      Parent::setForwardFilterMap(cm);
      Parent::setBackwardFilterMap(cm);
    }
//     void setCapacityMap(const CapacityMap& _capacity) {
//       capacity=&_capacity;
//     }
//     void setFlowMap(FlowMap& _flow) {
//       flow=&_flow;
//     }

  public:

    BidirGraphWrapper(Graph& _graph) : Parent() { 
      Parent::setGraph(_graph);
      Parent::setForwardFilterMap(cm);
      Parent::setBackwardFilterMap(cm);
    }
  };




  template<typename Graph>
  class OldBidirGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    //const CapacityMap* capacity;
    //FlowMap* flow;

    OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
                                                 capacity(0), flow(0)*/ { }
//     void setCapacityMap(const CapacityMap& _capacity) {
//       capacity=&_capacity;
//     }
//     void setFlowMap(FlowMap& _flow) {
//       flow=&_flow;
//     }

  public:

    OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
                                     FlowMap& _flow*/) : 
      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }

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

    //template<typename T> class NodeMap;    
    template<typename T> class EdgeMap;

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

    class Edge : public Graph::Edge {
      friend class OldBidirGraphWrapper<Graph>;
      ///\bug ez nem is kell
      //template<typename T> friend class NodeMap;
      template<typename T> friend class EdgeMap;
    protected:
      bool backward; //true, iff backward
//      typename Graph::Edge e;
    public:
      Edge() { }
      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
      Edge(const typename Graph::Edge& _e, bool _backward=false) : 
        Graph::Edge(_e), backward(_backward) { }
      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.backward==u.backward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.backward!=u.backward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };

    class OutEdgeIt {
      friend class OldBidirGraphWrapper<Graph>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
        backward=false;
        _G.graph->first(out, v);
        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
        if (!_G.graph->valid(out)) {
          backward=true;
          _G.graph->first(in, v);
          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(in, this->backward); 
        else 
          return Edge(out, this->backward);
      }
    };

    class InEdgeIt {
      friend class OldBidirGraphWrapper<Graph>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      InEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) { 
        backward=false;
        _G.graph->first(in, v);
        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
        if (!_G.graph->valid(in)) {
          backward=true;
          _G.graph->first(out, v);
          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(out, this->backward); 
        else 
          return Edge(in, this->backward);
      }
    };

    class EdgeIt {
      friend class OldBidirGraphWrapper<Graph>;
    protected:
      typename Graph::EdgeIt e;
      bool backward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), backward(true) { }
      EdgeIt(const OldBidirGraphWrapper<Graph>& _G) { 
        backward=false;
        _G.graph->first(e);
        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
        if (!_G.graph->valid(e)) {
          backward=true;
          _G.graph->first(e);
          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->backward);
      }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//    FIXME not tested
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
  
    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.out);
        this->graph->next(e.out);
        while(this->graph->valid(e.out) && !enabled(e)) { 
          this->graph->next(e.out); }
        if (!this->graph->valid(e.out)) {
          e.backward=true;
          this->graph->first(e.in, v); 
          while(this->graph->valid(e.in) && !enabled(e)) { 
            this->graph->next(e.in); }
        }
      } else {
        this->graph->next(e.in);
        while(this->graph->valid(e.in) && !enabled(e)) { 
          this->graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.in);
        this->graph->next(e.in);
        while(this->graph->valid(e.in) && !enabled(e)) { 
          this->graph->next(e.in); }
        if (!this->graph->valid(e.in)) {
          e.backward=true;
          this->graph->first(e.out, v); 
          while(this->graph->valid(e.out) && !enabled(e)) { 
            this->graph->next(e.out); }
        }
      } else {
        this->graph->next(e.out);
        while(this->graph->valid(e.out) && !enabled(e)) { 
          this->graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (!e.backward) {
        this->graph->next(e.e);
        while(this->graph->valid(e.e) && !enabled(e)) { 
          this->graph->next(e.e); }
        if (!this->graph->valid(e.e)) {
          e.backward=true;
          this->graph->first(e.e); 
          while(this->graph->valid(e.e) && !enabled(e)) { 
            this->graph->next(e.e); }
        }
      } else {
        this->graph->next(e.e);
        while(this->graph->valid(e.e) && !enabled(e)) { 
          this->graph->next(e.e); } 
      }
      return e;
    }

    Node tail(Edge e) const { 
      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
    Node head(Edge e) const { 
      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.out) : 
              this->graph->aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.out) : 
              this->graph->bNode(e.in)); }

    Node aNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.in) : 
              this->graph->aNode(e.out)); }
    Node bNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.in) : 
              this->graph->bNode(e.out)); }

    /// Gives back the opposite edge.
    Edge opposite(const Edge& e) const { 
      Edge f=e;
      f.backward=!f.backward;
      return f;
    }

//    int nodeNum() const { return graph->nodeNum(); }
    //FIXME
    void edgeNum() const { }
    //int edgeNum() const { return graph->edgeNum(); }


//    int id(Node v) const { return graph->id(v); }

    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    bool valid(Edge e) const { 
      return this->graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    bool forward(const Edge& e) const { return !e.backward; }
    bool backward(const Edge& e) const { return e.backward; }

//     void augment(const Edge& e, Number a) const {
//       if (!e.backward)  
// //   flow->set(e.out, flow->get(e.out)+a);
//      flow->set(e, (*flow)[e]+a);
//       else  
// //   flow->set(e.in, flow->get(e.in)-a);
//      flow->set(e, (*flow)[e]-a);
//     }

    bool enabled(const Edge& e) const { 
      if (!e.backward) 
//      return (capacity->get(e.out)-flow->get(e.out)); 
        //return ((*capacity)[e]-(*flow)[e]);
        return true;
      else 
//      return (flow->get(e.in)); 
        //return ((*flow)[e]); 
        return true;
    }

//     Number enabled(typename Graph::OutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number enabled(typename Graph::InEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

    template <typename T>
    class EdgeMap {
      typename Graph::template EdgeMap<T> forward_map, backward_map; 
    public:
      typedef T ValueType;
      typedef Edge KeyType;
      EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
      EdgeMap(const OldBidirGraphWrapper<Graph>& _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/*.out*/, a); 
        else 
          backward_map.set(e/*.in*/, a); 
      }
      T operator[](Edge e) const { 
        if (!e.backward) 
          return forward_map[e/*.out*/]; 
        else 
          return backward_map[e/*.in*/]; 
      }
      void update() { 
        forward_map.update(); 
        backward_map.update();
      }
//       T get(Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map.get(e.out); 
//      else 
//        return backward_map.get(e.in); 
//       }
    };
  };



  /// \brief A bidirected graph template.
  ///
  /// 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); 
    }
  };



  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 setGraph(const Graph& _graph) { graph=&_graph; }
    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    void setFlow(const FlowMap& _flow) { flow=&_flow; }
    bool operator[](const typename Graph::Edge& e) const {
      return ((*flow)[e] < (*capacity)[e]);
    }
  };

  template<typename Graph, typename Number,
           typename CapacityMap, typename FlowMap>
  class ResBackwardFilter {
    //const Graph* graph;
    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 setGraph(const Graph& _graph) { graph=&_graph; }
    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    void setFlow(const FlowMap& _flow) { flow=&_flow; }
    bool operator[](const typename Graph::Edge& e) const {
      return (0 < (*flow)[e]);
    }
  };

  
  /// A wrapper for composing the residual graph for directed flow and circulation problems.

  /// 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);
    }
//     /// \bug does graph reference needed in filtermaps??
//     void setGraph(const Graph& _graph) { 
//       Parent::setGraph(_graph);
//       forward_filter.setGraph(_graph);
//       backward_filter.setGraph(_graph);
//     }
  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;

    //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
    //bool backward(const Edge& e) const { return e.backward; }

    void augment(const Edge& e, Number a) const {
      if (Parent::forward(e))  
//      flow->set(e.out, flow->get(e.out)+a);
        flow->set(e, (*flow)[e]+a);
      else  
        //flow->set(e.in, flow->get(e.in)-a);
        flow->set(e, (*flow)[e]-a);
    }

    /// \deprecated
    ///
    Number resCap(const Edge& e) const { 
      if (Parent::forward(e)) 
//      return (capacity->get(e.out)-flow->get(e.out)); 
        return ((*capacity)[e]-(*flow)[e]); 
      else 
//      return (flow->get(e.in)); 
        return ((*flow)[e]); 
    }

    /// \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 (capacity->get(e.out)-flow->get(e.out)); 
          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
        else 
          //    return (flow->get(e.in)); 
          return (*(res_graph->flow))[e]; 
      }
      /// \bug not needed with dynamic maps, or does it?
      void update() { }
    };

  };


  template<typename Graph, typename Number, 
           typename CapacityMap, typename FlowMap>
  class OldResGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef GraphWrapper<Graph> Parent; 
  protected:
    const CapacityMap* capacity;
    FlowMap* flow;

    OldResGraphWrapper() : GraphWrapper<Graph>(0), 
                        capacity(0), flow(0) { }
    void setCapacityMap(const CapacityMap& _capacity) {
      capacity=&_capacity;
    }
    void setFlowMap(FlowMap& _flow) {
      flow=&_flow;
    }

  public:

    OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
                    FlowMap& _flow) : 
      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }

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

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    class Edge : public Graph::Edge {
      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      bool backward; //true, iff backward
//      typename Graph::Edge e;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e, bool _backward) : 
        Graph::Edge(_e), backward(_backward) { }
      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.backward==u.backward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.backward!=u.backward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };

    class OutEdgeIt {
      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
        backward=false;
        _G.graph->first(out, v);
        while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
        if (!_G.graph->valid(out)) {
          backward=true;
          _G.graph->first(in, v);
          while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(in, this->backward); 
        else 
          return Edge(out, this->backward);
      }
    };

    class InEdgeIt {
      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool backward;
    public:
      InEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
//the unique invalid iterator
      InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
        backward=false;
        _G.graph->first(in, v);
        while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
        if (!_G.graph->valid(in)) {
          backward=true;
          _G.graph->first(out, v);
          while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->backward) 
          return Edge(out, this->backward); 
        else 
          return Edge(in, this->backward);
      }
    };

    class EdgeIt {
      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::EdgeIt e;
      bool backward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), backward(true) { }
      EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
        backward=false;
        _G.graph->first(e);
        while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
        if (!_G.graph->valid(e)) {
          backward=true;
          _G.graph->first(e);
          while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->backward);
      }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//    FIXME not tested
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
  
    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.out);
        this->graph->next(e.out);
        while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
          this->graph->next(e.out); }
        if (!this->graph->valid(e.out)) {
          e.backward=true;
          this->graph->first(e.in, v); 
          while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
            this->graph->next(e.in); }
        }
      } else {
        this->graph->next(e.in);
        while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
          this->graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (!e.backward) {
        Node v=this->graph->aNode(e.in);
        this->graph->next(e.in);
        while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
          this->graph->next(e.in); }
        if (!this->graph->valid(e.in)) {
          e.backward=true;
          this->graph->first(e.out, v); 
          while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
            this->graph->next(e.out); }
        }
      } else {
        this->graph->next(e.out);
        while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
          this->graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (!e.backward) {
        this->graph->next(e.e);
        while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
          this->graph->next(e.e); }
        if (!this->graph->valid(e.e)) {
          e.backward=true;
          this->graph->first(e.e); 
          while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
            this->graph->next(e.e); }
        }
      } else {
        this->graph->next(e.e);
        while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
          this->graph->next(e.e); } 
      }
      return e;
    }

    Node tail(Edge e) const { 
      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
    Node head(Edge e) const { 
      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.out) : 
              this->graph->aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.out) : 
              this->graph->bNode(e.in)); }

    Node aNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->aNode(e.in) : 
              this->graph->aNode(e.out)); }
    Node bNode(InEdgeIt e) const { 
      return ((!e.backward) ? this->graph->bNode(e.in) : 
              this->graph->bNode(e.out)); }

//    int nodeNum() const { return graph->nodeNum(); }
    //FIXME
    void edgeNum() const { }
    //int edgeNum() const { return graph->edgeNum(); }


//    int id(Node v) const { return graph->id(v); }

    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    bool valid(Edge e) const { 
      return this->graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    bool forward(const Edge& e) const { return !e.backward; }
    bool backward(const Edge& e) const { return e.backward; }

    void augment(const Edge& e, Number a) const {
      if (!e.backward)  
//      flow->set(e.out, flow->get(e.out)+a);
        flow->set(e, (*flow)[e]+a);
      else  
//      flow->set(e.in, flow->get(e.in)-a);
        flow->set(e, (*flow)[e]-a);
    }

    Number resCap(const Edge& e) const { 
      if (!e.backward) 
//      return (capacity->get(e.out)-flow->get(e.out)); 
        return ((*capacity)[e]-(*flow)[e]); 
      else 
//      return (flow->get(e.in)); 
        return ((*flow)[e]); 
    }

//     Number resCap(typename Graph::OutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number resCap(typename Graph::InEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

    template <typename T>
    class EdgeMap {
      typename Graph::template EdgeMap<T> forward_map, backward_map; 
    public:
      typedef T ValueType;
      typedef Edge KeyType;
      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _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/*.out*/, a); 
        else 
          backward_map.set(e/*.in*/, a); 
      }
      T operator[](Edge e) const { 
        if (!e.backward) 
          return forward_map[e/*.out*/]; 
        else 
          return backward_map[e/*.in*/]; 
      }
      void update() { 
        forward_map.update(); 
        backward_map.update();
      }
//       T get(Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map.get(e.out); 
//      else 
//        return backward_map.get(e.in); 
//       }
    };
  };



  /// For blocking flows.

  /// This graph wrapper is used for 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;
//     class NodeIt { 
//       friend class GraphWrapper<Graph>;
//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//       typename Graph::NodeIt n;
//      public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
//       NodeIt(const Invalid& i) : n(i) { }
//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
//      n(*(_G.graph)) { }
//       operator Node() const { return Node(typename Graph::Node(n)); }
//     };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
                const Node& _n) : 
        e((*_G.first_out_edges)[_n]) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::EdgeIt GraphEdgeIt;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
        e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
//     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;
    }

    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
    
    Node aNode(const OutEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); }

    void erase(const OutEdgeIt& e) const {
      OutEdgeIt f=e;
      this->next(f);
      first_out_edges->set(this->tail(e), f.e);
    }
  };

  ///@}

} //namespace hugo

#endif //HUGO_GRAPH_WRAPPER_H