src/lemon/smart_graph.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1161 1c9658d51c8d
child 1274 5676e48ca026
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@105
    16
alpar@921
    17
#ifndef LEMON_SMART_GRAPH_H
alpar@921
    18
#define LEMON_SMART_GRAPH_H
alpar@104
    19
klao@491
    20
///\ingroup graphs
alpar@242
    21
///\file
alpar@242
    22
///\brief SmartGraph and SymSmartGraph classes.
alpar@242
    23
alpar@104
    24
#include <vector>
alpar@104
    25
alpar@921
    26
#include <lemon/invalid.h>
alpar@157
    27
klao@946
    28
#include <lemon/clearable_graph_extender.h>
klao@946
    29
#include <lemon/extendable_graph_extender.h>
klao@946
    30
#include <lemon/iterable_graph_extender.h>
deba@1039
    31
#include <lemon/alteration_notifier.h>
klao@946
    32
#include <lemon/default_map.h>
klao@946
    33
klao@1034
    34
#include <lemon/undir_graph_extender.h>
klao@1034
    35
klao@977
    36
#include <lemon/utility.h>
deba@782
    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() { }
klao@946
    78
    SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
alpar@104
    79
    
klao@977
    80
    typedef True NodeNumTag;
klao@977
    81
    typedef True EdgeNumTag;
klao@977
    82
alpar@813
    83
    ///Number of nodes.
alpar@813
    84
    int nodeNum() const { return nodes.size(); }
alpar@813
    85
    ///Number of edges.
alpar@813
    86
    int edgeNum() const { return edges.size(); }
alpar@104
    87
alpar@813
    88
    /// Maximum node ID.
alpar@813
    89
    
alpar@813
    90
    /// Maximum node ID.
alpar@813
    91
    ///\sa id(Node)
deba@980
    92
    int maxId(Node = INVALID) const { return nodes.size()-1; }
alpar@813
    93
    /// Maximum edge ID.
alpar@813
    94
    
alpar@813
    95
    /// Maximum edge ID.
alpar@813
    96
    ///\sa id(Edge)
deba@980
    97
    int maxId(Edge = INVALID) const { return edges.size()-1; }
alpar@108
    98
alpar@986
    99
    Node source(Edge e) const { return edges[e.n].source; }
alpar@986
   100
    Node target(Edge e) const { return edges[e.n].target; }
alpar@104
   101
alpar@813
   102
    /// Node ID.
alpar@813
   103
    
alpar@813
   104
    /// The ID of a valid Node is a nonnegative integer not greater than
alpar@813
   105
    /// \ref maxNodeId(). The range of the ID's is not surely continuous
alpar@813
   106
    /// and the greatest node ID can be actually less then \ref maxNodeId().
alpar@813
   107
    ///
alpar@813
   108
    /// The ID of the \ref INVALID node is -1.
alpar@813
   109
    ///\return The ID of the node \c v. 
alpar@713
   110
    static int id(Node v) { return v.n; }
alpar@813
   111
    /// Edge ID.
alpar@813
   112
    
alpar@813
   113
    /// The ID of a valid Edge is a nonnegative integer not greater than
alpar@813
   114
    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
alpar@813
   115
    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
alpar@813
   116
    ///
alpar@813
   117
    /// The ID of the \ref INVALID edge is -1.
alpar@813
   118
    ///\return The ID of the edge \c e. 
alpar@713
   119
    static int id(Edge e) { return e.n; }
alpar@104
   120
deba@1106
   121
    static Node fromId(int id, Node) { return Node(id);}
deba@1106
   122
deba@1106
   123
    static Edge fromId(int id, Edge) { return Edge(id);}
deba@1106
   124
alpar@164
   125
    Node addNode() {
alpar@164
   126
      Node n; n.n=nodes.size();
alpar@104
   127
      nodes.push_back(NodeT()); //FIXME: Hmmm...
alpar@104
   128
      return n;
alpar@104
   129
    }
alpar@108
   130
    
