lemon/list_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 15 May 2019 13:41:19 +0200
branch1.3
changeset 1425 ed2c21cbd6ef
parent 1357 2126945deb6a
permissions -rw-r--r--
Backport relevant part of bugfix [4add05447ca0] to branch 1.3 (#623)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@39
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@39
     4
 *
alpar@1270
     5
 * Copyright (C) 2003-2013
alpar@39
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@39
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@39
     8
 *
alpar@39
     9
 * Permission to use, modify and distribute this software is granted
alpar@39
    10
 * provided that this copyright notice appears in all copies. For
alpar@39
    11
 * precise terms see the accompanying LICENSE file.
alpar@39
    12
 *
alpar@39
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@39
    14
 * express or implied, and with no claim as to its suitability for any
alpar@39
    15
 * purpose.
alpar@39
    16
 *
alpar@39
    17
 */
alpar@39
    18
deba@57
    19
#ifndef LEMON_LIST_GRAPH_H
deba@57
    20
#define LEMON_LIST_GRAPH_H
deba@57
    21
deba@57
    22
///\ingroup graphs
deba@57
    23
///\file
kpeter@782
    24
///\brief ListDigraph and ListGraph classes.
deba@57
    25
deba@220
    26
#include <lemon/core.h>
deba@220
    27
#include <lemon/error.h>
deba@57
    28
#include <lemon/bits/graph_extender.h>
deba@57
    29
deba@57
    30
#include <vector>
deba@57
    31
#include <list>
deba@57
    32
deba@57
    33
namespace lemon {
deba@57
    34
kpeter@785
    35
  class ListDigraph;
kpeter@785
    36
deba@57
    37
  class ListDigraphBase {
deba@57
    38
deba@57
    39
  protected:
deba@57
    40
    struct NodeT {
deba@57
    41
      int first_in, first_out;
deba@57
    42
      int prev, next;
deba@57
    43
    };
alpar@209
    44
deba@57
    45
    struct ArcT {
deba@57
    46
      int target, source;
deba@57
    47
      int prev_in, prev_out;
deba@57
    48
      int next_in, next_out;
deba@57
    49
    };
deba@57
    50
deba@57
    51
    std::vector<NodeT> nodes;
deba@57
    52
deba@57
    53
    int first_node;
deba@57
    54
deba@57
    55
    int first_free_node;
deba@57
    56
deba@57
    57
    std::vector<ArcT> arcs;
deba@57
    58
deba@57
    59
    int first_free_arc;
alpar@209
    60
deba@57
    61
  public:
alpar@209
    62
deba@57
    63
    typedef ListDigraphBase Digraph;
alpar@209
    64
deba@57
    65
    class Node {
deba@57
    66
      friend class ListDigraphBase;
kpeter@785
    67
      friend class ListDigraph;
deba@57
    68
    protected:
deba@57
    69
deba@57
    70
      int id;
deba@57
    71
      explicit Node(int pid) { id = pid;}
deba@57
    72
deba@57
    73
    public:
deba@57
    74
      Node() {}
deba@57
    75
      Node (Invalid) { id = -1; }
deba@57
    76
      bool operator==(const Node& node) const {return id == node.id;}
deba@57
    77
      bool operator!=(const Node& node) const {return id != node.id;}
deba@57
    78
      bool operator<(const Node& node) const {return id < node.id;}
deba@57
    79
    };
deba@57
    80
deba@57
    81
    class Arc {
deba@57
    82
      friend class ListDigraphBase;
kpeter@785
    83
      friend class ListDigraph;
deba@57
    84
    protected:
deba@57
    85
deba@57
    86
      int id;
deba@57
    87
      explicit Arc(int pid) { id = pid;}
deba@57
    88
deba@57
    89
    public:
deba@57
    90
      Arc() {}
deba@57
    91
      Arc (Invalid) { id = -1; }
deba@57
    92
      bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57
    93
      bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57
    94
      bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57
    95
    };
deba@57
    96
deba@57
    97
deba@57
    98
deba@57
    99
    ListDigraphBase()
deba@57
   100
      : nodes(), first_node(-1),
alpar@209
   101
        first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57
   102
alpar@209
   103
alpar@209
   104
    int maxNodeId() const { return nodes.size()-1; }
deba@57
   105
    int maxArcId() const { return arcs.size()-1; }
deba@57
   106
deba@57
   107
    Node source(Arc e) const { return Node(arcs[e.id].source); }
deba@57
   108
    Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57
   109
deba@57
   110
alpar@209
   111
    void first(Node& node) const {
deba@57
   112
      node.id = first_node;
deba@57
   113
    }
deba@57
   114
deba@57
   115
    void next(Node& node) const {
deba@57
   116
      node.id = nodes[node.id].next;
deba@57
   117
    }
deba@57
   118
deba@57
   119
alpar@209
   120
    void first(Arc& arc) const {
deba@57
   121
      int n;
alpar@209
   122
      for(n = first_node;
kpeter@786
   123
          n != -1 && nodes[n].first_out == -1;
alpar@209
   124
          n = nodes[n].next) {}
kpeter@786
   125
      arc.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57
   126
    }
deba@57
   127
deba@57
   128
    void next(Arc& arc) const {
kpeter@786
   129
      if (arcs[arc.id].next_out != -1) {
kpeter@786
   130
        arc.id = arcs[arc.id].next_out;
deba@57
   131
      } else {
alpar@209
   132
        int n;
kpeter@786
   133
        for(n = nodes[arcs[arc.id].source].next;
kpeter@786
   134
            n != -1 && nodes[n].first_out == -1;
alpar@209
   135
            n = nodes[n].next) {}
kpeter@786
   136
        arc.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209
   137
      }
deba@57
   138
    }
deba@57
   139
deba@57
   140
    void firstOut(Arc &e, const Node& v) const {
deba@57
   141
      e.id = nodes[v.id].first_out;
deba@57
   142
    }
deba@57
   143
    void nextOut(Arc &e) const {
deba@57
   144
      e.id=arcs[e.id].next_out;
deba@57
   145
    }
deba@57
   146
deba@57
   147
    void firstIn(Arc &e, const Node& v) const {
deba@57
   148
      e.id = nodes[v.id].first_in;
deba@57
   149
    }
deba@57
   150
    void nextIn(Arc &e) const {
deba@57
   151
      e.id=arcs[e.id].next_in;
deba@57
   152
    }
deba@57
   153
alpar@209
   154
deba@57
   155
    static int id(Node v) { return v.id; }
deba@57
   156
    static int id(Arc e) { return e.id; }
deba@57
   157
deba@57
   158
    static Node nodeFromId(int id) { return Node(id);}
deba@57
   159
    static Arc arcFromId(int id) { return Arc(id);}
deba@57
   160
alpar@209
   161
    bool valid(Node n) const {
alpar@209
   162
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209
   163
        nodes[n.id].prev != -2;
deba@149
   164
    }
deba@149
   165
alpar@209
   166
    bool valid(Arc a) const {
alpar@209
   167
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209
   168
        arcs[a.id].prev_in != -2;
deba@149
   169
    }
deba@149
   170
alpar@209
   171
    Node addNode() {
deba@57
   172
      int n;
alpar@209
   173
deba@57
   174
      if(first_free_node==-1) {
alpar@209
   175
        n = nodes.size();
alpar@209
   176
        nodes.push_back(NodeT());
deba@57
   177
      } else {
alpar@209
   178
        n = first_free_node;
alpar@209
   179
        first_free_node = nodes[n].next;
deba@57
   180
      }
alpar@209
   181
deba@57
   182
      nodes[n].next = first_node;
deba@57
   183
      if(first_node != -1) nodes[first_node].prev = n;
deba@57
   184
      first_node = n;
deba@57
   185
      nodes[n].prev = -1;
alpar@209
   186
deba@57
   187
      nodes[n].first_in = nodes[n].first_out = -1;
alpar@209
   188
deba@57
   189
      return Node(n);
deba@57
   190
    }
alpar@209
   191
deba@57
   192
    Arc addArc(Node u, Node v) {
alpar@209
   193
      int n;
deba@57
   194
deba@57
   195
      if (first_free_arc == -1) {
alpar@209
   196
        n = arcs.size();
alpar@209
   197
        arcs.push_back(ArcT());
deba@57
   198
      } else {
alpar@209
   199
        n = first_free_arc;
alpar@209
   200
        first_free_arc = arcs[n].next_in;
deba@57
   201
      }
alpar@209
   202
alpar@209
   203
      arcs[n].source = u.id;
deba@57
   204
      arcs[n].target = v.id;
deba@57
   205
deba@57
   206
      arcs[n].next_out = nodes[u.id].first_out;
deba@57
   207
      if(nodes[u.id].first_out != -1) {
alpar@209
   208
        arcs[nodes[u.id].first_out].prev_out = n;
deba@57
   209
      }
alpar@209
   210
deba@57
   211
      arcs[n].next_in = nodes[v.id].first_in;
deba@57
   212
      if(nodes[v.id].first_in != -1) {
alpar@209
   213
        arcs[nodes[v.id].first_in].prev_in = n;
deba@57
   214
      }
alpar@209
   215
deba@57
   216
      arcs[n].prev_in = arcs[n].prev_out = -1;
alpar@209
   217
deba@57
   218
      nodes[u.id].first_out = nodes[v.id].first_in = n;
deba@57
   219
deba@57
   220
      return Arc(n);
deba@57
   221
    }
alpar@209
   222
deba@57
   223
    void erase(const Node& node) {
deba@57
   224
      int n = node.id;
alpar@209
   225
deba@57
   226
      if(nodes[n].next != -1) {
alpar@209
   227
        nodes[nodes[n].next].prev = nodes[n].prev;
deba@57
   228
      }
alpar@209
   229
deba@57
   230
      if(nodes[n].prev != -1) {
alpar@209
   231
        nodes[nodes[n].prev].next = nodes[n].next;
deba@57
   232
      } else {
alpar@209
   233
        first_node = nodes[n].next;
deba@57
   234
      }
alpar@209
   235
deba@57
   236
      nodes[n].next = first_free_node;
deba@57
   237
      first_free_node = n;
deba@149
   238
      nodes[n].prev = -2;
deba@57
   239
deba@57
   240
    }
alpar@209
   241
deba@57
   242
    void erase(const Arc& arc) {
deba@57
   243
      int n = arc.id;
alpar@209
   244
deba@57
   245
      if(arcs[n].next_in!=-1) {
alpar@209
   246
        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
deba@57
   247
      }
deba@57
   248
deba@57
   249
      if(arcs[n].prev_in!=-1) {
alpar@209
   250
        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
deba@57
   251
      } else {
alpar@209
   252
        nodes[arcs[n].target].first_in = arcs[n].next_in;
deba@57
   253
      }
deba@57
   254
alpar@209
   255
deba@57
   256
      if(arcs[n].next_out!=-1) {
alpar@209
   257
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209
   258
      }
deba@57
   259
deba@57
   260
      if(arcs[n].prev_out!=-1) {
alpar@209
   261
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57
   262
      } else {
alpar@209
   263
        nodes[arcs[n].source].first_out = arcs[n].next_out;
deba@57
   264
      }
alpar@209
   265
deba@57
   266
      arcs[n].next_in = first_free_arc;
deba@149
   267
      first_free_arc = n;
deba@149
   268
      arcs[n].prev_in = -2;
deba@57
   269
    }
deba@57
   270
deba@57
   271
    void clear() {
deba@57
   272
      arcs.clear();
deba@57
   273
      nodes.clear();
deba@57
   274
      first_node = first_free_node = first_free_arc = -1;
deba@57
   275
    }
deba@57
   276
deba@57
   277
  protected:
alpar@209
   278
    void changeTarget(Arc e, Node n)
deba@57
   279
    {
deba@57
   280
      if(arcs[e.id].next_in != -1)
alpar@209
   281
        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
deba@57
   282
      if(arcs[e.id].prev_in != -1)
alpar@209
   283
        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
deba@57
   284
      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
deba@57
   285
      if (nodes[n.id].first_in != -1) {
alpar@209
   286
        arcs[nodes[n.id].first_in].prev_in = e.id;
deba@57
   287
      }
deba@57
   288
      arcs[e.id].target = n.id;
deba@57
   289
      arcs[e.id].prev_in = -1;
deba@57
   290
      arcs[e.id].next_in = nodes[n.id].first_in;
deba@57
   291
      nodes[n.id].first_in = e.id;
deba@57
   292
    }
alpar@209
   293
    void changeSource(Arc e, Node n)
deba@57
   294
    {
deba@57
   295
      if(arcs[e.id].next_out != -1)
alpar@209
   296
        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
deba@57
   297
      if(arcs[e.id].prev_out != -1)
alpar@209
   298
        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
deba@57
   299
      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
deba@57
   300
      if (nodes[n.id].first_out != -1) {
alpar@209
   301
        arcs[nodes[n.id].first_out].prev_out = e.id;
deba@57
   302
      }
deba@57
   303
      arcs[e.id].source = n.id;
deba@57
   304
      arcs[e.id].prev_out = -1;
deba@57
   305
      arcs[e.id].next_out = nodes[n.id].first_out;
deba@57
   306
      nodes[n.id].first_out = e.id;
deba@57
   307
    }
deba@57
   308
deba@57
   309
  };
deba@57
   310
deba@57
   311
  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
deba@57
   312
kpeter@73
   313
  /// \addtogroup graphs
deba@57
   314
  /// @{
deba@57
   315
alpar@209
   316
  ///A general directed graph structure.
deba@57
   317
kpeter@782
   318
  ///\ref ListDigraph is a versatile and fast directed graph
kpeter@782
   319
  ///implementation based on linked lists that are stored in
alpar@209
   320
  ///\c std::vector structures.
deba@57
   321
  ///
kpeter@782
   322
  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
kpeter@782
   323
  ///and it also provides several useful additional functionalities.
kpeter@782
   324
  ///Most of its member functions and nested classes are documented
kpeter@73
   325
  ///only in the concept class.
deba@57
   326
  ///
kpeter@834
   327
  ///This class provides only linear time counting for nodes and arcs.
kpeter@834
   328
  ///
kpeter@73
   329
  ///\sa concepts::Digraph
kpeter@782
   330
  ///\sa ListGraph
deba@57
   331
  class ListDigraph : public ExtendedListDigraphBase {
kpeter@664
   332
    typedef ExtendedListDigraphBase Parent;
kpeter@664
   333
deba@57
   334
  private:
kpeter@782
   335
    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
deba@57
   336
    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
kpeter@782
   337
    /// \brief Assignment of a digraph to another one is \e not allowed.
kpeter@782
   338
    /// Use DigraphCopy instead.
deba@57
   339
    void operator=(const ListDigraph &) {}
deba@57
   340
  public:
deba@57
   341
deba@57
   342
    /// Constructor
alpar@209
   343
deba@57
   344
    /// Constructor.
deba@57
   345
    ///
deba@57
   346
    ListDigraph() {}
deba@57
   347
deba@57
   348
    ///Add a new node to the digraph.
alpar@209
   349
kpeter@782
   350
    ///This function adds a new node to the digraph.
kpeter@606
   351
    ///\return The new node.
deba@57
   352
    Node addNode() { return Parent::addNode(); }
deba@57
   353
deba@57
   354
    ///Add a new arc to the digraph.
alpar@209
   355
kpeter@782
   356
    ///This function adds a new arc to the digraph with source node \c s
deba@57
   357
    ///and target node \c t.
kpeter@606
   358
    ///\return The new arc.
kpeter@782
   359
    Arc addArc(Node s, Node t) {
alpar@209
   360
      return Parent::addArc(s, t);
deba@57
   361
    }
deba@57
   362
deba@234
   363
    ///\brief Erase a node from the digraph.
deba@234
   364
    ///
kpeter@834
   365
    ///This function erases the given node along with its outgoing and
kpeter@834
   366
    ///incoming arcs from the digraph.
kpeter@834
   367
    ///
kpeter@834
   368
    ///\note All iterators referencing the removed node or the connected
kpeter@834
   369
    ///arcs are invalidated, of course.
kpeter@782
   370
    void erase(Node n) { Parent::erase(n); }
deba@234
   371
deba@234
   372
    ///\brief Erase an arc from the digraph.
deba@234
   373
    ///
kpeter@782
   374
    ///This function erases the given arc from the digraph.
kpeter@834
   375
    ///
kpeter@834
   376
    ///\note All iterators referencing the removed arc are invalidated,
kpeter@834
   377
    ///of course.
kpeter@782
   378
    void erase(Arc a) { Parent::erase(a); }
deba@234
   379
deba@149
   380
    /// Node validity check
deba@149
   381
kpeter@782
   382
    /// This function gives back \c true if the given node is valid,
kpeter@782
   383
    /// i.e. it is a real node of the digraph.
deba@149
   384
    ///
kpeter@782
   385
    /// \warning A removed node could become valid again if new nodes are
kpeter@782
   386
    /// added to the digraph.
deba@149
   387
    bool valid(Node n) const { return Parent::valid(n); }
deba@149
   388
deba@149
   389
    /// Arc validity check
deba@149
   390
kpeter@782
   391
    /// This function gives back \c true if the given arc is valid,
kpeter@782
   392
    /// i.e. it is a real arc of the digraph.
deba@149
   393
    ///
kpeter@782
   394
    /// \warning A removed arc could become valid again if new arcs are
kpeter@782
   395
    /// added to the digraph.
deba@149
   396
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
   397
kpeter@782
   398
    /// Change the target node of an arc
deba@57
   399
kpeter@782
   400
    /// This function changes the target node of the given arc \c a to \c n.
deba@57
   401
    ///
kpeter@782
   402
    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
kpeter@833
   403
    ///arc remain valid, but \c InArcIt iterators are invalidated.
kpeter@73
   404
    ///
deba@57
   405
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   406
    ///feature.
deba@235
   407
    void changeTarget(Arc a, Node n) {
deba@235
   408
      Parent::changeTarget(a,n);
deba@57
   409
    }
kpeter@782
   410
    /// Change the source node of an arc
deba@57
   411
kpeter@782
   412
    /// This function changes the source node of the given arc \c a to \c n.
deba@57
   413
    ///
kpeter@782
   414
    ///\note \c InArcIt iterators referencing the changed arc remain
kpeter@833
   415
    ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
kpeter@73
   416
    ///
deba@57
   417
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   418
    ///feature.
deba@235
   419
    void changeSource(Arc a, Node n) {
deba@235
   420
      Parent::changeSource(a,n);
deba@57
   421
    }
deba@57
   422
kpeter@782
   423
    /// Reverse the direction of an arc.
deba@57
   424
kpeter@782
   425
    /// This function reverses the direction of the given arc.
kpeter@782
   426
    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
kpeter@782
   427
    ///the changed arc are invalidated.
kpeter@73
   428
    ///
deba@57
   429
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   430
    ///feature.
kpeter@782
   431
    void reverseArc(Arc a) {
kpeter@782
   432
      Node t=target(a);
kpeter@782
   433
      changeTarget(a,source(a));
kpeter@782
   434
      changeSource(a,t);
deba@57
   435
    }
deba@57
   436
deba@57
   437
    ///Contract two nodes.
deba@57
   438
kpeter@782
   439
    ///This function contracts the given two nodes.
kpeter@782
   440
    ///Node \c v is removed, but instead of deleting its
kpeter@782
   441
    ///incident arcs, they are joined to node \c u.
kpeter@782
   442
    ///If the last parameter \c r is \c true (this is the default value),
kpeter@782
   443
    ///then the newly created loops are removed.
deba@57
   444
    ///
kpeter@782
   445
    ///\note The moved arcs are joined to node \c u using changeSource()
kpeter@782
   446
    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
kpeter@782
   447
    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
kpeter@1217
   448
    ///iterators are invalidated for the incoming arcs of \c v.
alpar@956
   449
    ///Moreover all iterators referencing node \c v or the removed
kpeter@782
   450
    ///loops are also invalidated. Other iterators remain valid.
kpeter@73
   451
    ///
deba@57
   452
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   453
    ///feature.
kpeter@782
   454
    void contract(Node u, Node v, bool r = true)
deba@57
   455
    {
kpeter@782
   456
      for(OutArcIt e(*this,v);e!=INVALID;) {
alpar@209
   457
        OutArcIt f=e;
alpar@209
   458
        ++f;
kpeter@782
   459
        if(r && target(e)==u) erase(e);
kpeter@782
   460
        else changeSource(e,u);
alpar@209
   461
        e=f;
deba@57
   462
      }
kpeter@782
   463
      for(InArcIt e(*this,v);e!=INVALID;) {
alpar@209
   464
        InArcIt f=e;
alpar@209
   465
        ++f;
kpeter@782
   466
        if(r && source(e)==u) erase(e);
kpeter@782
   467
        else changeTarget(e,u);
alpar@209
   468
        e=f;
deba@57
   469
      }
kpeter@782
   470
      erase(v);
deba@57
   471
    }
deba@57
   472
deba@57
   473
    ///Split a node.
deba@57
   474
kpeter@782
   475
    ///This function splits the given node. First, a new node is added
kpeter@782
   476
    ///to the digraph, then the source of each outgoing arc of node \c n
kpeter@782
   477
    ///is moved to this new node.
kpeter@782
   478
    ///If the second parameter \c connect is \c true (this is the default
kpeter@782
   479
    ///value), then a new arc from node \c n to the newly created node
kpeter@782
   480
    ///is also added.
deba@57
   481
    ///\return The newly created node.
deba@57
   482
    ///
kpeter@785
   483
    ///\note All iterators remain valid.
deba@57
   484
    ///
kpeter@782
   485
    ///\warning This functionality cannot be used together with the
kpeter@73
   486
    ///Snapshot feature.
deba@57
   487
    Node split(Node n, bool connect = true) {
deba@57
   488
      Node b = addNode();
kpeter@785
   489
      nodes[b.id].first_out=nodes[n.id].first_out;
kpeter@785
   490
      nodes[n.id].first_out=-1;
kpeter@785
   491
      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
kpeter@785
   492
        arcs[i].source=b.id;
deba@57
   493
      }
deba@57
   494
      if (connect) addArc(n,b);
deba@57
   495
      return b;
deba@57
   496
    }
alpar@209
   497
deba@57
   498
    ///Split an arc.
deba@57
   499
kpeter@782
   500
    ///This function splits the given arc. First, a new node \c v is
kpeter@782
   501
    ///added to the digraph, then the target node of the original arc
kpeter@782
   502
    ///is set to \c v. Finally, an arc from \c v to the original target
kpeter@782
   503
    ///is added.
kpeter@782
   504
    ///\return The newly created node.
kpeter@73
   505
    ///
kpeter@782
   506
    ///\note \c InArcIt iterators referencing the original arc are
kpeter@782
   507
    ///invalidated. Other iterators remain valid.
kpeter@73
   508
    ///
kpeter@73
   509
    ///\warning This functionality cannot be used together with the
kpeter@73
   510
    ///Snapshot feature.
kpeter@782
   511
    Node split(Arc a) {
kpeter@782
   512
      Node v = addNode();
kpeter@782
   513
      addArc(v,target(a));
kpeter@782
   514
      changeTarget(a,v);
kpeter@782
   515
      return v;
deba@57
   516
    }
alpar@209
   517
kpeter@782
   518
    ///Clear the digraph.
kpeter@782
   519
kpeter@782
   520
    ///This function erases all nodes and arcs from the digraph.
kpeter@782
   521
    ///
kpeter@834
   522
    ///\note All iterators of the digraph are invalidated, of course.
kpeter@782
   523
    void clear() {
kpeter@782
   524
      Parent::clear();
kpeter@782
   525
    }
kpeter@782
   526
kpeter@782
   527
    /// Reserve memory for nodes.
kpeter@782
   528
kpeter@782
   529
    /// Using this function, it is possible to avoid superfluous memory
kpeter@782
   530
    /// allocation: if you know that the digraph you want to build will
kpeter@782
   531
    /// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782
   532
    /// then it is worth reserving space for this amount before starting
kpeter@782
   533
    /// to build the digraph.
kpeter@782
   534
    /// \sa reserveArc()
kpeter@782
   535
    void reserveNode(int n) { nodes.reserve(n); };
kpeter@782
   536
kpeter@782
   537
    /// Reserve memory for arcs.
kpeter@782
   538
kpeter@782
   539
    /// Using this function, it is possible to avoid superfluous memory
kpeter@782
   540
    /// allocation: if you know that the digraph you want to build will
kpeter@782
   541
    /// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782
   542
    /// then it is worth reserving space for this amount before starting
kpeter@782
   543
    /// to build the digraph.
kpeter@782
   544
    /// \sa reserveNode()
kpeter@782
   545
    void reserveArc(int m) { arcs.reserve(m); };
kpeter@782
   546
deba@57
   547
    /// \brief Class to make a snapshot of the digraph and restore
kpeter@73
   548
    /// it later.
deba@57
   549
    ///
kpeter@73
   550
    /// Class to make a snapshot of the digraph and restore it later.
deba@57
   551
    ///
deba@57
   552
    /// The newly added nodes and arcs can be removed using the
deba@57
   553
    /// restore() function.
deba@57
   554
    ///
alpar@956
   555
    /// \note After a state is restored, you cannot restore a later state,
kpeter@782
   556
    /// i.e. you cannot add the removed nodes and arcs again using
kpeter@782
   557
    /// another Snapshot instance.
kpeter@782
   558
    ///
kpeter@782
   559
    /// \warning Node and arc deletions and other modifications (e.g.
kpeter@782
   560
    /// reversing, contracting, splitting arcs or nodes) cannot be
alpar@209
   561
    /// restored. These events invalidate the snapshot.
kpeter@833
   562
    /// However, the arcs and nodes that were added to the digraph after
kpeter@782
   563
    /// making the current snapshot can be removed without invalidating it.
deba@57
   564
    class Snapshot {
deba@57
   565
    protected:
deba@57
   566
deba@57
   567
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
   568
deba@57
   569
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
   570
      public:
deba@57
   571
deba@57
   572
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
   573
          : snapshot(_snapshot) {}
deba@57
   574
deba@57
   575
        using NodeNotifier::ObserverBase::attach;
deba@57
   576
        using NodeNotifier::ObserverBase::detach;
deba@57
   577
        using NodeNotifier::ObserverBase::attached;
alpar@209
   578
deba@57
   579
      protected:
alpar@209
   580
deba@57
   581
        virtual void add(const Node& node) {
deba@57
   582
          snapshot.addNode(node);
deba@57
   583
        }
deba@57
   584
        virtual void add(const std::vector<Node>& nodes) {
alpar@1355
   585
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
   586
            snapshot.addNode(nodes[i]);
deba@57
   587
          }
deba@57
   588
        }
deba@57
   589
        virtual void erase(const Node& node) {
deba@57
   590
          snapshot.eraseNode(node);
deba@57
   591
        }
deba@57
   592
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
   593
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
   594
            snapshot.eraseNode(nodes[i]);
deba@57
   595
          }
deba@57
   596
        }
