src/work/deba/list_graph.h
author alpar
Thu, 23 Sep 2004 14:40:45 +0000
changeset 905 5be029d19c98
parent 703 32f280a5ed7d
child 921 818510fa3d99
permissions -rw-r--r--
Some code cleaning in id related stuffs
alpar@395
     1
// -*- mode:C++ -*-
alpar@395
     2
alpar@405
     3
#ifndef HUGO_LIST_GRAPH_H
alpar@405
     4
#define HUGO_LIST_GRAPH_H
alpar@395
     5
klao@491
     6
///\ingroup graphs
alpar@395
     7
///\file
alpar@405
     8
///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
alpar@395
     9
alpar@395
    10
#include <vector>
deba@698
    11
#include <climits>
alpar@395
    12
deba@698
    13
#include "invalid.h"
deba@698
    14
deba@703
    15
#include "array_map_factory.h"
deba@698
    16
#include "map_registry.h"
deba@698
    17
deba@698
    18
#include "map_defines.h"
alpar@395
    19
alpar@395
    20
namespace hugo {
alpar@395
    21
alpar@406
    22
/// \addtogroup graphs
alpar@406
    23
/// @{
alpar@406
    24
alpar@401
    25
  ///A list graph class.
alpar@395
    26
alpar@397
    27
  ///This is a simple and fast erasable graph implementation.
alpar@397
    28
  ///
alpar@395
    29
  ///It conforms to the graph interface documented under
alpar@880
    30
  ///the description of \ref Graph.
alpar@880
    31
  ///\sa \ref Graph.
alpar@397
    32
  class ListGraph {
alpar@395
    33
alpar@397
    34
    //Nodes are double linked.
alpar@397
    35
    //The free nodes are only single linked using the "next" field.
alpar@395
    36
    struct NodeT 
alpar@395
    37
    {
alpar@397
    38
      int first_in,first_out;
alpar@397
    39
      int prev, next;
alpar@397
    40
      //      NodeT() {}
alpar@395
    41
    };
alpar@397
    42
    //Edges are double linked.
alpar@397
    43
    //The free edges are only single linked using the "next_in" field.
alpar@395
    44
    struct EdgeT 
alpar@395
    45
    {
alpar@397
    46
      int head, tail;
alpar@397
    47
      int prev_in, prev_out;
alpar@397
    48
      int next_in, next_out;
alpar@395
    49
      //FIXME: is this necessary?
alpar@397
    50
      //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}  
alpar@395
    51
    };
alpar@395
    52
alpar@395
    53
    std::vector<NodeT> nodes;
alpar@397
    54
    //The first node
alpar@397
    55
    int first_node;
alpar@397
    56
    //The first free node
alpar@397
    57
    int first_free_node;
alpar@395
    58
    std::vector<EdgeT> edges;
alpar@397
    59
    //The first free edge
alpar@397
    60
    int first_free_edge;
alpar@395
    61
    
alpar@397
    62
  protected:
alpar@395
    63
    
alpar@395
    64
  public:
alpar@397
    65
    
alpar@395
    66
    class Node;
alpar@395
    67
    class Edge;
alpar@395
    68
deba@698
    69
    typedef ListGraph Graph;
deba@698
    70
alpar@395
    71
  public:
alpar@395
    72
alpar@395
    73
    class NodeIt;
alpar@395
    74
    class EdgeIt;
alpar@395
    75
    class OutEdgeIt;
alpar@395
    76
    class InEdgeIt;
alpar@395
    77
    
deba@698
    78
    CREATE_MAP_REGISTRIES;
deba@703
    79
    CREATE_MAPS(ArrayMapFactory);
alpar@395
    80
  public:
alpar@395
    81
alpar@397
    82
    ListGraph() : nodes(), first_node(-1),
alpar@397
    83
		  first_free_node(-1), edges(), first_free_edge(-1) {}
alpar@397
    84
    ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
alpar@397
    85
				     first_free_node(_g.first_free_node),
alpar@397
    86
				     edges(_g.edges),
alpar@397
    87
				     first_free_edge(_g.first_free_edge) {}
alpar@395
    88
    
alpar@395
    89
alpar@395
    90
    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
alpar@395
    91
    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
alpar@395
    92
alpar@695
    93
    ///Set the expected number of edges
alpar@695
    94
alpar@695
    95
    ///With this function, it is possible to set the expected number of edges.
alpar@695
    96
    ///The use of this fasten the building of the graph and makes
alpar@695
    97
    ///it possible to avoid the superfluous memory allocation.
alpar@695
    98
    void reserveEdge(int n) { edges.reserve(n); };
alpar@695
    99
    
alpar@395
   100
    ///\bug This function does something different than
alpar@395
   101
    ///its name would suggests...
alpar@395
   102
    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
alpar@395
   103
    ///\bug This function does something different than
alpar@395
   104
    ///its name would suggests...
alpar@395
   105
    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
alpar@395
   106
alpar@395
   107
    Node tail(Edge e) const { return edges[e.n].tail; }
alpar@395
   108
    Node head(Edge e) const { return edges[e.n].head; }
alpar@395
   109
alpar@395
   110
    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
alpar@395
   111
    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
alpar@395
   112
alpar@395
   113
    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
alpar@395
   114
    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
alpar@395
   115
alpar@395
   116
    NodeIt& first(NodeIt& v) const { 
alpar@395
   117
      v=NodeIt(*this); return v; }
alpar@395
   118
    EdgeIt& first(EdgeIt& e) const { 
alpar@395
   119
      e=EdgeIt(*this); return e; }
alpar@395
   120
    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
alpar@395
   121
      e=OutEdgeIt(*this,v); return e; }
alpar@395
   122
    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
alpar@395
   123
      e=InEdgeIt(*this,v); return e; }
