287 edges[e.id].target = n.id; |
287 edges[e.id].target = n.id; |
288 edges[e.id].prev_in = -1; |
288 edges[e.id].prev_in = -1; |
289 edges[e.id].next_in = nodes[n.id].first_in; |
289 edges[e.id].next_in = nodes[n.id].first_in; |
290 nodes[n.id].first_in = e.id; |
290 nodes[n.id].first_in = e.id; |
291 } |
291 } |
292 void _changeSource(Edge e, Node n) |
292 void changeSource(Edge e, Node n) |
293 { |
293 { |
294 if(edges[e.id].next_out != -1) |
294 if(edges[e.id].next_out != -1) |
295 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
295 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
296 if(edges[e.id].prev_out != -1) |
296 if(edges[e.id].prev_out != -1) |
297 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
297 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
314 |
314 |
315 ///A list graph class. |
315 ///A list graph class. |
316 |
316 |
317 ///This is a simple and fast erasable graph implementation. |
317 ///This is a simple and fast erasable graph implementation. |
318 /// |
318 /// |
319 ///It conforms to the |
319 ///It conforms to the \ref concept::Graph "Graph" concept and it |
320 ///\ref concept::ErasableGraph "ErasableGraph" concept and |
320 ///also provides several additional useful extra functionalities. |
321 ///it also provides several additional useful extra functionalities. |
321 ///The most of the member functions and nested classes are |
322 ///\sa concept::ErasableGraph. |
322 ///documented only in the concept class. |
|
323 ///\sa concept::Graph. |
323 |
324 |
324 class ListGraph : public ExtendedListGraphBase { |
325 class ListGraph : public ExtendedListGraphBase { |
325 public: |
326 public: |
326 |
327 |
327 typedef ExtendedListGraphBase Parent; |
328 typedef ExtendedListGraphBase Parent; |
|
329 |
|
330 ///Add a new node to the graph. |
|
331 |
|
332 /// \return the new node. |
|
333 /// |
|
334 Node addNode() { return Parent::addNode(); } |
|
335 |
|
336 ///Add a new edge to the graph. |
|
337 |
|
338 ///Add a new edge to the graph with source node \c s |
|
339 ///and target node \c t. |
|
340 ///\return the new edge. |
|
341 Edge addEdge(const Node& s, const Node& t) { |
|
342 return Parent::addEdge(s, t); |
|
343 } |
328 |
344 |
329 /// Changes the target of \c e to \c n |
345 /// Changes the target of \c e to \c n |
330 |
346 |
331 /// Changes the target of \c e to \c n |
347 /// Changes the target of \c e to \c n |
332 /// |
348 /// |
333 ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s |
349 ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s |
334 ///referencing the changed edge remain |
350 ///referencing the changed edge remain |
335 ///valid. However <tt>InEdge</tt>s are invalidated. |
351 ///valid. However <tt>InEdge</tt>s are invalidated. |
336 void changeTarget(Edge e, Node n) { |
352 void changeTarget(Edge e, Node n) { |
337 _changeTarget(e,n); |
353 Parent::changeTarget(e,n); |
338 } |
354 } |
339 /// Changes the source of \c e to \c n |
355 /// Changes the source of \c e to \c n |
340 |
356 |
341 /// Changes the source of \c e to \c n |
357 /// Changes the source of \c e to \c n |
342 /// |
358 /// |
343 ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s |
359 ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s |
344 ///referencing the changed edge remain |
360 ///referencing the changed edge remain |
345 ///valid. However <tt>OutEdge</tt>s are invalidated. |
361 ///valid. However <tt>OutEdge</tt>s are invalidated. |
346 void changeSource(Edge e, Node n) { |
362 void changeSource(Edge e, Node n) { |
347 _changeSource(e,n); |
363 Parent::changeSource(e,n); |
348 } |
364 } |
349 |
365 |
350 /// Invert the direction of an edge. |
366 /// Invert the direction of an edge. |
351 |
367 |
352 ///\note The <tt>Edge</tt>s |
368 ///\note The <tt>Edge</tt>s |
353 ///referencing the changed edge remain |
369 ///referencing the changed edge remain |
354 ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated. |
370 ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated. |
355 void reverseEdge(Edge e) { |
371 void reverseEdge(Edge e) { |
356 Node t=target(e); |
372 Node t=target(e); |
357 _changeTarget(e,source(e)); |
373 changeTarget(e,source(e)); |
358 _changeSource(e,t); |
374 changeSource(e,t); |
359 } |
375 } |
360 |
376 |
361 ///Using this it is possible to avoid the superfluous memory |
377 /// \brief Using this it is possible to avoid the superfluous memory |
362 ///allocation. |
378 /// allocation. |
363 |
379 |
364 ///Using this it is possible to avoid the superfluous memory |
380 ///Using this it is possible to avoid the superfluous memory |
365 ///allocation: if you know that the graph you want to build will |
381 ///allocation: if you know that the graph you want to build will |
366 ///contain at least 10 million nodes then it is worth to reserve |
382 ///contain at least 10 million nodes then it is worth to reserve |
367 ///space for this amount before starting to build the graph. |
383 ///space for this amount before starting to build the graph. |
368 void reserveNode(int n) { nodes.reserve(n); }; |
384 void reserveNode(int n) { nodes.reserve(n); }; |
369 |
385 |
370 ///Using this it is possible to avoid the superfluous memory |
386 /// \brief Using this it is possible to avoid the superfluous memory |
371 ///allocation. |
387 /// allocation. |
372 |
388 |
373 ///Using this it is possible to avoid the superfluous memory |
389 ///Using this it is possible to avoid the superfluous memory |
374 ///allocation: see the \ref reserveNode function. |
390 ///allocation: see the \ref reserveNode function. |
375 void reserveEdge(int n) { edges.reserve(n); }; |
391 void reserveEdge(int n) { edges.reserve(n); }; |
376 |
392 |
596 ///haven't been implemented yet. |
612 ///haven't been implemented yet. |
597 /// |
613 /// |
598 class ListUGraph : public ExtendedListUGraphBase { |
614 class ListUGraph : public ExtendedListUGraphBase { |
599 public: |
615 public: |
600 typedef ExtendedListUGraphBase Parent; |
616 typedef ExtendedListUGraphBase Parent; |
|
617 /// \brief Add a new node to the graph. |
|
618 /// |
|
619 /// \return the new node. |
|
620 /// |
|
621 Node addNode() { return Parent::addNode(); } |
|
622 |
|
623 /// \brief Add a new edge to the graph. |
|
624 /// |
|
625 /// Add a new edge to the graph with source node \c s |
|
626 /// and target node \c t. |
|
627 /// \return the new undirected edge. |
|
628 UEdge addEdge(const Node& s, const Node& t) { |
|
629 return Parent::addEdge(s, t); |
|
630 } |
601 /// \brief Changes the target of \c e to \c n |
631 /// \brief Changes the target of \c e to \c n |
602 /// |
632 /// |
603 /// Changes the target of \c e to \c n |
633 /// Changes the target of \c e to \c n |
604 /// |
634 /// |
605 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
635 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
606 /// referencing the changed edge remain |
636 /// referencing the changed edge remain |
607 /// valid. However <tt>InEdge</tt>'s are invalidated. |
637 /// valid. However <tt>InEdge</tt>'s are invalidated. |
608 void changeTarget(UEdge e, Node n) { |
638 void changeTarget(UEdge e, Node n) { |
609 _changeTarget(e,n); |
639 Parent::changeTarget(e,n); |
610 } |
640 } |
611 /// Changes the source of \c e to \c n |
641 /// Changes the source of \c e to \c n |
612 /// |
642 /// |
613 /// Changes the source of \c e to \c n |
643 /// Changes the source of \c e to \c n |
614 /// |
644 /// |
615 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
645 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
616 ///referencing the changed edge remain |
646 ///referencing the changed edge remain |
617 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
647 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
618 void changeSource(UEdge e, Node n) { |
648 void changeSource(UEdge e, Node n) { |
619 _changeSource(e,n); |
649 Parent::changeSource(e,n); |
620 } |
650 } |
621 /// \brief Contract two nodes. |
651 /// \brief Contract two nodes. |
622 /// |
652 /// |
623 /// This function contracts two nodes. |
653 /// This function contracts two nodes. |
624 /// |
654 /// |