lemon/list_graph.h
author alpar
Fri, 14 Jul 2006 10:51:14 +0000
changeset 2139 582c8c28aa01
parent 2128 509846825ddf
child 2151 38ec4a930c05
permissions -rw-r--r--
Some updates and restructuring
alpar@948
     1
/* -*- C++ -*-
alpar@948
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@948
     8
 *
alpar@948
     9
 * Permission to use, modify and distribute this software is granted
alpar@948
    10
 * provided that this copyright notice appears in all copies. For
alpar@948
    11
 * precise terms see the accompanying LICENSE file.
alpar@948
    12
 *
alpar@948
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@948
    14
 * express or implied, and with no claim as to its suitability for any
alpar@948
    15
 * purpose.
alpar@948
    16
 *
alpar@948
    17
 */
alpar@395
    18
alpar@921
    19
#ifndef LEMON_LIST_GRAPH_H
alpar@921
    20
#define LEMON_LIST_GRAPH_H
alpar@395
    21
alpar@948
    22
///\ingroup graphs
alpar@948
    23
///\file
deba@2116
    24
///\brief ListGraph, ListUGraph classes.
alpar@948
    25
deba@2116
    26
#include <lemon/bits/base_extender.h>
deba@1791
    27
#include <lemon/bits/graph_extender.h>
deba@782
    28
deba@2116
    29
#include <lemon/error.h>
deba@2116
    30
deba@1979
    31
#include <vector>
alpar@1011
    32
#include <list>
deba@782
    33
alpar@921
    34
