COIN-OR::LEMON - Graph Library

Changeset 559:9b9ffe7d9b75 in lemon


Ignore:
Timestamp:
02/13/09 13:29:28 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Fixes for MSVC 2008 in grap_adaptors.h and edge_set.h (#194)

Several renamings and changes in adaptors and edge sets

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/adaptors.h

    r487 r559  
    3737namespace lemon {
    3838
    39   template<typename _Digraph>
     39#ifdef _MSC_VER
     40#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
     41#else
     42#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
     43#endif
     44
     45  template<typename DGR>
    4046  class DigraphAdaptorBase {
    4147  public:
    42     typedef _Digraph Digraph;
     48    typedef DGR Digraph;
    4349    typedef DigraphAdaptorBase Adaptor;
    44     typedef Digraph ParentDigraph;
    4550
    4651  protected:
    47     Digraph* _digraph;
     52    DGR* _digraph;
    4853    DigraphAdaptorBase() : _digraph(0) { }
    49     void setDigraph(Digraph& digraph) { _digraph = &digraph; }
    50 
    51   public:
    52     DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
    53 
    54     typedef typename Digraph::Node Node;
    55     typedef typename Digraph::Arc Arc;
     54    void initialize(DGR& digraph) { _digraph = &digraph; }
     55
     56  public:
     57    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
     58
     59    typedef typename DGR::Node Node;
     60    typedef typename DGR::Arc Arc;
    5661
    5762    void first(Node& i) const { _digraph->first(i); }
     
    6873    Node target(const Arc& a) const { return _digraph->target(a); }
    6974
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
     75    typedef NodeNumTagIndicator<DGR> NodeNumTag;
    7176    int nodeNum() const { return _digraph->nodeNum(); }
    7277
    73     typedef ArcNumTagIndicator<Digraph> ArcNumTag;
     78    typedef ArcNumTagIndicator<DGR> ArcNumTag;
    7479    int arcNum() const { return _digraph->arcNum(); }
    7580
    76     typedef FindArcTagIndicator<Digraph> FindArcTag;
     81    typedef FindArcTagIndicator<DGR> FindArcTag;
    7782    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    7883      return _digraph->findArc(u, v, prev);
     
    96101    int maxArcId() const { return _digraph->maxArcId(); }
    97102
    98     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     103    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    99104    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    100105
    101     typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
     106    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
    102107    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
    103108
    104     template <typename _Value>
    105     class NodeMap : public Digraph::template NodeMap<_Value> {
     109    template <typename V>
     110    class NodeMap : public DGR::template NodeMap<V> {
    106111    public:
    107112
    108       typedef typename Digraph::template NodeMap<_Value> Parent;
     113      typedef typename DGR::template NodeMap<V> Parent;
    109114
    110115      explicit NodeMap(const Adaptor& adaptor)
    111116        : Parent(*adaptor._digraph) {}
    112117
    113       NodeMap(const Adaptor& adaptor, const _Value& value)
     118      NodeMap(const Adaptor& adaptor, const V& value)
    114119        : Parent(*adaptor._digraph, value) { }
    115120
     
    127132    };
    128133
    129     template <typename _Value>
    130     class ArcMap : public Digraph::template ArcMap<_Value> {
     134    template <typename V>
     135    class ArcMap : public DGR::template ArcMap<V> {
    131136    public:
    132137
    133       typedef typename Digraph::template ArcMap<_Value> Parent;
    134 
    135       explicit ArcMap(const Adaptor& adaptor)
     138      typedef typename DGR::template ArcMap<V> Parent;
     139
     140      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    136141        : Parent(*adaptor._digraph) {}
    137142
    138       ArcMap(const Adaptor& adaptor, const _Value& value)
     143      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    139144        : Parent(*adaptor._digraph, value) {}
    140145
     
    154159  };
    155160
    156   template<typename _Graph>
     161  template<typename GR>
    157162  class GraphAdaptorBase {
    158163  public:
    159     typedef _Graph Graph;
    160     typedef Graph ParentGraph;
     164    typedef GR Graph;
    161165
    162166  protected:
    163     Graph* _graph;
     167    GR* _graph;
    164168
    165169    GraphAdaptorBase() : _graph(0) {}
    166170
    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;
     171    void initialize(GR& graph) { _graph = &graph; }
     172
     173  public:
     174    GraphAdaptorBase(GR& graph) : _graph(&graph) {}
     175
     176    typedef typename GR::Node Node;
     177    typedef typename GR::Arc Arc;
     178    typedef typename GR::Edge Edge;
    175179
    176180    void first(Node& i) const { _graph->first(i); }
     
    240244    int maxEdgeId() const { return _graph->maxEdgeId(); }
    241245
    242     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     246    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    243247    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    244248
    245     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     249    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    246250    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    247251
    248     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     252    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
    249253    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
    250254
    251     template <typename _Value>
    252     class NodeMap : public Graph::template NodeMap<_Value> {
     255    template <typename V>
     256    class NodeMap : public GR::template NodeMap<V> {
    253257    public:
    254       typedef typename Graph::template NodeMap<_Value> Parent;
    255       explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
     258      typedef typename GR::template NodeMap<V> Parent;
     259      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    256260        : Parent(*adapter._graph) {}
    257       NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     261      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    258262        : Parent(*adapter._graph, value) {}
    259263
     
    271275    };
    272276
    273     template <typename _Value>
    274     class ArcMap : public Graph::template ArcMap<_Value> {
     277    template <typename V>
     278    class ArcMap : public GR::template ArcMap<V> {
    275279    public:
    276       typedef typename Graph::template ArcMap<_Value> Parent;
    277       explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
     280      typedef typename GR::template ArcMap<V> Parent;
     281      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    278282        : Parent(*adapter._graph) {}
    279       ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     283      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    280284        : Parent(*adapter._graph, value) {}
    281285
     
    292296    };
    293297
    294     template <typename _Value>
    295     class EdgeMap : public Graph::template EdgeMap<_Value> {
     298    template <typename V>
     299    class EdgeMap : public GR::template EdgeMap<V> {
    296300    public:
    297       typedef typename Graph::template EdgeMap<_Value> Parent;
    298       explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
     301      typedef typename GR::template EdgeMap<V> Parent;
     302      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    299303        : Parent(*adapter._graph) {}
    300       EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     304      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    301305        : Parent(*adapter._graph, value) {}
    302306
     
    315319  };
    316320
    317   template <typename _Digraph>
    318   class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
    319   public:
    320     typedef _Digraph Digraph;
    321     typedef DigraphAdaptorBase<_Digraph> Parent;
     321  template <typename DGR>
     322  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     323  public:
     324    typedef DGR Digraph;
     325    typedef DigraphAdaptorBase<DGR> Parent;
    322326  protected:
    323327    ReverseDigraphBase() : Parent() { }
     
    337341    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    338342
    339     typedef FindArcTagIndicator<Digraph> FindArcTag;
     343    typedef FindArcTagIndicator<DGR> FindArcTag;
    340344    Arc findArc(const Node& u, const Node& v,
    341345                const Arc& prev = INVALID) const {
     
    357361  /// parameter is set to be \c const.
    358362  ///
    359   /// \tparam GR The type of the adapted digraph.
     363  /// \tparam DGR The type of the adapted digraph.
    360364  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    361365  /// It can also be specified to be \c const.
     
    363367  /// \note The \c Node and \c Arc types of this adaptor and the adapted
    364368  /// digraph are convertible to each other.
    365   template<typename GR>
     369  template<typename DGR>
    366370#ifdef DOXYGEN
    367371  class ReverseDigraph {
    368372#else
    369373  class ReverseDigraph :
    370     public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
     374    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    371375#endif
    372376  public:
    373377    /// The type of the adapted digraph.
    374     typedef GR Digraph;
    375     typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
     378    typedef DGR Digraph;
     379    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    376380  protected:
    377381    ReverseDigraph() { }
     
    381385    ///
    382386    /// Creates a reverse digraph adaptor for the given digraph.
    383     explicit ReverseDigraph(Digraph& digraph) {
    384       Parent::setDigraph(digraph);
     387    explicit ReverseDigraph(DGR& digraph) {
     388      Parent::initialize(digraph);
    385389    }
    386390  };
     
    391395  /// \ingroup graph_adaptors
    392396  /// \relates ReverseDigraph
    393   template<typename GR>
    394   ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
    395     return ReverseDigraph<const GR>(digraph);
     397  template<typename DGR>
     398  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
     399    return ReverseDigraph<const DGR>(digraph);
    396400  }
    397401
    398402
    399   template <typename _Digraph, typename _NodeFilterMap,
    400             typename _ArcFilterMap, bool _checked = true>
    401   class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
    402   public:
    403     typedef _Digraph Digraph;
    404     typedef _NodeFilterMap NodeFilterMap;
    405     typedef _ArcFilterMap ArcFilterMap;
     403  template <typename DGR, typename NF, typename AF, bool ch = true>
     404  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
     405  public:
     406    typedef DGR Digraph;
     407    typedef NF NodeFilterMap;
     408    typedef AF ArcFilterMap;
    406409
    407410    typedef SubDigraphBase Adaptor;
    408     typedef DigraphAdaptorBase<_Digraph> Parent;
     411    typedef DigraphAdaptorBase<DGR> Parent;
    409412  protected:
    410     NodeFilterMap* _node_filter;
    411     ArcFilterMap* _arc_filter;
     413    NF* _node_filter;
     414    AF* _arc_filter;
    412415    SubDigraphBase()
    413416      : Parent(), _node_filter(0), _arc_filter(0) { }
    414417
    415     void setNodeFilterMap(NodeFilterMap& node_filter) {
     418    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     419      Parent::initialize(digraph);
    416420      _node_filter = &node_filter;
    417     }
    418     void setArcFilterMap(ArcFilterMap& arc_filter) {
    419       _arc_filter = &arc_filter;
     421      _arc_filter = &arc_filter;     
    420422    }
    421423
     
    488490    typedef False ArcNumTag;
    489491
    490     typedef FindArcTagIndicator<Digraph> FindArcTag;
     492    typedef FindArcTagIndicator<DGR> FindArcTag;
    491493    Arc findArc(const Node& source, const Node& target,
    492494                const Arc& prev = INVALID) const {
     
    501503    }
    502504
    503     template <typename _Value>
    504     class NodeMap : public SubMapExtender<Adaptor,
    505       typename Parent::template NodeMap<_Value> > {
     505  public:
     506
     507    template <typename V>
     508    class NodeMap
     509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     510              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    506511    public:
    507       typedef _Value Value;
    508       typedef SubMapExtender<Adaptor, typename Parent::
    509                              template NodeMap<Value> > MapParent;
    510 
    511       NodeMap(const Adaptor& adaptor)
    512         : MapParent(adaptor) {}
    513       NodeMap(const Adaptor& adaptor, const Value& value)
    514         : MapParent(adaptor, value) {}
     512      typedef V Value;
     513      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     514            LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515
     516      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     517        : Parent(adaptor) {}
     518      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
     519        : Parent(adaptor, value) {}
    515520
    516521    private:
     
    521526      template <typename CMap>
    522527      NodeMap& operator=(const CMap& cmap) {
    523         MapParent::operator=(cmap);
     528        Parent::operator=(cmap);
    524529        return *this;
    525530      }
    526531    };
    527532
    528     template <typename _Value>
    529     class ArcMap : public SubMapExtender<Adaptor,
    530       typename Parent::template ArcMap<_Value> > {
     533    template <typename V>
     534    class ArcMap
     535      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     536              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    531537    public:
    532       typedef _Value Value;
    533       typedef SubMapExtender<Adaptor, typename Parent::
    534                              template ArcMap<Value> > MapParent;
    535 
    536       ArcMap(const Adaptor& adaptor)
    537         : MapParent(adaptor) {}
    538       ArcMap(const Adaptor& adaptor, const Value& value)
    539         : MapParent(adaptor, value) {}
     538      typedef V Value;
     539      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     540        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     541
     542      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     543        : Parent(adaptor) {}
     544      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
     545        : Parent(adaptor, value) {}
    540546
    541547    private:
     
    546552      template <typename CMap>
    547553      ArcMap& operator=(const CMap& cmap) {
    548         MapParent::operator=(cmap);
     554        Parent::operator=(cmap);
    549555        return *this;
    550556      }
     
    553559  };
    554560
    555   template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
    556   class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
    557     : public DigraphAdaptorBase<_Digraph> {
    558   public:
    559     typedef _Digraph Digraph;
    560     typedef _NodeFilterMap NodeFilterMap;
    561     typedef _ArcFilterMap ArcFilterMap;
     561  template <typename DGR, typename NF, typename AF>
     562  class SubDigraphBase<DGR, NF, AF, false>
     563    : public DigraphAdaptorBase<DGR> {
     564  public:
     565    typedef DGR Digraph;
     566    typedef NF NodeFilterMap;
     567    typedef AF ArcFilterMap;
    562568
    563569    typedef SubDigraphBase Adaptor;
    564570    typedef DigraphAdaptorBase<Digraph> Parent;
    565571  protected:
    566     NodeFilterMap* _node_filter;
    567     ArcFilterMap* _arc_filter;
     572    NF* _node_filter;
     573    AF* _arc_filter;
    568574    SubDigraphBase()
    569575      : Parent(), _node_filter(0), _arc_filter(0) { }
    570576
    571     void setNodeFilterMap(NodeFilterMap& node_filter) {
     577    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     578      Parent::initialize(digraph);
    572579      _node_filter = &node_filter;
    573     }
    574     void setArcFilterMap(ArcFilterMap& arc_filter) {
    575       _arc_filter = &arc_filter;
     580      _arc_filter = &arc_filter;     
    576581    }
    577582
     
    628633    typedef False ArcNumTag;
    629634
    630     typedef FindArcTagIndicator<Digraph> FindArcTag;
     635    typedef FindArcTagIndicator<DGR> FindArcTag;
    631636    Arc findArc(const Node& source, const Node& target,
    632637                const Arc& prev = INVALID) const {
     
    641646    }
    642647
    643     template <typename _Value>
    644     class NodeMap : public SubMapExtender<Adaptor,
    645       typename Parent::template NodeMap<_Value> > {
     648    template <typename V>
     649    class NodeMap
     650      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     651          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    646652    public:
    647       typedef _Value Value;
    648       typedef SubMapExtender<Adaptor, typename Parent::
    649                              template NodeMap<Value> > MapParent;
    650 
    651       NodeMap(const Adaptor& adaptor)
    652         : MapParent(adaptor) {}
    653       NodeMap(const Adaptor& adaptor, const Value& value)
    654         : MapParent(adaptor, value) {}
     653      typedef V Value;
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     656
     657      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     658        : Parent(adaptor) {}
     659      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
     660        : Parent(adaptor, value) {}
    655661
    656662    private:
     
    661667      template <typename CMap>
    662668      NodeMap& operator=(const CMap& cmap) {
    663         MapParent::operator=(cmap);
     669        Parent::operator=(cmap);
    664670        return *this;
    665671      }
    666672    };
    667673
    668     template <typename _Value>
    669     class ArcMap : public SubMapExtender<Adaptor,
    670       typename Parent::template ArcMap<_Value> > {
     674    template <typename V>
     675    class ArcMap
     676      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     677          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    671678    public:
    672       typedef _Value Value;
    673       typedef SubMapExtender<Adaptor, typename Parent::
    674                              template ArcMap<Value> > MapParent;
    675 
    676       ArcMap(const Adaptor& adaptor)
    677         : MapParent(adaptor) {}
    678       ArcMap(const Adaptor& adaptor, const Value& value)
    679         : MapParent(adaptor, value) {}
     679      typedef V Value;
     680      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     681          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     682
     683      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     684        : Parent(adaptor) {}
     685      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
     686        : Parent(adaptor, value) {}
    680687
    681688    private:
     
    686693      template <typename CMap>
    687694      ArcMap& operator=(const CMap& cmap) {
    688         MapParent::operator=(cmap);
     695        Parent::operator=(cmap);
    689696        return *this;
    690697      }
     
    709716  /// parameter is set to be \c const.
    710717  ///
    711   /// \tparam GR The type of the adapted digraph.
     718  /// \tparam DGR The type of the adapted digraph.
    712719  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    713720  /// It can also be specified to be \c const.
     
    715722  /// It must be a \c bool (or convertible) node map of the
    716723  /// adapted digraph. The default type is
    717   /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
     724  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
    718725  /// \tparam AF The type of the arc filter map.
    719726  /// It must be \c bool (or convertible) arc map of the
    720727  /// adapted digraph. The default type is
    721   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     728  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    722729  ///
    723730  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     
    727734  /// \see FilterArcs
    728735#ifdef DOXYGEN
    729   template<typename GR, typename NF, typename AF>
     736  template<typename DGR, typename NF, typename AF>
    730737  class SubDigraph {
    731738#else
    732   template<typename GR,
    733            typename NF = typename GR::template NodeMap<bool>,
    734            typename AF = typename GR::template ArcMap<bool> >
     739  template<typename DGR,
     740           typename NF = typename DGR::template NodeMap<bool>,
     741           typename AF = typename DGR::template ArcMap<bool> >
    735742  class SubDigraph :
    736     public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
     743    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
    737744#endif
    738745  public:
    739746    /// The type of the adapted digraph.
    740     typedef GR Digraph;
     747    typedef DGR Digraph;
    741748    /// The type of the node filter map.
    742749    typedef NF NodeFilterMap;
     
    744751    typedef AF ArcFilterMap;
    745752
    746     typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
     753    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
    747754      Parent;
    748755
     
    758765    /// Creates a subdigraph for the given digraph with the
    759766    /// given node and arc filter maps.
    760     SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
    761                ArcFilterMap& arc_filter) {
    762       setDigraph(digraph);
    763       setNodeFilterMap(node_filter);
    764       setArcFilterMap(arc_filter);
     767    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
     768      Parent::initialize(digraph, node_filter, arc_filter);
    765769    }
    766770
     
    824828  /// \ingroup graph_adaptors
    825829  /// \relates SubDigraph
    826   template<typename GR, typename NF, typename AF>
    827   SubDigraph<const GR, NF, AF>
    828   subDigraph(const GR& digraph,
    829              NF& node_filter_map, AF& arc_filter_map) {
    830     return SubDigraph<const GR, NF, AF>
    831       (digraph, node_filter_map, arc_filter_map);
     830  template<typename DGR, typename NF, typename AF>
     831  SubDigraph<const DGR, NF, AF>
     832  subDigraph(const DGR& digraph,
     833             NF& node_filter, AF& arc_filter) {
     834    return SubDigraph<const DGR, NF, AF>
     835      (digraph, node_filter, arc_filter);
    832836  }
    833837
    834   template<typename GR, typename NF, typename AF>
    835   SubDigraph<const GR, const NF, AF>
    836   subDigraph(const GR& digraph,
    837              const NF& node_filter_map, AF& arc_filter_map) {
    838     return SubDigraph<const GR, const NF, AF>
    839       (digraph, node_filter_map, arc_filter_map);
     838  template<typename DGR, typename NF, typename AF>
     839  SubDigraph<const DGR, const NF, AF>
     840  subDigraph(const DGR& digraph,
     841             const NF& node_filter, AF& arc_filter) {
     842    return SubDigraph<const DGR, const NF, AF>
     843      (digraph, node_filter, arc_filter);
    840844  }
    841845
    842   template<typename GR, typename NF, typename AF>
    843   SubDigraph<const GR, NF, const AF>
    844   subDigraph(const GR& digraph,
    845              NF& node_filter_map, const AF& arc_filter_map) {
    846     return SubDigraph<const GR, NF, const AF>
    847       (digraph, node_filter_map, arc_filter_map);
     846  template<typename DGR, typename NF, typename AF>
     847  SubDigraph<const DGR, NF, const AF>
     848  subDigraph(const DGR& digraph,
     849             NF& node_filter, const AF& arc_filter) {
     850    return SubDigraph<const DGR, NF, const AF>
     851      (digraph, node_filter, arc_filter);
    848852  }
    849853
    850   template<typename GR, typename NF, typename AF>
    851   SubDigraph<const GR, const NF, const AF>
    852   subDigraph(const GR& digraph,
    853              const NF& node_filter_map, const AF& arc_filter_map) {
    854     return SubDigraph<const GR, const NF, const AF>
    855       (digraph, node_filter_map, arc_filter_map);
     854  template<typename DGR, typename NF, typename AF>
     855  SubDigraph<const DGR, const NF, const AF>
     856  subDigraph(const DGR& digraph,
     857             const NF& node_filter, const AF& arc_filter) {
     858    return SubDigraph<const DGR, const NF, const AF>
     859      (digraph, node_filter, arc_filter);
    856860  }
    857861
    858862
    859   template <typename _Graph, typename _NodeFilterMap,
    860             typename _EdgeFilterMap, bool _checked = true>
    861   class SubGraphBase : public GraphAdaptorBase<_Graph> {
    862   public:
    863     typedef _Graph Graph;
    864     typedef _NodeFilterMap NodeFilterMap;
    865     typedef _EdgeFilterMap EdgeFilterMap;
     863  template <typename GR, typename NF, typename EF, bool ch = true>
     864  class SubGraphBase : public GraphAdaptorBase<GR> {
     865  public:
     866    typedef GR Graph;
     867    typedef NF NodeFilterMap;
     868    typedef EF EdgeFilterMap;
    866869
    867870    typedef SubGraphBase Adaptor;
    868     typedef GraphAdaptorBase<_Graph> Parent;
     871    typedef GraphAdaptorBase<GR> Parent;
    869872  protected:
    870873
    871     NodeFilterMap* _node_filter_map;
    872     EdgeFilterMap* _edge_filter_map;
     874    NF* _node_filter;
     875    EF* _edge_filter;
    873876
    874877    SubGraphBase()
    875       : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
    876 
    877     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
    878       _node_filter_map=&node_filter_map;
    879     }
    880     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
    881       _edge_filter_map=&edge_filter_map;
     878      : Parent(), _node_filter(0), _edge_filter(0) { }
     879
     880    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     881      Parent::initialize(graph);
     882      _node_filter = &node_filter;
     883      _edge_filter = &edge_filter;
    882884    }
    883885
     
    890892    void first(Node& i) const {
    891893      Parent::first(i);
    892       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     894      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    893895    }
    894896
    895897    void first(Arc& i) const {
    896898      Parent::first(i);
    897       while (i!=INVALID && (!(*_edge_filter_map)[i]
    898                             || !(*_node_filter_map)[Parent::source(i)]
    899                             || !(*_node_filter_map)[Parent::target(i)]))
     899      while (i!=INVALID && (!(*_edge_filter)[i]
     900                            || !(*_node_filter)[Parent::source(i)]
     901                            || !(*_node_filter)[Parent::target(i)]))
    900902        Parent::next(i);
    901903    }
     
    903905    void first(Edge& i) const {
    904906      Parent::first(i);
    905       while (i!=INVALID && (!(*_edge_filter_map)[i]
    906                             || !(*_node_filter_map)[Parent::u(i)]
    907                             || !(*_node_filter_map)[Parent::v(i)]))
     907      while (i!=INVALID && (!(*_edge_filter)[i]
     908                            || !(*_node_filter)[Parent::u(i)]
     909                            || !(*_node_filter)[Parent::v(i)]))
    908910        Parent::next(i);
    909911    }
     
    911913    void firstIn(Arc& i, const Node& n) const {
    912914      Parent::firstIn(i, n);
    913       while (i!=INVALID && (!(*_edge_filter_map)[i]
    914                             || !(*_node_filter_map)[Parent::source(i)]))
     915      while (i!=INVALID && (!(*_edge_filter)[i]
     916                            || !(*_node_filter)[Parent::source(i)]))
    915917        Parent::nextIn(i);
    916918    }
     
    918920    void firstOut(Arc& i, const Node& n) const {
    919921      Parent::firstOut(i, n);
    920       while (i!=INVALID && (!(*_edge_filter_map)[i]
    921                             || !(*_node_filter_map)[Parent::target(i)]))
     922      while (i!=INVALID && (!(*_edge_filter)[i]
     923                            || !(*_node_filter)[Parent::target(i)]))
    922924        Parent::nextOut(i);
    923925    }
     
    925927    void firstInc(Edge& i, bool& d, const Node& n) const {
    926928      Parent::firstInc(i, d, n);
    927       while (i!=INVALID && (!(*_edge_filter_map)[i]
    928                             || !(*_node_filter_map)[Parent::u(i)]
    929                             || !(*_node_filter_map)[Parent::v(i)]))
     929      while (i!=INVALID && (!(*_edge_filter)[i]
     930                            || !(*_node_filter)[Parent::u(i)]
     931                            || !(*_node_filter)[Parent::v(i)]))
    930932        Parent::nextInc(i, d);
    931933    }
     
    933935    void next(Node& i) const {
    934936      Parent::next(i);
    935       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     937      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    936938    }
    937939
    938940    void next(Arc& i) const {
    939941      Parent::next(i);
    940       while (i!=INVALID && (!(*_edge_filter_map)[i]
    941                             || !(*_node_filter_map)[Parent::source(i)]
    942                             || !(*_node_filter_map)[Parent::target(i)]))
     942      while (i!=INVALID && (!(*_edge_filter)[i]
     943                            || !(*_node_filter)[Parent::source(i)]
     944                            || !(*_node_filter)[Parent::target(i)]))
    943945        Parent::next(i);
    944946    }
     
    946948    void next(Edge& i) const {
    947949      Parent::next(i);
    948       while (i!=INVALID && (!(*_edge_filter_map)[i]
    949                             || !(*_node_filter_map)[Parent::u(i)]
    950                             || !(*_node_filter_map)[Parent::v(i)]))
     950      while (i!=INVALID && (!(*_edge_filter)[i]
     951                            || !(*_node_filter)[Parent::u(i)]
     952                            || !(*_node_filter)[Parent::v(i)]))
    951953        Parent::next(i);
    952954    }
     
    954956    void nextIn(Arc& i) const {
    955957      Parent::nextIn(i);
    956       while (i!=INVALID && (!(*_edge_filter_map)[i]
    957                             || !(*_node_filter_map)[Parent::source(i)]))
     958      while (i!=INVALID && (!(*_edge_filter)[i]
     959                            || !(*_node_filter)[Parent::source(i)]))
    958960        Parent::nextIn(i);
    959961    }
     
    961963    void nextOut(Arc& i) const {
    962964      Parent::nextOut(i);
    963       while (i!=INVALID && (!(*_edge_filter_map)[i]
    964                             || !(*_node_filter_map)[Parent::target(i)]))
     965      while (i!=INVALID && (!(*_edge_filter)[i]
     966                            || !(*_node_filter)[Parent::target(i)]))
    965967        Parent::nextOut(i);
    966968    }
     
    968970    void nextInc(Edge& i, bool& d) const {
    969971      Parent::nextInc(i, d);
    970       while (i!=INVALID && (!(*_edge_filter_map)[i]
    971                             || !(*_node_filter_map)[Parent::u(i)]
    972                             || !(*_node_filter_map)[Parent::v(i)]))
     972      while (i!=INVALID && (!(*_edge_filter)[i]
     973                            || !(*_node_filter)[Parent::u(i)]
     974                            || !(*_node_filter)[Parent::v(i)]))
    973975        Parent::nextInc(i, d);
    974976    }
    975977
    976     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
    977     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
    978 
    979     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
    980     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
     978    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     979    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
     980
     981    bool status(const Node& n) const { return (*_node_filter)[n]; }
     982    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
    981983
    982984    typedef False NodeNumTag;
     
    987989    Arc findArc(const Node& u, const Node& v,
    988990                const Arc& prev = INVALID) const {
    989       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
     991      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
    990992        return INVALID;
    991993      }
    992994      Arc arc = Parent::findArc(u, v, prev);
    993       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
     995      while (arc != INVALID && !(*_edge_filter)[arc]) {
    994996        arc = Parent::findArc(u, v, arc);
    995997      }
     
    10001002    Edge findEdge(const Node& u, const Node& v,
    10011003                  const Edge& prev = INVALID) const {
    1002       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
     1004      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
    10031005        return INVALID;
    10041006      }
    10051007      Edge edge = Parent::findEdge(u, v, prev);
    1006       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1008      while (edge != INVALID && !(*_edge_filter)[edge]) {
    10071009        edge = Parent::findEdge(u, v, edge);
    10081010      }
     
    10101012    }
    10111013
    1012     template <typename _Value>
    1013     class NodeMap : public SubMapExtender<Adaptor,
    1014       typename Parent::template NodeMap<_Value> > {
     1014    template <typename V>
     1015    class NodeMap
     1016      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1017          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    10151018    public:
    1016       typedef _Value Value;
    1017       typedef SubMapExtender<Adaptor, typename Parent::
    1018                              template NodeMap<Value> > MapParent;
    1019 
    1020       NodeMap(const Adaptor& adaptor)
    1021         : MapParent(adaptor) {}
    1022       NodeMap(const Adaptor& adaptor, const Value& value)
    1023         : MapParent(adaptor, value) {}
     1019      typedef V Value;
     1020      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1021        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1022
     1023      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1024        : Parent(adaptor) {}
     1025      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1026        : Parent(adaptor, value) {}
    10241027
    10251028    private:
     
    10301033      template <typename CMap>
    10311034      NodeMap& operator=(const CMap& cmap) {
    1032         MapParent::operator=(cmap);
     1035        Parent::operator=(cmap);
    10331036        return *this;
    10341037      }
    10351038    };
    10361039
    1037     template <typename _Value>
    1038     class ArcMap : public SubMapExtender<Adaptor,
    1039       typename Parent::template ArcMap<_Value> > {
     1040    template <typename V>
     1041    class ArcMap
     1042      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1043          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    10401044    public:
    1041       typedef _Value Value;
    1042       typedef SubMapExtender<Adaptor, typename Parent::
    1043                              template ArcMap<Value> > MapParent;
    1044 
    1045       ArcMap(const Adaptor& adaptor)
    1046         : MapParent(adaptor) {}
    1047       ArcMap(const Adaptor& adaptor, const Value& value)
    1048         : MapParent(adaptor, value) {}
     1045      typedef V Value;
     1046      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1047        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1048
     1049      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1050        : Parent(adaptor) {}
     1051      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1052        : Parent(adaptor, value) {}
    10491053
    10501054    private:
     
    10551059      template <typename CMap>
    10561060      ArcMap& operator=(const CMap& cmap) {
    1057         MapParent::operator=(cmap);
     1061        Parent::operator=(cmap);
    10581062        return *this;
    10591063      }
    10601064    };
    10611065
    1062     template <typename _Value>
    1063     class EdgeMap : public SubMapExtender<Adaptor,
    1064       typename Parent::template EdgeMap<_Value> > {
     1066    template <typename V>
     1067    class EdgeMap
     1068      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1069        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    10651070    public:
    1066       typedef _Value Value;
    1067       typedef SubMapExtender<Adaptor, typename Parent::
    1068                              template EdgeMap<Value> > MapParent;
    1069 
    1070       EdgeMap(const Adaptor& adaptor)
    1071         : MapParent(adaptor) {}
    1072 
    1073       EdgeMap(const Adaptor& adaptor, const Value& value)
    1074         : MapParent(adaptor, value) {}
     1071      typedef V Value;
     1072      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1073        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1074
     1075      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1076        : Parent(adaptor) {}
     1077
     1078      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1079        : Parent(adaptor, value) {}
    10751080
    10761081    private:
     
    10811086      template <typename CMap>
    10821087      EdgeMap& operator=(const CMap& cmap) {
    1083         MapParent::operator=(cmap);
     1088        Parent::operator=(cmap);
    10841089        return *this;
    10851090      }
     
    10881093  };
    10891094
    1090   template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
    1091   class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
    1092     : public GraphAdaptorBase<_Graph> {
    1093   public:
    1094     typedef _Graph Graph;
    1095     typedef _NodeFilterMap NodeFilterMap;
    1096     typedef _EdgeFilterMap EdgeFilterMap;
     1095  template <typename GR, typename NF, typename EF>
     1096  class SubGraphBase<GR, NF, EF, false>
     1097    : public GraphAdaptorBase<GR> {
     1098  public:
     1099    typedef GR Graph;
     1100    typedef NF NodeFilterMap;
     1101    typedef EF EdgeFilterMap;
    10971102
    10981103    typedef SubGraphBase Adaptor;
    1099     typedef GraphAdaptorBase<_Graph> Parent;
     1104    typedef GraphAdaptorBase<GR> Parent;
    11001105  protected:
    1101     NodeFilterMap* _node_filter_map;
    1102     EdgeFilterMap* _edge_filter_map;
    1103     SubGraphBase() : Parent(),
    1104                      _node_filter_map(0), _edge_filter_map(0) { }
    1105 
    1106     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
    1107       _node_filter_map=&node_filter_map;
    1108     }
    1109     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
    1110       _edge_filter_map=&edge_filter_map;
     1106    NF* _node_filter;
     1107    EF* _edge_filter;
     1108    SubGraphBase()
     1109          : Parent(), _node_filter(0), _edge_filter(0) { }
     1110
     1111    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     1112      Parent::initialize(graph);
     1113      _node_filter = &node_filter;
     1114      _edge_filter = &edge_filter;
    11111115    }
    11121116
     
    11191123    void first(Node& i) const {
    11201124      Parent::first(i);
    1121       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1125      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    11221126    }
    11231127
    11241128    void first(Arc& i) const {
    11251129      Parent::first(i);
    1126       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1130      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11271131    }
    11281132
    11291133    void first(Edge& i) const {
    11301134      Parent::first(i);
    1131       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1135      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11321136    }
    11331137
    11341138    void firstIn(Arc& i, const Node& n) const {
    11351139      Parent::firstIn(i, n);
    1136       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1140      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    11371141    }
    11381142
    11391143    void firstOut(Arc& i, const Node& n) const {
    11401144      Parent::firstOut(i, n);
    1141       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1145      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    11421146    }
    11431147
    11441148    void firstInc(Edge& i, bool& d, const Node& n) const {
    11451149      Parent::firstInc(i, d, n);
    1146       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
     1150      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
    11471151    }
    11481152
    11491153    void next(Node& i) const {
    11501154      Parent::next(i);
    1151       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1155      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    11521156    }
    11531157    void next(Arc& i) const {
    11541158      Parent::next(i);
    1155       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1159      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11561160    }
    11571161    void next(Edge& i) const {
    11581162      Parent::next(i);
    1159       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1163      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11601164    }
    11611165    void nextIn(Arc& i) const {
    11621166      Parent::nextIn(i);
    1163       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1167      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    11641168    }
    11651169
    11661170    void nextOut(Arc& i) const {
    11671171      Parent::nextOut(i);
    1168       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1172      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    11691173    }
    11701174    void nextInc(Edge& i, bool& d) const {
    11711175      Parent::nextInc(i, d);
    1172       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
    1173     }
    1174 
    1175     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
    1176     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
    1177 
    1178     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
    1179     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
     1176      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
     1177    }
     1178
     1179    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     1180    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
     1181
     1182    bool status(const Node& n) const { return (*_node_filter)[n]; }
     1183    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
    11801184
    11811185    typedef False NodeNumTag;
     
    11871191                const Arc& prev = INVALID) const {
    11881192      Arc arc = Parent::findArc(u, v, prev);
    1189       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
     1193      while (arc != INVALID && !(*_edge_filter)[arc]) {
    11901194        arc = Parent::findArc(u, v, arc);
    11911195      }
     
    11971201                  const Edge& prev = INVALID) const {
    11981202      Edge edge = Parent::findEdge(u, v, prev);
    1199       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1203      while (edge != INVALID && !(*_edge_filter)[edge]) {
    12001204        edge = Parent::findEdge(u, v, edge);
    12011205      }
     
    12031207    }
    12041208
    1205     template <typename _Value>
    1206     class NodeMap : public SubMapExtender<Adaptor,
    1207       typename Parent::template NodeMap<_Value> > {
     1209    template <typename V>
     1210    class NodeMap
     1211      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1212          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    12081213    public:
    1209       typedef _Value Value;
    1210       typedef SubMapExtender<Adaptor, typename Parent::
    1211                              template NodeMap<Value> > MapParent;
    1212 
    1213       NodeMap(const Adaptor& adaptor)
    1214         : MapParent(adaptor) {}
    1215       NodeMap(const Adaptor& adaptor, const Value& value)
    1216         : MapParent(adaptor, value) {}
     1214      typedef V Value;
     1215      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1216        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1217
     1218      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1219        : Parent(adaptor) {}
     1220      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1221        : Parent(adaptor, value) {}
    12171222
    12181223    private:
     
    12231228      template <typename CMap>
    12241229      NodeMap& operator=(const CMap& cmap) {
    1225         MapParent::operator=(cmap);
     1230        Parent::operator=(cmap);
    12261231        return *this;
    12271232      }
    12281233    };
    12291234
    1230     template <typename _Value>
    1231     class ArcMap : public SubMapExtender<Adaptor,
    1232       typename Parent::template ArcMap<_Value> > {
     1235    template <typename V>
     1236    class ArcMap
     1237      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1238          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    12331239    public:
    1234       typedef _Value Value;
    1235       typedef SubMapExtender<Adaptor, typename Parent::
    1236                              template ArcMap<Value> > MapParent;
    1237 
    1238       ArcMap(const Adaptor& adaptor)
    1239         : MapParent(adaptor) {}
    1240       ArcMap(const Adaptor& adaptor, const Value& value)
    1241         : MapParent(adaptor, value) {}
     1240      typedef V Value;
     1241      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1242        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1243
     1244      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1245        : Parent(adaptor) {}
     1246      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1247        : Parent(adaptor, value) {}
    12421248
    12431249    private:
     
    12481254      template <typename CMap>
    12491255      ArcMap& operator=(const CMap& cmap) {
    1250         MapParent::operator=(cmap);
     1256        Parent::operator=(cmap);
    12511257        return *this;
    12521258      }
    12531259    };
    12541260
    1255     template <typename _Value>
    1256     class EdgeMap : public SubMapExtender<Adaptor,
    1257       typename Parent::template EdgeMap<_Value> > {
     1261    template <typename V>
     1262    class EdgeMap
     1263      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1264        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    12581265    public:
    1259       typedef _Value Value;
    1260       typedef SubMapExtender<Adaptor, typename Parent::
    1261                              template EdgeMap<Value> > MapParent;
    1262 
    1263       EdgeMap(const Adaptor& adaptor)
    1264         : MapParent(adaptor) {}
    1265 
    1266       EdgeMap(const Adaptor& adaptor, const _Value& value)
    1267         : MapParent(adaptor, value) {}
     1266      typedef V Value;
     1267      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1268                  LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1269
     1270      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1271        : Parent(adaptor) {}
     1272
     1273      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1274        : Parent(adaptor, value) {}
    12681275
    12691276    private:
     
    12741281      template <typename CMap>
    12751282      EdgeMap& operator=(const CMap& cmap) {
    1276         MapParent::operator=(cmap);
     1283        Parent::operator=(cmap);
    12771284        return *this;
    12781285      }
     
    13331340    typedef EF EdgeFilterMap;
    13341341
    1335     typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
     1342    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
    13361343      Parent;
    13371344
     
    13471354    /// Creates a subgraph for the given graph with the given node
    13481355    /// and edge filter maps.
    1349     SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
    1350              EdgeFilterMap& edge_filter_map) {
    1351       setGraph(graph);
    1352       setNodeFilterMap(node_filter_map);
    1353       setEdgeFilterMap(edge_filter_map);
     1356    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
     1357      initialize(graph, node_filter, edge_filter);
    13541358    }
    13551359
     
    14151419  template<typename GR, typename NF, typename EF>
    14161420  SubGraph<const GR, NF, EF>
    1417   subGraph(const GR& graph,
    1418            NF& node_filter_map, EF& edge_filter_map) {
     1421  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
    14191422    return SubGraph<const GR, NF, EF>
    1420       (graph, node_filter_map, edge_filter_map);
     1423      (graph, node_filter, edge_filter);
    14211424  }
    14221425
    14231426  template<typename GR, typename NF, typename EF>
    14241427  SubGraph<const GR, const NF, EF>
    1425   subGraph(const GR& graph,
    1426            const NF& node_filter_map, EF& edge_filter_map) {
     1428  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
    14271429    return SubGraph<const GR, const NF, EF>
    1428       (graph, node_filter_map, edge_filter_map);
     1430      (graph, node_filter, edge_filter);
    14291431  }
    14301432
    14311433  template<typename GR, typename NF, typename EF>
    14321434  SubGraph<const GR, NF, const EF>
    1433   subGraph(const GR& graph,
    1434            NF& node_filter_map, const EF& edge_filter_map) {
     1435  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
    14351436    return SubGraph<const GR, NF, const EF>
    1436       (graph, node_filter_map, edge_filter_map);
     1437      (graph, node_filter, edge_filter);
    14371438  }
    14381439
    14391440  template<typename GR, typename NF, typename EF>
    14401441  SubGraph<const GR, const NF, const EF>
    1441   subGraph(const GR& graph,
    1442            const NF& node_filter_map, const EF& edge_filter_map) {
     1442  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
    14431443    return SubGraph<const GR, const NF, const EF>
    1444       (graph, node_filter_map, edge_filter_map);
     1444      (graph, node_filter, edge_filter);
    14451445  }
    14461446
     
    14821482  class FilterNodes :
    14831483    public DigraphAdaptorExtender<
    1484       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
     1484      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1485                     true> > {
    14851486#endif
    14861487  public:
     
    14901491
    14911492    typedef DigraphAdaptorExtender<
    1492       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
    1493       Parent;
     1493      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1494                     true> > Parent;
    14941495
    14951496    typedef typename Parent::Node Node;
    14961497
    14971498  protected:
    1498     ConstMap<typename Digraph::Arc, bool> const_true_map;
    1499 
    1500     FilterNodes() : const_true_map(true) {
    1501       Parent::setArcFilterMap(const_true_map);
    1502     }
     1499    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
     1500
     1501    FilterNodes() : const_true_map() {}
    15031502
    15041503  public:
     
    15081507    /// Creates a subgraph for the given digraph or graph with the
    15091508    /// given node filter map.
    1510     FilterNodes(GR& graph, NodeFilterMap& node_filter) :
    1511       Parent(), const_true_map(true)
     1509    FilterNodes(GR& graph, NF& node_filter)
     1510      : Parent(), const_true_map()
    15121511    {
    1513       Parent::setDigraph(graph);
    1514       Parent::setNodeFilterMap(node_filter);
    1515       Parent::setArcFilterMap(const_true_map);
     1512      Parent::initialize(graph, node_filter, const_true_map);
    15161513    }
    15171514
     
    15481545                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15491546    public GraphAdaptorExtender<
    1550       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
     1547      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1548                   true> > {
    15511549
    15521550  public:
     
    15541552    typedef NF NodeFilterMap;
    15551553    typedef GraphAdaptorExtender<
    1556       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
    1557       Parent;
     1554      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1555                   true> > Parent;
    15581556
    15591557    typedef typename Parent::Node Node;
    15601558  protected:
    1561     ConstMap<typename Graph::Edge, bool> const_true_map;
    1562 
    1563     FilterNodes() : const_true_map(true) {
    1564       Parent::setEdgeFilterMap(const_true_map);
    1565     }
    1566 
    1567   public:
    1568 
    1569     FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
    1570       Parent(), const_true_map(true) {
    1571       Parent::setGraph(_graph);
    1572       Parent::setNodeFilterMap(node_filter_map);
    1573       Parent::setEdgeFilterMap(const_true_map);
     1559    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
     1560
     1561    FilterNodes() : const_true_map() {}
     1562
     1563  public:
     1564
     1565    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
     1566      Parent(), const_true_map() {
     1567      Parent::initialize(graph, node_filter, const_true_map);
    15741568    }
    15751569
     
    15891583  template<typename GR, typename NF>
    15901584  FilterNodes<const GR, NF>
    1591   filterNodes(const GR& graph, NF& node_filter_map) {
    1592     return FilterNodes<const GR, NF>(graph, node_filter_map);
     1585  filterNodes(const GR& graph, NF& node_filter) {
     1586    return FilterNodes<const GR, NF>(graph, node_filter);
    15931587  }
    15941588
    15951589  template<typename GR, typename NF>
    15961590  FilterNodes<const GR, const NF>
    1597   filterNodes(const GR& graph, const NF& node_filter_map) {
    1598     return FilterNodes<const GR, const NF>(graph, node_filter_map);
     1591  filterNodes(const GR& graph, const NF& node_filter) {
     1592    return FilterNodes<const GR, const NF>(graph, node_filter);
    15991593  }
    16001594
     
    16131607  /// parameter is set to be \c const.
    16141608  ///
    1615   /// \tparam GR The type of the adapted digraph.
     1609  /// \tparam DGR The type of the adapted digraph.
    16161610  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    16171611  /// It can also be specified to be \c const.
     
    16191613  /// It must be a \c bool (or convertible) arc map of the
    16201614  /// adapted digraph. The default type is
    1621   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     1615  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    16221616  ///
    16231617  /// \note The \c Node and \c Arc types of this adaptor and the adapted
    16241618  /// digraph are convertible to each other.
    16251619#ifdef DOXYGEN
    1626   template<typename GR,
     1620  template<typename DGR,
    16271621           typename AF>
    16281622  class FilterArcs {
    16291623#else
    1630   template<typename GR,
    1631            typename AF = typename GR::template ArcMap<bool> >
     1624  template<typename DGR,
     1625           typename AF = typename DGR::template ArcMap<bool> >
    16321626  class FilterArcs :
    16331627    public DigraphAdaptorExtender<
    1634       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
     1628      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1629                     AF, false> > {
    16351630#endif
    16361631  public:
    16371632    /// The type of the adapted digraph.
    1638     typedef GR Digraph;
     1633    typedef DGR Digraph;
    16391634    /// The type of the arc filter map.
    16401635    typedef AF ArcFilterMap;
    16411636
    16421637    typedef DigraphAdaptorExtender<
    1643       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
    1644       Parent;
     1638      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1639                     AF, false> > Parent;
    16451640
    16461641    typedef typename Parent::Arc Arc;
    16471642
    16481643  protected:
    1649     ConstMap<typename Digraph::Node, bool> const_true_map;
    1650 
    1651     FilterArcs() : const_true_map(true) {
    1652       Parent::setNodeFilterMap(const_true_map);
    1653     }
     1644    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
     1645
     1646    FilterArcs() : const_true_map() {}
    16541647
    16551648  public:
     
    16591652    /// Creates a subdigraph for the given digraph with the given arc
    16601653    /// filter map.
    1661     FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
    1662       : Parent(), const_true_map(true) {
    1663       Parent::setDigraph(digraph);
    1664       Parent::setNodeFilterMap(const_true_map);
    1665       Parent::setArcFilterMap(arc_filter);
     1654    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
     1655      : Parent(), const_true_map() {
     1656      Parent::initialize(digraph, const_true_map, arc_filter);
    16661657    }
    16671658
     
    16991690  /// \ingroup graph_adaptors
    17001691  /// \relates FilterArcs
    1701   template<typename GR, typename AF>
    1702   FilterArcs<const GR, AF>
    1703   filterArcs(const GR& digraph, AF& arc_filter_map) {
    1704     return FilterArcs<const GR, AF>(digraph, arc_filter_map);
     1692  template<typename DGR, typename AF>
     1693  FilterArcs<const DGR, AF>
     1694  filterArcs(const DGR& digraph, AF& arc_filter) {
     1695    return FilterArcs<const DGR, AF>(digraph, arc_filter);
    17051696  }
    17061697
    1707   template<typename GR, typename AF>
    1708   FilterArcs<const GR, const AF>
    1709   filterArcs(const GR& digraph, const AF& arc_filter_map) {
    1710     return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
     1698  template<typename DGR, typename AF>
     1699  FilterArcs<const DGR, const AF>
     1700  filterArcs(const DGR& digraph, const AF& arc_filter) {
     1701    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
    17111702  }
    17121703
     
    17441735  class FilterEdges :
    17451736    public GraphAdaptorExtender<
    1746       SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
     1737      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
     1738                   EF, false> > {
    17471739#endif
    17481740  public:
     
    17531745
    17541746    typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
    1756       Parent;
     1747      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1748                   EF, false> > Parent;
    17571749
    17581750    typedef typename Parent::Edge Edge;
    17591751
    17601752  protected:
    1761     ConstMap<typename Graph::Node, bool> const_true_map;
     1753    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
    17621754
    17631755    FilterEdges() : const_true_map(true) {
     
    17711763    /// Creates a subgraph for the given graph with the given edge
    17721764    /// filter map.
    1773     FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
    1774       Parent(), const_true_map(true) {
    1775       Parent::setGraph(graph);
    1776       Parent::setNodeFilterMap(const_true_map);
    1777       Parent::setEdgeFilterMap(edge_filter_map);
     1765    FilterEdges(GR& graph, EF& edge_filter)
     1766      : Parent(), const_true_map() {
     1767      Parent::initialize(graph, const_true_map, edge_filter);
    17781768    }
    17791769
     
    18131803  template<typename GR, typename EF>
    18141804  FilterEdges<const GR, EF>
    1815   filterEdges(const GR& graph, EF& edge_filter_map) {
    1816     return FilterEdges<const GR, EF>(graph, edge_filter_map);
     1805  filterEdges(const GR& graph, EF& edge_filter) {
     1806    return FilterEdges<const GR, EF>(graph, edge_filter);
    18171807  }
    18181808
    18191809  template<typename GR, typename EF>
    18201810  FilterEdges<const GR, const EF>
    1821   filterEdges(const GR& graph, const EF& edge_filter_map) {
    1822     return FilterEdges<const GR, const EF>(graph, edge_filter_map);
     1811  filterEdges(const GR& graph, const EF& edge_filter) {
     1812    return FilterEdges<const GR, const EF>(graph, edge_filter);
    18231813  }
    18241814
    18251815
    1826   template <typename _Digraph>
     1816  template <typename DGR>
    18271817  class UndirectorBase {
    18281818  public:
    1829     typedef _Digraph Digraph;
     1819    typedef DGR Digraph;
    18301820    typedef UndirectorBase Adaptor;
    18311821
     
    20632053  private:
    20642054
    2065     template <typename _Value>
     2055    template <typename V>
    20662056    class ArcMapBase {
    20672057    private:
    20682058
    2069       typedef typename Digraph::template ArcMap<_Value> MapImpl;
     2059      typedef typename DGR::template ArcMap<V> MapImpl;
    20702060
    20712061    public:
     
    20732063      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
    20742064
    2075       typedef _Value Value;
     2065      typedef V Value;
    20762066      typedef Arc Key;
    20772067      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
     
    20802070      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    20812071
    2082       ArcMapBase(const Adaptor& adaptor) :
     2072      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
    20832073        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    20842074
    2085       ArcMapBase(const Adaptor& adaptor, const Value& v)
    2086         : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
    2087 
    2088       void set(const Arc& a, const Value& v) {
     2075      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
     2076        : _forward(*adaptor._digraph, value),
     2077          _backward(*adaptor._digraph, value) {}
     2078
     2079      void set(const Arc& a, const V& value) {
    20892080        if (direction(a)) {
    2090           _forward.set(a, v);
     2081          _forward.set(a, value);
    20912082        } else {
    2092           _backward.set(a, v);
     2083          _backward.set(a, value);
    20932084        }
    20942085      }
     
    21182109  public:
    21192110
    2120     template <typename _Value>
    2121     class NodeMap : public Digraph::template NodeMap<_Value> {
     2111    template <typename V>
     2112    class NodeMap : public DGR::template NodeMap<V> {
    21222113    public:
    21232114
    2124       typedef _Value Value;
    2125       typedef typename Digraph::template NodeMap<Value> Parent;
    2126 
    2127       explicit NodeMap(const Adaptor& adaptor)
     2115      typedef V Value;
     2116      typedef typename DGR::template NodeMap<Value> Parent;
     2117
     2118      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
    21282119        : Parent(*adaptor._digraph) {}
    21292120
    2130       NodeMap(const Adaptor& adaptor, const _Value& value)
     2121      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21312122        : Parent(*adaptor._digraph, value) { }
    21322123
     
    21442135    };
    21452136
    2146     template <typename _Value>
     2137    template <typename V>
    21472138    class ArcMap
    2148       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
     2139      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
    21492140    {
    21502141    public:
    2151       typedef _Value Value;
    2152       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    2153 
    2154       explicit ArcMap(const Adaptor& adaptor)
     2142      typedef V Value;
     2143      typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
     2144
     2145      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
    21552146        : Parent(adaptor) {}
    21562147
    2157       ArcMap(const Adaptor& adaptor, const Value& value)
     2148      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21582149        : Parent(adaptor, value) {}
    21592150
     
    21702161    };
    21712162
    2172     template <typename _Value>
    2173     class EdgeMap : public Digraph::template ArcMap<_Value> {
     2163    template <typename V>
     2164    class EdgeMap : public Digraph::template ArcMap<V> {
    21742165    public:
    21752166
    2176       typedef _Value Value;
    2177       typedef typename Digraph::template ArcMap<Value> Parent;
    2178 
    2179       explicit EdgeMap(const Adaptor& adaptor)
     2167      typedef V Value;
     2168      typedef typename Digraph::template ArcMap<V> Parent;
     2169
     2170      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
    21802171        : Parent(*adaptor._digraph) {}
    21812172
    2182       EdgeMap(const Adaptor& adaptor, const Value& value)
     2173      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21832174        : Parent(*adaptor._digraph, value) {}
    21842175
     
    21962187    };
    21972188
    2198     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     2189    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    21992190    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    22002191
    2201     typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
     2192    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22022193    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    22032194
     
    22062197    UndirectorBase() : _digraph(0) {}
    22072198
    2208     Digraph* _digraph;
    2209 
    2210     void setDigraph(Digraph& digraph) {
     2199    DGR* _digraph;
     2200
     2201    void initialize(DGR& digraph) {
    22112202      _digraph = &digraph;
    22122203    }
     
    22272218  /// parameter is set to be \c const.
    22282219  ///
    2229   /// \tparam GR The type of the adapted digraph.
     2220  /// \tparam DGR The type of the adapted digraph.
    22302221  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    22312222  /// It can also be specified to be \c const.
     
    22372228  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
    22382229  /// of the adapted digraph.)
    2239   template<typename GR>
     2230  template<typename DGR>
    22402231#ifdef DOXYGEN
    22412232  class Undirector {
    22422233#else
    22432234  class Undirector :
    2244     public GraphAdaptorExtender<UndirectorBase<GR> > {
     2235    public GraphAdaptorExtender<UndirectorBase<DGR> > {
    22452236#endif
    22462237  public:
    22472238    /// The type of the adapted digraph.
    2248     typedef GR Digraph;
    2249     typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
     2239    typedef DGR Digraph;
     2240    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22502241  protected:
    22512242    Undirector() { }
     
    22552246    ///
    22562247    /// Creates an undirected graph from the given digraph.
    2257     Undirector(Digraph& digraph) {
    2258       setDigraph(digraph);
     2248    Undirector(DGR& digraph) {
     2249      initialize(digraph);
    22592250    }
    22602251
     
    23562347  /// \ingroup graph_adaptors
    23572348  /// \relates Undirector
    2358   template<typename GR>
    2359   Undirector<const GR> undirector(const GR& digraph) {
    2360     return Undirector<const GR>(digraph);
     2349  template<typename DGR>
     2350  Undirector<const DGR> undirector(const DGR& digraph) {
     2351    return Undirector<const DGR>(digraph);
    23612352  }
    23622353
    23632354
    2364   template <typename _Graph, typename _DirectionMap>
     2355  template <typename GR, typename DM>
    23652356  class OrienterBase {
    23662357  public:
    23672358
    2368     typedef _Graph Graph;
    2369     typedef _DirectionMap DirectionMap;
    2370 
    2371     typedef typename Graph::Node Node;
    2372     typedef typename Graph::Edge Arc;
     2359    typedef GR Graph;
     2360    typedef DM DirectionMap;
     2361
     2362    typedef typename GR::Node Node;
     2363    typedef typename GR::Edge Arc;
    23732364
    23742365    void reverseArc(const Arc& arc) {
     
    24492440    int maxArcId() const { return _graph->maxEdgeId(); }
    24502441
    2451     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     2442    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    24522443    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    24532444
    2454     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     2445    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    24552446    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    24562447
    2457     template <typename _Value>
    2458     class NodeMap : public _Graph::template NodeMap<_Value> {
     2448    template <typename V>
     2449    class NodeMap : public GR::template NodeMap<V> {
    24592450    public:
    24602451
    2461       typedef typename _Graph::template NodeMap<_Value> Parent;
    2462 
    2463       explicit NodeMap(const OrienterBase& adapter)
     2452      typedef typename GR::template NodeMap<V> Parent;
     2453
     2454      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
    24642455        : Parent(*adapter._graph) {}
    24652456
    2466       NodeMap(const OrienterBase& adapter, const _Value& value)
     2457      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
    24672458        : Parent(*adapter._graph, value) {}
    24682459
     
    24802471    };
    24812472
    2482     template <typename _Value>
    2483     class ArcMap : public _Graph::template EdgeMap<_Value> {
     2473    template <typename V>
     2474    class ArcMap : public GR::template EdgeMap<V> {
    24842475    public:
    24852476
    2486       typedef typename Graph::template EdgeMap<_Value> Parent;
    2487 
    2488       explicit ArcMap(const OrienterBase& adapter)
     2477      typedef typename Graph::template EdgeMap<V> Parent;
     2478
     2479      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
    24892480        : Parent(*adapter._graph) { }
    24902481
    2491       ArcMap(const OrienterBase& adapter, const _Value& value)
     2482      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
    24922483        : Parent(*adapter._graph, value) { }
    24932484
     
    25082499  protected:
    25092500    Graph* _graph;
    2510     DirectionMap* _direction;
    2511 
    2512     void setDirectionMap(DirectionMap& direction) {
     2501    DM* _direction;
     2502
     2503    void initialize(GR& graph, DM& direction) {
     2504      _graph = &graph;
    25132505      _direction = &direction;
    2514     }
    2515 
    2516     void setGraph(Graph& graph) {
    2517       _graph = &graph;
    25182506    }
    25192507
     
    25732561    ///
    25742562    /// Constructor of the adaptor.
    2575     Orienter(Graph& graph, DirectionMap& direction) {
    2576       setGraph(graph);
    2577       setDirectionMap(direction);
     2563    Orienter(GR& graph, DM& direction) {
     2564      Parent::initialize(graph, direction);
    25782565    }
    25792566
     
    25952582  template<typename GR, typename DM>
    25962583  Orienter<const GR, DM>
    2597   orienter(const GR& graph, DM& direction_map) {
    2598     return Orienter<const GR, DM>(graph, direction_map);
     2584  orienter(const GR& graph, DM& direction) {
     2585    return Orienter<const GR, DM>(graph, direction);
    25992586  }
    26002587
    26012588  template<typename GR, typename DM>
    26022589  Orienter<const GR, const DM>
    2603   orienter(const GR& graph, const DM& direction_map) {
    2604     return Orienter<const GR, const DM>(graph, direction_map);
     2590  orienter(const GR& graph, const DM& direction) {
     2591    return Orienter<const GR, const DM>(graph, direction);
    26052592  }
    26062593
    26072594  namespace _adaptor_bits {
    26082595
    2609     template<typename Digraph,
    2610              typename CapacityMap,
    2611              typename FlowMap,
    2612              typename Tolerance>
     2596    template <typename DGR, typename CM, typename FM, typename TL>
    26132597    class ResForwardFilter {
    26142598    public:
    26152599
    2616       typedef typename Digraph::Arc Key;
     2600      typedef typename DGR::Arc Key;
    26172601      typedef bool Value;
    26182602
    26192603    private:
    26202604
    2621       const CapacityMap* _capacity;
    2622       const FlowMap* _flow;
    2623       Tolerance _tolerance;
     2605      const CM* _capacity;
     2606      const FM* _flow;
     2607      TL _tolerance;
     2608
    26242609    public:
    26252610
    2626       ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2627                        const Tolerance& tolerance = Tolerance())
     2611      ResForwardFilter(const CM& capacity, const FM& flow,
     2612                       const TL& tolerance = TL())
    26282613        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    26292614
    2630       bool operator[](const typename Digraph::Arc& a) const {
     2615      bool operator[](const typename DGR::Arc& a) const {
    26312616        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
    26322617      }
    26332618    };
    26342619
    2635     template<typename Digraph,
    2636              typename CapacityMap,
    2637              typename FlowMap,
    2638              typename Tolerance>
     2620    template<typename DGR,typename CM, typename FM, typename TL>
    26392621    class ResBackwardFilter {
    26402622    public:
    26412623
    2642       typedef typename Digraph::Arc Key;
     2624      typedef typename DGR::Arc Key;
    26432625      typedef bool Value;
    26442626
    26452627    private:
    26462628
    2647       const CapacityMap* _capacity;
    2648       const FlowMap* _flow;
    2649       Tolerance _tolerance;
     2629      const CM* _capacity;
     2630      const FM* _flow;
     2631      TL _tolerance;
    26502632
    26512633    public:
    26522634
    2653       ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2654                         const Tolerance& tolerance = Tolerance())
     2635      ResBackwardFilter(const CM& capacity, const FM& flow,
     2636                        const TL& tolerance = TL())
    26552637        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    26562638
    2657       bool operator[](const typename Digraph::Arc& a) const {
     2639      bool operator[](const typename DGR::Arc& a) const {
    26582640        return _tolerance.positive((*_flow)[a]);
    26592641      }
     
    26822664  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26832665  ///
    2684   /// \tparam GR The type of the adapted digraph.
     2666  /// \tparam DGR The type of the adapted digraph.
    26852667  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    26862668  /// It is implicitly \c const.
     
    27042686  /// is convertible to the \c Arc type of the adapted digraph.
    27052687#ifdef DOXYGEN
    2706   template<typename GR, typename CM, typename FM, typename TL>
     2688  template<typename DGR, typename CM, typename FM, typename TL>
    27072689  class ResidualDigraph
    27082690#else
    2709   template<typename GR,
    2710            typename CM = typename GR::template ArcMap<int>,
     2691  template<typename DGR,
     2692           typename CM = typename DGR::template ArcMap<int>,
    27112693           typename FM = CM,
    27122694           typename TL = Tolerance<typename CM::Value> >
    2713   class ResidualDigraph :
    2714     public FilterArcs<
    2715       Undirector<const GR>,
    2716       typename Undirector<const GR>::template CombinedArcMap<
    2717         _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
    2718         _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
     2695  class ResidualDigraph
     2696    : public SubDigraph<
     2697        Undirector<const DGR>,
     2698        ConstMap<typename DGR::Node, Const<bool, true> >,
     2699        typename Undirector<const DGR>::template CombinedArcMap<
     2700          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
     2701          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
    27192702#endif
    27202703  {
     
    27222705
    27232706    /// The type of the underlying digraph.
    2724     typedef GR Digraph;
     2707    typedef DGR Digraph;
    27252708    /// The type of the capacity map.
    27262709    typedef CM CapacityMap;
     
    27372720    typedef Undirector<const Digraph> Undirected;
    27382721
    2739     typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
    2740                                             FlowMap, Tolerance> ForwardFilter;
    2741 
    2742     typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
    2743                                              FlowMap, Tolerance> BackwardFilter;
     2722    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
     2723
     2724    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
     2725                                            FM, TL> ForwardFilter;
     2726
     2727    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
     2728                                             FM, TL> BackwardFilter;
    27442729
    27452730    typedef typename Undirected::
    27462731      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    27472732
    2748     typedef FilterArcs<Undirected, ArcFilter> Parent;
     2733    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
    27492734
    27502735    const CapacityMap* _capacity;
     
    27522737
    27532738    Undirected _graph;
     2739    NodeFilter _node_filter;
    27542740    ForwardFilter _forward_filter;
    27552741    BackwardFilter _backward_filter;
     
    27622748    /// Constructor of the residual digraph adaptor. The parameters are the
    27632749    /// digraph, the capacity map, the flow map, and a tolerance object.
    2764     ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity,
    2765                     FlowMap& flow, const Tolerance& tolerance = Tolerance())
    2766       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
     2750    ResidualDigraph(const DGR& digraph, const CM& capacity,
     2751                    FM& flow, const TL& tolerance = Tolerance())
     2752      : Parent(), _capacity(&capacity), _flow(&flow),
     2753        _graph(digraph), _node_filter(),
    27672754        _forward_filter(capacity, flow, tolerance),
    27682755        _backward_filter(capacity, flow, tolerance),
    27692756        _arc_filter(_forward_filter, _backward_filter)
    27702757    {
    2771       Parent::setDigraph(_graph);
    2772       Parent::setArcFilterMap(_arc_filter);
     2758      Parent::initialize(_graph, _node_filter, _arc_filter);
    27732759    }
    27742760
     
    28462832
    28472833      /// Constructor
    2848       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
     2834      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
     2835        : _adaptor(&adaptor) {}
    28492836
    28502837      /// Returns the value associated with the given residual arc
     
    28662853  /// \brief Returns a (read-only) Residual adaptor
    28672854  ///
    2868   /// This function just returns a (read-only) \ref Residual adaptor.
     2855  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
    28692856  /// \ingroup graph_adaptors
    2870   /// \relates Residual
    2871   template<typename GR, typename CM, typename FM>
    2872   ResidualDigraph<GR, CM, FM>
    2873   residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {
    2874     return ResidualDigraph<GR, CM, FM> (digraph, capacity_map, flow_map);
     2857  /// \relates ResidualDigraph
     2858    template<typename DGR, typename CM, typename FM>
     2859  ResidualDigraph<DGR, CM, FM>
     2860  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
     2861    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
    28752862  }
    28762863
    28772864
    2878   template <typename _Digraph>
     2865  template <typename DGR>
    28792866  class SplitNodesBase {
    28802867  public:
    28812868
    2882     typedef _Digraph Digraph;
    2883     typedef DigraphAdaptorBase<const _Digraph> Parent;
     2869    typedef DGR Digraph;
     2870    typedef DigraphAdaptorBase<const DGR> Parent;
    28842871    typedef SplitNodesBase Adaptor;
    28852872
    2886     typedef typename Digraph::Node DigraphNode;
    2887     typedef typename Digraph::Arc DigraphArc;
     2873    typedef typename DGR::Node DigraphNode;
     2874    typedef typename DGR::Arc DigraphArc;
    28882875
    28892876    class Node;
     
    31493136  private:
    31503137
    3151     template <typename _Value>
     3138    template <typename V>
    31523139    class NodeMapBase
    3153       : public MapTraits<typename Parent::template NodeMap<_Value> > {
    3154       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3140      : public MapTraits<typename Parent::template NodeMap<V> > {
     3141      typedef typename Parent::template NodeMap<V> NodeImpl;
    31553142    public:
    31563143      typedef Node Key;
    3157       typedef _Value Value;
     3144      typedef V Value;
    31583145      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
    31593146      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
     
    31623149      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    31633150
    3164       NodeMapBase(const Adaptor& adaptor)
     3151      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
    31653152        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    3166       NodeMapBase(const Adaptor& adaptor, const Value& value)
     3153      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    31673154        : _in_map(*adaptor._digraph, value),
    31683155          _out_map(*adaptor._digraph, value) {}
    31693156
    3170       void set(const Node& key, const Value& val) {
    3171         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
     3157      void set(const Node& key, const V& val) {
     3158        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
    31723159        else {_out_map.set(key, val); }
    31733160      }
    31743161
    31753162      ReturnValue operator[](const Node& key) {
    3176         if (Adaptor::inNode(key)) { return _in_map[key]; }
     3163        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
    31773164        else { return _out_map[key]; }
    31783165      }
     
    31873174    };
    31883175
    3189     template <typename _Value>
     3176    template <typename V>
    31903177    class ArcMapBase
    3191       : public MapTraits<typename Parent::template ArcMap<_Value> > {
    3192       typedef typename Parent::template ArcMap<_Value> ArcImpl;
    3193       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3178      : public MapTraits<typename Parent::template ArcMap<V> > {
     3179      typedef typename Parent::template ArcMap<V> ArcImpl;
     3180      typedef typename Parent::template NodeMap<V> NodeImpl;
    31943181    public:
    31953182      typedef Arc Key;
    3196       typedef _Value Value;
     3183      typedef V Value;
    31973184      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
    31983185      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
     
    32013188      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    32023189
    3203       ArcMapBase(const Adaptor& adaptor)
     3190      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
    32043191        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    3205       ArcMapBase(const Adaptor& adaptor, const Value& value)
     3192      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    32063193        : _arc_map(*adaptor._digraph, value),
    32073194          _node_map(*adaptor._digraph, value) {}
    32083195
    3209       void set(const Arc& key, const Value& val) {
    3210         if (Adaptor::origArc(key)) {
     3196      void set(const Arc& key, const V& val) {
     3197        if (SplitNodesBase<DGR>::origArc(key)) {
    32113198          _arc_map.set(key._item.first(), val);
    32123199        } else {
     
    32163203
    32173204      ReturnValue operator[](const Arc& key) {
    3218         if (Adaptor::origArc(key)) {
     3205        if (SplitNodesBase<DGR>::origArc(key)) {
    32193206          return _arc_map[key._item.first()];
    32203207        } else {
     
    32243211
    32253212      ConstReturnValue operator[](const Arc& key) const {
    3226         if (Adaptor::origArc(key)) {
     3213        if (SplitNodesBase<DGR>::origArc(key)) {
    32273214          return _arc_map[key._item.first()];
    32283215        } else {
     
    32383225  public:
    32393226
    3240     template <typename _Value>
     3227    template <typename V>
    32413228    class NodeMap
    3242       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
     3229      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
    32433230    {
    32443231    public:
    3245       typedef _Value Value;
    3246       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
    3247 
    3248       NodeMap(const Adaptor& adaptor)
     3232      typedef V Value;
     3233      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
     3234
     3235      NodeMap(const SplitNodesBase<DGR>& adaptor)
    32493236        : Parent(adaptor) {}
    32503237
    3251       NodeMap(const Adaptor& adaptor, const Value& value)
     3238      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32523239        : Parent(adaptor, value) {}
    32533240
     
    32643251    };
    32653252
    3266     template <typename _Value>
     3253    template <typename V>
    32673254    class ArcMap
    3268       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
     3255      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
    32693256    {
    32703257    public:
    3271       typedef _Value Value;
    3272       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    3273 
    3274       ArcMap(const Adaptor& adaptor)
     3258      typedef V Value;
     3259      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
     3260
     3261      ArcMap(const SplitNodesBase<DGR>& adaptor)
    32753262        : Parent(adaptor) {}
    32763263
    3277       ArcMap(const Adaptor& adaptor, const Value& value)
     3264      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32783265        : Parent(adaptor, value) {}
    32793266
     
    32943281    SplitNodesBase() : _digraph(0) {}
    32953282
    3296     Digraph* _digraph;
    3297 
    3298     void setDigraph(Digraph& digraph) {
     3283    DGR* _digraph;
     3284
     3285    void initialize(Digraph& digraph) {
    32993286      _digraph = &digraph;
    33003287    }
     
    33233310  /// in the adaptor.
    33243311  ///
    3325   /// \tparam GR The type of the adapted digraph.
     3312  /// \tparam DGR The type of the adapted digraph.
    33263313  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    33273314  /// It is implicitly \c const.
     
    33293316  /// \note The \c Node type of this adaptor is converible to the \c Node
    33303317  /// type of the adapted digraph.
    3331   template <typename GR>
     3318  template <typename DGR>
    33323319#ifdef DOXYGEN
    33333320  class SplitNodes {
    33343321#else
    33353322  class SplitNodes
    3336     : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
     3323    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33373324#endif
    33383325  public:
    3339     typedef GR Digraph;
    3340     typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
    3341 
    3342     typedef typename Digraph::Node DigraphNode;
    3343     typedef typename Digraph::Arc DigraphArc;
     3326    typedef DGR Digraph;
     3327    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
     3328
     3329    typedef typename DGR::Node DigraphNode;
     3330    typedef typename DGR::Arc DigraphArc;
    33443331
    33453332    typedef typename Parent::Node Node;
     
    33493336    ///
    33503337    /// Constructor of the adaptor.
    3351     SplitNodes(const Digraph& g) {
    3352       Parent::setDigraph(g);
     3338    SplitNodes(const DGR& g) {
     3339      Parent::initialize(g);
    33533340    }
    33543341
     
    34423429      /// Returns the value associated with the given key.
    34433430      Value operator[](const Key& key) const {
    3444         if (Parent::inNode(key)) {
     3431        if (SplitNodesBase<const DGR>::inNode(key)) {
    34453432          return _in_map[key];
    34463433        } else {
     
    34513438      /// Returns a reference to the value associated with the given key.
    34523439      Value& operator[](const Key& key) {
    3453         if (Parent::inNode(key)) {
     3440        if (SplitNodesBase<const DGR>::inNode(key)) {
    34543441          return _in_map[key];
    34553442        } else {
     
    34603447      /// Sets the value associated with the given key.
    34613448      void set(const Key& key, const Value& value) {
    3462         if (Parent::inNode(key)) {
     3449        if (SplitNodesBase<const DGR>::inNode(key)) {
    34633450          _in_map.set(key, value);
    34643451        } else {
     
    35313518      /// Returns the value associated with the given key.
    35323519      Value operator[](const Key& arc) const {
    3533         if (Parent::origArc(arc)) {
     3520        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35343521          return _arc_map[arc];
    35353522        } else {
     
    35403527      /// Returns a reference to the value associated with the given key.
    35413528      Value& operator[](const Key& arc) {
    3542         if (Parent::origArc(arc)) {
     3529        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35433530          return _arc_map[arc];
    35443531        } else {
     
    35493536      /// Sets the value associated with the given key.
    35503537      void set(const Arc& arc, const Value& val) {
    3551         if (Parent::origArc(arc)) {
     3538        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35523539          _arc_map.set(arc, val);
    35533540        } else {
     
    35953582  /// \ingroup graph_adaptors
    35963583  /// \relates SplitNodes
    3597   template<typename GR>
    3598   SplitNodes<GR>
    3599   splitNodes(const GR& digraph) {
    3600     return SplitNodes<GR>(digraph);
     3584  template<typename DGR>
     3585  SplitNodes<DGR>
     3586  splitNodes(const DGR& digraph) {
     3587    return SplitNodes<DGR>(digraph);
    36013588  }
    36023589
     3590#undef LEMON_SCOPE_FIX
     3591
    36033592} //namespace lemon
    36043593
  • lemon/edge_set.h

    r491 r559  
    3030namespace lemon {
    3131
    32   template <typename _Graph>
     32  template <typename GR>
    3333  class ListArcSetBase {
    3434  public:
    3535
    36     typedef _Graph Graph;
    37     typedef typename Graph::Node Node;
    38     typedef typename Graph::NodeIt NodeIt;
     36    typedef GR Graph;
     37    typedef typename GR::Node Node;
     38    typedef typename GR::NodeIt NodeIt;
    3939
    4040  protected:
     
    4545    };
    4646
    47     typedef typename ItemSetTraits<Graph, Node>::
     47    typedef typename ItemSetTraits<GR, Node>::
    4848    template Map<NodeT>::Type NodesImplBase;
    4949
    50     NodesImplBase* nodes;
     50    NodesImplBase* _nodes;
    5151
    5252    struct ArcT {
     
    6262    int first_free_arc;
    6363
    64     const Graph* graph;
    65 
    66     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    67       graph = &_graph;
    68       nodes = &_nodes;
     64    const GR* _graph;
     65
     66    void initalize(const GR& graph, NodesImplBase& nodes) {
     67      _graph = &graph;
     68      _nodes = &nodes;
    6969    }
    7070
     
    7272
    7373    class Arc {
    74       friend class ListArcSetBase<Graph>;
     74      friend class ListArcSetBase<GR>;
    7575    protected:
    7676      Arc(int _id) : id(_id) {}
     
    9595        first_free_arc = arcs[first_free_arc].next_in;
    9696      }
    97       arcs[n].next_in = (*nodes)[v].first_in;
    98       if ((*nodes)[v].first_in != -1) {
    99         arcs[(*nodes)[v].first_in].prev_in = n;
    100       }
    101       (*nodes)[v].first_in = n;
    102       arcs[n].next_out = (*nodes)[u].first_out;
    103       if ((*nodes)[u].first_out != -1) {
    104         arcs[(*nodes)[u].first_out].prev_out = n;
    105       }
    106       (*nodes)[u].first_out = n;
     97      arcs[n].next_in = (*_nodes)[v].first_in;
     98      if ((*_nodes)[v].first_in != -1) {
     99        arcs[(*_nodes)[v].first_in].prev_in = n;
     100      }
     101      (*_nodes)[v].first_in = n;
     102      arcs[n].next_out = (*_nodes)[u].first_out;
     103      if ((*_nodes)[u].first_out != -1) {
     104        arcs[(*_nodes)[u].first_out].prev_out = n;
     105      }
     106      (*_nodes)[u].first_out = n;
    107107      arcs[n].source = u;
    108108      arcs[n].target = v;
     
    115115        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
    116116      } else {
    117         (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
     117        (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
    118118      }
    119119      if (arcs[n].next_in != -1) {
     
    124124        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    125125      } else {
    126         (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
     126        (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
    127127      }
    128128      if (arcs[n].next_out != -1) {
     
    135135      Node node;
    136136      for (first(node); node != INVALID; next(node)) {
    137         (*nodes)[node].first_in = -1;
    138         (*nodes)[node].first_out = -1;
     137        (*_nodes)[node].first_in = -1;
     138        (*_nodes)[node].first_out = -1;
    139139      }
    140140      arcs.clear();
     
    144144
    145145    void first(Node& node) const {
    146       graph->first(node);
     146      _graph->first(node);
    147147    }
    148148
    149149    void next(Node& node) const {
    150       graph->next(node);
     150      _graph->next(node);
    151151    }
    152152
     
    154154      Node node;
    155155      first(node);
    156       while (node != INVALID && (*nodes)[node].first_in == -1) {
     156      while (node != INVALID && (*_nodes)[node].first_in == -1) {
    157157        next(node);
    158158      }
    159       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
     159      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
    160160    }
    161161
     
    166166        Node node = arcs[arc.id].target;
    167167        next(node);
    168         while (node != INVALID && (*nodes)[node].first_in == -1) {
     168        while (node != INVALID && (*_nodes)[node].first_in == -1) {
    169169          next(node);
    170170        }
    171         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
     171        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
    172172      }
    173173    }
    174174
    175175    void firstOut(Arc& arc, const Node& node) const {
    176       arc.id = (*nodes)[node].first_out;
     176      arc.id = (*_nodes)[node].first_out;
    177177    }
    178178
     
    182182
    183183    void firstIn(Arc& arc, const Node& node) const {
    184       arc.id = (*nodes)[node].first_in;
     184      arc.id = (*_nodes)[node].first_in;
    185185    }
    186186
     
    189189    }
    190190
    191     int id(const Node& node) const { return graph->id(node); }
     191    int id(const Node& node) const { return _graph->id(node); }
    192192    int id(const Arc& arc) const { return arc.id; }
    193193
    194     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
     194    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
    195195    Arc arcFromId(int ix) const { return Arc(ix); }
    196196
    197     int maxNodeId() const { return graph->maxNodeId(); };
     197    int maxNodeId() const { return _graph->maxNodeId(); };
    198198    int maxArcId() const { return arcs.size() - 1; }
    199199
     
    201201    Node target(const Arc& arc) const { return arcs[arc.id].target;}
    202202
    203     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     203    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    204204
    205205    NodeNotifier& notifier(Node) const {
    206       return graph->notifier(Node());
    207     }
    208 
    209     template <typename _Value>
    210     class NodeMap : public Graph::template NodeMap<_Value> {
     206      return _graph->notifier(Node());
     207    }
     208
     209    template <typename V>
     210    class NodeMap : public GR::template NodeMap<V> {
    211211    public:
    212212
    213       typedef typename _Graph::template NodeMap<_Value> Parent;
    214 
    215       explicit NodeMap(const ListArcSetBase<Graph>& arcset)
    216         : Parent(*arcset.graph) {}
    217 
    218       NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
    219         : Parent(*arcset.graph, value) {}
     213      typedef typename GR::template NodeMap<V> Parent;
     214
     215      explicit NodeMap(const ListArcSetBase<GR>& arcset)
     216        : Parent(*arcset._graph) {}
     217
     218      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
     219        : Parent(*arcset._graph, value) {}
    220220
    221221      NodeMap& operator=(const NodeMap& cmap) {
     
    251251  /// all arcs incident to the given node is erased from the arc set.
    252252  ///
    253   /// \param _Graph The type of the graph which shares its node set with
     253  /// \param GR The type of the graph which shares its node set with
    254254  /// this class. Its interface must conform to the
    255255  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
     
    258258  /// This class is fully conform to the \ref concepts::Digraph
    259259  /// "Digraph" concept.
    260   template <typename _Graph>
    261   class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
    262 
    263   public:
    264 
    265     typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
     260  template <typename GR>
     261  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
     262
     263  public:
     264
     265    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
    266266
    267267    typedef typename Parent::Node Node;
    268268    typedef typename Parent::Arc Arc;
    269269
    270     typedef _Graph Graph;
     270    typedef GR Graph;
    271271
    272272
     
    296296      typedef NodesImplBase Parent;
    297297
    298       NodesImpl(const Graph& graph, ListArcSet& arcset)
     298      NodesImpl(const GR& graph, ListArcSet& arcset)
    299299        : Parent(graph), _arcset(arcset) {}
    300300
     
    322322    };
    323323
    324     NodesImpl nodes;
     324    NodesImpl _nodes;
    325325
    326326  public:
     
    329329    ///
    330330    /// Constructor of the ArcSet.
    331     ListArcSet(const Graph& graph) : nodes(graph, *this) {
    332       Parent::initalize(graph, nodes);
     331    ListArcSet(const GR& graph) : _nodes(graph, *this) {
     332      Parent::initalize(graph, _nodes);
    333333    }
    334334
     
    351351  };
    352352
    353   template <typename _Graph>
     353  template <typename GR>
    354354  class ListEdgeSetBase {
    355355  public:
    356356
    357     typedef _Graph Graph;
    358     typedef typename Graph::Node Node;
    359     typedef typename Graph::NodeIt NodeIt;
     357    typedef GR Graph;
     358    typedef typename GR::Node Node;
     359    typedef typename GR::NodeIt NodeIt;
    360360
    361361  protected:
     
    366366    };
    367367
    368     typedef typename ItemSetTraits<Graph, Node>::
     368    typedef typename ItemSetTraits<GR, Node>::
    369369    template Map<NodeT>::Type NodesImplBase;
    370370
    371     NodesImplBase* nodes;
     371    NodesImplBase* _nodes;
    372372
    373373    struct ArcT {
     
    382382    int first_free_arc;
    383383
    384     const Graph* graph;
    385 
    386     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    387       graph = &_graph;
    388       nodes = &_nodes;
     384    const GR* _graph;
     385
     386    void initalize(const GR& graph, NodesImplBase& nodes) {
     387      _graph = &graph;
     388      _nodes = &nodes;
    389389    }
    390390
     
    438438      arcs[n | 1].target = v;
    439439
    440       arcs[n].next_out = (*nodes)[v].first_out;
    441       if ((*nodes)[v].first_out != -1) {
    442         arcs[(*nodes)[v].first_out].prev_out = n;
    443       }
    444       (*nodes)[v].first_out = n;
     440      arcs[n].next_out = (*_nodes)[v].first_out;
     441      if ((*_nodes)[v].first_out != -1) {
     442        arcs[(*_nodes)[v].first_out].prev_out = n;
     443      }
     444      (*_nodes)[v].first_out = n;
    445445      arcs[n].prev_out = -1;
    446446
    447       if ((*nodes)[u].first_out != -1) {
    448         arcs[(*nodes)[u].first_out].prev_out = (n | 1);
    449       }
    450       arcs[n | 1].next_out = (*nodes)[u].first_out;
    451       (*nodes)[u].first_out = (n | 1);
     447      if ((*_nodes)[u].first_out != -1) {
     448        arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
     449      }
     450      arcs[n | 1].next_out = (*_nodes)[u].first_out;
     451      (*_nodes)[u].first_out = (n | 1);
    452452      arcs[n | 1].prev_out = -1;
    453453
     
    465465        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    466466      } else {
    467         (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
     467        (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
    468468      }
    469469
     
    475475        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    476476      } else {
    477         (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
     477        (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
    478478      }
    479479
     
    486486      Node node;
    487487      for (first(node); node != INVALID; next(node)) {
    488         (*nodes)[node].first_out = -1;
     488        (*_nodes)[node].first_out = -1;
    489489      }
    490490      arcs.clear();
     
    494494
    495495    void first(Node& node) const {
    496       graph->first(node);
     496      _graph->first(node);
    497497    }
    498498
    499499    void next(Node& node) const {
    500       graph->next(node);
     500      _graph->next(node);
    501501    }
    502502
     
    504504      Node node;
    505505      first(node);
    506       while (node != INVALID && (*nodes)[node].first_out == -1) {
     506      while (node != INVALID && (*_nodes)[node].first_out == -1) {
    507507        next(node);
    508508      }
    509       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
     509      arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
    510510    }
    511511
     
    516516        Node node = arcs[arc.id ^ 1].target;
    517517        next(node);
    518         while(node != INVALID && (*nodes)[node].first_out == -1) {
     518        while(node != INVALID && (*_nodes)[node].first_out == -1) {
    519519          next(node);
    520520        }
    521         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
     521        arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
    522522      }
    523523    }
     
    527527      first(node);
    528528      while (node != INVALID) {
    529         edge.id = (*nodes)[node].first_out;
     529        edge.id = (*_nodes)[node].first_out;
    530530        while ((edge.id & 1) != 1) {
    531531          edge.id = arcs[edge.id].next_out;
     
    552552      next(node);
    553553      while (node != INVALID) {
    554         edge.id = (*nodes)[node].first_out;
     554        edge.id = (*_nodes)[node].first_out;
    555555        while ((edge.id & 1) != 1) {
    556556          edge.id = arcs[edge.id].next_out;
     
    566566
    567567    void firstOut(Arc& arc, const Node& node) const {
    568       arc.id = (*nodes)[node].first_out;
     568      arc.id = (*_nodes)[node].first_out;
    569569    }
    570570
     
    574574
    575575    void firstIn(Arc& arc, const Node& node) const {
    576       arc.id = (((*nodes)[node].first_out) ^ 1);
     576      arc.id = (((*_nodes)[node].first_out) ^ 1);
    577577      if (arc.id == -2) arc.id = -1;
    578578    }
     
    584584
    585585    void firstInc(Edge &arc, bool& dir, const Node& node) const {
    586       int de = (*nodes)[node].first_out;
     586      int de = (*_nodes)[node].first_out;
    587587      if (de != -1 ) {
    588588        arc.id = de / 2;
     
    612612    }
    613613
    614     int id(const Node& node) const { return graph->id(node); }
     614    int id(const Node& node) const { return _graph->id(node); }
    615615    static int id(Arc e) { return e.id; }
    616616    static int id(Edge e) { return e.id; }
    617617
    618     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     618    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
    619619    static Arc arcFromId(int id) { return Arc(id);}
    620620    static Edge edgeFromId(int id) { return Edge(id);}
    621621
    622     int maxNodeId() const { return graph->maxNodeId(); };
     622    int maxNodeId() const { return _graph->maxNodeId(); };
    623623    int maxEdgeId() const { return arcs.size() / 2 - 1; }
    624624    int maxArcId() const { return arcs.size()-1; }
     
    630630    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
    631631
    632     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     632    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    633633
    634634    NodeNotifier& notifier(Node) const {
    635       return graph->notifier(Node());
    636     }
    637 
    638     template <typename _Value>
    639     class NodeMap : public Graph::template NodeMap<_Value> {
     635      return _graph->notifier(Node());
     636    }
     637
     638    template <typename V>
     639    class NodeMap : public GR::template NodeMap<V> {
    640640    public:
    641641
    642       typedef typename _Graph::template NodeMap<_Value> Parent;
    643 
    644       explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
    645         : Parent(*arcset.graph) {}
    646 
    647       NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
    648         : Parent(*arcset.graph, value) {}
     642      typedef typename GR::template NodeMap<V> Parent;
     643
     644      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
     645        : Parent(*arcset._graph) {}
     646
     647      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
     648        : Parent(*arcset._graph, value) {}
    649649
    650650      NodeMap& operator=(const NodeMap& cmap) {
     
    680680  /// incident to the given node is erased from the arc set.
    681681  ///
    682   /// \param _Graph The type of the graph which shares its node set
     682  /// \param GR The type of the graph which shares its node set
    683683  /// with this class. Its interface must conform to the
    684684  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
     
    687687  /// This class is fully conform to the \ref concepts::Graph "Graph"
    688688  /// concept.
    689   template <typename _Graph>
    690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
    691 
    692   public:
    693 
    694     typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
     689  template <typename GR>
     690  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
     691
     692  public:
     693
     694    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
    695695
    696696    typedef typename Parent::Node Node;
     
    698698    typedef typename Parent::Edge Edge;
    699699
    700     typedef _Graph Graph;
     700    typedef GR Graph;
    701701
    702702
     
    721721      typedef NodesImplBase Parent;
    722722
    723       NodesImpl(const Graph& graph, ListEdgeSet& arcset)
     723      NodesImpl(const GR& graph, ListEdgeSet& arcset)
    724724        : Parent(graph), _arcset(arcset) {}
    725725
     
    747747    };
    748748
    749     NodesImpl nodes;
     749    NodesImpl _nodes;
    750750
    751751  public:
     
    754754    ///
    755755    /// Constructor of the EdgeSet.
    756     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
    757       Parent::initalize(graph, nodes);
     756    ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
     757      Parent::initalize(graph, _nodes);
    758758    }
    759759
     
    776776  };
    777777
    778   template <typename _Graph>
     778  template <typename GR>
    779779  class SmartArcSetBase {
    780780  public:
    781781
    782     typedef _Graph Graph;
     782    typedef GR Graph;
    783783    typedef typename Graph::Node Node;
    784784    typedef typename Graph::NodeIt NodeIt;
     
    791791    };
    792792
    793     typedef typename ItemSetTraits<Graph, Node>::
     793    typedef typename ItemSetTraits<GR, Node>::
    794794    template Map<NodeT>::Type NodesImplBase;
    795795
    796     NodesImplBase* nodes;
     796    NodesImplBase* _nodes;
    797797
    798798    struct ArcT {
     
    804804    std::vector<ArcT> arcs;
    805805
    806     const Graph* graph;
    807 
    808     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    809       graph = &_graph;
    810       nodes = &_nodes;
     806    const GR* _graph;
     807
     808    void initalize(const GR& graph, NodesImplBase& nodes) {
     809      _graph = &graph;
     810      _nodes = &nodes;
    811811    }
    812812
     
    814814
    815815    class Arc {
    816       friend class SmartArcSetBase<Graph>;
     816      friend class SmartArcSetBase<GR>;
    817817    protected:
    818818      Arc(int _id) : id(_id) {}
     
    831831      int n = arcs.size();
    832832      arcs.push_back(ArcT());
    833       arcs[n].next_in = (*nodes)[v].first_in;
    834       (*nodes)[v].first_in = n;
    835       arcs[n].next_out = (*nodes)[u].first_out;
    836       (*nodes)[u].first_out = n;
     833      arcs[n].next_in = (*_nodes)[v].first_in;
     834      (*_nodes)[v].first_in = n;
     835      arcs[n].next_out = (*_nodes)[u].first_out;
     836      (*_nodes)[u].first_out = n;
    837837      arcs[n].source = u;
    838838      arcs[n].target = v;
     
    843843      Node node;
    844844      for (first(node); node != INVALID; next(node)) {
    845         (*nodes)[node].first_in = -1;
    846         (*nodes)[node].first_out = -1;
     845        (*_nodes)[node].first_in = -1;
     846        (*_nodes)[node].first_out = -1;
    847847      }
    848848      arcs.clear();
     
    850850
    851851    void first(Node& node) const {
    852       graph->first(node);
     852      _graph->first(node);
    853853    }
    854854
    855855    void next(Node& node) const {
    856       graph->next(node);
     856      _graph->next(node);
    857857    }
    858858
     
    866866
    867867    void firstOut(Arc& arc, const Node& node) const {
    868       arc.id = (*nodes)[node].first_out;
     868      arc.id = (*_nodes)[node].first_out;
    869869    }
    870870
     
    874874
    875875    void firstIn(Arc& arc, const Node& node) const {
    876       arc.id = (*nodes)[node].first_in;
     876      arc.id = (*_nodes)[node].first_in;
    877877    }
    878878
     
    881881    }
    882882
    883     int id(const Node& node) const { return graph->id(node); }
     883    int id(const Node& node) const { return _graph->id(node); }
    884884    int id(const Arc& arc) const { return arc.id; }
    885885
    886     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
     886    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
    887887    Arc arcFromId(int ix) const { return Arc(ix); }
    888888
    889     int maxNodeId() const { return graph->maxNodeId(); };
     889    int maxNodeId() const { return _graph->maxNodeId(); };
    890890    int maxArcId() const { return arcs.size() - 1; }
    891891
     
    893893    Node target(const Arc& arc) const { return arcs[arc.id].target;}
    894894
    895     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     895    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    896896
    897897    NodeNotifier& notifier(Node) const {
    898       return graph->notifier(Node());
    899     }
    900 
    901     template <typename _Value>
    902     class NodeMap : public Graph::template NodeMap<_Value> {
     898      return _graph->notifier(Node());
     899    }
     900
     901    template <typename V>
     902    class NodeMap : public GR::template NodeMap<V> {
    903903    public:
    904904
    905       typedef typename _Graph::template NodeMap<_Value> Parent;
    906 
    907       explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
    908         : Parent(*arcset.graph) { }
    909 
    910       NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
    911         : Parent(*arcset.graph, value) { }
     905      typedef typename GR::template NodeMap<V> Parent;
     906
     907      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
     908        : Parent(*arcset._graph) { }
     909
     910      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
     911        : Parent(*arcset._graph, value) { }
    912912
    913913      NodeMap& operator=(const NodeMap& cmap) {
     
    938938  /// iterators) works equivalently as in the original graph.
    939939  ///
    940   /// \param _Graph The type of the graph which shares its node set with
     940  /// \param GR The type of the graph which shares its node set with
    941941  /// this class. Its interface must conform to the
    942942  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
     
    955955  /// This class is fully conform to the \ref concepts::Digraph
    956956  /// "Digraph" concept.
    957   template <typename _Graph>
    958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
    959 
    960   public:
    961 
    962     typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
     957  template <typename GR>
     958  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
     959
     960  public:
     961
     962    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
    963963
    964964    typedef typename Parent::Node Node;
    965965    typedef typename Parent::Arc Arc;
    966966
    967     typedef _Graph Graph;
     967    typedef GR Graph;
    968968
    969969  protected:
     
    987987      typedef NodesImplBase Parent;
    988988
    989       NodesImpl(const Graph& graph, SmartArcSet& arcset)
     989      NodesImpl(const GR& graph, SmartArcSet& arcset)
    990990        : Parent(graph), _arcset(arcset) {}
    991991
     
    10271027    };
    10281028
    1029     NodesImpl nodes;
     1029    NodesImpl _nodes;
    10301030
    10311031  public:
     
    10341034    ///
    10351035    /// Constructor of the ArcSet.
    1036     SmartArcSet(const Graph& graph) : nodes(graph, *this) {
    1037       Parent::initalize(graph, nodes);
     1036    SmartArcSet(const GR& graph) : _nodes(graph, *this) {
     1037      Parent::initalize(graph, _nodes);
    10381038    }
    10391039
     
    10531053    /// erased and it is not isolated in the ArcSet.
    10541054    bool valid() const {
    1055       return nodes.attached();
     1055      return _nodes.attached();
    10561056    }
    10571057
     
    10591059
    10601060
    1061   template <typename _Graph>
     1061  template <typename GR>
    10621062  class SmartEdgeSetBase {
    10631063  public:
    10641064
    1065     typedef _Graph Graph;
    1066     typedef typename Graph::Node Node;
    1067     typedef typename Graph::NodeIt NodeIt;
     1065    typedef GR Graph;
     1066    typedef typename GR::Node Node;
     1067    typedef typename GR::NodeIt NodeIt;
    10681068
    10691069  protected:
     
    10741074    };
    10751075
    1076     typedef typename ItemSetTraits<Graph, Node>::
     1076    typedef typename ItemSetTraits<GR, Node>::
    10771077    template Map<NodeT>::Type NodesImplBase;
    10781078
    1079     NodesImplBase* nodes;
     1079    NodesImplBase* _nodes;
    10801080
    10811081    struct ArcT {
     
    10871087    std::vector<ArcT> arcs;
    10881088
    1089     const Graph* graph;
    1090 
    1091     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    1092       graph = &_graph;
    1093       nodes = &_nodes;
     1089    const GR* _graph;
     1090
     1091    void initalize(const GR& graph, NodesImplBase& nodes) {
     1092      _graph = &graph;
     1093      _nodes = &nodes;
    10941094    }
    10951095
     
    11361136      arcs[n | 1].target = v;
    11371137
    1138       arcs[n].next_out = (*nodes)[v].first_out;
    1139       (*nodes)[v].first_out = n;
    1140 
    1141       arcs[n | 1].next_out = (*nodes)[u].first_out;
    1142       (*nodes)[u].first_out = (n | 1);
     1138      arcs[n].next_out = (*_nodes)[v].first_out;
     1139      (*_nodes)[v].first_out = n;
     1140
     1141      arcs[n | 1].next_out = (*_nodes)[u].first_out;
     1142      (*_nodes)[u].first_out = (n | 1);
    11431143
    11441144      return Edge(n / 2);
     
    11481148      Node node;
    11491149      for (first(node); node != INVALID; next(node)) {
    1150         (*nodes)[node].first_out = -1;
     1150        (*_nodes)[node].first_out = -1;
    11511151      }
    11521152      arcs.clear();
     
    11541154
    11551155    void first(Node& node) const {
    1156       graph->first(node);
     1156      _graph->first(node);
    11571157    }
    11581158
    11591159    void next(Node& node) const {
    1160       graph->next(node);
     1160      _graph->next(node);
    11611161    }
    11621162
     
    11781178
    11791179    void firstOut(Arc& arc, const Node& node) const {
    1180       arc.id = (*nodes)[node].first_out;
     1180      arc.id = (*_nodes)[node].first_out;
    11811181    }
    11821182
     
    11861186
    11871187    void firstIn(Arc& arc, const Node& node) const {
    1188       arc.id = (((*nodes)[node].first_out) ^ 1);
     1188      arc.id = (((*_nodes)[node].first_out) ^ 1);
    11891189      if (arc.id == -2) arc.id = -1;
    11901190    }
     
    11961196
    11971197    void firstInc(Edge &arc, bool& dir, const Node& node) const {
    1198       int de = (*nodes)[node].first_out;
     1198      int de = (*_nodes)[node].first_out;
    11991199      if (de != -1 ) {
    12001200        arc.id = de / 2;
     
    12241224    }
    12251225
    1226     int id(Node node) const { return graph->id(node); }
     1226    int id(Node node) const { return _graph->id(node); }
    12271227    static int id(Arc arc) { return arc.id; }
    12281228    static int id(Edge arc) { return arc.id; }
    12291229
    1230     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     1230    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
    12311231    static Arc arcFromId(int id) { return Arc(id); }
    12321232    static Edge edgeFromId(int id) { return Edge(id);}
    12331233
    1234     int maxNodeId() const { return graph->maxNodeId(); };
     1234    int maxNodeId() const { return _graph->maxNodeId(); };
    12351235    int maxArcId() const { return arcs.size() - 1; }
    12361236    int maxEdgeId() const { return arcs.size() / 2 - 1; }
     
    12421242    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
    12431243
    1244     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     1244    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    12451245
    12461246    NodeNotifier& notifier(Node) const {
    1247       return graph->notifier(Node());
    1248     }
    1249 
    1250     template <typename _Value>
    1251     class NodeMap : public Graph::template NodeMap<_Value> {
     1247      return _graph->notifier(Node());
     1248    }
     1249
     1250    template <typename V>
     1251    class NodeMap : public GR::template NodeMap<V> {
    12521252    public:
    12531253
    1254       typedef typename _Graph::template NodeMap<_Value> Parent;
    1255 
    1256       explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
    1257         : Parent(*arcset.graph) { }
    1258 
    1259       NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
    1260         : Parent(*arcset.graph, value) { }
     1254      typedef typename GR::template NodeMap<V> Parent;
     1255
     1256      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
     1257        : Parent(*arcset._graph) { }
     1258
     1259      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
     1260        : Parent(*arcset._graph, value) { }
    12611261
    12621262      NodeMap& operator=(const NodeMap& cmap) {
     
    12861286  /// works equivalently as in the original graph.
    12871287  ///
    1288   /// \param _Graph The type of the graph which shares its node set
     1288  /// \param GR The type of the graph which shares its node set
    12891289  /// with this class. Its interface must conform to the
    12901290  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
     
    13031303  /// This class is fully conform to the \ref concepts::Graph
    13041304  /// "Graph" concept.
    1305   template <typename _Graph>
    1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
    1307 
    1308   public:
    1309 
    1310     typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
     1305  template <typename GR>
     1306  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
     1307
     1308  public:
     1309
     1310    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
    13111311
    13121312    typedef typename Parent::Node Node;
     
    13141314    typedef typename Parent::Edge Edge;
    13151315
    1316     typedef _Graph Graph;
     1316    typedef GR Graph;
    13171317
    13181318  protected:
     
    13351335      typedef NodesImplBase Parent;
    13361336
    1337       NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
     1337      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
    13381338        : Parent(graph), _arcset(arcset) {}
    13391339
     
    13751375    };
    13761376
    1377     NodesImpl nodes;
     1377    NodesImpl _nodes;
    13781378
    13791379  public:
     
    13821382    ///
    13831383    /// Constructor of the EdgeSet.
    1384     SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
    1385       Parent::initalize(graph, nodes);
     1384    SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
     1385      Parent::initalize(graph, _nodes);
    13861386    }
    13871387
     
    14011401    /// erased and it is not isolated in the EdgeSet.
    14021402    bool valid() const {
    1403       return nodes.attached();
     1403      return _nodes.attached();
    14041404    }
    14051405
  • test/CMakeLists.txt

    r554 r559  
    1111
    1212SET(TESTS
    13 #   adaptors_test
     13  adaptors_test
    1414  bfs_test
    1515  circulation_test
     
    1919  dijkstra_test
    2020  dim_test
    21 #   edge_set_test
     21  edge_set_test
    2222  error_test
    2323  graph_copy_test
  • test/edge_set_test.cc

    r491 r559  
    3434
    3535void checkSmartArcSet() {
    36   checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
     36  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
    3737
    3838  typedef ListDigraph Digraph;
     
    100100
    101101void checkListArcSet() {
    102   checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
     102  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
    103103
    104104  typedef ListDigraph Digraph;
     
    180180
    181181void checkSmartEdgeSet() {
    182   checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
     182  checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();
    183183
    184184  typedef ListDigraph Digraph;
     
    264264
    265265void checkListEdgeSet() {
    266   checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
     266  checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();
    267267
    268268  typedef ListDigraph Digraph;
Note: See TracChangeset for help on using the changeset viewer.