COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_list_graph.hh @ 16:dd19ef4d7ba4

Last change on this file since 16:dd19ef4d7ba4 was 16:dd19ef4d7ba4, checked in by marci, 20 years ago

* empty log message *

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