namespace lemon {
alpar@395
    35
klao@946
    36
  class ListGraphBase {
alpar@406
    37
alpar@949
    38
  protected:
klao@946
    39
    struct NodeT {
deba@1470
    40
      int first_in, first_out;
alpar@397
    41
      int prev, next;
alpar@395
    42
    };
klao@946
    43
 
klao@946
    44
    struct EdgeT {
alpar@986
    45
      int target, source;
alpar@397
    46
      int prev_in, prev_out;
alpar@397
    47
      int next_in, next_out;
alpar@395
    48
    };
alpar@395
    49
alpar@395
    50
    std::vector<NodeT> nodes;
klao@946
    51
alpar@397
    52
    int first_node;
klao@946
    53
alpar@397
    54
    int first_free_node;
klao@946
    55
alpar@395
    56
    std::vector<EdgeT> edges;
klao@946
    57
alpar@397
    58
    int first_free_edge;
alpar@395
    59
    
deba@782
    60
  public:
alpar@395
    61
    
klao@946
    62
    typedef ListGraphBase Graph;
alpar@397
    63
    
klao@946
    64
    class Node {
marci@975
    65
      friend class ListGraphBase;
klao@946
    66
    protected:
alpar@395
    67
klao@946
    68
      int id;
deba@2031
    69
      explicit Node(int pid) { id = pid;}
alpar@395
    70
klao@946
    71
    public:
klao@946
    72
      Node() {}
klao@946
    73
      Node (Invalid) { id = -1; }
klao@946
    74
      bool operator==(const Node& node) const {return id == node.id;}
klao@946
    75
      bool operator!=(const Node& node) const {return id != node.id;}
klao@946
    76
      bool operator<(const Node& node) const {return id < node.id;}
klao@946
    77
    };
deba@782
    78
klao@946
    79
    class Edge {
marci@975
    80
      friend class ListGraphBase;
klao@946
    81
    protected:
deba@782
    82
klao@946
    83
      int id;
deba@2031
    84
      explicit Edge(int pid) { id = pid;}
alpar@395
    85
klao@946
    86
    public:
klao@946
    87
      Edge() {}
klao@946
    88
      Edge (Invalid) { id = -1; }
klao@946
    89
      bool operator==(const Edge& edge) const {return id == edge.id;}
klao@946
    90
      bool operator!=(const Edge& edge) const {return id != edge.id;}
klao@946
    91
      bool operator<(const Edge& edge) const {return id < edge.id;}
klao@946
    92
    };
klao@946
    93
klao@946
    94
klao@946
    95
klao@946
    96
    ListGraphBase()
deba@782
    97
      : nodes(), first_node(-1),
deba@782
    98
	first_free_node(-1), edges(), first_free_edge(-1) {}
deba@782
    99
alpar@395
   100
    
alpar@813
   101
    /// Maximum node ID.
alpar@813
   102
    
alpar@813
   103
    /// Maximum node ID.
alpar@813
   104
    ///\sa id(Node)
deba@1791
   105
    int maxNodeId() const { return nodes.size()-1; } 
klao@946
   106
alpar@813
   107
    /// Maximum edge ID.
alpar@813
   108
    
alpar@813
   109
    /// Maximum edge ID.
alpar@813
   110
    ///\sa id(Edge)
deba@1791
   111
    int maxEdgeId() const { return edges.size()-1; }
alpar@395
   112
deba@2031
   113
    Node source(Edge e) const { return Node(edges[e.id].source); }
deba@2031
   114
    Node target(Edge e) const { return Node(edges[e.id].target); }
alpar@395
   115
alpar@395
   116
klao@946
   117
    void first(Node& node) const { 
klao@946
   118
      node.id = first_node;
klao@946
   119
    }
klao@946
   120
klao@946
   121
    void next(Node& node) const {
klao@946
   122
      node.id = nodes[node.id].next;
klao@946
   123
    }
klao@946
   124
klao@946
   125
klao@946
   126
    void first(Edge& e) const { 
klao@946
   127
      int n;
klao@946
   128
      for(n = first_node; 
klao@946
   129
	  n!=-1 && nodes[n].first_in == -1; 
klao@946
   130
	  n = nodes[n].next);
klao@946
   131
      e.id = (n == -1) ? -1 : nodes[n].first_in;
klao@946
   132
    }
klao@946
   133
klao@946
   134
    void next(Edge& edge) const {
klao@946
   135
      if (edges[edge.id].next_in != -1) {
klao@946
   136
	edge.id = edges[edge.id].next_in;
klao@946
   137
      } else {
klao@946
   138
	int n;
alpar@986
   139
	for(n = nodes[edges[edge.id].target].next;
klao@946
   140
	  n!=-1 && nodes[n].first_in == -1; 
klao@946
   141
	  n = nodes[n].next);
klao@946
   142
	edge.id = (n == -1) ? -1 : nodes[n].first_in;
klao@946
   143
      }      
klao@946
   144
    }
klao@946
   145
klao@946
   146
    void firstOut(Edge &e, const Node& v) const {
klao@946
   147
      e.id = nodes[v.id].first_out;
klao@946
   148
    }
klao@946
   149
    void nextOut(Edge &e) const {
klao@946
   150
      e.id=edges[e.id].next_out;
klao@946
   151
    }
klao@946
   152
klao@946
   153
    void firstIn(Edge &e, const Node& v) const {
klao@946
   154
      e.id = nodes[v.id].first_in;
klao@946
   155
    }
klao@946
   156
    void nextIn(Edge &e) const {
klao@946
   157
      e.id=edges[e.id].next_in;
klao@946
   158
    }
klao@946
   159
alpar@813
   160
    
klao@946
   161
    static int id(Node v) { return v.id; }
klao@946
   162
    static int id(Edge e) { return e.id; }
alpar@395
   163
deba@1791
   164
    static Node nodeFromId(int id) { return Node(id);}
deba@1791
   165
    static Edge edgeFromId(int id) { return Edge(id);}
deba@1106
   166
alpar@397
   167
    /// Adds a new node to the graph.
alpar@397
   168
alpar@2123
   169
    /// Adds a new node to the graph.
alpar@2123
   170
    ///
alpar@813
   171
    /// \warning It adds the new node to the front of the list.
alpar@397
   172
    /// (i.e. the lastly added node becomes the first.)
klao@946
   173
    Node addNode() {     
alpar@397
   174
      int n;
alpar@397
   175
      
klao@946
   176
      if(first_free_node==-1) {
klao@946
   177
	n = nodes.size();
klao@946
   178
	nodes.push_back(NodeT());
klao@946
   179
      } else {
alpar@397
   180
	n = first_free_node;
alpar@397
   181
	first_free_node = nodes[n].next;
alpar@397
   182
      }
alpar@397
   183
      
alpar@397
   184
      nodes[n].next = first_node;
alpar@397
   185
      if(first_node != -1) nodes[first_node].prev = n;
alpar@397
   186
      first_node = n;
alpar@397
   187
      nodes[n].prev = -1;
alpar@397
   188
      
alpar@397
   189
      nodes[n].first_in = nodes[n].first_out = -1;
alpar@397
   190
      
klao@946
   191
      return Node(n);
alpar@395
   192
    }
alpar@395
   193
    
alpar@395
   194
    Edge addEdge(Node u, Node v) {
klao@946
   195
      int n;      
klao@946
   196
klao@946
   197
      if (first_free_edge == -1) {
klao@946
   198
	n = edges.size();
klao@946
   199
	edges.push_back(EdgeT());
klao@946
   200
      } else {
alpar@397
   201
	n = first_free_edge;
alpar@397
   202
	first_free_edge = edges[n].next_in;
alpar@397
   203
      }
alpar@397
   204
      
alpar@986
   205
      edges[n].source = u.id; 
alpar@986
   206
      edges[n].target = v.id;
alpar@395
   207
klao@946
   208
      edges[n].next_out = nodes[u.id].first_out;
klao@946
   209
      if(nodes[u.id].first_out != -1) {
klao@946
   210
	edges[nodes[u.id].first_out].prev_out = n;
klao@946
   211
      }
klao@946
   212
      
klao@946
   213
      edges[n].next_in = nodes[v.id].first_in;
klao@946
   214
      if(nodes[v.id].first_in != -1) {
klao@946
   215
	edges[nodes[v.id].first_in].prev_in = n;
klao@946
   216
      }
klao@946
   217
      
alpar@397
   218
      edges[n].prev_in = edges[n].prev_out = -1;
alpar@397
   219
	
klao@946
   220
      nodes[u.id].first_out = nodes[v.id].first_in = n;
alpar@397
   221
klao@946
   222
      return Edge(n);
alpar@395
   223
    }
alpar@774
   224
    
klao@946
   225
    void erase(const Node& node) {
klao@946
   226
      int n = node.id;
klao@946
   227
      
klao@946
   228
      if(nodes[n].next != -1) {
klao@946
   229
	nodes[nodes[n].next].prev = nodes[n].prev;
klao@946
   230
      }
klao@946
   231
      
klao@946
   232
      if(nodes[n].prev != -1) {
klao@946
   233
	nodes[nodes[n].prev].next = nodes[n].next;
klao@946
   234
      } else {
klao@946
   235
	first_node = nodes[n].next;
klao@946
   236
      }
klao@946
   237
      
klao@946
   238
      nodes[n].next = first_free_node;
klao@946
   239
      first_free_node = n;
alpar@395
   240
alpar@774
   241
    }
alpar@774
   242
    
klao@946
   243
    void erase(const Edge& edge) {
klao@946
   244
      int n = edge.id;
alpar@397
   245
      
klao@946
   246
      if(edges[n].next_in!=-1) {
alpar@397
   247
	edges[edges[n].next_in].prev_in = edges[n].prev_in;
klao@946
   248
      }
klao@946
   249
klao@946
   250
      if(edges[n].prev_in!=-1) {
alpar@397
   251
	edges[edges[n].prev_in].next_in = edges[n].next_in;
klao@946
   252
      } else {
alpar@986
   253
	nodes[edges[n].target].first_in = edges[n].next_in;
klao@946
   254
      }
klao@946
   255
alpar@397
   256
      
klao@946
   257
      if(edges[n].next_out!=-1) {
alpar@397
   258
	edges[edges[n].next_out].prev_out = edges[n].prev_out;
klao@946
   259
      } 
klao@946
   260
klao@946
   261
      if(edges[n].prev_out!=-1) {
alpar@397
   262
	edges[edges[n].prev_out].next_out = edges[n].next_out;
klao@946
   263
      } else {
alpar@986
   264
	nodes[edges[n].source].first_out = edges[n].next_out;
klao@946
   265
      }
alpar@397
   266
      
alpar@397
   267
      edges[n].next_in = first_free_edge;
alpar@695
   268
      first_free_edge = n;      
alpar@397
   269
alpar@397
   270
    }
alpar@397
   271
alpar@397
   272
    void clear() {
deba@782
   273
      edges.clear();
deba@782
   274
      nodes.clear();
klao@946
   275
      first_node = first_free_node = first_free_edge = -1;
deba@937
   276
    }
deba@937
   277
alpar@949
   278
  protected:
deba@2111
   279
    void changeTarget(Edge e, Node n) 
alpar@949
   280
    {
alpar@949
   281
      if(edges[e.id].next_in != -1)
alpar@949
   282
	edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
alpar@949
   283
      if(edges[e.id].prev_in != -1)
alpar@949
   284
	edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
alpar@986
   285
      else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
deba@1702
   286
      if (nodes[n.id].first_in != -1) {
deba@1702
   287
	edges[nodes[n.id].first_in].prev_in = e.id;
deba@1702
   288
      }
alpar@986
   289
      edges[e.id].target = n.id;
alpar@949
   290
      edges[e.id].prev_in = -1;
alpar@949
   291
      edges[e.id].next_in = nodes[n.id].first_in;
alpar@949
   292
      nodes[n.id].first_in = e.id;
alpar@949
   293
    }
deba@2111
   294
    void changeSource(Edge e, Node n) 
alpar@949
   295
    {
alpar@949
   296
      if(edges[e.id].next_out != -1)
alpar@949
   297
	edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
alpar@949
   298
      if(edges[e.id].prev_out != -1)
alpar@949
   299
	edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
alpar@986
   300
      else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
deba@1702
   301
      if (nodes[n.id].first_out != -1) {
deba@1702
   302
	edges[nodes[n.id].first_out].prev_out = e.id;
deba@1702
   303
      }
alpar@986
   304
      edges[e.id].source = n.id;
alpar@949
   305
      edges[e.id].prev_out = -1;
alpar@949
   306
      edges[e.id].next_out = nodes[n.id].first_out;
alpar@949
   307
      nodes[n.id].first_out = e.id;
alpar@949
   308
    }
alpar@949
   309
alpar@919
   310
  };
deba@909
   311
deba@1979
   312
  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
alpar@400
   313
deba@2116
   314
  /// \addtogroup graphs
deba@2116
   315
  /// @{
alpar@400
   316
alpar@948
   317
  ///A list graph class.
alpar@400
   318
alpar@2117
   319
  ///This is a simple and fast graph implementation.
alpar@948
   320
  ///
alpar@2117
   321
  ///It conforms to the \ref concept::Graph "Graph concept" and it
deba@2111
   322
  ///also provides several additional useful extra functionalities.
deba@2111
   323
  ///The most of the member functions and nested classes are
deba@2111
   324
  ///documented only in the concept class.
deba@2111
   325
  ///\sa concept::Graph.
deba@782
   326
deba@1999
   327
  class ListGraph : public ExtendedListGraphBase {
alpar@2128
   328
  private:
alpar@2128
   329
    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128
   330
    
alpar@2128
   331
    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128
   332
    ///
alpar@2128
   333
    ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
alpar@2132
   334
    ///\brief Assignment of ListGraph to another one is \e not allowed.
alpar@2128
   335
    ///Use GraphCopy() instead.
alpar@2128
   336
alpar@2132
   337
    ///Assignment of ListGraph to another one is \e not allowed.
alpar@2128
   338
    ///Use GraphCopy() instead.
alpar@2128
   339
    void operator=(const ListGraph &) {}
alpar@948
   340
  public:
deba@1999
   341
deba@1999
   342
    typedef ExtendedListGraphBase Parent;
deba@1999
   343
alpar@2128
   344
    /// Constructor
alpar@2128
   345
    
alpar@2128
   346
    /// Constructor.
alpar@2128
   347
    ///
alpar@2128
   348
    ListGraph() {}
alpar@2128
   349
deba@2111
   350
    ///Add a new node to the graph.
deba@2111
   351
    
deba@2111
   352
    /// \return the new node.
deba@2111
   353
    ///
deba@2111
   354
    Node addNode() { return Parent::addNode(); }
deba@2111
   355
deba@2111
   356
    ///Add a new edge to the graph.
deba@2111
   357
    
deba@2111
   358
    ///Add a new edge to the graph with source node \c s
deba@2111
   359
    ///and target node \c t.
deba@2111
   360
    ///\return the new edge.
deba@2111
   361
    Edge addEdge(const Node& s, const Node& t) { 
deba@2111
   362
      return Parent::addEdge(s, t); 
deba@2111
   363
    }
deba@2111
   364
alpar@1546
   365
    /// Changes the target of \c e to \c n
alpar@948
   366
alpar@1546
   367
    /// Changes the target of \c e to \c n
alpar@948
   368
    ///
deba@2114
   369
    ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
deba@2114
   370
    ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
deba@2114
   371
    ///invalidated.
alpar@2123
   372
    ///\warning This functionality cannot be used together with the Snapshot
alpar@2123
   373
    ///feature.
deba@1718
   374
    void changeTarget(Edge e, Node n) { 
deba@2111
   375
      Parent::changeTarget(e,n); 
deba@1718
   376
    }
alpar@1546
   377
    /// Changes the source of \c e to \c n
alpar@948
   378
alpar@1546
   379
    /// Changes the source of \c e to \c n
alpar@948
   380
    ///
deba@2114
   381
    ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2114
   382
    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2114
   383
    ///invalidated.
alpar@2123
   384
    ///\warning This functionality cannot be used together with the Snapshot
alpar@2123
   385
    ///feature.
deba@1718
   386
    void changeSource(Edge e, Node n) { 
deba@2111
   387
      Parent::changeSource(e,n);
deba@1718
   388
    }
alpar@949
   389
alpar@1010
   390
    /// Invert the direction of an edge.
alpar@1010
   391
deba@2114
   392
    ///\note The <tt>Edge</tt>s referencing the changed edge remain
deba@2114
   393
    ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
deba@2114
   394
    ///invalidated.
alpar@2123
   395
    ///\warning This functionality cannot be used together with the Snapshot
alpar@2123
   396
    ///feature.
alpar@1010
   397
    void reverseEdge(Edge e) {
alpar@1010
   398
      Node t=target(e);
deba@2111
   399
      changeTarget(e,source(e));
deba@2111
   400
      changeSource(e,t);
alpar@1010
   401
    }
alpar@1010
   402
deba@2111
   403
    /// \brief Using this it is possible to avoid the superfluous memory
deba@2111
   404
    /// allocation.
alpar@1010
   405
deba@2107
   406
    ///Using this it is possible to avoid the superfluous memory
deba@2107
   407
    ///allocation: if you know that the graph you want to build will
alpar@2123
   408
    ///contain at least 10 million nodes then it is worth reserving
deba@2107
   409
    ///space for this amount before starting to build the graph.
deba@2107
   410
    void reserveNode(int n) { nodes.reserve(n); };
deba@2107
   411
deba@2111
   412
    /// \brief Using this it is possible to avoid the superfluous memory
deba@2111
   413
    /// allocation.
deba@2107
   414
deba@2107
   415
    ///Using this it is possible to avoid the superfluous memory
deba@2107
   416
    ///allocation: see the \ref reserveNode function.
alpar@949
   417
    void reserveEdge(int n) { edges.reserve(n); };
alpar@1010
   418
deba@2107
   419
alpar@1010
   420
    ///Contract two nodes.
alpar@1010
   421
alpar@1010
   422
    ///This function contracts two nodes.
alpar@1010
   423
    ///
alpar@1010
   424
    ///Node \p b will be removed but instead of deleting
athos@2102
   425
    ///incident edges, they will be joined to \p a.
alpar@1010
   426
    ///The last parameter \p r controls whether to remove loops. \c true
alpar@1010
   427
    ///means that loops will be removed.
alpar@1010
   428
    ///
alpar@1010
   429
    ///\note The <tt>Edge</tt>s
alpar@1281
   430
    ///referencing a moved edge remain
athos@2102
   431
    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
alpar@1010
   432
    ///may be invalidated.
alpar@2123
   433
    ///\warning This functionality cannot be used together with the Snapshot
alpar@2123
   434
    ///feature.
deba@1718
   435
    void contract(Node a, Node b, bool r = true) 
alpar@1010
   436
    {
alpar@1010
   437
      for(OutEdgeIt e(*this,b);e!=INVALID;) {
alpar@1010
   438
	OutEdgeIt f=e;
alpar@1010
   439
	++f;
alpar@1010
   440
	if(r && target(e)==a) erase(e);
alpar@1546
   441
	else changeSource(e,a);
alpar@1010
   442
	e=f;
alpar@1010
   443
      }
alpar@1010
   444
      for(InEdgeIt e(*this,b);e!=INVALID;) {
alpar@1010
   445
	InEdgeIt f=e;
alpar@1010
   446
	++f;
alpar@1010
   447
	if(r && source(e)==a) erase(e);
alpar@1546
   448
	else changeTarget(e,a);
alpar@1010
   449
	e=f;
alpar@1010
   450
      }
alpar@1010
   451
      erase(b);
alpar@1010
   452
    }
alpar@1011
   453
alpar@1281
   454
    ///Split a node.
alpar@1011
   455
alpar@1284
   456
    ///This function splits a node. First a new node is added to the graph,
alpar@1284
   457
    ///then the source of each outgoing edge of \c n is moved to this new node.
alpar@1281
   458
    ///If \c connect is \c true (this is the default value), then a new edge
alpar@1281
   459
    ///from \c n to the newly created node is also added.
alpar@1281
   460
    ///\return The newly created node.
alpar@1281
   461
    ///
alpar@1281
   462
    ///\note The <tt>Edge</tt>s
alpar@1281
   463
    ///referencing a moved edge remain
athos@2102
   464
    ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
alpar@1281
   465
    ///may be invalidated.
alpar@1770
   466
    ///\warning This functionality cannot be used together with the Snapshot
alpar@1284
   467
    ///feature.
alpar@1281
   468
    ///\todo It could be implemented in a bit faster way.
deba@2114
   469
    Node split(Node n, bool connect = true) {
alpar@1281
   470
      Node b = addNode();
alpar@1281
   471
      for(OutEdgeIt e(*this,n);e!=INVALID;) {
alpar@1281
   472
 	OutEdgeIt f=e;
alpar@1281
   473
	++f;
alpar@1546
   474
	changeSource(e,b);
alpar@1281
   475
	e=f;
alpar@1281
   476
      }
deba@2114
   477
      if (connect) addEdge(n,b);
alpar@1281
   478
      return b;
alpar@1281
   479
    }
alpar@1281
   480
      
alpar@1812
   481
    ///Split an edge.
alpar@1812
   482
athos@2102
   483
    ///This function splits an edge. First a new node \c b is added to
athos@2102
   484
    ///the graph, then the original edge is re-targeted to \c
athos@2102
   485
    ///b. Finally an edge from \c b to the original target is added.
athos@2102
   486
    ///\return The newly created node.  
athos@2102
   487
    ///\warning This functionality
athos@2102
   488
    ///cannot be used together with the Snapshot feature.
deba@2114
   489
    Node split(Edge e) {
alpar@1812
   490
      Node b = addNode();
alpar@1812
   491
      addEdge(b,target(e));
alpar@1812
   492
      changeTarget(e,b);
alpar@1812
   493
      return b;
alpar@1812
   494
    }
alpar@1812
   495
      
deba@2114
   496
    /// \brief Class to make a snapshot of the graph and restore
deba@2114
   497
    /// to it later.
alpar@1011
   498
    ///
deba@2114
   499
    /// Class to make a snapshot of the graph and to restore it
deba@2114
   500
    /// later.
alpar@1011
   501
    ///
deba@2114
   502
    /// The newly added nodes and edges can be removed using the
deba@2114
   503
    /// restore() function.
deba@2114
   504
    ///
deba@2114
   505
    /// \warning Edge and node deletions cannot be restored.
deba@2114
   506
    class Snapshot {
deba@1774
   507
    public:
deba@1774
   508
      
deba@1774
   509
      class UnsupportedOperation : public LogicError {
deba@1774
   510
      public:
deba@1774
   511
	virtual const char* exceptionName() const {
deba@1774
   512
	  return "lemon::ListGraph::Snapshot::UnsupportedOperation";
deba@1774
   513
	}
deba@1774
   514
      };
deba@1774
   515
            
deba@1774
   516
deba@1999
   517
    protected:
deba@2114
   518
deba@2114
   519
      typedef Parent::NodeNotifier NodeNotifier;
deba@2114
   520
deba@2114
   521
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2114
   522
      public:
deba@2114
   523
deba@2114
   524
        NodeObserverProxy(Snapshot& _snapshot)
deba@2114
   525
          : snapshot(_snapshot) {}
deba@2114
   526
deba@2114
   527
        using NodeNotifier::ObserverBase::attach;
deba@2114
   528
        using NodeNotifier::ObserverBase::detach;
deba@2114
   529
        using NodeNotifier::ObserverBase::attached;
deba@2114
   530
        
deba@2114
   531
      protected:
deba@2114
   532
        
deba@2114
   533
        virtual void add(const Node& node) {
deba@2114
   534
          snapshot.addNode(node);
deba@2114
   535
        }
deba@2114
   536
        virtual void add(const std::vector<Node>& nodes) {
deba@2114
   537
          for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2114
   538
            snapshot.addNode(nodes[i]);
deba@2114
   539
          }
deba@2114
   540
        }
deba@2114
   541
        virtual void erase(const Node& node) {
deba@2114
   542
          snapshot.eraseNode(node);
deba@2114
   543
        }
deba@2114
   544
        virtual void erase(const std::vector<Node>& nodes) {
deba@2114
   545
          for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2114
   546
            if (!snapshot.eraseNode(nodes[i])) break;
deba@2114
   547
          }
deba@2114
   548
        }
deba@2114
   549
        virtual void build() {
deba@2114
   550
          NodeNotifier* notifier = getNotifier();
deba@2114
   551
          Node node;
deba@2114
   552
          std::vector<Node> nodes;
deba@2114
   553
          for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2114
   554
            nodes.push_back(node);
deba@2114
   555
          }
deba@2114
   556
          for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2114
   557
            snapshot.addNode(nodes[i]);
deba@2114
   558
          }
