lemon/adaptors.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 12 Dec 2008 22:18:41 +0100
changeset 448 9d9990909fc8
parent 447 3c0d39b6388c
child 449 91fcb8ed4cdc
permissions -rw-r--r--
Add missing const keywords (+ remove misleading ones) (#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
deba@416
   820
  template <typename _Graph, typename NodeFilterMap,
deba@416
   821
            typename EdgeFilterMap, bool _checked = true>
deba@416
   822
  class SubGraphBase : public GraphAdaptorBase<_Graph> {
deba@416
   823
  public:
deba@416
   824
    typedef _Graph Graph;
deba@416
   825
    typedef SubGraphBase Adaptor;
deba@416
   826
    typedef GraphAdaptorBase<_Graph> Parent;
deba@416
   827
  protected:
deba@416
   828
deba@416
   829
    NodeFilterMap* _node_filter_map;
deba@416
   830
    EdgeFilterMap* _edge_filter_map;
deba@416
   831
deba@416
   832
    SubGraphBase()
deba@416
   833
      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
deba@416
   834
deba@416
   835
    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416
   836
      _node_filter_map=&node_filter_map;
deba@416
   837
    }
deba@416
   838
    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416
   839
      _edge_filter_map=&edge_filter_map;
deba@416
   840
    }
deba@416
   841
deba@416
   842
  public:
deba@416
   843
deba@416
   844
    typedef typename Parent::Node Node;
deba@416
   845
    typedef typename Parent::Arc Arc;
deba@416
   846
    typedef typename Parent::Edge Edge;
deba@416
   847
deba@416
   848
    void first(Node& i) const {
deba@416
   849
      Parent::first(i);
deba@416
   850
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
   851
    }
deba@416
   852
deba@416
   853
    void first(Arc& i) const {
deba@416
   854
      Parent::first(i);
deba@416
   855
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   856
                            || !(*_node_filter_map)[Parent::source(i)]
deba@416
   857
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   858
        Parent::next(i);
deba@416
   859
    }
deba@416
   860
deba@416
   861
    void first(Edge& i) const {
deba@416
   862
      Parent::first(i);
deba@416
   863
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   864
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   865
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   866
        Parent::next(i);
deba@416
   867
    }
deba@416
   868
deba@416
   869
    void firstIn(Arc& i, const Node& n) const {
deba@416
   870
      Parent::firstIn(i, n);
deba@416
   871
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   872
                            || !(*_node_filter_map)[Parent::source(i)]))
deba@416
   873
        Parent::nextIn(i);
deba@416
   874
    }
deba@416
   875
deba@416
   876
    void firstOut(Arc& i, const Node& n) const {
deba@416
   877
      Parent::firstOut(i, n);
deba@416
   878
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   879
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   880
        Parent::nextOut(i);
deba@416
   881
    }
deba@416
   882
deba@416
   883
    void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416
   884
      Parent::firstInc(i, d, n);
deba@416
   885
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   886
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   887
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   888
        Parent::nextInc(i, d);
deba@416
   889
    }
deba@416
   890
deba@416
   891
    void next(Node& i) const {
deba@416
   892
      Parent::next(i);
deba@416
   893
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
   894
    }
deba@416
   895
deba@416
   896
    void next(Arc& i) const {
deba@416
   897
      Parent::next(i);
deba@416
   898
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   899
                            || !(*_node_filter_map)[Parent::source(i)]
deba@416
   900
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   901
        Parent::next(i);
deba@416
   902
    }
deba@416
   903
deba@416
   904
    void next(Edge& i) const {
deba@416
   905
      Parent::next(i);
deba@416
   906
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   907
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   908
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   909
        Parent::next(i);
deba@416
   910
    }
deba@416
   911
deba@416
   912
    void nextIn(Arc& i) const {
deba@416
   913
      Parent::nextIn(i);
deba@416
   914
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   915
                            || !(*_node_filter_map)[Parent::source(i)]))
deba@416
   916
        Parent::nextIn(i);
deba@416
   917
    }
deba@416
   918
deba@416
   919
    void nextOut(Arc& i) const {
deba@416
   920
      Parent::nextOut(i);
deba@416
   921
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   922
                            || !(*_node_filter_map)[Parent::target(i)]))
deba@416
   923
        Parent::nextOut(i);
deba@416
   924
    }
deba@416
   925
deba@416
   926
    void nextInc(Edge& i, bool& d) const {
deba@416
   927
      Parent::nextInc(i, d);
deba@416
   928
      while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416
   929
                            || !(*_node_filter_map)[Parent::u(i)]
deba@416
   930
                            || !(*_node_filter_map)[Parent::v(i)]))
deba@416
   931
        Parent::nextInc(i, d);
deba@416
   932
    }
deba@416
   933
deba@416
   934
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416
   935
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416
   936
deba@416
   937
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416
   938
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416
   939
deba@416
   940
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416
   941
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416
   942
deba@416
   943
    typedef False NodeNumTag;
kpeter@446
   944
    typedef False ArcNumTag;
deba@416
   945
    typedef False EdgeNumTag;
deba@416
   946
kpeter@446
   947
    typedef FindArcTagIndicator<Graph> FindArcTag;
deba@416
   948
    Arc findArc(const Node& u, const Node& v,
kpeter@448
   949
                const Arc& prev = INVALID) const {
deba@416
   950
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@416
   951
        return INVALID;
deba@416
   952
      }
deba@416
   953
      Arc arc = Parent::findArc(u, v, prev);
deba@416
   954
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416
   955
        arc = Parent::findArc(u, v, arc);
deba@416
   956
      }
deba@416
   957
      return arc;
deba@416
   958
    }
kpeter@446
   959
kpeter@446
   960
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
   961
    Edge findEdge(const Node& u, const Node& v,
kpeter@448
   962
                  const Edge& prev = INVALID) const {
deba@416
   963
      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@416
   964
        return INVALID;
deba@416
   965
      }
deba@416
   966
      Edge edge = Parent::findEdge(u, v, prev);
deba@416
   967
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416
   968
        edge = Parent::findEdge(u, v, edge);
deba@416
   969
      }
deba@416
   970
      return edge;
deba@416
   971
    }
deba@416
   972
deba@416
   973
    template <typename _Value>
deba@416
   974
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
   975
      typename Parent::template NodeMap<_Value> > {
deba@416
   976
    public:
deba@416
   977
      typedef _Value Value;
deba@416
   978
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
   979
                             template NodeMap<Value> > MapParent;
deba@416
   980
deba@416
   981
      NodeMap(const Adaptor& adaptor)
deba@416
   982
        : MapParent(adaptor) {}
deba@416
   983
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
   984
        : MapParent(adaptor, value) {}
deba@416
   985
deba@416
   986
    private:
deba@416
   987
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
   988
        return operator=<NodeMap>(cmap);
deba@416
   989
      }
deba@416
   990
deba@416
   991
      template <typename CMap>
deba@416
   992
      NodeMap& operator=(const CMap& cmap) {
deba@416
   993
        MapParent::operator=(cmap);
deba@416
   994
        return *this;
deba@416
   995
      }
deba@416
   996
    };
deba@416
   997
deba@416
   998
    template <typename _Value>
deba@416
   999
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
  1000
      typename Parent::template ArcMap<_Value> > {
deba@416
  1001
    public:
deba@416
  1002
      typedef _Value Value;
deba@416
  1003
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1004
                             template ArcMap<Value> > MapParent;
deba@416
  1005
deba@416
  1006
      ArcMap(const Adaptor& adaptor)
deba@416
  1007
        : MapParent(adaptor) {}
deba@416
  1008
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  1009
        : MapParent(adaptor, value) {}
deba@416
  1010
deba@416
  1011
    private:
deba@416
  1012
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  1013
        return operator=<ArcMap>(cmap);
deba@416
  1014
      }
deba@416
  1015
deba@416
  1016
      template <typename CMap>
deba@416
  1017
      ArcMap& operator=(const CMap& cmap) {
deba@416
  1018
        MapParent::operator=(cmap);
deba@416
  1019
        return *this;
deba@416
  1020
      }
deba@416
  1021
    };
deba@416
  1022
deba@416
  1023
    template <typename _Value>
deba@416
  1024
    class EdgeMap : public SubMapExtender<Adaptor,
deba@416
  1025
      typename Parent::template EdgeMap<_Value> > {
deba@416
  1026
    public:
deba@416
  1027
      typedef _Value Value;
deba@416
  1028
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1029
                             template EdgeMap<Value> > MapParent;
deba@416
  1030
deba@416
  1031
      EdgeMap(const Adaptor& adaptor)
deba@416
  1032
        : MapParent(adaptor) {}
deba@416
  1033
deba@416
  1034
      EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416
  1035
        : MapParent(adaptor, value) {}
deba@416
  1036
deba@416
  1037
    private:
deba@416
  1038
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@416
  1039
        return operator=<EdgeMap>(cmap);
deba@416
  1040
      }
deba@416
  1041
deba@416
  1042
      template <typename CMap>
deba@416
  1043
      EdgeMap& operator=(const CMap& cmap) {
deba@416
  1044
        MapParent::operator=(cmap);
deba@416
  1045
        return *this;
deba@416
  1046
      }
deba@416
  1047
    };
deba@416
  1048
deba@416
  1049
  };
deba@416
  1050
deba@416
  1051
  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@416
  1052
  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@416
  1053
    : public GraphAdaptorBase<_Graph> {
deba@416
  1054
  public:
deba@416
  1055
    typedef _Graph Graph;
deba@416
  1056
    typedef SubGraphBase Adaptor;
deba@416
  1057
    typedef GraphAdaptorBase<_Graph> Parent;
deba@416
  1058
  protected:
deba@416
  1059
    NodeFilterMap* _node_filter_map;
deba@416
  1060
    EdgeFilterMap* _edge_filter_map;
deba@416
  1061
    SubGraphBase() : Parent(),
deba@416
  1062
                     _node_filter_map(0), _edge_filter_map(0) { }
deba@416
  1063
deba@416
  1064
    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416
  1065
      _node_filter_map=&node_filter_map;
deba@416
  1066
    }
deba@416
  1067
    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416
  1068
      _edge_filter_map=&edge_filter_map;
deba@416
  1069
    }
deba@416
  1070
deba@416
  1071
  public:
deba@416
  1072
deba@416
  1073
    typedef typename Parent::Node Node;
deba@416
  1074
    typedef typename Parent::Arc Arc;
