// -*-mode: c++; -*-
#ifndef GRAPH_WRAPPER_H
#define GRAPH_WRAPPER_H

namespace hugo {

  template<typename Graph>
  class TrivGraphWrapper {
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;

    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;

    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef typename Graph::InEdgeIt InEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

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

    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    NodeIt tail(const EdgeIt& e) const { return graph->tail(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(); }
  
    template<typename I> NodeIt aNode(const I& e) const { 
      return graph->aNode(e); }
    template<typename I> NodeIt bNode(const I& e) const { 
      return graph->bNode(e); }
  
    NodeIt addNode() const { return graph->addNode(); }
    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
      return graph->addEdge(tail, head); }
  
    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 TrivGraphWrapper<Graph>& _G) : 
	Graph::NodeMap<T>(_G.getGraph()) { }
      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
	Graph::NodeMap<T>(_G.getGraph(), a) { }
    };

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

  template<typename Graph>
  class RevGraphWrapper
  {
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;

    typedef typename Graph::NodeIt NodeIt;    
    typedef typename Graph::EachNodeIt EachNodeIt;
  
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::OutEdgeIt InEdgeIt;
    typedef typename Graph::InEdgeIt OutEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    typedef typename Graph::EachEdgeIt EachEdgeIt;

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

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

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

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

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

    NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
    NodeIt tail(const EdgeIt& 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> NodeIt aNode(const I& e) const { 
      return graph->aNode(e); }
    template<typename I> NodeIt bNode(const I& e) const { 
      return graph->bNode(e); }

    NodeIt addNode() const { return graph->addNode(); }
    EdgeIt addEdge(const NodeIt& tail, const NodeIt& 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 UndirGraphWrapper {
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;

    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;

    //typedef typename Graph::EdgeIt EdgeIt;
    //typedef typename Graph::OutEdgeIt OutEdgeIt;
    //typedef typename Graph::InEdgeIt InEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    //typedef typename Graph::EachEdgeIt EachEdgeIt;

    //private:
    typedef typename Graph::EdgeIt GraphEdgeIt;
    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    typedef typename Graph::InEdgeIt GraphInEdgeIt;
    //public:

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

    void setGraph(Graph& _graph) { graph = &_graph; }
    Graph& getGraph() const { return (*graph); }
  
    class EdgeIt {
      friend class UndirGraphWrapper<Graph>;
      bool out_or_in; //true iff out
      GraphOutEdgeIt out;
      GraphInEdgeIt in;
    public:
      EdgeIt() : out_or_in(true), out(), in() { }
      operator GraphEdgeIt() const {
	if (out_or_in) return(out); else return(in);
      }
    };

    class OutEdgeIt : public EdgeIt {
      friend class UndirGraphWrapper<Graph>;
    public:
      OutEdgeIt() : EdgeIt() { }
      OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { 
	_G.graph->getFirst(out, n);
	if (!(_G.graph->valid(out))) {
	  out_or_in=false;
	  _G.graph->getFirst(in, n);
	}
      }
    };

    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
      e.out_or_in=true;
      graph->getFirst(e.out, n);
      if (!(graph->valid(e.out))) {
	e.out_or_in=false;
	graph->getFirst(e.in, n);
      }
      return e;
    }

    OutEdgeIt& next(OutEdgeIt& e) const {
      if (e.out_or_in) {
	NodeIt n=graph->tail(e.out);
	graph->next(e.out);
	if (!graph->valid(e.out)) {
	  e.out_or_in=false;
	  graph->getFirst(e.in, n);
	}
      } else {
	graph->next(e.in);
      }
      return e;
    }

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

    typedef OutEdgeIt InEdgeIt; 

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

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

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

    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    NodeIt tail(const EdgeIt& e) const { return graph->tail(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(); }
  
//     template<typename I> NodeIt aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> NodeIt bNode(const I& e) const { 
//       return graph->bNode(e); }
  
    NodeIt addNode() const { return graph->addNode(); }
    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
      return graph->addEdge(tail, head); }
  
    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 UndirGraphWrapper<Graph>& _G) : 
	Graph::NodeMap<T>(_G.getGraph()) { }
      NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : 
	Graph::NodeMap<T>(_G.getGraph(), a) { }
    };

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



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

//     typedef typename Graph::NodeIt NodeIt;
//     typedef typename Graph::EdgeIt EdgeIt;
  
//     typedef typename Graph::EachNodeIt EachNodeIt;
    
//     //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::EachEdgeIt EachEdgeIt;

//     int nodeNum() const { return graph->nodeNum(); }
//     int edgeNum() const { return graph->edgeNum(); }
    
//     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
//     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
//       return graph->getFirst(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; getFirst(e); return e; }

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

//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
  
//     template<typename I> NodeIt aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> NodeIt 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); }
  
//     NodeIt addNode() { return graph->addNode(); }
//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& 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 FlowMap, typename CapacityMap>
  class ResGraphWrapper {
  public:
    typedef Graph BaseGraph;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;
  private:
    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    typedef typename Graph::InEdgeIt OldInEdgeIt;
    const Graph* G;
    FlowMap* flow;
    const CapacityMap* capacity;
  public:

    ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
	     const CapacityMap& _capacity) : 
      G(&_G), flow(&_flow), capacity(&_capacity) { }
//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 
//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }

    void setGraph(const Graph& _graph) { graph = &_graph; }
    const Graph& getGraph() const { return (*G); }

    class EdgeIt; 
    class OutEdgeIt; 
    friend class EdgeIt; 
    friend class OutEdgeIt; 

    class EdgeIt {
      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    protected:
      bool out_or_in; //true, iff out
      OldOutEdgeIt out;
      OldInEdgeIt in;
    public:
      EdgeIt() : out_or_in(true) { } 
//       bool valid() const { 
// 	return out_or_in && out.valid() || in.valid(); }
    };


    class OutEdgeIt : public EdgeIt {
      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    public:
      OutEdgeIt() { }
      //FIXME
      OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
    private:
      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() { 
	resG.G->getFirst(out, v);
	while( out.valid() && !(resG.free(out)>0) ) { ++out; }
	if (!out.valid()) {
	  out_or_in=0;
	  resG.G->getFirst(in, v);
	  while( in.valid() && !(resG.free(in)>0) ) { ++in; }
	}
      }
//     public:
//       OutEdgeIt& operator++() { 
// 	if (out_or_in) {
// 	  NodeIt v=/*resG->*/G->aNode(out);
// 	  ++out;
// 	  while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
// 	  if (!out.valid()) {
// 	    out_or_in=0;
// 	    G->getFirst(in, v); 
// 	    while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
// 	  }
// 	} else {
// 	  ++in;
// 	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
// 	}
// 	return *this; 
//       }
    };

    class EachEdgeIt : public EdgeIt {
      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
      typename Graph::EachNodeIt v;
    public:
      EachEdgeIt() { }
      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
      EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { 
	resG.G->getFirst(v);
	if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
	while (out.valid() && !(resG.free(out)>0) ) { ++out; }
	while (v.valid() && !out.valid()) { 
	  ++v; 
	  if (v.valid()) resG.G->getFirst(out, v); 
	  while (out.valid() && !(resG.free(out)>0) ) { ++out; }
	}
	if (!out.valid()) {
	  out_or_in=0;
	  resG.G->getFirst(v);
	  if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
	  while (in.valid() && !(resG.free(in)>0) ) { ++in; }
	  while (v.valid() && !in.valid()) { 
	    ++v; 
	    if (v.valid()) resG.G->getFirst(in, v); 
	    while (in.valid() && !(resG.free(in)>0) ) { ++in; }
	  }
	}
      }
//       EachEdgeIt& operator++() { 
// 	if (out_or_in) {
// 	  ++out;
// 	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
// 	  while (v.valid() && !out.valid()) { 
// 	    ++v; 
// 	    if (v.valid()) G->getFirst(out, v); 
// 	    while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
// 	  }
// 	  if (!out.valid()) {
// 	    out_or_in=0;
// 	    G->getFirst(v);
// 	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
// 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
// 	    while (v.valid() && !in.valid()) { 
// 	      ++v; 
// 	      if (v.valid()) G->getFirst(in, v); 
// 	      while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
// 	    }  
// 	  }
// 	} else {
// 	  ++in;
// 	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
// 	  while (v.valid() && !in.valid()) { 
// 	    ++v; 
// 	    if (v.valid()) G->getFirst(in, v); 
// 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
// 	  }
// 	}
// 	return *this;
//       }
    };

    EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
    OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 
      e=OutEdgeIt(*this, v); 
    }
    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
      e=EachEdgeIt(*this); 
    }
   
    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }

    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (e.out_or_in) {
	NodeIt v=G->aNode(e.out);
	++(e.out);
	while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
	if (!G->valid(e.out)) {
	  e.out_or_in=0;
	  G->getFirst(e.in, v); 
	  while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
	}
      } else {
	++(e.in);
	while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 
      }
      return e;
    }

    EachEdgeIt& next(EachEdgeIt& e) const { 
      if (e.out_or_in) {
	++(e.out);
	while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
	  while (G->valid(e.v) && !G->valid(e.out)) { 
	    ++(e.v); 
	    if (G->valid(e.v)) G->getFirst(e.out, e.v); 
	    while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
	  }
	  if (!G->valid(e.out)) {
	    e.out_or_in=0;
	    G->getFirst(e.v);
	    if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
	    while (G->valid(e.v) && !G->valid(e.in)) { 
	      ++(e.v); 
	      if (G->valid(e.v)) G->getFirst(e.in, e.v); 
	      while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
	    }  
	  }
	} else {
	  ++(e.in);
	  while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
	  while (G->valid(e.v) && !G->valid(e.in)) { 
	    ++(e.v); 
	    if (G->valid(e.v)) G->getFirst(e.in, e.v); 
	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
	  }
	}
	return e;
      }
    

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

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

    NodeIt tail(EdgeIt e) const { 
      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    NodeIt head(EdgeIt e) const { 
      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

    NodeIt aNode(OutEdgeIt e) const { 
      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    NodeIt bNode(OutEdgeIt e) const { 
      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }

    int id(NodeIt v) const { return G->id(v); }

    bool valid(NodeIt n) const { return G->valid(n); }
    bool valid(EdgeIt e) const { 
      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }

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

    Number free(const EdgeIt& e) const { 
      if (e.out_or_in) 
	return (capacity->get(e.out)-flow->get(e.out)); 
      else 
	return (flow->get(e.in)); 
    }

    Number free(OldOutEdgeIt out) const { 
      return (capacity->get(out)-flow->get(out)); 
    }
    
    Number free(OldInEdgeIt in) const { 
      return (flow->get(in)); 
    }

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

//     template <typename T>
//     class NodeMap {
//       typename Graph::NodeMap<T> node_map; 
//     public:
//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
//       void set(NodeIt nit, T a) { node_map.set(nit, a); }
//       T get(NodeIt 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.getGraph()), backward_map(_G.getGraph()) { }
      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
      void set(EdgeIt e, T a) { 
	if (e.out_or_in) 
	  forward_map.set(e.out, a); 
	else 
	  backward_map.set(e.in, a); 
      }
      T get(EdgeIt e) { 
	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 ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
  protected:
    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
  public:
    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, 
			   const CapacityMap& _capacity) : 
      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 
      first_out_edges(*this) /*, dist(*this)*/ { 
      for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
	OutEdgeIt e;
	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
	first_out_edges.set(n, e);
      }
    }

    //void setGraph(Graph& _graph) { graph = &_graph; }
    //Graph& getGraph() const { return (*graph); }
  
    //TrivGraphWrapper() : graph(0) { }
    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }

    //typedef Graph BaseGraph;

    //typedef typename Graph::NodeIt NodeIt;
    //typedef typename Graph::EachNodeIt EachNodeIt;

    //typedef typename Graph::EdgeIt EdgeIt;
    //typedef typename Graph::OutEdgeIt OutEdgeIt;
    //typedef typename Graph::InEdgeIt InEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    //typedef typename Graph::EachEdgeIt EachEdgeIt;

    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;

    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;

    EachNodeIt& getFirst(EachNodeIt& n) const { 
      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
    }

    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 
      e=first_out_edges.get(n);
      return e;
    }
    
    //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
    //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
    //  return getFirst(i, p); }
    
    //template<typename I> I getNext(const I& i) const { 
    //  return graph->getNext(i); }
    //template<typename I> I& next(I &i) const { return graph->next(i); }    

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

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

    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }

    //template<typename I> bool valid(const I& i) const 
    //  { return graph->valid(i); }
  
    //int nodeNum() const { return graph->nodeNum(); }
    //int edgeNum() const { return graph->edgeNum(); }
  
    //template<typename I> NodeIt aNode(const I& e) const { 
    //  return graph->aNode(e); }
    //template<typename I> NodeIt bNode(const I& e) const { 
    //  return graph->bNode(e); }
  
    //NodeIt addNode() const { return graph->addNode(); }
    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
    //  return graph->addEdge(tail, head); }
  
    //void erase(const OutEdgeIt& e) {
    //  first_out_edge(this->tail(e))=e;
    //}
    void erase(const EdgeIt& e) {
      OutEdgeIt f(e);
      next(f);
      first_out_edges.set(this->tail(e), f);
    }
    //template<typename I> void erase(const I& i) const { graph->erase(i); }
  
    //void clear() const { graph->clear(); }
    
    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 
    public:
      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : 
	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : 
	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
    };

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

  template<typename GraphWrapper> 
  class FilterGraphWrapper {
  };

  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {

    //Graph* graph;
  
  public:
    //typedef Graph BaseGraph;

    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;

    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;

    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
    
  public:
    FilterGraphWrapper(const Graph& _G, FlowMap& _flow, 
			   const CapacityMap& _capacity) : 
      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { 
    }

    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
      return e;
    }

    EachNodeIt& next(EachNodeIt& e) const {
      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    }

    OutEdgeIt& next(OutEdgeIt& e) const {
      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
      return e;
    }

    EachNodeIt& getFirst(EachNodeIt& n) const {
      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
    }

    void erase(const EdgeIt& e) {
      OutEdgeIt f(e);
      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
      while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
      first_out_edges.set(this->tail(e), f);
    }

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

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

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

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

    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    //NodeIt tail(const EdgeIt& e) const { return graph->tail(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(); }
  
    //template<typename I> NodeIt aNode(const I& e) const { 
    //  return graph->aNode(e); }
    //template<typename I> NodeIt bNode(const I& e) const { 
    //  return graph->bNode(e); }
  
    //NodeIt addNode() const { return graph->addNode(); }
    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
    //  return graph->addEdge(tail, head); }
  
    //template<typename I> void erase(const I& i) const { graph->erase(i); }
  
    //void clear() const { graph->clear(); }
    
    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 
    public:
      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
    };

    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> { 
    public:
      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 
	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
    };

  public:
    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;

  };



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

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

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

//     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }

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

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

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

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

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

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

//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
  
//     template<typename I> NodeIt aNode(const I& e) const { 
//       return graph->aNode(e); }
//     template<typename I> NodeIt 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); }
  
//     NodeIt addNode() { return graph->addNode(); }
//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
//       return graph->addEdge(tail, head); }
  
//     template<typename I> void erase(const I& i) { graph->erase(i); }
  
//     void clear() { graph->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 //GRAPH_WRAPPER_H