source: lemon-0.x/src/work/marci/graph_wrapper.h @ 335:999eb3cd7b49

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

#include <invalid.h>

namespace hugo {

  /// Graph wrappers

  /// The 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 more 
  /// clear. 
  /// Suppose that we have an instance \code g \endcode of a directed graph
  /// type say \code ListGraph \endcode and an algorithm 
  /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
  /// is needed to run on the reversed oriented graph. 
  /// It can be expensive (in time or in memory usage) to copy 
  /// \code g \endcode with the reversed 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 \code g \endcode 
  /// is untouched. Thus the above used graph wrapper is to consider the 
  /// original graph with reversed 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 particualar significance. Combining a wrapper impleneting 
  /// this, shortest path algorithms and mimimum 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 domumentation of graph 
  /// wrappers. 
  /// The behavior of graph wrappers are 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 model of depend 
  /// on the graph wrapper, and the wrapped graph(s). 
  /// If an edge of \code rgw \endcode is deleted, this is carried out by 
  /// deleting the corresponding edge of \code g \endcode. 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 
  /// \code RevGraphWrapper(Graph& _g); \endcode. 
  /// This means that in a situation, 
  /// when a \code const ListGraph& \endcode reference to a graph is given, 
  /// then it have to be instatiated with Graph=const ListGraph.
  /// \code
  /// int algorithm1(const ListGraph& g) {
  ///   RevGraphWrapper<const ListGraph> rgw(g);
  ///   return algorithm2(rgw);
  /// }
  /// \endcode
  template<typename Graph>
  class GraphWrapper {
  protected:
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;
    typedef Graph ParentGraph;

//     GraphWrapper() : graph(0) { }
    GraphWrapper(Graph& _graph) : graph(&_graph) { }
//     void setGraph(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) { }
      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>;
//      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 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>;
//      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 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>;
//      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 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;
    }
//     template<typename I> I& first(I& i) const {       
//       i=I(*this);
//       return i;
//     }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       i=I(*this, p);
//       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; }    
//    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }

//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }

    Node head(const Edge& e) const { 
      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    Node tail(const Edge& e) const { 
      return Node(graph->tail(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)); }
//    template<typename I> bool valid(const I& i) const { 
//      return graph->valid(i); }
  
    //template<typename I> void setInvalid(const I &i);
    //{ return graph->setInvalid(i); }

    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)); }
//     template<typename I> Node aNode(const I& e) const { 
//       return Node(graph->aNode(e.e)); }
//     template<typename I> Node bNode(const I& 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); }
//    template<typename I> void erase(const I& i) const { graph->erase(i); }
  
    void clear() const { graph->clear(); }
    
    template<typename T> class NodeMap : public Graph::NodeMap<T> { 
    public:
      NodeMap(const GraphWrapper<Graph>& _G) :  
        Graph::NodeMap<T>(*(_G.graph)) { }
      NodeMap(const GraphWrapper<Graph>& _G, T a) : 
        Graph::NodeMap<T>(*(_G.graph), a) { }
    };

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


//   template<typename Graph>
//   class RevGraphWrapper
//   {
//   protected:
//     Graph* graph;
  
//   public:
//     typedef Graph ParentGraph;

//     typedef typename Graph::Node Node;    
//     typedef typename Graph::NodeIt NodeIt;
  
//     typedef typename Graph::Edge Edge;
//     typedef typename Graph::OutEdgeIt InEdgeIt;
//     typedef typename Graph::InEdgeIt OutEdgeIt;
//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     typedef typename Graph::EdgeIt EdgeIt;

//     //RevGraphWrapper() : graph(0) { }
//     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

//     void setGraph(Graph& _graph) { graph = &_graph; }
//     Graph& getGraph() const { return (*graph); }
    
//     template<typename I> I& first(I& i) const { return graph->first(i); }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       return graph->first(i, p); }

//     template<typename I> I& next(I &i) const { return graph->next(i); }    

//     template< typename It > It first() const { 
//       It e; first(e); return e; }

//     template< typename It > It first(const Node& v) const { 
//       It e; first(e, v); return e; }

//     Node head(const Edge& e) const { return graph->tail(e); }
//     Node tail(const Edge& e) const { return graph->head(e); }
  
//     template<typename I> bool valid(const I& i) const 
//       { return graph->valid(i); }
  
//     //template<typename I> void setInvalid(const I &i);
//     //{ return graph->setInvalid(i); }
  
//     template<typename I> Node aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> Node bNode(const I& e) const { 
//       return graph->bNode(e); }

//     Node addNode() const { return graph->addNode(); }
//     Edge addEdge(const Node& tail, const Node& head) const { 
//       return graph->addEdge(tail, head); }
  
//     int nodeNum() const { return graph->nodeNum(); }
//     int edgeNum() const { return graph->edgeNum(); }
  
