lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 17 Oct 2018 18:55:53 +0200
changeset 1174 7c86f14b3bc5
parent 1027 8b2b9e61d8ce
child 1130 0759d974de81
permissions -rw-r--r--
Merge #1.3 related bugfix heads
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@1092
     5
 * Copyright (C) 2003-2013
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
kpeter@314
    30
//\ingroup graphbits
kpeter@314
    31
//\file
kpeter@361
    32
//\brief Extenders for the graph types
deba@57
    33
namespace lemon {
deba@57
    34
kpeter@314
    35
  // \ingroup graphbits
kpeter@314
    36
  //
kpeter@361
    37
  // \brief Extender for the digraph implementations
deba@57
    38
  template <typename Base>
deba@57
    39
  class DigraphExtender : public Base {
kpeter@617
    40
    typedef Base Parent;
kpeter@617
    41
deba@57
    42
  public:
deba@57
    43
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
kpeter@778
    59
    static Node fromId(int id, Node) {
deba@57
    60
      return Parent::nodeFromId(id);
deba@57
    61
    }
deba@57
    62
kpeter@778
    63
    static Arc fromId(int id, Arc) {
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))
alpar@209
    69
        return Parent::target(arc);
deba@78
    70
      else if(node == Parent::target(arc))
alpar@209
    71
        return Parent::source(arc);
deba@57
    72
      else
alpar@209
    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
    }
alpar@209
    92
deba@57
    93
    ArcNotifier& notifier(Arc) const {
deba@57
    94
      return arc_notifier;
deba@57
    95
    }
deba@57
    96
alpar@209
    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) {
alpar@209
   106
        _digraph->first(static_cast<Node&>(*this));
deba@57
   107
      }
deba@57
   108
alpar@209
   109
      NodeIt(const Digraph& digraph, const Node& node)
alpar@209
   110
        : Node(node), _digraph(&digraph) {}
deba@57
   111
alpar@209
   112
      NodeIt& operator++() {
alpar@209
   113
        _digraph->next(*this);
alpar@209
   114
        return *this;
deba@57
   115
      }
deba@57
   116
deba@57
   117
    };
deba@57
   118
deba@57
   119
alpar@209
   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) {
alpar@209
   129
        _digraph->first(static_cast<Arc&>(*this));
deba@57
   130
      }
deba@57
   131
alpar@209
   132
      ArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209
   133
        Arc(arc), _digraph(&digraph) { }
deba@57
   134
alpar@209
   135
      ArcIt& operator++() {
alpar@209
   136
        _digraph->next(*this);
alpar@209
   137
        return *this;
deba@57
   138
      }
deba@57
   139
deba@57
   140
    };
deba@57
   141
deba@57
   142
alpar@209
   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
alpar@209
   151
      OutArcIt(const Digraph& digraph, const Node& node)
alpar@209
   152
        : _digraph(&digraph) {
alpar@209
   153
        _digraph->firstOut(*this, node);
deba@57
   154
      }
deba@57
   155
alpar@209
   156
      OutArcIt(const Digraph& digraph, const Arc& arc)
alpar@209
   157
        : Arc(arc), _digraph(&digraph) {}
deba@57
   158
alpar@209
   159
      OutArcIt& operator++() {
alpar@209
   160
        _digraph->nextOut(*this);
alpar@209
   161
        return *this;
deba@57
   162
      }
deba@57
   163
deba@57
   164
    };
deba@57
   165
deba@57
   166
alpar@209
   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
alpar@209
   175
      InArcIt(const Digraph& digraph, const Node& node)
alpar@209
   176
        : _digraph(&digraph) {
alpar@209
   177
        _digraph->firstIn(*this, node);
deba@57
   178
      }
deba@57
   179
alpar@209
   180
      InArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209
   181
        Arc(arc), _digraph(&digraph) {}
deba@57
   182
alpar@209
   183
      InArcIt& operator++() {
alpar@209
   184
        _digraph->nextIn(*this);
alpar@209
   185
        return *this;
deba@57
   186
      }
deba@57
   187
deba@57
   188
    };
deba@57
   189
kpeter@314
   190
    // \brief Base node of the iterator
kpeter@314
   191
    //
kpeter@314
   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
    }
kpeter@314
   196
    // \brief Running node of the iterator
kpeter@314
   197
    //
kpeter@314
   198
    // Returns the running node (i.e. the target in this case) of the
kpeter@314
   199
    // iterator
deba@78
   200
    Node runningNode(const OutArcIt &arc) const {
deba@78
   201
      return Parent::target(arc);
deba@57
   202
    }
deba@57
   203
kpeter@314
   204
    // \brief Base node of the iterator
kpeter@314
   205
    //
kpeter@314
   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
    }
kpeter@314
   210
    // \brief Running node of the iterator
kpeter@314
   211
    //
kpeter@314
   212
    // Returns the running node (i.e. the source in this case) of the
kpeter@314
   213
    // iterator
deba@78
   214
    Node runningNode(const InArcIt &arc) const {
deba@78
   215
      return Parent::source(arc);
deba@57
   216
    }
deba@57
   217
alpar@209
   218
deba@57
   219
    template <typename _Value>
alpar@209
   220
    class NodeMap
deba@57
   221
      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
deba@57
   222
      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57
   223
kpeter@617
   224
    public:
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
kpeter@263
   230
    private:
deba@57
   231
      NodeMap& operator=(const NodeMap& cmap) {
alpar@209
   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);
alpar@209
   238
        return *this;
deba@57
   239
      }
deba@57
   240
deba@57
   241
    };
deba@57
   242
deba@57
   243
    template <typename _Value>
alpar@209
   244
    class ArcMap
deba@57
   245
      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
deba@57
   246
      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57
   247
kpeter@617
   248
    public:
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
kpeter@263
   254
    private:
deba@57
   255
      ArcMap& operator=(const ArcMap& cmap) {
alpar@209
   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);
alpar@209
   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
    }
alpar@209
   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 ) {
alpar@209
   296
        erase(arc);
alpar@209
   297
        Parent::firstOut(arc, node);
alpar@209
   298
      }
deba@57
   299
deba@57
   300
      Parent::firstIn(arc, node);
deba@57
   301
      while (arc != INVALID ) {
alpar@209
   302
        erase(arc);
alpar@209
   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
    }
alpar@209
   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);
alpar@209
   318
    }
alpar@209
   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
kpeter@314
   327
  // \ingroup _graphbits
kpeter@314
   328
  //
