lemon/bits/graph_extender.h
author Balazs Dezso <deba@inf.elte.hu>
Mon, 21 Jul 2008 16:30:28 +0200
changeset 228 b6732e0d38c5
parent 209 765619b7cbb2
child 263 be8a861d3bb7
permissions -rw-r--r--
Reworking graph testing

- The graph tests check more graph functionality.
- The petersen graph is too regular, therefore special graphs are used.
- The graph_test.h contains just general tools to test graphs.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@57
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@57
     4
 *
alpar@107
     5
 * Copyright (C) 2003-2008
deba@57
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@57
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@57
     8
 *
deba@57
     9
 * Permission to use, modify and distribute this software is granted
deba@57
    10
 * provided that this copyright notice appears in all copies. For
deba@57
    11
 * precise terms see the accompanying LICENSE file.
deba@57
    12
 *
deba@57
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@57
    14
 * express or implied, and with no claim as to its suitability for any
deba@57
    15
 * purpose.
deba@57
    16
 *
deba@57
    17
 */
deba@57
    18
deba@57
    19
#ifndef LEMON_BITS_GRAPH_EXTENDER_H
deba@57
    20
#define LEMON_BITS_GRAPH_EXTENDER_H
deba@57
    21
deba@220
    22
#include <lemon/core.h>
deba@57
    23
deba@57
    24
#include <lemon/bits/map_extender.h>
deba@57
    25
#include <lemon/bits/default_map.h>
deba@57
    26
deba@57
    27
#include <lemon/concept_check.h>
deba@57
    28
#include <lemon/concepts/maps.h>
deba@57
    29
deba@57
    30
///\ingroup graphbits
deba@57
    31
///\file
deba@57
    32
///\brief Extenders for the digraph types
deba@57
    33
namespace lemon {
deba@57
    34
deba@57
    35
  /// \ingroup graphbits
deba@57
    36
  ///
deba@57
    37
  /// \brief Extender for the Digraphs
deba@57
    38
  template <typename Base>
deba@57
    39
  class DigraphExtender : public Base {
deba@57
    40
  public:
deba@57
    41
deba@57
    42
    typedef Base Parent;
deba@57
    43
    typedef DigraphExtender Digraph;
deba@57
    44
deba@57
    45
    // Base extensions
deba@57
    46
deba@57
    47
    typedef typename Parent::Node Node;
deba@57
    48
    typedef typename Parent::Arc Arc;
deba@57
    49
deba@57
    50
    int maxId(Node) const {
deba@57
    51
      return Parent::maxNodeId();
deba@57
    52
    }
deba@57
    53
deba@57
    54
    int maxId(Arc) const {
deba@57
    55
      return Parent::maxArcId();
deba@57
    56
    }
deba@57
    57
deba@57
    58
    Node fromId(int id, Node) const {
deba@57
    59
      return Parent::nodeFromId(id);
deba@57
    60
    }
deba@57
    61
deba@57
    62
    Arc fromId(int id, Arc) const {
deba@57
    63
      return Parent::arcFromId(id);
deba@57
    64
    }
deba@57
    65
deba@78
    66
    Node oppositeNode(const Node &node, const Arc &arc) const {
deba@78
    67
      if (node == Parent::source(arc))
alpar@209
    68
        return Parent::target(arc);
deba@78
    69
      else if(node == Parent::target(arc))
alpar@209
    70
        return Parent::source(arc);
deba@57
    71
      else
alpar@209
    72
        return INVALID;
deba@57
    73
    }
deba@57
    74
deba@57
    75
    // Alterable extension
deba@57
    76
deba@57
    77
    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
deba@57
    78
    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
deba@57
    79
deba@57
    80
deba@57
    81
  protected:
deba@57
    82
deba@57
    83
    mutable NodeNotifier node_notifier;
deba@57
    84
    mutable ArcNotifier arc_notifier;
deba@57
    85
deba@57
    86
  public:
deba@57
    87
deba@57
    88
    NodeNotifier& notifier(Node) const {
deba@57
    89
      return node_notifier;
deba@57
    90
    }
alpar@209
    91
deba@57
    92
    ArcNotifier& notifier(Arc) const {
deba@57
    93
      return arc_notifier;
deba@57
    94
    }
deba@57
    95
alpar@209
    96
    class NodeIt : public Node {
deba@78
    97
      const Digraph* _digraph;
deba@57
    98
    public:
deba@57
    99
deba@57
   100
      NodeIt() {}
deba@57
   101
deba@57
   102
      NodeIt(Invalid i) : Node(i) { }
deba@57
   103
deba@78
   104
      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
alpar@209
   105
        _digraph->first(static_cast<Node&>(*this));
deba@57
   106
      }
deba@57
   107
alpar@209
   108
      NodeIt(const Digraph& digraph, const Node& node)
alpar@209
   109
        : Node(node), _digraph(&digraph) {}
deba@57
   110
alpar@209
   111
      NodeIt& operator++() {
alpar@209
   112
        _digraph->next(*this);
alpar@209
   113
        return *this;
deba@57
   114
      }
deba@57
   115
deba@57
   116
    };
deba@57
   117
deba@57
   118
alpar@209
   119
    class ArcIt : public Arc {
deba@78
   120
      const Digraph* _digraph;
deba@57
   121
    public:
deba@57
   122
deba@57
   123
      ArcIt() { }
deba@57
   124
deba@57
   125
      ArcIt(Invalid i) : Arc(i) { }
deba@57
   126
deba@78
   127
      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
alpar@209
   128
        _digraph->first(static_cast<Arc&>(*this));
deba@57
   129
      }
deba@57
   130
alpar@209
   131
      ArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209
   132
        Arc(arc), _digraph(&digraph) { }
deba@57
   133
alpar@209
   134
      ArcIt& operator++() {
alpar@209
   135
        _digraph->next(*this);
alpar@209
   136
        return *this;
deba@57
   137
      }
deba@57
   138
deba@57
   139
    };
