lemon/list_graph.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 23 Jul 2008 19:32:48 +0200
changeset 233 28239207a8a3
parent 212 1ae84dea7d09
child 234 ad6b8c47bd56
permissions -rw-r--r--
Unify DynArcLookUp interface (ticket #127)
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@39
     5
 * Copyright (C) 2003-2008
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
deba@57
    24
///\brief ListDigraph, 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
deba@57
    35
  class ListDigraphBase {
deba@57
    36
deba@57
    37
  protected:
deba@57
    38
    struct NodeT {
deba@57
    39
      int first_in, first_out;
deba@57
    40
      int prev, next;
deba@57
    41
    };
alpar@209
    42
deba@57
    43
    struct ArcT {
deba@57
    44
      int target, source;
deba@57
    45
      int prev_in, prev_out;
deba@57
    46
      int next_in, next_out;
deba@57
    47
    };
deba@57
    48
deba@57
    49
    std::vector<NodeT> nodes;
deba@57
    50
deba@57
    51
    int first_node;
deba@57
    52
deba@57
    53
    int first_free_node;
deba@57
    54
deba@57
    55
    std::vector<ArcT> arcs;
deba@57
    56
deba@57
    57
    int first_free_arc;
alpar@209
    58
deba@57
    59
  public:
alpar@209
    60
deba@57
    61
    typedef ListDigraphBase Digraph;
alpar@209
    62
deba@57
    63
    class Node {
deba@57
    64
      friend class ListDigraphBase;
deba@57
    65
    protected:
deba@57
    66
deba@57
    67
      int id;
deba@57
    68
      explicit Node(int pid) { id = pid;}
deba@57
    69
deba@57
    70
    public:
deba@57
    71
      Node() {}
deba@57
    72
      Node (Invalid) { id = -1; }
deba@57
    73
      bool operator==(const Node& node) const {return id == node.id;}
deba@57
    74
      bool operator!=(const Node& node) const {return id != node.id;}
deba@57
    75
      bool operator<(const Node& node) const {return id < node.id;}
deba@57
    76
    };
deba@57
    77
deba@57
    78
    class Arc {
deba@57
    79
      friend class ListDigraphBase;
deba@57
    80
    protected:
deba@57
    81
deba@57
    82
      int id;
deba@57
    83
      explicit Arc(int pid) { id = pid;}
deba@57
    84
deba@57
    85
    public:
deba@57
    86
      Arc() {}
deba@57
    87
      Arc (Invalid) { id = -1; }
deba@57
    88
      bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57
    89
      bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57
    90
      bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57
    91
    };
deba@57
    92
deba@57
    93
deba@57
    94
deba@57
    95
    ListDigraphBase()
deba@57
    96
      : nodes(), first_node(-1),
alpar@209
    97
        first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57
    98
alpar@209
    99
alpar@209
   100
    int maxNodeId() const { return nodes.size()-1; }
deba@57
   101
    int maxArcId() const { return arcs.size()-1; }
deba@57
   102
deba@57
   103
    Node source(Arc e) const { return Node(arcs[e.id].source); }
deba@57
   104
    Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57
   105
deba@57
   106
alpar@209
   107
    void first(Node& node) const {
deba@57
   108
      node.id = first_node;
deba@57
   109
    }
deba@57
   110
deba@57
   111
    void next(Node& node) const {
deba@57
   112
      node.id = nodes[node.id].next;
deba@57
   113
    }
deba@57
   114
deba@57
   115
alpar@209
   116
    void first(Arc& arc) const {
deba@57
   117
      int n;
alpar@209
   118
      for(n = first_node;
alpar@209
   119
          n!=-1 && nodes[n].first_in == -1;
alpar@209
   120
          n = nodes[n].next) {}
kpeter@73
   121
      arc.id = (n == -1) ? -1 : nodes[n].first_in;
deba@57
   122
    }
deba@57
   123
deba@57
   124
    void next(Arc& arc) const {
deba@57
   125
      if (arcs[arc.id].next_in != -1) {
alpar@209
   126
        arc.id = arcs[arc.id].next_in;
deba@57
   127
      } else {
alpar@209
   128
        int n;
alpar@209
   129
        for(n = nodes[arcs[arc.id].target].next;
alpar@209
   130
            n!=-1 && nodes[n].first_in == -1;
alpar@209
   131
            n = nodes[n].next) {}
alpar@209
   132
        arc.id = (n == -1) ? -1 : nodes[n].first_in;
alpar@209
   133
      }
deba@57
   134
    }
deba@57
   135
deba@57
   136
    void firstOut(Arc &e, const Node& v) const {
deba@57
   137
      e.id = nodes[v.id].first_out;
deba@57
   138
    }
deba@57
   139
    void nextOut(Arc &e) const {
deba@57
   140
      e.id=arcs[e.id].next_out;
deba@57
   141
    }
deba@57
   142
deba@57
   143
    void firstIn(Arc &e, const Node& v) const {
deba@57
   144
      e.id = nodes[v.id].first_in;
deba@57
   145
    }
deba@57
   146
    void nextIn(Arc &e) const {
deba@57
   147
      e.id=arcs[e.id].next_in;
deba@57
   148
    }
deba@57
   149
alpar@209
   150
deba@57
   151
    static int id(Node v) { return v.id; }
deba@57
   152
    static int id(Arc e) { return e.id; }
deba@57
   153
deba@57
   154
    static Node nodeFromId(int id) { return Node(id);}
deba@57
   155
    static Arc arcFromId(int id) { return Arc(id);}
deba@57
   156
alpar@209
   157
    bool valid(Node n) const {
alpar@209
   158
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209
   159
        nodes[n.id].prev != -2;
deba@149
   160
    }
deba@149
   161
alpar@209
   162
    bool valid(Arc a) const {
alpar@209
   163
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209
   164
        arcs[a.id].prev_in != -2;
deba@149
   165
    }
deba@149
   166
alpar@209
   167
    Node addNode() {
deba@57
   168
      int n;
alpar@209
   169
deba@57
   170
      if(first_free_node==-1) {
alpar@209
   171
        n = nodes.size();
alpar@209
   172
        nodes.push_back(NodeT());
deba@57
   173
      } else {
alpar@209
   174
        n = first_free_node;
alpar@209
   175
        first_free_node = nodes[n].next;
deba@57
   176
      }
alpar@209
   177
deba@57
   178
      nodes[n].next = first_node;
deba@57
   179
      if(first_node != -1) nodes[first_node].prev = n;
deba@57
   180
      first_node = n;
deba@57
   181
      nodes[n].prev = -1;
alpar@209
   182
deba@57
   183
      nodes[n].first_in = nodes[n].first_out = -1;
alpar@209
   184
deba@57
   185
      return Node(n);
deba@57
   186
    }
alpar@209
   187
deba@57
   188
    Arc addArc(Node u, Node v) {
alpar@209
   189
      int n;
deba@57
   190
deba@57
   191
      if (first_free_arc == -1) {
alpar@209
   192
        n = arcs.size();
alpar@209
   193
        arcs.push_back(ArcT());
deba@57
   194
      } else {
alpar@209
   195
        n = first_free_arc;
alpar@209
   196
        first_free_arc = arcs[n].next_in;
deba@57
   197
      }
alpar@209
   198
alpar@209
   199
      arcs[n].source = u.id;
deba@57
   200
      arcs[n].target = v.id;
deba@57
   201
deba@57
   202
      arcs[n].next_out = nodes[u.id].first_out;
deba@57
   203
      if(nodes[u.id].first_out != -1) {
alpar@209
   204
        arcs[nodes[u.id].first_out].prev_out = n;
deba@57
   205
      }
alpar@209
   206
deba@57
   207
      arcs[n].next_in = nodes[v.id].first_in;
deba@57
   208
      if(nodes[v.id].first_in != -1) {
alpar@209
   209
        arcs[nodes[v.id].first_in].prev_in = n;
deba@57
   210
      }
alpar@209
   211
deba@57
   212
      arcs[n].prev_in = arcs[n].prev_out = -1;
alpar@209
   213
deba@57
   214
      nodes[u.id].first_out = nodes[v.id].first_in = n;
deba@57
   215
deba@57
   216
      return Arc(n);
deba@57
   217
    }
alpar@209
   218
deba@57
   219
    void erase(const Node& node) {
deba@57
   220
      int n = node.id;
alpar@209
   221
deba@57
   222
      if(nodes[n].next != -1) {
alpar@209
   223
        nodes[nodes[n].next].prev = nodes[n].prev;
deba@57
   224
      }
alpar@209
   225
deba@57
   226
      if(nodes[n].prev != -1) {
alpar@209
   227
        nodes[nodes[n].prev].next = nodes[n].next;
deba@57
   228
      } else {
alpar@209
   229
        first_node = nodes[n].next;
deba@57
   230
      }
alpar@209
   231
deba@57
   232
      nodes[n].next = first_free_node;
deba@57
   233
      first_free_node = n;
deba@149
   234
      nodes[n].prev = -2;
deba@57
   235
deba@57
   236
    }
alpar@209
   237
deba@57
   238
    void erase(const Arc& arc) {
deba@57
   239
      int n = arc.id;
alpar@209
   240
deba@57
   241
      if(arcs[n].next_in!=-1) {
alpar@209
   242
        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
deba@57
   243
      }
deba@57
   244
deba@57
   245
      if(arcs[n].prev_in!=-1) {
alpar@209
   246
        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
deba@57
   247
      } else {
alpar@209
   248
        nodes[arcs[n].target].first_in = arcs[n].next_in;
deba@57
   249
      }
deba@57
   250
alpar@209
   251
deba@57
   252
      if(arcs[n].next_out!=-1) {
alpar@209
   253
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209
   254
      }
deba@57
   255
deba@57
   256
      if(arcs[n].prev_out!=-1) {
alpar@209
   257
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57
   258
      } else {
alpar@209
   259
        nodes[arcs[n].source].first_out = arcs[n].next_out;
deba@57
   260
      }
alpar@209
   261
deba@57
   262
      arcs[n].next_in = first_free_arc;
deba@149
   263
      first_free_arc = n;
deba@149
   264
      arcs[n].prev_in = -2;
deba@57
   265
    }
deba@57
   266
deba@57
   267
    void clear() {
deba@57
   268
      arcs.clear();
deba@57
   269
      nodes.clear();
deba@57
   270
      first_node = first_free_node = first_free_arc = -1;
deba@57
   271
    }
deba@57
   272
deba@57
   273
  protected:
alpar@209
   274
    void changeTarget(Arc e, Node n)
deba@57
   275
    {
deba@57
   276
      if(arcs[e.id].next_in != -1)
alpar@209
   277
        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
deba@57
   278
      if(arcs[e.id].prev_in != -1)
alpar@209
   279
        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
deba@57
   280
      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
deba@57
   281
      if (nodes[n.id].first_in != -1) {
alpar@209
   282
        arcs[nodes[n.id].first_in].prev_in = e.id;
deba@57
   283
      }
deba@57
   284
      arcs[e.id].target = n.id;
deba@57
   285
      arcs[e.id].prev_in = -1;
deba@57
   286
      arcs[e.id].next_in = nodes[n.id].first_in;
deba@57
   287
      nodes[n.id].first_in = e.id;
deba@57
   288
    }
alpar@209
   289
    void changeSource(Arc e, Node n)
deba@57
   290
    {
deba@57
   291
      if(arcs[e.id].next_out != -1)
alpar@209
   292
        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
deba@57
   293
      if(arcs[e.id].prev_out != -1)
alpar@209
   294
        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
deba@57
   295
      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
deba@57
   296
      if (nodes[n.id].first_out != -1) {
alpar@209
   297
        arcs[nodes[n.id].first_out].prev_out = e.id;
deba@57
   298
      }
deba@57
   299
      arcs[e.id].source = n.id;
deba@57
   300
      arcs[e.id].prev_out = -1;
deba@57
   301
      arcs[e.id].next_out = nodes[n.id].first_out;
deba@57
   302
      nodes[n.id].first_out = e.id;
deba@57
   303
    }
deba@57
   304
deba@57
   305
  };
deba@57
   306
deba@57
   307
  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
deba@57
   308
kpeter@73
   309
  /// \addtogroup graphs
deba@57
   310
  /// @{
deba@57
   311
alpar@209
   312
  ///A general directed graph structure.
deba@57
   313
alpar@209
   314
  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
alpar@209
   315
  ///implementation based on static linked lists that are stored in
alpar@209
   316
  ///\c std::vector structures.
deba@57
   317
  ///
deba@57
   318
  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
kpeter@73
   319
  ///also provides several useful additional functionalities.
kpeter@73
   320
  ///Most of the member functions and nested classes are documented
kpeter@73
   321
  ///only in the concept class.
deba@57
   322
  ///
deba@57
   323
  ///An important extra feature of this digraph implementation is that
deba@57
   324
  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
deba@57
   325
  ///
kpeter@73
   326
  ///\sa concepts::Digraph
deba@57
   327
deba@57
   328
  class ListDigraph : public ExtendedListDigraphBase {
deba@57
   329
  private:
kpeter@73
   330
    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
alpar@209
   331
kpeter@73
   332
    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
deba@57
   333
    ///
deba@57
   334
    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
deba@57
   335
    ///\brief Assignment of ListDigraph to another one is \e not allowed.
kpeter@73
   336
    ///Use copyDigraph() instead.
deba@57
   337
deba@57
   338
    ///Assignment of ListDigraph to another one is \e not allowed.
kpeter@73
   339
    ///Use copyDigraph() instead.
deba@57
   340
    void operator=(const ListDigraph &) {}
deba@57
   341
  public:
deba@57
   342
deba@57
   343
    typedef ExtendedListDigraphBase Parent;
deba@57
   344
deba@57
   345
    /// Constructor
alpar@209
   346
deba@57
   347
    /// Constructor.
deba@57
   348
    ///
deba@57
   349
    ListDigraph() {}
deba@57
   350
deba@57
   351
    ///Add a new node to the digraph.
alpar@209
   352
kpeter@73
   353
    ///Add a new node to the digraph.
kpeter@73
   354
    ///\return the new node.
deba@57
   355
    Node addNode() { return Parent::addNode(); }
deba@57
   356
deba@57
   357
    ///Add a new arc to the digraph.
alpar@209
   358
deba@57
   359
    ///Add a new arc to the digraph with source node \c s
deba@57
   360
    ///and target node \c t.
deba@57
   361
    ///\return the new arc.
alpar@209
   362
    Arc addArc(const Node& s, const Node& t) {
alpar@209
   363
      return Parent::addArc(s, t);
deba@57
   364
    }
deba@57
   365
deba@149
   366
    /// Node validity check
deba@149
   367
deba@149
   368
    /// This function gives back true if the given node is valid,
alpar@209
   369
    /// ie. it is a real node of the graph.
deba@149
   370
    ///
deba@149
   371
    /// \warning A Node pointing to a removed item
deba@149
   372
    /// could become valid again later if new nodes are
deba@149
   373
    /// added to the graph.
deba@149
   374
    bool valid(Node n) const { return Parent::valid(n); }
deba@149
   375
deba@149
   376
    /// Arc validity check
deba@149
   377
deba@149
   378
    /// This function gives back true if the given arc is valid,
alpar@209
   379
    /// ie. it is a real arc of the graph.
deba@149
   380
    ///
deba@149
   381
    /// \warning An Arc pointing to a removed item
deba@149
   382
    /// could become valid again later if new nodes are
deba@149
   383
    /// added to the graph.
deba@149
   384
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
   385
kpeter@73
   386
    /// Change the target of \c e to \c n
deba@57
   387
kpeter@73
   388
    /// Change the target of \c e to \c n
deba@57
   389
    ///
deba@57
   390
    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
deba@57
   391
    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
deba@57
   392
    ///invalidated.
kpeter@73
   393
    ///
deba@57
   394
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   395
    ///feature.
alpar@209
   396
    void changeTarget(Arc e, Node n) {
alpar@209
   397
      Parent::changeTarget(e,n);
deba@57
   398
    }
kpeter@73
   399
    /// Change the source of \c e to \c n
deba@57
   400
kpeter@73
   401
    /// Change the source of \c e to \c n
deba@57
   402
    ///
deba@57
   403
    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
deba@57
   404
    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
deba@57
   405
    ///invalidated.
kpeter@73
   406
    ///
deba@57
   407
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   408
    ///feature.
alpar@209
   409
    void changeSource(Arc e, Node n) {
deba@57
   410
      Parent::changeSource(e,n);
deba@57
   411
    }
deba@57
   412
deba@57
   413
    /// Invert the direction of an arc.
deba@57
   414
deba@57
   415
    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
deba@57
   416
    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
deba@57
   417
    ///invalidated.
kpeter@73
   418
    ///
deba@57
   419
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   420
    ///feature.
deba@57
   421
    void reverseArc(Arc e) {
deba@57
   422
      Node t=target(e);
deba@57
   423
      changeTarget(e,source(e));
deba@57
   424
      changeSource(e,t);
deba@57
   425
    }
deba@57
   426
kpeter@73
   427
    /// Reserve memory for nodes.
kpeter@73
   428
kpeter@73
   429
    /// Using this function it is possible to avoid the superfluous memory
deba@57
   430
    /// allocation: if you know that the digraph you want to build will
deba@57
   431
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
deba@57
   432
    /// then it is worth reserving space for this amount before starting
deba@57
   433
    /// to build the digraph.
deba@57
   434
    /// \sa reserveArc
deba@57
   435
    void reserveNode(int n) { nodes.reserve(n); };
deba@57
   436
kpeter@73
   437
    /// Reserve memory for arcs.
deba@57
   438
kpeter@73
   439
    /// Using this function it is possible to avoid the superfluous memory
deba@57
   440
    /// allocation: if you know that the digraph you want to build will
deba@57
   441
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
deba@57
   442
    /// then it is worth reserving space for this amount before starting
deba@57
   443
    /// to build the digraph.
deba@57
   444
    /// \sa reserveNode
deba@57
   445
    void reserveArc(int m) { arcs.reserve(m); };
deba@57
   446
deba@57
   447
    ///Contract two nodes.
deba@57
   448
deba@57
   449
    ///This function contracts two nodes.
deba@57
   450
    ///Node \p b will be removed but instead of deleting
deba@57
   451
    ///incident arcs, they will be joined to \p a.
deba@57
   452
    ///The last parameter \p r controls whether to remove loops. \c true
deba@57
   453
    ///means that loops will be removed.
deba@57
   454
    ///
kpeter@73
   455
    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
deba@57
   456
    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
deba@57
   457
    ///may be invalidated.
kpeter@73
   458
    ///
deba@57
   459
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   460
    ///feature.
alpar@209
   461
    void contract(Node a, Node b, bool r = true)
deba@57
   462
    {
deba@57
   463
      for(OutArcIt e(*this,b);e!=INVALID;) {
alpar@209
   464
        OutArcIt f=e;
alpar@209
   465
        ++f;
alpar@209
   466
        if(r && target(e)==a) erase(e);
alpar@209
   467
        else changeSource(e,a);
alpar@209
   468
        e=f;
deba@57
   469
      }
deba@57
   470
      for(InArcIt e(*this,b);e!=INVALID;) {
alpar@209
   471
        InArcIt f=e;
alpar@209
   472
        ++f;
alpar@209
   473
        if(r && source(e)==a) erase(e);
alpar@209
   474
        else changeTarget(e,a);
alpar@209
   475
        e=f;
deba@57
   476
      }
deba@57
   477
      erase(b);
deba@57
   478
    }
deba@57
   479
deba@57
   480
    ///Split a node.
deba@57
   481
deba@57
   482
    ///This function splits a node. First a new node is added to the digraph,
deba@57
   483
    ///then the source of each outgoing arc of \c n is moved to this new node.
deba@57
   484
    ///If \c connect is \c true (this is the default value), then a new arc
deba@57
   485
    ///from \c n to the newly created node is also added.
deba@57
   486
    ///\return The newly created node.
deba@57
   487
    ///
deba@57
   488
    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
deba@57
   489
    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
alpar@209
   490
    ///be invalidated.
deba@57
   491
    ///
deba@57
   492
    ///\warning This functionality cannot be used together with the
kpeter@73
   493
    ///Snapshot feature.
kpeter@73
   494
    ///
kpeter@73
   495
    ///\todo It could be implemented in a bit faster way.
deba@57
   496
    Node split(Node n, bool connect = true) {
deba@57
   497
      Node b = addNode();
deba@57
   498
      for(OutArcIt e(*this,n);e!=INVALID;) {
kpeter@212
   499
        OutArcIt f=e;
alpar@209
   500
        ++f;
alpar@209
   501
        changeSource(e,b);
alpar@209
   502
        e=f;
deba@57
   503
      }
deba@57
   504
      if (connect) addArc(n,b);
deba@57
   505
      return b;
deba@57
   506
    }
alpar@209
   507
deba@57
   508
    ///Split an arc.
deba@57
   509
deba@57
   510
    ///This function splits an arc. First a new node \c b is added to
deba@57
   511
    ///the digraph, then the original arc is re-targeted to \c
deba@57
   512
    ///b. Finally an arc from \c b to the original target is added.
kpeter@73
   513
    ///
kpeter@73
   514
    ///\return The newly created node.
kpeter@73
   515
    ///
kpeter@73
   516
    ///\warning This functionality cannot be used together with the
kpeter@73
   517
    ///Snapshot feature.
deba@57
   518
    Node split(Arc e) {
deba@57
   519
      Node b = addNode();
deba@57
   520
      addArc(b,target(e));
deba@57
   521
      changeTarget(e,b);
deba@57
   522
      return b;
deba@57
   523
    }
alpar@209
   524
deba@57
   525
    /// \brief Class to make a snapshot of the digraph and restore
kpeter@73
   526
    /// it later.
deba@57
   527
    ///
kpeter@73
   528
    /// Class to make a snapshot of the digraph and restore it later.
deba@57
   529
    ///
deba@57
   530
    /// The newly added nodes and arcs can be removed using the
deba@57
   531
    /// restore() function.
deba@57
   532
    ///
kpeter@73
   533
    /// \warning Arc and node deletions and other modifications (e.g.
alpar@209
   534
    /// contracting, splitting, reversing arcs or nodes) cannot be
alpar@209
   535
    /// restored. These events invalidate the snapshot.
deba@57
   536
    class Snapshot {
deba@57
   537
    protected:
deba@57
   538
deba@57
   539
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
   540
deba@57
   541
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
   542
      public:
deba@57
   543
deba@57
   544
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
   545
          : snapshot(_snapshot) {}
deba@57
   546
deba@57
   547
        using NodeNotifier::ObserverBase::attach;
deba@57
   548
        using NodeNotifier::ObserverBase::detach;
deba@57
   549
        using NodeNotifier::ObserverBase::attached;
alpar@209
   550
deba@57
   551
      protected:
alpar@209
   552
deba@57
   553
        virtual void add(const Node& node) {
deba@57
   554
          snapshot.addNode(node);
deba@57
   555
        }
deba@57
   556
        virtual void add(const std::vector<Node>& nodes) {
deba@57
   557
          for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57
   558
            snapshot.addNode(nodes[i]);
deba@57
   559
          }
deba@57
   560
        }
deba@57
   561
        virtual void erase(const Node& node) {
deba@57
   562
          snapshot.eraseNode(node);
deba@57
   563
        }
deba@57
   564
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
   565
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
   566
            snapshot.eraseNode(nodes[i]);
deba@57
   567
          }
deba@57
   568
        }