deba@57
   597
        virtual void build() {
deba@57
   598
          Node node;
deba@57
   599
          std::vector<Node> nodes;
alpar@209
   600
          for (notifier()->first(node); node != INVALID;
deba@57
   601
               notifier()->next(node)) {
deba@57
   602
            nodes.push_back(node);
deba@57
   603
          }
deba@57
   604
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
   605
            snapshot.addNode(nodes[i]);
deba@57
   606
          }
deba@57
   607
        }
deba@57
   608
        virtual void clear() {
deba@57
   609
          Node node;
alpar@209
   610
          for (notifier()->first(node); node != INVALID;
deba@57
   611
               notifier()->next(node)) {
deba@57
   612
            snapshot.eraseNode(node);
deba@57
   613
          }
deba@57
   614
        }
deba@57
   615
deba@57
   616
        Snapshot& snapshot;
deba@57
   617
      };
deba@57
   618
deba@57
   619
      class ArcObserverProxy : public ArcNotifier::ObserverBase {
deba@57
   620
      public:
deba@57
   621
deba@57
   622
        ArcObserverProxy(Snapshot& _snapshot)
deba@57
   623
          : snapshot(_snapshot) {}
deba@57
   624
deba@57
   625
        using ArcNotifier::ObserverBase::attach;
deba@57
   626
        using ArcNotifier::ObserverBase::detach;
deba@57
   627
        using ArcNotifier::ObserverBase::attached;
alpar@209
   628
deba@57
   629
      protected:
deba@57
   630
deba@57
   631
        virtual void add(const Arc& arc) {
deba@57
   632
          snapshot.addArc(arc);
deba@57
   633
        }
deba@57
   634
        virtual void add(const std::vector<Arc>& arcs) {
alpar@1355
   635
          for (int i = arcs.size() - 1; i >= 0; --i) {
deba@57
   636
            snapshot.addArc(arcs[i]);
deba@57
   637
          }
deba@57
   638
        }
deba@57
   639
        virtual void erase(const Arc& arc) {
deba@57
   640
          snapshot.eraseArc(arc);
deba@57
   641
        }
deba@57
   642
        virtual void erase(const std::vector<Arc>& arcs) {
deba@57
   643
          for (int i = 0; i < int(arcs.size()); ++i) {
deba@57
   644
            snapshot.eraseArc(arcs[i]);
deba@57
   645
          }
deba@57
   646
        }
deba@57
   647
        virtual void build() {
deba@57
   648
          Arc arc;
deba@57
   649
          std::vector<Arc> arcs;
alpar@209
   650
          for (notifier()->first(arc); arc != INVALID;
deba@57
   651
               notifier()->next(arc)) {
deba@57
   652
            arcs.push_back(arc);
deba@57
   653
          }
deba@57
   654
          for (int i = arcs.size() - 1; i >= 0; --i) {
deba@57
   655
            snapshot.addArc(arcs[i]);
deba@57
   656
          }
deba@57
   657
        }
deba@57
   658
        virtual void clear() {
deba@57
   659
          Arc arc;
alpar@209
   660
          for (notifier()->first(arc); arc != INVALID;
deba@57
   661
               notifier()->next(arc)) {
deba@57
   662
            snapshot.eraseArc(arc);
deba@57
   663
          }
deba@57
   664
        }
deba@57
   665
deba@57
   666
        Snapshot& snapshot;
deba@57
   667
      };
alpar@209
   668
deba@57
   669
      ListDigraph *digraph;
deba@57
   670
