78 p->_prev_node=_last_node; |
80 p->_prev_node=_last_node; |
79 p->_next_node=0; |
81 p->_next_node=0; |
80 if (_last_node) _last_node->_next_node=p; |
82 if (_last_node) _last_node->_next_node=p; |
81 _last_node=p; |
83 _last_node=p; |
82 if (!_first_node) _first_node=p; |
84 if (!_first_node) _first_node=p; |
|
85 ++_node_num; |
83 return p; |
86 return p; |
84 } |
87 } |
85 |
88 |
86 edge_item* _add_edge(node_item* _tail, node_item* _head) { |
89 edge_item* _add_edge(node_item* _tail, node_item* _head) { |
87 edge_item* e=new edge_item; |
90 edge_item* e=new edge_item; |
96 |
99 |
97 e->_prev_in=_head->_last_in_edge; |
100 e->_prev_in=_head->_last_in_edge; |
98 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; |
101 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; |
99 _head->_last_in_edge=e; |
102 _head->_last_in_edge=e; |
100 if (!_head->_first_in_edge) { _head->_first_in_edge=e; } |
103 if (!_head->_first_in_edge) { _head->_first_in_edge=e; } |
|
104 ++_edge_num; |
101 return e; |
105 return e; |
102 } |
106 } |
103 |
107 |
104 public: |
108 public: |
105 |
109 |
106 /* default constructor */ |
110 /* default constructor */ |
107 |
111 |
108 list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { } |
112 list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { } |
109 |
113 |
|
114 int node_num() { return _node_num; } |
|
115 int edge_num() { return _edge_num; } |
|
116 |
110 /* functions to construct iterators from the graph, or from each other */ |
117 /* functions to construct iterators from the graph, or from each other */ |
111 |
118 |
112 each_node_iterator first_node() { return each_node_iterator(_first_node); } |
119 each_node_iterator first_node() { return each_node_iterator(_first_node); } |
113 each_edge_iterator first_edge() { |
120 each_edge_iterator first_edge() { |
114 node_item* v=_first_node; |
121 node_item* v=_first_node; |
207 node_item* node; |
214 node_item* node; |
208 friend int list_graph::id(const node_iterator& v); |
215 friend int list_graph::id(const node_iterator& v); |
209 public: |
216 public: |
210 node_iterator() : node(0) { } |
217 node_iterator() : node(0) { } |
211 node_iterator(node_item* _node) : node(_node) { } |
218 node_iterator(node_item* _node) : node(_node) { } |
212 bool is_valid() { return (node!=0); } |
219 bool valid() { return (node!=0); } |
213 void make_invalid() { node=0; } |
220 void make_invalid() { node=0; } |
214 friend bool operator==(const node_iterator& u, const node_iterator& v) { |
221 friend bool operator==(const node_iterator& u, const node_iterator& v) { |
215 return v.node==u.node; |
222 return v.node==u.node; |
216 } |
223 } |
217 friend bool operator!=(const node_iterator& u, const node_iterator& v) { |
224 friend bool operator!=(const node_iterator& u, const node_iterator& v) { |
237 edge_item* edge; |
244 edge_item* edge; |
238 friend int list_graph::id(const edge_iterator& e); |
245 friend int list_graph::id(const edge_iterator& e); |
239 public: |
246 public: |
240 edge_iterator() : edge(0) { } |
247 edge_iterator() : edge(0) { } |
241 edge_iterator(edge_item* _edge) : edge(_edge) { } |
248 edge_iterator(edge_item* _edge) : edge(_edge) { } |
242 bool is_valid() { return (edge!=0); } |
249 bool valid() { return (edge!=0); } |
243 void make_invalid() { edge=0; } |
250 void make_invalid() { edge=0; } |
244 friend bool operator==(const edge_iterator& u, const edge_iterator& v) { |
251 friend bool operator==(const edge_iterator& u, const edge_iterator& v) { |
245 return v.edge==u.edge; |
252 return v.edge==u.edge; |
246 } |
253 } |
247 friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { |
254 friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { |