src/work/marci_list_graph.hh
author alpar
Mon, 23 Feb 2004 07:05:27 +0000
changeset 118 38e16c594a4f
parent 19 3151a1026db9
permissions -rw-r--r--
Improvements in 'Timer'/'TimeStamp'
marci@9
     1
#ifndef MARCI_LIST_GRAPH_HH
marci@9
     2
#define MARCI_LIST_GRAPH_HH
marci@9
     3
marci@9
     4
#include <iostream>
marci@9
     5
alpar@107
     6
namespace hugo {
marci@9
     7
marci@9
     8
  class list_graph {
marci@9
     9
    class node_item;
marci@9
    10
    class edge_item;
marci@9
    11
  public:
marci@9
    12
    class node_iterator;
marci@9
    13
    class each_node_iterator;
marci@9
    14
    class edge_iterator;
marci@9
    15
    class each_edge_iterator;
marci@9
    16
    class out_edge_iterator;
marci@9
    17
    class in_edge_iterator;
marci@9
    18
    class sym_edge_iterator;
marci@9
    19
  private:
marci@9
    20
    int node_id;
marci@9
    21
    int edge_id;
marci@19
    22
    int _node_num;
marci@19
    23
    int _edge_num;
marci@9
    24
marci@9
    25
    node_item* _first_node;
marci@9
    26
    node_item* _last_node;
marci@9
    27
marci@9
    28
    class node_item {
marci@9
    29
      friend class list_graph;
marci@9
    30
      friend class node_iterator;
marci@9
    31
      friend class each_node_iterator;
marci@9
    32
      friend class edge_iterator;
marci@9
    33
      friend class each_edge_iterator;
marci@9
    34
      friend class out_edge_iterator;
marci@9
    35
      friend class in_edge_iterator;
marci@9
    36
      friend class sym_edge_iterator;
marci@9
    37
      friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
marci@9
    38
      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@9
    39
      list_graph* G;
marci@9
    40
      int id;
marci@9
    41
      edge_item* _first_out_edge;
marci@9
    42
      edge_item* _last_out_edge;
marci@9
    43
      edge_item* _first_in_edge;
marci@9
    44
      edge_item* _last_in_edge;
marci@9
    45
      node_item* _next_node;
marci@9
    46
      node_item* _prev_node;
marci@9
    47
    public:
marci@9
    48
      node_item() { }
marci@9
    49
    };
marci@9
    50
marci@9
    51
    class edge_item {
marci@9
    52
      friend class list_graph;
marci@9
    53
      friend class node_iterator;
marci@9
    54
      friend class each_node_iterator;
marci@9
    55
      friend class edge_iterator;
marci@9
    56
      friend class each_edge_iterator;
marci@9
    57
      friend class out_edge_iterator;
marci@9
    58
      friend class in_edge_iterator;
marci@9
    59
      friend class sym_edge_iterator;
marci@9
    60
      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@9
    61
      list_graph* G;
marci@9
    62
      int id;
marci@9
    63
      node_item* _tail;
marci@9
    64
      node_item* _head;
marci@9
    65
      edge_item* _next_out;
marci@9
    66
      edge_item* _prev_out;
marci@9
    67
      edge_item* _next_in;
marci@9
    68
      edge_item* _prev_in;
marci@9
    69
    public:
marci@9
    70
      edge_item() { }
marci@9
    71
    };
marci@9
    72
marci@9
    73
    node_item* _add_node() { 
marci@9
    74
      node_item* p=new node_item;
marci@9
    75
      p->id=node_id++;
marci@9
    76
      p->_first_out_edge=0;
marci@9
    77
      p->_last_out_edge=0;
marci@9
    78
      p->_first_in_edge=0;
marci@9
    79
      p->_last_in_edge=0;
marci@9
    80
      p->_prev_node=_last_node;
marci@9
    81
      p->_next_node=0;
marci@9
    82
      if (_last_node) _last_node->_next_node=p;
marci@9
    83
      _last_node=p;
marci@9
    84
      if (!_first_node) _first_node=p;
marci@19
    85
      ++_node_num;
marci@9
    86
      return p;
marci@9
    87
    }
marci@9
    88
marci@9
    89
    edge_item* _add_edge(node_item* _tail, node_item* _head) {
marci@9
    90
      edge_item* e=new edge_item;
marci@9
    91
      e->id=edge_id++;
marci@9
    92
      e->_tail=_tail;
marci@9
    93
      e->_head=_head;
marci@9
    94
      
marci@9
    95
      e->_prev_out=_tail->_last_out_edge;
marci@9
    96
      if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
marci@9
    97
      _tail->_last_out_edge=e;
marci@9
    98
      if (!_tail->_first_out_edge) _tail->_first_out_edge=e; 
marci@9
    99
       
marci@9
   100
      e->_prev_in=_head->_last_in_edge;
marci@9
   101
      if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
marci@9
   102
      _head->_last_in_edge=e;
marci@9
   103
      if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 
marci@19
   104
      ++_edge_num;
marci@9
   105
      return e;
marci@9
   106
    }
marci@9
   107
marci@9
   108
  public:
marci@9
   109
marci@9
   110
    /* default constructor */
marci@9
   111
marci@19
   112
    list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
marci@9
   113
    
marci@19
   114
    int node_num() { return _node_num; }
marci@19
   115
    int edge_num() { return _edge_num; }
marci@19
   116
marci@9
   117
    /* functions to construct iterators from the graph, or from each other */
marci@9
   118
marci@9
   119
    each_node_iterator first_node() { return each_node_iterator(_first_node); }
marci@9
   120
    each_edge_iterator first_edge() { 
marci@9
   121
      node_item* v=_first_node;
marci@9
   122
      edge_item* edge=v->_first_out_edge;
marci@9
   123
      while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
marci@9
   124
      return each_edge_iterator(v, edge); 
marci@9
   125
    }
marci@9
   126
    
marci@9
   127
    out_edge_iterator first_out_edge(const node_iterator& v) { 
marci@9
   128
      return out_edge_iterator(v); 
marci@9
   129
    }
marci@9
   130
    in_edge_iterator first_in_edge(const node_iterator& v) { 
marci@9
   131
      return in_edge_iterator(v); 
marci@9
   132
    }
marci@9
   133
    sym_edge_iterator first_sym_edge(const node_iterator& v) { 
marci@9
   134
      return sym_edge_iterator(v); 
marci@9
   135
    }
marci@9
   136
    node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
marci@9
   137
    node_iterator head(const edge_iterator& e) { return e.head_node(); }
marci@9
   138
marci@9
   139
    node_iterator a_node(const out_edge_iterator& e) { return e.a_node(); }
marci@9
   140
    node_iterator a_node(const in_edge_iterator& e) { return e.a_node(); }
marci@9
   141
    node_iterator a_node(const sym_edge_iterator& e) { return e.a_node(); }
marci@9
   142
marci@9
   143
    node_iterator b_node(const out_edge_iterator& e) { return e.b_node(); }
marci@9
   144
    node_iterator b_node(const in_edge_iterator& e) { return e.b_node(); }
marci@9
   145
    node_iterator b_node(const sym_edge_iterator& e) { return e.b_node(); }
marci@9
   146
marci@16
   147
    //node_iterator invalid_node() { return node_iterator(); }
marci@16
   148
    //edge_iterator invalid_edge() { return edge_iterator(); }
marci@16
   149
    //out_edge_iterator invalid_out_edge() { return out_edge_iterator(); }
marci@16
   150
    //in_edge_iterator invalid_in_edge() { return in_edge_iterator(); }
marci@16
   151
    //sym_edge_iterator invalid_sym_edge() { return sym_edge_iterator(); }
marci@9
   152
marci@9
   153
    /* same methods in other style */
marci@9
   154
    /* for experimental purpose */
marci@9
   155
marci@9
   156
    void get_first(each_node_iterator& v) { v=each_node_iterator(_first_node); }
marci@9
   157
    void get_first(each_edge_iterator& e) { e=first_edge(); }
marci@9
   158
    void get_first(out_edge_iterator& e, const node_iterator& v) { 
marci@9
   159
      e=out_edge_iterator(v); 
marci@9
   160
    }
marci@9
   161
    void get_first(in_edge_iterator& e, const node_iterator& v) { 
marci@9
   162
      e=in_edge_iterator(v); 
marci@9
   163
    }
marci@9
   164
    void get_first(sym_edge_iterator& e, const node_iterator& v) { 
marci@9
   165
      e=sym_edge_iterator(v); 
marci@9
   166
    }
marci@9
   167
    void get_tail(node_iterator& n, const edge_iterator& e) { n=tail(e); }
marci@9
   168
    void get_head(node_iterator& n, const edge_iterator& e) { n=head(e); }
marci@9
   169
marci@9
   170
    void get_a_node(node_iterator& n, const out_edge_iterator& e) { n=e.a_node(); }
marci@9
   171
    void get_a_node(node_iterator& n, const in_edge_iterator& e) { n=e.a_node(); }
marci@9
   172
    void get_a_node(node_iterator& n, const sym_edge_iterator& e) { n=e.a_node(); }
marci@9
   173
    void get_b_node(node_iterator& n, const out_edge_iterator& e) { n=e.b_node(); }
marci@9
   174
    void get_b_node(node_iterator& n, const in_edge_iterator& e) { n=e.b_node(); }
marci@9
   175
    void get_b_node(node_iterator& n, const sym_edge_iterator& e) { n=e.b_node(); }
marci@16
   176
    //void get_invalid(node_iterator& n) { n=node_iterator(); }
marci@16
   177
    //void get_invalid(edge_iterator& e) { e=edge_iterator(); }
marci@16
   178
    //void get_invalid(out_edge_iterator& e) { e=out_edge_iterator(); }
marci@16
   179
    //void get_invalid(in_edge_iterator& e) { e=in_edge_iterator(); }
marci@16
   180
    //void get_invalid(sym_edge_iterator& e) { e=sym_edge_iterator(); }
marci@9
   181
marci@9
   182
marci@9
   183
    /* for getting id's of graph objects */
marci@9
   184
    /* these are important for the implementation of property vectors */
marci@9
   185
marci@9
   186
    int id(const node_iterator& v) { return v.node->id; }
marci@9
   187
    int id(const edge_iterator& e) { return e.edge->id; }
marci@9
   188
marci@9
   189
    /* adding nodes and edges */
marci@9
   190
marci@9
   191
    node_iterator add_node() { return node_iterator(_add_node()); }
marci@9
   192
    edge_iterator add_edge(const node_iterator& u, const node_iterator& v) {
marci@9
   193
      return edge_iterator(_add_edge(u.node, v.node)); 
marci@9
   194
    }
marci@9
   195
marci@9
   196
    /* stream operations, for testing purpose */
marci@9
   197
marci@9
   198
    friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) { 
marci@9
   199
      os << i.node->id; return os; 
marci@9
   200
    }
marci@9
   201
    friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i) { 
marci@9
   202
      os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 
marci@9
   203
      return os; 
marci@9
   204
    }