deba@57
   671
      NodeObserverProxy node_observer_proxy;
deba@57
   672
      ArcObserverProxy arc_observer_proxy;
deba@57
   673
deba@57
   674
      std::list<Node> added_nodes;
deba@57
   675
      std::list<Arc> added_arcs;
deba@57
   676
deba@57
   677
deba@57
   678
      void addNode(const Node& node) {
alpar@209
   679
        added_nodes.push_front(node);
deba@57
   680
      }
deba@57
   681
      void eraseNode(const Node& node) {
alpar@209
   682
        std::list<Node>::iterator it =
deba@57
   683
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
   684
        if (it == added_nodes.end()) {
deba@57
   685
          clear();
deba@57
   686
          arc_observer_proxy.detach();
deba@57
   687
          throw NodeNotifier::ImmediateDetach();
deba@57
   688
        } else {
deba@57
   689
          added_nodes.erase(it);
deba@57
   690
        }
deba@57
   691
      }
deba@57
   692
deba@57
   693
      void addArc(const Arc& arc) {
alpar@209
   694
        added_arcs.push_front(arc);
deba@57
   695
      }
deba@57
   696
      void eraseArc(const Arc& arc) {
alpar@209
   697
        std::list<Arc>::iterator it =
deba@57
   698
          std::find(added_arcs.begin(), added_arcs.end(), arc);
deba@57
   699
        if (it == added_arcs.end()) {
deba@57
   700
          clear();
alpar@209
   701
          node_observer_proxy.detach();
deba@57
   702
          throw ArcNotifier::ImmediateDetach();
deba@57
   703
        } else {
deba@57
   704
          added_arcs.erase(it);
alpar@209
   705
        }
deba@57
   706
      }
deba@57
   707
deba@57
   708
      void attach(ListDigraph &_digraph) {
alpar@209
   709
        digraph = &_digraph;
alpar@209
   710
        node_observer_proxy.attach(digraph->notifier(Node()));
deba@57
   711
        arc_observer_proxy.attach(digraph->notifier(Arc()));
deba@57
   712
      }
alpar@209
   713
deba@57
   714
      void detach() {
alpar@209
   715
        node_observer_proxy.detach();
alpar@209
   716
        arc_observer_proxy.detach();
deba@57
   717
      }
deba@57
   718
deba@57
   719
      bool attached() const {
deba@57
   720
        return node_observer_proxy.attached();
deba@57
   721
      }
deba@57
   722
deba@57
   723
      void clear() {
deba@57
   724
        added_nodes.clear();
alpar@209
   725
        added_arcs.clear();
deba@57
   726
      }
deba@57
   727
deba@57
   728
    public:
deba@57
   729
deba@57
   730
      /// \brief Default constructor.
deba@57
   731
      ///
deba@57
   732
      /// Default constructor.
kpeter@782
   733
      /// You have to call save() to actually make a snapshot.
alpar@209
   734
      Snapshot()
alpar@209
   735
        : digraph(0), node_observer_proxy(*this),
deba@57
   736
          arc_observer_proxy(*this) {}
alpar@209
   737
deba@57
   738
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
   739
      ///
kpeter@782
   740
      /// This constructor immediately makes a snapshot of the given digraph.
kpeter@782
   741
      Snapshot(ListDigraph &gr)
alpar@209
   742
        : node_observer_proxy(*this),
deba@57
   743
          arc_observer_proxy(*this) {
kpeter@782
   744
        attach(gr);
deba@57
   745
      }
alpar@209
   746
deba@57
   747
      /// \brief Make a snapshot.
deba@57
   748
      ///
kpeter@782
   749
      /// This function makes a snapshot of the given digraph.
kpeter@782
   750
      /// It can be called more than once. In case of a repeated
deba@57
   751
      /// call, the previous snapshot gets lost.
kpeter@782
   752
      void save(ListDigraph &gr) {
deba@57
   753
        if (attached()) {
deba@57
   754
          detach();
deba@57
   755
          clear();
deba@57
   756
        }
kpeter@782
   757
        attach(gr);
deba@57
   758
      }
alpar@209
   759
deba@57
   760
      /// \brief Undo the changes until the last snapshot.
kpeter@782
   761
      ///
kpeter@782
   762
      /// This function undos the changes until the last snapshot
kpeter@782
   763
      /// created by save() or Snapshot(ListDigraph&).
kpeter@787
   764
      ///
kpeter@787
   765
      /// \warning This method invalidates the snapshot, i.e. repeated
kpeter@787
   766
      /// restoring is not supported unless you call save() again.
deba@57
   767
      void restore() {
alpar@209
   768
        detach();
alpar@209
   769
        for(std::list<Arc>::iterator it = added_arcs.begin();
deba@57
   770
            it != added_arcs.end(); ++it) {
alpar@209
   771
          digraph->erase(*it);
alpar@209
   772
        }
alpar@209
   773
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
   774
            it != added_nodes.end(); ++it) {
alpar@209
   775
          digraph->erase(*it);
alpar@209
   776
        }
deba@57
   777
        clear();
deba@57
   778
      }
deba@57
   779
kpeter@782
   780
      /// \brief Returns \c true if the snapshot is valid.
deba@57
   781
      ///
kpeter@782
   782
      /// This function returns \c true if the snapshot is valid.
deba@57
   783
      bool valid() const {
deba@57
   784
        return attached();
deba@57
   785
      }
deba@57
   786
    };
alpar@209
   787
deba@57
   788
  };
deba@57
   789
deba@57
   790
  ///@}
deba@57
   791
deba@57
   792
  class ListGraphBase {
deba@57
   793
deba@57
   794
  protected:
deba@57
   795
deba@57
   796
    struct NodeT {
deba@57
   797
      int first_out;
deba@57
   798
      int prev, next;
deba@57
   799
    };
alpar@209
   800
deba@57
   801
    struct ArcT {
deba@57
   802
      int target;
deba@57
   803
      int prev_out, next_out;
deba@57
   804
    };
deba@57
   805
deba@57
   806
    std::vector<NodeT> nodes;
deba@57
   807
deba@57
   808
    int first_node;
deba@57
   809
deba@57
   810
    int first_free_node;
deba@57
   811
deba@57
   812
    std::vector<ArcT> arcs;
deba@57
   813
deba@57
   814
    int first_free_arc;
alpar@209
   815
deba@57
   816
  public:
alpar@209
   817
kpeter@664
   818
    typedef ListGraphBase Graph;
deba@57
   819
deba@57
   820
    class Node {
deba@57
   821
      friend class ListGraphBase;
deba@57
   822
    protected:
deba@57
   823
deba@57
   824
      int id;
deba@57
   825
      explicit Node(int pid) { id = pid;}
deba@57
   826
deba@57
   827
    public:
deba@57
   828
      Node() {}
deba@57
   829
      Node (Invalid) { id = -1; }
deba@57
   830
      bool operator==(const Node& node) const {return id == node.id;}
deba@57
   831
      bool operator!=(const Node& node) const {return id != node.id;}
deba@57
   832
      bool operator<(const Node& node) const {return id < node.id;}
deba@57
   833
    };
deba@57
   834
deba@57
   835
    class Edge {
deba@57
   836
      friend class ListGraphBase;
deba@57
   837
    protected:
deba@57
   838
deba@57
   839
      int id;
deba@57
   840
      explicit Edge(int pid) { id = pid;}
deba@57
   841
deba@57
   842
    public:
deba@57
   843
      Edge() {}
deba@57
   844
      Edge (Invalid) { id = -1; }
kpeter@73
   845
      bool operator==(const Edge& edge) const {return id == edge.id;}
kpeter@73
   846
      bool operator!=(const Edge& edge) const {return id != edge.id;}
kpeter@73
   847
      bool operator<(const Edge& edge) const {return id < edge.id;}
deba@57
   848
    };
deba@57
   849
deba@57
   850
    class Arc {
deba@57
   851
      friend class ListGraphBase;
deba@57
   852
    protected:
deba@57
   853
deba@57
   854
      int id;
deba@57
   855
      explicit Arc(int pid) { id = pid;}
deba@57
   856
deba@57
   857
    public:
kpeter@341
   858
      operator Edge() const {
kpeter@341
   859
        return id != -1 ? edgeFromId(id / 2) : INVALID;
deba@238
   860
      }
deba@57
   861
deba@57
   862
      Arc() {}
deba@57
   863
      Arc (Invalid) { id = -1; }
deba@57
   864
      bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57
   865
      bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57
   866
      bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57
   867
    };
deba@57
   868
deba@57
   869
    ListGraphBase()
deba@57
   870
      : nodes(), first_node(-1),
alpar@209
   871
        first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57
   872
alpar@209
   873
alpar@209
   874
    int maxNodeId() const { return nodes.size()-1; }
deba@57
   875
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@57
   876
    int maxArcId() const { return arcs.size()-1; }
deba@57
   877
deba@57
   878
    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
deba@57
   879
    Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57
   880
deba@57
   881
    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
deba@57
   882
    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
deba@57
   883
deba@57
   884
    static bool direction(Arc e) {
deba@57
   885
      return (e.id & 1) == 1;
deba@57
   886
    }
deba@57
   887
deba@57
   888
    static Arc direct(Edge e, bool d) {
deba@57
   889
      return Arc(e.id * 2 + (d ? 1 : 0));
deba@57
   890
    }
deba@57
   891
alpar@209
   892
    void first(Node& node) const {
deba@57
   893
      node.id = first_node;
deba@57
   894
    }
deba@57
   895
deba@57
   896
    void next(Node& node) const {
deba@57
   897
      node.id = nodes[node.id].next;
deba@57
   898
    }
deba@57
   899
alpar@209
   900
    void first(Arc& e) const {
deba@57
   901
      int n = first_node;
deba@57
   902
      while (n != -1 && nodes[n].first_out == -1) {
deba@57
   903
        n = nodes[n].next;
deba@57
   904
      }
deba@57
   905
      e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57
   906
    }
deba@57
   907
deba@57
   908
    void next(Arc& e) const {
deba@57
   909
      if (arcs[e.id].next_out != -1) {
alpar@209
   910
        e.id = arcs[e.id].next_out;
deba@57
   911
      } else {
alpar@209
   912
        int n = nodes[arcs[e.id ^ 1].target].next;
deba@57
   913
        while(n != -1 && nodes[n].first_out == -1) {
deba@57
   914
          n = nodes[n].next;
deba@57
   915
        }
alpar@209
   916
        e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209
   917
      }
deba@57
   918
    }
deba@57
   919
alpar@209
   920
    void first(Edge& e) const {
deba@57
   921
      int n = first_node;
deba@57
   922
      while (n != -1) {
deba@57
   923
        e.id = nodes[n].first_out;
deba@57
   924
        while ((e.id & 1) != 1) {
deba@57
   925
          e.id = arcs[e.id].next_out;
deba@57
   926
        }
deba@57
   927
        if (e.id != -1) {
deba@57
   928
          e.id /= 2;
deba@57
   929
          return;
alpar@209
   930
        }
deba@57
   931
        n = nodes[n].next;
deba@57
   932
      }
deba@57
   933
      e.id = -1;
deba@57
   934
    }
deba@57
   935
deba@57
   936
    void next(Edge& e) const {
deba@57
   937
      int n = arcs[e.id * 2].target;
deba@57
   938
      e.id = arcs[(e.id * 2) | 1].next_out;
deba@57
   939
      while ((e.id & 1) != 1) {
deba@57
   940
        e.id = arcs[e.id].next_out;
deba@57
   941
      }
deba@57
   942
      if (e.id != -1) {
deba@57
   943
        e.id /= 2;
deba@57
   944
        return;
alpar@209
   945
      }
deba@57
   946
      n = nodes[n].next;
deba@57
   947
      while (n != -1) {
deba@57
   948
        e.id = nodes[n].first_out;
deba@57
   949
        while ((e.id & 1) != 1) {
deba@57
   950
          e.id = arcs[e.id].next_out;
deba@57
   951
        }
deba@57
   952
        if (e.id != -1) {
deba@57
   953
          e.id /= 2;
deba@57
   954
          return;
alpar@209
   955
        }
deba@57
   956
        n = nodes[n].next;
deba@57
   957
      }
deba@57
   958
      e.id = -1;
deba@57
   959
    }
deba@57
   960
deba@57
   961
    void firstOut(Arc &e, const Node& v) const {
deba@57
   962
      e.id = nodes[v.id].first_out;
deba@57
   963
    }
deba@57
   964
    void nextOut(Arc &e) const {
deba@57
   965
      e.id = arcs[e.id].next_out;
deba@57
   966
    }
deba@57
   967
deba@57
   968
    void firstIn(Arc &e, const Node& v) const {
deba@57
   969
      e.id = ((nodes[v.id].first_out) ^ 1);
deba@57
   970
      if (e.id == -2) e.id = -1;
deba@57
   971
    }
deba@57
   972
    void nextIn(Arc &e) const {
deba@57
   973
      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
deba@57
   974
      if (e.id == -2) e.id = -1;
deba@57
   975
    }
deba@57
   976
deba@57
   977
    void firstInc(Edge &e, bool& d, const Node& v) const {
kpeter@73
   978
      int a = nodes[v.id].first_out;
kpeter@73
   979
      if (a != -1 ) {
kpeter@73
   980
        e.id = a / 2;
kpeter@73
   981
        d = ((a & 1) == 1);
deba@57
   982
      } else {
deba@57
   983
        e.id = -1;
deba@57
   984
        d = true;
deba@57
   985
      }
deba@57
   986
    }
deba@57
   987
    void nextInc(Edge &e, bool& d) const {
kpeter@73
   988
      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
kpeter@73
   989
      if (a != -1 ) {
kpeter@73
   990
        e.id = a / 2;
kpeter@73
   991
        d = ((a & 1) == 1);
deba@57
   992
      } else {
deba@57
   993
        e.id = -1;
deba@57
   994
        d = true;
deba@57
   995
      }
deba@57
   996
    }
alpar@209
   997
deba@57
   998
    static int id(Node v) { return v.id; }
deba@57
   999
    static int id(Arc e) { return e.id; }
deba@57
  1000
    static int id(Edge e) { return e.id; }
deba@57
  1001
deba@57
  1002
    static Node nodeFromId(int id) { return Node(id);}
deba@57
  1003
    static Arc arcFromId(int id) { return Arc(id);}
deba@57
  1004
    static Edge edgeFromId(int id) { return Edge(id);}
deba@57
  1005
alpar@209
  1006
    bool valid(Node n) const {
alpar@209
  1007
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209
  1008
        nodes[n.id].prev != -2;
deba@149
  1009
    }
deba@149
  1010
alpar@209
  1011
    bool valid(Arc a) const {
alpar@209
  1012
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209
  1013
        arcs[a.id].prev_out != -2;
deba@149
  1014
    }
deba@149
  1015
alpar@209
  1016
    bool valid(Edge e) const {
alpar@209
  1017
      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
alpar@209
  1018
        arcs[2 * e.id].prev_out != -2;
deba@149
  1019
    }
deba@149
  1020
alpar@209
  1021
    Node addNode() {
deba@57
  1022
      int n;
alpar@209
  1023
deba@57
  1024
      if(first_free_node==-1) {
alpar@209
  1025
        n = nodes.size();
alpar@209
  1026
        nodes.push_back(NodeT());
deba@57
  1027
      } else {
alpar@209
  1028
        n = first_free_node;
alpar@209
  1029
        first_free_node = nodes[n].next;
deba@57
  1030
      }
alpar@209
  1031
deba@57
  1032
      nodes[n].next = first_node;
deba@57
  1033
      if (first_node != -1) nodes[first_node].prev = n;
deba@57
  1034
      first_node = n;
deba@57
  1035
      nodes[n].prev = -1;
alpar@209
  1036
deba@57
  1037
      nodes[n].first_out = -1;
alpar@209
  1038
deba@57
  1039
      return Node(n);
deba@57
  1040
    }
alpar@209
  1041
deba@57
  1042
    Edge addEdge(Node u, Node v) {
alpar@209
  1043
      int n;
deba@57
  1044
deba@57
  1045
      if (first_free_arc == -1) {
alpar@209
  1046
        n = arcs.size();
alpar@209
  1047
        arcs.push_back(ArcT());
alpar@209
  1048
        arcs.push_back(ArcT());
deba@57
  1049
      } else {
alpar@209
  1050
        n = first_free_arc;
alpar@209
  1051
        first_free_arc = arcs[n].next_out;
deba@57
  1052
      }
alpar@209
  1053
deba@57
  1054
      arcs[n].target = u.id;
deba@57
  1055
      arcs[n | 1].target = v.id;
deba@57
  1056
deba@57
  1057
      arcs[n].next_out = nodes[v.id].first_out;
deba@57
  1058
      if (nodes[v.id].first_out != -1) {
alpar@209
  1059
        arcs[nodes[v.id].first_out].prev_out = n;
alpar@209
  1060
      }
deba@57
  1061
      arcs[n].prev_out = -1;
deba@57
  1062
      nodes[v.id].first_out = n;
alpar@209
  1063
deba@57
  1064
      arcs[n | 1].next_out = nodes[u.id].first_out;
deba@57
  1065
      if (nodes[u.id].first_out != -1) {
alpar@209
  1066
        arcs[nodes[u.id].first_out].prev_out = (n | 1);
deba@57
  1067
      }
alpar@209
  1068
      arcs[n | 1].prev_out = -1;
deba@57
  1069
      nodes[u.id].first_out = (n | 1);
deba@57
  1070
deba@57
  1071
      return Edge(n / 2);
deba@57
  1072
    }
alpar@209
  1073
deba@57
  1074
    void erase(const Node& node) {
deba@57
  1075
      int n = node.id;
alpar@209
  1076
deba@57
  1077
      if(nodes[n].next != -1) {
alpar@209
  1078
        nodes[nodes[n].next].prev = nodes[n].prev;
deba@57
  1079
      }
alpar@209
  1080
deba@57
  1081
      if(nodes[n].prev != -1) {
alpar@209
  1082
        nodes[nodes[n].prev].next = nodes[n].next;
deba@57
  1083
      } else {
alpar@209
  1084
        first_node = nodes[n].next;
deba@57
  1085
      }
alpar@209
  1086
deba@57
  1087
      nodes[n].next = first_free_node;
deba@57
  1088
      first_free_node = n;
deba@149
  1089
      nodes[n].prev = -2;
deba@57
  1090
    }
alpar@209
  1091
kpeter@73
  1092
    void erase(const Edge& edge) {
kpeter@73
  1093
      int n = edge.id * 2;
alpar@209
  1094
deba@57
  1095
      if (arcs[n].next_out != -1) {
alpar@209
  1096
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209
  1097
      }
deba@57
  1098
deba@57
  1099
      if (arcs[n].prev_out != -1) {
alpar@209
  1100
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57
  1101
      } else {
alpar@209
  1102
        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
deba@57
  1103
      }
deba@57
  1104
deba@57
  1105
      if (arcs[n | 1].next_out != -1) {
alpar@209
  1106
        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
alpar@209
  1107
      }
deba@57
  1108
deba@57
  1109
      if (arcs[n | 1].prev_out != -1) {
alpar@209
  1110
        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
deba@57
  1111
      } else {
alpar@209
  1112
        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
deba@57
  1113
      }
alpar@209
  1114
deba@57
  1115
      arcs[n].next_out = first_free_arc;
alpar@209
  1116
      first_free_arc = n;
deba@149
  1117
      arcs[n].prev_out = -2;
deba@149
  1118
      arcs[n | 1].prev_out = -2;
deba@57
  1119
deba@57
  1120
    }
deba@57
  1121
deba@57
  1122
    void clear() {
deba@57
  1123
      arcs.clear();
deba@57
  1124
      nodes.clear();
deba@57
  1125
      first_node = first_free_node = first_free_arc = -1;
deba@57
  1126
    }
deba@57
  1127
deba@57
  1128
  protected:
deba@57
  1129
deba@235
  1130
    void changeV(Edge e, Node n) {
deba@57
  1131
      if(arcs[2 * e.id].next_out != -1) {
alpar@209
  1132
        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
deba@57
  1133
      }
deba@57
  1134
      if(arcs[2 * e.id].prev_out != -1) {
alpar@209
  1135
        arcs[arcs[2 * e.id].prev_out].next_out =
deba@57
  1136
          arcs[2 * e.id].next_out;
deba@57
  1137
      } else {
alpar@209
  1138
        nodes[arcs[(2 * e.id) | 1].target].first_out =
deba@57
  1139
          arcs[2 * e.id].next_out;
deba@57
  1140
      }
deba@57
  1141
deba@57
  1142
      if (nodes[n.id].first_out != -1) {
alpar@209
  1143
        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@57
  1144
      }
deba@57
  1145
      arcs[(2 * e.id) | 1].target = n.id;
deba@57
  1146
      arcs[2 * e.id].prev_out = -1;
deba@57
  1147
      arcs[2 * e.id].next_out = nodes[n.id].first_out;
deba@57
  1148
      nodes[n.id].first_out = 2 * e.id;
deba@57
  1149
    }
deba@57
  1150
deba@235
  1151
    void changeU(Edge e, Node n) {
deba@57
  1152
      if(arcs[(2 * e.id) | 1].next_out != -1) {
alpar@209
  1153
        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
deba@57
  1154
          arcs[(2 * e.id) | 1].prev_out;
deba@57
  1155
      }
deba@57
  1156
      if(arcs[(2 * e.id) | 1].prev_out != -1) {
alpar@209
  1157
        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
deba@57
  1158
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1159
      } else {
alpar@209
  1160
        nodes[arcs[2 * e.id].target].first_out =
deba@57
  1161
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1162
      }
deba@57
  1163
deba@57
  1164
      if (nodes[n.id].first_out != -1) {
alpar@209
  1165
        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
deba@57
  1166
      }
deba@57
  1167
      arcs[2 * e.id].target = n.id;
deba@57
  1168
      arcs[(2 * e.id) | 1].prev_out = -1;
deba@57
  1169
      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
deba@57
  1170
      nodes[n.id].first_out = ((2 * e.id) | 1);
deba@57
  1171
    }
deba@57
  1172
deba@57
  1173
  };
