lemon/list_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 07 Feb 2008 22:25:42 +0000
changeset 68 a315a588a20d
parent 39 0a01d811071f
child 73 c56b7389dc78
permissions -rw-r--r--
Some usefull math constants

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