lemon/list_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 10 Oct 2009 08:15:07 +0200
changeset 754 2de0fc630899
parent 740 819ca5b50de0
parent 739 32baeb8e5c8f
child 786 e20173729589
child 787 c2230649a493
permissions -rw-r--r--
Handle url fields in bib2dox.py (#184)
and modify the bibtex file using url fields.
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@440
     5
 * Copyright (C) 2003-2009
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@735
    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@738
    35
  class ListDigraph;
kpeter@738
    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@738
    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@738
    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@739
   123
          n != -1 && nodes[n].first_out == -1;
alpar@209
   124
          n = nodes[n].next) {}
kpeter@739
   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@739
   129
      if (arcs[arc.id].next_out != -1) {
kpeter@739
   130
        arc.id = arcs[arc.id].next_out;
deba@57
   131
      } else {
alpar@209
   132
        int n;
kpeter@739
   133
        for(n = nodes[arcs[arc.id].source].next;
kpeter@739
   134
            n != -1 && nodes[n].first_out == -1;
alpar@209
   135
            n = nodes[n].next) {}
kpeter@739
   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@735
   318
  ///\ref ListDigraph is a versatile and fast directed graph
kpeter@735
   319
  ///implementation based on linked lists that are stored in
alpar@209
   320
  ///\c std::vector structures.
deba@57
   321
  ///
kpeter@735
   322
  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
kpeter@735
   323
  ///and it also provides several useful additional functionalities.
kpeter@735
   324
  ///Most of its member functions and nested classes are documented
kpeter@73
   325
  ///only in the concept class.
deba@57
   326
  ///
kpeter@73
   327
  ///\sa concepts::Digraph
kpeter@735
   328
  ///\sa ListGraph
deba@57
   329
  class ListDigraph : public ExtendedListDigraphBase {
kpeter@617
   330
    typedef ExtendedListDigraphBase Parent;
kpeter@617
   331
deba@57
   332
  private:
kpeter@735
   333
    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
deba@57
   334
    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
kpeter@735
   335
    /// \brief Assignment of a digraph to another one is \e not allowed.
kpeter@735
   336
    /// Use DigraphCopy instead.
deba@57
   337
    void operator=(const ListDigraph &) {}
deba@57
   338
  public:
deba@57
   339
deba@57
   340
    /// Constructor
alpar@209
   341
deba@57
   342
    /// Constructor.
deba@57
   343
    ///
deba@57
   344
    ListDigraph() {}
deba@57
   345
deba@57
   346
    ///Add a new node to the digraph.
alpar@209
   347
kpeter@735
   348
    ///This function adds a new node to the digraph.
kpeter@559
   349
    ///\return The new node.
deba@57
   350
    Node addNode() { return Parent::addNode(); }
deba@57
   351
deba@57
   352
    ///Add a new arc to the digraph.
alpar@209
   353
kpeter@735
   354
    ///This function adds a new arc to the digraph with source node \c s
deba@57
   355
    ///and target node \c t.
kpeter@559
   356
    ///\return The new arc.
kpeter@735
   357
    Arc addArc(Node s, Node t) {
alpar@209
   358
      return Parent::addArc(s, t);
deba@57
   359
    }
deba@57
   360
deba@234
   361
    ///\brief Erase a node from the digraph.
deba@234
   362
    ///
kpeter@735
   363
    ///This function erases the given node from the digraph.
kpeter@735
   364
    void erase(Node n) { Parent::erase(n); }
deba@234
   365
deba@234
   366
    ///\brief Erase an arc from the digraph.
deba@234
   367
    ///
kpeter@735
   368
    ///This function erases the given arc from the digraph.
kpeter@735
   369
    void erase(Arc a) { Parent::erase(a); }
deba@234
   370
deba@149
   371
    /// Node validity check
deba@149
   372
kpeter@735
   373
    /// This function gives back \c true if the given node is valid,
kpeter@735
   374
    /// i.e. it is a real node of the digraph.
deba@149
   375
    ///
kpeter@735
   376
    /// \warning A removed node could become valid again if new nodes are
kpeter@735
   377
    /// added to the digraph.
deba@149
   378
    bool valid(Node n) const { return Parent::valid(n); }
deba@149
   379
deba@149
   380
    /// Arc validity check
deba@149
   381
kpeter@735
   382
    /// This function gives back \c true if the given arc is valid,
kpeter@735
   383
    /// i.e. it is a real arc of the digraph.
deba@149
   384
    ///
kpeter@735
   385
    /// \warning A removed arc could become valid again if new arcs are
kpeter@735
   386
    /// added to the digraph.
deba@149
   387
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
   388
kpeter@735
   389
    /// Change the target node of an arc
deba@57
   390
kpeter@735
   391
    /// This function changes the target node of the given arc \c a to \c n.
deba@57
   392
    ///
kpeter@735
   393
    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
kpeter@735
   394
    ///arc remain valid, however \c InArcIt iterators are invalidated.
kpeter@73
   395
    ///
deba@57
   396
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   397
    ///feature.
deba@235
   398
    void changeTarget(Arc a, Node n) {
deba@235
   399
      Parent::changeTarget(a,n);
deba@57
   400
    }
kpeter@735
   401
    /// Change the source node of an arc
deba@57
   402
kpeter@735
   403
    /// This function changes the source node of the given arc \c a to \c n.
deba@57
   404
    ///
kpeter@735
   405
    ///\note \c InArcIt iterators referencing the changed arc remain
kpeter@735
   406
    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
kpeter@73
   407
    ///
deba@57
   408
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   409
    ///feature.
deba@235
   410
    void changeSource(Arc a, Node n) {
deba@235
   411
      Parent::changeSource(a,n);
deba@57
   412
    }
deba@57
   413
kpeter@735
   414
    /// Reverse the direction of an arc.
deba@57
   415
kpeter@735
   416
    /// This function reverses the direction of the given arc.
kpeter@735
   417
    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
kpeter@735
   418
    ///the changed arc are invalidated.
kpeter@73
   419
    ///
deba@57
   420
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   421
    ///feature.
kpeter@735
   422
    void reverseArc(Arc a) {
kpeter@735
   423
      Node t=target(a);
kpeter@735
   424
      changeTarget(a,source(a));
kpeter@735
   425
      changeSource(a,t);
deba@57
   426
    }
deba@57
   427
deba@57
   428
    ///Contract two nodes.
deba@57
   429
kpeter@735
   430
    ///This function contracts the given two nodes.
kpeter@735
   431
    ///Node \c v is removed, but instead of deleting its
kpeter@735
   432
    ///incident arcs, they are joined to node \c u.
kpeter@735
   433
    ///If the last parameter \c r is \c true (this is the default value),
kpeter@735
   434
    ///then the newly created loops are removed.
deba@57
   435
    ///
kpeter@735
   436
    ///\note The moved arcs are joined to node \c u using changeSource()
kpeter@735
   437
    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
kpeter@735
   438
    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
kpeter@735
   439
    ///iterators are invalidated for the incomming arcs of \c v.
kpeter@735
   440
    ///Moreover all iterators referencing node \c v or the removed 
kpeter@735
   441
    ///loops are also invalidated. Other iterators remain valid.
kpeter@73
   442
    ///
deba@57
   443
    ///\warning This functionality cannot be used together with the Snapshot
deba@57
   444
    ///feature.
kpeter@735
   445
    void contract(Node u, Node v, bool r = true)
deba@57
   446
    {
kpeter@735
   447
      for(OutArcIt e(*this,v);e!=INVALID;) {
alpar@209
   448
        OutArcIt f=e;
alpar@209
   449
        ++f;
kpeter@735
   450
        if(r && target(e)==u) erase(e);
kpeter@735
   451
        else changeSource(e,u);
alpar@209
   452
        e=f;
deba@57
   453
      }
kpeter@735
   454
      for(InArcIt e(*this,v);e!=INVALID;) {
alpar@209
   455
        InArcIt f=e;
alpar@209
   456
        ++f;
kpeter@735
   457
        if(r && source(e)==u) erase(e);
kpeter@735
   458
        else changeTarget(e,u);
alpar@209
   459
        e=f;
deba@57
   460
      }
kpeter@735
   461
      erase(v);
deba@57
   462
    }
deba@57
   463
deba@57
   464
    ///Split a node.
deba@57
   465
kpeter@735
   466
    ///This function splits the given node. First, a new node is added
kpeter@735
   467
    ///to the digraph, then the source of each outgoing arc of node \c n
kpeter@735
   468
    ///is moved to this new node.
kpeter@735
   469
    ///If the second parameter \c connect is \c true (this is the default
kpeter@735
   470
    ///value), then a new arc from node \c n to the newly created node
kpeter@735
   471
    ///is also added.
deba@57
   472
    ///\return The newly created node.
deba@57
   473
    ///
kpeter@738
   474
    ///\note All iterators remain valid.
deba@57
   475
    ///
kpeter@735
   476
    ///\warning This functionality cannot be used together with the
kpeter@73
   477
    ///Snapshot feature.
deba@57
   478
    Node split(Node n, bool connect = true) {
deba@57
   479
      Node b = addNode();
kpeter@738
   480
      nodes[b.id].first_out=nodes[n.id].first_out;
kpeter@738
   481
      nodes[n.id].first_out=-1;
kpeter@738
   482
      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
kpeter@738
   483
        arcs[i].source=b.id;
deba@57
   484
      }
deba@57
   485
      if (connect) addArc(n,b);
deba@57
   486
      return b;
deba@57
   487
    }
alpar@209
   488
deba@57
   489
    ///Split an arc.
deba@57
   490
kpeter@735
   491
    ///This function splits the given arc. First, a new node \c v is
kpeter@735
   492
    ///added to the digraph, then the target node of the original arc
kpeter@735
   493
    ///is set to \c v. Finally, an arc from \c v to the original target
kpeter@735
   494
    ///is added.
kpeter@735
   495
    ///\return The newly created node.
kpeter@73
   496
    ///
kpeter@735
   497
    ///\note \c InArcIt iterators referencing the original arc are
kpeter@735
   498
    ///invalidated. Other iterators remain valid.
kpeter@73
   499
    ///
kpeter@73
   500
    ///\warning This functionality cannot be used together with the
kpeter@73
   501
    ///Snapshot feature.
kpeter@735
   502
    Node split(Arc a) {
kpeter@735
   503
      Node v = addNode();
kpeter@735
   504
      addArc(v,target(a));
kpeter@735
   505
      changeTarget(a,v);
kpeter@735
   506
      return v;
deba@57
   507
    }
alpar@209
   508
kpeter@735
   509
    ///Clear the digraph.
kpeter@735
   510
kpeter@735
   511
    ///This function erases all nodes and arcs from the digraph.
kpeter@735
   512
    ///
kpeter@735
   513
    void clear() {
kpeter@735
   514
      Parent::clear();
kpeter@735
   515
    }
kpeter@735
   516
kpeter@735
   517
    /// Reserve memory for nodes.
kpeter@735
   518
kpeter@735
   519
    /// Using this function, it is possible to avoid superfluous memory
kpeter@735
   520
    /// allocation: if you know that the digraph you want to build will
kpeter@735
   521
    /// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@735
   522
    /// then it is worth reserving space for this amount before starting
kpeter@735
   523
    /// to build the digraph.
kpeter@735
   524
    /// \sa reserveArc()
kpeter@735
   525
    void reserveNode(int n) { nodes.reserve(n); };
kpeter@735
   526
kpeter@735
   527
    /// Reserve memory for arcs.
kpeter@735
   528
kpeter@735
   529
    /// Using this function, it is possible to avoid superfluous memory
kpeter@735
   530
    /// allocation: if you know that the digraph you want to build will
kpeter@735
   531
    /// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@735
   532
    /// then it is worth reserving space for this amount before starting
kpeter@735
   533
    /// to build the digraph.
kpeter@735
   534
    /// \sa reserveNode()
kpeter@735
   535
    void reserveArc(int m) { arcs.reserve(m); };
kpeter@735
   536
deba@57
   537
    /// \brief Class to make a snapshot of the digraph and restore
kpeter@73
   538
    /// it later.
deba@57
   539
    ///
kpeter@73
   540
    /// Class to make a snapshot of the digraph and restore it later.
deba@57
   541
    ///
deba@57
   542
    /// The newly added nodes and arcs can be removed using the
deba@57
   543
    /// restore() function.
deba@57
   544
    ///
kpeter@735
   545
    /// \note After a state is restored, you cannot restore a later state, 
kpeter@735
   546
    /// i.e. you cannot add the removed nodes and arcs again using
kpeter@735
   547
    /// another Snapshot instance.
kpeter@735
   548
    ///
kpeter@735
   549
    /// \warning Node and arc deletions and other modifications (e.g.
kpeter@735
   550
    /// reversing, contracting, splitting arcs or nodes) cannot be
alpar@209
   551
    /// restored. These events invalidate the snapshot.
kpeter@735
   552
    /// However the arcs and nodes that were added to the digraph after
kpeter@735
   553
    /// making the current snapshot can be removed without invalidating it.
deba@57
   554
    class Snapshot {
deba@57
   555
    protected:
deba@57
   556
deba@57
   557
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
   558
deba@57
   559
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
   560
      public:
deba@57
   561
deba@57
   562
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
   563
          : snapshot(_snapshot) {}
deba@57
   564
deba@57
   565
        using NodeNotifier::ObserverBase::attach;
deba@57
   566
        using NodeNotifier::ObserverBase::detach;
deba@57
   567
        using NodeNotifier::ObserverBase::attached;
alpar@209
   568
deba@57
   569
      protected:
alpar@209
   570
deba@57
   571
        virtual void add(const Node& node) {
deba@57
   572
          snapshot.addNode(node);
deba@57
   573
        }
deba@57
   574
        virtual void add(const std::vector<Node>& nodes) {
deba@57
   575
          for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57
   576
            snapshot.addNode(nodes[i]);
deba@57
   577
          }
deba@57
   578
        }
deba@57
   579
        virtual void erase(const Node& node) {
deba@57
   580
          snapshot.eraseNode(node);
deba@57
   581
        }
deba@57
   582
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
   583
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
   584
            snapshot.eraseNode(nodes[i]);
deba@57
   585
          }
