source: lemon-0.x/src/work/athos/graph_wrapper.h @ 276:b38f4cfa76cf

// -*- c++ -*-
#ifndef HUGO_GRAPH_WRAPPER_H
#define HUGO_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;
    class NodeIt : public Graph::NodeIt { 
    public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
      NodeIt(const TrivGraphWrapper<Graph>& _G) : 
        Graph::NodeIt(*(_G.graph)) { }
    };
    typedef typename Graph::Edge Edge;
    //typedef typename Graph::OutEdgeIt OutEdgeIt;
    class OutEdgeIt : public Graph::OutEdgeIt { 
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
      OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 
        Graph::OutEdgeIt(*(_G.graph), n) { }
    };
    //typedef typename Graph::InEdgeIt InEdgeIt;
    class InEdgeIt : public Graph::InEdgeIt { 
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
      InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : 
        Graph::InEdgeIt(*(_G.graph), n) { }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    //typedef typename Graph::EdgeIt EdgeIt;
    class EdgeIt : public Graph::EdgeIt { 
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
      EdgeIt(const TrivGraphWrapper<Graph>& _G) : 
        Graph::EdgeIt(*(_G.graph)) { }
    };

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

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

    NodeIt& first(NodeIt& i) const { 
      i=NodeIt(*this);
      return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this);
      return i;
    }
//     template<typename I> I& first(I& i) const { 
//       //return graph->first(i); 
//       i=I(*this);
//       return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p);
      return i;
    }
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p);
      return i;
    }
//     template<typename I, typename P> I& first(I& i, const P& p) const { 
//       //return graph->first(i, p);
//       i=I(*this, p);
//       return i;
//     }
    
//    template<typename I> I getNext(const I& i) const { 
//      return graph->getNext(i); }
    template<typename I> I& next(I &i) const { graph->next(i); return 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.graph)) { }
      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
        Graph::NodeMap<T>(*(_G.graph), a) { }
    };

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

    template<typename Map, typename T> class NodeMapWrapper {
    protected:
      Map* map;
    public:
      NodeMapWrapper(Map& _map) : map(&_map) { }
      //template<typename T> 
      void set(Node n, T a) { map->set(n, a); }
      //template<typename T>
      T get(Node n) const { return map->get(n); }
    };

    template<typename Map, typename T> class EdgeMapWrapper {
    protected:
      Map* map;
    public:
      EdgeMapWrapper(Map& _map) : map(&_map) { }
      //template<typename T> 
      void set(Edge n, T a) { map->set(n, a); }
      //template<typename T>
      T get(Edge n) const { return map->get(n); }
    };
  };

  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;

    typedef typename GraphWrapper::Node Node;
    class NodeIt : public GraphWrapper::NodeIt { 
    public:
      NodeIt() { }
      NodeIt(const typename GraphWrapper::NodeIt& n) : 
        GraphWrapper::NodeIt(n) { }
      NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
      NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
        GraphWrapper::NodeIt(_G.gw) { }
    };
    typedef typename GraphWrapper::Edge Edge;
    //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    class OutEdgeIt : public GraphWrapper::OutEdgeIt { 
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) : 
        GraphWrapper::OutEdgeIt(e) { }
      OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
      OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) : 
        GraphWrapper::OutEdgeIt(_G.gw, n) { }
    };
    //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
    class InEdgeIt : public GraphWrapper::InEdgeIt { 
    public:
      InEdgeIt() { }
      InEdgeIt(const typename GraphWrapper::InEdgeIt& e) : 
        GraphWrapper::InEdgeIt(e) { }
      InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
      InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) : 
        GraphWrapper::InEdgeIt(_G.gw, n) { }
    };
    //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
    //typedef typename GraphWrapper::EdgeIt EdgeIt;
    class EdgeIt : public GraphWrapper::EdgeIt { 
    public:
      EdgeIt() { }
      EdgeIt(const typename GraphWrapper::EdgeIt& e) : 
        GraphWrapper::EdgeIt(e) { }
      EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
      EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) : 
        GraphWrapper::EdgeIt(_G.gw) { }
    };


    //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 {       
      i=I(*this);
      return i;
    }
    template<typename I, typename P> I& first(I& i, const P& p) const { 
      i=I(*this, p);
      return i; 
    }
    
