// -*- c++ -*-

 #ifndef GRAPH_WRAPPER_H

 #define GRAPH_WRAPPER_H

 #include <invalid.h>

 namespace hugo {

   template<typename Graph>

   class TrivGraphWrapper {

   protected:

     Graph* graph;

   public:

     typedef Graph BaseGraph;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     typedef typename Graph::InEdgeIt InEdgeIt;

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     typedef typename Graph::EdgeIt EdgeIt;

     //TrivGraphWrapper() : graph(0) { }

     TrivGraphWrapper(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 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; 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->head(e); }

     Node tail(const Edge& 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> 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); }

     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 GraphWrapper>

   class GraphWrapperSkeleton {

   protected:

     GraphWrapper gw;

   public:

     typedef typename GraphWrapper::BaseGraph BaseGraph;

     typedef typename GraphWrapper::Node Node;

     typedef typename GraphWrapper::NodeIt NodeIt;

     typedef typename GraphWrapper::Edge Edge;

     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

     typedef typename GraphWrapper::EdgeIt EdgeIt;

     //GraphWrapperSkeleton() : gw() { }

     GraphWrapperSkeleton(GraphWrapper& _gw) : gw(_gw) { }

     void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }

     BaseGraph& getGraph() const { return gw.getGraph(); }

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

     template<typename I, typename P> I& first(I& i, const P& p) const { 

       return gw.first(i, p); }

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

     template<typename I> I& next(I &i) const { return gw.next(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); }

     //template<typename I> void setInvalid(const I &i);

     //{ return graph->setInvalid(i); }

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

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

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

     Node addNode() const { return gw.addNode(); }

     Edge addEdge(const Node& tail, const Node& head) const { 

       return gw.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 GraphWrapper::NodeMap<T> { 

     public:

       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 

 	GraphWrapper::NodeMap<T>(_G.gw) { }

       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : 

 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

     };

     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { 

     public:

       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : 

 	GraphWrapper::EdgeMap<T>(_G.gw) { }

       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : 

 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

     };

   };

   template<typename Graph>

   class RevGraphWrapper

   {

   protected:

     Graph* graph;

   public:

     typedef Graph BaseGraph;

     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 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; 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 UndirGraphWrapper {

   protected:

     Graph* graph;

   public:

     typedef Graph BaseGraph;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     //typedef typename Graph::Edge Edge;

     //typedef typename Graph::OutEdgeIt OutEdgeIt;

     //typedef typename Graph::InEdgeIt InEdgeIt;

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     //typedef typename Graph::EdgeIt EdgeIt;

     //private:

     typedef typename Graph::Edge GraphEdge;

     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 Edge {

       friend class UndirGraphWrapper<Graph>;

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

       }

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

       } 

     };

     class OutEdgeIt : public Edge {

       friend class UndirGraphWrapper<Graph>;

     public:

       OutEdgeIt() : Edge() { }

       OutEdgeIt(const Invalid& i) : Edge(i) { }

       OutEdgeIt(const UndirGraphWrapper& _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);

 	}

       }

     };

     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

       e.out_or_in=true;

       graph->first(e.out, n);

       if (!(graph->valid(e.out))) {

 	e.out_or_in=false;

 	graph->first(e.in, n);

       }

       return e;

     }

     OutEdgeIt& next(OutEdgeIt& e) const {

       if (e.out_or_in) {

 	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;

     }

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

     typedef OutEdgeIt InEdgeIt; 

     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 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; 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->head(e); }

     Node tail(const Edge& 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> 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); }

     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::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 FlowMap, typename CapacityMap>

   class ResGraphWrapper {

   public:

     typedef Graph BaseGraph;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

   private:

     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

     typedef typename Graph::InEdgeIt OldInEdgeIt;

   protected:

     const Graph* graph;

     FlowMap* flow;

     const CapacityMap* capacity;

   public:

     ResGraphWrapper(const Graph& _G, FlowMap& _flow, 

 	     const CapacityMap& _capacity) : 

       graph(&_G), flow(&_flow), capacity(&_capacity) { }

     void setGraph(const Graph& _graph) { graph = &_graph; }

     const Graph& getGraph() const { return (*graph); }

     class Edge; 

     class OutEdgeIt; 

     friend class Edge; 

     friend class OutEdgeIt; 

     class Edge {

       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

     protected:

       bool out_or_in; //true, iff out

       OldOutEdgeIt out;

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

       } 

     };

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

     private:

       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 

 	resG.graph->first(out, v);

 	while( resG.graph->valid(out) && !(resG.free(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.free(in)>0) ) { resG.graph->next(in); }

 	}

       }

 //     public:

 //       OutEdgeIt& operator++() { 

 // 	if (out_or_in) {

 // 	  Node v=/*resG->*/G->aNode(out);

 // 	  ++out;

 // 	  while( out.valid() && !(Edge::free()>0) ) { ++out; }

 // 	  if (!out.valid()) {

 // 	    out_or_in=0;

 // 	    G->first(in, v); 

 // 	    while( in.valid() && !(Edge::free()>0) ) { ++in; }

 // 	  }

 // 	} else {

 // 	  ++in;

 // 	  while( in.valid() && !(Edge::free()>0) ) { ++in; } 

 // 	}

 // 	return *this; 

 //       }

     };

     class EdgeIt : public Edge {

       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

       typename Graph::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=OldOutEdgeIt(INVALID);

 	while (resG.graph->valid(out) && !(resG.free(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.free(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=OldInEdgeIt(INVALID);

 	  while (resG.graph->valid(in) && !(resG.free(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.free(in)>0) ) { resG.graph->next(in); }

 	  }

 	}

       }

 //       EdgeIt& operator++() { 

 // 	if (out_or_in) {

 // 	  ++out;

 // 	  while (out.valid() && !(Edge::free()>0) ) { ++out; }

 // 	  while (v.valid() && !out.valid()) { 

 // 	    ++v; 

 // 	    if (v.valid()) G->first(out, v); 

 // 	    while (out.valid() && !(Edge::free()>0) ) { ++out; }

 // 	  }

 // 	  if (!out.valid()) {

 // 	    out_or_in=0;

 // 	    G->first(v);

 // 	    if (v.valid()) G->first(in, v); else in=OldInEdgeIt();

 // 	    while (in.valid() && !(Edge::free()>0) ) { ++in; }

 // 	    while (v.valid() && !in.valid()) { 

 // 	      ++v; 

 // 	      if (v.valid()) G->first(in, v); 

 // 	      while (in.valid() && !(Edge::free()>0) ) { ++in; }

 // 	    }  

 // 	  }

 // 	} else {

 // 	  ++in;

 // 	  while (in.valid() && !(Edge::free()>0) ) { ++in; }

 // 	  while (v.valid() && !in.valid()) { 

 // 	    ++v; 

 // 	    if (v.valid()) G->first(in, v); 

 // 	    while (in.valid() && !(Edge::free()>0) ) { ++in; }

 // 	  }

 // 	}

 // 	return *this;

 //       }

     };

     NodeIt& first(NodeIt& v) const { return graph->first(v); }

     OutEdgeIt& first(OutEdgeIt& e, Node v) const { 

       e=OutEdgeIt(*this, v); 

       return e;

     }

     EdgeIt& first(EdgeIt& e) const { 

       e=EdgeIt(*this); 

       return e;

     }

     NodeIt& next(NodeIt& n) const { return graph->next(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) && !(free(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) && !(free(e.in)>0) ) { graph->next(e.in); }

 	}

       } else {

 	graph->next(e.in);

 	while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 

       }

       return e;

     }

     EdgeIt& next(EdgeIt& e) const { 

       if (e.out_or_in) {

 	graph->next(e.out);

 	while (graph->valid(e.out) && !(free(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) && !(free(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=OldInEdgeIt(INVALID);

 	    while (graph->valid(e.in) && !(free(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) && !(free(e.in)>0) ) { graph->next(e.in); }

 	    }  

 	  }

 	} else {

 	  graph->next(e.in);

 	  while (graph->valid(e.in) && !(free(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) && !(free(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 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);

       else  

 	flow->set(e.in, flow->get(e.in)-a);

     }

     Number free(const Edge& 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.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.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(Edge e, T a) { 

 	if (e.out_or_in) 

 	  forward_map.set(e.out, a); 

 	else 

 	  backward_map.set(e.in, a); 

       }

       T get(Edge 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(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {

 	OutEdgeIt e;

 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(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::Node Node;

     //typedef typename Graph::NodeIt NodeIt;

     //typedef typename Graph::Edge Edge;

     //typedef typename Graph::OutEdgeIt OutEdgeIt;

     //typedef typename Graph::InEdgeIt InEdgeIt;

     //typedef typename Graph::SymEdgeIt SymEdgeIt;

     //typedef typename Graph::EdgeIt EdgeIt;

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

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

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

     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>::EdgeIt EdgeIt;

     NodeIt& first(NodeIt& n) const { 

       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

     }

     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 

       e=first_out_edges.get(n);

       return e;

     }

     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }

     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const { 

     //  return first(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; 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->head(e); }

     //Node tail(const Edge& 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> 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); }

     //void erase(const OutEdgeIt& e) {

     //  first_out_edge(this->tail(e))=e;

     //}

     void erase(const Edge& 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>::Node Node;

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

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

     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>::EdgeIt EdgeIt;

     //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, graph->nodeNum()) { 

     }

     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);

       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) 

 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

       return e;

     }

     NodeIt& next(NodeIt& 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;

     }

     NodeIt& first(NodeIt& n) const {

       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

     }

     void erase(const Edge& 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& 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 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; 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->head(e); }

     //Node tail(const Edge& 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> 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); }

     //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::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 graph->nodeNum(); }

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

 //     Node& first(Node& n) const { return graph->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;

 // 	graph->first(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->first(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->first(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& first(InEdgeIt& e, const Node& n) const 

 //       {

 // 	e.n=n;

 // 	graph->first(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->first(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->first(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; 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 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