COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_list_graph.hh @ 141:a17d2a6462ee

Last change on this file since 141:a17d2a6462ee was 107:8d62f0072ff0, checked in by Alpar Juttner, 20 years ago

marci -> hugo
resize -> update

File size: 11.4 KB
Line 
1#ifndef MARCI_LIST_GRAPH_HH
2#define MARCI_LIST_GRAPH_HH
3
4#include <iostream>
5
6namespace 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
Note: See TracBrowser for help on using the repository browser.