lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 07 Feb 2008 21:37:07 +0000
changeset 100 4f754b4cf82b
child 77 2de55e4f57a7
permissions -rw-r--r--
Bfs/Dfs/Dijkstra and their deps ported from svn trung -r 3441.
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@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@57
    66
    Node oppositeNode(const Node &n, const Arc &e) const {
deba@57
    67
      if (n == Parent::source(e))
deba@57
    68
	return Parent::target(e);
deba@57
    69
      else if(n==Parent::target(e))
deba@57
    70
	return Parent::source(e);
deba@57
    71
      else
deba@57
    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
    }
deba@57
    91
    
deba@57
    92
    ArcNotifier& notifier(Arc) const {
deba@57
    93
      return arc_notifier;
deba@57
    94
    }
deba@57
    95
deba@57
    96
    class NodeIt : public Node { 
deba@57
    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@57
   104
      explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57
   105
	_digraph.first(static_cast<Node&>(*this));
deba@57
   106
      }
deba@57
   107
deba@57
   108
      NodeIt(const Digraph& _digraph, const Node& node) 
deba@57
   109
	: Node(node), digraph(&_digraph) {}
deba@57
   110
deba@57
   111
      NodeIt& operator++() { 
deba@57
   112
	digraph->next(*this);
deba@57
   113
	return *this; 
deba@57
   114
      }
deba@57
   115
deba@57
   116
    };
deba@57
   117
deba@57
   118
deba@57
   119
    class ArcIt : public Arc { 
deba@57
   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@57
   127
      explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57
   128
	_digraph.first(static_cast<Arc&>(*this));
deba@57
   129
      }
deba@57
   130
deba@57
   131
      ArcIt(const Digraph& _digraph, const Arc& e) : 
deba@57
   132
	Arc(e), digraph(&_digraph) { }
deba@57
   133
deba@57
   134
      ArcIt& operator++() { 
deba@57
   135
	digraph->next(*this);
deba@57
   136
	return *this; 
deba@57
   137
      }
deba@57
   138
deba@57
   139
    };
deba@57
   140
deba@57
   141
deba@57
   142
    class OutArcIt : public Arc { 
deba@57
   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
deba@57
   150
      OutArcIt(const Digraph& _digraph, const Node& node) 
deba@57
   151
	: digraph(&_digraph) {
deba@57
   152
	_digraph.firstOut(*this, node);
deba@57
   153
      }
deba@57
   154
deba@57
   155
      OutArcIt(const Digraph& _digraph, const Arc& arc) 
deba@57
   156
	: Arc(arc), digraph(&_digraph) {}
deba@57
   157
deba@57
   158
      OutArcIt& operator++() { 
deba@57
   159
	digraph->nextOut(*this);
deba@57
   160
	return *this; 
deba@57
   161
      }
deba@57
   162
deba@57
   163
    };
deba@57
   164
deba@57
   165
