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