alpar@395
   124
alpar@395
   125
//     template< typename It >
alpar@395
   126
//     It first() const { It e; first(e); return e; }
alpar@395
   127
alpar@395
   128
//     template< typename It >
alpar@395
   129
//     It first(Node v) const { It e; first(e,v); return e; }
alpar@395
   130
alpar@395
   131
    bool valid(Edge e) const { return e.n!=-1; }
alpar@395
   132
    bool valid(Node n) const { return n.n!=-1; }
alpar@395
   133
    
alpar@395
   134
    void setInvalid(Edge &e) { e.n=-1; }
alpar@395
   135
    void setInvalid(Node &n) { n.n=-1; }
alpar@395
   136
    
alpar@395
   137
    template <typename It> It getNext(It it) const
alpar@395
   138
    { It tmp(it); return next(tmp); }
alpar@395
   139
alpar@395
   140
    NodeIt& next(NodeIt& it) const { 
alpar@397
   141
      it.n=nodes[it.n].next; 
alpar@395
   142
      return it; 
alpar@395
   143
    }
alpar@395
   144
    OutEdgeIt& next(OutEdgeIt& it) const
alpar@395
   145
    { it.n=edges[it.n].next_out; return it; }
alpar@395
   146
    InEdgeIt& next(InEdgeIt& it) const
alpar@395
   147
    { it.n=edges[it.n].next_in; return it; }
alpar@397
   148
    EdgeIt& next(EdgeIt& it) const {
alpar@397
   149
      if(edges[it.n].next_in!=-1) { 
alpar@397
   150
	it.n=edges[it.n].next_in;
alpar@397
   151
      }
alpar@397
   152
      else {
alpar@397
   153
	int n;
alpar@397
   154
	for(n=nodes[edges[it.n].head].next;
alpar@397
   155
	    n!=-1 && nodes[n].first_in == -1;
alpar@397
   156
	    n = nodes[n].next) ;
alpar@397
   157
	it.n = (n==-1)?-1:nodes[n].first_in;
alpar@397
   158
      }
alpar@397
   159
      return it;
alpar@397
   160
    }