deba@57
  1174
deba@57
  1175
  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
deba@57
  1176
deba@57
  1177
kpeter@73
  1178
  /// \addtogroup graphs
deba@57
  1179
  /// @{
deba@57
  1180
kpeter@73
  1181
  ///A general undirected graph structure.
deba@57
  1182
kpeter@782
  1183
  ///\ref ListGraph is a versatile and fast undirected graph
kpeter@782
  1184
  ///implementation based on linked lists that are stored in
alpar@209
  1185
  ///\c std::vector structures.
deba@57
  1186
  ///
kpeter@782
  1187
  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
kpeter@782
  1188
  ///and it also provides several useful additional functionalities.
kpeter@782
  1189
  ///Most of its member functions and nested classes are documented
kpeter@73
  1190
  ///only in the concept class.
kpeter@73
  1191
  ///
kpeter@834
  1192
  ///This class provides only linear time counting for nodes, edges and arcs.
kpeter@834
  1193
  ///
kpeter@73
  1194
  ///\sa concepts::Graph
kpeter@782
  1195
  ///\sa ListDigraph
deba@57
  1196
  class ListGraph : public ExtendedListGraphBase {
kpeter@664
  1197
    typedef ExtendedListGraphBase Parent;
kpeter@664
  1198
deba@57
  1199
  private:
kpeter@782
  1200
    /// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@57
  1201
    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
kpeter@782
  1202
    /// \brief Assignment of a graph to another one is \e not allowed.
kpeter@782
  1203
    /// Use GraphCopy instead.
deba@57
  1204
    void operator=(const ListGraph &) {}
deba@57
  1205
  public:
deba@57
  1206
    /// Constructor
alpar@209
  1207
deba@57
  1208
    /// Constructor.
deba@57
  1209
    ///
deba@57
  1210
    ListGraph() {}
deba@57
  1211
alpar@1425
  1212
    typedef Parent::IncEdgeIt IncEdgeIt;
deba@57
  1213
kpeter@73
  1214
    /// \brief Add a new node to the graph.
deba@57
  1215
    ///
kpeter@782
  1216
    /// This function adds a new node to the graph.
kpeter@606
  1217
    /// \return The new node.
deba@57
  1218
    Node addNode() { return Parent::addNode(); }
deba@57
  1219
kpeter@73
  1220
    /// \brief Add a new edge to the graph.
deba@57
  1221
    ///
kpeter@782
  1222
    /// This function adds a new edge to the graph between nodes
kpeter@782
  1223
    /// \c u and \c v with inherent orientation from node \c u to
kpeter@782
  1224
    /// node \c v.
kpeter@606
  1225
    /// \return The new edge.
kpeter@782
  1226
    Edge addEdge(Node u, Node v) {
kpeter@782
  1227
      return Parent::addEdge(u, v);
deba@57
  1228
    }
deba@234
  1229
kpeter@782
  1230
    ///\brief Erase a node from the graph.
deba@234
  1231
    ///
kpeter@834
  1232
    /// This function erases the given node along with its incident arcs
kpeter@834
  1233
    /// from the graph.
kpeter@834
  1234
    ///
kpeter@834
  1235
    /// \note All iterators referencing the removed node or the incident
kpeter@834
  1236
    /// edges are invalidated, of course.
kpeter@782
  1237
    void erase(Node n) { Parent::erase(n); }
kpeter@782
  1238
kpeter@782
  1239
    ///\brief Erase an edge from the graph.
deba@234
  1240
    ///
kpeter@782
  1241
    /// This function erases the given edge from the graph.
kpeter@834
  1242
    ///
kpeter@834
  1243
    /// \note All iterators referencing the removed edge are invalidated,
kpeter@834
  1244
    /// of course.
kpeter@782
  1245
    void erase(Edge e) { Parent::erase(e); }
deba@149
  1246
    /// Node validity check
deba@149
  1247
kpeter@782
  1248
    /// This function gives back \c true if the given node is valid,
kpeter@782
  1249
    /// i.e. it is a real node of the graph.
deba@149
  1250
    ///
kpeter@782
  1251
    /// \warning A removed node could become valid again if new nodes are
deba@149
  1252
    /// added to the graph.
deba@149
  1253
    bool valid(Node n) const { return Parent::valid(n); }
kpeter@782
  1254
    /// Edge validity check
kpeter@782
  1255
kpeter@782
  1256
    /// This function gives back \c true if the given edge is valid,
kpeter@782
  1257
    /// i.e. it is a real edge of the graph.
kpeter@782
  1258
    ///
kpeter@782
  1259
    /// \warning A removed edge could become valid again if new edges are
kpeter@782
  1260
    /// added to the graph.
kpeter@782
  1261
    bool valid(Edge e) const { return Parent::valid(e); }
deba@149
  1262
    /// Arc validity check
deba@149
  1263
kpeter@782
  1264
    /// This function gives back \c true if the given arc is valid,
kpeter@782
  1265
    /// i.e. it is a real arc of the graph.
deba@149
  1266
    ///
kpeter@782
  1267
    /// \warning A removed arc could become valid again if new edges are
deba@149
  1268
    /// added to the graph.
deba@149
  1269
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
  1270
kpeter@782
  1271
    /// \brief Change the first node of an edge.
deba@149
  1272
    ///
kpeter@782
  1273
    /// This function changes the first node of the given edge \c e to \c n.
deba@57
  1274
    ///
kpeter@782
  1275
    ///\note \c EdgeIt and \c ArcIt iterators referencing the
kpeter@782
  1276
    ///changed edge are invalidated and all other iterators whose
kpeter@782
  1277
    ///base node is the changed node are also invalidated.
kpeter@73
  1278
    ///
kpeter@73
  1279
    ///\warning This functionality cannot be used together with the
kpeter@73
  1280
    ///Snapshot feature.
deba@235
  1281
    void changeU(Edge e, Node n) {
deba@235
  1282
      Parent::changeU(e,n);
alpar@209
  1283
    }
kpeter@782
  1284
    /// \brief Change the second node of an edge.
deba@57
  1285
    ///
kpeter@782
  1286
    /// This function changes the second node of the given edge \c e to \c n.
deba@57
  1287
    ///
kpeter@782
  1288
    ///\note \c EdgeIt iterators referencing the changed edge remain
kpeter@833
  1289
    ///valid, but \c ArcIt iterators referencing the changed edge and
kpeter@782
  1290
    ///all other iterators whose base node is the changed node are also
kpeter@782
  1291
    ///invalidated.
kpeter@73
  1292
    ///
kpeter@73
  1293
    ///\warning This functionality cannot be used together with the
kpeter@73
  1294
    ///Snapshot feature.
deba@235
  1295
    void changeV(Edge e, Node n) {
deba@235
  1296
      Parent::changeV(e,n);
deba@57
  1297
    }
kpeter@782
  1298
deba@57
  1299
    /// \brief Contract two nodes.
deba@57
  1300
    ///
kpeter@782
  1301
    /// This function contracts the given two nodes.
kpeter@782
  1302
    /// Node \c b is removed, but instead of deleting
kpeter@782
  1303
    /// its incident edges, they are joined to node \c a.
kpeter@782
  1304
    /// If the last parameter \c r is \c true (this is the default value),
kpeter@782
  1305
    /// then the newly created loops are removed.
deba@57
  1306
    ///
kpeter@782
  1307
    /// \note The moved edges are joined to node \c a using changeU()
kpeter@782
  1308
    /// or changeV(), thus all edge and arc iterators whose base node is
kpeter@782
  1309
    /// \c b are invalidated.
alpar@956
  1310
    /// Moreover all iterators referencing node \c b or the removed
kpeter@782
  1311
    /// loops are also invalidated. Other iterators remain valid.
kpeter@73
  1312
    ///
kpeter@73
  1313
    ///\warning This functionality cannot be used together with the
kpeter@73
  1314
    ///Snapshot feature.
deba@57
  1315
    void contract(Node a, Node b, bool r = true) {
kpeter@73
  1316
      for(IncEdgeIt e(*this, b); e!=INVALID;) {
alpar@209
  1317
        IncEdgeIt f = e; ++f;
alpar@209
  1318
        if (r && runningNode(e) == a) {
alpar@209
  1319
          erase(e);
deba@235
  1320
        } else if (u(e) == b) {
deba@235
  1321
          changeU(e, a);
alpar@209
  1322
        } else {
deba@235
  1323
          changeV(e, a);
alpar@209
  1324
        }
alpar@209
  1325
        e = f;
deba@57
  1326
      }
deba@57
  1327
      erase(b);
deba@57
  1328
    }
deba@57
  1329
kpeter@782
  1330
    ///Clear the graph.
kpeter@782
  1331
kpeter@782
  1332
    ///This function erases all nodes and arcs from the graph.
kpeter@782
  1333
    ///
kpeter@834
  1334
    ///\note All iterators of the graph are invalidated, of course.
kpeter@782
  1335
    void clear() {
kpeter@782
  1336
      Parent::clear();
kpeter@782
  1337
    }
kpeter@664
  1338
kpeter@783
  1339
    /// Reserve memory for nodes.
kpeter@783
  1340
kpeter@783
  1341
    /// Using this function, it is possible to avoid superfluous memory
kpeter@783
  1342
    /// allocation: if you know that the graph you want to build will
kpeter@783
  1343
    /// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783
  1344
    /// then it is worth reserving space for this amount before starting
kpeter@783
  1345
    /// to build the graph.
kpeter@783
  1346
    /// \sa reserveEdge()
kpeter@783
  1347
    void reserveNode(int n) { nodes.reserve(n); };
kpeter@783
  1348
kpeter@783
  1349
    /// Reserve memory for edges.
kpeter@783
  1350
kpeter@783
  1351
    /// Using this function, it is possible to avoid superfluous memory
kpeter@783
  1352
    /// allocation: if you know that the graph you want to build will
kpeter@783
  1353
    /// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783
  1354
    /// then it is worth reserving space for this amount before starting
kpeter@783
  1355
    /// to build the graph.
kpeter@783
  1356
    /// \sa reserveNode()
kpeter@783
  1357
    void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@57
  1358
kpeter@73
  1359
    /// \brief Class to make a snapshot of the graph and restore
kpeter@73
  1360
    /// it later.
deba@57
  1361
    ///
kpeter@73
  1362
    /// Class to make a snapshot of the graph and restore it later.
deba@57
  1363
    ///
deba@57
  1364
    /// The newly added nodes and edges can be removed
deba@57
  1365
    /// using the restore() function.
deba@57
  1366
    ///
alpar@956
  1367
    /// \note After a state is restored, you cannot restore a later state,
kpeter@782
  1368
    /// i.e. you cannot add the removed nodes and edges again using
kpeter@782
  1369
    /// another Snapshot instance.
kpeter@782
  1370
    ///
kpeter@782
  1371
    /// \warning Node and edge deletions and other modifications
kpeter@782
  1372
    /// (e.g. changing the end-nodes of edges or contracting nodes)
kpeter@782
  1373
    /// cannot be restored. These events invalidate the snapshot.
kpeter@833
  1374
    /// However, the edges and nodes that were added to the graph after
kpeter@782
  1375
    /// making the current snapshot can be removed without invalidating it.
deba@57
  1376
    class Snapshot {
deba@57
  1377
    protected:
deba@57
  1378
deba@57
  1379
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
  1380
deba@57
  1381
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
  1382
      public:
deba@57
  1383
deba@57
  1384
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
  1385
          : snapshot(_snapshot) {}
deba@57
  1386
deba@57
  1387
        using NodeNotifier::ObserverBase::attach;
deba@57
  1388
        using NodeNotifier::ObserverBase::detach;
deba@57
  1389
        using NodeNotifier::ObserverBase::attached;
alpar@209
  1390
deba@57
  1391
      protected:
alpar@209
  1392
deba@57
  1393
        virtual void add(const Node& node) {
deba@57
  1394
          snapshot.addNode(node);
deba@57
  1395
        }
deba@57
  1396
        virtual void add(const std::vector<Node>& nodes) {
alpar@1355
  1397
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
  1398
            snapshot.addNode(nodes[i]);
deba@57
  1399
          }
deba@57
  1400
        }
deba@57
  1401
        virtual void erase(const Node& node) {
deba@57
  1402
          snapshot.eraseNode(node);
deba@57
  1403
        }
deba@57
  1404
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
  1405
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
  1406
            snapshot.eraseNode(nodes[i]);
deba@57
  1407
          }
