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

  /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >

  class RevGraphWrapper : 

    public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {

  protected:

    //Graph* graph;

  public:

    //typedef Graph BaseGraph;

    //typedef typename Graph::Node Node;    

    //typedef typename Graph::NodeIt NodeIt;

    //typedef typename Graph::Edge Edge;

    typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;

    typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;

    //typedef typename Graph::SymEdgeIt SymEdgeIt;

    //typedef typename Graph::EdgeIt EdgeIt;

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

    RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<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 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T> 

    { 

    public:

      NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 

	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }

      NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 

	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }

    };

    template<typename T> class EdgeMap : 

      public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> { 

    public:

      EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 

	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }

      EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 

	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, 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(); }

// FIXME: ez igy nem jo, mert nem

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

//      return graph->addEdge(tail, head); }

    template<typename I> void erase(const I& i) const { 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;