deba@57
   569
        virtual void build() {
deba@57
   570
          Node node;
deba@57
   571
          std::vector<Node> nodes;
alpar@209
   572
          for (notifier()->first(node); node != INVALID;
deba@57
   573
               notifier()->next(node)) {
deba@57
   574
            nodes.push_back(node);
deba@57
   575
          }
deba@57
   576
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
   577
            snapshot.addNode(nodes[i]);
deba@57
   578
          }
deba@57
   579
        }
deba@57
   580
        virtual void clear() {
deba@57
   581
          Node node;
alpar@209
   582
          for (notifier()->first(node); node != INVALID;
deba@57
   583
               notifier()->next(node)) {
deba@57
   584
            snapshot.eraseNode(node);
deba@57
   585
          }
deba@57
   586
        }
deba@57
   587
deba@57
   588
        Snapshot& snapshot;
deba@57
   589
      };
deba@57
   590
deba@57
   591
      class ArcObserverProxy : public ArcNotifier::ObserverBase {
deba@57
   592
      public:
deba@57
   593
deba@57
   594
        ArcObserverProxy(Snapshot& _snapshot)
deba@57
   595
          : snapshot(_snapshot) {}
deba@57
   596
deba@57
   597
        using ArcNotifier::ObserverBase::attach;
deba@57
   598
        using ArcNotifier::ObserverBase::detach;
deba@57
   599
        using ArcNotifier::ObserverBase::attached;
alpar@209
   600
deba@57
   601
      protected:
deba@57
   602
deba@57
   603
        virtual void add(const Arc& arc) {
deba@57
   604
          snapshot.addArc(arc);
deba@57
   605
        }
deba@57
   606
        virtual void add(const std::vector<Arc>& arcs) {
deba@57
   607
          for (int i = arcs.size() - 1; i >= 0; ++i) {
deba@57
   608
            snapshot.addArc(arcs[i]);
deba@57
   609
          }
deba@57
   610
        }
deba@57
   611
        virtual void erase(const Arc& arc) {
deba@57
   612
          snapshot.eraseArc(arc);
deba@57
   613
        }
deba@57
   614
        virtual void erase(const std::vector<Arc>& arcs) {
deba@57
   615
          for (int i = 0; i < int(arcs.size()); ++i) {
deba@57
   616
            snapshot.eraseArc(arcs[i]);
deba@57
   617
          }
deba@57
   618
        }
deba@57
   619
        virtual void build() {
deba@57
   620
          Arc arc;
deba@57
   621
          std::vector<Arc> arcs;
alpar@209
   622
          for (notifier()->first(arc); arc != INVALID;
deba@57
   623
               notifier()->next(arc)) {
deba@57
   624
            arcs.push_back(arc);
deba@57
   625
          }
deba@57
   626
          for (int i = arcs.size() - 1; i >= 0; --i) {
deba@57
   627
            snapshot.addArc(arcs[i]);
deba@57
   628
          }
deba@57
   629
        }
deba@57
   630
        virtual void clear() {
deba@57
   631
          Arc arc;
alpar@209
   632
          for (notifier()->first(arc); arc != INVALID;
deba@57
   633
               notifier()->next(arc)) {
deba@57
   634
            snapshot.eraseArc(arc);
deba@57
   635
          }
deba@57
   636
        }
deba@57
   637
deba@57
   638
        Snapshot& snapshot;
deba@57
   639
      };