deba@2114
   559
        }
deba@2114
   560
        virtual void clear() {
deba@2114
   561
          NodeNotifier* notifier = getNotifier();
deba@2114
   562
          Node node;
deba@2114
   563
          for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2114
   564
            if (!snapshot.eraseNode(node)) break;
deba@2114
   565
          }
deba@2114
   566
        }
deba@2114
   567
deba@2114
   568
        Snapshot& snapshot;
deba@2114
   569
      };
deba@2114
   570
deba@2114
   571
      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@2114
   572
      public:
deba@2114
   573
deba@2114
   574
        EdgeObserverProxy(Snapshot& _snapshot)
deba@2114
   575
          : snapshot(_snapshot) {}
deba@2114
   576
deba@2114
   577
        using EdgeNotifier::ObserverBase::attach;
deba@2114
   578
        using EdgeNotifier::ObserverBase::detach;
deba@2114
   579
        using EdgeNotifier::ObserverBase::attached;
deba@2114
   580
        
deba@2114
   581
      protected:
deba@2114
   582
deba@2114
   583
        virtual void add(const Edge& edge) {
deba@2114
   584
          snapshot.addEdge(edge);
deba@2114
   585
        }
deba@2114
   586
        virtual void add(const std::vector<Edge>& edges) {
deba@2114
   587
          for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2114
   588
            snapshot.addEdge(edges[i]);
deba@2114
   589
          }
