COIN-OR::LEMON - Graph Library

Changeset 416:76287c8caa26 in lemon-1.2 for lemon


Ignore:
Timestamp:
11/30/08 19:18:32 (15 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Reorganication of graph adaptors and doc improvements (#67)

  • Moving to one file, lemon/adaptors.h
  • Renamings
  • Doc cleanings
Location:
lemon
Files:
1 deleted
3 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r414 r416  
    1717
    1818lemon_HEADERS += \
     19        lemon/adaptors.h \
    1920        lemon/arg_parser.h \
    2021        lemon/assert.h \
  • lemon/adaptors.h

    r415 r416  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    1717 */
    1818
    19 #ifndef LEMON_DIGRAPH_ADAPTOR_H
    20 #define LEMON_DIGRAPH_ADAPTOR_H
    21 
    22 ///\ingroup graph_adaptors
    23 ///\file
    24 ///\brief Several digraph adaptors.
     19#ifndef LEMON_ADAPTORS_H
     20#define LEMON_ADAPTORS_H
     21
     22/// \ingroup graph_adaptors
     23/// \file
     24/// \brief Several graph adaptors
    2525///
    26 ///This file contains several useful digraph adaptor classes.
     26/// This file contains several useful adaptors for digraphs and graphs.
    2727
    2828#include <lemon/core.h>
     
    3030#include <lemon/bits/variant.h>
    3131
    32 #include <lemon/bits/base_extender.h>
    3332#include <lemon/bits/graph_adaptor_extender.h>
    34 #include <lemon/bits/graph_extender.h>
    3533#include <lemon/tolerance.h>
    3634
     
    5654    typedef typename Digraph::Node Node;
    5755    typedef typename Digraph::Arc Arc;
    58    
     56
    5957    void first(Node& i) const { _digraph->first(i); }
    6058    void first(Arc& i) const { _digraph->first(i); }
     
    7270    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    7371    int nodeNum() const { return _digraph->nodeNum(); }
    74    
     72
    7573    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    7674    int arcNum() const { return _digraph->arcNum(); }
     
    8078      return _digraph->findArc(u, v, prev);
    8179    }
    82  
     80
    8381    Node addNode() { return _digraph->addNode(); }
    8482    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
     
    8684    void erase(const Node& n) const { _digraph->erase(n); }
    8785    void erase(const Arc& a) const { _digraph->erase(a); }
    88  
     86
    8987    void clear() const { _digraph->clear(); }
    90    
     88
    9189    int id(const Node& n) const { return _digraph->id(n); }
    9290    int id(const Arc& a) const { return _digraph->id(a); }
     
    9997
    10098    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()); }
    102100
    103101    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
    104     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 
    105    
     102    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
     103
    106104    template <typename _Value>
    107105    class NodeMap : public Digraph::template NodeMap<_Value> {
     
    110108      typedef typename Digraph::template NodeMap<_Value> Parent;
    111109
    112       explicit NodeMap(const Adaptor& adaptor) 
    113         : Parent(*adaptor._digraph) {}
     110      explicit NodeMap(const Adaptor& adaptor)
     111        : Parent(*adaptor._digraph) {}
    114112
    115113      NodeMap(const Adaptor& adaptor, const _Value& value)
    116         : Parent(*adaptor._digraph, value) { }
     114        : Parent(*adaptor._digraph, value) { }
    117115
    118116    private:
     
    126124        return *this;
    127125      }
    128      
     126
    129127    };
    130128
     
    132130    class ArcMap : public Digraph::template ArcMap<_Value> {
    133131    public:
    134      
     132
    135133      typedef typename Digraph::template ArcMap<_Value> Parent;
    136      
    137       explicit ArcMap(const Adaptor& adaptor) 
    138         : Parent(*adaptor._digraph) {}
     134
     135      explicit ArcMap(const Adaptor& adaptor)
     136        : Parent(*adaptor._digraph) {}
    139137
    140138      ArcMap(const Adaptor& adaptor, const _Value& value)
    141         : Parent(*adaptor._digraph, value) {}
     139        : Parent(*adaptor._digraph, value) {}
    142140
    143141    private:
     
    156154  };
    157155
     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  };
    158310
    159311  template <typename _Digraph>
    160   class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
     312  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
    161313  public:
    162314    typedef _Digraph Digraph;
    163315    typedef DigraphAdaptorBase<_Digraph> Parent;
    164316  protected:
    165     RevDigraphAdaptorBase() : Parent() { }
     317    ReverseDigraphBase() : Parent() { }
    166318  public:
    167319    typedef typename Parent::Node Node;
     
    177329    Node target(const Arc& a) const { return Parent::source(a); }
    178330
     331    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
     332
    179333    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    180     Arc findArc(const Node& u, const Node& v, 
    181                 const Arc& prev = INVALID) {
     334    Arc findArc(const Node& u, const Node& v,
     335                const Arc& prev = INVALID) {
    182336      return Parent::findArc(v, u, prev);
    183337    }
    184338
    185339  };
    186    
    187 
    188   ///\ingroup graph_adaptors
    189   ///
    190   ///\brief A digraph adaptor which reverses the orientation of the arcs.
    191   ///
    192   /// If \c g is defined as
    193   ///\code
    194   /// ListDigraph dg;
    195   ///\endcode
    196   /// then
    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
     340
     341  /// \ingroup graph_adaptors
     342  ///
     343  /// \brief A digraph adaptor which reverses the orientation of the arcs.
     344  ///
     345  /// ReverseDigraph reverses the arcs in the adapted digraph. The
     346  /// SubDigraph is conform to the \ref concepts::Digraph
     347  /// "Digraph concept".
     348  ///
     349  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     350  /// "Digraph concept". The type can be specified to be const.
    235351  template<typename _Digraph>
    236   class RevDigraphAdaptor :
    237     public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
     352  class ReverseDigraph :
     353    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
    238354  public:
    239355    typedef _Digraph Digraph;
    240356    typedef DigraphAdaptorExtender<
    241       RevDigraphAdaptorBase<_Digraph> > Parent;
     357      ReverseDigraphBase<_Digraph> > Parent;
    242358  protected:
    243     RevDigraphAdaptor() { }
     359    ReverseDigraph() { }
    244360  public:
    245361
    246362    /// \brief Constructor
    247363    ///
    248     /// Creates a reverse graph adaptor for the given digraph
    249     explicit RevDigraphAdaptor(Digraph& digraph) {
    250       Parent::setDigraph(digraph); 
     364    /// Creates a reverse digraph adaptor for the given digraph
     365    explicit ReverseDigraph(Digraph& digraph) {
     366      Parent::setDigraph(digraph);
    251367    }
    252368  };
     
    256372  /// Just gives back a reverse digraph adaptor
    257373  template<typename Digraph>
    258   RevDigraphAdaptor<const Digraph>
    259   revDigraphAdaptor(const Digraph& digraph) {
    260     return RevDigraphAdaptor<const Digraph>(digraph);
     374  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
     375    return ReverseDigraph<const Digraph>(digraph);
    261376  }
    262377
    263   template <typename _Digraph, typename _NodeFilterMap, 
    264             typename _ArcFilterMap, bool checked = true>
    265   class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
     378  template <typename _Digraph, typename _NodeFilterMap,
     379            typename _ArcFilterMap, bool _checked = true>
     380  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
    266381  public:
    267382    typedef _Digraph Digraph;
     
    269384    typedef _ArcFilterMap ArcFilterMap;
    270385
    271     typedef SubDigraphAdaptorBase Adaptor;
     386    typedef SubDigraphBase Adaptor;
    272387    typedef DigraphAdaptorBase<_Digraph> Parent;
    273388  protected:
    274389    NodeFilterMap* _node_filter;
    275390    ArcFilterMap* _arc_filter;
    276     SubDigraphAdaptorBase()
     391    SubDigraphBase()
    277392      : Parent(), _node_filter(0), _arc_filter(0) { }
    278393
     
    289404    typedef typename Parent::Arc Arc;
    290405
    291     void first(Node& i) const {
    292       Parent::first(i);
    293       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
    294     }
    295 
    296     void first(Arc& i) const {
    297       Parent::first(i);
    298       while (i != INVALID && (!(*_arc_filter)[i]
    299              || !(*_node_filter)[Parent::source(i)]
    300              || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
    301     }
    302 
    303     void firstIn(Arc& i, const Node& n) const {
    304       Parent::firstIn(i, n);
    305       while (i != INVALID && (!(*_arc_filter)[i]
    306              || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
    307     }
    308 
    309     void firstOut(Arc& i, const Node& n) const {
    310       Parent::firstOut(i, n);
    311       while (i != INVALID && (!(*_arc_filter)[i]
    312              || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
    313     }
    314 
    315     void next(Node& i) const {
    316       Parent::next(i);
    317       while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
    318     }
    319 
    320     void next(Arc& i) const {
    321       Parent::next(i);
    322       while (i != INVALID && (!(*_arc_filter)[i]
    323              || !(*_node_filter)[Parent::source(i)]
    324              || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
    325     }
    326 
    327     void nextIn(Arc& i) const {
    328       Parent::nextIn(i);
    329       while (i != INVALID && (!(*_arc_filter)[i]
    330              || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
    331     }
    332 
    333     void nextOut(Arc& i) const {
    334       Parent::nextOut(i);
    335       while (i != INVALID && (!(*_arc_filter)[i]
    336              || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
     406    void first(Node& i) const {
     407      Parent::first(i);
     408      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
     409    }
     410
     411    void first(Arc& i) const {
     412      Parent::first(i);
     413      while (i != INVALID && (!(*_arc_filter)[i]
     414                              || !(*_node_filter)[Parent::source(i)]
     415                              || !(*_node_filter)[Parent::target(i)]))
     416        Parent::next(i);
     417    }
     418
     419    void firstIn(Arc& i, const Node& n) const {
     420      Parent::firstIn(i, n);
     421      while (i != INVALID && (!(*_arc_filter)[i]
     422                              || !(*_node_filter)[Parent::source(i)]))
     423        Parent::nextIn(i);
     424    }
     425
     426    void firstOut(Arc& i, const Node& n) const {
     427      Parent::firstOut(i, n);
     428      while (i != INVALID && (!(*_arc_filter)[i]
     429                              || !(*_node_filter)[Parent::target(i)]))
     430        Parent::nextOut(i);
     431    }
     432
     433    void next(Node& i) const {
     434      Parent::next(i);
     435      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
     436    }
     437
     438    void next(Arc& i) const {
     439      Parent::next(i);
     440      while (i != INVALID && (!(*_arc_filter)[i]
     441                              || !(*_node_filter)[Parent::source(i)]
     442                              || !(*_node_filter)[Parent::target(i)]))
     443        Parent::next(i);
     444    }
     445
     446    void nextIn(Arc& i) const {
     447      Parent::nextIn(i);
     448      while (i != INVALID && (!(*_arc_filter)[i]
     449                              || !(*_node_filter)[Parent::source(i)]))
     450        Parent::nextIn(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);
    337458    }
    338459
     
    350471
    351472    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    352     Arc findArc(const Node& source, const Node& target, 
    353                 const Arc& prev = INVALID) {
     473    Arc findArc(const Node& source, const Node& target,
     474                const Arc& prev = INVALID) {
    354475      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    355476        return INVALID;
     
    363484
    364485    template <typename _Value>
    365     class NodeMap : public SubMapExtender<Adaptor, 
    366         typename Parent::template NodeMap<_Value> > {
     486    class NodeMap : public SubMapExtender<Adaptor,
     487      typename Parent::template NodeMap<_Value> > {
    367488    public:
    368489      typedef _Value Value;
    369490      typedef SubMapExtender<Adaptor, typename Parent::
    370491                             template NodeMap<Value> > MapParent;
    371    
    372       NodeMap(const Adaptor& adaptor) 
    373         : MapParent(adaptor) {}
    374       NodeMap(const Adaptor& adaptor, const Value& value) 
    375         : MapParent(adaptor, value) {}
    376    
     492
     493      NodeMap(const Adaptor& adaptor)
     494        : MapParent(adaptor) {}
     495      NodeMap(const Adaptor& adaptor, const Value& value)
     496        : MapParent(adaptor, value) {}
     497
    377498    private:
    378499      NodeMap& operator=(const NodeMap& cmap) {
    379         return operator=<NodeMap>(cmap);
    380       }
    381    
     500        return operator=<NodeMap>(cmap);
     501      }
     502
    382503      template <typename CMap>
    383504      NodeMap& operator=(const CMap& cmap) {
    384505        MapParent::operator=(cmap);
    385         return *this;
     506        return *this;
    386507      }
    387508    };
    388509
    389510    template <typename _Value>
    390     class ArcMap : public SubMapExtender<Adaptor, 
    391         typename Parent::template ArcMap<_Value> > {
     511    class ArcMap : public SubMapExtender<Adaptor,
     512      typename Parent::template ArcMap<_Value> > {
    392513    public:
    393514      typedef _Value Value;
    394515      typedef SubMapExtender<Adaptor, typename Parent::
    395516                             template ArcMap<Value> > MapParent;
    396    
    397       ArcMap(const Adaptor& adaptor) 
    398         : MapParent(adaptor) {}
    399       ArcMap(const Adaptor& adaptor, const Value& value) 
    400         : MapParent(adaptor, value) {}
    401    
     517
     518      ArcMap(const Adaptor& adaptor)
     519        : MapParent(adaptor) {}
     520      ArcMap(const Adaptor& adaptor, const Value& value)
     521        : MapParent(adaptor, value) {}
     522
    402523    private:
    403524      ArcMap& operator=(const ArcMap& cmap) {
    404         return operator=<ArcMap>(cmap);
    405       }
    406    
     525        return operator=<ArcMap>(cmap);
     526      }
     527
    407528      template <typename CMap>
    408529      ArcMap& operator=(const CMap& cmap) {
    409530        MapParent::operator=(cmap);
    410         return *this;
     531        return *this;
    411532      }
    412533    };
     
    415536
    416537  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
    417   class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
     538  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
    418539    : public DigraphAdaptorBase<_Digraph> {
    419540  public:
     
    422543    typedef _ArcFilterMap ArcFilterMap;
    423544
    424     typedef SubDigraphAdaptorBase Adaptor;
     545    typedef SubDigraphBase Adaptor;
    425546    typedef DigraphAdaptorBase<Digraph> Parent;
    426547  protected:
    427548    NodeFilterMap* _node_filter;
    428549    ArcFilterMap* _arc_filter;
    429     SubDigraphAdaptorBase()
     550    SubDigraphBase()
    430551      : Parent(), _node_filter(0), _arc_filter(0) { }
    431552
     
    442563    typedef typename Parent::Arc Arc;
    443564
    444     void first(Node& i) const { 
    445       Parent::first(i); 
    446       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 
    447     }
    448 
    449     void first(Arc& i) const { 
    450       Parent::first(i); 
    451       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 
    452     }
    453 
    454     void firstIn(Arc& i, const Node& n) const { 
    455       Parent::firstIn(i, n); 
    456       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 
    457     }
    458 
    459     void firstOut(Arc& i, const Node& n) const { 
    460       Parent::firstOut(i, n); 
    461       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 
    462     }
    463 
    464     void next(Node& i) const { 
    465       Parent::next(i); 
    466       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 
    467     }
    468     void next(Arc& i) const { 
    469       Parent::next(i); 
    470       while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 
    471     }
    472     void nextIn(Arc& i) const { 
    473       Parent::nextIn(i); 
    474       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 
    475     }
    476 
    477     void nextOut(Arc& i) const { 
    478       Parent::nextOut(i); 
    479       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 
     565    void first(Node& i) const {
     566      Parent::first(i);
     567      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     568    }
     569
     570    void first(Arc& i) const {
     571      Parent::first(i);
     572      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
     573    }
     574
     575    void firstIn(Arc& i, const Node& n) const {
     576      Parent::firstIn(i, n);
     577      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
     578    }
     579
     580    void firstOut(Arc& i, const Node& n) const {
     581      Parent::firstOut(i, n);
     582      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
     583    }
     584
     585    void next(Node& i) const {
     586      Parent::next(i);
     587      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     588    }
     589    void next(Arc& i) const {
     590      Parent::next(i);
     591      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
     592    }
     593    void nextIn(Arc& i) const {
     594      Parent::nextIn(i);
     595      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
     596    }
     597
     598    void nextOut(Arc& i) const {
     599      Parent::nextOut(i);
     600      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
    480601    }
    481602
     
    493614
    494615    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    495     Arc findArc(const Node& source, const Node& target, 
    496                   const Arc& prev = INVALID) {
     616    Arc findArc(const Node& source, const Node& target,
     617                const Arc& prev = INVALID) {
    497618      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    498619        return INVALID;
     
    506627
    507628    template <typename _Value>
    508     class NodeMap : public SubMapExtender<Adaptor, 
    509         typename Parent::template NodeMap<_Value> > {
     629    class NodeMap : public SubMapExtender<Adaptor,
     630      typename Parent::template NodeMap<_Value> > {
    510631    public:
    511632      typedef _Value Value;
    512633      typedef SubMapExtender<Adaptor, typename Parent::
    513634                             template NodeMap<Value> > MapParent;
    514    
    515       NodeMap(const Adaptor& adaptor) 
    516         : MapParent(adaptor) {}
    517       NodeMap(const Adaptor& adaptor, const Value& value) 
    518         : MapParent(adaptor, value) {}
    519    
     635
     636      NodeMap(const Adaptor& adaptor)
     637        : MapParent(adaptor) {}
     638      NodeMap(const Adaptor& adaptor, const Value& value)
     639        : MapParent(adaptor, value) {}
     640
    520641    private:
    521642      NodeMap& operator=(const NodeMap& cmap) {
    522         return operator=<NodeMap>(cmap);
    523       }
    524    
     643        return operator=<NodeMap>(cmap);
     644      }
     645
    525646      template <typename CMap>
    526647      NodeMap& operator=(const CMap& cmap) {
    527648        MapParent::operator=(cmap);
    528         return *this;
     649        return *this;
    529650      }
    530651    };
    531652
    532653    template <typename _Value>
    533     class ArcMap : public SubMapExtender<Adaptor, 
    534         typename Parent::template ArcMap<_Value> > {
     654    class ArcMap : public SubMapExtender<Adaptor,
     655      typename Parent::template ArcMap<_Value> > {
    535656    public:
    536657      typedef _Value Value;
    537658      typedef SubMapExtender<Adaptor, typename Parent::
    538659                             template ArcMap<Value> > MapParent;
    539    
    540       ArcMap(const Adaptor& adaptor) 
    541         : MapParent(adaptor) {}
    542       ArcMap(const Adaptor& adaptor, const Value& value) 
    543         : MapParent(adaptor, value) {}
    544    
     660
     661      ArcMap(const Adaptor& adaptor)
     662        : MapParent(adaptor) {}
     663      ArcMap(const Adaptor& adaptor, const Value& value)
     664        : MapParent(adaptor, value) {}
     665
    545666    private:
    546667      ArcMap& operator=(const ArcMap& cmap) {
    547         return operator=<ArcMap>(cmap);
    548       }
    549    
     668        return operator=<ArcMap>(cmap);
     669      }
     670
    550671      template <typename CMap>
    551672      ArcMap& operator=(const CMap& cmap) {
    552673        MapParent::operator=(cmap);
    553         return *this;
     674        return *this;
    554675      }
    555676    };
     
    559680  /// \ingroup graph_adaptors
    560681  ///
    561   /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
    562   ///
    563   /// SubDigraphAdaptor shows the digraph with filtered node-set and
    564   /// arc-set. If the \c checked parameter is true then it filters the arc-set
    565   /// respect to the source and target.
    566   ///
    567   /// If the \c checked template parameter is false then the
    568   /// node-iterator cares only the filter on the node-set, and the
    569   /// arc-iterator cares only the filter on the arc-set.  Therefore
    570   /// the arc-map have to filter all arcs which's source or target is
    571   /// filtered by the node-filter.
    572   ///\code
    573   /// typedef ListDigraph Digraph;
    574   /// DIGRAPH_TYPEDEFS(Digraph);
    575   /// Digraph g;
    576   /// Node u=g.addNode(); //node of id 0
    577   /// Node v=g.addNode(); //node of id 1
    578   /// Arc a=g.addArc(u, v); //arc of id 0
    579   /// Arc f=g.addArc(v, u); //arc of id 1
    580   /// BoolNodeMap nm(g, true);
    581   /// nm.set(u, false);
    582   /// BoolArcMap am(g, true);
    583   /// am.set(a, false);
    584   /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
    585   /// SubDGA ga(g, nm, am);
    586   /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
    587   ///   std::cout << g.id(n) << std::endl;
    588   /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a)
    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> > {
     682  /// \brief An adaptor for hiding nodes and arcs in a digraph
     683  ///
     684  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
     685  /// and a bool arc map must be specified, which define the filters
     686  /// for nodes and arcs. Just the nodes and arcs with true value are
     687  /// shown in the subdigraph. The SubDigraph is conform to the \ref
     688  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
     689  /// is true, then the arcs incident to filtered nodes are also
     690  /// filtered out.
     691  ///
     692  /// \tparam _Digraph It must be conform to the \ref
     693  /// concepts::Digraph "Digraph concept". The type can be specified
     694  /// to const.
     695  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
     696  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
     697  /// \tparam _checked If the parameter is false then the arc filtering
     698  /// is not checked with respect to node filter. Otherwise, each arc
     699  /// is automatically filtered, which is incident to a filtered node.
     700  ///
     701  /// \see FilterNodes
     702  /// \see FilterArcs
     703  template<typename _Digraph,
     704           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
     705           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
     706           bool _checked = true>
     707  class SubDigraph
     708    : public DigraphAdaptorExtender<
     709      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
    608710  public:
    609711    typedef _Digraph Digraph;
     
    612714
    613715    typedef DigraphAdaptorExtender<
    614       SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
     716      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
    615717    Parent;
    616718
     
    619721
    620722  protected:
    621     SubDigraphAdaptor() { }
     723    SubDigraph() { }
    622724  public:
    623725
    624726    /// \brief Constructor
    625727    ///
    626     /// Creates a sub-digraph-adaptor for the given digraph with
     728    /// Creates a subdigraph for the given digraph with
    627729    /// given node and arc map filters.
    628     SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
    629                       ArcFilterMap& arc_filter) {
     730    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
     731               ArcFilterMap& arc_filter) {
    630732      setDigraph(digraph);
    631733      setNodeFilterMap(node_filter);
     
    635737    /// \brief Hides the node of the graph
    636738    ///
    637     /// 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 
     739    /// This function hides \c n in the digraph, i.e. the iteration
     740    /// jumps over it. This is done by simply setting the value of \c n
    639741    /// to be false in the corresponding node-map.
    640742    void hide(const Node& n) const { Parent::hide(n); }
     
    642744    /// \brief Hides the arc of the graph
    643745    ///
    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
    645747    /// jumps over it. This is done by simply setting the value of \c a
    646748    /// to be false in the corresponding arc-map.
     
    649751    /// \brief Unhides the node of the graph
    650752    ///
    651     /// 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 
     753    /// The value of \c n is set to be true in the node-map which stores
     754    /// hide information. If \c n was hidden previuosly, then it is shown
    653755    /// again
    654756    void unHide(const Node& n) const { Parent::unHide(n); }
     
    656758    /// \brief Unhides the arc of the graph
    657759    ///
    658     /// 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 
     760    /// The value of \c a is set to be true in the arc-map which stores
     761    /// hide information. If \c a was hidden previuosly, then it is shown
    660762    /// again
    661763    void unHide(const Arc& a) const { Parent::unHide(a); }
     
    675777  };
    676778
    677   /// \brief Just gives back a sub-digraph-adaptor
    678   ///
    679   /// Just gives back a sub-digraph-adaptor
     779  /// \brief Just gives back a subdigraph
     780  ///
     781  /// Just gives back a subdigraph
    680782  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    681   SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
    682   subDigraphAdaptor(const Digraph& digraph,
    683                     NodeFilterMap& nfm, ArcFilterMap& afm) {
    684     return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
     783  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
     784  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
     785    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
    685786      (digraph, nfm, afm);
    686787  }
    687788
    688789  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    689   SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
    690   subDigraphAdaptor(const Digraph& digraph,
    691                    NodeFilterMap& nfm, ArcFilterMap& afm) {
    692     return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
     790  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
     791  subDigraph(const Digraph& digraph,
     792             const NodeFilterMap& nfm, ArcFilterMap& afm) {
     793    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
    693794      (digraph, nfm, afm);
    694795  }
    695796
    696797  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    697   SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
    698   subDigraphAdaptor(const Digraph& digraph,
    699                    NodeFilterMap& nfm, ArcFilterMap& afm) {
    700     return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
     798  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
     799  subDigraph(const Digraph& digraph,
     800             NodeFilterMap& nfm, const ArcFilterMap& afm) {
     801    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
    701802      (digraph, nfm, afm);
    702803  }
    703804
    704805  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    705   SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
    706   subDigraphAdaptor(const Digraph& digraph,
    707                    NodeFilterMap& nfm, ArcFilterMap& afm) {
    708     return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
     806  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
     807  subDigraph(const Digraph& digraph,
     808             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
     809    return SubDigraph<const Digraph, const NodeFilterMap,
    709810      const ArcFilterMap>(digraph, nfm, afm);
    710 
    711811  }
    712812
    713813
    714 
    715   ///\ingroup graph_adaptors
    716   ///
    717   ///\brief An adaptor for hiding nodes from a digraph.
    718   ///
    719   ///An adaptor for hiding nodes from a digraph.  This adaptor
    720   ///specializes SubDigraphAdaptor in the way that only the node-set
    721   ///can be filtered. In usual case the checked parameter is true, we
    722   ///get the induced subgraph. But if the checked parameter is false
    723   ///then we can filter only isolated nodes.
    724   template<typename _Digraph,
    725            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    726            bool checked = true>
    727   class NodeSubDigraphAdaptor :
    728     public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
    729                              ConstMap<typename _Digraph::Arc, bool>, checked> {
     814  template <typename _Graph, typename NodeFilterMap,
     815            typename EdgeFilterMap, bool _checked = true>
     816  class SubGraphBase : public GraphAdaptorBase<_Graph> {
     817  public:
     818    typedef _Graph Graph;
     819    typedef SubGraphBase Adaptor;
     820    typedef GraphAdaptorBase<_Graph> Parent;
     821  protected:
     822
     823    NodeFilterMap* _node_filter_map;
     824    EdgeFilterMap* _edge_filter_map;
     825
     826    SubGraphBase()
     827      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
     828
     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> {
    7301393  public:
    7311394
     
    7331396    typedef _NodeFilterMap NodeFilterMap;
    7341397
    735     typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
    736                               ConstMap<typename Digraph::Arc, bool>, checked>
     1398    typedef SubDigraph<Digraph, NodeFilterMap,
     1399                       ConstMap<typename Digraph::Arc, bool>, _checked>
    7371400    Parent;
    7381401
     
    7421405    ConstMap<typename Digraph::Arc, bool> const_true_map;
    7431406
    744     NodeSubDigraphAdaptor() : const_true_map(true) {
     1407    FilterNodes() : const_true_map(true) {
    7451408      Parent::setArcFilterMap(const_true_map);
    7461409    }
     
    7501413    /// \brief Constructor
    7511414    ///
    752     /// Creates a node-sub-digraph-adaptor for the given digraph with
    753     /// given node map filter.
    754     NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
    755       Parent(), const_true_map(true) { 
     1415    /// Creates an adaptor for the given digraph or graph with
     1416    /// given node filter map.
     1417    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
     1418      Parent(), const_true_map(true) {
    7561419      Parent::setDigraph(_digraph);
    7571420      Parent::setNodeFilterMap(node_filter);
     
    7611424    /// \brief Hides the node of the graph
    7621425    ///
    763     /// This function hides \c n in the digraph, i.e. the iteration
    764     /// jumps over it. This is done by simply setting the value of \c n 
    765     /// to be false in the corresponding node-map.
     1426    /// This function hides \c n in the digraph or graph, i.e. the iteration
     1427    /// jumps over it. This is done by simply setting the value of \c n
     1428    /// to be false in the corresponding node map.
    7661429    void hide(const Node& n) const { Parent::hide(n); }
    7671430
    7681431    /// \brief Unhides the node of the graph
    7691432    ///
    770     /// 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 
     1433    /// The value of \c n is set to be true in the node-map which stores
     1434    /// hide information. If \c n was hidden previuosly, then it is shown
    7721435    /// again
    7731436    void unHide(const Node& n) const { Parent::unHide(n); }
     
    7811444  };
    7821445
    783 
    784   /// \brief Just gives back a  node-sub-digraph adaptor
    785   ///
    786   /// Just gives back a node-sub-digraph adaptor
     1446  template<typename _Graph, typename _NodeFilterMap, bool _checked>
     1447  class FilterNodes<_Graph, _NodeFilterMap, _checked,
     1448                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
     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
    7871484  template<typename Digraph, typename NodeFilterMap>
    788   NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
    789   nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
    790     return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
     1485  FilterNodes<const Digraph, NodeFilterMap>
     1486  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
     1487    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
    7911488  }
    7921489
    7931490  template<typename Digraph, typename NodeFilterMap>
    794   NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
    795   nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
    796     return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
    797       (digraph, nfm);
     1491  FilterNodes<const Digraph, const NodeFilterMap>
     1492  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
     1493    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
    7981494  }
    7991495
    800   ///\ingroup graph_adaptors
    801   ///
    802   ///\brief An adaptor for hiding arcs from a digraph.
    803   ///
    804   ///An adaptor for hiding arcs from a digraph. This adaptor
    805   ///specializes SubDigraphAdaptor in the way that only the arc-set
    806   ///can be filtered. The usefulness of this adaptor is demonstrated
    807   ///in the problem of searching a maximum number of arc-disjoint
    808   ///shortest paths between two nodes \c s and \c t. Shortest here
    809   ///means being shortest with respect to non-negative
    810   ///arc-lengths. Note that the comprehension of the presented
    811   ///solution need's some elementary knowledge from combinatorial
    812   ///optimization.
    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
     1496  /// \ingroup graph_adaptors
     1497  ///
     1498  /// \brief An adaptor for hiding arcs from a digraph.
     1499  ///
     1500  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
     1501  /// be specified, which defines the filters for arcs. Just the
     1502  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
     1503  /// conform to the \ref concepts::Digraph "Digraph concept".
     1504  ///
     1505  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     1506  /// "Digraph concept". The type can be specified to be const.
     1507  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
     1508  /// graph.
    9281509  template<typename _Digraph, typename _ArcFilterMap>
    929   class ArcSubDigraphAdaptor :
    930     public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
    931                              _ArcFilterMap, false> {
     1510  class FilterArcs :
     1511    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
     1512                      _ArcFilterMap, false> {
    9321513  public:
    9331514    typedef _Digraph Digraph;
    9341515    typedef _ArcFilterMap ArcFilterMap;
    9351516
    936     typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
    937                               ArcFilterMap, false> Parent;
     1517    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
     1518                       ArcFilterMap, false> Parent;
    9381519
    9391520    typedef typename Parent::Arc Arc;
     
    9421523    ConstMap<typename Digraph::Node, bool> const_true_map;
    9431524
    944     ArcSubDigraphAdaptor() : const_true_map(true) {
     1525    FilterArcs() : const_true_map(true) {
    9451526      Parent::setNodeFilterMap(const_true_map);
    9461527    }
     
    9501531    /// \brief Constructor
    9511532    ///
    952     /// Creates a arc-sub-digraph-adaptor for the given digraph with
     1533    /// Creates a FilterArcs adaptor for the given graph with
    9531534    /// given arc map filter.
    954     ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
    955       : Parent(), const_true_map(true) { 
     1535    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
     1536      : Parent(), const_true_map(true) {
    9561537      Parent::setDigraph(digraph);
    9571538      Parent::setNodeFilterMap(const_true_map);
     
    9611542    /// \brief Hides the arc of the graph
    9621543    ///
    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
    9641545    /// 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.
    9661547    void hide(const Arc& a) const { Parent::hide(a); }
    9671548
    9681549    /// \brief Unhides the arc of the graph
    9691550    ///
    970     /// 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 
     1551    /// The value of \c a is set to be true in the arc-map which stores
     1552    /// hide information. If \c a was hidden previuosly, then it is shown
    9721553    /// again
    9731554    void unHide(const Arc& a) const { Parent::unHide(a); }
     
    9811562  };
    9821563
    983   /// \brief Just gives back an arc-sub-digraph adaptor
    984   ///
    985   /// Just gives back an arc-sub-digraph adaptor
     1564  /// \brief Just gives back an FilterArcs adaptor
     1565  ///
     1566  /// Just gives back an FilterArcs adaptor
    9861567  template<typename Digraph, typename ArcFilterMap>
    987   ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
    988   arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
    989     return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
     1568  FilterArcs<const Digraph, ArcFilterMap>
     1569  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
     1570    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
    9901571  }
    9911572
    9921573  template<typename Digraph, typename ArcFilterMap>
    993   ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
    994   arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
    995     return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
    996       (digraph, afm);
     1574  FilterArcs<const Digraph, const ArcFilterMap>
     1575  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
     1576    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
    9971577  }
    9981578
     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
    9991659  template <typename _Digraph>
    1000   class UndirDigraphAdaptorBase {
     1660  class UndirectorBase {
    10011661  public:
    10021662    typedef _Digraph Digraph;
    1003     typedef UndirDigraphAdaptorBase Adaptor;
     1663    typedef UndirectorBase Adaptor;
    10041664
    10051665    typedef True UndirectedTag;
     
    10091669
    10101670    class Arc : public Edge {
    1011       friend class UndirDigraphAdaptorBase;
     1671      friend class UndirectorBase;
    10121672    protected:
    10131673      bool _forward;
     
    10221682
    10231683      bool operator==(const Arc &other) const {
    1024         return _forward == other._forward &&
    1025           static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
     1684        return _forward == other._forward &&
     1685          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
    10261686      }
    10271687      bool operator!=(const Arc &other) const {
    1028         return _forward != other._forward ||
    1029           static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
     1688        return _forward != other._forward ||
     1689          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
    10301690      }
    10311691      bool operator<(const Arc &other) const {
    1032         return _forward < other._forward ||
    1033           (_forward == other._forward &&
    1034            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
     1692        return _forward < other._forward ||
     1693          (_forward == other._forward &&
     1694           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
    10351695      }
    10361696    };
     
    10531713    void next(Arc& a) const {
    10541714      if (a._forward) {
    1055         a._forward = false;
     1715        a._forward = false;
    10561716      } else {
    1057         _digraph->next(a);
    1058         a._forward = true;
     1717        _digraph->next(a);
     1718        a._forward = true;
    10591719      }
    10601720    }
     
    10711731      _digraph->firstIn(a, n);
    10721732      if( static_cast<const Edge&>(a) != INVALID ) {
    1073         a._forward = false;
     1733        a._forward = false;
    10741734      } else {
    1075         _digraph->firstOut(a, n);
    1076         a._forward = true;
     1735        _digraph->firstOut(a, n);
     1736        a._forward = true;
    10771737      }
    10781738    }
    10791739    void nextOut(Arc &a) const {
    10801740      if (!a._forward) {
    1081         Node n = _digraph->target(a);
    1082         _digraph->nextIn(a);
    1083         if (static_cast<const Edge&>(a) == INVALID ) {
    1084           _digraph->firstOut(a, n);
    1085           a._forward = true;
    1086         }
     1741        Node n = _digraph->target(a);
     1742        _digraph->nextIn(a);
     1743        if (static_cast<const Edge&>(a) == INVALID ) {
     1744          _digraph->firstOut(a, n);
     1745          a._forward = true;
     1746        }
    10871747      }
    10881748      else {
    1089         _digraph->nextOut(a);
     1749        _digraph->nextOut(a);
    10901750      }
    10911751    }
     
    10941754      _digraph->firstOut(a, n);
    10951755      if (static_cast<const Edge&>(a) != INVALID ) {
    1096         a._forward = false;
     1756        a._forward = false;
    10971757      } else {
    1098         _digraph->firstIn(a, n);
    1099         a._forward = true;
     1758        _digraph->firstIn(a, n);
     1759        a._forward = true;
    11001760      }
    11011761    }
    11021762    void nextIn(Arc &a) const {
    11031763      if (!a._forward) {
    1104         Node n = _digraph->source(a);
    1105         _digraph->nextOut(a);
    1106         if( static_cast<const Edge&>(a) == INVALID ) {
    1107           _digraph->firstIn(a, n);
    1108           a._forward = true;
    1109         }
     1764        Node n = _digraph->source(a);
     1765        _digraph->nextOut(a);
     1766        if( static_cast<const Edge&>(a) == INVALID ) {
     1767          _digraph->firstIn(a, n);
     1768          a._forward = true;
     1769        }
    11101770      }
    11111771      else {
    1112         _digraph->nextIn(a);
     1772        _digraph->nextIn(a);
    11131773      }
    11141774    }
     
    11241784    void nextInc(Edge &e, bool &d) const {
    11251785      if (d) {
    1126         Node s = _digraph->source(e);
    1127         _digraph->nextOut(e);
    1128         if (e != INVALID) return;
    1129         d = false;
    1130         _digraph->firstIn(e, s);
     1786        Node s = _digraph->source(e);
     1787        _digraph->nextOut(e);
     1788        if (e != INVALID) return;
     1789        d = false;
     1790        _digraph->firstIn(e, s);
    11311791      } else {
    1132         _digraph->nextIn(e);
     1792        _digraph->nextIn(e);
    11331793      }
    11341794    }
     
    11761836
    11771837    Node addNode() { return _digraph->addNode(); }
    1178     Edge addEdge(const Node& u, const Node& v) { 
    1179       return _digraph->addArc(u, v); 
     1838    Edge addEdge(const Node& u, const Node& v) {
     1839      return _digraph->addArc(u, v);
    11801840    }
    11811841
    11821842    void erase(const Node& i) { _digraph->erase(i); }
    11831843    void erase(const Edge& i) { _digraph->erase(i); }
    1184  
     1844
    11851845    void clear() { _digraph->clear(); }
    11861846
     
    11941854    Arc findArc(Node s, Node t, Arc p = INVALID) const {
    11951855      if (p == INVALID) {
    1196         Edge arc = _digraph->findArc(s, t);
    1197         if (arc != INVALID) return direct(arc, true);
    1198         arc = _digraph->findArc(t, s);
    1199         if (arc != INVALID) return direct(arc, false);
     1856        Edge arc = _digraph->findArc(s, t);
     1857        if (arc != INVALID) return direct(arc, true);
     1858        arc = _digraph->findArc(t, s);
     1859        if (arc != INVALID) return direct(arc, false);
    12001860      } else if (direction(p)) {
    1201         Edge arc = _digraph->findArc(s, t, p);
    1202         if (arc != INVALID) return direct(arc, true);
    1203         arc = _digraph->findArc(t, s);
    1204         if (arc != INVALID) return direct(arc, false); 
     1861        Edge arc = _digraph->findArc(s, t, p);
     1862        if (arc != INVALID) return direct(arc, true);
     1863        arc = _digraph->findArc(t, s);
     1864        if (arc != INVALID) return direct(arc, false);
    12051865      } else {
    1206         Edge arc = _digraph->findArc(t, s, p);
    1207         if (arc != INVALID) return direct(arc, false);       
     1866        Edge arc = _digraph->findArc(t, s, p);
     1867        if (arc != INVALID) return direct(arc, false);
    12081868      }
    12091869      return INVALID;
     
    12211881          if (arc != INVALID) return arc;
    12221882          arc = _digraph->findArc(t, s);
    1223           if (arc != INVALID) return arc;       
     1883          if (arc != INVALID) return arc;
    12241884        } else {
    12251885          Edge arc = _digraph->findArc(t, s, p);
    1226           if (arc != INVALID) return arc;             
     1886          if (arc != INVALID) return arc;
    12271887        }
    12281888      } else {
     
    12331893
    12341894  private:
    1235    
     1895
    12361896    template <typename _Value>
    12371897    class ArcMapBase {
    12381898    private:
    1239      
     1899
    12401900      typedef typename Digraph::template ArcMap<_Value> MapImpl;
    1241      
     1901
    12421902    public:
    12431903
     
    12461906      typedef _Value Value;
    12471907      typedef Arc Key;
    1248      
     1908
    12491909      ArcMapBase(const Adaptor& adaptor) :
    1250         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    1251 
    1252       ArcMapBase(const Adaptor& adaptor, const Value& v) 
     1910        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
     1911
     1912      ArcMapBase(const Adaptor& adaptor, const Value& v)
    12531913        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
    1254      
    1255       void set(const Arc& a, const Value& v) {
    1256         if (direction(a)) {
    1257           _forward.set(a, v);
    1258         } else {
    1259           _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];
     1914
     1915      void set(const Arc& a, const Value& v) {
     1916        if (direction(a)) {
     1917          _forward.set(a, v);
     1918        } else {
     1919          _backward.set(a, v);
    12691920        }
    12701921      }
    12711922
    1272       typename MapTraits<MapImpl>::ReturnValue
    1273       operator[](const Arc& a) {
    1274         if (direction(a)) {
    1275           return _forward[a];
    1276         } else {
    1277           return _backward[a];
     1923      typename MapTraits<MapImpl>::ConstReturnValue
     1924      operator[](const Arc& a) const {
     1925        if (direction(a)) {
     1926          return _forward[a];
     1927        } else {
     1928          return _backward[a];
    12781929        }
    12791930      }
    12801931
     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
    12811941    protected:
    12821942
    1283       MapImpl _forward, _backward; 
     1943      MapImpl _forward, _backward;
    12841944
    12851945    };
     
    12941954      typedef typename Digraph::template NodeMap<Value> Parent;
    12951955
    1296       explicit NodeMap(const Adaptor& adaptor) 
    1297         : Parent(*adaptor._digraph) {}
     1956      explicit NodeMap(const Adaptor& adaptor)
     1957        : Parent(*adaptor._digraph) {}
    12981958
    12991959      NodeMap(const Adaptor& adaptor, const _Value& value)
    1300         : Parent(*adaptor._digraph, value) { }
     1960        : Parent(*adaptor._digraph, value) { }
    13011961
    13021962    private:
     
    13101970        return *this;
    13111971      }
    1312      
     1972
    13131973    };
    13141974
    13151975    template <typename _Value>
    1316     class ArcMap 
    1317       : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 
     1976    class ArcMap
     1977      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    13181978    {
    13191979    public:
    13201980      typedef _Value Value;
    13211981      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    1322    
    1323       ArcMap(const Adaptor& adaptor) 
    1324         : Parent(adaptor) {}
    1325 
    1326       ArcMap(const Adaptor& adaptor, const Value& value) 
    1327         : Parent(adaptor, value) {}
    1328    
     1982
     1983      ArcMap(const Adaptor& adaptor)
     1984        : Parent(adaptor) {}
     1985
     1986      ArcMap(const Adaptor& adaptor, const Value& value)
     1987        : Parent(adaptor, value) {}
     1988
    13291989    private:
    13301990      ArcMap& operator=(const ArcMap& cmap) {
    1331         return operator=<ArcMap>(cmap);
    1332       }
    1333    
     1991        return operator=<ArcMap>(cmap);
     1992      }
     1993
    13341994      template <typename CMap>
    13351995      ArcMap& operator=(const CMap& cmap) {
    13361996        Parent::operator=(cmap);
    1337         return *this;
     1997        return *this;
    13381998      }
    13391999    };
    1340        
     2000
    13412001    template <typename _Value>
    13422002    class EdgeMap : public Digraph::template ArcMap<_Value> {
    13432003    public:
    1344      
     2004
    13452005      typedef _Value Value;
    13462006      typedef typename Digraph::template ArcMap<Value> Parent;
    1347      
    1348       explicit EdgeMap(const Adaptor& adaptor) 
    1349         : Parent(*adaptor._digraph) {}
     2007
     2008      explicit EdgeMap(const Adaptor& adaptor)
     2009        : Parent(*adaptor._digraph) {}
    13502010
    13512011      EdgeMap(const Adaptor& adaptor, const Value& value)
    1352         : Parent(*adaptor._digraph, value) {}
     2012        : Parent(*adaptor._digraph, value) {}
    13532013
    13542014    private:
     
    13662026
    13672027    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()); }
    13692029
    13702030  protected:
    13712031
    1372     UndirDigraphAdaptorBase() : _digraph(0) {}
     2032    UndirectorBase() : _digraph(0) {}
    13732033
    13742034    Digraph* _digraph;
     
    13772037      _digraph = &digraph;
    13782038    }
    1379    
     2039
    13802040  };
    13812041
    1382   ///\ingroup graph_adaptors
    1383   ///
    1384   /// \brief A graph is made from a directed digraph by an adaptor
     2042  /// \ingroup graph_adaptors
     2043  ///
     2044  /// \brief Undirect the graph
    13852045  ///
    13862046  /// This adaptor makes an undirected graph from a directed
    1387   /// graph. All arc of the underlying digraph will be showed in the
    1388   /// adaptor as an edge. Let's see an informal example about using
    1389   /// this adaptor.
    1390   ///
    1391   /// There is a network of the streets of a town. Of course there are
    1392   /// some one-way street in the town hence the network is a directed
    1393   /// one. There is a crazy driver who go oppositely in the one-way
    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.
     2047  /// graph. All arcs of the underlying digraph will be showed in the
     2048  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
     2049  /// concepts::Graph "Graph concept".
     2050  ///
     2051  /// \tparam _Digraph It must be conform to the \ref
     2052  /// concepts::Digraph "Digraph concept". The type can be specified
     2053  /// to const.
    14262054  template<typename _Digraph>
    1427   class UndirDigraphAdaptor
    1428     : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
     2055  class Undirector
     2056    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
    14292057  public:
    14302058    typedef _Digraph Digraph;
    1431     typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
     2059    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
    14322060  protected:
    1433     UndirDigraphAdaptor() { }
     2061    Undirector() { }
    14342062  public:
    14352063
    14362064    /// \brief Constructor
    14372065    ///
    1438     /// Constructor
    1439     UndirDigraphAdaptor(_Digraph& _digraph) {
    1440       setDigraph(_digraph);
     2066    /// Creates a undirected graph from the given digraph
     2067    Undirector(_Digraph& digraph) {
     2068      setDigraph(digraph);
    14412069    }
    14422070
     
    14442072    ///
    14452073    /// 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.
    14472075    template <typename _ForwardMap, typename _BackwardMap>
    14482076    class CombinedArcMap {
    14492077    public:
    1450      
     2078
    14512079      typedef _ForwardMap ForwardMap;
    14522080      typedef _BackwardMap BackwardMap;
     
    14572085      typedef typename Parent::Arc Key;
    14582086
    1459       /// \brief Constructor     
     2087      /// \brief Constructor
    14602088      ///
    1461       /// Constructor     
    1462       CombinedArcMap() : _forward(0), _backward(0) {}
    1463 
    1464       /// \brief Constructor     
    1465       ///
    1466       /// Constructor     
    1467       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
     2089      /// Constructor
     2090      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    14682091        : _forward(&forward), _backward(&backward) {}
    1469      
     2092
    14702093
    14712094      /// \brief Sets the value associated with a key.
    14722095      ///
    14732096      /// Sets the value associated with a key.
    1474       void set(const Key& e, const Value& a) { 
    1475         if (Parent::direction(e)) {
    1476           _forward->set(e, a);
    1477         } else { 
    1478           _backward->set(e, a);
    1479         } 
     2097      void set(const Key& e, const Value& a) {
     2098        if (Parent::direction(e)) {
     2099          _forward->set(e, a);
     2100        } else {
     2101          _backward->set(e, a);
     2102        }
    14802103      }
    14812104
     
    14832106      ///
    14842107      /// Returns the value associated with a key.
    1485       typename MapTraits<ForwardMap>::ConstReturnValue 
    1486       operator[](const Key& e) const { 
    1487         if (Parent::direction(e)) {
    1488           return (*_forward)[e];
    1489         } else {
    1490           return (*_backward)[e];
     2108      typename MapTraits<ForwardMap>::ConstReturnValue
     2109      operator[](const Key& e) const {
     2110        if (Parent::direction(e)) {
     2111          return (*_forward)[e];
     2112        } else {
     2113          return (*_backward)[e];
    14912114        }
    14922115      }
     
    14952118      ///
    14962119      /// Returns the value associated with a key.
    1497       typename MapTraits<ForwardMap>::ReturnValue 
    1498       operator[](const Key& e) { 
    1499         if (Parent::direction(e)) {
    1500           return (*_forward)[e];
    1501         } else {
    1502           return (*_backward)[e];
     2120      typename MapTraits<ForwardMap>::ReturnValue
     2121      operator[](const Key& e) {
     2122        if (Parent::direction(e)) {
     2123          return (*_forward)[e];
     2124        } else {
     2125          return (*_backward)[e];
    15032126        }
    15042127      }
    15052128
    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 
    15202129    protected:
    15212130
    15222131      ForwardMap* _forward;
    1523       BackwardMap* _backward; 
     2132      BackwardMap* _backward;
    15242133
    15252134    };
    15262135
     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
    15272166  };
    15282167
    1529   /// \brief Just gives back an undir digraph adaptor
    1530   ///
    1531   /// Just gives back an undir digraph adaptor
     2168  /// \brief Just gives back an undirected view of the given digraph
     2169  ///
     2170  /// Just gives back an undirected view of the given digraph
    15322171  template<typename Digraph>
    1533   UndirDigraphAdaptor<const Digraph>
    1534   undirDigraphAdaptor(const Digraph& digraph) {
    1535     return UndirDigraphAdaptor<const Digraph>(digraph);
     2172  Undirector<const Digraph>
     2173  undirector(const Digraph& digraph) {
     2174    return Undirector<const Digraph>(digraph);
    15362175  }
    15372176
    1538   template<typename _Digraph,
    1539            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    1540            typename _FlowMap = _CapacityMap,
     2177  template <typename _Graph, typename _DirectionMap>
     2178  class OrienterBase {
     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,
    15412501           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  {
    15432511  public:
    15442512
     
    15482516    typedef _Tolerance Tolerance;
    15492517
    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 
    16632518    typedef typename CapacityMap::Value Value;
    1664     typedef ResDigraphAdaptor Adaptor;
     2519    typedef Residual Adaptor;
    16652520
    16662521  protected:
    16672522
    1668     typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
    1669 
    1670     typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
    1671     ForwardFilter;
    1672 
    1673     typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
    1674     BackwardFilter;
    1675 
    1676     typedef typename UndirDigraph::
     2523    typedef Undirector<const Digraph> Undirected;
     2524
     2525    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
     2526                                            FlowMap, Tolerance> ForwardFilter;
     2527
     2528    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
     2529                                             FlowMap, Tolerance> BackwardFilter;
     2530
     2531    typedef typename Undirected::
    16772532    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    16782533
    1679     typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
     2534    typedef FilterArcs<Undirected, ArcFilter> Parent;
    16802535
    16812536    const CapacityMap* _capacity;
    16822537    FlowMap* _flow;
    16832538
    1684     UndirDigraph _graph;
     2539    Undirected _graph;
    16852540    ForwardFilter _forward_filter;
    16862541    BackwardFilter _backward_filter;
    16872542    ArcFilter _arc_filter;
    16882543
    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 
    17012544  public:
    17022545
    17032546    /// \brief Constructor of the residual digraph.
    17042547    ///
    1705     /// Constructor of the residual graph. The parameters are the digraph type,
     2548    /// Constructor of the residual graph. The parameters are the digraph,
    17062549    /// the flow map, the capacity map and a tolerance object.
    1707     ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
    1708                     FlowMap& flow, const Tolerance& tolerance = Tolerance())
     2550    Residual(const Digraph& digraph, const CapacityMap& capacity,
     2551             FlowMap& flow, const Tolerance& tolerance = Tolerance())
    17092552      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
    1710         _forward_filter(capacity, flow, tolerance), 
     2553        _forward_filter(capacity, flow, tolerance),
    17112554        _backward_filter(capacity, flow, tolerance),
    17122555        _arc_filter(_forward_filter, _backward_filter)
     
    17212564    ///
    17222565    /// Gives back the residual capacity of the arc.
    1723     Value rescap(const Arc& arc) const {
    1724       if (UndirDigraph::direction(arc)) {
    1725         return (*_capacity)[arc] - (*_flow)[arc];
     2566    Value residualCapacity(const Arc& a) const {
     2567      if (Undirected::direction(a)) {
     2568        return (*_capacity)[a] - (*_flow)[a];
    17262569      } else {
    1727         return (*_flow)[arc];
    1728       }
    1729     } 
    1730 
    1731     /// \brief Augment on the given arc in the residual digraph.
    1732     ///
    1733     /// Augment on the given arc in the residual digraph. It increase
     2570        return (*_flow)[a];
     2571      }
     2572    }
     2573
     2574    /// \brief Augment on the given arc in the residual graph.
     2575    ///
     2576    /// Augment on the given arc in the residual graph. It increase
    17342577    /// or decrease the flow on the original arc depend on the direction
    17352578    /// of the residual arc.
    1736     void augment(const Arc& e, const Value& a) const {
    1737       if (UndirDigraph::direction(e)) {
    1738         _flow->set(e, (*_flow)[e] + a);
    1739       } else { 
    1740         _flow->set(e, (*_flow)[e] - a);
     2579    void augment(const Arc& a, const Value& v) const {
     2580      if (Undirected::direction(a)) {
     2581        _flow->set(a, (*_flow)[a] + v);
     2582      } else {
     2583        _flow->set(a, (*_flow)[a] - v);
    17412584      }
    17422585    }
     
    17452588    ///
    17462589    /// Returns true when the arc is same oriented as the original arc.
    1747     static bool forward(const Arc& e) {
    1748       return UndirDigraph::direction(e);
     2590    static bool forward(const Arc& a) {
     2591      return Undirected::direction(a);
    17492592    }
    17502593
     
    17522595    ///
    17532596    /// Returns true when the arc is opposite oriented as the original arc.
    1754     static bool backward(const Arc& e) {
    1755       return !UndirDigraph::direction(e);
     2597    static bool backward(const Arc& a) {
     2598      return !Undirected::direction(a);
    17562599    }
    17572600
     
    17592602    ///
    17602603    /// Gives back the forward oriented residual arc.
    1761     static Arc forward(const typename Digraph::Arc& e) {
    1762       return UndirDigraph::direct(e, true);
     2604    static Arc forward(const typename Digraph::Arc& a) {
     2605      return Undirected::direct(a, true);
    17632606    }
    17642607
     
    17662609    ///
    17672610    /// Gives back the backward oriented residual arc.
    1768     static Arc backward(const typename Digraph::Arc& e) {
    1769       return UndirDigraph::direct(e, false);
     2611    static Arc backward(const typename Digraph::Arc& a) {
     2612      return Undirected::direct(a, false);
    17702613    }
    17712614
    17722615    /// \brief Residual capacity map.
    17732616    ///
    1774     /// In generic residual digraphs the residual capacity can be obtained
    1775     /// as a map. 
    1776     class ResCap {
     2617    /// In generic residual graph the residual capacity can be obtained
     2618    /// as a map.
     2619    class ResidualCapacity {
    17772620    protected:
    17782621      const Adaptor* _adaptor;
    17792622    public:
     2623      /// The Key type
    17802624      typedef Arc Key;
     2625      /// The Value type
    17812626      typedef typename _CapacityMap::Value Value;
    17822627
    1783       ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
    1784      
    1785       Value operator[](const Arc& e) const {
    1786         return _adaptor->rescap(e);
    1787       }
    1788      
     2628      /// Constructor
     2629      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
     2630
     2631      /// \e
     2632      Value operator[](const Arc& a) const {
     2633        return _adaptor->residualCapacity(a);
     2634      }
     2635
    17892636    };
    17902637
     
    17922639
    17932640  template <typename _Digraph>
    1794   class SplitDigraphAdaptorBase {
     2641  class SplitNodesBase {
    17952642  public:
    17962643
    17972644    typedef _Digraph Digraph;
    17982645    typedef DigraphAdaptorBase<const _Digraph> Parent;
    1799     typedef SplitDigraphAdaptorBase Adaptor;
     2646    typedef SplitNodesBase Adaptor;
    18002647
    18012648    typedef typename Digraph::Node DigraphNode;
     
    18112658
    18122659  public:
    1813    
     2660
    18142661    class Node : public DigraphNode {
    1815       friend class SplitDigraphAdaptorBase;
     2662      friend class SplitNodesBase;
    18162663      template <typename T> friend class NodeMapBase;
    18172664    private:
     
    18192666      bool _in;
    18202667      Node(DigraphNode node, bool in)
    1821         : DigraphNode(node), _in(in) {}
    1822      
     2668        : DigraphNode(node), _in(in) {}
     2669
    18232670    public:
    18242671
     
    18272674
    18282675      bool operator==(const Node& node) const {
    1829         return DigraphNode::operator==(node) && _in == node._in;
    1830       }
    1831      
     2676        return DigraphNode::operator==(node) && _in == node._in;
     2677      }
     2678
    18322679      bool operator!=(const Node& node) const {
    1833         return !(*this == node);
    1834       }
    1835      
     2680        return !(*this == node);
     2681      }
     2682
    18362683      bool operator<(const Node& node) const {
    1837         return DigraphNode::operator<(node) ||
    1838           (DigraphNode::operator==(node) && _in < node._in);
     2684        return DigraphNode::operator<(node) ||
     2685          (DigraphNode::operator==(node) && _in < node._in);
    18392686      }
    18402687    };
    18412688
    18422689    class Arc {
    1843       friend class SplitDigraphAdaptorBase;
     2690      friend class SplitNodesBase;
    18442691      template <typename T> friend class ArcMapBase;
    18452692    private:
     
    18482695      explicit Arc(const DigraphArc& arc) : _item(arc) {}
    18492696      explicit Arc(const DigraphNode& node) : _item(node) {}
    1850      
     2697
    18512698      ArcImpl _item;
    18522699
     
    18672714        return false;
    18682715      }
    1869      
     2716
    18702717      bool operator!=(const Arc& arc) const {
    1871         return !(*this == arc);
    1872       }
    1873      
     2718        return !(*this == arc);
     2719      }
     2720
    18742721      bool operator<(const Arc& arc) const {
    18752722        if (_item.firstState()) {
     
    18982745    void next(Node& n) const {
    18992746      if (n._in) {
    1900         n._in = false;
     2747        n._in = false;
    19012748      } else {
    1902         n._in = true;
    1903         _digraph->next(n);
     2749        n._in = true;
     2750        _digraph->next(n);
    19042751      }
    19052752    }
     
    19102757      if (e._item.second() == INVALID) {
    19112758        e._item.setFirst();
    1912         _digraph->first(e._item.first());
     2759        _digraph->first(e._item.first());
    19132760      }
    19142761    }
     
    19162763    void next(Arc& e) const {
    19172764      if (e._item.secondState()) {
    1918         _digraph->next(e._item.second());
     2765        _digraph->next(e._item.second());
    19192766        if (e._item.second() == INVALID) {
    19202767          e._item.setFirst();
     
    19222769        }
    19232770      } else {
    1924         _digraph->next(e._item.first());
    1925       }     
     2771        _digraph->next(e._item.first());
     2772      }
    19262773    }
    19272774
     
    19312778      } else {
    19322779        e._item.setFirst();
    1933         _digraph->firstOut(e._item.first(), n);
     2780        _digraph->firstOut(e._item.first(), n);
    19342781      }
    19352782    }
     
    19372784    void nextOut(Arc& e) const {
    19382785      if (!e._item.firstState()) {
    1939         e._item.setFirst(INVALID);
     2786        e._item.setFirst(INVALID);
    19402787      } else {
    1941         _digraph->nextOut(e._item.first());
    1942       }     
     2788        _digraph->nextOut(e._item.first());
     2789      }
    19432790    }
    19442791
    19452792    void firstIn(Arc& e, const Node& n) const {
    19462793      if (!n._in) {
    1947         e._item.setSecond(n);       
     2794        e._item.setSecond(n);
    19482795      } else {
    19492796        e._item.setFirst();
    1950         _digraph->firstIn(e._item.first(), n);
     2797        _digraph->firstIn(e._item.first(), n);
    19512798      }
    19522799    }
     
    19542801    void nextIn(Arc& e) const {
    19552802      if (!e._item.firstState()) {
    1956         e._item.setFirst(INVALID);
     2803        e._item.setFirst(INVALID);
    19572804      } else {
    1958         _digraph->nextIn(e._item.first());
     2805        _digraph->nextIn(e._item.first());
    19592806      }
    19602807    }
     
    19622809    Node source(const Arc& e) const {
    19632810      if (e._item.firstState()) {
    1964         return Node(_digraph->source(e._item.first()), false);
     2811        return Node(_digraph->source(e._item.first()), false);
    19652812      } else {
    1966         return Node(e._item.second(), true);
     2813        return Node(e._item.second(), true);
    19672814      }
    19682815    }
     
    19702817    Node target(const Arc& e) const {
    19712818      if (e._item.firstState()) {
    1972         return Node(_digraph->target(e._item.first()), true);
     2819        return Node(_digraph->target(e._item.first()), true);
    19732820      } else {
    1974         return Node(e._item.second(), false);
     2821        return Node(e._item.second(), false);
    19752822      }
    19762823    }
     
    20012848    }
    20022849    int maxArcId() const {
    2003       return std::max(_digraph->maxNodeId() << 1, 
     2850      return std::max(_digraph->maxNodeId() << 1,
    20042851                      (_digraph->maxArcId() << 1) | 1);
    20052852    }
     
    20492896
    20502897    typedef True FindEdgeTag;
    2051     Arc findArc(const Node& u, const Node& v, 
    2052                 const Arc& prev = INVALID) const {
     2898    Arc findArc(const Node& u, const Node& v,
     2899                const Arc& prev = INVALID) const {
    20532900      if (inNode(u)) {
    20542901        if (outNode(v)) {
    2055           if (static_cast<const DigraphNode&>(u) == 
     2902          if (static_cast<const DigraphNode&>(u) ==
    20562903              static_cast<const DigraphNode&>(v) && prev == INVALID) {
    20572904            return Arc(u);
     
    20672914
    20682915  private:
    2069    
     2916
    20702917    template <typename _Value>
    2071     class NodeMapBase 
     2918    class NodeMapBase
    20722919      : public MapTraits<typename Parent::template NodeMap<_Value> > {
    20732920      typedef typename Parent::template NodeMap<_Value> NodeImpl;
     
    20752922      typedef Node Key;
    20762923      typedef _Value Value;
    2077      
    2078       NodeMapBase(const Adaptor& adaptor) 
    2079         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    2080       NodeMapBase(const Adaptor& adaptor, const Value& value) 
    2081         : _in_map(*adaptor._digraph, value),
    2082           _out_map(*adaptor._digraph, value) {}
     2924
     2925      NodeMapBase(const Adaptor& adaptor)
     2926        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
     2927      NodeMapBase(const Adaptor& adaptor, const Value& value)
     2928        : _in_map(*adaptor._digraph, value),
     2929          _out_map(*adaptor._digraph, value) {}
    20832930
    20842931      void set(const Node& key, const Value& val) {
    2085         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
    2086         else {_out_map.set(key, val); }
    2087       }
    2088      
    2089       typename MapTraits<NodeImpl>::ReturnValue 
     2932        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
     2933        else {_out_map.set(key, val); }
     2934      }
     2935
     2936      typename MapTraits<NodeImpl>::ReturnValue
    20902937      operator[](const Node& key) {
    2091         if (Adaptor::inNode(key)) { return _in_map[key]; }
    2092         else { return _out_map[key]; }
     2938        if (Adaptor::inNode(key)) { return _in_map[key]; }
     2939        else { return _out_map[key]; }
    20932940      }
    20942941
    20952942      typename MapTraits<NodeImpl>::ConstReturnValue
    20962943      operator[](const Node& key) const {
    2097         if (Adaptor::inNode(key)) { return _in_map[key]; }
    2098         else { return _out_map[key]; }
     2944        if (Adaptor::inNode(key)) { return _in_map[key]; }
     2945        else { return _out_map[key]; }
    20992946      }
    21002947
     
    21042951
    21052952    template <typename _Value>
    2106     class ArcMapBase 
     2953    class ArcMapBase
    21072954      : public MapTraits<typename Parent::template ArcMap<_Value> > {
    21082955      typedef typename Parent::template ArcMap<_Value> ArcImpl;
     
    21122959      typedef _Value Value;
    21132960
    2114       ArcMapBase(const Adaptor& adaptor) 
    2115         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    2116       ArcMapBase(const Adaptor& adaptor, const Value& value) 
    2117         : _arc_map(*adaptor._digraph, value),
    2118           _node_map(*adaptor._digraph, value) {}
     2961      ArcMapBase(const Adaptor& adaptor)
     2962        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
     2963      ArcMapBase(const Adaptor& adaptor, const Value& value)
     2964        : _arc_map(*adaptor._digraph, value),
     2965          _node_map(*adaptor._digraph, value) {}
    21192966
    21202967      void set(const Arc& key, const Value& val) {
    2121         if (Adaptor::origArc(key)) {
    2122           _arc_map.set(key._item.first(), val); 
     2968        if (Adaptor::origArc(key)) {
     2969          _arc_map.set(key._item.first(), val);
    21232970        } else {
    2124           _node_map.set(key._item.second(), val); 
     2971          _node_map.set(key._item.second(), val);
    21252972        }
    21262973      }
    2127      
     2974
    21282975      typename MapTraits<ArcImpl>::ReturnValue
    21292976      operator[](const Arc& key) {
    2130         if (Adaptor::origArc(key)) {
     2977        if (Adaptor::origArc(key)) {
    21312978          return _arc_map[key._item.first()];
    21322979        } else {
     
    21372984      typename MapTraits<ArcImpl>::ConstReturnValue
    21382985      operator[](const Arc& key) const {
    2139         if (Adaptor::origArc(key)) {
     2986        if (Adaptor::origArc(key)) {
    21402987          return _arc_map[key._item.first()];
    21412988        } else {
     
    21522999
    21533000    template <typename _Value>
    2154     class NodeMap 
    2155       : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 
     3001    class NodeMap
     3002      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
    21563003    {
    21573004    public:
    21583005      typedef _Value Value;
    21593006      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
    2160    
    2161       NodeMap(const Adaptor& adaptor) 
    2162         : Parent(adaptor) {}
    2163 
    2164       NodeMap(const Adaptor& adaptor, const Value& value) 
    2165         : Parent(adaptor, value) {}
    2166    
     3007
     3008      NodeMap(const Adaptor& adaptor)
     3009        : Parent(adaptor) {}
     3010
     3011      NodeMap(const Adaptor& adaptor, const Value& value)
     3012        : Parent(adaptor, value) {}
     3013
    21673014    private:
    21683015      NodeMap& operator=(const NodeMap& cmap) {
    2169         return operator=<NodeMap>(cmap);
    2170       }
    2171    
     3016        return operator=<NodeMap>(cmap);
     3017      }
     3018
    21723019      template <typename CMap>
    21733020      NodeMap& operator=(const CMap& cmap) {
    21743021        Parent::operator=(cmap);
    2175         return *this;
     3022        return *this;
    21763023      }
    21773024    };
    21783025
    21793026    template <typename _Value>
    2180     class ArcMap 
    2181       : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 
     3027    class ArcMap
     3028      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    21823029    {
    21833030    public:
    21843031      typedef _Value Value;
    21853032      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    2186    
    2187       ArcMap(const Adaptor& adaptor) 
    2188         : Parent(adaptor) {}
    2189 
    2190       ArcMap(const Adaptor& adaptor, const Value& value) 
    2191         : Parent(adaptor, value) {}
    2192    
     3033
     3034      ArcMap(const Adaptor& adaptor)
     3035        : Parent(adaptor) {}
     3036
     3037      ArcMap(const Adaptor& adaptor, const Value& value)
     3038        : Parent(adaptor, value) {}
     3039
    21933040    private:
    21943041      ArcMap& operator=(const ArcMap& cmap) {
    2195         return operator=<ArcMap>(cmap);
    2196       }
    2197    
     3042        return operator=<ArcMap>(cmap);
     3043      }
     3044
    21983045      template <typename CMap>
    21993046      ArcMap& operator=(const CMap& cmap) {
    22003047        Parent::operator=(cmap);
    2201         return *this;
     3048        return *this;
    22023049      }
    22033050    };
     
    22053052  protected:
    22063053
    2207     SplitDigraphAdaptorBase() : _digraph(0) {}
     3054    SplitNodesBase() : _digraph(0) {}
    22083055
    22093056    Digraph* _digraph;
     
    22123059      _digraph = &digraph;
    22133060    }
    2214    
     3061
    22153062  };
    22163063
    22173064  /// \ingroup graph_adaptors
    22183065  ///
    2219   /// \brief Split digraph adaptor class
    2220   /// 
    2221   /// This is an digraph adaptor which splits all node into an in-node
    2222   /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
    2223   /// node in the digraph with two node, \f$ u_{in} \f$ node and
    2224   /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
    2225   /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
    2226   /// similarly the source of the original \f$ (u, v) \f$ arc will be
    2227   /// \f$ u_{out} \f$.  The adaptor will add for each node in the
    2228   /// original digraph an additional arc which will connect
     3066  /// \brief Split the nodes of a directed graph
     3067  ///
     3068  /// The SplitNodes adaptor splits each node into an in-node and an
     3069  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
     3070  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
     3071  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
     3072  /// original digraph the new target of the arc will be \f$ u_{in} \f$
     3073  /// and similarly the source of the original \f$ (u, v) \f$ arc
     3074  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
     3075  /// the original digraph an additional arc which connects
    22293076  /// \f$ (u_{in}, u_{out}) \f$.
    22303077  ///
    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
    22323079  /// 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
    2234   /// bind arc in the adapted digraph.
    2235   ///
    2236   /// For example a maximum flow algorithm can compute how many arc
    2237   /// disjoint paths are in the digraph. But we would like to know how
    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
     3080  /// a \c SplitNodes and set the node cost of the graph to the
     3081  /// bind arc in the adapted graph.
     3082  ///
     3083  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     3084  /// "Digraph concept". The type can be specified to be const.
    22843085  template <typename _Digraph>
    2285   class SplitDigraphAdaptor
    2286     : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
     3086  class SplitNodes
     3087    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
    22873088  public:
    22883089    typedef _Digraph Digraph;
    2289     typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
     3090    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
    22903091
    22913092    typedef typename Digraph::Node DigraphNode;
     
    22983099    ///
    22993100    /// Constructor of the adaptor.
    2300     SplitDigraphAdaptor(Digraph& g) {
     3101    SplitNodes(Digraph& g) {
    23013102      Parent::setDigraph(g);
    23023103    }
     
    23453146
    23463147    /// \brief Gives back the arc binds the two part of the node.
    2347     /// 
     3148    ///
    23483149    /// Gives back the arc binds the two part of the node.
    23493150    static Arc arc(const DigraphNode& n) {
     
    23523153
    23533154    /// \brief Gives back the arc of the original arc.
    2354     /// 
     3155    ///
    23553156    /// Gives back the arc of the original arc.
    23563157    static Arc arc(const DigraphArc& a) {
     
    23723173      ///
    23733174      /// Constructor.
    2374       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 
    2375         : _in_map(in_map), _out_map(out_map) {}
     3175      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
     3176        : _in_map(in_map), _out_map(out_map) {}
    23763177
    23773178      /// \brief The subscript operator.
     
    23793180      /// The subscript operator.
    23803181      Value& operator[](const Key& key) {
    2381         if (Parent::inNode(key)) {
    2382           return _in_map[key];
    2383         } else {
    2384           return _out_map[key];
    2385         }
     3182        if (Parent::inNode(key)) {
     3183          return _in_map[key];
     3184        } else {
     3185          return _out_map[key];
     3186        }
    23863187      }
    23873188
     
    23903191      /// The const subscript operator.
    23913192      Value operator[](const Key& key) const {
    2392         if (Parent::inNode(key)) {
    2393           return _in_map[key];
    2394         } else {
    2395           return _out_map[key];
    2396         }
     3193        if (Parent::inNode(key)) {
     3194          return _in_map[key];
     3195        } else {
     3196          return _out_map[key];
     3197        }
    23973198      }
    23983199
    23993200      /// \brief The setter function of the map.
    2400       /// 
     3201      ///
    24013202      /// The setter function of the map.
    24023203      void set(const Key& key, const Value& value) {
    2403         if (Parent::inNode(key)) {
    2404           _in_map.set(key, value);
    2405         } else {
    2406           _out_map.set(key, value);
    2407         }
    2408       }
    2409      
     3204        if (Parent::inNode(key)) {
     3205          _in_map.set(key, value);
     3206        } else {
     3207          _out_map.set(key, value);
     3208        }
     3209      }
     3210
    24103211    private:
    2411      
     3212
    24123213      InNodeMap& _in_map;
    24133214      OutNodeMap& _out_map;
    2414      
     3215
    24153216    };
    24163217
    24173218
    2418     /// \brief Just gives back a combined node map.
    2419     /// 
    2420     /// Just gives back a combined node map.
     3219    /// \brief Just gives back a combined node map
     3220    ///
     3221    /// Just gives back a combined node map
    24213222    template <typename InNodeMap, typename OutNodeMap>
    2422     static CombinedNodeMap<InNodeMap, OutNodeMap> 
     3223    static CombinedNodeMap<InNodeMap, OutNodeMap>
    24233224    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
    24243225      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
     
    24263227
    24273228    template <typename InNodeMap, typename OutNodeMap>
    2428     static CombinedNodeMap<const InNodeMap, OutNodeMap> 
     3229    static CombinedNodeMap<const InNodeMap, OutNodeMap>
    24293230    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
    24303231      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
     
    24323233
    24333234    template <typename InNodeMap, typename OutNodeMap>
    2434     static CombinedNodeMap<InNodeMap, const OutNodeMap> 
     3235    static CombinedNodeMap<InNodeMap, const OutNodeMap>
    24353236    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
    24363237      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
     
    24383239
    24393240    template <typename InNodeMap, typename OutNodeMap>
    2440     static CombinedNodeMap<const InNodeMap, const OutNodeMap> 
     3241    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
    24413242    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
    2442       return CombinedNodeMap<const InNodeMap, 
     3243      return CombinedNodeMap<const InNodeMap,
    24433244        const OutNodeMap>(in_map, out_map);
    24443245    }
    24453246
    2446     /// \brief ArcMap combined from an original ArcMap and NodeMap
    2447     ///
    2448     /// This class adapt an original digraph ArcMap and NodeMap to
    2449     /// get an arc map on the adapted digraph.
     3247    /// \brief ArcMap combined from an original ArcMap and a NodeMap
     3248    ///
     3249    /// This class adapt an original ArcMap and a NodeMap to get an
     3250    /// arc map on the adapted digraph
    24503251    template <typename DigraphArcMap, typename DigraphNodeMap>
    24513252    class CombinedArcMap {
    24523253    public:
    2453      
     3254
    24543255      typedef Arc Key;
    24553256      typedef typename DigraphArcMap::Value Value;
    2456      
     3257
    24573258      /// \brief Constructor
    24583259      ///
    24593260      /// Constructor.
    2460       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 
    2461         : _arc_map(arc_map), _node_map(node_map) {}
     3261      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
     3262        : _arc_map(arc_map), _node_map(node_map) {}
    24623263
    24633264      /// \brief The subscript operator.
     
    24653266      /// The subscript operator.
    24663267      void set(const Arc& arc, const Value& val) {
    2467         if (Parent::origArc(arc)) {
    2468           _arc_map.set(arc, val);
    2469         } else {
    2470           _node_map.set(arc, val);
    2471         }
     3268        if (Parent::origArc(arc)) {
     3269          _arc_map.set(arc, val);
     3270        } else {
     3271          _node_map.set(arc, val);
     3272        }
    24723273      }
    24733274
     
    24763277      /// The const subscript operator.
    24773278      Value operator[](const Key& arc) const {
    2478         if (Parent::origArc(arc)) {
    2479           return _arc_map[arc];
    2480         } else {
    2481           return _node_map[arc];
    2482         }
    2483       }     
     3279        if (Parent::origArc(arc)) {
     3280          return _arc_map[arc];
     3281        } else {
     3282          return _node_map[arc];
     3283        }
     3284      }
    24843285
    24853286      /// \brief The const subscript operator.
     
    24873288      /// The const subscript operator.
    24883289      Value& operator[](const Key& arc) {
    2489         if (Parent::origArc(arc)) {
    2490           return _arc_map[arc];
    2491         } else {
    2492           return _node_map[arc];
    2493         }
    2494       }     
    2495      
     3290        if (Parent::origArc(arc)) {
     3291          return _arc_map[arc];
     3292        } else {
     3293          return _node_map[arc];
     3294        }
     3295      }
     3296
    24963297    private:
    24973298      DigraphArcMap& _arc_map;
    24983299      DigraphNodeMap& _node_map;
    24993300    };
    2500                    
    2501     /// \brief Just gives back a combined arc map.
    2502     /// 
    2503     /// Just gives back a combined arc map.
     3301
     3302    /// \brief Just gives back a combined arc map
     3303    ///
     3304    /// Just gives back a combined arc map
    25043305    template <typename DigraphArcMap, typename DigraphNodeMap>
    2505     static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 
     3306    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
    25063307    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
    25073308      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
     
    25093310
    25103311    template <typename DigraphArcMap, typename DigraphNodeMap>
    2511     static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 
     3312    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
    25123313    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
    2513       return CombinedArcMap<const DigraphArcMap, 
     3314      return CombinedArcMap<const DigraphArcMap,
    25143315        DigraphNodeMap>(arc_map, node_map);
    25153316    }
    25163317
    25173318    template <typename DigraphArcMap, typename DigraphNodeMap>
    2518     static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 
     3319    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
    25193320    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
    2520       return CombinedArcMap<DigraphArcMap, 
     3321      return CombinedArcMap<DigraphArcMap,
    25213322        const DigraphNodeMap>(arc_map, node_map);
    25223323    }
    25233324
    25243325    template <typename DigraphArcMap, typename DigraphNodeMap>
    2525     static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 
    2526     combinedArcMap(const DigraphArcMap& arc_map, 
    2527                     const DigraphNodeMap& node_map) {
    2528       return CombinedArcMap<const DigraphArcMap, 
     3326    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
     3327    combinedArcMap(const DigraphArcMap& arc_map,
     3328                   const DigraphNodeMap& node_map) {
     3329      return CombinedArcMap<const DigraphArcMap,
    25293330        const DigraphNodeMap>(arc_map, node_map);
    25303331    }
     
    25323333  };
    25333334
    2534   /// \brief Just gives back a split digraph adaptor
    2535   ///
    2536   /// Just gives back a split digraph adaptor
     3335  /// \brief Just gives back a node splitter
     3336  ///
     3337  /// Just gives back a node splitter
    25373338  template<typename Digraph>
    2538   SplitDigraphAdaptor<Digraph>
    2539   splitDigraphAdaptor(const Digraph& digraph) {
    2540     return SplitDigraphAdaptor<Digraph>(digraph);
     3339  SplitNodes<Digraph>
     3340  splitNodes(const Digraph& digraph) {
     3341    return SplitNodes<Digraph>(digraph);
    25413342  }
    25423343
     
    25443345} //namespace lemon
    25453346
    2546 #endif //LEMON_DIGRAPH_ADAPTOR_H
    2547 
     3347#endif //LEMON_ADAPTORS_H
  • lemon/bits/graph_adaptor_extender.h

    r414 r416  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    2525#include <lemon/bits/default_map.h>
    2626
    27 
    28 ///\ingroup digraphbits
    29 ///\file
    30 ///\brief Extenders for the digraph adaptor types
    3127namespace lemon {
    3228
    33   /// \ingroup digraphbits
    34   ///
    35   /// \brief Extender for the DigraphAdaptors
    3629  template <typename _Digraph>
    3730  class DigraphAdaptorExtender : public _Digraph {
     
    6558    Node oppositeNode(const Node &n, const Arc &e) const {
    6659      if (n == Parent::source(e))
    67         return Parent::target(e);
     60        return Parent::target(e);
    6861      else if(n==Parent::target(e))
    69         return Parent::source(e);
     62        return Parent::source(e);
    7063      else
    71         return INVALID;
    72     }
    73 
    74     class NodeIt : public Node { 
     64        return INVALID;
     65    }
     66
     67    class NodeIt : public Node {
    7568      const Adaptor* _adaptor;
    7669    public:
     
    8174
    8275      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    83         _adaptor->first(static_cast<Node&>(*this));
    84       }
    85 
    86       NodeIt(const Adaptor& adaptor, const Node& node) 
    87         : Node(node), _adaptor(&adaptor) {}
    88 
    89       NodeIt& operator++() { 
    90         _adaptor->next(*this);
    91         return *this;
    92       }
    93 
    94     };
    95 
    96 
    97     class ArcIt : public Arc { 
     76        _adaptor->first(static_cast<Node&>(*this));
     77      }
     78
     79      NodeIt(const Adaptor& adaptor, const Node& node)
     80        : Node(node), _adaptor(&adaptor) {}
     81
     82      NodeIt& operator++() {
     83        _adaptor->next(*this);
     84        return *this;
     85      }
     86
     87    };
     88
     89
     90    class ArcIt : public Arc {
    9891      const Adaptor* _adaptor;
    9992    public:
     
    10497
    10598      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    106         _adaptor->first(static_cast<Arc&>(*this));
    107       }
    108 
    109       ArcIt(const Adaptor& adaptor, const Arc& e) : 
    110         Arc(e), _adaptor(&adaptor) { }
    111 
    112       ArcIt& operator++() { 
    113         _adaptor->next(*this);
    114         return *this;
    115       }
    116 
    117     };
    118 
    119 
    120     class OutArcIt : public Arc { 
     99        _adaptor->first(static_cast<Arc&>(*this));
     100      }
     101
     102      ArcIt(const Adaptor& adaptor, const Arc& e) :
     103        Arc(e), _adaptor(&adaptor) { }
     104
     105      ArcIt& operator++() {
     106        _adaptor->next(*this);
     107        return *this;
     108      }
     109
     110    };
     111
     112
     113    class OutArcIt : public Arc {
    121114      const Adaptor* _adaptor;
    122115    public:
     
    126119      OutArcIt(Invalid i) : Arc(i) { }
    127120
    128       OutArcIt(const Adaptor& adaptor, const Node& node) 
    129         : _adaptor(&adaptor) {
    130         _adaptor->firstOut(*this, node);
    131       }
    132 
    133       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
    134         : Arc(arc), _adaptor(&adaptor) {}
    135 
    136       OutArcIt& operator++() { 
    137         _adaptor->nextOut(*this);
    138         return *this;
    139       }
    140 
    141     };
    142 
    143 
    144     class InArcIt : public Arc { 
     121      OutArcIt(const Adaptor& adaptor, const Node& node)
     122        : _adaptor(&adaptor) {
     123        _adaptor->firstOut(*this, node);
     124      }
     125
     126      OutArcIt(const Adaptor& adaptor, const Arc& arc)
     127        : Arc(arc), _adaptor(&adaptor) {}
     128
     129      OutArcIt& operator++() {
     130        _adaptor->nextOut(*this);
     131        return *this;
     132      }
     133
     134    };
     135
     136
     137    class InArcIt : public Arc {
    145138      const Adaptor* _adaptor;
    146139    public:
     
    150143      InArcIt(Invalid i) : Arc(i) { }
    151144
    152       InArcIt(const Adaptor& adaptor, const Node& node)
    153         : _adaptor(&adaptor) {
    154         _adaptor->firstIn(*this, node);
    155       }
    156 
    157       InArcIt(const Adaptor& adaptor, const Arc& arc) :
    158         Arc(arc), _adaptor(&adaptor) {}
    159 
    160       InArcIt& operator++() {
    161         _adaptor->nextIn(*this);
    162         return *this;
    163       }
    164 
    165     };
    166 
    167     /// \brief Base node of the iterator
    168     ///
    169     /// Returns the base node (ie. the source in this case) of the iterator
     145      InArcIt(const Adaptor& adaptor, const Node& node)
     146        : _adaptor(&adaptor) {
     147        _adaptor->firstIn(*this, node);
     148      }
     149
     150      InArcIt(const Adaptor& adaptor, const Arc& arc) :
     151        Arc(arc), _adaptor(&adaptor) {}
     152
     153      InArcIt& operator++() {
     154        _adaptor->nextIn(*this);
     155        return *this;
     156      }
     157
     158    };
     159
    170160    Node baseNode(const OutArcIt &e) const {
    171161      return Parent::source(e);
    172162    }
    173     /// \brief Running node of the iterator
    174     ///
    175     /// Returns the running node (ie. the target in this case) of the
    176     /// iterator
    177163    Node runningNode(const OutArcIt &e) const {
    178164      return Parent::target(e);
    179165    }
    180166
    181     /// \brief Base node of the iterator
    182     ///
    183     /// Returns the base node (ie. the target in this case) of the iterator
    184167    Node baseNode(const InArcIt &e) const {
    185168      return Parent::target(e);
    186169    }
    187     /// \brief Running node of the iterator
    188     ///
    189     /// Returns the running node (ie. the source in this case) of the
    190     /// iterator
    191170    Node runningNode(const InArcIt &e) const {
    192171      return Parent::source(e);
     
    199178  ///
    200179  /// \brief Extender for the GraphAdaptors
    201   template <typename _Graph> 
     180  template <typename _Graph>
    202181  class GraphAdaptorExtender : public _Graph {
    203182  public:
    204    
     183
    205184    typedef _Graph Parent;
    206185    typedef _Graph Graph;
     
    211190    typedef typename Parent::Edge Edge;
    212191
    213     // Graph extension   
     192    // Graph extension
    214193
    215194    int maxId(Node) const {
     
    239218    Node oppositeNode(const Node &n, const Edge &e) const {
    240219      if( n == Parent::u(e))
    241         return Parent::v(e);
     220        return Parent::v(e);
    242221      else if( n == Parent::v(e))
    243         return Parent::u(e);
     222        return Parent::u(e);
    244223      else
    245         return INVALID;
     224        return INVALID;
    246225    }
    247226
     
    256235
    257236
    258     class NodeIt : public Node { 
     237    class NodeIt : public Node {
    259238      const Adaptor* _adaptor;
    260239    public:
     
    265244
    266245      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    267         _adaptor->first(static_cast<Node&>(*this));
    268       }
    269 
    270       NodeIt(const Adaptor& adaptor, const Node& node) 
    271         : Node(node), _adaptor(&adaptor) {}
    272 
    273       NodeIt& operator++() { 
    274         _adaptor->next(*this);
    275         return *this;
    276       }
    277 
    278     };
    279 
    280 
    281     class ArcIt : public Arc { 
     246        _adaptor->first(static_cast<Node&>(*this));
     247      }
     248
     249      NodeIt(const Adaptor& adaptor, const Node& node)
     250        : Node(node), _adaptor(&adaptor) {}
     251
     252      NodeIt& operator++() {
     253        _adaptor->next(*this);
     254        return *this;
     255      }
     256
     257    };
     258
     259
     260    class ArcIt : public Arc {
    282261      const Adaptor* _adaptor;
    283262    public:
     
    288267
    289268      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    290         _adaptor->first(static_cast<Arc&>(*this));
    291       }
    292 
    293       ArcIt(const Adaptor& adaptor, const Arc& e) : 
    294         Arc(e), _adaptor(&adaptor) { }
    295 
    296       ArcIt& operator++() { 
    297         _adaptor->next(*this);
    298         return *this;
    299       }
    300 
    301     };
    302 
    303 
    304     class OutArcIt : public Arc { 
     269        _adaptor->first(static_cast<Arc&>(*this));
     270      }
     271
     272      ArcIt(const Adaptor& adaptor, const Arc& e) :
     273        Arc(e), _adaptor(&adaptor) { }
     274
     275      ArcIt& operator++() {
     276        _adaptor->next(*this);
     277        return *this;
     278      }
     279
     280    };
     281
     282
     283    class OutArcIt : public Arc {
    305284      const Adaptor* _adaptor;
    306285    public:
     
    310289      OutArcIt(Invalid i) : Arc(i) { }
    311290
    312       OutArcIt(const Adaptor& adaptor, const Node& node) 
    313         : _adaptor(&adaptor) {
    314         _adaptor->firstOut(*this, node);
    315       }
    316 
    317       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
    318         : Arc(arc), _adaptor(&adaptor) {}
    319 
    320       OutArcIt& operator++() { 
    321         _adaptor->nextOut(*this);
    322         return *this;
    323       }
    324 
    325     };
    326 
    327 
    328     class InArcIt : public Arc { 
     291      OutArcIt(const Adaptor& adaptor, const Node& node)
     292        : _adaptor(&adaptor) {
     293        _adaptor->firstOut(*this, node);
     294      }
     295
     296      OutArcIt(const Adaptor& adaptor, const Arc& arc)
     297        : Arc(arc), _adaptor(&adaptor) {}
     298
     299      OutArcIt& operator++() {
     300        _adaptor->nextOut(*this);
     301        return *this;
     302      }
     303
     304    };
     305
     306
     307    class InArcIt : public Arc {
    329308      const Adaptor* _adaptor;
    330309    public:
     
    334313      InArcIt(Invalid i) : Arc(i) { }
    335314
    336       InArcIt(const Adaptor& adaptor, const Node& node) 
    337         : _adaptor(&adaptor) {
    338         _adaptor->firstIn(*this, node);
    339       }
    340 
    341       InArcIt(const Adaptor& adaptor, const Arc& arc) : 
    342         Arc(arc), _adaptor(&adaptor) {}
    343 
    344       InArcIt& operator++() { 
    345         _adaptor->nextIn(*this);
    346         return *this;
    347       }
    348 
    349     };
    350 
    351     class EdgeIt : public Parent::Edge { 
     315      InArcIt(const Adaptor& adaptor, const Node& node)
     316        : _adaptor(&adaptor) {
     317        _adaptor->firstIn(*this, node);
     318      }
     319
     320      InArcIt(const Adaptor& adaptor, const Arc& arc) :
     321        Arc(arc), _adaptor(&adaptor) {}
     322
     323      InArcIt& operator++() {
     324        _adaptor->nextIn(*this);
     325        return *this;
     326      }
     327
     328    };
     329
     330    class EdgeIt : public Parent::Edge {
    352331      const Adaptor* _adaptor;
    353332    public:
     
    358337
    359338      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    360         _adaptor->first(static_cast<Edge&>(*this));
    361       }
    362 
    363       EdgeIt(const Adaptor& adaptor, const Edge& e) : 
    364         Edge(e), _adaptor(&adaptor) { }
    365 
    366       EdgeIt& operator++() { 
    367         _adaptor->next(*this);
    368         return *this;
    369       }
    370 
    371     };
    372 
    373     class IncEdgeIt : public Edge { 
     339        _adaptor->first(static_cast<Edge&>(*this));
     340      }
     341
     342      EdgeIt(const Adaptor& adaptor, const Edge& e) :
     343        Edge(e), _adaptor(&adaptor) { }
     344
     345      EdgeIt& operator++() {
     346        _adaptor->next(*this);
     347        return *this;
     348      }
     349
     350    };
     351
     352    class IncEdgeIt : public Edge {
    374353      friend class GraphAdaptorExtender;
    375354      const Adaptor* _adaptor;
     
    382361
    383362      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
    384         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
     363        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
    385364      }
    386365
    387366      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
    388         : _adaptor(&adaptor), Edge(e) {
    389         direction = (_adaptor->u(e) == n);
     367        : _adaptor(&adaptor), Edge(e) {
     368        direction = (_adaptor->u(e) == n);
    390369      }
    391370
    392371      IncEdgeIt& operator++() {
    393         _adaptor->nextInc(*this, direction);
    394         return *this;
    395       }
    396     };
    397 
    398     /// \brief Base node of the iterator
    399     ///
    400     /// Returns the base node (ie. the source in this case) of the iterator
     372        _adaptor->nextInc(*this, direction);
     373        return *this;
     374      }
     375    };
     376
    401377    Node baseNode(const OutArcIt &a) const {
    402378      return Parent::source(a);
    403379    }
    404     /// \brief Running node of the iterator
    405     ///
    406     /// Returns the running node (ie. the target in this case) of the
    407     /// iterator
    408380    Node runningNode(const OutArcIt &a) const {
    409381      return Parent::target(a);
    410382    }
    411383
    412     /// \brief Base node of the iterator
    413     ///
    414     /// Returns the base node (ie. the target in this case) of the iterator
    415384    Node baseNode(const InArcIt &a) const {
    416385      return Parent::target(a);
    417386    }
    418     /// \brief Running node of the iterator
    419     ///
    420     /// Returns the running node (ie. the source in this case) of the
    421     /// iterator
    422387    Node runningNode(const InArcIt &a) const {
    423388      return Parent::source(a);
    424389    }
    425390
    426     /// Base node of the iterator
    427     ///
    428     /// Returns the base node of the iterator
    429391    Node baseNode(const IncEdgeIt &e) const {
    430392      return e.direction ? Parent::u(e) : Parent::v(e);
    431393    }
    432     /// Running node of the iterator
    433     ///
    434     /// Returns the running node of the iterator
    435394    Node runningNode(const IncEdgeIt &e) const {
    436395      return e.direction ? Parent::v(e) : Parent::u(e);
  • lemon/bits/variant.h

    r414 r416  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    2828
    2929  namespace _variant_bits {
    30  
     30
    3131    template <int left, int right>
    3232    struct CTMax {
     
    8787      flag = bivariant.flag;
    8888      if (flag) {
    89         new(reinterpret_cast<First*>(data)) First(bivariant.first());     
     89        new(reinterpret_cast<First*>(data)) First(bivariant.first());
    9090      } else {
    91         new(reinterpret_cast<Second*>(data)) Second(bivariant.second());     
     91        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
    9292      }
    9393    }
     
    107107      destroy();
    108108      flag = true;
    109       new(reinterpret_cast<First*>(data)) First();   
     109      new(reinterpret_cast<First*>(data)) First();
    110110      return *this;
    111111    }
     
    118118      destroy();
    119119      flag = true;
    120       new(reinterpret_cast<First*>(data)) First(f);   
     120      new(reinterpret_cast<First*>(data)) First(f);
    121121      return *this;
    122122    }
     
    129129      destroy();
    130130      flag = false;
    131       new(reinterpret_cast<Second*>(data)) Second();   
     131      new(reinterpret_cast<Second*>(data)) Second();
    132132      return *this;
    133133    }
     
    140140      destroy();
    141141      flag = false;
    142       new(reinterpret_cast<Second*>(data)) Second(s);   
     142      new(reinterpret_cast<Second*>(data)) Second(s);
    143143      return *this;
    144144    }
     
    160160      flag = bivariant.flag;
    161161      if (flag) {
    162         new(reinterpret_cast<First*>(data)) First(bivariant.first());     
     162        new(reinterpret_cast<First*>(data)) First(bivariant.first());
    163163      } else {
    164         new(reinterpret_cast<Second*>(data)) Second(bivariant.second());     
     164        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
    165165      }
    166166      return *this;
     
    232232      }
    233233    }
    234    
     234
    235235    char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
    236236    bool flag;
     
    238238
    239239  namespace _variant_bits {
    240    
     240
    241241    template <int _idx, typename _TypeMap>
    242242    struct Memory {
     
    277277    template <int _idx, typename _TypeMap>
    278278    struct Size {
    279       static const int value = 
    280       CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), 
     279      static const int value =
     280      CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
    281281            Size<_idx - 1, _TypeMap>::value>::value;
    282282    };
     
    284284    template <typename _TypeMap>
    285285    struct Size<0, _TypeMap> {
    286       static const int value = 
     286      static const int value =
    287287      sizeof(typename _TypeMap::template Map<0>::Type);
    288288    };
     
    302302  /// variant type.
    303303  /// \param _TypeMap This class describes the types of the Variant. The
    304   /// _TypeMap::Map<index>::Type should be a valid type for each index 
     304  /// _TypeMap::Map<index>::Type should be a valid type for each index
    305305  /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
    306306  /// class to define such type mappings up to 10 types.
     
    338338    Variant() {
    339339      flag = 0;
    340       new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) 
     340      new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
    341341        typename TypeMap::template Map<0>::Type();
    342342    }
     
    379379      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
    380380      flag = _idx;
    381       new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 
     381      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
    382382        typename TypeMap::template Map<_idx>::Type();
    383383      return *this;
     
    392392      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
    393393      flag = _idx;
    394       new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 
     394      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
    395395        typename TypeMap::template Map<_idx>::Type(init);
    396396      return *this;
     
    404404      LEMON_DEBUG(_idx == flag, "Variant wrong index");
    405405      return *reinterpret_cast<const typename TypeMap::
    406         template Map<_idx>::Type*>(data); 
     406        template Map<_idx>::Type*>(data);
    407407    }
    408408
     
    414414      LEMON_DEBUG(_idx == flag, "Variant wrong index");
    415415      return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
    416         (data); 
     416        (data);
    417417    }
    418418
     
    425425
    426426  private:
    427    
     427
    428428    char data[_variant_bits::Size<num - 1, TypeMap>::value];
    429429    int flag;
     
    443443
    444444    struct List {};
    445    
     445
    446446    template <typename _Type, typename _List>
    447447    struct Insert {
     
    450450    };
    451451
    452     template <int _idx, typename _T0, typename _T1, typename _T2, 
     452    template <int _idx, typename _T0, typename _T1, typename _T2,
    453453              typename _T3, typename _T5, typename _T4, typename _T6,
    454454              typename _T7, typename _T8, typename _T9>
     
    467467      typedef typename Get<_idx, L0>::Type Type;
    468468    };
    469    
     469
    470470  }
    471471
     
    476476  /// \see Variant
    477477  template <
    478     typename _T0, 
     478    typename _T0,
    479479    typename _T1 = void, typename _T2 = void, typename _T3 = void,
    480480    typename _T5 = void, typename _T4 = void, typename _T6 = void,
     
    488488    };
    489489  };
    490  
     490
    491491}
    492492
Note: See TracChangeset for help on using the changeset viewer.