source: lemon-0.x/lemon/graph_adaptor.h @ 2050:d9a221218ea4

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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/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 <iostream>

namespace lemon {

  ///\brief Base type for the Graph Adaptors
  ///\ingroup 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& source, const Node& target, 
                  const Edge& prev = INVALID) {
      return graph->findEdge(source, target, prev);
    }
  
    Node addNode() const { 
      return Node(graph->addNode()); 
    }

    Edge addEdge(const Node& source, const Node& target) const { 
      return Edge(graph->addEdge(source, target)); 
    }

    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 id) const {
      return graph->fromNodeId(id);
    }

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

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

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

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

    NodeNotifier& getNotifier(Node) const {
      return graph->getNotifier(Node());
    } 

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

    EdgeNotifier& getNotifier(Edge) const {
      return graph->getNotifier(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;
      }

    };

  };

  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& source, const Node& target, 
                  const Edge& prev = INVALID) {
      return Parent::findEdge(target, source, prev);
    }

  };
    

  ///\brief A graph adaptor which reverses the orientation of the edges.
  ///\ingroup graph_adaptors
  ///
  /// 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.

  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& graph) 
        : Parent(graph) {}
      NodeMap(const Graph& graph, const _Value& value) 
        : Parent(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 SubMapExtender<Adaptor, 
                              typename Parent::template EdgeMap<_Value> > 
    {
    public:
      typedef Adaptor Graph;
      typedef SubMapExtender<Adaptor, typename Parent::
                             template EdgeMap<_Value> > Parent;
    
      EdgeMap(const Graph& graph) 
        : Parent(graph) {}
      EdgeMap(const Graph& graph, const _Value& value) 
        : Parent(graph, value) {}
    
      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& graph) 
        : Parent(graph) {}
      NodeMap(const Graph& graph, const _Value& value) 
        : Parent(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 SubMapExtender<Adaptor, 
                              typename Parent::template EdgeMap<_Value> > 
    {
    public:
      typedef Adaptor Graph;
      typedef SubMapExtender<Adaptor, typename Parent::
                             template EdgeMap<_Value> > Parent;
    
      EdgeMap(const Graph& graph) 
        : Parent(graph) {}
      EdgeMap(const Graph& graph, const _Value& value) 
        : Parent(graph, value) {}
    
      EdgeMap& operator=(const EdgeMap& cmap) {
        return operator=<EdgeMap>(cmap);
      }
    
      template <typename CMap>
      EdgeMap& operator=(const CMap& cmap) {
        Parent::operator=(cmap);
        return *this;
      }
    };

  };

  /// \brief A graph adaptor for hiding nodes and edges from a graph.
  /// \ingroup graph_adaptors
  /// 
  /// 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);
  }



  ///\brief An adaptor for hiding nodes from a graph.
  ///\ingroup graph_adaptors
  ///
  ///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 only
  ///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);
  }

  ///\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, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
  ///  preflow(ga, s, t, const_1_map, flow);
  ///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 (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, typename Enable = void>
  class UndirGraphAdaptorBase : 
    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef UndirGraphAdaptorBase Adaptor;
    typedef UGraphBaseExtender<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& graph) 
        : Parent(graph) {}
      EdgeMap(const Graph& graph, const _Value& value) 
        : Parent(graph, value) {}
    
      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>
  class UndirGraphAdaptorBase<
    _Graph, typename enable_if<
    typename _Graph::EdgeNotifier::Notifier>::type > 
      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
  public:

    typedef _Graph Graph;
    typedef UndirGraphAdaptorBase Adaptor;
    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;

  protected:

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

    void setGraph(_Graph& graph) {
      Parent::setGraph(graph);
      edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
    }

  public:

    ~UndirGraphAdaptorBase() {
      edge_notifier.clear();
    }

    int maxId(typename Parent::Edge) const {
      return Parent::maxEdgeId();
    }


    typedef typename Parent::UEdge UEdge;
    typedef typename Parent::Edge Edge;

    typedef typename Parent::EdgeNotifier UEdgeNotifier;

    using Parent::getNotifier;

    typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }

  protected:

    class NotifierProxy : public UEdgeNotifier::ObserverBase {
    public:

      typedef typename UEdgeNotifier::ObserverBase Parent;
      typedef UndirGraphAdaptorBase AdaptorBase;
      
      NotifierProxy(EdgeNotifier& _edge_notifier)
        : Parent(), edge_notifier(_edge_notifier) {
      }

      virtual ~NotifierProxy() {
        if (Parent::attached()) {
          Parent::detach();
        }
      }

      void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
        Parent::attach(_uedge_notifier);
      }

      
    protected:

      virtual void add(const UEdge& uedge) {
        std::vector<Edge> edges;
        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
        edge_notifier.add(edges);
      }
      virtual void add(const std::vector<UEdge>& uedges) {
        std::vector<Edge> edges;
        for (int i = 0; i < (int)uedges.size(); ++i) { 
          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
        }
        edge_notifier.add(edges);
      }
      virtual void erase(const UEdge& uedge) {
        std::vector<Edge> edges;
        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
        edge_notifier.erase(edges);
      }
      virtual void erase(const std::vector<UEdge>& uedges) {
        std::vector<Edge> edges;
        for (int i = 0; i < (int)uedges.size(); ++i) { 
          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
        }
        edge_notifier.erase(edges);
      }
      virtual void build() {
        edge_notifier.build();
      }
      virtual void clear() {
        edge_notifier.clear();
      }

      EdgeNotifier& edge_notifier;
    };


    mutable EdgeNotifier edge_notifier;
    NotifierProxy edge_notifier_proxy;

  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& graph) 
        : Parent(graph) {}
      EdgeMap(const Graph& graph, const _Value& value) 
        : Parent(graph, value) {}
    
      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;
      }

    };
      
  };

  ///\brief An undirected graph is made from a directed graph by an adaptor
  ///\ingroup graph_adaptors
  ///
  /// Undocumented, untested!!!
  /// If somebody knows nice demo application, let's polulate it.
  /// 
  /// \author Marton Makai
  template<typename _Graph>
  class UndirGraphAdaptor : 
    public UGraphAdaptorExtender<
    UndirGraphAdaptorBase<_Graph> > {
  public:
    typedef _Graph Graph;
    typedef UGraphAdaptorExtender<
      UndirGraphAdaptorBase<_Graph> > Parent;
  protected:
    UndirGraphAdaptor() { }
  public:
    UndirGraphAdaptor(_Graph& _graph) { 
      setGraph(_graph);
    }

    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;
      
      CombinedEdgeMap() : forward_map(0), backward_map(0) {}

      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) 
        : forward_map(&_forward_map), backward_map(&_backward_map) {}
      
      void set(const Key& e, const Value& a) { 
        if (Parent::direction(e)) {
          forward_map->set(e, a); 
        } else { 
          backward_map->set(e, a);
        } 
      }

      typename MapTraits<ForwardMap>::ConstReturnValue 
      operator[](const Key& e) const { 
        if (Parent::direction(e)) {
          return (*forward_map)[e]; 
        } else { 
          return (*backward_map)[e]; 
        }
      }

      typename MapTraits<ForwardMap>::ReturnValue 
      operator[](const Key& e) { 
        if (Parent::direction(e)) {
          return (*forward_map)[e]; 
        } else { 
          return (*backward_map)[e]; 
        }
      }

      void setForwardMap(ForwardMap& _forward_map) {
        forward_map = &_forward_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 Tolerance = Tolerance<Number> >
  class ResForwardFilter {
    const CapacityMap* capacity;
    const FlowMap* flow;
    Tolerance tolerance;
  public:
    typedef typename Graph::Edge Key;
    typedef bool Value;

    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
                     const Tolerance& _tolerance = Tolerance()) 
      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }

    ResForwardFilter(const Tolerance& _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.less((*flow)[e], (*capacity)[e]);
    }
  };

  template<typename Graph, typename Number,
           typename CapacityMap, typename FlowMap,
           typename Tolerance = Tolerance<Number> >
  class ResBackwardFilter {
    const CapacityMap* capacity;
    const FlowMap* flow;
    Tolerance tolerance;
  public:
    typedef typename Graph::Edge Key;
    typedef bool Value;

    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
                      const Tolerance& _tolerance = Tolerance())
      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
    ResBackwardFilter(const Tolerance& _tolerance = 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.less(0, Number((*flow)[e]));
    }
  };

  
  ///\brief An adaptor for composing the residual
  ///graph for directed flow and circulation problems.
  ///
  ///\ingroup graph_adaptors
  ///
  ///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 RevGraphAdaptor 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 Tolerance = 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 Tolerance& _tolerance = Tolerance()) 
      : 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);
    }    
  };


  ///\brief For blocking flows.
  ///\ingroup graph_adaptors
  ///
  ///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);
    } 

  };

