lemon/smart_graph.h
author alpar
Wed, 05 Jul 2006 16:59:45 +0000
changeset 2120 a907fb95f1e0
parent 2115 4cd528a30ec1
child 2123 85c6f5e82108
permissions -rw-r--r--
As we agreed, Node/Edge::operator<() is required by the concept
alpar@906
     1
/* -*- C++ -*-
alpar@906
     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@906
     8
 *
alpar@906
     9
 * Permission to use, modify and distribute this software is granted
alpar@906
    10
 * provided that this copyright notice appears in all copies. For
alpar@906
    11
 * precise terms see the accompanying LICENSE file.
alpar@906
    12
 *
alpar@906
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    14
 * express or implied, and with no claim as to its suitability for any
alpar@906
    15
 * purpose.
alpar@906
    16
 *
alpar@906
    17
 */
alpar@105
    18
alpar@921
    19
#ifndef LEMON_SMART_GRAPH_H
alpar@921
    20
#define LEMON_SMART_GRAPH_H
alpar@104
    21
klao@491
    22
///\ingroup graphs
alpar@242
    23
///\file
deba@2116
    24
///\brief SmartGraph and SmartUGraph classes.
alpar@242
    25
alpar@104
    26
#include <vector>
alpar@104
    27
deba@1993
    28
#include <lemon/bits/invalid.h>
alpar@157
    29
deba@2116
    30
#include <lemon/bits/base_extender.h>
deba@1791
    31
#include <lemon/bits/graph_extender.h>
klao@1034
    32
deba@1993
    33
#include <lemon/bits/utility.h>
deba@2116
    34
#include <lemon/error.h>
deba@782
    35
deba@1979
    36
#include <lemon/bits/graph_extender.h>
deba@1979
    37
alpar@921
    38