//    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
    template<typename I> I& next(I &i) const { gw.next(i); return i; }    

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

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

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

    template<typename I> bool valid(const I& i) const { return gw.valid(i); }
  
    //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 GraphWrapper>
  class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
  public:
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;

    RevGraphWrapper(GraphWrapper _gw) : 
      GraphWrapperSkeleton<GraphWrapper>(_gw) { }  

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

  //Subgraph on the same node-set and partial edge-set
  template<typename GraphWrapper, typename EdgeFilterMap>
  class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
  protected:
    EdgeFilterMap* filter_map;
  public:
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

    SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) : 
      GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }  

    template<typename I> I& first(I& i) const { 
      gw.first(i); 
      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    template<typename I, typename P> I& first(I& i, const P& p) const { 
      gw.first(i, p); 
      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    
    //template<typename I> I getNext(const I& i) const { 
    //  return gw.getNext(i); 
    //}
    template<typename I> I& next(I &i) const { 
      gw.next(i); 
      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    
    template< typename It > It first() const { 
      It e; this->first(e); return e; }
    
    template< typename It > It first(const Node& v) const { 
      It e; this->first(e, v); return e; }
  };

//   template<typename GraphWrapper>
//   class UndirGraphWrapper {
//   protected:
//     //Graph* graph;
//     GraphWrapper gw;

//   public:
//     typedef GraphWrapper BaseGraph;

//     typedef typename GraphWrapper::Node Node;
//     typedef typename GraphWrapper::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 GraphWrapper::Edge GraphEdge;
//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
//     //public:

//     //UndirGraphWrapper() : graph(0) { }
//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

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

//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
//       e.out_or_in=true;
//       gw.first(e.out, n);
//       if (!(gw.valid(e.out))) {
//      e.out_or_in=false;
//      gw.first(e.in, n);
//       }
//       return e;
//     }

//     OutEdgeIt& next(OutEdgeIt& e) const {
//       if (e.out_or_in) {
//      Node n=gw.tail(e.out);
//      gw.next(e.out);
//      if (!gw.valid(e.out)) {
//        e.out_or_in=false;
//        gw.first(e.in, n);
//      }
//       } else {
//      gw.next(e.in);
//       }
//       return e;
//     }

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

//     typedef OutEdgeIt InEdgeIt; 

//     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 graph->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; 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 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 graph->aNode(e); }
// //     template<typename I> Node bNode(const I& e) const { 
// //       return graph->bNode(e); }
  
//     Node addNode() const { return gw.addNode(); }
// // FIXME: ez igy nem jo, mert nem
// //    Edge addEdge(const Node& tail, const Node& head) const { 
// //      return graph->addEdge(tail, head); }
  
//     template<typename I> void erase(const I& i) const { gw.erase(i); }
  
//     void clear() const { gw.clear(); }
    
//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { 
//     public:
//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) : 
//      GraphWrapper::NodeMap<T>(_G.gw) { }
//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : 
//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
//     };

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


  template<typename GraphWrapper>
  class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
  protected:
//    GraphWrapper gw;

  public:
    //typedef GraphWrapper BaseGraph;

    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

    //private:
    //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy 
    //legyenek, at kell irni
    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
    GraphWrapper::Edge GraphEdge;
    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 
    GraphWrapper::OutEdgeIt GraphOutEdgeIt;
    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/ 
    GraphWrapper::InEdgeIt GraphInEdgeIt;
    //public:

    //UndirGraphWrapper() : graph(0) { }
    UndirGraphWrapper(GraphWrapper _gw) : 
      GraphWrapperSkeleton<GraphWrapper>(_gw) { }  

    //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

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

    class OutEdgeIt : public Edge {
      friend class UndirGraphWrapper<GraphWrapper>;
    public:
      OutEdgeIt() : Edge() { }
      OutEdgeIt(const Invalid& i) : Edge(i) { }
      OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n) 
        : Edge() { 
        out_or_in=true; _G.gw.first(out, n);
        if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
      }
    };

    typedef OutEdgeIt InEdgeIt; 

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

    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
      e.out_or_in=true; gw.first(e.out, n);
      if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
      return e;
    }

    EdgeIt& first(EdgeIt& e) const {
      e.out_or_in=true;
      //NodeIt v;
      first(e.v);
      if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
      while (valid(e.v) && !gw.valid(e.out)) { 
        gw.next(e.v); 
        if (valid(e.v)) gw.first(e.out, e.v); 
      }
      return e;
    }

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

    OutEdgeIt& next(OutEdgeIt& e) const {
      if (e.out_or_in) {
        Node n=gw.tail(e.out);
        gw.next(e.out);
        if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
      } else {
        gw.next(e.in);
      }
      return e;
    }

    EdgeIt& next(EdgeIt& e) const {
      //NodeIt v=tail(e);
      gw.next(e.out);
      while (valid(e.v) && !gw.valid(e.out)) { 
        next(e.v); 
        if (valid(e.v)) gw.first(e.out, e.v); 
      }
      return e;
    }

    template<typename I> I& next(I &i) const { return gw.next(i); }    