deba@416
  1075
    typedef typename Parent::Edge Edge;
deba@416
  1076
deba@416
  1077
    void first(Node& i) const {
deba@416
  1078
      Parent::first(i);
deba@416
  1079
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
  1080
    }
deba@416
  1081
deba@416
  1082
    void first(Arc& i) const {
deba@416
  1083
      Parent::first(i);
deba@416
  1084
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1085
    }
deba@416
  1086
deba@416
  1087
    void first(Edge& i) const {
deba@416
  1088
      Parent::first(i);
deba@416
  1089
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1090
    }
deba@416
  1091
deba@416
  1092
    void firstIn(Arc& i, const Node& n) const {
deba@416
  1093
      Parent::firstIn(i, n);
deba@416
  1094
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416
  1095
    }
deba@416
  1096
deba@416
  1097
    void firstOut(Arc& i, const Node& n) const {
deba@416
  1098
      Parent::firstOut(i, n);
deba@416
  1099
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416
  1100
    }
deba@416
  1101
deba@416
  1102
    void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416
  1103
      Parent::firstInc(i, d, n);
deba@416
  1104
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416
  1105
    }
deba@416
  1106
deba@416
  1107
    void next(Node& i) const {
deba@416
  1108
      Parent::next(i);
deba@416
  1109
      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416
  1110
    }
deba@416
  1111
    void next(Arc& i) const {
deba@416
  1112
      Parent::next(i);
deba@416
  1113
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1114
    }
deba@416
  1115
    void next(Edge& i) const {
deba@416
  1116
      Parent::next(i);
deba@416
  1117
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416
  1118
    }
deba@416
  1119
    void nextIn(Arc& i) const {
deba@416
  1120
      Parent::nextIn(i);
deba@416
  1121
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416
  1122
    }
deba@416
  1123
deba@416
  1124
    void nextOut(Arc& i) const {
deba@416
  1125
      Parent::nextOut(i);
deba@416
  1126
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416
  1127
    }
deba@416
  1128
    void nextInc(Edge& i, bool& d) const {
deba@416
  1129
      Parent::nextInc(i, d);
deba@416
  1130
      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416
  1131
    }
deba@416
  1132
deba@416
  1133
    void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416
  1134
    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416
  1135
deba@416
  1136
    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416
  1137
    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416
  1138
deba@416
  1139
    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416
  1140
    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416
  1141
deba@416
  1142
    typedef False NodeNumTag;
kpeter@446
  1143
    typedef False ArcNumTag;
deba@416
  1144
    typedef False EdgeNumTag;
deba@416
  1145
kpeter@446
  1146
    typedef FindArcTagIndicator<Graph> FindArcTag;
deba@416
  1147
    Arc findArc(const Node& u, const Node& v,
kpeter@448
  1148
                const Arc& prev = INVALID) const {
deba@416
  1149
      Arc arc = Parent::findArc(u, v, prev);
deba@416
  1150
      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416
  1151
        arc = Parent::findArc(u, v, arc);
deba@416
  1152
      }
deba@416
  1153
      return arc;
deba@416
  1154
    }
kpeter@446
  1155
kpeter@446
  1156
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416
  1157
    Edge findEdge(const Node& u, const Node& v,
kpeter@448
  1158
                  const Edge& prev = INVALID) const {
deba@416
  1159
      Edge edge = Parent::findEdge(u, v, prev);
deba@416
  1160
      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416
  1161
        edge = Parent::findEdge(u, v, edge);
deba@416
  1162
      }
deba@416
  1163
      return edge;
deba@416
  1164
    }
deba@416
  1165
deba@416
  1166
    template <typename _Value>
deba@416
  1167
    class NodeMap : public SubMapExtender<Adaptor,
deba@416
  1168
      typename Parent::template NodeMap<_Value> > {
deba@416
  1169
    public:
deba@416
  1170
      typedef _Value Value;
deba@416
  1171
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1172
                             template NodeMap<Value> > MapParent;
deba@416
  1173
deba@416
  1174
      NodeMap(const Adaptor& adaptor)
deba@416
  1175
        : MapParent(adaptor) {}
deba@416
  1176
      NodeMap(const Adaptor& adaptor, const Value& value)
deba@416
  1177
        : MapParent(adaptor, value) {}
deba@416
  1178
deba@416
  1179
    private:
deba@416
  1180
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
  1181
        return operator=<NodeMap>(cmap);
deba@416
  1182
      }
deba@416
  1183
deba@416
  1184
      template <typename CMap>
deba@416
  1185
      NodeMap& operator=(const CMap& cmap) {
deba@416
  1186
        MapParent::operator=(cmap);
deba@416
  1187
        return *this;
deba@416
  1188
      }
deba@416
  1189
    };
deba@416
  1190
deba@416
  1191
    template <typename _Value>
deba@416
  1192
    class ArcMap : public SubMapExtender<Adaptor,
deba@416
  1193
      typename Parent::template ArcMap<_Value> > {
deba@416
  1194
    public:
deba@416
  1195
      typedef _Value Value;
deba@416
  1196
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1197
                             template ArcMap<Value> > MapParent;
deba@416
  1198
deba@416
  1199
      ArcMap(const Adaptor& adaptor)
deba@416
  1200
        : MapParent(adaptor) {}
deba@416
  1201
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  1202
        : MapParent(adaptor, value) {}
deba@416
  1203
deba@416
  1204
    private:
deba@416
  1205
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  1206
        return operator=<ArcMap>(cmap);
deba@416
  1207
      }
deba@416
  1208
deba@416
  1209
      template <typename CMap>
deba@416
  1210
      ArcMap& operator=(const CMap& cmap) {
deba@416
  1211
        MapParent::operator=(cmap);
deba@416
  1212
        return *this;
deba@416
  1213
      }
deba@416
  1214
    };
deba@416
  1215
deba@416
  1216
    template <typename _Value>
deba@416
  1217
    class EdgeMap : public SubMapExtender<Adaptor,
deba@416
  1218
      typename Parent::template EdgeMap<_Value> > {
deba@416
  1219
    public:
deba@416
  1220
      typedef _Value Value;
deba@416
  1221
      typedef SubMapExtender<Adaptor, typename Parent::
deba@416
  1222
                             template EdgeMap<Value> > MapParent;
deba@416
  1223
deba@416
  1224
      EdgeMap(const Adaptor& adaptor)
deba@416
  1225
        : MapParent(adaptor) {}
deba@416
  1226
deba@416
  1227
      EdgeMap(const Adaptor& adaptor, const _Value& value)
deba@416
  1228
        : MapParent(adaptor, value) {}
deba@416
  1229
deba@416
  1230
    private:
deba@416
  1231
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@416
  1232
        return operator=<EdgeMap>(cmap);
deba@416
  1233
      }
deba@416
  1234
deba@416
  1235
      template <typename CMap>
deba@416
  1236
      EdgeMap& operator=(const CMap& cmap) {
deba@416
  1237
        MapParent::operator=(cmap);
deba@416
  1238
        return *this;
deba@416
  1239
      }
deba@416
  1240
    };
deba@416
  1241
deba@416
  1242
  };
deba@416
  1243
deba@416
  1244
  /// \ingroup graph_adaptors
deba@414
  1245
  ///
deba@416
  1246
  /// \brief A graph adaptor for hiding nodes and edges in an
deba@416
  1247
  /// undirected graph.
deba@414
  1248
  ///
deba@416
  1249
  /// SubGraph hides nodes and edges in a graph. A bool node map and a
deba@416
  1250
  /// bool edge map must be specified, which define the filters for
deba@416
  1251
  /// nodes and edges. Just the nodes and edges with true value are
deba@416
  1252
  /// shown in the subgraph. The SubGraph is conform to the \ref
deba@416
  1253
  /// concepts::Graph "Graph concept". If the \c _checked parameter is
deba@416
  1254
  /// true, then the edges incident to filtered nodes are also
deba@416
  1255
  /// filtered out.
deba@416
  1256
  ///
deba@416
  1257
  /// \tparam _Graph It must be conform to the \ref
deba@416
  1258
  /// concepts::Graph "Graph concept". The type can be specified
deba@416
  1259
  /// to const.
deba@416
  1260
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416
  1261
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
deba@416
  1262
  /// \tparam _checked If the parameter is false then the edge filtering
deba@416
  1263
  /// is not checked with respect to node filter. Otherwise, each edge
deba@416
  1264
  /// is automatically filtered, which is incident to a filtered node.
deba@416
  1265
  ///
deba@416
  1266
  /// \see FilterNodes
deba@416
  1267
  /// \see FilterEdges
deba@416
  1268
  template<typename _Graph, typename NodeFilterMap,
deba@416
  1269
           typename EdgeFilterMap, bool _checked = true>
deba@416
  1270
  class SubGraph
deba@416
  1271
    : public GraphAdaptorExtender<
deba@416
  1272
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
deba@414
  1273
  public:
deba@416
  1274
    typedef _Graph Graph;
deba@416
  1275
    typedef GraphAdaptorExtender<
deba@416
  1276
      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
deba@414
  1277
deba@415
  1278
    typedef typename Parent::Node Node;
deba@416
  1279
    typedef typename Parent::Edge Edge;
deba@415
  1280
deba@414
  1281
  protected:
deba@416
  1282
    SubGraph() { }
deba@414
  1283
  public:
deba@414
  1284
deba@415
  1285
    /// \brief Constructor
deba@415
  1286
    ///
deba@416
  1287
    /// Creates a subgraph for the given graph with given node and
deba@416
  1288
    /// edge map filters.
deba@416
  1289
    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
deba@416
  1290
             EdgeFilterMap& edge_filter_map) {
deba@416
  1291
      setGraph(_graph);
deba@416
  1292
      setNodeFilterMap(node_filter_map);
deba@416
  1293
      setEdgeFilterMap(edge_filter_map);
deba@414
  1294
    }
deba@414
  1295
deba@415
  1296
    /// \brief Hides the node of the graph
deba@415
  1297
    ///
deba@416
  1298
    /// This function hides \c n in the graph, i.e. the iteration
deba@416
  1299
    /// jumps over it. This is done by simply setting the value of \c n
deba@415
  1300
    /// to be false in the corresponding node-map.
deba@415
  1301
    void hide(const Node& n) const { Parent::hide(n); }
deba@415
  1302
deba@416
  1303
    /// \brief Hides the edge of the graph
deba@416
  1304
    ///