deba@57
   586
        }
deba@57
   587
        virtual void build() {
deba@57
   588
          Node node;
deba@57
   589
          std::vector<Node> nodes;
alpar@209
   590
          for (notifier()->first(node); node != INVALID;
deba@57
   591
               notifier()->next(node)) {
deba@57
   592
            nodes.push_back(node);
deba@57
   593
          }
deba@57
   594
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
   595
            snapshot.addNode(nodes[i]);
deba@57
   596
          }
deba@57
   597
        }
deba@57
   598
        virtual void clear() {
deba@57
   599
          Node node;
alpar@209
   600
          for (notifier()->first(node); node != INVALID;
deba@57
   601
               notifier()->next(node)) {
deba@57
   602
            snapshot.eraseNode(node);
deba@57
   603
          }
deba@57
   604
        }
deba@57
   605
deba@57
   606
        Snapshot& snapshot;
deba@57
   607
      };
deba@57
   608
deba@57
   609
      class ArcObserverProxy : public ArcNotifier::ObserverBase {
deba@57
   610
      public:
deba@57
   611
deba@57
   612
        ArcObserverProxy(Snapshot& _snapshot)
deba@57
   613
          : snapshot(_snapshot) {}
deba@57
   614
deba@57
   615
        using ArcNotifier::ObserverBase::attach;
deba@57
   616
        using ArcNotifier::ObserverBase::detach;
deba@57
   617
        using ArcNotifier::ObserverBase::attached;
alpar@209
   618
deba@57
   619
      protected:
deba@57
   620
deba@57
   621
        virtual void add(const Arc& arc) {
deba@57
   622
          snapshot.addArc(arc);
deba@57
   623
        }
deba@57
   624
        virtual void add(const std::vector<Arc>& arcs) {
deba@57
   625
          for (int i = arcs.size() - 1; i >= 0; ++i) {
deba@57
   626
            snapshot.addArc(arcs[i]);
deba@57
   627
          }
deba@57
   628
        }
deba@57
   629
        virtual void erase(const Arc& arc) {
deba@57
   630
          snapshot.eraseArc(arc);
deba@57
   631
        }
deba@57
   632
        virtual void erase(const std::vector<Arc>& arcs) {
deba@57
   633
          for (int i = 0; i < int(arcs.size()); ++i) {
deba@57
   634
            snapshot.eraseArc(arcs[i]);
deba@57
   635
          }
deba@57
   636
        }
deba@57
   637
        virtual void build() {
deba@57
   638
          Arc arc;
deba@57
   639
          std::vector<Arc> arcs;
alpar@209
   640
          for (notifier()->first(arc); arc != INVALID;
deba@57
   641
               notifier()->next(arc)) {
deba@57
   642
            arcs.push_back(arc);
deba@57
   643
          }
deba@57
   644
          for (int i = arcs.size() - 1; i >= 0; --i) {
deba@57
   645
            snapshot.addArc(arcs[i]);
deba@57
   646
          }
deba@57
   647
        }
deba@57
   648
        virtual void clear() {
deba@57
   649
          Arc arc;
alpar@209
   650
          for (notifier()->first(arc); arc != INVALID;
deba@57
   651
               notifier()->next(arc)) {
deba@57
   652
            snapshot.eraseArc(arc);
deba@57
   653
          }
deba@57
   654
        }
deba@57
   655
deba@57
   656
        Snapshot& snapshot;
deba@57
   657
      };