alpar@395
   161
alpar@395
   162
    int id(Node v) const { return v.n; }
alpar@395
   163
    int id(Edge e) const { return e.n; }
alpar@395
   164
alpar@397
   165
    /// Adds a new node to the graph.
alpar@397
   166
alpar@397
   167
    /// \todo It adds the nodes in a reversed order.
alpar@397
   168
    /// (i.e. the lastly added node becomes the first.)
alpar@395
   169
    Node addNode() {
alpar@397
   170
      int n;
alpar@397
   171
      
alpar@397
   172
      if(first_free_node==-1)
alpar@397
   173
	{
alpar@397
   174
	  n = nodes.size();
alpar@397
   175
	  nodes.push_back(NodeT());
alpar@397
   176
	}
alpar@397
   177
      else {
alpar@397
   178
	n = first_free_node;
alpar@397
   179
	first_free_node = nodes[n].next;
alpar@397
   180
      }
alpar@397
   181
      
alpar@397
   182
      nodes[n].next = first_node;
alpar@397
   183
      if(first_node != -1) nodes[first_node].prev = n;
alpar@397
   184
      first_node = n;
alpar@397
   185
      nodes[n].prev = -1;
alpar@397
   186
      
alpar@397
   187
      nodes[n].first_in = nodes[n].first_out = -1;
alpar@397
   188
      
alpar@397
   189
      Node nn; nn.n=n;
alpar@395
   190
alpar@397
   191
      //Update dynamic maps
deba@698
   192
      node_maps.add(nn);
alpar@395
   193
alpar@397
   194
      return nn;
alpar@395
   195
    }
alpar@395
   196
    
alpar@395
   197
    Edge addEdge(Node u, Node v) {
alpar@397
   198
      int n;
alpar@397
   199
      
alpar@397
   200
      if(first_free_edge==-1)
alpar@397
   201
	{
alpar@397
   202
	  n = edges.size();
alpar@397
   203
	  edges.push_back(EdgeT());
alpar@397
   204
	}
alpar@397
   205
      else {
alpar@397
   206
	n = first_free_edge;
alpar@397
   207
	first_free_edge = edges[n].next_in;
alpar@397
   208
      }
alpar@397
   209
      
alpar@397
   210
      edges[n].tail = u.n; edges[n].head = v.n;
alpar@395
   211
alpar@397
   212
      edges[n].next_out = nodes[u.n].first_out;
alpar@397
   213
      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
alpar@397
   214
      edges[n].next_in = nodes[v.n].first_in;
alpar@397
   215
      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
alpar@397
   216
      edges[n].prev_in = edges[n].prev_out = -1;
alpar@397
   217
	
alpar@397
   218
      nodes[u.n].first_out = nodes[v.n].first_in = n;
alpar@397
   219
alpar@397
   220
      Edge e; e.n=n;
alpar@397
   221
alpar@397
   222
      //Update dynamic maps
deba@698
   223
      edge_maps.add(e);
alpar@395
   224
alpar@395
   225
      return e;
alpar@395
   226
    }
alpar@395
   227
alpar@397
   228
  private:
alpar@397
   229
    void eraseEdge(int n) {
alpar@397
   230
      
alpar@397
   231
      if(edges[n].next_in!=-1)
alpar@397
   232
	edges[edges[n].next_in].prev_in = edges[n].prev_in;
alpar@397
   233
      if(edges[n].prev_in!=-1)
alpar@397
   234
	edges[edges[n].prev_in].next_in = edges[n].next_in;
alpar@397
   235
      else nodes[edges[n].head].first_in = edges[n].next_in;
alpar@397
   236
      
alpar@397
   237
      if(edges[n].next_out!=-1)
alpar@397
   238
	edges[edges[n].next_out].prev_out = edges[n].prev_out;
alpar@397
   239
      if(edges[n].prev_out!=-1)
alpar@397
   240
	edges[edges[n].prev_out].next_out = edges[n].next_out;
alpar@397
   241
      else nodes[edges[n].tail].first_out = edges[n].next_out;
alpar@397
   242
      
alpar@397
   243
      edges[n].next_in = first_free_edge;
alpar@695
   244
      first_free_edge = n;      
alpar@397
   245
alpar@397
   246
      //Update dynamic maps
alpar@397
   247
      Edge e; e.n=n;
alpar@397
   248
    }