kpeter@314
   329
  // \brief Extender for the Graphs
alpar@209
   330
  template <typename Base>
deba@57
   331
  class GraphExtender : public Base {
kpeter@617
   332
    typedef Base Parent;
kpeter@617
   333
deba@57
   334
  public:
alpar@209
   335
deba@78
   336
    typedef GraphExtender Graph;
deba@57
   337
deba@77
   338
    typedef True UndirectedTag;
deba@77
   339
deba@57
   340
    typedef typename Parent::Node Node;
deba@57
   341
    typedef typename Parent::Arc Arc;
deba@57
   342
    typedef typename Parent::Edge Edge;
deba@57
   343
alpar@209
   344
    // Graph extension
deba@57
   345
deba@57
   346
    int maxId(Node) const {
deba@57
   347
      return Parent::maxNodeId();
deba@57
   348
    }
deba@57
   349
deba@57
   350
    int maxId(Arc) const {
deba@57
   351
      return Parent::maxArcId();
deba@57
   352
    }
deba@57
   353
deba@57
   354
    int maxId(Edge) const {
deba@57
   355
      return Parent::maxEdgeId();
deba@57
   356
    }
deba@57
   357
kpeter@778
   358
    static Node fromId(int id, Node) {
deba@57
   359
      return Parent::nodeFromId(id);
deba@57
   360
    }
deba@57
   361
kpeter@778
   362
    static Arc fromId(int id, Arc) {
deba@57
   363
      return Parent::arcFromId(id);
deba@57
   364
    }
deba@57
   365
kpeter@778
   366
    static Edge fromId(int id, Edge) {
deba@57
   367
      return Parent::edgeFromId(id);
deba@57
   368
    }
deba@57
   369
deba@57
   370
    Node oppositeNode(const Node &n, const Edge &e) const {
deba@125
   371
      if( n == Parent::u(e))
alpar@209
   372
        return Parent::v(e);
deba@125
   373
      else if( n == Parent::v(e))
alpar@209
   374
        return Parent::u(e);
deba@57
   375
      else
alpar@209
   376
        return INVALID;
deba@57
   377
    }
deba@57
   378
deba@78
   379
    Arc oppositeArc(const Arc &arc) const {
deba@78
   380
      return Parent::direct(arc, !Parent::direction(arc));
deba@57
   381
    }
deba@57
   382
deba@57
   383
    using Parent::direct;
deba@78
   384
    Arc direct(const Edge &edge, const Node &node) const {
deba@125
   385
      return Parent::direct(edge, Parent::u(edge) == node);
deba@57
   386
    }
deba@57
   387
deba@57
   388
    // Alterable extension
deba@57
   389
deba@57
   390
    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
deba@57
   391
    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
deba@57
   392
    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
deba@57
   393
deba@57
   394
deba@57
   395
  protected:
deba@57
   396
deba@57
   397
    mutable NodeNotifier node_notifier;
deba@57
   398
    mutable ArcNotifier arc_notifier;
deba@57
   399
    mutable EdgeNotifier edge_notifier;
deba@57
   400
deba@57
   401
  public:
deba@57
   402
deba@57
   403
    NodeNotifier& notifier(Node) const {
deba@57
   404
      return node_notifier;
deba@57
   405
    }
alpar@209
   406
deba@57
   407
    ArcNotifier& notifier(Arc) const {
deba@57
   408
      return arc_notifier;
deba@57
   409
    }
deba@57
   410
deba@57
   411
    EdgeNotifier& notifier(Edge) const {
deba@57
   412
      return edge_notifier;
deba@57
   413
    }
deba@57
   414
deba@57
   415
deba@57
   416
alpar@209
   417
    class NodeIt : public Node {
deba@78
   418
      const Graph* _graph;
deba@57
   419
    public:
deba@57
   420
deba@57
   421
      NodeIt() {}
deba@57
   422
deba@57
   423
      NodeIt(Invalid i) : Node(i) { }
deba@57
   424
deba@78
   425
      explicit NodeIt(const Graph& graph) : _graph(&graph) {
alpar@209
   426
        _graph->first(static_cast<Node&>(*this));
deba@57
   427
      }
deba@57
   428
alpar@209
   429
      NodeIt(const Graph& graph, const Node& node)
alpar@209
   430
        : Node(node), _graph(&graph) {}
deba@57
   431
alpar@209
   432
      NodeIt& operator++() {
alpar@209
   433
        _graph->next(*this);
alpar@209
   434
        return *this;
deba@57
   435
      }
deba@57
   436
deba@57
   437
    };
deba@57
   438
deba@57
   439
alpar@209
   440
    class ArcIt : public Arc {
deba@78
   441
      const Graph* _graph;
deba@57
   442
    public:
deba@57
   443
deba@57
   444
      ArcIt() { }
deba@57
   445
deba@57
   446
      ArcIt(Invalid i) : Arc(i) { }
deba@57
   447
deba@78
   448
      explicit ArcIt(const Graph& graph) : _graph(&graph) {
alpar@209
   449
        _graph->first(static_cast<Arc&>(*this));
deba@57
   450
      }
deba@57
   451
alpar@209
   452
      ArcIt(const Graph& graph, const Arc& arc) :
alpar@209
   453
        Arc(arc), _graph(&graph) { }
deba@57
   454
alpar@209
   455
      ArcIt& operator++() {
alpar@209
   456
        _graph->next(*this);
alpar@209
   457
        return *this;
deba@57
   458
      }
deba@57
   459
deba@57
   460
    };
deba@57
   461
deba@57
   462
alpar@209
   463
    class OutArcIt : public Arc {
deba@78
   464
      const Graph* _graph;
deba@57
   465
    public:
deba@57
   466
deba@57
   467
      OutArcIt() { }
deba@57
   468
deba@57
   469
      OutArcIt(Invalid i) : Arc(i) { }
deba@57
   470
alpar@209
   471
      OutArcIt(const Graph& graph, const Node& node)
alpar@209
   472
        : _graph(&graph) {
alpar@209
   473
        _graph->firstOut(*this, node);
deba@57
   474
      }
deba@57
   475
alpar@209
   476
      OutArcIt(const Graph& graph, const Arc& arc)
alpar@209
   477
        : Arc(arc), _graph(&graph) {}
deba@57
   478
alpar@209
   479
      OutArcIt& operator++() {
alpar@209
   480
        _graph->nextOut(*this);
alpar@209
   481
        return *this;
deba@57
   482
      }
deba@57
   483
deba@57
   484
    };
deba@57
   485
deba@57
   486
alpar@209
   487
    class InArcIt : public Arc {
deba@78
   488
      const Graph* _graph;
deba@57
   489
    public:
deba@57
   490
deba@57
   491
      InArcIt() { }
deba@57
   492
deba@57
   493
      InArcIt(Invalid i) : Arc(i) { }
deba@57
   494
alpar@209
   495
      InArcIt(const Graph& graph, const Node& node)
alpar@209
   496
        : _graph(&graph) {
alpar@209
   497
        _graph->firstIn(*this, node);
deba@57
   498
      }
deba@57
   499
alpar@209
   500
      InArcIt(const Graph& graph, const Arc& arc) :
alpar@209
   501
        Arc(arc), _graph(&graph) {}
deba@57
   502
alpar@209
   503
      InArcIt& operator++() {
alpar@209
   504
        _graph->nextIn(*this);
alpar@209
   505
        return *this;
deba@57
   506
      }
deba@57
   507
deba@57
   508
    };
deba@57
   509
deba@57
   510
alpar@209
   511
    class EdgeIt : public Parent::Edge {
deba@78
   512
      const Graph* _graph;
deba@57
   513
    public:
deba@57
   514
deba@57
   515
      EdgeIt() { }
deba@57
   516
deba@57
   517
      EdgeIt(Invalid i) : Edge(i) { }
deba@57
   518
deba@78
   519
      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
alpar@209
   520
        _graph->first(static_cast<Edge&>(*this));
deba@57
   521
      }
deba@57
   522
alpar@209
   523
      EdgeIt(const Graph& graph, const Edge& edge) :
alpar@209
   524
        Edge(edge), _graph(&graph) { }
deba@57
   525
alpar@209
   526
      EdgeIt& operator++() {
alpar@209
   527
        _graph->next(*this);
alpar@209
   528
        return *this;
deba@57
   529
      }
deba@57
   530
deba@57
   531
    };