//    template<typename I> I getNext(const I& i) const { return gw.getNext(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 gw.head(e); }
//    Node tail(const Edge& e) const { return gw.tail(e); }

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

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

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

//     template<typename T> class EdgeMap : 
//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> { 
//     public:
//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) : 
//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : 
//      GraphWrapper::EdgeMap<T>(_G.gw, 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 GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
  class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
  public:
    //typedef Graph BaseGraph;
    //typedef TrivGraphWrapper<const Graph> GraphWrapper;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
  private:
    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
    GraphWrapper::OutEdgeIt OldOutEdgeIt;
    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
    GraphWrapper::InEdgeIt OldInEdgeIt;

    typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
    GraphWrapper::Edge OldEdge;
  protected:
    //const Graph* graph;
    //GraphWrapper gw;
    FlowMap* flow;
    const CapacityMap* capacity;
  public:

    ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow, 
                    const CapacityMap& _capacity) : 
      GraphWrapperSkeleton<GraphWrapper>(_gw), 
      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<GraphWrapper, 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);
      }
      operator OldEdge() {
        if(out_or_in)
          return out; 
        else
          return in;
      }
    };


    class OutEdgeIt : public Edge {
      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
    public:
      OutEdgeIt() { }
      //FIXME
      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : Edge(i) { }
    protected:
      OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 
        resG.gw.first(out, v);
        while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
        if (!resG.gw.valid(out)) {
          out_or_in=0;
          resG.gw.first(in, v);
          while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
        }
      }