alpar@397
   249
      
alpar@397
   250
  public:
alpar@397
   251
alpar@397
   252
    void erase(Node nn) {
alpar@397
   253
      int n=nn.n;
alpar@397
   254
      
alpar@397
   255
      int m;
alpar@397
   256
      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
alpar@397
   257
      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
alpar@397
   258
alpar@397
   259
      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
alpar@397
   260
      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
alpar@397
   261
      else first_node = nodes[n].next;
alpar@397
   262
      
alpar@397
   263
      nodes[n].next = first_free_node;
alpar@397
   264
      first_free_node = n;
alpar@397
   265
alpar@397
   266
      //Update dynamic maps
deba@698
   267
      node_maps.erase(nn);
deba@698
   268
     }
deba@698
   269
    
deba@698
   270
    void erase(Edge e) { 
deba@698
   271
      edge_maps.erase(e);
deba@698
   272
      eraseEdge(e.n); 
alpar@397
   273
    }
alpar@397
   274
alpar@397
   275
    ///\bug Dynamic maps must be updated!
alpar@397
   276
    ///
alpar@397
   277
    void clear() {
alpar@397
   278
      nodes.clear();edges.clear();
alpar@397
   279
      first_node=first_free_node=first_free_edge=-1;
alpar@397
   280
    }
alpar@395
   281
alpar@395
   282
    class Node {
alpar@397
   283
      friend class ListGraph;
alpar@395
   284
      template <typename T> friend class NodeMap;
alpar@400
   285
       
alpar@395
   286
      friend class Edge;
alpar@395
   287
      friend class OutEdgeIt;
alpar@395
   288
      friend class InEdgeIt;
alpar@395
   289
      friend class SymEdge;
alpar@395
   290
alpar@395
   291
    protected:
alpar@395
   292
      int n;
alpar@397
   293
      friend int ListGraph::id(Node v) const; 
alpar@395
   294
      Node(int nn) {n=nn;}
alpar@395
   295
    public:
alpar@395
   296
      Node() {}
alpar@503
   297
      Node (Invalid) { n=-1; }
alpar@395
   298
      bool operator==(const Node i) const {return n==i.n;}
alpar@395
   299
      bool operator!=(const Node i) const {return n!=i.n;}
alpar@395
   300
      bool operator<(const Node i) const {return n<i.n;}
alpar@395
   301
    };
alpar@395
   302
    
alpar@395
   303
    class NodeIt : public Node {
alpar@397
   304
      friend class ListGraph;
alpar@395
   305
    public:
alpar@400
   306
      NodeIt() : Node() { }
alpar@400
   307
      NodeIt(Invalid i) : Node(i) { }
alpar@397
   308
      NodeIt(const ListGraph& G) : Node(G.first_node) { }
alpar@579
   309
      ///\todo Undocumented conversion Node -\> NodeIt.
alpar@579
   310
      NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
alpar@395
   311
    };
alpar@395
   312