alpar@209
   640
deba@57
   641
      ListDigraph *digraph;
deba@57
   642
deba@57
   643
      NodeObserverProxy node_observer_proxy;
deba@57
   644
      ArcObserverProxy arc_observer_proxy;
deba@57
   645
deba@57
   646
      std::list<Node> added_nodes;
deba@57
   647
      std::list<Arc> added_arcs;
deba@57
   648
deba@57
   649
deba@57
   650
      void addNode(const Node& node) {
alpar@209
   651
        added_nodes.push_front(node);
deba@57
   652
      }
deba@57
   653
      void eraseNode(const Node& node) {
alpar@209
   654
        std::list<Node>::iterator it =
deba@57
   655
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
   656
        if (it == added_nodes.end()) {
deba@57
   657
          clear();
deba@57
   658
          arc_observer_proxy.detach();
deba@57
   659
          throw NodeNotifier::ImmediateDetach();
deba@57
   660
        } else {
deba@57
   661
          added_nodes.erase(it);
deba@57
   662
        }
deba@57
   663
      }
deba@57
   664
deba@57
   665
      void addArc(const Arc& arc) {
alpar@209
   666
        added_arcs.push_front(arc);
deba@57
   667
      }
deba@57
   668
      void eraseArc(const Arc& arc) {
alpar@209
   669
        std::list<Arc>::iterator it =
deba@57
   670
          std::find(added_arcs.begin(), added_arcs.end(), arc);
deba@57
   671
        if (it == added_arcs.end()) {
deba@57
   672
          clear();
alpar@209
   673
          node_observer_proxy.detach();
deba@57
   674
          throw ArcNotifier::ImmediateDetach();
deba@57
   675
        } else {
deba@57
   676
          added_arcs.erase(it);
alpar@209
   677
        }
deba@57
   678
      }