deba@2114
   590
        }
deba@2114
   591
        virtual void erase(const Edge& edge) {
deba@2114
   592
          snapshot.eraseEdge(edge);
deba@2114
   593
        }
deba@2114
   594
        virtual void erase(const std::vector<Edge>& edges) {
deba@2114
   595
          for (int i = 0; i < (int)edges.size(); ++i) {
deba@2114
   596
            if (!snapshot.eraseEdge(edges[i])) break;
deba@2114
   597
          }
deba@2114
   598
        }
deba@2114
   599
        virtual void build() {
deba@2114
   600
          EdgeNotifier* notifier = getNotifier();
deba@2114
   601
          Edge edge;
deba@2114
   602
          std::vector<Edge> edges;
deba@2114
   603
          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2114
   604
            edges.push_back(edge);
deba@2114
   605
          }
deba@2114
   606
          for (int i = edges.size() - 1; i >= 0; --i) {
deba@2114
   607
            snapshot.addEdge(edges[i]);
deba@2114
   608
          }
deba@2114
   609
        }
deba@2114
   610
        virtual void clear() {
deba@2114
   611
          EdgeNotifier* notifier = getNotifier();
deba@2114
   612
          Edge edge;
deba@2114
   613
          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2114
   614
            if (!snapshot.eraseEdge(edge)) break;
deba@2114
   615
          }