deba@57
   532
deba@78
   533
    class IncEdgeIt : public Parent::Edge {
deba@57
   534
      friend class GraphExtender;
deba@78
   535
      const Graph* _graph;
deba@78
   536
      bool _direction;
deba@57
   537
    public:
deba@57
   538
deba@78
   539
      IncEdgeIt() { }
deba@57
   540
deba@78
   541
      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
deba@57
   542
deba@78
   543
      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
alpar@209
   544
        _graph->firstInc(*this, _direction, node);
deba@57
   545
      }
deba@57
   546
deba@78
   547
      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
alpar@209
   548
        : _graph(&graph), Edge(edge) {
alpar@209
   549
        _direction = (_graph->source(edge) == node);
deba@57
   550
      }
deba@57
   551
deba@78
   552
      IncEdgeIt& operator++() {
alpar@209
   553
        _graph->nextInc(*this, _direction);
alpar@209
   554
        return *this;
deba@57
   555
      }
deba@57
   556
    };
deba@57
   557
kpeter@314
   558
    // \brief Base node of the iterator
kpeter@314
   559
    //
kpeter@314
   560
    // Returns the base node (ie. the source in this case) of the iterator
deba@78
   561
    Node baseNode(const OutArcIt &arc) const {
deba@78
   562
      return Parent::source(static_cast<const Arc&>(arc));
deba@57
   563
    }
kpeter@314
   564
    // \brief Running node of the iterator
kpeter@314
   565
    //
kpeter@314
   566
    // Returns the running node (ie. the target in this case) of the
kpeter@314
   567
    // iterator
deba@78
   568
    Node runningNode(const OutArcIt &arc) const {
deba@78
   569
      return Parent::target(static_cast<const Arc&>(arc));
deba@57
   570
    }
deba@57
   571
kpeter@314
   572
    // \brief Base node of the iterator
kpeter@314
   573
    //
kpeter@314
   574
    // Returns the base node (ie. the target in this case) of the iterator
deba@78
   575
    Node baseNode(const InArcIt &arc) const {
deba@78
   576
      return Parent::target(static_cast<const Arc&>(arc));
deba@57
   577
    }
kpeter@314
   578
    // \brief Running node of the iterator
kpeter@314
   579
    //
kpeter@314
   580
    // Returns the running node (ie. the source in this case) of the
kpeter@314
   581
    // iterator
deba@78
   582
    Node runningNode(const InArcIt &arc) const {
deba@78
   583
      return Parent::source(static_cast<const Arc&>(arc));
deba@57
   584
    }
deba@57
   585
kpeter@314
   586
    // Base node of the iterator
kpeter@314
   587
    //
kpeter@314
   588
    // Returns the base node of the iterator
deba@78
   589
    Node baseNode(const IncEdgeIt &edge) const {
alpar@997
   590
      return edge._direction ? this->u(edge) : this->v(edge);
deba@57
   591
    }
kpeter@314
   592
    // Running node of the iterator
kpeter@314
   593
    //
kpeter@314
   594
    // Returns the running node of the iterator
deba@78
   595
    Node runningNode(const IncEdgeIt &edge) const {
alpar@997
   596
      return edge._direction ? this->v(edge) : this->u(edge);
deba@57
   597
    }
deba@57
   598
deba@57
   599
    // Mappable extension
deba@57
   600
deba@57
   601
    template <typename _Value>
alpar@209
   602
    class NodeMap
deba@78
   603
      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
deba@78
   604
      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
deba@57
   605
kpeter@617
   606
    public:
kpeter@685
   607
      explicit NodeMap(const Graph& graph)
alpar@209
   608
        : Parent(graph) {}
alpar@209
   609
      NodeMap(const Graph& graph, const _Value& value)
alpar@209
   610
        : Parent(graph, value) {}
deba@57
   611
kpeter@263
   612
    private:
deba@57
   613
      NodeMap& operator=(const NodeMap& cmap) {
alpar@209
   614
        return operator=<NodeMap>(cmap);
deba@57
   615
      }
deba@57
   616
deba@57
   617
      template <typename CMap>
deba@57
   618
      NodeMap& operator=(const CMap& cmap) {
deba@57
   619
        Parent::operator=(cmap);
alpar@209
   620
        return *this;
deba@57
   621
      }
deba@57
   622
deba@57
   623
    };
deba@57
   624
deba@57
   625
    template <typename _Value>
alpar@209
   626
    class ArcMap
deba@78
   627
      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
deba@78
   628
      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
deba@57
   629
kpeter@617
   630
    public:
kpeter@685
   631
      explicit ArcMap(const Graph& graph)