deba@57
   679
deba@57
   680
      void attach(ListDigraph &_digraph) {
alpar@209
   681
        digraph = &_digraph;
alpar@209
   682
        node_observer_proxy.attach(digraph->notifier(Node()));
deba@57
   683
        arc_observer_proxy.attach(digraph->notifier(Arc()));
deba@57
   684
      }
alpar@209
   685
deba@57
   686
      void detach() {
alpar@209
   687
        node_observer_proxy.detach();
alpar@209
   688
        arc_observer_proxy.detach();
deba@57
   689
      }
deba@57
   690
deba@57
   691
      bool attached() const {
deba@57
   692
        return node_observer_proxy.attached();
deba@57
   693
      }
deba@57
   694
deba@57
   695
      void clear() {
deba@57
   696
        added_nodes.clear();
alpar@209
   697
        added_arcs.clear();
deba@57
   698
      }
deba@57
   699
deba@57
   700
    public:
deba@57
   701
deba@57
   702
      /// \brief Default constructor.
deba@57
   703
      ///
deba@57
   704
      /// Default constructor.
deba@57
   705
      /// To actually make a snapshot you must call save().
alpar@209
   706
      Snapshot()
alpar@209
   707
        : digraph(0), node_observer_proxy(*this),
deba@57
   708
          arc_observer_proxy(*this) {}
alpar@209
   709
deba@57
   710
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
   711
      ///
deba@57
   712
      /// This constructor immediately makes a snapshot of the digraph.
deba@57
   713
      /// \param _digraph The digraph we make a snapshot of.
alpar@209
   714
      Snapshot(ListDigraph &_digraph)
alpar@209
   715
        : node_observer_proxy(*this),
deba@57
   716
          arc_observer_proxy(*this) {
alpar@209
   717
        attach(_digraph);
deba@57
   718
      }
alpar@209
   719
deba@57
   720
      /// \brief Make a snapshot.
deba@57
   721
      ///
deba@57
   722
      /// Make a snapshot of the digraph.
deba@57
   723
      ///
deba@57
   724
      /// This function can be called more than once. In case of a repeated
deba@57
   725
      /// call, the previous snapshot gets lost.
deba@57
   726
      /// \param _digraph The digraph we make the snapshot of.
deba@57
   727
      void save(ListDigraph &_digraph) {
deba@57
   728
        if (attached()) {
deba@57
   729
          detach();
deba@57
   730
          clear();
deba@57
   731
        }
deba@57
   732
        attach(_digraph);
deba@57
   733
      }
alpar@209
   734
deba@57
   735
      /// \brief Undo the changes until the last snapshot.
alpar@209
   736
      //
deba@57
   737
      /// Undo the changes until the last snapshot created by save().
deba@57
   738
      void restore() {
alpar@209
   739
        detach();
alpar@209
   740
        for(std::list<Arc>::iterator it = added_arcs.begin();
deba@57
   741
            it != added_arcs.end(); ++it) {
alpar@209
   742
          digraph->erase(*it);
alpar@209
   743
        }
alpar@209
   744
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
   745
            it != added_nodes.end(); ++it) {
alpar@209
   746
          digraph->erase(*it);
alpar@209
   747
        }
deba@57
   748
        clear();
deba@57
   749
      }
deba@57
   750
deba@57
   751
      /// \brief Gives back true when the snapshot is valid.
deba@57
   752
      ///
deba@57
   753
      /// Gives back true when the snapshot is valid.
deba@57
   754
      bool valid() const {
deba@57
   755
        return attached();
deba@57
   756
      }
deba@57
   757
    };
alpar@209
   758
deba@57
   759
  };
deba@57
   760
deba@57
   761
  ///@}
deba@57
   762