deba@2114
   616
        }
deba@2114
   617
deba@2114
   618
        Snapshot& snapshot;
deba@2114
   619
      };
alpar@1011
   620
      
deba@2114
   621
      ListGraph *graph;
deba@2114
   622
deba@2114
   623
      NodeObserverProxy node_observer_proxy;
deba@2114
   624
      EdgeObserverProxy edge_observer_proxy;
deba@2114
   625
alpar@1011
   626
      std::list<Node> added_nodes;
alpar@1011
   627
      std::list<Edge> added_edges;
deba@2114
   628
deba@2114
   629
deba@2114
   630
      void addNode(const Node& node) {
deba@2114
   631
        added_nodes.push_front(node);        
alpar@1011
   632
      }
deba@2114
   633
      bool eraseNode(const Node& node) {
deba@2114
   634
        std::list<Node>::iterator it = 
deba@2114
   635
          std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2114
   636
        if (it == added_nodes.end()) {
deba@2114
   637
          clear();
deba@2114
   638
          return false;
deba@2114
   639
        } else {
deba@2114
   640
          added_nodes.erase(it);
deba@2114
   641
          return true;
deba@2114
   642
        }
alpar@1011
   643
      }
alpar@1011
   644
deba@2114
   645
      void addEdge(const Edge& edge) {
deba@2114
   646
        added_edges.push_front(edge);        
deba@2114
   647
      }
deba@2114
   648
      bool eraseEdge(const Edge& edge) {
deba@2114
   649
        std::list<Edge>::iterator it = 
deba@2114
   650
          std::find(added_edges.begin(), added_edges.end(), edge);
deba@2114
   651
        if (it == added_edges.end()) {
deba@2114
   652
          clear();
deba@2114
   653
          return false;
deba@2114
   654
        } else {
deba@2114
   655
          added_edges.erase(it);
deba@2114
   656
          return true;
deba@2114
   657
        }        
deba@2114
   658
      }
alpar@1457
   659
deba@2114
   660
      void attach(ListGraph &_graph) {
deba@2114
   661
	graph = &_graph;
deba@2114
   662
	node_observer_proxy.attach(graph->getNotifier(Node()));
deba@2114
   663
        edge_observer_proxy.attach(graph->getNotifier(Edge()));
alpar@1011
   664
      }
alpar@1011
   665
            
deba@2114
   666
      void detach() {
deba@2114
   667
	node_observer_proxy.detach();
deba@2114
   668
	edge_observer_proxy.detach();
deba@2114
   669
      }
deba@2114
   670
deba@2114
   671
      void clear() {
deba@2114
   672
        detach();
deba@2114
   673
        added_nodes.clear();
deba@2114
   674
        added_edges.clear();        
alpar@1011
   675
      }
deba@1774
   676
alpar@1011
   677
    public:
deba@2114
   678
deba@2114
   679
      /// \brief Default constructur.
deba@2114
   680
      ///
deba@2114
   681
      /// Default constructor.
deba@2114
   682
      /// To actually make a snapshot you must call save().
deba@2114
   683
      Snapshot() 
deba@2114
   684
        : graph(0), node_observer_proxy(*this), 
deba@2114
   685
          edge_observer_proxy(*this) {}
alpar@1011
   686
      
deba@2114
   687
      /// \brief Constructor that immediately makes a snapshot.
deba@2114
   688
      ///      
deba@2114
   689
      /// This constructor immediately makes a snapshot of the graph.
deba@2114
   690
      /// \param _graph The graph we make a snapshot of.
deba@2114
   691
      Snapshot(ListGraph &_graph) 
deba@2114
   692
        : node_observer_proxy(*this), 
deba@2114
   693
          edge_observer_proxy(*this) {
deba@2114
   694
	attach(_graph);
alpar@1011
   695
      }
alpar@1011
   696
      
deba@2114
   697
      /// \brief Make a snapshot.
alpar@1011
   698
      ///
deba@2114
   699
      /// Make a snapshot of the graph.
deba@2114
   700
      ///
deba@2114
   701
      /// This function can be called more than once. In case of a repeated
deba@2114
   702
      /// call, the previous snapshot gets lost.
deba@2114
   703
      /// \param _graph The graph we make the snapshot of.
deba@2114
   704
      void save(ListGraph &_graph) {
deba@2114
   705
        clear();
deba@2114
   706
        attach(_graph);
alpar@1011
   707
      }
alpar@1011
   708
      
deba@2114
   709
      /// \brief Undo the changes until the last snapshot.
deba@2114
   710
      // 
alpar@2123
   711
      /// Undo the changes until the last snapshot created by save().
alpar@1011
   712
      void restore() {
deba@2114
   713
	detach();
alpar@1011
   714
	while(!added_edges.empty()) {
deba@2114
   715
	  graph->erase(added_edges.front());
alpar@1011
   716
	  added_edges.pop_front();
alpar@1011
   717
	}
alpar@1011
   718
 	while(!added_nodes.empty()) {
deba@2114
   719
	  graph->erase(added_nodes.front());
alpar@1011
   720
	  added_nodes.pop_front();
alpar@1011
   721
	}
alpar@1011
   722
      }
deba@2114
   723
deba@2114
   724
      /// \brief Gives back true when the snapshot is valid.
deba@2114
   725
      ///
deba@2114
   726
      /// Gives back true when the snapshot is valid.
deba@2114
   727
      bool valid() const {
deba@2114
   728
        return node_observer_proxy.attached();
deba@2114
   729
      }
alpar@1011
   730
    };
alpar@1011
   731
    
alpar@949
   732
  };
klao@1034
   733
deba@2116
   734
  ///@}
deba@2116
   735
deba@2116
   736
  /**************** Undirected List Graph ****************/
deba@2116
   737
deba@2116
   738
  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
deba@2116
   739
  ExtendedListUGraphBase;
deba@2116
   740
deba@2116
   741
  /// \addtogroup graphs
deba@2116
   742
  /// @{
deba@2116
   743
deba@2116
   744
  ///An undirected list graph class.
deba@2116
   745
alpar@2117
   746
  ///This is a simple and fast undirected graph implementation.
deba@2116
   747
  ///
deba@2116
   748
  ///It conforms to the
alpar@2117
   749
  ///\ref concept::UGraph "UGraph concept".
deba@2116
   750
  ///
deba@2116
   751
  ///\sa concept::UGraph.
deba@2116
   752
  ///
deba@2116
   753
  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
deba@2116
   754
  ///haven't been implemented yet.
deba@2116
   755
  ///