deba@416
  1305
    /// This function hides \c e in the graph, i.e. the iteration
deba@416
  1306
    /// jumps over it. This is done by simply setting the value of \c e
deba@416
  1307
    /// to be false in the corresponding edge-map.
deba@416
  1308
    void hide(const Edge& e) const { Parent::hide(e); }
deba@416
  1309
deba@415
  1310
    /// \brief Unhides the node of the graph
deba@415
  1311
    ///
deba@416
  1312
    /// The value of \c n is set to be true in the node-map which stores
deba@416
  1313
    /// hide information. If \c n was hidden previuosly, then it is shown
deba@415
  1314
    /// again
deba@415
  1315
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@415
  1316
deba@416
  1317
    /// \brief Unhides the edge of the graph
deba@416
  1318
    ///
deba@416
  1319
    /// The value of \c e is set to be true in the edge-map which stores
deba@416
  1320
    /// hide information. If \c e was hidden previuosly, then it is shown
deba@416
  1321
    /// again
deba@416
  1322
    void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416
  1323
deba@415
  1324
    /// \brief Returns true if \c n is hidden.
deba@415
  1325
    ///
deba@415
  1326
    /// Returns true if \c n is hidden.
deba@415
  1327
    ///
deba@415
  1328
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@415
  1329
deba@416
  1330
    /// \brief Returns true if \c e is hidden.
deba@416
  1331
    ///
deba@416
  1332
    /// Returns true if \c e is hidden.
deba@416
  1333
    ///
deba@416
  1334
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@414
  1335
  };
deba@414
  1336
deba@416
  1337
  /// \brief Just gives back a subgraph
deba@414
  1338
  ///
deba@416
  1339
  /// Just gives back a subgraph
deba@416
  1340
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1341
  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
deba@416
  1342
  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416
  1343
    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
deba@416
  1344
  }
deba@416
  1345
deba@416
  1346
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1347
  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416
  1348
  subGraph(const Graph& graph,
deba@416
  1349
           const NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416
  1350
    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416
  1351
      (graph, nfm, efm);
deba@416
  1352
  }
deba@416
  1353
deba@416
  1354
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1355
  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416
  1356
  subGraph(const Graph& graph,
deba@416
  1357
           NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416
  1358
    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416
  1359
      (graph, nfm, efm);
deba@416
  1360
  }
deba@416
  1361
deba@416
  1362
  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416
  1363
  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416
  1364
  subGraph(const Graph& graph,
deba@416
  1365
           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416
  1366
    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416
  1367
      (graph, nfm, efm);
deba@416
  1368
  }
deba@416
  1369
deba@416
  1370
  /// \ingroup graph_adaptors
deba@416
  1371
  ///
deba@416
  1372
  /// \brief An adaptor for hiding nodes from a digraph or a graph.
deba@416
  1373
  ///
deba@416
  1374
  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
deba@416
  1375
  /// node map must be specified, which defines the filters for
deba@416
  1376
  /// nodes. Just the unfiltered nodes and the arcs or edges incident
deba@416
  1377
  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
deba@416
  1378
  /// FilterNodes is conform to the \ref concepts::Digraph
deba@416
  1379
  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
deba@416
  1380
  /// on the \c _Digraph template parameter. If the \c _checked
deba@416
  1381
  /// parameter is true, then the arc or edges incident to filtered nodes
deba@416
  1382
  /// are also filtered out.
deba@416
  1383
  ///
deba@416
  1384
  /// \tparam _Digraph It must be conform to the \ref
deba@416
  1385
  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
deba@416
  1386
  /// "Graph concept". The type can be specified to be const.
deba@416
  1387
  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416
  1388
  /// \tparam _checked If the parameter is false then the arc or edge
deba@416
  1389
  /// filtering is not checked with respect to node filter. In this
deba@416
  1390
  /// case just isolated nodes can be filtered out from the
deba@416
  1391
  /// graph.
deba@416
  1392
#ifdef DOXYGEN
deba@416
  1393
  template<typename _Digraph,
deba@416
  1394
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416
  1395
           bool _checked = true>
deba@416
  1396
#else
deba@416
  1397
  template<typename _Digraph,
deba@416
  1398
           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416
  1399
           bool _checked = true,
deba@416
  1400
           typename Enable = void>
deba@416
  1401
#endif
deba@416
  1402
  class FilterNodes
deba@416
  1403
    : public SubDigraph<_Digraph, _NodeFilterMap,
deba@416
  1404
                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
deba@416
  1405
  public:
deba@416
  1406
deba@416
  1407
    typedef _Digraph Digraph;
deba@416
  1408
    typedef _NodeFilterMap NodeFilterMap;
deba@416
  1409
deba@416
  1410
    typedef SubDigraph<Digraph, NodeFilterMap,
deba@416
  1411
                       ConstMap<typename Digraph::Arc, bool>, _checked>
deba@416
  1412
    Parent;
deba@416
  1413
deba@416
  1414
    typedef typename Parent::Node Node;
deba@416
  1415
deba@416
  1416
  protected:
deba@416
  1417
    ConstMap<typename Digraph::Arc, bool> const_true_map;
deba@416
  1418
deba@416
  1419
    FilterNodes() : const_true_map(true) {
deba@416
  1420
      Parent::setArcFilterMap(const_true_map);
deba@416
  1421
    }
deba@416
  1422
deba@416
  1423
  public:
deba@416
  1424
deba@416
  1425
    /// \brief Constructor
deba@416
  1426
    ///
deba@416
  1427
    /// Creates an adaptor for the given digraph or graph with
deba@416
  1428
    /// given node filter map.
deba@416
  1429
    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
deba@416
  1430
      Parent(), const_true_map(true) {
deba@416
  1431
      Parent::setDigraph(_digraph);
deba@416
  1432
      Parent::setNodeFilterMap(node_filter);
deba@416
  1433
      Parent::setArcFilterMap(const_true_map);
deba@416
  1434
    }
deba@416
  1435
deba@416
  1436
    /// \brief Hides the node of the graph
deba@416
  1437
    ///
deba@416
  1438
    /// This function hides \c n in the digraph or graph, i.e. the iteration
deba@416
  1439
    /// jumps over it. This is done by simply setting the value of \c n
deba@416
  1440
    /// to be false in the corresponding node map.
deba@416
  1441
    void hide(const Node& n) const { Parent::hide(n); }
deba@416
  1442
deba@416
  1443
    /// \brief Unhides the node of the graph
deba@416
  1444
    ///
deba@416
  1445
    /// The value of \c n is set to be true in the node-map which stores
deba@416
  1446
    /// hide information. If \c n was hidden previuosly, then it is shown
deba@416
  1447
    /// again
deba@416
  1448
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@416
  1449
deba@416
  1450
    /// \brief Returns true if \c n is hidden.
deba@416
  1451
    ///
deba@416
  1452
    /// Returns true if \c n is hidden.
deba@416
  1453
    ///
deba@416
  1454
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416
  1455
deba@416
  1456
  };
deba@416
  1457
deba@416
  1458
  template<typename _Graph, typename _NodeFilterMap, bool _checked>
deba@416
  1459
  class FilterNodes<_Graph, _NodeFilterMap, _checked,
deba@416
  1460
                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
deba@416
  1461
    : public SubGraph<_Graph, _NodeFilterMap,
deba@416
  1462
                      ConstMap<typename _Graph::Edge, bool>, _checked> {
deba@416
  1463
  public:
deba@416
  1464
    typedef _Graph Graph;
deba@416
  1465
    typedef _NodeFilterMap NodeFilterMap;
deba@416
  1466
    typedef SubGraph<Graph, NodeFilterMap,
deba@416
  1467
                     ConstMap<typename Graph::Edge, bool> > Parent;
deba@416
  1468
deba@416
  1469
    typedef typename Parent::Node Node;
deba@416
  1470
  protected:
deba@416
  1471
    ConstMap<typename Graph::Edge, bool> const_true_map;
deba@416
  1472
deba@416
  1473
    FilterNodes() : const_true_map(true) {
deba@416
  1474
      Parent::setEdgeFilterMap(const_true_map);
deba@416
  1475
    }
deba@416
  1476
deba@416
  1477
  public:
deba@416
  1478
deba@416
  1479
    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
deba@416
  1480
      Parent(), const_true_map(true) {
deba@416
  1481
      Parent::setGraph(_graph);
deba@416
  1482
      Parent::setNodeFilterMap(node_filter_map);
deba@416
  1483
      Parent::setEdgeFilterMap(const_true_map);
deba@416
  1484
    }
deba@416
  1485
deba@416
  1486
    void hide(const Node& n) const { Parent::hide(n); }
deba@416
  1487
    void unHide(const Node& n) const { Parent::unHide(n); }
deba@416
  1488
    bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416
  1489
deba@416
  1490
  };
deba@416
  1491
deba@416
  1492
deba@416
  1493
  /// \brief Just gives back a FilterNodes adaptor
deba@416
  1494
  ///
deba@416
  1495
  /// Just gives back a FilterNodes adaptor
deba@414
  1496
  template<typename Digraph, typename NodeFilterMap>
deba@416
  1497
  FilterNodes<const Digraph, NodeFilterMap>
deba@416
  1498
  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
deba@416
  1499
    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
deba@414
  1500
  }
deba@414
  1501
deba@414
  1502
  template<typename Digraph, typename NodeFilterMap>
deba@416
  1503
  FilterNodes<const Digraph, const NodeFilterMap>
deba@416
  1504
  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
deba@416
  1505
    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
deba@414
  1506
  }
deba@414
  1507
deba@416
  1508
  /// \ingroup graph_adaptors
deba@414
  1509
  ///
deba@416
  1510
  /// \brief An adaptor for hiding arcs from a digraph.
deba@414
  1511
  ///
deba@416
  1512
  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
deba@416
  1513
  /// be specified, which defines the filters for arcs. Just the
deba@416
  1514
  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
deba@416
  1515
  /// conform to the \ref concepts::Digraph "Digraph concept".
deba@414
  1516
  ///
deba@416
  1517
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416
  1518
  /// "Digraph concept". The type can be specified to be const.
deba@416
  1519
  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
deba@416
  1520
  /// graph.
deba@414
  1521
  template<typename _Digraph, typename _ArcFilterMap>
deba@416
  1522
  class FilterArcs :
deba@416
  1523
    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
