source: lemon-0.x/src/work/marci/graph_wrapper.h @ 371:b2acba449222

// -*- c++ -*-
#ifndef HUGO_GRAPH_WRAPPER_H
#define HUGO_GRAPH_WRAPPER_H

#include <invalid.h>
#include <iter_map.h>

namespace hugo {

  /// Graph wrappers

  /// A main parts of HUGOlib are the different graph structures, 
  /// generic graph algorithms, graph concepts which couple these, and 
  /// graph wrappers. While the previous ones are more or less clear, the 
  /// latter notion needs further explanation.
  /// Graph wrappers are graph classes which serve for considering graph 
  /// structures in different ways. A short example makes the notion much 
  /// clearer. 
  /// Suppose that we have an instance \c g of a directed graph
  /// type say \c ListGraph and an algorithm 
  /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
  /// is needed to run on the reversely oriented graph. 
  /// It may be expensive (in time or in memory usage) to copy 
  /// \c g with the reverse orientation. 
  /// Thus, a wrapper class
  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
  /// The code looks as follows
  /// \code
  /// ListGraph g;
  /// RevGraphWrapper<ListGraph> rgw(g);
  /// int result=algorithm(rgw);
  /// \endcode
  /// After running the algorithm, the original graph \c g 
  /// remains untouched. Thus the graph wrapper used above is to consider the 
  /// original graph with reverse orientation. 
  /// This techniques gives rise to an elegant code, and 
  /// based on stable graph wrappers, complex algorithms can be 
  /// implemented easily. 
  /// In flow, circulation and bipartite matching problems, the residual 
  /// graph is of particular importance. Combining a wrapper implementing 
  /// this, shortest path algorithms and minimum mean cycle algorithms, 
  /// a range of weighted and cardinality optimization algorithms can be 
  /// obtained. For lack of space, for other examples, 
  /// the interested user is referred to the detailed documentation of graph 
  /// wrappers. 
  /// The behavior of graph wrappers can be very different. Some of them keep 
  /// capabilities of the original graph while in other cases this would be 
  /// meaningless. This means that the concepts that they are a model of depend 
  /// on the graph wrapper, and the wrapped graph(s). 
  /// If an edge of \c rgw is deleted, this is carried out by 
  /// deleting the corresponding edge of \c g. But for a residual 
  /// graph, this operation has no sense. 
  /// Let we stand one more example here to simplify your work. 
  /// wrapper class
  /// \code template<typename Graph> class RevGraphWrapper; \endcode 
  /// has constructor 
  /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
  /// This means that in a situation, 
  /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
  /// \code
  /// int algorithm1(const ListGraph& g) {
  ///   RevGraphWrapper<const ListGraph> rgw(g);
  ///   return algorithm2(rgw);
  /// }
  /// \endcode
  template<typename Graph>
  class GraphWrapper {
  protected:
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;
    typedef Graph ParentGraph;

//     GraphWrapper() : graph(0) { }
    GraphWrapper(Graph& _graph) : graph(&_graph) { }
//     void setGraph(Graph& _graph) { graph=&_graph; }
//     Graph& getGraph() const { return *graph; }
 
//    typedef typename Graph::Node Node;
    class Node : public Graph::Node {
      friend class GraphWrapper<Graph>;
    public:
      Node() { }
      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
      Node(const Invalid& i) : Graph::Node(i) { }
    };
    class NodeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
//    typedef typename Graph::Edge Edge;
    class Edge : public Graph::Edge {
      friend class GraphWrapper<Graph>;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
      Edge(const Invalid& i) : Graph::Edge(i) { }
    };
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
   