deba@57
   140
deba@57
   141
alpar@209
   142
    class OutArcIt : public Arc {
deba@78
   143
      const Digraph* _digraph;
deba@57
   144
    public:
deba@57
   145
deba@57
   146
      OutArcIt() { }
deba@57
   147
deba@57
   148
      OutArcIt(Invalid i) : Arc(i) { }
deba@57
   149
alpar@209
   150
      OutArcIt(const Digraph& digraph, const Node& node)
alpar@209
   151
        : _digraph(&digraph) {
alpar@209
   152
        _digraph->firstOut(*this, node);
deba@57
   153
      }
deba@57
   154
alpar@209
   155
      OutArcIt(const Digraph& digraph, const Arc& arc)
alpar@209
   156
        : Arc(arc), _digraph(&digraph) {}
deba@57
   157
alpar@209
   158
      OutArcIt& operator++() {
alpar@209
   159
        _digraph->nextOut(*this);
alpar@209
   160
        return *this;
deba@57
   161
      }
deba@57
   162
deba@57
   163
    };
deba@57
   164
deba@57
   165
alpar@209
   166
    class InArcIt : public Arc {
deba@78
   167
      const Digraph* _digraph;
deba@57
   168
    public:
deba@57
   169
deba@57
   170
      InArcIt() { }
deba@57
   171
deba@57
   172
      InArcIt(Invalid i) : Arc(i) { }
deba@57
   173
alpar@209
   174
      InArcIt(const Digraph& digraph, const Node& node)
alpar@209
   175
        : _digraph(&digraph) {
alpar@209
   176
        _digraph->firstIn(*this, node);
deba@57
   177
      }
deba@57
   178
alpar@209
   179
      InArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209
   180
        Arc(arc), _digraph(&digraph) {}
deba@57
   181
alpar@209
   182
      InArcIt& operator++() {
alpar@209
   183
        _digraph->nextIn(*this);
alpar@209
   184
        return *this;
deba@57
   185
      }
deba@57
   186
deba@57
   187
    };
deba@57
   188
deba@57
   189
    /// \brief Base node of the iterator
deba@57
   190
    ///
