lemon/adaptors.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 01 Jan 2009 00:00:00 +0100
changeset 440 88ed40ad0d4f
parent 416 76287c8caa26
child 455 5a1e9fdcfd3a
permissions -rw-r--r--
Happy New Year again
- update the copyright headers + run the source unifier
deba@416
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@414
     2
 *
deba@416
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@414
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@414
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414
     8
 *
deba@414
     9
 * Permission to use, modify and distribute this software is granted
deba@414
    10
 * provided that this copyright notice appears in all copies. For
deba@414
    11
 * precise terms see the accompanying LICENSE file.
deba@414
    12
 *
deba@414
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@414
    14
 * express or implied, and with no claim as to its suitability for any
deba@414
    15
 * purpose.
deba@414
    16
 *
deba@414
    17
 */
deba@414
    18
deba@416
    19
#ifndef LEMON_ADAPTORS_H
deba@416
    20
#define LEMON_ADAPTORS_H
deba@416
    21
deba@416
    22
/// \ingroup graph_adaptors
deba@416
    23
/// \file
deba@416
    24
/// \brief Several graph adaptors
deba@414
    25
///
deba@416
    26
/// This file contains several useful adaptors for digraphs and graphs.
deba@414
    27
deba@414
    28
#include <lemon/core.h>
deba@414
    29
#include <lemon/maps.h>
deba@414
    30
#include <lemon/bits/variant.h>
deba@414
    31
deba@414
    32
#include <lemon/bits/graph_adaptor_extender.h>
deba@414
    33
#include <lemon/tolerance.h>
deba@414
    34
deba@414
    35
#include <algorithm>
deba@414
    36
deba@414
    37
namespace lemon {
deba@414
    38
deba@414
    39
  template<typename _Digraph>
deba@414
    40
  class DigraphAdaptorBase {
deba@414
    41
  public:
deba@414
    42
    typedef _Digraph Digraph;
deba@414
    43
    typedef DigraphAdaptorBase Adaptor;
deba@414
    44
    typedef Digraph ParentDigraph;
deba@414
    45
deba@414
    46
  protected:
deba@414
    47
    Digraph* _digraph;
deba@414
    48
    DigraphAdaptorBase() : _digraph(0) { }
deba@414
    49
    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
deba@414
    50
deba@414
    51
  public:
deba@414
    52
    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
deba@414
    53
deba@414
    54
    typedef typename Digraph::Node Node;
deba@414
    55
    typedef typename Digraph::Arc Arc;
deba@416
    56
deba@414
    57
    void first(Node& i) const { _digraph->first(i); }
deba@414
    58
    void first(Arc& i) const { _digraph->first(i); }
deba@414
    59
    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
deba@414
    60
    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
deba@414
    61
deba@414
    62
    void next(Node& i) const { _digraph->next(i); }
deba@414
    63
    void next(Arc& i) const { _digraph->next(i); }
deba@414
    64
    void nextIn(Arc& i) const { _digraph->nextIn(i); }
deba@414
    65
    void nextOut(Arc& i) const { _digraph->nextOut(i); }
deba@414
    66
deba@414
    67
    Node source(const Arc& a) const { return _digraph->source(a); }
deba@414
    68
    Node target(const Arc& a) const { return _digraph->target(a); }
deba@414
    69
deba@414
    70
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
deba@414
    71
    int nodeNum() const { return _digraph->nodeNum(); }
deba@416
    72
deba@414
    73
    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
deba@414
    74
    int arcNum() const { return _digraph->arcNum(); }
deba@414
    75
deba@414
    76
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@414
    77
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
deba@414
    78
      return _digraph->findArc(u, v, prev);
deba@414
    79
    }
deba@416
    80
deba@414
    81
    Node addNode() { return _digraph->addNode(); }
deba@414
    82
    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
deba@414
    83
deba@414
    84
    void erase(const Node& n) const { _digraph->erase(n); }
deba@414
    85
    void erase(const Arc& a) const { _digraph->erase(a); }
deba@416
    86
deba@414
    87
    void clear() const { _digraph->clear(); }
deba@416
    88
deba@414
    89
    int id(const Node& n) const { return _digraph->id(n); }
deba@414
    90
    int id(const Arc& a) const { return _digraph->id(a); }
deba@414
    91
deba@414
    92
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414
    93
    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414
    94
deba@414
    95
    int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414
    96
    int maxArcId() const { return _digraph->maxArcId(); }
deba@414
    97
deba@414
    98
    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
deba@416
    99
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414
   100
deba@414
   101
    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
deba@416
   102
    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
deba@416
   103
deba@414
   104
    template <typename _Value>
deba@414
   105
    class NodeMap : public Digraph::template NodeMap<_Value> {
deba@414
   106
    public:
deba@414
   107
deba@414
   108
      typedef typename Digraph::template NodeMap<_Value> Parent;
deba@414
   109
deba@416
   110
      explicit NodeMap(const Adaptor& adaptor)
deba@416
   111
        : Parent(*adaptor._digraph) {}
deba@414
   112
deba@414
   113
      NodeMap(const Adaptor& adaptor, const _Value& value)
deba@416
   114
        : Parent(*adaptor._digraph, value) { }
deba@414
   115
deba@414
   116
    private:
deba@414
   117
      NodeMap& operator=(const NodeMap& cmap) {
deba@414
   118
        return operator=<NodeMap>(cmap);
deba@414
   119
      }
deba@414
   120
deba@414
   121
      template <typename CMap>
deba@414
   122
      NodeMap& operator=(const CMap& cmap) {
deba@414
   123
        Parent::operator=(cmap);
deba@414
   124
        return *this;
deba@414
   125
      }
deba@416
   126
deba@414
   127
    };
deba@414
   128
deba@414
   129
    template <typename _Value>
deba@414
   130
    class ArcMap : public Digraph::template ArcMap<_Value> {
deba@414
   131
    public:
deba@416
   132
deba@414
   133
      typedef typename Digraph::template ArcMap<_Value> Parent;
deba@416
   134
deba@416
   135
      explicit ArcMap(const Adaptor& adaptor)
deba@416
   136
        : Parent(*adaptor._digraph) {}
deba@414
   137
deba@414
   138
      ArcMap(const Adaptor& adaptor, const _Value& value)
deba@416
   139
        : Parent(*adaptor._digraph, value) {}
deba@414
   140
deba@414
   141
    private:
deba@414
   142
      ArcMap& operator=(const ArcMap& cmap) {
deba@414
   143
        return operator=<ArcMap>(cmap);
deba@414
   144
      }
deba@414
   145
deba@414
   146
      template <typename CMap>
deba@414
   147
      ArcMap& operator=(const CMap& cmap) {
deba@414
   148
        Parent::operator=(cmap);
deba@414
   149
        return *this;
deba@414
   150
      }
deba@414
   151
deba@414
   152
    };
deba@414
   153
deba@414
   154
  };
deba@414
   155
deba@416
   156
  template<typename _Graph>
deba@416
   157
  class GraphAdaptorBase {
deba@416
   158
  public:
deba@416
   159
    typedef _Graph Graph;
deba@416
   160
    typedef Graph ParentGraph;
deba@416
   161
deba@416
   162
  protected:
deba@416
   163
    Graph* _graph;
deba@416
   164
deba@416
   165
    GraphAdaptorBase() : _graph(0) {}
deba@416
   166
deba@416
   167
    void setGraph(Graph& graph) { _graph = &graph; }
deba@416
   168
deba@416
   169
  public:
deba@416
   170
    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
deba@416
   171
deba@416
   172
    typedef typename Graph::Node Node;
deba@416
   173
    typedef typename Graph::Arc Arc;
deba@416
   174
    typedef typename Graph::Edge Edge;
deba@416
   175
deba@416
   176
    void first(Node& i) const { _graph->first(i); }
deba@416
   177
    void first(Arc& i) const { _graph->first(i); }
deba@416
   178
    void first(Edge& i) const { _graph->first(i); }
deba@416
   179
    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
deba@416
   180
    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
deba@416
   181
    void firstInc(Edge &i, bool &d, const Node &n) const {
deba@416
   182
      _graph->firstInc(i, d, n);
deba@416
   183
    }
deba@416
   184
deba@416
   185
    void next(Node& i) const { _graph->next(i); }
deba@416
   186
    void next(Arc& i) const { _graph->next(i); }
deba@416
   187
    void next(Edge& i) const { _graph->next(i); }
deba@416
   188
    void nextIn(Arc& i) const { _graph->nextIn(i); }
deba@416
   189
    void nextOut(Arc& i) const { _graph->nextOut(i); }
deba@416
   190
    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
deba@416
   191
deba@416
   192
    Node u(const Edge& e) const { return _graph->u(e); }
deba@416
   193
    Node v(const Edge& e) const { return _graph->v(e); }
deba@416
   194
deba@416
   195
    Node source(const Arc& a) const { return _graph->source(a); }
deba@416
   196
    Node target(const Arc& a) const { return _graph->target(a); }
deba@416
   197
deba@416
   198
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416
   199
    int nodeNum() const { return _graph->nodeNum(); }
deba@416
   200
deba@416
   201
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@416
   202
    int arcNum() const { return _graph->arcNum(); }
deba@416
   203
    int edgeNum() const { return _graph->edgeNum(); }
deba@416
   204
deba@416
   205
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
   206
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
deba@416
   207
      return _graph->findArc(u, v, prev);
deba@416
   208
    }
deba@416
   209
    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
deba@416
   210
      return _graph->findEdge(u, v, prev);
deba@416
   211
    }
deba@416
   212
deba@416
   213
    Node addNode() { return _graph->addNode(); }
deba@416
   214
    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
deba@416
   215
deba@416
   216
    void erase(const Node& i) { _graph->erase(i); }
deba@416
   217
    void erase(const Edge& i) { _graph->erase(i); }
deba@416
   218
deba@416
   219
    void clear() { _graph->clear(); }
deba@416
   220
deba@416
   221
    bool direction(const Arc& a) const { return _graph->direction(a); }
deba@416
   222
    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
deba@416
   223
deba@416
   224
    int id(const Node& v) const { return _graph->id(v); }
deba@416
   225
    int id(const Arc& a) const { return _graph->id(a); }
deba@416
   226
    int id(const Edge& e) const { return _graph->id(e); }
deba@416
   227
deba@416
   228
    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@416
   229
    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
deba@416
   230
    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
deba@416
   231
deba@416
   232
    int maxNodeId() const { return _graph->maxNodeId(); }
deba@416
   233
    int maxArcId() const { return _graph->maxArcId(); }
deba@416
   234
    int maxEdgeId() const { return _graph->maxEdgeId(); }
deba@416
   235
deba@416
   236
    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@416
   237
    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416
   238
deba@416
   239
    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@416
   240
    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416
   241
deba@416
   242
    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@416
   243
    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
deba@416
   244
deba@416
   245
    template <typename _Value>
deba@416
   246
    class NodeMap : public Graph::template NodeMap<_Value> {
deba@416
   247
    public:
deba@416
   248
      typedef typename Graph::template NodeMap<_Value> Parent;
deba@416
   249
      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
deba@416
   250
        : Parent(*adapter._graph) {}
deba@416
   251
      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416
   252
        : Parent(*adapter._graph, value) {}
deba@416
   253
deba@416
   254
    private:
deba@416
   255
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
   256
        return operator=<NodeMap>(cmap);
deba@416
   257
      }
deba@416
   258
deba@416
   259
      template <typename CMap>
deba@416
   260
      NodeMap& operator=(const CMap& cmap) {
deba@416
   261
        Parent::operator=(cmap);
deba@416
   262
        return *this;
deba@416
   263
      }
deba@416
   264
deba@416
   265
    };
deba@416
   266
deba@416
   267
    template <typename _Value>
deba@416
   268
    class ArcMap : public Graph::template ArcMap<_Value> {
deba@416
   269
    public:
deba@416
   270
      typedef typename Graph::template ArcMap<_Value> Parent;
deba@416
   271
      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
deba@416
   272
        : Parent(*adapter._graph) {}
deba@416
   273
      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416
   274
        : Parent(*adapter._graph, value) {}
deba@416
   275
deba@416
   276
    private:
deba@416
   277
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
   278
        return operator=<ArcMap>(cmap);
deba@416
   279
      }
deba@416
   280
deba@416
   281
      template <typename CMap>
deba@416
   282
      ArcMap& operator=(const CMap& cmap) {
deba@416
   283
        Parent::operator=(cmap);
deba@416
   284
        return *this;
deba@416
   285
      }
deba@416
   286
    };
deba@416
   287
deba@416
   288
    template <typename _Value>
deba@416
   289
    class EdgeMap : public Graph::template EdgeMap<_Value> {
deba@416
   290
    public:
deba@416
   291
      typedef typename Graph::template EdgeMap<_Value> Parent;
deba@416
   292
      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
deba@416
   293
        : Parent(*adapter._graph) {}
deba@416
   294
      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416
   295
        : Parent(*adapter._graph, value) {}
deba@416
   296
deba@416
   297
    private:
deba@416
   298
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@416
   299
        return operator=<EdgeMap>(cmap);
deba@416
   300
      }
deba@416
   301
deba@416
   302
      template <typename CMap>
deba@416
   303
      EdgeMap& operator=(const CMap& cmap) {
deba@416
   304
        Parent::operator=(cmap);
deba@416
   305
        return *this;
deba@416
   306
      }
deba@416
   307
    };
deba@416
   308
deba@416
   309
  };
deba@414
   310
deba@414
   311
  template <typename _Digraph>
deba@416
   312
  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
deba@414
   313
  public:
deba@414
   314
    typedef _Digraph Digraph;
deba@414
   315
    typedef DigraphAdaptorBase<_Digraph> Parent;
deba@414
   316
  protected:
deba@416
   317
    ReverseDigraphBase() : Parent() { }
deba@414
   318
  public:
deba@414
   319
    typedef typename Parent::Node Node;
deba@414
   320
    typedef typename Parent::Arc Arc;
deba@414
   321
deba@414
   322
    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
deba@414
   323
    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
deba@414
   324
deba@414
   325
    void nextIn(Arc& a) const { Parent::nextOut(a); }
deba@414
   326
    void nextOut(Arc& a) const { Parent::nextIn(a); }
deba@414
   327
deba@414
   328
    Node source(const Arc& a) const { return Parent::target(a); }
deba@414
   329
    Node target(const Arc& a) const { return Parent::source(a); }
deba@414
   330
deba@416
   331
    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
deba@416
   332
deba@414
   333
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416
   334
    Arc findArc(const Node& u, const Node& v,
deba@416
   335
                const Arc& prev = INVALID) {
deba@414
   336
      return Parent::findArc(v, u, prev);
deba@414
   337
    }