deba@57
   166
    class InArcIt : public Arc { 
deba@57
   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
deba@57
   174
      InArcIt(const Digraph& _digraph, const Node& node) 
deba@57
   175
	: digraph(&_digraph) {
deba@57
   176
	_digraph.firstIn(*this, node);
deba@57
   177
      }
deba@57
   178
deba@57
   179
      InArcIt(const Digraph& _digraph, const Arc& arc) : 
deba@57
   180
	Arc(arc), digraph(&_digraph) {}
deba@57
   181
deba@57
   182
      InArcIt& operator++() { 
deba@57
   183
	digraph->nextIn(*this);
deba@57
   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@57
   192
    Node baseNode(const OutArcIt &e) const {
deba@57
   193
      return Parent::source(e);
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@57
   199
    Node runningNode(const OutArcIt &e) const {
deba@57
   200
      return Parent::target(e);
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@57
   206
    Node baseNode(const InArcIt &e) const {
deba@57
   207
      return Parent::target(e);
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@57
   213
    Node runningNode(const InArcIt &e) const {
deba@57
   214
      return Parent::source(e);
deba@57
   215
    }
deba@57
   216
deba@57
   217
    
deba@57
   218
    template <typename _Value>
deba@57
   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
deba@57
   225
      explicit NodeMap(const Digraph& digraph) 
deba@57
   226
	: Parent(digraph) {}
deba@57
   227
      NodeMap(const Digraph& digraph, const _Value& value) 
deba@57
   228
	: Parent(digraph, value) {}
deba@57
   229
deba@57
   230
      NodeMap& operator=(const NodeMap& cmap) {
deba@57
   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);
deba@57
   237
	return *this;
deba@57
   238
      }
deba@57
   239
deba@57
   240
    };
deba@57
   241
deba@57
   242
    template <typename _Value>
deba@57
   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
deba@57
   249
      explicit ArcMap(const Digraph& digraph) 
deba@57
   250
	: Parent(digraph) {}
deba@57
   251
      ArcMap(const Digraph& digraph, const _Value& value) 
deba@57
   252
	: Parent(digraph, value) {}
deba@57
   253
deba@57
   254
      ArcMap& operator=(const ArcMap& cmap) {
deba@57
   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);
deba@57
   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
    }
deba@57
   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 ) {
deba@57
   295
	erase(arc);
deba@57
   296
	Parent::firstOut(arc, node);
deba@57
   297
      } 
deba@57
   298
deba@57
   299
      Parent::firstIn(arc, node);
deba@57
   300
      while (arc != INVALID ) {
deba@57
   301
	erase(arc);
deba@57
   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
    }
deba@57
   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);
deba@57
   317
    } 
deba@57
   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@57
   326
  /// \ingroup graphbits
deba@57
   327
  ///
deba@57
   328
  /// \brief Extender for the Graphs
deba@57
   329
  template <typename Base> 
deba@57
   330
  class GraphExtender : public Base {
deba@57
   331
  public:
deba@57
   332
    
deba@57
   333
    typedef Base Parent;
deba@57
   334
    typedef GraphExtender Digraph;
deba@57
   335
deba@57
   336
    typedef typename Parent::Node Node;
deba@57
   337
    typedef typename Parent::Arc Arc;
deba@57
   338
    typedef typename Parent::Edge Edge;
deba@57
   339
deba@57
   340
    // Graph extension    
deba@57
   341
deba@57
   342
    int maxId(Node) const {
deba@57
   343
      return Parent::maxNodeId();
deba@57
   344
    }
deba@57
   345
deba@57
   346
    int maxId(Arc) const {
deba@57
   347
      return Parent::maxArcId();
deba@57
   348
    }
deba@57
   349
deba@57
   350
    int maxId(Edge) const {
deba@57
   351
      return Parent::maxEdgeId();
deba@57
   352
    }
deba@57
   353
deba@57
   354
    Node fromId(int id, Node) const {
deba@57
   355
      return Parent::nodeFromId(id);
deba@57
   356
    }
deba@57
   357
deba@57
   358
    Arc fromId(int id, Arc) const {
deba@57
   359
      return Parent::arcFromId(id);
deba@57
   360
    }
deba@57
   361
deba@57
   362
    Edge fromId(int id, Edge) const {
deba@57
   363
      return Parent::edgeFromId(id);
deba@57
   364
    }
deba@57
   365
deba@57
   366
    Node oppositeNode(const Node &n, const Edge &e) const {
deba@57
   367
      if( n == Parent::source(e))
deba@57
   368
	return Parent::target(e);
deba@57
   369
      else if( n == Parent::target(e))
deba@57
   370
	return Parent::source(e);
deba@57
   371
      else
deba@57
   372
	return INVALID;
deba@57
   373
    }
deba@57
   374
deba@57
   375
    Arc oppositeArc(const Arc &e) const {
deba@57
   376
      return Parent::direct(e, !Parent::direction(e));
deba@57
   377
    }
deba@57
   378
deba@57
   379
    using Parent::direct;
deba@57
   380
    Arc direct(const Edge &ue, const Node &s) const {
deba@57
   381
      return Parent::direct(ue, Parent::source(ue) == s);
deba@57
   382
    }
deba@57
   383
deba@57
   384
    // Alterable extension
deba@57
   385
deba@57
   386
    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
deba@57
   387
    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
deba@57
   388
    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
deba@57
   389
deba@57
   390
deba@57
   391
  protected:
deba@57
   392
deba@57
   393
    mutable NodeNotifier node_notifier;
deba@57
   394
    mutable ArcNotifier arc_notifier;
deba@57
   395
    mutable EdgeNotifier edge_notifier;
deba@57
   396
deba@57
   397
  public:
deba@57
   398
deba@57
   399
    NodeNotifier& notifier(Node) const {
deba@57
   400
      return node_notifier;
deba@57
   401
    }
deba@57
   402
    
deba@57
   403
    ArcNotifier& notifier(Arc) const {
deba@57
   404
      return arc_notifier;
deba@57
   405
    }
deba@57
   406
deba@57
   407
    EdgeNotifier& notifier(Edge) const {
deba@57
   408
      return edge_notifier;
deba@57
   409
    }
deba@57
   410
deba@57
   411
deba@57
   412
deba@57
   413
    class NodeIt : public Node { 
deba@57
   414
      const Digraph* digraph;
deba@57
   415
    public:
deba@57
   416
deba@57
   417
      NodeIt() {}
deba@57
   418
deba@57
   419
      NodeIt(Invalid i) : Node(i) { }
deba@57
   420
deba@57
   421
      explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57
   422
	_digraph.first(static_cast<Node&>(*this));
deba@57
   423
      }
deba@57
   424
deba@57
   425
      NodeIt(const Digraph& _digraph, const Node& node) 
deba@57
   426
	: Node(node), digraph(&_digraph) {}
deba@57
   427
deba@57
   428
      NodeIt& operator++() { 
deba@57
   429
	digraph->next(*this);
deba@57
   430
	return *this; 
deba@57
   431
      }
deba@57
   432
deba@57
   433
    };