alpar@209
   658
deba@57
   659
      ListDigraph *digraph;
deba@57
   660
deba@57
   661
      NodeObserverProxy node_observer_proxy;
deba@57
   662
      ArcObserverProxy arc_observer_proxy;
deba@57
   663
deba@57
   664
      std::list<Node> added_nodes;
deba@57
   665
      std::list<Arc> added_arcs;
deba@57
   666
deba@57
   667
deba@57
   668
      void addNode(const Node& node) {
alpar@209
   669
        added_nodes.push_front(node);
deba@57
   670
      }
deba@57
   671
      void eraseNode(const Node& node) {
alpar@209
   672
        std::list<Node>::iterator it =
deba@57
   673
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
   674
        if (it == added_nodes.end()) {
deba@57
   675
          clear();
deba@57
   676
          arc_observer_proxy.detach();
deba@57
   677
          throw NodeNotifier::ImmediateDetach();
deba@57
   678
        } else {
deba@57
   679
          added_nodes.erase(it);
deba@57
   680
        }
deba@57
   681
      }
deba@57
   682
deba@57
   683
      void addArc(const Arc& arc) {
alpar@209
   684
        added_arcs.push_front(arc);
deba@57
   685
      }
deba@57
   686
      void eraseArc(const Arc& arc) {
alpar@209
   687
        std::list<Arc>::iterator it =
deba@57
   688
          std::find(added_arcs.begin(), added_arcs.end(), arc);
deba@57
   689
        if (it == added_arcs.end()) {
deba@57
   690
          clear();
alpar@209
   691
          node_observer_proxy.detach();
deba@57
   692
          throw ArcNotifier::ImmediateDetach();
deba@57
   693
        } else {
deba@57
   694
          added_arcs.erase(it);
alpar@209
   695
        }
deba@57
   696
      }
deba@57
   697
deba@57
   698
      void attach(ListDigraph &_digraph) {
alpar@209
   699
        digraph = &_digraph;
alpar@209
   700
        node_observer_proxy.attach(digraph->notifier(Node()));
deba@57
   701
        arc_observer_proxy.attach(digraph->notifier(Arc()));
deba@57
   702
      }
alpar@209
   703
deba@57
   704
      void detach() {
alpar@209
   705
        node_observer_proxy.detach();
alpar@209
   706
        arc_observer_proxy.detach();
deba@57
   707
      }
deba@57
   708
deba@57
   709
      bool attached() const {
deba@57
   710
        return node_observer_proxy.attached();
deba@57
   711
      }
deba@57
   712
deba@57
   713
      void clear() {
deba@57
   714
        added_nodes.clear();
alpar@209
   715
        added_arcs.clear();
deba@57
   716
      }
deba@57
   717
deba@57
   718
    public:
deba@57
   719
deba@57
   720
      /// \brief Default constructor.
deba@57
   721
      ///
deba@57
   722
      /// Default constructor.
kpeter@735
   723
      /// You have to call save() to actually make a snapshot.
alpar@209
   724
      Snapshot()
alpar@209
   725
        : digraph(0), node_observer_proxy(*this),
deba@57
   726
          arc_observer_proxy(*this) {}
alpar@209
   727
deba@57
   728
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
   729
      ///
kpeter@735
   730
      /// This constructor immediately makes a snapshot of the given digraph.
kpeter@735
   731
      Snapshot(ListDigraph &gr)
alpar@209
   732
        : node_observer_proxy(*this),
deba@57
   733
          arc_observer_proxy(*this) {
kpeter@735
   734
        attach(gr);
deba@57
   735
      }
alpar@209
   736
deba@57
   737
      /// \brief Make a snapshot.
deba@57
   738
      ///
kpeter@735
   739
      /// This function makes a snapshot of the given digraph.
kpeter@735
   740
      /// It can be called more than once. In case of a repeated
deba@57
   741
      /// call, the previous snapshot gets lost.
kpeter@735
   742
      void save(ListDigraph &gr) {
deba@57
   743
        if (attached()) {
deba@57
   744
          detach();
deba@57
   745
          clear();
deba@57
   746
        }
kpeter@735
   747
        attach(gr);
deba@57
   748
      }
alpar@209
   749
deba@57
   750
      /// \brief Undo the changes until the last snapshot.
kpeter@735
   751
      ///
kpeter@735
   752
      /// This function undos the changes until the last snapshot
kpeter@735
   753
      /// created by save() or Snapshot(ListDigraph&).
kpeter@740
   754
      ///
kpeter@740
   755
      /// \warning This method invalidates the snapshot, i.e. repeated
kpeter@740
   756
      /// restoring is not supported unless you call save() again.
deba@57
   757
      void restore() {
alpar@209
   758
        detach();
alpar@209
   759
        for(std::list<Arc>::iterator it = added_arcs.begin();
deba@57
   760
            it != added_arcs.end(); ++it) {
alpar@209
   761
          digraph->erase(*it);
alpar@209
   762
        }
alpar@209
   763
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
   764
            it != added_nodes.end(); ++it) {
alpar@209
   765
          digraph->erase(*it);
alpar@209
   766
        }
deba@57
   767
        clear();
deba@57
   768
      }
deba@57
   769
kpeter@735
   770
      /// \brief Returns \c true if the snapshot is valid.