deba@57
   191
    /// Returns the base node (i.e. the source in this case) of the iterator
deba@78
   192
    Node baseNode(const OutArcIt &arc) const {
deba@78
   193
      return Parent::source(arc);
deba@57
   194
    }
deba@57
   195
    /// \brief Running node of the iterator
deba@57
   196
    ///
deba@57
   197
    /// Returns the running node (i.e. the target in this case) of the
deba@57
   198
    /// iterator
deba@78
   199
    Node runningNode(const OutArcIt &arc) const {
deba@78
   200
      return Parent::target(arc);
deba@57
   201
    }
deba@57
   202
deba@57
   203
    /// \brief Base node of the iterator
deba@57
   204
    ///
deba@57
   205
    /// Returns the base node (i.e. the target in this case) of the iterator
deba@78
   206
    Node baseNode(const InArcIt &arc) const {
deba@78
   207
      return Parent::target(arc);
deba@57
   208
    }
deba@57
   209
    /// \brief Running node of the iterator
deba@57
   210
    ///
deba@57
   211
    /// Returns the running node (i.e. the source in this case) of the
deba@57
   212
    /// iterator
deba@78
   213
    Node runningNode(const InArcIt &arc) const {
deba@78
   214
      return Parent::source(arc);
deba@57
   215
    }
deba@57
   216
alpar@209
   217
deba@57
   218
    template <typename _Value>
alpar@209
   219
    class NodeMap
deba@57
   220
      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
deba@57
   221
    public:
deba@57
   222
      typedef DigraphExtender Digraph;
deba@57
   223
      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57
   224
alpar@209
   225
      explicit NodeMap(const Digraph& digraph)
alpar@209
   226
        : Parent(digraph) {}
alpar@209
   227
      NodeMap(const Digraph& digraph, const _Value& value)
alpar@209
   228
        : Parent(digraph, value) {}
deba@57
   229
deba@57
   230
      NodeMap& operator=(const NodeMap& cmap) {
alpar@209
   231
        return operator=<NodeMap>(cmap);
deba@57
   232
      }
deba@57
   233
deba@57
   234
      template <typename CMap>
deba@57
   235
      NodeMap& operator=(const CMap& cmap) {
deba@57
   236
        Parent::operator=(cmap);
alpar@209
   237
        return *this;
deba@57
   238
      }
deba@57
   239
deba@57
   240
    };
deba@57
   241
deba@57
   242
    template <typename _Value>
alpar@209
   243
    class ArcMap
deba@57
   244
      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
deba@57
   245
    public:
deba@57
   246
      typedef DigraphExtender Digraph;
deba@57
   247
      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57
   248
alpar@209
   249
      explicit ArcMap(const Digraph& digraph)
alpar@209
   250
        : Parent(digraph) {}
alpar@209
   251
      ArcMap(const Digraph& digraph, const _Value& value)
alpar@209
   252
        : Parent(digraph, value) {}
deba@57
   253
deba@57
   254
      ArcMap& operator=(const ArcMap& cmap) {
alpar@209
   255
        return operator=<ArcMap>(cmap);
deba@57
   256
      }
deba@57
   257
deba@57
   258
      template <typename CMap>
deba@57
   259
      ArcMap& operator=(const CMap& cmap) {
deba@57
   260
        Parent::operator=(cmap);
alpar@209
   261
        return *this;
deba@57
   262
      }
deba@57
   263
    };
deba@57
   264
deba@57
   265
deba@57
   266
    Node addNode() {
deba@57
   267
      Node node = Parent::addNode();
deba@57
   268
      notifier(Node()).add(node);
deba@57
   269
      return node;
deba@57
   270
    }
alpar@209
   271
deba@57
   272
    Arc addArc(const Node& from, const Node& to) {
deba@57
   273
      Arc arc = Parent::addArc(from, to);
deba@57
   274
      notifier(Arc()).add(arc);
deba@57
   275
      return arc;
deba@57
   276
    }
deba@57
   277
deba@57
   278
    void clear() {
deba@57
   279
      notifier(Arc()).clear();
deba@57
   280
      notifier(Node()).clear();
deba@57
   281
      Parent::clear();
deba@57
   282
    }