deba@57
   434
deba@57
   435
deba@57
   436
    class ArcIt : public Arc { 
deba@57
   437
      const Digraph* digraph;
deba@57
   438
    public:
deba@57
   439
deba@57
   440
      ArcIt() { }
deba@57
   441
deba@57
   442
      ArcIt(Invalid i) : Arc(i) { }
deba@57
   443
deba@57
   444
      explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57
   445
	_digraph.first(static_cast<Arc&>(*this));
deba@57
   446
      }
deba@57
   447
deba@57
   448
      ArcIt(const Digraph& _digraph, const Arc& e) : 
deba@57
   449
	Arc(e), digraph(&_digraph) { }
deba@57
   450
deba@57
   451
      ArcIt& operator++() { 
deba@57
   452
	digraph->next(*this);
deba@57
   453
	return *this; 
deba@57
   454
      }
deba@57
   455
deba@57
   456
    };
deba@57
   457
deba@57
   458
deba@57
   459
    class OutArcIt : public Arc { 
deba@57
   460
      const Digraph* digraph;
deba@57
   461
    public:
deba@57
   462
deba@57
   463
      OutArcIt() { }
deba@57
   464
deba@57
   465
      OutArcIt(Invalid i) : Arc(i) { }
deba@57
   466
deba@57
   467
      OutArcIt(const Digraph& _digraph, const Node& node) 
deba@57
   468
	: digraph(&_digraph) {
deba@57
   469
	_digraph.firstOut(*this, node);
deba@57
   470
      }
deba@57
   471
deba@57
   472
      OutArcIt(const Digraph& _digraph, const Arc& arc) 
deba@57
   473
	: Arc(arc), digraph(&_digraph) {}
deba@57
   474
deba@57
   475
      OutArcIt& operator++() { 
deba@57
   476
	digraph->nextOut(*this);
deba@57
   477
	return *this; 
deba@57
   478
      }
deba@57
   479
deba@57
   480
    };