deba@57
   763
  class ListGraphBase {
deba@57
   764
deba@57
   765
  protected:
deba@57
   766
deba@57
   767
    struct NodeT {
deba@57
   768
      int first_out;
deba@57
   769
      int prev, next;
deba@57
   770
    };
alpar@209
   771
deba@57
   772
    struct ArcT {
deba@57
   773
      int target;
deba@57
   774
      int prev_out, next_out;
deba@57
   775
    };
deba@57
   776
deba@57
   777
    std::vector<NodeT> nodes;
deba@57
   778
deba@57
   779
    int first_node;
deba@57
   780
deba@57
   781
    int first_free_node;
deba@57
   782
deba@57
   783
    std::vector<ArcT> arcs;
deba@57
   784
deba@57
   785
    int first_free_arc;
alpar@209
   786
deba@57
   787
  public:
alpar@209
   788
deba@57
   789
    typedef ListGraphBase Digraph;
deba@57
   790
deba@57
   791
    class Node;
deba@57
   792
    class Arc;
deba@57
   793
    class Edge;
alpar@209
   794
deba@57
   795
    class Node {
deba@57
   796
      friend class ListGraphBase;
deba@57
   797
    protected:
deba@57
   798
deba@57
   799
      int id;
deba@57
   800
      explicit Node(int pid) { id = pid;}
deba@57
   801
deba@57
   802
    public:
deba@57
   803
      Node() {}
deba@57
   804
      Node (Invalid) { id = -1; }
deba@57
   805
      bool operator==(const Node& node) const {return id == node.id;}
deba@57
   806
      bool operator!=(const Node& node) const {return id != node.id;}
deba@57
   807
      bool operator<(const Node& node) const {return id < node.id;}
deba@57
   808
    };
deba@57
   809
deba@57
   810
    class Edge {
deba@57
   811
      friend class ListGraphBase;
deba@57
   812
    protected:
deba@57
   813
deba@57
   814
      int id;
deba@57
   815
      explicit Edge(int pid) { id = pid;}
deba@57
   816
deba@57
   817
    public:
deba@57
   818
      Edge() {}
deba@57
   819
      Edge (Invalid) { id = -1; }
kpeter@73
   820
      bool operator==(const Edge& edge) const {return id == edge.id;}
kpeter@73
   821
      bool operator!=(const Edge& edge) const {return id != edge.id;}
kpeter@73
   822
      bool operator<(const Edge& edge) const {return id < edge.id;}
deba@57
   823
    };
deba@57
   824
deba@57
   825
    class Arc {
deba@57
   826
      friend class ListGraphBase;
deba@57
   827
    protected:
deba@57
   828
deba@57
   829
      int id;
deba@57
   830
      explicit Arc(int pid) { id = pid;}
deba@57
   831
deba@57
   832
    public:
deba@57
   833
      operator Edge() const { return edgeFromId(id / 2); }
deba@57
   834
deba@57
   835
      Arc() {}
deba@57
   836
      Arc (Invalid) { id = -1; }
deba@57
   837
      bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57
   838
      bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57
   839
      bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57
   840
    };
deba@57
   841
deba@57
   842
deba@57
   843
deba@57
   844
    ListGraphBase()
deba@57
   845
      : nodes(), first_node(-1),
alpar@209
   846
        first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57
   847
alpar@209
   848
alpar@209
   849
    int maxNodeId() const { return nodes.size()-1; }
deba@57
   850
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@57
   851
    int maxArcId() const { return arcs.size()-1; }
deba@57
   852
deba@57
   853
    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
deba@57
   854
    Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57
   855
deba@57
   856
    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
deba@57
   857
    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
deba@57
   858
deba@57
   859
    static bool direction(Arc e) {
deba@57
   860
      return (e.id & 1) == 1;
deba@57
   861
    }
deba@57
   862
deba@57
   863
    static Arc direct(Edge e, bool d) {
deba@57
   864
      return Arc(e.id * 2 + (d ? 1 : 0));
deba@57
   865
    }
deba@57
   866
alpar@209
   867
    void first(Node& node) const {
deba@57
   868
      node.id = first_node;
deba@57
   869
    }
deba@57
   870
deba@57
   871
    void next(Node& node) const {
deba@57
   872
      node.id = nodes[node.id].next;
deba@57
   873
    }
deba@57
   874
alpar@209
   875
    void first(Arc& e) const {
deba@57
   876
      int n = first_node;
deba@57
   877
      while (n != -1 && nodes[n].first_out == -1) {
deba@57
   878
        n = nodes[n].next;
deba@57
   879
      }
deba@57
   880
      e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57
   881
    }
deba@57
   882
deba@57
   883
    void next(Arc& e) const {
deba@57
   884
      if (arcs[e.id].next_out != -1) {
alpar@209
   885
        e.id = arcs[e.id].next_out;
deba@57
   886
      } else {
alpar@209
   887
        int n = nodes[arcs[e.id ^ 1].target].next;
deba@57
   888
        while(n != -1 && nodes[n].first_out == -1) {
deba@57
   889
          n = nodes[n].next;
deba@57
   890
        }
alpar@209
   891
        e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209
   892
      }
deba@57
   893
    }
deba@57
   894
alpar@209
   895
    void first(Edge& e) const {
deba@57
   896
      int n = first_node;
deba@57
   897
      while (n != -1) {
deba@57
   898
        e.id = nodes[n].first_out;
deba@57
   899
        while ((e.id & 1) != 1) {
deba@57
   900
          e.id = arcs[e.id].next_out;
deba@57
   901
        }
deba@57
   902
        if (e.id != -1) {
deba@57
   903
          e.id /= 2;
deba@57
   904
          return;
alpar@209
   905
        }
deba@57
   906
        n = nodes[n].next;
deba@57
   907
      }
deba@57
   908
      e.id = -1;
deba@57
   909
    }
deba@57
   910
deba@57
   911
    void next(Edge& e) const {
deba@57
   912
      int n = arcs[e.id * 2].target;
deba@57
   913
      e.id = arcs[(e.id * 2) | 1].next_out;
deba@57
   914
      while ((e.id & 1) != 1) {
deba@57
   915
        e.id = arcs[e.id].next_out;
deba@57
   916
      }
deba@57
   917
      if (e.id != -1) {
deba@57
   918
        e.id /= 2;
deba@57
   919
        return;
alpar@209
   920
      }
deba@57
   921
      n = nodes[n].next;
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 firstOut(Arc &e, const Node& v) const {
deba@57
   937
      e.id = nodes[v.id].first_out;
deba@57
   938
    }
deba@57
   939
    void nextOut(Arc &e) const {
deba@57
   940
      e.id = arcs[e.id].next_out;
deba@57
   941
    }
deba@57
   942
deba@57
   943
    void firstIn(Arc &e, const Node& v) const {
deba@57
   944
      e.id = ((nodes[v.id].first_out) ^ 1);
deba@57
   945
      if (e.id == -2) e.id = -1;
deba@57
   946
    }
deba@57
   947
    void nextIn(Arc &e) const {
deba@57
   948
      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
deba@57
   949
      if (e.id == -2) e.id = -1;
deba@57
   950
    }
deba@57
   951
deba@57
   952
    void firstInc(Edge &e, bool& d, const Node& v) const {
kpeter@73
   953
      int a = nodes[v.id].first_out;
kpeter@73
   954
      if (a != -1 ) {
kpeter@73
   955
        e.id = a / 2;
kpeter@73
   956
        d = ((a & 1) == 1);
deba@57
   957
      } else {
deba@57
   958
        e.id = -1;
deba@57
   959
        d = true;
deba@57
   960
      }
deba@57
   961
    }
deba@57
   962
    void nextInc(Edge &e, bool& d) const {
kpeter@73
   963
      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
kpeter@73
   964
      if (a != -1 ) {
kpeter@73
   965
        e.id = a / 2;
kpeter@73
   966
        d = ((a & 1) == 1);
deba@57
   967
      } else {
deba@57
   968
        e.id = -1;
deba@57
   969
        d = true;
deba@57
   970
      }
deba@57
   971
    }
alpar@209
   972
deba@57
   973
    static int id(Node v) { return v.id; }
deba@57
   974
    static int id(Arc e) { return e.id; }
deba@57
   975
    static int id(Edge e) { return e.id; }
deba@57
   976
deba@57
   977
    static Node nodeFromId(int id) { return Node(id);}
deba@57
   978
    static Arc arcFromId(int id) { return Arc(id);}
deba@57
   979
    static Edge edgeFromId(int id) { return Edge(id);}
deba@57
   980
alpar@209
   981
    bool valid(Node n) const {
alpar@209
   982
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209
   983
        nodes[n.id].prev != -2;
deba@149
   984
    }
deba@149
   985
alpar@209
   986
    bool valid(Arc a) const {
alpar@209
   987
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209
   988
        arcs[a.id].prev_out != -2;
deba@149
   989
    }
deba@149
   990
alpar@209
   991
    bool valid(Edge e) const {
alpar@209
   992
      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
alpar@209
   993
        arcs[2 * e.id].prev_out != -2;
deba@149
   994
    }
deba@149
   995
alpar@209
   996
    Node addNode() {
deba@57
   997
      int n;
alpar@209
   998
deba@57
   999
      if(first_free_node==-1) {
alpar@209
  1000
        n = nodes.size();
alpar@209
  1001
        nodes.push_back(NodeT());
deba@57
  1002
      } else {
alpar@209
  1003
        n = first_free_node;
alpar@209
  1004
        first_free_node = nodes[n].next;
deba@57
  1005
      }
alpar@209
  1006
deba@57
  1007
      nodes[n].next = first_node;
deba@57
  1008
      if (first_node != -1) nodes[first_node].prev = n;
deba@57
  1009
      first_node = n;
deba@57
  1010
      nodes[n].prev = -1;
alpar@209
  1011
deba@57
  1012
      nodes[n].first_out = -1;
alpar@209
  1013
deba@57
  1014
      return Node(n);
deba@57
  1015
    }
alpar@209
  1016
deba@57
  1017
    Edge addEdge(Node u, Node v) {
alpar@209
  1018
      int n;
deba@57
  1019
deba@57
  1020
      if (first_free_arc == -1) {
alpar@209
  1021
        n = arcs.size();
alpar@209
  1022
        arcs.push_back(ArcT());
alpar@209
  1023
        arcs.push_back(ArcT());
deba@57
  1024
      } else {
alpar@209
  1025
        n = first_free_arc;
alpar@209
  1026
        first_free_arc = arcs[n].next_out;
deba@57
  1027
      }
alpar@209
  1028
deba@57
  1029
      arcs[n].target = u.id;
deba@57
  1030
      arcs[n | 1].target = v.id;
deba@57
  1031
deba@57
  1032
      arcs[n].next_out = nodes[v.id].first_out;
deba@57
  1033
      if (nodes[v.id].first_out != -1) {
alpar@209
  1034
        arcs[nodes[v.id].first_out].prev_out = n;
alpar@209
  1035
      }
deba@57
  1036
      arcs[n].prev_out = -1;
deba@57
  1037
      nodes[v.id].first_out = n;
alpar@209
  1038
deba@57
  1039
      arcs[n | 1].next_out = nodes[u.id].first_out;
deba@57
  1040
      if (nodes[u.id].first_out != -1) {
alpar@209
  1041
        arcs[nodes[u.id].first_out].prev_out = (n | 1);
deba@57
  1042
      }
alpar@209
  1043
      arcs[n | 1].prev_out = -1;
deba@57
  1044
      nodes[u.id].first_out = (n | 1);
deba@57
  1045
deba@57
  1046
      return Edge(n / 2);
deba@57
  1047
    }
alpar@209
  1048
deba@57
  1049
    void erase(const Node& node) {
deba@57
  1050
      int n = node.id;
alpar@209
  1051
deba@57
  1052
      if(nodes[n].next != -1) {
alpar@209
  1053
        nodes[nodes[n].next].prev = nodes[n].prev;
deba@57
  1054
      }
alpar@209
  1055
deba@57
  1056
      if(nodes[n].prev != -1) {
alpar@209
  1057
        nodes[nodes[n].prev].next = nodes[n].next;
deba@57
  1058
      } else {
alpar@209
  1059
        first_node = nodes[n].next;
deba@57
  1060
      }
alpar@209
  1061
deba@57
  1062
      nodes[n].next = first_free_node;
deba@57
  1063
      first_free_node = n;
deba@149
  1064
      nodes[n].prev = -2;
deba@57
  1065
    }
alpar@209
  1066
kpeter@73
  1067
    void erase(const Edge& edge) {
kpeter@73
  1068
      int n = edge.id * 2;
alpar@209
  1069
deba@57
  1070
      if (arcs[n].next_out != -1) {
alpar@209
  1071
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209
  1072
      }
deba@57
  1073
deba@57
  1074
      if (arcs[n].prev_out != -1) {
alpar@209
  1075
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57
  1076
      } else {
alpar@209
  1077
        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
deba@57
  1078
      }
deba@57
  1079
deba@57
  1080
      if (arcs[n | 1].next_out != -1) {
alpar@209
  1081
        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
alpar@209
  1082
      }
deba@57
  1083
deba@57
  1084
      if (arcs[n | 1].prev_out != -1) {
alpar@209
  1085
        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
deba@57
  1086
      } else {
alpar@209
  1087
        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
deba@57
  1088
      }
alpar@209
  1089
deba@57
  1090
      arcs[n].next_out = first_free_arc;
alpar@209
  1091
      first_free_arc = n;
deba@149
  1092
      arcs[n].prev_out = -2;
deba@149
  1093
      arcs[n | 1].prev_out = -2;
deba@57
  1094
deba@57
  1095
    }
deba@57
  1096
deba@57
  1097
    void clear() {
deba@57
  1098
      arcs.clear();
deba@57
  1099
      nodes.clear();
deba@57
  1100
      first_node = first_free_node = first_free_arc = -1;
deba@57
  1101
    }
deba@57
  1102
deba@57
  1103
  protected:
deba@57
  1104
deba@57
  1105
    void changeTarget(Edge e, Node n) {
deba@57
  1106
      if(arcs[2 * e.id].next_out != -1) {
alpar@209
  1107
        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
deba@57
  1108
      }
deba@57
  1109
      if(arcs[2 * e.id].prev_out != -1) {
alpar@209
  1110
        arcs[arcs[2 * e.id].prev_out].next_out =
deba@57
  1111
          arcs[2 * e.id].next_out;
deba@57
  1112
      } else {
alpar@209
  1113
        nodes[arcs[(2 * e.id) | 1].target].first_out =
deba@57
  1114
          arcs[2 * e.id].next_out;
deba@57
  1115
      }
deba@57
  1116
deba@57
  1117
      if (nodes[n.id].first_out != -1) {
alpar@209
  1118
        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@57
  1119
      }
deba@57
  1120
      arcs[(2 * e.id) | 1].target = n.id;
deba@57
  1121
      arcs[2 * e.id].prev_out = -1;
deba@57
  1122
      arcs[2 * e.id].next_out = nodes[n.id].first_out;
deba@57
  1123
      nodes[n.id].first_out = 2 * e.id;
deba@57
  1124
    }
deba@57
  1125
deba@57
  1126
    void changeSource(Edge e, Node n) {
deba@57
  1127
      if(arcs[(2 * e.id) | 1].next_out != -1) {
alpar@209
  1128
        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
deba@57
  1129
          arcs[(2 * e.id) | 1].prev_out;
deba@57
  1130
      }
deba@57
  1131
      if(arcs[(2 * e.id) | 1].prev_out != -1) {
alpar@209
  1132
        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
deba@57
  1133
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1134
      } else {
alpar@209
  1135
        nodes[arcs[2 * e.id].target].first_out =
deba@57
  1136
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1137
      }
deba@57
  1138
deba@57
  1139
      if (nodes[n.id].first_out != -1) {
alpar@209
  1140
        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
deba@57
  1141
      }
deba@57
  1142
      arcs[2 * e.id].target = n.id;
deba@57
  1143
      arcs[(2 * e.id) | 1].prev_out = -1;
deba@57
  1144
      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
deba@57
  1145
      nodes[n.id].first_out = ((2 * e.id) | 1);
deba@57
  1146
    }
deba@57
  1147
deba@57
  1148
  };
deba@57
  1149
deba@57
  1150
  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
deba@57
  1151
deba@57
  1152
kpeter@73
  1153
  /// \addtogroup graphs
deba@57
  1154
  /// @{
deba@57
  1155
kpeter@73
  1156
  ///A general undirected graph structure.
deba@57
  1157
alpar@209
  1158
  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
alpar@209
  1159
  ///implementation based on static linked lists that are stored in
alpar@209
  1160
  ///\c std::vector structures.
deba@57
  1161
  ///
kpeter@73
  1162
  ///It conforms to the \ref concepts::Graph "Graph concept" and it
kpeter@73
  1163
  ///also provides several useful additional functionalities.
kpeter@73
  1164
  ///Most of the member functions and nested classes are documented
kpeter@73
  1165
  ///only in the concept class.
kpeter@73
  1166
  ///
kpeter@73
  1167
  ///An important extra feature of this graph implementation is that
deba@57
  1168
  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
deba@57
  1169
  ///
kpeter@73
  1170
  ///\sa concepts::Graph
kpeter@73
  1171
deba@57
  1172
  class ListGraph : public ExtendedListGraphBase {
deba@57
  1173
  private:
kpeter@73
  1174
    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
deba@57
  1175
kpeter@73
  1176
    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
deba@57
  1177
    ///
deba@57
  1178
    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
deba@57
  1179
    ///\brief Assignment of ListGraph to another one is \e not allowed.
kpeter@73
  1180
    ///Use copyGraph() instead.
deba@57
  1181
deba@57
  1182
    ///Assignment of ListGraph to another one is \e not allowed.
kpeter@73
  1183
    ///Use copyGraph() instead.
deba@57
  1184
    void operator=(const ListGraph &) {}
deba@57
  1185
  public:
deba@57
  1186
    /// Constructor
alpar@209
  1187
deba@57
  1188
    /// Constructor.
deba@57
  1189
    ///
deba@57
  1190
    ListGraph() {}
deba@57
  1191
deba@57
  1192
    typedef ExtendedListGraphBase Parent;
deba@57
  1193
kpeter@73
  1194
    typedef Parent::OutArcIt IncEdgeIt;
deba@57
  1195
kpeter@73
  1196
    /// \brief Add a new node to the graph.
deba@57
  1197
    ///
kpeter@73
  1198
    /// Add a new node to the graph.
deba@57
  1199
    /// \return the new node.
deba@57
  1200
    Node addNode() { return Parent::addNode(); }
deba@57
  1201
kpeter@73
  1202
    /// \brief Add a new edge to the graph.
deba@57
  1203
    ///
kpeter@73
  1204
    /// Add a new edge to the graph with source node \c s
deba@57
  1205
    /// and target node \c t.
deba@57
  1206
    /// \return the new edge.
alpar@209
  1207
    Edge addEdge(const Node& s, const Node& t) {
alpar@209
  1208
      return Parent::addEdge(s, t);
deba@57
  1209
    }
deba@149
  1210
    /// Node validity check
deba@149
  1211
deba@149
  1212
    /// This function gives back true if the given node is valid,
alpar@209
  1213
    /// ie. it is a real node of the graph.
deba@149
  1214
    ///
deba@149
  1215
    /// \warning A Node pointing to a removed item
deba@149
  1216
    /// could become valid again later if new nodes are
deba@149
  1217
    /// added to the graph.
deba@149
  1218
    bool valid(Node n) const { return Parent::valid(n); }
deba@149
  1219
    /// Arc validity check
deba@149
  1220
deba@149
  1221
    /// This function gives back true if the given arc is valid,
alpar@209
  1222
    /// ie. it is a real arc of the graph.
deba@149
  1223
    ///
deba@149
  1224
    /// \warning An Arc pointing to a removed item
deba@149
  1225
    /// could become valid again later if new edges are
deba@149
  1226
    /// added to the graph.
deba@149
  1227
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
  1228
    /// Edge validity check
deba@149
  1229
deba@149
  1230
    /// This function gives back true if the given edge is valid,
alpar@209
  1231
    /// ie. it is a real arc of the graph.
deba@149
  1232
    ///
deba@149
  1233
    /// \warning A Edge pointing to a removed item
deba@149
  1234
    /// could become valid again later if new edges are
deba@149
  1235
    /// added to the graph.
deba@149
  1236
    bool valid(Edge e) const { return Parent::valid(e); }
kpeter@73
  1237
    /// \brief Change the source of \c e to \c n
deba@57
  1238
    ///
kpeter@73
  1239
    /// This function changes the source of \c e to \c n.
deba@57
  1240
    ///
deba@57
  1241
    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
deba@57
  1242
    ///referencing the changed arc remain
deba@57
  1243
    ///valid. However <tt>OutArcIt</tt>s are invalidated.
kpeter@73
  1244
    ///
kpeter@73
  1245
    ///\warning This functionality cannot be used together with the
kpeter@73
  1246
    ///Snapshot feature.
alpar@209
  1247
    void changeSource(Edge e, Node n) {
alpar@209
  1248
      Parent::changeSource(e,n);
alpar@209
  1249
    }
kpeter@73
  1250
    /// \brief Change the target of \c e to \c n
deba@57
  1251
    ///
kpeter@73
  1252
    /// This function changes the target of \c e to \c n.
deba@57
  1253
    ///
deba@57
  1254
    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
deba@57
  1255
    /// valid. However the other iterators may be invalidated.
kpeter@73
  1256
    ///
kpeter@73
  1257
    ///\warning This functionality cannot be used together with the
kpeter@73
  1258
    ///Snapshot feature.
alpar@209
  1259
    void changeTarget(Edge e, Node n) {
alpar@209
  1260
      Parent::changeTarget(e,n);
deba@57
  1261
    }
kpeter@73
  1262
    /// \brief Change the source of \c e to \c n
deba@57
  1263
    ///
alpar@209
  1264
    /// This function changes the source of \c e to \c n.
kpeter@73
  1265
    /// It also changes the proper node of the represented edge.
deba@57
  1266
    ///
deba@57
  1267
    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
deba@57
  1268
    ///referencing the changed arc remain
deba@57
  1269
    ///valid. However <tt>OutArcIt</tt>s are invalidated.
kpeter@73
  1270
    ///
kpeter@73
  1271
    ///\warning This functionality cannot be used together with the
kpeter@73
  1272
    ///Snapshot feature.
alpar@209
  1273
    void changeSource(Arc e, Node n) {
deba@57
  1274
      if (Parent::direction(e)) {
deba@57
  1275
        Parent::changeSource(e,n);
deba@57
  1276
      } else {
deba@57
  1277
        Parent::changeTarget(e,n);
alpar@209
  1278
      }
deba@57
  1279
    }
kpeter@73
  1280
    /// \brief Change the target of \c e to \c n
deba@57
  1281
    ///
alpar@209
  1282
    /// This function changes the target of \c e to \c n.
kpeter@73
  1283
    /// It also changes the proper node of the represented edge.
deba@57
  1284
    ///
deba@57
  1285
    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
deba@57
  1286
    ///referencing the changed arc remain
deba@57
  1287
    ///valid. However <tt>InArcIt</tt>s are invalidated.
kpeter@73
  1288
    ///
kpeter@73
  1289
    ///\warning This functionality cannot be used together with the
kpeter@73
  1290
    ///Snapshot feature.
alpar@209
  1291
    void changeTarget(Arc e, Node n) {
deba@57
  1292
      if (Parent::direction(e)) {
deba@57
  1293
        Parent::changeTarget(e,n);
deba@57
  1294
      } else {
deba@57
  1295
        Parent::changeSource(e,n);
alpar@209
  1296
      }
deba@57
  1297
    }
deba@57
  1298
    /// \brief Contract two nodes.
deba@57
  1299
    ///
deba@57
  1300
    /// This function contracts two nodes.
deba@57
  1301
    /// Node \p b will be removed but instead of deleting
deba@57
  1302
    /// its neighboring arcs, they will be joined to \p a.
deba@57
  1303
    /// The last parameter \p r controls whether to remove loops. \c true
deba@57
  1304
    /// means that loops will be removed.
deba@57
  1305
    ///
deba@57
  1306
    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
deba@57
  1307
    /// valid.
kpeter@73
  1308
    ///
kpeter@73
  1309
    ///\warning This functionality cannot be used together with the
kpeter@73
  1310
    ///Snapshot feature.
deba@57
  1311
    void contract(Node a, Node b, bool r = true) {
kpeter@73
  1312
      for(IncEdgeIt e(*this, b); e!=INVALID;) {
alpar@209
  1313
        IncEdgeIt f = e; ++f;
alpar@209
  1314
        if (r && runningNode(e) == a) {
alpar@209
  1315
          erase(e);
alpar@209
  1316
        } else if (source(e) == b) {
alpar@209
  1317
          changeSource(e, a);
alpar@209
  1318
        } else {
alpar@209
  1319
          changeTarget(e, a);
alpar@209
  1320
        }
alpar@209
  1321
        e = f;
deba@57
  1322
      }
deba@57
  1323
      erase(b);
deba@57
  1324
    }
deba@57
  1325
deba@57
  1326
kpeter@73
  1327
    /// \brief Class to make a snapshot of the graph and restore
kpeter@73
  1328
    /// it later.
deba@57
  1329
    ///
kpeter@73
  1330
    /// Class to make a snapshot of the graph and restore it later.
deba@57
  1331
    ///
deba@57
  1332
    /// The newly added nodes and edges can be removed
deba@57
  1333
    /// using the restore() function.
deba@57
  1334
    ///
kpeter@73
  1335
    /// \warning Edge and node deletions and other modifications
alpar@209
  1336
    /// (e.g. changing nodes of edges, contracting nodes) cannot be
kpeter@73
  1337
    /// restored. These events invalidate the snapshot.
deba@57
  1338
    class Snapshot {
deba@57
  1339
    protected:
deba@57
  1340
deba@57
  1341
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
  1342
deba@57
  1343
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
  1344
      public:
deba@57
  1345
deba@57
  1346
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
  1347
          : snapshot(_snapshot) {}
deba@57
  1348
deba@57
  1349
        using NodeNotifier::ObserverBase::attach;
deba@57
  1350
        using NodeNotifier::ObserverBase::detach;
deba@57
  1351
        using NodeNotifier::ObserverBase::attached;
alpar@209
  1352
deba@57
  1353
      protected:
alpar@209
  1354
deba@57
  1355
        virtual void add(const Node& node) {
deba@57
  1356
          snapshot.addNode(node);
deba@57
  1357
        }
deba@57
  1358
        virtual void add(const std::vector<Node>& nodes) {
deba@57
  1359
          for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57
  1360
            snapshot.addNode(nodes[i]);
deba@57
  1361
          }
deba@57
  1362
        }
deba@57
  1363
        virtual void erase(const Node& node) {
deba@57
  1364
          snapshot.eraseNode(node);
deba@57
  1365
        }
deba@57
  1366
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
  1367
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
  1368
            snapshot.eraseNode(nodes[i]);
deba@57
  1369
          }
deba@57
  1370
        }
