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 |
|