deba@2116
   756
  class ListUGraph : public ExtendedListUGraphBase {
alpar@2128
   757
  private:
alpar@2128
   758
    ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128
   759
alpar@2128
   760
    ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128
   761
    ///
alpar@2128
   762
    ListUGraph(const ListUGraph &) :ExtendedListUGraphBase()  {};
alpar@2132
   763
    ///\brief Assignment of ListUGraph to another one is \e not allowed.
alpar@2128
   764
    ///Use UGraphCopy() instead.
alpar@2128
   765
alpar@2132
   766
    ///Assignment of ListUGraph to another one is \e not allowed.
alpar@2128
   767
    ///Use UGraphCopy() instead.
alpar@2128
   768
    void operator=(const ListUGraph &) {}
deba@2116
   769
  public:
alpar@2128
   770
    /// Constructor
alpar@2128
   771
    
alpar@2128
   772
    /// Constructor.
alpar@2128
   773
    ///
alpar@2128
   774
    ListUGraph() {}
alpar@2128
   775
deba@2116
   776
    typedef ExtendedListUGraphBase Parent;
deba@2116
   777
    /// \brief Add a new node to the graph.
deba@2116
   778
    ///
deba@2116
   779
    /// \return the new node.
deba@2116
   780
    ///
deba@2116
   781
    Node addNode() { return Parent::addNode(); }
deba@2116
   782
deba@2116
   783
    /// \brief Add a new edge to the graph.
deba@2116
   784
    ///
deba@2116
   785
    /// Add a new edge to the graph with source node \c s
deba@2116
   786
    /// and target node \c t.
deba@2116
   787
    /// \return the new undirected edge.
deba@2116
   788
    UEdge addEdge(const Node& s, const Node& t) { 
deba@2116
   789
      return Parent::addEdge(s, t); 
deba@2116
   790
    }
deba@2116
   791
    /// \brief Changes the target of \c e to \c n
deba@2116
   792
    ///
deba@2116
   793
    /// Changes the target of \c e to \c n
deba@2116
   794
    ///
deba@2116
   795
    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
deba@2116
   796
    /// referencing the changed edge remain
deba@2116
   797
    /// valid. However <tt>InEdge</tt>'s are invalidated.
deba@2116
   798
    void changeTarget(UEdge e, Node n) { 
deba@2116
   799
      Parent::changeTarget(e,n); 
deba@2116
   800
    }
deba@2116
   801
    /// Changes the source of \c e to \c n
deba@2116
   802
    ///
deba@2116
   803
    /// Changes the source of \c e to \c n
deba@2116
   804
    ///
deba@2116
   805
    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
deba@2116
   806
    ///referencing the changed edge remain
deba@2116
   807
    ///valid. However <tt>OutEdge</tt>'s are invalidated.
deba@2116
   808
    void changeSource(UEdge e, Node n) { 
deba@2116
   809
      Parent::changeSource(e,n); 
deba@2116
   810
    }
deba@2116
   811
    /// \brief Contract two nodes.
deba@2116
   812
    ///
deba@2116
   813
    /// This function contracts two nodes.
deba@2116
   814
    ///
deba@2116
   815
    /// Node \p b will be removed but instead of deleting
deba@2116
   816
    /// its neighboring edges, they will be joined to \p a.
deba@2116
   817
    /// The last parameter \p r controls whether to remove loops. \c true
deba@2116
   818
    /// means that loops will be removed.
deba@2116
   819
    ///
deba@2116
   820
    /// \note The <tt>Edge</tt>s
deba@2116
   821
    /// referencing a moved edge remain
deba@2116
   822
    /// valid.
deba@2116
   823
    void contract(Node a, Node b, bool r = true) {
deba@2116
   824
      for(IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2116
   825
	IncEdgeIt f = e; ++f;
deba@2116
   826
	if (r && runningNode(e) == a) {
deba@2116
   827
	  erase(e);
deba@2116
   828
	} else if (source(e) == b) {
deba@2116
   829
	  changeSource(e, a);
deba@2116
   830
	} else {
deba@2116
   831
	  changeTarget(e, a);
deba@2116
   832
	}
deba@2116
   833
	e = f;
deba@2116
   834
      }
deba@2116
   835
      erase(b);
deba@2116
   836
    }
deba@2116
   837
  };
deba@2116
   838
deba@2116
   839
deba@2116
   840
  class ListBpUGraphBase {
deba@2116
   841
  public:
deba@2116
   842
deba@2116
   843
    class NodeSetError : public LogicError {
deba@2116
   844
      virtual const char* exceptionName() const { 
deba@2116
   845
	return "lemon::ListBpUGraph::NodeSetError";
deba@2116
   846
      }
deba@2116
   847
    };
deba@2116
   848
deba@2116
   849
  protected:
deba@2116
   850
deba@2116
   851
    struct NodeT {
deba@2116
   852
      int first_edge, prev, next;
deba@2116
   853
    };
deba@2116
   854
deba@2116
   855
    struct UEdgeT {
deba@2116
   856
      int aNode, prev_out, next_out;
deba@2116
   857
      int bNode, prev_in, next_in;
deba@2116
   858
    };
deba@2116
   859
deba@2116
   860
    std::vector<NodeT> aNodes;
deba@2116
   861
    std::vector<NodeT> bNodes;
deba@2116
   862
deba@2116
   863
    std::vector<UEdgeT> edges;
deba@2116
   864
deba@2116
   865
    int first_anode;
deba@2116
   866
    int first_free_anode;
deba@2116
   867
deba@2116
   868
    int first_bnode;
deba@2116
   869
    int first_free_bnode;
deba@2116
   870
deba@2116
   871
    int first_free_edge;
deba@2116
   872
deba@2116
   873
  public:
deba@2116
   874
  
deba@2116
   875
    class Node {
deba@2116
   876
      friend class ListBpUGraphBase;
deba@2116
   877
    protected:
deba@2116
   878
      int id;
deba@2116
   879
deba@2116
   880
      explicit Node(int _id) : id(_id) {}
deba@2116
   881
    public:
deba@2116
   882
      Node() {}
deba@2116
   883
      Node(Invalid) { id = -1; }
deba@2116
   884
      bool operator==(const Node i) const {return id==i.id;}
deba@2116
   885
      bool operator!=(const Node i) const {return id!=i.id;}
deba@2116
   886
      bool operator<(const Node i) const {return id<i.id;}
deba@2116
   887
    };
deba@2116
   888
deba@2116
   889
    class UEdge {
deba@2116
   890
      friend class ListBpUGraphBase;
deba@2116
   891
    protected:
deba@2116
   892
      int id;
deba@2116
   893
deba@2116
   894
      explicit UEdge(int _id) { id = _id;}
deba@2116
   895
    public:
deba@2116
   896
      UEdge() {}
deba@2116
   897
      UEdge (Invalid) { id = -1; }
deba@2116
   898
      bool operator==(const UEdge i) const {return id==i.id;}
deba@2116
   899
      bool operator!=(const UEdge i) const {return id!=i.id;}
deba@2116
   900
      bool operator<(const UEdge i) const {return id<i.id;}
deba@2116
   901
    };
deba@2116
   902
deba@2116
   903
    ListBpUGraphBase()
deba@2116
   904
      : first_anode(-1), first_free_anode(-1),
deba@2116
   905
        first_bnode(-1), first_free_bnode(-1),
deba@2116
   906
        first_free_edge(-1) {}
deba@2116
   907
deba@2116
   908
    void firstANode(Node& node) const {
deba@2116
   909
      node.id = first_anode != -1 ? (first_anode << 1) : -1;
deba@2116
   910
    }
deba@2116
   911
    void nextANode(Node& node) const {
deba@2116
   912
      node.id = aNodes[node.id >> 1].next;
deba@2116
   913
    }
deba@2116
   914
deba@2116
   915
    void firstBNode(Node& node) const {
deba@2116
   916
      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
deba@2116
   917
    }
deba@2116
   918
    void nextBNode(Node& node) const {
deba@2116
   919
      node.id = bNodes[node.id >> 1].next;
deba@2116
   920
    }
deba@2116
   921
deba@2116
   922
    void first(Node& node) const {
deba@2116
   923
      if (first_anode != -1) {
deba@2116
   924
        node.id = (first_anode << 1);
deba@2116
   925
      } else if (first_bnode != -1) {
deba@2116
   926
        node.id = (first_bnode << 1) + 1;
deba@2116
   927
      } else {
deba@2116
   928
        node.id = -1;
deba@2116
   929
      }
deba@2116
   930
    }
deba@2116
   931
    void next(Node& node) const {
deba@2116
   932
      if (aNode(node)) {
deba@2116
   933
        node.id = aNodes[node.id >> 1].next;
deba@2116
   934
        if (node.id == -1) {
deba@2116
   935
          if (first_bnode != -1) {
deba@2116
   936
            node.id = (first_bnode << 1) + 1;
deba@2116
   937
          }
deba@2116
   938
        }
deba@2116
   939
      } else {
deba@2116
   940
        node.id = bNodes[node.id >> 1].next;
deba@2116
   941
      }
deba@2116
   942
    }
deba@2116
   943
  
deba@2116
   944
    void first(UEdge& edge) const {
deba@2116
   945
      int aNodeId = first_anode;
deba@2116
   946
      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
deba@2116
   947
        aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116
   948
          aNodes[aNodeId].next >> 1 : -1;
deba@2116
   949
      }
deba@2116
   950
      if (aNodeId != -1) {
deba@2116
   951
        edge.id = aNodes[aNodeId].first_edge;
deba@2116
   952
      } else {
deba@2116
   953
        edge.id = -1;
deba@2116
   954
      }
deba@2116
   955
    }