deba@57
  1408
        }
deba@57
  1409
        virtual void build() {
deba@57
  1410
          Node node;
deba@57
  1411
          std::vector<Node> nodes;
alpar@209
  1412
          for (notifier()->first(node); node != INVALID;
deba@57
  1413
               notifier()->next(node)) {
deba@57
  1414
            nodes.push_back(node);
deba@57
  1415
          }
deba@57
  1416
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
  1417
            snapshot.addNode(nodes[i]);
deba@57
  1418
          }
deba@57
  1419
        }
deba@57
  1420
        virtual void clear() {
deba@57
  1421
          Node node;
alpar@209
  1422
          for (notifier()->first(node); node != INVALID;
deba@57
  1423
               notifier()->next(node)) {
deba@57
  1424
            snapshot.eraseNode(node);
deba@57
  1425
          }
deba@57
  1426
        }
deba@57
  1427
deba@57
  1428
        Snapshot& snapshot;
deba@57
  1429
      };
deba@57
  1430
deba@57
  1431
      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@57
  1432
      public:
deba@57
  1433
deba@57
  1434
        EdgeObserverProxy(Snapshot& _snapshot)
deba@57
  1435
          : snapshot(_snapshot) {}
deba@57
  1436
deba@57
  1437
        using EdgeNotifier::ObserverBase::attach;
deba@57
  1438
        using EdgeNotifier::ObserverBase::detach;
deba@57
  1439
        using EdgeNotifier::ObserverBase::attached;
alpar@209
  1440
deba@57
  1441
      protected:
deba@57
  1442
kpeter@73
  1443
        virtual void add(const Edge& edge) {
kpeter@73
  1444
          snapshot.addEdge(edge);
deba@57
  1445
        }
kpeter@73
  1446
        virtual void add(const std::vector<Edge>& edges) {
alpar@1355
  1447
          for (int i = edges.size() - 1; i >= 0; --i) {
kpeter@73
  1448
            snapshot.addEdge(edges[i]);
deba@57
  1449
          }
deba@57
  1450
        }
kpeter@73
  1451
        virtual void erase(const Edge& edge) {
kpeter@73
  1452
          snapshot.eraseEdge(edge);
deba@57
  1453
        }
kpeter@73
  1454
        virtual void erase(const std::vector<Edge>& edges) {
kpeter@73
  1455
          for (int i = 0; i < int(edges.size()); ++i) {
kpeter@73
  1456
            snapshot.eraseEdge(edges[i]);
deba@57
  1457
          }
deba@57
  1458
        }
deba@57
  1459
        virtual void build() {
kpeter@73
  1460
          Edge edge;
kpeter@73
  1461
          std::vector<Edge> edges;
alpar@209
  1462
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1463
               notifier()->next(edge)) {
kpeter@73
  1464
            edges.push_back(edge);
deba@57
  1465
          }
kpeter@73
  1466
          for (int i = edges.size() - 1; i >= 0; --i) {
kpeter@73
  1467
            snapshot.addEdge(edges[i]);
deba@57
  1468
          }
deba@57
  1469
        }
deba@57
  1470
        virtual void clear() {
kpeter@73
  1471
          Edge edge;
alpar@209
  1472
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1473
               notifier()->next(edge)) {
kpeter@73
  1474
            snapshot.eraseEdge(edge);
deba@57
  1475
          }
deba@57
  1476
        }
deba@57
  1477
deba@57
  1478
        Snapshot& snapshot;
deba@57
  1479
      };
kpeter@73
  1480
kpeter@73
  1481
      ListGraph *graph;
deba@57
  1482
deba@57
  1483
      NodeObserverProxy node_observer_proxy;
kpeter@73
  1484
      EdgeObserverProxy edge_observer_proxy;
deba@57
  1485
deba@57
  1486
      std::list<Node> added_nodes;
kpeter@73
  1487
      std::list<Edge> added_edges;
deba@57
  1488
deba@57
  1489
deba@57
  1490
      void addNode(const Node& node) {
alpar@209
  1491
        added_nodes.push_front(node);
deba@57
  1492
      }
deba@57
  1493
      void eraseNode(const Node& node) {
alpar@209
  1494
        std::list<Node>::iterator it =
deba@57
  1495
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
  1496
        if (it == added_nodes.end()) {
deba@57
  1497
          clear();
kpeter@73
  1498
          edge_observer_proxy.detach();
deba@57
  1499
          throw NodeNotifier::ImmediateDetach();
deba@57
  1500
        } else {
deba@57
  1501
          added_nodes.erase(it);
deba@57
  1502
        }
deba@57
  1503
      }
deba@57
  1504
kpeter@73
  1505
      void addEdge(const Edge& edge) {
alpar@209
  1506
        added_edges.push_front(edge);
deba@57
  1507
      }
kpeter@73
  1508
      void eraseEdge(const Edge& edge) {
alpar@209
  1509
        std::list<Edge>::iterator it =
kpeter@73
  1510
          std::find(added_edges.begin(), added_edges.end(), edge);
kpeter@73
  1511
        if (it == added_edges.end()) {
deba@57
  1512
          clear();
deba@57
  1513
          node_observer_proxy.detach();
deba@57
  1514
          throw EdgeNotifier::ImmediateDetach();
deba@57
  1515
        } else {
kpeter@73
  1516
          added_edges.erase(it);
kpeter@73
  1517
        }
deba@57
  1518
      }
deba@57
  1519
kpeter@73
  1520
      void attach(ListGraph &_graph) {
alpar@209
  1521
        graph = &_graph;
alpar@209
  1522
        node_observer_proxy.attach(graph->notifier(Node()));
kpeter@73
  1523
        edge_observer_proxy.attach(graph->notifier(Edge()));
deba@57
  1524
      }
alpar@209
  1525
deba@57
  1526
      void detach() {
alpar@209
  1527
        node_observer_proxy.detach();
alpar@209
  1528
        edge_observer_proxy.detach();
deba@57
  1529
      }
deba@57
  1530
deba@57
  1531
      bool attached() const {
deba@57
  1532
        return node_observer_proxy.attached();
deba@57
  1533
      }
deba@57
  1534
deba@57
  1535
      void clear() {
deba@57
  1536
        added_nodes.clear();
alpar@209
  1537
        added_edges.clear();
deba@57
  1538
      }
deba@57
  1539
deba@57
  1540
    public:
deba@57
  1541
deba@57
  1542
      /// \brief Default constructor.
deba@57
  1543
      ///
deba@57
  1544
      /// Default constructor.
kpeter@782
  1545
      /// You have to call save() to actually make a snapshot.
alpar@209
  1546
      Snapshot()
alpar@209
  1547
        : graph(0), node_observer_proxy(*this),
kpeter@73
  1548
          edge_observer_proxy(*this) {}
alpar@209
  1549
deba@57
  1550
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
  1551
      ///
kpeter@782
  1552
      /// This constructor immediately makes a snapshot of the given graph.
kpeter@782
  1553
      Snapshot(ListGraph &gr)
alpar@209
  1554
        : node_observer_proxy(*this),
kpeter@73
  1555
          edge_observer_proxy(*this) {
kpeter@782
  1556
        attach(gr);
deba@57
  1557
      }
alpar@209
  1558
deba@57
  1559
      /// \brief Make a snapshot.
deba@57
  1560
      ///
kpeter@782
  1561
      /// This function makes a snapshot of the given graph.
kpeter@782
  1562
      /// It can be called more than once. In case of a repeated
deba@57
  1563
      /// call, the previous snapshot gets lost.
kpeter@782
  1564
      void save(ListGraph &gr) {
deba@57
  1565
        if (attached()) {
deba@57
  1566
          detach();
deba@57
  1567
          clear();
deba@57
  1568
        }
kpeter@782
  1569
        attach(gr);
deba@57
  1570
      }
alpar@209
  1571
deba@57
  1572
      /// \brief Undo the changes until the last snapshot.
kpeter@782
  1573
      ///
kpeter@782
  1574
      /// This function undos the changes until the last snapshot
kpeter@782
  1575
      /// created by save() or Snapshot(ListGraph&).
kpeter@787
  1576
      ///
kpeter@787
  1577
      /// \warning This method invalidates the snapshot, i.e. repeated
kpeter@787
  1578
      /// restoring is not supported unless you call save() again.
deba@57
  1579
      void restore() {
alpar@209
  1580
        detach();
alpar@209
  1581
        for(std::list<Edge>::iterator it = added_edges.begin();
kpeter@73
  1582
            it != added_edges.end(); ++it) {
alpar@209
  1583
          graph->erase(*it);
alpar@209
  1584
        }
alpar@209
  1585
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
  1586
            it != added_nodes.end(); ++it) {
alpar@209
  1587
          graph->erase(*it);
alpar@209
  1588
        }
deba@57
  1589
        clear();
deba@57
  1590
      }
deba@57
  1591
kpeter@782
  1592
      /// \brief Returns \c true if the snapshot is valid.
deba@57
  1593
      ///
kpeter@782
  1594
      /// This function returns \c true if the snapshot is valid.
deba@57
  1595
      bool valid() const {
deba@57
  1596
        return attached();
deba@57
  1597
      }
deba@57
  1598
    };
deba@57
  1599
  };
alpar@209
  1600
alpar@209
  1601
  /// @}
alpar@1356
  1602
