nem hekkelunk.
1 #ifndef MARCI_LIST_GRAPH_HH
2 #define MARCI_LIST_GRAPH_HH
13 class each_node_iterator;
15 class each_edge_iterator;
16 class out_edge_iterator;
17 class in_edge_iterator;
18 class sym_edge_iterator;
25 node_item* _first_node;
26 node_item* _last_node;
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);
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;
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);
73 node_item* _add_node() {
74 node_item* p=new node_item;
80 p->_prev_node=_last_node;
82 if (_last_node) _last_node->_next_node=p;
84 if (!_first_node) _first_node=p;
89 edge_item* _add_edge(node_item* _tail, node_item* _head) {
90 edge_item* e=new edge_item;
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;
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; }
110 /* default constructor */
112 list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
114 int node_num() { return _node_num; }
115 int edge_num() { return _edge_num; }
117 /* functions to construct iterators from the graph, or from each other */
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);
127 out_edge_iterator first_out_edge(const node_iterator& v) {
128 return out_edge_iterator(v);
130 in_edge_iterator first_in_edge(const node_iterator& v) {
131 return in_edge_iterator(v);
133 sym_edge_iterator first_sym_edge(const node_iterator& v) {
134 return sym_edge_iterator(v);
136 node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
137 node_iterator head(const edge_iterator& e) { return e.head_node(); }
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(); }
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(); }
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(); }
153 /* same methods in other style */
154 /* for experimental purpose */
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);
161 void get_first(in_edge_iterator& e, const node_iterator& v) {
162 e=in_edge_iterator(v);
164 void get_first(sym_edge_iterator& e, const node_iterator& v) {
165 e=sym_edge_iterator(v);
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); }
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(); }
183 /* for getting id's of graph objects */
184 /* these are important for the implementation of property vectors */
186 int id(const node_iterator& v) { return v.node->id; }
187 int id(const edge_iterator& e) { return e.edge->id; }
189 /* adding nodes and edges */
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));
196 /* stream operations, for testing purpose */
198 friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) {
199 os << i.node->id; return os;
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 << ")";
206 class node_iterator {
207 friend class list_graph;
209 friend class edge_iterator;
210 friend class out_edge_iterator;
211 friend class in_edge_iterator;
212 friend class sym_edge_iterator;
215 friend int list_graph::id(const node_iterator& v);
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;
224 friend bool operator!=(const node_iterator& u, const node_iterator& v) {
225 return v.node!=u.node;
227 friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
230 class each_node_iterator : public node_iterator {
231 friend class list_graph;
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; }
238 class edge_iterator {
239 friend class list_graph;
241 friend class node_iterator;
242 friend class each_node_iterator;
245 friend int list_graph::id(const edge_iterator& e);
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;
254 friend bool operator!=(const edge_iterator& u, const edge_iterator& v) {
255 return v.edge!=u.edge;
258 node_iterator tail_node() const { return node_iterator(edge->_tail); }
259 node_iterator head_node() const { return node_iterator(edge->_head); }
261 friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
264 class each_edge_iterator : public edge_iterator {
265 friend class list_graph;
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; }
277 class out_edge_iterator : public edge_iterator {
278 friend class list_graph;
281 out_edge_iterator() : edge_iterator(), v(0) { }
283 out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
285 out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
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); }
292 class in_edge_iterator : public edge_iterator {
293 friend class list_graph;
296 in_edge_iterator() : edge_iterator(), v(0) { }
298 in_edge_iterator(const node_iterator& _v) : v(_v.node) {
299 edge=v->_first_in_edge;
302 in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
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); }
309 class sym_edge_iterator : public edge_iterator {
310 friend class list_graph;
311 bool out_or_in; //1 iff out, 0 iff in
314 sym_edge_iterator() : edge_iterator(), v(0) { }
316 sym_edge_iterator(const node_iterator& _v) : v(_v.node) {
318 edge=v->_first_out_edge;
319 if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
322 sym_edge_iterator& operator++() {
324 edge=edge->_next_out;
325 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
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); }
343 #endif //MARCI_LIST_GRAPH_HH