alpar@395
   313
    class Edge {
alpar@397
   314
      friend class ListGraph;
alpar@395
   315
      template <typename T> friend class EdgeMap;
alpar@395
   316
alpar@397
   317
      //template <typename T> friend class SymListGraph::SymEdgeMap;      
alpar@397
   318
      //friend Edge SymListGraph::opposite(Edge) const;
alpar@395
   319
      
alpar@395
   320
      friend class Node;
alpar@395
   321
      friend class NodeIt;
alpar@395
   322
    protected:
alpar@395
   323
      int n;
alpar@397
   324
      friend int ListGraph::id(Edge e) const;
alpar@395
   325
alpar@395
   326
      Edge(int nn) {n=nn;}
alpar@395
   327
    public:
alpar@395
   328
      Edge() { }
alpar@395
   329
      Edge (Invalid) { n=-1; }
alpar@395
   330
      bool operator==(const Edge i) const {return n==i.n;}
alpar@395
   331
      bool operator!=(const Edge i) const {return n!=i.n;}
alpar@395
   332
      bool operator<(const Edge i) const {return n<i.n;}
alpar@395
   333
      ///\bug This is a workaround until somebody tells me how to
alpar@397
   334
      ///make class \c SymListGraph::SymEdgeMap friend of Edge
alpar@395
   335
      int &idref() {return n;}
alpar@395
   336
      const int &idref() const {return n;}
alpar@395
   337
    };
alpar@395
   338
    
alpar@395
   339
    class EdgeIt : public Edge {
alpar@397
   340
      friend class ListGraph;
alpar@395
   341
    public:
alpar@397
   342
      EdgeIt(const ListGraph& G) : Edge() {
alpar@397
   343
      	int m;
alpar@397
   344
	for(m=G.first_node;
alpar@397
   345
	    m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
alpar@397
   346
	n = (m==-1)?-1:G.nodes[m].first_in;
alpar@397
   347
      }
alpar@395
   348
      EdgeIt (Invalid i) : Edge(i) { }
alpar@395
   349
      EdgeIt() : Edge() { }
alpar@395
   350
      ///\bug This is a workaround until somebody tells me how to
alpar@397
   351
      ///make class \c SymListGraph::SymEdgeMap friend of Edge
alpar@395
   352
      int &idref() {return n;}
alpar@395
   353
    };
alpar@395
   354
    
alpar@395
   355
    class OutEdgeIt : public Edge {
alpar@397
   356
      friend class ListGraph;
alpar@395
   357
    public: 
alpar@395
   358
      OutEdgeIt() : Edge() { }
alpar@395
   359
      OutEdgeIt (Invalid i) : Edge(i) { }
alpar@395
   360
alpar@397
   361
      OutEdgeIt(const ListGraph& G,const Node v)
alpar@395
   362
	: Edge(G.nodes[v.n].first_out) {}
alpar@395
   363
    };
alpar@395
   364
    
alpar@395
   365
    class InEdgeIt : public Edge {
alpar@397
   366
      friend class ListGraph;
alpar@395
   367
    public: 
alpar@395
   368
      InEdgeIt() : Edge() { }
alpar@395
   369
      InEdgeIt (Invalid i) : Edge(i) { }
alpar@681
   370
      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
alpar@395
   371
    };
alpar@395
   372
alpar@395
   373
  };
alpar@395
   374
alpar@395
   375
  ///Graph for bidirectional edges.
alpar@395
   376
alpar@395
   377
  ///The purpose of this graph structure is to handle graphs
alpar@395
   378
  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
alpar@395
   379
  ///of oppositely directed edges.
alpar@395
   380
  ///There is a new edge map type called
alpar@397
   381
  ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
alpar@395
   382
  ///that complements this
alpar@395
   383
  ///feature by
alpar@395
   384
  ///storing shared values for the edge pairs. The usual
alpar@880
   385
  ///\ref Graph::EdgeMap "EdgeMap"
alpar@395
   386
  ///can be used
alpar@395
   387
  ///as well.
alpar@395
   388
  ///
alpar@395
   389
  ///The oppositely directed edge can also be obtained easily
alpar@395
   390
  ///using \ref opposite.
alpar@397
   391
  ///
alpar@397
   392
  ///Here erase(Edge) deletes a pair of edges.
alpar@397
   393
  ///
alpar@397
   394
  ///\todo this date structure need some reconsiderations. Maybe it
alpar@397
   395
  ///should be implemented independently from ListGraph.
alpar@395
   396
deba@701
   397
}
alpar@395
   398
alpar@405
   399
#endif //HUGO_LIST_GRAPH_H