deba@57
  1371
        virtual void build() {
deba@57
  1372
          Node node;
deba@57
  1373
          std::vector<Node> nodes;
alpar@209
  1374
          for (notifier()->first(node); node != INVALID;
deba@57
  1375
               notifier()->next(node)) {
deba@57
  1376
            nodes.push_back(node);
deba@57
  1377
          }
deba@57
  1378
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
  1379
            snapshot.addNode(nodes[i]);
deba@57
  1380
          }
deba@57
  1381
        }
deba@57
  1382
        virtual void clear() {
deba@57
  1383
          Node node;
alpar@209
  1384
          for (notifier()->first(node); node != INVALID;
deba@57
  1385
               notifier()->next(node)) {
deba@57
  1386
            snapshot.eraseNode(node);
deba@57
  1387
          }
deba@57
  1388
        }
deba@57
  1389
deba@57
  1390
        Snapshot& snapshot;
deba@57
  1391
      };
deba@57
  1392
deba@57
  1393
      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@57
  1394
      public:
deba@57
  1395
deba@57
  1396
        EdgeObserverProxy(Snapshot& _snapshot)
deba@57
  1397
          : snapshot(_snapshot) {}
deba@57
  1398
deba@57
  1399
        using EdgeNotifier::ObserverBase::attach;