//     template<typename I> void erase(const I& i) const { graph->erase(i); }
  
//     void clear() const { graph->clear(); }

//     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
//     public:
//       NodeMap(const RevGraphWrapper<Graph>& _G) : 
//      Graph::NodeMap<T>(_G.getGraph()) { }
//       NodeMap(const RevGraphWrapper<Graph>& _G, T a) : 
//      Graph::NodeMap<T>(_G.getGraph(), a) { }
//     };

//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
//     public:
//       EdgeMap(const RevGraphWrapper<Graph>& _G) : 
//      Graph::EdgeMap<T>(_G.getGraph()) { }
//       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : 
//      Graph::EdgeMap<T>(_G.getGraph(), a) { }
//     };
//   };


  template<typename Graph>
  class RevGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //FIXME 
    //If Graph::OutEdgeIt is not defined
    //and we do not want to use RevGraphWrapper::InEdgeIt,
    //this won't work, because of typedef
    //OR
    //graphs have to define their non-existing iterators to void
    //Unfortunately all the typedefs are instantiated in templates, 
    //unlike other stuff
    typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

//     RevGraphWrapper() : GraphWrapper<Graph>() { }
    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

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

  /// 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 iterators jumps over 
  /// the lazy dog nodes or edges if the values for them are false 
  /// in the bool maps. 
  template<typename Graph, typename NodeFilterMap, 
           typename EdgeFilterMap>
  class SubGraphWrapper : public GraphWrapper<Graph> {
  protected:
    NodeFilterMap* node_filter_map;
    EdgeFilterMap* edge_filter_map;
  public:
//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
    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)); }
    };
//     class NodeIt : public Graph::NodeIt { 
// //      typedef typename Graph::NodeIt GraphNodeIt;
//     public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
//      Graph::NodeIt(*(_G.graph)) { 
//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 
//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 
//        _G.graph->next((*this)/*.GraphNodeIt*/);
//       }
//     };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
//      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 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>;
//      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 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>;
//      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 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)); }
    };
//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
//     };
//     class OutEdgeIt : public Graph::OutEdgeIt { 
// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
//     public:
//       OutEdgeIt() { }
//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 
//              _G, const Node& n) : 
//      Graph::OutEdgeIt(*(_G.graph), n) { 
//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
//       }
//     };
//     class InEdgeIt : public Graph::InEdgeIt { 
// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
//     public:
//       InEdgeIt() { }
//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
//             const Node& n) : 
//      Graph::InEdgeIt(*(_G.graph), n) { 
//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
//       }
//     };
// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     class EdgeIt : public Graph::EdgeIt { 
// //      typedef typename Graph::EdgeIt GraphEdgeIt;
//     public:
//       EdgeIt() { }
//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
//      Graph::EdgeIt(*(_G.graph)) { 
//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphEdgeIt*/);
//       }
//     };
   

    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;
    }
    
//     template<typename I> I& first(I& i) const { 
//       graph->first(i); 
//       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       graph->first(i, p); 
// //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     }

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

//     template<typename I> I& next(I &i) const { 
//       graph->next(i); 
// //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     } 

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

    void hide(const Node& n) const { node_filter_map->set(n, false); }
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    void unHide(const Node& n) const { node_filter_map->set(n, true); }
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }

//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }
    
//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }
  };

//   //Subgraph on the same node-set and partial edge-set
//   template<typename Graph, typename NodeFilterMap, 
//         typename EdgeFilterMap>
//   class SubGraphWrapper : public GraphWrapper<Graph> {
//   protected:
//     NodeFilterMap* node_filter_map;
//     EdgeFilterMap* edge_filter_map;
//   public:
// //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
//     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 Graph::Node Node;
//     class NodeIt : public Graph::NodeIt { 
// //      typedef typename Graph::NodeIt GraphNodeIt;
//     public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
//      Graph::NodeIt(*(_G.graph)) { 
//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 
//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 
//        _G.graph->next((*this)/*.GraphNodeIt*/);
//       }
//     };
//     typedef typename Graph::Edge Edge;
//     class OutEdgeIt : public Graph::OutEdgeIt { 
// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
//     public:
//       OutEdgeIt() { }
//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 
//              _G, const Node& n) : 
//      Graph::OutEdgeIt(*(_G.graph), n) { 
//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
//       }
//     };
//     class InEdgeIt : public Graph::InEdgeIt { 
// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
//     public:
//       InEdgeIt() { }
//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
//             const Node& n) : 
//      Graph::InEdgeIt(*(_G.graph), n) { 
//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
//       }
//     };
// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     class EdgeIt : public Graph::EdgeIt { 
// //      typedef typename Graph::EdgeIt GraphEdgeIt;
//     public:
//       EdgeIt() { }
//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
//      Graph::EdgeIt(*(_G.graph)) { 
//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 
//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 
//        _G.graph->next((*this)/*.GraphEdgeIt*/);
//       }
//     };
   