deba@414
   338
deba@414
   339
  };
deba@416
   340
deba@416
   341
  /// \ingroup graph_adaptors
deba@414
   342
  ///
deba@416
   343
  /// \brief A digraph adaptor which reverses the orientation of the arcs.
deba@414
   344
  ///
deba@416
   345
  /// ReverseDigraph reverses the arcs in the adapted digraph. The
deba@416
   346
  /// SubDigraph is conform to the \ref concepts::Digraph
deba@416
   347
  /// "Digraph concept".
deba@414
   348
  ///
deba@416
   349
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416
   350
  /// "Digraph concept". The type can be specified to be const.
deba@414
   351
  template<typename _Digraph>
deba@416
   352
  class ReverseDigraph :
deba@416
   353
    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
deba@414
   354
  public:
deba@414
   355
    typedef _Digraph Digraph;
deba@414
   356
    typedef DigraphAdaptorExtender<
deba@416
   357
      ReverseDigraphBase<_Digraph> > Parent;
deba@414
   358
  protected:
deba@416
   359
    ReverseDigraph() { }
deba@414
   360
  public:
deba@415
   361
deba@415
   362
    /// \brief Constructor
deba@415
   363
    ///
deba@416
   364
    /// Creates a reverse digraph adaptor for the given digraph
deba@416
   365
    explicit ReverseDigraph(Digraph& digraph) {
deba@416
   366
      Parent::setDigraph(digraph);
deba@414
   367
    }
deba@414
   368
  };
deba@414
   369
deba@414
   370
  /// \brief Just gives back a reverse digraph adaptor
deba@414
   371
  ///
deba@414
   372
  /// Just gives back a reverse digraph adaptor
deba@414
   373
  template<typename Digraph>
deba@416
   374
  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
deba@416
   375
    return ReverseDigraph<const Digraph>(digraph);
deba@414
   376
  }
deba@414
   377
deba@416
   378
  template <typename _Digraph, typename _NodeFilterMap,
deba@416
   379
            typename _ArcFilterMap, bool _checked = true>
deba@416
   380
  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
deba@414
   381
  public:
deba@414
   382
    typedef _Digraph Digraph;
deba@414
   383
    typedef _NodeFilterMap NodeFilterMap;
deba@414
   384
    typedef _ArcFilterMap ArcFilterMap;
deba@414
   385
deba@416
   386
    typedef SubDigraphBase Adaptor;
deba@414
   387
    typedef DigraphAdaptorBase<_Digraph> Parent;
deba@414
   388
  protected:
deba@414
   389
    NodeFilterMap* _node_filter;
deba@414
   390
    ArcFilterMap* _arc_filter;
deba@416
   391
    SubDigraphBase()
deba@414
   392
      : Parent(), _node_filter(0), _arc_filter(0) { }
deba@414
   393
deba@414
   394
    void setNodeFilterMap(NodeFilterMap& node_filter) {
deba@414
   395
      _node_filter = &node_filter;
deba@414
   396
    }
deba@414
   397
    void setArcFilterMap(ArcFilterMap& arc_filter) {
deba@414
   398
      _arc_filter = &arc_filter;
deba@414
   399
    }
deba@414
   400
deba@414
   401
  public:
deba@414
   402
deba@414
   403
    typedef typename Parent::Node Node;
deba@414
   404
    typedef typename Parent::Arc Arc;
deba@414
   405
deba@416
   406
    void first(Node& i) const {
deba@416
   407
      Parent::first(i);
deba@416
   408
      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414
   409
    }
deba@414
   410
deba@416
   411
    void first(Arc& i) const {
deba@416
   412
      Parent::first(i);
deba@416
   413
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   414
                              || !(*_node_filter)[Parent::source(i)]
deba@416
   415
                              || !(*_node_filter)[Parent::target(i)]))
deba@416
   416
        Parent::next(i);
deba@414
   417
    }
deba@414
   418
deba@416
   419
    void firstIn(Arc& i, const Node& n) const {
deba@416
   420
      Parent::firstIn(i, n);
deba@416
   421
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   422
                              || !(*_node_filter)[Parent::source(i)]))
deba@416
   423
        Parent::nextIn(i);
deba@414
   424
    }
deba@414
   425
deba@416
   426
    void firstOut(Arc& i, const Node& n) const {
deba@416
   427
      Parent::firstOut(i, n);
deba@416
   428
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   429
                              || !(*_node_filter)[Parent::target(i)]))
deba@416
   430
        Parent::nextOut(i);
deba@414
   431
    }
deba@414
   432
deba@416
   433
    void next(Node& i) const {
deba@416
   434
      Parent::next(i);
deba@416
   435
      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414
   436
    }
deba@414
   437
deba@416
   438
    void next(Arc& i) const {
deba@416
   439
      Parent::next(i);
deba@416
   440
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   441
                              || !(*_node_filter)[Parent::source(i)]
deba@416
   442
                              || !(*_node_filter)[Parent::target(i)]))
deba@416
   443
        Parent::next(i);
deba@414
   444
    }
deba@414
   445
deba@416
   446
    void nextIn(Arc& i) const {
deba@416
   447
      Parent::nextIn(i);
deba@416
   448
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   449
                              || !(*_node_filter)[Parent::source(i)]))
deba@416
   450
        Parent::nextIn(i);
deba@414
   451
    }
deba@414
   452
deba@416
   453
    void nextOut(Arc& i) const {
deba@416
   454
      Parent::nextOut(i);
deba@416
   455
      while (i != INVALID && (!(*_arc_filter)[i]
deba@416
   456
                              || !(*_node_filter)[Parent::target(i)]))
deba@416
   457
        Parent::nextOut(i);
deba@414
   458
    }
deba@414
   459
deba@414
   460
    void hide(const Node& n) const { _node_filter->set(n, false); }
deba@414
   461
    void hide(const Arc& a) const { _arc_filter->set(a, false); }
deba@414
   462
deba@415
   463
    void unHide(const Node& n) const { _node_filter->set(n, true); }
deba@414
   464
    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
deba@414
   465
deba@414
   466
    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
deba@414
   467
    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
deba@414
   468
deba@414
   469
    typedef False NodeNumTag;
deba@414
   470
    typedef False EdgeNumTag;
deba@414
   471
deba@414
   472
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416
   473
    Arc findArc(const Node& source, const Node& target,
deba@416
   474
                const Arc& prev = INVALID) {
deba@414
   475
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
deba@414
   476
        return INVALID;
deba@414
   477
      }
deba@414
   478
      Arc arc = Parent::findArc(source, target, prev);
deba@414
   479
      while (arc != INVALID && !(*_arc_filter)[arc]) {
deba@414
   480
        arc = Parent::findArc(source, target, arc);
deba@414
   481
      }
deba@414
   482
      return arc;
deba@414
   483
    }
deba@414
   484
deba@414
   485
    template <typename _Value>
deba@416
   486
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
   487
      typename Parent::template NodeMap<_Value> > {
deba@414
   488
    public:
deba@414
   489
      typedef _Value Value;
deba@414
   490
      typedef SubMapExtender<Adaptor, typename Parent::
deba@414
   491
                             template NodeMap<Value> > MapParent;
deba@416
   492
deba@416
   493
      NodeMap(const Adaptor& adaptor)
deba@416
   494
        : MapParent(adaptor) {}
deba@416
   495
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
   496
        : MapParent(adaptor, value) {}
deba@416
   497
deba@414
   498
    private:
deba@414
   499
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
   500
        return operator=<NodeMap>(cmap);
deba@414
   501
      }
deba@416
   502
deba@414
   503
      template <typename CMap>
deba@414
   504
      NodeMap& operator=(const CMap& cmap) {
deba@414
   505
        MapParent::operator=(cmap);
deba@416
   506
        return *this;
deba@414
   507
      }
deba@414
   508
    };
deba@414
   509
deba@414
   510
    template <typename _Value>
deba@416
   511
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
   512
      typename Parent::template ArcMap<_Value> > {
deba@414
   513
    public:
deba@414
   514
      typedef _Value Value;
deba@414
   515
      typedef SubMapExtender<Adaptor, typename Parent::
deba@414
   516
                             template ArcMap<Value> > MapParent;
deba@416
   517
deba@416
   518
      ArcMap(const Adaptor& adaptor)
deba@416
   519
        : MapParent(adaptor) {}
deba@416
   520
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
   521
        : MapParent(adaptor, value) {}
deba@416
   522
deba@414
   523
    private:
deba@414
   524
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
   525
        return operator=<ArcMap>(cmap);
deba@414
   526
      }
deba@416
   527
deba@414
   528
      template <typename CMap>
deba@414
   529
      ArcMap& operator=(const CMap& cmap) {
deba@414
   530
        MapParent::operator=(cmap);
deba@416
   531
        return *this;
deba@414
   532
      }
deba@414
   533
    };
deba@414
   534
deba@414
   535
  };
deba@414
   536
deba@414
   537
  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
deba@416
   538
  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
deba@414
   539
    : public DigraphAdaptorBase<_Digraph> {
deba@414
   540
  public:
deba@414
   541
    typedef _Digraph Digraph;
deba@414
   542
    typedef _NodeFilterMap NodeFilterMap;
deba@414
   543
    typedef _ArcFilterMap ArcFilterMap;
deba@414
   544
deba@416
   545
    typedef SubDigraphBase Adaptor;
deba@414
   546
    typedef DigraphAdaptorBase<Digraph> Parent;
deba@414
   547
  protected:
deba@414
   548
    NodeFilterMap* _node_filter;
deba@414
   549
    ArcFilterMap* _arc_filter;
deba@416
   550
    SubDigraphBase()
deba@414
   551
      : Parent(), _node_filter(0), _arc_filter(0) { }
deba@414
   552
deba@414
   553
    void setNodeFilterMap(NodeFilterMap& node_filter) {
deba@414
   554
      _node_filter = &node_filter;
deba@414
   555
    }
deba@414
   556
    void setArcFilterMap(ArcFilterMap& arc_filter) {
deba@414
   557
      _arc_filter = &arc_filter;
deba@414
   558
    }
deba@414
   559
deba@414
   560
  public:
deba@414
   561
deba@414
   562
    typedef typename Parent::Node Node;
deba@414
   563
    typedef typename Parent::Arc Arc;
deba@414
   564
deba@416
   565
    void first(Node& i) const {
deba@416
   566
      Parent::first(i);
deba@416
   567
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414
   568
    }
deba@414
   569
deba@416
   570
    void first(Arc& i) const {
deba@416
   571
      Parent::first(i);
deba@416
   572
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
deba@414
   573
    }
deba@414
   574
deba@416
   575
    void firstIn(Arc& i, const Node& n) const {
deba@416
   576
      Parent::firstIn(i, n);
deba@416
   577
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
deba@414
   578
    }
deba@414
   579
deba@416
   580
    void firstOut(Arc& i, const Node& n) const {
deba@416
   581
      Parent::firstOut(i, n);
deba@416
   582
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
deba@414
   583
    }
deba@414
   584
deba@416
   585
    void next(Node& i) const {
deba@416
   586
      Parent::next(i);
deba@416
   587
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414
   588
    }
deba@416
   589
    void next(Arc& i) const {
deba@416
   590
      Parent::next(i);
deba@416
   591
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
deba@414
   592
    }
deba@416
   593
    void nextIn(Arc& i) const {
deba@416
   594
      Parent::nextIn(i);
deba@416
   595
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
deba@414
   596
    }
deba@414
   597
deba@416
   598
    void nextOut(Arc& i) const {
deba@416
   599
      Parent::nextOut(i);
deba@416
   600
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
deba@414
   601
    }
deba@414
   602
deba@414
   603
    void hide(const Node& n) const { _node_filter->set(n, false); }
deba@414
   604
    void hide(const Arc& e) const { _arc_filter->set(e, false); }
deba@414
   605
deba@415
   606
    void unHide(const Node& n) const { _node_filter->set(n, true); }
deba@414
   607
    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
deba@414
   608
deba@414
   609
    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
deba@414
   610
    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
deba@414
   611
deba@414
   612
    typedef False NodeNumTag;
deba@414
   613
    typedef False EdgeNumTag;
deba@414
   614
deba@414
   615
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416
   616
    Arc findArc(const Node& source, const Node& target,
deba@416
   617
                const Arc& prev = INVALID) {
deba@414
   618
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
deba@414
   619
        return INVALID;
deba@414
   620
      }
deba@414
   621
      Arc arc = Parent::findArc(source, target, prev);
deba@414
   622
      while (arc != INVALID && !(*_arc_filter)[arc]) {
deba@414
   623
        arc = Parent::findArc(source, target, arc);
deba@414
   624
      }
deba@414
   625
      return arc;
deba@414
   626
    }
deba@414
   627
deba@414
   628
    template <typename _Value>
deba@416
   629
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
   630
      typename Parent::template NodeMap<_Value> > {
deba@414
   631
    public:
deba@414
   632
      typedef _Value Value;
deba@414
   633
      typedef SubMapExtender<Adaptor, typename Parent::
deba@414
   634
                             template NodeMap<Value> > MapParent;
deba@416
   635
deba@416
   636
      NodeMap(const Adaptor& adaptor)
deba@416
   637
        : MapParent(adaptor) {}
deba@416
   638
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
   639
        : MapParent(adaptor, value) {}
deba@416
   640
deba@414
   641
    private:
deba@414
   642
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
   643
        return operator=<NodeMap>(cmap);
deba@414
   644
      }
deba@416
   645
deba@414
   646
      template <typename CMap>
deba@414
   647
      NodeMap& operator=(const CMap& cmap) {
deba@414
   648
        MapParent::operator=(cmap);
deba@416
   649
        return *this;
deba@414
   650
      }
deba@414
   651
    };
deba@414
   652
deba@414
   653
    template <typename _Value>
deba@416
   654
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
   655
      typename Parent::template ArcMap<_Value> > {
deba@414
   656
    public:
deba@414
   657
      typedef _Value Value;
deba@414
   658
      typedef SubMapExtender<Adaptor, typename Parent::
deba@414
   659
                             template ArcMap<Value> > MapParent;
deba@416
   660
deba@416
   661
      ArcMap(const Adaptor& adaptor)
deba@416
   662
        : MapParent(adaptor) {}
deba@416
   663
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
   664
        : MapParent(adaptor, value) {}
deba@416
   665
deba@414
   666
    private:
deba@414
   667
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
   668
        return operator=<ArcMap>(cmap);
deba@414
   669
      }
deba@416
   670
deba@414
   671
      template <typename CMap>