deba@57
   283
deba@57
   284
    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
deba@57
   285
    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
deba@57
   286
      Parent::build(digraph, nodeRef, arcRef);
deba@57
   287
      notifier(Node()).build();
deba@57
   288
      notifier(Arc()).build();
deba@57
   289
    }
deba@57
   290
deba@57
   291
    void erase(const Node& node) {
deba@57
   292
      Arc arc;
deba@57
   293
      Parent::firstOut(arc, node);
deba@57
   294
      while (arc != INVALID ) {
alpar@209
   295
        erase(arc);
alpar@209
   296
        Parent::firstOut(arc, node);
alpar@209
   297
      }
deba@57
   298
deba@57
   299
      Parent::firstIn(arc, node);
deba@57
   300
      while (arc != INVALID ) {
alpar@209
   301
        erase(arc);
alpar@209
   302
        Parent::firstIn(arc, node);
deba@57
   303
      }
deba@57
   304
deba@57
   305
      notifier(Node()).erase(node);
deba@57
   306
      Parent::erase(node);
deba@57
   307
    }
alpar@209
   308
deba@57
   309
    void erase(const Arc& arc) {
deba@57
   310
      notifier(Arc()).erase(arc);
deba@57
   311
      Parent::erase(arc);
deba@57
   312
    }
deba@57
   313
deba@57
   314
    DigraphExtender() {
deba@57
   315
      node_notifier.setContainer(*this);
deba@57
   316
      arc_notifier.setContainer(*this);
alpar@209
   317
    }
alpar@209
   318
deba@57
   319
deba@57
   320
    ~DigraphExtender() {
deba@57
   321
      arc_notifier.clear();
deba@57
   322
      node_notifier.clear();
deba@57
   323
    }
deba@57
   324
  };
deba@57
   325
deba@78
   326
  /// \ingroup _graphbits
deba@57
   327
  ///
deba@57
   328
  /// \brief Extender for the Graphs
alpar@209
   329
  template <typename Base>