deba@57
   481
deba@57
   482
deba@57
   483
    class InArcIt : public Arc { 
deba@57
   484
      const Digraph* digraph;
deba@57
   485
    public:
deba@57
   486
deba@57
   487
      InArcIt() { }
deba@57
   488
deba@57
   489
      InArcIt(Invalid i) : Arc(i) { }
deba@57
   490
deba@57
   491
      InArcIt(const Digraph& _digraph, const Node& node) 
deba@57
   492
	: digraph(&_digraph) {
deba@57
   493
	_digraph.firstIn(*this, node);
deba@57
   494
      }
deba@57
   495
deba@57
   496
      InArcIt(const Digraph& _digraph, const Arc& arc) : 
deba@57
   497
	Arc(arc), digraph(&_digraph) {}
deba@57
   498
deba@57
   499
      InArcIt& operator++() { 
deba@57
   500
	digraph->nextIn(*this);
deba@57
   501
	return *this; 
deba@57
   502
      }
deba@57
   503
deba@57
   504
    };
deba@57
   505
deba@57
   506
deba@57
   507
    class EdgeIt : public Parent::Edge { 
deba@57
   508
      const Digraph* digraph;
deba@57
   509
    public:
deba@57
   510
deba@57
   511
      EdgeIt() { }
deba@57
   512
deba@57
   513
      EdgeIt(Invalid i) : Edge(i) { }
deba@57
   514
deba@57
   515
      explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57
   516
	_digraph.first(static_cast<Edge&>(*this));
deba@57
   517
      }
deba@57
   518
deba@57
   519
      EdgeIt(const Digraph& _digraph, const Edge& e) : 
deba@57
   520
	Edge(e), digraph(&_digraph) { }
deba@57
   521
deba@57
   522
      EdgeIt& operator++() { 
deba@57
   523
	digraph->next(*this);
deba@57
   524
	return *this; 
deba@57
   525
      }
deba@57
   526
deba@57
   527
    };
deba@57
   528
deba@57
   529
    class IncArcIt : public Parent::Edge {
deba@57
   530
      friend class GraphExtender;
deba@57
   531
      const Digraph* digraph;
deba@57
   532
      bool direction;
deba@57
   533
    public:
deba@57
   534
deba@57
   535
      IncArcIt() { }
deba@57
   536
deba@57
   537
      IncArcIt(Invalid i) : Edge(i), direction(false) { }
deba@57
   538
deba@57
   539
      IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
deba@57
   540
	_digraph.firstInc(*this, direction, n);
deba@57
   541
      }
deba@57
   542
deba@57
   543
      IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
deba@57
   544
	: digraph(&_digraph), Edge(ue) {
deba@57
   545
	direction = (_digraph.source(ue) == n);
deba@57
   546
      }
deba@57
   547
deba@57
   548
      IncArcIt& operator++() {
deba@57
   549
	digraph->nextInc(*this, direction);
deba@57
   550
	return *this; 
deba@57
   551
      }
deba@57
   552
    };
deba@57
   553
deba@57
   554
    /// \brief Base node of the iterator
deba@57
   555
    ///
deba@57
   556
    /// Returns the base node (ie. the source in this case) of the iterator
deba@57
   557
    Node baseNode(const OutArcIt &e) const {
deba@57
   558
      return Parent::source(static_cast<const Arc&>(e));
deba@57
   559
    }
deba@57
   560
    /// \brief Running node of the iterator
deba@57
   561
    ///
deba@57
   562
    /// Returns the running node (ie. the target in this case) of the
deba@57
   563
    /// iterator
deba@57
   564
    Node runningNode(const OutArcIt &e) const {
deba@57
   565
      return Parent::target(static_cast<const Arc&>(e));
deba@57
   566
    }
deba@57
   567
deba@57
   568
    /// \brief Base node of the iterator
deba@57
   569
    ///
