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