//     public:
//       OutEdgeIt& operator++() { 
//      if (out_or_in) {
//        Node v=/*resG->*/G->aNode(out);
//        ++out;
//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        if (!out.valid()) {
//          out_or_in=0;
//          G->first(in, v); 
//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        }
//      } else {
//        ++in;
//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 
//      }
//      return *this; 
//       }
    };

    //FIXME This is just for having InEdgeIt
    typedef void InEdgeIt;

    class EdgeIt : public Edge {
      friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
      NodeIt v; 
    public:
      EdgeIt() { }
      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
      EdgeIt(const Invalid& i) : Edge(i) { }
      EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() { 
        resG.gw.first(v);
        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
        while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
        while (resG.gw.valid(v) && !resG.gw.valid(out)) { 
          resG.gw.next(v); 
          if (resG.gw.valid(v)) resG.gw.first(out, v); 
          while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
        }
        if (!resG.gw.valid(out)) {
          out_or_in=0;
          resG.gw.first(v);
          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
          while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
          while (resG.gw.valid(v) && !resG.gw.valid(in)) { 
            resG.gw.next(v); 
            if (resG.gw.valid(v)) resG.gw.first(in, v); 
            while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
          }
        }
      }
//       EdgeIt& operator++() { 
//      if (out_or_in) {
//        ++out;
//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        while (v.valid() && !out.valid()) { 
//          ++v; 
//          if (v.valid()) G->first(out, v); 
//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
//        }
//        if (!out.valid()) {
//          out_or_in=0;
//          G->first(v);
//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//          while (v.valid() && !in.valid()) { 
//            ++v; 
//            if (v.valid()) G->first(in, v); 
//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//          }  
//        }
//      } else {
//        ++in;
//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        while (v.valid() && !in.valid()) { 
//          ++v; 
//          if (v.valid()) G->first(in, v); 
//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
//        }
//      }
//      return *this;
//       }
    };

    NodeIt& first(NodeIt& v) const { gw.first(v); return 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 gw.next(n); }

    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (e.out_or_in) {
        Node v=gw.aNode(e.out);
        gw.next(e.out);
        while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
        if (!gw.valid(e.out)) {
          e.out_or_in=0;
          gw.first(e.in, v); 
          while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
        }
      } else {
        gw.next(e.in);
        while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 
      }
      return e;
    }

    EdgeIt& next(EdgeIt& e) const { 
      if (e.out_or_in) {
        gw.next(e.out);
        while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
          while (gw.valid(e.v) && !gw.valid(e.out)) { 
            gw.next(e.v); 
            if (gw.valid(e.v)) gw.first(e.out, e.v); 
            while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
          }
          if (!gw.valid(e.out)) {
            e.out_or_in=0;
            gw.first(e.v);
            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
            while (gw.valid(e.v) && !gw.valid(e.in)) { 
              gw.next(e.v); 
              if (gw.valid(e.v)) gw.first(e.in, e.v); 
              while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
            }  
          }
        } else {
          gw.next(e.in);
          while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
          while (gw.valid(e.v) && !gw.valid(e.in)) { 
            gw.next(e.v); 
            if (gw.valid(e.v)) gw.first(e.in, e.v); 
            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.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) ? gw.aNode(e.out) : gw.aNode(e.in)); }
    Node head(Edge e) const { 
      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

    Node aNode(OutEdgeIt e) const { 
      return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

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


    int id(Node v) const { return gw.id(v); }

    bool valid(Node n) const { return gw.valid(n); }
    bool valid(Edge e) const { 
      return e.out_or_in ? gw.valid(e.out) : gw.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 resCap(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 resCap(OldOutEdgeIt out) const { 
      return ( (*capacity)[out] - (*flow)[out]); 
    }
    
    Number resCap(OldInEdgeIt in) const { 
      return ( (*flow)[in] ); 
    }

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

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

    template <typename T>
    class EdgeMap {
      typename GraphWrapper::EdgeMap<T> forward_map, backward_map; 
    public:
      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
      EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, 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); 
      }
    };
  };

  //Subgraph on the same node-set and partial edge-set
  template<typename GraphWrapper, typename FirstOutEdgesMap>
  class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
  protected:
    FirstOutEdgesMap* first_out_edges;
  public:
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

    ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) : 
      GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }  

    template<typename I> I& first(I& i) const { 
      gw.first(i); 
      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
      e=first_out_edges->get(n);
      return e;
    }
    template<typename I, typename P> I& first(I& i, const P& p) const { 
      gw.first(i, p); 
      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    
    //template<typename I> I getNext(const I& i) const { 
    //  return gw.getNext(i); 
    //}
    template<typename I> I& next(I &i) const { 
      gw.next(i); 
      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
      return i;
    }
    
    template< typename It > It first() const { 
      It e; this->first(e); return e; }
    
    template< typename It > It first(const Node& v) const { 
      It e; this->first(e, v); return e; }

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

//   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 gw.getNext(i); }
//     //template<typename I> I& next(I &i) const { return gw.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 gw.head(e); }
//     //Node tail(const Edge& e) const { return gw.tail(e); }

//     //template<typename I> bool valid(const I& i) const 
//     //  { return gw.valid(i); }
  
//     //int nodeNum() const { return gw.nodeNum(); }
//     //int edgeNum() const { return gw.edgeNum(); }
  
//     //template<typename I> Node aNode(const I& e) const { 
//     //  return 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); }
  
//     //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 { gw.erase(i); }
  
//     //void clear() const { gw.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, gw.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 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; 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 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 gw.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 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 gw.nodeNum(); }
//     int edgeNum() const { return gw.edgeNum(); }

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

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

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

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

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

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

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

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

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

} //namespace hugo

#endif //HUGO_GRAPH_WRAPPER_H