// -*-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))