deba@57
   570
    /// Returns the base node (ie. the target in this case) of the iterator
deba@57
   571
    Node baseNode(const InArcIt &e) const {
deba@57
   572
      return Parent::target(static_cast<const Arc&>(e));
deba@57
   573
    }
deba@57
   574
    /// \brief Running node of the iterator
deba@57
   575
    ///
deba@57
   576
    /// Returns the running node (ie. the source in this case) of the
deba@57
   577
    /// iterator
deba@57
   578
    Node runningNode(const InArcIt &e) const {
deba@57
   579
      return Parent::source(static_cast<const Arc&>(e));
deba@57
   580
    }
deba@57
   581
deba@57
   582
    /// Base node of the iterator
deba@57
   583
    ///
deba@57
   584
    /// Returns the base node of the iterator
deba@57
   585
    Node baseNode(const IncArcIt &e) const {
deba@57
   586
      return e.direction ? source(e) : target(e);
deba@57
   587
    }
deba@57
   588
    /// Running node of the iterator
deba@57
   589
    ///
deba@57
   590
    /// Returns the running node of the iterator
deba@57
   591
    Node runningNode(const IncArcIt &e) const {
deba@57
   592
      return e.direction ? target(e) : source(e);
deba@57
   593
    }
deba@57
   594
deba@57
   595
    // Mappable extension
deba@57
   596
deba@57
   597
    template <typename _Value>
deba@57
   598
    class NodeMap 
deba@57
   599
      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
deba@57
   600
    public:
deba@57
   601
      typedef GraphExtender Digraph;
deba@57
   602
      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57
   603
deba@57
   604
      NodeMap(const Digraph& digraph) 
deba@57
   605
	: Parent(digraph) {}
deba@57
   606
      NodeMap(const Digraph& digraph, const _Value& value) 
deba@57
   607
	: Parent(digraph, value) {}
deba@57
   608
deba@57
   609
      NodeMap& operator=(const NodeMap& cmap) {
deba@57
   610
	return operator=<NodeMap>(cmap);
deba@57
   611
      }
deba@57
   612
deba@57
   613
      template <typename CMap>
deba@57
   614
      NodeMap& operator=(const CMap& cmap) {
deba@57
   615
        Parent::operator=(cmap);
deba@57
   616
	return *this;
deba@57
   617
      }
deba@57
   618
deba@57
   619
    };
deba@57
   620
deba@57
   621
    template <typename _Value>
deba@57
   622
    class ArcMap 
deba@57
   623
      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
deba@57
   624
    public:
deba@57
   625
      typedef GraphExtender Digraph;
deba@57
   626
      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57
   627
deba@57
   628
      ArcMap(const Digraph& digraph) 
deba@57
   629
	: Parent(digraph) {}
deba@57
   630
      ArcMap(const Digraph& digraph, const _Value& value) 
deba@57
   631
	: Parent(digraph, value) {}
deba@57
   632
deba@57
   633
      ArcMap& operator=(const ArcMap& cmap) {
deba@57
   634
	return operator=<ArcMap>(cmap);
deba@57
   635
      }
deba@57
   636
deba@57
   637
      template <typename CMap>
deba@57
   638
      ArcMap& operator=(const CMap& cmap) {
deba@57
   639
        Parent::operator=(cmap);
deba@57
   640
	return *this;
deba@57
   641
      }
deba@57
   642
    };
deba@57
   643
deba@57
   644
deba@57
   645
    template <typename _Value>
deba@57
   646
    class EdgeMap 
deba@57
   647
      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
deba@57
   648
    public:
deba@57
   649
      typedef GraphExtender Digraph;
deba@57
   650
      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
deba@57
   651
deba@57
   652
      EdgeMap(const Digraph& digraph) 
deba@57
   653
	: Parent(digraph) {}
deba@57
   654
deba@57
   655
      EdgeMap(const Digraph& digraph, const _Value& value) 
deba@57
   656
	: Parent(digraph, value) {}
deba@57
   657
