/* -*- C++ -*-

 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Combinatorial Optimization Research Group, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_GRAPH_WRAPPER_H

#define LEMON_GRAPH_WRAPPER_H

///\ingroup gwrappers

///\file

///\brief Several graph wrappers.

///

///This file contains several useful graph wrapper functions.

///

///\author Marton Makai

#include <lemon/invalid.h>

#include <lemon/maps.h>

#include <lemon/map_defines.h>

#include <iostream>

namespace lemon {

  // Graph wrappers

  /// \addtogroup gwrappers

  /// The main parts of LEMON 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

  /// \addtogroup gwrappers

  /// @{

  ///Base type for the Graph Wrappers

  ///\warning Graph wrappers are in even more experimental state than the other

  ///parts of the lib. Use them at you own risk.

  ///

  /// This is the base type for most of LEMON graph wrappers. 

  /// This class implements a trivial graph wrapper i.e. it only wraps the 

  /// functions and types of the graph. The purpose of this class is to 

  /// make easier implementing graph wrappers. E.g. if a wrapper is 

  /// considered which differs from the wrapped graph only in some of its 

  /// functions or types, then it can be derived from GraphWrapper, and only the 

  /// differences should be implemented.

  ///

  ///\author Marton Makai 

  template<typename Graph>

  class GraphWrapper {

  protected:

    Graph* graph;

    GraphWrapper() : graph(0) { }

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

  public:

    typedef Graph BaseGraph;

    typedef Graph ParentGraph;

    GraphWrapper(Graph& _graph) : graph(&_graph) { }

    GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }

    typedef typename Graph::Node Node;

    class NodeIt : public Node { 

      const GraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      NodeIt() { }

      NodeIt(Invalid i) : Node(i) { }

      NodeIt(const GraphWrapper<Graph>& _gw) : 

	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }

      NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

	Node(n), gw(&_gw) { }

      NodeIt& operator++() { 

	*(static_cast<Node*>(this))=

	  ++(typename Graph::NodeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    typedef typename Graph::Edge Edge;

    class OutEdgeIt : public Edge { 

      const GraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      OutEdgeIt() { }

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

      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      OutEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    class InEdgeIt : public Edge { 

      const GraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      InEdgeIt() { }

      InEdgeIt(Invalid i) : Edge(i) { }

      InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 

	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

      InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      InEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    class EdgeIt : public Edge { 

      const GraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      EdgeIt() { }

      EdgeIt(Invalid i) : Edge(i) { }

      EdgeIt(const GraphWrapper<Graph>& _gw) : 

	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }

      EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      EdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::EdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    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;

    }

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

    int nodeNum() const { return graph->nodeNum(); }

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

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

    bool forward(const Edge& e) const { return graph->forward(e); }

    bool backward(const Edge& e) const { return graph->backward(e); }

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

    int id(const Edge& e) const { return graph->id(e); }

    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }

    IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);    

    IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);

  };

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

  ///\warning Graph wrappers are in even more experimental state than the other

  ///parts of the lib. Use them at you own risk.

  ///

  /// Let \f$G=(V, A)\f$ be a directed graph and 

  /// suppose that a graph instange \c g of type 

  /// \c ListGraph implements \f$G\f$.

  /// \code

  /// ListGraph g;

  /// \endcode

  /// For each directed edge 

  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 

  /// reversing its orientation. 

  /// Then RevGraphWrapper implements the graph structure with node-set 

  /// \f$V\f$ and edge-set 

  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 

  /// reversing the orientation of its edges. The following code shows how 

  /// such an instance can be constructed.

  /// \code

  /// RevGraphWrapper<ListGraph> gw(g);

  /// \endcode

  ///\author Marton Makai

  template<typename Graph>

  class RevGraphWrapper : public GraphWrapper<Graph> {

  public:

    typedef GraphWrapper<Graph> Parent; 

  protected:

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

  public:

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

    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }

    typedef typename GraphWrapper<Graph>::Node Node;

    typedef typename GraphWrapper<Graph>::Edge Edge;

    //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other

    //because this does not work is some of them are not defined in the 

    //original graph. The problem with this is that typedef-ed stuff 

    //are instantiated in c++.

    class OutEdgeIt : public Edge { 

      const RevGraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      OutEdgeIt() { }

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

      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 

	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      OutEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    class InEdgeIt : public Edge { 

      const RevGraphWrapper<Graph>* gw;

      friend class GraphWrapper<Graph>;

     public:

      InEdgeIt() { }

      InEdgeIt(Invalid i) : Edge(i) { }

      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 

	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }

      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      InEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    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;

    }

    Node tail(const Edge& e) const { 

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

    Node head(const Edge& e) const { 

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

    //    KEEP_MAPS(Parent, RevGraphWrapper);

  };

  /// A graph wrapper for hiding nodes and edges from a graph.

  ///\warning Graph wrappers are in even more experimental state than the other

  ///parts of the lib. Use them at you own risk.

  ///

  /// This wrapper shows a graph with filtered node-set and 

  /// edge-set. 

  /// Given a bool-valued map on the node-set and one on 

  /// the edge-set of the graph, the iterators show only the objects 

  /// having true value. We have to note that this does not mean that an 

  /// induced subgraph is obtained, the node-iterator cares only the filter 

  /// on the node-set, and the edge-iterators care only the filter on the 

  /// edge-set.

  /// \code

  /// typedef SmartGraph Graph;

  /// Graph g;

  /// typedef Graph::Node Node;

  /// typedef Graph::Edge Edge;

  /// Node u=g.addNode(); //node of id 0

  /// Node v=g.addNode(); //node of id 1

  /// Node e=g.addEdge(u, v); //edge of id 0

  /// Node f=g.addEdge(v, u); //edge of id 1

  /// Graph::NodeMap<bool> nm(g, true);

  /// nm.set(u, false);

  /// Graph::EdgeMap<bool> em(g, true);

  /// em.set(e, false);

  /// typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

  /// SubGW gw(g, nm, em);

  /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;

  /// std::cout << ":-)" << std::endl;

  /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;

  /// \endcode

  /// The output of the above code is the following.

  /// \code

  /// 1

  /// :-)

  /// 1

  /// \endcode

  /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to

  /// \c Graph::Node that is why \c g.id(n) can be applied.

  ///

  ///\author Marton Makai

  template<typename Graph, typename NodeFilterMap, 

	   typename EdgeFilterMap>

  class SubGraphWrapper : public GraphWrapper<Graph> {

  public:

    typedef GraphWrapper<Graph> Parent;

  protected:

    NodeFilterMap* node_filter_map;

    EdgeFilterMap* edge_filter_map;

    SubGraphWrapper() : GraphWrapper<Graph>(), 

			node_filter_map(0), edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

      node_filter_map=&_node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

      edge_filter_map=&_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 : public Node { 

      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

    public:

      NodeIt() { }

      NodeIt(Invalid i) : Node(i) { }

      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 

	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 

	while (*static_cast<Node*>(this)!=INVALID && 

	       !(*(gw->node_filter_map))[*this]) 

	  *(static_cast<Node*>(this))=

	    ++(typename Graph::NodeIt(*(gw->graph), *this));

      }

      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

	     const Node& n) : 

	Node(n), gw(&_gw) { }

      NodeIt& operator++() { 

	*(static_cast<Node*>(this))=

	  ++(typename Graph::NodeIt(*(gw->graph), *this));

	while (*static_cast<Node*>(this)!=INVALID && 

	       !(*(gw->node_filter_map))[*this]) 

	  *(static_cast<Node*>(this))=

	    ++(typename Graph::NodeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    typedef typename GraphWrapper<Graph>::Edge Edge;

    class OutEdgeIt : public Edge { 

      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

    public:

      OutEdgeIt() { }

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

      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 

	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

      }

      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

	     const Edge& e) : 

	Edge(e), gw(&_gw) { }

      OutEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    class InEdgeIt : public Edge { 

      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

    public:

      InEdgeIt() { }

      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }

      InEdgeIt(Invalid i) : Edge(i) { }

      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 

	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

      }

      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

	     const Edge& e) : 

	Edge(e), gw(&_gw) { }

      InEdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    class EdgeIt : public Edge { 

      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;

      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

    public:

      EdgeIt() { }

      EdgeIt(Invalid i) : Edge(i) { }

      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 

	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

      }

      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 

	     const Edge& e) : 

	Edge(e), gw(&_gw) { }

      EdgeIt& operator++() { 

	*(static_cast<Edge*>(this))=

	  ++(typename Graph::EdgeIt(*(gw->graph), *this));

	while (*static_cast<Edge*>(this)!=INVALID && 

	       !(*(gw->edge_filter_map))[*this]) 

	  *(static_cast<Edge*>(this))=

	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

	return *this; 

      }

    };

    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;

    }

    /// This function hides \c n in the graph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c n  

    /// to be false in the corresponding node-map.

    void hide(const Node& n) const { node_filter_map->set(n, false); }

    /// This function hides \c e in the graph, i.e. the iteration 

    /// jumps over it. This is done by simply setting the value of \c e  

    /// to be false in the corresponding edge-map.

    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    /// The value of \c n is set to be true in the node-map which stores 

    /// hide information. If \c n was hidden previuosly, then it is shown 

    /// again

     void unHide(const Node& n) const { node_filter_map->set(n, true); }

    /// The value of \c e is set to be true in the edge-map which stores 

    /// hide information. If \c e was hidden previuosly, then it is shown 

    /// again

    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    /// Returns true if \c n is hidden.

    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

    /// Returns true if \c n is hidden.

    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }

    /// \warning This is a linear time operation and works only if 

    /// \c Graph::NodeIt is defined.

    int nodeNum() const { 

      int i=0;

      for (NodeIt n(*this); n!=INVALID; ++n) ++i;

      return i; 

    }

    /// \warning This is a linear time operation and works only if 

    /// \c Graph::EdgeIt is defined.

    int edgeNum() const { 

      int i=0;

      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;

      return i; 

    }

    //    KEEP_MAPS(Parent, SubGraphWrapper);

  };

  template<typename Graph>

  class UndirGraphWrapper : public GraphWrapper<Graph> {

  public:

    typedef GraphWrapper<Graph> Parent; 

  protected:

    UndirGraphWrapper() : 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); 

      }

    };

    typedef OutEdgeIt InEdgeIt; 

    using GraphWrapper<Graph>::first;

    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

      i=OutEdgeIt(*this, p); return i;

    }

    using GraphWrapper<Graph>::next;

    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;

    }

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

    //    KEEP_MAPS(Parent, UndirGraphWrapper);

  };

//   /// \brief An undirected graph template.

//   ///

//   ///\warning Graph wrappers are in even more experimental state than the other

//   ///parts of the lib. Use them at your own risk.

//   ///

//   /// An undirected graph template.

//   /// This class works as an undirected graph and a directed graph of 

//   /// class \c Graph is used for the physical storage.

//   /// \ingroup graphs

  template<typename Graph>

  class UndirGraph : public UndirGraphWrapper<Graph> {

    typedef UndirGraphWrapper<Graph> Parent;

  protected:

    Graph gr;

  public:

    UndirGraph() : UndirGraphWrapper<Graph>() { 

      Parent::setGraph(gr); 

    }

    //    KEEP_MAPS(Parent, UndirGraph);

  };

  ///\brief A wrapper for composing a subgraph of a 

  /// bidirected graph made from a directed one. 

  ///

  /// A wrapper for composing a subgraph of a 

  /// bidirected graph made from a directed one. 

  ///

  ///\warning Graph wrappers are in even more experimental state than the other

  ///parts of the lib. Use them at you own risk.

  ///

  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 

  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by

  /// reversing its orientation. We are given moreover two bool valued 

  /// maps on the edge-set, 

  /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 

  /// SubBidirGraphWrapper implements the graph structure with node-set 

  /// \f$V\f$ and edge-set 

  /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 

  /// The purpose of writing + instead of union is because parallel 

  /// edges can arise. (Similarly, antiparallel edges also can arise).

  /// In other words, a subgraph of the bidirected graph obtained, which 

  /// is given by orienting the edges of the original graph in both directions.

  /// As the oppositely directed edges are logically different, 

  /// the maps are able to attach different values for them. 

  ///

  /// An example for such a construction is \c RevGraphWrapper where the 

  /// forward_filter is everywhere false and the backward_filter is 

  /// everywhere true. We note that for sake of efficiency, 

  /// \c RevGraphWrapper is implemented in a different way. 

  /// But BidirGraphWrapper is obtained from 

  /// SubBidirGraphWrapper by considering everywhere true 

  /// valued maps both for forward_filter and backward_filter. 

  /// Finally, one of the most important applications of SubBidirGraphWrapper 

  /// is ResGraphWrapper, which stands for the residual graph in directed 

  /// flow and circulation problems. 

  /// As wrappers usually, the SubBidirGraphWrapper implements the 

  /// above mentioned graph structure without its physical storage, 

  /// that is the whole stuff is stored in constant memory. 

  template<typename Graph, 

	   typename ForwardFilterMap, typename BackwardFilterMap>

  class SubBidirGraphWrapper : public GraphWrapper<Graph> {

  public:

    typedef GraphWrapper<Graph> Parent; 

  protected:

    ForwardFilterMap* forward_filter;

    BackwardFilterMap* backward_filter;

    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }

    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

      forward_filter=&_forward_filter;

    }

    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

      backward_filter=&_backward_filter;

    }

  public:

    SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 

			 BackwardFilterMap& _backward_filter) : 

      GraphWrapper<Graph>(_graph), 

      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }

    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 

			 ForwardFilterMap, BackwardFilterMap>& gw) : 

      Parent(gw), 

      forward_filter(gw.forward_filter), 

      backward_filter(gw.backward_filter) { }

    class Edge; 

    class OutEdgeIt; 

    friend class Edge; 

    friend class OutEdgeIt; 

    template<typename T> class EdgeMap;

    typedef typename GraphWrapper<Graph>::Node Node;

    typedef typename Graph::Edge GraphEdge;

    /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 

    /// Graph::Edge. It contains an extra bool flag which is true 

    /// if and only if the 

    /// edge is the backward version of the original edge.

    class Edge : public Graph::Edge {

      friend class SubBidirGraphWrapper<Graph, 

					ForwardFilterMap, BackwardFilterMap>;

      template<typename T> friend class EdgeMap;

    protected:

      bool backward; //true, iff backward

    public:

      Edge() { }

      /// \todo =false is needed, or causes problems?

      /// If \c _backward is false, then we get an edge corresponding to the 

      /// original one, otherwise its oppositely directed pair is obtained.

      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 

	Graph::Edge(e), backward(_backward) { }

      Edge(Invalid i) : Graph::Edge(i), backward(true) { }

      bool operator==(const Edge& v) const { 

	return (this->backward==v.backward && 

		static_cast<typename Graph::Edge>(*this)==

		static_cast<typename Graph::Edge>(v));

      } 

      bool operator!=(const Edge& v) const { 

	return (this->backward!=v.backward || 

		static_cast<typename Graph::Edge>(*this)!=

		static_cast<typename Graph::Edge>(v));

      }

    };

    class OutEdgeIt : public Edge {

      friend class SubBidirGraphWrapper<Graph, 

					ForwardFilterMap, BackwardFilterMap>;

    protected:

      const SubBidirGraphWrapper<Graph, 

				 ForwardFilterMap, BackwardFilterMap>* gw;

    public:

      OutEdgeIt() { }

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

      OutEdgeIt(const SubBidirGraphWrapper<Graph, 

		ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 

	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 

	while (*static_cast<GraphEdge*>(this)!=INVALID && 

	       !(*(gw->forward_filter))[*this]) 

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	if (*static_cast<GraphEdge*>(this)==INVALID) {

	  *static_cast<Edge*>(this)=

	    Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	}

      }

      OutEdgeIt(const SubBidirGraphWrapper<Graph, 

		ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      OutEdgeIt& operator++() { 

	if (!this->backward) {

	  Node n=gw->tail(*this);

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->forward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	  if (*static_cast<GraphEdge*>(this)==INVALID) {

	    *static_cast<Edge*>(this)=

	      Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);

	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

		   !(*(gw->backward_filter))[*this]) 

	      *(static_cast<GraphEdge*>(this))=

		++(typename Graph::InEdgeIt(*(gw->graph), *this));

	  }

	} else {

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	}

	return *this;

      }

    };

    class InEdgeIt : public Edge {

      friend class SubBidirGraphWrapper<Graph, 

					ForwardFilterMap, BackwardFilterMap>;

    protected:

      const SubBidirGraphWrapper<Graph, 

				 ForwardFilterMap, BackwardFilterMap>* gw;

    public:

      InEdgeIt() { }

      InEdgeIt(Invalid i) : Edge(i) { }

      InEdgeIt(const SubBidirGraphWrapper<Graph, 

	       ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 

	Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 

	while (*static_cast<GraphEdge*>(this)!=INVALID && 

	       !(*(gw->forward_filter))[*this]) 

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	if (*static_cast<GraphEdge*>(this)==INVALID) {

	  *static_cast<Edge*>(this)=

	    Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	}

      }

      InEdgeIt(const SubBidirGraphWrapper<Graph, 

	       ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      InEdgeIt& operator++() { 

	if (!this->backward) {

	  Node n=gw->tail(*this);

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->forward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));

	  if (*static_cast<GraphEdge*>(this)==INVALID) {

	    *static_cast<Edge*>(this)=

	      Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);

	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

		   !(*(gw->backward_filter))[*this]) 

	      *(static_cast<GraphEdge*>(this))=

		++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	  }

	} else {

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));

	}

	return *this;

      }

    };

    class EdgeIt : public Edge {

      friend class SubBidirGraphWrapper<Graph, 

					ForwardFilterMap, BackwardFilterMap>;

    protected:

      const SubBidirGraphWrapper<Graph, 

				 ForwardFilterMap, BackwardFilterMap>* gw;

    public:

      EdgeIt() { }

      EdgeIt(Invalid i) : Edge(i) { }

      EdgeIt(const SubBidirGraphWrapper<Graph, 

	     ForwardFilterMap, BackwardFilterMap>& _gw) : 

	Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 

	while (*static_cast<GraphEdge*>(this)!=INVALID && 

	       !(*(gw->forward_filter))[*this]) 

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

	if (*static_cast<GraphEdge*>(this)==INVALID) {

	  *static_cast<Edge*>(this)=

	    Edge(typename Graph::EdgeIt(*(_gw.graph)), true);

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

	}

      }

      EdgeIt(const SubBidirGraphWrapper<Graph, 

	     ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 

	Edge(e), gw(&_gw) { }

      EdgeIt& operator++() { 

	if (!this->backward) {

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->forward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

	  if (*static_cast<GraphEdge*>(this)==INVALID) {

	    *static_cast<Edge*>(this)=

	      Edge(typename Graph::EdgeIt(*(gw->graph)), true);

	    while (*static_cast<GraphEdge*>(this)!=INVALID && 

		   !(*(gw->backward_filter))[*this]) 

	      *(static_cast<GraphEdge*>(this))=

		++(typename Graph::EdgeIt(*(gw->graph), *this));

	  }

	} else {

	  *(static_cast<GraphEdge*>(this))=

	    ++(typename Graph::EdgeIt(*(gw->graph), *this));

	  while (*static_cast<GraphEdge*>(this)!=INVALID && 

		 !(*(gw->backward_filter))[*this]) 

	    *(static_cast<GraphEdge*>(this))=

	      ++(typename Graph::EdgeIt(*(gw->graph), *this));

	}

	return *this;

      }

    };

    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;

    }

    EdgeIt& first(EdgeIt& i) const { 

      i=EdgeIt(*this); return i;

    }

    Node tail(Edge e) const { 

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

    Node head(Edge e) const { 

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

    /// Gives back the opposite edge.

    Edge opposite(const Edge& e) const { 

      Edge f=e;

      f.backward=!f.backward;

      return f;

    }

    /// \warning This is a linear time operation and works only if 

    /// \c Graph::EdgeIt is defined.

    int edgeNum() const { 

      int i=0;

      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;

      return i; 

    }

    bool forward(const Edge& e) const { return !e.backward; }

    bool backward(const Edge& e) const { return e.backward; }

    template <typename T>

    /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 

    /// Graph::EdgeMap one for the forward edges and 

    /// one for the backward edges.

    class EdgeMap {

      template <typename TT> friend class EdgeMap;

      typename Graph::template EdgeMap<T> forward_map, backward_map; 

    public:

      typedef T ValueType;

      typedef Edge KeyType;

      EdgeMap(const SubBidirGraphWrapper<Graph, 

	      ForwardFilterMap, BackwardFilterMap>& g) : 

	forward_map(*(g.graph)), backward_map(*(g.graph)) { }

      EdgeMap(const SubBidirGraphWrapper<Graph, 

	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 

	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }

      template <typename TT>

      EdgeMap(const EdgeMap<TT>& copy) 

	: forward_map(copy.forward_map), backward_map(copy.backward_map) {}

      template <typename TT>

      EdgeMap& operator=(const EdgeMap<TT>& copy) {

	forward_map = copy.forward_map;

	backward_map = copy.backward_map;

	return *this;

      }