deba@57
   771
      ///
kpeter@735
   772
      /// This function returns \c true if the snapshot is valid.
deba@57
   773
      bool valid() const {
deba@57
   774
        return attached();
deba@57
   775
      }
deba@57
   776
    };
alpar@209
   777
deba@57
   778
  };
deba@57
   779
deba@57
   780
  ///@}
deba@57
   781
deba@57
   782
  class ListGraphBase {
deba@57
   783
deba@57
   784
  protected:
deba@57
   785
deba@57
   786
    struct NodeT {
deba@57
   787
      int first_out;
deba@57
   788
      int prev, next;
deba@57
   789
    };
alpar@209
   790
deba@57
   791
    struct ArcT {
deba@57
   792
      int target;
deba@57
   793
      int prev_out, next_out;
deba@57
   794
    };
deba@57
   795
deba@57
   796
    std::vector<NodeT> nodes;
deba@57
   797
deba@57
   798
    int first_node;
deba@57
   799
deba@57
   800
    int first_free_node;
deba@57
   801
deba@57
   802
    std::vector<ArcT> arcs;
deba@57
   803
deba@57
   804
    int first_free_arc;
alpar@209
   805
deba@57
   806
  public:
alpar@209
   807
kpeter@617
   808
    typedef ListGraphBase Graph;
deba@57
   809
deba@57
   810
    class Node {
deba@57
   811
      friend class ListGraphBase;
deba@57
   812
    protected:
deba@57
   813
deba@57
   814
      int id;
deba@57
   815
      explicit Node(int pid) { id = pid;}
deba@57
   816
deba@57
   817
    public:
deba@57
   818
      Node() {}
deba@57
   819
      Node (Invalid) { id = -1; }
deba@57
   820
      bool operator==(const Node& node) const {return id == node.id;}
deba@57
   821
      bool operator!=(const Node& node) const {return id != node.id;}
deba@57
   822
      bool operator<(const Node& node) const {return id < node.id;}
deba@57
   823
    };
deba@57
   824
deba@57
   825
    class Edge {
deba@57
   826
      friend class ListGraphBase;
deba@57
   827
    protected:
deba@57
   828
deba@57
   829
      int id;
deba@57
   830
      explicit Edge(int pid) { id = pid;}
deba@57
   831
deba@57
   832
    public:
deba@57
   833
      Edge() {}
deba@57
   834
      Edge (Invalid) { id = -1; }
kpeter@73
   835
      bool operator==(const Edge& edge) const {return id == edge.id;}
kpeter@73
   836
      bool operator!=(const Edge& edge) const {return id != edge.id;}
kpeter@73
   837
      bool operator<(const Edge& edge) const {return id < edge.id;}
deba@57
   838
    };
deba@57
   839
deba@57
   840
    class Arc {
deba@57
   841
      friend class ListGraphBase;
deba@57
   842
    protected:
deba@57
   843
deba@57
   844
      int id;
deba@57
   845
      explicit Arc(int pid) { id = pid;}
deba@57
   846
deba@57
   847
    public:
kpeter@329
   848
      operator Edge() const {
kpeter@329
   849
        return id != -1 ? edgeFromId(id / 2) : INVALID;
deba@238
   850
      }
deba@57
   851
deba@57
   852
      Arc() {}
deba@57
   853
      Arc (Invalid) { id = -1; }
deba@57
   854
      bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57
   855
      bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57
   856
      bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57
   857
    };
deba@57
   858
deba@57
   859
    ListGraphBase()
deba@57
   860
      : nodes(), first_node(-1),
alpar@209
   861
        first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57
   862
alpar@209
   863
alpar@209
   864
    int maxNodeId() const { return nodes.size()-1; }
deba@57
   865
    int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@57
   866
    int maxArcId() const { return arcs.size()-1; }
deba@57
   867
deba@57
   868
    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
deba@57
   869
    Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57
   870
deba@57
   871
    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
deba@57
   872
    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
deba@57
   873
deba@57
   874
    static bool direction(Arc e) {
deba@57
   875
      return (e.id & 1) == 1;
deba@57
   876
    }
deba@57
   877
deba@57
   878
    static Arc direct(Edge e, bool d) {
deba@57
   879
      return Arc(e.id * 2 + (d ? 1 : 0));
deba@57
   880
    }
deba@57
   881
alpar@209
   882
    void first(Node& node) const {
deba@57
   883
      node.id = first_node;
deba@57
   884
    }
deba@57
   885
deba@57
   886
    void next(Node& node) const {
deba@57
   887
      node.id = nodes[node.id].next;
deba@57
   888
    }
deba@57
   889
alpar@209
   890
    void first(Arc& e) const {
deba@57
   891
      int n = first_node;
deba@57
   892
      while (n != -1 && nodes[n].first_out == -1) {
deba@57
   893
        n = nodes[n].next;
deba@57
   894
      }
deba@57
   895
      e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57
   896
    }
deba@57
   897
deba@57
   898
    void next(Arc& e) const {
deba@57
   899
      if (arcs[e.id].next_out != -1) {
alpar@209
   900
        e.id = arcs[e.id].next_out;
deba@57
   901
      } else {
alpar@209
   902
        int n = nodes[arcs[e.id ^ 1].target].next;
deba@57
   903
        while(n != -1 && nodes[n].first_out == -1) {
deba@57
   904
          n = nodes[n].next;
deba@57
   905
        }
alpar@209
   906
        e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209
   907
      }
deba@57
   908
    }
deba@57
   909
alpar@209
   910
    void first(Edge& e) const {
deba@57
   911
      int n = first_node;
deba@57
   912
      while (n != -1) {
deba@57
   913
        e.id = nodes[n].first_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
      }
deba@57
   923
      e.id = -1;
deba@57
   924
    }
deba@57
   925
deba@57
   926
    void next(Edge& e) const {
deba@57
   927
      int n = arcs[e.id * 2].target;
deba@57
   928
      e.id = arcs[(e.id * 2) | 1].next_out;
deba@57
   929
      while ((e.id & 1) != 1) {
deba@57
   930
        e.id = arcs[e.id].next_out;
deba@57
   931
      }
deba@57
   932
      if (e.id != -1) {
deba@57
   933
        e.id /= 2;
deba@57
   934
        return;
alpar@209
   935
      }
deba@57
   936
      n = nodes[n].next;
deba@57
   937
      while (n != -1) {
deba@57
   938
        e.id = nodes[n].first_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
      }
deba@57
   948
      e.id = -1;
deba@57
   949
    }
deba@57
   950
deba@57
   951
    void firstOut(Arc &e, const Node& v) const {
deba@57
   952
      e.id = nodes[v.id].first_out;
deba@57
   953
    }
deba@57
   954
    void nextOut(Arc &e) const {
deba@57
   955
      e.id = arcs[e.id].next_out;
deba@57
   956
    }
deba@57
   957
deba@57
   958
    void firstIn(Arc &e, const Node& v) const {
deba@57
   959
      e.id = ((nodes[v.id].first_out) ^ 1);
deba@57
   960
      if (e.id == -2) e.id = -1;
deba@57
   961
    }
deba@57
   962
    void nextIn(Arc &e) const {
deba@57
   963
      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
deba@57
   964
      if (e.id == -2) e.id = -1;
deba@57
   965
    }
deba@57
   966
deba@57
   967
    void firstInc(Edge &e, bool& d, const Node& v) const {
kpeter@73
   968
      int a = nodes[v.id].first_out;
kpeter@73
   969
      if (a != -1 ) {
kpeter@73
   970
        e.id = a / 2;
kpeter@73
   971
        d = ((a & 1) == 1);
deba@57
   972
      } else {
deba@57
   973
        e.id = -1;
deba@57
   974
        d = true;
deba@57
   975
      }
deba@57
   976
    }
deba@57
   977
    void nextInc(Edge &e, bool& d) const {
kpeter@73
   978
      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_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
    }
alpar@209
   987
deba@57
   988
    static int id(Node v) { return v.id; }
deba@57
   989
    static int id(Arc e) { return e.id; }
deba@57
   990
    static int id(Edge e) { return e.id; }
deba@57
   991
deba@57
   992
    static Node nodeFromId(int id) { return Node(id);}
deba@57
   993
    static Arc arcFromId(int id) { return Arc(id);}
deba@57
   994
    static Edge edgeFromId(int id) { return Edge(id);}
deba@57
   995
alpar@209
   996
    bool valid(Node n) const {
alpar@209
   997
      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209
   998
        nodes[n.id].prev != -2;
deba@149
   999
    }
deba@149
  1000
alpar@209
  1001
    bool valid(Arc a) const {
alpar@209
  1002
      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209
  1003
        arcs[a.id].prev_out != -2;
deba@149
  1004
    }
deba@149
  1005
alpar@209
  1006
    bool valid(Edge e) const {
alpar@209
  1007
      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
alpar@209
  1008
        arcs[2 * e.id].prev_out != -2;
deba@149
  1009
    }
deba@149
  1010
alpar@209
  1011
    Node addNode() {
deba@57
  1012
      int n;
alpar@209
  1013
deba@57
  1014
      if(first_free_node==-1) {
alpar@209
  1015
        n = nodes.size();
alpar@209
  1016
        nodes.push_back(NodeT());
deba@57
  1017
      } else {
alpar@209
  1018
        n = first_free_node;
alpar@209
  1019
        first_free_node = nodes[n].next;
deba@57
  1020
      }
alpar@209
  1021
deba@57
  1022
      nodes[n].next = first_node;
deba@57
  1023
      if (first_node != -1) nodes[first_node].prev = n;
deba@57
  1024
      first_node = n;
deba@57
  1025
      nodes[n].prev = -1;
alpar@209
  1026
deba@57
  1027
      nodes[n].first_out = -1;
alpar@209
  1028
deba@57
  1029
      return Node(n);
deba@57
  1030
    }
alpar@209
  1031
deba@57
  1032
    Edge addEdge(Node u, Node v) {
alpar@209
  1033
      int n;
deba@57
  1034
deba@57
  1035
      if (first_free_arc == -1) {
alpar@209
  1036
        n = arcs.size();
alpar@209
  1037
        arcs.push_back(ArcT());
alpar@209
  1038
        arcs.push_back(ArcT());
deba@57
  1039
      } else {
alpar@209
  1040
        n = first_free_arc;
alpar@209
  1041
        first_free_arc = arcs[n].next_out;
deba@57
  1042
      }
alpar@209
  1043
deba@57
  1044
      arcs[n].target = u.id;
deba@57
  1045
      arcs[n | 1].target = v.id;
deba@57
  1046
deba@57
  1047
      arcs[n].next_out = nodes[v.id].first_out;
deba@57
  1048
      if (nodes[v.id].first_out != -1) {
alpar@209
  1049
        arcs[nodes[v.id].first_out].prev_out = n;
alpar@209
  1050
      }
deba@57
  1051
      arcs[n].prev_out = -1;
deba@57
  1052
      nodes[v.id].first_out = n;
alpar@209
  1053
deba@57
  1054
      arcs[n | 1].next_out = nodes[u.id].first_out;
deba@57
  1055
      if (nodes[u.id].first_out != -1) {
alpar@209
  1056
        arcs[nodes[u.id].first_out].prev_out = (n | 1);
deba@57
  1057
      }
alpar@209
  1058
      arcs[n | 1].prev_out = -1;
deba@57
  1059
      nodes[u.id].first_out = (n | 1);
deba@57
  1060
deba@57
  1061
      return Edge(n / 2);
deba@57
  1062
    }
alpar@209
  1063
deba@57
  1064
    void erase(const Node& node) {
deba@57
  1065
      int n = node.id;
alpar@209
  1066
deba@57
  1067
      if(nodes[n].next != -1) {
alpar@209
  1068
        nodes[nodes[n].next].prev = nodes[n].prev;
deba@57
  1069
      }
alpar@209
  1070
deba@57
  1071
      if(nodes[n].prev != -1) {
alpar@209
  1072
        nodes[nodes[n].prev].next = nodes[n].next;
deba@57
  1073
      } else {
alpar@209
  1074
        first_node = nodes[n].next;
deba@57
  1075
      }
alpar@209
  1076
deba@57
  1077
      nodes[n].next = first_free_node;
deba@57
  1078
      first_free_node = n;
deba@149
  1079
      nodes[n].prev = -2;
deba@57
  1080
    }
alpar@209
  1081
kpeter@73
  1082
    void erase(const Edge& edge) {
kpeter@73
  1083
      int n = edge.id * 2;
alpar@209
  1084
deba@57
  1085
      if (arcs[n].next_out != -1) {
alpar@209
  1086
        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209
  1087
      }
deba@57
  1088
deba@57
  1089
      if (arcs[n].prev_out != -1) {
alpar@209
  1090
        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57
  1091
      } else {
alpar@209
  1092
        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
deba@57
  1093
      }
deba@57
  1094
deba@57
  1095
      if (arcs[n | 1].next_out != -1) {
alpar@209
  1096
        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
alpar@209
  1097
      }
deba@57
  1098
deba@57
  1099
      if (arcs[n | 1].prev_out != -1) {
alpar@209
  1100
        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
deba@57
  1101
      } else {
alpar@209
  1102
        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
deba@57
  1103
      }
alpar@209
  1104
deba@57
  1105
      arcs[n].next_out = first_free_arc;
alpar@209
  1106
      first_free_arc = n;
deba@149
  1107
      arcs[n].prev_out = -2;
deba@149
  1108
      arcs[n | 1].prev_out = -2;
deba@57
  1109
deba@57
  1110
    }
deba@57
  1111
deba@57
  1112
    void clear() {
deba@57
  1113
      arcs.clear();
deba@57
  1114
      nodes.clear();
deba@57
  1115
      first_node = first_free_node = first_free_arc = -1;
deba@57
  1116
    }
deba@57
  1117
deba@57
  1118
  protected:
deba@57
  1119
deba@235
  1120
    void changeV(Edge e, Node n) {
deba@57
  1121
      if(arcs[2 * e.id].next_out != -1) {
alpar@209
  1122
        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
deba@57
  1123
      }
deba@57
  1124
      if(arcs[2 * e.id].prev_out != -1) {
alpar@209
  1125
        arcs[arcs[2 * e.id].prev_out].next_out =
deba@57
  1126
          arcs[2 * e.id].next_out;
deba@57
  1127
      } else {
alpar@209
  1128
        nodes[arcs[(2 * e.id) | 1].target].first_out =
deba@57
  1129
          arcs[2 * e.id].next_out;
deba@57
  1130
      }
deba@57
  1131
deba@57
  1132
      if (nodes[n.id].first_out != -1) {
alpar@209
  1133
        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@57
  1134
      }
deba@57
  1135
      arcs[(2 * e.id) | 1].target = n.id;
deba@57
  1136
      arcs[2 * e.id].prev_out = -1;
deba@57
  1137
      arcs[2 * e.id].next_out = nodes[n.id].first_out;
deba@57
  1138
      nodes[n.id].first_out = 2 * e.id;
deba@57
  1139
    }
deba@57
  1140
deba@235
  1141
    void changeU(Edge e, Node n) {
deba@57
  1142
      if(arcs[(2 * e.id) | 1].next_out != -1) {
alpar@209
  1143
        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
deba@57
  1144
          arcs[(2 * e.id) | 1].prev_out;
deba@57
  1145
      }
deba@57
  1146
      if(arcs[(2 * e.id) | 1].prev_out != -1) {
alpar@209
  1147
        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
deba@57
  1148
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1149
      } else {
alpar@209
  1150
        nodes[arcs[2 * e.id].target].first_out =
deba@57
  1151
          arcs[(2 * e.id) | 1].next_out;
deba@57
  1152
      }
deba@57
  1153
deba@57
  1154
      if (nodes[n.id].first_out != -1) {
alpar@209
  1155
        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
deba@57
  1156
      }
deba@57
  1157
      arcs[2 * e.id].target = n.id;
deba@57
  1158
      arcs[(2 * e.id) | 1].prev_out = -1;
deba@57
  1159
      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
deba@57
  1160
      nodes[n.id].first_out = ((2 * e.id) | 1);
deba@57
  1161
    }
deba@57
  1162
deba@57
  1163
  };