//     NodeIt& first(NodeIt& i) const {
//       i=NodeIt(*this);
//       return i;
//     }
//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
//       i=OutEdgeIt(*this, n);
//       return i;
//     }
//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
//       i=InEdgeIt(*this, n);
//       return i;
//     }
//     EdgeIt& first(EdgeIt& i) const {
//       i=EdgeIt(*this);
//       return i;
//     }
    
// //     template<typename I> I& first(I& i) const { 
// //       graph->first(i); 
// //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
// //       return i;
// //     }
// //     template<typename I, typename P> I& first(I& i, const P& p) const { 
// //       graph->first(i, p); 
// // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
// //       return i;
// //     }

//     NodeIt& next(NodeIt& i) const {
//       graph->next(i); 
//       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
//       return i;
//     }
//     OutEdgeIt& next(OutEdgeIt& i) const {
//       graph->next(i); 
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     }
//     InEdgeIt& next(InEdgeIt& i) const {
//       graph->next(i); 
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     }
//     EdgeIt& next(EdgeIt& i) const {
//       graph->next(i); 
//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
//       return i;
//     }

// //     template<typename I> I& next(I &i) const { 
// //       graph->next(i); 
// // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
// //       return i;
// //     }
    
//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }
    
//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }
//   };

  template<typename Graph>
  class UndirGraphWrapper : public GraphWrapper<Graph> {
//  protected:
//    typedef typename Graph::Edge GraphEdge;
//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
//    typedef typename Graph::InEdgeIt GraphInEdgeIt;    
  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() : GraphWrapper<Graph>() { }
    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

    
//     class Edge {
//       friend class UndirGraphWrapper<Graph>;
//     protected:
//       bool out_or_in; //true iff out
//       GraphOutEdgeIt out;
//       GraphInEdgeIt in;
//     public:
//       Edge() : out_or_in(), out(), in() { }
//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
//       operator GraphEdge() const {
//      if (out_or_in) return(out); else return(in);
//       }
// //FIXME
// //2 edges are equal if they "refer" to the same physical edge 
// //is it good?
//       friend bool operator==(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
//      //return (u.out_or_in && u.out==v.out);
//      else
//        if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
//      //return (!u.out_or_in && u.in==v.in);
//       } 
//       friend bool operator!=(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
//      //return (!u.out_or_in || u.out!=v.out);
//      else
//        if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
//      //return (u.out_or_in || u.in!=v.in);
//       } 
//     };

    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); 
      }
    };
//     class OutEdgeIt : public Edge {
//       friend class UndirGraphWrapper<Graph>;
//     public:
//       OutEdgeIt() : Edge() { }
//       OutEdgeIt(const Invalid& i) : Edge(i) { }
//       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) 
//      : Edge() { 
//      out_or_in=true; _G.graph->first(out, n);
//      if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
//       }
//     };

//FIXME InEdgeIt
    typedef OutEdgeIt InEdgeIt; 

//     class EdgeIt : public Edge {
//       friend class UndirGraphWrapper<Graph>;
//     protected:
//       NodeIt v;
//     public:
//       EdgeIt() : Edge() { }
//       EdgeIt(const Invalid& i) : Edge(i) { }
//       EdgeIt(const UndirGraphWrapper<Graph>& _G) 
//      : Edge() { 
//      out_or_in=true;
//      //Node v;
//      _G.first(v);
//      if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
//      while (_G.valid(v) && !_G.graph->valid(out)) { 
//        _G.graph->next(v); 
//        if (_G.valid(v)) _G.graph->first(out); 
//      }
//       }
//     };

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

//     template<typename I> I& first(I& i) const { graph->first(i); return i; }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       graph->first(i, p); return i; }

    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=graph->tail(e.out);
        graph->next(e.out);
        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
      } else {
        graph->next(e.in);
      }
      return e;
    }
    //FIXME InEdgeIt
    EdgeIt& next(EdgeIt& e) const {
      GraphWrapper<Graph>::next(n);
//      graph->next(e.e);
      return e;
    }

//    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }

//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }

//    Node head(const Edge& e) const { return gw.head(e); }
//    Node tail(const Edge& e) const { return gw.tail(e); }

//    template<typename I> bool valid(const I& i) const 
//      { return gw.valid(i); }
  
//    int nodeNum() const { return gw.nodeNum(); }
//    int edgeNum() const { return gw.edgeNum(); }
  
//     template<typename I> Node aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> Node bNode(const I& e) const { 
//       return graph->bNode(e); }

    Node aNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
    Node bNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
  
//    Node addNode() const { return gw.addNode(); }

// FIXME: ez igy nem jo, mert nem
//    Edge addEdge(const Node& tail, const Node& head) const { 
//      return graph->addEdge(tail, head); }
  
//    template<typename I> void erase(const I& i) const { gw.erase(i); }
  