namespace lemon {
alpar@104
    39
alpar@973
    40
  class SmartGraph;
alpar@969
    41
  ///Base of SmartGraph
alpar@969
    42
alpar@969
    43
  ///Base of SmartGraph
alpar@969
    44
  ///
klao@946
    45
  class SmartGraphBase {
alpar@104
    46
alpar@973
    47
    friend class SmatGraph;
alpar@973
    48
alpar@973
    49
  protected:
alpar@104
    50
    struct NodeT 
alpar@104
    51
    {
alpar@104
    52
      int first_in,first_out;      
alpar@157
    53
      NodeT() : first_in(-1), first_out(-1) {}
alpar@104
    54
    };
alpar@104
    55
    struct EdgeT 
alpar@104
    56
    {
alpar@986
    57
      int target, source, next_in, next_out;      
alpar@104
    58
      //FIXME: is this necessary?
alpar@157
    59
      EdgeT() : next_in(-1), next_out(-1) {}  
alpar@104
    60
    };
alpar@104
    61
alpar@104
    62
    std::vector<NodeT> nodes;
alpar@129
    63
alpar@104
    64
    std::vector<EdgeT> edges;
alpar@104
    65
    
alpar@185
    66
    
alpar@104
    67
  public:
deba@782
    68
klao@946
    69
    typedef SmartGraphBase Graph;
alpar@104
    70
alpar@164
    71
    class Node;
alpar@164
    72
    class Edge;
alpar@108
    73
alpar@104
    74
    
alpar@104
    75
  public:
alpar@104
    76
klao@946
    77
    SmartGraphBase() : nodes(), edges() { }
deba@1718
    78
    SmartGraphBase(const SmartGraphBase &_g) 
deba@1718
    79
      : nodes(_g.nodes), edges(_g.edges) { }
alpar@104
    80
    
klao@977
    81
    typedef True NodeNumTag;
klao@977
    82
    typedef True EdgeNumTag;
klao@977
    83
alpar@813
    84
    ///Number of nodes.
alpar@813
    85
    int nodeNum() const { return nodes.size(); }
alpar@813
    86
    ///Number of edges.
alpar@813
    87
    int edgeNum() const { return edges.size(); }
alpar@104
    88
alpar@813
    89
    /// Maximum node ID.
alpar@813
    90
    
alpar@813
    91
    /// Maximum node ID.
alpar@813
    92
    ///\sa id(Node)
deba@1791
    93
    int maxNodeId() const { return nodes.size()-1; }
alpar@813
    94
    /// Maximum edge ID.
alpar@813
    95
    
alpar@813
    96
    /// Maximum edge ID.
alpar@813
    97
    ///\sa id(Edge)
deba@1791
    98
    int maxEdgeId() const { return edges.size()-1; }
alpar@108
    99
alpar@986
   100
    Node source(Edge e) const { return edges[e.n].source; }
alpar@986
   101
    Node target(Edge e) const { return edges[e.n].target; }
alpar@104
   102
alpar@813
   103
    /// Node ID.
alpar@813
   104
    
alpar@813
   105
    /// The ID of a valid Node is a nonnegative integer not greater than
deba@1791
   106
    /// \ref maxNodeId(). The range of the ID's is not surely continuous
deba@1791
   107
    /// and the greatest node ID can be actually less then \ref maxNodeId().
alpar@813
   108
    ///
alpar@813
   109
    /// The ID of the \ref INVALID node is -1.
alpar@813
   110
    ///\return The ID of the node \c v. 
alpar@713
   111
    static int id(Node v) { return v.n; }
alpar@813
   112
    /// Edge ID.
alpar@813
   113
    
alpar@813
   114
    /// The ID of a valid Edge is a nonnegative integer not greater than
deba@1791
   115
    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
deba@1791
   116
    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
alpar@813
   117
    ///
alpar@813
   118
    /// The ID of the \ref INVALID edge is -1.
alpar@813
   119
    ///\return The ID of the edge \c e. 
alpar@713
   120
    static int id(Edge e) { return e.n; }
alpar@104
   121
deba@2076
   122
    /// \brief Returns the node from its \c id.
deba@2076
   123
    ///
deba@2076
   124
    /// Returns the node from its \c id. If there is not node
deba@2076
   125
    /// with the given id the effect of the function is undefinied.
deba@1791
   126
    static Node nodeFromId(int id) { return Node(id);}
deba@1106
   127
deba@2076
   128
    /// \brief Returns the edge from its \c id.
deba@2076
   129
    ///
deba@2076
   130
    /// Returns the edge from its \c id. If there is not edge
deba@2076
   131
    /// with the given id the effect of the function is undefinied.
deba@1791
   132
    static Edge edgeFromId(int id) { return Edge(id);}
deba@1106
   133
alpar@164
   134
    Node addNode() {
alpar@164
   135
      Node n; n.n=nodes.size();
alpar@104
   136
      nodes.push_back(NodeT()); //FIXME: Hmmm...
alpar@104
   137
      return n;
alpar@104
   138
    }
alpar@108
   139
    
alpar@164
   140
    Edge addEdge(Node u, Node v) {
alpar@164
   141
      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
alpar@986
   142
      edges[e.n].source=u.n; edges[e.n].target=v.n;
alpar@104
   143
      edges[e.n].next_out=nodes[u.n].first_out;
alpar@104
   144
      edges[e.n].next_in=nodes[v.n].first_in;
alpar@104
   145
      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
alpar@108
   146
alpar@104
   147
      return e;
alpar@104
   148
    }
alpar@104
   149
deba@782
   150
    void clear() {
deba@782
   151
      edges.clear();
deba@782
   152
      nodes.clear();
deba@782
   153
    }
alpar@104
   154
klao@946
   155
alpar@164
   156
    class Node {
klao@946
   157
      friend class SmartGraphBase;
alpar@973
   158
      friend class SmartGraph;
alpar@104
   159
alpar@104
   160
    protected:
alpar@104
   161
      int n;
alpar@164
   162
      Node(int nn) {n=nn;}
alpar@104
   163
    public:
alpar@164
   164
      Node() {}
alpar@503
   165
      Node (Invalid) { n=-1; }
alpar@164
   166
      bool operator==(const Node i) const {return n==i.n;}
alpar@164
   167
      bool operator!=(const Node i) const {return n!=i.n;}
alpar@164
   168
      bool operator<(const Node i) const {return n<i.n;}
alpar@104
   169
    };
alpar@104
   170
    
alpar@104
   171
alpar@164
   172
    class Edge {
klao@946
   173
      friend class SmartGraphBase;
alpar@973
   174
      friend class SmartGraph;
alpar@185
   175
alpar@104
   176
    protected:
alpar@104
   177
      int n;
alpar@905
   178
      Edge(int nn) {n=nn;}
alpar@706
   179
    public:
alpar@164
   180
      Edge() { }
marci@174
   181
      Edge (Invalid) { n=-1; }
alpar@164
   182
      bool operator==(const Edge i) const {return n==i.n;}
alpar@164
   183
      bool operator!=(const Edge i) const {return n!=i.n;}
alpar@164
   184
      bool operator<(const Edge i) const {return n<i.n;}
klao@946
   185
    };
alpar@905
   186
klao@946
   187
    void first(Node& node) const {
klao@946
   188
      node.n = nodes.size() - 1;
klao@946
   189
    }
klao@946
   190
klao@946
   191
    static void next(Node& node) {
klao@946
   192
      --node.n;
klao@946
   193
    }
klao@946
   194
klao@946
   195
    void first(Edge& edge) const {
klao@946
   196
      edge.n = edges.size() - 1;
klao@946
   197
    }
klao@946
   198
klao@946
   199
    static void next(Edge& edge) {
klao@946
   200
      --edge.n;
klao@946
   201
    }
klao@946
   202
klao@946
   203
    void firstOut(Edge& edge, const Node& node) const {
klao@946
   204
      edge.n = nodes[node.n].first_out;
klao@946
   205
    }
klao@946
   206
klao@946
   207
    void nextOut(Edge& edge) const {
klao@946
   208
      edge.n = edges[edge.n].next_out;
klao@946
   209
    }
klao@946
   210
klao@946
   211
    void firstIn(Edge& edge, const Node& node) const {
klao@946
   212
      edge.n = nodes[node.n].first_in;
klao@946
   213
    }
alpar@104
   214
    
klao@946
   215
    void nextIn(Edge& edge) const {
klao@946
   216
      edge.n = edges[edge.n].next_in;
klao@946
   217
    }
alpar@105
   218
alpar@1284
   219
    Node _split(Node n, bool connect = true)
alpar@1284
   220
    {
alpar@1284
   221
      Node b = addNode();
alpar@1284
   222
      nodes[b.n].first_out=nodes[n.n].first_out;
alpar@1284
   223
      nodes[n.n].first_out=-1;
alpar@1284
   224
      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
alpar@1284
   225
      if(connect) addEdge(n,b);
alpar@1284
   226
      return b;
alpar@1284
   227
    }
alpar@1284
   228
alpar@104
   229
  };
alpar@185
   230
deba@1979
   231
  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
deba@937
   232
deba@1791
   233
  /// \ingroup graphs
alpar@1161
   234
alpar@950
   235
  ///A smart graph class.
deba@937
   236
alpar@950
   237
  ///This is a simple and fast graph implementation.
alpar@950
   238
  ///It is also quite memory efficient, but at the price
alpar@974
   239
  ///that <b> it does support only limited (only stack-like)
alpar@974
   240
  ///node and edge deletions</b>.
alpar@950
   241
  ///It conforms to 
deba@2111
   242
  ///the \ref concept::Graph "Graph" concept.
deba@2111
   243
  ///\sa concept::Graph.
alpar@950
   244
  ///
alpar@950
   245
  ///\author Alpar Juttner
deba@1669
   246
  class SmartGraph : public ExtendedSmartGraphBase {
alpar@969
   247
  public:
deba@1979
   248
deba@1979
   249
    typedef ExtendedSmartGraphBase Parent;
deba@1979
   250
alpar@1770
   251
    class Snapshot;
alpar@1770
   252
    friend class Snapshot;
alpar@973
   253
alpar@1011
   254
  protected:
alpar@1770
   255
    void restoreSnapshot(const Snapshot &s)
alpar@973
   256
    {
alpar@1457
   257
      while(s.edge_num<edges.size()) {
deba@1040
   258
	Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
alpar@986
   259
	nodes[edges.back().target].first_in=edges.back().next_in;
alpar@986
   260
	nodes[edges.back().source].first_out=edges.back().next_out;
alpar@973
   261
	edges.pop_back();
alpar@973
   262
      }
alpar@973
   263
      //nodes.resize(s.nodes_num);
alpar@1457
   264
      while(s.node_num<nodes.size()) {
deba@1040
   265
	Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
alpar@973
   266
	nodes.pop_back();
alpar@973
   267
      }
alpar@1011
   268
    }    
alpar@1011
   269
alpar@1011
   270
  public:
alpar@1284
   271
alpar@1284
   272
    ///Split a node.
alpar@1284
   273
    
alpar@1284
   274
    ///This function splits a node. First a new node is added to the graph,
alpar@1284
   275
    ///then the source of each outgoing edge of \c n is moved to this new node.
alpar@1284
   276
    ///If \c connect is \c true (this is the default value), then a new edge
alpar@1284
   277
    ///from \c n to the newly created node is also added.
alpar@1284
   278
    ///\return The newly created node.
alpar@1284
   279
    ///
alpar@1284
   280
    ///\note The <tt>Edge</tt>s
alpar@1284
   281
    ///referencing a moved edge remain
alpar@1284
   282
    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
alpar@1284
   283
    ///may be invalidated.
alpar@1770
   284
    ///\warning This functionality cannot be used together with the Snapshot
alpar@1284
   285
    ///feature.
alpar@1284
   286
    ///\todo It could be implemented in a bit faster way.
alpar@1284
   287
    Node split(Node n, bool connect = true) 
alpar@1284
   288
    {
deba@1718
   289
      Node b = _split(n,connect);
deba@1718
   290
      return b;
alpar@1284
   291
    }
alpar@1284
   292
  
alpar@1284
   293
alpar@1011
   294
    ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011
   295
alpar@1011
   296
    ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011
   297
    ///
alpar@1011
   298
    ///The newly added nodes and edges can be removed using the
alpar@1011
   299
    ///restore() function.
alpar@1011
   300
    ///\note After you restore a state, you cannot restore
alpar@1011
   301
    ///a later state, in other word you cannot add again the edges deleted
alpar@1770
   302
    ///by restore() using another Snapshot instance.
alpar@1011
   303
    ///
alpar@1770
   304
    class Snapshot 
alpar@1011
   305
    {
alpar@1011
   306
      SmartGraph *g;
alpar@1011
   307
    protected:
alpar@1011
   308
      friend class SmartGraph;
alpar@1011
   309
      unsigned int node_num;
alpar@1011
   310
      unsigned int edge_num;
alpar@1011
   311
    public:
zsuzska@1274
   312
      ///Default constructor.
alpar@1011
   313
      
zsuzska@1274
   314
      ///Default constructor.
alpar@1011
   315
      ///To actually make a snapshot you must call save().
alpar@1011
   316
      ///
alpar@1770
   317
      Snapshot() : g(0) {}
alpar@1011
   318
      ///Constructor that immediately makes a snapshot
alpar@1011
   319
      
alpar@1011
   320
      ///This constructor immediately makes a snapshot of the graph.
alpar@1011
   321
      ///\param _g The graph we make a snapshot of.
alpar@1770
   322
      Snapshot(SmartGraph &_g) :g(&_g) {
alpar@1011
   323
	node_num=g->nodes.size();
alpar@1011
   324
	edge_num=g->edges.size();
alpar@1011
   325
      }
alpar@1011
   326
alpar@1011
   327
      ///Make a snapshot.
alpar@1011
   328
alpar@1011
   329
      ///Make a snapshot of the graph.
alpar@1011
   330
      ///
alpar@1011
   331
      ///This function can be called more than once. In case of a repeated
alpar@1011
   332
      ///call, the previous snapshot gets lost.
alpar@1011
   333
      ///\param _g The graph we make the snapshot of.
alpar@1011
   334
      void save(SmartGraph &_g) 
alpar@1011
   335
      {
alpar@1011
   336
	g=&_g;
alpar@1011
   337
	node_num=g->nodes.size();
alpar@1011
   338
	edge_num=g->edges.size();
alpar@1011
   339
      }
alpar@1011
   340
alpar@1011
   341
      ///Undo the changes until a snapshot.
alpar@1011
   342
      
alpar@1011
   343
      ///Undo the changes until a snapshot created by save().
alpar@1011
   344
      ///
alpar@1011
   345
      ///\note After you restored a state, you cannot restore
alpar@1011
   346
      ///a later state, in other word you cannot add again the edges deleted
alpar@1011
   347
      ///by restore().
alpar@1011
   348
      ///
alpar@1011
   349
      ///\todo This function might be called undo().
alpar@1011
   350
      
alpar@1011
   351
      void restore()
alpar@1011
   352
      {
alpar@1770
   353
	g->restoreSnapshot(*this);
alpar@1011
   354
      }
alpar@1011
   355
    };
alpar@973
   356
  };
klao@1034
   357
klao@1034
   358
deba@2116
   359
  /**************** Undirected List Graph ****************/
deba@2116
   360
deba@2116
   361
  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
deba@2116
   362
  ExtendedSmartUGraphBase;
deba@2116
   363
deba@2116
   364
  /// \ingroup graphs
deba@2116
   365
  ///
deba@2116
   366
  /// \brief A smart undirected graph class.
deba@2116
   367
  ///
deba@2116
   368
  /// This is a simple and fast undirected graph implementation.
deba@2116
   369
  /// It is also quite memory efficient, but at the price
deba@2116
   370
  /// that <b> it does support only limited (only stack-like)
deba@2116
   371
  /// node and edge deletions</b>.
deba@2116
   372
  /// Except from this it conforms to 
deba@2116
   373
  /// the \ref concept::UGraph "UGraph" concept.
deba@2116
   374
  /// \sa concept::UGraph.
deba@2116
   375
  ///
deba@2116
   376
  /// \todo Snapshot hasn't been implemented yet.
deba@2116
   377
  ///
deba@2116
   378
  class SmartUGraph : public ExtendedSmartUGraphBase {
deba@2116
   379
  };
deba@2116
   380
deba@2116
   381
deba@2116
   382
  class SmartBpUGraphBase {
deba@2116
   383
  public:
deba@2116
   384
deba@2116
   385
    class NodeSetError : public LogicError {
deba@2116
   386
      virtual const char* exceptionName() const { 
deba@2116
   387
	return "lemon::SmartBpUGraph::NodeSetError";
deba@2116
   388
      }
deba@2116
   389
    };
deba@2116
   390
deba@2116
   391
  protected:
deba@2116
   392
deba@2116
   393
    struct NodeT {
deba@2116
   394
      int first;
deba@2116
   395
      NodeT() {}
deba@2116
   396
      NodeT(int _first) : first(_first) {}
deba@2116
   397
    };
deba@2116
   398
deba@2116
   399
    struct UEdgeT {
deba@2116
   400
      int aNode, next_out;
deba@2116
   401
      int bNode, next_in;
deba@2116
   402
    };
deba@2116
   403
deba@2116
   404
    std::vector<NodeT> aNodes;
deba@2116
   405
    std::vector<NodeT> bNodes;
deba@2116
   406
deba@2116
   407
    std::vector<UEdgeT> edges;
deba@2116
   408
deba@2116
   409
  public:
deba@2116
   410
  
deba@2116
   411
    class Node {
deba@2116
   412
      friend class SmartBpUGraphBase;
deba@2116
   413
    protected:
deba@2116
   414
      int id;
deba@2116
   415
deba@2116
   416
      Node(int _id) : id(_id) {}
deba@2116
   417
    public:
deba@2116
   418
      Node() {}
deba@2116
   419
      Node(Invalid) { id = -1; }
deba@2116
   420
      bool operator==(const Node i) const {return id==i.id;}
deba@2116
   421
      bool operator!=(const Node i) const {return id!=i.id;}
deba@2116
   422
      bool operator<(const Node i) const {return id<i.id;}
deba@2116
   423
    };
deba@2116
   424
deba@2116
   425
    class UEdge {
deba@2116
   426
      friend class SmartBpUGraphBase;
deba@2116
   427
    protected:
deba@2116
   428
      int id;
deba@2116
   429
deba@2116
   430
      UEdge(int _id) { id = _id;}
deba@2116
   431
    public:
deba@2116
   432
      UEdge() {}
deba@2116
   433
      UEdge (Invalid) { id = -1; }
deba@2116
   434
      bool operator==(const UEdge i) const {return id==i.id;}
deba@2116
   435
      bool operator!=(const UEdge i) const {return id!=i.id;}
deba@2116
   436
      bool operator<(const UEdge i) const {return id<i.id;}
deba@2116
   437
    };
deba@2116
   438
deba@2116
   439
    void firstANode(Node& node) const {
deba@2116
   440
      node.id = 2 * aNodes.size() - 2;
deba@2116
   441
      if (node.id < 0) node.id = -1; 
deba@2116
   442
    }
deba@2116
   443
    void nextANode(Node& node) const {
deba@2116
   444
      node.id -= 2;
deba@2116
   445
      if (node.id < 0) node.id = -1; 
deba@2116
   446
    }
deba@2116
   447
deba@2116
   448
    void firstBNode(Node& node) const {
deba@2116
   449
      node.id = 2 * bNodes.size() - 1;
deba@2116
   450
    }
deba@2116
   451
    void nextBNode(Node& node) const {
deba@2116
   452
      node.id -= 2;
deba@2116
   453
    }
deba@2116
   454
deba@2116
   455
    void first(Node& node) const {
deba@2116
   456
      if (aNodes.size() > 0) {
deba@2116
   457
	node.id = 2 * aNodes.size() - 2;
deba@2116
   458
      } else {
deba@2116
   459
	node.id = 2 * bNodes.size() - 1;
deba@2116
   460
      }
deba@2116
   461
    }
deba@2116
   462
    void next(Node& node) const {
deba@2116
   463
      node.id -= 2;
deba@2116
   464
      if (node.id == -2) {
deba@2116
   465
	node.id = 2 * bNodes.size() - 1;
deba@2116
   466
      }
deba@2116
   467
    }
deba@2116
   468
  
deba@2116
   469
    void first(UEdge& edge) const {
deba@2116
   470
      edge.id = edges.size() - 1;
deba@2116
   471
    }
deba@2116
   472
    void next(UEdge& edge) const {
deba@2116
   473
      --edge.id;
deba@2116
   474
    }
deba@2116
   475
deba@2116
   476
    void firstFromANode(UEdge& edge, const Node& node) const {
deba@2116
   477
      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
deba@2116
   478
      edge.id = aNodes[node.id >> 1].first;
deba@2116
   479
    }
deba@2116
   480
    void nextFromANode(UEdge& edge) const {
deba@2116
   481
      edge.id = edges[edge.id].next_out;
deba@2116
   482
    }
deba@2116
   483
deba@2116
   484
    void firstFromBNode(UEdge& edge, const Node& node) const {
deba@2116
   485
      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
deba@2116
   486
      edge.id = bNodes[node.id >> 1].first;
deba@2116
   487
    }
deba@2116
   488
    void nextFromBNode(UEdge& edge) const {
deba@2116
   489
      edge.id = edges[edge.id].next_in;
deba@2116
   490
    }
deba@2116
   491
deba@2116
   492
    static int id(const Node& node) {
deba@2116
   493
      return node.id;
deba@2116
   494
    }
deba@2116
   495
    static Node nodeFromId(int id) {
deba@2116
   496
      return Node(id);
deba@2116
   497
    }
deba@2116
   498
    int maxNodeId() const {
deba@2116
   499
      return aNodes.size() > bNodes.size() ?
deba@2116
   500
	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
deba@2116
   501
    }
deba@2116
   502
  
deba@2116
   503
    static int id(const UEdge& edge) {
deba@2116
   504
      return edge.id;
deba@2116
   505
    }
deba@2116
   506
    static UEdge uEdgeFromId(int id) {
deba@2116
   507
      return UEdge(id);
deba@2116
   508
    }
deba@2116
   509
    int maxUEdgeId() const {
deba@2116
   510
      return edges.size();
deba@2116
   511
    }
deba@2116
   512
  
deba@2116
   513
    static int aNodeId(const Node& node) {
deba@2116
   514
      return node.id >> 1;
deba@2116
   515
    }
deba@2116
   516
    static Node fromANodeId(int id) {
deba@2116
   517
      return Node(id << 1);
deba@2116
   518
    }
deba@2116
   519
    int maxANodeId() const {
deba@2116
   520
      return aNodes.size();
deba@2116
   521
    }
deba@2116
   522
deba@2116
   523
    static int bNodeId(const Node& node) {
deba@2116
   524
      return node.id >> 1;
deba@2116
   525
    }
deba@2116
   526
    static Node fromBNodeId(int id) {
deba@2116
   527
      return Node((id << 1) + 1);
deba@2116
   528
    }
deba@2116
   529
    int maxBNodeId() const {
deba@2116
   530
      return bNodes.size();
deba@2116
   531
    }
deba@2116
   532
deba@2116
   533
    Node aNode(const UEdge& edge) const {
deba@2116
   534
      return Node(edges[edge.id].aNode);
deba@2116
   535
    }
deba@2116
   536
    Node bNode(const UEdge& edge) const {
deba@2116
   537
      return Node(edges[edge.id].bNode);
deba@2116
   538
    }
deba@2116
   539
deba@2116
   540
    static bool aNode(const Node& node) {
deba@2116
   541
      return (node.id & 1) == 0;
deba@2116
   542
    }
deba@2116
   543
deba@2116
   544
    static bool bNode(const Node& node) {
deba@2116
   545
      return (node.id & 1) == 1;
deba@2116
   546
    }
deba@2116
   547
deba@2116
   548
    Node addANode() {
deba@2116
   549
      NodeT nodeT;
deba@2116
   550
      nodeT.first = -1;
deba@2116
   551
      aNodes.push_back(nodeT);
deba@2116
   552
      return Node(aNodes.size() * 2 - 2);
deba@2116
   553
    }
deba@2116
   554
deba@2116
   555
    Node addBNode() {
deba@2116
   556
      NodeT nodeT;
deba@2116
   557
      nodeT.first = -1;
deba@2116
   558
      bNodes.push_back(nodeT);
deba@2116
   559
      return Node(bNodes.size() * 2 - 1);
deba@2116
   560
    }
deba@2116
   561
deba@2116
   562
    UEdge addEdge(const Node& source, const Node& target) {
deba@2116
   563
      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
deba@2116
   564
      UEdgeT edgeT;
deba@2116
   565
      if ((source.id & 1) == 0) {
deba@2116
   566
	edgeT.aNode = source.id;
deba@2116
   567
	edgeT.bNode = target.id;
deba@2116
   568
      } else {
deba@2116
   569
	edgeT.aNode = target.id;
deba@2116
   570
	edgeT.bNode = source.id;
deba@2116
   571
      }
deba@2116
   572
      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
deba@2116
   573
      aNodes[edgeT.aNode >> 1].first = edges.size();
deba@2116
   574
      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
deba@2116
   575
      bNodes[edgeT.bNode >> 1].first = edges.size();
deba@2116
   576
      edges.push_back(edgeT);
deba@2116
   577
      return UEdge(edges.size() - 1);
deba@2116
   578
    }
deba@2116
   579
deba@2116
   580
    void clear() {
deba@2116
   581
      aNodes.clear();
deba@2116
   582
      bNodes.clear();
deba@2116
   583
      edges.clear();
deba@2116
   584
    }
deba@2116
   585
deba@2116
   586
    typedef True NodeNumTag;
deba@2116
   587
    int nodeNum() const { return aNodes.size() + bNodes.size(); }
deba@2116
   588
    int aNodeNum() const { return aNodes.size(); }
deba@2116
   589
    int bNodeNum() const { return bNodes.size(); }
deba@2116
   590
deba@2116
   591
    typedef True EdgeNumTag;
deba@2116
   592
    int uEdgeNum() const { return edges.size(); }
deba@2116
   593
deba@2116
   594
  };
deba@2116
   595
deba@2116
   596
deba@2116
   597
  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
deba@2116
   598
deba@2116
   599
  /// \ingroup graphs
deba@2116
   600
  ///
deba@2116
   601
  /// \brief A smart bipartite undirected graph class.
deba@2116
   602
  ///
deba@2116
   603
  /// This is a simple and fast bipartite undirected graph implementation.
deba@2116
   604
  /// It is also quite memory efficient, but at the price
deba@2116
   605
  /// that <b> it does not support node and edge deletions</b>.
deba@2116
   606
  /// Except from this it conforms to 
deba@2116
   607
  /// the \ref concept::BpUGraph "BpUGraph" concept.
deba@2116
   608
  /// \sa concept::BpUGraph.
deba@2116
   609
  ///
deba@2116
   610
  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
deba@2116
   611
deba@2116
   612
  
deba@2116
   613
  /// @}  
alpar@921
   614
} //namespace lemon
alpar@104
   615
alpar@157
   616
alpar@921
   617
#endif //LEMON_SMART_GRAPH_H