deba@414
   672
      ArcMap& operator=(const CMap& cmap) {
deba@414
   673
        MapParent::operator=(cmap);
deba@416
   674
        return *this;
deba@414
   675
      }
deba@414
   676
    };
deba@414
   677
deba@414
   678
  };
deba@414
   679
deba@414
   680
  /// \ingroup graph_adaptors
deba@414
   681
  ///
deba@416
   682
  /// \brief An adaptor for hiding nodes and arcs in a digraph
deba@416
   683
  ///
deba@416
   684
  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
deba@416
   685
  /// and a bool arc map must be specified, which define the filters
deba@416
   686
  /// for nodes and arcs. Just the nodes and arcs with true value are
deba@416
   687
  /// shown in the subdigraph. The SubDigraph is conform to the \ref
deba@416
   688
  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
deba@416
   689
  /// is true, then the arcs incident to filtered nodes are also
deba@416
   690
  /// filtered out.
deba@416
   691
  ///
deba@416
   692
  /// \tparam _Digraph It must be conform to the \ref
deba@416
   693
  /// concepts::Digraph "Digraph concept". The type can be specified
deba@416
   694
  /// to const.
deba@416
   695
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
deba@416
   696
  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
deba@416
   697
  /// \tparam _checked If the parameter is false then the arc filtering
deba@416
   698
  /// is not checked with respect to node filter. Otherwise, each arc
deba@416
   699
  /// is automatically filtered, which is incident to a filtered node.
deba@416
   700
  ///
deba@416
   701
  /// \see FilterNodes
deba@416
   702
  /// \see FilterArcs
deba@416
   703
  template<typename _Digraph,
deba@416
   704
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416
   705
           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
deba@416
   706
           bool _checked = true>
deba@416
   707
  class SubDigraph
deba@416
   708
    : public DigraphAdaptorExtender<
deba@416
   709
      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
deba@414
   710
  public:
deba@414
   711
    typedef _Digraph Digraph;
deba@414
   712
    typedef _NodeFilterMap NodeFilterMap;
deba@414
   713
    typedef _ArcFilterMap ArcFilterMap;
deba@414
   714
deba@414
   715
    typedef DigraphAdaptorExtender<
deba@416
   716
      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
deba@414
   717
    Parent;
deba@414
   718
deba@415
   719
    typedef typename Parent::Node Node;
deba@415
   720
    typedef typename Parent::Arc Arc;
deba@415
   721
deba@414
   722
  protected:
deba@416
   723
    SubDigraph() { }
deba@414
   724
  public:
deba@414
   725
deba@415
   726
    /// \brief Constructor
deba@415
   727
    ///
deba@416
   728
    /// Creates a subdigraph for the given digraph with
deba@415
   729
    /// given node and arc map filters.
deba@416
   730
    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
deba@416
   731
               ArcFilterMap& arc_filter) {
deba@414
   732
      setDigraph(digraph);
deba@414
   733
      setNodeFilterMap(node_filter);
deba@414
   734
      setArcFilterMap(arc_filter);
deba@414
   735
    }
deba@414
   736
deba@415
   737
    /// \brief Hides the node of the graph
deba@415
   738
    ///
deba@416
   739
    /// This function hides \c n in the digraph, i.e. the iteration
deba@416
   740
    /// jumps over it. This is done by simply setting the value of \c n
deba@415
   741
    /// to be false in the corresponding node-map.
deba@415
   742
    void hide(const Node& n) const { Parent::hide(n); }
deba@415
   743
deba@415
   744
    /// \brief Hides the arc of the graph
deba@415
   745
    ///
deba@416
   746
    /// This function hides \c a in the digraph, i.e. the iteration
deba@415
   747
    /// jumps over it. This is done by simply setting the value of \c a
deba@415
   748
    /// to be false in the corresponding arc-map.
deba@415
   749
    void hide(const Arc& a) const { Parent::hide(a); }
deba@415
   750
deba@415
   751
    /// \brief Unhides the node of the graph
deba@415
   752
    ///
deba@416
   753
    /// The value of \c n is set to be true in the node-map which stores
deba@416
   754
    /// hide information. If \c n was hidden previuosly, then it is shown
deba@415
   755
    /// again
deba@415
   756
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@415
   757
deba@415
   758
    /// \brief Unhides the arc of the graph
deba@415
   759
    ///
deba@416
   760
    /// The value of \c a is set to be true in the arc-map which stores
deba@416
   761
    /// hide information. If \c a was hidden previuosly, then it is shown
deba@415
   762
    /// again
deba@415
   763
    void unHide(const Arc& a) const { Parent::unHide(a); }
deba@415
   764
deba@415
   765
    /// \brief Returns true if \c n is hidden.
deba@415
   766
    ///
deba@415
   767
    /// Returns true if \c n is hidden.
deba@415
   768
    ///
deba@415
   769
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@415
   770
deba@415
   771
    /// \brief Returns true if \c a is hidden.
deba@415
   772
    ///
deba@415
   773
    /// Returns true if \c a is hidden.
deba@415
   774
    ///
deba@415
   775
    bool hidden(const Arc& a) const { return Parent::hidden(a); }
deba@415
   776
deba@414
   777
  };
deba@414
   778
deba@416
   779
  /// \brief Just gives back a subdigraph
deba@414
   780
  ///
deba@416
   781
  /// Just gives back a subdigraph
deba@414
   782
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
   783
  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
deba@416
   784
  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
deba@416
   785
    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
deba@414
   786
      (digraph, nfm, afm);
deba@414
   787
  }
deba@414
   788
deba@414
   789
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
   790
  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
deba@416
   791
  subDigraph(const Digraph& digraph,
deba@416
   792
             const NodeFilterMap& nfm, ArcFilterMap& afm) {
deba@416
   793
    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
deba@414
   794
      (digraph, nfm, afm);
deba@414
   795
  }
deba@414
   796
deba@414
   797
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
   798
  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
deba@416
   799
  subDigraph(const Digraph& digraph,
deba@416
   800
             NodeFilterMap& nfm, const ArcFilterMap& afm) {
deba@416
   801
    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
deba@414
   802
      (digraph, nfm, afm);
deba@414
   803
  }
deba@414
   804
deba@414
   805
  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
   806
  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
deba@416
   807
  subDigraph(const Digraph& digraph,
deba@416
   808
             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
deba@416
   809
    return SubDigraph<const Digraph, const NodeFilterMap,
deba@414
   810
      const ArcFilterMap>(digraph, nfm, afm);
deba@414
   811
  }
deba@414
   812
deba@414
   813
deba@416
   814
  template <typename _Graph, typename NodeFilterMap,
deba@416
   815
            typename EdgeFilterMap, bool _checked = true>
deba@416
   816
  class SubGraphBase : public GraphAdaptorBase<_Graph> {
deba@416
   817
  public:
deba@416
   818
    typedef _Graph Graph;
deba@416
   819
    typedef SubGraphBase Adaptor;
deba@416
   820
    typedef GraphAdaptorBase<_Graph> Parent;
deba@416
   821
  protected:
deba@416
   822
deba@416
   823
    NodeFilterMap* _node_filter_map;
deba@416
   824
    EdgeFilterMap* _edge_filter_map;
deba@416
   825
deba@416
   826
    SubGraphBase()
deba@416
   827
      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
deba@416
   828
deba@416
   829
    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416
   830
      _node_filter_map=&node_filter_map;
deba@416
   831
    }
deba@416
   832
    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416
   833
      _edge_filter_map=&edge_filter_map;
deba@416
   834
    }
deba@416
   835
deba@416
   836
  public:
deba@416
   837
deba@416
   838
    typedef typename Parent::Node Node;
deba@416
   839
    typedef typename Parent::Arc Arc;
deba@416
   840
    typedef typename Parent::Edge Edge;
deba@416
   841
deba@416
   842
    void first(Node& i) const {
deba@416
   843
      Parent::first(i);
deba@416
   844
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
   845
    }
deba@416
   846
deba@416
   847
    void first(Arc& i) const {
deba@416
   848
      Parent::first(i);
deba@416
   849
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   850
                            || !(*_node_filter_map)[Parent::source(i)]
deba@416
   851
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   852
        Parent::next(i);
deba@416
   853
    }
deba@416
   854
deba@416
   855
    void first(Edge& i) const {
deba@416
   856
      Parent::first(i);
deba@416
   857
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   858
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   859
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   860
        Parent::next(i);
deba@416
   861
    }
deba@416
   862
deba@416
   863
    void firstIn(Arc& i, const Node& n) const {
deba@416
   864
      Parent::firstIn(i, n);
deba@416
   865
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   866
                            || !(*_node_filter_map)[Parent::source(i)]))
deba@416
   867
        Parent::nextIn(i);
deba@416
   868
    }
deba@416
   869
deba@416
   870
    void firstOut(Arc& i, const Node& n) const {
deba@416
   871
      Parent::firstOut(i, n);
deba@416
   872
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   873
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   874
        Parent::nextOut(i);
deba@416
   875
    }
deba@416
   876
deba@416
   877
    void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416
   878
      Parent::firstInc(i, d, n);
deba@416
   879
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   880
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   881
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   882
        Parent::nextInc(i, d);
deba@416
   883
    }
deba@416
   884
deba@416
   885
    void next(Node& i) const {
deba@416
   886
      Parent::next(i);
deba@416
   887
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
   888
    }
deba@416
   889
deba@416
   890
    void next(Arc& i) const {
deba@416
   891
      Parent::next(i);
deba@416
   892
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   893
                            || !(*_node_filter_map)[Parent::source(i)]
deba@416
   894
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   895
        Parent::next(i);
deba@416
   896
    }
deba@416
   897
deba@416
   898
    void next(Edge& i) const {
deba@416
   899
      Parent::next(i);
deba@416
   900
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   901
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   902
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   903
        Parent::next(i);
deba@416
   904
    }
deba@416
   905
deba@416
   906
    void nextIn(Arc& i) const {
deba@416
   907
      Parent::nextIn(i);
deba@416
   908
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   909
                            || !(*_node_filter_map)[Parent::source(i)]))
deba@416
   910
        Parent::nextIn(i);
deba@416
   911
    }
deba@416
   912
deba@416
   913
    void nextOut(Arc& i) const {
deba@416
   914
      Parent::nextOut(i);
deba@416
   915
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   916
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   917
        Parent::nextOut(i);
deba@416
   918
    }
deba@416
   919
deba@416
   920
    void nextInc(Edge& i, bool& d) const {
deba@416
   921
      Parent::nextInc(i, d);
deba@416
   922
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   923
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   924
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   925
        Parent::nextInc(i, d);
deba@416
   926
    }
deba@416
   927
deba@416
   928
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416
   929
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416
   930
deba@416
   931
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416
   932
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416
   933
deba@416
   934
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416
   935
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416
   936
deba@416
   937
    typedef False NodeNumTag;
deba@416
   938
    typedef False EdgeNumTag;
deba@416
   939
deba@416
   940
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
   941
    Arc findArc(const Node& u, const Node& v,
deba@416
   942
                const Arc& prev = INVALID) {
deba@416
   943
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@416
   944
        return INVALID;
deba@416
   945
      }
deba@416
   946
      Arc arc = Parent::findArc(u, v, prev);
deba@416
   947
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416
   948
        arc = Parent::findArc(u, v, arc);
deba@416
   949
      }
deba@416
   950
      return arc;
deba@416
   951
    }
deba@416
   952
    Edge findEdge(const Node& u, const Node& v,
deba@416
   953
                  const Edge& prev = INVALID) {
deba@416
   954
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@416
   955
        return INVALID;
deba@416
   956
      }
deba@416
   957
      Edge edge = Parent::findEdge(u, v, prev);
deba@416
   958
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416
   959
        edge = Parent::findEdge(u, v, edge);
deba@416
   960
      }
deba@416
   961
      return edge;
deba@416
   962
    }
deba@416
   963
deba@416
   964
    template <typename _Value>
deba@416
   965
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
   966
      typename Parent::template NodeMap<_Value> > {
deba@416
   967
    public:
deba@416
   968
      typedef _Value Value;
deba@416
   969
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
   970
                             template NodeMap<Value> > MapParent;
deba@416
   971
deba@416
   972
      NodeMap(const Adaptor& adaptor)
deba@416
   973
        : MapParent(adaptor) {}
deba@416
   974
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
   975
        : MapParent(adaptor, value) {}
deba@416
   976
deba@416
   977
    private:
deba@416
   978
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
   979
        return operator=<NodeMap>(cmap);
deba@416
   980
      }
deba@416
   981
deba@416
   982
      template <typename CMap>
deba@416
   983
      NodeMap& operator=(const CMap& cmap) {
deba@416
   984
        MapParent::operator=(cmap);
deba@416
   985
        return *this;
deba@416
   986
      }
deba@416
   987
    };
deba@416
   988
deba@416
   989
    template <typename _Value>
deba@416
   990
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
   991
      typename Parent::template ArcMap<_Value> > {
deba@416
   992
    public:
deba@416
   993
      typedef _Value Value;
deba@416
   994
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
   995
                             template ArcMap<Value> > MapParent;
deba@416
   996
deba@416
   997
      ArcMap(const Adaptor& adaptor)
deba@416
   998
        : MapParent(adaptor) {}
deba@416
   999
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  1000
        : MapParent(adaptor, value) {}
deba@416
  1001
deba@416
  1002
    private:
deba@416
  1003
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  1004
        return operator=<ArcMap>(cmap);
deba@416
  1005
      }
deba@416
  1006
deba@416
  1007
      template <typename CMap>
deba@416
  1008
      ArcMap& operator=(const CMap& cmap) {
deba@416
  1009
        MapParent::operator=(cmap);
deba@416
  1010
        return *this;
deba@416
  1011
      }
deba@416
  1012
    };
deba@416
  1013
deba@416
  1014
    template <typename _Value>
deba@416
  1015
    class EdgeMap : public SubMapExtender<Adaptor,
deba@416
  1016
      typename Parent::template EdgeMap<_Value> > {
deba@416
  1017
    public:
deba@416
  1018
      typedef _Value Value;
deba@416
  1019
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1020
                             template EdgeMap<Value> > MapParent;
deba@416
  1021
deba@416
  1022
      EdgeMap(const Adaptor& adaptor)
deba@416
  1023
        : MapParent(adaptor) {}
deba@416
  1024
deba@416
  1025
      EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416
  1026
        : MapParent(adaptor, value) {}
deba@416
  1027
deba@416
  1028
    private:
deba@416
  1029
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@416
  1030
        return operator=<EdgeMap>(cmap);
deba@416
  1031
      }
deba@416
  1032
deba@416
  1033
      template <typename CMap>
