1.1 --- a/src/work/marci/oldies/marci_list_graph.hh Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,343 +0,0 @@
1.4 -#ifndef MARCI_LIST_GRAPH_HH
1.5 -#define MARCI_LIST_GRAPH_HH
1.6 -
1.7 -#include <iostream>
1.8 -
1.9 -namespace hugo {
1.10 -
1.11 - class list_graph {
1.12 - class node_item;
1.13 - class edge_item;
1.14 - public:
1.15 - class node_iterator;
1.16 - class each_node_iterator;
1.17 - class edge_iterator;
1.18 - class each_edge_iterator;
1.19 - class out_edge_iterator;
1.20 - class in_edge_iterator;
1.21 - class sym_edge_iterator;
1.22 - private:
1.23 - int node_id;
1.24 - int edge_id;
1.25 - int _node_num;
1.26 - int _edge_num;
1.27 -
1.28 - node_item* _first_node;
1.29 - node_item* _last_node;
1.30 -
1.31 - class node_item {
1.32 - friend class list_graph;
1.33 - friend class node_iterator;
1.34 - friend class each_node_iterator;
1.35 - friend class edge_iterator;
1.36 - friend class each_edge_iterator;
1.37 - friend class out_edge_iterator;
1.38 - friend class in_edge_iterator;
1.39 - friend class sym_edge_iterator;
1.40 - friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
1.41 - friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
1.42 - list_graph* G;
1.43 - int id;
1.44 - edge_item* _first_out_edge;
1.45 - edge_item* _last_out_edge;
1.46 - edge_item* _first_in_edge;
1.47 - edge_item* _last_in_edge;
1.48 - node_item* _next_node;
1.49 - node_item* _prev_node;
1.50 - public:
1.51 - node_item() { }
1.52 - };
1.53 -
1.54 - class edge_item {
1.55 - friend class list_graph;
1.56 - friend class node_iterator;
1.57 - friend class each_node_iterator;
1.58 - friend class edge_iterator;
1.59 - friend class each_edge_iterator;
1.60 - friend class out_edge_iterator;
1.61 - friend class in_edge_iterator;
1.62 - friend class sym_edge_iterator;
1.63 - friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
1.64 - list_graph* G;
1.65 - int id;
1.66 - node_item* _tail;
1.67 - node_item* _head;
1.68 - edge_item* _next_out;
1.69 - edge_item* _prev_out;
1.70 - edge_item* _next_in;
1.71 - edge_item* _prev_in;
1.72 - public:
1.73 - edge_item() { }
1.74 - };
1.75 -
1.76 - node_item* _add_node() {
1.77 - node_item* p=new node_item;
1.78 - p->id=node_id++;
1.79 - p->_first_out_edge=0;
1.80 - p->_last_out_edge=0;
1.81 - p->_first_in_edge=0;
1.82 - p->_last_in_edge=0;
1.83 - p->_prev_node=_last_node;
1.84 - p->_next_node=0;
1.85 - if (_last_node) _last_node->_next_node=p;
1.86 - _last_node=p;
1.87 - if (!_first_node) _first_node=p;
1.88 - ++_node_num;
1.89 - return p;
1.90 - }
1.91 -
1.92 - edge_item* _add_edge(node_item* _tail, node_item* _head) {
1.93 - edge_item* e=new edge_item;
1.94 - e->id=edge_id++;
1.95 - e->_tail=_tail;
1.96 - e->_head=_head;
1.97 -
1.98 - e->_prev_out=_tail->_last_out_edge;
1.99 - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
1.100 - _tail->_last_out_edge=e;
1.101 - if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
1.102 -
1.103 - e->_prev_in=_head->_last_in_edge;
1.104 - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
1.105 - _head->_last_in_edge=e;
1.106 - if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
1.107 - ++_edge_num;
1.108 - return e;
1.109 - }
1.110 -
1.111 - public:
1.112 -
1.113 - /* default constructor */
1.114 -
1.115 - list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
1.116 -
1.117 - int node_num() { return _node_num; }
1.118 - int edge_num() { return _edge_num; }
1.119 -
1.120 - /* functions to construct iterators from the graph, or from each other */
1.121 -
1.122 - each_node_iterator first_node() { return each_node_iterator(_first_node); }
1.123 - each_edge_iterator first_edge() {
1.124 - node_item* v=_first_node;
1.125 - edge_item* edge=v->_first_out_edge;
1.126 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
1.127 - return each_edge_iterator(v, edge);
1.128 - }
1.129 -
1.130 - out_edge_iterator first_out_edge(const node_iterator& v) {
1.131 - return out_edge_iterator(v);
1.132 - }
1.133 - in_edge_iterator first_in_edge(const node_iterator& v) {
1.134 - return in_edge_iterator(v);
1.135 - }
1.136 - sym_edge_iterator first_sym_edge(const node_iterator& v) {
1.137 - return sym_edge_iterator(v);
1.138 - }
1.139 - node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
1.140 - node_iterator head(const edge_iterator& e) { return e.head_node(); }
1.141 -
1.142 - node_iterator a_node(const out_edge_iterator& e) { return e.a_node(); }
1.143 - node_iterator a_node(const in_edge_iterator& e) { return e.a_node(); }
1.144 - node_iterator a_node(const sym_edge_iterator& e) { return e.a_node(); }
1.145 -
1.146 - node_iterator b_node(const out_edge_iterator& e) { return e.b_node(); }
1.147 - node_iterator b_node(const in_edge_iterator& e) { return e.b_node(); }
1.148 - node_iterator b_node(const sym_edge_iterator& e) { return e.b_node(); }
1.149 -
1.150 - //node_iterator invalid_node() { return node_iterator(); }
1.151 - //edge_iterator invalid_edge() { return edge_iterator(); }
1.152 - //out_edge_iterator invalid_out_edge() { return out_edge_iterator(); }
1.153 - //in_edge_iterator invalid_in_edge() { return in_edge_iterator(); }
1.154 - //sym_edge_iterator invalid_sym_edge() { return sym_edge_iterator(); }
1.155 -
1.156 - /* same methods in other style */
1.157 - /* for experimental purpose */
1.158 -
1.159 - void get_first(each_node_iterator& v) { v=each_node_iterator(_first_node); }
1.160 - void get_first(each_edge_iterator& e) { e=first_edge(); }
1.161 - void get_first(out_edge_iterator& e, const node_iterator& v) {
1.162 - e=out_edge_iterator(v);
1.163 - }
1.164 - void get_first(in_edge_iterator& e, const node_iterator& v) {
1.165 - e=in_edge_iterator(v);
1.166 - }
1.167 - void get_first(sym_edge_iterator& e, const node_iterator& v) {
1.168 - e=sym_edge_iterator(v);
1.169 - }
1.170 - void get_tail(node_iterator& n, const edge_iterator& e) { n=tail(e); }
1.171 - void get_head(node_iterator& n, const edge_iterator& e) { n=head(e); }
1.172 -
1.173 - void get_a_node(node_iterator& n, const out_edge_iterator& e) { n=e.a_node(); }
1.174 - void get_a_node(node_iterator& n, const in_edge_iterator& e) { n=e.a_node(); }
1.175 - void get_a_node(node_iterator& n, const sym_edge_iterator& e) { n=e.a_node(); }
1.176 - void get_b_node(node_iterator& n, const out_edge_iterator& e) { n=e.b_node(); }
1.177 - void get_b_node(node_iterator& n, const in_edge_iterator& e) { n=e.b_node(); }
1.178 - void get_b_node(node_iterator& n, const sym_edge_iterator& e) { n=e.b_node(); }
1.179 - //void get_invalid(node_iterator& n) { n=node_iterator(); }
1.180 - //void get_invalid(edge_iterator& e) { e=edge_iterator(); }
1.181 - //void get_invalid(out_edge_iterator& e) { e=out_edge_iterator(); }
1.182 - //void get_invalid(in_edge_iterator& e) { e=in_edge_iterator(); }
1.183 - //void get_invalid(sym_edge_iterator& e) { e=sym_edge_iterator(); }
1.184 -
1.185 -
1.186 - /* for getting id's of graph objects */
1.187 - /* these are important for the implementation of property vectors */
1.188 -
1.189 - int id(const node_iterator& v) { return v.node->id; }
1.190 - int id(const edge_iterator& e) { return e.edge->id; }
1.191 -
1.192 - /* adding nodes and edges */
1.193 -
1.194 - node_iterator add_node() { return node_iterator(_add_node()); }
1.195 - edge_iterator add_edge(const node_iterator& u, const node_iterator& v) {
1.196 - return edge_iterator(_add_edge(u.node, v.node));
1.197 - }
1.198 -
1.199 - /* stream operations, for testing purpose */
1.200 -
1.201 - friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) {
1.202 - os << i.node->id; return os;
1.203 - }
1.204 - friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i) {
1.205 - os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
1.206 - return os;
1.207 - }
1.208 -
1.209 - class node_iterator {
1.210 - friend class list_graph;
1.211 -
1.212 - friend class edge_iterator;
1.213 - friend class out_edge_iterator;
1.214 - friend class in_edge_iterator;
1.215 - friend class sym_edge_iterator;
1.216 - protected:
1.217 - node_item* node;
1.218 - friend int list_graph::id(const node_iterator& v);
1.219 - public:
1.220 - node_iterator() : node(0) { }
1.221 - node_iterator(node_item* _node) : node(_node) { }
1.222 - bool valid() { return (node!=0); }
1.223 - void make_invalid() { node=0; }
1.224 - friend bool operator==(const node_iterator& u, const node_iterator& v) {
1.225 - return v.node==u.node;
1.226 - }
1.227 - friend bool operator!=(const node_iterator& u, const node_iterator& v) {
1.228 - return v.node!=u.node;
1.229 - }
1.230 - friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
1.231 - };
1.232 -
1.233 - class each_node_iterator : public node_iterator {
1.234 - friend class list_graph;
1.235 - public:
1.236 - each_node_iterator() : node_iterator() { }
1.237 - each_node_iterator(node_item* v) : node_iterator(v) { }
1.238 - each_node_iterator& operator++() { node=node->_next_node; return *this; }
1.239 - };
1.240 -
1.241 - class edge_iterator {
1.242 - friend class list_graph;
1.243 -
1.244 - friend class node_iterator;
1.245 - friend class each_node_iterator;
1.246 - protected:
1.247 - edge_item* edge;
1.248 - friend int list_graph::id(const edge_iterator& e);
1.249 - public:
1.250 - edge_iterator() : edge(0) { }
1.251 - edge_iterator(edge_item* _edge) : edge(_edge) { }
1.252 - bool valid() { return (edge!=0); }
1.253 - void make_invalid() { edge=0; }
1.254 - friend bool operator==(const edge_iterator& u, const edge_iterator& v) {
1.255 - return v.edge==u.edge;
1.256 - }
1.257 - friend bool operator!=(const edge_iterator& u, const edge_iterator& v) {
1.258 - return v.edge!=u.edge;
1.259 - }
1.260 - protected:
1.261 - node_iterator tail_node() const { return node_iterator(edge->_tail); }
1.262 - node_iterator head_node() const { return node_iterator(edge->_head); }
1.263 - public:
1.264 - friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
1.265 - };
1.266 -
1.267 - class each_edge_iterator : public edge_iterator {
1.268 - friend class list_graph;
1.269 - node_item* v;
1.270 - public:
1.271 - each_edge_iterator() : edge_iterator(), v(0) { }
1.272 - each_edge_iterator(node_item* _v, edge_item* _e) : edge_iterator(_e), v(_v) { }
1.273 - each_edge_iterator& operator++() {
1.274 - edge=edge->_next_out;
1.275 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
1.276 - return *this;
1.277 - }
1.278 - };
1.279 -
1.280 - class out_edge_iterator : public edge_iterator {
1.281 - friend class list_graph;
1.282 - node_item* v;
1.283 - public:
1.284 - out_edge_iterator() : edge_iterator(), v(0) { }
1.285 - protected:
1.286 - out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
1.287 - public:
1.288 - out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
1.289 - protected:
1.290 - node_iterator a_node() const { return node_iterator(v); }
1.291 - node_iterator b_node() const {
1.292 - return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
1.293 - };
1.294 -
1.295 - class in_edge_iterator : public edge_iterator {
1.296 - friend class list_graph;
1.297 - node_item* v;
1.298 - public:
1.299 - in_edge_iterator() : edge_iterator(), v(0) { }
1.300 - protected:
1.301 - in_edge_iterator(const node_iterator& _v) : v(_v.node) {
1.302 - edge=v->_first_in_edge;
1.303 - }
1.304 - public:
1.305 - in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
1.306 - protected:
1.307 - node_iterator a_node() const { return node_iterator(v); }
1.308 - node_iterator b_node() const {
1.309 - return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
1.310 - };
1.311 -
1.312 - class sym_edge_iterator : public edge_iterator {
1.313 - friend class list_graph;
1.314 - bool out_or_in; //1 iff out, 0 iff in
1.315 - node_item* v;
1.316 - public:
1.317 - sym_edge_iterator() : edge_iterator(), v(0) { }
1.318 - protected:
1.319 - sym_edge_iterator(const node_iterator& _v) : v(_v.node) {
1.320 - out_or_in=1;
1.321 - edge=v->_first_out_edge;
1.322 - if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
1.323 - }
1.324 - public:
1.325 - sym_edge_iterator& operator++() {
1.326 - if (out_or_in) {
1.327 - edge=edge->_next_out;
1.328 - if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
1.329 - } else {
1.330 - edge=edge->_next_in;
1.331 - }
1.332 - return *this;
1.333 - }
1.334 - protected:
1.335 - node_iterator a_node() const { return node_iterator(v); }
1.336 - node_iterator b_node() const {
1.337 - return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(edge->_tail); }
1.338 - };
1.339 -
1.340 - };
1.341 -
1.342 -
1.343 -
1.344 -} //namespace hugo
1.345 -
1.346 -#endif //MARCI_LIST_GRAPH_HH