alpar@1356
  1603
  class ListBpGraphBase {
alpar@1356
  1604
alpar@1356
  1605
  protected:
alpar@1356
  1606
alpar@1356
  1607
    struct NodeT {
alpar@1356
  1608
      int first_out;
alpar@1356
  1609
      int prev, next;
alpar@1356
  1610
      int partition_prev, partition_next;
alpar@1356
  1611
      int partition_index;
alpar@1356
  1612
      bool red;
alpar@1356
  1613
    };
alpar@1356
  1614
alpar@1356
  1615
    struct ArcT {
alpar@1356
  1616
      int target;
alpar@1356
  1617
      int prev_out, next_out;
alpar@1356
  1618
    };
alpar@1356
  1619
alpar@1356
  1620
    std::vector<NodeT> nodes;
alpar@1356
  1621
alpar@1356
  1622
    int first_node, first_red, first_blue;
alpar@1356
  1623
    int max_red, max_blue;
alpar@1356
  1624
alpar@1356
  1625
    int first_free_red, first_free_blue;
alpar@1356
  1626
alpar@1356
  1627
    std::vector<ArcT> arcs;
alpar@1356
  1628
alpar@1356
  1629
    int first_free_arc;
alpar@1356
  1630
alpar@1356
  1631
  public:
alpar@1356
  1632
alpar@1356
  1633
    typedef ListBpGraphBase BpGraph;
alpar@1356
  1634
alpar@1356
  1635
    class Node {
alpar@1356
  1636
      friend class ListBpGraphBase;
alpar@1356
  1637
    protected:
alpar@1356
  1638
alpar@1356
  1639
      int id;
alpar@1356
  1640
      explicit Node(int pid) { id = pid;}
alpar@1356
  1641
alpar@1356
  1642
    public:
alpar@1356
  1643
      Node() {}
alpar@1356
  1644
      Node (Invalid) { id = -1; }
alpar@1356
  1645
      bool operator==(const Node& node) const {return id == node.id;}
alpar@1356
  1646
      bool operator!=(const Node& node) const {return id != node.id;}
alpar@1356
  1647
      bool operator<(const Node& node) const {return id < node.id;}
alpar@1356
  1648
    };
alpar@1356
  1649
alpar@1356
  1650
    class RedNode : public Node {
alpar@1356
  1651
      friend class ListBpGraphBase;
alpar@1356
  1652
    protected:
alpar@1356
  1653
alpar@1356
  1654
      explicit RedNode(int pid) : Node(pid) {}
alpar@1356
  1655
alpar@1356
  1656
    public:
alpar@1356
  1657
      RedNode() {}
alpar@1356
  1658
      RedNode(const RedNode& node) : Node(node) {}
alpar@1356
  1659
      RedNode(Invalid) : Node(INVALID){}
alpar@1356
  1660
    };
alpar@1356
  1661
alpar@1356
  1662
    class BlueNode : public Node {
alpar@1356
  1663
      friend class ListBpGraphBase;
alpar@1356
  1664
    protected:
alpar@1356
  1665
alpar@1356
  1666
      explicit BlueNode(int pid) : Node(pid) {}
alpar@1356
  1667
alpar@1356
  1668
    public:
alpar@1356
  1669
      BlueNode() {}
alpar@1356
  1670
      BlueNode(const BlueNode& node) : Node(node) {}
alpar@1356
  1671
      BlueNode(Invalid) : Node(INVALID){}
alpar@1356
  1672
    };
alpar@1356
  1673
alpar@1356
  1674
    class Edge {
alpar@1356
  1675
      friend class ListBpGraphBase;
alpar@1356
  1676
    protected:
alpar@1356
  1677
alpar@1356
  1678
      int id;
alpar@1356
  1679
      explicit Edge(int pid) { id = pid;}
alpar@1356
  1680
alpar@1356
  1681
    public:
alpar@1356
  1682
      Edge() {}
alpar@1356
  1683
      Edge (Invalid) { id = -1; }
alpar@1356
  1684
      bool operator==(const Edge& edge) const {return id == edge.id;}
alpar@1356
  1685
      bool operator!=(const Edge& edge) const {return id != edge.id;}
alpar@1356
  1686
      bool operator<(const Edge& edge) const {return id < edge.id;}
alpar@1356
  1687
    };
alpar@1356
  1688
alpar@1356
  1689
    class Arc {
alpar@1356
  1690
      friend class ListBpGraphBase;
alpar@1356
  1691
    protected:
alpar@1356
  1692
alpar@1356
  1693
      int id;
alpar@1356
  1694
      explicit Arc(int pid) { id = pid;}
alpar@1356
  1695
alpar@1356
  1696
    public:
alpar@1356
  1697
      operator Edge() const {
alpar@1356
  1698
        return id != -1 ? edgeFromId(id / 2) : INVALID;
alpar@1356
  1699
      }
alpar@1356
  1700
alpar@1356
  1701
      Arc() {}
alpar@1356
  1702
      Arc (Invalid) { id = -1; }
alpar@1356
  1703
      bool operator==(const Arc& arc) const {return id == arc.id;}
alpar@1356
  1704
      bool operator!=(const Arc& arc) const {return id != arc.id;}
alpar@1356
  1705
      bool operator<(const Arc& arc) const {return id < arc.id;}
alpar@1356
  1706
    };
alpar@1356
  1707
alpar@1356
  1708
    ListBpGraphBase()
alpar@1356
  1709
      : nodes(), first_node(-1),
alpar@1356
  1710
        first_red(-1), first_blue(-1),
alpar@1356
  1711
        max_red(-1), max_blue(-1),
alpar@1356
  1712
        first_free_red(-1), first_free_blue(-1),
alpar@1356
  1713
        arcs(), first_free_arc(-1) {}
alpar@1356
  1714
alpar@1356
  1715
alpar@1356
  1716
    bool red(Node n) const { return nodes[n.id].red; }
alpar@1356
  1717
    bool blue(Node n) const { return !nodes[n.id].red; }
alpar@1356
  1718
alpar@1356
  1719
    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
alpar@1356
  1720
    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
alpar@1356
  1721
alpar@1356
  1722
    int maxNodeId() const { return nodes.size()-1; }
alpar@1356
  1723
    int maxRedId() const { return max_red; }
alpar@1356
  1724
    int maxBlueId() const { return max_blue; }
alpar@1356
  1725
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
alpar@1356
  1726
    int maxArcId() const { return arcs.size()-1; }
alpar@1356
  1727
alpar@1356
  1728
    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
alpar@1356
  1729
    Node target(Arc e) const { return Node(arcs[e.id].target); }
alpar@1356
  1730
alpar@1356
  1731
    RedNode redNode(Edge e) const {
alpar@1356
  1732
      return RedNode(arcs[2 * e.id].target);
alpar@1356
  1733
    }
alpar@1356
  1734
    BlueNode blueNode(Edge e) const {
alpar@1356
  1735
      return BlueNode(arcs[2 * e.id + 1].target);
alpar@1356
  1736
    }
alpar@1356
  1737
alpar@1356
  1738
    static bool direction(Arc e) {
alpar@1356
  1739
      return (e.id & 1) == 1;
alpar@1356
  1740
    }
alpar@1356
  1741
alpar@1356
  1742
    static Arc direct(Edge e, bool d) {
alpar@1356
  1743
      return Arc(e.id * 2 + (d ? 1 : 0));
alpar@1356
  1744
    }
alpar@1356
  1745
alpar@1356
  1746
    void first(Node& node) const {
alpar@1356
  1747
      node.id = first_node;
alpar@1356
  1748
    }
alpar@1356
  1749
alpar@1356
  1750
    void next(Node& node) const {
alpar@1356
  1751
      node.id = nodes[node.id].next;
alpar@1356
  1752
    }
alpar@1356
  1753
alpar@1356
  1754
    void first(RedNode& node) const {
alpar@1356
  1755
      node.id = first_red;
alpar@1356
  1756
    }
alpar@1356
  1757
alpar@1356
  1758
    void next(RedNode& node) const {
alpar@1356
  1759
      node.id = nodes[node.id].partition_next;
alpar@1356
  1760
    }
alpar@1356
  1761
alpar@1356
  1762
    void first(BlueNode& node) const {
alpar@1356
  1763
      node.id = first_blue;
alpar@1356
  1764
    }
alpar@1356
  1765
alpar@1356
  1766
    void next(BlueNode& node) const {
alpar@1356
  1767
      node.id = nodes[node.id].partition_next;
alpar@1356
  1768
    }
alpar@1356
  1769
alpar@1356
  1770
    void first(Arc& e) const {
alpar@1356
  1771
      int n = first_node;
alpar@1356
  1772
      while (n != -1 && nodes[n].first_out == -1) {
alpar@1356
  1773
        n = nodes[n].next;
alpar@1356
  1774
      }
alpar@1356
  1775
      e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@1356
  1776
    }
alpar@1356
  1777
alpar@1356
  1778
    void next(Arc& e) const {
alpar@1356
  1779
      if (arcs[e.id].next_out != -1) {
alpar@1356
  1780
        e.id = arcs[e.id].next_out;
alpar@1356
  1781
      } else {
alpar@1356
  1782
        int n = nodes[arcs[e.id ^ 1].target].next;
alpar@1356
  1783
        while(n != -1 && nodes[n].first_out == -1) {
alpar@1356
  1784
          n = nodes[n].next;
alpar@1356
  1785
        }
alpar@1356
  1786
        e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@1356
  1787
      }
alpar@1356
  1788
    }
alpar@1356
  1789
alpar@1356
  1790
    void first(Edge& e) const {
alpar@1356
  1791
      int n = first_node;
alpar@1356
  1792
      while (n != -1) {
alpar@1356
  1793
        e.id = nodes[n].first_out;
alpar@1356
  1794
        while ((e.id & 1) != 1) {
alpar@1356
  1795
          e.id = arcs[e.id].next_out;
alpar@1356
  1796
        }
alpar@1356
  1797
        if (e.id != -1) {
alpar@1356
  1798
          e.id /= 2;
alpar@1356
  1799
          return;
alpar@1356
  1800
        }
alpar@1356
  1801
        n = nodes[n].next;
alpar@1356
  1802
      }
alpar@1356
  1803
      e.id = -1;
alpar@1356
  1804
    }
alpar@1356
  1805
alpar@1356
  1806
    void next(Edge& e) const {
alpar@1356
  1807
      int n = arcs[e.id * 2].target;
alpar@1356
  1808
      e.id = arcs[(e.id * 2) | 1].next_out;
alpar@1356
  1809
      while ((e.id & 1) != 1) {
alpar@1356
  1810
        e.id = arcs[e.id].next_out;
alpar@1356
  1811
      }
alpar@1356
  1812
      if (e.id != -1) {
alpar@1356
  1813
        e.id /= 2;
alpar@1356
  1814
        return;
alpar@1356
  1815
      }
alpar@1356
  1816
      n = nodes[n].next;
alpar@1356
  1817
      while (n != -1) {
alpar@1356
  1818
        e.id = nodes[n].first_out;
alpar@1356
  1819
        while ((e.id & 1) != 1) {
alpar@1356
  1820
          e.id = arcs[e.id].next_out;
alpar@1356
  1821
        }
alpar@1356
  1822
        if (e.id != -1) {
alpar@1356
  1823
          e.id /= 2;
alpar@1356
  1824
          return;
alpar@1356
  1825
        }
alpar@1356
  1826
        n = nodes[n].next;
alpar@1356
  1827
      }
alpar@1356
  1828
      e.id = -1;
alpar@1356
  1829
    }
alpar@1356
  1830
alpar@1356
  1831
    void firstOut(Arc &e, const Node& v) const {
alpar@1356
  1832
      e.id = nodes[v.id].first_out;
alpar@1356
  1833
    }
alpar@1356
  1834
    void nextOut(Arc &e) const {
alpar@1356
  1835
      e.id = arcs[e.id].next_out;
alpar@1356
  1836
    }
alpar@1356
  1837
alpar@1356
  1838
    void firstIn(Arc &e, const Node& v) const {
alpar@1356
  1839
      e.id = ((nodes[v.id].first_out) ^ 1);
alpar@1356
  1840
      if (e.id == -2) e.id = -1;
alpar@1356
  1841
    }
alpar@1356
  1842
    void nextIn(Arc &e) const {
alpar@1356
  1843
      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
alpar@1356
  1844
      if (e.id == -2) e.id = -1;
alpar@1356
  1845
    }
alpar@1356
  1846
alpar@1356
  1847
    void firstInc(Edge &e, bool& d, const Node& v) const {
alpar@1356
  1848
      int a = nodes[v.id].first_out;
alpar@1356
  1849
      if (a != -1 ) {
alpar@1356
  1850
        e.id = a / 2;
alpar@1356
  1851
        d = ((a & 1) == 1);
alpar@1356
  1852
      } else {
alpar@1356
  1853
        e.id = -1;
alpar@1356
  1854
        d = true;
alpar@1356
  1855
      }
alpar@1356
  1856
    }
alpar@1356
  1857
    void nextInc(Edge &e, bool& d) const {
alpar@1356
  1858
      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
alpar@1356
  1859
      if (a != -1 ) {
alpar@1356
  1860
        e.id = a / 2;
alpar@1356
  1861
        d = ((a & 1) == 1);
alpar@1356
  1862
      } else {
alpar@1356
  1863
        e.id = -1;
alpar@1356
  1864
        d = true;
alpar@1356
  1865
      }
alpar@1356
  1866
    }
alpar@1356
  1867
alpar@1356
  1868
    static int id(Node v) { return v.id; }
alpar@1356
  1869
    int id(RedNode v) const { return nodes[v.id].partition_index; }
alpar@1356
  1870
    int id(BlueNode v) const { return nodes[v.id].partition_index; }
alpar@1356
  1871
    static int id(Arc e) { return e.id; }
alpar@1356
  1872
    static int id(Edge e) { return e.id; }
alpar@1356
  1873
alpar@1356
  1874
    static Node nodeFromId(int id) { return Node(id);}
alpar@1356
  1875
    static Arc arcFromId(int id) { return Arc(id);}
alpar@1356
  1876
    static Edge edgeFromId(int id) { return Edge(id);}
alpar@1356
  1877
alpar@1356
  1878
    bool valid(Node n) const {
alpar@1356
  1879
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@1356
  1880
        nodes[n.id].prev != -2;
alpar@1356
  1881
    }
alpar@1356
  1882
alpar@1356
  1883
    bool valid(Arc a) const {
alpar@1356
  1884
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@1356
  1885
        arcs[a.id].prev_out != -2;
alpar@1356
  1886
    }
alpar@1356
  1887
alpar@1356
  1888
    bool valid(Edge e) const {
alpar@1356
  1889
      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
alpar@1356
  1890
        arcs[2 * e.id].prev_out != -2;
alpar@1356
  1891
    }
alpar@1356
  1892
alpar@1356
  1893
    RedNode addRedNode() {
alpar@1356
  1894
      int n;
alpar@1356
  1895
alpar@1356
  1896
      if(first_free_red==-1) {
alpar@1356
  1897
        n = nodes.size();
alpar@1356
  1898
        nodes.push_back(NodeT());
alpar@1356
  1899
        nodes[n].partition_index = ++max_red;
alpar@1356
  1900
        nodes[n].red = true;
alpar@1356
  1901
      } else {
alpar@1356
  1902
        n = first_free_red;
alpar@1356
  1903
        first_free_red = nodes[n].next;
alpar@1356
  1904
      }
alpar@1356
  1905
alpar@1356
  1906
      nodes[n].next = first_node;
alpar@1356
  1907
      if (first_node != -1) nodes[first_node].prev = n;
alpar@1356
  1908
      first_node = n;
alpar@1356
  1909
      nodes[n].prev = -1;
alpar@1356
  1910
alpar@1356
  1911
      nodes[n].partition_next = first_red;
alpar@1356
  1912
      if (first_red != -1) nodes[first_red].partition_prev = n;
alpar@1356
  1913
      first_red = n;
alpar@1356
  1914
      nodes[n].partition_prev = -1;
alpar@1356
  1915
alpar@1356
  1916
      nodes[n].first_out = -1;
alpar@1356
  1917
alpar@1356
  1918
      return RedNode(n);
alpar@1356
  1919
    }
alpar@1356
  1920
alpar@1356
  1921
    BlueNode addBlueNode() {
alpar@1356
  1922
      int n;
alpar@1356
  1923
alpar@1356
  1924
      if(first_free_blue==-1) {
alpar@1356
  1925
        n = nodes.size();
alpar@1356
  1926
        nodes.push_back(NodeT());
alpar@1356
  1927
        nodes[n].partition_index = ++max_blue;
alpar@1356
  1928
        nodes[n].red = false;
alpar@1356
  1929
      } else {
alpar@1356
  1930
        n = first_free_blue;
alpar@1356
  1931
        first_free_blue = nodes[n].next;
alpar@1356
  1932
      }
alpar@1356
  1933
alpar@1356
  1934
      nodes[n].next = first_node;
alpar@1356
  1935
      if (first_node != -1) nodes[first_node].prev = n;
alpar@1356
  1936
      first_node = n;
alpar@1356
  1937
      nodes[n].prev = -1;
alpar@1356
  1938
alpar@1356
  1939
      nodes[n].partition_next = first_blue;
alpar@1356
  1940
      if (first_blue != -1) nodes[first_blue].partition_prev = n;
alpar@1356
  1941
      first_blue = n;
alpar@1356
  1942
      nodes[n].partition_prev = -1;
alpar@1356
  1943
alpar@1356
  1944
      nodes[n].first_out = -1;
alpar@1356
  1945
alpar@1356
  1946
      return BlueNode(n);
alpar@1356
  1947
    }
alpar@1356
  1948
alpar@1356
  1949
    Edge addEdge(Node u, Node v) {
alpar@1356
  1950
      int n;
alpar@1356
  1951
alpar@1356
  1952
      if (first_free_arc == -1) {
alpar@1356
  1953
        n = arcs.size();
alpar@1356
  1954
        arcs.push_back(ArcT());
alpar@1356
  1955
        arcs.push_back(ArcT());
alpar@1356
  1956
      } else {
alpar@1356
  1957
        n = first_free_arc;
alpar@1356
  1958
        first_free_arc = arcs[n].next_out;
alpar@1356
  1959
      }
alpar@1356
  1960
alpar@1356
  1961
      arcs[n].target = u.id;
alpar@1356
  1962
      arcs[n | 1].target = v.id;
alpar@1356
  1963
alpar@1356
  1964
      arcs[n].next_out = nodes[v.id].first_out;
alpar@1356
  1965
      if (nodes[v.id].first_out != -1) {
alpar@1356
  1966
        arcs[nodes[v.id].first_out].prev_out = n;
alpar@1356
  1967
      }
alpar@1356
  1968
      arcs[n].prev_out = -1;
alpar@1356
  1969
      nodes[v.id].first_out = n;
alpar@1356
  1970
alpar@1356
  1971
      arcs[n | 1].next_out = nodes[u.id].first_out;
alpar@1356
  1972
      if (nodes[u.id].first_out != -1) {
alpar@1356
  1973
        arcs[nodes[u.id].first_out].prev_out = (n | 1);
alpar@1356
  1974
      }
alpar@1356
  1975
      arcs[n | 1].prev_out = -1;
alpar@1356
  1976
      nodes[u.id].first_out = (n | 1);
alpar@1356
  1977
alpar@1356
  1978
      return Edge(n / 2);
alpar@1356
  1979
    }
alpar@1356
  1980
alpar@1356
  1981
    void erase(const Node& node) {
alpar@1356
  1982
      int n = node.id;
alpar@1356
  1983
alpar@1356
  1984
      if(nodes[n].next != -1) {
alpar@1356
  1985
        nodes[nodes[n].next].prev = nodes[n].prev;
alpar@1356
  1986
      }
alpar@1356
  1987
alpar@1356
  1988
      if(nodes[n].prev != -1) {
alpar@1356
  1989
        nodes[nodes[n].prev].next = nodes[n].next;
alpar@1356
  1990
      } else {
alpar@1356
  1991
        first_node = nodes[n].next;
alpar@1356
  1992
      }
alpar@1356
  1993
alpar@1356
  1994
      if (nodes[n].partition_next != -1) {
alpar@1356
  1995
        nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
alpar@1356
  1996
      }
alpar@1356
  1997
alpar@1356
  1998
      if (nodes[n].partition_prev != -1) {
alpar@1356
  1999
        nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
alpar@1356
  2000
      } else {
alpar@1356
  2001
        if (nodes[n].red) {
alpar@1356
  2002
          first_red = nodes[n].partition_next;
alpar@1356
  2003
        } else {
alpar@1356
  2004
          first_blue = nodes[n].partition_next;
alpar@1356
  2005
        }
alpar@1356
  2006
      }
alpar@1356
  2007
alpar@1356
  2008
      if (nodes[n].red) {
alpar@1356
  2009
        nodes[n].next = first_free_red;
alpar@1356
  2010
        first_free_red = n;
alpar@1356
  2011
      } else {
alpar@1356
  2012
        nodes[n].next = first_free_blue;
alpar@1356
  2013
        first_free_blue = n;
alpar@1356
  2014
      }
alpar@1356
  2015
      nodes[n].prev = -2;
alpar@1356
  2016
    }
alpar@1356
  2017
alpar@1356
  2018
    void erase(const Edge& edge) {
alpar@1356
  2019
      int n = edge.id * 2;
alpar@1356
  2020
alpar@1356
  2021
      if (arcs[n].next_out != -1) {
alpar@1356
  2022
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@1356
  2023
      }
alpar@1356
  2024
alpar@1356
  2025
      if (arcs[n].prev_out != -1) {
alpar@1356
  2026
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
alpar@1356
  2027
      } else {
alpar@1356
  2028
        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
alpar@1356
  2029
      }
alpar@1356
  2030
alpar@1356
  2031
      if (arcs[n | 1].next_out != -1) {
alpar@1356
  2032
        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
alpar@1356
  2033
      }
alpar@1356
  2034
alpar@1356
  2035
      if (arcs[n | 1].prev_out != -1) {
alpar@1356
  2036
        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
alpar@1356
  2037
      } else {
alpar@1356
  2038
        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
alpar@1356
  2039
      }
alpar@1356
  2040
alpar@1356
  2041
      arcs[n].next_out = first_free_arc;
alpar@1356
  2042
      first_free_arc = n;
alpar@1356
  2043
      arcs[n].prev_out = -2;
alpar@1356
  2044
      arcs[n | 1].prev_out = -2;
alpar@1356
  2045
alpar@1356
  2046
    }
alpar@1356
  2047
alpar@1356
  2048
    void clear() {
alpar@1356
  2049
      arcs.clear();
alpar@1356
  2050
      nodes.clear();
alpar@1356
  2051
      first_node = first_free_arc = first_red = first_blue =
alpar@1356
  2052
        max_red = max_blue = first_free_red = first_free_blue = -1;
alpar@1356
  2053
    }
alpar@1356
  2054
alpar@1356
  2055
  protected:
alpar@1356
  2056
alpar@1356
  2057
    void changeRed(Edge e, RedNode n) {
alpar@1356
  2058
      if(arcs[(2 * e.id) | 1].next_out != -1) {
alpar@1356
  2059
        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
alpar@1356
  2060
          arcs[(2 * e.id) | 1].prev_out;
alpar@1356
  2061
      }
alpar@1356
  2062
      if(arcs[(2 * e.id) | 1].prev_out != -1) {
alpar@1356
  2063
        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
alpar@1356
  2064
          arcs[(2 * e.id) | 1].next_out;
alpar@1356
  2065
      } else {
alpar@1356
  2066
        nodes[arcs[2 * e.id].target].first_out =
alpar@1356
  2067
          arcs[(2 * e.id) | 1].next_out;
alpar@1356
  2068
      }
alpar@1356
  2069
alpar@1356
  2070
      if (nodes[n.id].first_out != -1) {
alpar@1356
  2071
        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
alpar@1356
  2072
      }
alpar@1356
  2073
      arcs[2 * e.id].target = n.id;
alpar@1356
  2074
      arcs[(2 * e.id) | 1].prev_out = -1;
alpar@1356
  2075
      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
alpar@1356
  2076
      nodes[n.id].first_out = ((2 * e.id) | 1);
alpar@1356
  2077
    }
alpar@1356
  2078
alpar@1356
  2079
    void changeBlue(Edge e, BlueNode n) {
alpar@1356
  2080
       if(arcs[2 * e.id].next_out != -1) {
alpar@1356
  2081
        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
alpar@1356
  2082
      }
alpar@1356
  2083
      if(arcs[2 * e.id].prev_out != -1) {
alpar@1356
  2084
        arcs[arcs[2 * e.id].prev_out].next_out =
alpar@1356
  2085
          arcs[2 * e.id].next_out;
alpar@1356
  2086
      } else {
alpar@1356
  2087
        nodes[arcs[(2 * e.id) | 1].target].first_out =
alpar@1356
  2088
          arcs[2 * e.id].next_out;
alpar@1356
  2089
      }
alpar@1356
  2090
alpar@1356
  2091
      if (nodes[n.id].first_out != -1) {
alpar@1356
  2092
        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
alpar@1356
  2093
      }
alpar@1356
  2094
      arcs[(2 * e.id) | 1].target = n.id;
alpar@1356
  2095
      arcs[2 * e.id].prev_out = -1;
alpar@1356
  2096
      arcs[2 * e.id].next_out = nodes[n.id].first_out;
alpar@1356
  2097
      nodes[n.id].first_out = 2 * e.id;
alpar@1356
  2098
    }
alpar@1356
  2099
alpar@1356
  2100
  };