//   template <typename _Graph>
//   class SplitGraphAdaptorBase 
//     : public GraphAdaptorBase<_Graph> {
//   public:
//     typedef GraphAdaptorBase<_Graph> Parent;

//     class Node;
//     class Edge;
//     template <typename T> class NodeMap;
//     template <typename T> class EdgeMap;
    

//     class Node : public Parent::Node {
//       friend class SplitGraphAdaptorBase;
//       template <typename T> friend class NodeMap;
//       typedef typename Parent::Node NodeParent;
//     private:

//       bool entry;
//       Node(typename Parent::Node _node, bool _entry)
//      : Parent::Node(_node), entry(_entry) {}
      
//     public:
//       Node() {}
//       Node(Invalid) : NodeParent(INVALID), entry(true) {}

//       bool operator==(const Node& node) const {
//      return NodeParent::operator==(node) && entry == node.entry;
//       }
      
//       bool operator!=(const Node& node) const {
//      return !(*this == node);
//       }
      
//       bool operator<(const Node& node) const {
//      return NodeParent::operator<(node) || 
//        (NodeParent::operator==(node) && entry < node.entry);
//       }
//     };

//     /// \todo May we want VARIANT/union type
//     class Edge : public Parent::Edge {
//       friend class SplitGraphAdaptorBase;
//       template <typename T> friend class EdgeMap;
//     private:
//       typedef typename Parent::Edge EdgeParent;
//       typedef typename Parent::Node NodeParent;
//       NodeParent bind;