alpar@209
   632
        : Parent(graph) {}
alpar@209
   633
      ArcMap(const Graph& graph, const _Value& value)
alpar@209
   634
        : Parent(graph, value) {}
deba@57
   635
kpeter@263
   636
    private:
deba@57
   637
      ArcMap& operator=(const ArcMap& cmap) {
alpar@209
   638
        return operator=<ArcMap>(cmap);
deba@57
   639
      }
deba@57
   640
deba@57
   641
      template <typename CMap>
deba@57
   642
      ArcMap& operator=(const CMap& cmap) {
deba@57
   643
        Parent::operator=(cmap);
alpar@209
   644
        return *this;
deba@57
   645
      }
deba@57
   646
    };
deba@57
   647
deba@57
   648
deba@57
   649
    template <typename _Value>
alpar@209
   650
    class EdgeMap
deba@78
   651
      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
deba@78
   652
      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
deba@57
   653
kpeter@617
   654
    public:
kpeter@685
   655
      explicit EdgeMap(const Graph& graph)
alpar@209
   656
        : Parent(graph) {}
deba@57
   657
alpar@209
   658
      EdgeMap(const Graph& graph, const _Value& value)
alpar@209
   659
        : Parent(graph, value) {}
deba@57
   660
kpeter@263
   661
    private:
deba@57
   662
      EdgeMap& operator=(const EdgeMap& cmap) {
alpar@209
   663
        return operator=<EdgeMap>(cmap);
deba@57
   664
      }
deba@57
   665
deba@57
   666
      template <typename CMap>
deba@57
   667
      EdgeMap& operator=(const CMap& cmap) {
deba@57
   668
        Parent::operator=(cmap);
alpar@209
   669
        return *this;
deba@57
   670
      }
deba@57
   671
deba@57
   672
    };
deba@57
   673
deba@57
   674
    // Alteration extension
deba@57
   675
deba@57
   676
    Node addNode() {
deba@57
   677
      Node node = Parent::addNode();
deba@57
   678
      notifier(Node()).add(node);
deba@57
   679
      return node;
deba@57
   680
    }
deba@57
   681
deba@57
   682
    Edge addEdge(const Node& from, const Node& to) {
deba@57
   683
      Edge edge = Parent::addEdge(from, to);
deba@57
   684
      notifier(Edge()).add(edge);
deba@57
   685
      std::vector<Arc> ev;
deba@57
   686
      ev.push_back(Parent::direct(edge, true));
alpar@209
   687
      ev.push_back(Parent::direct(edge, false));
deba@57
   688
      notifier(Arc()).add(ev);
deba@57
   689
      return edge;
deba@57
   690
    }
alpar@209
   691
deba@57
   692
    void clear() {
deba@57
   693
      notifier(Arc()).clear();
deba@57
   694
      notifier(Edge()).clear();
deba@57
   695
      notifier(Node()).clear();
deba@57
   696
      Parent::clear();
deba@57
   697
    }
deba@57
   698
deba@78
   699
    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
alpar@209
   700
    void build(const Graph& graph, NodeRefMap& nodeRef,
deba@57
   701
               EdgeRefMap& edgeRef) {
deba@78
   702
      Parent::build(graph, nodeRef, edgeRef);
deba@57
   703
      notifier(Node()).build();
deba@57
   704
      notifier(Edge()).build();
deba@57
   705
      notifier(Arc()).build();
deba@57
   706
    }
deba@57
   707
deba@57
   708
    void erase(const Node& node) {
deba@57
   709
      Arc arc;
deba@57
   710
      Parent::firstOut(arc, node);
deba@57
   711
      while (arc != INVALID ) {
alpar@209
   712
        erase(arc);
alpar@209
   713
        Parent::firstOut(arc, node);
alpar@209
   714
      }
deba@57
   715
deba@57
   716
      Parent::firstIn(arc, node);
deba@57
   717
      while (arc != INVALID ) {
alpar@209
   718
        erase(arc);
alpar@209
   719
        Parent::firstIn(arc, node);
deba@57
   720
      }
deba@57
   721
deba@57
   722
      notifier(Node()).erase(node);
deba@57
   723
      Parent::erase(node);
deba@57
   724
    }
deba@57
   725
deba@57
   726
    void erase(const Edge& edge) {
deba@78
   727
      std::vector<Arc> av;
deba@78
   728
      av.push_back(Parent::direct(edge, true));
alpar@209
   729
      av.push_back(Parent::direct(edge, false));
deba@78
   730
      notifier(Arc()).erase(av);
deba@57
   731
      notifier(Edge()).erase(edge);
deba@57
   732
      Parent::erase(edge);
deba@57
   733
    }
deba@57
   734
deba@57
   735
    GraphExtender() {
alpar@209
   736
      node_notifier.setContainer(*this);
deba@57
   737
      arc_notifier.setContainer(*this);
deba@57
   738
      edge_notifier.setContainer(*this);
alpar@209
   739
    }
deba@57
   740
deba@57
   741
    ~GraphExtender() {
deba@57
   742
      edge_notifier.clear();
deba@57
   743
      arc_notifier.clear();
alpar@209
   744
      node_notifier.clear();
alpar@209
   745
    }
deba@57
   746
deba@57
   747
  };
deba@57
   748
deba@1019
   749
  // \ingroup _graphbits
deba@1019
   750
  //
deba@1019
   751
  // \brief Extender for the BpGraphs
deba@1019
   752
  template <typename Base>