    NodeIt& first(NodeIt& i) const { 
      i=NodeIt(*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;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }

    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    

    Node head(const Edge& e) const { 
      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    Node tail(const Edge& e) const { 
      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }

    bool valid(const Node& n) const { 
      return graph->valid(static_cast<typename Graph::Node>(n)); }
    bool valid(const Edge& e) const { 
      return graph->valid(static_cast<typename Graph::Edge>(e)); }

    int nodeNum() const { return graph->nodeNum(); }
    int edgeNum() const { return graph->edgeNum(); }
  
    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
  
    Node addNode() const { return Node(graph->addNode()); }
    Edge addEdge(const Node& tail, const Node& head) const { 
      return Edge(graph->addEdge(tail, head)); }

    void erase(const Node& i) const { graph->erase(i); }
    void erase(const Edge& i) const { graph->erase(i); }
  
    void clear() const { graph->clear(); }
    
    template<typename T> class NodeMap : public Graph::NodeMap<T> { 
    public:
      NodeMap(const GraphWrapper<Graph>& _G) :  
        Graph::NodeMap<T>(*(_G.graph)) { }
      NodeMap(const GraphWrapper<Graph>& _G, T a) : 
        Graph::NodeMap<T>(*(_G.graph), a) { }
    };

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

  /// A graph wrapper which reverses the orientation of the edges.

  /// A graph wrapper which reverses the orientation of the edges.
  template<typename Graph>
  class RevGraphWrapper : public GraphWrapper<Graph> {
  public:

    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //If Graph::OutEdgeIt is not defined
    //and we do not want to use RevGraphWrapper::InEdgeIt,
    //the typdef techinque does not work.
    //Unfortunately all the typedefs are instantiated in templates.
    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
    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;
    }

    using GraphWrapper<Graph>::next;
    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }

    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
  };

  /// Wrapper for hiding nodes and edges from a graph.
  
  /// This wrapper shows a graph with filtered node-set and 
  /// edge-set. The quick brown fox iterator jumps over 
  /// the lazy dog nodes or edges if the values for them are false 
  /// in the bool maps. 
  template<typename Graph, typename NodeFilterMap, 
           typename EdgeFilterMap>
  class SubGraphWrapper : public GraphWrapper<Graph> {
  protected:
    NodeFilterMap* node_filter_map;
    EdgeFilterMap* edge_filter_map;
  public:

    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
                    EdgeFilterMap& _edge_filter_map) : 
      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
      edge_filter_map(&_edge_filter_map) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    class NodeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        n(*(_G.graph)) { 
        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
          _G.graph->next(n);
      }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
                const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        e(*(_G.graph)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    NodeIt& first(NodeIt& i) const { 
      i=NodeIt(*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;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
    
    NodeIt& next(NodeIt& i) const {
      graph->next(i.n); 
      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
      return i;
    }
    OutEdgeIt& next(OutEdgeIt& i) const {
      graph->next(i.e); 
      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
      return i;
    }
    InEdgeIt& next(InEdgeIt& i) const {
      graph->next(i.e); 
      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
      return i;
    }
    EdgeIt& next(EdgeIt& i) const {
      graph->next(i.e); 
      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
      return i;
    }

    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

    ///\todo
    ///Some doki, please.
    void hide(const Node& n) const { node_filter_map->set(n, false); }
    ///\todo
    ///Some doki, please.
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    ///\todo
    ///Some doki, please.
    void unHide(const Node& n) const { node_filter_map->set(n, true); }
    ///\todo
    ///Some doki, please.
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    ///\todo
    ///Some doki, please.
    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
    ///\todo
    ///Some doki, please.
    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
  };

  /// A wrapper for forgetting the orientation of a graph.

  /// A wrapper for getting an undirected graph by forgetting
  /// the orientation of a directed one.
  template<typename Graph>
  class UndirGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

    class OutEdgeIt {
      friend class UndirGraphWrapper<Graph>;
      bool out_or_in; //true iff out
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const Invalid& i) : Edge(i) { }
      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
        out_or_in=true; _G.graph->first(out, _n);
        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
      } 
      operator Edge() const { 
        if (out_or_in) return Edge(out); else return Edge(in); 
      }
    };

//FIXME InEdgeIt
    typedef OutEdgeIt InEdgeIt; 

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//FIXME
//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
//       i=InEdgeIt(*this, p); return i;
//     }
//     EdgeIt& first(EdgeIt& i) const { 
//       i=EdgeIt(*this); return i;
//     }