//       Edge(const EdgeParent& edge, const NodeParent& node)
//      : EdgeParent(edge), bind(node) {}
//     public:
//       Edge() {}
//       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}

//       bool operator==(const Edge& edge) const {
//      return EdgeParent::operator==(edge) && bind == edge.bind;
//       }
      
//       bool operator!=(const Edge& edge) const {
//      return !(*this == edge);
//       }
      
//       bool operator<(const Edge& edge) const {
//      return EdgeParent::operator<(edge) || 
//        (EdgeParent::operator==(edge) && bind < edge.bind);
//       }
//     };

//     void first(Node& node) const {
//       Parent::first(node);
//       node.entry = true;
//     } 

//     void next(Node& node) const {
//       if (node.entry) {
//      node.entry = false;
//       } else {
//      node.entry = true;
//      Parent::next(node);
//       }
//     }

//     void first(Edge& edge) const {
//       Parent::first(edge);
//       if ((typename Parent::Edge&)edge == INVALID) {
//      Parent::first(edge.bind);
//       } else {
//      edge.bind = INVALID;
//       }
//     }

//     void next(Edge& edge) const {
//       if ((typename Parent::Edge&)edge != INVALID) {
//      Parent::next(edge);
//      if ((typename Parent::Edge&)edge == INVALID) {
//        Parent::first(edge.bind);
//      }
//       } else {
//      Parent::next(edge.bind);
//       }      
//     }

//     void firstIn(Edge& edge, const Node& node) const {
//       if (node.entry) {
//      Parent::firstIn(edge, node);
//      edge.bind = INVALID;
//       } else {
//      (typename Parent::Edge&)edge = INVALID;
//      edge.bind = node;
//       }
//     }

//     void nextIn(Edge& edge) const {
//       if ((typename Parent::Edge&)edge != INVALID) {
//      Parent::nextIn(edge);
//       } else {
//      edge.bind = INVALID;
//       }      
//     }

//     void firstOut(Edge& edge, const Node& node) const {
//       if (!node.entry) {
//      Parent::firstOut(edge, node);
//      edge.bind = INVALID;
//       } else {
//      (typename Parent::Edge&)edge = INVALID;
//      edge.bind = node;
//       }
//     }

//     void nextOut(Edge& edge) const {
//       if ((typename Parent::Edge&)edge != INVALID) {
//      Parent::nextOut(edge);
//       } else {
//      edge.bind = INVALID;
//       }
//     }

//     Node source(const Edge& edge) const {
//       if ((typename Parent::Edge&)edge != INVALID) {
//      return Node(Parent::source(edge), false);
//       } else {
//      return Node(edge.bind, true);
//       }
//     }

//     Node target(const Edge& edge) const {
//       if ((typename Parent::Edge&)edge != INVALID) {
//      return Node(Parent::target(edge), true);
//       } else {
//      return Node(edge.bind, false);
//       }
//     }

//     static bool entryNode(const Node& node) {
//       return node.entry;
//     }

//     static bool exitNode(const Node& node) {
//       return !node.entry;
//     }

//     static Node getEntry(const typename Parent::Node& node) {
//       return Node(node, true);
//     }

//     static Node getExit(const typename Parent::Node& node) {
//       return Node(node, false);
//     }

//     static bool originalEdge(const Edge& edge) {
//       return (typename Parent::Edge&)edge != INVALID;
//     }

//     static bool bindingEdge(const Edge& edge) {
//       return edge.bind != INVALID;
//     }

//     static Node getBindedNode(const Edge& edge) {
//       return edge.bind;
//     }

//     int nodeNum() const {
//       return Parent::nodeNum() * 2;
//     }