deba@416
  1524
                      _ArcFilterMap, false> {
deba@414
  1525
  public:
deba@414
  1526
    typedef _Digraph Digraph;
deba@414
  1527
    typedef _ArcFilterMap ArcFilterMap;
deba@414
  1528
deba@416
  1529
    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
deba@416
  1530
                       ArcFilterMap, false> Parent;
deba@415
  1531
deba@415
  1532
    typedef typename Parent::Arc Arc;
deba@415
  1533
deba@414
  1534
  protected:
deba@414
  1535
    ConstMap<typename Digraph::Node, bool> const_true_map;
deba@414
  1536
deba@416
  1537
    FilterArcs() : const_true_map(true) {
deba@414
  1538
      Parent::setNodeFilterMap(const_true_map);
deba@414
  1539
    }
deba@414
  1540
deba@414
  1541
  public:
deba@414
  1542
deba@415
  1543
    /// \brief Constructor
deba@415
  1544
    ///
deba@416
  1545
    /// Creates a FilterArcs adaptor for the given graph with
deba@415
  1546
    /// given arc map filter.
deba@416
  1547
    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
deba@416
  1548
      : Parent(), const_true_map(true) {
deba@414
  1549
      Parent::setDigraph(digraph);
deba@414
  1550
      Parent::setNodeFilterMap(const_true_map);
deba@414
  1551
      Parent::setArcFilterMap(arc_filter);
deba@414
  1552
    }
deba@414
  1553
deba@415
  1554
    /// \brief Hides the arc of the graph
deba@415
  1555
    ///
deba@416
  1556
    /// This function hides \c a in the graph, i.e. the iteration
deba@415
  1557
    /// jumps over it. This is done by simply setting the value of \c a
deba@416
  1558
    /// to be false in the corresponding arc map.
deba@415
  1559
    void hide(const Arc& a) const { Parent::hide(a); }
deba@415
  1560
deba@415
  1561
    /// \brief Unhides the arc of the graph
deba@415
  1562
    ///
deba@416
  1563
    /// The value of \c a is set to be true in the arc-map which stores
deba@416
  1564
    /// hide information. If \c a was hidden previuosly, then it is shown
deba@415
  1565
    /// again
deba@415
  1566
    void unHide(const Arc& a) const { Parent::unHide(a); }
deba@415
  1567
deba@415
  1568
    /// \brief Returns true if \c a is hidden.
deba@415
  1569
    ///
deba@415
  1570
    /// Returns true if \c a is hidden.
deba@415
  1571
    ///
deba@415
  1572
    bool hidden(const Arc& a) const { return Parent::hidden(a); }
deba@415
  1573
deba@414
  1574
  };
deba@414
  1575
deba@416
  1576
  /// \brief Just gives back an FilterArcs adaptor
deba@414
  1577
  ///
deba@416
  1578
  /// Just gives back an FilterArcs adaptor
deba@414
  1579
  template<typename Digraph, typename ArcFilterMap>
deba@416
  1580
  FilterArcs<const Digraph, ArcFilterMap>
deba@416
  1581
  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
deba@416
  1582
    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
deba@414
  1583
  }
deba@414
  1584
deba@414
  1585
  template<typename Digraph, typename ArcFilterMap>
deba@416
  1586
  FilterArcs<const Digraph, const ArcFilterMap>
deba@416
  1587
  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
deba@416
  1588
    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
deba@414
  1589
  }
deba@414
  1590
deba@416
  1591
  /// \ingroup graph_adaptors
deba@416
  1592
  ///
deba@416
  1593
  /// \brief An adaptor for hiding edges from a graph.
deba@416
  1594
  ///
deba@416
  1595
  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
deba@416
  1596
  /// be specified, which defines the filters for edges. Just the
deba@416
  1597
  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
deba@416
  1598
  /// conform to the \ref concepts::Graph "Graph concept".
deba@416
  1599
  ///
deba@416
  1600
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416
  1601
  /// "Graph concept". The type can be specified to be const.
deba@416
  1602
  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
deba@416
  1603
  /// graph.
deba@416
  1604
  template<typename _Graph, typename _EdgeFilterMap>
deba@416
  1605
  class FilterEdges :
deba@416
  1606
    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
deba@416
  1607
                    _EdgeFilterMap, false> {
deba@416
  1608
  public:
deba@416
  1609
    typedef _Graph Graph;
deba@416
  1610
    typedef _EdgeFilterMap EdgeFilterMap;
deba@416
  1611
    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
deba@416
  1612
                     EdgeFilterMap, false> Parent;
deba@416
  1613
    typedef typename Parent::Edge Edge;
deba@416
  1614
  protected:
deba@416
  1615
    ConstMap<typename Graph::Node, bool> const_true_map;
deba@416
  1616
deba@416
  1617
    FilterEdges() : const_true_map(true) {
deba@416
  1618
      Parent::setNodeFilterMap(const_true_map);
deba@416
  1619
    }
deba@416
  1620
deba@416
  1621
  public:
deba@416
  1622
deba@416
  1623
    /// \brief Constructor
deba@416
  1624
    ///
deba@416
  1625
    /// Creates a FilterEdges adaptor for the given graph with
deba@416
  1626
    /// given edge map filters.
deba@416
  1627
    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
deba@416
  1628
      Parent(), const_true_map(true) {
deba@416
  1629
      Parent::setGraph(_graph);
deba@416
  1630
      Parent::setNodeFilterMap(const_true_map);
deba@416
  1631
      Parent::setEdgeFilterMap(edge_filter_map);
deba@416
  1632
    }
deba@416
  1633
deba@416
  1634
    /// \brief Hides the edge of the graph
deba@416
  1635
    ///
deba@416
  1636
    /// This function hides \c e in the graph, i.e. the iteration
deba@416
  1637
    /// jumps over it. This is done by simply setting the value of \c e
deba@416
  1638
    /// to be false in the corresponding edge-map.
deba@416
  1639
    void hide(const Edge& e) const { Parent::hide(e); }
deba@416
  1640
deba@416
  1641
    /// \brief Unhides the edge of the graph
deba@416
  1642
    ///
deba@416
  1643
    /// The value of \c e is set to be true in the edge-map which stores
deba@416
  1644
    /// hide information. If \c e was hidden previuosly, then it is shown
deba@416
  1645
    /// again
deba@416
  1646
    void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416
  1647
deba@416
  1648
    /// \brief Returns true if \c e is hidden.
deba@416
  1649
    ///
deba@416
  1650
    /// Returns true if \c e is hidden.
deba@416
  1651
    ///
deba@416
  1652
    bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@416
  1653
deba@416
  1654
  };
deba@416
  1655
deba@416
  1656
  /// \brief Just gives back a FilterEdges adaptor
deba@416
  1657
  ///
deba@416
  1658
  /// Just gives back a FilterEdges adaptor
deba@416
  1659
  template<typename Graph, typename EdgeFilterMap>
deba@416
  1660
  FilterEdges<const Graph, EdgeFilterMap>
deba@416
  1661
  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
deba@416
  1662
    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
deba@416
  1663
  }
deba@416
  1664
deba@416
  1665
  template<typename Graph, typename EdgeFilterMap>
deba@416
  1666
  FilterEdges<const Graph, const EdgeFilterMap>
deba@416
  1667
  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
deba@416
  1668
    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
deba@416
  1669
  }
deba@416
  1670
deba@414
  1671
  template <typename _Digraph>
