COIN-OR::LEMON - Graph Library

Changeset 432:76287c8caa26 in 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
Files:
1 deleted
5 edited
1 moved

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r403 r432  
    5858
    5959<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
     60*/
     61
     62/**
     63@defgroup graph_adaptors Adaptor Classes for graphs
     64@ingroup graphs
     65\brief This group contains several adaptor classes for digraphs and graphs
     66
     67The main parts of LEMON are the different graph structures, generic
     68graph algorithms, graph concepts which couple these, and graph
     69adaptors. While the previous notions are more or less clear, the
     70latter one needs further explanation. Graph adaptors are graph classes
     71which serve for considering graph structures in different ways.
     72
     73A short example makes this much clearer.  Suppose that we have an
     74instance \c g of a directed graph type say ListDigraph and an algorithm
     75\code
     76template <typename Digraph>
     77int algorithm(const Digraph&);
     78\endcode
     79is needed to run on the reverse oriented graph.  It may be expensive
     80(in time or in memory usage) to copy \c g with the reversed
     81arcs.  In this case, an adaptor class is used, which (according
     82to LEMON digraph concepts) works as a digraph.  The adaptor uses the
     83original digraph structure and digraph operations when methods of the
     84reversed oriented graph are called.  This means that the adaptor have
     85minor memory usage, and do not perform sophisticated algorithmic
     86actions.  The purpose of it is to give a tool for the cases when a
     87graph have to be used in a specific alteration.  If this alteration is
     88obtained by a usual construction like filtering the arc-set or
     89considering a new orientation, then an adaptor is worthwhile to use.
     90To come back to the reverse oriented graph, in this situation
     91\code
     92template<typename Digraph> class ReverseDigraph;
     93\endcode
     94template class can be used. The code looks as follows
     95\code
     96ListDigraph g;
     97ReverseDigraph<ListGraph> rg(g);
     98int result = algorithm(rg);
     99\endcode
     100After running the algorithm, the original graph \c g is untouched.
     101This techniques gives rise to an elegant code, and based on stable
     102graph adaptors, complex algorithms can be implemented easily.
     103
     104In flow, circulation and bipartite matching problems, the residual
     105graph is of particular importance. Combining an adaptor implementing
     106this, shortest path algorithms and minimum mean cycle algorithms,
     107a range of weighted and cardinality optimization algorithms can be
     108obtained. For other examples, the interested user is referred to the
     109detailed documentation of particular adaptors.
     110
     111The behavior of graph adaptors can be very different. Some of them keep
     112capabilities of the original graph while in other cases this would be
     113meaningless. This means that the concepts that they are models of depend
     114on the graph adaptor, and the wrapped graph(s).
     115If an arc of \c rg is deleted, this is carried out by deleting the
     116corresponding arc of \c g, thus the adaptor modifies the original graph.
     117
     118But for a residual graph, this operation has no sense.
     119Let us stand one more example here to simplify your work.
     120RevGraphAdaptor has constructor
     121\code
     122ReverseDigraph(Digraph& digraph);
     123\endcode
     124This means that in a situation, when a <tt>const ListDigraph&</tt>
     125reference to a graph is given, then it have to be instantiated with
     126<tt>Digraph=const ListDigraph</tt>.
     127\code
     128int algorithm1(const ListDigraph& g) {
     129  RevGraphAdaptor<const ListDigraph> rg(g);
     130  return algorithm2(rg);
     131}
     132\endcode
    60133*/
    61134
  • lemon/Makefile.am

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

    r431 r432  
    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

    r430 r432  
    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

    r430 r432  
    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
  • test/graph_adaptor_test.cc

    r431 r432  
    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
     
    2626#include<lemon/concepts/graph.h>
    2727
    28 #include<lemon/digraph_adaptor.h>
    29 #include<lemon/graph_adaptor.h>
     28#include<lemon/adaptors.h>
    3029
    3130#include <limits>
     
    3837using namespace lemon;
    3938
    40 void checkRevDigraphAdaptor() {
    41   checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
     39void checkReverseDigraph() {
     40  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
    4241
    4342  typedef ListDigraph Digraph;
    44   typedef RevDigraphAdaptor<Digraph> Adaptor;
     43  typedef ReverseDigraph<Digraph> Adaptor;
    4544
    4645  Digraph digraph;
     
    5453  Digraph::Arc a2 = digraph.addArc(n1, n3);
    5554  Digraph::Arc a3 = digraph.addArc(n2, n3);
    56  
     55
    5756  checkGraphNodeList(adaptor, 3);
    5857  checkGraphArcList(adaptor, 3);
     
    7978}
    8079
    81 void checkSubDigraphAdaptor() {
    82   checkConcept<concepts::Digraph, 
    83     SubDigraphAdaptor<concepts::Digraph,
     80void checkSubDigraph() {
     81  checkConcept<concepts::Digraph,
     82    SubDigraph<concepts::Digraph,
    8483    concepts::Digraph::NodeMap<bool>,
    8584    concepts::Digraph::ArcMap<bool> > >();
     
    8887  typedef Digraph::NodeMap<bool> NodeFilter;
    8988  typedef Digraph::ArcMap<bool> ArcFilter;
    90   typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
     89  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
    9190
    9291  Digraph digraph;
     
    124123  checkGraphArcMap(adaptor);
    125124
    126   arc_filter[a2] = false; 
     125  arc_filter[a2] = false;
    127126
    128127  checkGraphNodeList(adaptor, 3);
     
    144143  checkGraphArcMap(adaptor);
    145144
    146   node_filter[n1] = false; 
     145  node_filter[n1] = false;
    147146
    148147  checkGraphNodeList(adaptor, 2);
     
    176175}
    177176
    178 void checkNodeSubDigraphAdaptor() {
    179   checkConcept<concepts::Digraph, 
    180     NodeSubDigraphAdaptor<concepts::Digraph,
     177void checkFilterNodes1() {
     178  checkConcept<concepts::Digraph,
     179    FilterNodes<concepts::Digraph,
    181180      concepts::Digraph::NodeMap<bool> > >();
    182181
    183182  typedef ListDigraph Digraph;
    184183  typedef Digraph::NodeMap<bool> NodeFilter;
    185   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
     184  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
    186185
    187186  Digraph digraph;
     
    217216  checkGraphArcMap(adaptor);
    218217
    219   node_filter[n1] = false; 
     218  node_filter[n1] = false;
    220219
    221220  checkGraphNodeList(adaptor, 2);
     
    248247}
    249248
    250 void checkArcSubDigraphAdaptor() {
    251   checkConcept<concepts::Digraph, 
    252     ArcSubDigraphAdaptor<concepts::Digraph,
     249void checkFilterArcs() {
     250  checkConcept<concepts::Digraph,
     251    FilterArcs<concepts::Digraph,
    253252    concepts::Digraph::ArcMap<bool> > >();
    254253
    255254  typedef ListDigraph Digraph;
    256255  typedef Digraph::ArcMap<bool> ArcFilter;
    257   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
     256  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
    258257
    259258  Digraph digraph;
     
    289288  checkGraphArcMap(adaptor);
    290289
    291   arc_filter[a2] = false; 
     290  arc_filter[a2] = false;
    292291
    293292  checkGraphNodeList(adaptor, 3);
     
    322321}
    323322
    324 void checkUndirDigraphAdaptor() {
    325   checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
     323void checkUndirector() {
     324  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
    326325
    327326  typedef ListDigraph Digraph;
    328   typedef UndirDigraphAdaptor<Digraph> Adaptor;
     327  typedef Undirector<Digraph> Adaptor;
    329328
    330329  Digraph digraph;
     
    338337  Digraph::Arc a2 = digraph.addArc(n1, n3);
    339338  Digraph::Arc a3 = digraph.addArc(n2, n3);
    340  
     339
    341340  checkGraphNodeList(adaptor, 3);
    342341  checkGraphArcList(adaptor, 6);
     
    372371}
    373372
    374 void checkResDigraphAdaptor() {
    375   checkConcept<concepts::Digraph, 
    376     ResDigraphAdaptor<concepts::Digraph,
    377     concepts::Digraph::ArcMap<int>, 
     373void checkResidual() {
     374  checkConcept<concepts::Digraph,
     375    Residual<concepts::Digraph,
     376    concepts::Digraph::ArcMap<int>,
    378377    concepts::Digraph::ArcMap<int> > >();
    379378
    380379  typedef ListDigraph Digraph;
    381380  typedef Digraph::ArcMap<int> IntArcMap;
    382   typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
     381  typedef Residual<Digraph, IntArcMap> Adaptor;
    383382
    384383  Digraph digraph;
     
    408407    flow[a] = 0;
    409408  }
    410  
     409
    411410  checkGraphNodeList(adaptor, 4);
    412411  checkGraphArcList(adaptor, 6);
     
    426425    flow[a] = capacity[a] / 2;
    427426  }
    428  
     427
    429428  checkGraphNodeList(adaptor, 4);
    430429  checkGraphArcList(adaptor, 12);
     
    450449    flow[a] = capacity[a];
    451450  }
    452  
     451
    453452  checkGraphNodeList(adaptor, 4);
    454453  checkGraphArcList(adaptor, 6);
     
    471470  int flow_value = 0;
    472471  while (true) {
    473    
     472
    474473    Bfs<Adaptor> bfs(adaptor);
    475474    bfs.run(n1, n4);
    476    
     475
    477476    if (!bfs.reached(n4)) break;
    478477
    479478    Path<Adaptor> p = bfs.path(n4);
    480    
     479
    481480    int min = std::numeric_limits<int>::max();
    482481    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
    483       if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
     482      if (adaptor.residualCapacity(a) < min)
     483        min = adaptor.residualCapacity(a);
    484484    }
    485485
     
    494494}
    495495
    496 void checkSplitDigraphAdaptor() {
    497   checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
     496void checkSplitNodes() {
     497  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
    498498
    499499  typedef ListDigraph Digraph;
    500   typedef SplitDigraphAdaptor<Digraph> Adaptor;
     500  typedef SplitNodes<Digraph> Adaptor;
    501501
    502502  Digraph digraph;
     
    510510  Digraph::Arc a2 = digraph.addArc(n1, n3);
    511511  Digraph::Arc a3 = digraph.addArc(n2, n3);
    512  
     512
    513513  checkGraphNodeList(adaptor, 6);
    514514  checkGraphArcList(adaptor, 6);
     
    531531  checkNodeIds(adaptor);
    532532  checkArcIds(adaptor);
    533  
     533
    534534  checkGraphNodeMap(adaptor);
    535535  checkGraphArcMap(adaptor);
     
    538538    if (adaptor.origArc(a)) {
    539539      Digraph::Arc oa = a;
    540       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 
    541             "Wrong split");
    542       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 
    543             "Wrong split");
     540      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
     541            "Wrong split");
     542      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
     543            "Wrong split");
    544544    } else {
    545545      Digraph::Node on = a;
     
    550550}
    551551
    552 void checkSubGraphAdaptor() {
    553   checkConcept<concepts::Graph, 
    554     SubGraphAdaptor<concepts::Graph,
     552void checkSubGraph() {
     553  checkConcept<concepts::Graph,
     554    SubGraph<concepts::Graph,
    555555    concepts::Graph::NodeMap<bool>,
    556556    concepts::Graph::EdgeMap<bool> > >();
     
    559559  typedef Graph::NodeMap<bool> NodeFilter;
    560560  typedef Graph::EdgeMap<bool> EdgeFilter;
    561   typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
     561  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
    562562
    563563  Graph graph;
     
    608608  checkGraphEdgeMap(adaptor);
    609609
    610   edge_filter[e2] = false; 
     610  edge_filter[e2] = false;
    611611
    612612  checkGraphNodeList(adaptor, 4);
     
    639639  checkGraphEdgeMap(adaptor);
    640640
    641   node_filter[n1] = false; 
     641  node_filter[n1] = false;
    642642
    643643  checkGraphNodeList(adaptor, 3);
     
    685685}
    686686
    687 void checkNodeSubGraphAdaptor() {
    688   checkConcept<concepts::Graph, 
    689     NodeSubGraphAdaptor<concepts::Graph,
     687void checkFilterNodes2() {
     688  checkConcept<concepts::Graph,
     689    FilterNodes<concepts::Graph,
    690690      concepts::Graph::NodeMap<bool> > >();
    691691
    692692  typedef ListGraph Graph;
    693693  typedef Graph::NodeMap<bool> NodeFilter;
    694   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
     694  typedef FilterNodes<Graph, NodeFilter> Adaptor;
    695695
    696696  Graph graph;
     
    739739  checkGraphEdgeMap(adaptor);
    740740
    741   node_filter[n1] = false; 
     741  node_filter[n1] = false;
    742742
    743743  checkGraphNodeList(adaptor, 3);
     
    784784}
    785785
    786 void checkEdgeSubGraphAdaptor() {
    787   checkConcept<concepts::Graph, 
    788     EdgeSubGraphAdaptor<concepts::Graph,
     786void checkFilterEdges() {
     787  checkConcept<concepts::Graph,
     788    FilterEdges<concepts::Graph,
    789789    concepts::Graph::EdgeMap<bool> > >();
    790790
    791791  typedef ListGraph Graph;
    792792  typedef Graph::EdgeMap<bool> EdgeFilter;
    793   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
     793  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
    794794
    795795  Graph graph;
     
    838838  checkGraphEdgeMap(adaptor);
    839839
    840   edge_filter[e2] = false; 
     840  edge_filter[e2] = false;
    841841
    842842  checkGraphNodeList(adaptor, 4);
     
    886886}
    887887
    888 void checkDirGraphAdaptor() {
    889   checkConcept<concepts::Digraph, 
    890     DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
     888void checkOrienter() {
     889  checkConcept<concepts::Digraph,
     890    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
    891891
    892892  typedef ListGraph Graph;
    893893  typedef ListGraph::EdgeMap<bool> DirMap;
    894   typedef DirGraphAdaptor<Graph> Adaptor;
     894  typedef Orienter<Graph> Adaptor;
    895895
    896896  Graph graph;
     
    905905  Graph::Edge e2 = graph.addEdge(n1, n3);
    906906  Graph::Edge e3 = graph.addEdge(n2, n3);
    907  
     907
    908908  checkGraphNodeList(adaptor, 3);
    909909  checkGraphArcList(adaptor, 3);
    910910  checkGraphConArcList(adaptor, 3);
    911  
     911
    912912  {
    913913    dir[e1] = true;
    914914    Adaptor::Node u = adaptor.source(e1);
    915915    Adaptor::Node v = adaptor.target(e1);
    916    
     916
    917917    dir[e1] = false;
    918918    check (u == adaptor.target(e1), "Wrong dir");
     
    927927    Adaptor::Node u = adaptor.source(e2);
    928928    Adaptor::Node v = adaptor.target(e2);
    929    
     929
    930930    dir[e2] = false;
    931931    check (u == adaptor.target(e2), "Wrong dir");
     
    940940    Adaptor::Node u = adaptor.source(e3);
    941941    Adaptor::Node v = adaptor.target(e3);
    942    
     942
    943943    dir[e3] = false;
    944944    check (u == adaptor.target(e3), "Wrong dir");
     
    968968int main(int, const char **) {
    969969
    970   checkRevDigraphAdaptor();
    971   checkSubDigraphAdaptor();
    972   checkNodeSubDigraphAdaptor();
    973   checkArcSubDigraphAdaptor();
    974   checkUndirDigraphAdaptor();
    975   checkResDigraphAdaptor();
    976   checkSplitDigraphAdaptor();
    977 
    978   checkSubGraphAdaptor();
    979   checkNodeSubGraphAdaptor();
    980   checkEdgeSubGraphAdaptor();
    981   checkDirGraphAdaptor();
     970  checkReverseDigraph();
     971  checkSubDigraph();
     972  checkFilterNodes1();
     973  checkFilterArcs();
     974  checkUndirector();
     975  checkResidual();
     976  checkSplitNodes();
     977
     978  checkSubGraph();
     979  checkFilterNodes2();
     980  checkFilterEdges();
     981  checkOrienter();
    982982
    983983  return 0;
Note: See TracChangeset for help on using the changeset viewer.