//     typedef True EdgeNumTag;
    
//     int edgeNum() const {
//       return countEdges() + Parent::nodeNum();
//     }

//     Edge findEdge(const Node& source, const Node& target, 
//                const Edge& prev = INVALID) const {
//       if (exitNode(source) && entryNode(target)) {
//      return Parent::findEdge(source, target, prev);
//       } else {
//      if (prev == INVALID && entryNode(source) && exitNode(target) && 
//          (typename Parent::Node&)source == (typename Parent::Node&)target) {
//        return Edge(INVALID, source);
//      } else {
//        return INVALID;
//      }
//       }
//     }
    
//     template <typename T>
//     class NodeMap : public MapBase<Node, T> {
//       typedef typename Parent::template NodeMap<T> NodeImpl;
//     public:
//       NodeMap(const SplitGraphAdaptorBase& _graph) 
//      : entry(_graph), exit(_graph) {}
//       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
//      : entry(_graph, t), exit(_graph, t) {}
      
//       void set(const Node& key, const T& val) {
//      if (key.entry) { entry.set(key, val); }
//      else {exit.set(key, val); }
//       }
      
//       typename MapTraits<NodeImpl>::ReturnValue 
//       operator[](const Node& key) {
//      if (key.entry) { return entry[key]; }
//      else { return exit[key]; }
//       }

//       typename MapTraits<NodeImpl>::ConstReturnValue
//       operator[](const Node& key) const {
//      if (key.entry) { return entry[key]; }
//      else { return exit[key]; }
//       }

//     private:
//       NodeImpl entry, exit;
//     };

//     template <typename T>
//     class EdgeMap : public MapBase<Edge, T> {
//       typedef typename Parent::template NodeMap<T> NodeImpl;
//       typedef typename Parent::template EdgeMap<T> EdgeImpl;
//     public:
//       EdgeMap(const SplitGraphAdaptorBase& _graph) 
//      : bind(_graph), orig(_graph) {}
//       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
//      : bind(_graph, t), orig(_graph, t) {}
      
//       void set(const Edge& key, const T& val) {
//      if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
//      else {bind.set(key.bind, val); }
//       }
      
//       typename MapTraits<EdgeImpl>::ReturnValue
//       operator[](const Edge& key) {
//      if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
//      else {return bind[key.bind]; }
//       }

//       typename MapTraits<EdgeImpl>::ConstReturnValue
//       operator[](const Edge& key) const {
//      if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
//      else {return bind[key.bind]; }
//       }

//     private:
//       typename Parent::template NodeMap<T> bind;
//       typename Parent::template EdgeMap<T> orig;
//     };

//     template <typename EntryMap, typename ExitMap>
//     class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
//     public:
//       typedef MapBase<Node, typename EntryMap::Value> Parent;

//       typedef typename Parent::Key Key;
//       typedef typename Parent::Value Value;

//       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
//      : entryMap(_entryMap), exitMap(_exitMap) {}

//       Value& operator[](const Key& key) {
//      if (key.entry) {
//        return entryMap[key];
//      } else {
//        return exitMap[key];
//      }
//       }

//       Value operator[](const Key& key) const {
//      if (key.entry) {
//        return entryMap[key];
//      } else {
//        return exitMap[key];
//      }
//       }

//       void set(const Key& key, const Value& value) {
//      if (key.entry) {
//        entryMap.set(key, value);
//      } else {
//        exitMap.set(key, value);
//      }
//       }
      
//     private:
      
//       EntryMap& entryMap;
//       ExitMap& exitMap;
      
//     };

//     template <typename EdgeMap, typename NodeMap>
//     class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
//     public:
//       typedef MapBase<Edge, typename EdgeMap::Value> Parent;

//       typedef typename Parent::Key Key;
//       typedef typename Parent::Value Value;

//       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
//      : edgeMap(_edgeMap), nodeMap(_nodeMap) {}

//       void set(const Edge& edge, const Value& val) {
//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
//        edgeMap.set(edge, val);
//      } else {
//        nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
//      }
//       }

//       Value operator[](const Key& edge) const {
//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
//        return edgeMap[edge];
//      } else {
//        return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
//      }
//       }      

//       Value& operator[](const Key& edge) {
//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
//        return edgeMap[edge];
//      } else {
//        return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
//      }
//       }      
      
//     private:
//       EdgeMap& edgeMap;
//       NodeMap& nodeMap;
//     };

//   };

//   template <typename _Graph>
//   class SplitGraphAdaptor 
//     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
//   public:
//     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;

//     SplitGraphAdaptor(_Graph& graph) {
//       Parent::setGraph(graph);
//     }


//   };

} //namespace lemon

#endif //LEMON_GRAPH_ADAPTOR_H