//    void clear() const { gw.clear(); }
    
//     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
//     public:
//       NodeMap(const UndirGraphWrapper<Graph>& _G) : 
//      Graph::NodeMap<T>(_G.gw) { }
//       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : 
//      Graph::NodeMap<T>(_G.gw, a) { }
//     };

//     template<typename T> class EdgeMap : 
//       public GraphWrapperSkeleton<Graph>::EdgeMap<T> { 
//     public:
//       EdgeMap(const UndirGraphWrapper<Graph>& _G) : 
//      GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
//       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : 
//      Graph::EdgeMap<T>(_G.gw, a) { }
//     };
   };





//   template<typename Graph>
//   class SymGraphWrapper
//   {
//     Graph* graph;
  
//   public:
//     typedef Graph ParentGraph;

//     typedef typename Graph::Node Node;
//     typedef typename Graph::Edge Edge;
  
//     typedef typename Graph::NodeIt NodeIt;
    
//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
//     //iranyitatlant, ami van
//     //mert csak 1 dolgot lehet be typedef-elni
//     typedef typename Graph::OutEdgeIt SymEdgeIt;
//     //typedef typename Graph::InEdgeIt SymEdgeIt;
//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     typedef typename Graph::EdgeIt EdgeIt;

//     int nodeNum() const { return graph->nodeNum(); }
//     int edgeNum() const { return graph->edgeNum(); }
    
//     template<typename I> I& first(I& i) const { return graph->first(i); }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       return graph->first(i, p); }
//     //template<typename I> I next(const I i); { return graph->goNext(i); }
//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }

//     template< typename It > It first() const { 
//       It e; first(e); return e; }

//     template< typename It > It first(Node v) const { 
//       It e; first(e, v); return e; }

//     Node head(const Edge& e) const { return graph->head(e); }
//     Node tail(const Edge& e) const { return graph->tail(e); }
  
//     template<typename I> Node aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> Node bNode(const I& e) const { 
//       return graph->bNode(e); }
  
//     //template<typename I> bool valid(const I i);
//     //{ return graph->valid(i); }
  
//     //template<typename I> void setInvalid(const I &i);
//     //{ return graph->setInvalid(i); }
  
//     Node addNode() { return graph->addNode(); }
//     Edge addEdge(const Node& tail, const Node& head) { 
//       return graph->addEdge(tail, head); }
  
//     template<typename I> void erase(const I& i) { graph->erase(i); }
  
//     void clear() { graph->clear(); }
  
//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
  
//     void setGraph(Graph& _graph) { graph = &_graph; }
//     Graph& getGraph() { return (*graph); }

//     //SymGraphWrapper() : graph(0) { }
//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
//   };


  

  template<typename Graph, typename Number, 
           typename CapacityMap, typename FlowMap>
  class ResGraphWrapper : public GraphWrapper<Graph> {
  protected:
//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
//    typedef typename Graph::InEdgeIt GraphInEdgeIt;
//    typedef typename Graph::Edge GraphEdge;
    const CapacityMap* capacity;
    FlowMap* flow;
  public:

    ResGraphWrapper(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 ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      bool forward; //true, iff forward
//      typename Graph::Edge e;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e, bool _forward) : 
        Graph::Edge(_e), forward(_forward) { }
      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.forward==u.forward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.forward!=u.forward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };
//     class Edge {
//       friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;
//     protected:
//       bool out_or_in; //true, iff out
//       GraphOutEdgeIt out;
//       GraphInEdgeIt in;
//     public:
//       Edge() : out_or_in(true) { } 
//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
// //       bool valid() const { 
// //   return out_or_in && out.valid() || in.valid(); }
//       friend bool operator==(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        return (u.out_or_in && u.out==v.out);
//      else
//        return (!u.out_or_in && u.in==v.in);
//       } 
//       friend bool operator!=(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        return (!u.out_or_in || u.out!=v.out);
//      else
//        return (u.out_or_in || u.in!=v.in);
//       } 
//       operator GraphEdge() const {
//      if (out_or_in) return(out); else return(in);
//       }
//     };
    class OutEdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool forward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
//the unique invalid iterator
      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
        forward=true;
        resG.graph->first(out, v);
        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
        if (!resG.graph->valid(out)) {
          forward=false;
          resG.graph->first(in, v);
          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->forward) 
          return Edge(out, this->forward); 
        else 
          return Edge(in, this->forward);
      }
    };