deba@416
  1672
  class UndirectorBase {
deba@414
  1673
  public:
deba@414
  1674
    typedef _Digraph Digraph;
deba@416
  1675
    typedef UndirectorBase Adaptor;
deba@414
  1676
deba@414
  1677
    typedef True UndirectedTag;
deba@414
  1678
deba@414
  1679
    typedef typename Digraph::Arc Edge;
deba@414
  1680
    typedef typename Digraph::Node Node;
deba@414
  1681
deba@414
  1682
    class Arc : public Edge {
deba@416
  1683
      friend class UndirectorBase;
deba@414
  1684
    protected:
deba@414
  1685
      bool _forward;
deba@414
  1686
deba@414
  1687
      Arc(const Edge& edge, bool forward) :
deba@414
  1688
        Edge(edge), _forward(forward) {}
deba@414
  1689
deba@414
  1690
    public:
deba@414
  1691
      Arc() {}
deba@414
  1692
deba@414
  1693
      Arc(Invalid) : Edge(INVALID), _forward(true) {}
deba@414
  1694
deba@414
  1695
      bool operator==(const Arc &other) const {
deba@416
  1696
        return _forward == other._forward &&
deba@416
  1697
          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
deba@414
  1698
      }
deba@414
  1699
      bool operator!=(const Arc &other) const {
deba@416
  1700
        return _forward != other._forward ||
deba@416
  1701
          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
deba@414
  1702
      }
deba@414
  1703
      bool operator<(const Arc &other) const {
deba@416
  1704
        return _forward < other._forward ||
deba@416
  1705
          (_forward == other._forward &&
deba@416
  1706
           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
deba@414
  1707
      }
deba@414
  1708
    };
deba@414
  1709
deba@414
  1710
deba@414
  1711
deba@414
  1712
    void first(Node& n) const {
deba@414
  1713
      _digraph->first(n);
deba@414
  1714
    }
deba@414
  1715
deba@414
  1716
    void next(Node& n) const {
deba@414
  1717
      _digraph->next(n);
deba@414
  1718
    }
deba@414
  1719
deba@414
  1720
    void first(Arc& a) const {
deba@414
  1721
      _digraph->first(a);
deba@414
  1722
      a._forward = true;
deba@414
  1723
    }
deba@414
  1724
deba@414
  1725
    void next(Arc& a) const {
deba@414
  1726
      if (a._forward) {
deba@416
  1727
        a._forward = false;
deba@414
  1728
      } else {
deba@416
  1729
        _digraph->next(a);
deba@416
  1730
        a._forward = true;
deba@414
  1731
      }
deba@414
  1732
    }
deba@414
  1733
deba@414
  1734
    void first(Edge& e) const {
deba@414
  1735
      _digraph->first(e);
deba@414
  1736
    }
deba@414
  1737
deba@414
  1738
    void next(Edge& e) const {
deba@414
  1739
      _digraph->next(e);
deba@414
  1740
    }
deba@414
  1741
deba@414
  1742
    void firstOut(Arc& a, const Node& n) const {
deba@414
  1743
      _digraph->firstIn(a, n);
deba@414
  1744
      if( static_cast<const Edge&>(a) != INVALID ) {
deba@416
  1745
        a._forward = false;
deba@414
  1746
      } else {
deba@416
  1747
        _digraph->firstOut(a, n);
deba@416
  1748
        a._forward = true;
deba@414
  1749
      }
deba@414
  1750
    }
deba@414
  1751
    void nextOut(Arc &a) const {
deba@414
  1752
      if (!a._forward) {
deba@416
  1753
        Node n = _digraph->target(a);
deba@416
  1754
        _digraph->nextIn(a);
deba@416
  1755
        if (static_cast<const Edge&>(a) == INVALID ) {
deba@416
  1756
          _digraph->firstOut(a, n);
deba@416
  1757
          a._forward = true;
deba@416
  1758
        }
deba@414
  1759
      }
deba@414
  1760
      else {
deba@416
  1761
        _digraph->nextOut(a);
deba@414
  1762
      }
deba@414
  1763
    }
deba@414
  1764
deba@414
  1765
    void firstIn(Arc &a, const Node &n) const {
deba@414
  1766
      _digraph->firstOut(a, n);
deba@414
  1767
      if (static_cast<const Edge&>(a) != INVALID ) {
deba@416
  1768
        a._forward = false;
deba@414
  1769
      } else {
deba@416
  1770
        _digraph->firstIn(a, n);
deba@416
  1771
        a._forward = true;
deba@414
  1772
      }
deba@414
  1773
    }
deba@414
  1774
    void nextIn(Arc &a) const {
deba@414
  1775
      if (!a._forward) {
deba@416
  1776
        Node n = _digraph->source(a);
deba@416
  1777
        _digraph->nextOut(a);
deba@416
  1778
        if( static_cast<const Edge&>(a) == INVALID ) {
deba@416
  1779
          _digraph->firstIn(a, n);
deba@416
  1780
          a._forward = true;
deba@416
  1781
        }
deba@414
  1782
      }
deba@414
  1783
      else {
deba@416
  1784
        _digraph->nextIn(a);
deba@414
  1785
      }
deba@414
  1786
    }
deba@414
  1787
deba@414
  1788
    void firstInc(Edge &e, bool &d, const Node &n) const {
deba@414
  1789
      d = true;
deba@414
  1790
      _digraph->firstOut(e, n);
deba@414
  1791
      if (e != INVALID) return;
deba@414
  1792
      d = false;
deba@414
  1793
      _digraph->firstIn(e, n);
deba@414
  1794
    }
deba@414
  1795
deba@414
  1796
    void nextInc(Edge &e, bool &d) const {
deba@414
  1797
      if (d) {
deba@416
  1798
        Node s = _digraph->source(e);
deba@416
  1799
        _digraph->nextOut(e);
deba@416
  1800
        if (e != INVALID) return;
deba@416
  1801
        d = false;
deba@416
  1802
        _digraph->firstIn(e, s);
deba@414
  1803
      } else {
deba@416
  1804
        _digraph->nextIn(e);
deba@414
  1805
      }
deba@414
  1806
    }
deba@414
  1807
deba@414
  1808
    Node u(const Edge& e) const {
deba@414
  1809
      return _digraph->source(e);
deba@414
  1810
    }
deba@414
  1811
deba@414
  1812
    Node v(const Edge& e) const {
deba@414
  1813
      return _digraph->target(e);
deba@414
  1814
    }
deba@414
  1815
deba@414
  1816
    Node source(const Arc &a) const {
deba@414
  1817
      return a._forward ? _digraph->source(a) : _digraph->target(a);
deba@414
  1818
    }
deba@414
  1819
deba@414
  1820
    Node target(const Arc &a) const {
deba@414
  1821
      return a._forward ? _digraph->target(a) : _digraph->source(a);
deba@414
  1822
    }
deba@414
  1823
deba@414
  1824
    static Arc direct(const Edge &e, bool d) {
deba@414
  1825
      return Arc(e, d);
deba@414
  1826
    }
deba@414
  1827
    Arc direct(const Edge &e, const Node& n) const {
deba@414
  1828
      return Arc(e, _digraph->source(e) == n);
deba@414
  1829
    }
deba@414
  1830
deba@414
  1831
    static bool direction(const Arc &a) { return a._forward; }
deba@414
  1832
deba@414
  1833
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414
  1834
    Arc arcFromId(int ix) const {
deba@414
  1835
      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
deba@414
  1836
    }
deba@414
  1837
    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414
  1838
deba@414
  1839
    int id(const Node &n) const { return _digraph->id(n); }
deba@414
  1840
    int id(const Arc &a) const {
deba@414
  1841
      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
deba@414
  1842
    }
deba@414
  1843
    int id(const Edge &e) const { return _digraph->id(e); }
deba@414
  1844
deba@414
  1845
    int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414
  1846
    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
deba@414
  1847
    int maxEdgeId() const { return _digraph->maxArcId(); }
deba@414
  1848
deba@414
  1849
    Node addNode() { return _digraph->addNode(); }
deba@416
  1850
    Edge addEdge(const Node& u, const Node& v) {
deba@416
  1851
      return _digraph->addArc(u, v);
deba@414
  1852
    }
deba@414
  1853
deba@414
  1854
    void erase(const Node& i) { _digraph->erase(i); }
deba@414
  1855
    void erase(const Edge& i) { _digraph->erase(i); }
deba@416
  1856
deba@414
  1857
    void clear() { _digraph->clear(); }
deba@414
  1858
deba@414
  1859
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
deba@414
  1860
    int nodeNum() const { return 2 * _digraph->arcNum(); }
kpeter@446
  1861
kpeter@446
  1862
    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
deba@414
  1863
    int arcNum() const { return 2 * _digraph->arcNum(); }
kpeter@446
  1864
kpeter@446
  1865
    typedef ArcNumTag EdgeNumTag;
deba@414
  1866
    int edgeNum() const { return _digraph->arcNum(); }
deba@414
  1867
kpeter@446
  1868
    typedef FindArcTagIndicator<Digraph> FindArcTag;
deba@414
  1869
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
deba@414
  1870
      if (p == INVALID) {
deba@416
  1871
        Edge arc = _digraph->findArc(s, t);
deba@416
  1872
        if (arc != INVALID) return direct(arc, true);
deba@416
  1873
        arc = _digraph->findArc(t, s);
deba@416
  1874
        if (arc != INVALID) return direct(arc, false);
deba@414
  1875
      } else if (direction(p)) {
deba@416
  1876
        Edge arc = _digraph->findArc(s, t, p);
deba@416
  1877
        if (arc != INVALID) return direct(arc, true);
deba@416
  1878
        arc = _digraph->findArc(t, s);
deba@416
  1879
        if (arc != INVALID) return direct(arc, false);
deba@414
  1880
      } else {
deba@416
  1881
        Edge arc = _digraph->findArc(t, s, p);
deba@416
  1882
        if (arc != INVALID) return direct(arc, false);
deba@414
  1883
      }
deba@414
  1884
      return INVALID;
deba@414
  1885
    }
deba@414
  1886
kpeter@446
  1887
    typedef FindArcTag FindEdgeTag;
deba@414
  1888
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
deba@414
  1889
      if (s != t) {
deba@414
  1890
        if (p == INVALID) {
deba@414
  1891
          Edge arc = _digraph->findArc(s, t);
deba@414
  1892
          if (arc != INVALID) return arc;
deba@414
  1893
          arc = _digraph->findArc(t, s);
deba@414
  1894
          if (arc != INVALID) return arc;
deba@414
  1895
        } else if (_digraph->s(p) == s) {
deba@414
  1896
          Edge arc = _digraph->findArc(s, t, p);
deba@414
  1897
          if (arc != INVALID) return arc;
deba@414
  1898
          arc = _digraph->findArc(t, s);
deba@416
  1899
          if (arc != INVALID) return arc;
deba@414
  1900
        } else {
deba@414
  1901
          Edge arc = _digraph->findArc(t, s, p);
deba@416
  1902
          if (arc != INVALID) return arc;
deba@414
  1903
        }
deba@414
  1904
      } else {
deba@414
  1905
        return _digraph->findArc(s, t, p);
deba@414
  1906
      }
deba@414
  1907
      return INVALID;
deba@414
  1908
    }
deba@414
  1909
deba@414
  1910
  private:
deba@416
  1911
deba@414
  1912
    template <typename _Value>
deba@414
  1913
    class ArcMapBase {
deba@414
  1914
    private:
deba@416
  1915
deba@414
  1916
      typedef typename Digraph::template ArcMap<_Value> MapImpl;
deba@416
  1917
deba@414
  1918
    public:
deba@414
  1919
deba@414
  1920
      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@414
  1921
deba@414
  1922
      typedef _Value Value;
deba@414
  1923
      typedef Arc Key;
deba@416
  1924
deba@414
  1925
      ArcMapBase(const Adaptor& adaptor) :
deba@416
  1926
        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
deba@416
  1927
deba@416
  1928
      ArcMapBase(const Adaptor& adaptor, const Value& v)
deba@414
  1929
        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
deba@416
  1930
deba@416
  1931
      void set(const Arc& a, const Value& v) {
deba@416
  1932
        if (direction(a)) {
deba@416
  1933
          _forward.set(a, v);
deba@416
  1934
        } else {
deba@416
  1935
          _backward.set(a, v);
deba@414
  1936
        }
deba@414
  1937
      }
deba@414
  1938
deba@416
  1939
      typename MapTraits<MapImpl>::ConstReturnValue
deba@416
  1940
      operator[](const Arc& a) const {
deba@416
  1941
        if (direction(a)) {
deba@416
  1942
          return _forward[a];
deba@416
  1943
        } else {
deba@416
  1944
          return _backward[a];
deba@414
  1945
        }
deba@414
  1946
      }
deba@414
  1947
deba@416
  1948
      typename MapTraits<MapImpl>::ReturnValue
deba@416
  1949
      operator[](const Arc& a) {
deba@416
  1950
        if (direction(a)) {
deba@416
  1951
          return _forward[a];
deba@416
  1952
        } else {
deba@416
  1953
          return _backward[a];
deba@416
  1954
        }
deba@416
  1955
      }
deba@416
  1956
deba@414
  1957
    protected:
deba@414
  1958
deba@416
  1959
      MapImpl _forward, _backward;
deba@414
  1960
deba@414
  1961
    };
deba@414
  1962
deba@414
  1963
  public:
deba@414
  1964
deba@414
  1965
    template <typename _Value>
