/* -*- 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/invalid.h>

#include <lemon/maps.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); }

    template <typename _Value>

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

    public:

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

      explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) 

	: Parent(*gw.graph) { }

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

	: Parent(*gw.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>& gw) 

	: Parent(*gw.graph) { }

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

	: Parent(*gw.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); }

  };

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

  };

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

  };

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

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

  };

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

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

  };

  /// \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> > SubGW;

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

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

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

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

  ///\endcode

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

  ///\code

  /// 1

  /// :-)

  /// 1

  ///\endcode

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

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

  /// 

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

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

  ///SubGW gw(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<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 

  ///  preflow(gw, 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;

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

    }

  };

  template <typename _Graph>

  class UndirectGraphAdaptorBase : 

    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {

  public:

    typedef _Graph Graph;

    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;

  protected:

    UndirectGraphAdaptorBase() : Parent() { }

  public:

    typedef typename Parent::UEdge UEdge;

    typedef typename Parent::Edge Edge;

    template <typename T>

    class EdgeMap {

    protected:

      const UndirectGraphAdaptorBase<_Graph>* g;

      template <typename TT> friend class EdgeMap;

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

    public:

      typedef T Value;

      typedef Edge Key;

      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g), 

	forward_map(*(g->graph)), backward_map(*(g->graph)) { }

      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 

	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }

      void set(Edge e, T a) { 

	if (g->direction(e)) 

	  forward_map.set(e, a); 

	else 

	  backward_map.set(e, a); 

      }

      T operator[](Edge e) const { 

	if (g->direction(e)) 

	  return forward_map[e]; 

	else 

	  return backward_map[e]; 

      }

    };

    template <typename T>

    class UEdgeMap {

      template <typename TT> friend class UEdgeMap;

      typename _Graph::template EdgeMap<T> map; 

    public:

      typedef T Value;

      typedef UEdge Key;

      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) : 

	map(*(g.graph)) { }

      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) : 

	map(*(g.graph), a) { }

      void set(UEdge e, T a) { 

	map.set(e, a); 

      }

      T operator[](UEdge e) const { 

	return map[e]; 

      }

    };

  };

  ///\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 UndirectGraphAdaptor : 

    public UGraphAdaptorExtender<

    UndirectGraphAdaptorBase<_Graph> > {

  public:

    typedef _Graph Graph;

    typedef UGraphAdaptorExtender<

      UndirectGraphAdaptorBase<_Graph> > Parent;

  protected:

    UndirectGraphAdaptor() { }

  public:

    UndirectGraphAdaptor(_Graph& _graph) { 

      setGraph(_graph);

    }

  };

  template <typename _Graph, 

	    typename ForwardFilterMap, typename BackwardFilterMap>

  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    ForwardFilterMap* forward_filter;

    BackwardFilterMap* backward_filter;

    SubBidirGraphAdaptorBase() : Parent(), 

				 forward_filter(0), backward_filter(0) { }

    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

      forward_filter=&_forward_filter;

    }

    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

      backward_filter=&_backward_filter;

    }

  public:

//     SubGraphAdaptorBase(Graph& _graph, 

// 			NodeFilterMap& _node_filter_map, 

// 			EdgeFilterMap& _edge_filter_map) : 

//       Parent(&_graph), 

//       node_filter_map(&node_filter_map), 

//       edge_filter_map(&edge_filter_map) { }

    typedef typename Parent::Node Node;

    typedef typename _Graph::Edge GraphEdge;

    template <typename T> class EdgeMap;

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

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

    // if and only if the 

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

    class Edge : public _Graph::Edge {

      friend class SubBidirGraphAdaptorBase<

	Graph, ForwardFilterMap, BackwardFilterMap>;

      template<typename T> friend class EdgeMap;

    protected:

      bool backward; //true, iff backward

    public:

      Edge() { }

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

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

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

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

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

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

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

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

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

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

      } 

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

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

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

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

      }

    };

    void first(Node& i) const { 

      Parent::first(i); 

    }

    void first(Edge& i) const { 

      Parent::first(i); 

      i.backward=false;

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

	     !(*forward_filter)[i]) Parent::next(i);

      if (*static_cast<GraphEdge*>(&i)==INVALID) {

	Parent::first(i); 

	i.backward=true;

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

	       !(*backward_filter)[i]) Parent::next(i);

      }

    }

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

      Parent::firstIn(i, n); 

      i.backward=false;

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

	     !(*forward_filter)[i]) Parent::nextIn(i);

      if (*static_cast<GraphEdge*>(&i)==INVALID) {

	Parent::firstOut(i, n); 

	i.backward=true;

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

	       !(*backward_filter)[i]) Parent::nextOut(i);

      }

    }

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

      Parent::firstOut(i, n); 

      i.backward=false;

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

	     !(*forward_filter)[i]) Parent::nextOut(i);

      if (*static_cast<GraphEdge*>(&i)==INVALID) {

	Parent::firstIn(i, n); 

	i.backward=true;

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

	       !(*backward_filter)[i]) Parent::nextIn(i);

      }

    }

    void next(Node& i) const { 

      Parent::next(i); 

    }

    void next(Edge& i) const { 

      if (!(i.backward)) {

	Parent::next(i);

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

	       !(*forward_filter)[i]) Parent::next(i);

	if (*static_cast<GraphEdge*>(&i)==INVALID) {

	  Parent::first(i); 

	  i.backward=true;

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

		 !(*backward_filter)[i]) Parent::next(i);

	}

      } else {

	Parent::next(i);

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

	       !(*backward_filter)[i]) Parent::next(i);

      }

    }

    void nextIn(Edge& i) const { 

      if (!(i.backward)) {

	Node n=Parent::target(i);

	Parent::nextIn(i);

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

	       !(*forward_filter)[i]) Parent::nextIn(i);

	if (*static_cast<GraphEdge*>(&i)==INVALID) {

	  Parent::firstOut(i, n); 

	  i.backward=true;

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

		 !(*backward_filter)[i]) Parent::nextOut(i);

	}

      } else {

	Parent::nextOut(i);

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

	       !(*backward_filter)[i]) Parent::nextOut(i);

      }

    }

    void nextOut(Edge& i) const { 

      if (!(i.backward)) {

	Node n=Parent::source(i);

	Parent::nextOut(i);

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

	       !(*forward_filter)[i]) Parent::nextOut(i);

	if (*static_cast<GraphEdge*>(&i)==INVALID) {

	  Parent::firstIn(i, n); 

	  i.backward=true;

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

		 !(*backward_filter)[i]) Parent::nextIn(i);

	}

      } else {

	Parent::nextIn(i);

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

	       !(*backward_filter)[i]) Parent::nextIn(i);

      }

    }

    Node source(Edge e) const { 

      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }

    Node target(Edge e) const { 

      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }

    /// Gives back the opposite edge.

    ///\e

    ///

    Edge opposite(const Edge& e) const { 

      Edge f=e;

      f.backward=!f.backward;

      return f;

    }

    ///\e

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

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

    /// \todo hmm

    int edgeNum() const { 

      int i=0;

      Edge e;

      for (first(e); e!=INVALID; next(e)) ++i;

      return i; 

    }

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

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

    ///\e

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

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

    /// one for the backward edges.

    template <typename T>

    class EdgeMap {

      template <typename TT> friend class EdgeMap;