//     class OutEdgeIt : public Edge {
//       friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;
//     public:
//       OutEdgeIt() { }
//       //FIXME
//       OutEdgeIt(const Edge& e) : Edge(e) { }
//       OutEdgeIt(const Invalid& i) : Edge(i) { }
//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() { 
//      resG.graph->first(out, v);
//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      if (!resG.graph->valid(out)) {
//        out_or_in=0;
//        resG.graph->first(in, v);
//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//      }
//       }
//     public:
//       OutEdgeIt& operator++() { 
//      if (out_or_in) {
//        Node v=/*resG->*/G->aNode(out);
//        ++out;
//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        if (!out.valid()) {
//          out_or_in=0;
//          G->first(in, v); 
//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        }
//      } else {
//        ++in;
//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 
//      }
//      return *this; 
//       }
//    };

    //FIXME This is just for having InEdgeIt
//    class InEdgeIt : public Edge { };

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

    class EdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::EdgeIt e;
      bool forward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), forward(false) { }
      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
        forward=true;
        resG.graph->first(e);
        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        if (!resG.graph->valid(e)) {
          forward=false;
          resG.graph->first(e);
          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->forward);
      }
    };
//     class EdgeIt : public Edge {
//       friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;
//       NodeIt v; 
//     public:
//       EdgeIt() { }
//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
//       EdgeIt(const Invalid& i) : Edge(i) { }
//       EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() { 
//      resG.graph->first(v);
//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      while (resG.graph->valid(v) && !resG.graph->valid(out)) { 
//        resG.graph->next(v); 
//        if (resG.graph->valid(v)) resG.graph->first(out, v); 
//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      }
//      if (!resG.graph->valid(out)) {
//        out_or_in=0;
//        resG.graph->first(v);
//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//        while (resG.graph->valid(v) && !resG.graph->valid(in)) { 
//          resG.graph->next(v); 
//          if (resG.graph->valid(v)) resG.graph->first(in, v); 
//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//        }
//      }
//       }
//       EdgeIt& operator++() { 
//      if (out_or_in) {
//        ++out;
//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        while (v.valid() && !out.valid()) { 
//          ++v; 
//          if (v.valid()) G->first(out, v); 
//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        }
//        if (!out.valid()) {
//          out_or_in=0;
//          G->first(v);
//          if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//          while (v.valid() && !in.valid()) { 
//            ++v; 
//            if (v.valid()) G->first(in, v); 
//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//          }  
//        }
//      } else {
//        ++in;
//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        while (v.valid() && !in.valid()) { 
//          ++v; 
//          if (v.valid()) G->first(in, v); 
//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        }
//      }
//      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;
    }