deba@414
  1966
    class NodeMap : public Digraph::template NodeMap<_Value> {
deba@414
  1967
    public:
deba@414
  1968
deba@414
  1969
      typedef _Value Value;
deba@414
  1970
      typedef typename Digraph::template NodeMap<Value> Parent;
deba@414
  1971
deba@416
  1972
      explicit NodeMap(const Adaptor& adaptor)
deba@416
  1973
        : Parent(*adaptor._digraph) {}
deba@414
  1974
deba@414
  1975
      NodeMap(const Adaptor& adaptor, const _Value& value)
deba@416
  1976
        : Parent(*adaptor._digraph, value) { }
deba@414
  1977
deba@414
  1978
    private:
deba@414
  1979
      NodeMap& operator=(const NodeMap& cmap) {
deba@414
  1980
        return operator=<NodeMap>(cmap);
deba@414
  1981
      }
deba@414
  1982
deba@414
  1983
      template <typename CMap>
deba@414
  1984
      NodeMap& operator=(const CMap& cmap) {
deba@414
  1985
        Parent::operator=(cmap);
deba@414
  1986
        return *this;
deba@414
  1987
      }
deba@416
  1988
deba@414
  1989
    };
deba@414
  1990
deba@414
  1991
    template <typename _Value>
deba@416
  1992
    class ArcMap
deba@416
  1993
      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
deba@414
  1994
    {
deba@414
  1995
    public:
deba@414
  1996
      typedef _Value Value;
deba@414
  1997
      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
deba@416
  1998
deba@416
  1999
      ArcMap(const Adaptor& adaptor)
deba@416
  2000
        : Parent(adaptor) {}
deba@416
  2001
deba@416
  2002
      ArcMap(const Adaptor& adaptor, const Value& value)
deba@416
  2003
        : Parent(adaptor, value) {}
deba@416
  2004
deba@414
  2005
    private:
deba@414
  2006
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  2007
        return operator=<ArcMap>(cmap);
deba@414
  2008
      }
deba@416
  2009
deba@414
  2010
      template <typename CMap>
deba@414
  2011
      ArcMap& operator=(const CMap& cmap) {
deba@414
  2012
        Parent::operator=(cmap);
deba@416
  2013
        return *this;
deba@414
  2014
      }
deba@414
  2015
    };
deba@416
  2016
deba@414
  2017
    template <typename _Value>
deba@414
  2018
    class EdgeMap : public Digraph::template ArcMap<_Value> {
deba@414
  2019
    public:
deba@416
  2020
deba@414
  2021
      typedef _Value Value;
deba@414
  2022
      typedef typename Digraph::template ArcMap<Value> Parent;
deba@416
  2023
deba@416
  2024
      explicit EdgeMap(const Adaptor& adaptor)
deba@416
  2025
        : Parent(*adaptor._digraph) {}
deba@414
  2026
deba@414
  2027
      EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416
  2028
        : Parent(*adaptor._digraph, value) {}
deba@414
  2029
deba@414
  2030
    private:
deba@414
  2031
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@414
  2032
        return operator=<EdgeMap>(cmap);
deba@414
  2033
      }
deba@414
  2034
deba@414
  2035
      template <typename CMap>
deba@414
  2036
      EdgeMap& operator=(const CMap& cmap) {
deba@414
  2037
        Parent::operator=(cmap);
deba@414
  2038
        return *this;
deba@414
  2039
      }
deba@414
  2040
deba@414
  2041
    };
deba@414
  2042
deba@414
  2043
    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
deba@416
  2044
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414
  2045
deba@414
  2046
  protected:
deba@414
  2047
deba@416
  2048
    UndirectorBase() : _digraph(0) {}
deba@414
  2049
deba@414
  2050
    Digraph* _digraph;
deba@414
  2051
deba@414
  2052
    void setDigraph(Digraph& digraph) {
deba@414
  2053
      _digraph = &digraph;
deba@414
  2054
    }
deba@416
  2055
deba@414
  2056
  };
deba@414
  2057
deba@416
  2058
  /// \ingroup graph_adaptors
deba@414
  2059
  ///
deba@416
  2060
  /// \brief Undirect the graph
deba@414
  2061
  ///
deba@414
  2062
  /// This adaptor makes an undirected graph from a directed
deba@416
  2063
  /// graph. All arcs of the underlying digraph will be showed in the
deba@416
  2064
  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
deba@416
  2065
  /// concepts::Graph "Graph concept".
deba@414
  2066
  ///
deba@416
  2067
  /// \tparam _Digraph It must be conform to the \ref
deba@416
  2068
  /// concepts::Digraph "Digraph concept". The type can be specified
deba@416
  2069
  /// to const.
deba@414
  2070
  template<typename _Digraph>
deba@416
  2071
  class Undirector
deba@416
  2072
    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
deba@414
  2073
  public:
deba@414
  2074
    typedef _Digraph Digraph;
deba@416
  2075
    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
deba@414
  2076
  protected:
deba@416
  2077
    Undirector() { }
deba@414
  2078
  public:
deba@414
  2079
deba@414
  2080
    /// \brief Constructor
deba@414
  2081
    ///
deba@416
  2082
    /// Creates a undirected graph from the given digraph
deba@416
  2083
    Undirector(_Digraph& digraph) {
deba@416
  2084
      setDigraph(digraph);
deba@414
  2085
    }
deba@414
  2086
deba@414
  2087
    /// \brief ArcMap combined from two original ArcMap
deba@414
  2088
    ///
deba@414
  2089
    /// This class adapts two original digraph ArcMap to
deba@416
  2090
    /// get an arc map on the undirected graph.
deba@414
  2091
    template <typename _ForwardMap, typename _BackwardMap>
deba@414
  2092
    class CombinedArcMap {
deba@414
  2093
    public:
deba@416
  2094
deba@414
  2095
      typedef _ForwardMap ForwardMap;
deba@414
  2096
      typedef _BackwardMap BackwardMap;
deba@414
  2097
deba@414
  2098
      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
deba@414
  2099
deba@414
  2100
      typedef typename ForwardMap::Value Value;
deba@414
  2101
      typedef typename Parent::Arc Key;
deba@414
  2102
deba@416
  2103
      /// \brief Constructor
deba@414
  2104
      ///
deba@416
  2105
      /// Constructor
deba@416
  2106
      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
deba@414
  2107
        : _forward(&forward), _backward(&backward) {}
deba@416
  2108
deba@414
  2109
deba@414
  2110
      /// \brief Sets the value associated with a key.
deba@414
  2111
      ///
deba@414
  2112
      /// Sets the value associated with a key.
deba@416
  2113
      void set(const Key& e, const Value& a) {
deba@416
  2114
        if (Parent::direction(e)) {
deba@416
  2115
          _forward->set(e, a);
deba@416
  2116
        } else {
deba@416
  2117
          _backward->set(e, a);
deba@416
  2118
        }
deba@414
  2119
      }
deba@414
  2120
deba@414
  2121
      /// \brief Returns the value associated with a key.
deba@414
  2122
      ///
deba@414
  2123
      /// Returns the value associated with a key.
deba@416
  2124
      typename MapTraits<ForwardMap>::ConstReturnValue
deba@416
  2125
      operator[](const Key& e) const {
deba@416
  2126
        if (Parent::direction(e)) {
deba@416
  2127
          return (*_forward)[e];
deba@416
  2128
        } else {
deba@416
  2129
          return (*_backward)[e];
deba@414
  2130
        }
deba@414
  2131
      }
deba@414
  2132
deba@414
  2133
      /// \brief Returns the value associated with a key.
deba@414
  2134
      ///
deba@414
  2135
      /// Returns the value associated with a key.
deba@416
  2136
      typename MapTraits<ForwardMap>::ReturnValue
deba@416
  2137
      operator[](const Key& e) {
deba@416
  2138
        if (Parent::direction(e)) {
deba@416
  2139
          return (*_forward)[e];
deba@416
  2140
        } else {
deba@416
  2141
          return (*_backward)[e];
deba@414
  2142
        }
deba@414
  2143
      }
deba@414
  2144
deba@416
  2145
    protected:
deba@416
  2146
deba@416
  2147
      ForwardMap* _forward;
deba@416
  2148
      BackwardMap* _backward;
deba@416
  2149
deba@416
  2150
    };
deba@416
  2151
deba@416
  2152
    /// \brief Just gives back a combined arc map
deba@416
  2153
    ///
deba@416
  2154
    /// Just gives back a combined arc map
deba@416
  2155
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2156
    static CombinedArcMap<ForwardMap, BackwardMap>
deba@416
  2157
    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
deba@416
  2158
      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
deba@416
  2159
    }
deba@416
  2160
deba@416
  2161
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2162
    static CombinedArcMap<const ForwardMap, BackwardMap>
deba@416
  2163
    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
deba@416
  2164
      return CombinedArcMap<const ForwardMap,
deba@416
  2165
        BackwardMap>(forward, backward);
deba@416
  2166
    }
deba@416
  2167
deba@416
  2168
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2169
    static CombinedArcMap<ForwardMap, const BackwardMap>
deba@416
  2170
    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
deba@416
  2171
      return CombinedArcMap<ForwardMap,
deba@416
  2172
        const BackwardMap>(forward, backward);
deba@416
  2173
    }
deba@416
  2174
deba@416
  2175
    template <typename ForwardMap, typename BackwardMap>
deba@416
  2176
    static CombinedArcMap<const ForwardMap, const BackwardMap>
deba@416
  2177
    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
deba@416
  2178
      return CombinedArcMap<const ForwardMap,
deba@416
  2179
        const BackwardMap>(forward, backward);
deba@416
  2180
    }
deba@416
  2181
deba@416
  2182
  };
deba@416
  2183
deba@416
  2184
  /// \brief Just gives back an undirected view of the given digraph
deba@416
  2185
  ///
deba@416
  2186
  /// Just gives back an undirected view of the given digraph
deba@416
  2187
  template<typename Digraph>
deba@416
  2188
  Undirector<const Digraph>
deba@416
  2189
  undirector(const Digraph& digraph) {
deba@416
  2190
    return Undirector<const Digraph>(digraph);
deba@416
  2191
  }
deba@416
  2192
deba@416
  2193
  template <typename _Graph, typename _DirectionMap>