deba@416
  1034
      EdgeMap& operator=(const CMap& cmap) {
deba@416
  1035
        MapParent::operator=(cmap);
deba@416
  1036
        return *this;
deba@416
  1037
      }
deba@416
  1038
    };
deba@416
  1039
deba@416
  1040
  };
deba@416
  1041
deba@416
  1042
  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@416
  1043
  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@416
  1044
    : public GraphAdaptorBase<_Graph> {
deba@416
  1045
  public:
deba@416
  1046
    typedef _Graph Graph;
deba@416
  1047
    typedef SubGraphBase Adaptor;
deba@416
  1048
    typedef GraphAdaptorBase<_Graph> Parent;
deba@416
  1049
  protected:
deba@416
  1050
    NodeFilterMap* _node_filter_map;
deba@416
  1051
    EdgeFilterMap* _edge_filter_map;
deba@416
  1052
    SubGraphBase() : Parent(),
deba@416
  1053
                     _node_filter_map(0), _edge_filter_map(0) { }
deba@416
  1054
deba@416
  1055
    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416
  1056
      _node_filter_map=&node_filter_map;
deba@416
  1057
    }
deba@416
  1058
    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416
  1059
      _edge_filter_map=&edge_filter_map;
deba@416
  1060
    }
deba@416
  1061
deba@416
  1062
  public:
deba@416
  1063
deba@416
  1064
    typedef typename Parent::Node Node;
deba@416
  1065
    typedef typename Parent::Arc Arc;
deba@416
  1066
    typedef typename Parent::Edge Edge;
deba@416
  1067
deba@416
  1068
    void first(Node& i) const {
deba@416
  1069
      Parent::first(i);
deba@416
  1070
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
  1071
    }
deba@416
  1072
deba@416
  1073
    void first(Arc& i) const {
deba@416
  1074
      Parent::first(i);
deba@416
  1075
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1076
    }
deba@416
  1077
deba@416
  1078
    void first(Edge& i) const {
deba@416
  1079
      Parent::first(i);
deba@416
  1080
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1081
    }
deba@416
  1082
deba@416
  1083
    void firstIn(Arc& i, const Node& n) const {
deba@416
  1084
      Parent::firstIn(i, n);
deba@416
  1085
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416
  1086
    }
deba@416
  1087
deba@416
  1088
    void firstOut(Arc& i, const Node& n) const {
deba@416
  1089
      Parent::firstOut(i, n);
deba@416
  1090
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416
  1091
    }
deba@416
  1092
deba@416
  1093
    void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416
  1094
      Parent::firstInc(i, d, n);
deba@416
  1095
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416
  1096
    }
deba@416
  1097
deba@416
  1098
    void next(Node& i) const {
deba@416
  1099
      Parent::next(i);
deba@416
  1100
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
  1101
    }
deba@416
  1102
    void next(Arc& i) const {
deba@416
  1103
      Parent::next(i);
deba@416
  1104
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1105
    }
deba@416
  1106
    void next(Edge& i) const {
deba@416
  1107
      Parent::next(i);
deba@416
  1108
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1109
    }
deba@416
  1110
    void nextIn(Arc& i) const {
deba@416
  1111
      Parent::nextIn(i);
deba@416
  1112
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416
  1113
    }
deba@416
  1114
deba@416
  1115
    void nextOut(Arc& i) const {
deba@416
  1116
      Parent::nextOut(i);
deba@416
  1117
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416
  1118
    }
deba@416
  1119
    void nextInc(Edge& i, bool& d) const {
deba@416
  1120
      Parent::nextInc(i, d);
deba@416
  1121
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416
  1122
    }
deba@416
  1123
deba@416
  1124
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416
  1125
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416
  1126
deba@416
  1127
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416
  1128
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416
  1129
deba@416
  1130
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416
  1131
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416
  1132
deba@416
  1133
    typedef False NodeNumTag;
deba@416
  1134
    typedef False EdgeNumTag;
deba@416
  1135
deba@416
  1136
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
  1137
    Arc findArc(const Node& u, const Node& v,
deba@416
  1138
                const Arc& prev = INVALID) {
deba@416
  1139
      Arc arc = Parent::findArc(u, v, prev);
deba@416
  1140
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416
  1141
        arc = Parent::findArc(u, v, arc);
deba@416
  1142
      }
deba@416
  1143
      return arc;
deba@416
  1144
    }
deba@416
  1145
    Edge findEdge(const Node& u, const Node& v,
deba@416
  1146
                  const Edge& prev = INVALID) {
deba@416
  1147
      Edge edge = Parent::findEdge(u, v, prev);
deba@416
  1148
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416
  1149
        edge = Parent::findEdge(u, v, edge);
deba@416
  1150
      }
deba@416
  1151
      return edge;
deba@416
  1152
    }
deba@416
  1153
deba@416
  1154
    template <typename _Value>
deba@416
  1155
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
  1156
      typename Parent::template NodeMap<_Value> > {
deba@416
  1157
    public:
deba@416
  1158
      typedef _Value Value;
deba@416
  1159
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1160
                             template NodeMap<Value> > MapParent;
deba@416
  1161
deba@416
  1162
      NodeMap(const Adaptor& adaptor)
deba@416
  1163
        : MapParent(adaptor) {}
deba@416
  1164
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
  1165
        : MapParent(adaptor, value) {}
deba@416
  1166
deba@416
  1167
    private:
deba@416
  1168
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
  1169
        return operator=<NodeMap>(cmap);
deba@416
  1170
      }
deba@416
  1171
deba@416
  1172
      template <typename CMap>
deba@416
  1173
      NodeMap& operator=(const CMap& cmap) {
deba@416
  1174
        MapParent::operator=(cmap);
deba@416
  1175
        return *this;
deba@416
  1176
      }
deba@416
  1177
    };
deba@416
  1178
deba@416
  1179
    template <typename _Value>
deba@416
  1180
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
  1181
      typename Parent::template ArcMap<_Value> > {
deba@416
  1182
    public:
deba@416
  1183
      typedef _Value Value;
deba@416
  1184
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1185
                             template ArcMap<Value> > MapParent;
deba@416
  1186
deba@416
  1187
      ArcMap(const Adaptor& adaptor)
deba@416
  1188
        : MapParent(adaptor) {}
deba@416
  1189
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  1190
        : MapParent(adaptor, value) {}
deba@416
  1191
deba@416
  1192
    private:
deba@416
  1193
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  1194
        return operator=<ArcMap>(cmap);
deba@416
  1195
      }
deba@416
  1196
deba@416
  1197
      template <typename CMap>
deba@416
  1198
      ArcMap& operator=(const CMap& cmap) {
deba@416
  1199
        MapParent::operator=(cmap);
deba@416
  1200
        return *this;
deba@416
  1201
      }
deba@416
  1202
    };
deba@416
  1203
deba@416
  1204
    template <typename _Value>
deba@416
  1205
    class EdgeMap : public SubMapExtender<Adaptor,
deba@416
  1206
      typename Parent::template EdgeMap<_Value> > {
deba@416
  1207
    public:
deba@416
  1208
      typedef _Value Value;
deba@416
  1209
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1210
                             template EdgeMap<Value> > MapParent;
deba@416
  1211
deba@416
  1212
      EdgeMap(const Adaptor& adaptor)
deba@416
  1213
        : MapParent(adaptor) {}
deba@416
  1214
deba@416
  1215
      EdgeMap(const Adaptor& adaptor, const _Value& value)
deba@416
  1216
        : MapParent(adaptor, value) {}
deba@416
  1217
deba@416
  1218
    private:
deba@416
  1219
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@416
  1220
        return operator=<EdgeMap>(cmap);
deba@416
  1221
      }
deba@416
  1222
deba@416
  1223
      template <typename CMap>
deba@416
  1224
      EdgeMap& operator=(const CMap& cmap) {
deba@416
  1225
        MapParent::operator=(cmap);
deba@416
  1226
        return *this;
deba@416
  1227
      }
deba@416
  1228
    };
deba@416
  1229
deba@416
  1230
  };
deba@416
  1231
deba@416
  1232
  /// \ingroup graph_adaptors
deba@414
  1233
  ///
deba@416
  1234
  /// \brief A graph adaptor for hiding nodes and edges in an
deba@416
  1235
  /// undirected graph.
deba@414
  1236
  ///
deba@416
  1237
  /// SubGraph hides nodes and edges in a graph. A bool node map and a
deba@416
  1238
  /// bool edge map must be specified, which define the filters for
deba@416
  1239
  /// nodes and edges. Just the nodes and edges with true value are
deba@416
  1240
  /// shown in the subgraph. The SubGraph is conform to the \ref
deba@416
  1241
  /// concepts::Graph "Graph concept". If the \c _checked parameter is
deba@416
  1242
  /// true, then the edges incident to filtered nodes are also
deba@416
  1243
  /// filtered out.
deba@416
  1244
  ///
deba@416
  1245
  /// \tparam _Graph It must be conform to the \ref
deba@416
  1246
  /// concepts::Graph "Graph concept". The type can be specified
deba@416
  1247
  /// to const.
deba@416
  1248
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416
  1249
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
deba@416
  1250
  /// \tparam _checked If the parameter is false then the edge filtering
deba@416
  1251
  /// is not checked with respect to node filter. Otherwise, each edge
deba@416
  1252
  /// is automatically filtered, which is incident to a filtered node.
deba@416
  1253
  ///
deba@416
  1254
  /// \see FilterNodes
deba@416
  1255
  /// \see FilterEdges
deba@416
  1256
  template<typename _Graph, typename NodeFilterMap,
deba@416
  1257
           typename EdgeFilterMap, bool _checked = true>
deba@416
  1258
  class SubGraph
deba@416
  1259
    : public GraphAdaptorExtender<
deba@416
  1260
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
deba@414
  1261
  public:
deba@416
  1262
    typedef _Graph Graph;
deba@416
  1263
    typedef GraphAdaptorExtender<
deba@416
  1264
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
deba@414
  1265
deba@415
  1266
    typedef typename Parent::Node Node;
deba@416
  1267
    typedef typename Parent::Edge Edge;
deba@415
  1268
deba@414
  1269
  protected:
deba@416
  1270
    SubGraph() { }
deba@414
  1271
  public:
deba@414
  1272
deba@415
  1273
    /// \brief Constructor
deba@415
  1274
    ///
deba@416
  1275
    /// Creates a subgraph for the given graph with given node and
deba@416
  1276
    /// edge map filters.
deba@416
  1277
    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
deba@416
  1278
             EdgeFilterMap& edge_filter_map) {
deba@416
  1279
      setGraph(_graph);
deba@416
  1280
      setNodeFilterMap(node_filter_map);
deba@416
  1281
      setEdgeFilterMap(edge_filter_map);
deba@414
  1282
    }
deba@414
  1283
deba@415
  1284
    /// \brief Hides the node of the graph
deba@415
  1285
    ///
deba@416
  1286
    /// This function hides \c n in the graph, i.e. the iteration
deba@416
  1287
    /// jumps over it. This is done by simply setting the value of \c n
deba@415
  1288
    /// to be false in the corresponding node-map.
deba@415
  1289
    void hide(const Node& n) const { Parent::hide(n); }
deba@415
  1290
deba@416
  1291
    /// \brief Hides the edge of the graph
deba@416
  1292
    ///
deba@416
  1293
    /// This function hides \c e in the graph, i.e. the iteration
deba@416
  1294
    /// jumps over it. This is done by simply setting the value of \c e
deba@416
  1295
    /// to be false in the corresponding edge-map.
deba@416
  1296
    void hide(const Edge& e) const { Parent::hide(e); }
deba@416
  1297
deba@415
  1298
    /// \brief Unhides the node of the graph
deba@415
  1299
    ///
deba@416
  1300
    /// The value of \c n is set to be true in the node-map which stores
deba@416
  1301
    /// hide information. If \c n was hidden previuosly, then it is shown
deba@415
  1302
    /// again
deba@415
  1303
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@415
  1304
deba@416
  1305
    /// \brief Unhides the edge of the graph
deba@416
  1306
    ///
deba@416
  1307
    /// The value of \c e is set to be true in the edge-map which stores
deba@416
  1308
    /// hide information. If \c e was hidden previuosly, then it is shown
deba@416
  1309
    /// again
deba@416
  1310
    void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416
  1311
deba@415
  1312
    /// \brief Returns true if \c n is hidden.
deba@415
  1313
    ///
deba@415
  1314
    /// Returns true if \c n is hidden.
deba@415
  1315
    ///
deba@415
  1316
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@415
  1317
deba@416
  1318
    /// \brief Returns true if \c e is hidden.
deba@416
  1319
    ///
deba@416
  1320
    /// Returns true if \c e is hidden.
deba@416
  1321
    ///
deba@416
  1322
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@414
  1323
  };
deba@414
  1324
deba@416
  1325
  /// \brief Just gives back a subgraph
deba@414
  1326
  ///
deba@416
  1327
  /// Just gives back a subgraph
deba@416
  1328
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1329
  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
deba@416
  1330
  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416
  1331
    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
deba@416
  1332
  }
deba@416
  1333
deba@416
  1334
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1335
  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416
  1336
  subGraph(const Graph& graph,
deba@416
  1337
           const NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416
  1338
    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416
  1339
      (graph, nfm, efm);
deba@416
  1340
  }
deba@416
  1341
deba@416
  1342
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1343
  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416
  1344
  subGraph(const Graph& graph,
deba@416
  1345
           NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416
  1346
    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416
  1347
      (graph, nfm, efm);
deba@416
  1348
  }
deba@416
  1349
deba@416
  1350
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1351
  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416
  1352
  subGraph(const Graph& graph,
deba@416
  1353
           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416
  1354
    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416
  1355
      (graph, nfm, efm);
deba@416
  1356
  }
deba@416
  1357
deba@416
  1358
  /// \ingroup graph_adaptors
deba@416
  1359
  ///
deba@416
  1360
  /// \brief An adaptor for hiding nodes from a digraph or a graph.
deba@416
  1361
  ///
deba@416
  1362
  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
deba@416
  1363
  /// node map must be specified, which defines the filters for
deba@416
  1364
  /// nodes. Just the unfiltered nodes and the arcs or edges incident
deba@416
  1365
  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
deba@416
  1366
  /// FilterNodes is conform to the \ref concepts::Digraph
deba@416
  1367
  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
deba@416
  1368
  /// on the \c _Digraph template parameter. If the \c _checked
deba@416
  1369
  /// parameter is true, then the arc or edges incident to filtered nodes
deba@416
  1370
  /// are also filtered out.
deba@416
  1371
  ///
deba@416
  1372
  /// \tparam _Digraph It must be conform to the \ref