deba@57
  1164
deba@57
  1165
  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
deba@57
  1166
deba@57
  1167
kpeter@73
  1168
  /// \addtogroup graphs
deba@57
  1169
  /// @{
deba@57
  1170
kpeter@73
  1171
  ///A general undirected graph structure.
deba@57
  1172
kpeter@735
  1173
  ///\ref ListGraph is a versatile and fast undirected graph
kpeter@735
  1174
  ///implementation based on linked lists that are stored in
alpar@209
  1175
  ///\c std::vector structures.
deba@57
  1176
  ///
kpeter@735
  1177
  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
kpeter@735
  1178
  ///and it also provides several useful additional functionalities.
kpeter@735
  1179
  ///Most of its member functions and nested classes are documented
kpeter@73
  1180
  ///only in the concept class.
kpeter@73
  1181
  ///
kpeter@73
  1182
  ///\sa concepts::Graph
kpeter@735
  1183
  ///\sa ListDigraph
deba@57
  1184
  class ListGraph : public ExtendedListGraphBase {
kpeter@617
  1185
    typedef ExtendedListGraphBase Parent;
kpeter@617
  1186
deba@57
  1187
  private:
kpeter@735
  1188
    /// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@57
  1189
    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
kpeter@735
  1190
    /// \brief Assignment of a graph to another one is \e not allowed.
kpeter@735
  1191
    /// Use GraphCopy instead.
deba@57
  1192
    void operator=(const ListGraph &) {}
deba@57
  1193
  public:
deba@57
  1194
    /// Constructor
alpar@209
  1195
deba@57
  1196
    /// Constructor.
deba@57
  1197
    ///
deba@57
  1198
    ListGraph() {}
deba@57
  1199
kpeter@73
  1200
    typedef Parent::OutArcIt IncEdgeIt;
deba@57
  1201
kpeter@73
  1202
    /// \brief Add a new node to the graph.
deba@57
  1203
    ///
kpeter@735
  1204
    /// This function adds a new node to the graph.
kpeter@559
  1205
    /// \return The new node.
deba@57
  1206
    Node addNode() { return Parent::addNode(); }
deba@57
  1207
kpeter@73
  1208
    /// \brief Add a new edge to the graph.
deba@57
  1209
    ///
kpeter@735
  1210
    /// This function adds a new edge to the graph between nodes
kpeter@735
  1211
    /// \c u and \c v with inherent orientation from node \c u to
kpeter@735
  1212
    /// node \c v.
kpeter@559
  1213
    /// \return The new edge.
kpeter@735
  1214
    Edge addEdge(Node u, Node v) {
kpeter@735
  1215
      return Parent::addEdge(u, v);
deba@57
  1216
    }
deba@234
  1217
kpeter@735
  1218
    ///\brief Erase a node from the graph.
deba@234
  1219
    ///
kpeter@735
  1220
    /// This function erases the given node from the graph.
kpeter@735
  1221
    void erase(Node n) { Parent::erase(n); }
kpeter@735
  1222
kpeter@735
  1223
    ///\brief Erase an edge from the graph.
deba@234
  1224
    ///
kpeter@735
  1225
    /// This function erases the given edge from the graph.
kpeter@735
  1226
    void erase(Edge e) { Parent::erase(e); }
deba@149
  1227
    /// Node validity check
deba@149
  1228
kpeter@735
  1229
    /// This function gives back \c true if the given node is valid,
kpeter@735
  1230
    /// i.e. it is a real node of the graph.
deba@149
  1231
    ///
kpeter@735
  1232
    /// \warning A removed node could become valid again if new nodes are
deba@149
  1233
    /// added to the graph.
deba@149
  1234
    bool valid(Node n) const { return Parent::valid(n); }
kpeter@735
  1235
    /// Edge validity check
kpeter@735
  1236
kpeter@735
  1237
    /// This function gives back \c true if the given edge is valid,
kpeter@735
  1238
    /// i.e. it is a real edge of the graph.
kpeter@735
  1239
    ///
kpeter@735
  1240
    /// \warning A removed edge could become valid again if new edges are
kpeter@735
  1241
    /// added to the graph.
kpeter@735
  1242
    bool valid(Edge e) const { return Parent::valid(e); }
deba@149
  1243
    /// Arc validity check
deba@149
  1244
kpeter@735
  1245
    /// This function gives back \c true if the given arc is valid,
kpeter@735
  1246
    /// i.e. it is a real arc of the graph.
deba@149
  1247
    ///
kpeter@735
  1248
    /// \warning A removed arc could become valid again if new edges are
deba@149
  1249
    /// added to the graph.
deba@149
  1250
    bool valid(Arc a) const { return Parent::valid(a); }
deba@149
  1251
kpeter@735
  1252
    /// \brief Change the first node of an edge.
deba@149
  1253
    ///
kpeter@735
  1254
    /// This function changes the first node of the given edge \c e to \c n.
deba@57
  1255
    ///
kpeter@735
  1256
    ///\note \c EdgeIt and \c ArcIt iterators referencing the
kpeter@735
  1257
    ///changed edge are invalidated and all other iterators whose
kpeter@735
  1258
    ///base node is the changed node are also invalidated.
kpeter@73
  1259
    ///
kpeter@73
  1260
    ///\warning This functionality cannot be used together with the
kpeter@73
  1261
    ///Snapshot feature.
deba@235
  1262
    void changeU(Edge e, Node n) {
deba@235
  1263
      Parent::changeU(e,n);
alpar@209
  1264
    }
kpeter@735
  1265
    /// \brief Change the second node of an edge.
deba@57
  1266
    ///
kpeter@735
  1267
    /// This function changes the second node of the given edge \c e to \c n.
deba@57
  1268
    ///
kpeter@735
  1269
    ///\note \c EdgeIt iterators referencing the changed edge remain
kpeter@735
  1270
    ///valid, however \c ArcIt iterators referencing the changed edge and
kpeter@735
  1271
    ///all other iterators whose base node is the changed node are also
kpeter@735
  1272
    ///invalidated.
kpeter@73
  1273
    ///
kpeter@73
  1274
    ///\warning This functionality cannot be used together with the
kpeter@73
  1275
    ///Snapshot feature.
deba@235
  1276
    void changeV(Edge e, Node n) {
deba@235
  1277
      Parent::changeV(e,n);
deba@57
  1278
    }
kpeter@735
  1279
deba@57
  1280
    /// \brief Contract two nodes.
deba@57
  1281
    ///
kpeter@735
  1282
    /// This function contracts the given two nodes.
kpeter@735
  1283
    /// Node \c b is removed, but instead of deleting
kpeter@735
  1284
    /// its incident edges, they are joined to node \c a.
kpeter@735
  1285
    /// If the last parameter \c r is \c true (this is the default value),
kpeter@735
  1286
    /// then the newly created loops are removed.
deba@57
  1287
    ///
kpeter@735
  1288
    /// \note The moved edges are joined to node \c a using changeU()
kpeter@735
  1289
    /// or changeV(), thus all edge and arc iterators whose base node is
kpeter@735
  1290
    /// \c b are invalidated.
kpeter@735
  1291
    /// Moreover all iterators referencing node \c b or the removed 
kpeter@735
  1292
    /// loops are also invalidated. Other iterators remain valid.
kpeter@73
  1293
    ///
kpeter@73
  1294
    ///\warning This functionality cannot be used together with the
kpeter@73
  1295
    ///Snapshot feature.
deba@57
  1296
    void contract(Node a, Node b, bool r = true) {
kpeter@73
  1297
      for(IncEdgeIt e(*this, b); e!=INVALID;) {
alpar@209
  1298
        IncEdgeIt f = e; ++f;
alpar@209
  1299
        if (r && runningNode(e) == a) {
alpar@209
  1300
          erase(e);
deba@235
  1301
        } else if (u(e) == b) {
deba@235
  1302
          changeU(e, a);
alpar@209
  1303
        } else {
deba@235
  1304
          changeV(e, a);
alpar@209
  1305
        }
alpar@209
  1306
        e = f;
deba@57
  1307
      }
deba@57
  1308
      erase(b);
deba@57
  1309
    }
deba@57
  1310
kpeter@735
  1311
    ///Clear the graph.
kpeter@735
  1312
kpeter@735
  1313
    ///This function erases all nodes and arcs from the graph.
kpeter@735
  1314
    ///
kpeter@735
  1315
    void clear() {
kpeter@735
  1316
      Parent::clear();
kpeter@735
  1317
    }
kpeter@617
  1318
kpeter@736
  1319
    /// Reserve memory for nodes.
kpeter@736
  1320
kpeter@736
  1321
    /// Using this function, it is possible to avoid superfluous memory
kpeter@736
  1322
    /// allocation: if you know that the graph you want to build will
kpeter@736
  1323
    /// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@736
  1324
    /// then it is worth reserving space for this amount before starting
kpeter@736
  1325
    /// to build the graph.
kpeter@736
  1326
    /// \sa reserveEdge()
kpeter@736
  1327
    void reserveNode(int n) { nodes.reserve(n); };
kpeter@736
  1328
kpeter@736
  1329
    /// Reserve memory for edges.
kpeter@736
  1330
kpeter@736
  1331
    /// Using this function, it is possible to avoid superfluous memory
kpeter@736
  1332
    /// allocation: if you know that the graph you want to build will
kpeter@736
  1333
    /// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@736
  1334
    /// then it is worth reserving space for this amount before starting
kpeter@736
  1335
    /// to build the graph.
kpeter@736
  1336
    /// \sa reserveNode()
kpeter@736
  1337
    void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@57
  1338
kpeter@73
  1339
    /// \brief Class to make a snapshot of the graph and restore
kpeter@73
  1340
    /// it later.
deba@57
  1341
    ///
kpeter@73
  1342
    /// Class to make a snapshot of the graph and restore it later.
deba@57
  1343
    ///
deba@57
  1344
    /// The newly added nodes and edges can be removed
deba@57
  1345
    /// using the restore() function.
deba@57
  1346
    ///
kpeter@735
  1347
    /// \note After a state is restored, you cannot restore a later state, 
kpeter@735
  1348
    /// i.e. you cannot add the removed nodes and edges again using
kpeter@735
  1349
    /// another Snapshot instance.
kpeter@735
  1350
    ///
kpeter@735
  1351
    /// \warning Node and edge deletions and other modifications
kpeter@735
  1352
    /// (e.g. changing the end-nodes of edges or contracting nodes)
kpeter@735
  1353
    /// cannot be restored. These events invalidate the snapshot.
kpeter@735
  1354
    /// However the edges and nodes that were added to the graph after
kpeter@735
  1355
    /// making the current snapshot can be removed without invalidating it.
deba@57
  1356
    class Snapshot {
deba@57
  1357
    protected:
deba@57
  1358
deba@57
  1359
      typedef Parent::NodeNotifier NodeNotifier;
deba@57
  1360
deba@57
  1361
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57
  1362
      public:
deba@57
  1363
deba@57
  1364
        NodeObserverProxy(Snapshot& _snapshot)
deba@57
  1365
          : snapshot(_snapshot) {}
deba@57
  1366
deba@57
  1367
        using NodeNotifier::ObserverBase::attach;
deba@57
  1368
        using NodeNotifier::ObserverBase::detach;
deba@57
  1369
        using NodeNotifier::ObserverBase::attached;
alpar@209
  1370
deba@57
  1371
      protected:
alpar@209
  1372
deba@57
  1373
        virtual void add(const Node& node) {
deba@57
  1374
          snapshot.addNode(node);
deba@57
  1375
        }
deba@57
  1376
        virtual void add(const std::vector<Node>& nodes) {
deba@57
  1377
          for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57
  1378
            snapshot.addNode(nodes[i]);
deba@57
  1379
          }
deba@57
  1380
        }
deba@57
  1381
        virtual void erase(const Node& node) {
deba@57
  1382
          snapshot.eraseNode(node);
deba@57
  1383
        }
deba@57
  1384
        virtual void erase(const std::vector<Node>& nodes) {
deba@57
  1385
          for (int i = 0; i < int(nodes.size()); ++i) {
deba@57
  1386
            snapshot.eraseNode(nodes[i]);
deba@57
  1387
          }
deba@57
  1388
        }
deba@57
  1389
        virtual void build() {
deba@57
  1390
          Node node;
deba@57
  1391
          std::vector<Node> nodes;
alpar@209
  1392
          for (notifier()->first(node); node != INVALID;
deba@57
  1393
               notifier()->next(node)) {
deba@57
  1394
            nodes.push_back(node);
deba@57
  1395
          }
deba@57
  1396
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57
  1397
            snapshot.addNode(nodes[i]);
deba@57
  1398
          }
deba@57
  1399
        }
