41 int first_in,first_out; |
41 int first_in,first_out; |
42 int prev, next; |
42 int prev, next; |
43 }; |
43 }; |
44 |
44 |
45 struct EdgeT { |
45 struct EdgeT { |
46 int head, tail; |
46 int target, source; |
47 int prev_in, prev_out; |
47 int prev_in, prev_out; |
48 int next_in, next_out; |
48 int next_in, next_out; |
49 }; |
49 }; |
50 |
50 |
51 std::vector<NodeT> nodes; |
51 std::vector<NodeT> nodes; |
109 |
109 |
110 /// Maximum edge ID. |
110 /// Maximum edge ID. |
111 ///\sa id(Edge) |
111 ///\sa id(Edge) |
112 int maxId(Edge = INVALID) const { return edges.size()-1; } |
112 int maxId(Edge = INVALID) const { return edges.size()-1; } |
113 |
113 |
114 Node tail(Edge e) const { return edges[e.id].tail; } |
114 Node source(Edge e) const { return edges[e.id].source; } |
115 Node head(Edge e) const { return edges[e.id].head; } |
115 Node target(Edge e) const { return edges[e.id].target; } |
116 |
116 |
117 |
117 |
118 void first(Node& node) const { |
118 void first(Node& node) const { |
119 node.id = first_node; |
119 node.id = first_node; |
120 } |
120 } |
135 void next(Edge& edge) const { |
135 void next(Edge& edge) const { |
136 if (edges[edge.id].next_in != -1) { |
136 if (edges[edge.id].next_in != -1) { |
137 edge.id = edges[edge.id].next_in; |
137 edge.id = edges[edge.id].next_in; |
138 } else { |
138 } else { |
139 int n; |
139 int n; |
140 for(n = nodes[edges[edge.id].head].next; |
140 for(n = nodes[edges[edge.id].target].next; |
141 n!=-1 && nodes[n].first_in == -1; |
141 n!=-1 && nodes[n].first_in == -1; |
142 n = nodes[n].next); |
142 n = nodes[n].next); |
143 edge.id = (n == -1) ? -1 : nodes[n].first_in; |
143 edge.id = (n == -1) ? -1 : nodes[n].first_in; |
144 } |
144 } |
145 } |
145 } |
196 } else { |
196 } else { |
197 n = first_free_edge; |
197 n = first_free_edge; |
198 first_free_edge = edges[n].next_in; |
198 first_free_edge = edges[n].next_in; |
199 } |
199 } |
200 |
200 |
201 edges[n].tail = u.id; |
201 edges[n].source = u.id; |
202 edges[n].head = v.id; |
202 edges[n].target = v.id; |
203 |
203 |
204 edges[n].next_out = nodes[u.id].first_out; |
204 edges[n].next_out = nodes[u.id].first_out; |
205 if(nodes[u.id].first_out != -1) { |
205 if(nodes[u.id].first_out != -1) { |
206 edges[nodes[u.id].first_out].prev_out = n; |
206 edges[nodes[u.id].first_out].prev_out = n; |
207 } |
207 } |
244 } |
244 } |
245 |
245 |
246 if(edges[n].prev_in!=-1) { |
246 if(edges[n].prev_in!=-1) { |
247 edges[edges[n].prev_in].next_in = edges[n].next_in; |
247 edges[edges[n].prev_in].next_in = edges[n].next_in; |
248 } else { |
248 } else { |
249 nodes[edges[n].head].first_in = edges[n].next_in; |
249 nodes[edges[n].target].first_in = edges[n].next_in; |
250 } |
250 } |
251 |
251 |
252 |
252 |
253 if(edges[n].next_out!=-1) { |
253 if(edges[n].next_out!=-1) { |
254 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
254 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
255 } |
255 } |
256 |
256 |
257 if(edges[n].prev_out!=-1) { |
257 if(edges[n].prev_out!=-1) { |
258 edges[edges[n].prev_out].next_out = edges[n].next_out; |
258 edges[edges[n].prev_out].next_out = edges[n].next_out; |
259 } else { |
259 } else { |
260 nodes[edges[n].tail].first_out = edges[n].next_out; |
260 nodes[edges[n].source].first_out = edges[n].next_out; |
261 } |
261 } |
262 |
262 |
263 edges[n].next_in = first_free_edge; |
263 edges[n].next_in = first_free_edge; |
264 first_free_edge = n; |
264 first_free_edge = n; |
265 |
265 |
270 nodes.clear(); |
270 nodes.clear(); |
271 first_node = first_free_node = first_free_edge = -1; |
271 first_node = first_free_node = first_free_edge = -1; |
272 } |
272 } |
273 |
273 |
274 protected: |
274 protected: |
275 void _moveHead(Edge e, Node n) |
275 void _moveTarget(Edge e, Node n) |
276 { |
276 { |
277 if(edges[e.id].next_in != -1) |
277 if(edges[e.id].next_in != -1) |
278 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
278 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
279 if(edges[e.id].prev_in != -1) |
279 if(edges[e.id].prev_in != -1) |
280 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
280 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
281 else nodes[edges[e.id].head].first_in = edges[e.id].next_in; |
281 else nodes[edges[e.id].target].first_in = edges[e.id].next_in; |
282 edges[e.id].head = n.id; |
282 edges[e.id].target = n.id; |
283 edges[e.id].prev_in = -1; |
283 edges[e.id].prev_in = -1; |
284 edges[e.id].next_in = nodes[n.id].first_in; |
284 edges[e.id].next_in = nodes[n.id].first_in; |
285 nodes[n.id].first_in = e.id; |
285 nodes[n.id].first_in = e.id; |
286 } |
286 } |
287 void _moveTail(Edge e, Node n) |
287 void _moveSource(Edge e, Node n) |
288 { |
288 { |
289 if(edges[e.id].next_out != -1) |
289 if(edges[e.id].next_out != -1) |
290 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
290 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
291 if(edges[e.id].prev_out != -1) |
291 if(edges[e.id].prev_out != -1) |
292 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
292 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
293 else nodes[edges[e.id].tail].first_out = edges[e.id].next_out; |
293 else nodes[edges[e.id].source].first_out = edges[e.id].next_out; |
294 edges[e.id].tail = n.id; |
294 edges[e.id].source = n.id; |
295 edges[e.id].prev_out = -1; |
295 edges[e.id].prev_out = -1; |
296 edges[e.id].next_out = nodes[n.id].first_out; |
296 edges[e.id].next_out = nodes[n.id].first_out; |
297 nodes[n.id].first_out = e.id; |
297 nodes[n.id].first_out = e.id; |
298 } |
298 } |
299 |
299 |
318 ///\sa concept::ErasableGraph. |
318 ///\sa concept::ErasableGraph. |
319 |
319 |
320 class ListGraph : public ErasableListGraphBase |
320 class ListGraph : public ErasableListGraphBase |
321 { |
321 { |
322 public: |
322 public: |
323 /// Moves the head of \c e to \c n |
323 /// Moves the target of \c e to \c n |
324 |
324 |
325 /// Moves the head of \c e to \c n |
325 /// Moves the target of \c e to \c n |
326 /// |
326 /// |
327 void moveHead(Edge e, Node n) { _moveHead(e,n); } |
327 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } |
328 /// Moves the tail of \c e to \c n |
328 /// Moves the source of \c e to \c n |
329 |
329 |
330 /// Moves the tail of \c e to \c n |
330 /// Moves the source of \c e to \c n |
331 /// |
331 /// |
332 void moveTail(Edge e, Node n) { _moveTail(e,n); } |
332 void moveSource(Edge e, Node n) { _moveSource(e,n); } |
333 |
333 |
334 ///Using this it possible to avoid the superfluous memory allocation. |
334 ///Using this it possible to avoid the superfluous memory allocation. |
335 ///\todo more docs... |
335 ///\todo more docs... |
336 void reserveEdge(int n) { edges.reserve(n); }; |
336 void reserveEdge(int n) { edges.reserve(n); }; |
337 |
337 |