deba@416
  1373
  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
deba@416
  1374
  /// "Graph concept". The type can be specified to be const.
deba@416
  1375
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416
  1376
  /// \tparam _checked If the parameter is false then the arc or edge
deba@416
  1377
  /// filtering is not checked with respect to node filter. In this
deba@416
  1378
  /// case just isolated nodes can be filtered out from the
deba@416
  1379
  /// graph.
deba@416
  1380
#ifdef DOXYGEN
deba@416
  1381
  template<typename _Digraph,
deba@416
  1382
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416
  1383
           bool _checked = true>
deba@416
  1384
#else
deba@416
  1385
  template<typename _Digraph,
deba@416
  1386
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416
  1387
           bool _checked = true,
deba@416
  1388
           typename Enable = void>
deba@416
  1389
#endif
deba@416
  1390
  class FilterNodes
deba@416
  1391
    : public SubDigraph<_Digraph, _NodeFilterMap,
deba@416
  1392
                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
deba@416
  1393
  public:
deba@416
  1394
deba@416
  1395
    typedef _Digraph Digraph;
deba@416
  1396
    typedef _NodeFilterMap NodeFilterMap;
deba@416
  1397
deba@416
  1398
    typedef SubDigraph<Digraph, NodeFilterMap,
deba@416
  1399
                       ConstMap<typename Digraph::Arc, bool>, _checked>
deba@416
  1400
    Parent;
deba@416
  1401
deba@416
  1402
    typedef typename Parent::Node Node;
deba@416
  1403
deba@416
  1404
  protected:
deba@416
  1405
    ConstMap<typename Digraph::Arc, bool> const_true_map;
deba@416
  1406
deba@416
  1407
    FilterNodes() : const_true_map(true) {
deba@416
  1408
      Parent::setArcFilterMap(const_true_map);
deba@416
  1409
    }
deba@416
  1410
deba@416
  1411
  public:
deba@416
  1412
deba@416
  1413
    /// \brief Constructor
deba@416
  1414
    ///
deba@416
  1415
    /// Creates an adaptor for the given digraph or graph with
deba@416
  1416
    /// given node filter map.
deba@416
  1417
    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
deba@416
  1418
      Parent(), const_true_map(true) {
deba@416
  1419
      Parent::setDigraph(_digraph);
deba@416
  1420
      Parent::setNodeFilterMap(node_filter);
deba@416
  1421
      Parent::setArcFilterMap(const_true_map);
deba@416
  1422
    }
deba@416
  1423
deba@416
  1424
    /// \brief Hides the node of the graph
deba@416
  1425
    ///
deba@416
  1426
    /// This function hides \c n in the digraph or graph, i.e. the iteration
deba@416
  1427
    /// jumps over it. This is done by simply setting the value of \c n
deba@416
  1428
    /// to be false in the corresponding node map.
deba@416
  1429
    void hide(const Node& n) const { Parent::hide(n); }
deba@416
  1430
deba@416
  1431
    /// \brief Unhides the node of the graph
deba@416
  1432
    ///
deba@416
  1433
    /// The value of \c n is set to be true in the node-map which stores
deba@416
  1434
    /// hide information. If \c n was hidden previuosly, then it is shown
deba@416
  1435
    /// again
deba@416
  1436
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@416
  1437
deba@416
  1438
    /// \brief Returns true if \c n is hidden.
deba@416
  1439
    ///
deba@416
  1440
    /// Returns true if \c n is hidden.
deba@416
  1441
    ///
deba@416
  1442
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416
  1443
deba@416
  1444
  };
deba@416
  1445
deba@416
  1446
  template<typename _Graph, typename _NodeFilterMap, bool _checked>
deba@416
  1447
  class FilterNodes<_Graph, _NodeFilterMap, _checked,
deba@416
  1448
                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
deba@416
  1449
    : public SubGraph<_Graph, _NodeFilterMap,
deba@416
  1450
                      ConstMap<typename _Graph::Edge, bool>, _checked> {
deba@416
  1451
  public:
deba@416
  1452
    typedef _Graph Graph;
deba@416
  1453
    typedef _NodeFilterMap NodeFilterMap;
deba@416
  1454
    typedef SubGraph<Graph, NodeFilterMap,
deba@416
  1455
                     ConstMap<typename Graph::Edge, bool> > Parent;
deba@416
  1456
deba@416
  1457
    typedef typename Parent::Node Node;
deba@416
  1458
  protected:
deba@416
  1459
    ConstMap<typename Graph::Edge, bool> const_true_map;
deba@416
  1460
deba@416
  1461
    FilterNodes() : const_true_map(true) {
deba@416
  1462
      Parent::setEdgeFilterMap(const_true_map);
deba@416
  1463
    }
deba@416
  1464
deba@416
  1465
  public:
deba@416
  1466
deba@416
  1467
    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
deba@416
  1468
      Parent(), const_true_map(true) {
deba@416
  1469
      Parent::setGraph(_graph);
deba@416
  1470
      Parent::setNodeFilterMap(node_filter_map);
deba@416
  1471
      Parent::setEdgeFilterMap(const_true_map);
deba@416
  1472
    }
deba@416
  1473
deba@416
  1474
    void hide(const Node& n) const { Parent::hide(n); }
deba@416
  1475
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@416
  1476
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416
  1477
deba@416
  1478
  };
deba@416
  1479
deba@416
  1480
deba@416
  1481
  /// \brief Just gives back a FilterNodes adaptor
deba@416
  1482
  ///
deba@416
  1483
  /// Just gives back a FilterNodes adaptor
deba@414
  1484
  template<typename Digraph, typename NodeFilterMap>
deba@416
  1485
  FilterNodes<const Digraph, NodeFilterMap>
deba@416
  1486
  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
deba@416
  1487
    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
deba@414
  1488
  }
deba@414
  1489
deba@414
  1490
  template<typename Digraph, typename NodeFilterMap>
deba@416
  1491
  FilterNodes<const Digraph, const NodeFilterMap>
deba@416
  1492
  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
deba@416
  1493
    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
deba@414
  1494
  }
deba@414
  1495
deba@416
  1496
  /// \ingroup graph_adaptors
deba@414
  1497
  ///
deba@416
  1498
  /// \brief An adaptor for hiding arcs from a digraph.
deba@414
  1499
  ///
deba@416
  1500
  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
deba@416
  1501
  /// be specified, which defines the filters for arcs. Just the
deba@416
  1502
  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
deba@416
  1503
  /// conform to the \ref concepts::Digraph "Digraph concept".
deba@414
  1504
  ///
deba@416
  1505
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416
  1506
  /// "Digraph concept". The type can be specified to be const.
deba@416
  1507
  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
deba@416
  1508
  /// graph.
deba@414
  1509
  template<typename _Digraph, typename _ArcFilterMap>
deba@416
  1510
  class FilterArcs :
deba@416
  1511
    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
deba@416
  1512
                      _ArcFilterMap, false> {
deba@414
  1513
  public:
deba@414
  1514
    typedef _Digraph Digraph;
deba@414
  1515
    typedef _ArcFilterMap ArcFilterMap;
deba@414
  1516
deba@416
  1517
    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
deba@416
  1518
                       ArcFilterMap, false> Parent;
deba@415
  1519
deba@415
  1520
    typedef typename Parent::Arc Arc;
deba@415
  1521
deba@414
  1522
  protected:
deba@414
  1523
    ConstMap<typename Digraph::Node, bool> const_true_map;
deba@414
  1524
deba@416
  1525
    FilterArcs() : const_true_map(true) {
deba@414
  1526
      Parent::setNodeFilterMap(const_true_map);
deba@414
  1527
    }
deba@414
  1528
deba@414
  1529
  public:
deba@414
  1530
deba@415
  1531
    /// \brief Constructor
deba@415
  1532
    ///
deba@416
  1533
    /// Creates a FilterArcs adaptor for the given graph with
deba@415
  1534
    /// given arc map filter.
deba@416
  1535
    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
deba@416
  1536
      : Parent(), const_true_map(true) {
deba@414
  1537
      Parent::setDigraph(digraph);
deba@414
  1538
      Parent::setNodeFilterMap(const_true_map);
deba@414
  1539
      Parent::setArcFilterMap(arc_filter);
deba@414
  1540
    }
deba@414
  1541
deba@415
  1542
    /// \brief Hides the arc of the graph
deba@415
  1543
    ///
deba@416
  1544
    /// This function hides \c a in the graph, i.e. the iteration
deba@415
  1545
    /// jumps over it. This is done by simply setting the value of \c a
deba@416
  1546
    /// to be false in the corresponding arc map.
deba@415
  1547
    void hide(const Arc& a) const { Parent::hide(a); }
deba@415
  1548
deba@415
  1549
    /// \brief Unhides the arc of the graph
deba@415
  1550
    ///
deba@416
  1551
    /// The value of \c a is set to be true in the arc-map which stores
deba@416
  1552
    /// hide information. If \c a was hidden previuosly, then it is shown
deba@415
  1553
    /// again
deba@415
  1554
    void unHide(const Arc& a) const { Parent::unHide(a); }
deba@415
  1555
deba@415
  1556
    /// \brief Returns true if \c a is hidden.
deba@415
  1557
    ///
deba@415
  1558
    /// Returns true if \c a is hidden.
deba@415
  1559
    ///
deba@415
  1560
    bool hidden(const Arc& a) const { return Parent::hidden(a); }
deba@415
  1561
deba@414
  1562
  };
deba@414
  1563
deba@416
  1564
  /// \brief Just gives back an FilterArcs adaptor
deba@414
  1565
  ///
deba@416
  1566
  /// Just gives back an FilterArcs adaptor
deba@414
  1567
  template<typename Digraph, typename ArcFilterMap>
deba@416
  1568
  FilterArcs<const Digraph, ArcFilterMap>
deba@416
  1569
  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
deba@416
  1570
    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
deba@414
  1571
  }
deba@414
  1572
deba@414
  1573
  template<typename Digraph, typename ArcFilterMap>
deba@416
  1574
  FilterArcs<const Digraph, const ArcFilterMap>
deba@416
  1575
  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
deba@416
  1576
    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
deba@414
  1577
  }
deba@414
  1578
deba@416
  1579
  /// \ingroup graph_adaptors
deba@416
  1580
  ///
deba@416
  1581
  /// \brief An adaptor for hiding edges from a graph.
deba@416
  1582
  ///
deba@416
  1583
  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
deba@416
  1584
  /// be specified, which defines the filters for edges. Just the
deba@416
  1585
  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
deba@416
  1586
  /// conform to the \ref concepts::Graph "Graph concept".
deba@416
  1587
  ///
deba@416
  1588
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416
  1589
  /// "Graph concept". The type can be specified to be const.
deba@416
  1590
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
deba@416
  1591
  /// graph.
deba@416
  1592
  template<typename _Graph, typename _EdgeFilterMap>
deba@416
  1593
  class FilterEdges :
deba@416
  1594
    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
deba@416
  1595
                    _EdgeFilterMap, false> {
deba@416
  1596
  public:
deba@416
  1597
    typedef _Graph Graph;
deba@416
  1598
    typedef _EdgeFilterMap EdgeFilterMap;
deba@416
  1599
    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
deba@416
  1600
                     EdgeFilterMap, false> Parent;
deba@416
  1601
    typedef typename Parent::Edge Edge;
deba@416
  1602
  protected:
deba@416
  1603
    ConstMap<typename Graph::Node, bool> const_true_map;
deba@416
  1604
deba@416
  1605
    FilterEdges() : const_true_map(true) {
deba@416
  1606
      Parent::setNodeFilterMap(const_true_map);
deba@416
  1607
    }
deba@416
  1608
deba@416
  1609
  public:
deba@416
  1610
deba@416
  1611
    /// \brief Constructor
deba@416
  1612
    ///
deba@416
  1613
    /// Creates a FilterEdges adaptor for the given graph with
deba@416
  1614
    /// given edge map filters.
deba@416
  1615
    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
deba@416
  1616
      Parent(), const_true_map(true) {
deba@416
  1617
      Parent::setGraph(_graph);
deba@416
  1618
      Parent::setNodeFilterMap(const_true_map);
deba@416
  1619
      Parent::setEdgeFilterMap(edge_filter_map);
deba@416
  1620
    }
deba@416
  1621
deba@416
  1622
    /// \brief Hides the edge of the graph
deba@416
  1623
    ///
deba@416
  1624
    /// This function hides \c e in the graph, i.e. the iteration
deba@416
  1625
    /// jumps over it. This is done by simply setting the value of \c e
deba@416
  1626
    /// to be false in the corresponding edge-map.
deba@416
  1627
    void hide(const Edge& e) const { Parent::hide(e); }
deba@416
  1628
deba@416
  1629
    /// \brief Unhides the edge of the graph
deba@416
  1630
    ///
deba@416
  1631
    /// The value of \c e is set to be true in the edge-map which stores
deba@416
  1632
    /// hide information. If \c e was hidden previuosly, then it is shown
deba@416
  1633
    /// again
deba@416
  1634
    void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416
  1635
deba@416
  1636
    /// \brief Returns true if \c e is hidden.
deba@416
  1637
    ///
deba@416
  1638
    /// Returns true if \c e is hidden.
deba@416
  1639
    ///
deba@416
  1640
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@416
  1641
deba@416
  1642
  };
deba@416
  1643
deba@416
  1644
  /// \brief Just gives back a FilterEdges adaptor
deba@416
  1645
  ///
deba@416
  1646
  /// Just gives back a FilterEdges adaptor
deba@416
  1647
  template<typename Graph, typename EdgeFilterMap>
deba@416
  1648
  FilterEdges<const Graph, EdgeFilterMap>
deba@416
  1649
  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
deba@416
  1650
    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
deba@416
  1651
  }
deba@416
  1652
deba@416
  1653
  template<typename Graph, typename EdgeFilterMap>
deba@416
  1654
  FilterEdges<const Graph, const EdgeFilterMap>
deba@416
  1655
  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
deba@416
  1656
    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
deba@416
  1657
  }
deba@416
  1658
deba@414
  1659
  template <typename _Digraph>