deba@57
  1400
        virtual void clear() {
deba@57
  1401
          Node node;
alpar@209
  1402
          for (notifier()->first(node); node != INVALID;
deba@57
  1403
               notifier()->next(node)) {
deba@57
  1404
            snapshot.eraseNode(node);
deba@57
  1405
          }
deba@57
  1406
        }
deba@57
  1407
deba@57
  1408
        Snapshot& snapshot;
deba@57
  1409
      };
deba@57
  1410
deba@57
  1411
      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@57
  1412
      public:
deba@57
  1413
deba@57
  1414
        EdgeObserverProxy(Snapshot& _snapshot)
deba@57
  1415
          : snapshot(_snapshot) {}
deba@57
  1416
deba@57
  1417
        using EdgeNotifier::ObserverBase::attach;
deba@57
  1418
        using EdgeNotifier::ObserverBase::detach;
deba@57
  1419
        using EdgeNotifier::ObserverBase::attached;
alpar@209
  1420
deba@57
  1421
      protected:
deba@57
  1422
kpeter@73
  1423
        virtual void add(const Edge& edge) {
kpeter@73
  1424
          snapshot.addEdge(edge);
deba@57
  1425
        }
kpeter@73
  1426
        virtual void add(const std::vector<Edge>& edges) {
kpeter@73
  1427
          for (int i = edges.size() - 1; i >= 0; ++i) {
kpeter@73
  1428
            snapshot.addEdge(edges[i]);
deba@57
  1429
          }
deba@57
  1430
        }