deba@2116
   956
    void next(UEdge& edge) const {
deba@2116
   957
      int aNodeId = edges[edge.id].aNode >> 1;
deba@2116
   958
      edge.id = edges[edge.id].next_out;
deba@2116
   959
      if (edge.id == -1) {
deba@2116
   960
        aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116
   961
          aNodes[aNodeId].next >> 1 : -1;
deba@2116
   962
        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
deba@2116
   963
          aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116
   964
          aNodes[aNodeId].next >> 1 : -1;
deba@2116
   965
        }
deba@2116
   966
        if (aNodeId != -1) {
deba@2116
   967
          edge.id = aNodes[aNodeId].first_edge;
deba@2116
   968
        } else {
deba@2116
   969
          edge.id = -1;
deba@2116
   970
        }
deba@2116
   971
      }
deba@2116
   972
    }
deba@2116
   973
deba@2116
   974
    void firstFromANode(UEdge& edge, const Node& node) const {
deba@2116
   975
      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
deba@2116
   976
      edge.id = aNodes[node.id >> 1].first_edge;
deba@2116
   977
    }
deba@2116
   978
    void nextFromANode(UEdge& edge) const {
deba@2116
   979
      edge.id = edges[edge.id].next_out;
deba@2116
   980
    }
deba@2116
   981
deba@2116
   982
    void firstFromBNode(UEdge& edge, const Node& node) const {
deba@2116
   983
      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
deba@2116
   984
      edge.id = bNodes[node.id >> 1].first_edge;
deba@2116
   985
    }
deba@2116
   986
    void nextFromBNode(UEdge& edge) const {
deba@2116
   987
      edge.id = edges[edge.id].next_in;
deba@2116
   988
    }
deba@2116
   989
deba@2116
   990
    static int id(const Node& node) {
deba@2116
   991
      return node.id;
deba@2116
   992
    }
deba@2116
   993
    static Node nodeFromId(int id) {
deba@2116
   994
      return Node(id);
deba@2116
   995
    }
deba@2116
   996
    int maxNodeId() const {
deba@2116
   997
      return aNodes.size() > bNodes.size() ?
deba@2116
   998
	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
deba@2116
   999
    }
deba@2116
  1000
  
deba@2116
  1001
    static int id(const UEdge& edge) {
deba@2116
  1002
      return edge.id;
deba@2116
  1003
    }
deba@2116
  1004
    static UEdge uEdgeFromId(int id) {
deba@2116
  1005
      return UEdge(id);
deba@2116
  1006
    }
deba@2116
  1007
    int maxUEdgeId() const {
deba@2116
  1008
      return edges.size();
deba@2116
  1009
    }
deba@2116
  1010
  
deba@2116
  1011
    static int aNodeId(const Node& node) {
deba@2116
  1012
      return node.id >> 1;
deba@2116
  1013
    }
deba@2116
  1014
    static Node fromANodeId(int id) {
deba@2116
  1015
      return Node(id << 1);
deba@2116
  1016
    }
deba@2116
  1017
    int maxANodeId() const {
deba@2116
  1018
      return aNodes.size();
deba@2116
  1019
    }
deba@2116
  1020
deba@2116
  1021
    static int bNodeId(const Node& node) {
deba@2116
  1022
      return node.id >> 1;
deba@2116
  1023
    }
deba@2116
  1024
    static Node fromBNodeId(int id) {
deba@2116
  1025
      return Node((id << 1) + 1);
deba@2116
  1026
    }
deba@2116
  1027
    int maxBNodeId() const {
deba@2116
  1028
      return bNodes.size();
deba@2116
  1029
    }
deba@2116
  1030
deba@2116
  1031
    Node aNode(const UEdge& edge) const {
deba@2116
  1032
      return Node(edges[edge.id].aNode);
deba@2116
  1033
    }
deba@2116
  1034
    Node bNode(const UEdge& edge) const {
deba@2116
  1035
      return Node(edges[edge.id].bNode);
deba@2116
  1036
    }
deba@2116
  1037
deba@2116
  1038
    static bool aNode(const Node& node) {
deba@2116
  1039
      return (node.id & 1) == 0;
deba@2116
  1040
    }
deba@2116
  1041
deba@2116
  1042
    static bool bNode(const Node& node) {
deba@2116
  1043
      return (node.id & 1) == 1;
deba@2116
  1044
    }
deba@2116
  1045
deba@2116
  1046
    Node addANode() {
deba@2116
  1047
      int aNodeId;
deba@2116
  1048
      if (first_free_anode == -1) {
deba@2116
  1049
        aNodeId = aNodes.size();
deba@2116
  1050
        aNodes.push_back(NodeT());
deba@2116
  1051
      } else {
deba@2116
  1052
        aNodeId = first_free_anode;
deba@2116
  1053
        first_free_anode = aNodes[first_free_anode].next;
deba@2116
  1054
      }
deba@2116
  1055
      if (first_anode != -1) {
deba@2116
  1056
        aNodes[aNodeId].next = first_anode << 1;
deba@2116
  1057
        aNodes[first_anode].prev = aNodeId << 1;
deba@2116
  1058
      } else {
deba@2116
  1059
        aNodes[aNodeId].next = -1;
deba@2116
  1060
      }
deba@2116
  1061
      aNodes[aNodeId].prev = -1;
deba@2116
  1062
      first_anode = aNodeId;
deba@2116
  1063
      aNodes[aNodeId].first_edge = -1;
deba@2116
  1064
      return Node(aNodeId << 1);
deba@2116
  1065
    }