deba@416
  1660
  class UndirectorBase {
deba@414
  1661
  public:
deba@414
  1662
    typedef _Digraph Digraph;
deba@416
  1663
    typedef UndirectorBase Adaptor;
deba@414
  1664
deba@414
  1665
    typedef True UndirectedTag;
deba@414
  1666
deba@414
  1667
    typedef typename Digraph::Arc Edge;
deba@414
  1668
    typedef typename Digraph::Node Node;
deba@414
  1669
deba@414
  1670
    class Arc : public Edge {
deba@416
  1671
      friend class UndirectorBase;
deba@414
  1672
    protected:
deba@414
  1673
      bool _forward;
deba@414
  1674
deba@414
  1675
      Arc(const Edge& edge, bool forward) :
deba@414
  1676
        Edge(edge), _forward(forward) {}
deba@414
  1677
deba@414
  1678
    public:
deba@414
  1679
      Arc() {}
deba@414
  1680
deba@414
  1681
      Arc(Invalid) : Edge(INVALID), _forward(true) {}
deba@414
  1682
deba@414
  1683
      bool operator==(const Arc &other) const {
deba@416
  1684
        return _forward == other._forward &&
deba@416
  1685
          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
deba@414
  1686
      }
deba@414
  1687
      bool operator!=(const Arc &other) const {
deba@416
  1688
        return _forward != other._forward ||
deba@416
  1689
          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
deba@414
  1690
      }
deba@414
  1691
      bool operator<(const Arc &other) const {
deba@416
  1692
        return _forward < other._forward ||
deba@416
  1693
          (_forward == other._forward &&
deba@416
  1694
           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
deba@414
  1695
      }
deba@414
  1696
    };
deba@414
  1697
deba@414
  1698
deba@414
  1699
deba@414
  1700
    void first(Node& n) const {
deba@414
  1701
      _digraph->first(n);
deba@414
  1702
    }
deba@414
  1703
deba@414
  1704
    void next(Node& n) const {
deba@414
  1705
      _digraph->next(n);
deba@414
  1706
    }
deba@414
  1707
deba@414
  1708
    void first(Arc& a) const {
deba@414
  1709
      _digraph->first(a);
deba@414
  1710
      a._forward = true;
deba@414
  1711
    }
deba@414
  1712
deba@414
  1713
    void next(Arc& a) const {
deba@414
  1714
      if (a._forward) {
deba@416
  1715
        a._forward = false;
deba@414
  1716
      } else {
deba@416
  1717
        _digraph->next(a);
deba@416
  1718
        a._forward = true;
deba@414
  1719
      }
deba@414
  1720
    }
deba@414
  1721
deba@414
  1722
    void first(Edge& e) const {
deba@414
  1723
      _digraph->first(e);
deba@414
  1724
    }
deba@414
  1725
deba@414
  1726
    void next(Edge& e) const {
deba@414
  1727
      _digraph->next(e);
deba@414
  1728
    }
deba@414
  1729
deba@414
  1730
    void firstOut(Arc& a, const Node& n) const {
deba@414
  1731
      _digraph->firstIn(a, n);
deba@414
  1732
      if( static_cast<const Edge&>(a) != INVALID ) {
deba@416
  1733
        a._forward = false;
deba@414
  1734
      } else {
deba@416
  1735
        _digraph->firstOut(a, n);
deba@416
  1736
        a._forward = true;
deba@414
  1737
      }
deba@414
  1738
    }
deba@414
  1739
    void nextOut(Arc &a) const {
deba@414
  1740
      if (!a._forward) {
deba@416
  1741
        Node n = _digraph->target(a);
deba@416
  1742
        _digraph->nextIn(a);
deba@416
  1743
        if (static_cast<const Edge&>(a) == INVALID ) {
deba@416
  1744
          _digraph->firstOut(a, n);
deba@416
  1745
          a._forward = true;
deba@416
  1746
        }
deba@414
  1747
      }
deba@414
  1748
      else {
deba@416
  1749
        _digraph->nextOut(a);
deba@414
  1750
      }
deba@414
  1751
    }
deba@414
  1752
deba@414
  1753
    void firstIn(Arc &a, const Node &n) const {
deba@414
  1754
      _digraph->firstOut(a, n);
deba@414
  1755
      if (static_cast<const Edge&>(a) != INVALID ) {
deba@416
  1756
        a._forward = false;
deba@414
  1757
      } else {
deba@416
  1758
        _digraph->firstIn(a, n);
deba@416
  1759
        a._forward = true;
deba@414
  1760
      }
deba@414
  1761
    }
deba@414
  1762
    void nextIn(Arc &a) const {
deba@414
  1763
      if (!a._forward) {
deba@416
  1764
        Node n = _digraph->source(a);
deba@416
  1765
        _digraph->nextOut(a);
deba@416
  1766
        if( static_cast<const Edge&>(a) == INVALID ) {
deba@416
  1767
          _digraph->firstIn(a, n);
deba@416
  1768
          a._forward = true;
deba@416
  1769
        }
deba@414
  1770
      }
deba@414
  1771
      else {
deba@416
  1772
        _digraph->nextIn(a);
deba@414
  1773
      }
deba@414
  1774
    }
deba@414
  1775
deba@414
  1776
    void firstInc(Edge &e, bool &d, const Node &n) const {
deba@414
  1777
      d = true;
deba@414
  1778
      _digraph->firstOut(e, n);
deba@414
  1779
      if (e != INVALID) return;
deba@414
  1780
      d = false;
deba@414
  1781
      _digraph->firstIn(e, n);
deba@414
  1782
    }
deba@414
  1783
deba@414
  1784
    void nextInc(Edge &e, bool &d) const {
deba@414
  1785
      if (d) {
deba@416
  1786
        Node s = _digraph->source(e);
deba@416
  1787
        _digraph->nextOut(e);
deba@416
  1788
        if (e != INVALID) return;
deba@416
  1789
        d = false;
deba@416
  1790
        _digraph->firstIn(e, s);
deba@414
  1791
      } else {
deba@416
  1792
        _digraph->nextIn(e);
deba@414
  1793
      }
deba@414
  1794
    }
deba@414
  1795
deba@414
  1796
    Node u(const Edge& e) const {
deba@414
  1797
      return _digraph->source(e);
deba@414
  1798
    }
deba@414
  1799
deba@414
  1800
    Node v(const Edge& e) const {
deba@414
  1801
      return _digraph->target(e);
deba@414
  1802
    }
deba@414
  1803
deba@414
  1804
    Node source(const Arc &a) const {
deba@414
  1805
      return a._forward ? _digraph->source(a) : _digraph->target(a);
deba@414
  1806
    }
deba@414
  1807
deba@414
  1808
    Node target(const Arc &a) const {
deba@414
  1809
      return a._forward ? _digraph->target(a) : _digraph->source(a);
deba@414
  1810
    }
deba@414
  1811
deba@414
  1812
    static Arc direct(const Edge &e, bool d) {
deba@414
  1813
      return Arc(e, d);
deba@414
  1814
    }
deba@414
  1815
    Arc direct(const Edge &e, const Node& n) const {
deba@414
  1816
      return Arc(e, _digraph->source(e) == n);
deba@414
  1817
    }
deba@414
  1818
deba@414
  1819
    static bool direction(const Arc &a) { return a._forward; }
deba@414
  1820
deba@414
  1821
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414
  1822
    Arc arcFromId(int ix) const {
deba@414
  1823
      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
deba@414
  1824
    }
deba@414
  1825
    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414
  1826
deba@414
  1827
    int id(const Node &n) const { return _digraph->id(n); }
deba@414
  1828
    int id(const Arc &a) const {
deba@414
  1829
      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
deba@414
  1830
    }
deba@414
  1831
    int id(const Edge &e) const { return _digraph->id(e); }
deba@414
  1832
deba@414
  1833
    int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414
  1834
    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
deba@414
  1835
    int maxEdgeId() const { return _digraph->maxArcId(); }
deba@414
  1836
deba@414
  1837
    Node addNode() { return _digraph->addNode(); }
deba@416
  1838
    Edge addEdge(const Node& u, const Node& v) {
deba@416
  1839
      return _digraph->addArc(u, v);
deba@414
  1840
    }
deba@414
  1841
deba@414
  1842
    void erase(const Node& i) { _digraph->erase(i); }
deba@414
  1843
    void erase(const Edge& i) { _digraph->erase(i); }
deba@416
  1844
deba@414
  1845
    void clear() { _digraph->clear(); }
deba@414
  1846
deba@414
  1847
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
deba@414
  1848
    int nodeNum() const { return 2 * _digraph->arcNum(); }
deba@414
  1849
    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
deba@414
  1850
    int arcNum() const { return 2 * _digraph->arcNum(); }
deba@414
  1851
    int edgeNum() const { return _digraph->arcNum(); }
deba@414
  1852
deba@414
  1853
    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@414
  1854
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
deba@414
  1855
      if (p == INVALID) {
deba@416
  1856
        Edge arc = _digraph->findArc(s, t);
deba@416
  1857
        if (arc != INVALID) return direct(arc, true);
deba@416
  1858
        arc = _digraph->findArc(t, s);
deba@416
  1859
        if (arc != INVALID) return direct(arc, false);
deba@414
  1860
      } else if (direction(p)) {
deba@416
  1861
        Edge arc = _digraph->findArc(s, t, p);
deba@416
  1862
        if (arc != INVALID) return direct(arc, true);
deba@416
  1863
        arc = _digraph->findArc(t, s);
deba@416
  1864
        if (arc != INVALID) return direct(arc, false);
deba@414
  1865
      } else {
deba@416
  1866
        Edge arc = _digraph->findArc(t, s, p);
deba@416
  1867
        if (arc != INVALID) return direct(arc, false);
deba@414
  1868
      }
deba@414
  1869
      return INVALID;
deba@414
  1870
    }
deba@414
  1871
deba@414
  1872
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
deba@414
  1873
      if (s != t) {
deba@414
  1874
        if (p == INVALID) {
deba@414
  1875
          Edge arc = _digraph->findArc(s, t);
deba@414
  1876
          if (arc != INVALID) return arc;
deba@414
  1877
          arc = _digraph->findArc(t, s);
deba@414
  1878
          if (arc != INVALID) return arc;
deba@414
  1879
        } else if (_digraph->s(p) == s) {
deba@414
  1880
          Edge arc = _digraph->findArc(s, t, p);
deba@414
  1881
          if (arc != INVALID) return arc;
deba@414
  1882
          arc = _digraph->findArc(t, s);
deba@416
  1883
          if (arc != INVALID) return arc;
deba@414
  1884
        } else {
deba@414
  1885
          Edge arc = _digraph->findArc(t, s, p);
deba@416
  1886
          if (arc != INVALID) return arc;
deba@414
  1887
        }
deba@414
  1888
      } else {
deba@414
  1889
        return _digraph->findArc(s, t, p);
deba@414
  1890
      }
deba@414
  1891
      return INVALID;
deba@414
  1892
    }
deba@414
  1893
deba@414
  1894
  private:
deba@416
  1895
deba@414
  1896
    template <typename _Value>
deba@414
  1897
    class ArcMapBase {
deba@414
  1898
    private:
deba@416
  1899
deba@414
  1900
      typedef typename Digraph::template ArcMap<_Value> MapImpl;
deba@416
  1901
deba@414
  1902
    public:
deba@414
  1903
deba@414
  1904
      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@414
  1905
deba@414
  1906
      typedef _Value Value;
deba@414
  1907
      typedef Arc Key;
deba@416
  1908
deba@414
  1909
      ArcMapBase(const Adaptor& adaptor) :
deba@416
  1910
        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
deba@416
  1911
deba@416
  1912
      ArcMapBase(const Adaptor& adaptor, const Value& v)
deba@414
  1913
        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
deba@416
  1914
deba@416
  1915
      void set(const Arc& a, const Value& v) {
deba@416
  1916
        if (direction(a)) {
deba@416
  1917
          _forward.set(a, v);
deba@416
  1918
        } else {
deba@416
  1919
          _backward.set(a, v);
deba@414
  1920
        }
deba@414
  1921
      }
deba@414
  1922
deba@416
  1923
      typename MapTraits<MapImpl>::ConstReturnValue
deba@416
  1924
      operator[](const Arc& a) const {
deba@416
  1925
        if (direction(a)) {
deba@416
  1926
          return _forward[a];
deba@416
  1927
        } else {
deba@416
  1928
          return _backward[a];
deba@414
  1929
        }
deba@414
  1930
      }
deba@414
  1931
deba@416
  1932
      typename MapTraits<MapImpl>::ReturnValue
deba@416
  1933
      operator[](const Arc& a) {
deba@416
  1934
        if (direction(a)) {
deba@416
  1935
          return _forward[a];
deba@416
  1936
        } else {
deba@416
  1937
          return _backward[a];
deba@416
  1938
        }
deba@416
  1939
      }
deba@416
  1940
deba@414
  1941
    protected:
deba@414
  1942
deba@416
  1943
      MapImpl _forward, _backward;
deba@414
  1944
deba@414
  1945
    };
deba@414
  1946
deba@414
  1947
  public:
deba@414
  1948
deba@414
  1949
    template <typename _Value>
deba@414
  1950
    class NodeMap : public Digraph::template NodeMap<_Value> {
deba@414
  1951
    public:
deba@414
  1952
deba@414
  1953
      typedef _Value Value;
deba@414
  1954
      typedef typename Digraph::template NodeMap<Value> Parent;
deba@414
  1955
deba@416
  1956
      explicit NodeMap(const Adaptor& adaptor)
deba@416
  1957
        : Parent(*adaptor._digraph) {}
deba@414
  1958
deba@414
  1959
      NodeMap(const Adaptor& adaptor, const _Value& value)
deba@416
  1960
        : Parent(*adaptor._digraph, value) { }
deba@414
  1961
deba@414
  1962
    private:
deba@414
  1963
      NodeMap& operator=(const NodeMap& cmap) {
deba@414
  1964
        return operator=<NodeMap>(cmap);
deba@414
  1965
      }
deba@414
  1966
deba@414
  1967
      template <typename CMap>
deba@414
  1968
      NodeMap& operator=(const CMap& cmap) {
deba@414
  1969
        Parent::operator=(cmap);
deba@414
  1970
        return *this;
deba@414
  1971
      }
deba@416
  1972
deba@414
  1973
    };
deba@414
  1974
deba@414
  1975
    template <typename _Value>
deba@416
  1976
    class ArcMap
deba@416
  1977
      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
deba@414
  1978
    {
deba@414
  1979
    public:
deba@414
  1980
      typedef _Value Value;
deba@414
  1981
      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
deba@416
  1982
deba@416
  1983
      ArcMap(const Adaptor& adaptor)
deba@416
  1984
        : Parent(adaptor) {}
deba@416
  1985
deba@416
  1986
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  1987
        : Parent(adaptor, value) {}
deba@416
  1988
deba@414
  1989
    private:
deba@414
  1990
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  1991
        return operator=<ArcMap>(cmap);
deba@414
  1992
      }
deba@416
  1993
deba@414
  1994
      template <typename CMap>