alpar@1356
  2101
alpar@1356
  2102
  typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
alpar@1356
  2103
alpar@1356
  2104
alpar@1356
  2105
  /// \addtogroup graphs
alpar@1356
  2106
  /// @{
alpar@1356
  2107
alpar@1356
  2108
  ///A general undirected graph structure.
alpar@1356
  2109
alpar@1356
  2110
  ///\ref ListBpGraph is a versatile and fast undirected graph
alpar@1356
  2111
  ///implementation based on linked lists that are stored in
alpar@1356
  2112
  ///\c std::vector structures.
alpar@1356
  2113
  ///
alpar@1356
  2114
  ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
alpar@1356
  2115
  ///and it also provides several useful additional functionalities.
alpar@1356
  2116
  ///Most of its member functions and nested classes are documented
alpar@1356
  2117
  ///only in the concept class.
alpar@1356
  2118
  ///
alpar@1356
  2119
  ///This class provides only linear time counting for nodes, edges and arcs.
alpar@1356
  2120
  ///
alpar@1356
  2121
  ///\sa concepts::BpGraph
alpar@1356
  2122
  ///\sa ListDigraph
alpar@1356
  2123
  class ListBpGraph : public ExtendedListBpGraphBase {
alpar@1356
  2124
    typedef ExtendedListBpGraphBase Parent;
alpar@1356
  2125
alpar@1356
  2126
  private:
alpar@1356
  2127
    /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
alpar@1356
  2128
    ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase()  {};
alpar@1356
  2129
    /// \brief Assignment of a graph to another one is \e not allowed.
alpar@1356
  2130
    /// Use BpGraphCopy instead.
alpar@1356
  2131
    void operator=(const ListBpGraph &) {}
alpar@1356
  2132
  public:
alpar@1356
  2133
    /// Constructor
alpar@1356
  2134
alpar@1356
  2135
    /// Constructor.
alpar@1356
  2136
    ///
alpar@1356
  2137
    ListBpGraph() {}
alpar@1356
  2138
alpar@1425
  2139
    typedef Parent::IncEdgeIt IncEdgeIt;
alpar@1356
  2140
alpar@1356
  2141
    /// \brief Add a new red node to the graph.
alpar@1356
  2142
    ///
alpar@1356
  2143
    /// This function adds a red new node to the graph.
alpar@1356
  2144
    /// \return The new node.
alpar@1356
  2145
    RedNode addRedNode() { return Parent::addRedNode(); }
alpar@1356
  2146
alpar@1356
  2147
    /// \brief Add a new blue node to the graph.
alpar@1356
  2148
    ///
alpar@1356
  2149
    /// This function adds a blue new node to the graph.
alpar@1356
  2150
    /// \return The new node.
alpar@1356
  2151
    BlueNode addBlueNode() { return Parent::addBlueNode(); }
alpar@1356
  2152
alpar@1356
  2153
    /// \brief Add a new edge to the graph.
alpar@1356
  2154
    ///
alpar@1356
  2155
    /// This function adds a new edge to the graph between nodes
alpar@1356
  2156
    /// \c u and \c v with inherent orientation from node \c u to
alpar@1356
  2157
    /// node \c v.
alpar@1356
  2158
    /// \return The new edge.
alpar@1356
  2159
    Edge addEdge(RedNode u, BlueNode v) {
alpar@1356
  2160
      return Parent::addEdge(u, v);
alpar@1356
  2161
    }
alpar@1356
  2162
    Edge addEdge(BlueNode v, RedNode u) {
alpar@1356
  2163
      return Parent::addEdge(u, v);
alpar@1356
  2164
    }
alpar@1356
  2165
alpar@1356
  2166
    ///\brief Erase a node from the graph.
alpar@1356
  2167
    ///
alpar@1356
  2168
    /// This function erases the given node along with its incident arcs
alpar@1356
  2169
    /// from the graph.
alpar@1356
  2170
    ///
alpar@1356
  2171
    /// \note All iterators referencing the removed node or the incident
alpar@1356
  2172
    /// edges are invalidated, of course.
alpar@1356
  2173
    void erase(Node n) { Parent::erase(n); }
alpar@1356
  2174
alpar@1356
  2175
    ///\brief Erase an edge from the graph.
alpar@1356
  2176
    ///
alpar@1356
  2177
    /// This function erases the given edge from the graph.
alpar@1356
  2178
    ///
alpar@1356
  2179
    /// \note All iterators referencing the removed edge are invalidated,
alpar@1356
  2180
    /// of course.
alpar@1356
  2181
    void erase(Edge e) { Parent::erase(e); }
alpar@1356
  2182
    /// Node validity check
alpar@1356
  2183
alpar@1356
  2184
    /// This function gives back \c true if the given node is valid,
alpar@1356
  2185
    /// i.e. it is a real node of the graph.
alpar@1356
  2186
    ///
alpar@1356
  2187
    /// \warning A removed node could become valid again if new nodes are
alpar@1356
  2188
    /// added to the graph.
alpar@1356
  2189
    bool valid(Node n) const { return Parent::valid(n); }
alpar@1356
  2190
    /// Edge validity check
alpar@1356
  2191
alpar@1356
  2192
    /// This function gives back \c true if the given edge is valid,
alpar@1356
  2193
    /// i.e. it is a real edge of the graph.
alpar@1356
  2194
    ///
alpar@1356
  2195
    /// \warning A removed edge could become valid again if new edges are
alpar@1356
  2196
    /// added to the graph.
alpar@1356
  2197
    bool valid(Edge e) const { return Parent::valid(e); }
alpar@1356
  2198
    /// Arc validity check
alpar@1356
  2199
alpar@1356
  2200
    /// This function gives back \c true if the given arc is valid,
alpar@1356
  2201
    /// i.e. it is a real arc of the graph.
alpar@1356
  2202
    ///
alpar@1356
  2203
    /// \warning A removed arc could become valid again if new edges are
alpar@1356
  2204
    /// added to the graph.
alpar@1356
  2205
    bool valid(Arc a) const { return Parent::valid(a); }
alpar@1356
  2206
alpar@1356
  2207
    /// \brief Change the red node of an edge.
alpar@1356
  2208
    ///
alpar@1356
  2209
    /// This function changes the red node of the given edge \c e to \c n.
alpar@1356
  2210
    ///
alpar@1356
  2211
    ///\note \c EdgeIt and \c ArcIt iterators referencing the
alpar@1356
  2212
    ///changed edge are invalidated and all other iterators whose
alpar@1356
  2213
    ///base node is the changed node are also invalidated.
alpar@1356
  2214
    ///
alpar@1356
  2215
    ///\warning This functionality cannot be used together with the
alpar@1356
  2216
    ///Snapshot feature.
alpar@1356
  2217
    void changeRed(Edge e, RedNode n) {
alpar@1356
  2218
      Parent::changeRed(e, n);
alpar@1356
  2219
    }
alpar@1356
  2220
    /// \brief Change the blue node of an edge.
alpar@1356
  2221
    ///
alpar@1356
  2222
    /// This function changes the blue node of the given edge \c e to \c n.
alpar@1356
  2223
    ///
alpar@1356
  2224
    ///\note \c EdgeIt iterators referencing the changed edge remain
alpar@1356
  2225
    ///valid, but \c ArcIt iterators referencing the changed edge and
alpar@1356
  2226
    ///all other iterators whose base node is the changed node are also
alpar@1356
  2227
    ///invalidated.
alpar@1356
  2228
    ///
alpar@1356
  2229
    ///\warning This functionality cannot be used together with the
alpar@1356
  2230
    ///Snapshot feature.
alpar@1356
  2231
    void changeBlue(Edge e, BlueNode n) {
alpar@1356
  2232
      Parent::changeBlue(e, n);
alpar@1356
  2233
    }
alpar@1356
  2234
alpar@1356
  2235
    ///Clear the graph.
alpar@1356
  2236
alpar@1356
  2237
    ///This function erases all nodes and arcs from the graph.
alpar@1356
  2238
    ///
alpar@1356
  2239
    ///\note All iterators of the graph are invalidated, of course.
alpar@1356
  2240
    void clear() {
alpar@1356
  2241
      Parent::clear();
alpar@1356
  2242
    }
alpar@1356
  2243
alpar@1356
  2244
    /// Reserve memory for nodes.
alpar@1356
  2245
alpar@1356
  2246
    /// Using this function, it is possible to avoid superfluous memory
alpar@1356
  2247
    /// allocation: if you know that the graph you want to build will
alpar@1356
  2248
    /// be large (e.g. it will contain millions of nodes and/or edges),
alpar@1356
  2249
    /// then it is worth reserving space for this amount before starting
alpar@1356
  2250
    /// to build the graph.
alpar@1356
  2251
    /// \sa reserveEdge()
alpar@1356
  2252
    void reserveNode(int n) { nodes.reserve(n); };
alpar@1356
  2253
alpar@1356
  2254
    /// Reserve memory for edges.
alpar@1356
  2255
alpar@1356
  2256
    /// Using this function, it is possible to avoid superfluous memory
alpar@1356
  2257
    /// allocation: if you know that the graph you want to build will
alpar@1356
  2258
    /// be large (e.g. it will contain millions of nodes and/or edges),
alpar@1356
  2259
    /// then it is worth reserving space for this amount before starting
alpar@1356
  2260
    /// to build the graph.
alpar@1356
  2261
    /// \sa reserveNode()
alpar@1356
  2262
    void reserveEdge(int m) { arcs.reserve(2 * m); };
alpar@1356
  2263
alpar@1356
  2264
    /// \brief Class to make a snapshot of the graph and restore
alpar@1356
  2265
    /// it later.
alpar@1356
  2266
    ///
alpar@1356
  2267
    /// Class to make a snapshot of the graph and restore it later.
alpar@1356
  2268
    ///
alpar@1356
  2269
    /// The newly added nodes and edges can be removed
alpar@1356
  2270
    /// using the restore() function.
alpar@1356
  2271
    ///
alpar@1356
  2272
    /// \note After a state is restored, you cannot restore a later state,
alpar@1356
  2273
    /// i.e. you cannot add the removed nodes and edges again using
alpar@1356
  2274
    /// another Snapshot instance.
alpar@1356
  2275
    ///
alpar@1356
  2276
    /// \warning Node and edge deletions and other modifications
alpar@1356
  2277
    /// (e.g. changing the end-nodes of edges or contracting nodes)
alpar@1356
  2278
    /// cannot be restored. These events invalidate the snapshot.
alpar@1356
  2279
    /// However, the edges and nodes that were added to the graph after
alpar@1356
  2280
    /// making the current snapshot can be removed without invalidating it.
alpar@1356
  2281
    class Snapshot {
alpar@1356
  2282
    protected:
alpar@1356
  2283
alpar@1356
  2284
      typedef Parent::NodeNotifier NodeNotifier;
alpar@1356
  2285
alpar@1356
  2286
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
alpar@1356
  2287
      public:
alpar@1356
  2288
alpar@1356
  2289
        NodeObserverProxy(Snapshot& _snapshot)
alpar@1356
  2290
          : snapshot(_snapshot) {}
alpar@1356
  2291
alpar@1356
  2292
        using NodeNotifier::ObserverBase::attach;
alpar@1356
  2293
        using NodeNotifier::ObserverBase::detach;
alpar@1356
  2294
        using NodeNotifier::ObserverBase::attached;
alpar@1356
  2295
alpar@1356
  2296
      protected:
alpar@1356
  2297
alpar@1356
  2298
        virtual void add(const Node& node) {
alpar@1356
  2299
          snapshot.addNode(node);
alpar@1356
  2300
        }
alpar@1356
  2301
        virtual void add(const std::vector<Node>& nodes) {
alpar@1357
  2302
          for (int i = nodes.size() - 1; i >= 0; --i) {
alpar@956
  2303
            snapshot.addNode(nodes[i]);
alpar@956
  2304
          }
alpar@956
  2305
        }
alpar@956
  2306
        virtual void erase(const Node& node) {
alpar@956
  2307
          snapshot.eraseNode(node);
alpar@956
  2308
        }
alpar@956
  2309
        virtual void erase(const std::vector<Node>& nodes) {
alpar@956
  2310
          for (int i = 0; i < int(nodes.size()); ++i) {
alpar@956
  2311
            snapshot.eraseNode(nodes[i]);
alpar@956
  2312
          }
alpar@956
  2313
        }
alpar@956
  2314
        virtual void build() {
alpar@956
  2315
          Node node;
alpar@956
  2316
          std::vector<Node> nodes;
alpar@956
  2317
          for (notifier()->first(node); node != INVALID;
alpar@956
  2318
               notifier()->next(node)) {
alpar@956
  2319
            nodes.push_back(node);
alpar@956
  2320
          }
alpar@956
  2321
          for (int i = nodes.size() - 1; i >= 0; --i) {
alpar@956
  2322
            snapshot.addNode(nodes[i]);
alpar@956
  2323
          }
alpar@956
  2324
        }
alpar@956
  2325
        virtual void clear() {
alpar@956
  2326
          Node node;
alpar@956
  2327
          for (notifier()->first(node); node != INVALID;
alpar@956
  2328
               notifier()->next(node)) {
alpar@956
  2329
            snapshot.eraseNode(node);
alpar@956
  2330
          }
alpar@956
  2331
        }
alpar@956
  2332
alpar@956
  2333
        Snapshot& snapshot;
alpar@956
  2334
      };
alpar@956
  2335
alpar@956
  2336
      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
alpar@956
  2337
      public:
alpar@956
  2338
alpar@956
  2339
        EdgeObserverProxy(Snapshot& _snapshot)
alpar@956
  2340
          : snapshot(_snapshot) {}
alpar@956
  2341
alpar@956
  2342
        using EdgeNotifier::ObserverBase::attach;
alpar@956
  2343
        using EdgeNotifier::ObserverBase::detach;
alpar@956
  2344
        using EdgeNotifier::ObserverBase::attached;
alpar@956
  2345
alpar@956
  2346
      protected:
alpar@956
  2347
alpar@956
  2348
        virtual void add(const Edge& edge) {
alpar@956
  2349
          snapshot.addEdge(edge);
alpar@956
  2350
        }
alpar@956
  2351
        virtual void add(const std::vector<Edge>& edges) {
alpar@1357
  2352
          for (int i = edges.size() - 1; i >= 0; --i) {
alpar@956
  2353
            snapshot.addEdge(edges[i]);
alpar@956
  2354
          }
alpar@956
  2355
        }
alpar@956
  2356
        virtual void erase(const Edge& edge) {
alpar@956
  2357
          snapshot.eraseEdge(edge);
alpar@956
  2358
        }
alpar@956
  2359
        virtual void erase(const std::vector<Edge>& edges) {
alpar@956
  2360
          for (int i = 0; i < int(edges.size()); ++i) {
alpar@956
  2361
            snapshot.eraseEdge(edges[i]);
alpar@956
  2362
          }
alpar@956
  2363
        }
alpar@956
  2364
        virtual void build() {
alpar@956
  2365
          Edge edge;
alpar@956
  2366
          std::vector<Edge> edges;
alpar@956
  2367
          for (notifier()->first(edge); edge != INVALID;
alpar@956
  2368
               notifier()->next(edge)) {
alpar@956
  2369
            edges.push_back(edge);
alpar@956
  2370
          }
alpar@956
  2371
          for (int i = edges.size() - 1; i >= 0; --i) {
alpar@956
  2372
            snapshot.addEdge(edges[i]);
alpar@956
  2373
          }
alpar@956
  2374
        }
alpar@956
  2375
        virtual void clear() {
alpar@956
  2376
          Edge edge;
alpar@956
  2377
          for (notifier()->first(edge); edge != INVALID;
alpar@956
  2378
               notifier()->next(edge)) {
alpar@956
  2379
            snapshot.eraseEdge(edge);
alpar@956
  2380
          }
alpar@956
  2381
        }
alpar@956
  2382
alpar@956
  2383
        Snapshot& snapshot;
alpar@956
  2384
      };