    using GraphWrapper<Graph>::next;
//     NodeIt& next(NodeIt& n) const {
//       GraphWrapper<Graph>::next(n);
//       return n;
//     }
    OutEdgeIt& next(OutEdgeIt& e) const {
      if (e.out_or_in) {
        typename Graph::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;
    }
    //FIXME InEdgeIt
//     EdgeIt& next(EdgeIt& e) const {
//       GraphWrapper<Graph>::next(n);
// //      graph->next(e.e);
//       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); }
  };
  
  /// A wrapper for composing the residual graph for directed flow and circulation problems.

  /// A wrapper for composing the residual graph for directed flow and circulation problems.
  template<typename Graph, typename Number, 
           typename CapacityMap, typename FlowMap>
  class ResGraphWrapper : public GraphWrapper<Graph> {
  protected:
    const CapacityMap* capacity;
    FlowMap* flow;
  public:

    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
                    FlowMap& _flow) : 
      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }

    class Edge; 
    class OutEdgeIt; 
    friend class Edge; 
    friend class OutEdgeIt; 

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    class Edge : public Graph::Edge {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      bool forward; //true, iff forward
//      typename Graph::Edge e;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e, bool _forward) : 
        Graph::Edge(_e), forward(_forward) { }
      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.forward==u.forward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.forward!=u.forward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };

    class OutEdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool forward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
//the unique invalid iterator
      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
        forward=true;
        resG.graph->first(out, v);
        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
        if (!resG.graph->valid(out)) {
          forward=false;
          resG.graph->first(in, v);
          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->forward) 
          return Edge(out, this->forward); 
        else 
          return Edge(in, this->forward);
      }
    };

    class InEdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool forward;
    public:
      InEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