deba@57
   658
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@57
   659
	return operator=<EdgeMap>(cmap);
deba@57
   660
      }
deba@57
   661
deba@57
   662
      template <typename CMap>
deba@57
   663
      EdgeMap& operator=(const CMap& cmap) {
deba@57
   664
        Parent::operator=(cmap);
deba@57
   665
	return *this;
deba@57
   666
      }
deba@57
   667
deba@57
   668
    };
deba@57
   669
deba@57
   670
    // Alteration extension
deba@57
   671
deba@57
   672
    Node addNode() {
deba@57
   673
      Node node = Parent::addNode();
deba@57
   674
      notifier(Node()).add(node);
deba@57
   675
      return node;
deba@57
   676
    }
deba@57
   677
deba@57
   678
    Edge addEdge(const Node& from, const Node& to) {
deba@57
   679
      Edge edge = Parent::addEdge(from, to);
deba@57
   680
      notifier(Edge()).add(edge);
deba@57
   681
      std::vector<Arc> ev;
deba@57
   682
      ev.push_back(Parent::direct(edge, true));
deba@57
   683
      ev.push_back(Parent::direct(edge, false));      
deba@57
   684
      notifier(Arc()).add(ev);
deba@57
   685
      return edge;
deba@57
   686
    }
deba@57
   687
    
deba@57
   688
    void clear() {
deba@57
   689
      notifier(Arc()).clear();
deba@57
   690
      notifier(Edge()).clear();
deba@57
   691
      notifier(Node()).clear();
deba@57
   692
      Parent::clear();
deba@57
   693
    }
deba@57
   694
deba@57
   695
    template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
deba@57
   696
    void build(const Digraph& digraph, NodeRefMap& nodeRef, 
deba@57
   697
               EdgeRefMap& edgeRef) {
deba@57
   698
      Parent::build(digraph, nodeRef, edgeRef);
deba@57
   699
      notifier(Node()).build();
deba@57
   700
      notifier(Edge()).build();
deba@57
   701
      notifier(Arc()).build();
deba@57
   702
    }
deba@57
   703
deba@57
   704
    void erase(const Node& node) {
deba@57
   705
      Arc arc;
deba@57
   706
      Parent::firstOut(arc, node);
deba@57
   707
      while (arc != INVALID ) {
deba@57
   708
	erase(arc);
deba@57
   709
	Parent::firstOut(arc, node);
deba@57
   710
      } 
deba@57
   711
deba@57
   712
      Parent::firstIn(arc, node);
deba@57
   713
      while (arc != INVALID ) {
deba@57
   714
	erase(arc);
deba@57
   715
	Parent::firstIn(arc, node);
deba@57
   716
      }
deba@57
   717
deba@57
   718
      notifier(Node()).erase(node);
deba@57
   719
      Parent::erase(node);
deba@57
   720
    }
deba@57
   721
deba@57
   722
    void erase(const Edge& edge) {
deba@57
   723
      std::vector<Arc> ev;
deba@57
   724
      ev.push_back(Parent::direct(edge, true));
deba@57
   725
      ev.push_back(Parent::direct(edge, false));      
deba@57
   726
      notifier(Arc()).erase(ev);
deba@57
   727
      notifier(Edge()).erase(edge);
deba@57
   728
      Parent::erase(edge);
deba@57
   729
    }
deba@57
   730
deba@57
   731
    GraphExtender() {
deba@57
   732
      node_notifier.setContainer(*this); 
deba@57
   733
      arc_notifier.setContainer(*this);
deba@57
   734
      edge_notifier.setContainer(*this);
deba@57
   735
    } 
deba@57
   736
deba@57
   737
    ~GraphExtender() {
deba@57
   738
      edge_notifier.clear();
deba@57
   739
      arc_notifier.clear();
deba@57
   740
      node_notifier.clear(); 
deba@57
   741
    } 
deba@57
   742
deba@57
   743
  };
deba@57
   744
deba@57
   745
}
deba@57
   746
deba@57
   747
#endif