marci@9
   205
marci@9
   206
    class node_iterator {
marci@9
   207
      friend class list_graph;
marci@9
   208
marci@9
   209
      friend class edge_iterator;
marci@9
   210
      friend class out_edge_iterator;
marci@9
   211
      friend class in_edge_iterator;
marci@9
   212
      friend class sym_edge_iterator;
marci@9
   213
    protected:
marci@9
   214
      node_item* node;
marci@9
   215
      friend int list_graph::id(const node_iterator& v); 
marci@9
   216
    public:
marci@9
   217
      node_iterator() : node(0) { }
marci@9
   218
      node_iterator(node_item* _node) : node(_node) { }
marci@19
   219
      bool valid() { return (node!=0); }
marci@16
   220
      void make_invalid() { node=0; }
marci@9
   221
      friend bool operator==(const node_iterator& u, const node_iterator& v) { 
marci@9
   222
	return v.node==u.node; 
marci@9
   223
      } 
marci@9
   224
      friend bool operator!=(const node_iterator& u, const node_iterator& v) { 
marci@9
   225
	return v.node!=u.node; 
marci@9
   226
      } 
marci@9
   227
      friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
marci@9
   228
    };
marci@9
   229
    
marci@9
   230
    class each_node_iterator : public node_iterator {
marci@9
   231
      friend class list_graph;
marci@9
   232
    public:
marci@9
   233
      each_node_iterator() : node_iterator() { }
marci@9
   234
      each_node_iterator(node_item* v) : node_iterator(v) { }
marci@9
   235
      each_node_iterator& operator++() { node=node->_next_node; return *this; }
marci@9
   236
    };