deba@2116
  1066
deba@2116
  1067
    Node addBNode() {
deba@2116
  1068
      int bNodeId;
deba@2116
  1069
      if (first_free_bnode == -1) {
deba@2116
  1070
        bNodeId = bNodes.size();
deba@2116
  1071
        bNodes.push_back(NodeT());
deba@2116
  1072
      } else {
deba@2116
  1073
        bNodeId = first_free_bnode;
deba@2116
  1074
        first_free_bnode = bNodes[first_free_bnode].next;
deba@2116
  1075
      }
deba@2116
  1076
      if (first_bnode != -1) {
deba@2116
  1077
        bNodes[bNodeId].next = (first_bnode << 1) + 1;
deba@2116
  1078
        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
deba@2116
  1079
      } else {
deba@2116
  1080
        bNodes[bNodeId].next = -1;
deba@2116
  1081
      }
deba@2116
  1082
      first_bnode = bNodeId;
deba@2116
  1083
      bNodes[bNodeId].first_edge = -1;
deba@2116
  1084
      return Node((bNodeId << 1) + 1);
deba@2116
  1085
    }
deba@2116
  1086
deba@2116
  1087
    UEdge addEdge(const Node& source, const Node& target) {
deba@2116
  1088
      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
deba@2116
  1089
      int edgeId;
deba@2116
  1090
      if (first_free_edge != -1) {
deba@2116
  1091
        edgeId = first_free_edge;
deba@2116
  1092
        first_free_edge = edges[edgeId].next_out;
deba@2116
  1093
      } else {
deba@2116
  1094
        edgeId = edges.size();
deba@2116
  1095
        edges.push_back(UEdgeT());
deba@2116
  1096
      }
deba@2116
  1097
      if ((source.id & 1) == 0) {
deba@2116
  1098
	edges[edgeId].aNode = source.id;
deba@2116
  1099
	edges[edgeId].bNode = target.id;
deba@2116
  1100
      } else {
deba@2116
  1101
	edges[edgeId].aNode = target.id;
deba@2116
  1102
	edges[edgeId].bNode = source.id;
deba@2116
  1103
      }
deba@2116
  1104
      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
deba@2116
  1105
      edges[edgeId].prev_out = -1;
deba@2116
  1106
      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
deba@2116
  1107
        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
deba@2116
  1108
      }
deba@2116
  1109
      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
deba@2116
  1110
      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
deba@2116
  1111
      edges[edgeId].prev_in = -1;
deba@2116
  1112
      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
deba@2116
  1113
        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
deba@2116
  1114
      }
deba@2116
  1115
      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
deba@2116
  1116
      return UEdge(edgeId);
deba@2116
  1117
    }
deba@2116
  1118
deba@2116
  1119
    void erase(const Node& node) {
deba@2116
  1120
      if (aNode(node)) {
deba@2116
  1121
        int aNodeId = node.id >> 1;
deba@2116
  1122
        if (aNodes[aNodeId].prev != -1) {
deba@2116
  1123
          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
deba@2116
  1124
        } else {
deba@2116
  1125
          first_anode = aNodes[aNodeId].next >> 1;
deba@2116
  1126
        }
deba@2116
  1127
        if (aNodes[aNodeId].next != -1) {
deba@2116
  1128
          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
deba@2116
  1129
        }
deba@2116
  1130
        aNodes[aNodeId].next = first_free_anode;
deba@2116
  1131
        first_free_anode = aNodeId;
deba@2116
  1132
      } else {
deba@2116
  1133
        int bNodeId = node.id >> 1;
deba@2116
  1134
        if (bNodes[bNodeId].prev != -1) {
deba@2116
  1135
          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
deba@2116
  1136
        } else {
deba@2116
  1137
          first_bnode = bNodes[bNodeId].next >> 1;
deba@2116
  1138
        }
deba@2116
  1139
        if (bNodes[bNodeId].next != -1) {
deba@2116
  1140
          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
deba@2116
  1141
        }
deba@2116
  1142
        bNodes[bNodeId].next = first_free_bnode;
deba@2116
  1143
        first_free_bnode = bNodeId;
deba@2116
  1144
      }
deba@2116
  1145
    }
deba@2116
  1146
deba@2116
  1147
    void erase(const UEdge& edge) {
deba@2116
  1148
deba@2116
  1149
      if (edges[edge.id].prev_out != -1) {
deba@2116
  1150
        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
deba@2116
  1151
      } else {
deba@2116
  1152
        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
deba@2116
  1153
      }
deba@2116
  1154
      if (edges[edge.id].next_out != -1) {
deba@2116
  1155
        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
deba@2116
  1156
      }
deba@2116
  1157
deba@2116
  1158
      if (edges[edge.id].prev_in != -1) {
deba@2116
  1159
        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
deba@2116
  1160
      } else {
deba@2116
  1161
        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
deba@2116
  1162
      }
deba@2116
  1163
      if (edges[edge.id].next_in != -1) {
deba@2116
  1164
        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
deba@2116
  1165
      }
deba@2116
  1166
deba@2116
  1167
      edges[edge.id].next_out = first_free_edge;
deba@2116
  1168
      first_free_edge = edge.id;
deba@2116
  1169
    }
alpar@2128
  1170
 
alpar@2128
  1171
    ///\e
alpar@2128
  1172
    
alpar@2128
  1173
    ///\bug Undocumented
alpar@2128
  1174
    ///\bug Doesn't destruct the maps.
deba@2116
  1175
    void clear() {
deba@2116
  1176
      aNodes.clear();
deba@2116
  1177
      bNodes.clear();
deba@2116
  1178
      edges.clear();
deba@2116
  1179
      first_anode = -1;
deba@2116
  1180
      first_free_anode = -1;
deba@2116
  1181
      first_bnode = -1;
deba@2116
  1182
      first_free_bnode = -1;
deba@2116
  1183
      first_free_edge = -1;
deba@2116
  1184
    }
deba@2116
  1185
deba@2116
  1186
  };
deba@2116
  1187
deba@2116
  1188
deba@2116
  1189
  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
deba@2116
  1190
deba@2116
  1191
  /// \ingroup graphs
deba@2116
  1192
  ///
deba@2116
  1193
  /// \brief A smart bipartite undirected graph class.
deba@2116
  1194
  ///
deba@2116
  1195
  /// This is a bipartite undirected graph implementation.
alpar@2117
  1196
  /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
deba@2116
  1197
  /// \sa concept::BpUGraph.
deba@2116
  1198
  ///
deba@2116
  1199
  class ListBpUGraph : public ExtendedListBpUGraphBase {};
deba@2116
  1200
deba@2116
  1201
  
deba@2116
  1202
  /// @}  
alpar@948
  1203
} //namespace lemon
klao@946
  1204
  
alpar@400
  1205
klao@946
  1206
#endif