// -*- 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 tail(const Edge& e) const { 

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

    Node head(const Edge& e) const { 

      return Node(graph->head(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::template NodeMap<T> { 

      typedef typename Graph::template NodeMap<T> Parent;

    public:

      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }

      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }

    };

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

      typedef typename Graph::template EdgeMap<T> Parent;

    public:

      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }

      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_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::InEdgeIt e;

    public:

      OutEdgeIt() { }

      OutEdgeIt(const typename Graph::InEdgeIt& _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::OutEdgeIt e;

    public:

      InEdgeIt() { }

      InEdgeIt(const typename Graph::OutEdgeIt& _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 { this->graph->next(i.e); return i; }

    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

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

    Node tail(const Edge& e) const { 

      return GraphWrapper<Graph>::head(e); }

    Node head(const Edge& e) const { 

      return GraphWrapper<Graph>::tail(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 {

      this->graph->next(i.n); 

      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 

	this->graph->next(i.n); }

      return i;

    }

    OutEdgeIt& next(OutEdgeIt& i) const {

      this->graph->next(i.e); 

      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

	this->graph->next(i.e); }

      return i;

    }

    InEdgeIt& next(InEdgeIt& i) const {

      this->graph->next(i.e); 

      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

	this->graph->next(i.e); }

      return i;

    }

    EdgeIt& next(EdgeIt& i) const {

      this->graph->next(i.e); 

      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 

	this->graph->next(i.e); }

      return i;

    }

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

    ///\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=this->graph->tail(e.out);

	this->graph->next(e.out);

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

	  e.out_or_in=false; this->graph->first(e.in, n); }

      } else {

	this->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 this->graph->tail(e); else 

	return this->graph->head(e); }

    Node bNode(const OutEdgeIt& e) const { 

      if (e.out_or_in) return this->graph->head(e); else 

	return this->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=this->graph->aNode(e.out);

	this->graph->next(e.out);

	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 

	  this->graph->next(e.out); }

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

	  e.forward=false;

	  this->graph->first(e.in, v); 

	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 

	    this->graph->next(e.in); }

	}

      } else {

	this->graph->next(e.in);

	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 

	  this->graph->next(e.in); } 

      }

      return e;

    }

//     FIXME Not tested

    InEdgeIt& next(InEdgeIt& e) const { 

      if (e.forward) {

	Node v=this->graph->aNode(e.in);

	this->graph->next(e.in);

	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 

	  this->graph->next(e.in); }

	if (!this->graph->valid(e.in)) {

	  e.forward=false;

	  this->graph->first(e.out, v); 

	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 

	    this->graph->next(e.out); }

	}

      } else {

	this->graph->next(e.out);

	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 

	  this->graph->next(e.out); } 

      }

      return e;

    }

    EdgeIt& next(EdgeIt& e) const {

      if (e.forward) {

	this->graph->next(e.e);

	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 

	  this->graph->next(e.e); }

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

	  e.forward=false;

	  this->graph->first(e.e); 

	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 

	    this->graph->next(e.e); }

	}

      } else {

	this->graph->next(e.e);

	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 

	  this->graph->next(e.e); } 

      }

      return e;

    }

    Node tail(Edge e) const { 

      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }

    Node head(Edge e) const { 

      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 

      return ((e.forward) ? this->graph->aNode(e.out) : 

	      this->graph->aNode(e.in)); }

    Node bNode(OutEdgeIt e) const { 

      return ((e.forward) ? this->graph->bNode(e.out) : 

	      this->graph->bNode(e.in)); }

    Node aNode(InEdgeIt e) const { 

      return ((e.forward) ? this->graph->aNode(e.in) : 

	      this->graph->aNode(e.out)); }

    Node bNode(InEdgeIt e) const { 

      return ((e.forward) ? this->graph->bNode(e.in) : 

	      this->graph->bNode(e.out)); }

//    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 this->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::template 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 { this->graph->next(i.e); return i; }

    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    

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

    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::template NodeMap<int> > 

    SFalseTTrueMap;

    SFalseTTrueMap* s_false_t_true_map;

  public:

    static const bool S_CLASS=false;

    static const bool T_CLASS=true;

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

    friend class ClassNodeIt;

    class OutEdgeIt;

    friend class OutEdgeIt;

    class InEdgeIt;

    friend class InEdgeIt;

    class ClassNodeIt {

      friend class BipartiteGraphWrapper<Graph>;

    protected:

      Node n;

    public:

      ClassNodeIt() { }

      ClassNodeIt(const Invalid& i) : n(i) { }

      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 

	_G.s_false_t_true_map->first(n, _class); 

      }

      //FIXME needed in new concept, important here

      ClassNodeIt(const Node& _n) : n(_n) { }

      operator Node() const { return n; }

    };

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

      friend class BipartiteGraphWrapper<Graph>;

    protected:

      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=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));

	else 

	  e=INVALID;

      }

      operator Edge() const { return Edge(typename Graph::Edge(e)); }

    };

    class InEdgeIt { 

      friend class BipartiteGraphWrapper<Graph>;

    protected:

      typename Graph::InEdgeIt e;

    public:

      InEdgeIt() { }