//the unique invalid iterator
      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
        forward=true;
        resG.graph->first(in, v);
        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
        if (!resG.graph->valid(in)) {
          forward=false;
          resG.graph->first(out, v);
          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->forward) 
          return Edge(in, this->forward); 
        else 
          return Edge(out, this->forward);
      }
    };

    class EdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::EdgeIt e;
      bool forward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), forward(false) { }
      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
        forward=true;
        resG.graph->first(e);
        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        if (!resG.graph->valid(e)) {
          forward=false;
          resG.graph->first(e);
          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->forward);
      }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//    FIXME not tested
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
  
    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (e.forward) {
        Node v=graph->aNode(e.out);
        graph->next(e.out);
        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
        if (!graph->valid(e.out)) {
          e.forward=false;
          graph->first(e.in, v); 
          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
        }
      } else {
        graph->next(e.in);
        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (e.forward) {
        Node v=graph->aNode(e.in);
        graph->next(e.in);
        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
        if (!graph->valid(e.in)) {
          e.forward=false;
          graph->first(e.out, v); 
          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
        }
      } else {
        graph->next(e.out);
        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (e.forward) {
        graph->next(e.e);
        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
        if (!graph->valid(e.e)) {
          e.forward=false;
          graph->first(e.e); 
          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
        }
      } else {
        graph->next(e.e);
        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 
      }
      return e;
    }

    Node tail(Edge e) const { 
      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
    Node head(Edge e) const { 
      return ((e.forward) ? graph->head(e) : graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 
      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }

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


//    int id(Node v) const { return graph->id(v); }

    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    bool valid(Edge e) const { 
      return graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    void augment(const Edge& e, Number a) const {
      if (e.forward)  
//      flow->set(e.out, flow->get(e.out)+a);
        flow->set(e, (*flow)[e]+a);
      else  
//      flow->set(e.in, flow->get(e.in)-a);
        flow->set(e, (*flow)[e]-a);
    }

    Number resCap(const Edge& e) const { 
      if (e.forward) 
//      return (capacity->get(e.out)-flow->get(e.out)); 
        return ((*capacity)[e]-(*flow)[e]); 
      else 
//      return (flow->get(e.in)); 
        return ((*flow)[e]); 
    }

//     Number resCap(typename Graph::OutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number resCap(typename Graph::InEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

    template <typename T>
    class EdgeMap {
      typename Graph::EdgeMap<T> forward_map, backward_map; 
    public:
      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
      void set(Edge e, T a) { 
        if (e.forward) 
          forward_map.set(e.out, a); 
        else 
          backward_map.set(e.in, a); 
      }
      T operator[](Edge e) const { 
        if (e.forward) 
          return forward_map[e.out]; 
        else 
          return backward_map[e.in]; 
      }
//       T get(Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map.get(e.out); 
//      else 
//        return backward_map.get(e.in); 
//       }
    };
  };

  /// ErasingFirstGraphWrapper for blocking flows.

  /// ErasingFirstGraphWrapper for blocking flows.
  template<typename Graph, typename FirstOutEdgesMap>
  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
  protected:
    FirstOutEdgesMap* first_out_edges;
  public:
    ErasingFirstGraphWrapper(Graph& _graph, 
                             FirstOutEdgesMap& _first_out_edges) : 
      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
//     class NodeIt { 
//       friend class GraphWrapper<Graph>;
//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//       typename Graph::NodeIt n;
//      public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
//       NodeIt(const Invalid& i) : n(i) { }
//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
//      n(*(_G.graph)) { }
//       operator Node() const { return Node(typename Graph::Node(n)); }
//     };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
                const Node& _n) : 
        e((*_G.first_out_edges)[_n]) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::EdgeIt GraphEdgeIt;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
        e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*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;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }

    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
    
    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

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

  /// A wrapper for composing a bipartite graph.
  /// \c _graph have to be a reference to a graph of type \c Graph 
  /// and \c _s_false_t_true_map is an \c IterableBoolMap 
  /// reference containing the elements for the 
  /// color classes S and T. \c _graph is to be referred to an undirected 
  /// graph or a directed graph with edges oriented from S to T.
  template<typename Graph> 
  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
    SFalseTTrueMap* s_false_t_true_map;
    
  public:
    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
    }
    typedef typename GraphWrapper<Graph>::Node Node;
    //using GraphWrapper<Graph>::NodeIt;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //using GraphWrapper<Graph>::EdgeIt;
    class SNodeIt {
      Node n;
    public:
      SNodeIt() { }
      SNodeIt(const Invalid& i) : n(i) { }
      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
        _G.s_false_t_true_map->first(n, false); 
      }
      operator Node() const { return n; }
    };
    class TNodeIt {
      Node n;
    public:
      TNodeIt() { }
      TNodeIt(const Invalid& i) : n(i) { }
      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
        _G.s_false_t_true_map->first(n, true); 
      }
      operator Node() const { return n; }
    };
    class OutEdgeIt { 
    public:
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
        if (!(*(_G.s_false_t_true_map))[_n]) 
          e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
        else 
          e=INVALID;
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
    public:
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
        if ((*(_G.s_false_t_true_map))[_n]) 
          e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
        else 
          e=INVALID;
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }

    using GraphWrapper<Graph>::next;
    SNodeIt& next(SNodeIt& n) const { 
      this->s_false_t_true_map->next(n); return n; 
    }
    TNodeIt& next(TNodeIt& n) const { 
      this->s_false_t_true_map->next(n); return n; 
    }

    Node tail(const Edge& e) { 
      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
        return Node(this->graph->tail(e));
      else
        return Node(this->graph->head(e));      
    }
    Node head(const Edge& e) { 
      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
        return Node(this->graph->head(e));
      else
        return Node(this->graph->tail(e));      
    }

    Node aNode(const OutEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); 
    }
    Node aNode(const InEdgeIt& e) const { 
      return Node(this->graph->aNode(e.e)); 
    }
    Node bNode(const OutEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); 
    }
    Node bNode(const InEdgeIt& e) const { 
      return Node(this->graph->bNode(e.e)); 
    }
  };



//   /// experimentral, do not try it.
//   template<typename Graph>
//   class stGraphWrapper : public GraphWrapper<Graph> {
//   public:
//     class Node;
//     class NodeIt;
//     class Edge;
//     class OutEdgeIt;
//     class InEdgeIt;
//     class EdgeIt;

//     const Node s;
//     const Node t;

//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph), 
//                                  s(INVALID, 1), t(INVALID, 2) { }