//    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;
    }
   
    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (e.forward) {
        Node v=graph->aNode(e.out);
        graph->next(e.out);
        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
        if (!graph->valid(e.out)) {
          e.forward=false;
          graph->first(e.in, v); 
          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
        }
      } else {
        graph->next(e.in);
        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (e.forward) {
        Node v=graph->aNode(e.in);
        graph->next(e.in);
        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
        if (!graph->valid(e.in)) {
          e.forward=false;
          graph->first(e.out, v); 
          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
        }
      } else {
        graph->next(e.out);
        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (e.forward) {
        graph->next(e.e);
        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
        if (!graph->valid(e.e)) {
          e.forward=false;
          graph->first(e.e); 
          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
        }
      } else {
        graph->next(e.e);
        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 
      }
      return e;
    }
//     EdgeIt& next(EdgeIt& e) const { 
//       if (e.out_or_in) {
//      graph->next(e.out);
//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
//        while (graph->valid(e.v) && !graph->valid(e.out)) { 
//          graph->next(e.v); 
//          if (graph->valid(e.v)) graph->first(e.out, e.v); 
//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
//        }
//        if (!graph->valid(e.out)) {
//          e.out_or_in=0;
//          graph->first(e.v);
//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//          while (graph->valid(e.v) && !graph->valid(e.in)) { 
//            graph->next(e.v); 
//            if (graph->valid(e.v)) graph->first(e.in, e.v); 
//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//          }  
//        }
//      } else {
//        graph->next(e.in);
//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//        while (graph->valid(e.v) && !graph->valid(e.in)) { 
//          graph->next(e.v); 
//          if (graph->valid(e.v)) graph->first(e.in, e.v); 
//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//        }
//      }
//      return e;
//       }
    

//     template< typename It >
//     It first() const { 
//       It e;
//       first(e);
//       return e; 
//     }

//     template< typename It >
//     It first(Node v) const { 
//       It e;
//       first(e, v);
//       return e; 
//     }

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

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

    int nodeNum() const { return graph->nodeNum(); }
    //FIXME
    //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 graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    void augment(const Edge& e, Number a) const {
      if (e.forward)  
//      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.forward) 
//      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 NodeMap : public Graph::NodeMap<T> { 
//     public:
//       NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G) 
//      : Graph::NodeMap<T>(_G.gw) { }
//       NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G, 
//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
//     };

//     template <typename T>
//     class NodeMap {
//       typename Graph::NodeMap<T> node_map; 
//     public:
//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
//       void set(Node nit, T a) { node_map.set(nit, a); }
//       T get(Node nit) const { return node_map.get(nit); }
//     };

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

  

//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
//   class ResGraphWrapper : public GraphWrapper<Graph> {
//   protected:
//     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
//     typedef typename Graph::InEdgeIt GraphInEdgeIt;
//     typedef typename Graph::Edge GraphEdge;
//     FlowMap* flow;
//     const CapacityMap* capacity;
//   public:

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

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

//     typedef typename GraphWrapper<Graph>::Node Node;
//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
//     class Edge {
//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
//     protected:
//       bool out_or_in; //true, iff out
//       GraphOutEdgeIt out;
//       GraphInEdgeIt in;
//     public:
//       Edge() : out_or_in(true) { } 
//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
// //       bool valid() const { 
// //   return out_or_in && out.valid() || in.valid(); }
//       friend bool operator==(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        return (u.out_or_in && u.out==v.out);
//      else
//        return (!u.out_or_in && u.in==v.in);
//       } 
//       friend bool operator!=(const Edge& u, const Edge& v) { 
//      if (v.out_or_in) 
//        return (!u.out_or_in || u.out!=v.out);
//      else
//        return (u.out_or_in || u.in!=v.in);
//       } 
//       operator GraphEdge() const {
//      if (out_or_in) return(out); else return(in);
//       }
//     };
//     class OutEdgeIt : public Edge {
//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
//     public:
//       OutEdgeIt() { }
//       //FIXME
//       OutEdgeIt(const Edge& e) : Edge(e) { }
//       OutEdgeIt(const Invalid& i) : Edge(i) { }
//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 
//      resG.graph->first(out, v);
//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      if (!resG.graph->valid(out)) {
//        out_or_in=0;
//        resG.graph->first(in, v);
//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//      }
//       }
// //     public:
// //       OutEdgeIt& operator++() { 
// //   if (out_or_in) {
// //     Node v=/*resG->*/G->aNode(out);
// //     ++out;
// //     while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
// //     if (!out.valid()) {
// //       out_or_in=0;
// //       G->first(in, v); 
// //       while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
// //     }
// //   } else {
// //     ++in;
// //     while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 
// //   }
// //   return *this; 
// //       }
//     };

//     //FIXME This is just for having InEdgeIt
// //    class InEdgeIt : public Edge { };

//     class EdgeIt : public Edge {
//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
//       NodeIt v; 
//     public:
//       EdgeIt() { }
//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
//       EdgeIt(const Invalid& i) : Edge(i) { }
//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 
//      resG.graph->first(v);
//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      while (resG.graph->valid(v) && !resG.graph->valid(out)) { 
//        resG.graph->next(v); 
//        if (resG.graph->valid(v)) resG.graph->first(out, v); 
//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
//      }
//      if (!resG.graph->valid(out)) {
//        out_or_in=0;
//        resG.graph->first(v);
//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//        while (resG.graph->valid(v) && !resG.graph->valid(in)) { 
//          resG.graph->next(v); 
//          if (resG.graph->valid(v)) resG.graph->first(in, v); 
//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
//        }
//      }
//       }
// //       EdgeIt& operator++() { 
// //   if (out_or_in) {
// //     ++out;
// //     while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
// //     while (v.valid() && !out.valid()) { 
// //       ++v; 
// //       if (v.valid()) G->first(out, v); 
// //       while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
// //     }
// //     if (!out.valid()) {
// //       out_or_in=0;
// //       G->first(v);
// //       if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
// //       while (v.valid() && !in.valid()) { 
// //         ++v; 
// //         if (v.valid()) G->first(in, v); 
// //         while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
// //       }  
// //     }
// //   } else {
// //     ++in;
// //     while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
// //     while (v.valid() && !in.valid()) { 
// //       ++v; 
// //       if (v.valid()) G->first(in, v); 
// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
// //     }
// //   }
// //   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;
//     }
//     //FIXME Not yet implemented
//     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
//     //i=InEdgeIt(*this, p);
//     //  return i;
//     //}
//     EdgeIt& first(EdgeIt& e) const { 
//       e=EdgeIt(*this); 
//       return e;
//     }
   
//     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
//     OutEdgeIt& next(OutEdgeIt& e) const { 
//       if (e.out_or_in) {
//      Node v=graph->aNode(e.out);
//      graph->next(e.out);
//      while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
//      if (!graph->valid(e.out)) {
//        e.out_or_in=0;
//        graph->first(e.in, v); 
//        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//      }
//       } else {
//      graph->next(e.in);
//      while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 
//       }
//       return e;
//     }
//     //FIXME Not yet implemented
//     //InEdgeIt& next(InEdgeIt& e) const {
//     //  return e;
//     //}
//     EdgeIt& next(EdgeIt& e) const { 
//       if (e.out_or_in) {
//      graph->next(e.out);
//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
//        while (graph->valid(e.v) && !graph->valid(e.out)) { 
//          graph->next(e.v); 
//          if (graph->valid(e.v)) graph->first(e.out, e.v); 
//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
//        }
//        if (!graph->valid(e.out)) {
//          e.out_or_in=0;
//          graph->first(e.v);
//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//          while (graph->valid(e.v) && !graph->valid(e.in)) { 
//            graph->next(e.v); 
//            if (graph->valid(e.v)) graph->first(e.in, e.v); 
//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//          }  
//        }
//      } else {
//        graph->next(e.in);
//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//        while (graph->valid(e.v) && !graph->valid(e.in)) { 
//          graph->next(e.v); 
//          if (graph->valid(e.v)) graph->first(e.in, e.v); 
//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
//        }
//      }
//      return e;
//       }
    

//     template< typename It >
//     It first() const { 
//       It e;
//       first(e);
//       return e; 
//     }

//     template< typename It >
//     It first(Node v) const { 
//       It e;
//       first(e, v);
//       return e; 
//     }

//     Node tail(Edge e) const { 
//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
//     Node head(Edge e) const { 
//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

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

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


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

//     bool valid(Node n) const { return graph->valid(n); }
//     bool valid(Edge e) const { 
//       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }

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

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

//     Number resCap(GraphOutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number resCap(GraphInEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

// //     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
// //     public:
// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 
// //   : Graph::NodeMap<T>(_G.gw) { }
// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 
// //         T a) : Graph::NodeMap<T>(_G.gw, a) { }
// //     };

// //     template <typename T>
// //     class NodeMap {
// //       typename Graph::NodeMap<T> node_map; 
// //     public:
// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
// //       void set(Node nit, T a) { node_map.set(nit, a); }
// //       T get(Node nit) const { return node_map.get(nit); }
// //     };

//     template <typename T>
//     class EdgeMap {
//       typename Graph::EdgeMap<T> forward_map, backward_map; 
//     public:
//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
//       void set(Edge e, T a) { 
//      if (e.out_or_in) 
//        forward_map.set(e.out, a); 
//      else 
//        backward_map.set(e.in, a); 
//       }
//       T operator[](Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map[e.out]; 
//      else 
//        return backward_map[e.in]; 
//       }
// //       T get(Edge e) const { 
// //   if (e.out_or_in) 
// //     return forward_map.get(e.out); 
// //   else 
// //     return backward_map.get(e.in); 
// //       }
//     };
//   };


  //ErasingFirstGraphWrapper for blocking flows
  template<typename Graph, typename FirstOutEdgesMap>
  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
  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)); }
    };

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

