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

#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 <iostream>

namespace lemon {

  ///\brief Base type for the Graph Adaptors

  ///\ingroup graph_adaptors

  ///

  ///Base type for the Graph Adaptors

  ///

  ///\warning Graph adaptors are in even

  ///more experimental state than the other

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

  ///

  ///This is the base type for most of LEMON graph 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 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); }

    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 GraphAdaptorBase<_Graph>& ga) 

	: Parent(*ga.graph) { }

      NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)

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

    };

    template <typename _Value>

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

    public:

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

      explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga) 

	: Parent(*ga.graph) { }

      EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)

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

    };

  };

  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

  ///

  ///\warning Graph adaptors are in even more experimental 

  ///state than the other

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

  ///

  /// 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 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 _Graph, typename NodeFilterMap, typename EdgeFilterMap>

  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 

    : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    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;

    }

  };

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

  /// \ingroup graph_adaptors

  /// 

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

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

  /// 

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

  ///

  ///\warning Graph adaptors are in even more experimental state

  ///than the other

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

  ///

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

  ///

  ///\warning Graph adaptors are in even more experimental state

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

  ///

  ///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 UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;

  protected:

    UndirGraphAdaptorBase() : Parent() {}

  public:

    typedef typename Parent::UEdge UEdge;

    typedef typename Parent::Edge Edge;

    template <typename _Value>

    class EdgeMap {

    private:

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

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef _Value Value;

      typedef Edge Key;

      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :

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

      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) 

        : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}

      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; 

    };

    template <typename _Value>

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

    public:

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

      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) 

        : Parent(*(g.graph)) {}

      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) 

        : Parent(*(g.graph), a) {}

    };

  };

  template <typename _Graph>

  class UndirGraphAdaptorBase<

    _Graph, typename enable_if<

    typename _Graph::EdgeNotifier::Notifier>::type > 

      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {

  public:

    typedef _Graph Graph;

    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: