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