alpar@164
   131
    Edge addEdge(Node u, Node v) {
alpar@164
   132
      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
alpar@986
   133
      edges[e.n].source=u.n; edges[e.n].target=v.n;
alpar@104
   134
      edges[e.n].next_out=nodes[u.n].first_out;
alpar@104
   135
      edges[e.n].next_in=nodes[v.n].first_in;
alpar@104
   136
      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
alpar@108
   137
alpar@104
   138
      return e;
alpar@104
   139
    }
alpar@104
   140
deba@782
   141
    void clear() {
deba@782
   142
      edges.clear();
deba@782
   143
      nodes.clear();
deba@782
   144
    }
alpar@104
   145
klao@946
   146
alpar@164
   147
    class Node {
klao@946
   148
      friend class SmartGraphBase;
alpar@973
   149
      friend class SmartGraph;
alpar@104
   150
alpar@104
   151
    protected:
alpar@104
   152
      int n;
alpar@973
   153
      ///\todo It should be removed (or at least define a setToId() instead).
alpar@973
   154
      ///
alpar@164
   155
      Node(int nn) {n=nn;}
alpar@104
   156
    public:
alpar@164
   157
      Node() {}
alpar@503
   158
      Node (Invalid) { n=-1; }
alpar@164
   159
      bool operator==(const Node i) const {return n==i.n;}
alpar@164
   160
      bool operator!=(const Node i) const {return n!=i.n;}
alpar@164
   161
      bool operator<(const Node i) const {return n<i.n;}
alpar@104
   162
    };
alpar@104
   163
    
alpar@104
   164
alpar@164
   165
    class Edge {
klao@946
   166
      friend class SmartGraphBase;
alpar@973
   167
      friend class SmartGraph;
alpar@185
   168
alpar@104
   169
    protected:
alpar@104
   170
      int n;
alpar@973
   171
      ///\todo It should be removed (or at least define a setToId() instead).
alpar@973
   172
      ///
alpar@905
   173
      Edge(int nn) {n=nn;}
alpar@706
   174
    public:
alpar@164
   175
      Edge() { }
marci@174
   176
      Edge (Invalid) { n=-1; }
alpar@164
   177
      bool operator==(const Edge i) const {return n==i.n;}
alpar@164
   178
      bool operator!=(const Edge i) const {return n!=i.n;}
alpar@164
   179
      bool operator<(const Edge i) const {return n<i.n;}
klao@946
   180
    };
alpar@905
   181
klao@946
   182
    void first(Node& node) const {
klao@946
   183
      node.n = nodes.size() - 1;
klao@946
   184
    }
klao@946
   185
klao@946
   186
    static void next(Node& node) {
klao@946
   187
      --node.n;
klao@946
   188
    }
klao@946
   189
klao@946
   190
    void first(Edge& edge) const {
klao@946
   191
      edge.n = edges.size() - 1;
klao@946
   192
    }
klao@946
   193
klao@946
   194
    static void next(Edge& edge) {
klao@946
   195
      --edge.n;
klao@946
   196
    }
klao@946
   197
klao@946
   198
    void firstOut(Edge& edge, const Node& node) const {
klao@946
   199
      edge.n = nodes[node.n].first_out;
klao@946
   200
    }
klao@946
   201
klao@946
   202
    void nextOut(Edge& edge) const {
klao@946
   203
      edge.n = edges[edge.n].next_out;
klao@946
   204
    }
klao@946
   205
klao@946
   206
    void firstIn(Edge& edge, const Node& node) const {
klao@946
   207
      edge.n = nodes[node.n].first_in;
klao@946
   208
    }
alpar@104
   209
    
klao@946
   210
    void nextIn(Edge& edge) const {
klao@946
   211
      edge.n = edges[edge.n].next_in;
klao@946
   212
    }
alpar@105
   213
alpar@969
   214
    Edge _findEdge(Node u,Node v, Edge prev = INVALID) 
alpar@969
   215
    {
alpar@969
   216
      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
alpar@1082
   217
      while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out;
alpar@969
   218
      prev.n=e;
alpar@969
   219
      return prev;
alpar@969
   220
    }