//     template<typename I> I& first(I& i) const { 
//       graph->first(i); 
//       return i;
//     }
//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
// //      e=first_out_edges->get(n);
//       e=(*first_out_edges)[n];
//       return e;
//     }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       graph->first(i, p); 
//       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 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)); }

//     template<typename I> I& next(I &i) const { 
//       graph->next(i); 
//       return i;
//     }
    
//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }
    
//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }

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

//   //ErasingFirstGraphWrapper for blocking flows
//   template<typename Graph, typename FirstOutEdgesMap>
//   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
//   protected:
//     FirstOutEdgesMap* first_out_edges;
//   public:
//     ErasingFirstGraphWrapper(Graph& _graph, 
//                           FirstOutEdgesMap& _first_out_edges) : 
//       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  

//     typedef typename Graph::Node Node;
//     class NodeIt : public Graph::NodeIt { 
//     public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
//      Graph::NodeIt(*(_G.graph)) { }
//     };
//     typedef typename Graph::Edge Edge;
//     class OutEdgeIt : public Graph::OutEdgeIt { 
//     public:
//       OutEdgeIt() { }
//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
//              const Node& n) : 
//      Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
//     };
//     class InEdgeIt : public Graph::InEdgeIt { 
//     public:
//       InEdgeIt() { }
//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
//             const Node& n) : 
//      Graph::InEdgeIt(*(_G.graph), n) { }
//     };
//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     class EdgeIt : public Graph::EdgeIt { 
//     public:
//       EdgeIt() { }
//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
//      Graph::EdgeIt(*(_G.graph)) { }
//     };

//     NodeIt& first(NodeIt& i) const {
//       i=NodeIt(*this);
//       return i;
//     }
//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
//       i=OutEdgeIt(*this, n);
// //      i=(*first_out_edges)[n];
//       return i;
//     }
//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
//       i=InEdgeIt(*this, n);
//       return i;
//     }
//     EdgeIt& first(EdgeIt& i) const {
//       i=EdgeIt(*this);
//       return i;
//     }

// //     template<typename I> I& first(I& i) const { 
// //       graph->first(i); 
// //       return i;
// //     }
// //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
// // //      e=first_out_edges->get(n);
// //       e=(*first_out_edges)[n];
// //       return e;
// //     }
// //     template<typename I, typename P> I& first(I& i, const P& p) const { 
// //       graph->first(i, p); 
// //       return i;
// //     }
    