deba@57
   330
  class GraphExtender : public Base {
deba@57
   331
  public:
alpar@209
   332
deba@57
   333
    typedef Base Parent;
deba@78
   334
    typedef GraphExtender Graph;
deba@57
   335
deba@77
   336
    typedef True UndirectedTag;
deba@77
   337
deba@57
   338
    typedef typename Parent::Node Node;
deba@57
   339
    typedef typename Parent::Arc Arc;
deba@57
   340
    typedef typename Parent::Edge Edge;
deba@57
   341
alpar@209
   342
    // Graph extension
deba@57
   343
deba@57
   344
    int maxId(Node) const {
deba@57
   345
      return Parent::maxNodeId();
deba@57
   346
    }
deba@57
   347
deba@57
   348
    int maxId(Arc) const {
deba@57
   349
      return Parent::maxArcId();
deba@57
   350
    }
deba@57
   351
deba@57
   352
    int maxId(Edge) const {
deba@57
   353
      return Parent::maxEdgeId();
deba@57
   354
    }
deba@57
   355
deba@57
   356
    Node fromId(int id, Node) const {
deba@57
   357
      return Parent::nodeFromId(id);
deba@57
   358
    }
deba@57
   359
deba@57
   360
    Arc fromId(int id, Arc) const {
deba@57
   361
      return Parent::arcFromId(id);
deba@57
   362
    }
deba@57
   363
deba@57
   364
    Edge fromId(int id, Edge) const {
deba@57
   365
      return Parent::edgeFromId(id);
deba@57
   366
    }
deba@57
   367
deba@57
   368
    Node oppositeNode(const Node &n, const Edge &e) const {
deba@125
   369
      if( n == Parent::u(e))
alpar@209
   370
        return Parent::v(e);
deba@125
   371
      else if( n == Parent::v(e))
alpar@209
   372
        return Parent::u(e);
deba@57
   373
      else
alpar@209
   374
        return INVALID;
deba@57
   375
    }
deba@57
   376
deba@78
   377
    Arc oppositeArc(const Arc &arc) const {
deba@78
   378
      return Parent::direct(arc, !Parent::direction(arc));
deba@57
   379
    }
deba@57
   380
deba@57
   381
    using Parent::direct;
deba@78
   382
    Arc direct(const Edge &edge, const Node &node) const {
deba@125
   383
      return Parent::direct(edge, Parent::u(edge) == node);
deba@57
   384
    }
deba@57
   385
deba@57
   386
    // Alterable extension
deba@57
   387
deba@57
   388
    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
deba@57
   389
    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
deba@57
   390
    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
deba@57
   391
deba@57
   392
deba@57
   393
  protected:
deba@57
   394
deba@57
   395
    mutable NodeNotifier node_notifier;
deba@57
   396
    mutable ArcNotifier arc_notifier;
deba@57
   397
    mutable EdgeNotifier edge_notifier;
deba@57
   398
deba@57
   399
  public:
deba@57
   400
deba@57
   401
    NodeNotifier& notifier(Node) const {
deba@57
   402
      return node_notifier;
deba@57
   403
    }
alpar@209
   404
deba@57
   405
    ArcNotifier& notifier(Arc) const {
deba@57
   406
      return arc_notifier;
deba@57
   407
    }
deba@57
   408
deba@57
   409
    EdgeNotifier& notifier(Edge) const {
deba@57
   410
      return edge_notifier;
deba@57
   411
    }
deba@57
   412
deba@57
   413
deba@57
   414
alpar@209
   415
    class NodeIt : public Node {
deba@78
   416
      const Graph* _graph;
deba@57
   417
    public:
deba@57
   418
deba@57
   419
      NodeIt() {}
deba@57
   420
deba@57
   421
      NodeIt(Invalid i) : Node(i) { }
deba@57
   422
deba@78
   423
      explicit NodeIt(const Graph& graph) : _graph(&graph) {
alpar@209
   424
        _graph->first(static_cast<Node&>(*this));
deba@57
   425
      }
deba@57
   426
alpar@209
   427
      NodeIt(const Graph& graph, const Node& node)
alpar@209
   428
        : Node(node), _graph(&graph) {}
deba@57
   429
alpar@209
   430
      NodeIt& operator++() {
alpar@209
   431
        _graph->next(*this);
alpar@209
   432
        return *this;
deba@57
   433
      }
deba@57
   434
deba@57
   435
    };
deba@57
   436
deba@57
   437
alpar@209
   438
    class ArcIt : public Arc {
deba@78
   439
      const Graph* _graph;
deba@57
   440
    public:
deba@57
   441
deba@57
   442
      ArcIt() { }
deba@57
   443
deba@57
   444
      ArcIt(Invalid i) : Arc(i) { }
deba@57
   445
deba@78
   446
      explicit ArcIt(const Graph& graph) : _graph(&graph) {
alpar@209
   447
        _graph->first(static_cast<Arc&>(*this));
deba@57
   448
      }
deba@57
   449
alpar@209
   450
      ArcIt(const Graph& graph, const Arc& arc) :
alpar@209
   451
        Arc(arc), _graph(&graph) { }
deba@57
   452
alpar@209
   453
      ArcIt& operator++() {
alpar@209
   454
        _graph->next(*this);
alpar@209
   455
        return *this;
deba@57
   456
      }
deba@57
   457
deba@57
   458
    };
deba@57
   459
deba@57
   460
alpar@209
   461
    class OutArcIt : public Arc {
deba@78
   462
      const Graph* _graph;
deba@57
   463
    public:
deba@57
   464
deba@57
   465
      OutArcIt() { }
deba@57
   466
deba@57
   467
      OutArcIt(Invalid i) : Arc(i) { }
deba@57
   468
alpar@209
   469
      OutArcIt(const Graph& graph, const Node& node)
alpar@209
   470
        : _graph(&graph) {
alpar@209
   471
        _graph->firstOut(*this, node);
deba@57
   472
      }
deba@57
   473
alpar@209
   474
      OutArcIt(const Graph& graph, const Arc& arc)
alpar@209
   475
        : Arc(arc), _graph(&graph) {}
deba@57
   476
alpar@209
   477
      OutArcIt& operator++() {
alpar@209
   478
        _graph->nextOut(*this);
alpar@209
   479
        return *this;
deba@57
   480
      }
deba@57
   481
deba@57
   482
    };
deba@57
   483
deba@57
   484
alpar@209
   485
    class InArcIt : public Arc {
deba@78
   486
      const Graph* _graph;
deba@57
   487
    public:
deba@57
   488
deba@57
   489
      InArcIt() { }
deba@57
   490
deba@57
   491
      InArcIt(Invalid i) : Arc(i) { }
deba@57
   492
alpar@209
   493
      InArcIt(const Graph& graph, const Node& node)
alpar@209
   494
        : _graph(&graph) {
alpar@209
   495
        _graph->firstIn(*this, node);
deba@57
   496
      }
deba@57
   497
alpar@209
   498
      InArcIt(const Graph& graph, const Arc& arc) :
alpar@209
   499
        Arc(arc), _graph(&graph) {}
deba@57
   500
alpar@209
   501
      InArcIt& operator++() {
alpar@209
   502
        _graph->nextIn(*this);
alpar@209
   503
        return *this;
deba@57
   504
      }
deba@57
   505
deba@57
   506
    };
deba@57
   507
deba@57
   508
alpar@209
   509
    class EdgeIt : public Parent::Edge {
deba@78
   510
      const Graph* _graph;
deba@57
   511
    public:
deba@57
   512
deba@57
   513
      EdgeIt() { }
deba@57
   514
deba@57
   515
      EdgeIt(Invalid i) : Edge(i) { }
deba@57
   516
deba@78
   517
      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
alpar@209
   518
        _graph->first(static_cast<Edge&>(*this));
deba@57
   519
      }
deba@57
   520
alpar@209
   521
      EdgeIt(const Graph& graph, const Edge& edge) :
alpar@209
   522
        Edge(edge), _graph(&graph) { }
deba@57
   523
alpar@209
   524
      EdgeIt& operator++() {
alpar@209
   525
        _graph->next(*this);
alpar@209
   526
        return *this;
deba@57
   527
      }
deba@57
   528
deba@57
   529
    };