//     class Node : public Graph::Node {
//       friend class GraphWrapper<Graph>;
//       friend class stGraphWrapper<Graph>;
//     protected:
//       int spec; //0 if real node, 1 iff s, 2 iff t
//     public:
//       Node() { }
//       Node(const typename Graph::Node& _n, int _spec=0) : 
//      Graph::Node(_n), spec(_spec) { }
//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
//       //invalid: (invalid, 2);
//     };

//     class NodeIt { 
//       friend class GraphWrapper<Graph>;
//       friend class stGraphWrapper<Graph>;
//       typename Graph::NodeIt n;
//       int spec; 
//      public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) : 
//      n(_n), spec(_spec) { }
//       NodeIt(const Invalid& i) : n(i), spec(2) { }
//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
//      if (!_G->valid(n)) spec=1;
//       }
//       operator Node() const { return Node(n, spec); }
//     };
// //    typedef typename Graph::Edge Edge;
//     class Edge : public Graph::Edge {
//       friend class GraphWrapper<Graph>;
//       friend class stGraphWrapper<Graph>;
//       Node tail_spec;
//       Node head_spec;
//     public:
//       Edge() { }
//       Edge(const typename Graph::Edge& _e) : 
//      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) { 
//      //a tail-t es a head-et real node-ra csinaljuk
//       }
//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
//     };
//     class OutEdgeIt { 
//       friend class GraphWrapper<Graph>;
//       friend class stGraphWrapper<Graph>;
//       typename Graph::OutEdgeIt e;
//       Node tail_spec;
//       Node head_spec;
//     public:
//       OutEdgeIt() { }
//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : 
//      e(_e), tail_spec(i, 0), head_spec(i, 0) { 
//      //a tail-t es a head-et real node-ra csinaljuk
//       }
//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
//       //invalid: (barmi, 0, 2)
//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
//      switch (_n.spec) {
//      case 0 : 
//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 
//        _tail.spec=0;
//        _head.spec=0;
//        if (!_G.graph->valid(e)) spec=1;
//        break;
//      case 1:
//        e=INVALID;
//        _tail.spec=1;
//        _head(_G.graph->first(typename Graph::NodeIt()));
//        if _head.spec==1
//        break;
//      };
        
//        }
//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
//     };
//     class InEdgeIt { 
//       friend class GraphWrapper<Graph>;
//       typename Graph::InEdgeIt e;
//     public:
//       InEdgeIt() { }
//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
//       InEdgeIt(const Invalid& i) : e(i) { }
//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
//      e(*(_G.graph), typename Graph::Node(_n)) { }
//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
//     };
//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
//     class EdgeIt { 
//       friend class GraphWrapper<Graph>;
//       typename Graph::EdgeIt e;
//     public:
//       EdgeIt() { }
//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
//       EdgeIt(const Invalid& i) : e(i) { }
//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
//     };
   
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*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;
//     }
//     EdgeIt& first(EdgeIt& i) const { 
//       i=EdgeIt(*this); return i;
//     }

//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    

//     Node head(const Edge& e) const { 
//       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
//     Node tail(const Edge& e) const { 
//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }

//     bool valid(const Node& n) const { 
//       return graph->valid(static_cast<typename Graph::Node>(n)); }
//     bool valid(const Edge& e) const { 
//       return graph->valid(static_cast<typename Graph::Edge>(e)); }

//     int nodeNum() const { return graph->nodeNum(); }
//     int edgeNum() const { return graph->edgeNum(); }
  
//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
  
//     Node addNode() const { return Node(graph->addNode()); }
//     Edge addEdge(const Node& tail, const Node& head) const { 
//       return Edge(graph->addEdge(tail, head)); }

//     void erase(const Node& i) const { graph->erase(i); }
//     void erase(const Edge& i) const { graph->erase(i); }
  
//     void clear() const { graph->clear(); }
    
//     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
//     public:
//       NodeMap(const GraphWrapper<Graph>& _G) :  
//      Graph::NodeMap<T>(*(_G.graph)) { }
//       NodeMap(const GraphWrapper<Graph>& _G, T a) : 
//      Graph::NodeMap<T>(*(_G.graph), a) { }
//     };

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

} //namespace hugo

#endif //HUGO_GRAPH_WRAPPER_H