deba@1019
   753
  class BpGraphExtender : public Base {
deba@1019
   754
    typedef Base Parent;
deba@1019
   755
deba@1019
   756
  public:
deba@1019
   757
deba@1019
   758
    typedef BpGraphExtender BpGraph;
deba@1019
   759
deba@1019
   760
    typedef True UndirectedTag;
deba@1019
   761
deba@1019
   762
    typedef typename Parent::Node Node;
deba@1025
   763
    typedef typename Parent::RedNode RedNode;
deba@1025
   764
    typedef typename Parent::BlueNode BlueNode;
deba@1019
   765
    typedef typename Parent::Arc Arc;
deba@1019
   766
    typedef typename Parent::Edge Edge;
deba@1019
   767
deba@1019
   768
    // BpGraph extension
deba@1019
   769
deba@1019
   770
    using Parent::first;
deba@1019
   771
    using Parent::next;
deba@1019
   772
    using Parent::id;
deba@1019
   773
deba@1019
   774
    int maxId(Node) const {
deba@1019
   775
      return Parent::maxNodeId();
deba@1019
   776
    }
deba@1019
   777
deba@1019
   778
    int maxId(RedNode) const {
deba@1019
   779
      return Parent::maxRedId();
deba@1019
   780
    }
deba@1019
   781
deba@1019
   782
    int maxId(BlueNode) const {
deba@1019
   783
      return Parent::maxBlueId();
deba@1019
   784
    }
deba@1019
   785
deba@1019
   786
    int maxId(Arc) const {
deba@1019
   787
      return Parent::maxArcId();
deba@1019
   788
    }
deba@1019
   789
deba@1019
   790
    int maxId(Edge) const {
deba@1019
   791
      return Parent::maxEdgeId();
deba@1019
   792
    }
deba@1019
   793
deba@1019
   794
    static Node fromId(int id, Node) {
deba@1019
   795
      return Parent::nodeFromId(id);
deba@1019
   796
    }
deba@1019
   797
deba@1019
   798
    static Arc fromId(int id, Arc) {
deba@1019
   799
      return Parent::arcFromId(id);
deba@1019
   800
    }
deba@1019
   801
deba@1019
   802
    static Edge fromId(int id, Edge) {
deba@1019
   803
      return Parent::edgeFromId(id);
deba@1019
   804
    }
deba@1019
   805
deba@1020
   806
    Node u(Edge e) const { return this->redNode(e); }
deba@1020
   807
    Node v(Edge e) const { return this->blueNode(e); }
deba@1020
   808
deba@1019
   809
    Node oppositeNode(const Node &n, const Edge &e) const {
deba@1020
   810
      if( n == u(e))
deba@1020
   811
        return v(e);
deba@1020
   812
      else if( n == v(e))
deba@1020
   813
        return u(e);
deba@1019
   814
      else
deba@1019
   815
        return INVALID;
deba@1019
   816
    }
deba@1019
   817
deba@1019
   818
    Arc oppositeArc(const Arc &arc) const {
deba@1019
   819
      return Parent::direct(arc, !Parent::direction(arc));
deba@1019
   820
    }
deba@1019
   821
deba@1019
   822
    using Parent::direct;
deba@1019
   823
    Arc direct(const Edge &edge, const Node &node) const {
deba@1020
   824
      return Parent::direct(edge, Parent::redNode(edge) == node);
deba@1019
   825
    }
deba@1019
   826
deba@1025
   827
    RedNode asRedNode(const Node& node) const {
deba@1025
   828
      if (node == INVALID || Parent::blue(node)) {
deba@1025
   829
        return INVALID;
deba@1025
   830
      } else {
deba@1025
   831
        return Parent::asRedNodeUnsafe(node);
deba@1025
   832
      }
deba@1025
   833
    }
deba@1025
   834
deba@1025
   835
    BlueNode asBlueNode(const Node& node) const {
deba@1025
   836
      if (node == INVALID || Parent::red(node)) {
deba@1025
   837
        return INVALID;
deba@1025
   838
      } else {
deba@1025
   839
        return Parent::asBlueNodeUnsafe(node);
deba@1025
   840
      }
deba@1025
   841
    }
deba@1025
   842
deba@1019
   843
    // Alterable extension
deba@1019
   844
deba@1019
   845
    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
alpar@1092
   846
    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
deba@1019
   847
    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
deba@1019
   848
    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
deba@1019
   849
    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
deba@1019
   850
deba@1019
   851
deba@1019
   852
  protected:
deba@1019
   853
deba@1019
   854
    mutable NodeNotifier node_notifier;
deba@1019
   855
    mutable RedNodeNotifier red_node_notifier;
deba@1019
   856
    mutable BlueNodeNotifier blue_node_notifier;
deba@1019
   857
    mutable ArcNotifier arc_notifier;
deba@1019
   858
    mutable EdgeNotifier edge_notifier;
deba@1019
   859
deba@1019
   860
  public:
deba@1019
   861
deba@1019
   862
    NodeNotifier& notifier(Node) const {
deba@1019
   863
      return node_notifier;
deba@1019
   864
    }
deba@1019
   865
deba@1019
   866
    RedNodeNotifier& notifier(RedNode) const {
deba@1019
   867
      return red_node_notifier;
deba@1019
   868
    }
deba@1019
   869
deba@1019
   870
    BlueNodeNotifier& notifier(BlueNode) const {
deba@1019
   871
      return blue_node_notifier;
deba@1019
   872
    }
deba@1019
   873
deba@1019
   874
    ArcNotifier& notifier(Arc) const {
deba@1019
   875
      return arc_notifier;
deba@1019
   876
    }
deba@1019
   877
deba@1019
   878
    EdgeNotifier& notifier(Edge) const {
deba@1019
   879
      return edge_notifier;
deba@1019
   880
    }
deba@1019
   881
deba@1019
   882
deba@1019
   883
deba@1019
   884
    class NodeIt : public Node {
deba@1019
   885
      const BpGraph* _graph;
deba@1019
   886
    public:
deba@1019
   887
deba@1019
   888
      NodeIt() {}
deba@1019
   889
deba@1019
   890
      NodeIt(Invalid i) : Node(i) { }
deba@1019
   891
deba@1019
   892
      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1019
   893
        _graph->first(static_cast<Node&>(*this));
deba@1019
   894
      }
deba@1019
   895
deba@1019
   896
      NodeIt(const BpGraph& graph, const Node& node)
deba@1019
   897
        : Node(node), _graph(&graph) {}
deba@1019
   898
deba@1019
   899
      NodeIt& operator++() {
deba@1019
   900
        _graph->next(*this);
deba@1019
   901
        return *this;
deba@1019
   902
      }
deba@1019
   903
deba@1019
   904
    };
deba@1019
   905
deba@1026
   906
    class RedNodeIt : public RedNode {
deba@1019
   907
      const BpGraph* _graph;
deba@1019
   908
    public:
deba@1019
   909
deba@1026
   910
      RedNodeIt() {}
deba@1019
   911
deba@1026
   912
      RedNodeIt(Invalid i) : RedNode(i) { }
deba@1019
   913
deba@1026
   914
      explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1025
   915
        _graph->first(static_cast<RedNode&>(*this));
deba@1019
   916
      }
deba@1019
   917
deba@1026
   918
      RedNodeIt(const BpGraph& graph, const RedNode& node)
deba@1025
   919
        : RedNode(node), _graph(&graph) {}
deba@1019
   920
deba@1026
   921
      RedNodeIt& operator++() {
deba@1025
   922
        _graph->next(static_cast<RedNode&>(*this));
deba@1019
   923
        return *this;
deba@1019
   924
      }