deba@57
   530
deba@78
   531
    class IncEdgeIt : public Parent::Edge {
deba@57
   532
      friend class GraphExtender;
deba@78
   533
      const Graph* _graph;
deba@78
   534
      bool _direction;
deba@57
   535
    public:
deba@57
   536
deba@78
   537
      IncEdgeIt() { }
deba@57
   538
deba@78
   539
      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
deba@57
   540
deba@78
   541
      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
alpar@209
   542
        _graph->firstInc(*this, _direction, node);
deba@57
   543
      }
deba@57
   544
deba@78
   545
      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
alpar@209
   546
        : _graph(&graph), Edge(edge) {
alpar@209
   547
        _direction = (_graph->source(edge) == node);
deba@57
   548
      }
deba@57
   549
deba@78
   550
      IncEdgeIt& operator++() {
alpar@209
   551
        _graph->nextInc(*this, _direction);
alpar@209
   552
        return *this;
deba@57
   553
      }
deba@57
   554
    };
deba@57
   555
deba@57
   556
    /// \brief Base node of the iterator
deba@57
   557
    ///
deba@57
   558
    /// Returns the base node (ie. the source in this case) of the iterator
deba@78
   559
    Node baseNode(const OutArcIt &arc) const {
deba@78
   560
      return Parent::source(static_cast<const Arc&>(arc));
deba@57
   561
    }
deba@57
   562
    /// \brief Running node of the iterator
deba@57
   563
    ///
deba@57
   564
    /// Returns the running node (ie. the target in this case) of the
deba@57
   565
    /// iterator
deba@78
   566
    Node runningNode(const OutArcIt &arc) const {
deba@78
   567
      return Parent::target(static_cast<const Arc&>(arc));
deba@57
   568
    }
deba@57
   569