deba@414
  1995
      ArcMap& operator=(const CMap& cmap) {
deba@414
  1996
        Parent::operator=(cmap);
deba@416
  1997
        return *this;
deba@414
  1998
      }
deba@414
  1999
    };
deba@416
  2000
deba@414
  2001
    template <typename _Value>
deba@414
  2002
    class EdgeMap : public Digraph::template ArcMap<_Value> {
deba@414
  2003
    public:
deba@416
  2004
deba@414
  2005
      typedef _Value Value;
deba@414
  2006
      typedef typename Digraph::template ArcMap<Value> Parent;
deba@416
  2007
deba@416
  2008
      explicit EdgeMap(const Adaptor& adaptor)
deba@416
  2009
        : Parent(*adaptor._digraph) {}
deba@414
  2010
deba@414
  2011
      EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416
  2012
        : Parent(*adaptor._digraph, value) {}
deba@414
  2013
deba@414
  2014
    private:
deba@414
  2015
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@414
  2016
        return operator=<EdgeMap>(cmap);
deba@414
  2017
      }
deba@414
  2018
deba@414
  2019
      template <typename CMap>
deba@414
  2020
      EdgeMap& operator=(const CMap& cmap) {
deba@414
  2021
        Parent::operator=(cmap);
deba@414
  2022
        return *this;
deba@414
  2023
      }
deba@414
  2024
deba@414
  2025
    };
deba@414
  2026
deba@414
  2027
    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
deba@416
  2028
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414
  2029
deba@414
  2030
  protected:
deba@414
  2031
deba@416
  2032
    UndirectorBase() : _digraph(0) {}
deba@414
  2033
deba@414
  2034
    Digraph* _digraph;
deba@414
  2035
deba@414
  2036
    void setDigraph(Digraph& digraph) {
deba@414
  2037
      _digraph = &digraph;
deba@414
  2038
    }
deba@416
  2039
deba@414
  2040
  };
deba@414
  2041
deba@416
  2042
  /// \ingroup graph_adaptors
deba@414
  2043
  ///
deba@416
  2044
  /// \brief Undirect the graph
deba@414
  2045
  ///
deba@414
  2046
  /// This adaptor makes an undirected graph from a directed
deba@416
  2047
  /// graph. All arcs of the underlying digraph will be showed in the
deba@416
  2048
  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
deba@416
  2049
  /// concepts::Graph "Graph concept".
deba@414
  2050
  ///
deba@416
  2051
  /// \tparam _Digraph It must be conform to the \ref
deba@416
  2052
  /// concepts::Digraph "Digraph concept". The type can be specified
deba@416
  2053
  /// to const.
deba@414
  2054
  template<typename _Digraph>
deba@416
  2055
  class Undirector
deba@416
  2056
    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
deba@414
  2057
  public:
deba@414
  2058
    typedef _Digraph Digraph;
deba@416
  2059
    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
deba@414
  2060
  protected:
deba@416
  2061
    Undirector() { }
deba@414
  2062
  public:
deba@414
  2063
deba@414
  2064
    /// \brief Constructor
deba@414
  2065
    ///
deba@416
  2066
    /// Creates a undirected graph from the given digraph
deba@416
  2067
    Undirector(_Digraph& digraph) {
deba@416
  2068
      setDigraph(digraph);
deba@414
  2069
    }
deba@414
  2070
deba@414
  2071
    /// \brief ArcMap combined from two original ArcMap
deba@414
  2072
    ///
deba@414
  2073
    /// This class adapts two original digraph ArcMap to
deba@416
  2074
    /// get an arc map on the undirected graph.
deba@414
  2075
    template <typename _ForwardMap, typename _BackwardMap>
deba@414
  2076
    class CombinedArcMap {
deba@414
  2077
    public:
deba@416
  2078
deba@414
  2079
      typedef _ForwardMap ForwardMap;
deba@414
  2080
      typedef _BackwardMap BackwardMap;
deba@414
  2081
deba@414
  2082
      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
deba@414
  2083
deba@414
  2084
      typedef typename ForwardMap::Value Value;
deba@414
  2085
      typedef typename Parent::Arc Key;
deba@414
  2086
deba@416
  2087
      /// \brief Constructor
deba@414
  2088
      ///
deba@416
  2089
      /// Constructor
deba@416
  2090
      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
deba@414
  2091
        : _forward(&forward), _backward(&backward) {}
deba@416
  2092
deba@414
  2093
deba@414
  2094
      /// \brief Sets the value associated with a key.
deba@414
  2095
      ///
deba@414
  2096
      /// Sets the value associated with a key.
deba@416
  2097
      void set(const Key& e, const Value& a) {
deba@416
  2098
        if (Parent::direction(e)) {
deba@416
  2099
          _forward->set(e, a);
deba@416
  2100
        } else {
deba@416
  2101
          _backward->set(e, a);
deba@416
  2102
        }
deba@414
  2103
      }
deba@414
  2104
deba@414
  2105
      /// \brief Returns the value associated with a key.
deba@414
  2106
      ///
deba@414
  2107
      /// Returns the value associated with a key.
deba@416
  2108
      typename MapTraits<ForwardMap>::ConstReturnValue
deba@416
  2109
      operator[](const Key& e) const {
deba@416
  2110
        if (Parent::direction(e)) {
deba@416
  2111
          return (*_forward)[e];
deba@416
  2112
        } else {
deba@416
  2113
          return (*_backward)[e];
deba@414
  2114
        }
deba@414
  2115
      }
deba@414
  2116
deba@414
  2117
      /// \brief Returns the value associated with a key.
deba@414
  2118
      ///
deba@414
  2119
      /// Returns the value associated with a key.
deba@416
  2120
      typename MapTraits<ForwardMap>::ReturnValue
deba@416
  2121
      operator[](const Key& e) {
deba@416
  2122
        if (Parent::direction(e)) {
deba@416
  2123
          return (*_forward)[e];
deba@416
  2124
        } else {
deba@416
  2125
          return (*_backward)[e];
deba@414
  2126
        }
deba@414
  2127
      }
deba@414
  2128
deba@416
  2129
    protected:
deba@416
  2130
deba@416
  2131
      ForwardMap* _forward;
deba@416
  2132
      BackwardMap* _backward;
deba@416
  2133
deba@416
  2134
    };
deba@416
  2135
deba@416
  2136
    /// \brief Just gives back a combined arc map
deba@416
  2137
    ///
deba@416
  2138
    /// Just gives back a combined arc map
deba@416
  2139
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2140
    static CombinedArcMap<ForwardMap, BackwardMap>
deba@416
  2141
    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
deba@416
  2142
      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
deba@416
  2143
    }
deba@416
  2144
deba@416
  2145
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2146
    static CombinedArcMap<const ForwardMap, BackwardMap>
deba@416
  2147
    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
deba@416
  2148
      return CombinedArcMap<const ForwardMap,
deba@416
  2149
        BackwardMap>(forward, backward);
deba@416
  2150
    }
deba@416
  2151
deba@416
  2152
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2153
    static CombinedArcMap<ForwardMap, const BackwardMap>
deba@416
  2154
    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
deba@416
  2155
      return CombinedArcMap<ForwardMap,
deba@416
  2156
        const BackwardMap>(forward, backward);
deba@416
  2157
    }
deba@416
  2158
deba@416
  2159
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2160
    static CombinedArcMap<const ForwardMap, const BackwardMap>
deba@416
  2161
    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
deba@416
  2162
      return CombinedArcMap<const ForwardMap,
deba@416
  2163
        const BackwardMap>(forward, backward);
deba@416
  2164
    }
deba@416
  2165
deba@416
  2166
  };
deba@416
  2167
deba@416
  2168
  /// \brief Just gives back an undirected view of the given digraph
deba@416
  2169
  ///
deba@416
  2170
  /// Just gives back an undirected view of the given digraph
deba@416
  2171
  template<typename Digraph>
deba@416
  2172
  Undirector<const Digraph>
deba@416
  2173
  undirector(const Digraph& digraph) {
deba@416
  2174
    return Undirector<const Digraph>(digraph);
deba@416
  2175
  }
deba@416
  2176
deba@416
  2177
  template <typename _Graph, typename _DirectionMap>
deba@416
  2178
  class OrienterBase {
deba@416
  2179
  public:
deba@416
  2180
deba@416
  2181
    typedef _Graph Graph;
deba@416
  2182
    typedef _DirectionMap DirectionMap;
deba@416
  2183
deba@416
  2184
    typedef typename Graph::Node Node;
deba@416
  2185
    typedef typename Graph::Edge Arc;
deba@416
  2186
deba@416
  2187
    void reverseArc(const Arc& arc) {
deba@416
  2188
      _direction->set(arc, !(*_direction)[arc]);
deba@416
  2189
    }
deba@416
  2190
deba@416
  2191
    void first(Node& i) const { _graph->first(i); }
deba@416
  2192
    void first(Arc& i) const { _graph->first(i); }
deba@416
  2193
    void firstIn(Arc& i, const Node& n) const {
deba@416
  2194
      bool d;
deba@416
  2195
      _graph->firstInc(i, d, n);
deba@416
  2196
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2197
    }
deba@416
  2198
    void firstOut(Arc& i, const Node& n ) const {
deba@416
  2199
      bool d;
deba@416
  2200
      _graph->firstInc(i, d, n);
deba@416
  2201
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2202
    }
deba@416
  2203
deba@416
  2204
    void next(Node& i) const { _graph->next(i); }
deba@416
  2205
    void next(Arc& i) const { _graph->next(i); }
deba@416
  2206
    void nextIn(Arc& i) const {
deba@416
  2207
      bool d = !(*_direction)[i];
deba@416
  2208
      _graph->nextInc(i, d);
deba@416
  2209
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2210
    }
deba@416
  2211
    void nextOut(Arc& i) const {
deba@416
  2212
      bool d = (*_direction)[i];
deba@416
  2213
      _graph->nextInc(i, d);
deba@416
  2214
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2215
    }
deba@416
  2216
deba@416
  2217
    Node source(const Arc& e) const {
deba@416
  2218
      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
deba@416
  2219
    }
deba@416
  2220
    Node target(const Arc& e) const {
deba@416
  2221
      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
deba@416
  2222
    }
deba@416
  2223
deba@416
  2224
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416
  2225
    int nodeNum() const { return _graph->nodeNum(); }
deba@416
  2226
deba@416
  2227
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@416
  2228
    int arcNum() const { return _graph->edgeNum(); }
deba@416
  2229
deba@416
  2230
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
  2231
    Arc findArc(const Node& u, const Node& v,
deba@416
  2232
                const Arc& prev = INVALID) {
deba@416
  2233
      Arc arc = prev;
deba@416
  2234
      bool d = arc == INVALID ? true : (*_direction)[arc];
deba@416
  2235
      if (d) {
deba@416
  2236
        arc = _graph->findEdge(u, v, arc);
deba@416
  2237
        while (arc != INVALID && !(*_direction)[arc]) {
deba@416
  2238
          _graph->findEdge(u, v, arc);
deba@416
  2239
        }
deba@416
  2240
        if (arc != INVALID) return arc;
deba@414
  2241
      }
deba@416
  2242
      _graph->findEdge(v, u, arc);
deba@416
  2243
      while (arc != INVALID && (*_direction)[arc]) {
deba@416
  2244
        _graph->findEdge(u, v, arc);
deba@414
  2245
      }
deba@416
  2246
      return arc;
deba@416
  2247
    }
deba@416
  2248
deba@416
  2249
    Node addNode() {
deba@416
  2250
      return Node(_graph->addNode());
deba@416
  2251
    }
deba@416
  2252
deba@416
  2253
    Arc addArc(const Node& u, const Node& v) {
deba@416
  2254
      Arc arc = _graph->addArc(u, v);
deba@416
  2255
      _direction->set(arc, _graph->source(arc) == u);
deba@416
  2256
      return arc;
deba@416
  2257
    }
deba@416
  2258
deba@416
  2259
    void erase(const Node& i) { _graph->erase(i); }
deba@416
  2260
    void erase(const Arc& i) { _graph->erase(i); }
deba@416
  2261
deba@416
  2262
    void clear() { _graph->clear(); }
deba@416
  2263
deba@416
  2264
    int id(const Node& v) const { return _graph->id(v); }
deba@416
  2265
    int id(const Arc& e) const { return _graph->id(e); }
deba@416
  2266
deba@416
  2267
    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@416
  2268
    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@416
  2269
deba@416
  2270
    int maxNodeId() const { return _graph->maxNodeId(); }
deba@416
  2271
    int maxArcId() const { return _graph->maxEdgeId(); }
deba@416
  2272
deba@416
  2273
    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@416
  2274
    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416
  2275
deba@416
  2276
    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@416
  2277
    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416
  2278
deba@416
  2279
    template <typename _Value>
deba@416
  2280
    class NodeMap : public _Graph::template NodeMap<_Value> {
deba@416
  2281
    public:
deba@416
  2282
deba@416
  2283
      typedef typename _Graph::template NodeMap<_Value> Parent;
deba@416
  2284
deba@416
  2285
      explicit NodeMap(const OrienterBase& adapter)
deba@416
  2286
        : Parent(*adapter._graph) {}
deba@416
  2287
deba@416
  2288
      NodeMap(const OrienterBase& adapter, const _Value& value)
deba@416
  2289
        : Parent(*adapter._graph, value) {}
deba@416
  2290
deba@416
  2291
    private:
deba@416
  2292
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
  2293
        return operator=<NodeMap>(cmap);
deba@416
  2294
      }
deba@416
  2295
deba@416
  2296
      template <typename CMap>
deba@416
  2297
      NodeMap& operator=(const CMap& cmap) {
deba@416
  2298
        Parent::operator=(cmap);
deba@416
  2299
        return *this;
deba@416
  2300
      }
deba@414
  2301
deba@414
  2302
    };
deba@414
  2303
deba@416
  2304
    template <typename _Value>
deba@416
  2305
    class ArcMap : public _Graph::template EdgeMap<_Value> {
deba@416
  2306
    public:
deba@416
  2307
deba@416
  2308
      typedef typename Graph::template EdgeMap<_Value> Parent;
deba@416
  2309
deba@416
  2310
      explicit ArcMap(const OrienterBase& adapter)
deba@416
  2311
        : Parent(*adapter._graph) { }
deba@416
  2312
deba@416
  2313
      ArcMap(const OrienterBase& adapter, const _Value& value)
deba@416
  2314
        : Parent(*adapter._graph, value) { }
deba@416
  2315
deba@416
  2316
    private:
deba@416
  2317
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  2318
        return operator=<ArcMap>(cmap);
deba@416
  2319
      }
deba@416
  2320
deba@416
  2321
      template <typename CMap>
