/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, 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_ADAPTOR_H

 #define LEMON_GRAPH_ADAPTOR_H

 ///\ingroup graph_adaptors

 ///\file

 ///\brief Several graph adaptors.

 ///

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

 ///

 ///\author Marton Makai and Balazs Dezso

 #include <lemon/bits/invalid.h>

 #include <lemon/bits/variant.h>

 #include <lemon/maps.h>

 #include <lemon/bits/base_extender.h>

 #include <lemon/bits/graph_adaptor_extender.h>

 #include <lemon/bits/graph_extender.h>

 #include <lemon/tolerance.h>

 #include <algorithm>

 namespace lemon {

   ///\brief Base type for the Graph Adaptors

   ///

   ///Base type for the Graph Adaptors

   ///

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

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

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

   ///make easier implementing graph adaptors. E.g. if an adaptor is 

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

   ///functions or types, then it can be derived from GraphAdaptor,

   ///and only the 

   ///differences should be implemented.

   ///

   ///author Marton Makai 

   template<typename _Graph>

   class GraphAdaptorBase {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase Adaptor;

     typedef Graph ParentGraph;

   protected:

     Graph* graph;

     GraphAdaptorBase() : graph(0) { }

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

   public:

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

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     void first(Node& i) const { graph->first(i); }

     void first(Edge& i) const { graph->first(i); }

     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

     void next(Node& i) const { graph->next(i); }

     void next(Edge& i) const { graph->next(i); }

     void nextIn(Edge& i) const { graph->nextIn(i); }

     void nextOut(Edge& i) const { graph->nextOut(i); }

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

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

     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v, 

 		  const Edge& prev = INVALID) {

       return graph->findEdge(u, v, prev);

     }

     Node addNode() const { 

       return Node(graph->addNode()); 

     }

     Edge addEdge(const Node& u, const Node& v) const { 

       return Edge(graph->addEdge(u, v)); 

     }

     void erase(const Node& i) const { graph->erase(i); }

     void erase(const Edge& i) const { graph->erase(i); }

     void clear() const { graph->clear(); }

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

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

     Node fromNodeId(int ix) const {

       return graph->fromNodeId(ix);

     }

     Edge fromEdgeId(int ix) const {

       return graph->fromEdgeId(ix);

     }

     int maxNodeId() const {

       return graph->maxNodeId();

     }

     int maxEdgeId() const {

       return graph->maxEdgeId();

     }

     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& notifier(Node) const {

       return graph->notifier(Node());

     } 

     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

     EdgeNotifier& notifier(Edge) const {

       return graph->notifier(Edge());

     } 

     template <typename _Value>

     class NodeMap : public Graph::template NodeMap<_Value> {

     public:

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

       explicit NodeMap(const Adaptor& ga) 

 	: Parent(*ga.graph) {}

       NodeMap(const Adaptor& ga, const _Value& value)

 	: Parent(*ga.graph, value) { }

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

     template <typename _Value>

     class EdgeMap : public Graph::template EdgeMap<_Value> {

     public:

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

       explicit EdgeMap(const Adaptor& ga) 

 	: Parent(*ga.graph) {}

       EdgeMap(const Adaptor& ga, const _Value& value)

 	: Parent(*ga.graph, value) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   ///\ingroup graph_adaptors

   ///

   ///\brief Trivial Graph Adaptor

   /// 

   /// This class is an adaptor which does not change the adapted graph.

   /// It can be used only to test the graph adaptors.

   template <typename _Graph>

   class GraphAdaptor :

     public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;

   protected:

     GraphAdaptor() : Parent() { }

   public:

     explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }

   };

   /// \brief Just gives back a graph adaptor

   ///

   /// Just gives back a graph adaptor which 

   /// should be provide original graph

   template<typename Graph>

   GraphAdaptor<const Graph>

   graphAdaptor(const Graph& graph) {

     return GraphAdaptor<const Graph>(graph);

   }

   template <typename _Graph>

   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     RevGraphAdaptorBase() : Parent() { }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }

     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }

     void nextIn(Edge& i) const { Parent::nextOut(i); }

     void nextOut(Edge& i) const { Parent::nextIn(i); }

     Node source(const Edge& e) const { return Parent::target(e); }

     Node target(const Edge& e) const { return Parent::source(e); }

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v, 

 		  const Edge& prev = INVALID) {

       return Parent::findEdge(v, u, prev);

     }

   };

   ///\ingroup graph_adaptors

   ///

   ///\brief A graph adaptor which reverses the orientation of the edges.

   ///

   /// If \c g is defined as

   ///\code

   /// ListGraph g;

   ///\endcode

   /// then

   ///\code

   /// RevGraphAdaptor<ListGraph> ga(g);

   ///\endcode

   /// implements the graph obtained from \c g by 

   /// reversing the orientation of its edges.

   ///

   /// A good example of using RevGraphAdaptor is to decide that the

   /// directed graph is wheter strongly connected or not. If from one

   /// node each node is reachable and from each node is reachable this

   /// node then and just then the graph is strongly connected. Instead of

   /// this condition we use a little bit different. From one node each node

   /// ahould be reachable in the graph and in the reversed graph. Now this

   /// condition can be checked with the Dfs algorithm class and the

   /// RevGraphAdaptor algorithm class.

   ///

   /// And look at the code:

   ///

   ///\code

   /// bool stronglyConnected(const Graph& graph) {

   ///   if (NodeIt(graph) == INVALID) return true;

   ///   Dfs<Graph> dfs(graph);

   ///   dfs.run(NodeIt(graph));

   ///   for (NodeIt it(graph); it != INVALID; ++it) {

   ///     if (!dfs.reached(it)) {

   ///       return false;

   ///     }

   ///   }

   ///   typedef RevGraphAdaptor<const Graph> RGraph;

   ///   RGraph rgraph(graph);

   ///   DfsVisit<RGraph> rdfs(rgraph);

   ///   rdfs.run(NodeIt(graph));

   ///   for (NodeIt it(graph); it != INVALID; ++it) {

   ///     if (!rdfs.reached(it)) {

   ///       return false;

   ///     }

   ///   }

   ///   return true;

   /// }

   ///\endcode

   template<typename _Graph>

   class RevGraphAdaptor : 

     public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorExtender<

       RevGraphAdaptorBase<_Graph> > Parent;

   protected:

     RevGraphAdaptor() { }

   public:

     explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }

   };

   /// \brief Just gives back a reverse graph adaptor

   ///

   /// Just gives back a reverse graph adaptor

   template<typename Graph>

   RevGraphAdaptor<const Graph>

   revGraphAdaptor(const Graph& graph) {

     return RevGraphAdaptor<const Graph>(graph);

   }

   template <typename _Graph, typename NodeFilterMap, 

 	    typename EdgeFilterMap, bool checked = true>

   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef SubGraphAdaptorBase Adaptor;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     EdgeFilterMap* edge_filter_map;

     SubGraphAdaptorBase() : Parent(), 

 			    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:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void first(Edge& i) const { 

       Parent::first(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)]

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 

     }

     void firstIn(Edge& i, const Node& n) const { 

       Parent::firstIn(i, n); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

     }

     void firstOut(Edge& i, const Node& n) const { 

       Parent::firstOut(i, n); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

     }

     void next(Node& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void next(Edge& i) const { 

       Parent::next(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)]

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

       while (i!=INVALID && (!(*edge_filter_map)[i] 

 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 

     }

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

     ///

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

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

     ///\e

     ///

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

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) {

       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {

         return INVALID;

       }

       Edge edge = Parent::findEdge(source, target, prev);

       while (edge != INVALID && !(*edge_filter_map)[edge]) {

         edge = Parent::findEdge(source, target, edge);

       }

       return edge;

     }

     template <typename _Value>

     class NodeMap 

       : public SubMapExtender<Adaptor, 

                               typename Parent::template NodeMap<_Value> > 

     {

     public:

       typedef Adaptor Graph;

       typedef SubMapExtender<Adaptor, typename Parent::

                              template NodeMap<_Value> > Parent;

       NodeMap(const Graph& g) 

 	: Parent(g) {}

       NodeMap(const Graph& g, const _Value& v) 

 	: Parent(g, v) {}

       NodeMap& operator=(const NodeMap& cmap) {

 	return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

 	return *this;

       }

     };

     template <typename _Value>

     class EdgeMap 

       : public SubMapExtender<Adaptor, 

                               typename Parent::template EdgeMap<_Value> > 

     {

     public:

       typedef Adaptor Graph;

       typedef SubMapExtender<Adaptor, typename Parent::

                              template EdgeMap<_Value> > Parent;

       EdgeMap(const Graph& g) 

 	: Parent(g) {}

       EdgeMap(const Graph& g, const _Value& v) 

 	: Parent(g, v) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

 	return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

 	return *this;

       }

     };

   };

   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

   class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 

     : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef SubGraphAdaptorBase Adaptor;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     NodeFilterMap* node_filter_map;

     EdgeFilterMap* edge_filter_map;

     SubGraphAdaptorBase() : Parent(), 

 			    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:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void first(Node& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void first(Edge& i) const { 

       Parent::first(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 

     }

     void firstIn(Edge& i, const Node& n) const { 

       Parent::firstIn(i, n); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 

     }

     void firstOut(Edge& i, const Node& n) const { 

       Parent::firstOut(i, n); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 

     }

     void next(Node& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 

     }

     void next(Edge& i) const { 

       Parent::next(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 

     }

     void nextIn(Edge& i) const { 

       Parent::nextIn(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 

     }

     void nextOut(Edge& i) const { 

       Parent::nextOut(i); 

       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 

     }

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

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

     ///\e

     ///

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

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

     ///\e

     ///

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

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

     Edge findEdge(const Node& source, const Node& target, 

 		  const Edge& prev = INVALID) {

       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {

         return INVALID;

       }

       Edge edge = Parent::findEdge(source, target, prev);

       while (edge != INVALID && !(*edge_filter_map)[edge]) {

         edge = Parent::findEdge(source, target, edge);

       }

       return edge;

     }

     template <typename _Value>

     class NodeMap 

       : public SubMapExtender<Adaptor, 

                               typename Parent::template NodeMap<_Value> > 

     {

     public:

       typedef Adaptor Graph;

       typedef SubMapExtender<Adaptor, typename Parent::

                              template NodeMap<_Value> > Parent;

       NodeMap(const Graph& g) 

 	: Parent(g) {}

       NodeMap(const Graph& g, const _Value& v) 

 	: Parent(g, v) {}

       NodeMap& operator=(const NodeMap& cmap) {

 	return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

 	return *this;

       }

     };

     template <typename _Value>

     class EdgeMap 

       : public SubMapExtender<Adaptor, 

                               typename Parent::template EdgeMap<_Value> > 

     {

     public:

       typedef Adaptor Graph;

       typedef SubMapExtender<Adaptor, typename Parent::

                              template EdgeMap<_Value> > Parent;

       EdgeMap(const Graph& g) 

 	: Parent(g) {}

       EdgeMap(const Graph& g, const _Value& v) 

 	: Parent(g, v) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

 	return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

 	return *this;

       }

     };

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief A graph adaptor for hiding nodes and edges from a graph.

   /// 

   /// SubGraphAdaptor shows the graph with filtered node-set and 

   /// edge-set. If the \c checked parameter is true then it filters the edgeset

   /// to do not get invalid edges without source or target.

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

   /// and suppose that the graph instance \c g of type ListGraph

   /// implements \f$ G \f$.

   /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.

   /// on the node-set and edge-set.

   /// SubGraphAdaptor<...>::NodeIt iterates 

   /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and 

   /// SubGraphAdaptor<...>::EdgeIt iterates 

   /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly, 

   /// SubGraphAdaptor<...>::OutEdgeIt and

   /// SubGraphAdaptor<...>::InEdgeIt iterates 

   /// only on edges leaving and entering a specific node which have true value.

   /// 

   /// If the \c checked template parameter is false then we have to note that 

   /// the node-iterator cares only the filter on the node-set, and the 

   /// edge-iterator cares only the filter on the edge-set.

   /// This way the edge-map

   /// should filter all edges which's source or target is filtered by the 

   /// node-filter.

   ///\code

   /// typedef ListGraph 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 SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;

   /// SubGA ga(g, nm, em);

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

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

   /// for (SubGA::EdgeIt e(ga); 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 SubGA::NodeIt, but it can be converted to

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

   /// 

   /// For other examples see also the documentation of NodeSubGraphAdaptor and 

   /// EdgeSubGraphAdaptor.

   /// 

   /// \author Marton Makai

   template<typename _Graph, typename NodeFilterMap, 

 	   typename EdgeFilterMap, bool checked = true>

   class SubGraphAdaptor : 

     public GraphAdaptorExtender<

     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap, 

                                                       EdgeFilterMap, checked> >

     Parent;

   protected:

     SubGraphAdaptor() { }

   public:

     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 

 		    EdgeFilterMap& _edge_filter_map) { 

       setGraph(_graph);

       setNodeFilterMap(_node_filter_map);

       setEdgeFilterMap(_edge_filter_map);

     }

   };

   /// \brief Just gives back a sub graph adaptor

   ///

   /// Just gives back a sub graph adaptor

   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>

   SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>

   subGraphAdaptor(const Graph& graph, 

                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

     return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>

       (graph, nfm, efm);

   }

   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>

   SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>

   subGraphAdaptor(const Graph& graph, 

                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

     return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>

       (graph, nfm, efm);

   }

   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>

   SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>

   subGraphAdaptor(const Graph& graph, 

                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

     return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>

       (graph, nfm, efm);

   }

   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>

   SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>

   subGraphAdaptor(const Graph& graph, 

                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

     return SubGraphAdaptor<const Graph, const NodeFilterMap, 

       const EdgeFilterMap>(graph, nfm, efm);

   }

   ///\ingroup graph_adaptors

   ///

   ///\brief An adaptor for hiding nodes from a graph.

   ///

   ///An adaptor for hiding nodes from a graph.

   ///This adaptor specializes SubGraphAdaptor in the way that only

   ///the node-set 

   ///can be filtered. In usual case the checked parameter is true, we get the

   ///induced subgraph. But if the checked parameter is false then we can

   ///filter only isolated nodes.

   ///\author Marton Makai

   template<typename Graph, typename NodeFilterMap, bool checked = true>

   class NodeSubGraphAdaptor : 

     public SubGraphAdaptor<Graph, NodeFilterMap, 

 			   ConstMap<typename Graph::Edge,bool>, checked> {

   public:

     typedef SubGraphAdaptor<Graph, NodeFilterMap, 

 			    ConstMap<typename Graph::Edge,bool>, checked > 

     Parent;

   protected:

     ConstMap<typename Graph::Edge, bool> const_true_map;

     NodeSubGraphAdaptor() : const_true_map(true) {

       Parent::setEdgeFilterMap(const_true_map);

     }

   public:

     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(_node_filter_map);

       Parent::setEdgeFilterMap(const_true_map);

     }

   };

   /// \brief Just gives back a node sub graph adaptor

   ///

   /// Just gives back a node sub graph adaptor

   template<typename Graph, typename NodeFilterMap>

   NodeSubGraphAdaptor<const Graph, NodeFilterMap>

   nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {

     return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);

   }

   template<typename Graph, typename NodeFilterMap>

   NodeSubGraphAdaptor<const Graph, const NodeFilterMap>

   nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {

     return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);

   }

   ///\ingroup graph_adaptors

   ///

   ///\brief An adaptor for hiding edges from a graph.

   ///

   ///An adaptor for hiding edges from a graph.

   ///This adaptor specializes SubGraphAdaptor in the way that

   ///only the edge-set 

   ///can be filtered. The usefulness of this adaptor is demonstrated in the 

   ///problem of searching a maximum number of edge-disjoint shortest paths 

   ///between 

   ///two nodes \c s and \c t. Shortest here means being shortest w.r.t. 

   ///non-negative edge-lengths. Note that 

   ///the comprehension of the presented solution 

   ///need's some elementary knowledge from combinatorial optimization. 

   ///

   ///If a single shortest path is to be 

   ///searched between \c s and \c t, then this can be done easily by 

   ///applying the Dijkstra algorithm. What happens, if a maximum number of 

   ///edge-disjoint shortest paths is to be computed. It can be proved that an 

   ///edge can be in a shortest path if and only

   ///if it is tight with respect to 

   ///the potential function computed by Dijkstra.

   ///Moreover, any path containing 

   ///only such edges is a shortest one.

   ///Thus we have to compute a maximum number 

   ///of edge-disjoint paths between \c s and \c t in

   ///the graph which has edge-set 

   ///all the tight edges. The computation will be demonstrated

   ///on the following 

   ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 

   ///The full source code is available in \ref sub_graph_adaptor_demo.cc. 

   ///If you are interested in more demo programs, you can use 

   ///\ref dim_to_dot.cc to generate .dot files from dimacs files. 

   ///The .dot file of the following figure was generated by  

   ///the demo program \ref dim_to_dot.cc.

   ///

   ///\dot

   ///digraph lemon_dot_example {

   ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   ///n0 [ label="0 (s)" ];

   ///n1 [ label="1" ];

   ///n2 [ label="2" ];

   ///n3 [ label="3" ];

   ///n4 [ label="4" ];

   ///n5 [ label="5" ];

   ///n6 [ label="6 (t)" ];

   ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   ///n5 ->  n6 [ label="9, length:4" ];

   ///n4 ->  n6 [ label="8, length:2" ];

   ///n3 ->  n5 [ label="7, length:1" ];

   ///n2 ->  n5 [ label="6, length:3" ];

   ///n2 ->  n6 [ label="5, length:5" ];

   ///n2 ->  n4 [ label="4, length:2" ];

   ///n1 ->  n4 [ label="3, length:3" ];

   ///n0 ->  n3 [ label="2, length:1" ];

   ///n0 ->  n2 [ label="1, length:2" ];

   ///n0 ->  n1 [ label="0, length:3" ];

   ///}

   ///\enddot

   ///

   ///\code

   ///Graph g;

   ///Node s, t;

   ///LengthMap length(g);

   ///

   ///readDimacs(std::cin, g, length, s, t);

   ///

   ///cout << "edges with lengths (of form id, source--length->target): " << endl;

   ///for(EdgeIt e(g); e!=INVALID; ++e) 

   ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 

   ///       << length[e] << "->" << g.id(g.target(e)) << endl;

   ///

   ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;

   ///\endcode

   ///Next, the potential function is computed with Dijkstra.

   ///\code

   ///typedef Dijkstra<Graph, LengthMap> Dijkstra;

   ///Dijkstra dijkstra(g, length);

   ///dijkstra.run(s);

   ///\endcode

   ///Next, we consrtruct a map which filters the edge-set to the tight edges.

   ///\code

   ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 

   ///  TightEdgeFilter;

   ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);

   ///

   ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;

   ///SubGA ga(g, tight_edge_filter);

   ///\endcode

   ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 

   ///with a max flow algorithm Preflow.

   ///\code

   ///ConstMap<Edge, int> const_1_map(1);

   ///Graph::EdgeMap<int> flow(g, 0);

   ///

   ///Preflow<SubGA, ConstMap<Edge, int>, Graph::EdgeMap<int> > 

   ///  preflow(ga, const_1_map, s, t);

   ///preflow.run();

   ///\endcode

   ///Last, the output is:

   ///\code  

   ///cout << "maximum number of edge-disjoint shortest path: " 

   ///     << preflow.flowValue() << endl;

   ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 

   ///     << endl;

   ///for(EdgeIt e(g); e!=INVALID; ++e) 

   ///  if (preflow.flow(e))

   ///    cout << " " << g.id(g.source(e)) << "--"

   ///         << length[e] << "->" << g.id(g.target(e)) << endl;

   ///\endcode

   ///The program has the following (expected :-)) output:

   ///\code

   ///edges with lengths (of form id, source--length->target):

   /// 9, 5--4->6

   /// 8, 4--2->6

   /// 7, 3--1->5

   /// 6, 2--3->5

   /// 5, 2--5->6

   /// 4, 2--2->4

   /// 3, 1--3->4

   /// 2, 0--1->3

   /// 1, 0--2->2

   /// 0, 0--3->1

   ///s: 0 t: 6

   ///maximum number of edge-disjoint shortest path: 2

   ///edges of the maximum number of edge-disjoint shortest s-t paths:

   /// 9, 5--4->6

   /// 8, 4--2->6

   /// 7, 3--1->5

   /// 4, 2--2->4

   /// 2, 0--1->3

   /// 1, 0--2->2

   ///\endcode

   ///

   ///\author Marton Makai

   template<typename Graph, typename EdgeFilterMap>

   class EdgeSubGraphAdaptor : 

     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

 			   EdgeFilterMap, false> {

   public:

     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

 			    EdgeFilterMap, false> Parent;

   protected:

     ConstMap<typename Graph::Node, bool> const_true_map;

     EdgeSubGraphAdaptor() : const_true_map(true) {

       Parent::setNodeFilterMap(const_true_map);

     }

   public:

     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 

       Parent(), const_true_map(true) { 

       Parent::setGraph(_graph);

       Parent::setNodeFilterMap(const_true_map);

       Parent::setEdgeFilterMap(_edge_filter_map);

     }

   };

   /// \brief Just gives back an edge sub graph adaptor

   ///

   /// Just gives back an edge sub graph adaptor

   template<typename Graph, typename EdgeFilterMap>

   EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>

   edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {

     return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);

   }

   template<typename Graph, typename EdgeFilterMap>

   EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>

   edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {

     return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);

   }

   template <typename _Graph>

   class UndirGraphAdaptorBase : 

     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   public:

     typedef _Graph Graph;

     typedef UndirGraphAdaptorBase Adaptor;

     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   protected:

     UndirGraphAdaptorBase() : Parent() {}

   public:

     typedef typename Parent::UEdge UEdge;

     typedef typename Parent::Edge Edge;

   private:

     template <typename _Value>

     class EdgeMapBase {

     private:

       typedef typename _Graph::template EdgeMap<_Value> MapImpl;

     public:

       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

       typedef _Value Value;

       typedef Edge Key;

       EdgeMapBase(const Adaptor& adaptor) :

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

       EdgeMapBase(const Adaptor& adaptor, const Value& v) 

         : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}

       void set(const Edge& e, const Value& a) { 

 	if (Parent::direction(e)) {

 	  forward_map.set(e, a); 

         } else { 

 	  backward_map.set(e, a);

         } 

       }

       typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const { 

 	if (Parent::direction(e)) {

 	  return forward_map[e]; 

 	} else { 

 	  return backward_map[e]; 

         }

       }

       typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) { 

 	if (Parent::direction(e)) {

 	  return forward_map[e]; 

 	} else { 

 	  return backward_map[e]; 

         }

       }

     protected:

       MapImpl forward_map, backward_map; 

     };

   public:

     template <typename _Value>

     class EdgeMap 

       : public SubMapExtender<Adaptor, EdgeMapBase<_Value> > 

     {

     public:

       typedef Adaptor Graph;

       typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;

       EdgeMap(const Graph& g) 

 	: Parent(g) {}

       EdgeMap(const Graph& g, const _Value& v) 

 	: Parent(g, v) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

 	return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

 	return *this;

       }

     };

     template <typename _Value>

     class UEdgeMap : public Graph::template EdgeMap<_Value> {

     public:

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

       explicit UEdgeMap(const Adaptor& ga) 

 	: Parent(*ga.graph) {}

       UEdgeMap(const Adaptor& ga, const _Value& value)

 	: Parent(*ga.graph, value) {}

       UEdgeMap& operator=(const UEdgeMap& cmap) {

         return operator=<UEdgeMap>(cmap);

       }

       template <typename CMap>

       UEdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   template <typename _Graph, typename Enable = void>

   class AlterableUndirGraphAdaptor 

     : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {

   public:

     typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;

   protected:

     AlterableUndirGraphAdaptor() : Parent() {}

   public:

     typedef typename Parent::EdgeNotifier UEdgeNotifier;

     typedef InvalidType EdgeNotifier;

   };

   template <typename _Graph>

   class AlterableUndirGraphAdaptor<

     _Graph, 

     typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type > 

     : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {

   public:

     typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;

     typedef _Graph Graph;

     typedef typename _Graph::Edge GraphEdge;

   protected:

     AlterableUndirGraphAdaptor() 

       : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}

     void setGraph(_Graph& g) {

       Parent::setGraph(g);

       edge_notifier_proxy.setNotifier(g.notifier(GraphEdge()));

     }

   public:

     ~AlterableUndirGraphAdaptor() {

       edge_notifier.clear();

     }

     typedef typename Parent::UEdge UEdge;

     typedef typename Parent::Edge Edge;

     typedef typename Parent::EdgeNotifier UEdgeNotifier;

     using Parent::notifier;

     typedef AlterationNotifier<AlterableUndirGraphAdaptor, 

                                Edge> EdgeNotifier;

     EdgeNotifier& notifier(Edge) const { return edge_notifier; }

   protected:

     class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {

     public:

       typedef typename Graph::EdgeNotifier::ObserverBase Parent;

       typedef AlterableUndirGraphAdaptor AdaptorBase;

       NotifierProxy(const AdaptorBase& _adaptor)

         : Parent(), adaptor(&_adaptor) {

       }

       virtual ~NotifierProxy() {

         if (Parent::attached()) {

           Parent::detach();

         }

       }

       void setNotifier(typename Graph::EdgeNotifier& nf) {

         Parent::attach(nf);

       }

     protected:

       virtual void add(const GraphEdge& ge) {

         std::vector<Edge> edges;

         edges.push_back(AdaptorBase::Parent::direct(ge, true));

         edges.push_back(AdaptorBase::Parent::direct(ge, false));

         adaptor->notifier(Edge()).add(edges);

       }

       virtual void add(const std::vector<GraphEdge>& ge) {

         std::vector<Edge> edges;

         for (int i = 0; i < int(ge.size()); ++i) { 

           edges.push_back(AdaptorBase::Parent::direct(ge[i], true));

           edges.push_back(AdaptorBase::Parent::direct(ge[i], false));

         }

         adaptor->notifier(Edge()).add(edges);

       }

       virtual void erase(const GraphEdge& ge) {

         std::vector<Edge> edges;

         edges.push_back(AdaptorBase::Parent::direct(ge, true));

         edges.push_back(AdaptorBase::Parent::direct(ge, false));

         adaptor->notifier(Edge()).erase(edges);

       }

       virtual void erase(const std::vector<GraphEdge>& ge) {

         std::vector<Edge> edges;

         for (int i = 0; i < int(ge.size()); ++i) { 

           edges.push_back(AdaptorBase::Parent::direct(ge[i], true));

           edges.push_back(AdaptorBase::Parent::direct(ge[i], false));

         }

         adaptor->notifier(Edge()).erase(edges);

       }

       virtual void build() {

         adaptor->notifier(Edge()).build();

       }

       virtual void clear() {

         adaptor->notifier(Edge()).clear();

       }

       const AdaptorBase* adaptor;

     };

     mutable EdgeNotifier edge_notifier;

     NotifierProxy edge_notifier_proxy;

   };

   ///\ingroup graph_adaptors

   ///

   /// \brief An undirected graph is made from a directed graph by an adaptor

   ///

   /// This adaptor makes an undirected graph from a directed

   /// graph. All edge of the underlying will be showed in the adaptor

   /// as an undirected edge. Let's see an informal example about using

   /// this adaptor:

   ///

   /// There is a network of the streets of a town. Of course there are

   /// some one-way street in the town hence the network is a directed

   /// one. There is a crazy driver who go oppositely in the one-way

   /// street without moral sense. Of course he can pass this streets

   /// slower than the regular way, in fact his speed is half of the

   /// normal speed. How long should he drive to get from a source

   /// point to the target? Let see the example code which calculate it:

   ///

   ///\code

   /// typedef UndirGraphAdaptor<Graph> UGraph;

   /// UGraph ugraph(graph);

   ///

   /// typedef SimpleMap<LengthMap> FLengthMap;

   /// FLengthMap flength(length);

   ///

   /// typedef ScaleMap<LengthMap> RLengthMap;

   /// RLengthMap rlength(length, 2.0);

   ///

   /// typedef UGraph::CombinedEdgeMap<FLengthMap, RLengthMap > ULengthMap;

   /// ULengthMap ulength(flength, rlength);

   /// 

   /// Dijkstra<UGraph, ULengthMap> dijkstra(ugraph, ulength);

   /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;

   ///\endcode

   ///

   /// The combined edge map makes the length map for the undirected

   /// graph. It is created from a forward and reverse map. The forward

   /// map is created from the original length map with a SimpleMap

   /// adaptor which just makes a read-write map from the reference map

   /// i.e. it forgets that it can be return reference to values. The

   /// reverse map is just the scaled original map with the ScaleMap

   /// adaptor. The combination solves that passing the reverse way

   /// takes double time than the original. To get the driving time we

   /// run the dijkstra algorithm on the undirected graph.

   ///

   /// \author Marton Makai and Balazs Dezso

   template<typename _Graph>

   class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {

   public:

     typedef _Graph Graph;

     typedef AlterableUndirGraphAdaptor<_Graph> Parent;

   protected:

     UndirGraphAdaptor() { }

   public:

     /// \brief Constructor

     ///

     /// Constructor

     UndirGraphAdaptor(_Graph& _graph) { 

       setGraph(_graph);

     }

     /// \brief EdgeMap combined from two original EdgeMap

     ///

     /// This class adapts two original graph EdgeMap to

     /// get an edge map on the adaptor.

     template <typename _ForwardMap, typename _BackwardMap>

     class CombinedEdgeMap {

     public:

       typedef _ForwardMap ForwardMap;

       typedef _BackwardMap BackwardMap;

       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;

       typedef typename ForwardMap::Value Value;

       typedef typename Parent::Edge Key;

       /// \brief Constructor      

       ///

       /// Constructor      

       CombinedEdgeMap() : forward_map(0), backward_map(0) {}

       /// \brief Constructor      

       ///

       /// Constructor      

       CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) 

         : forward_map(&_forward_map), backward_map(&_backward_map) {}

       /// \brief Sets the value associated with a key.

       ///

       /// Sets the value associated with a key.

       void set(const Key& e, const Value& a) { 

 	if (Parent::direction(e)) {

 	  forward_map->set(e, a); 

         } else { 

 	  backward_map->set(e, a);

         } 

       }

       /// \brief Returns the value associated with a key.

       ///

       /// Returns the value associated with a key.

       typename MapTraits<ForwardMap>::ConstReturnValue 

       operator[](const Key& e) const { 

 	if (Parent::direction(e)) {

 	  return (*forward_map)[e]; 

 	} else { 

 	  return (*backward_map)[e]; 

         }

       }

       /// \brief Returns the value associated with a key.

       ///

       /// Returns the value associated with a key.

       typename MapTraits<ForwardMap>::ReturnValue 

       operator[](const Key& e) { 

 	if (Parent::direction(e)) {

 	  return (*forward_map)[e]; 

 	} else { 

 	  return (*backward_map)[e]; 

         }

       }

       /// \brief Sets the forward map

       ///

       /// Sets the forward map

       void setForwardMap(ForwardMap& _forward_map) {

         forward_map = &_forward_map;

       }

       /// \brief Sets the backward map

       ///

       /// Sets the backward map

       void setBackwardMap(BackwardMap& _backward_map) {

         backward_map = &_backward_map;

       }

     protected:

       ForwardMap* forward_map;

       BackwardMap* backward_map; 

     };

   };

   /// \brief Just gives back an undir graph adaptor

   ///

   /// Just gives back an undir graph adaptor

   template<typename Graph>

   UndirGraphAdaptor<const Graph>

   undirGraphAdaptor(const Graph& graph) {

     return UndirGraphAdaptor<const Graph>(graph);

   }

   template<typename Graph, typename Number,  

            typename CapacityMap, typename FlowMap, 

            typename Tol = Tolerance<Number> >

   class ResForwardFilter {

     const CapacityMap* capacity;

     const FlowMap* flow;

     Tol tolerance;

   public:

     typedef typename Graph::Edge Key;

     typedef bool Value;

     ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,

                      const Tol& _tolerance = Tol()) 

       : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }

     ResForwardFilter(const Tol& _tolerance) 

       : capacity(0), flow(0), tolerance(_tolerance)  { }

     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }

     void setFlow(const FlowMap& _flow) { flow = &_flow; }

     bool operator[](const typename Graph::Edge& e) const {

       return tolerance.positive((*capacity)[e] - (*flow)[e]);

     }

   };

   template<typename Graph, typename Number,

 	   typename CapacityMap, typename FlowMap,

            typename Tol = Tolerance<Number> >

   class ResBackwardFilter {

     const CapacityMap* capacity;

     const FlowMap* flow;

     Tol tolerance;

   public:

     typedef typename Graph::Edge Key;

     typedef bool Value;

     ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,

                       const Tol& _tolerance = Tol())

       : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }

     ResBackwardFilter(const Tol& _tolerance = Tol())

       : capacity(0), flow(0), tolerance(_tolerance) { }

     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }

     void setFlow(const FlowMap& _flow) { flow = &_flow; }

     bool operator[](const typename Graph::Edge& e) const {

       return tolerance.positive((*flow)[e]);

     }

   };

   ///\ingroup graph_adaptors

   ///

   ///\brief An adaptor for composing the residual

   ///graph for directed flow and circulation problems.

   ///

   ///An adaptor for composing the residual graph for directed flow and

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

   ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,

   ///be functions on the edge-set.

   ///

   ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands

   ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a

   ///graph instange \c g of type \c ListGraph implements \f$ G \f$.

   ///

   ///\code 

   ///  ListGraph g;

   ///\endcode 

   ///

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

   /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,

   ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 

   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called

   ///residual graph.  When we take the union 

   /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e. 

   ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$, 

   ///then in the adaptor it appears twice. The following code shows how 

   ///such an instance can be constructed.

   ///

   ///\code 

   ///  typedef ListGraph Graph; 

   ///  Graph::EdgeMap<int> f(g);

   ///  Graph::EdgeMap<int> c(g); 

   ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); 

   ///\endcode

   ///\author Marton Makai

   ///

   template<typename Graph, typename Number, 

 	   typename CapacityMap, typename FlowMap,

            typename Tol = Tolerance<Number> >

   class ResGraphAdaptor : 

     public EdgeSubGraphAdaptor< 

     UndirGraphAdaptor<const Graph>, 

     typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<

     ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,  

     ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {

   public:

     typedef UndirGraphAdaptor<const Graph> UGraph;

     typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap> 

     ForwardFilter;

     typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> 

     BackwardFilter;

     typedef typename UGraph::

     template CombinedEdgeMap<ForwardFilter, BackwardFilter>

     EdgeFilter;

     typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;

   protected:

     const CapacityMap* capacity;

     FlowMap* flow;

     UGraph ugraph;

     ForwardFilter forward_filter;

     BackwardFilter backward_filter;

     EdgeFilter edge_filter;

     void setCapacityMap(const CapacityMap& _capacity) {

       capacity=&_capacity;

       forward_filter.setCapacity(_capacity);

       backward_filter.setCapacity(_capacity);

     }

     void setFlowMap(FlowMap& _flow) {

       flow=&_flow;

       forward_filter.setFlow(_flow);

       backward_filter.setFlow(_flow);

     }

   public:

     /// \brief Constructor of the residual graph.

     ///

     /// Constructor of the residual graph. The parameters are the graph type,

     /// the flow map, the capacity map and a tolerance object.

     ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity, 

                     FlowMap& _flow, const Tol& _tolerance = Tol()) 

       : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),

         forward_filter(_capacity, _flow, _tolerance), 

         backward_filter(_capacity, _flow, _tolerance),

         edge_filter(forward_filter, backward_filter)

     {

       Parent::setGraph(ugraph);

       Parent::setEdgeFilterMap(edge_filter);

     }

     typedef typename Parent::Edge Edge;

     /// \brief Gives back the residual capacity of the edge.

     ///

     /// Gives back the residual capacity of the edge.

     Number rescap(const Edge& edge) const {

       if (UGraph::direction(edge)) {

         return (*capacity)[edge]-(*flow)[edge]; 

       } else {

         return (*flow)[edge];

       }

     } 

     /// \brief Augment on the given edge in the residual graph.

     ///

     /// Augment on the given edge in the residual graph. It increase

     /// or decrease the flow on the original edge depend on the direction

     /// of the residual edge.

     void augment(const Edge& e, Number a) const {

       if (UGraph::direction(e)) {

         flow->set(e, (*flow)[e] + a);

       } else {  

         flow->set(e, (*flow)[e] - a);

       }

     }

     /// \brief Returns the direction of the edge.

     ///

     /// Returns true when the edge is same oriented as the original edge.

     static bool forward(const Edge& e) {

       return UGraph::direction(e);

     }

     /// \brief Returns the direction of the edge.

     ///

     /// Returns true when the edge is opposite oriented as the original edge.

     static bool backward(const Edge& e) {

       return !UGraph::direction(e);

     }

     /// \brief Gives back the forward oriented residual edge.

     ///

     /// Gives back the forward oriented residual edge.

     static Edge forward(const typename Graph::Edge& e) {

       return UGraph::direct(e, true);

     }

     /// \brief Gives back the backward oriented residual edge.

     ///

     /// Gives back the backward oriented residual edge.

     static Edge backward(const typename Graph::Edge& e) {

       return UGraph::direct(e, false);

     }

     /// \brief Residual capacity map.

     ///

     /// In generic residual graphs the residual capacity can be obtained 

     /// as a map. 

     class ResCap {

     protected:

       const ResGraphAdaptor* res_graph;

     public:

       typedef Number Value;

       typedef Edge Key;

       ResCap(const ResGraphAdaptor& _res_graph) 

         : res_graph(&_res_graph) {}

       Number operator[](const Edge& e) const {

         return res_graph->rescap(e);

       }

     };

   };

   template <typename _Graph, typename FirstOutEdgesMap>

   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<_Graph> Parent;

   protected:

     FirstOutEdgesMap* first_out_edges;

     ErasingFirstGraphAdaptorBase() : Parent(), 

 				     first_out_edges(0) { }

     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

       first_out_edges=&_first_out_edges;

     }

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     void firstOut(Edge& i, const Node& n) const { 

       i=(*first_out_edges)[n];

     }

     void erase(const Edge& e) const {

       Node n=source(e);

       Edge f=e;

       Parent::nextOut(f);

       first_out_edges->set(n, f);

     }    

   };

   ///\ingroup graph_adaptors

   ///

   ///\brief For blocking flows.

   ///

   ///This graph adaptor is used for on-the-fly 

   ///Dinits blocking flow computations.

   ///For each node, an out-edge is stored which is used when the 

   ///\code

   ///OutEdgeIt& first(OutEdgeIt&, const Node&)

   ///\endcode

   ///is called. 

   ///

   ///\author Marton Makai

   ///

   template <typename _Graph, typename FirstOutEdgesMap>

   class ErasingFirstGraphAdaptor : 

     public GraphAdaptorExtender<

     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorExtender<

       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

     ErasingFirstGraphAdaptor(Graph& _graph, 

 			     FirstOutEdgesMap& _first_out_edges) { 

       setGraph(_graph);

       setFirstOutEdgesMap(_first_out_edges);

     } 

   };

   /// \brief Base class for split graph adaptor

   ///

   /// Base class of split graph adaptor. In most case you do not need to

   /// use it directly but the documented member functions of this class can 

   /// be used with the SplitGraphAdaptor class.

   /// \sa SplitGraphAdaptor

   template <typename _Graph>

   class SplitGraphAdaptorBase 

     : public GraphAdaptorBase<const _Graph> {

   public:

     typedef _Graph Graph;

     typedef GraphAdaptorBase<const _Graph> Parent;

     typedef typename Graph::Node GraphNode;

     typedef typename Graph::Edge GraphEdge;

     class Node;

     class Edge;

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

     class Node : public GraphNode {

       friend class SplitGraphAdaptorBase;

       template <typename T> friend class NodeMap;

     private:

       bool in_node;

       Node(GraphNode _node, bool _in_node)

 	: GraphNode(_node), in_node(_in_node) {}

     public:

       Node() {}

       Node(Invalid) : GraphNode(INVALID), in_node(true) {}

       bool operator==(const Node& node) const {

 	return GraphNode::operator==(node) && in_node == node.in_node;

       }

       bool operator!=(const Node& node) const {

 	return !(*this == node);

       }

       bool operator<(const Node& node) const {

 	return GraphNode::operator<(node) || 

 	  (GraphNode::operator==(node) && in_node < node.in_node);

       }

     };

     class Edge {

       friend class SplitGraphAdaptorBase;

       template <typename T> friend class EdgeMap;

     private:

       typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;

       explicit Edge(const GraphEdge& edge) : item(edge) {}

       explicit Edge(const GraphNode& node) : item(node) {}

       EdgeImpl item;

     public:

       Edge() {}

       Edge(Invalid) : item(GraphEdge(INVALID)) {}

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

         if (item.firstState()) {

           if (edge.item.firstState()) {

             return item.first() == edge.item.first();

           }

         } else {

           if (edge.item.secondState()) {

             return item.second() == edge.item.second();

           }

         }

         return false;

       }

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

 	return !(*this == edge);

       }

       bool operator<(const Edge& edge) const {

         if (item.firstState()) {

           if (edge.item.firstState()) {

             return item.first() < edge.item.first();

           }

           return false;

         } else {

           if (edge.item.secondState()) {

             return item.second() < edge.item.second();

           }

           return true;

         }

       }

       operator GraphEdge() const { return item.first(); }

       operator GraphNode() const { return item.second(); }

     };

     void first(Node& n) const {

       Parent::first(n);

       n.in_node = true;

     }

     void next(Node& n) const {

       if (n.in_node) {

 	n.in_node = false;

       } else {

 	n.in_node = true;

 	Parent::next(n);

       }

     }

     void first(Edge& e) const {

       e.item.setSecond();

       Parent::first(e.item.second());

       if (e.item.second() == INVALID) {

         e.item.setFirst();

 	Parent::first(e.item.first());

       }

     }

     void next(Edge& e) const {

       if (e.item.secondState()) {

 	Parent::next(e.item.second());

         if (e.item.second() == INVALID) {

           e.item.setFirst();

           Parent::first(e.item.first());

         }

       } else {

 	Parent::next(e.item.first());

       }      

     }

     void firstOut(Edge& e, const Node& n) const {

       if (n.in_node) {

         e.item.setSecond(n);

       } else {

         e.item.setFirst();

 	Parent::firstOut(e.item.first(), n);

       }

     }

     void nextOut(Edge& e) const {

       if (!e.item.firstState()) {

 	e.item.setFirst(INVALID);

       } else {

 	Parent::nextOut(e.item.first());

       }      

     }

     void firstIn(Edge& e, const Node& n) const {

       if (!n.in_node) {

         e.item.setSecond(n);        

       } else {

         e.item.setFirst();

 	Parent::firstIn(e.item.first(), n);

       }

     }

     void nextIn(Edge& e) const {

       if (!e.item.firstState()) {

 	e.item.setFirst(INVALID);

       } else {

 	Parent::nextIn(e.item.first());

       }

     }

     Node source(const Edge& e) const {

       if (e.item.firstState()) {

 	return Node(Parent::source(e.item.first()), false);

       } else {

 	return Node(e.item.second(), true);

       }

     }

     Node target(const Edge& e) const {

       if (e.item.firstState()) {

 	return Node(Parent::target(e.item.first()), true);

       } else {

 	return Node(e.item.second(), false);

       }

     }

     int id(const Node& n) const {

       return (Parent::id(n) << 1) | (n.in_node ? 0 : 1);

     }

     Node nodeFromId(int ix) const {

       return Node(Parent::nodeFromId(ix >> 1), (ix & 1) == 0);

     }

     int maxNodeId() const {

       return 2 * Parent::maxNodeId() + 1;

     }

     int id(const Edge& e) const {

       if (e.item.firstState()) {

         return Parent::id(e.item.first()) << 1;

       } else {

         return (Parent::id(e.item.second()) << 1) | 1;

       }

     }

     Edge edgeFromId(int ix) const {

       if ((ix & 1) == 0) {

         return Edge(Parent::edgeFromId(ix >> 1));

       } else {

         return Edge(Parent::nodeFromId(ix >> 1));

       }

     }

     int maxEdgeId() const {

       return std::max(Parent::maxNodeId() << 1, 

                       (Parent::maxEdgeId() << 1) | 1);

     }

     /// \brief Returns true when the node is in-node.

     ///

     /// Returns true when the node is in-node.

     static bool inNode(const Node& n) {

       return n.in_node;

     }

     /// \brief Returns true when the node is out-node.

     ///

     /// Returns true when the node is out-node.

     static bool outNode(const Node& n) {

       return !n.in_node;

     }

     /// \brief Returns true when the edge is edge in the original graph.

     ///

     /// Returns true when the edge is edge in the original graph.

     static bool origEdge(const Edge& e) {

       return e.item.firstState();

     }

     /// \brief Returns true when the edge binds an in-node and an out-node.

     ///

     /// Returns true when the edge binds an in-node and an out-node.

     static bool bindEdge(const Edge& e) {

       return e.item.secondState();

     }

     /// \brief Gives back the in-node created from the \c node.

     ///

     /// Gives back the in-node created from the \c node.

     static Node inNode(const GraphNode& n) {

       return Node(n, true);

     }

     /// \brief Gives back the out-node created from the \c node.

     ///

     /// Gives back the out-node created from the \c node.

     static Node outNode(const GraphNode& n) {

       return Node(n, false);

     }

     /// \brief Gives back the edge binds the two part of the node.

     /// 

     /// Gives back the edge binds the two part of the node.

     static Edge edge(const GraphNode& n) {

       return Edge(n);

     }

     /// \brief Gives back the edge of the original edge.

     /// 

     /// Gives back the edge of the original edge.

     static Edge edge(const GraphEdge& e) {

       return Edge(e);

     }

     typedef True NodeNumTag;

     int nodeNum() const {

       return  2 * countNodes(*Parent::graph);

     }

     typedef True EdgeNumTag;

     int edgeNum() const {

       return countEdges(*Parent::graph) + countNodes(*Parent::graph);

     }

     typedef True FindEdgeTag;

     Edge findEdge(const Node& u, const Node& v, 

 		  const Edge& prev = INVALID) const {

       if (inNode(u)) {

         if (outNode(v)) {

           if (static_cast<const GraphNode&>(u) == 

               static_cast<const GraphNode&>(v) && prev == INVALID) {

             return Edge(u);

           }

         }

       } else {

         if (inNode(v)) {

           return Edge(findEdge(*Parent::graph, u, v, prev));

         }

       }

       return INVALID;

     }

     template <typename T>

     class NodeMap : public MapBase<Node, T> {

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

     public:

       NodeMap(const SplitGraphAdaptorBase& _graph) 

 	: inNodeMap(_graph), outNodeMap(_graph) {}

       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 

 	: inNodeMap(_graph, t), outNodeMap(_graph, t) {}

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

       void set(const Node& key, const T& val) {

 	if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }

 	else {outNodeMap.set(key, val); }

       }

       typename MapTraits<NodeImpl>::ReturnValue 

       operator[](const Node& key) {

 	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }

 	else { return outNodeMap[key]; }

       }

       typename MapTraits<NodeImpl>::ConstReturnValue

       operator[](const Node& key) const {

 	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }

 	else { return outNodeMap[key]; }

       }

     private:

       NodeImpl inNodeMap, outNodeMap;

     };

     template <typename T>

     class EdgeMap : public MapBase<Edge, T> {

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

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

     public:

       EdgeMap(const SplitGraphAdaptorBase& _graph) 

 	: edge_map(_graph), node_map(_graph) {}

       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 

 	: edge_map(_graph, t), node_map(_graph, t) {}

       EdgeMap& operator=(const EdgeMap& cmap) {

         return operator=<EdgeMap>(cmap);

       }

       template <typename CMap>

       EdgeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

       void set(const Edge& key, const T& val) {

 	if (SplitGraphAdaptorBase::origEdge(key)) { 

           edge_map.set(key.item.first(), val); 

         } else {

           node_map.set(key.item.second(), val); 

         }

       }

       typename MapTraits<EdgeMapImpl>::ReturnValue

       operator[](const Edge& key) {

 	if (SplitGraphAdaptorBase::origEdge(key)) { 

           return edge_map[key.item.first()];

         } else {

           return node_map[key.item.second()];

         }

       }

       typename MapTraits<EdgeMapImpl>::ConstReturnValue

       operator[](const Edge& key) const {

 	if (SplitGraphAdaptorBase::origEdge(key)) { 

           return edge_map[key.item.first()];

         } else {

           return node_map[key.item.second()];

         }

       }

     private:

       typename Parent::template EdgeMap<T> edge_map;

       typename Parent::template NodeMap<T> node_map;

     };

   };

   template <typename _Graph, typename NodeEnable = void, 

             typename EdgeEnable = void>

   class AlterableSplitGraphAdaptor 

     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {

   public:

     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node GraphNode;

     typedef typename Graph::Node GraphEdge;

   protected:

     AlterableSplitGraphAdaptor() : Parent() {}

   public:

     typedef InvalidType NodeNotifier;

     typedef InvalidType EdgeNotifier;

   };

   template <typename _Graph, typename EdgeEnable>

   class AlterableSplitGraphAdaptor<

     _Graph,

     typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,

     EdgeEnable> 

       : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {

   public:

     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node GraphNode;

     typedef typename Graph::Edge GraphEdge;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   protected:

     AlterableSplitGraphAdaptor() 

       : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}

     void setGraph(_Graph& graph) {

       Parent::setGraph(graph);

       node_notifier_proxy.setNotifier(graph.notifier(GraphNode()));

     }

   public:

     ~AlterableSplitGraphAdaptor() {

       node_notifier.clear();

     }

     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;

     typedef InvalidType EdgeNotifier;

     NodeNotifier& notifier(Node) const { return node_notifier; }

   protected:

     class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {

     public:

       typedef typename Graph::NodeNotifier::ObserverBase Parent;

       typedef AlterableSplitGraphAdaptor AdaptorBase;

       NodeNotifierProxy(const AdaptorBase& _adaptor)

         : Parent(), adaptor(&_adaptor) {

       }

       virtual ~NodeNotifierProxy() {

         if (Parent::attached()) {

           Parent::detach();

         }

       }

       void setNotifier(typename Graph::NodeNotifier& graph_notifier) {

         Parent::attach(graph_notifier);

       }

     protected:

       virtual void add(const GraphNode& gn) {

         std::vector<Node> nodes;

         nodes.push_back(AdaptorBase::Parent::inNode(gn));

         nodes.push_back(AdaptorBase::Parent::outNode(gn));

         adaptor->notifier(Node()).add(nodes);

       }

       virtual void add(const std::vector<GraphNode>& gn) {

         std::vector<Node> nodes;

         for (int i = 0; i < int(gn.size()); ++i) {

           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));

           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));

         }

         adaptor->notifier(Node()).add(nodes);

       }

       virtual void erase(const GraphNode& gn) {

         std::vector<Node> nodes;

         nodes.push_back(AdaptorBase::Parent::inNode(gn));

         nodes.push_back(AdaptorBase::Parent::outNode(gn));

         adaptor->notifier(Node()).erase(nodes);

       }

       virtual void erase(const std::vector<GraphNode>& gn) {

         std::vector<Node> nodes;

         for (int i = 0; i < int(gn.size()); ++i) {

           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));

           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));

         }

         adaptor->notifier(Node()).erase(nodes);

       }

       virtual void build() {

         adaptor->notifier(Node()).build();

       }

       virtual void clear() {

         adaptor->notifier(Node()).clear();

       }

       const AdaptorBase* adaptor;

     };

     mutable NodeNotifier node_notifier;

     NodeNotifierProxy node_notifier_proxy;

   };

   template <typename _Graph>

   class AlterableSplitGraphAdaptor<

     _Graph,

     typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,

     typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type> 

       : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {

   public:

     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node GraphNode;

     typedef typename Graph::Edge GraphEdge;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   protected:

     AlterableSplitGraphAdaptor() 

       : Parent(), node_notifier(*this), edge_notifier(*this), 

         node_notifier_proxy(*this), edge_notifier_proxy(*this) {}

     void setGraph(_Graph& g) {

       Parent::setGraph(g);

       node_notifier_proxy.setNotifier(g.notifier(GraphNode()));

       edge_notifier_proxy.setNotifier(g.notifier(GraphEdge()));

     }

   public:

     ~AlterableSplitGraphAdaptor() {

       node_notifier.clear();

       edge_notifier.clear();

     }

     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;

     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;

     NodeNotifier& notifier(Node) const { return node_notifier; }

     EdgeNotifier& notifier(Edge) const { return edge_notifier; }

   protected:

     class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {

     public:

       typedef typename Graph::NodeNotifier::ObserverBase Parent;

       typedef AlterableSplitGraphAdaptor AdaptorBase;

       NodeNotifierProxy(const AdaptorBase& _adaptor)

         : Parent(), adaptor(&_adaptor) {

       }

       virtual ~NodeNotifierProxy() {

         if (Parent::attached()) {

           Parent::detach();

         }

       }

       void setNotifier(typename Graph::NodeNotifier& graph_notifier) {

         Parent::attach(graph_notifier);

       }

     protected:

       virtual void add(const GraphNode& gn) {

         std::vector<Node> nodes;

         nodes.push_back(AdaptorBase::Parent::inNode(gn));

         nodes.push_back(AdaptorBase::Parent::outNode(gn));

         adaptor->notifier(Node()).add(nodes);

         adaptor->notifier(Edge()).add(AdaptorBase::Parent::edge(gn));

       }

       virtual void add(const std::vector<GraphNode>& gn) {

         std::vector<Node> nodes;

         std::vector<Edge> edges;

         for (int i = 0; i < int(gn.size()); ++i) {

           edges.push_back(AdaptorBase::Parent::edge(gn[i]));

           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));

           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));

         }

         adaptor->notifier(Node()).add(nodes);

         adaptor->notifier(Edge()).add(edges);

       }

       virtual void erase(const GraphNode& gn) {

         adaptor->notifier(Edge()).erase(AdaptorBase::Parent::edge(gn));

         std::vector<Node> nodes;

         nodes.push_back(AdaptorBase::Parent::inNode(gn));

         nodes.push_back(AdaptorBase::Parent::outNode(gn));

         adaptor->notifier(Node()).erase(nodes);

       }

       virtual void erase(const std::vector<GraphNode>& gn) {

         std::vector<Node> nodes;

         std::vector<Edge> edges;

         for (int i = 0; i < int(gn.size()); ++i) {

           edges.push_back(AdaptorBase::Parent::edge(gn[i]));

           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));

           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));

         }

         adaptor->notifier(Edge()).erase(edges);

         adaptor->notifier(Node()).erase(nodes);

       }

       virtual void build() {

         std::vector<Edge> edges;

         const typename Parent::Notifier* nf = Parent::notifier();

         GraphNode it;

         for (nf->first(it); it != INVALID; nf->next(it)) {

           edges.push_back(AdaptorBase::Parent::edge(it));

         }

         adaptor->notifier(Node()).build();

         adaptor->notifier(Edge()).add(edges);        

       }

       virtual void clear() {

         std::vector<Edge> edges;

         const typename Parent::Notifier* nf = Parent::notifier();

         GraphNode it;

         for (nf->first(it); it != INVALID; nf->next(it)) {

           edges.push_back(AdaptorBase::Parent::edge(it));

         }

         adaptor->notifier(Edge()).erase(edges);        

         adaptor->notifier(Node()).clear();

       }

       const AdaptorBase* adaptor;

     };

     class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {

     public:

       typedef typename Graph::EdgeNotifier::ObserverBase Parent;

       typedef AlterableSplitGraphAdaptor AdaptorBase;

       EdgeNotifierProxy(const AdaptorBase& _adaptor)

         : Parent(), adaptor(&_adaptor) {

       }

       virtual ~EdgeNotifierProxy() {

         if (Parent::attached()) {

           Parent::detach();

         }

       }

       void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {

         Parent::attach(graph_notifier);

       }

     protected:

       virtual void add(const GraphEdge& ge) {

         adaptor->notifier(Edge()).add(AdaptorBase::edge(ge));

       }

       virtual void add(const std::vector<GraphEdge>& ge) {

         std::vector<Edge> edges;

         for (int i = 0; i < int(ge.size()); ++i) {

           edges.push_back(AdaptorBase::edge(ge[i]));

         }

         adaptor->notifier(Edge()).add(edges);

       }

       virtual void erase(const GraphEdge& ge) {

         adaptor->notifier(Edge()).erase(AdaptorBase::edge(ge));

       }

       virtual void erase(const std::vector<GraphEdge>& ge) {

         std::vector<Edge> edges;

         for (int i = 0; i < int(ge.size()); ++i) {

           edges.push_back(AdaptorBase::edge(ge[i]));

         }

         adaptor->notifier(Edge()).erase(edges);

       }

       virtual void build() {

         std::vector<Edge> edges;

         const typename Parent::Notifier* nf = Parent::notifier();

         GraphEdge it;

         for (nf->first(it); it != INVALID; nf->next(it)) {

           edges.push_back(AdaptorBase::Parent::edge(it));

         }

         adaptor->notifier(Edge()).add(edges);

       }

       virtual void clear() {

         std::vector<Edge> edges;

         const typename Parent::Notifier* nf = Parent::notifier();

         GraphEdge it;

         for (nf->first(it); it != INVALID; nf->next(it)) {

           edges.push_back(AdaptorBase::Parent::edge(it));

         }

         adaptor->notifier(Edge()).erase(edges);

       }

       const AdaptorBase* adaptor;

     };

     mutable NodeNotifier node_notifier;

     mutable EdgeNotifier edge_notifier;

     NodeNotifierProxy node_notifier_proxy;

     EdgeNotifierProxy edge_notifier_proxy;

   };

   /// \ingroup graph_adaptors

   ///

   /// \brief Split graph adaptor class

   /// 

   /// This is an graph adaptor which splits all node into an in-node

   /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$

   /// node in the graph with two node, \f$ u_{in} \f$ node and 

   /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the 

   /// original graph the new target of the edge will be \f$ u_{in} \f$ and

   /// similarly the source of the original \f$ (u, v) \f$ edge will be

   /// \f$ u_{out} \f$.  The adaptor will add for each node in the 

   /// original graph an additional edge which will connect 

   /// \f$ (u_{in}, u_{out}) \f$.

   ///

   /// The aim of this class is to run algorithm with node costs if the 

   /// algorithm can use directly just edge costs. In this case we should use

   /// a \c SplitGraphAdaptor and set the node cost of the graph to the

   /// bind edge in the adapted graph.

   /// 

   /// By example a maximum flow algoritm can compute how many edge

   /// disjoint paths are in the graph. But we would like to know how

   /// many node disjoint paths are in the graph. First we have to

   /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow

   /// algorithm on the adapted graph. The bottleneck of the flow will

   /// be the bind edges which bounds the flow with the count of the

   /// node disjoint paths.

   ///

   ///\code

   ///

   /// typedef SplitGraphAdaptor<SmartGraph> SGraph;

   ///

   /// SGraph sgraph(graph);

   ///

   /// typedef ConstMap<SGraph::Edge, int> SCapacity;

   /// SCapacity scapacity(1);

   ///

   /// SGraph::EdgeMap<int> sflow(sgraph);

   ///

   /// Preflow<SGraph, SCapacity> 

   ///   spreflow(sgraph, scapacity, 

   ///            SGraph::outNode(source), SGraph::inNode(target));

   ///                                            

   /// spreflow.run();

   ///

   ///\endcode

   ///

   /// The result of the mamixum flow on the original graph

   /// shows the next figure:

   ///

   /// \image html edge_disjoint.png

   /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth

   /// 

   /// And the maximum flow on the adapted graph:

   ///

   /// \image html node_disjoint.png

   /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth

   ///

   /// The second solution contains just 3 disjoint paths while the first 4.

   /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.

   ///

   /// This graph adaptor is fully conform to the 

   /// \ref concepts::Graph "Graph" concept and

   /// contains some additional member functions and types. The 

   /// documentation of some member functions may be found just in the

   /// SplitGraphAdaptorBase class.

   ///

   /// \sa SplitGraphAdaptorBase

   template <typename _Graph>

   class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {

   public:

     typedef AlterableSplitGraphAdaptor<_Graph> Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     /// \brief Constructor of the adaptor.

     ///

     /// Constructor of the adaptor.

     SplitGraphAdaptor(_Graph& g) {

       Parent::setGraph(g);

     }

     /// \brief NodeMap combined from two original NodeMap

     ///

     /// This class adapt two of the original graph NodeMap to

     /// get a node map on the adapted graph.

     template <typename InNodeMap, typename OutNodeMap>

     class CombinedNodeMap {

     public:

       typedef Node Key;

       typedef typename InNodeMap::Value Value;

       /// \brief Constructor

       ///

       /// Constructor.

       CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap) 

 	: inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}

       /// \brief The subscript operator.

       ///

       /// The subscript operator.

       Value& operator[](const Key& key) {

 	if (Parent::inNode(key)) {

 	  return inNodeMap[key];

 	} else {

 	  return outNodeMap[key];

 	}

       }

       /// \brief The const subscript operator.

       ///

       /// The const subscript operator.

       Value operator[](const Key& key) const {

 	if (Parent::inNode(key)) {

 	  return inNodeMap[key];

 	} else {

 	  return outNodeMap[key];

 	}

       }

       /// \brief The setter function of the map.

       /// 

       /// The setter function of the map.

       void set(const Key& key, const Value& value) {

 	if (Parent::inNode(key)) {

 	  inNodeMap.set(key, value);

 	} else {

 	  outNodeMap.set(key, value);

 	}

       }

     private:

       InNodeMap& inNodeMap;

       OutNodeMap& outNodeMap;

     };

     /// \brief Just gives back a combined node map.

     /// 

     /// Just gives back a combined node map.

     template <typename InNodeMap, typename OutNodeMap>

     static CombinedNodeMap<InNodeMap, OutNodeMap> 

     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {

       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);

     }

     template <typename InNodeMap, typename OutNodeMap>

     static CombinedNodeMap<const InNodeMap, OutNodeMap> 

     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {

       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);

     }

     template <typename InNodeMap, typename OutNodeMap>

     static CombinedNodeMap<InNodeMap, const OutNodeMap> 

     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

     }

     template <typename InNodeMap, typename OutNodeMap>

     static CombinedNodeMap<const InNodeMap, const OutNodeMap> 

     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

       return CombinedNodeMap<const InNodeMap, 

         const OutNodeMap>(in_map, out_map);

     }

     /// \brief EdgeMap combined from an original EdgeMap and NodeMap

     ///

     /// This class adapt an original graph EdgeMap and NodeMap to

     /// get an edge map on the adapted graph.

     template <typename GraphEdgeMap, typename GraphNodeMap>

     class CombinedEdgeMap {

     public:

       typedef Edge Key;

       typedef typename GraphEdgeMap::Value Value;

       /// \brief Constructor

       ///

       /// Constructor.

       CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map) 

 	: edge_map(_edge_map), node_map(_node_map) {}

       /// \brief The subscript operator.

       ///

       /// The subscript operator.

       void set(const Edge& edge, const Value& val) {

 	if (Parent::origEdge(edge)) {

 	  edge_map.set(edge, val);

 	} else {

 	  node_map.set(edge, val);

 	}

       }