//     NodeIt& next(NodeIt& i) const {
//       graph->next(i); 
//       return i;
//     }
//     OutEdgeIt& next(OutEdgeIt& i) const {
//       graph->next(i); 
//       return i;
//     }
//     InEdgeIt& next(InEdgeIt& i) const {
//       graph->next(i); 
//       return i;
//     }
//     EdgeIt& next(EdgeIt& i) const {
//       graph->next(i); 
//       return i;
//     }

// //     template<typename I> I& next(I &i) const { 
// //       graph->next(i); 
// //       return i;
// //     }
    
//     template< typename It > It first() const { 
//       It e; this->first(e); return e; }
    
//     template< typename It > It first(const Node& v) const { 
//       It e; this->first(e, v); return e; }

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


// // FIXME: comparison should be made better!!!
//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
//   class ResGraphWrapper
//   {
//     Graph* graph;
  
//   public:
//     typedef Graph ParentGraph;

//     typedef typename Graph::Node Node;
//     typedef typename Graph::Edge Edge;
  
//     typedef typename Graph::NodeIt NodeIt;
   
//     class OutEdgeIt {
//     public:
//       //Graph::Node n;
//       bool out_or_in;
//       typename Graph::OutEdgeIt o;
//       typename Graph::InEdgeIt i;   
//     };
//     class InEdgeIt {
//     public:
//       //Graph::Node n;
//       bool out_or_in;
//       typename Graph::OutEdgeIt o;
//       typename Graph::InEdgeIt i;   
//     };
//     typedef typename Graph::SymEdgeIt SymEdgeIt;
//     typedef typename Graph::EdgeIt EdgeIt;

//     int nodeNum() const { return gw.nodeNum(); }
//     int edgeNum() const { return gw.edgeNum(); }

//     Node& first(Node& n) const { return gw.first(n); }

//     // Edge and SymEdge  is missing!!!!
//     // Edge <-> In/OutEdgeIt conversion is missing!!!!

//     //FIXME
//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const 
//       {
//      e.n=n;
//      gw.first(e.o,n);
//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
//        gw.goNext(e.o);
//      if(!gw.valid(e.o)) {
//        gw.first(e.i,n);
//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
//          gw.goNext(e.i);
//      }
//      return e;
//       }
// /*
//   OutEdgeIt &goNext(OutEdgeIt &e)
//   {
//   if(gw.valid(e.o)) {
//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
//   gw.goNext(e.o);
//   if(gw.valid(e.o)) return e;
//   else gw.first(e.i,e.n);
//   }
//   else {
//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
//   gw.goNext(e.i);
//   return e;
//   }
//   }
//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
// */
//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}

//     //FIXME
//     InEdgeIt& first(InEdgeIt& e, const Node& n) const 
//       {
//      e.n=n;
//      gw.first(e.i,n);
//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
//        gw.goNext(e.i);
//      if(!gw.valid(e.i)) {
//        gw.first(e.o,n);
//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
//          gw.goNext(e.o);
//      }
//      return e;
//       }
// /*
//   InEdgeIt &goNext(InEdgeIt &e)
//   {
//   if(gw.valid(e.i)) {
//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
//   gw.goNext(e.i);
//   if(gw.valid(e.i)) return e;
//   else gw.first(e.o,e.n);
//   }
//   else {
//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
//   gw.goNext(e.o);
//   return e;
//   }
//   }
//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
// */
//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}

//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
//     //template<typename I> I next(const I i); { return gw.goNext(i); }

//     template< typename It > It first() const { 
//       It e; first(e); return e; }

//     template< typename It > It first(Node v) const { 
//       It e; first(e, v); return e; }

//     Node head(const Edge& e) const { return gw.head(e); }
//     Node tail(const Edge& e) const { return gw.tail(e); }
  
//     template<typename I> Node aNode(const I& e) const { 
//       return gw.aNode(e); }
//     template<typename I> Node bNode(const I& e) const { 
//       return gw.bNode(e); }
  
//     //template<typename I> bool valid(const I i);
//     //{ return gw.valid(i); }
  
//     //template<typename I> void setInvalid(const I &i);
//     //{ return gw.setInvalid(i); }
  
//     Node addNode() { return gw.addNode(); }
//     Edge addEdge(const Node& tail, const Node& head) { 
//       return gw.addEdge(tail, head); }
  
//     template<typename I> void erase(const I& i) { gw.erase(i); }
  
//     void clear() { gw.clear(); }
  
//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
  
//     void setGraph(Graph& _graph) { graph = &_graph; }
//     Graph& getGraph() { return (*graph); }

//     //ResGraphWrapper() : graph(0) { }
//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
//   };

} //namespace hugo

#endif //HUGO_GRAPH_WRAPPER_H