alpar@956
  2385
deba@1189
  2386
      ListBpGraph *graph;
deba@1189
  2387
deba@1189
  2388
      NodeObserverProxy node_observer_proxy;
deba@1189
  2389
      EdgeObserverProxy edge_observer_proxy;
deba@1189
  2390
deba@1189
  2391
      std::list<Node> added_nodes;
deba@1189
  2392
      std::list<Edge> added_edges;
deba@1189
  2393
deba@1189
  2394
deba@1189
  2395
      void addNode(const Node& node) {
deba@1189
  2396
        added_nodes.push_front(node);
deba@1189
  2397
      }
deba@1189
  2398
      void eraseNode(const Node& node) {
deba@1189
  2399
        std::list<Node>::iterator it =
deba@1189
  2400
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@1189
  2401
        if (it == added_nodes.end()) {
deba@1189
  2402
          clear();
deba@1189
  2403
          edge_observer_proxy.detach();
deba@1189
  2404
          throw NodeNotifier::ImmediateDetach();
deba@1189
  2405
        } else {
deba@1189
  2406
          added_nodes.erase(it);
deba@1189
  2407
        }
deba@1189
  2408
      }
deba@1189
  2409
deba@1189
  2410
      void addEdge(const Edge& edge) {
deba@1189
  2411
        added_edges.push_front(edge);
deba@1189
  2412
      }
deba@1189
  2413
      void eraseEdge(const Edge& edge) {
deba@1189
  2414
        std::list<Edge>::iterator it =
deba@1189
  2415
          std::find(added_edges.begin(), added_edges.end(), edge);
deba@1189
  2416
        if (it == added_edges.end()) {
deba@1189
  2417
          clear();
deba@1189
  2418
          node_observer_proxy.detach();
deba@1189
  2419
          throw EdgeNotifier::ImmediateDetach();
deba@1189
  2420
        } else {
deba@1189
  2421
          added_edges.erase(it);
deba@1189
  2422
        }
deba@1189
  2423
      }
deba@1189
  2424
deba@1189
  2425
      void attach(ListBpGraph &_graph) {
deba@1189
  2426
        graph = &_graph;
deba@1189
  2427
        node_observer_proxy.attach(graph->notifier(Node()));
deba@1189
  2428
        edge_observer_proxy.attach(graph->notifier(Edge()));
deba@1189
  2429
      }
deba@1189
  2430
deba@1189
  2431
      void detach() {
deba@1189
  2432
        node_observer_proxy.detach();
deba@1189
  2433
        edge_observer_proxy.detach();
deba@1189
  2434
      }
deba@1189
  2435
deba@1189
  2436
      bool attached() const {
deba@1189
  2437
        return node_observer_proxy.attached();
deba@1189
  2438
      }
deba@1189
  2439
deba@1189
  2440
      void clear() {
deba@1189
  2441
        added_nodes.clear();
deba@1189
  2442
        added_edges.clear();
deba@1189
  2443
      }
deba@1189
  2444
deba@1189
  2445
    public:
deba@1189
  2446
deba@1189
  2447
      /// \brief Default constructor.
deba@1189
  2448
      ///
deba@1189
  2449
      /// Default constructor.
deba@1189
  2450
      /// You have to call save() to actually make a snapshot.
deba@1189
  2451
      Snapshot()
deba@1189
  2452
        : graph(0), node_observer_proxy(*this),
deba@1189
  2453
          edge_observer_proxy(*this) {}
deba@1189
  2454
deba@1189
  2455
      /// \brief Constructor that immediately makes a snapshot.
deba@1189
  2456
      ///
deba@1189
  2457
      /// This constructor immediately makes a snapshot of the given graph.
deba@1189
  2458
      Snapshot(ListBpGraph &gr)
deba@1189
  2459
        : node_observer_proxy(*this),
deba@1189
  2460
          edge_observer_proxy(*this) {
deba@1189
  2461
        attach(gr);
deba@1189
  2462
      }
deba@1189
  2463
deba@1189
  2464
      /// \brief Make a snapshot.
deba@1189
  2465
      ///
deba@1189
  2466
      /// This function makes a snapshot of the given graph.
deba@1189
  2467
      /// It can be called more than once. In case of a repeated
deba@1189
  2468
      /// call, the previous snapshot gets lost.
deba@1189
  2469
      void save(ListBpGraph &gr) {
deba@1189
  2470
        if (attached()) {
deba@1189
  2471
          detach();
deba@1189
  2472
          clear();
deba@1189
  2473
        }
deba@1189
  2474
        attach(gr);
deba@1189
  2475
      }
deba@1189
  2476
deba@1189
  2477
      /// \brief Undo the changes until the last snapshot.
deba@1189
  2478
      ///
deba@1189
  2479
      /// This function undos the changes until the last snapshot
deba@1189
  2480
      /// created by save() or Snapshot(ListBpGraph&).
deba@1189
  2481
      ///
deba@1189
  2482
      /// \warning This method invalidates the snapshot, i.e. repeated
deba@1189
  2483
      /// restoring is not supported unless you call save() again.
deba@1189
  2484
      void restore() {
deba@1189
  2485
        detach();
deba@1189
  2486
        for(std::list<Edge>::iterator it = added_edges.begin();
deba@1189
  2487
            it != added_edges.end(); ++it) {
deba@1189
  2488
          graph->erase(*it);
deba@1189
  2489
        }
deba@1189
  2490
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@1189
  2491
            it != added_nodes.end(); ++it) {
deba@1189
  2492
          graph->erase(*it);
deba@1189
  2493
        }
deba@1189
  2494
        clear();
deba@1189
  2495
      }
deba@1189
  2496
deba@1189
  2497
      /// \brief Returns \c true if the snapshot is valid.
deba@1189
  2498
      ///
deba@1189
  2499
      /// This function returns \c true if the snapshot is valid.
deba@1189
  2500
      bool valid() const {
deba@1189
  2501
        return attached();
deba@1189
  2502
      }
deba@1189
  2503
    };
deba@1189
  2504
  };
deba@1189
  2505
deba@1189
  2506
  /// @}
deba@57
  2507
} //namespace lemon
alpar@209
  2508
deba@57
  2509
deba@57
  2510
#endif