lemon/adaptors.h
changeset 425 cace3206223b
parent 415 4b6112235fad
child 440 88ed40ad0d4f
child 446 d369e885d196
equal deleted inserted replaced
1:e9b3d914b40d 0:24393885e9fc
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #ifndef LEMON_DIGRAPH_ADAPTOR_H
    19 #ifndef LEMON_ADAPTORS_H
    20 #define LEMON_DIGRAPH_ADAPTOR_H
    20 #define LEMON_ADAPTORS_H
    21 
    21 
    22 ///\ingroup graph_adaptors
    22 /// \ingroup graph_adaptors
    23 ///\file
    23 /// \file
    24 ///\brief Several digraph adaptors.
    24 /// \brief Several graph adaptors
    25 ///
    25 ///
    26 ///This file contains several useful digraph adaptor classes.
    26 /// This file contains several useful adaptors for digraphs and graphs.
    27 
    27 
    28 #include <lemon/core.h>
    28 #include <lemon/core.h>
    29 #include <lemon/maps.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/bits/variant.h>
    30 #include <lemon/bits/variant.h>
    31 
    31 
    32 #include <lemon/bits/base_extender.h>
       
    33 #include <lemon/bits/graph_adaptor_extender.h>
    32 #include <lemon/bits/graph_adaptor_extender.h>
    34 #include <lemon/bits/graph_extender.h>
       
    35 #include <lemon/tolerance.h>
    33 #include <lemon/tolerance.h>
    36 
    34 
    37 #include <algorithm>
    35 #include <algorithm>
    38 
    36 
    39 namespace lemon {
    37 namespace lemon {
    53   public:
    51   public:
    54     DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
    52     DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
    55 
    53 
    56     typedef typename Digraph::Node Node;
    54     typedef typename Digraph::Node Node;
    57     typedef typename Digraph::Arc Arc;
    55     typedef typename Digraph::Arc Arc;
    58    
    56 
    59     void first(Node& i) const { _digraph->first(i); }
    57     void first(Node& i) const { _digraph->first(i); }
    60     void first(Arc& i) const { _digraph->first(i); }
    58     void first(Arc& i) const { _digraph->first(i); }
    61     void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
    59     void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
    62     void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
    60     void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
    63 
    61 
    69     Node source(const Arc& a) const { return _digraph->source(a); }
    67     Node source(const Arc& a) const { return _digraph->source(a); }
    70     Node target(const Arc& a) const { return _digraph->target(a); }
    68     Node target(const Arc& a) const { return _digraph->target(a); }
    71 
    69 
    72     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    73     int nodeNum() const { return _digraph->nodeNum(); }
    71     int nodeNum() const { return _digraph->nodeNum(); }
    74     
    72 
    75     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    73     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    76     int arcNum() const { return _digraph->arcNum(); }
    74     int arcNum() const { return _digraph->arcNum(); }
    77 
    75 
    78     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    76     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    79     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    77     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    80       return _digraph->findArc(u, v, prev);
    78       return _digraph->findArc(u, v, prev);
    81     }
    79     }
    82   
    80 
    83     Node addNode() { return _digraph->addNode(); }
    81     Node addNode() { return _digraph->addNode(); }
    84     Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    82     Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    85 
    83 
    86     void erase(const Node& n) const { _digraph->erase(n); }
    84     void erase(const Node& n) const { _digraph->erase(n); }
    87     void erase(const Arc& a) const { _digraph->erase(a); }
    85     void erase(const Arc& a) const { _digraph->erase(a); }
    88   
    86 
    89     void clear() const { _digraph->clear(); }
    87     void clear() const { _digraph->clear(); }
    90     
    88 
    91     int id(const Node& n) const { return _digraph->id(n); }
    89     int id(const Node& n) const { return _digraph->id(n); }
    92     int id(const Arc& a) const { return _digraph->id(a); }
    90     int id(const Arc& a) const { return _digraph->id(a); }
    93 
    91 
    94     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
    92     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
    95     Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
    93     Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
    96 
    94 
    97     int maxNodeId() const { return _digraph->maxNodeId(); }
    95     int maxNodeId() const { return _digraph->maxNodeId(); }
    98     int maxArcId() const { return _digraph->maxArcId(); }
    96     int maxArcId() const { return _digraph->maxArcId(); }
    99 
    97 
   100     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
    98     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
   101     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 
    99     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
   102 
   100 
   103     typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
   101     typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
   104     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 
   102     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
   105     
   103 
   106     template <typename _Value>
   104     template <typename _Value>
   107     class NodeMap : public Digraph::template NodeMap<_Value> {
   105     class NodeMap : public Digraph::template NodeMap<_Value> {
   108     public:
   106     public:
   109 
   107 
   110       typedef typename Digraph::template NodeMap<_Value> Parent;
   108       typedef typename Digraph::template NodeMap<_Value> Parent;
   111 
   109 
   112       explicit NodeMap(const Adaptor& adaptor) 
   110       explicit NodeMap(const Adaptor& adaptor)
   113 	: Parent(*adaptor._digraph) {}
   111         : Parent(*adaptor._digraph) {}
   114 
   112 
   115       NodeMap(const Adaptor& adaptor, const _Value& value)
   113       NodeMap(const Adaptor& adaptor, const _Value& value)
   116 	: Parent(*adaptor._digraph, value) { }
   114         : Parent(*adaptor._digraph, value) { }
   117 
   115 
   118     private:
   116     private:
   119       NodeMap& operator=(const NodeMap& cmap) {
   117       NodeMap& operator=(const NodeMap& cmap) {
   120         return operator=<NodeMap>(cmap);
   118         return operator=<NodeMap>(cmap);
   121       }
   119       }
   123       template <typename CMap>
   121       template <typename CMap>
   124       NodeMap& operator=(const CMap& cmap) {
   122       NodeMap& operator=(const CMap& cmap) {
   125         Parent::operator=(cmap);
   123         Parent::operator=(cmap);
   126         return *this;
   124         return *this;
   127       }
   125       }
   128       
   126 
   129     };
   127     };
   130 
   128 
   131     template <typename _Value>
   129     template <typename _Value>
   132     class ArcMap : public Digraph::template ArcMap<_Value> {
   130     class ArcMap : public Digraph::template ArcMap<_Value> {
   133     public:
   131     public:
   134       
   132 
   135       typedef typename Digraph::template ArcMap<_Value> Parent;
   133       typedef typename Digraph::template ArcMap<_Value> Parent;
   136       
   134 
   137       explicit ArcMap(const Adaptor& adaptor) 
   135       explicit ArcMap(const Adaptor& adaptor)
   138 	: Parent(*adaptor._digraph) {}
   136         : Parent(*adaptor._digraph) {}
   139 
   137 
   140       ArcMap(const Adaptor& adaptor, const _Value& value)
   138       ArcMap(const Adaptor& adaptor, const _Value& value)
   141 	: Parent(*adaptor._digraph, value) {}
   139         : Parent(*adaptor._digraph, value) {}
   142 
   140 
   143     private:
   141     private:
   144       ArcMap& operator=(const ArcMap& cmap) {
   142       ArcMap& operator=(const ArcMap& cmap) {
   145         return operator=<ArcMap>(cmap);
   143         return operator=<ArcMap>(cmap);
   146       }
   144       }
   153 
   151 
   154     };
   152     };
   155 
   153 
   156   };
   154   };
   157 
   155 
       
   156   template<typename _Graph>
       
   157   class GraphAdaptorBase {
       
   158   public:
       
   159     typedef _Graph Graph;
       
   160     typedef Graph ParentGraph;
       
   161 
       
   162   protected:
       
   163     Graph* _graph;
       
   164 
       
   165     GraphAdaptorBase() : _graph(0) {}
       
   166 
       
   167     void setGraph(Graph& graph) { _graph = &graph; }
       
   168 
       
   169   public:
       
   170     GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
       
   171 
       
   172     typedef typename Graph::Node Node;
       
   173     typedef typename Graph::Arc Arc;
       
   174     typedef typename Graph::Edge Edge;
       
   175 
       
   176     void first(Node& i) const { _graph->first(i); }
       
   177     void first(Arc& i) const { _graph->first(i); }
       
   178     void first(Edge& i) const { _graph->first(i); }
       
   179     void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
       
   180     void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
       
   181     void firstInc(Edge &i, bool &d, const Node &n) const {
       
   182       _graph->firstInc(i, d, n);
       
   183     }
       
   184 
       
   185     void next(Node& i) const { _graph->next(i); }
       
   186     void next(Arc& i) const { _graph->next(i); }
       
   187     void next(Edge& i) const { _graph->next(i); }
       
   188     void nextIn(Arc& i) const { _graph->nextIn(i); }
       
   189     void nextOut(Arc& i) const { _graph->nextOut(i); }
       
   190     void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
       
   191 
       
   192     Node u(const Edge& e) const { return _graph->u(e); }
       
   193     Node v(const Edge& e) const { return _graph->v(e); }
       
   194 
       
   195     Node source(const Arc& a) const { return _graph->source(a); }
       
   196     Node target(const Arc& a) const { return _graph->target(a); }
       
   197 
       
   198     typedef NodeNumTagIndicator<Graph> NodeNumTag;
       
   199     int nodeNum() const { return _graph->nodeNum(); }
       
   200 
       
   201     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
       
   202     int arcNum() const { return _graph->arcNum(); }
       
   203     int edgeNum() const { return _graph->edgeNum(); }
       
   204 
       
   205     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
       
   206     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
       
   207       return _graph->findArc(u, v, prev);
       
   208     }
       
   209     Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
       
   210       return _graph->findEdge(u, v, prev);
       
   211     }
       
   212 
       
   213     Node addNode() { return _graph->addNode(); }
       
   214     Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
       
   215 
       
   216     void erase(const Node& i) { _graph->erase(i); }
       
   217     void erase(const Edge& i) { _graph->erase(i); }
       
   218 
       
   219     void clear() { _graph->clear(); }
       
   220 
       
   221     bool direction(const Arc& a) const { return _graph->direction(a); }
       
   222     Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
       
   223 
       
   224     int id(const Node& v) const { return _graph->id(v); }
       
   225     int id(const Arc& a) const { return _graph->id(a); }
       
   226     int id(const Edge& e) const { return _graph->id(e); }
       
   227 
       
   228     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
       
   229     Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
       
   230     Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
       
   231 
       
   232     int maxNodeId() const { return _graph->maxNodeId(); }
       
   233     int maxArcId() const { return _graph->maxArcId(); }
       
   234     int maxEdgeId() const { return _graph->maxEdgeId(); }
       
   235 
       
   236     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
       
   237     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
       
   238 
       
   239     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
       
   240     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
       
   241 
       
   242     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
       
   243     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
       
   244 
       
   245     template <typename _Value>
       
   246     class NodeMap : public Graph::template NodeMap<_Value> {
       
   247     public:
       
   248       typedef typename Graph::template NodeMap<_Value> Parent;
       
   249       explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
       
   250         : Parent(*adapter._graph) {}
       
   251       NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
       
   252         : Parent(*adapter._graph, value) {}
       
   253 
       
   254     private:
       
   255       NodeMap& operator=(const NodeMap& cmap) {
       
   256         return operator=<NodeMap>(cmap);
       
   257       }
       
   258 
       
   259       template <typename CMap>
       
   260       NodeMap& operator=(const CMap& cmap) {
       
   261         Parent::operator=(cmap);
       
   262         return *this;
       
   263       }
       
   264 
       
   265     };
       
   266 
       
   267     template <typename _Value>
       
   268     class ArcMap : public Graph::template ArcMap<_Value> {
       
   269     public:
       
   270       typedef typename Graph::template ArcMap<_Value> Parent;
       
   271       explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
       
   272         : Parent(*adapter._graph) {}
       
   273       ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
       
   274         : Parent(*adapter._graph, value) {}
       
   275 
       
   276     private:
       
   277       ArcMap& operator=(const ArcMap& cmap) {
       
   278         return operator=<ArcMap>(cmap);
       
   279       }
       
   280 
       
   281       template <typename CMap>
       
   282       ArcMap& operator=(const CMap& cmap) {
       
   283         Parent::operator=(cmap);
       
   284         return *this;
       
   285       }
       
   286     };
       
   287 
       
   288     template <typename _Value>
       
   289     class EdgeMap : public Graph::template EdgeMap<_Value> {
       
   290     public:
       
   291       typedef typename Graph::template EdgeMap<_Value> Parent;
       
   292       explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
       
   293         : Parent(*adapter._graph) {}
       
   294       EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
       
   295         : Parent(*adapter._graph, value) {}
       
   296 
       
   297     private:
       
   298       EdgeMap& operator=(const EdgeMap& cmap) {
       
   299         return operator=<EdgeMap>(cmap);
       
   300       }
       
   301 
       
   302       template <typename CMap>
       
   303       EdgeMap& operator=(const CMap& cmap) {
       
   304         Parent::operator=(cmap);
       
   305         return *this;
       
   306       }
       
   307     };
       
   308 
       
   309   };
   158 
   310 
   159   template <typename _Digraph>
   311   template <typename _Digraph>
   160   class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
   312   class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
   161   public:
   313   public:
   162     typedef _Digraph Digraph;
   314     typedef _Digraph Digraph;
   163     typedef DigraphAdaptorBase<_Digraph> Parent;
   315     typedef DigraphAdaptorBase<_Digraph> Parent;
   164   protected:
   316   protected:
   165     RevDigraphAdaptorBase() : Parent() { }
   317     ReverseDigraphBase() : Parent() { }
   166   public:
   318   public:
   167     typedef typename Parent::Node Node;
   319     typedef typename Parent::Node Node;
   168     typedef typename Parent::Arc Arc;
   320     typedef typename Parent::Arc Arc;
   169 
   321 
   170     void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
   322     void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
   174     void nextOut(Arc& a) const { Parent::nextIn(a); }
   326     void nextOut(Arc& a) const { Parent::nextIn(a); }
   175 
   327 
   176     Node source(const Arc& a) const { return Parent::target(a); }
   328     Node source(const Arc& a) const { return Parent::target(a); }
   177     Node target(const Arc& a) const { return Parent::source(a); }
   329     Node target(const Arc& a) const { return Parent::source(a); }
   178 
   330 
       
   331     Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
       
   332 
   179     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   333     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   180     Arc findArc(const Node& u, const Node& v, 
   334     Arc findArc(const Node& u, const Node& v,
   181 		const Arc& prev = INVALID) {
   335                 const Arc& prev = INVALID) {
   182       return Parent::findArc(v, u, prev);
   336       return Parent::findArc(v, u, prev);
   183     }
   337     }
   184 
   338 
   185   };
   339   };
   186     
   340 
   187 
   341   /// \ingroup graph_adaptors
   188   ///\ingroup graph_adaptors
   342   ///
   189   ///
   343   /// \brief A digraph adaptor which reverses the orientation of the arcs.
   190   ///\brief A digraph adaptor which reverses the orientation of the arcs.
   344   ///
   191   ///
   345   /// ReverseDigraph reverses the arcs in the adapted digraph. The
   192   /// If \c g is defined as
   346   /// SubDigraph is conform to the \ref concepts::Digraph
   193   ///\code
   347   /// "Digraph concept".
   194   /// ListDigraph dg;
   348   ///
   195   ///\endcode
   349   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
   196   /// then
   350   /// "Digraph concept". The type can be specified to be const.
   197   ///\code
       
   198   /// RevDigraphAdaptor<ListDigraph> dga(dg);
       
   199   ///\endcode
       
   200   /// implements the digraph obtained from \c dg by 
       
   201   /// reversing the orientation of its arcs.
       
   202   ///
       
   203   /// A good example of using RevDigraphAdaptor is to decide whether
       
   204   /// the directed graph is strongly connected or not. The digraph is
       
   205   /// strongly connected iff each node is reachable from one node and
       
   206   /// this node is reachable from the others. Instead of this
       
   207   /// condition we use a slightly different, from one node each node
       
   208   /// is reachable both in the digraph and the reversed digraph. Now
       
   209   /// this condition can be checked with the Dfs algorithm and the
       
   210   /// RevDigraphAdaptor class.
       
   211   ///
       
   212   /// The implementation:
       
   213   ///\code
       
   214   /// bool stronglyConnected(const Digraph& digraph) {
       
   215   ///   if (NodeIt(digraph) == INVALID) return true;
       
   216   ///   Dfs<Digraph> dfs(digraph);
       
   217   ///   dfs.run(NodeIt(digraph));
       
   218   ///   for (NodeIt it(digraph); it != INVALID; ++it) {
       
   219   ///     if (!dfs.reached(it)) {
       
   220   ///       return false;
       
   221   ///     }
       
   222   ///   }
       
   223   ///   typedef RevDigraphAdaptor<const Digraph> RDigraph;
       
   224   ///   RDigraph rdigraph(digraph);
       
   225   ///   DfsVisit<RDigraph> rdfs(rdigraph);
       
   226   ///   rdfs.run(NodeIt(digraph));
       
   227   ///   for (NodeIt it(digraph); it != INVALID; ++it) {
       
   228   ///     if (!rdfs.reached(it)) {
       
   229   ///       return false;
       
   230   ///     }
       
   231   ///   }
       
   232   ///   return true;
       
   233   /// }
       
   234   ///\endcode
       
   235   template<typename _Digraph>
   351   template<typename _Digraph>
   236   class RevDigraphAdaptor : 
   352   class ReverseDigraph :
   237     public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
   353     public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
   238   public:
   354   public:
   239     typedef _Digraph Digraph;
   355     typedef _Digraph Digraph;
   240     typedef DigraphAdaptorExtender<
   356     typedef DigraphAdaptorExtender<
   241       RevDigraphAdaptorBase<_Digraph> > Parent;
   357       ReverseDigraphBase<_Digraph> > Parent;
   242   protected:
   358   protected:
   243     RevDigraphAdaptor() { }
   359     ReverseDigraph() { }
   244   public:
   360   public:
   245 
   361 
   246     /// \brief Constructor
   362     /// \brief Constructor
   247     ///
   363     ///
   248     /// Creates a reverse graph adaptor for the given digraph
   364     /// Creates a reverse digraph adaptor for the given digraph
   249     explicit RevDigraphAdaptor(Digraph& digraph) { 
   365     explicit ReverseDigraph(Digraph& digraph) {
   250       Parent::setDigraph(digraph); 
   366       Parent::setDigraph(digraph);
   251     }
   367     }
   252   };
   368   };
   253 
   369 
   254   /// \brief Just gives back a reverse digraph adaptor
   370   /// \brief Just gives back a reverse digraph adaptor
   255   ///
   371   ///
   256   /// Just gives back a reverse digraph adaptor
   372   /// Just gives back a reverse digraph adaptor
   257   template<typename Digraph>
   373   template<typename Digraph>
   258   RevDigraphAdaptor<const Digraph>
   374   ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
   259   revDigraphAdaptor(const Digraph& digraph) {
   375     return ReverseDigraph<const Digraph>(digraph);
   260     return RevDigraphAdaptor<const Digraph>(digraph);
       
   261   }
   376   }
   262 
   377 
   263   template <typename _Digraph, typename _NodeFilterMap, 
   378   template <typename _Digraph, typename _NodeFilterMap,
   264 	    typename _ArcFilterMap, bool checked = true>
   379             typename _ArcFilterMap, bool _checked = true>
   265   class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
   380   class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
   266   public:
   381   public:
   267     typedef _Digraph Digraph;
   382     typedef _Digraph Digraph;
   268     typedef _NodeFilterMap NodeFilterMap;
   383     typedef _NodeFilterMap NodeFilterMap;
   269     typedef _ArcFilterMap ArcFilterMap;
   384     typedef _ArcFilterMap ArcFilterMap;
   270 
   385 
   271     typedef SubDigraphAdaptorBase Adaptor;
   386     typedef SubDigraphBase Adaptor;
   272     typedef DigraphAdaptorBase<_Digraph> Parent;
   387     typedef DigraphAdaptorBase<_Digraph> Parent;
   273   protected:
   388   protected:
   274     NodeFilterMap* _node_filter;
   389     NodeFilterMap* _node_filter;
   275     ArcFilterMap* _arc_filter;
   390     ArcFilterMap* _arc_filter;
   276     SubDigraphAdaptorBase() 
   391     SubDigraphBase()
   277       : Parent(), _node_filter(0), _arc_filter(0) { }
   392       : Parent(), _node_filter(0), _arc_filter(0) { }
   278 
   393 
   279     void setNodeFilterMap(NodeFilterMap& node_filter) {
   394     void setNodeFilterMap(NodeFilterMap& node_filter) {
   280       _node_filter = &node_filter;
   395       _node_filter = &node_filter;
   281     }
   396     }
   286   public:
   401   public:
   287 
   402 
   288     typedef typename Parent::Node Node;
   403     typedef typename Parent::Node Node;
   289     typedef typename Parent::Arc Arc;
   404     typedef typename Parent::Arc Arc;
   290 
   405 
   291     void first(Node& i) const { 
   406     void first(Node& i) const {
   292       Parent::first(i); 
   407       Parent::first(i);
   293       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 
   408       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
   294     }
   409     }
   295 
   410 
   296     void first(Arc& i) const { 
   411     void first(Arc& i) const {
   297       Parent::first(i); 
   412       Parent::first(i);
   298       while (i != INVALID && (!(*_arc_filter)[i] 
   413       while (i != INVALID && (!(*_arc_filter)[i]
   299 	     || !(*_node_filter)[Parent::source(i)]
   414                               || !(*_node_filter)[Parent::source(i)]
   300 	     || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 
   415                               || !(*_node_filter)[Parent::target(i)]))
   301     }
   416         Parent::next(i);
   302 
   417     }
   303     void firstIn(Arc& i, const Node& n) const { 
   418 
   304       Parent::firstIn(i, n); 
   419     void firstIn(Arc& i, const Node& n) const {
   305       while (i != INVALID && (!(*_arc_filter)[i] 
   420       Parent::firstIn(i, n);
   306 	     || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 
   421       while (i != INVALID && (!(*_arc_filter)[i]
   307     }
   422                               || !(*_node_filter)[Parent::source(i)]))
   308 
   423         Parent::nextIn(i);
   309     void firstOut(Arc& i, const Node& n) const { 
   424     }
   310       Parent::firstOut(i, n); 
   425 
   311       while (i != INVALID && (!(*_arc_filter)[i] 
   426     void firstOut(Arc& i, const Node& n) const {
   312 	     || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 
   427       Parent::firstOut(i, n);
   313     }
   428       while (i != INVALID && (!(*_arc_filter)[i]
   314 
   429                               || !(*_node_filter)[Parent::target(i)]))
   315     void next(Node& i) const { 
   430         Parent::nextOut(i);
   316       Parent::next(i); 
   431     }
   317       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 
   432 
   318     }
   433     void next(Node& i) const {
   319 
   434       Parent::next(i);
   320     void next(Arc& i) const { 
   435       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
   321       Parent::next(i); 
   436     }
   322       while (i != INVALID && (!(*_arc_filter)[i] 
   437 
   323 	     || !(*_node_filter)[Parent::source(i)]
   438     void next(Arc& i) const {
   324 	     || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 
   439       Parent::next(i);
   325     }
   440       while (i != INVALID && (!(*_arc_filter)[i]
   326 
   441                               || !(*_node_filter)[Parent::source(i)]
   327     void nextIn(Arc& i) const { 
   442                               || !(*_node_filter)[Parent::target(i)]))
   328       Parent::nextIn(i); 
   443         Parent::next(i);
   329       while (i != INVALID && (!(*_arc_filter)[i] 
   444     }
   330 	     || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 
   445 
   331     }
   446     void nextIn(Arc& i) const {
   332 
   447       Parent::nextIn(i);
   333     void nextOut(Arc& i) const { 
   448       while (i != INVALID && (!(*_arc_filter)[i]
   334       Parent::nextOut(i); 
   449                               || !(*_node_filter)[Parent::source(i)]))
   335       while (i != INVALID && (!(*_arc_filter)[i] 
   450         Parent::nextIn(i);
   336 	     || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 
   451     }
       
   452 
       
   453     void nextOut(Arc& i) const {
       
   454       Parent::nextOut(i);
       
   455       while (i != INVALID && (!(*_arc_filter)[i]
       
   456                               || !(*_node_filter)[Parent::target(i)]))
       
   457         Parent::nextOut(i);
   337     }
   458     }
   338 
   459 
   339     void hide(const Node& n) const { _node_filter->set(n, false); }
   460     void hide(const Node& n) const { _node_filter->set(n, false); }
   340     void hide(const Arc& a) const { _arc_filter->set(a, false); }
   461     void hide(const Arc& a) const { _arc_filter->set(a, false); }
   341 
   462 
   347 
   468 
   348     typedef False NodeNumTag;
   469     typedef False NodeNumTag;
   349     typedef False EdgeNumTag;
   470     typedef False EdgeNumTag;
   350 
   471 
   351     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   472     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   352     Arc findArc(const Node& source, const Node& target, 
   473     Arc findArc(const Node& source, const Node& target,
   353 		const Arc& prev = INVALID) {
   474                 const Arc& prev = INVALID) {
   354       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   475       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   355         return INVALID;
   476         return INVALID;
   356       }
   477       }
   357       Arc arc = Parent::findArc(source, target, prev);
   478       Arc arc = Parent::findArc(source, target, prev);
   358       while (arc != INVALID && !(*_arc_filter)[arc]) {
   479       while (arc != INVALID && !(*_arc_filter)[arc]) {
   360       }
   481       }
   361       return arc;
   482       return arc;
   362     }
   483     }
   363 
   484 
   364     template <typename _Value>
   485     template <typename _Value>
   365     class NodeMap : public SubMapExtender<Adaptor, 
   486     class NodeMap : public SubMapExtender<Adaptor,
   366         typename Parent::template NodeMap<_Value> > {
   487       typename Parent::template NodeMap<_Value> > {
   367     public:
   488     public:
   368       typedef _Value Value;
   489       typedef _Value Value;
   369       typedef SubMapExtender<Adaptor, typename Parent::
   490       typedef SubMapExtender<Adaptor, typename Parent::
   370                              template NodeMap<Value> > MapParent;
   491                              template NodeMap<Value> > MapParent;
   371     
   492 
   372       NodeMap(const Adaptor& adaptor) 
   493       NodeMap(const Adaptor& adaptor)
   373 	: MapParent(adaptor) {}
   494         : MapParent(adaptor) {}
   374       NodeMap(const Adaptor& adaptor, const Value& value) 
   495       NodeMap(const Adaptor& adaptor, const Value& value)
   375 	: MapParent(adaptor, value) {}
   496         : MapParent(adaptor, value) {}
   376     
   497 
   377     private:
   498     private:
   378       NodeMap& operator=(const NodeMap& cmap) {
   499       NodeMap& operator=(const NodeMap& cmap) {
   379 	return operator=<NodeMap>(cmap);
   500         return operator=<NodeMap>(cmap);
   380       }
   501       }
   381     
   502 
   382       template <typename CMap>
   503       template <typename CMap>
   383       NodeMap& operator=(const CMap& cmap) {
   504       NodeMap& operator=(const CMap& cmap) {
   384         MapParent::operator=(cmap);
   505         MapParent::operator=(cmap);
   385 	return *this;
   506         return *this;
   386       }
   507       }
   387     };
   508     };
   388 
   509 
   389     template <typename _Value>
   510     template <typename _Value>
   390     class ArcMap : public SubMapExtender<Adaptor, 
   511     class ArcMap : public SubMapExtender<Adaptor,
   391 	typename Parent::template ArcMap<_Value> > {
   512       typename Parent::template ArcMap<_Value> > {
   392     public:
   513     public:
   393       typedef _Value Value;
   514       typedef _Value Value;
   394       typedef SubMapExtender<Adaptor, typename Parent::
   515       typedef SubMapExtender<Adaptor, typename Parent::
   395                              template ArcMap<Value> > MapParent;
   516                              template ArcMap<Value> > MapParent;
   396     
   517 
   397       ArcMap(const Adaptor& adaptor) 
   518       ArcMap(const Adaptor& adaptor)
   398 	: MapParent(adaptor) {}
   519         : MapParent(adaptor) {}
   399       ArcMap(const Adaptor& adaptor, const Value& value) 
   520       ArcMap(const Adaptor& adaptor, const Value& value)
   400 	: MapParent(adaptor, value) {}
   521         : MapParent(adaptor, value) {}
   401     
   522 
   402     private:
   523     private:
   403       ArcMap& operator=(const ArcMap& cmap) {
   524       ArcMap& operator=(const ArcMap& cmap) {
   404 	return operator=<ArcMap>(cmap);
   525         return operator=<ArcMap>(cmap);
   405       }
   526       }
   406     
   527 
   407       template <typename CMap>
   528       template <typename CMap>
   408       ArcMap& operator=(const CMap& cmap) {
   529       ArcMap& operator=(const CMap& cmap) {
   409         MapParent::operator=(cmap);
   530         MapParent::operator=(cmap);
   410 	return *this;
   531         return *this;
   411       }
   532       }
   412     };
   533     };
   413 
   534 
   414   };
   535   };
   415 
   536 
   416   template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
   537   template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
   417   class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 
   538   class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
   418     : public DigraphAdaptorBase<_Digraph> {
   539     : public DigraphAdaptorBase<_Digraph> {
   419   public:
   540   public:
   420     typedef _Digraph Digraph;
   541     typedef _Digraph Digraph;
   421     typedef _NodeFilterMap NodeFilterMap;
   542     typedef _NodeFilterMap NodeFilterMap;
   422     typedef _ArcFilterMap ArcFilterMap;
   543     typedef _ArcFilterMap ArcFilterMap;
   423 
   544 
   424     typedef SubDigraphAdaptorBase Adaptor;
   545     typedef SubDigraphBase Adaptor;
   425     typedef DigraphAdaptorBase<Digraph> Parent;
   546     typedef DigraphAdaptorBase<Digraph> Parent;
   426   protected:
   547   protected:
   427     NodeFilterMap* _node_filter;
   548     NodeFilterMap* _node_filter;
   428     ArcFilterMap* _arc_filter;
   549     ArcFilterMap* _arc_filter;
   429     SubDigraphAdaptorBase() 
   550     SubDigraphBase()
   430       : Parent(), _node_filter(0), _arc_filter(0) { }
   551       : Parent(), _node_filter(0), _arc_filter(0) { }
   431 
   552 
   432     void setNodeFilterMap(NodeFilterMap& node_filter) {
   553     void setNodeFilterMap(NodeFilterMap& node_filter) {
   433       _node_filter = &node_filter;
   554       _node_filter = &node_filter;
   434     }
   555     }
   439   public:
   560   public:
   440 
   561 
   441     typedef typename Parent::Node Node;
   562     typedef typename Parent::Node Node;
   442     typedef typename Parent::Arc Arc;
   563     typedef typename Parent::Arc Arc;
   443 
   564 
   444     void first(Node& i) const { 
   565     void first(Node& i) const {
   445       Parent::first(i); 
   566       Parent::first(i);
   446       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 
   567       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
   447     }
   568     }
   448 
   569 
   449     void first(Arc& i) const { 
   570     void first(Arc& i) const {
   450       Parent::first(i); 
   571       Parent::first(i);
   451       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 
   572       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
   452     }
   573     }
   453 
   574 
   454     void firstIn(Arc& i, const Node& n) const { 
   575     void firstIn(Arc& i, const Node& n) const {
   455       Parent::firstIn(i, n); 
   576       Parent::firstIn(i, n);
   456       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 
   577       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
   457     }
   578     }
   458 
   579 
   459     void firstOut(Arc& i, const Node& n) const { 
   580     void firstOut(Arc& i, const Node& n) const {
   460       Parent::firstOut(i, n); 
   581       Parent::firstOut(i, n);
   461       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 
   582       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
   462     }
   583     }
   463 
   584 
   464     void next(Node& i) const { 
   585     void next(Node& i) const {
   465       Parent::next(i); 
   586       Parent::next(i);
   466       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 
   587       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
   467     }
   588     }
   468     void next(Arc& i) const { 
   589     void next(Arc& i) const {
   469       Parent::next(i); 
   590       Parent::next(i);
   470       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 
   591       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
   471     }
   592     }
   472     void nextIn(Arc& i) const { 
   593     void nextIn(Arc& i) const {
   473       Parent::nextIn(i); 
   594       Parent::nextIn(i);
   474       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 
   595       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
   475     }
   596     }
   476 
   597 
   477     void nextOut(Arc& i) const { 
   598     void nextOut(Arc& i) const {
   478       Parent::nextOut(i); 
   599       Parent::nextOut(i);
   479       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 
   600       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
   480     }
   601     }
   481 
   602 
   482     void hide(const Node& n) const { _node_filter->set(n, false); }
   603     void hide(const Node& n) const { _node_filter->set(n, false); }
   483     void hide(const Arc& e) const { _arc_filter->set(e, false); }
   604     void hide(const Arc& e) const { _arc_filter->set(e, false); }
   484 
   605 
   490 
   611 
   491     typedef False NodeNumTag;
   612     typedef False NodeNumTag;
   492     typedef False EdgeNumTag;
   613     typedef False EdgeNumTag;
   493 
   614 
   494     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   615     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   495     Arc findArc(const Node& source, const Node& target, 
   616     Arc findArc(const Node& source, const Node& target,
   496 		  const Arc& prev = INVALID) {
   617                 const Arc& prev = INVALID) {
   497       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   618       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   498         return INVALID;
   619         return INVALID;
   499       }
   620       }
   500       Arc arc = Parent::findArc(source, target, prev);
   621       Arc arc = Parent::findArc(source, target, prev);
   501       while (arc != INVALID && !(*_arc_filter)[arc]) {
   622       while (arc != INVALID && !(*_arc_filter)[arc]) {
   503       }
   624       }
   504       return arc;
   625       return arc;
   505     }
   626     }
   506 
   627 
   507     template <typename _Value>
   628     template <typename _Value>
   508     class NodeMap : public SubMapExtender<Adaptor, 
   629     class NodeMap : public SubMapExtender<Adaptor,
   509         typename Parent::template NodeMap<_Value> > {
   630       typename Parent::template NodeMap<_Value> > {
   510     public:
   631     public:
   511       typedef _Value Value;
   632       typedef _Value Value;
   512       typedef SubMapExtender<Adaptor, typename Parent::
   633       typedef SubMapExtender<Adaptor, typename Parent::
   513                              template NodeMap<Value> > MapParent;
   634                              template NodeMap<Value> > MapParent;
   514     
   635 
   515       NodeMap(const Adaptor& adaptor) 
   636       NodeMap(const Adaptor& adaptor)
   516 	: MapParent(adaptor) {}
   637         : MapParent(adaptor) {}
   517       NodeMap(const Adaptor& adaptor, const Value& value) 
   638       NodeMap(const Adaptor& adaptor, const Value& value)
   518 	: MapParent(adaptor, value) {}
   639         : MapParent(adaptor, value) {}
   519     
   640 
   520     private:
   641     private:
   521       NodeMap& operator=(const NodeMap& cmap) {
   642       NodeMap& operator=(const NodeMap& cmap) {
   522 	return operator=<NodeMap>(cmap);
   643         return operator=<NodeMap>(cmap);
   523       }
   644       }
   524     
   645 
   525       template <typename CMap>
   646       template <typename CMap>
   526       NodeMap& operator=(const CMap& cmap) {
   647       NodeMap& operator=(const CMap& cmap) {
   527         MapParent::operator=(cmap);
   648         MapParent::operator=(cmap);
   528 	return *this;
   649         return *this;
   529       }
   650       }
   530     };
   651     };
   531 
   652 
   532     template <typename _Value>
   653     template <typename _Value>
   533     class ArcMap : public SubMapExtender<Adaptor, 
   654     class ArcMap : public SubMapExtender<Adaptor,
   534 	typename Parent::template ArcMap<_Value> > {
   655       typename Parent::template ArcMap<_Value> > {
   535     public:
   656     public:
   536       typedef _Value Value;
   657       typedef _Value Value;
   537       typedef SubMapExtender<Adaptor, typename Parent::
   658       typedef SubMapExtender<Adaptor, typename Parent::
   538                              template ArcMap<Value> > MapParent;
   659                              template ArcMap<Value> > MapParent;
   539     
   660 
   540       ArcMap(const Adaptor& adaptor) 
   661       ArcMap(const Adaptor& adaptor)
   541 	: MapParent(adaptor) {}
   662         : MapParent(adaptor) {}
   542       ArcMap(const Adaptor& adaptor, const Value& value) 
   663       ArcMap(const Adaptor& adaptor, const Value& value)
   543 	: MapParent(adaptor, value) {}
   664         : MapParent(adaptor, value) {}
   544     
   665 
   545     private:
   666     private:
   546       ArcMap& operator=(const ArcMap& cmap) {
   667       ArcMap& operator=(const ArcMap& cmap) {
   547 	return operator=<ArcMap>(cmap);
   668         return operator=<ArcMap>(cmap);
   548       }
   669       }
   549     
   670 
   550       template <typename CMap>
   671       template <typename CMap>
   551       ArcMap& operator=(const CMap& cmap) {
   672       ArcMap& operator=(const CMap& cmap) {
   552         MapParent::operator=(cmap);
   673         MapParent::operator=(cmap);
   553 	return *this;
   674         return *this;
   554       }
   675       }
   555     };
   676     };
   556 
   677 
   557   };
   678   };
   558 
   679 
   559   /// \ingroup graph_adaptors
   680   /// \ingroup graph_adaptors
   560   ///
   681   ///
   561   /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
   682   /// \brief An adaptor for hiding nodes and arcs in a digraph
   562   /// 
   683   ///
   563   /// SubDigraphAdaptor shows the digraph with filtered node-set and 
   684   /// SubDigraph hides nodes and arcs in a digraph. A bool node map
   564   /// arc-set. If the \c checked parameter is true then it filters the arc-set
   685   /// and a bool arc map must be specified, which define the filters
   565   /// respect to the source and target.
   686   /// for nodes and arcs. Just the nodes and arcs with true value are
   566   /// 
   687   /// shown in the subdigraph. The SubDigraph is conform to the \ref
   567   /// If the \c checked template parameter is false then the
   688   /// concepts::Digraph "Digraph concept". If the \c _checked parameter
   568   /// node-iterator cares only the filter on the node-set, and the
   689   /// is true, then the arcs incident to filtered nodes are also
   569   /// arc-iterator cares only the filter on the arc-set.  Therefore
   690   /// filtered out.
   570   /// the arc-map have to filter all arcs which's source or target is
   691   ///
   571   /// filtered by the node-filter.
   692   /// \tparam _Digraph It must be conform to the \ref
   572   ///\code
   693   /// concepts::Digraph "Digraph concept". The type can be specified
   573   /// typedef ListDigraph Digraph;
   694   /// to const.
   574   /// DIGRAPH_TYPEDEFS(Digraph);
   695   /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
   575   /// Digraph g;
   696   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
   576   /// Node u=g.addNode(); //node of id 0
   697   /// \tparam _checked If the parameter is false then the arc filtering
   577   /// Node v=g.addNode(); //node of id 1
   698   /// is not checked with respect to node filter. Otherwise, each arc
   578   /// Arc a=g.addArc(u, v); //arc of id 0
   699   /// is automatically filtered, which is incident to a filtered node.
   579   /// Arc f=g.addArc(v, u); //arc of id 1
   700   ///
   580   /// BoolNodeMap nm(g, true);
   701   /// \see FilterNodes
   581   /// nm.set(u, false);
   702   /// \see FilterArcs
   582   /// BoolArcMap am(g, true);
   703   template<typename _Digraph,
   583   /// am.set(a, false);
   704            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
   584   /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
   705            typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
   585   /// SubDGA ga(g, nm, am);
   706            bool _checked = true>
   586   /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
   707   class SubDigraph
   587   ///   std::cout << g.id(n) << std::endl;
   708     : public DigraphAdaptorExtender<
   588   /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a) 
   709       SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
   589   ///   std::cout << g.id(a) << std::endl;
       
   590   ///\endcode
       
   591   /// The output of the above code is the following.
       
   592   ///\code
       
   593   /// 1
       
   594   /// 1
       
   595   ///\endcode
       
   596   /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to
       
   597   /// \c Digraph::Node that is why \c g.id(n) can be applied.
       
   598   /// 
       
   599   /// For other examples see also the documentation of
       
   600   /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
       
   601   template<typename _Digraph, 
       
   602 	   typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 
       
   603 	   typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 
       
   604 	   bool checked = true>
       
   605   class SubDigraphAdaptor : 
       
   606     public DigraphAdaptorExtender<
       
   607     SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
       
   608   public:
   710   public:
   609     typedef _Digraph Digraph;
   711     typedef _Digraph Digraph;
   610     typedef _NodeFilterMap NodeFilterMap;
   712     typedef _NodeFilterMap NodeFilterMap;
   611     typedef _ArcFilterMap ArcFilterMap;
   713     typedef _ArcFilterMap ArcFilterMap;
   612 
   714 
   613     typedef DigraphAdaptorExtender<
   715     typedef DigraphAdaptorExtender<
   614       SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
   716       SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
   615     Parent;
   717     Parent;
   616 
   718 
   617     typedef typename Parent::Node Node;
   719     typedef typename Parent::Node Node;
   618     typedef typename Parent::Arc Arc;
   720     typedef typename Parent::Arc Arc;
   619 
   721 
   620   protected:
   722   protected:
   621     SubDigraphAdaptor() { }
   723     SubDigraph() { }
   622   public:
   724   public:
   623 
   725 
   624     /// \brief Constructor
   726     /// \brief Constructor
   625     ///
   727     ///
   626     /// Creates a sub-digraph-adaptor for the given digraph with
   728     /// Creates a subdigraph for the given digraph with
   627     /// given node and arc map filters.
   729     /// given node and arc map filters.
   628     SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter, 
   730     SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
   629 		      ArcFilterMap& arc_filter) { 
   731                ArcFilterMap& arc_filter) {
   630       setDigraph(digraph);
   732       setDigraph(digraph);
   631       setNodeFilterMap(node_filter);
   733       setNodeFilterMap(node_filter);
   632       setArcFilterMap(arc_filter);
   734       setArcFilterMap(arc_filter);
   633     }
   735     }
   634 
   736 
   635     /// \brief Hides the node of the graph
   737     /// \brief Hides the node of the graph
   636     ///
   738     ///
   637     /// This function hides \c n in the digraph, i.e. the iteration 
   739     /// This function hides \c n in the digraph, i.e. the iteration
   638     /// jumps over it. This is done by simply setting the value of \c n  
   740     /// jumps over it. This is done by simply setting the value of \c n
   639     /// to be false in the corresponding node-map.
   741     /// to be false in the corresponding node-map.
   640     void hide(const Node& n) const { Parent::hide(n); }
   742     void hide(const Node& n) const { Parent::hide(n); }
   641 
   743 
   642     /// \brief Hides the arc of the graph
   744     /// \brief Hides the arc of the graph
   643     ///
   745     ///
   644     /// This function hides \c a in the digraph, i.e. the iteration 
   746     /// This function hides \c a in the digraph, i.e. the iteration
   645     /// jumps over it. This is done by simply setting the value of \c a
   747     /// jumps over it. This is done by simply setting the value of \c a
   646     /// to be false in the corresponding arc-map.
   748     /// to be false in the corresponding arc-map.
   647     void hide(const Arc& a) const { Parent::hide(a); }
   749     void hide(const Arc& a) const { Parent::hide(a); }
   648 
   750 
   649     /// \brief Unhides the node of the graph
   751     /// \brief Unhides the node of the graph
   650     ///
   752     ///
   651     /// The value of \c n is set to be true in the node-map which stores 
   753     /// The value of \c n is set to be true in the node-map which stores
   652     /// hide information. If \c n was hidden previuosly, then it is shown 
   754     /// hide information. If \c n was hidden previuosly, then it is shown
   653     /// again
   755     /// again
   654     void unHide(const Node& n) const { Parent::unHide(n); }
   756     void unHide(const Node& n) const { Parent::unHide(n); }
   655 
   757 
   656     /// \brief Unhides the arc of the graph
   758     /// \brief Unhides the arc of the graph
   657     ///
   759     ///
   658     /// The value of \c a is set to be true in the arc-map which stores 
   760     /// The value of \c a is set to be true in the arc-map which stores
   659     /// hide information. If \c a was hidden previuosly, then it is shown 
   761     /// hide information. If \c a was hidden previuosly, then it is shown
   660     /// again
   762     /// again
   661     void unHide(const Arc& a) const { Parent::unHide(a); }
   763     void unHide(const Arc& a) const { Parent::unHide(a); }
   662 
   764 
   663     /// \brief Returns true if \c n is hidden.
   765     /// \brief Returns true if \c n is hidden.
   664     ///
   766     ///
   672     ///
   774     ///
   673     bool hidden(const Arc& a) const { return Parent::hidden(a); }
   775     bool hidden(const Arc& a) const { return Parent::hidden(a); }
   674 
   776 
   675   };
   777   };
   676 
   778 
   677   /// \brief Just gives back a sub-digraph-adaptor
   779   /// \brief Just gives back a subdigraph
   678   ///
   780   ///
   679   /// Just gives back a sub-digraph-adaptor
   781   /// Just gives back a subdigraph
   680   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   782   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   681   SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
   783   SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   682   subDigraphAdaptor(const Digraph& digraph, 
   784   subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
   683 		    NodeFilterMap& nfm, ArcFilterMap& afm) {
   785     return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   684     return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
       
   685       (digraph, nfm, afm);
   786       (digraph, nfm, afm);
   686   }
   787   }
   687 
   788 
   688   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   789   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   689   SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
   790   SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   690   subDigraphAdaptor(const Digraph& digraph, 
   791   subDigraph(const Digraph& digraph,
   691                    NodeFilterMap& nfm, ArcFilterMap& afm) {
   792              const NodeFilterMap& nfm, ArcFilterMap& afm) {
   692     return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
   793     return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   693       (digraph, nfm, afm);
   794       (digraph, nfm, afm);
   694   }
   795   }
   695 
   796 
   696   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   797   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   697   SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
   798   SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   698   subDigraphAdaptor(const Digraph& digraph, 
   799   subDigraph(const Digraph& digraph,
   699                    NodeFilterMap& nfm, ArcFilterMap& afm) {
   800              NodeFilterMap& nfm, const ArcFilterMap& afm) {
   700     return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
   801     return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   701       (digraph, nfm, afm);
   802       (digraph, nfm, afm);
   702   }
   803   }
   703 
   804 
   704   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   805   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   705   SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
   806   SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
   706   subDigraphAdaptor(const Digraph& digraph, 
   807   subDigraph(const Digraph& digraph,
   707                    NodeFilterMap& nfm, ArcFilterMap& afm) {
   808              const NodeFilterMap& nfm, const ArcFilterMap& afm) {
   708     return SubDigraphAdaptor<const Digraph, const NodeFilterMap, 
   809     return SubDigraph<const Digraph, const NodeFilterMap,
   709       const ArcFilterMap>(digraph, nfm, afm);
   810       const ArcFilterMap>(digraph, nfm, afm);
   710 
       
   711   }
   811   }
   712 
   812 
   713 
   813 
   714 
   814   template <typename _Graph, typename NodeFilterMap,
   715   ///\ingroup graph_adaptors
   815             typename EdgeFilterMap, bool _checked = true>
   716   ///
   816   class SubGraphBase : public GraphAdaptorBase<_Graph> {
   717   ///\brief An adaptor for hiding nodes from a digraph.
   817   public:
   718   ///
   818     typedef _Graph Graph;
   719   ///An adaptor for hiding nodes from a digraph.  This adaptor
   819     typedef SubGraphBase Adaptor;
   720   ///specializes SubDigraphAdaptor in the way that only the node-set
   820     typedef GraphAdaptorBase<_Graph> Parent;
   721   ///can be filtered. In usual case the checked parameter is true, we
   821   protected:
   722   ///get the induced subgraph. But if the checked parameter is false
   822 
   723   ///then we can filter only isolated nodes.
   823     NodeFilterMap* _node_filter_map;
   724   template<typename _Digraph, 
   824     EdgeFilterMap* _edge_filter_map;
   725 	   typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 
   825 
   726 	   bool checked = true>
   826     SubGraphBase()
   727   class NodeSubDigraphAdaptor : 
   827       : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
   728     public SubDigraphAdaptor<_Digraph, _NodeFilterMap, 
   828 
   729 			     ConstMap<typename _Digraph::Arc, bool>, checked> {
   829     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
       
   830       _node_filter_map=&node_filter_map;
       
   831     }
       
   832     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
       
   833       _edge_filter_map=&edge_filter_map;
       
   834     }
       
   835 
       
   836   public:
       
   837 
       
   838     typedef typename Parent::Node Node;
       
   839     typedef typename Parent::Arc Arc;
       
   840     typedef typename Parent::Edge Edge;
       
   841 
       
   842     void first(Node& i) const {
       
   843       Parent::first(i);
       
   844       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
       
   845     }
       
   846 
       
   847     void first(Arc& i) const {
       
   848       Parent::first(i);
       
   849       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   850                             || !(*_node_filter_map)[Parent::source(i)]
       
   851                             || !(*_node_filter_map)[Parent::target(i)]))
       
   852         Parent::next(i);
       
   853     }
       
   854 
       
   855     void first(Edge& i) const {
       
   856       Parent::first(i);
       
   857       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   858                             || !(*_node_filter_map)[Parent::u(i)]
       
   859                             || !(*_node_filter_map)[Parent::v(i)]))
       
   860         Parent::next(i);
       
   861     }
       
   862 
       
   863     void firstIn(Arc& i, const Node& n) const {
       
   864       Parent::firstIn(i, n);
       
   865       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   866                             || !(*_node_filter_map)[Parent::source(i)]))
       
   867         Parent::nextIn(i);
       
   868     }
       
   869 
       
   870     void firstOut(Arc& i, const Node& n) const {
       
   871       Parent::firstOut(i, n);
       
   872       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   873                             || !(*_node_filter_map)[Parent::target(i)]))
       
   874         Parent::nextOut(i);
       
   875     }
       
   876 
       
   877     void firstInc(Edge& i, bool& d, const Node& n) const {
       
   878       Parent::firstInc(i, d, n);
       
   879       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   880                             || !(*_node_filter_map)[Parent::u(i)]
       
   881                             || !(*_node_filter_map)[Parent::v(i)]))
       
   882         Parent::nextInc(i, d);
       
   883     }
       
   884 
       
   885     void next(Node& i) const {
       
   886       Parent::next(i);
       
   887       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
       
   888     }
       
   889 
       
   890     void next(Arc& i) const {
       
   891       Parent::next(i);
       
   892       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   893                             || !(*_node_filter_map)[Parent::source(i)]
       
   894                             || !(*_node_filter_map)[Parent::target(i)]))
       
   895         Parent::next(i);
       
   896     }
       
   897 
       
   898     void next(Edge& i) const {
       
   899       Parent::next(i);
       
   900       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   901                             || !(*_node_filter_map)[Parent::u(i)]
       
   902                             || !(*_node_filter_map)[Parent::v(i)]))
       
   903         Parent::next(i);
       
   904     }
       
   905 
       
   906     void nextIn(Arc& i) const {
       
   907       Parent::nextIn(i);
       
   908       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   909                             || !(*_node_filter_map)[Parent::source(i)]))
       
   910         Parent::nextIn(i);
       
   911     }
       
   912 
       
   913     void nextOut(Arc& i) const {
       
   914       Parent::nextOut(i);
       
   915       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   916                             || !(*_node_filter_map)[Parent::target(i)]))
       
   917         Parent::nextOut(i);
       
   918     }
       
   919 
       
   920     void nextInc(Edge& i, bool& d) const {
       
   921       Parent::nextInc(i, d);
       
   922       while (i!=INVALID && (!(*_edge_filter_map)[i]
       
   923                             || !(*_node_filter_map)[Parent::u(i)]
       
   924                             || !(*_node_filter_map)[Parent::v(i)]))
       
   925         Parent::nextInc(i, d);
       
   926     }
       
   927 
       
   928     void hide(const Node& n) const { _node_filter_map->set(n, false); }
       
   929     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
       
   930 
       
   931     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
       
   932     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
       
   933 
       
   934     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
       
   935     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
       
   936 
       
   937     typedef False NodeNumTag;
       
   938     typedef False EdgeNumTag;
       
   939 
       
   940     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
       
   941     Arc findArc(const Node& u, const Node& v,
       
   942                 const Arc& prev = INVALID) {
       
   943       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
       
   944         return INVALID;
       
   945       }
       
   946       Arc arc = Parent::findArc(u, v, prev);
       
   947       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
       
   948         arc = Parent::findArc(u, v, arc);
       
   949       }
       
   950       return arc;
       
   951     }
       
   952     Edge findEdge(const Node& u, const Node& v,
       
   953                   const Edge& prev = INVALID) {
       
   954       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
       
   955         return INVALID;
       
   956       }
       
   957       Edge edge = Parent::findEdge(u, v, prev);
       
   958       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
       
   959         edge = Parent::findEdge(u, v, edge);
       
   960       }
       
   961       return edge;
       
   962     }
       
   963 
       
   964     template <typename _Value>
       
   965     class NodeMap : public SubMapExtender<Adaptor,
       
   966       typename Parent::template NodeMap<_Value> > {
       
   967     public:
       
   968       typedef _Value Value;
       
   969       typedef SubMapExtender<Adaptor, typename Parent::
       
   970                              template NodeMap<Value> > MapParent;
       
   971 
       
   972       NodeMap(const Adaptor& adaptor)
       
   973         : MapParent(adaptor) {}
       
   974       NodeMap(const Adaptor& adaptor, const Value& value)
       
   975         : MapParent(adaptor, value) {}
       
   976 
       
   977     private:
       
   978       NodeMap& operator=(const NodeMap& cmap) {
       
   979         return operator=<NodeMap>(cmap);
       
   980       }
       
   981 
       
   982       template <typename CMap>
       
   983       NodeMap& operator=(const CMap& cmap) {
       
   984         MapParent::operator=(cmap);
       
   985         return *this;
       
   986       }
       
   987     };
       
   988 
       
   989     template <typename _Value>
       
   990     class ArcMap : public SubMapExtender<Adaptor,
       
   991       typename Parent::template ArcMap<_Value> > {
       
   992     public:
       
   993       typedef _Value Value;
       
   994       typedef SubMapExtender<Adaptor, typename Parent::
       
   995                              template ArcMap<Value> > MapParent;
       
   996 
       
   997       ArcMap(const Adaptor& adaptor)
       
   998         : MapParent(adaptor) {}
       
   999       ArcMap(const Adaptor& adaptor, const Value& value)
       
  1000         : MapParent(adaptor, value) {}
       
  1001 
       
  1002     private:
       
  1003       ArcMap& operator=(const ArcMap& cmap) {
       
  1004         return operator=<ArcMap>(cmap);
       
  1005       }
       
  1006 
       
  1007       template <typename CMap>
       
  1008       ArcMap& operator=(const CMap& cmap) {
       
  1009         MapParent::operator=(cmap);
       
  1010         return *this;
       
  1011       }
       
  1012     };
       
  1013 
       
  1014     template <typename _Value>
       
  1015     class EdgeMap : public SubMapExtender<Adaptor,
       
  1016       typename Parent::template EdgeMap<_Value> > {
       
  1017     public:
       
  1018       typedef _Value Value;
       
  1019       typedef SubMapExtender<Adaptor, typename Parent::
       
  1020                              template EdgeMap<Value> > MapParent;
       
  1021 
       
  1022       EdgeMap(const Adaptor& adaptor)
       
  1023         : MapParent(adaptor) {}
       
  1024 
       
  1025       EdgeMap(const Adaptor& adaptor, const Value& value)
       
  1026         : MapParent(adaptor, value) {}
       
  1027 
       
  1028     private:
       
  1029       EdgeMap& operator=(const EdgeMap& cmap) {
       
  1030         return operator=<EdgeMap>(cmap);
       
  1031       }
       
  1032 
       
  1033       template <typename CMap>
       
  1034       EdgeMap& operator=(const CMap& cmap) {
       
  1035         MapParent::operator=(cmap);
       
  1036         return *this;
       
  1037       }
       
  1038     };
       
  1039 
       
  1040   };
       
  1041 
       
  1042   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
       
  1043   class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
       
  1044     : public GraphAdaptorBase<_Graph> {
       
  1045   public:
       
  1046     typedef _Graph Graph;
       
  1047     typedef SubGraphBase Adaptor;
       
  1048     typedef GraphAdaptorBase<_Graph> Parent;
       
  1049   protected:
       
  1050     NodeFilterMap* _node_filter_map;
       
  1051     EdgeFilterMap* _edge_filter_map;
       
  1052     SubGraphBase() : Parent(),
       
  1053                      _node_filter_map(0), _edge_filter_map(0) { }
       
  1054 
       
  1055     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
       
  1056       _node_filter_map=&node_filter_map;
       
  1057     }
       
  1058     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
       
  1059       _edge_filter_map=&edge_filter_map;
       
  1060     }
       
  1061 
       
  1062   public:
       
  1063 
       
  1064     typedef typename Parent::Node Node;
       
  1065     typedef typename Parent::Arc Arc;
       
  1066     typedef typename Parent::Edge Edge;
       
  1067 
       
  1068     void first(Node& i) const {
       
  1069       Parent::first(i);
       
  1070       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
       
  1071     }
       
  1072 
       
  1073     void first(Arc& i) const {
       
  1074       Parent::first(i);
       
  1075       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
       
  1076     }
       
  1077 
       
  1078     void first(Edge& i) const {
       
  1079       Parent::first(i);
       
  1080       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
       
  1081     }
       
  1082 
       
  1083     void firstIn(Arc& i, const Node& n) const {
       
  1084       Parent::firstIn(i, n);
       
  1085       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
       
  1086     }
       
  1087 
       
  1088     void firstOut(Arc& i, const Node& n) const {
       
  1089       Parent::firstOut(i, n);
       
  1090       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
       
  1091     }
       
  1092 
       
  1093     void firstInc(Edge& i, bool& d, const Node& n) const {
       
  1094       Parent::firstInc(i, d, n);
       
  1095       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
       
  1096     }
       
  1097 
       
  1098     void next(Node& i) const {
       
  1099       Parent::next(i);
       
  1100       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
       
  1101     }
       
  1102     void next(Arc& i) const {
       
  1103       Parent::next(i);
       
  1104       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
       
  1105     }
       
  1106     void next(Edge& i) const {
       
  1107       Parent::next(i);
       
  1108       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
       
  1109     }
       
  1110     void nextIn(Arc& i) const {
       
  1111       Parent::nextIn(i);
       
  1112       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
       
  1113     }
       
  1114 
       
  1115     void nextOut(Arc& i) const {
       
  1116       Parent::nextOut(i);
       
  1117       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
       
  1118     }
       
  1119     void nextInc(Edge& i, bool& d) const {
       
  1120       Parent::nextInc(i, d);
       
  1121       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
       
  1122     }
       
  1123 
       
  1124     void hide(const Node& n) const { _node_filter_map->set(n, false); }
       
  1125     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
       
  1126 
       
  1127     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
       
  1128     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
       
  1129 
       
  1130     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
       
  1131     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
       
  1132 
       
  1133     typedef False NodeNumTag;
       
  1134     typedef False EdgeNumTag;
       
  1135 
       
  1136     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
       
  1137     Arc findArc(const Node& u, const Node& v,
       
  1138                 const Arc& prev = INVALID) {
       
  1139       Arc arc = Parent::findArc(u, v, prev);
       
  1140       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
       
  1141         arc = Parent::findArc(u, v, arc);
       
  1142       }
       
  1143       return arc;
       
  1144     }
       
  1145     Edge findEdge(const Node& u, const Node& v,
       
  1146                   const Edge& prev = INVALID) {
       
  1147       Edge edge = Parent::findEdge(u, v, prev);
       
  1148       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
       
  1149         edge = Parent::findEdge(u, v, edge);
       
  1150       }
       
  1151       return edge;
       
  1152     }
       
  1153 
       
  1154     template <typename _Value>
       
  1155     class NodeMap : public SubMapExtender<Adaptor,
       
  1156       typename Parent::template NodeMap<_Value> > {
       
  1157     public:
       
  1158       typedef _Value Value;
       
  1159       typedef SubMapExtender<Adaptor, typename Parent::
       
  1160                              template NodeMap<Value> > MapParent;
       
  1161 
       
  1162       NodeMap(const Adaptor& adaptor)
       
  1163         : MapParent(adaptor) {}
       
  1164       NodeMap(const Adaptor& adaptor, const Value& value)
       
  1165         : MapParent(adaptor, value) {}
       
  1166 
       
  1167     private:
       
  1168       NodeMap& operator=(const NodeMap& cmap) {
       
  1169         return operator=<NodeMap>(cmap);
       
  1170       }
       
  1171 
       
  1172       template <typename CMap>
       
  1173       NodeMap& operator=(const CMap& cmap) {
       
  1174         MapParent::operator=(cmap);
       
  1175         return *this;
       
  1176       }
       
  1177     };
       
  1178 
       
  1179     template <typename _Value>
       
  1180     class ArcMap : public SubMapExtender<Adaptor,
       
  1181       typename Parent::template ArcMap<_Value> > {
       
  1182     public:
       
  1183       typedef _Value Value;
       
  1184       typedef SubMapExtender<Adaptor, typename Parent::
       
  1185                              template ArcMap<Value> > MapParent;
       
  1186 
       
  1187       ArcMap(const Adaptor& adaptor)
       
  1188         : MapParent(adaptor) {}
       
  1189       ArcMap(const Adaptor& adaptor, const Value& value)
       
  1190         : MapParent(adaptor, value) {}
       
  1191 
       
  1192     private:
       
  1193       ArcMap& operator=(const ArcMap& cmap) {
       
  1194         return operator=<ArcMap>(cmap);
       
  1195       }
       
  1196 
       
  1197       template <typename CMap>
       
  1198       ArcMap& operator=(const CMap& cmap) {
       
  1199         MapParent::operator=(cmap);
       
  1200         return *this;
       
  1201       }
       
  1202     };
       
  1203 
       
  1204     template <typename _Value>
       
  1205     class EdgeMap : public SubMapExtender<Adaptor,
       
  1206       typename Parent::template EdgeMap<_Value> > {
       
  1207     public:
       
  1208       typedef _Value Value;
       
  1209       typedef SubMapExtender<Adaptor, typename Parent::
       
  1210                              template EdgeMap<Value> > MapParent;
       
  1211 
       
  1212       EdgeMap(const Adaptor& adaptor)
       
  1213         : MapParent(adaptor) {}
       
  1214 
       
  1215       EdgeMap(const Adaptor& adaptor, const _Value& value)
       
  1216         : MapParent(adaptor, value) {}
       
  1217 
       
  1218     private:
       
  1219       EdgeMap& operator=(const EdgeMap& cmap) {
       
  1220         return operator=<EdgeMap>(cmap);
       
  1221       }
       
  1222 
       
  1223       template <typename CMap>
       
  1224       EdgeMap& operator=(const CMap& cmap) {
       
  1225         MapParent::operator=(cmap);
       
  1226         return *this;
       
  1227       }
       
  1228     };
       
  1229 
       
  1230   };
       
  1231 
       
  1232   /// \ingroup graph_adaptors
       
  1233   ///
       
  1234   /// \brief A graph adaptor for hiding nodes and edges in an
       
  1235   /// undirected graph.
       
  1236   ///
       
  1237   /// SubGraph hides nodes and edges in a graph. A bool node map and a
       
  1238   /// bool edge map must be specified, which define the filters for
       
  1239   /// nodes and edges. Just the nodes and edges with true value are
       
  1240   /// shown in the subgraph. The SubGraph is conform to the \ref
       
  1241   /// concepts::Graph "Graph concept". If the \c _checked parameter is
       
  1242   /// true, then the edges incident to filtered nodes are also
       
  1243   /// filtered out.
       
  1244   ///
       
  1245   /// \tparam _Graph It must be conform to the \ref
       
  1246   /// concepts::Graph "Graph concept". The type can be specified
       
  1247   /// to const.
       
  1248   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
       
  1249   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
       
  1250   /// \tparam _checked If the parameter is false then the edge filtering
       
  1251   /// is not checked with respect to node filter. Otherwise, each edge
       
  1252   /// is automatically filtered, which is incident to a filtered node.
       
  1253   ///
       
  1254   /// \see FilterNodes
       
  1255   /// \see FilterEdges
       
  1256   template<typename _Graph, typename NodeFilterMap,
       
  1257            typename EdgeFilterMap, bool _checked = true>
       
  1258   class SubGraph
       
  1259     : public GraphAdaptorExtender<
       
  1260       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
       
  1261   public:
       
  1262     typedef _Graph Graph;
       
  1263     typedef GraphAdaptorExtender<
       
  1264       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
       
  1265 
       
  1266     typedef typename Parent::Node Node;
       
  1267     typedef typename Parent::Edge Edge;
       
  1268 
       
  1269   protected:
       
  1270     SubGraph() { }
       
  1271   public:
       
  1272 
       
  1273     /// \brief Constructor
       
  1274     ///
       
  1275     /// Creates a subgraph for the given graph with given node and
       
  1276     /// edge map filters.
       
  1277     SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
       
  1278              EdgeFilterMap& edge_filter_map) {
       
  1279       setGraph(_graph);
       
  1280       setNodeFilterMap(node_filter_map);
       
  1281       setEdgeFilterMap(edge_filter_map);
       
  1282     }
       
  1283 
       
  1284     /// \brief Hides the node of the graph
       
  1285     ///
       
  1286     /// This function hides \c n in the graph, i.e. the iteration
       
  1287     /// jumps over it. This is done by simply setting the value of \c n
       
  1288     /// to be false in the corresponding node-map.
       
  1289     void hide(const Node& n) const { Parent::hide(n); }
       
  1290 
       
  1291     /// \brief Hides the edge of the graph
       
  1292     ///
       
  1293     /// This function hides \c e in the graph, i.e. the iteration
       
  1294     /// jumps over it. This is done by simply setting the value of \c e
       
  1295     /// to be false in the corresponding edge-map.
       
  1296     void hide(const Edge& e) const { Parent::hide(e); }
       
  1297 
       
  1298     /// \brief Unhides the node of the graph
       
  1299     ///
       
  1300     /// The value of \c n is set to be true in the node-map which stores
       
  1301     /// hide information. If \c n was hidden previuosly, then it is shown
       
  1302     /// again
       
  1303     void unHide(const Node& n) const { Parent::unHide(n); }
       
  1304 
       
  1305     /// \brief Unhides the edge of the graph
       
  1306     ///
       
  1307     /// The value of \c e is set to be true in the edge-map which stores
       
  1308     /// hide information. If \c e was hidden previuosly, then it is shown
       
  1309     /// again
       
  1310     void unHide(const Edge& e) const { Parent::unHide(e); }
       
  1311 
       
  1312     /// \brief Returns true if \c n is hidden.
       
  1313     ///
       
  1314     /// Returns true if \c n is hidden.
       
  1315     ///
       
  1316     bool hidden(const Node& n) const { return Parent::hidden(n); }
       
  1317 
       
  1318     /// \brief Returns true if \c e is hidden.
       
  1319     ///
       
  1320     /// Returns true if \c e is hidden.
       
  1321     ///
       
  1322     bool hidden(const Edge& e) const { return Parent::hidden(e); }
       
  1323   };
       
  1324 
       
  1325   /// \brief Just gives back a subgraph
       
  1326   ///
       
  1327   /// Just gives back a subgraph
       
  1328   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
       
  1329   SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
       
  1330   subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
       
  1331     return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
       
  1332   }
       
  1333 
       
  1334   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
       
  1335   SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
       
  1336   subGraph(const Graph& graph,
       
  1337            const NodeFilterMap& nfm, ArcFilterMap& efm) {
       
  1338     return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
       
  1339       (graph, nfm, efm);
       
  1340   }
       
  1341 
       
  1342   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
       
  1343   SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
       
  1344   subGraph(const Graph& graph,
       
  1345            NodeFilterMap& nfm, const ArcFilterMap& efm) {
       
  1346     return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
       
  1347       (graph, nfm, efm);
       
  1348   }
       
  1349 
       
  1350   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
       
  1351   SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
       
  1352   subGraph(const Graph& graph,
       
  1353            const NodeFilterMap& nfm, const ArcFilterMap& efm) {
       
  1354     return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
       
  1355       (graph, nfm, efm);
       
  1356   }
       
  1357 
       
  1358   /// \ingroup graph_adaptors
       
  1359   ///
       
  1360   /// \brief An adaptor for hiding nodes from a digraph or a graph.
       
  1361   ///
       
  1362   /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
       
  1363   /// node map must be specified, which defines the filters for
       
  1364   /// nodes. Just the unfiltered nodes and the arcs or edges incident
       
  1365   /// to unfiltered nodes are shown in the subdigraph or subgraph. The
       
  1366   /// FilterNodes is conform to the \ref concepts::Digraph
       
  1367   /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
       
  1368   /// on the \c _Digraph template parameter. If the \c _checked
       
  1369   /// parameter is true, then the arc or edges incident to filtered nodes
       
  1370   /// are also filtered out.
       
  1371   ///
       
  1372   /// \tparam _Digraph It must be conform to the \ref
       
  1373   /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
       
  1374   /// "Graph concept". The type can be specified to be const.
       
  1375   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
       
  1376   /// \tparam _checked If the parameter is false then the arc or edge
       
  1377   /// filtering is not checked with respect to node filter. In this
       
  1378   /// case just isolated nodes can be filtered out from the
       
  1379   /// graph.
       
  1380 #ifdef DOXYGEN
       
  1381   template<typename _Digraph,
       
  1382            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
       
  1383            bool _checked = true>
       
  1384 #else
       
  1385   template<typename _Digraph,
       
  1386            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
       
  1387            bool _checked = true,
       
  1388            typename Enable = void>
       
  1389 #endif
       
  1390   class FilterNodes
       
  1391     : public SubDigraph<_Digraph, _NodeFilterMap,
       
  1392                         ConstMap<typename _Digraph::Arc, bool>, _checked> {
   730   public:
  1393   public:
   731 
  1394 
   732     typedef _Digraph Digraph;
  1395     typedef _Digraph Digraph;
   733     typedef _NodeFilterMap NodeFilterMap;
  1396     typedef _NodeFilterMap NodeFilterMap;
   734 
  1397 
   735     typedef SubDigraphAdaptor<Digraph, NodeFilterMap, 
  1398     typedef SubDigraph<Digraph, NodeFilterMap,
   736 			      ConstMap<typename Digraph::Arc, bool>, checked> 
  1399                        ConstMap<typename Digraph::Arc, bool>, _checked>
   737     Parent;
  1400     Parent;
   738 
  1401 
   739     typedef typename Parent::Node Node;
  1402     typedef typename Parent::Node Node;
   740 
  1403 
   741   protected:
  1404   protected:
   742     ConstMap<typename Digraph::Arc, bool> const_true_map;
  1405     ConstMap<typename Digraph::Arc, bool> const_true_map;
   743 
  1406 
   744     NodeSubDigraphAdaptor() : const_true_map(true) {
  1407     FilterNodes() : const_true_map(true) {
   745       Parent::setArcFilterMap(const_true_map);
  1408       Parent::setArcFilterMap(const_true_map);
   746     }
  1409     }
   747 
  1410 
   748   public:
  1411   public:
   749 
  1412 
   750     /// \brief Constructor
  1413     /// \brief Constructor
   751     ///
  1414     ///
   752     /// Creates a node-sub-digraph-adaptor for the given digraph with
  1415     /// Creates an adaptor for the given digraph or graph with
   753     /// given node map filter.
  1416     /// given node filter map.
   754     NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) : 
  1417     FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
   755       Parent(), const_true_map(true) { 
  1418       Parent(), const_true_map(true) {
   756       Parent::setDigraph(_digraph);
  1419       Parent::setDigraph(_digraph);
   757       Parent::setNodeFilterMap(node_filter);
  1420       Parent::setNodeFilterMap(node_filter);
   758       Parent::setArcFilterMap(const_true_map);
  1421       Parent::setArcFilterMap(const_true_map);
   759     }
  1422     }
   760 
  1423 
   761     /// \brief Hides the node of the graph
  1424     /// \brief Hides the node of the graph
   762     ///
  1425     ///
   763     /// This function hides \c n in the digraph, i.e. the iteration 
  1426     /// This function hides \c n in the digraph or graph, i.e. the iteration
   764     /// jumps over it. This is done by simply setting the value of \c n  
  1427     /// jumps over it. This is done by simply setting the value of \c n
   765     /// to be false in the corresponding node-map.
  1428     /// to be false in the corresponding node map.
   766     void hide(const Node& n) const { Parent::hide(n); }
  1429     void hide(const Node& n) const { Parent::hide(n); }
   767 
  1430 
   768     /// \brief Unhides the node of the graph
  1431     /// \brief Unhides the node of the graph
   769     ///
  1432     ///
   770     /// The value of \c n is set to be true in the node-map which stores 
  1433     /// The value of \c n is set to be true in the node-map which stores
   771     /// hide information. If \c n was hidden previuosly, then it is shown 
  1434     /// hide information. If \c n was hidden previuosly, then it is shown
   772     /// again
  1435     /// again
   773     void unHide(const Node& n) const { Parent::unHide(n); }
  1436     void unHide(const Node& n) const { Parent::unHide(n); }
   774 
  1437 
   775     /// \brief Returns true if \c n is hidden.
  1438     /// \brief Returns true if \c n is hidden.
   776     ///
  1439     ///
   778     ///
  1441     ///
   779     bool hidden(const Node& n) const { return Parent::hidden(n); }
  1442     bool hidden(const Node& n) const { return Parent::hidden(n); }
   780 
  1443 
   781   };
  1444   };
   782 
  1445 
   783 
  1446   template<typename _Graph, typename _NodeFilterMap, bool _checked>
   784   /// \brief Just gives back a  node-sub-digraph adaptor
  1447   class FilterNodes<_Graph, _NodeFilterMap, _checked,
   785   ///
  1448                     typename enable_if<UndirectedTagIndicator<_Graph> >::type>
   786   /// Just gives back a node-sub-digraph adaptor
  1449     : public SubGraph<_Graph, _NodeFilterMap,
       
  1450                       ConstMap<typename _Graph::Edge, bool>, _checked> {
       
  1451   public:
       
  1452     typedef _Graph Graph;
       
  1453     typedef _NodeFilterMap NodeFilterMap;
       
  1454     typedef SubGraph<Graph, NodeFilterMap,
       
  1455                      ConstMap<typename Graph::Edge, bool> > Parent;
       
  1456 
       
  1457     typedef typename Parent::Node Node;
       
  1458   protected:
       
  1459     ConstMap<typename Graph::Edge, bool> const_true_map;
       
  1460 
       
  1461     FilterNodes() : const_true_map(true) {
       
  1462       Parent::setEdgeFilterMap(const_true_map);
       
  1463     }
       
  1464 
       
  1465   public:
       
  1466 
       
  1467     FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
       
  1468       Parent(), const_true_map(true) {
       
  1469       Parent::setGraph(_graph);
       
  1470       Parent::setNodeFilterMap(node_filter_map);
       
  1471       Parent::setEdgeFilterMap(const_true_map);
       
  1472     }
       
  1473 
       
  1474     void hide(const Node& n) const { Parent::hide(n); }
       
  1475     void unHide(const Node& n) const { Parent::unHide(n); }
       
  1476     bool hidden(const Node& n) const { return Parent::hidden(n); }
       
  1477 
       
  1478   };
       
  1479 
       
  1480 
       
  1481   /// \brief Just gives back a FilterNodes adaptor
       
  1482   ///
       
  1483   /// Just gives back a FilterNodes adaptor
   787   template<typename Digraph, typename NodeFilterMap>
  1484   template<typename Digraph, typename NodeFilterMap>
   788   NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
  1485   FilterNodes<const Digraph, NodeFilterMap>
   789   nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
  1486   filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
   790     return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
  1487     return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
   791   }
  1488   }
   792 
  1489 
   793   template<typename Digraph, typename NodeFilterMap>
  1490   template<typename Digraph, typename NodeFilterMap>
   794   NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
  1491   FilterNodes<const Digraph, const NodeFilterMap>
   795   nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
  1492   filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
   796     return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
  1493     return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
   797       (digraph, nfm);
       
   798   }
  1494   }
   799 
  1495 
   800   ///\ingroup graph_adaptors
  1496   /// \ingroup graph_adaptors
   801   ///
  1497   ///
   802   ///\brief An adaptor for hiding arcs from a digraph.
  1498   /// \brief An adaptor for hiding arcs from a digraph.
   803   ///
  1499   ///
   804   ///An adaptor for hiding arcs from a digraph. This adaptor
  1500   /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
   805   ///specializes SubDigraphAdaptor in the way that only the arc-set
  1501   /// be specified, which defines the filters for arcs. Just the
   806   ///can be filtered. The usefulness of this adaptor is demonstrated
  1502   /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
   807   ///in the problem of searching a maximum number of arc-disjoint
  1503   /// conform to the \ref concepts::Digraph "Digraph concept".
   808   ///shortest paths between two nodes \c s and \c t. Shortest here
  1504   ///
   809   ///means being shortest with respect to non-negative
  1505   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
   810   ///arc-lengths. Note that the comprehension of the presented
  1506   /// "Digraph concept". The type can be specified to be const.
   811   ///solution need's some elementary knowledge from combinatorial
  1507   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
   812   ///optimization.
  1508   /// graph.
   813   ///
       
   814   ///If a single shortest path is to be searched between \c s and \c
       
   815   ///t, then this can be done easily by applying the Dijkstra
       
   816   ///algorithm. What happens, if a maximum number of arc-disjoint
       
   817   ///shortest paths is to be computed. It can be proved that an arc
       
   818   ///can be in a shortest path if and only if it is tight with respect
       
   819   ///to the potential function computed by Dijkstra.  Moreover, any
       
   820   ///path containing only such arcs is a shortest one.  Thus we have
       
   821   ///to compute a maximum number of arc-disjoint paths between \c s
       
   822   ///and \c t in the digraph which has arc-set all the tight arcs. The
       
   823   ///computation will be demonstrated on the following digraph, which
       
   824   ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
       
   825   ///The full source code is available in \ref
       
   826   ///sub_digraph_adaptor_demo.cc.  If you are interested in more demo
       
   827   ///programs, you can use \ref dim_to_dot.cc to generate .dot files
       
   828   ///from dimacs files.  The .dot file of the following figure was
       
   829   ///generated by the demo program \ref dim_to_dot.cc.
       
   830   ///
       
   831   ///\dot
       
   832   ///digraph lemon_dot_example {
       
   833   ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
       
   834   ///n0 [ label="0 (s)" ];
       
   835   ///n1 [ label="1" ];
       
   836   ///n2 [ label="2" ];
       
   837   ///n3 [ label="3" ];
       
   838   ///n4 [ label="4" ];
       
   839   ///n5 [ label="5" ];
       
   840   ///n6 [ label="6 (t)" ];
       
   841   ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
       
   842   ///n5 ->  n6 [ label="9, length:4" ];
       
   843   ///n4 ->  n6 [ label="8, length:2" ];
       
   844   ///n3 ->  n5 [ label="7, length:1" ];
       
   845   ///n2 ->  n5 [ label="6, length:3" ];
       
   846   ///n2 ->  n6 [ label="5, length:5" ];
       
   847   ///n2 ->  n4 [ label="4, length:2" ];
       
   848   ///n1 ->  n4 [ label="3, length:3" ];
       
   849   ///n0 ->  n3 [ label="2, length:1" ];
       
   850   ///n0 ->  n2 [ label="1, length:2" ];
       
   851   ///n0 ->  n1 [ label="0, length:3" ];
       
   852   ///}
       
   853   ///\enddot
       
   854   ///
       
   855   ///\code
       
   856   ///Digraph g;
       
   857   ///Node s, t;
       
   858   ///LengthMap length(g);
       
   859   ///
       
   860   ///readDimacs(std::cin, g, length, s, t);
       
   861   ///
       
   862   ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
       
   863   ///for(ArcIt e(g); e!=INVALID; ++e) 
       
   864   ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
       
   865   ///       << length[e] << "->" << g.id(g.target(e)) << endl;
       
   866   ///
       
   867   ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
       
   868   ///\endcode
       
   869   ///Next, the potential function is computed with Dijkstra.
       
   870   ///\code
       
   871   ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
       
   872   ///Dijkstra dijkstra(g, length);
       
   873   ///dijkstra.run(s);
       
   874   ///\endcode
       
   875   ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
       
   876   ///\code
       
   877   ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap> 
       
   878   ///  TightArcFilter;
       
   879   ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
       
   880   ///
       
   881   ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
       
   882   ///SubGA ga(g, tight_arc_filter);
       
   883   ///\endcode
       
   884   ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed 
       
   885   ///with a max flow algorithm Preflow.
       
   886   ///\code
       
   887   ///ConstMap<Arc, int> const_1_map(1);
       
   888   ///Digraph::ArcMap<int> flow(g, 0);
       
   889   ///
       
   890   ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> > 
       
   891   ///  preflow(ga, const_1_map, s, t);
       
   892   ///preflow.run();
       
   893   ///\endcode
       
   894   ///Last, the output is:
       
   895   ///\code  
       
   896   ///cout << "maximum number of arc-disjoint shortest path: " 
       
   897   ///     << preflow.flowValue() << endl;
       
   898   ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: " 
       
   899   ///     << endl;
       
   900   ///for(ArcIt e(g); e!=INVALID; ++e) 
       
   901   ///  if (preflow.flow(e))
       
   902   ///    cout << " " << g.id(g.source(e)) << "--"
       
   903   ///         << length[e] << "->" << g.id(g.target(e)) << endl;
       
   904   ///\endcode
       
   905   ///The program has the following (expected :-)) output:
       
   906   ///\code
       
   907   ///arcs with lengths (of form id, source--length->target):
       
   908   /// 9, 5--4->6
       
   909   /// 8, 4--2->6
       
   910   /// 7, 3--1->5
       
   911   /// 6, 2--3->5
       
   912   /// 5, 2--5->6
       
   913   /// 4, 2--2->4
       
   914   /// 3, 1--3->4
       
   915   /// 2, 0--1->3
       
   916   /// 1, 0--2->2
       
   917   /// 0, 0--3->1
       
   918   ///s: 0 t: 6
       
   919   ///maximum number of arc-disjoint shortest path: 2
       
   920   ///arcs of the maximum number of arc-disjoint shortest s-t paths:
       
   921   /// 9, 5--4->6
       
   922   /// 8, 4--2->6
       
   923   /// 7, 3--1->5
       
   924   /// 4, 2--2->4
       
   925   /// 2, 0--1->3
       
   926   /// 1, 0--2->2
       
   927   ///\endcode
       
   928   template<typename _Digraph, typename _ArcFilterMap>
  1509   template<typename _Digraph, typename _ArcFilterMap>
   929   class ArcSubDigraphAdaptor : 
  1510   class FilterArcs :
   930     public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>, 
  1511     public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
   931 			     _ArcFilterMap, false> {
  1512                       _ArcFilterMap, false> {
   932   public:
  1513   public:
   933     typedef _Digraph Digraph;
  1514     typedef _Digraph Digraph;
   934     typedef _ArcFilterMap ArcFilterMap;
  1515     typedef _ArcFilterMap ArcFilterMap;
   935 
  1516 
   936     typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>, 
  1517     typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
   937 			      ArcFilterMap, false> Parent;
  1518                        ArcFilterMap, false> Parent;
   938 
  1519 
   939     typedef typename Parent::Arc Arc;
  1520     typedef typename Parent::Arc Arc;
   940 
  1521 
   941   protected:
  1522   protected:
   942     ConstMap<typename Digraph::Node, bool> const_true_map;
  1523     ConstMap<typename Digraph::Node, bool> const_true_map;
   943 
  1524 
   944     ArcSubDigraphAdaptor() : const_true_map(true) {
  1525     FilterArcs() : const_true_map(true) {
   945       Parent::setNodeFilterMap(const_true_map);
  1526       Parent::setNodeFilterMap(const_true_map);
   946     }
  1527     }
   947 
  1528 
   948   public:
  1529   public:
   949 
  1530 
   950     /// \brief Constructor
  1531     /// \brief Constructor
   951     ///
  1532     ///
   952     /// Creates a arc-sub-digraph-adaptor for the given digraph with
  1533     /// Creates a FilterArcs adaptor for the given graph with
   953     /// given arc map filter.
  1534     /// given arc map filter.
   954     ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter) 
  1535     FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
   955       : Parent(), const_true_map(true) { 
  1536       : Parent(), const_true_map(true) {
   956       Parent::setDigraph(digraph);
  1537       Parent::setDigraph(digraph);
   957       Parent::setNodeFilterMap(const_true_map);
  1538       Parent::setNodeFilterMap(const_true_map);
   958       Parent::setArcFilterMap(arc_filter);
  1539       Parent::setArcFilterMap(arc_filter);
   959     }
  1540     }
   960 
  1541 
   961     /// \brief Hides the arc of the graph
  1542     /// \brief Hides the arc of the graph
   962     ///
  1543     ///
   963     /// This function hides \c a in the digraph, i.e. the iteration 
  1544     /// This function hides \c a in the graph, i.e. the iteration
   964     /// jumps over it. This is done by simply setting the value of \c a
  1545     /// jumps over it. This is done by simply setting the value of \c a
   965     /// to be false in the corresponding arc-map.
  1546     /// to be false in the corresponding arc map.
   966     void hide(const Arc& a) const { Parent::hide(a); }
  1547     void hide(const Arc& a) const { Parent::hide(a); }
   967 
  1548 
   968     /// \brief Unhides the arc of the graph
  1549     /// \brief Unhides the arc of the graph
   969     ///
  1550     ///
   970     /// The value of \c a is set to be true in the arc-map which stores 
  1551     /// The value of \c a is set to be true in the arc-map which stores
   971     /// hide information. If \c a was hidden previuosly, then it is shown 
  1552     /// hide information. If \c a was hidden previuosly, then it is shown
   972     /// again
  1553     /// again
   973     void unHide(const Arc& a) const { Parent::unHide(a); }
  1554     void unHide(const Arc& a) const { Parent::unHide(a); }
   974 
  1555 
   975     /// \brief Returns true if \c a is hidden.
  1556     /// \brief Returns true if \c a is hidden.
   976     ///
  1557     ///
   978     ///
  1559     ///
   979     bool hidden(const Arc& a) const { return Parent::hidden(a); }
  1560     bool hidden(const Arc& a) const { return Parent::hidden(a); }
   980 
  1561 
   981   };
  1562   };
   982 
  1563 
   983   /// \brief Just gives back an arc-sub-digraph adaptor
  1564   /// \brief Just gives back an FilterArcs adaptor
   984   ///
  1565   ///
   985   /// Just gives back an arc-sub-digraph adaptor
  1566   /// Just gives back an FilterArcs adaptor
   986   template<typename Digraph, typename ArcFilterMap>
  1567   template<typename Digraph, typename ArcFilterMap>
   987   ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
  1568   FilterArcs<const Digraph, ArcFilterMap>
   988   arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
  1569   filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
   989     return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
  1570     return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
   990   }
  1571   }
   991 
  1572 
   992   template<typename Digraph, typename ArcFilterMap>
  1573   template<typename Digraph, typename ArcFilterMap>
   993   ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
  1574   FilterArcs<const Digraph, const ArcFilterMap>
   994   arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
  1575   filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
   995     return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
  1576     return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
   996       (digraph, afm);
       
   997   }
  1577   }
   998 
  1578 
       
  1579   /// \ingroup graph_adaptors
       
  1580   ///
       
  1581   /// \brief An adaptor for hiding edges from a graph.
       
  1582   ///
       
  1583   /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
       
  1584   /// be specified, which defines the filters for edges. Just the
       
  1585   /// unfiltered edges are shown in the subdigraph. The FilterEdges is
       
  1586   /// conform to the \ref concepts::Graph "Graph concept".
       
  1587   ///
       
  1588   /// \tparam _Graph It must be conform to the \ref concepts::Graph
       
  1589   /// "Graph concept". The type can be specified to be const.
       
  1590   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
       
  1591   /// graph.
       
  1592   template<typename _Graph, typename _EdgeFilterMap>
       
  1593   class FilterEdges :
       
  1594     public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
       
  1595                     _EdgeFilterMap, false> {
       
  1596   public:
       
  1597     typedef _Graph Graph;
       
  1598     typedef _EdgeFilterMap EdgeFilterMap;
       
  1599     typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
       
  1600                      EdgeFilterMap, false> Parent;
       
  1601     typedef typename Parent::Edge Edge;
       
  1602   protected:
       
  1603     ConstMap<typename Graph::Node, bool> const_true_map;
       
  1604 
       
  1605     FilterEdges() : const_true_map(true) {
       
  1606       Parent::setNodeFilterMap(const_true_map);
       
  1607     }
       
  1608 
       
  1609   public:
       
  1610 
       
  1611     /// \brief Constructor
       
  1612     ///
       
  1613     /// Creates a FilterEdges adaptor for the given graph with
       
  1614     /// given edge map filters.
       
  1615     FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
       
  1616       Parent(), const_true_map(true) {
       
  1617       Parent::setGraph(_graph);
       
  1618       Parent::setNodeFilterMap(const_true_map);
       
  1619       Parent::setEdgeFilterMap(edge_filter_map);
       
  1620     }
       
  1621 
       
  1622     /// \brief Hides the edge of the graph
       
  1623     ///
       
  1624     /// This function hides \c e in the graph, i.e. the iteration
       
  1625     /// jumps over it. This is done by simply setting the value of \c e
       
  1626     /// to be false in the corresponding edge-map.
       
  1627     void hide(const Edge& e) const { Parent::hide(e); }
       
  1628 
       
  1629     /// \brief Unhides the edge of the graph
       
  1630     ///
       
  1631     /// The value of \c e is set to be true in the edge-map which stores
       
  1632     /// hide information. If \c e was hidden previuosly, then it is shown
       
  1633     /// again
       
  1634     void unHide(const Edge& e) const { Parent::unHide(e); }
       
  1635 
       
  1636     /// \brief Returns true if \c e is hidden.
       
  1637     ///
       
  1638     /// Returns true if \c e is hidden.
       
  1639     ///
       
  1640     bool hidden(const Edge& e) const { return Parent::hidden(e); }
       
  1641 
       
  1642   };
       
  1643 
       
  1644   /// \brief Just gives back a FilterEdges adaptor
       
  1645   ///
       
  1646   /// Just gives back a FilterEdges adaptor
       
  1647   template<typename Graph, typename EdgeFilterMap>
       
  1648   FilterEdges<const Graph, EdgeFilterMap>
       
  1649   filterEdges(const Graph& graph, EdgeFilterMap& efm) {
       
  1650     return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
       
  1651   }
       
  1652 
       
  1653   template<typename Graph, typename EdgeFilterMap>
       
  1654   FilterEdges<const Graph, const EdgeFilterMap>
       
  1655   filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
       
  1656     return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
       
  1657   }
       
  1658 
   999   template <typename _Digraph>
  1659   template <typename _Digraph>
  1000   class UndirDigraphAdaptorBase { 
  1660   class UndirectorBase {
  1001   public:
  1661   public:
  1002     typedef _Digraph Digraph;
  1662     typedef _Digraph Digraph;
  1003     typedef UndirDigraphAdaptorBase Adaptor;
  1663     typedef UndirectorBase Adaptor;
  1004 
  1664 
  1005     typedef True UndirectedTag;
  1665     typedef True UndirectedTag;
  1006 
  1666 
  1007     typedef typename Digraph::Arc Edge;
  1667     typedef typename Digraph::Arc Edge;
  1008     typedef typename Digraph::Node Node;
  1668     typedef typename Digraph::Node Node;
  1009 
  1669 
  1010     class Arc : public Edge {
  1670     class Arc : public Edge {
  1011       friend class UndirDigraphAdaptorBase;
  1671       friend class UndirectorBase;
  1012     protected:
  1672     protected:
  1013       bool _forward;
  1673       bool _forward;
  1014 
  1674 
  1015       Arc(const Edge& edge, bool forward) :
  1675       Arc(const Edge& edge, bool forward) :
  1016         Edge(edge), _forward(forward) {}
  1676         Edge(edge), _forward(forward) {}
  1019       Arc() {}
  1679       Arc() {}
  1020 
  1680 
  1021       Arc(Invalid) : Edge(INVALID), _forward(true) {}
  1681       Arc(Invalid) : Edge(INVALID), _forward(true) {}
  1022 
  1682 
  1023       bool operator==(const Arc &other) const {
  1683       bool operator==(const Arc &other) const {
  1024 	return _forward == other._forward && 
  1684         return _forward == other._forward &&
  1025 	  static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
  1685           static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
  1026       }
  1686       }
  1027       bool operator!=(const Arc &other) const {
  1687       bool operator!=(const Arc &other) const {
  1028 	return _forward != other._forward || 
  1688         return _forward != other._forward ||
  1029 	  static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
  1689           static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
  1030       }
  1690       }
  1031       bool operator<(const Arc &other) const {
  1691       bool operator<(const Arc &other) const {
  1032 	return _forward < other._forward ||
  1692         return _forward < other._forward ||
  1033 	  (_forward == other._forward &&
  1693           (_forward == other._forward &&
  1034 	   static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
  1694            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
  1035       }
  1695       }
  1036     };
  1696     };
  1037 
  1697 
  1038 
  1698 
  1039 
  1699 
  1050       a._forward = true;
  1710       a._forward = true;
  1051     }
  1711     }
  1052 
  1712 
  1053     void next(Arc& a) const {
  1713     void next(Arc& a) const {
  1054       if (a._forward) {
  1714       if (a._forward) {
  1055 	a._forward = false;
  1715         a._forward = false;
  1056       } else {
  1716       } else {
  1057 	_digraph->next(a);
  1717         _digraph->next(a);
  1058 	a._forward = true;
  1718         a._forward = true;
  1059       }
  1719       }
  1060     }
  1720     }
  1061 
  1721 
  1062     void first(Edge& e) const {
  1722     void first(Edge& e) const {
  1063       _digraph->first(e);
  1723       _digraph->first(e);
  1068     }
  1728     }
  1069 
  1729 
  1070     void firstOut(Arc& a, const Node& n) const {
  1730     void firstOut(Arc& a, const Node& n) const {
  1071       _digraph->firstIn(a, n);
  1731       _digraph->firstIn(a, n);
  1072       if( static_cast<const Edge&>(a) != INVALID ) {
  1732       if( static_cast<const Edge&>(a) != INVALID ) {
  1073 	a._forward = false;
  1733         a._forward = false;
  1074       } else {
  1734       } else {
  1075 	_digraph->firstOut(a, n);
  1735         _digraph->firstOut(a, n);
  1076 	a._forward = true;
  1736         a._forward = true;
  1077       }
  1737       }
  1078     }
  1738     }
  1079     void nextOut(Arc &a) const {
  1739     void nextOut(Arc &a) const {
  1080       if (!a._forward) {
  1740       if (!a._forward) {
  1081 	Node n = _digraph->target(a);
  1741         Node n = _digraph->target(a);
  1082 	_digraph->nextIn(a);
  1742         _digraph->nextIn(a);
  1083 	if (static_cast<const Edge&>(a) == INVALID ) {
  1743         if (static_cast<const Edge&>(a) == INVALID ) {
  1084 	  _digraph->firstOut(a, n);
  1744           _digraph->firstOut(a, n);
  1085 	  a._forward = true;
  1745           a._forward = true;
  1086 	}
  1746         }
  1087       }
  1747       }
  1088       else {
  1748       else {
  1089 	_digraph->nextOut(a);
  1749         _digraph->nextOut(a);
  1090       }
  1750       }
  1091     }
  1751     }
  1092 
  1752 
  1093     void firstIn(Arc &a, const Node &n) const {
  1753     void firstIn(Arc &a, const Node &n) const {
  1094       _digraph->firstOut(a, n);
  1754       _digraph->firstOut(a, n);
  1095       if (static_cast<const Edge&>(a) != INVALID ) {
  1755       if (static_cast<const Edge&>(a) != INVALID ) {
  1096 	a._forward = false;
  1756         a._forward = false;
  1097       } else {
  1757       } else {
  1098 	_digraph->firstIn(a, n);
  1758         _digraph->firstIn(a, n);
  1099 	a._forward = true;
  1759         a._forward = true;
  1100       }
  1760       }
  1101     }
  1761     }
  1102     void nextIn(Arc &a) const {
  1762     void nextIn(Arc &a) const {
  1103       if (!a._forward) {
  1763       if (!a._forward) {
  1104 	Node n = _digraph->source(a);
  1764         Node n = _digraph->source(a);
  1105 	_digraph->nextOut(a);
  1765         _digraph->nextOut(a);
  1106 	if( static_cast<const Edge&>(a) == INVALID ) {
  1766         if( static_cast<const Edge&>(a) == INVALID ) {
  1107 	  _digraph->firstIn(a, n);
  1767           _digraph->firstIn(a, n);
  1108 	  a._forward = true;
  1768           a._forward = true;
  1109 	}
  1769         }
  1110       }
  1770       }
  1111       else {
  1771       else {
  1112 	_digraph->nextIn(a);
  1772         _digraph->nextIn(a);
  1113       }
  1773       }
  1114     }
  1774     }
  1115 
  1775 
  1116     void firstInc(Edge &e, bool &d, const Node &n) const {
  1776     void firstInc(Edge &e, bool &d, const Node &n) const {
  1117       d = true;
  1777       d = true;
  1121       _digraph->firstIn(e, n);
  1781       _digraph->firstIn(e, n);
  1122     }
  1782     }
  1123 
  1783 
  1124     void nextInc(Edge &e, bool &d) const {
  1784     void nextInc(Edge &e, bool &d) const {
  1125       if (d) {
  1785       if (d) {
  1126 	Node s = _digraph->source(e);
  1786         Node s = _digraph->source(e);
  1127 	_digraph->nextOut(e);
  1787         _digraph->nextOut(e);
  1128 	if (e != INVALID) return;
  1788         if (e != INVALID) return;
  1129 	d = false;
  1789         d = false;
  1130 	_digraph->firstIn(e, s);
  1790         _digraph->firstIn(e, s);
  1131       } else {
  1791       } else {
  1132 	_digraph->nextIn(e);
  1792         _digraph->nextIn(e);
  1133       }
  1793       }
  1134     }
  1794     }
  1135 
  1795 
  1136     Node u(const Edge& e) const {
  1796     Node u(const Edge& e) const {
  1137       return _digraph->source(e);
  1797       return _digraph->source(e);
  1173     int maxNodeId() const { return _digraph->maxNodeId(); }
  1833     int maxNodeId() const { return _digraph->maxNodeId(); }
  1174     int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
  1834     int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
  1175     int maxEdgeId() const { return _digraph->maxArcId(); }
  1835     int maxEdgeId() const { return _digraph->maxArcId(); }
  1176 
  1836 
  1177     Node addNode() { return _digraph->addNode(); }
  1837     Node addNode() { return _digraph->addNode(); }
  1178     Edge addEdge(const Node& u, const Node& v) { 
  1838     Edge addEdge(const Node& u, const Node& v) {
  1179       return _digraph->addArc(u, v); 
  1839       return _digraph->addArc(u, v);
  1180     }
  1840     }
  1181 
  1841 
  1182     void erase(const Node& i) { _digraph->erase(i); }
  1842     void erase(const Node& i) { _digraph->erase(i); }
  1183     void erase(const Edge& i) { _digraph->erase(i); }
  1843     void erase(const Edge& i) { _digraph->erase(i); }
  1184   
  1844 
  1185     void clear() { _digraph->clear(); }
  1845     void clear() { _digraph->clear(); }
  1186 
  1846 
  1187     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
  1847     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
  1188     int nodeNum() const { return 2 * _digraph->arcNum(); }
  1848     int nodeNum() const { return 2 * _digraph->arcNum(); }
  1189     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
  1849     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
  1191     int edgeNum() const { return _digraph->arcNum(); }
  1851     int edgeNum() const { return _digraph->arcNum(); }
  1192 
  1852 
  1193     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
  1853     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
  1194     Arc findArc(Node s, Node t, Arc p = INVALID) const {
  1854     Arc findArc(Node s, Node t, Arc p = INVALID) const {
  1195       if (p == INVALID) {
  1855       if (p == INVALID) {
  1196 	Edge arc = _digraph->findArc(s, t);
  1856         Edge arc = _digraph->findArc(s, t);
  1197 	if (arc != INVALID) return direct(arc, true);
  1857         if (arc != INVALID) return direct(arc, true);
  1198 	arc = _digraph->findArc(t, s);
  1858         arc = _digraph->findArc(t, s);
  1199 	if (arc != INVALID) return direct(arc, false);
  1859         if (arc != INVALID) return direct(arc, false);
  1200       } else if (direction(p)) {
  1860       } else if (direction(p)) {
  1201 	Edge arc = _digraph->findArc(s, t, p);
  1861         Edge arc = _digraph->findArc(s, t, p);
  1202 	if (arc != INVALID) return direct(arc, true);
  1862         if (arc != INVALID) return direct(arc, true);
  1203 	arc = _digraph->findArc(t, s);
  1863         arc = _digraph->findArc(t, s);
  1204 	if (arc != INVALID) return direct(arc, false);	
  1864         if (arc != INVALID) return direct(arc, false);
  1205       } else {
  1865       } else {
  1206 	Edge arc = _digraph->findArc(t, s, p);
  1866         Edge arc = _digraph->findArc(t, s, p);
  1207 	if (arc != INVALID) return direct(arc, false);	      
  1867         if (arc != INVALID) return direct(arc, false);
  1208       }
  1868       }
  1209       return INVALID;
  1869       return INVALID;
  1210     }
  1870     }
  1211 
  1871 
  1212     Edge findEdge(Node s, Node t, Edge p = INVALID) const {
  1872     Edge findEdge(Node s, Node t, Edge p = INVALID) const {
  1218           if (arc != INVALID) return arc;
  1878           if (arc != INVALID) return arc;
  1219         } else if (_digraph->s(p) == s) {
  1879         } else if (_digraph->s(p) == s) {
  1220           Edge arc = _digraph->findArc(s, t, p);
  1880           Edge arc = _digraph->findArc(s, t, p);
  1221           if (arc != INVALID) return arc;
  1881           if (arc != INVALID) return arc;
  1222           arc = _digraph->findArc(t, s);
  1882           arc = _digraph->findArc(t, s);
  1223           if (arc != INVALID) return arc;	
  1883           if (arc != INVALID) return arc;
  1224         } else {
  1884         } else {
  1225           Edge arc = _digraph->findArc(t, s, p);
  1885           Edge arc = _digraph->findArc(t, s, p);
  1226           if (arc != INVALID) return arc;	      
  1886           if (arc != INVALID) return arc;
  1227         }
  1887         }
  1228       } else {
  1888       } else {
  1229         return _digraph->findArc(s, t, p);
  1889         return _digraph->findArc(s, t, p);
  1230       }
  1890       }
  1231       return INVALID;
  1891       return INVALID;
  1232     }
  1892     }
  1233 
  1893 
  1234   private:
  1894   private:
  1235     
  1895 
  1236     template <typename _Value>
  1896     template <typename _Value>
  1237     class ArcMapBase {
  1897     class ArcMapBase {
  1238     private:
  1898     private:
  1239       
  1899 
  1240       typedef typename Digraph::template ArcMap<_Value> MapImpl;
  1900       typedef typename Digraph::template ArcMap<_Value> MapImpl;
  1241       
  1901 
  1242     public:
  1902     public:
  1243 
  1903 
  1244       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
  1904       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
  1245 
  1905 
  1246       typedef _Value Value;
  1906       typedef _Value Value;
  1247       typedef Arc Key;
  1907       typedef Arc Key;
  1248       
  1908 
  1249       ArcMapBase(const Adaptor& adaptor) :
  1909       ArcMapBase(const Adaptor& adaptor) :
  1250 	_forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  1910         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  1251 
  1911 
  1252       ArcMapBase(const Adaptor& adaptor, const Value& v) 
  1912       ArcMapBase(const Adaptor& adaptor, const Value& v)
  1253         : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
  1913         : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
  1254       
  1914 
  1255       void set(const Arc& a, const Value& v) { 
  1915       void set(const Arc& a, const Value& v) {
  1256 	if (direction(a)) {
  1916         if (direction(a)) {
  1257 	  _forward.set(a, v); 
  1917           _forward.set(a, v);
  1258         } else { 
  1918         } else {
  1259 	  _backward.set(a, v);
  1919           _backward.set(a, v);
  1260         } 
       
  1261       }
       
  1262 
       
  1263       typename MapTraits<MapImpl>::ConstReturnValue 
       
  1264       operator[](const Arc& a) const { 
       
  1265 	if (direction(a)) {
       
  1266 	  return _forward[a]; 
       
  1267 	} else { 
       
  1268 	  return _backward[a]; 
       
  1269         }
  1920         }
  1270       }
  1921       }
  1271 
  1922 
  1272       typename MapTraits<MapImpl>::ReturnValue 
  1923       typename MapTraits<MapImpl>::ConstReturnValue
  1273       operator[](const Arc& a) { 
  1924       operator[](const Arc& a) const {
  1274 	if (direction(a)) {
  1925         if (direction(a)) {
  1275 	  return _forward[a]; 
  1926           return _forward[a];
  1276 	} else { 
  1927         } else {
  1277 	  return _backward[a]; 
  1928           return _backward[a];
  1278         }
  1929         }
  1279       }
  1930       }
  1280 
  1931 
       
  1932       typename MapTraits<MapImpl>::ReturnValue
       
  1933       operator[](const Arc& a) {
       
  1934         if (direction(a)) {
       
  1935           return _forward[a];
       
  1936         } else {
       
  1937           return _backward[a];
       
  1938         }
       
  1939       }
       
  1940 
  1281     protected:
  1941     protected:
  1282 
  1942 
  1283       MapImpl _forward, _backward; 
  1943       MapImpl _forward, _backward;
  1284 
  1944 
  1285     };
  1945     };
  1286 
  1946 
  1287   public:
  1947   public:
  1288 
  1948 
  1291     public:
  1951     public:
  1292 
  1952 
  1293       typedef _Value Value;
  1953       typedef _Value Value;
  1294       typedef typename Digraph::template NodeMap<Value> Parent;
  1954       typedef typename Digraph::template NodeMap<Value> Parent;
  1295 
  1955 
  1296       explicit NodeMap(const Adaptor& adaptor) 
  1956       explicit NodeMap(const Adaptor& adaptor)
  1297 	: Parent(*adaptor._digraph) {}
  1957         : Parent(*adaptor._digraph) {}
  1298 
  1958 
  1299       NodeMap(const Adaptor& adaptor, const _Value& value)
  1959       NodeMap(const Adaptor& adaptor, const _Value& value)
  1300 	: Parent(*adaptor._digraph, value) { }
  1960         : Parent(*adaptor._digraph, value) { }
  1301 
  1961 
  1302     private:
  1962     private:
  1303       NodeMap& operator=(const NodeMap& cmap) {
  1963       NodeMap& operator=(const NodeMap& cmap) {
  1304         return operator=<NodeMap>(cmap);
  1964         return operator=<NodeMap>(cmap);
  1305       }
  1965       }
  1307       template <typename CMap>
  1967       template <typename CMap>
  1308       NodeMap& operator=(const CMap& cmap) {
  1968       NodeMap& operator=(const CMap& cmap) {
  1309         Parent::operator=(cmap);
  1969         Parent::operator=(cmap);
  1310         return *this;
  1970         return *this;
  1311       }
  1971       }
  1312       
  1972 
  1313     };
  1973     };
  1314 
  1974 
  1315     template <typename _Value>
  1975     template <typename _Value>
  1316     class ArcMap 
  1976     class ArcMap
  1317       : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 
  1977       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
  1318     {
  1978     {
  1319     public:
  1979     public:
  1320       typedef _Value Value;
  1980       typedef _Value Value;
  1321       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  1981       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  1322     
  1982 
  1323       ArcMap(const Adaptor& adaptor) 
  1983       ArcMap(const Adaptor& adaptor)
  1324 	: Parent(adaptor) {}
  1984         : Parent(adaptor) {}
  1325 
  1985 
  1326       ArcMap(const Adaptor& adaptor, const Value& value) 
  1986       ArcMap(const Adaptor& adaptor, const Value& value)
  1327 	: Parent(adaptor, value) {}
  1987         : Parent(adaptor, value) {}
  1328     
  1988 
  1329     private:
  1989     private:
  1330       ArcMap& operator=(const ArcMap& cmap) {
  1990       ArcMap& operator=(const ArcMap& cmap) {
  1331 	return operator=<ArcMap>(cmap);
  1991         return operator=<ArcMap>(cmap);
  1332       }
  1992       }
  1333     
  1993 
  1334       template <typename CMap>
  1994       template <typename CMap>
  1335       ArcMap& operator=(const CMap& cmap) {
  1995       ArcMap& operator=(const CMap& cmap) {
  1336         Parent::operator=(cmap);
  1996         Parent::operator=(cmap);
  1337 	return *this;
  1997         return *this;
  1338       }
  1998       }
  1339     };
  1999     };
  1340         
  2000 
  1341     template <typename _Value>
  2001     template <typename _Value>
  1342     class EdgeMap : public Digraph::template ArcMap<_Value> {
  2002     class EdgeMap : public Digraph::template ArcMap<_Value> {
  1343     public:
  2003     public:
  1344       
  2004 
  1345       typedef _Value Value;
  2005       typedef _Value Value;
  1346       typedef typename Digraph::template ArcMap<Value> Parent;
  2006       typedef typename Digraph::template ArcMap<Value> Parent;
  1347       
  2007 
  1348       explicit EdgeMap(const Adaptor& adaptor) 
  2008       explicit EdgeMap(const Adaptor& adaptor)
  1349 	: Parent(*adaptor._digraph) {}
  2009         : Parent(*adaptor._digraph) {}
  1350 
  2010 
  1351       EdgeMap(const Adaptor& adaptor, const Value& value)
  2011       EdgeMap(const Adaptor& adaptor, const Value& value)
  1352 	: Parent(*adaptor._digraph, value) {}
  2012         : Parent(*adaptor._digraph, value) {}
  1353 
  2013 
  1354     private:
  2014     private:
  1355       EdgeMap& operator=(const EdgeMap& cmap) {
  2015       EdgeMap& operator=(const EdgeMap& cmap) {
  1356         return operator=<EdgeMap>(cmap);
  2016         return operator=<EdgeMap>(cmap);
  1357       }
  2017       }
  1363       }
  2023       }
  1364 
  2024 
  1365     };
  2025     };
  1366 
  2026 
  1367     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
  2027     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
  1368     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 
  2028     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
  1369 
  2029 
  1370   protected:
  2030   protected:
  1371 
  2031 
  1372     UndirDigraphAdaptorBase() : _digraph(0) {}
  2032     UndirectorBase() : _digraph(0) {}
  1373 
  2033 
  1374     Digraph* _digraph;
  2034     Digraph* _digraph;
  1375 
  2035 
  1376     void setDigraph(Digraph& digraph) {
  2036     void setDigraph(Digraph& digraph) {
  1377       _digraph = &digraph;
  2037       _digraph = &digraph;
  1378     }
  2038     }
  1379     
  2039 
  1380   };
  2040   };
  1381 
  2041 
  1382   ///\ingroup graph_adaptors
  2042   /// \ingroup graph_adaptors
  1383   ///
  2043   ///
  1384   /// \brief A graph is made from a directed digraph by an adaptor
  2044   /// \brief Undirect the graph
  1385   ///
  2045   ///
  1386   /// This adaptor makes an undirected graph from a directed
  2046   /// This adaptor makes an undirected graph from a directed
  1387   /// graph. All arc of the underlying digraph will be showed in the
  2047   /// graph. All arcs of the underlying digraph will be showed in the
  1388   /// adaptor as an edge. Let's see an informal example about using
  2048   /// adaptor as an edge. The Orienter adaptor is conform to the \ref
  1389   /// this adaptor.
  2049   /// concepts::Graph "Graph concept".
  1390   ///
  2050   ///
  1391   /// There is a network of the streets of a town. Of course there are
  2051   /// \tparam _Digraph It must be conform to the \ref
  1392   /// some one-way street in the town hence the network is a directed
  2052   /// concepts::Digraph "Digraph concept". The type can be specified
  1393   /// one. There is a crazy driver who go oppositely in the one-way
  2053   /// to const.
  1394   /// street without moral sense. Of course he can pass this streets
       
  1395   /// slower than the regular way, in fact his speed is half of the
       
  1396   /// normal speed. How long should he drive to get from a source
       
  1397   /// point to the target? Let see the example code which calculate it:
       
  1398   ///
       
  1399   /// \todo BadCode, SimpleMap does no exists
       
  1400   ///\code
       
  1401   /// typedef UndirDigraphAdaptor<Digraph> Graph;
       
  1402   /// Graph graph(digraph);
       
  1403   ///
       
  1404   /// typedef SimpleMap<LengthMap> FLengthMap;
       
  1405   /// FLengthMap flength(length);
       
  1406   ///
       
  1407   /// typedef ScaleMap<LengthMap> RLengthMap;
       
  1408   /// RLengthMap rlength(length, 2.0);
       
  1409   ///
       
  1410   /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
       
  1411   /// ULengthMap ulength(flength, rlength);
       
  1412   /// 
       
  1413   /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
       
  1414   /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
       
  1415   ///\endcode
       
  1416   ///
       
  1417   /// The combined arc map makes the length map for the undirected
       
  1418   /// graph. It is created from a forward and reverse map. The forward
       
  1419   /// map is created from the original length map with a SimpleMap
       
  1420   /// adaptor which just makes a read-write map from the reference map
       
  1421   /// i.e. it forgets that it can be return reference to values. The
       
  1422   /// reverse map is just the scaled original map with the ScaleMap
       
  1423   /// adaptor. The combination solves that passing the reverse way
       
  1424   /// takes double time than the original. To get the driving time we
       
  1425   /// run the dijkstra algorithm on the graph.
       
  1426   template<typename _Digraph>
  2054   template<typename _Digraph>
  1427   class UndirDigraphAdaptor 
  2055   class Undirector
  1428     : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
  2056     : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
  1429   public:
  2057   public:
  1430     typedef _Digraph Digraph;
  2058     typedef _Digraph Digraph;
  1431     typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
  2059     typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
  1432   protected:
  2060   protected:
  1433     UndirDigraphAdaptor() { }
  2061     Undirector() { }
  1434   public:
  2062   public:
  1435 
  2063 
  1436     /// \brief Constructor
  2064     /// \brief Constructor
  1437     ///
  2065     ///
  1438     /// Constructor
  2066     /// Creates a undirected graph from the given digraph
  1439     UndirDigraphAdaptor(_Digraph& _digraph) { 
  2067     Undirector(_Digraph& digraph) {
  1440       setDigraph(_digraph);
  2068       setDigraph(digraph);
  1441     }
  2069     }
  1442 
  2070 
  1443     /// \brief ArcMap combined from two original ArcMap
  2071     /// \brief ArcMap combined from two original ArcMap
  1444     ///
  2072     ///
  1445     /// This class adapts two original digraph ArcMap to
  2073     /// This class adapts two original digraph ArcMap to
  1446     /// get an arc map on the adaptor.
  2074     /// get an arc map on the undirected graph.
  1447     template <typename _ForwardMap, typename _BackwardMap>
  2075     template <typename _ForwardMap, typename _BackwardMap>
  1448     class CombinedArcMap {
  2076     class CombinedArcMap {
  1449     public:
  2077     public:
  1450       
  2078 
  1451       typedef _ForwardMap ForwardMap;
  2079       typedef _ForwardMap ForwardMap;
  1452       typedef _BackwardMap BackwardMap;
  2080       typedef _BackwardMap BackwardMap;
  1453 
  2081 
  1454       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
  2082       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
  1455 
  2083 
  1456       typedef typename ForwardMap::Value Value;
  2084       typedef typename ForwardMap::Value Value;
  1457       typedef typename Parent::Arc Key;
  2085       typedef typename Parent::Arc Key;
  1458 
  2086 
  1459       /// \brief Constructor      
  2087       /// \brief Constructor
  1460       ///
  2088       ///
  1461       /// Constructor      
  2089       /// Constructor
  1462       CombinedArcMap() : _forward(0), _backward(0) {}
  2090       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
  1463 
       
  1464       /// \brief Constructor      
       
  1465       ///
       
  1466       /// Constructor      
       
  1467       CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 
       
  1468         : _forward(&forward), _backward(&backward) {}
  2091         : _forward(&forward), _backward(&backward) {}
  1469       
  2092 
  1470 
  2093 
  1471       /// \brief Sets the value associated with a key.
  2094       /// \brief Sets the value associated with a key.
  1472       ///
  2095       ///
  1473       /// Sets the value associated with a key.
  2096       /// Sets the value associated with a key.
  1474       void set(const Key& e, const Value& a) { 
  2097       void set(const Key& e, const Value& a) {
  1475 	if (Parent::direction(e)) {
  2098         if (Parent::direction(e)) {
  1476 	  _forward->set(e, a); 
  2099           _forward->set(e, a);
  1477         } else { 
  2100         } else {
  1478 	  _backward->set(e, a);
  2101           _backward->set(e, a);
  1479         } 
  2102         }
  1480       }
  2103       }
  1481 
  2104 
  1482       /// \brief Returns the value associated with a key.
  2105       /// \brief Returns the value associated with a key.
  1483       ///
  2106       ///
  1484       /// Returns the value associated with a key.
  2107       /// Returns the value associated with a key.
  1485       typename MapTraits<ForwardMap>::ConstReturnValue 
  2108       typename MapTraits<ForwardMap>::ConstReturnValue
  1486       operator[](const Key& e) const { 
  2109       operator[](const Key& e) const {
  1487 	if (Parent::direction(e)) {
  2110         if (Parent::direction(e)) {
  1488 	  return (*_forward)[e]; 
  2111           return (*_forward)[e];
  1489 	} else { 
  2112         } else {
  1490 	  return (*_backward)[e]; 
  2113           return (*_backward)[e];
  1491         }
  2114         }
  1492       }
  2115       }
  1493 
  2116 
  1494       /// \brief Returns the value associated with a key.
  2117       /// \brief Returns the value associated with a key.
  1495       ///
  2118       ///
  1496       /// Returns the value associated with a key.
  2119       /// Returns the value associated with a key.
  1497       typename MapTraits<ForwardMap>::ReturnValue 
  2120       typename MapTraits<ForwardMap>::ReturnValue
  1498       operator[](const Key& e) { 
  2121       operator[](const Key& e) {
  1499 	if (Parent::direction(e)) {
  2122         if (Parent::direction(e)) {
  1500 	  return (*_forward)[e]; 
  2123           return (*_forward)[e];
  1501 	} else { 
  2124         } else {
  1502 	  return (*_backward)[e]; 
  2125           return (*_backward)[e];
  1503         }
  2126         }
  1504       }
  2127       }
  1505 
  2128 
  1506       /// \brief Sets the forward map
       
  1507       ///
       
  1508       /// Sets the forward map
       
  1509       void setForwardMap(ForwardMap& forward) {
       
  1510         _forward = &forward;
       
  1511       }
       
  1512 
       
  1513       /// \brief Sets the backward map
       
  1514       ///
       
  1515       /// Sets the backward map
       
  1516       void setBackwardMap(BackwardMap& backward) {
       
  1517         _backward = &backward;
       
  1518       }
       
  1519 
       
  1520     protected:
  2129     protected:
  1521 
  2130 
  1522       ForwardMap* _forward;
  2131       ForwardMap* _forward;
  1523       BackwardMap* _backward; 
  2132       BackwardMap* _backward;
  1524 
  2133 
  1525     };
  2134     };
  1526 
  2135 
       
  2136     /// \brief Just gives back a combined arc map
       
  2137     ///
       
  2138     /// Just gives back a combined arc map
       
  2139     template <typename ForwardMap, typename BackwardMap>
       
  2140     static CombinedArcMap<ForwardMap, BackwardMap>
       
  2141     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
       
  2142       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
       
  2143     }
       
  2144 
       
  2145     template <typename ForwardMap, typename BackwardMap>
       
  2146     static CombinedArcMap<const ForwardMap, BackwardMap>
       
  2147     combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
       
  2148       return CombinedArcMap<const ForwardMap,
       
  2149         BackwardMap>(forward, backward);
       
  2150     }
       
  2151 
       
  2152     template <typename ForwardMap, typename BackwardMap>
       
  2153     static CombinedArcMap<ForwardMap, const BackwardMap>
       
  2154     combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
       
  2155       return CombinedArcMap<ForwardMap,
       
  2156         const BackwardMap>(forward, backward);
       
  2157     }
       
  2158 
       
  2159     template <typename ForwardMap, typename BackwardMap>
       
  2160     static CombinedArcMap<const ForwardMap, const BackwardMap>
       
  2161     combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
       
  2162       return CombinedArcMap<const ForwardMap,
       
  2163         const BackwardMap>(forward, backward);
       
  2164     }
       
  2165 
  1527   };
  2166   };
  1528 
  2167 
  1529   /// \brief Just gives back an undir digraph adaptor
  2168   /// \brief Just gives back an undirected view of the given digraph
  1530   ///
  2169   ///
  1531   /// Just gives back an undir digraph adaptor
  2170   /// Just gives back an undirected view of the given digraph
  1532   template<typename Digraph>
  2171   template<typename Digraph>
  1533   UndirDigraphAdaptor<const Digraph>
  2172   Undirector<const Digraph>
  1534   undirDigraphAdaptor(const Digraph& digraph) {
  2173   undirector(const Digraph& digraph) {
  1535     return UndirDigraphAdaptor<const Digraph>(digraph);
  2174     return Undirector<const Digraph>(digraph);
  1536   }
  2175   }
  1537 
  2176 
  1538   template<typename _Digraph, 
  2177   template <typename _Graph, typename _DirectionMap>
  1539 	   typename _CapacityMap = typename _Digraph::template ArcMap<int>, 
  2178   class OrienterBase {
  1540 	   typename _FlowMap = _CapacityMap, 
  2179   public:
       
  2180 
       
  2181     typedef _Graph Graph;
       
  2182     typedef _DirectionMap DirectionMap;
       
  2183 
       
  2184     typedef typename Graph::Node Node;
       
  2185     typedef typename Graph::Edge Arc;
       
  2186 
       
  2187     void reverseArc(const Arc& arc) {
       
  2188       _direction->set(arc, !(*_direction)[arc]);
       
  2189     }
       
  2190 
       
  2191     void first(Node& i) const { _graph->first(i); }
       
  2192     void first(Arc& i) const { _graph->first(i); }
       
  2193     void firstIn(Arc& i, const Node& n) const {
       
  2194       bool d;
       
  2195       _graph->firstInc(i, d, n);
       
  2196       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
       
  2197     }
       
  2198     void firstOut(Arc& i, const Node& n ) const {
       
  2199       bool d;
       
  2200       _graph->firstInc(i, d, n);
       
  2201       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
       
  2202     }
       
  2203 
       
  2204     void next(Node& i) const { _graph->next(i); }
       
  2205     void next(Arc& i) const { _graph->next(i); }
       
  2206     void nextIn(Arc& i) const {
       
  2207       bool d = !(*_direction)[i];
       
  2208       _graph->nextInc(i, d);
       
  2209       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
       
  2210     }
       
  2211     void nextOut(Arc& i) const {
       
  2212       bool d = (*_direction)[i];
       
  2213       _graph->nextInc(i, d);
       
  2214       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
       
  2215     }
       
  2216 
       
  2217     Node source(const Arc& e) const {
       
  2218       return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
       
  2219     }
       
  2220     Node target(const Arc& e) const {
       
  2221       return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
       
  2222     }
       
  2223 
       
  2224     typedef NodeNumTagIndicator<Graph> NodeNumTag;
       
  2225     int nodeNum() const { return _graph->nodeNum(); }
       
  2226 
       
  2227     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
       
  2228     int arcNum() const { return _graph->edgeNum(); }
       
  2229 
       
  2230     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
       
  2231     Arc findArc(const Node& u, const Node& v,
       
  2232                 const Arc& prev = INVALID) {
       
  2233       Arc arc = prev;
       
  2234       bool d = arc == INVALID ? true : (*_direction)[arc];
       
  2235       if (d) {
       
  2236         arc = _graph->findEdge(u, v, arc);
       
  2237         while (arc != INVALID && !(*_direction)[arc]) {
       
  2238           _graph->findEdge(u, v, arc);
       
  2239         }
       
  2240         if (arc != INVALID) return arc;
       
  2241       }
       
  2242       _graph->findEdge(v, u, arc);
       
  2243       while (arc != INVALID && (*_direction)[arc]) {
       
  2244         _graph->findEdge(u, v, arc);
       
  2245       }
       
  2246       return arc;
       
  2247     }
       
  2248 
       
  2249     Node addNode() {
       
  2250       return Node(_graph->addNode());
       
  2251     }
       
  2252 
       
  2253     Arc addArc(const Node& u, const Node& v) {
       
  2254       Arc arc = _graph->addArc(u, v);
       
  2255       _direction->set(arc, _graph->source(arc) == u);
       
  2256       return arc;
       
  2257     }
       
  2258 
       
  2259     void erase(const Node& i) { _graph->erase(i); }
       
  2260     void erase(const Arc& i) { _graph->erase(i); }
       
  2261 
       
  2262     void clear() { _graph->clear(); }
       
  2263 
       
  2264     int id(const Node& v) const { return _graph->id(v); }
       
  2265     int id(const Arc& e) const { return _graph->id(e); }
       
  2266 
       
  2267     Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
       
  2268     Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
       
  2269 
       
  2270     int maxNodeId() const { return _graph->maxNodeId(); }
       
  2271     int maxArcId() const { return _graph->maxEdgeId(); }
       
  2272 
       
  2273     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
       
  2274     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
       
  2275 
       
  2276     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
       
  2277     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
       
  2278 
       
  2279     template <typename _Value>
       
  2280     class NodeMap : public _Graph::template NodeMap<_Value> {
       
  2281     public:
       
  2282 
       
  2283       typedef typename _Graph::template NodeMap<_Value> Parent;
       
  2284 
       
  2285       explicit NodeMap(const OrienterBase& adapter)
       
  2286         : Parent(*adapter._graph) {}
       
  2287 
       
  2288       NodeMap(const OrienterBase& adapter, const _Value& value)
       
  2289         : Parent(*adapter._graph, value) {}
       
  2290 
       
  2291     private:
       
  2292       NodeMap& operator=(const NodeMap& cmap) {
       
  2293         return operator=<NodeMap>(cmap);
       
  2294       }
       
  2295 
       
  2296       template <typename CMap>
       
  2297       NodeMap& operator=(const CMap& cmap) {
       
  2298         Parent::operator=(cmap);
       
  2299         return *this;
       
  2300       }
       
  2301 
       
  2302     };
       
  2303 
       
  2304     template <typename _Value>
       
  2305     class ArcMap : public _Graph::template EdgeMap<_Value> {
       
  2306     public:
       
  2307 
       
  2308       typedef typename Graph::template EdgeMap<_Value> Parent;
       
  2309 
       
  2310       explicit ArcMap(const OrienterBase& adapter)
       
  2311         : Parent(*adapter._graph) { }
       
  2312 
       
  2313       ArcMap(const OrienterBase& adapter, const _Value& value)
       
  2314         : Parent(*adapter._graph, value) { }
       
  2315 
       
  2316     private:
       
  2317       ArcMap& operator=(const ArcMap& cmap) {
       
  2318         return operator=<ArcMap>(cmap);
       
  2319       }
       
  2320 
       
  2321       template <typename CMap>
       
  2322       ArcMap& operator=(const CMap& cmap) {
       
  2323         Parent::operator=(cmap);
       
  2324         return *this;
       
  2325       }
       
  2326     };
       
  2327 
       
  2328 
       
  2329 
       
  2330   protected:
       
  2331     Graph* _graph;
       
  2332     DirectionMap* _direction;
       
  2333 
       
  2334     void setDirectionMap(DirectionMap& direction) {
       
  2335       _direction = &direction;
       
  2336     }
       
  2337 
       
  2338     void setGraph(Graph& graph) {
       
  2339       _graph = &graph;
       
  2340     }
       
  2341 
       
  2342   };
       
  2343 
       
  2344   /// \ingroup graph_adaptors
       
  2345   ///
       
  2346   /// \brief Orients the edges of the graph to get a digraph
       
  2347   ///
       
  2348   /// This adaptor orients each edge in the undirected graph. The
       
  2349   /// direction of the arcs stored in an edge node map.  The arcs can
       
  2350   /// be easily reverted by the \c reverseArc() member function in the
       
  2351   /// adaptor. The Orienter adaptor is conform to the \ref
       
  2352   /// concepts::Digraph "Digraph concept".
       
  2353   ///
       
  2354   /// \tparam _Graph It must be conform to the \ref concepts::Graph
       
  2355   /// "Graph concept". The type can be specified to be const.
       
  2356   /// \tparam _DirectionMap A bool valued edge map of the the adapted
       
  2357   /// graph.
       
  2358   ///
       
  2359   /// \sa orienter
       
  2360   template<typename _Graph,
       
  2361            typename DirectionMap = typename _Graph::template EdgeMap<bool> >
       
  2362   class Orienter :
       
  2363     public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
       
  2364   public:
       
  2365     typedef _Graph Graph;
       
  2366     typedef DigraphAdaptorExtender<
       
  2367       OrienterBase<_Graph, DirectionMap> > Parent;
       
  2368     typedef typename Parent::Arc Arc;
       
  2369   protected:
       
  2370     Orienter() { }
       
  2371   public:
       
  2372 
       
  2373     /// \brief Constructor of the adaptor
       
  2374     ///
       
  2375     /// Constructor of the adaptor
       
  2376     Orienter(Graph& graph, DirectionMap& direction) {
       
  2377       setGraph(graph);
       
  2378       setDirectionMap(direction);
       
  2379     }
       
  2380 
       
  2381     /// \brief Reverse arc
       
  2382     ///
       
  2383     /// It reverse the given arc. It simply negate the direction in the map.
       
  2384     void reverseArc(const Arc& a) {
       
  2385       Parent::reverseArc(a);
       
  2386     }
       
  2387   };
       
  2388 
       
  2389   /// \brief Just gives back a Orienter
       
  2390   ///
       
  2391   /// Just gives back a Orienter
       
  2392   template<typename Graph, typename DirectionMap>
       
  2393   Orienter<const Graph, DirectionMap>
       
  2394   orienter(const Graph& graph, DirectionMap& dm) {
       
  2395     return Orienter<const Graph, DirectionMap>(graph, dm);
       
  2396   }
       
  2397 
       
  2398   template<typename Graph, typename DirectionMap>
       
  2399   Orienter<const Graph, const DirectionMap>
       
  2400   orienter(const Graph& graph, const DirectionMap& dm) {
       
  2401     return Orienter<const Graph, const DirectionMap>(graph, dm);
       
  2402   }
       
  2403 
       
  2404   namespace _adaptor_bits {
       
  2405 
       
  2406     template<typename _Digraph,
       
  2407              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
       
  2408              typename _FlowMap = _CapacityMap,
       
  2409              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
       
  2410     class ResForwardFilter {
       
  2411     public:
       
  2412 
       
  2413       typedef _Digraph Digraph;
       
  2414       typedef _CapacityMap CapacityMap;
       
  2415       typedef _FlowMap FlowMap;
       
  2416       typedef _Tolerance Tolerance;
       
  2417 
       
  2418       typedef typename Digraph::Arc Key;
       
  2419       typedef bool Value;
       
  2420 
       
  2421     private:
       
  2422 
       
  2423       const CapacityMap* _capacity;
       
  2424       const FlowMap* _flow;
       
  2425       Tolerance _tolerance;
       
  2426     public:
       
  2427 
       
  2428       ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
       
  2429                        const Tolerance& tolerance = Tolerance())
       
  2430         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
       
  2431 
       
  2432       bool operator[](const typename Digraph::Arc& a) const {
       
  2433         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
       
  2434       }
       
  2435     };
       
  2436 
       
  2437     template<typename _Digraph,
       
  2438              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
       
  2439              typename _FlowMap = _CapacityMap,
       
  2440              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
       
  2441     class ResBackwardFilter {
       
  2442     public:
       
  2443 
       
  2444       typedef _Digraph Digraph;
       
  2445       typedef _CapacityMap CapacityMap;
       
  2446       typedef _FlowMap FlowMap;
       
  2447       typedef _Tolerance Tolerance;
       
  2448 
       
  2449       typedef typename Digraph::Arc Key;
       
  2450       typedef bool Value;
       
  2451 
       
  2452     private:
       
  2453 
       
  2454       const CapacityMap* _capacity;
       
  2455       const FlowMap* _flow;
       
  2456       Tolerance _tolerance;
       
  2457 
       
  2458     public:
       
  2459 
       
  2460       ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
       
  2461                         const Tolerance& tolerance = Tolerance())
       
  2462         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
       
  2463 
       
  2464       bool operator[](const typename Digraph::Arc& a) const {
       
  2465         return _tolerance.positive((*_flow)[a]);
       
  2466       }
       
  2467     };
       
  2468 
       
  2469   }
       
  2470 
       
  2471   /// \ingroup graph_adaptors
       
  2472   ///
       
  2473   /// \brief An adaptor for composing the residual graph for directed
       
  2474   /// flow and circulation problems.
       
  2475   ///
       
  2476   /// An adaptor for composing the residual graph for directed flow and
       
  2477   /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
       
  2478   /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
       
  2479   /// be functions on the arc-set.
       
  2480   ///
       
  2481   /// Then Residual implements the digraph structure with
       
  2482   /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
       
  2483   /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
       
  2484   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
       
  2485   /// called residual graph.  When we take the union
       
  2486   /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
       
  2487   /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
       
  2488   /// \f$ A_{backward} \f$, then in the adaptor it appears in both
       
  2489   /// orientation.
       
  2490   ///
       
  2491   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
       
  2492   /// "Digraph concept". The type is implicitly const.
       
  2493   /// \tparam _CapacityMap An arc map of some numeric type, it defines
       
  2494   /// the capacities in the flow problem. The map is implicitly const.
       
  2495   /// \tparam _FlowMap An arc map of some numeric type, it defines
       
  2496   /// the capacities in the flow problem.
       
  2497   /// \tparam _Tolerance Handler for inexact computation.
       
  2498   template<typename _Digraph,
       
  2499            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
       
  2500            typename _FlowMap = _CapacityMap,
  1541            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2501            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  1542   class ResForwardFilter {
  2502   class Residual :
       
  2503     public FilterArcs<
       
  2504     Undirector<const _Digraph>,
       
  2505     typename Undirector<const _Digraph>::template CombinedArcMap<
       
  2506       _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
       
  2507                                       _FlowMap, _Tolerance>,
       
  2508       _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
       
  2509                                        _FlowMap, _Tolerance> > >
       
  2510   {
  1543   public:
  2511   public:
  1544 
  2512 
  1545     typedef _Digraph Digraph;
  2513     typedef _Digraph Digraph;
  1546     typedef _CapacityMap CapacityMap;
  2514     typedef _CapacityMap CapacityMap;
  1547     typedef _FlowMap FlowMap;
  2515     typedef _FlowMap FlowMap;
  1548     typedef _Tolerance Tolerance;
  2516     typedef _Tolerance Tolerance;
  1549 
  2517 
  1550     typedef typename Digraph::Arc Key;
       
  1551     typedef bool Value;
       
  1552 
       
  1553   private:
       
  1554 
       
  1555     const CapacityMap* _capacity;
       
  1556     const FlowMap* _flow;
       
  1557     Tolerance _tolerance;
       
  1558   public:
       
  1559 
       
  1560     ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
       
  1561                      const Tolerance& tolerance = Tolerance()) 
       
  1562       : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
       
  1563 
       
  1564     ResForwardFilter(const Tolerance& tolerance = Tolerance()) 
       
  1565       : _capacity(0), _flow(0), _tolerance(tolerance)  { }
       
  1566 
       
  1567     void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
       
  1568     void setFlow(const FlowMap& flow) { _flow = &flow; }
       
  1569 
       
  1570     bool operator[](const typename Digraph::Arc& a) const {
       
  1571       return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
       
  1572     }
       
  1573   };
       
  1574 
       
  1575   template<typename _Digraph, 
       
  1576 	   typename _CapacityMap = typename _Digraph::template ArcMap<int>, 
       
  1577 	   typename _FlowMap = _CapacityMap, 
       
  1578            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
       
  1579   class ResBackwardFilter {
       
  1580   public:
       
  1581 
       
  1582     typedef _Digraph Digraph;
       
  1583     typedef _CapacityMap CapacityMap;
       
  1584     typedef _FlowMap FlowMap;
       
  1585     typedef _Tolerance Tolerance;
       
  1586 
       
  1587     typedef typename Digraph::Arc Key;
       
  1588     typedef bool Value;
       
  1589 
       
  1590   private:
       
  1591 
       
  1592     const CapacityMap* _capacity;
       
  1593     const FlowMap* _flow;
       
  1594     Tolerance _tolerance;
       
  1595 
       
  1596   public:
       
  1597 
       
  1598     ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
       
  1599                       const Tolerance& tolerance = Tolerance())
       
  1600       : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
       
  1601     ResBackwardFilter(const Tolerance& tolerance = Tolerance())
       
  1602       : _capacity(0), _flow(0), _tolerance(tolerance) { }
       
  1603 
       
  1604     void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
       
  1605     void setFlow(const FlowMap& flow) { _flow = &flow; }
       
  1606 
       
  1607     bool operator[](const typename Digraph::Arc& a) const {
       
  1608       return _tolerance.positive((*_flow)[a]);
       
  1609     }
       
  1610   };
       
  1611 
       
  1612   
       
  1613   ///\ingroup graph_adaptors
       
  1614   ///
       
  1615   ///\brief An adaptor for composing the residual graph for directed
       
  1616   ///flow and circulation problems.
       
  1617   ///
       
  1618   ///An adaptor for composing the residual graph for directed flow and
       
  1619   ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed digraph
       
  1620   ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
       
  1621   ///\f$, be functions on the arc-set.
       
  1622   ///
       
  1623   ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
       
  1624   ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
       
  1625   ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
       
  1626   ///
       
  1627   ///\code 
       
  1628   ///  ListDigraph g;
       
  1629   ///\endcode 
       
  1630   ///
       
  1631   ///Then ResDigraphAdaptor implements the digraph structure with
       
  1632   /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
       
  1633   /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
       
  1634   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
       
  1635   /// called residual graph.  When we take the union \f$
       
  1636   /// A_{forward}\cup A_{backward} \f$, multilicities are counted,
       
  1637   /// i.e.  if an arc is in both \f$ A_{forward} \f$ and \f$
       
  1638   /// A_{backward} \f$, then in the adaptor it appears twice. The
       
  1639   /// following code shows how such an instance can be constructed.
       
  1640   ///
       
  1641   ///\code 
       
  1642   ///  typedef ListDigraph Digraph; 
       
  1643   ///  IntArcMap f(g), c(g);
       
  1644   ///  ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g); 
       
  1645   ///\endcode
       
  1646   template<typename _Digraph, 
       
  1647 	   typename _CapacityMap = typename _Digraph::template ArcMap<int>, 
       
  1648 	   typename _FlowMap = _CapacityMap,
       
  1649            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
       
  1650   class ResDigraphAdaptor : 
       
  1651     public ArcSubDigraphAdaptor< 
       
  1652     UndirDigraphAdaptor<const _Digraph>, 
       
  1653     typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
       
  1654       ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,  
       
  1655       ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
       
  1656   public:
       
  1657 
       
  1658     typedef _Digraph Digraph;
       
  1659     typedef _CapacityMap CapacityMap;
       
  1660     typedef _FlowMap FlowMap;
       
  1661     typedef _Tolerance Tolerance;
       
  1662 
       
  1663     typedef typename CapacityMap::Value Value;
  2518     typedef typename CapacityMap::Value Value;
  1664     typedef ResDigraphAdaptor Adaptor;
  2519     typedef Residual Adaptor;
  1665 
  2520 
  1666   protected:
  2521   protected:
  1667 
  2522 
  1668     typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
  2523     typedef Undirector<const Digraph> Undirected;
  1669 
  2524 
  1670     typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap> 
  2525     typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
  1671     ForwardFilter;
  2526                                             FlowMap, Tolerance> ForwardFilter;
  1672 
  2527 
  1673     typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap> 
  2528     typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
  1674     BackwardFilter;
  2529                                              FlowMap, Tolerance> BackwardFilter;
  1675 
  2530 
  1676     typedef typename UndirDigraph::
  2531     typedef typename Undirected::
  1677     template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2532     template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  1678 
  2533 
  1679     typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
  2534     typedef FilterArcs<Undirected, ArcFilter> Parent;
  1680 
  2535 
  1681     const CapacityMap* _capacity;
  2536     const CapacityMap* _capacity;
  1682     FlowMap* _flow;
  2537     FlowMap* _flow;
  1683 
  2538 
  1684     UndirDigraph _graph;
  2539     Undirected _graph;
  1685     ForwardFilter _forward_filter;
  2540     ForwardFilter _forward_filter;
  1686     BackwardFilter _backward_filter;
  2541     BackwardFilter _backward_filter;
  1687     ArcFilter _arc_filter;
  2542     ArcFilter _arc_filter;
  1688 
  2543 
  1689     void setCapacityMap(const CapacityMap& capacity) {
       
  1690       _capacity = &capacity;
       
  1691       _forward_filter.setCapacity(capacity);
       
  1692       _backward_filter.setCapacity(capacity);
       
  1693     }
       
  1694 
       
  1695     void setFlowMap(FlowMap& flow) {
       
  1696       _flow = &flow;
       
  1697       _forward_filter.setFlow(flow);
       
  1698       _backward_filter.setFlow(flow);
       
  1699     }
       
  1700 
       
  1701   public:
  2544   public:
  1702 
  2545 
  1703     /// \brief Constructor of the residual digraph.
  2546     /// \brief Constructor of the residual digraph.
  1704     ///
  2547     ///
  1705     /// Constructor of the residual graph. The parameters are the digraph type,
  2548     /// Constructor of the residual graph. The parameters are the digraph,
  1706     /// the flow map, the capacity map and a tolerance object.
  2549     /// the flow map, the capacity map and a tolerance object.
  1707     ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity, 
  2550     Residual(const Digraph& digraph, const CapacityMap& capacity,
  1708                     FlowMap& flow, const Tolerance& tolerance = Tolerance()) 
  2551              FlowMap& flow, const Tolerance& tolerance = Tolerance())
  1709       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
  2552       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
  1710         _forward_filter(capacity, flow, tolerance), 
  2553         _forward_filter(capacity, flow, tolerance),
  1711         _backward_filter(capacity, flow, tolerance),
  2554         _backward_filter(capacity, flow, tolerance),
  1712         _arc_filter(_forward_filter, _backward_filter)
  2555         _arc_filter(_forward_filter, _backward_filter)
  1713     {
  2556     {
  1714       Parent::setDigraph(_graph);
  2557       Parent::setDigraph(_graph);
  1715       Parent::setArcFilterMap(_arc_filter);
  2558       Parent::setArcFilterMap(_arc_filter);
  1718     typedef typename Parent::Arc Arc;
  2561     typedef typename Parent::Arc Arc;
  1719 
  2562 
  1720     /// \brief Gives back the residual capacity of the arc.
  2563     /// \brief Gives back the residual capacity of the arc.
  1721     ///
  2564     ///
  1722     /// Gives back the residual capacity of the arc.
  2565     /// Gives back the residual capacity of the arc.
  1723     Value rescap(const Arc& arc) const {
  2566     Value residualCapacity(const Arc& a) const {
  1724       if (UndirDigraph::direction(arc)) {
  2567       if (Undirected::direction(a)) {
  1725         return (*_capacity)[arc] - (*_flow)[arc]; 
  2568         return (*_capacity)[a] - (*_flow)[a];
  1726       } else {
  2569       } else {
  1727         return (*_flow)[arc];
  2570         return (*_flow)[a];
  1728       }
  2571       }
  1729     } 
  2572     }
  1730 
  2573 
  1731     /// \brief Augment on the given arc in the residual digraph.
  2574     /// \brief Augment on the given arc in the residual graph.
  1732     ///
  2575     ///
  1733     /// Augment on the given arc in the residual digraph. It increase
  2576     /// Augment on the given arc in the residual graph. It increase
  1734     /// or decrease the flow on the original arc depend on the direction
  2577     /// or decrease the flow on the original arc depend on the direction
  1735     /// of the residual arc.
  2578     /// of the residual arc.
  1736     void augment(const Arc& e, const Value& a) const {
  2579     void augment(const Arc& a, const Value& v) const {
  1737       if (UndirDigraph::direction(e)) {
  2580       if (Undirected::direction(a)) {
  1738         _flow->set(e, (*_flow)[e] + a);
  2581         _flow->set(a, (*_flow)[a] + v);
  1739       } else {  
  2582       } else {
  1740         _flow->set(e, (*_flow)[e] - a);
  2583         _flow->set(a, (*_flow)[a] - v);
  1741       }
  2584       }
  1742     }
  2585     }
  1743 
  2586 
  1744     /// \brief Returns the direction of the arc.
  2587     /// \brief Returns the direction of the arc.
  1745     ///
  2588     ///
  1746     /// Returns true when the arc is same oriented as the original arc.
  2589     /// Returns true when the arc is same oriented as the original arc.
  1747     static bool forward(const Arc& e) {
  2590     static bool forward(const Arc& a) {
  1748       return UndirDigraph::direction(e);
  2591       return Undirected::direction(a);
  1749     }
  2592     }
  1750 
  2593 
  1751     /// \brief Returns the direction of the arc.
  2594     /// \brief Returns the direction of the arc.
  1752     ///
  2595     ///
  1753     /// Returns true when the arc is opposite oriented as the original arc.
  2596     /// Returns true when the arc is opposite oriented as the original arc.
  1754     static bool backward(const Arc& e) {
  2597     static bool backward(const Arc& a) {
  1755       return !UndirDigraph::direction(e);
  2598       return !Undirected::direction(a);
  1756     }
  2599     }
  1757 
  2600 
  1758     /// \brief Gives back the forward oriented residual arc.
  2601     /// \brief Gives back the forward oriented residual arc.
  1759     ///
  2602     ///
  1760     /// Gives back the forward oriented residual arc.
  2603     /// Gives back the forward oriented residual arc.
  1761     static Arc forward(const typename Digraph::Arc& e) {
  2604     static Arc forward(const typename Digraph::Arc& a) {
  1762       return UndirDigraph::direct(e, true);
  2605       return Undirected::direct(a, true);
  1763     }
  2606     }
  1764 
  2607 
  1765     /// \brief Gives back the backward oriented residual arc.
  2608     /// \brief Gives back the backward oriented residual arc.
  1766     ///
  2609     ///
  1767     /// Gives back the backward oriented residual arc.
  2610     /// Gives back the backward oriented residual arc.
  1768     static Arc backward(const typename Digraph::Arc& e) {
  2611     static Arc backward(const typename Digraph::Arc& a) {
  1769       return UndirDigraph::direct(e, false);
  2612       return Undirected::direct(a, false);
  1770     }
  2613     }
  1771 
  2614 
  1772     /// \brief Residual capacity map.
  2615     /// \brief Residual capacity map.
  1773     ///
  2616     ///
  1774     /// In generic residual digraphs the residual capacity can be obtained 
  2617     /// In generic residual graph the residual capacity can be obtained
  1775     /// as a map. 
  2618     /// as a map.
  1776     class ResCap {
  2619     class ResidualCapacity {
  1777     protected:
  2620     protected:
  1778       const Adaptor* _adaptor;
  2621       const Adaptor* _adaptor;
  1779     public:
  2622     public:
       
  2623       /// The Key type
  1780       typedef Arc Key;
  2624       typedef Arc Key;
       
  2625       /// The Value type
  1781       typedef typename _CapacityMap::Value Value;
  2626       typedef typename _CapacityMap::Value Value;
  1782 
  2627 
  1783       ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
  2628       /// Constructor
  1784       
  2629       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
  1785       Value operator[](const Arc& e) const {
  2630 
  1786         return _adaptor->rescap(e);
  2631       /// \e
  1787       }
  2632       Value operator[](const Arc& a) const {
  1788       
  2633         return _adaptor->residualCapacity(a);
       
  2634       }
       
  2635 
  1789     };
  2636     };
  1790 
  2637 
  1791   };
  2638   };
  1792 
  2639 
  1793   template <typename _Digraph>
  2640   template <typename _Digraph>
  1794   class SplitDigraphAdaptorBase {
  2641   class SplitNodesBase {
  1795   public:
  2642   public:
  1796 
  2643 
  1797     typedef _Digraph Digraph;
  2644     typedef _Digraph Digraph;
  1798     typedef DigraphAdaptorBase<const _Digraph> Parent;
  2645     typedef DigraphAdaptorBase<const _Digraph> Parent;
  1799     typedef SplitDigraphAdaptorBase Adaptor;
  2646     typedef SplitNodesBase Adaptor;
  1800 
  2647 
  1801     typedef typename Digraph::Node DigraphNode;
  2648     typedef typename Digraph::Node DigraphNode;
  1802     typedef typename Digraph::Arc DigraphArc;
  2649     typedef typename Digraph::Arc DigraphArc;
  1803 
  2650 
  1804     class Node;
  2651     class Node;
  1808 
  2655 
  1809     template <typename T> class NodeMapBase;
  2656     template <typename T> class NodeMapBase;
  1810     template <typename T> class ArcMapBase;
  2657     template <typename T> class ArcMapBase;
  1811 
  2658 
  1812   public:
  2659   public:
  1813     
  2660 
  1814     class Node : public DigraphNode {
  2661     class Node : public DigraphNode {
  1815       friend class SplitDigraphAdaptorBase;
  2662       friend class SplitNodesBase;
  1816       template <typename T> friend class NodeMapBase;
  2663       template <typename T> friend class NodeMapBase;
  1817     private:
  2664     private:
  1818 
  2665 
  1819       bool _in;
  2666       bool _in;
  1820       Node(DigraphNode node, bool in)
  2667       Node(DigraphNode node, bool in)
  1821 	: DigraphNode(node), _in(in) {}
  2668         : DigraphNode(node), _in(in) {}
  1822       
  2669 
  1823     public:
  2670     public:
  1824 
  2671 
  1825       Node() {}
  2672       Node() {}
  1826       Node(Invalid) : DigraphNode(INVALID), _in(true) {}
  2673       Node(Invalid) : DigraphNode(INVALID), _in(true) {}
  1827 
  2674 
  1828       bool operator==(const Node& node) const {
  2675       bool operator==(const Node& node) const {
  1829 	return DigraphNode::operator==(node) && _in == node._in;
  2676         return DigraphNode::operator==(node) && _in == node._in;
  1830       }
  2677       }
  1831       
  2678 
  1832       bool operator!=(const Node& node) const {
  2679       bool operator!=(const Node& node) const {
  1833 	return !(*this == node);
  2680         return !(*this == node);
  1834       }
  2681       }
  1835       
  2682 
  1836       bool operator<(const Node& node) const {
  2683       bool operator<(const Node& node) const {
  1837 	return DigraphNode::operator<(node) || 
  2684         return DigraphNode::operator<(node) ||
  1838 	  (DigraphNode::operator==(node) && _in < node._in);
  2685           (DigraphNode::operator==(node) && _in < node._in);
  1839       }
  2686       }
  1840     };
  2687     };
  1841 
  2688 
  1842     class Arc {
  2689     class Arc {
  1843       friend class SplitDigraphAdaptorBase;
  2690       friend class SplitNodesBase;
  1844       template <typename T> friend class ArcMapBase;
  2691       template <typename T> friend class ArcMapBase;
  1845     private:
  2692     private:
  1846       typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
  2693       typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
  1847 
  2694 
  1848       explicit Arc(const DigraphArc& arc) : _item(arc) {}
  2695       explicit Arc(const DigraphArc& arc) : _item(arc) {}
  1849       explicit Arc(const DigraphNode& node) : _item(node) {}
  2696       explicit Arc(const DigraphNode& node) : _item(node) {}
  1850       
  2697 
  1851       ArcImpl _item;
  2698       ArcImpl _item;
  1852 
  2699 
  1853     public:
  2700     public:
  1854       Arc() {}
  2701       Arc() {}
  1855       Arc(Invalid) : _item(DigraphArc(INVALID)) {}
  2702       Arc(Invalid) : _item(DigraphArc(INVALID)) {}
  1864             return _item.second() == arc._item.second();
  2711             return _item.second() == arc._item.second();
  1865           }
  2712           }
  1866         }
  2713         }
  1867         return false;
  2714         return false;
  1868       }
  2715       }
  1869       
  2716 
  1870       bool operator!=(const Arc& arc) const {
  2717       bool operator!=(const Arc& arc) const {
  1871 	return !(*this == arc);
  2718         return !(*this == arc);
  1872       }
  2719       }
  1873       
  2720 
  1874       bool operator<(const Arc& arc) const {
  2721       bool operator<(const Arc& arc) const {
  1875         if (_item.firstState()) {
  2722         if (_item.firstState()) {
  1876           if (arc._item.firstState()) {
  2723           if (arc._item.firstState()) {
  1877             return _item.first() < arc._item.first();
  2724             return _item.first() < arc._item.first();
  1878           }
  2725           }
  1895       n._in = true;
  2742       n._in = true;
  1896     }
  2743     }
  1897 
  2744 
  1898     void next(Node& n) const {
  2745     void next(Node& n) const {
  1899       if (n._in) {
  2746       if (n._in) {
  1900 	n._in = false;
  2747         n._in = false;
  1901       } else {
  2748       } else {
  1902 	n._in = true;
  2749         n._in = true;
  1903 	_digraph->next(n);
  2750         _digraph->next(n);
  1904       }
  2751       }
  1905     }
  2752     }
  1906 
  2753 
  1907     void first(Arc& e) const {
  2754     void first(Arc& e) const {
  1908       e._item.setSecond();
  2755       e._item.setSecond();
  1909       _digraph->first(e._item.second());
  2756       _digraph->first(e._item.second());
  1910       if (e._item.second() == INVALID) {
  2757       if (e._item.second() == INVALID) {
  1911         e._item.setFirst();
  2758         e._item.setFirst();
  1912 	_digraph->first(e._item.first());
  2759         _digraph->first(e._item.first());
  1913       }
  2760       }
  1914     }
  2761     }
  1915 
  2762 
  1916     void next(Arc& e) const {
  2763     void next(Arc& e) const {
  1917       if (e._item.secondState()) {
  2764       if (e._item.secondState()) {
  1918 	_digraph->next(e._item.second());
  2765         _digraph->next(e._item.second());
  1919         if (e._item.second() == INVALID) {
  2766         if (e._item.second() == INVALID) {
  1920           e._item.setFirst();
  2767           e._item.setFirst();
  1921           _digraph->first(e._item.first());
  2768           _digraph->first(e._item.first());
  1922         }
  2769         }
  1923       } else {
  2770       } else {
  1924 	_digraph->next(e._item.first());
  2771         _digraph->next(e._item.first());
  1925       }      
  2772       }
  1926     }
  2773     }
  1927 
  2774 
  1928     void firstOut(Arc& e, const Node& n) const {
  2775     void firstOut(Arc& e, const Node& n) const {
  1929       if (n._in) {
  2776       if (n._in) {
  1930         e._item.setSecond(n);
  2777         e._item.setSecond(n);
  1931       } else {
  2778       } else {
  1932         e._item.setFirst();
  2779         e._item.setFirst();
  1933 	_digraph->firstOut(e._item.first(), n);
  2780         _digraph->firstOut(e._item.first(), n);
  1934       }
  2781       }
  1935     }
  2782     }
  1936 
  2783 
  1937     void nextOut(Arc& e) const {
  2784     void nextOut(Arc& e) const {
  1938       if (!e._item.firstState()) {
  2785       if (!e._item.firstState()) {
  1939 	e._item.setFirst(INVALID);
  2786         e._item.setFirst(INVALID);
  1940       } else {
  2787       } else {
  1941 	_digraph->nextOut(e._item.first());
  2788         _digraph->nextOut(e._item.first());
  1942       }      
  2789       }
  1943     }
  2790     }
  1944 
  2791 
  1945     void firstIn(Arc& e, const Node& n) const {
  2792     void firstIn(Arc& e, const Node& n) const {
  1946       if (!n._in) {
  2793       if (!n._in) {
  1947         e._item.setSecond(n);        
  2794         e._item.setSecond(n);
  1948       } else {
  2795       } else {
  1949         e._item.setFirst();
  2796         e._item.setFirst();
  1950 	_digraph->firstIn(e._item.first(), n);
  2797         _digraph->firstIn(e._item.first(), n);
  1951       }
  2798       }
  1952     }
  2799     }
  1953 
  2800 
  1954     void nextIn(Arc& e) const {
  2801     void nextIn(Arc& e) const {
  1955       if (!e._item.firstState()) {
  2802       if (!e._item.firstState()) {
  1956 	e._item.setFirst(INVALID);
  2803         e._item.setFirst(INVALID);
  1957       } else {
  2804       } else {
  1958 	_digraph->nextIn(e._item.first());
  2805         _digraph->nextIn(e._item.first());
  1959       }
  2806       }
  1960     }
  2807     }
  1961 
  2808 
  1962     Node source(const Arc& e) const {
  2809     Node source(const Arc& e) const {
  1963       if (e._item.firstState()) {
  2810       if (e._item.firstState()) {
  1964 	return Node(_digraph->source(e._item.first()), false);
  2811         return Node(_digraph->source(e._item.first()), false);
  1965       } else {
  2812       } else {
  1966 	return Node(e._item.second(), true);
  2813         return Node(e._item.second(), true);
  1967       }
  2814       }
  1968     }
  2815     }
  1969 
  2816 
  1970     Node target(const Arc& e) const {
  2817     Node target(const Arc& e) const {
  1971       if (e._item.firstState()) {
  2818       if (e._item.firstState()) {
  1972 	return Node(_digraph->target(e._item.first()), true);
  2819         return Node(_digraph->target(e._item.first()), true);
  1973       } else {
  2820       } else {
  1974 	return Node(e._item.second(), false);
  2821         return Node(e._item.second(), false);
  1975       }
  2822       }
  1976     }
  2823     }
  1977 
  2824 
  1978     int id(const Node& n) const {
  2825     int id(const Node& n) const {
  1979       return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
  2826       return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
  1998       } else {
  2845       } else {
  1999         return Arc(_digraph->nodeFromId(ix >> 1));
  2846         return Arc(_digraph->nodeFromId(ix >> 1));
  2000       }
  2847       }
  2001     }
  2848     }
  2002     int maxArcId() const {
  2849     int maxArcId() const {
  2003       return std::max(_digraph->maxNodeId() << 1, 
  2850       return std::max(_digraph->maxNodeId() << 1,
  2004                       (_digraph->maxArcId() << 1) | 1);
  2851                       (_digraph->maxArcId() << 1) | 1);
  2005     }
  2852     }
  2006 
  2853 
  2007     static bool inNode(const Node& n) {
  2854     static bool inNode(const Node& n) {
  2008       return n._in;
  2855       return n._in;
  2046     int arcNum() const {
  2893     int arcNum() const {
  2047       return countArcs(*_digraph) + countNodes(*_digraph);
  2894       return countArcs(*_digraph) + countNodes(*_digraph);
  2048     }
  2895     }
  2049 
  2896 
  2050     typedef True FindEdgeTag;
  2897     typedef True FindEdgeTag;
  2051     Arc findArc(const Node& u, const Node& v, 
  2898     Arc findArc(const Node& u, const Node& v,
  2052 		const Arc& prev = INVALID) const {
  2899                 const Arc& prev = INVALID) const {
  2053       if (inNode(u)) {
  2900       if (inNode(u)) {
  2054         if (outNode(v)) {
  2901         if (outNode(v)) {
  2055           if (static_cast<const DigraphNode&>(u) == 
  2902           if (static_cast<const DigraphNode&>(u) ==
  2056               static_cast<const DigraphNode&>(v) && prev == INVALID) {
  2903               static_cast<const DigraphNode&>(v) && prev == INVALID) {
  2057             return Arc(u);
  2904             return Arc(u);
  2058           }
  2905           }
  2059         }
  2906         }
  2060       } else {
  2907       } else {
  2064       }
  2911       }
  2065       return INVALID;
  2912       return INVALID;
  2066     }
  2913     }
  2067 
  2914 
  2068   private:
  2915   private:
  2069     
  2916 
  2070     template <typename _Value>
  2917     template <typename _Value>
  2071     class NodeMapBase 
  2918     class NodeMapBase
  2072       : public MapTraits<typename Parent::template NodeMap<_Value> > {
  2919       : public MapTraits<typename Parent::template NodeMap<_Value> > {
  2073       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2920       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2074     public:
  2921     public:
  2075       typedef Node Key;
  2922       typedef Node Key;
  2076       typedef _Value Value;
  2923       typedef _Value Value;
  2077       
  2924 
  2078       NodeMapBase(const Adaptor& adaptor) 
  2925       NodeMapBase(const Adaptor& adaptor)
  2079 	: _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  2926         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  2080       NodeMapBase(const Adaptor& adaptor, const Value& value) 
  2927       NodeMapBase(const Adaptor& adaptor, const Value& value)
  2081 	: _in_map(*adaptor._digraph, value), 
  2928         : _in_map(*adaptor._digraph, value),
  2082 	  _out_map(*adaptor._digraph, value) {}
  2929           _out_map(*adaptor._digraph, value) {}
  2083 
  2930 
  2084       void set(const Node& key, const Value& val) {
  2931       void set(const Node& key, const Value& val) {
  2085 	if (Adaptor::inNode(key)) { _in_map.set(key, val); }
  2932         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
  2086 	else {_out_map.set(key, val); }
  2933         else {_out_map.set(key, val); }
  2087       }
  2934       }
  2088       
  2935 
  2089       typename MapTraits<NodeImpl>::ReturnValue 
  2936       typename MapTraits<NodeImpl>::ReturnValue
  2090       operator[](const Node& key) {
  2937       operator[](const Node& key) {
  2091 	if (Adaptor::inNode(key)) { return _in_map[key]; }
  2938         if (Adaptor::inNode(key)) { return _in_map[key]; }
  2092 	else { return _out_map[key]; }
  2939         else { return _out_map[key]; }
  2093       }
  2940       }
  2094 
  2941 
  2095       typename MapTraits<NodeImpl>::ConstReturnValue
  2942       typename MapTraits<NodeImpl>::ConstReturnValue
  2096       operator[](const Node& key) const {
  2943       operator[](const Node& key) const {
  2097 	if (Adaptor::inNode(key)) { return _in_map[key]; }
  2944         if (Adaptor::inNode(key)) { return _in_map[key]; }
  2098 	else { return _out_map[key]; }
  2945         else { return _out_map[key]; }
  2099       }
  2946       }
  2100 
  2947 
  2101     private:
  2948     private:
  2102       NodeImpl _in_map, _out_map;
  2949       NodeImpl _in_map, _out_map;
  2103     };
  2950     };
  2104 
  2951 
  2105     template <typename _Value>
  2952     template <typename _Value>
  2106     class ArcMapBase 
  2953     class ArcMapBase
  2107       : public MapTraits<typename Parent::template ArcMap<_Value> > {
  2954       : public MapTraits<typename Parent::template ArcMap<_Value> > {
  2108       typedef typename Parent::template ArcMap<_Value> ArcImpl;
  2955       typedef typename Parent::template ArcMap<_Value> ArcImpl;
  2109       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2956       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2110     public:
  2957     public:
  2111       typedef Arc Key;
  2958       typedef Arc Key;
  2112       typedef _Value Value;
  2959       typedef _Value Value;
  2113 
  2960 
  2114       ArcMapBase(const Adaptor& adaptor) 
  2961       ArcMapBase(const Adaptor& adaptor)
  2115 	: _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  2962         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  2116       ArcMapBase(const Adaptor& adaptor, const Value& value) 
  2963       ArcMapBase(const Adaptor& adaptor, const Value& value)
  2117 	: _arc_map(*adaptor._digraph, value), 
  2964         : _arc_map(*adaptor._digraph, value),
  2118 	  _node_map(*adaptor._digraph, value) {}
  2965           _node_map(*adaptor._digraph, value) {}
  2119 
  2966 
  2120       void set(const Arc& key, const Value& val) {
  2967       void set(const Arc& key, const Value& val) {
  2121 	if (Adaptor::origArc(key)) { 
  2968         if (Adaptor::origArc(key)) {
  2122           _arc_map.set(key._item.first(), val); 
  2969           _arc_map.set(key._item.first(), val);
  2123         } else {
  2970         } else {
  2124           _node_map.set(key._item.second(), val); 
  2971           _node_map.set(key._item.second(), val);
  2125         }
  2972         }
  2126       }
  2973       }
  2127       
  2974 
  2128       typename MapTraits<ArcImpl>::ReturnValue
  2975       typename MapTraits<ArcImpl>::ReturnValue
  2129       operator[](const Arc& key) {
  2976       operator[](const Arc& key) {
  2130 	if (Adaptor::origArc(key)) { 
  2977         if (Adaptor::origArc(key)) {
  2131           return _arc_map[key._item.first()];
  2978           return _arc_map[key._item.first()];
  2132         } else {
  2979         } else {
  2133           return _node_map[key._item.second()];
  2980           return _node_map[key._item.second()];
  2134         }
  2981         }
  2135       }
  2982       }
  2136 
  2983 
  2137       typename MapTraits<ArcImpl>::ConstReturnValue
  2984       typename MapTraits<ArcImpl>::ConstReturnValue
  2138       operator[](const Arc& key) const {
  2985       operator[](const Arc& key) const {
  2139 	if (Adaptor::origArc(key)) { 
  2986         if (Adaptor::origArc(key)) {
  2140           return _arc_map[key._item.first()];
  2987           return _arc_map[key._item.first()];
  2141         } else {
  2988         } else {
  2142           return _node_map[key._item.second()];
  2989           return _node_map[key._item.second()];
  2143         }
  2990         }
  2144       }
  2991       }
  2149     };
  2996     };
  2150 
  2997 
  2151   public:
  2998   public:
  2152 
  2999 
  2153     template <typename _Value>
  3000     template <typename _Value>
  2154     class NodeMap 
  3001     class NodeMap
  2155       : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 
  3002       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
  2156     {
  3003     {
  2157     public:
  3004     public:
  2158       typedef _Value Value;
  3005       typedef _Value Value;
  2159       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
  3006       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
  2160     
  3007 
  2161       NodeMap(const Adaptor& adaptor) 
  3008       NodeMap(const Adaptor& adaptor)
  2162 	: Parent(adaptor) {}
  3009         : Parent(adaptor) {}
  2163 
  3010 
  2164       NodeMap(const Adaptor& adaptor, const Value& value) 
  3011       NodeMap(const Adaptor& adaptor, const Value& value)
  2165 	: Parent(adaptor, value) {}
  3012         : Parent(adaptor, value) {}
  2166     
  3013 
  2167     private:
  3014     private:
  2168       NodeMap& operator=(const NodeMap& cmap) {
  3015       NodeMap& operator=(const NodeMap& cmap) {
  2169 	return operator=<NodeMap>(cmap);
  3016         return operator=<NodeMap>(cmap);
  2170       }
  3017       }
  2171     
  3018 
  2172       template <typename CMap>
  3019       template <typename CMap>
  2173       NodeMap& operator=(const CMap& cmap) {
  3020       NodeMap& operator=(const CMap& cmap) {
  2174         Parent::operator=(cmap);
  3021         Parent::operator=(cmap);
  2175 	return *this;
  3022         return *this;
  2176       }
  3023       }
  2177     };
  3024     };
  2178 
  3025 
  2179     template <typename _Value>
  3026     template <typename _Value>
  2180     class ArcMap 
  3027     class ArcMap
  2181       : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 
  3028       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
  2182     {
  3029     {
  2183     public:
  3030     public:
  2184       typedef _Value Value;
  3031       typedef _Value Value;
  2185       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  3032       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  2186     
  3033 
  2187       ArcMap(const Adaptor& adaptor) 
  3034       ArcMap(const Adaptor& adaptor)
  2188 	: Parent(adaptor) {}
  3035         : Parent(adaptor) {}
  2189 
  3036 
  2190       ArcMap(const Adaptor& adaptor, const Value& value) 
  3037       ArcMap(const Adaptor& adaptor, const Value& value)
  2191 	: Parent(adaptor, value) {}
  3038         : Parent(adaptor, value) {}
  2192     
  3039 
  2193     private:
  3040     private:
  2194       ArcMap& operator=(const ArcMap& cmap) {
  3041       ArcMap& operator=(const ArcMap& cmap) {
  2195 	return operator=<ArcMap>(cmap);
  3042         return operator=<ArcMap>(cmap);
  2196       }
  3043       }
  2197     
  3044 
  2198       template <typename CMap>
  3045       template <typename CMap>
  2199       ArcMap& operator=(const CMap& cmap) {
  3046       ArcMap& operator=(const CMap& cmap) {
  2200         Parent::operator=(cmap);
  3047         Parent::operator=(cmap);
  2201 	return *this;
  3048         return *this;
  2202       }
  3049       }
  2203     };
  3050     };
  2204 
  3051 
  2205   protected:
  3052   protected:
  2206 
  3053 
  2207     SplitDigraphAdaptorBase() : _digraph(0) {}
  3054     SplitNodesBase() : _digraph(0) {}
  2208 
  3055 
  2209     Digraph* _digraph;
  3056     Digraph* _digraph;
  2210 
  3057 
  2211     void setDigraph(Digraph& digraph) {
  3058     void setDigraph(Digraph& digraph) {
  2212       _digraph = &digraph;
  3059       _digraph = &digraph;
  2213     }
  3060     }
  2214     
  3061 
  2215   };
  3062   };
  2216 
  3063 
  2217   /// \ingroup graph_adaptors
  3064   /// \ingroup graph_adaptors
  2218   ///
  3065   ///
  2219   /// \brief Split digraph adaptor class
  3066   /// \brief Split the nodes of a directed graph
  2220   /// 
  3067   ///
  2221   /// This is an digraph adaptor which splits all node into an in-node
  3068   /// The SplitNodes adaptor splits each node into an in-node and an
  2222   /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
  3069   /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
  2223   /// node in the digraph with two node, \f$ u_{in} \f$ node and 
  3070   /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
  2224   /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the 
  3071   /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
  2225   /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
  3072   /// original digraph the new target of the arc will be \f$ u_{in} \f$
  2226   /// similarly the source of the original \f$ (u, v) \f$ arc will be
  3073   /// and similarly the source of the original \f$ (u, v) \f$ arc
  2227   /// \f$ u_{out} \f$.  The adaptor will add for each node in the 
  3074   /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
  2228   /// original digraph an additional arc which will connect 
  3075   /// the original digraph an additional arc which connects
  2229   /// \f$ (u_{in}, u_{out}) \f$.
  3076   /// \f$ (u_{in}, u_{out}) \f$.
  2230   ///
  3077   ///
  2231   /// The aim of this class is to run algorithm with node costs if the 
  3078   /// The aim of this class is to run algorithm with node costs if the
  2232   /// algorithm can use directly just arc costs. In this case we should use
  3079   /// algorithm can use directly just arc costs. In this case we should use
  2233   /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
  3080   /// a \c SplitNodes and set the node cost of the graph to the
  2234   /// bind arc in the adapted digraph.
  3081   /// bind arc in the adapted graph.
  2235   /// 
  3082   ///
  2236   /// For example a maximum flow algorithm can compute how many arc
  3083   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  2237   /// disjoint paths are in the digraph. But we would like to know how
  3084   /// "Digraph concept". The type can be specified to be const.
  2238   /// many node disjoint paths are in the digraph. First we have to
       
  2239   /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
       
  2240   /// algorithm on the adapted digraph. The bottleneck of the flow will
       
  2241   /// be the bind arcs which bounds the flow with the count of the
       
  2242   /// node disjoint paths.
       
  2243   ///
       
  2244   ///\code
       
  2245   ///
       
  2246   /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
       
  2247   ///
       
  2248   /// SDigraph sdigraph(digraph);
       
  2249   ///
       
  2250   /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
       
  2251   /// SCapacity scapacity(1);
       
  2252   ///
       
  2253   /// SDigraph::ArcMap<int> sflow(sdigraph);
       
  2254   ///
       
  2255   /// Preflow<SDigraph, SCapacity> 
       
  2256   ///   spreflow(sdigraph, scapacity, 
       
  2257   ///            SDigraph::outNode(source), SDigraph::inNode(target));
       
  2258   ///                                            
       
  2259   /// spreflow.run();
       
  2260   ///
       
  2261   ///\endcode
       
  2262   ///
       
  2263   /// The result of the mamixum flow on the original digraph
       
  2264   /// shows the next figure:
       
  2265   ///
       
  2266   /// \image html arc_disjoint.png
       
  2267   /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
       
  2268   /// 
       
  2269   /// And the maximum flow on the adapted digraph:
       
  2270   ///
       
  2271   /// \image html node_disjoint.png
       
  2272   /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
       
  2273   ///
       
  2274   /// The second solution contains just 3 disjoint paths while the first 4.
       
  2275   /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
       
  2276   ///
       
  2277   /// This digraph adaptor is fully conform to the 
       
  2278   /// \ref concepts::Digraph "Digraph" concept and
       
  2279   /// contains some additional member functions and types. The 
       
  2280   /// documentation of some member functions may be found just in the
       
  2281   /// SplitDigraphAdaptorBase class.
       
  2282   ///
       
  2283   /// \sa SplitDigraphAdaptorBase
       
  2284   template <typename _Digraph>
  3085   template <typename _Digraph>
  2285   class SplitDigraphAdaptor 
  3086   class SplitNodes
  2286     : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
  3087     : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
  2287   public:
  3088   public:
  2288     typedef _Digraph Digraph;
  3089     typedef _Digraph Digraph;
  2289     typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
  3090     typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
  2290 
  3091 
  2291     typedef typename Digraph::Node DigraphNode;
  3092     typedef typename Digraph::Node DigraphNode;
  2292     typedef typename Digraph::Arc DigraphArc;
  3093     typedef typename Digraph::Arc DigraphArc;
  2293 
  3094 
  2294     typedef typename Parent::Node Node;
  3095     typedef typename Parent::Node Node;
  2295     typedef typename Parent::Arc Arc;
  3096     typedef typename Parent::Arc Arc;
  2296 
  3097 
  2297     /// \brief Constructor of the adaptor.
  3098     /// \brief Constructor of the adaptor.
  2298     ///
  3099     ///
  2299     /// Constructor of the adaptor.
  3100     /// Constructor of the adaptor.
  2300     SplitDigraphAdaptor(Digraph& g) {
  3101     SplitNodes(Digraph& g) {
  2301       Parent::setDigraph(g);
  3102       Parent::setDigraph(g);
  2302     }
  3103     }
  2303 
  3104 
  2304     /// \brief Returns true when the node is in-node.
  3105     /// \brief Returns true when the node is in-node.
  2305     ///
  3106     ///
  2342     static Node outNode(const DigraphNode& n) {
  3143     static Node outNode(const DigraphNode& n) {
  2343       return Parent::outNode(n);
  3144       return Parent::outNode(n);
  2344     }
  3145     }
  2345 
  3146 
  2346     /// \brief Gives back the arc binds the two part of the node.
  3147     /// \brief Gives back the arc binds the two part of the node.
  2347     /// 
  3148     ///
  2348     /// Gives back the arc binds the two part of the node.
  3149     /// Gives back the arc binds the two part of the node.
  2349     static Arc arc(const DigraphNode& n) {
  3150     static Arc arc(const DigraphNode& n) {
  2350       return Parent::arc(n);
  3151       return Parent::arc(n);
  2351     }
  3152     }
  2352 
  3153 
  2353     /// \brief Gives back the arc of the original arc.
  3154     /// \brief Gives back the arc of the original arc.
  2354     /// 
  3155     ///
  2355     /// Gives back the arc of the original arc.
  3156     /// Gives back the arc of the original arc.
  2356     static Arc arc(const DigraphArc& a) {
  3157     static Arc arc(const DigraphArc& a) {
  2357       return Parent::arc(a);
  3158       return Parent::arc(a);
  2358     }
  3159     }
  2359 
  3160 
  2369       typedef typename InNodeMap::Value Value;
  3170       typedef typename InNodeMap::Value Value;
  2370 
  3171 
  2371       /// \brief Constructor
  3172       /// \brief Constructor
  2372       ///
  3173       ///
  2373       /// Constructor.
  3174       /// Constructor.
  2374       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 
  3175       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
  2375 	: _in_map(in_map), _out_map(out_map) {}
  3176         : _in_map(in_map), _out_map(out_map) {}
  2376 
  3177 
  2377       /// \brief The subscript operator.
  3178       /// \brief The subscript operator.
  2378       ///
  3179       ///
  2379       /// The subscript operator.
  3180       /// The subscript operator.
  2380       Value& operator[](const Key& key) {
  3181       Value& operator[](const Key& key) {
  2381 	if (Parent::inNode(key)) {
  3182         if (Parent::inNode(key)) {
  2382 	  return _in_map[key];
  3183           return _in_map[key];
  2383 	} else {
  3184         } else {
  2384 	  return _out_map[key];
  3185           return _out_map[key];
  2385 	}
  3186         }
  2386       }
  3187       }
  2387 
  3188 
  2388       /// \brief The const subscript operator.
  3189       /// \brief The const subscript operator.
  2389       ///
  3190       ///
  2390       /// The const subscript operator.
  3191       /// The const subscript operator.
  2391       Value operator[](const Key& key) const {
  3192       Value operator[](const Key& key) const {
  2392 	if (Parent::inNode(key)) {
  3193         if (Parent::inNode(key)) {
  2393 	  return _in_map[key];
  3194           return _in_map[key];
  2394 	} else {
  3195         } else {
  2395 	  return _out_map[key];
  3196           return _out_map[key];
  2396 	}
  3197         }
  2397       }
  3198       }
  2398 
  3199 
  2399       /// \brief The setter function of the map.
  3200       /// \brief The setter function of the map.
  2400       /// 
  3201       ///
  2401       /// The setter function of the map.
  3202       /// The setter function of the map.
  2402       void set(const Key& key, const Value& value) {
  3203       void set(const Key& key, const Value& value) {
  2403 	if (Parent::inNode(key)) {
  3204         if (Parent::inNode(key)) {
  2404 	  _in_map.set(key, value);
  3205           _in_map.set(key, value);
  2405 	} else {
  3206         } else {
  2406 	  _out_map.set(key, value);
  3207           _out_map.set(key, value);
  2407 	}
  3208         }
  2408       }
  3209       }
  2409       
  3210 
  2410     private:
  3211     private:
  2411       
  3212 
  2412       InNodeMap& _in_map;
  3213       InNodeMap& _in_map;
  2413       OutNodeMap& _out_map;
  3214       OutNodeMap& _out_map;
  2414       
  3215 
  2415     };
  3216     };
  2416 
  3217 
  2417 
  3218 
  2418     /// \brief Just gives back a combined node map.
  3219     /// \brief Just gives back a combined node map
  2419     /// 
  3220     ///
  2420     /// Just gives back a combined node map.
  3221     /// Just gives back a combined node map
  2421     template <typename InNodeMap, typename OutNodeMap>
  3222     template <typename InNodeMap, typename OutNodeMap>
  2422     static CombinedNodeMap<InNodeMap, OutNodeMap> 
  3223     static CombinedNodeMap<InNodeMap, OutNodeMap>
  2423     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  3224     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  2424       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
  3225       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
  2425     }
  3226     }
  2426 
  3227 
  2427     template <typename InNodeMap, typename OutNodeMap>
  3228     template <typename InNodeMap, typename OutNodeMap>
  2428     static CombinedNodeMap<const InNodeMap, OutNodeMap> 
  3229     static CombinedNodeMap<const InNodeMap, OutNodeMap>
  2429     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
  3230     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
  2430       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
  3231       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
  2431     }
  3232     }
  2432 
  3233 
  2433     template <typename InNodeMap, typename OutNodeMap>
  3234     template <typename InNodeMap, typename OutNodeMap>
  2434     static CombinedNodeMap<InNodeMap, const OutNodeMap> 
  3235     static CombinedNodeMap<InNodeMap, const OutNodeMap>
  2435     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
  3236     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
  2436       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
  3237       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
  2437     }
  3238     }
  2438 
  3239 
  2439     template <typename InNodeMap, typename OutNodeMap>
  3240     template <typename InNodeMap, typename OutNodeMap>
  2440     static CombinedNodeMap<const InNodeMap, const OutNodeMap> 
  3241     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
  2441     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
  3242     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
  2442       return CombinedNodeMap<const InNodeMap, 
  3243       return CombinedNodeMap<const InNodeMap,
  2443         const OutNodeMap>(in_map, out_map);
  3244         const OutNodeMap>(in_map, out_map);
  2444     }
  3245     }
  2445 
  3246 
  2446     /// \brief ArcMap combined from an original ArcMap and NodeMap
  3247     /// \brief ArcMap combined from an original ArcMap and a NodeMap
  2447     ///
  3248     ///
  2448     /// This class adapt an original digraph ArcMap and NodeMap to
  3249     /// This class adapt an original ArcMap and a NodeMap to get an
  2449     /// get an arc map on the adapted digraph.
  3250     /// arc map on the adapted digraph
  2450     template <typename DigraphArcMap, typename DigraphNodeMap>
  3251     template <typename DigraphArcMap, typename DigraphNodeMap>
  2451     class CombinedArcMap {
  3252     class CombinedArcMap {
  2452     public:
  3253     public:
  2453       
  3254 
  2454       typedef Arc Key;
  3255       typedef Arc Key;
  2455       typedef typename DigraphArcMap::Value Value;
  3256       typedef typename DigraphArcMap::Value Value;
  2456       
  3257 
  2457       /// \brief Constructor
  3258       /// \brief Constructor
  2458       ///
  3259       ///
  2459       /// Constructor.
  3260       /// Constructor.
  2460       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 
  3261       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
  2461 	: _arc_map(arc_map), _node_map(node_map) {}
  3262         : _arc_map(arc_map), _node_map(node_map) {}
  2462 
  3263 
  2463       /// \brief The subscript operator.
  3264       /// \brief The subscript operator.
  2464       ///
  3265       ///
  2465       /// The subscript operator.
  3266       /// The subscript operator.
  2466       void set(const Arc& arc, const Value& val) {
  3267       void set(const Arc& arc, const Value& val) {
  2467 	if (Parent::origArc(arc)) {
  3268         if (Parent::origArc(arc)) {
  2468 	  _arc_map.set(arc, val);
  3269           _arc_map.set(arc, val);
  2469 	} else {
  3270         } else {
  2470 	  _node_map.set(arc, val);
  3271           _node_map.set(arc, val);
  2471 	}
  3272         }
  2472       }
  3273       }
  2473 
  3274 
  2474       /// \brief The const subscript operator.
  3275       /// \brief The const subscript operator.
  2475       ///
  3276       ///
  2476       /// The const subscript operator.
  3277       /// The const subscript operator.
  2477       Value operator[](const Key& arc) const {
  3278       Value operator[](const Key& arc) const {
  2478 	if (Parent::origArc(arc)) {
  3279         if (Parent::origArc(arc)) {
  2479 	  return _arc_map[arc];
  3280           return _arc_map[arc];
  2480 	} else {
  3281         } else {
  2481 	  return _node_map[arc];
  3282           return _node_map[arc];
  2482 	}
  3283         }
  2483       }      
  3284       }
  2484 
  3285 
  2485       /// \brief The const subscript operator.
  3286       /// \brief The const subscript operator.
  2486       ///
  3287       ///
  2487       /// The const subscript operator.
  3288       /// The const subscript operator.
  2488       Value& operator[](const Key& arc) {
  3289       Value& operator[](const Key& arc) {
  2489 	if (Parent::origArc(arc)) {
  3290         if (Parent::origArc(arc)) {
  2490 	  return _arc_map[arc];
  3291           return _arc_map[arc];
  2491 	} else {
  3292         } else {
  2492 	  return _node_map[arc];
  3293           return _node_map[arc];
  2493 	}
  3294         }
  2494       }      
  3295       }
  2495       
  3296 
  2496     private:
  3297     private:
  2497       DigraphArcMap& _arc_map;
  3298       DigraphArcMap& _arc_map;
  2498       DigraphNodeMap& _node_map;
  3299       DigraphNodeMap& _node_map;
  2499     };
  3300     };
  2500                     
  3301 
  2501     /// \brief Just gives back a combined arc map.
  3302     /// \brief Just gives back a combined arc map
  2502     /// 
  3303     ///
  2503     /// Just gives back a combined arc map.
  3304     /// Just gives back a combined arc map
  2504     template <typename DigraphArcMap, typename DigraphNodeMap>
  3305     template <typename DigraphArcMap, typename DigraphNodeMap>
  2505     static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 
  3306     static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
  2506     combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  3307     combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  2507       return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
  3308       return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
  2508     }
  3309     }
  2509 
  3310 
  2510     template <typename DigraphArcMap, typename DigraphNodeMap>
  3311     template <typename DigraphArcMap, typename DigraphNodeMap>
  2511     static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 
  3312     static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
  2512     combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  3313     combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  2513       return CombinedArcMap<const DigraphArcMap, 
  3314       return CombinedArcMap<const DigraphArcMap,
  2514         DigraphNodeMap>(arc_map, node_map);
  3315         DigraphNodeMap>(arc_map, node_map);
  2515     }
  3316     }
  2516 
  3317 
  2517     template <typename DigraphArcMap, typename DigraphNodeMap>
  3318     template <typename DigraphArcMap, typename DigraphNodeMap>
  2518     static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 
  3319     static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
  2519     combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
  3320     combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
  2520       return CombinedArcMap<DigraphArcMap, 
  3321       return CombinedArcMap<DigraphArcMap,
  2521         const DigraphNodeMap>(arc_map, node_map);
  3322         const DigraphNodeMap>(arc_map, node_map);
  2522     }
  3323     }
  2523 
  3324 
  2524     template <typename DigraphArcMap, typename DigraphNodeMap>
  3325     template <typename DigraphArcMap, typename DigraphNodeMap>
  2525     static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 
  3326     static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
  2526     combinedArcMap(const DigraphArcMap& arc_map, 
  3327     combinedArcMap(const DigraphArcMap& arc_map,
  2527                     const DigraphNodeMap& node_map) {
  3328                    const DigraphNodeMap& node_map) {
  2528       return CombinedArcMap<const DigraphArcMap, 
  3329       return CombinedArcMap<const DigraphArcMap,
  2529         const DigraphNodeMap>(arc_map, node_map);
  3330         const DigraphNodeMap>(arc_map, node_map);
  2530     }
  3331     }
  2531 
  3332 
  2532   };
  3333   };
  2533 
  3334 
  2534   /// \brief Just gives back a split digraph adaptor
  3335   /// \brief Just gives back a node splitter
  2535   ///
  3336   ///
  2536   /// Just gives back a split digraph adaptor
  3337   /// Just gives back a node splitter
  2537   template<typename Digraph>
  3338   template<typename Digraph>
  2538   SplitDigraphAdaptor<Digraph>
  3339   SplitNodes<Digraph>
  2539   splitDigraphAdaptor(const Digraph& digraph) {
  3340   splitNodes(const Digraph& digraph) {
  2540     return SplitDigraphAdaptor<Digraph>(digraph);
  3341     return SplitNodes<Digraph>(digraph);
  2541   }
  3342   }
  2542 
  3343 
  2543 
  3344 
  2544 } //namespace lemon
  3345 } //namespace lemon
  2545 
  3346 
  2546 #endif //LEMON_DIGRAPH_ADAPTOR_H
  3347 #endif //LEMON_ADAPTORS_H
  2547