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