kpeter@73
  1431
        virtual void erase(const Edge& edge) {
kpeter@73
  1432
          snapshot.eraseEdge(edge);
deba@57
  1433
        }
kpeter@73
  1434
        virtual void erase(const std::vector<Edge>& edges) {
kpeter@73
  1435
          for (int i = 0; i < int(edges.size()); ++i) {
kpeter@73
  1436
            snapshot.eraseEdge(edges[i]);
deba@57
  1437
          }
deba@57
  1438
        }
deba@57
  1439
        virtual void build() {
kpeter@73
  1440
          Edge edge;
kpeter@73
  1441
          std::vector<Edge> edges;
alpar@209
  1442
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1443
               notifier()->next(edge)) {
kpeter@73
  1444
            edges.push_back(edge);
deba@57
  1445
          }
kpeter@73
  1446
          for (int i = edges.size() - 1; i >= 0; --i) {
kpeter@73
  1447
            snapshot.addEdge(edges[i]);
deba@57
  1448
          }
deba@57
  1449
        }
deba@57
  1450
        virtual void clear() {
kpeter@73
  1451
          Edge edge;
alpar@209
  1452
          for (notifier()->first(edge); edge != INVALID;
kpeter@73
  1453
               notifier()->next(edge)) {
kpeter@73
  1454
            snapshot.eraseEdge(edge);
deba@57
  1455
          }
deba@57
  1456
        }