deba@57
  1400
        using EdgeNotifier::ObserverBase::detach;
deba@57
  1401
        using EdgeNotifier::ObserverBase::attached;
alpar@209
  1402
deba@57
  1403
      protected:
deba@57
  1404
kpeter@73
  1405
        virtual void add(const Edge& edge) {
kpeter@73
  1406
          snapshot.addEdge(edge);
deba@57
  1407
        }
kpeter@73
  1408
        virtual void add(const std::vector<Edge>& edges) {
kpeter@73
  1409
          for (int i = edges.size() - 1; i >= 0; ++i) {
kpeter@73
  1410
            snapshot.addEdge(edges[i]);
deba@57
  1411
          }
deba@57
  1412
        }
kpeter@73
  1413
        virtual void erase(const Edge& edge) {
kpeter@73
  1414
          snapshot.eraseEdge(edge);
deba@57
  1415
        }
kpeter@73
  1416
        virtual void erase(const std::vector<Edge>& edges) {
kpeter@73
  1417
          for (int i = 0; i < int(edges.size()); ++i) {
kpeter@73
  1418
            snapshot.eraseEdge(edges[i]);
deba@57
  1419
          }
deba@57
  1420
        }
deba@57
  1421
        virtual void build() {
kpeter@73
  1422
          Edge edge;
kpeter@73
  1423
          std::vector<Edge> edges;
alpar@209
  1424
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1425
               notifier()->next(edge)) {
kpeter@73
  1426
            edges.push_back(edge);
deba@57
  1427
          }