deba@1019
   925
deba@1019
   926
    };
deba@1019
   927
deba@1026
   928
    class BlueNodeIt : public BlueNode {
deba@1019
   929
      const BpGraph* _graph;
deba@1019
   930
    public:
deba@1019
   931
deba@1026
   932
      BlueNodeIt() {}
deba@1019
   933
deba@1026
   934
      BlueNodeIt(Invalid i) : BlueNode(i) { }
deba@1019
   935
deba@1026
   936
      explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1025
   937
        _graph->first(static_cast<BlueNode&>(*this));
deba@1019
   938
      }
deba@1019
   939
deba@1026
   940
      BlueNodeIt(const BpGraph& graph, const BlueNode& node)
deba@1025
   941
        : BlueNode(node), _graph(&graph) {}
deba@1019
   942
deba@1026
   943
      BlueNodeIt& operator++() {
deba@1025
   944
        _graph->next(static_cast<BlueNode&>(*this));
deba@1019
   945
        return *this;
deba@1019
   946
      }
deba@1019
   947
deba@1019
   948
    };
deba@1019
   949
deba@1019
   950
deba@1019
   951
    class ArcIt : public Arc {
deba@1019
   952
      const BpGraph* _graph;
deba@1019
   953
    public:
deba@1019
   954
deba@1019
   955
      ArcIt() { }
deba@1019
   956
deba@1019
   957
      ArcIt(Invalid i) : Arc(i) { }
deba@1019
   958
deba@1019
   959
      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
deba@1019
   960
        _graph->first(static_cast<Arc&>(*this));
deba@1019
   961
      }
deba@1019
   962
deba@1019
   963
      ArcIt(const BpGraph& graph, const Arc& arc) :
deba@1019
   964
        Arc(arc), _graph(&graph) { }
deba@1019
   965
deba@1019
   966
      ArcIt& operator++() {
deba@1019
   967
        _graph->next(*this);
deba@1019
   968
        return *this;
deba@1019
   969
      }
deba@1019
   970
deba@1019
   971
    };
deba@1019
   972
deba@1019
   973
deba@1019
   974
    class OutArcIt : public Arc {
deba@1019
   975
      const BpGraph* _graph;
deba@1019
   976
    public:
deba@1019
   977
deba@1019
   978
      OutArcIt() { }
deba@1019
   979
deba@1019
   980
      OutArcIt(Invalid i) : Arc(i) { }
deba@1019
   981
deba@1019
   982
      OutArcIt(const BpGraph& graph, const Node& node)
deba@1019
   983
        : _graph(&graph) {
deba@1019
   984
        _graph->firstOut(*this, node);
deba@1019
   985
      }
deba@1019
   986
deba@1019
   987
      OutArcIt(const BpGraph& graph, const Arc& arc)
deba@1019
   988
        : Arc(arc), _graph(&graph) {}
deba@1019
   989
deba@1019
   990
      OutArcIt& operator++() {
deba@1019
   991
        _graph->nextOut(*this);
deba@1019
   992
        return *this;
deba@1019
   993
      }
deba@1019
   994
deba@1019
   995
    };
deba@1019
   996
deba@1019
   997
deba@1019
   998
    class InArcIt : public Arc {
deba@1019
   999
      const BpGraph* _graph;
deba@1019
  1000
    public:
deba@1019
  1001
deba@1019
  1002
      InArcIt() { }
deba@1019
  1003
deba@1019
  1004
      InArcIt(Invalid i) : Arc(i) { }
deba@1019
  1005
deba@1019
  1006
      InArcIt(const BpGraph& graph, const Node& node)
deba@1019
  1007
        : _graph(&graph) {
deba@1019
  1008
        _graph->firstIn(*this, node);
deba@1019
  1009
      }
deba@1019
  1010
deba@1019
  1011
      InArcIt(const BpGraph& graph, const Arc& arc) :
deba@1019
  1012
        Arc(arc), _graph(&graph) {}
deba@1019
  1013
deba@1019
  1014
      InArcIt& operator++() {
deba@1019
  1015
        _graph->nextIn(*this);
deba@1019
  1016
        return *this;
deba@1019
  1017
      }
deba@1019
  1018
deba@1019
  1019
    };
deba@1019
  1020
deba@1019
  1021
deba@1019
  1022
    class EdgeIt : public Parent::Edge {
deba@1019
  1023
      const BpGraph* _graph;
deba@1019
  1024
    public:
deba@1019
  1025
deba@1019
  1026
      EdgeIt() { }
deba@1019
  1027
deba@1019
  1028
      EdgeIt(Invalid i) : Edge(i) { }
deba@1019
  1029
deba@1019
  1030
      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
deba@1019
  1031
        _graph->first(static_cast<Edge&>(*this));
deba@1019
  1032
      }
deba@1019
  1033
deba@1019
  1034
      EdgeIt(const BpGraph& graph, const Edge& edge) :
deba@1019
  1035
        Edge(edge), _graph(&graph) { }
deba@1019
  1036
deba@1019
  1037
      EdgeIt& operator++() {
deba@1019
  1038
        _graph->next(*this);
deba@1019
  1039
        return *this;
deba@1019
  1040
      }
deba@1019
  1041
deba@1019
  1042
    };
deba@1019
  1043
deba@1019
  1044
    class IncEdgeIt : public Parent::Edge {
deba@1019
  1045
      friend class BpGraphExtender;
deba@1019
  1046
      const BpGraph* _graph;
deba@1019
  1047
      bool _direction;
deba@1019
  1048
    public:
deba@1019
  1049
deba@1019
  1050
      IncEdgeIt() { }
deba@1019
  1051
deba@1019
  1052
      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
deba@1019
  1053
deba@1019
  1054
      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
deba@1019
  1055
        _graph->firstInc(*this, _direction, node);
deba@1019
  1056
      }
deba@1019
  1057
deba@1019
  1058
      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
deba@1019
  1059
        : _graph(&graph), Edge(edge) {
deba@1019
  1060
        _direction = (_graph->source(edge) == node);
deba@1019
  1061
      }
deba@1019
  1062
deba@1019
  1063
      IncEdgeIt& operator++() {
deba@1019
  1064
        _graph->nextInc(*this, _direction);
deba@1019
  1065
        return *this;
deba@1019
  1066
      }
deba@1019
  1067
    };
deba@1019
  1068
deba@1019
  1069
    // \brief Base node of the iterator
