98 ListGraphBase() |
99 ListGraphBase() |
99 : nodes(), first_node(-1), |
100 : nodes(), first_node(-1), |
100 first_free_node(-1), edges(), first_free_edge(-1) {} |
101 first_free_node(-1), edges(), first_free_edge(-1) {} |
101 |
102 |
102 |
103 |
103 ///Using this it possible to avoid the superfluous memory allocation. |
|
104 ///\todo more docs... |
|
105 ///\todo It should be defined in ListGraph. |
|
106 void reserveEdge(int n) { edges.reserve(n); }; |
|
107 |
|
108 /// Maximum node ID. |
104 /// Maximum node ID. |
109 |
105 |
110 /// Maximum node ID. |
106 /// Maximum node ID. |
111 ///\sa id(Node) |
107 ///\sa id(Node) |
112 int maxNodeId() const { return nodes.size()-1; } |
108 int maxNodeId() const { return nodes.size()-1; } |
273 |
269 |
274 void clear() { |
270 void clear() { |
275 edges.clear(); |
271 edges.clear(); |
276 nodes.clear(); |
272 nodes.clear(); |
277 first_node = first_free_node = first_free_edge = -1; |
273 first_node = first_free_node = first_free_edge = -1; |
|
274 } |
|
275 |
|
276 protected: |
|
277 void _moveHead(Edge e, Node n) |
|
278 { |
|
279 if(edges[e.id].next_in != -1) |
|
280 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
|
281 if(edges[e.id].prev_in != -1) |
|
282 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
|
283 else nodes[edges[e.id].head].first_in = edges[e.id].next_in; |
|
284 edges[e.id].head = n.id; |
|
285 edges[e.id].prev_in = -1; |
|
286 edges[e.id].next_in = nodes[n.id].first_in; |
|
287 nodes[n.id].first_in = e.id; |
|
288 } |
|
289 void _moveTail(Edge e, Node n) |
|
290 { |
|
291 if(edges[e.id].next_out != -1) |
|
292 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
|
293 if(edges[e.id].prev_out != -1) |
|
294 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
|
295 else nodes[edges[e.id].tail].first_out = edges[e.id].next_out; |
|
296 edges[e.id].tail = n.id; |
|
297 edges[e.id].prev_out = -1; |
|
298 edges[e.id].next_out = nodes[n.id].first_out; |
|
299 nodes[n.id].first_out = e.id; |
278 } |
300 } |
279 |
301 |
280 }; |
302 }; |
281 |
303 |
282 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase; |
304 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase; |
303 public: |
325 public: |
304 /// Moves the head of \c e to \c n |
326 /// Moves the head of \c e to \c n |
305 |
327 |
306 /// Moves the head of \c e to \c n |
328 /// Moves the head of \c e to \c n |
307 /// |
329 /// |
308 void moveHead(Edge e, Node n) |
330 void moveHead(Edge e, Node n) { _moveHead(e,n); } |
309 { |
|
310 if(edges[e.n].next_in != -1) |
|
311 edges[edges[e.n].next_in].prev_in = edges[e.n].prev_in; |
|
312 if(edges[e.n].prev_in != -1) |
|
313 edges[edges[e.n].prev_in].next_in = edges[e.n].next_in; |
|
314 else nodes[edges[e.n].head].first_in = edges[e.n].next_in; |
|
315 edges[e.n].head = n.n; |
|
316 edges[e.n].prev_in = -1; |
|
317 edges[e.n].next_in = nodes[n.n].first_in; |
|
318 nodes[n.n].first_in = e.n; |
|
319 } |
|
320 /// Moves the tail of \c e to \c n |
331 /// Moves the tail of \c e to \c n |
321 |
332 |
322 /// Moves the tail of \c e to \c n |
333 /// Moves the tail of \c e to \c n |
323 /// |
334 /// |
324 void moveTail(Edge e, Node n) |
335 void moveTail(Edge e, Node n) { _moveTail(e,n); } |
325 { |
336 |
326 if(edges[e.n].next_out != -1) |
337 ///Using this it possible to avoid the superfluous memory allocation. |
327 edges[edges[e.n].next_out].prev_out = edges[e.n].prev_out; |
338 ///\todo more docs... |
328 if(edges[e.n].prev_out != -1) |
339 void reserveEdge(int n) { edges.reserve(n); }; |
329 edges[edges[e.n].prev_out].next_out = edges[e.n].next_out; |
340 |
330 else nodes[edges[e.n].tail].first_out = edges[e.n].next_out; |
341 }; |
331 edges[e.n].tail = n.n; |
342 |
332 edges[e.n].prev_out = -1; |
|
333 edges[e.n].next_out = nodes[n.n].first_out; |
|
334 nodes[n.n].first_out = e.n; |
|
335 } |
|
336 } |
|
337 /// @} |
343 /// @} |
338 } //namespace lemon |
344 } //namespace lemon |
339 |
345 |
340 |
346 |
341 #endif |
347 #endif |