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