deba@1019
  1070
    //
deba@1019
  1071
    // Returns the base node (ie. the source in this case) of the iterator
deba@1019
  1072
    Node baseNode(const OutArcIt &arc) const {
deba@1019
  1073
      return Parent::source(static_cast<const Arc&>(arc));
deba@1019
  1074
    }
deba@1019
  1075
    // \brief Running node of the iterator
deba@1019
  1076
    //
deba@1019
  1077
    // Returns the running node (ie. the target in this case) of the
deba@1019
  1078
    // iterator
deba@1019
  1079
    Node runningNode(const OutArcIt &arc) const {
deba@1019
  1080
      return Parent::target(static_cast<const Arc&>(arc));
deba@1019
  1081
    }
deba@1019
  1082
deba@1019
  1083
    // \brief Base node of the iterator
deba@1019
  1084
    //
deba@1019
  1085
    // Returns the base node (ie. the target in this case) of the iterator
deba@1019
  1086
    Node baseNode(const InArcIt &arc) const {
deba@1019
  1087
      return Parent::target(static_cast<const Arc&>(arc));
deba@1019
  1088
    }
deba@1019
  1089
    // \brief Running node of the iterator
deba@1019
  1090
    //
deba@1019
  1091
    // Returns the running node (ie. the source in this case) of the
deba@1019
  1092
    // iterator
deba@1019
  1093
    Node runningNode(const InArcIt &arc) const {
deba@1019
  1094
      return Parent::source(static_cast<const Arc&>(arc));
deba@1019
  1095
    }
deba@1019
  1096
deba@1019
  1097
    // Base node of the iterator
deba@1019
  1098
    //
deba@1019
  1099
    // Returns the base node of the iterator
deba@1019
  1100
    Node baseNode(const IncEdgeIt &edge) const {
deba@1019
  1101
      return edge._direction ? this->u(edge) : this->v(edge);
deba@1019
  1102
    }
deba@1019
  1103
    // Running node of the iterator
deba@1019
  1104
    //
deba@1019
  1105
    // Returns the running node of the iterator
deba@1019
  1106
    Node runningNode(const IncEdgeIt &edge) const {
deba@1019
  1107
      return edge._direction ? this->v(edge) : this->u(edge);
deba@1019
  1108
    }
deba@1019
  1109
deba@1019
  1110
    // Mappable extension
deba@1019
  1111
deba@1019
  1112
    template <typename _Value>
deba@1019
  1113
    class NodeMap
deba@1019
  1114
      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
deba@1019
  1115
      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
deba@1019
  1116
deba@1019
  1117
    public:
deba@1019
  1118
      explicit NodeMap(const BpGraph& bpgraph)
deba@1019
  1119
        : Parent(bpgraph) {}
deba@1019
  1120
      NodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019
  1121
        : Parent(bpgraph, value) {}
deba@1019
  1122
deba@1019
  1123
    private:
deba@1019
  1124
      NodeMap& operator=(const NodeMap& cmap) {
deba@1019
  1125
        return operator=<NodeMap>(cmap);
deba@1019
  1126
      }
deba@1019
  1127
deba@1019
  1128
      template <typename CMap>
deba@1019
  1129
      NodeMap& operator=(const CMap& cmap) {
deba@1019
  1130
        Parent::operator=(cmap);
deba@1019
  1131
        return *this;
deba@1019
  1132
      }
deba@1019
  1133
deba@1019
  1134
    };
deba@1019
  1135
deba@1019
  1136
    template <typename _Value>
deba@1026
  1137
    class RedNodeMap
deba@1019
  1138
      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
deba@1019
  1139
      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
deba@1019
  1140
deba@1019
  1141
    public:
deba@1026
  1142
      explicit RedNodeMap(const BpGraph& bpgraph)
deba@1019
  1143
        : Parent(bpgraph) {}
deba@1026
  1144
      RedNodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019
  1145
        : Parent(bpgraph, value) {}
deba@1019
  1146
deba@1019
  1147
    private:
deba@1026
  1148
      RedNodeMap& operator=(const RedNodeMap& cmap) {
deba@1026
  1149
        return operator=<RedNodeMap>(cmap);
deba@1019
  1150
      }
deba@1019
  1151
deba@1019
  1152
      template <typename CMap>
deba@1026
  1153
      RedNodeMap& operator=(const CMap& cmap) {
deba@1019
  1154
        Parent::operator=(cmap);
deba@1019
  1155
        return *this;
deba@1019
  1156
      }
deba@1019
  1157
deba@1019
  1158
    };
deba@1019
  1159
deba@1019
  1160
    template <typename _Value>
deba@1026
  1161
    class BlueNodeMap
deba@1019
  1162
      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
deba@1019
  1163
      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
deba@1019
  1164
deba@1019
  1165
    public:
deba@1026
  1166
      explicit BlueNodeMap(const BpGraph& bpgraph)
deba@1019
  1167
        : Parent(bpgraph) {}
deba@1026
  1168
      BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019
  1169
        : Parent(bpgraph, value) {}
deba@1019
  1170
deba@1019
  1171
    private:
deba@1026
  1172
      BlueNodeMap& operator=(const BlueNodeMap& cmap) {
deba@1026
  1173
        return operator=<BlueNodeMap>(cmap);
deba@1019
  1174
      }
deba@1019
  1175
deba@1019
  1176
      template <typename CMap>
deba@1026
  1177
      BlueNodeMap& operator=(const CMap& cmap) {
deba@1019
  1178
        Parent::operator=(cmap);
deba@1019
  1179
        return *this;
deba@1019
  1180
      }
deba@1019
  1181
deba@1019
  1182
    };
deba@1019
  1183
deba@1019
  1184
    template <typename _Value>
deba@1019
  1185
    class ArcMap
deba@1019
  1186
      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
deba@1019
  1187
      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
deba@1019
  1188
deba@1019
  1189
    public:
deba@1019
  1190
      explicit ArcMap(const BpGraph& graph)
deba@1019
  1191
        : Parent(graph) {}
deba@1019
  1192
      ArcMap(const BpGraph& graph, const _Value& value)
deba@1019
  1193
        : Parent(graph, value) {}
deba@1019
  1194
deba@1019
  1195
    private:
deba@1019
  1196
      ArcMap& operator=(const ArcMap& cmap) {
deba@1019
  1197
        return operator=<ArcMap>(cmap);
deba@1019
  1198
      }
deba@1019
  1199
deba@1019
  1200
      template <typename CMap>