deba@57
   570
    /// \brief Base node of the iterator
deba@57
   571
    ///
deba@57
   572
    /// Returns the base node (ie. the target in this case) of the iterator
deba@78
   573
    Node baseNode(const InArcIt &arc) const {
deba@78
   574
      return Parent::target(static_cast<const Arc&>(arc));
deba@57
   575
    }
deba@57
   576
    /// \brief Running node of the iterator
deba@57
   577
    ///
deba@57
   578
    /// Returns the running node (ie. the source in this case) of the
deba@57
   579
    /// iterator
deba@78
   580
    Node runningNode(const InArcIt &arc) const {
deba@78
   581
      return Parent::source(static_cast<const Arc&>(arc));
deba@57
   582
    }
deba@57
   583
deba@57
   584
    /// Base node of the iterator
deba@57
   585
    ///
deba@57
   586
    /// Returns the base node of the iterator
deba@78
   587
    Node baseNode(const IncEdgeIt &edge) const {
deba@125
   588
      return edge._direction ? u(edge) : v(edge);
deba@57
   589
    }
deba@57
   590
    /// Running node of the iterator
deba@57
   591
    ///
deba@57
   592
    /// Returns the running node of the iterator
deba@78
   593
    Node runningNode(const IncEdgeIt &edge) const {
deba@125
   594
      return edge._direction ? v(edge) : u(edge);
deba@57
   595
    }
deba@57
   596
deba@57
   597
    // Mappable extension
deba@57
   598
deba@57
   599
    template <typename _Value>
alpar@209
   600
    class NodeMap
deba@78
   601
      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
deba@57
   602
    public:
deba@78
   603
      typedef GraphExtender Graph;
deba@78
   604
      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
deba@57
   605
alpar@209
   606
      NodeMap(const Graph& graph)
alpar@209
   607
        : Parent(graph) {}
alpar@209
   608
      NodeMap(const Graph& graph, const _Value& value)
alpar@209
   609
        : Parent(graph, value) {}
deba@57
   610
deba@57
   611
      NodeMap& operator=(const NodeMap& cmap) {
alpar@209
   612
        return operator=<NodeMap>(cmap);
deba@57
   613
      }
deba@57
   614
deba@57
   615
      template <typename CMap>
deba@57
   616
      NodeMap& operator=(const CMap& cmap) {
deba@57
   617
        Parent::operator=(cmap);
alpar@209
   618
        return *this;
deba@57
   619
      }
deba@57
   620
deba@57
   621
    };
deba@57
   622
deba@57
   623
    template <typename _Value>
alpar@209
   624
    class ArcMap
deba@78
   625
      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
deba@57
   626
    public:
deba@78
   627
      typedef GraphExtender Graph;
deba@78
   628
      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
deba@57
   629
alpar@209
   630
      ArcMap(const Graph& graph)
alpar@209
   631
        : Parent(graph) {}
alpar@209
   632
      ArcMap(const Graph& graph, const _Value& value)
alpar@209
   633
        : Parent(graph, value) {}
deba@57
   634
deba@57
   635
      ArcMap& operator=(const ArcMap& cmap) {
alpar@209
   636
        return operator=<ArcMap>(cmap);
deba@57
   637
      }
deba@57
   638
deba@57
   639
      template <typename CMap>
deba@57
   640
      ArcMap& operator=(const CMap& cmap) {
deba@57
   641
        Parent::operator=(cmap);
alpar@209
   642
        return *this;
deba@57
   643
      }
deba@57
   644
    };
deba@57
   645
deba@57
   646
deba@57
   647
    template <typename _Value>
alpar@209
   648
    class EdgeMap
deba@78
   649
      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
deba@57
   650
    public:
deba@78
   651
      typedef GraphExtender Graph;
deba@78
   652
      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
deba@57
   653
alpar@209
   654
      EdgeMap(const Graph& graph)
alpar@209
   655
        : Parent(graph) {}
deba@57
   656
alpar@209
   657
      EdgeMap(const Graph& graph, const _Value& value)
alpar@209
   658
        : Parent(graph, value) {}