alpar@973
   221
alpar@104
   222
  };
alpar@185
   223
klao@946
   224
  typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
klao@946
   225
  typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
deba@980
   226
  typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
klao@946
   227
  typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
klao@946
   228
  typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
deba@937
   229
alpar@1161
   230
  /// \addtogroup graphs
alpar@1161
   231
  /// @{
alpar@1161
   232
alpar@950
   233
  ///A smart graph class.
deba@937
   234
alpar@950
   235
  ///This is a simple and fast graph implementation.
alpar@950
   236
  ///It is also quite memory efficient, but at the price
alpar@974
   237
  ///that <b> it does support only limited (only stack-like)
alpar@974
   238
  ///node and edge deletions</b>.
alpar@950
   239
  ///It conforms to 
klao@959
   240
  ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
klao@959
   241
  ///\sa concept::ExtendableGraph.
alpar@950
   242
  ///
alpar@950
   243
  ///\author Alpar Juttner
deba@980
   244
  class SmartGraph : public ClearableSmartGraphBase {
alpar@969
   245
  public:
alpar@969
   246
    /// Finds an edge between two nodes.
alpar@973
   247
    
alpar@969
   248
    /// Finds an edge from node \c u to node \c v.
alpar@969
   249
    ///
alpar@969
   250
    /// If \c prev is \ref INVALID (this is the default value), then
alpar@969
   251
    /// it finds the first edge from \c u to \c v. Otherwise it looks for
alpar@969
   252
    /// the next edge from \c u to \c v after \c prev.
alpar@969
   253
    /// \return The found edge or \ref INVALID if there is no such an edge.
alpar@969
   254
    ///
alpar@969
   255
    /// Thus you can iterate through each edge from \c u to \c v as it follows.
alpar@969
   256
    /// \code
alpar@969
   257
    /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {
alpar@969
   258
    ///   ...
alpar@969
   259
    /// }
alpar@969
   260
    /// \endcode
alpar@969
   261
    /// \todo Possibly it should be a global function.
alpar@969
   262
    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
alpar@969
   263
    {
alpar@969
   264
      return _findEdge(u,v,prev);
alpar@969
   265
    }
alpar@973
   266
    
alpar@1011
   267
    class SnapShot;
alpar@1011
   268
    friend class SnapShot;
alpar@973
   269
alpar@1011
   270
  protected:
alpar@1011
   271
    void restoreSnapShot(const SnapShot &s)
alpar@973
   272
    {
alpar@973
   273
      while(s.edge_num>edges.size()) {
deba@1040
   274
	Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
alpar@986
   275
	nodes[edges.back().target].first_in=edges.back().next_in;
alpar@986
   276
	nodes[edges.back().source].first_out=edges.back().next_out;
alpar@973
   277
	edges.pop_back();
alpar@973
   278
      }
alpar@973
   279
      //nodes.resize(s.nodes_num);
alpar@973
   280
      while(s.node_num>nodes.size()) {
deba@1040
   281
	Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
alpar@973
   282
	nodes.pop_back();
alpar@973
   283
      }
alpar@1011
   284
    }    
alpar@1011
   285
alpar@1011
   286
  public:
alpar@1011
   287
    ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011
   288
alpar@1011
   289
    ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011
   290
    ///
alpar@1011
   291
    ///The newly added nodes and edges can be removed using the
alpar@1011
   292
    ///restore() function.
alpar@1011
   293
    ///\note After you restore a state, you cannot restore
alpar@1011
   294
    ///a later state, in other word you cannot add again the edges deleted
alpar@1011
   295
    ///by restore() using another SnapShot instance.
alpar@1011
   296
    ///
alpar@1011
   297
    class SnapShot 
alpar@1011
   298
    {
alpar@1011
   299
      SmartGraph *g;
alpar@1011
   300
    protected:
alpar@1011
   301
      friend class SmartGraph;
alpar@1011
   302
      unsigned int node_num;
alpar@1011
   303
      unsigned int edge_num;
alpar@1011
   304
    public:
alpar@1011
   305
      ///Default constructur.
alpar@1011
   306
      
alpar@1011
   307
      ///Default constructur.
alpar@1011
   308
      ///To actually make a snapshot you must call save().
alpar@1011
   309
      ///
alpar@1011
   310
      SnapShot() : g(0) {}
alpar@1011
   311
      ///Constructor that immediately makes a snapshot
alpar@1011
   312
      
alpar@1011
   313
      ///This constructor immediately makes a snapshot of the graph.
alpar@1011
   314
      ///\param _g The graph we make a snapshot of.
alpar@1011
   315
      SnapShot(SmartGraph &_g) :g(&_g) {
alpar@1011
   316
	node_num=g->nodes.size();
alpar@1011
   317
	edge_num=g->edges.size();
alpar@1011
   318
      }
alpar@1011
   319
alpar@1011
   320
      ///Make a snapshot.
alpar@1011
   321
alpar@1011
   322
      ///Make a snapshot of the graph.
alpar@1011
   323
      ///
alpar@1011
   324
      ///This function can be called more than once. In case of a repeated
alpar@1011
   325
      ///call, the previous snapshot gets lost.
alpar@1011
   326
      ///\param _g The graph we make the snapshot of.
alpar@1011
   327
      void save(SmartGraph &_g) 
alpar@1011
   328
      {
alpar@1011
   329
	g=&_g;
alpar@1011
   330
	node_num=g->nodes.size();
alpar@1011
   331
	edge_num=g->edges.size();
alpar@1011
   332
      }
alpar@1011
   333
alpar@1011
   334
      ///Undo the changes until a snapshot.
alpar@1011
   335
      
alpar@1011
   336
      ///Undo the changes until a snapshot created by save().
alpar@1011
   337
      ///
alpar@1011
   338
      ///\param s an internal stucture given back by save()
alpar@1011
   339
      ///\note After you restored a state, you cannot restore
alpar@1011
   340
      ///a later state, in other word you cannot add again the edges deleted
alpar@1011
   341
      ///by restore().
alpar@1011
   342
      ///
alpar@1011
   343
      ///\todo This function might be called undo().
alpar@1011
   344
      
alpar@1011
   345
      void restore()
alpar@1011
   346
      {
alpar@1011
   347
	g->restoreSnapShot(*this);
alpar@1011
   348
      }
alpar@1011
   349
    };
alpar@973
   350
  };
klao@1034
   351
klao@1034
   352
klao@1034
   353
  /**************** Undirected List Graph ****************/
klao@1034
   354
klao@1034
   355
  typedef ClearableUndirGraphExtender<
klao@1034
   356
    ExtendableUndirGraphExtender<
klao@1034
   357
    MappableUndirGraphExtender<
klao@1034
   358
    IterableUndirGraphExtender<
klao@1034
   359
    AlterableUndirGraphExtender<
klao@1034
   360
    UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;
klao@1034
   361
alpar@1035
   362
  ///A smart undirected graph class.
alpar@1035
   363
alpar@1035
   364
  ///This is a simple and fast undirected graph implementation.
alpar@1035
   365
  ///It is also quite memory efficient, but at the price
alpar@1035
   366
  ///that <b> it does support only limited (only stack-like)
alpar@1035
   367
  ///node and edge deletions</b>.
alpar@1035
   368
  ///Except from this it conforms to 
alpar@1035
   369
  ///the \ref concept::UndirGraph "UndirGraph" concept.
alpar@1035
   370
  ///\sa concept::UndirGraph.
alpar@1035
   371
  ///
alpar@1035
   372
  ///\todo SnapShot hasn't been implemented yet.
alpar@1035
   373
  ///
klao@1034
   374
  class UndirSmartGraph : public UndirSmartGraphBase {
klao@1034
   375
  };
klao@1034
   376
alpar@950
   377
  
alpar@407
   378
  /// @}  
alpar@921
   379
} //namespace lemon
alpar@104
   380
alpar@157
   381
alpar@921
   382
#endif //LEMON_SMART_GRAPH_H