kpeter@73
  1428
          for (int i = edges.size() - 1; i >= 0; --i) {
kpeter@73
  1429
            snapshot.addEdge(edges[i]);
deba@57
  1430
          }
deba@57
  1431
        }
deba@57
  1432
        virtual void clear() {
kpeter@73
  1433
          Edge edge;
alpar@209
  1434
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1435
               notifier()->next(edge)) {
kpeter@73
  1436
            snapshot.eraseEdge(edge);
deba@57
  1437
          }
deba@57
  1438
        }
deba@57
  1439
deba@57
  1440
        Snapshot& snapshot;
deba@57
  1441
      };
kpeter@73
  1442
kpeter@73
  1443
      ListGraph *graph;
deba@57
  1444
deba@57
  1445
      NodeObserverProxy node_observer_proxy;
kpeter@73
  1446
      EdgeObserverProxy edge_observer_proxy;
deba@57
  1447
deba@57
  1448
      std::list<Node> added_nodes;
kpeter@73
  1449
      std::list<Edge> added_edges;
deba@57
  1450
deba@57
  1451
deba@57
  1452
      void addNode(const Node& node) {
alpar@209
  1453
        added_nodes.push_front(node);
deba@57
  1454
      }
deba@57
  1455
      void eraseNode(const Node& node) {
alpar@209
  1456
        std::list<Node>::iterator it =
deba@57
  1457
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
  1458
        if (it == added_nodes.end()) {
deba@57
  1459
          clear();
kpeter@73
  1460
          edge_observer_proxy.detach();
deba@57
  1461
          throw NodeNotifier::ImmediateDetach();
deba@57
  1462
        } else {
deba@57
  1463
          added_nodes.erase(it);
deba@57
  1464
        }
deba@57
  1465
      }
deba@57
  1466
kpeter@73
  1467
      void addEdge(const Edge& edge) {
alpar@209
  1468
        added_edges.push_front(edge);
deba@57
  1469
      }
kpeter@73
  1470
      void eraseEdge(const Edge& edge) {
alpar@209
  1471
        std::list<Edge>::iterator it =
kpeter@73
  1472
          std::find(added_edges.begin(), added_edges.end(), edge);
kpeter@73
  1473
        if (it == added_edges.end()) {
deba@57
  1474
          clear();
deba@57
  1475
          node_observer_proxy.detach();
deba@57
  1476
          throw EdgeNotifier::ImmediateDetach();
deba@57
  1477
        } else {
kpeter@73
  1478
          added_edges.erase(it);
kpeter@73
  1479
        }
deba@57
  1480
      }
deba@57
  1481
kpeter@73
  1482
      void attach(ListGraph &_graph) {
alpar@209
  1483
        graph = &_graph;
alpar@209
  1484
        node_observer_proxy.attach(graph->notifier(Node()));
kpeter@73
  1485
        edge_observer_proxy.attach(graph->notifier(Edge()));
deba@57
  1486
      }
alpar@209
  1487
deba@57
  1488
      void detach() {
alpar@209
  1489
        node_observer_proxy.detach();
alpar@209
  1490
        edge_observer_proxy.detach();
deba@57
  1491
      }
deba@57
  1492
deba@57
  1493
      bool attached() const {
deba@57
  1494
        return node_observer_proxy.attached();
deba@57
  1495
      }
deba@57
  1496
deba@57
  1497
      void clear() {
deba@57
  1498
        added_nodes.clear();
alpar@209
  1499
        added_edges.clear();
deba@57
  1500
      }
deba@57
  1501
deba@57
  1502
    public:
deba@57
  1503
deba@57
  1504
      /// \brief Default constructor.
deba@57
  1505
      ///
deba@57
  1506
      /// Default constructor.
deba@57
  1507
      /// To actually make a snapshot you must call save().
alpar@209
  1508
      Snapshot()
alpar@209
  1509
        : graph(0), node_observer_proxy(*this),
kpeter@73
  1510
          edge_observer_proxy(*this) {}
alpar@209
  1511
deba@57
  1512
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
  1513
      ///
kpeter@73
  1514
      /// This constructor immediately makes a snapshot of the graph.
kpeter@73
  1515
      /// \param _graph The graph we make a snapshot of.
alpar@209
  1516
      Snapshot(ListGraph &_graph)
alpar@209
  1517
        : node_observer_proxy(*this),
kpeter@73
  1518
          edge_observer_proxy(*this) {
alpar@209
  1519
        attach(_graph);
deba@57
  1520
      }
alpar@209
  1521
deba@57
  1522
      /// \brief Make a snapshot.
deba@57
  1523
      ///
kpeter@73
  1524
      /// Make a snapshot of the graph.
deba@57
  1525
      ///
deba@57
  1526
      /// This function can be called more than once. In case of a repeated
deba@57
  1527
      /// call, the previous snapshot gets lost.
kpeter@73
  1528
      /// \param _graph The graph we make the snapshot of.
kpeter@73
  1529
      void save(ListGraph &_graph) {
deba@57
  1530
        if (attached()) {
deba@57
  1531
          detach();
deba@57
  1532
          clear();
deba@57
  1533
        }
kpeter@73
  1534
        attach(_graph);
deba@57
  1535
      }
alpar@209
  1536
deba@57
  1537
      /// \brief Undo the changes until the last snapshot.
alpar@209
  1538
      //
deba@57
  1539
      /// Undo the changes until the last snapshot created by save().
deba@57
  1540
      void restore() {
alpar@209
  1541
        detach();
alpar@209
  1542
        for(std::list<Edge>::iterator it = added_edges.begin();
kpeter@73
  1543
            it != added_edges.end(); ++it) {
alpar@209
  1544
          graph->erase(*it);
alpar@209
  1545
        }
alpar@209
  1546
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
  1547
            it != added_nodes.end(); ++it) {
alpar@209
  1548
          graph->erase(*it);
alpar@209
  1549
        }
deba@57
  1550
        clear();
deba@57
  1551
      }
deba@57
  1552
deba@57
  1553
      /// \brief Gives back true when the snapshot is valid.
deba@57
  1554
      ///
deba@57
  1555
      /// Gives back true when the snapshot is valid.
deba@57
  1556
      bool valid() const {
deba@57
  1557
        return attached();
deba@57
  1558
      }
deba@57
  1559
    };
deba@57
  1560
  };
alpar@209
  1561
alpar@209
  1562
  /// @}
deba@57
  1563
} //namespace lemon
alpar@209
  1564
deba@57
  1565
deba@57
  1566
#endif