deba@416
  2194
  class OrienterBase {
deba@416
  2195
  public:
deba@416
  2196
deba@416
  2197
    typedef _Graph Graph;
deba@416
  2198
    typedef _DirectionMap DirectionMap;
deba@416
  2199
deba@416
  2200
    typedef typename Graph::Node Node;
deba@416
  2201
    typedef typename Graph::Edge Arc;
deba@416
  2202
deba@416
  2203
    void reverseArc(const Arc& arc) {
deba@416
  2204
      _direction->set(arc, !(*_direction)[arc]);
deba@416
  2205
    }
deba@416
  2206
deba@416
  2207
    void first(Node& i) const { _graph->first(i); }
deba@416
  2208
    void first(Arc& i) const { _graph->first(i); }
deba@416
  2209
    void firstIn(Arc& i, const Node& n) const {
kpeter@447
  2210
      bool d = true;
deba@416
  2211
      _graph->firstInc(i, d, n);
deba@416
  2212
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2213
    }
deba@416
  2214
    void firstOut(Arc& i, const Node& n ) const {
kpeter@447
  2215
      bool d = true;
deba@416
  2216
      _graph->firstInc(i, d, n);
deba@416
  2217
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2218
    }
deba@416
  2219
deba@416
  2220
    void next(Node& i) const { _graph->next(i); }
deba@416
  2221
    void next(Arc& i) const { _graph->next(i); }
deba@416
  2222
    void nextIn(Arc& i) const {
deba@416
  2223
      bool d = !(*_direction)[i];
deba@416
  2224
      _graph->nextInc(i, d);
deba@416
  2225
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2226
    }
deba@416
  2227
    void nextOut(Arc& i) const {
deba@416
  2228
      bool d = (*_direction)[i];
deba@416
  2229
      _graph->nextInc(i, d);
deba@416
  2230
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416
  2231
    }
deba@416
  2232
deba@416
  2233
    Node source(const Arc& e) const {
deba@416
  2234
      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
deba@416
  2235
    }
deba@416
  2236
    Node target(const Arc& e) const {
deba@416
  2237
      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
deba@416
  2238
    }
deba@416
  2239
deba@416
  2240
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416
  2241
    int nodeNum() const { return _graph->nodeNum(); }
deba@416
  2242
kpeter@446
  2243
    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
deba@416
  2244
    int arcNum() const { return _graph->edgeNum(); }
deba@416
  2245
kpeter@446
  2246
    typedef FindEdgeTagIndicator<Graph> FindArcTag;
deba@416
  2247
    Arc findArc(const Node& u, const Node& v,
kpeter@448
  2248
                const Arc& prev = INVALID) const {
deba@416
  2249
      Arc arc = prev;
deba@416
  2250
      bool d = arc == INVALID ? true : (*_direction)[arc];
deba@416
  2251
      if (d) {
deba@416
  2252
        arc = _graph->findEdge(u, v, arc);
deba@416
  2253
        while (arc != INVALID && !(*_direction)[arc]) {
deba@416
  2254
          _graph->findEdge(u, v, arc);
deba@416
  2255
        }
deba@416
  2256
        if (arc != INVALID) return arc;
deba@414
  2257
      }
deba@416
  2258
      _graph->findEdge(v, u, arc);
deba@416
  2259
      while (arc != INVALID && (*_direction)[arc]) {
deba@416
  2260
        _graph->findEdge(u, v, arc);
deba@414
  2261
      }
deba@416
  2262
      return arc;
deba@416
  2263
    }
deba@416
  2264
deba@416
  2265
    Node addNode() {
deba@416
  2266
      return Node(_graph->addNode());
deba@416
  2267
    }
deba@416
  2268
deba@416
  2269
    Arc addArc(const Node& u, const Node& v) {
deba@416
  2270
      Arc arc = _graph->addArc(u, v);
deba@416
  2271
      _direction->set(arc, _graph->source(arc) == u);
deba@416
  2272
      return arc;
deba@416
  2273
    }
deba@416
  2274
deba@416
  2275
    void erase(const Node& i) { _graph->erase(i); }
deba@416
  2276
    void erase(const Arc& i) { _graph->erase(i); }
deba@416
  2277
deba@416
  2278
    void clear() { _graph->clear(); }
deba@416
  2279
deba@416
  2280
    int id(const Node& v) const { return _graph->id(v); }
deba@416
  2281
    int id(const Arc& e) const { return _graph->id(e); }
deba@416
  2282
deba@416
  2283
    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@416
  2284
    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@416
  2285
deba@416
  2286
    int maxNodeId() const { return _graph->maxNodeId(); }
deba@416
  2287
    int maxArcId() const { return _graph->maxEdgeId(); }
deba@416
  2288
deba@416
  2289
    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@416
  2290
    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416
  2291
deba@416
  2292
    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@416
  2293
    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416
  2294
deba@416
  2295
    template <typename _Value>
deba@416
  2296
    class NodeMap : public _Graph::template NodeMap<_Value> {
deba@416
  2297
    public:
deba@416
  2298
deba@416
  2299
      typedef typename _Graph::template NodeMap<_Value> Parent;
deba@416
  2300
deba@416
  2301
      explicit NodeMap(const OrienterBase& adapter)
deba@416
  2302
        : Parent(*adapter._graph) {}
deba@416
  2303
deba@416
  2304
      NodeMap(const OrienterBase& adapter, const _Value& value)
deba@416
  2305
        : Parent(*adapter._graph, value) {}
deba@416
  2306
deba@416
  2307
    private:
deba@416
  2308
      NodeMap& operator=(const NodeMap& cmap) {
deba@416
  2309
        return operator=<NodeMap>(cmap);
deba@416
  2310
      }
deba@416
  2311
deba@416
  2312
      template <typename CMap>
deba@416
  2313
      NodeMap& operator=(const CMap& cmap) {
deba@416
  2314
        Parent::operator=(cmap);
deba@416
  2315
        return *this;
deba@416
  2316
      }
deba@414
  2317
deba@414
  2318
    };
deba@414
  2319
deba@416
  2320
    template <typename _Value>
deba@416
  2321
    class ArcMap : public _Graph::template EdgeMap<_Value> {
deba@416
  2322
    public:
deba@416
  2323
deba@416
  2324
      typedef typename Graph::template EdgeMap<_Value> Parent;
deba@416
  2325
deba@416
  2326
      explicit ArcMap(const OrienterBase& adapter)
deba@416
  2327
        : Parent(*adapter._graph) { }
deba@416
  2328
deba@416
  2329
      ArcMap(const OrienterBase& adapter, const _Value& value)
deba@416
  2330
        : Parent(*adapter._graph, value) { }
deba@416
  2331
deba@416
  2332
    private:
deba@416
  2333
      ArcMap& operator=(const ArcMap& cmap) {
deba@416
  2334
        return operator=<ArcMap>(cmap);
deba@416
  2335
      }
deba@416
  2336
deba@416
  2337
      template <typename CMap>
deba@416
  2338
      ArcMap& operator=(const CMap& cmap) {
deba@416
  2339
        Parent::operator=(cmap);
deba@416
  2340
        return *this;
deba@416
  2341
      }
deba@416
  2342
    };
deba@416
  2343
deba@416
  2344
deba@416
  2345
deba@416
  2346
  protected:
deba@416
  2347
    Graph* _graph;
deba@416
  2348
    DirectionMap* _direction;
deba@416
  2349
deba@416
  2350
    void setDirectionMap(DirectionMap& direction) {
deba@416
  2351
      _direction = &direction;
deba@416
  2352
    }
deba@416
  2353
deba@416
  2354
    void setGraph(Graph& graph) {
deba@416
  2355
      _graph = &graph;
deba@416
  2356
    }
deba@416
  2357
deba@414
  2358
  };
deba@414
  2359
deba@416
  2360
  /// \ingroup graph_adaptors
deba@414
  2361
  ///
deba@416
  2362
  /// \brief Orients the edges of the graph to get a digraph
deba@416
  2363
  ///
deba@416
  2364
  /// This adaptor orients each edge in the undirected graph. The
deba@416
  2365
  /// direction of the arcs stored in an edge node map.  The arcs can
deba@416
  2366
  /// be easily reverted by the \c reverseArc() member function in the
deba@416
  2367
  /// adaptor. The Orienter adaptor is conform to the \ref
deba@416
  2368
  /// concepts::Digraph "Digraph concept".
deba@416
  2369
  ///
deba@416
  2370
  /// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416
  2371
  /// "Graph concept". The type can be specified to be const.
deba@416
  2372
  /// \tparam _DirectionMap A bool valued edge map of the the adapted
deba@416
  2373
  /// graph.
deba@416
  2374
  ///
deba@416
  2375
  /// \sa orienter
deba@416
  2376
  template<typename _Graph,
deba@416
  2377
           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
deba@416
  2378
  class Orienter :
deba@416
  2379
    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
deba@416
  2380
  public:
deba@416
  2381
    typedef _Graph Graph;
deba@416
  2382
    typedef DigraphAdaptorExtender<
deba@416
  2383
      OrienterBase<_Graph, DirectionMap> > Parent;
deba@416
  2384
    typedef typename Parent::Arc Arc;
deba@416
  2385
  protected:
deba@416
  2386
    Orienter() { }
deba@416
  2387
  public:
deba@416
  2388
deba@416
  2389
    /// \brief Constructor of the adaptor
deba@416
  2390
    ///
deba@416
  2391
    /// Constructor of the adaptor
deba@416
  2392
    Orienter(Graph& graph, DirectionMap& direction) {
deba@416
  2393
      setGraph(graph);
deba@416
  2394
      setDirectionMap(direction);
deba@416
  2395
    }
deba@416
  2396
deba@416
  2397
    /// \brief Reverse arc
deba@416
  2398
    ///
deba@416
  2399
    /// It reverse the given arc. It simply negate the direction in the map.
deba@416
  2400
    void reverseArc(const Arc& a) {
deba@416
  2401
      Parent::reverseArc(a);
deba@416
  2402
    }
deba@416
  2403
  };
deba@416
  2404
deba@416
  2405
  /// \brief Just gives back a Orienter
deba@416
  2406
  ///
deba@416
  2407
  /// Just gives back a Orienter
deba@416
  2408
  template<typename Graph, typename DirectionMap>
deba@416
  2409
  Orienter<const Graph, DirectionMap>
deba@416
  2410
  orienter(const Graph& graph, DirectionMap& dm) {
deba@416
  2411
    return Orienter<const Graph, DirectionMap>(graph, dm);
deba@414
  2412
  }
deba@414
  2413
