185 |
182 |
186 ///\ingroup graphs |
183 ///\ingroup graphs |
187 /// |
184 /// |
188 ///\brief A smart directed graph class. |
185 ///\brief A smart directed graph class. |
189 /// |
186 /// |
190 ///This is a simple and fast digraph implementation. |
187 ///\ref SmartDigraph is a simple and fast digraph implementation. |
191 ///It is also quite memory efficient, but at the price |
188 ///It is also quite memory efficient but at the price |
192 ///that <b> it does support only limited (only stack-like) |
189 ///that it does not support node and arc deletion |
193 ///node and arc deletions</b>. |
190 ///(except for the Snapshot feature). |
194 ///It fully conforms to the \ref concepts::Digraph "Digraph concept". |
|
195 /// |
191 /// |
196 ///\sa concepts::Digraph. |
192 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" |
|
193 ///and it also provides some additional functionalities. |
|
194 ///Most of its member functions and nested classes are documented |
|
195 ///only in the concept class. |
|
196 /// |
|
197 ///\sa concepts::Digraph |
|
198 ///\sa SmartGraph |
197 class SmartDigraph : public ExtendedSmartDigraphBase { |
199 class SmartDigraph : public ExtendedSmartDigraphBase { |
198 typedef ExtendedSmartDigraphBase Parent; |
200 typedef ExtendedSmartDigraphBase Parent; |
199 |
201 |
200 private: |
202 private: |
201 |
203 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. |
202 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. |
|
203 |
|
204 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. |
|
205 /// |
|
206 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; |
204 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; |
207 ///\brief Assignment of SmartDigraph to another one is \e not allowed. |
205 /// \brief Assignment of a digraph to another one is \e not allowed. |
208 ///Use DigraphCopy() instead. |
206 /// Use DigraphCopy instead. |
209 |
|
210 ///Assignment of SmartDigraph to another one is \e not allowed. |
|
211 ///Use DigraphCopy() instead. |
|
212 void operator=(const SmartDigraph &) {} |
207 void operator=(const SmartDigraph &) {} |
213 |
208 |
214 public: |
209 public: |
215 |
210 |
216 /// Constructor |
211 /// Constructor |
219 /// |
214 /// |
220 SmartDigraph() {}; |
215 SmartDigraph() {}; |
221 |
216 |
222 ///Add a new node to the digraph. |
217 ///Add a new node to the digraph. |
223 |
218 |
224 /// Add a new node to the digraph. |
219 ///This function adds a new node to the digraph. |
225 /// \return The new node. |
220 ///\return The new node. |
226 Node addNode() { return Parent::addNode(); } |
221 Node addNode() { return Parent::addNode(); } |
227 |
222 |
228 ///Add a new arc to the digraph. |
223 ///Add a new arc to the digraph. |
229 |
224 |
230 ///Add a new arc to the digraph with source node \c s |
225 ///This function adds a new arc to the digraph with source node \c s |
231 ///and target node \c t. |
226 ///and target node \c t. |
232 ///\return The new arc. |
227 ///\return The new arc. |
233 Arc addArc(const Node& s, const Node& t) { |
228 Arc addArc(Node s, Node t) { |
234 return Parent::addArc(s, t); |
229 return Parent::addArc(s, t); |
235 } |
230 } |
236 |
231 |
237 /// \brief Using this it is possible to avoid the superfluous memory |
|
238 /// allocation. |
|
239 |
|
240 /// Using this it is possible to avoid the superfluous memory |
|
241 /// allocation: if you know that the digraph you want to build will |
|
242 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
|
243 /// then it is worth reserving space for this amount before starting |
|
244 /// to build the digraph. |
|
245 /// \sa reserveArc |
|
246 void reserveNode(int n) { nodes.reserve(n); }; |
|
247 |
|
248 /// \brief Using this it is possible to avoid the superfluous memory |
|
249 /// allocation. |
|
250 |
|
251 /// Using this it is possible to avoid the superfluous memory |
|
252 /// allocation: if you know that the digraph you want to build will |
|
253 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
|
254 /// then it is worth reserving space for this amount before starting |
|
255 /// to build the digraph. |
|
256 /// \sa reserveNode |
|
257 void reserveArc(int m) { arcs.reserve(m); }; |
|
258 |
|
259 /// \brief Node validity check |
232 /// \brief Node validity check |
260 /// |
233 /// |
261 /// This function gives back true if the given node is valid, |
234 /// This function gives back \c true if the given node is valid, |
262 /// ie. it is a real node of the graph. |
235 /// i.e. it is a real node of the digraph. |
263 /// |
236 /// |
264 /// \warning A removed node (using Snapshot) could become valid again |
237 /// \warning A removed node (using Snapshot) could become valid again |
265 /// when new nodes are added to the graph. |
238 /// if new nodes are added to the digraph. |
266 bool valid(Node n) const { return Parent::valid(n); } |
239 bool valid(Node n) const { return Parent::valid(n); } |
267 |
240 |
268 /// \brief Arc validity check |
241 /// \brief Arc validity check |
269 /// |
242 /// |
270 /// This function gives back true if the given arc is valid, |
243 /// This function gives back \c true if the given arc is valid, |
271 /// ie. it is a real arc of the graph. |
244 /// i.e. it is a real arc of the digraph. |
272 /// |
245 /// |
273 /// \warning A removed arc (using Snapshot) could become valid again |
246 /// \warning A removed arc (using Snapshot) could become valid again |
274 /// when new arcs are added to the graph. |
247 /// if new arcs are added to the graph. |
275 bool valid(Arc a) const { return Parent::valid(a); } |
248 bool valid(Arc a) const { return Parent::valid(a); } |
276 |
249 |
277 ///Clear the digraph. |
|
278 |
|
279 ///Erase all the nodes and arcs from the digraph. |
|
280 /// |
|
281 void clear() { |
|
282 Parent::clear(); |
|
283 } |
|
284 |
|
285 ///Split a node. |
250 ///Split a node. |
286 |
251 |
287 ///This function splits a node. First a new node is added to the digraph, |
252 ///This function splits the given node. First, a new node is added |
288 ///then the source of each outgoing arc of \c n is moved to this new node. |
253 ///to the digraph, then the source of each outgoing arc of node \c n |
289 ///If \c connect is \c true (this is the default value), then a new arc |
254 ///is moved to this new node. |
290 ///from \c n to the newly created node is also added. |
255 ///If the second parameter \c connect is \c true (this is the default |
|
256 ///value), then a new arc from node \c n to the newly created node |
|
257 ///is also added. |
291 ///\return The newly created node. |
258 ///\return The newly created node. |
292 /// |
259 /// |
293 ///\note The <tt>Arc</tt>s |
260 ///\note All iterators remain valid. |
294 ///referencing a moved arc remain |
261 /// |
295 ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s |
|
296 ///may be invalidated. |
|
297 ///\warning This functionality cannot be used together with the Snapshot |
262 ///\warning This functionality cannot be used together with the Snapshot |
298 ///feature. |
263 ///feature. |
299 Node split(Node n, bool connect = true) |
264 Node split(Node n, bool connect = true) |
300 { |
265 { |
301 Node b = addNode(); |
266 Node b = addNode(); |
306 } |
271 } |
307 if(connect) addArc(n,b); |
272 if(connect) addArc(n,b); |
308 return b; |
273 return b; |
309 } |
274 } |
310 |
275 |
|
276 ///Clear the digraph. |
|
277 |
|
278 ///This function erases all nodes and arcs from the digraph. |
|
279 /// |
|
280 void clear() { |
|
281 Parent::clear(); |
|
282 } |
|
283 |
|
284 /// Reserve memory for nodes. |
|
285 |
|
286 /// Using this function, it is possible to avoid superfluous memory |
|
287 /// allocation: if you know that the digraph you want to build will |
|
288 /// be large (e.g. it will contain millions of nodes and/or arcs), |
|
289 /// then it is worth reserving space for this amount before starting |
|
290 /// to build the digraph. |
|
291 /// \sa reserveArc() |
|
292 void reserveNode(int n) { nodes.reserve(n); }; |
|
293 |
|
294 /// Reserve memory for arcs. |
|
295 |
|
296 /// Using this function, it is possible to avoid superfluous memory |
|
297 /// allocation: if you know that the digraph you want to build will |
|
298 /// be large (e.g. it will contain millions of nodes and/or arcs), |
|
299 /// then it is worth reserving space for this amount before starting |
|
300 /// to build the digraph. |
|
301 /// \sa reserveNode() |
|
302 void reserveArc(int m) { arcs.reserve(m); }; |
|
303 |
311 public: |
304 public: |
312 |
305 |
313 class Snapshot; |
306 class Snapshot; |
314 |
307 |
315 protected: |
308 protected: |
330 } |
323 } |
331 } |
324 } |
332 |
325 |
333 public: |
326 public: |
334 |
327 |
335 ///Class to make a snapshot of the digraph and to restrore to it later. |
328 ///Class to make a snapshot of the digraph and to restore it later. |
336 |
329 |
337 ///Class to make a snapshot of the digraph and to restrore to it later. |
330 ///Class to make a snapshot of the digraph and to restore it later. |
338 /// |
331 /// |
339 ///The newly added nodes and arcs can be removed using the |
332 ///The newly added nodes and arcs can be removed using the |
340 ///restore() function. |
333 ///restore() function. This is the only way for deleting nodes and/or |
341 ///\note After you restore a state, you cannot restore |
334 ///arcs from a SmartDigraph structure. |
342 ///a later state, in other word you cannot add again the arcs deleted |
335 /// |
343 ///by restore() using another one Snapshot instance. |
336 ///\note After a state is restored, you cannot restore a later state, |
344 /// |
337 ///i.e. you cannot add the removed nodes and arcs again using |
345 ///\warning If you do not use correctly the snapshot that can cause |
338 ///another Snapshot instance. |
346 ///either broken program, invalid state of the digraph, valid but |
339 /// |
347 ///not the restored digraph or no change. Because the runtime performance |
340 ///\warning Node splitting cannot be restored. |
348 ///the validity of the snapshot is not stored. |
341 ///\warning The validity of the snapshot is not stored due to |
|
342 ///performance reasons. If you do not use the snapshot correctly, |
|
343 ///it can cause broken program, invalid or not restored state of |
|
344 ///the digraph or no change. |
349 class Snapshot |
345 class Snapshot |
350 { |
346 { |
351 SmartDigraph *_graph; |
347 SmartDigraph *_graph; |
352 protected: |
348 protected: |
353 friend class SmartDigraph; |
349 friend class SmartDigraph; |
355 unsigned int arc_num; |
351 unsigned int arc_num; |
356 public: |
352 public: |
357 ///Default constructor. |
353 ///Default constructor. |
358 |
354 |
359 ///Default constructor. |
355 ///Default constructor. |
360 ///To actually make a snapshot you must call save(). |
356 ///You have to call save() to actually make a snapshot. |
361 /// |
|
362 Snapshot() : _graph(0) {} |
357 Snapshot() : _graph(0) {} |
363 ///Constructor that immediately makes a snapshot |
358 ///Constructor that immediately makes a snapshot |
364 |
359 |
365 ///This constructor immediately makes a snapshot of the digraph. |
360 ///This constructor immediately makes a snapshot of the given digraph. |
366 ///\param graph The digraph we make a snapshot of. |
361 /// |
367 Snapshot(SmartDigraph &graph) : _graph(&graph) { |
362 Snapshot(SmartDigraph &gr) : _graph(&gr) { |
368 node_num=_graph->nodes.size(); |
363 node_num=_graph->nodes.size(); |
369 arc_num=_graph->arcs.size(); |
364 arc_num=_graph->arcs.size(); |
370 } |
365 } |
371 |
366 |
372 ///Make a snapshot. |
367 ///Make a snapshot. |
373 |
368 |
374 ///Make a snapshot of the digraph. |
369 ///This function makes a snapshot of the given digraph. |
375 /// |
370 ///It can be called more than once. In case of a repeated |
376 ///This function can be called more than once. In case of a repeated |
|
377 ///call, the previous snapshot gets lost. |
371 ///call, the previous snapshot gets lost. |
378 ///\param graph The digraph we make the snapshot of. |
372 void save(SmartDigraph &gr) { |
379 void save(SmartDigraph &graph) |
373 _graph=&gr; |
380 { |
|
381 _graph=&graph; |
|
382 node_num=_graph->nodes.size(); |
374 node_num=_graph->nodes.size(); |
383 arc_num=_graph->arcs.size(); |
375 arc_num=_graph->arcs.size(); |
384 } |
376 } |
385 |
377 |
386 ///Undo the changes until a snapshot. |
378 ///Undo the changes until a snapshot. |
387 |
379 |
388 ///Undo the changes until a snapshot created by save(). |
380 ///This function undos the changes until the last snapshot |
389 /// |
381 ///created by save() or Snapshot(SmartDigraph&). |
390 ///\note After you restored a state, you cannot restore |
|
391 ///a later state, in other word you cannot add again the arcs deleted |
|
392 ///by restore(). |
|
393 void restore() |
382 void restore() |
394 { |
383 { |
395 _graph->restoreSnapshot(*this); |
384 _graph->restoreSnapshot(*this); |
396 } |
385 } |
397 }; |
386 }; |
619 |
608 |
620 /// \ingroup graphs |
609 /// \ingroup graphs |
621 /// |
610 /// |
622 /// \brief A smart undirected graph class. |
611 /// \brief A smart undirected graph class. |
623 /// |
612 /// |
624 /// This is a simple and fast graph implementation. |
613 /// \ref SmartGraph is a simple and fast graph implementation. |
625 /// It is also quite memory efficient, but at the price |
614 /// It is also quite memory efficient but at the price |
626 /// that <b> it does support only limited (only stack-like) |
615 /// that it does not support node and edge deletion |
627 /// node and arc deletions</b>. |
616 /// (except for the Snapshot feature). |
628 /// It fully conforms to the \ref concepts::Graph "Graph concept". |
|
629 /// |
617 /// |
630 /// \sa concepts::Graph. |
618 /// This type fully conforms to the \ref concepts::Graph "Graph concept" |
|
619 /// and it also provides some additional functionalities. |
|
620 /// Most of its member functions and nested classes are documented |
|
621 /// only in the concept class. |
|
622 /// |
|
623 /// \sa concepts::Graph |
|
624 /// \sa SmartDigraph |
631 class SmartGraph : public ExtendedSmartGraphBase { |
625 class SmartGraph : public ExtendedSmartGraphBase { |
632 typedef ExtendedSmartGraphBase Parent; |
626 typedef ExtendedSmartGraphBase Parent; |
633 |
627 |
634 private: |
628 private: |
635 |
629 /// Graphs are \e not copy constructible. Use GraphCopy instead. |
636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. |
|
637 |
|
638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. |
|
639 /// |
|
640 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; |
630 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; |
641 |
631 /// \brief Assignment of a graph to another one is \e not allowed. |
642 ///\brief Assignment of SmartGraph to another one is \e not allowed. |
632 /// Use GraphCopy instead. |
643 ///Use GraphCopy() instead. |
|
644 |
|
645 ///Assignment of SmartGraph to another one is \e not allowed. |
|
646 ///Use GraphCopy() instead. |
|
647 void operator=(const SmartGraph &) {} |
633 void operator=(const SmartGraph &) {} |
648 |
634 |
649 public: |
635 public: |
650 |
636 |
651 /// Constructor |
637 /// Constructor |
652 |
638 |
653 /// Constructor. |
639 /// Constructor. |
654 /// |
640 /// |
655 SmartGraph() {} |
641 SmartGraph() {} |
656 |
642 |
657 ///Add a new node to the graph. |
643 /// \brief Add a new node to the graph. |
658 |
644 /// |
659 /// Add a new node to the graph. |
645 /// This function adds a new node to the graph. |
660 /// \return The new node. |
646 /// \return The new node. |
661 Node addNode() { return Parent::addNode(); } |
647 Node addNode() { return Parent::addNode(); } |
662 |
648 |
663 ///Add a new edge to the graph. |
649 /// \brief Add a new edge to the graph. |
664 |
650 /// |
665 ///Add a new edge to the graph with node \c s |
651 /// This function adds a new edge to the graph between nodes |
666 ///and \c t. |
652 /// \c u and \c v with inherent orientation from node \c u to |
667 ///\return The new edge. |
653 /// node \c v. |
668 Edge addEdge(const Node& s, const Node& t) { |
654 /// \return The new edge. |
669 return Parent::addEdge(s, t); |
655 Edge addEdge(Node u, Node v) { |
|
656 return Parent::addEdge(u, v); |
670 } |
657 } |
671 |
658 |
672 /// \brief Node validity check |
659 /// \brief Node validity check |
673 /// |
660 /// |
674 /// This function gives back true if the given node is valid, |
661 /// This function gives back \c true if the given node is valid, |
675 /// ie. it is a real node of the graph. |
662 /// i.e. it is a real node of the graph. |
676 /// |
663 /// |
677 /// \warning A removed node (using Snapshot) could become valid again |
664 /// \warning A removed node (using Snapshot) could become valid again |
678 /// when new nodes are added to the graph. |
665 /// if new nodes are added to the graph. |
679 bool valid(Node n) const { return Parent::valid(n); } |
666 bool valid(Node n) const { return Parent::valid(n); } |
680 |
667 |
|
668 /// \brief Edge validity check |
|
669 /// |
|
670 /// This function gives back \c true if the given edge is valid, |
|
671 /// i.e. it is a real edge of the graph. |
|
672 /// |
|
673 /// \warning A removed edge (using Snapshot) could become valid again |
|
674 /// if new edges are added to the graph. |
|
675 bool valid(Edge e) const { return Parent::valid(e); } |
|
676 |
681 /// \brief Arc validity check |
677 /// \brief Arc validity check |
682 /// |
678 /// |
683 /// This function gives back true if the given arc is valid, |
679 /// This function gives back \c true if the given arc is valid, |
684 /// ie. it is a real arc of the graph. |
680 /// i.e. it is a real arc of the graph. |
685 /// |
681 /// |
686 /// \warning A removed arc (using Snapshot) could become valid again |
682 /// \warning A removed arc (using Snapshot) could become valid again |
687 /// when new edges are added to the graph. |
683 /// if new edges are added to the graph. |
688 bool valid(Arc a) const { return Parent::valid(a); } |
684 bool valid(Arc a) const { return Parent::valid(a); } |
689 |
685 |
690 /// \brief Edge validity check |
|
691 /// |
|
692 /// This function gives back true if the given edge is valid, |
|
693 /// ie. it is a real edge of the graph. |
|
694 /// |
|
695 /// \warning A removed edge (using Snapshot) could become valid again |
|
696 /// when new edges are added to the graph. |
|
697 bool valid(Edge e) const { return Parent::valid(e); } |
|
698 |
|
699 ///Clear the graph. |
686 ///Clear the graph. |
700 |
687 |
701 ///Erase all the nodes and edges from the graph. |
688 ///This function erases all nodes and arcs from the graph. |
702 /// |
689 /// |
703 void clear() { |
690 void clear() { |
704 Parent::clear(); |
691 Parent::clear(); |
705 } |
692 } |
706 |
693 |
740 } |
727 } |
741 } |
728 } |
742 |
729 |
743 public: |
730 public: |
744 |
731 |
745 ///Class to make a snapshot of the digraph and to restrore to it later. |
732 ///Class to make a snapshot of the graph and to restore it later. |
746 |
733 |
747 ///Class to make a snapshot of the digraph and to restrore to it later. |
734 ///Class to make a snapshot of the graph and to restore it later. |
748 /// |
735 /// |
749 ///The newly added nodes and arcs can be removed using the |
736 ///The newly added nodes and edges can be removed using the |
750 ///restore() function. |
737 ///restore() function. This is the only way for deleting nodes and/or |
751 /// |
738 ///edges from a SmartGraph structure. |
752 ///\note After you restore a state, you cannot restore |
739 /// |
753 ///a later state, in other word you cannot add again the arcs deleted |
740 ///\note After a state is restored, you cannot restore a later state, |
754 ///by restore() using another one Snapshot instance. |
741 ///i.e. you cannot add the removed nodes and edges again using |
755 /// |
742 ///another Snapshot instance. |
756 ///\warning If you do not use correctly the snapshot that can cause |
743 /// |
757 ///either broken program, invalid state of the digraph, valid but |
744 ///\warning The validity of the snapshot is not stored due to |
758 ///not the restored digraph or no change. Because the runtime performance |
745 ///performance reasons. If you do not use the snapshot correctly, |
759 ///the validity of the snapshot is not stored. |
746 ///it can cause broken program, invalid or not restored state of |
|
747 ///the graph or no change. |
760 class Snapshot |
748 class Snapshot |
761 { |
749 { |
762 SmartGraph *_graph; |
750 SmartGraph *_graph; |
763 protected: |
751 protected: |
764 friend class SmartGraph; |
752 friend class SmartGraph; |
766 unsigned int arc_num; |
754 unsigned int arc_num; |
767 public: |
755 public: |
768 ///Default constructor. |
756 ///Default constructor. |
769 |
757 |
770 ///Default constructor. |
758 ///Default constructor. |
771 ///To actually make a snapshot you must call save(). |
759 ///You have to call save() to actually make a snapshot. |
772 /// |
|
773 Snapshot() : _graph(0) {} |
760 Snapshot() : _graph(0) {} |
774 ///Constructor that immediately makes a snapshot |
761 ///Constructor that immediately makes a snapshot |
775 |
762 |
776 ///This constructor immediately makes a snapshot of the digraph. |
763 /// This constructor immediately makes a snapshot of the given graph. |
777 ///\param graph The digraph we make a snapshot of. |
764 /// |
778 Snapshot(SmartGraph &graph) { |
765 Snapshot(SmartGraph &gr) { |
779 graph.saveSnapshot(*this); |
766 gr.saveSnapshot(*this); |
780 } |
767 } |
781 |
768 |
782 ///Make a snapshot. |
769 ///Make a snapshot. |
783 |
770 |
784 ///Make a snapshot of the graph. |
771 ///This function makes a snapshot of the given graph. |
785 /// |
772 ///It can be called more than once. In case of a repeated |
786 ///This function can be called more than once. In case of a repeated |
|
787 ///call, the previous snapshot gets lost. |
773 ///call, the previous snapshot gets lost. |
788 ///\param graph The digraph we make the snapshot of. |
774 void save(SmartGraph &gr) |
789 void save(SmartGraph &graph) |
|
790 { |
775 { |
791 graph.saveSnapshot(*this); |
776 gr.saveSnapshot(*this); |
792 } |
777 } |
793 |
778 |
794 ///Undo the changes until a snapshot. |
779 ///Undo the changes until the last snapshot. |
795 |
780 |
796 ///Undo the changes until a snapshot created by save(). |
781 ///This function undos the changes until the last snapshot |
797 /// |
782 ///created by save() or Snapshot(SmartGraph&). |
798 ///\note After you restored a state, you cannot restore |
|
799 ///a later state, in other word you cannot add again the arcs deleted |
|
800 ///by restore(). |
|
801 void restore() |
783 void restore() |
802 { |
784 { |
803 _graph->restoreSnapshot(*this); |
785 _graph->restoreSnapshot(*this); |
804 } |
786 } |
805 }; |
787 }; |