marci@9
   237
marci@9
   238
    class edge_iterator {
marci@9
   239
      friend class list_graph;
marci@9
   240
      
marci@9
   241
      friend class node_iterator;
marci@9
   242
      friend class each_node_iterator;
marci@9
   243
    protected:
marci@9
   244
      edge_item* edge;
marci@9
   245
      friend int list_graph::id(const edge_iterator& e);
marci@9
   246
    public:
marci@9
   247
      edge_iterator() : edge(0) { }
marci@9
   248
      edge_iterator(edge_item* _edge) : edge(_edge) { }
marci@19
   249
      bool valid() { return (edge!=0); }
marci@16
   250
      void make_invalid() { edge=0; }
marci@9
   251
      friend bool operator==(const edge_iterator& u, const edge_iterator& v) { 
marci@9
   252
	return v.edge==u.edge; 
marci@9
   253
      } 
marci@9
   254
      friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { 
marci@9
   255
	return v.edge!=u.edge; 
marci@9
   256
      } 
marci@9
   257
    protected:
marci@9
   258
      node_iterator tail_node() const { return node_iterator(edge->_tail); }
marci@9
   259
      node_iterator head_node() const { return node_iterator(edge->_head); }
marci@9
   260
    public:
marci@9
   261
      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
marci@9
   262
    };
