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