deba@416
  2414
  template<typename Graph, typename DirectionMap>
deba@416
  2415
  Orienter<const Graph, const DirectionMap>
deba@416
  2416
  orienter(const Graph& graph, const DirectionMap& dm) {
deba@416
  2417
    return Orienter<const Graph, const DirectionMap>(graph, dm);
deba@416
  2418
  }
deba@416
  2419
deba@416
  2420
  namespace _adaptor_bits {
deba@416
  2421
deba@416
  2422
    template<typename _Digraph,
deba@416
  2423
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2424
             typename _FlowMap = _CapacityMap,
deba@416
  2425
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2426
    class ResForwardFilter {
deba@416
  2427
    public:
deba@416
  2428
deba@416
  2429
      typedef _Digraph Digraph;
deba@416
  2430
      typedef _CapacityMap CapacityMap;
deba@416
  2431
      typedef _FlowMap FlowMap;
deba@416
  2432
      typedef _Tolerance Tolerance;
deba@416
  2433
deba@416
  2434
      typedef typename Digraph::Arc Key;
deba@416
  2435
      typedef bool Value;
deba@416
  2436
deba@416
  2437
    private:
deba@416
  2438
deba@416
  2439
      const CapacityMap* _capacity;
deba@416
  2440
      const FlowMap* _flow;
deba@416
  2441
      Tolerance _tolerance;
deba@416
  2442
    public:
deba@416
  2443
deba@416
  2444
      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416
  2445
                       const Tolerance& tolerance = Tolerance())
deba@416
  2446
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416
  2447
deba@416
  2448
      bool operator[](const typename Digraph::Arc& a) const {
deba@416
  2449
        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
deba@416
  2450
      }
deba@416
  2451
    };
deba@416
  2452
deba@416
  2453
    template<typename _Digraph,
deba@416
  2454
             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2455
             typename _FlowMap = _CapacityMap,
deba@416
  2456
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2457
    class ResBackwardFilter {
deba@416
  2458
    public:
deba@416
  2459
deba@416
  2460
      typedef _Digraph Digraph;
deba@416
  2461
      typedef _CapacityMap CapacityMap;
deba@416
  2462
      typedef _FlowMap FlowMap;
deba@416
  2463
      typedef _Tolerance Tolerance;
deba@416
  2464
deba@416
  2465
      typedef typename Digraph::Arc Key;
deba@416
  2466
      typedef bool Value;
deba@416
  2467
deba@416
  2468
    private:
deba@416
  2469
deba@416
  2470
      const CapacityMap* _capacity;
deba@416
  2471
      const FlowMap* _flow;
deba@416
  2472
      Tolerance _tolerance;
deba@416
  2473
deba@416
  2474
    public:
deba@416
  2475
deba@416
  2476
      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416
  2477
                        const Tolerance& tolerance = Tolerance())
deba@416
  2478
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416
  2479
deba@416
  2480
      bool operator[](const typename Digraph::Arc& a) const {
deba@416
  2481
        return _tolerance.positive((*_flow)[a]);
deba@416
  2482
      }
deba@416
  2483
    };
deba@416
  2484
deba@416
  2485
  }
deba@416
  2486
deba@416
  2487
  /// \ingroup graph_adaptors
deba@416
  2488
  ///
deba@416
  2489
  /// \brief An adaptor for composing the residual graph for directed
deba@416
  2490
  /// flow and circulation problems.
deba@416
  2491
  ///
deba@416
  2492
  /// An adaptor for composing the residual graph for directed flow and
deba@416
  2493
  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
deba@416
  2494
  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@416
  2495
  /// be functions on the arc-set.
deba@416
  2496
  ///
deba@416
  2497
  /// Then Residual implements the digraph structure with
deba@416
  2498
  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
deba@416
  2499
  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
deba@416
  2500
  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
deba@416
  2501
  /// called residual graph.  When we take the union
deba@416
  2502
  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
deba@416
  2503
  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
deba@416
  2504
  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
deba@416
  2505
  /// orientation.
deba@416
  2506
  ///
deba@416
  2507
  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416
  2508
  /// "Digraph concept". The type is implicitly const.
deba@416
  2509
  /// \tparam _CapacityMap An arc map of some numeric type, it defines
deba@416
  2510
  /// the capacities in the flow problem. The map is implicitly const.
deba@416
  2511
  /// \tparam _FlowMap An arc map of some numeric type, it defines
deba@416
  2512
  /// the capacities in the flow problem.
deba@416
  2513
  /// \tparam _Tolerance Handler for inexact computation.
deba@416
  2514
  template<typename _Digraph,
deba@416
  2515
           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416
  2516
           typename _FlowMap = _CapacityMap,
deba@414
  2517
           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416
  2518
  class Residual :
deba@416
  2519
    public FilterArcs<
deba@416
  2520
    Undirector<const _Digraph>,
deba@416
  2521
    typename Undirector<const _Digraph>::template CombinedArcMap<
deba@416
  2522
      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
deba@416
  2523
                                      _FlowMap, _Tolerance>,
deba@416
  2524
      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
deba@416
  2525
                                       _FlowMap, _Tolerance> > >
deba@416
  2526
  {
deba@414
  2527
  public:
deba@414
  2528
deba@414
  2529
    typedef _Digraph Digraph;
deba@414
  2530
    typedef _CapacityMap CapacityMap;
deba@414
  2531
    typedef _FlowMap FlowMap;
deba@414
  2532
    typedef _Tolerance Tolerance;
deba@414
  2533
deba@414
  2534
    typedef typename CapacityMap::Value Value;
deba@416
  2535
    typedef Residual Adaptor;
deba@414
  2536
deba@414
  2537
  protected:
deba@414
  2538
deba@416
  2539
    typedef Undirector<const Digraph> Undirected;
deba@416
  2540
deba@416
  2541
    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
deba@416
  2542
                                            FlowMap, Tolerance> ForwardFilter;
deba@416
  2543
deba@416
  2544
    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
deba@416
  2545
                                             FlowMap, Tolerance> BackwardFilter;
deba@416
  2546
deba@416
  2547
    typedef typename Undirected::
deba@414
  2548
    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
deba@414
  2549
deba@416
  2550
    typedef FilterArcs<Undirected, ArcFilter> Parent;
deba@414
  2551
deba@414
  2552
    const CapacityMap* _capacity;
deba@414
  2553
    FlowMap* _flow;
deba@414
  2554
deba@416
  2555
    Undirected _graph;
deba@414
  2556
    ForwardFilter _forward_filter;
deba@414
  2557
    BackwardFilter _backward_filter;
deba@414
  2558
    ArcFilter _arc_filter;
deba@414
  2559
deba@414
  2560
  public:
deba@414
  2561
deba@414
  2562
    /// \brief Constructor of the residual digraph.
deba@414
  2563
    ///
deba@416
  2564
    /// Constructor of the residual graph. The parameters are the digraph,
deba@414
  2565
    /// the flow map, the capacity map and a tolerance object.
deba@416
  2566
    Residual(const Digraph& digraph, const CapacityMap& capacity,
deba@416
  2567
             FlowMap& flow, const Tolerance& tolerance = Tolerance())
deba@414
  2568
      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
deba@416
  2569
        _forward_filter(capacity, flow, tolerance),
deba@414
  2570
        _backward_filter(capacity, flow, tolerance),
deba@414
  2571
        _arc_filter(_forward_filter, _backward_filter)
deba@414
  2572
    {
deba@414
  2573
      Parent::setDigraph(_graph);
deba@414
  2574
      Parent::setArcFilterMap(_arc_filter);
deba@414
  2575
    }
deba@414
  2576
deba@414
  2577
    typedef typename Parent::Arc Arc;
deba@414
  2578
deba@414
  2579
    /// \brief Gives back the residual capacity of the arc.
deba@414
  2580
    ///
deba@414
  2581
    /// Gives back the residual capacity of the arc.
deba@416
  2582
    Value residualCapacity(const Arc& a) const {
deba@416
  2583
      if (Undirected::direction(a)) {
deba@416
  2584
        return (*_capacity)[a] - (*_flow)[a];
deba@414
  2585
      } else {
deba@416
  2586
        return (*_flow)[a];
deba@414
  2587
      }
deba@416
  2588
    }
deba@416
  2589
deba@416
  2590
    /// \brief Augment on the given arc in the residual graph.
deba@414
  2591
    ///
deba@416
  2592
    /// Augment on the given arc in the residual graph. It increase
deba@414
  2593
    /// or decrease the flow on the original arc depend on the direction
deba@414
  2594
    /// of the residual arc.
deba@416
  2595
    void augment(const Arc& a, const Value& v) const {
deba@416
  2596
      if (Undirected::direction(a)) {
deba@416
  2597
        _flow->set(a, (*_flow)[a] + v);
deba@416
  2598
      } else {
deba@416
  2599
        _flow->set(a, (*_flow)[a] - v);
deba@414
  2600
      }
deba@414
  2601
    }
deba@414
  2602
deba@414
  2603
    /// \brief Returns the direction of the arc.
deba@414
  2604
    ///
deba@414
  2605
    /// Returns true when the arc is same oriented as the original arc.
deba@416
  2606
    static bool forward(const Arc& a) {
deba@416
  2607
      return Undirected::direction(a);
deba@414
  2608
    }
deba@414
  2609
deba@414
  2610
    /// \brief Returns the direction of the arc.
deba@414
  2611
    ///
deba@414
  2612
    /// Returns true when the arc is opposite oriented as the original arc.
deba@416
  2613
    static bool backward(const Arc& a) {
deba@416
  2614
      return !Undirected::direction(a);
deba@414
  2615
    }
deba@414
  2616
deba@414
  2617
    /// \brief Gives back the forward oriented residual arc.
deba@414
  2618
    ///
deba@414
  2619
    /// Gives back the forward oriented residual arc.
deba@416
  2620
    static Arc forward(const typename Digraph::Arc& a) {
deba@416
  2621
      return Undirected::direct(a, true);
deba@414
  2622
    }
deba@414
  2623
deba@414
  2624
    /// \brief Gives back the backward oriented residual arc.
deba@414
  2625
    ///
deba@414
  2626
    /// Gives back the backward oriented residual arc.
deba@416
  2627
    static Arc backward(const typename Digraph::Arc& a) {
deba@416
  2628
      return Undirected::direct(a, false);
deba@414
  2629
    }
deba@414
  2630
deba@414
  2631
    /// \brief Residual capacity map.