marci@9
   263
    
marci@9
   264
    class each_edge_iterator : public edge_iterator {
marci@9
   265
      friend class list_graph;
marci@9
   266
      node_item* v;
marci@9
   267
    public:
marci@9
   268
      each_edge_iterator() : edge_iterator(), v(0) { }
marci@9
   269
      each_edge_iterator(node_item* _v, edge_item* _e) : edge_iterator(_e), v(_v) { }
marci@9
   270
      each_edge_iterator& operator++() { 
marci@9
   271
	edge=edge->_next_out; 
marci@9
   272
	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
marci@9
   273
	return *this;
marci@9
   274
      }
marci@9
   275
    };
marci@9
   276
    
marci@9
   277
    class out_edge_iterator : public edge_iterator {
marci@9
   278
      friend class list_graph;
marci@9
   279
      node_item* v;
marci@9
   280
    public:
marci@9
   281
      out_edge_iterator() : edge_iterator(), v(0) { }
marci@9
   282
    protected:
marci@9
   283
      out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
marci@9
   284
    public:
marci@9
   285
      out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
marci@9
   286
    protected:
marci@9
   287
      node_iterator a_node() const { return node_iterator(v); }
marci@9
   288
      node_iterator b_node() const { 
marci@13
   289
	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@9
   290
    };
marci@9
   291
    
marci@9
   292
    class in_edge_iterator : public edge_iterator {
marci@9
   293
      friend class list_graph;
marci@9
   294
      node_item* v;
marci@9
   295
    public:
marci@9
   296
      in_edge_iterator() : edge_iterator(), v(0) { }
marci@9
   297
    protected:
marci@9
   298
      in_edge_iterator(const node_iterator& _v) : v(_v.node) { 
marci@9
   299
	edge=v->_first_in_edge; 
marci@9
   300
      }
marci@9
   301
    public:
marci@9
   302
      in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
marci@9
   303
    protected:
marci@9
   304
      node_iterator a_node() const { return node_iterator(v); }
marci@9
   305
      node_iterator b_node() const { 
marci@13
   306
	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@9
   307
    };
marci@9
   308
marci@9
   309
    class sym_edge_iterator : public edge_iterator {
marci@9
   310
      friend class list_graph;
marci@9
   311
      bool out_or_in; //1 iff out, 0 iff in
marci@9
   312
      node_item* v;
marci@9
   313
    public:
marci@9
   314
      sym_edge_iterator() : edge_iterator(), v(0) { }
marci@9
   315
    protected:
marci@9
   316
      sym_edge_iterator(const node_iterator& _v) : v(_v.node) { 
marci@9
   317
	out_or_in=1;
marci@9
   318
	edge=v->_first_out_edge; 
marci@9
   319
	if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
marci@9
   320
      }
marci@9
   321
    public:
marci@9
   322
      sym_edge_iterator& operator++() { 
marci@9
   323
	if (out_or_in) { 
marci@9
   324
	  edge=edge->_next_out; 
marci@9
   325
	  if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
marci@9
   326
	} else {
marci@9
   327
	  edge=edge->_next_in; 
marci@9
   328
	}
marci@9
   329
	return *this;
marci@9
   330
      }
marci@9
   331
    protected:
marci@9
   332
      node_iterator a_node() const { return node_iterator(v); }
marci@9
   333
      node_iterator b_node() const { 
marci@13
   334
	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
marci@9
   335
    };
marci@9
   336
marci@9
   337
  };
marci@9
   338
marci@9
   339
marci@9
   340
alpar@107
   341
} //namespace hugo
marci@9
   342
marci@9
   343
#endif //MARCI_LIST_GRAPH_HH