deba@416
  2322
      ArcMap& operator=(const CMap& cmap) {
deba@416
  2323
        Parent::operator=(cmap);
deba@416
  2324
        return *this;
deba@416
  2325
      }
deba@416
  2326
    };
deba@416
  2327
deba@416
  2328
deba@416
  2329
deba@416
  2330
  protected:
deba@416
  2331
    Graph* _graph;
deba@416
  2332
    DirectionMap* _direction;
deba@416
  2333
deba@416
  2334
    void setDirectionMap(DirectionMap& direction) {
deba@416
  2335
      _direction = &direction;
deba@416
  2336
    }
deba@416
  2337
deba@416
  2338
    void setGraph(Graph& graph) {
deba@416
  2339
      _graph = &graph;
deba@416
  2340
    }
deba@416
  2341
deba@414
  2342
  };
deba@414
  2343
deba@416
  2344
  /// \ingroup graph_adaptors
deba@414
  2345
  ///
deba@416
  2346
  /// \brief Orients the edges of the graph to get a digraph
deba@416
  2347
  ///
deba@416
  2348
  /// This adaptor orients each edge in the undirected graph. The
deba@416
  2349
  /// direction of the arcs stored in an edge node map.  The arcs can
deba@416
  2350
  /// be easily reverted by the \c reverseArc() member function in the
deba@416
  2351
  /// adaptor. The Orienter adaptor is conform to the \ref
deba@416
  2352
  /// concepts::Digraph "Digraph concept".
deba@416
  2353
  ///
deba@416
  2354
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416
  2355
  /// "Graph concept". The type can be specified to be const.
deba@416
  2356
  /// \tparam _DirectionMap A bool valued edge map of the the adapted
deba@416
  2357
  /// graph.
deba@416
  2358
  ///
deba@416
  2359
  /// \sa orienter
deba@416
  2360
  template<typename _Graph,
deba@416
  2361
           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
deba@416
  2362
  class Orienter :
deba@416
  2363
    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
deba@416
  2364
  public:
deba@416
  2365
    typedef _Graph Graph;
deba@416
  2366
    typedef DigraphAdaptorExtender<
deba@416
  2367
      OrienterBase<_Graph, DirectionMap> > Parent;
deba@416
  2368
    typedef typename Parent::Arc Arc;
deba@416
  2369
  protected:
deba@416
  2370
    Orienter() { }
deba@416
  2371
  public:
deba@416
  2372
deba@416
  2373
    /// \brief Constructor of the adaptor
deba@416
  2374
    ///
deba@416
  2375
    /// Constructor of the adaptor
deba@416
  2376
    Orienter(Graph& graph, DirectionMap& direction) {
deba@416
  2377
      setGraph(graph);
deba@416
  2378
      setDirectionMap(direction);
deba@416
  2379
    }
deba@416
  2380
deba@416
  2381
    /// \brief Reverse arc
deba@416
  2382
    ///
deba@416
  2383
    /// It reverse the given arc. It simply negate the direction in the map.
deba@416
  2384
    void reverseArc(const Arc& a) {
deba@416
  2385
      Parent::reverseArc(a);
deba@416
  2386
    }
deba@416
  2387
  };
deba@416
  2388
deba@416
  2389
  /// \brief Just gives back a Orienter
deba@416
  2390
  ///
deba@416
  2391
  /// Just gives back a Orienter
deba@416
  2392
  template<typename Graph, typename DirectionMap>
deba@416
  2393
  Orienter<const Graph, DirectionMap>
deba@416
  2394
  orienter(const Graph& graph, DirectionMap& dm) {
deba@416
  2395
    return Orienter<const Graph, DirectionMap>(graph, dm);
deba@414
  2396
  }
deba@414
  2397
deba@416
  2398
  template<typename Graph, typename DirectionMap>
deba@416
  2399
  Orienter<const Graph, const DirectionMap>
deba@416
  2400
  orienter(const Graph& graph, const DirectionMap& dm) {
deba@416
  2401
    return Orienter<const Graph, const DirectionMap>(graph, dm);
deba@416
  2402
  }
deba@416
  2403
deba@416
  2404
  namespace _adaptor_bits {
deba@416
  2405
deba@416
  2406
    template<typename _Digraph,
deba@416
  2407
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2408
             typename _FlowMap = _CapacityMap,
deba@416
  2409
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2410
    class ResForwardFilter {
deba@416
  2411
    public:
deba@416
  2412
deba@416
  2413
      typedef _Digraph Digraph;
deba@416
  2414
      typedef _CapacityMap CapacityMap;
deba@416
  2415
      typedef _FlowMap FlowMap;
deba@416
  2416
      typedef _Tolerance Tolerance;
deba@416
  2417
deba@416
  2418
      typedef typename Digraph::Arc Key;
deba@416
  2419
      typedef bool Value;
deba@416
  2420
deba@416
  2421
    private:
deba@416
  2422
deba@416
  2423
      const CapacityMap* _capacity;
deba@416
  2424
      const FlowMap* _flow;
deba@416
  2425
      Tolerance _tolerance;
deba@416
  2426
    public:
deba@416
  2427
deba@416
  2428
      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416
  2429
                       const Tolerance& tolerance = Tolerance())
deba@416
  2430
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416
  2431
deba@416
  2432
      bool operator[](const typename Digraph::Arc& a) const {
deba@416
  2433
        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
deba@416
  2434
      }
deba@416
  2435
    };
deba@416
  2436
deba@416
  2437
    template<typename _Digraph,
deba@416
  2438
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2439
             typename _FlowMap = _CapacityMap,
deba@416
  2440
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2441
    class ResBackwardFilter {
deba@416
  2442
    public:
deba@416
  2443
deba@416
  2444
      typedef _Digraph Digraph;
deba@416
  2445
      typedef _CapacityMap CapacityMap;
deba@416
  2446
      typedef _FlowMap FlowMap;
deba@416
  2447
      typedef _Tolerance Tolerance;
deba@416
  2448
deba@416
  2449
      typedef typename Digraph::Arc Key;
deba@416
  2450
      typedef bool Value;
deba@416
  2451
deba@416
  2452
    private:
deba@416
  2453
deba@416
  2454
      const CapacityMap* _capacity;
deba@416
  2455
      const FlowMap* _flow;
deba@416
  2456
      Tolerance _tolerance;
deba@416
  2457
deba@416
  2458
    public:
deba@416
  2459
deba@416
  2460
      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416
  2461
                        const Tolerance& tolerance = Tolerance())
deba@416
  2462
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416
  2463
deba@416
  2464
      bool operator[](const typename Digraph::Arc& a) const {
deba@416
  2465
        return _tolerance.positive((*_flow)[a]);
deba@416
  2466
      }
deba@416
  2467
    };
deba@416
  2468
deba@416
  2469
  }
deba@416
  2470
deba@416
  2471
  /// \ingroup graph_adaptors
deba@416
  2472
  ///
deba@416
  2473
  /// \brief An adaptor for composing the residual graph for directed
deba@416
  2474
  /// flow and circulation problems.
deba@416
  2475
  ///
deba@416
  2476
  /// An adaptor for composing the residual graph for directed flow and
deba@416
  2477
  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
deba@416
  2478
  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@416
  2479
  /// be functions on the arc-set.
deba@416
  2480
  ///
deba@416
  2481
  /// Then Residual implements the digraph structure with
deba@416
  2482
  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
deba@416
  2483
  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
deba@416
  2484
  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
deba@416
  2485
  /// called residual graph.  When we take the union
deba@416
  2486
  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
deba@416
  2487
  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
deba@416
  2488
  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
deba@416
  2489
  /// orientation.
deba@416
  2490
  ///
deba@416
  2491
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416
  2492
  /// "Digraph concept". The type is implicitly const.
deba@416
  2493
  /// \tparam _CapacityMap An arc map of some numeric type, it defines
deba@416
  2494
  /// the capacities in the flow problem. The map is implicitly const.
deba@416
  2495
  /// \tparam _FlowMap An arc map of some numeric type, it defines
deba@416
  2496
  /// the capacities in the flow problem.
deba@416
  2497
  /// \tparam _Tolerance Handler for inexact computation.
deba@416
  2498
  template<typename _Digraph,
deba@416
  2499
           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2500
           typename _FlowMap = _CapacityMap,
deba@414
  2501
           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2502
  class Residual :
deba@416
  2503
    public FilterArcs<
deba@416
  2504
    Undirector<const _Digraph>,
deba@416
  2505
    typename Undirector<const _Digraph>::template CombinedArcMap<
deba@416
  2506
      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
deba@416
  2507
                                      _FlowMap, _Tolerance>,
deba@416
  2508
      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
deba@416
  2509
                                       _FlowMap, _Tolerance> > >
deba@416
  2510
  {
deba@414
  2511
  public:
deba@414
  2512
deba@414
  2513
    typedef _Digraph Digraph;
deba@414
  2514
    typedef _CapacityMap CapacityMap;
deba@414
  2515
    typedef _FlowMap FlowMap;
deba@414
  2516
    typedef _Tolerance Tolerance;
deba@414
  2517
deba@414
  2518
    typedef typename CapacityMap::Value Value;
deba@416
  2519
    typedef Residual Adaptor;
deba@414
  2520
deba@414
  2521
  protected:
deba@414
  2522
deba@416
  2523
    typedef Undirector<const Digraph> Undirected;
deba@416
  2524
deba@416
  2525
    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
deba@416
  2526
                                            FlowMap, Tolerance> ForwardFilter;
deba@416
  2527
deba@416
  2528
    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
deba@416
  2529
                                             FlowMap, Tolerance> BackwardFilter;
deba@416
  2530
deba@416
  2531
    typedef typename Undirected::
deba@414
  2532
    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
deba@414
  2533
deba@416
  2534
    typedef FilterArcs<Undirected, ArcFilter> Parent;
deba@414
  2535
deba@414
  2536
    const CapacityMap* _capacity;
deba@414
  2537
    FlowMap* _flow;
deba@414
  2538
deba@416
  2539
    Undirected _graph;
deba@414
  2540
    ForwardFilter _forward_filter;
deba@414
  2541
    BackwardFilter _backward_filter;
deba@414
  2542
    ArcFilter _arc_filter;
deba@414
  2543
deba@414
  2544
  public:
deba@414
  2545
deba@414
  2546
    /// \brief Constructor of the residual digraph.
deba@414
  2547
    ///
deba@416
  2548
    /// Constructor of the residual graph. The parameters are the digraph,
deba@414
  2549
    /// the flow map, the capacity map and a tolerance object.
deba@416
  2550
    Residual(const Digraph& digraph, const CapacityMap& capacity,
deba@416
  2551
             FlowMap& flow, const Tolerance& tolerance = Tolerance())
deba@414
  2552
      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
deba@416
  2553
        _forward_filter(capacity, flow, tolerance),
deba@414
  2554
        _backward_filter(capacity, flow, tolerance),
deba@414
  2555
        _arc_filter(_forward_filter, _backward_filter)
deba@414
  2556
    {
deba@414
  2557
      Parent::setDigraph(_graph);
deba@414
  2558
      Parent::setArcFilterMap(_arc_filter);
deba@414
  2559
    }
deba@414
  2560
deba@414
  2561
    typedef typename Parent::Arc Arc;
deba@414
  2562
deba@414
  2563
    /// \brief Gives back the residual capacity of the arc.
deba@414
  2564
    ///
deba@414
  2565
    /// Gives back the residual capacity of the arc.
deba@416
  2566
    Value residualCapacity(const Arc& a) const {
deba@416
  2567
      if (Undirected::direction(a)) {
deba@416
  2568
        return (*_capacity)[a] - (*_flow)[a];
deba@414
  2569
      } else {
deba@416
  2570
        return (*_flow)[a];
deba@414
  2571
      }
deba@416
  2572
    }
deba@416
  2573
deba@416
  2574
    /// \brief Augment on the given arc in the residual graph.
deba@414
  2575
    ///
deba@416
  2576
    /// Augment on the given arc in the residual graph. It increase
deba@414
  2577
    /// or decrease the flow on the original arc depend on the direction
deba@414
  2578
    /// of the residual arc.
deba@416
  2579
    void augment(const Arc& a, const Value& v) const {
deba@416
  2580
      if (Undirected::direction(a)) {
deba@416
  2581
        _flow->set(a, (*_flow)[a] + v);
deba@416
  2582
      } else {
deba@416
  2583
        _flow->set(a, (*_flow)[a] - v);
deba@414
  2584
      }
deba@414
  2585
    }
deba@414
  2586
deba@414
  2587
    /// \brief Returns the direction of the arc.
deba@414
  2588
    ///
deba@414
  2589
    /// Returns true when the arc is same oriented as the original arc.
deba@416
  2590
    static bool forward(const Arc& a) {
deba@416
  2591
      return Undirected::direction(a);
deba@414
  2592
    }
deba@414
  2593
deba@414
  2594
    /// \brief Returns the direction of the arc.
deba@414
  2595
    ///
deba@414
  2596
    /// Returns true when the arc is opposite oriented as the original arc.
deba@416
  2597
    static bool backward(const Arc& a) {
deba@416
  2598
      return !Undirected::direction(a);
deba@414
  2599
    }
deba@414
  2600
deba@414
  2601
    /// \brief Gives back the forward oriented residual arc.
deba@414
  2602
    ///
deba@414
  2603
    /// Gives back the forward oriented residual arc.
deba@416
  2604
    static Arc forward(const typename Digraph::Arc& a) {
deba@416
  2605
      return Undirected::direct(a, true);
deba@414
  2606
    }
deba@414
  2607
deba@414
  2608
    /// \brief Gives back the backward oriented residual arc.
deba@414
  2609
    ///
deba@414
  2610
    /// Gives back the backward oriented residual arc.
deba@416
  2611
    static Arc backward(const typename Digraph::Arc& a) {
deba@416
  2612
      return Undirected::direct(a, false);
deba@414
  2613
    }
deba@414
  2614
deba@414
  2615
    /// \brief Residual capacity map.
deba@414
  2616
    ///
deba@416
  2617
    /// In generic residual graph the residual capacity can be obtained
deba@416
  2618
    /// as a map.
deba@416
  2619
    class ResidualCapacity {
deba@414
  2620
    protected:
deba@414
  2621
      const Adaptor* _adaptor;
deba@414
  2622
    public:
deba@416
  2623
      /// The Key type
deba@414
  2624
      typedef Arc Key;
deba@416
  2625
      /// The Value type
deba@414
  2626
      typedef typename _CapacityMap::Value Value;
deba@414
  2627
deba@416
  2628
      /// Constructor
deba@416
  2629
      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
deba@416
  2630