deba@57
  1457
deba@57
  1458
        Snapshot& snapshot;
deba@57
  1459
      };
kpeter@73
  1460
kpeter@73
  1461
      ListGraph *graph;
deba@57
  1462
deba@57
  1463
      NodeObserverProxy node_observer_proxy;
kpeter@73
  1464
      EdgeObserverProxy edge_observer_proxy;
deba@57
  1465
deba@57
  1466
      std::list<Node> added_nodes;
kpeter@73
  1467
      std::list<Edge> added_edges;
deba@57
  1468
deba@57
  1469
deba@57
  1470
      void addNode(const Node& node) {
alpar@209
  1471
        added_nodes.push_front(node);
deba@57
  1472
      }
deba@57
  1473
      void eraseNode(const Node& node) {
alpar@209
  1474
        std::list<Node>::iterator it =
deba@57
  1475
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57
  1476
        if (it == added_nodes.end()) {
deba@57
  1477
          clear();
kpeter@73
  1478
          edge_observer_proxy.detach();
deba@57
  1479
          throw NodeNotifier::ImmediateDetach();
deba@57
  1480
        } else {
deba@57
  1481
          added_nodes.erase(it);
deba@57
  1482
        }
deba@57
  1483
      }
deba@57
  1484
kpeter@73
  1485
      void addEdge(const Edge& edge) {
alpar@209
  1486
        added_edges.push_front(edge);
deba@57
  1487
      }
kpeter@73
  1488
      void eraseEdge(const Edge& edge) {
alpar@209
  1489
        std::list<Edge>::iterator it =
kpeter@73
  1490
          std::find(added_edges.begin(), added_edges.end(), edge);
kpeter@73
  1491
        if (it == added_edges.end()) {
deba@57
  1492
          clear();
deba@57
  1493
          node_observer_proxy.detach();
deba@57
  1494
          throw EdgeNotifier::ImmediateDetach();
deba@57
  1495
        } else {
kpeter@73
  1496
          added_edges.erase(it);
kpeter@73
  1497
        }
deba@57
  1498
      }
deba@57
  1499
kpeter@73
  1500
      void attach(ListGraph &_graph) {
alpar@209
  1501
        graph = &_graph;
alpar@209
  1502
        node_observer_proxy.attach(graph->notifier(Node()));
kpeter@73
  1503
        edge_observer_proxy.attach(graph->notifier(Edge()));
deba@57
  1504
      }
alpar@209
  1505
deba@57
  1506
      void detach() {
alpar@209
  1507
        node_observer_proxy.detach();
alpar@209
  1508
        edge_observer_proxy.detach();
deba@57
  1509
      }
deba@57
  1510
deba@57
  1511
      bool attached() const {
deba@57
  1512
        return node_observer_proxy.attached();
deba@57
  1513
      }
deba@57
  1514
deba@57
  1515
      void clear() {
deba@57
  1516
        added_nodes.clear();
alpar@209
  1517
        added_edges.clear();
deba@57
  1518
      }
deba@57
  1519
deba@57
  1520
    public:
deba@57
  1521
deba@57
  1522
      /// \brief Default constructor.
deba@57
  1523
      ///
deba@57
  1524
      /// Default constructor.
kpeter@735
  1525
      /// You have to call save() to actually make a snapshot.
alpar@209
  1526
      Snapshot()
alpar@209
  1527
        : graph(0), node_observer_proxy(*this),
kpeter@73
  1528
          edge_observer_proxy(*this) {}
alpar@209
  1529
deba@57
  1530
      /// \brief Constructor that immediately makes a snapshot.
alpar@209
  1531
      ///
kpeter@735
  1532
      /// This constructor immediately makes a snapshot of the given graph.
kpeter@735
  1533
      Snapshot(ListGraph &gr)
alpar@209
  1534
        : node_observer_proxy(*this),
kpeter@73
  1535
          edge_observer_proxy(*this) {
kpeter@735
  1536
        attach(gr);
deba@57
  1537
      }
alpar@209
  1538
deba@57
  1539
      /// \brief Make a snapshot.
deba@57
  1540
      ///
kpeter@735
  1541
      /// This function makes a snapshot of the given graph.
kpeter@735
  1542
      /// It can be called more than once. In case of a repeated
deba@57
  1543
      /// call, the previous snapshot gets lost.
kpeter@735
  1544
      void save(ListGraph &gr) {
deba@57
  1545
        if (attached()) {
deba@57
  1546
          detach();
deba@57
  1547
          clear();
deba@57
  1548
        }
kpeter@735
  1549
        attach(gr);
deba@57
  1550
      }
alpar@209
  1551
deba@57
  1552
      /// \brief Undo the changes until the last snapshot.
kpeter@735
  1553
      ///
kpeter@735
  1554
      /// This function undos the changes until the last snapshot
kpeter@735
  1555
      /// created by save() or Snapshot(ListGraph&).
kpeter@740
  1556
      ///
kpeter@740
  1557
      /// \warning This method invalidates the snapshot, i.e. repeated
kpeter@740
  1558
      /// restoring is not supported unless you call save() again.
deba@57
  1559
      void restore() {
alpar@209
  1560
        detach();
alpar@209
  1561
        for(std::list<Edge>::iterator it = added_edges.begin();
kpeter@73
  1562
            it != added_edges.end(); ++it) {
alpar@209
  1563
          graph->erase(*it);
alpar@209
  1564
        }
alpar@209
  1565
        for(std::list<Node>::iterator it = added_nodes.begin();
deba@57
  1566
            it != added_nodes.end(); ++it) {
alpar@209
  1567
          graph->erase(*it);
alpar@209
  1568
        }
deba@57
  1569
        clear();
deba@57
  1570
      }
deba@57
  1571
kpeter@735
  1572
      /// \brief Returns \c true if the snapshot is valid.
deba@57
  1573
      ///
kpeter@735
  1574
      /// This function returns \c true if the snapshot is valid.
deba@57
  1575
      bool valid() const {
deba@57
  1576
        return attached();
deba@57
  1577
      }
deba@57
  1578
    };
deba@57
  1579
  };
alpar@209
  1580
alpar@209
  1581
  /// @}
deba@57
  1582
} //namespace lemon
alpar@209
  1583
deba@57
  1584
deba@57
  1585
#endif