deba@1019
  1201
      ArcMap& operator=(const CMap& cmap) {
deba@1019
  1202
        Parent::operator=(cmap);
deba@1019
  1203
        return *this;
deba@1019
  1204
      }
deba@1019
  1205
    };
deba@1019
  1206
deba@1019
  1207
deba@1019
  1208
    template <typename _Value>
deba@1019
  1209
    class EdgeMap
deba@1019
  1210
      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
deba@1019
  1211
      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
deba@1019
  1212
deba@1019
  1213
    public:
deba@1019
  1214
      explicit EdgeMap(const BpGraph& graph)
deba@1019
  1215
        : Parent(graph) {}
deba@1019
  1216
deba@1019
  1217
      EdgeMap(const BpGraph& graph, const _Value& value)
deba@1019
  1218
        : Parent(graph, value) {}
deba@1019
  1219
deba@1019
  1220
    private:
deba@1019
  1221
      EdgeMap& operator=(const EdgeMap& cmap) {
deba@1019
  1222
        return operator=<EdgeMap>(cmap);
deba@1019
  1223
      }
deba@1019
  1224
deba@1019
  1225
      template <typename CMap>
deba@1019
  1226
      EdgeMap& operator=(const CMap& cmap) {
deba@1019
  1227
        Parent::operator=(cmap);
deba@1019
  1228
        return *this;
deba@1019
  1229
      }
deba@1019
  1230
deba@1019
  1231
    };
deba@1019
  1232
deba@1019
  1233
    // Alteration extension
deba@1019
  1234
deba@1025
  1235
    RedNode addRedNode() {
deba@1025
  1236
      RedNode node = Parent::addRedNode();
deba@1019
  1237
      notifier(RedNode()).add(node);
deba@1019
  1238
      notifier(Node()).add(node);
deba@1019
  1239
      return node;
deba@1019
  1240
    }
deba@1019
  1241
deba@1025
  1242
    BlueNode addBlueNode() {
deba@1025
  1243
      BlueNode node = Parent::addBlueNode();
deba@1019
  1244
      notifier(BlueNode()).add(node);
deba@1019
  1245
      notifier(Node()).add(node);
deba@1019
  1246
      return node;
deba@1019
  1247
    }
deba@1019
  1248
deba@1025
  1249
    Edge addEdge(const RedNode& from, const BlueNode& to) {
deba@1019
  1250
      Edge edge = Parent::addEdge(from, to);
deba@1019
  1251
      notifier(Edge()).add(edge);
deba@1019
  1252
      std::vector<Arc> av;
deba@1019
  1253
      av.push_back(Parent::direct(edge, true));
deba@1019
  1254
      av.push_back(Parent::direct(edge, false));
deba@1019
  1255
      notifier(Arc()).add(av);
deba@1019
  1256
      return edge;
deba@1019
  1257
    }
deba@1019
  1258
deba@1019
  1259
    void clear() {
deba@1019
  1260
      notifier(Arc()).clear();
deba@1019
  1261
      notifier(Edge()).clear();
deba@1019
  1262
      notifier(Node()).clear();
deba@1019
  1263
      notifier(BlueNode()).clear();
deba@1019
  1264
      notifier(RedNode()).clear();
deba@1019
  1265
      Parent::clear();
deba@1019
  1266
    }
deba@1019
  1267
deba@1019
  1268
    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
deba@1019
  1269
    void build(const BpGraph& graph, NodeRefMap& nodeRef,
deba@1019
  1270
               EdgeRefMap& edgeRef) {
deba@1019
  1271
      Parent::build(graph, nodeRef, edgeRef);
deba@1019
  1272
      notifier(RedNode()).build();
deba@1019
  1273
      notifier(BlueNode()).build();
deba@1019
  1274
      notifier(Node()).build();
deba@1019
  1275
      notifier(Edge()).build();
deba@1019
  1276
      notifier(Arc()).build();
deba@1019
  1277
    }
deba@1019
  1278
deba@1019
  1279
    void erase(const Node& node) {
deba@1019
  1280
      Arc arc;
deba@1019
  1281
      Parent::firstOut(arc, node);
deba@1019
  1282
      while (arc != INVALID ) {
deba@1019
  1283
        erase(arc);
deba@1019
  1284
        Parent::firstOut(arc, node);
deba@1019
  1285
      }
deba@1019
  1286
deba@1019
  1287
      Parent::firstIn(arc, node);
deba@1019
  1288
      while (arc != INVALID ) {
deba@1019
  1289
        erase(arc);
deba@1019
  1290
        Parent::firstIn(arc, node);
deba@1019
  1291
      }
deba@1019
  1292
deba@1019
  1293
      if (Parent::red(node)) {
deba@1025
  1294
        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
deba@1019
  1295
      } else {
deba@1025
  1296
        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
deba@1019
  1297
      }
deba@1019
  1298
deba@1019
  1299
      notifier(Node()).erase(node);
deba@1019
  1300
      Parent::erase(node);
deba@1019
  1301
    }
deba@1019
  1302
deba@1019
  1303
    void erase(const Edge& edge) {
deba@1019
  1304
      std::vector<Arc> av;
deba@1019
  1305
      av.push_back(Parent::direct(edge, true));
deba@1019
  1306
      av.push_back(Parent::direct(edge, false));
deba@1019
  1307
      notifier(Arc()).erase(av);
deba@1019
  1308
      notifier(Edge()).erase(edge);
deba@1019
  1309
      Parent::erase(edge);
deba@1019
  1310
    }
deba@1019
  1311
deba@1019
  1312
    BpGraphExtender() {
deba@1019
  1313
      red_node_notifier.setContainer(*this);
deba@1019
  1314
      blue_node_notifier.setContainer(*this);
deba@1019
  1315
      node_notifier.setContainer(*this);
deba@1019
  1316
      arc_notifier.setContainer(*this);
deba@1019
  1317
      edge_notifier.setContainer(*this);
deba@1019
  1318
    }
deba@1019
  1319
deba@1019
  1320
    ~BpGraphExtender() {
deba@1019
  1321
      edge_notifier.clear();
deba@1019
  1322
      arc_notifier.clear();
deba@1019
  1323
      node_notifier.clear();
deba@1019
  1324
      blue_node_notifier.clear();
deba@1019
  1325
      red_node_notifier.clear();
deba@1019
  1326
    }
deba@1019
  1327
deba@1019
  1328
  };
deba@1019
  1329
deba@57
  1330
}
deba@57
  1331
deba@57
  1332
#endif