deba@57
   659
deba@57
   660
      EdgeMap& operator=(const EdgeMap& cmap) {
alpar@209
   661
        return operator=<EdgeMap>(cmap);
deba@57
   662
      }
deba@57
   663
deba@57
   664
      template <typename CMap>
deba@57
   665
      EdgeMap& operator=(const CMap& cmap) {
deba@57
   666
        Parent::operator=(cmap);
alpar@209
   667
        return *this;
deba@57
   668
      }
deba@57
   669
deba@57
   670
    };
deba@57
   671
deba@57
   672
    // Alteration extension
deba@57
   673
deba@57
   674
    Node addNode() {
deba@57
   675
      Node node = Parent::addNode();
deba@57
   676
      notifier(Node()).add(node);
deba@57
   677
      return node;
deba@57
   678
    }
deba@57
   679
deba@57
   680
    Edge addEdge(const Node& from, const Node& to) {
deba@57
   681
      Edge edge = Parent::addEdge(from, to);
deba@57
   682
      notifier(Edge()).add(edge);
deba@57
   683
      std::vector<Arc> ev;
deba@57
   684
      ev.push_back(Parent::direct(edge, true));
alpar@209
   685
      ev.push_back(Parent::direct(edge, false));
deba@57
   686
      notifier(Arc()).add(ev);
deba@57
   687
      return edge;
deba@57
   688
    }
alpar@209
   689
deba@57
   690
    void clear() {
deba@57
   691
      notifier(Arc()).clear();
deba@57
   692
      notifier(Edge()).clear();
deba@57
   693
      notifier(Node()).clear();
deba@57
   694
      Parent::clear();
deba@57
   695
    }
deba@57
   696
deba@78
   697
    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
alpar@209
   698
    void build(const Graph& graph, NodeRefMap& nodeRef,
deba@57
   699
               EdgeRefMap& edgeRef) {
deba@78
   700
      Parent::build(graph, nodeRef, edgeRef);
deba@57
   701
      notifier(Node()).build();
deba@57
   702
      notifier(Edge()).build();
deba@57
   703
      notifier(Arc()).build();
deba@57
   704
    }
deba@57
   705
deba@57
   706
    void erase(const Node& node) {
deba@57
   707
      Arc arc;
deba@57
   708
      Parent::firstOut(arc, node);
deba@57
   709
      while (arc != INVALID ) {
alpar@209
   710
        erase(arc);
alpar@209
   711
        Parent::firstOut(arc, node);
alpar@209
   712
      }
deba@57
   713
deba@57
   714
      Parent::firstIn(arc, node);
deba@57
   715
      while (arc != INVALID ) {
alpar@209
   716
        erase(arc);
alpar@209
   717
        Parent::firstIn(arc, node);
deba@57
   718
      }
deba@57
   719
deba@57
   720
      notifier(Node()).erase(node);
deba@57
   721
      Parent::erase(node);
deba@57
   722
    }
deba@57
   723
deba@57
   724
    void erase(const Edge& edge) {
deba@78
   725
      std::vector<Arc> av;
deba@78
   726
      av.push_back(Parent::direct(edge, true));
alpar@209
   727
      av.push_back(Parent::direct(edge, false));
deba@78
   728
      notifier(Arc()).erase(av);
deba@57
   729
      notifier(Edge()).erase(edge);
deba@57
   730
      Parent::erase(edge);
deba@57
   731
    }
deba@57
   732
deba@57
   733
    GraphExtender() {
alpar@209
   734
      node_notifier.setContainer(*this);
deba@57
   735
      arc_notifier.setContainer(*this);
deba@57
   736
      edge_notifier.setContainer(*this);
alpar@209
   737
    }
deba@57
   738
deba@57
   739
    ~GraphExtender() {
deba@57
   740
      edge_notifier.clear();
deba@57
   741
      arc_notifier.clear();
alpar@209
   742
      node_notifier.clear();
alpar@209
   743
    }
deba@57
   744
deba@57
   745
  };
deba@57
   746
deba@57
   747
}
deba@57
   748
deba@57
   749
#endif