Do not append -Wall -W to CXXFLAGS when it is set on the commandline.
3 * lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
6 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
10 * Permission to use, modify and distribute this software is granted
11 * provided that this copyright notice appears in all copies. For
12 * precise terms see the accompanying LICENSE file.
14 * This software is provided "AS IS" with no warranty of any kind,
15 * express or implied, and with no claim as to its suitability for any
20 ///\ingroup graph_concepts
22 ///\brief Undirected graphs and components of.
25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
26 #define LEMON_CONCEPT_UNDIR_GRAPH_H
28 #include <lemon/concept/graph_component.h>
29 #include <lemon/concept/graph.h>
30 #include <lemon/utility.h>
35 // /// Skeleton class which describes an edge with direction in \ref
36 // /// UndirGraph "undirected graph".
37 template <typename UndirGraph>
38 class UndirGraphEdge : public UndirGraph::UndirEdge {
39 typedef typename UndirGraph::UndirEdge UndirEdge;
40 typedef typename UndirGraph::Node Node;
47 UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}
50 UndirGraphEdge(Invalid) {}
52 /// \brief Directed edge from undirected edge and a source node.
54 /// Constructs a directed edge from undirected edge and a source node.
56 /// \note You have to specify the graph for this constructor.
57 UndirGraphEdge(const UndirGraph &g,
58 UndirEdge undir_edge, Node n) {
59 ignore_unused_variable_warning(undir_edge);
60 ignore_unused_variable_warning(g);
61 ignore_unused_variable_warning(n);
65 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
68 bool operator==(UndirGraphEdge) const { return true; }
70 bool operator!=(UndirGraphEdge) const { return false; }
73 bool operator<(UndirGraphEdge) const { return false; }
75 template <typename Edge>
80 void const_constraints() const {
81 /// \bug This should be is_base_and_derived ...
85 Edge e_with_source(graph,ue,n);
86 ignore_unused_variable_warning(e_with_source);
96 struct BaseIterableUndirGraphConcept {
98 template <typename Graph>
101 typedef typename Graph::UndirEdge UndirEdge;
102 typedef typename Graph::Edge Edge;
103 typedef typename Graph::Node Node;
106 checkConcept<BaseIterableGraphComponent, Graph>();
107 checkConcept<GraphItem<>, UndirEdge>();
108 //checkConcept<UndirGraphEdge<Graph>, Edge>();
115 void const_constraints() {
117 n = graph.target(ue);
118 n = graph.source(ue);
119 n = graph.oppositeNode(n0, ue);
122 b = graph.direction(e);
123 Edge e = graph.direct(UndirEdge(), true);
124 e = graph.direct(UndirEdge(), n);
126 ignore_unused_variable_warning(b);
138 struct IterableUndirGraphConcept {
140 template <typename Graph>
143 /// \todo we don't need the iterable component to be base iterable
144 /// Don't we really???
145 //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
147 checkConcept<IterableGraphComponent, Graph> ();
149 typedef typename Graph::UndirEdge UndirEdge;
150 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
151 typedef typename Graph::IncEdgeIt IncEdgeIt;
153 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
154 checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
160 struct MappableUndirGraphConcept {
162 template <typename Graph>
167 Dummy() : value(0) {}
168 Dummy(int _v) : value(_v) {}
172 checkConcept<MappableGraphComponent, Graph>();
174 typedef typename Graph::template UndirEdgeMap<int> IntMap;
175 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
178 typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
179 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
182 typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
183 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
190 struct ExtendableUndirGraphConcept {
192 template <typename Graph>
195 node_a = graph.addNode();
196 uedge = graph.addEdge(node_a, node_b);
198 typename Graph::Node node_a, node_b;
199 typename Graph::UndirEdge uedge;
205 struct ErasableUndirGraphConcept {
207 template <typename Graph>
214 typename Graph::Node n;
215 typename Graph::UndirEdge e;
220 /// \addtogroup graph_concepts
224 /// Class describing the concept of Undirected Graphs.
226 /// This class describes the common interface of all Undirected
229 /// As all concept describing classes it provides only interface
230 /// without any sensible implementation. So any algorithm for
231 /// undirected graph should compile with this class, but it will not
232 /// run properly, of couse.
234 /// In LEMON undirected graphs also fulfill the concept of directed
235 /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
236 /// explanation of this and more see also the page \ref undir_graphs,
237 /// a tutorial about undirected graphs.
239 /// You can assume that all undirected graph can be handled
240 /// as a static directed graph. This way it is fully conform
241 /// to the StaticGraph concept.
247 ///\todo undocumented
249 typedef True UndirTag;
251 /// \brief The base type of node iterators,
252 /// or in other words, the trivial node iterator.
254 /// This is the base type of each node iterator,
255 /// thus each kind of node iterator converts to this.
256 /// More precisely each kind of node iterator should be inherited
257 /// from the trivial node iterator.
260 /// Default constructor
262 /// @warning The default constructor sets the iterator
263 /// to an undefined value.
265 /// Copy constructor.
267 /// Copy constructor.
269 Node(const Node&) { }
271 /// Invalid constructor \& conversion.
273 /// This constructor initializes the iterator to be invalid.
274 /// \sa Invalid for more details.
276 /// Equality operator
278 /// Two iterators are equal if and only if they point to the
279 /// same object or both are invalid.
280 bool operator==(Node) const { return true; }
282 /// Inequality operator
284 /// \sa operator==(Node n)
286 bool operator!=(Node) const { return true; }
288 /// Artificial ordering operator.
290 /// To allow the use of graph descriptors as key type in std::map or
291 /// similar associative container we require this.
293 /// \note This operator only have to define some strict ordering of
294 /// the items; this order has nothing to do with the iteration
295 /// ordering of the items.
297 /// \bug This is a technical requirement. Do we really need this?
298 bool operator<(Node) const { return false; }
302 /// This iterator goes through each node.
304 /// This iterator goes through each node.
305 /// Its usage is quite simple, for example you can count the number
306 /// of nodes in graph \c g of type \c Graph like this:
309 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
311 class NodeIt : public Node {
313 /// Default constructor
315 /// @warning The default constructor sets the iterator
316 /// to an undefined value.
318 /// Copy constructor.
320 /// Copy constructor.
322 NodeIt(const NodeIt& n) : Node(n) { }
323 /// Invalid constructor \& conversion.
325 /// Initialize the iterator to be invalid.
326 /// \sa Invalid for more details.
328 /// Sets the iterator to the first node.
330 /// Sets the iterator to the first node of \c g.
332 NodeIt(const UndirGraph&) { }
333 /// Node -> NodeIt conversion.
335 /// Sets the iterator to the node of \c the graph pointed by
336 /// the trivial iterator.
337 /// This feature necessitates that each time we
338 /// iterate the edge-set, the iteration order is the same.
339 NodeIt(const UndirGraph&, const Node&) { }
342 /// Assign the iterator to the next node.
344 NodeIt& operator++() { return *this; }
348 /// The base type of the undirected edge iterators.
350 /// The base type of the undirected edge iterators.
354 /// Default constructor
356 /// @warning The default constructor sets the iterator
357 /// to an undefined value.
359 /// Copy constructor.
361 /// Copy constructor.
363 UndirEdge(const UndirEdge&) { }
364 /// Initialize the iterator to be invalid.
366 /// Initialize the iterator to be invalid.
368 UndirEdge(Invalid) { }
369 /// Equality operator
371 /// Two iterators are equal if and only if they point to the
372 /// same object or both are invalid.
373 bool operator==(UndirEdge) const { return true; }
374 /// Inequality operator
376 /// \sa operator==(UndirEdge n)
378 bool operator!=(UndirEdge) const { return true; }
380 /// Artificial ordering operator.
382 /// To allow the use of graph descriptors as key type in std::map or
383 /// similar associative container we require this.
385 /// \note This operator only have to define some strict ordering of
386 /// the items; this order has nothing to do with the iteration
387 /// ordering of the items.
389 /// \bug This is a technical requirement. Do we really need this?
390 bool operator<(UndirEdge) const { return false; }
393 /// This iterator goes through each undirected edge.
395 /// This iterator goes through each undirected edge of a graph.
396 /// Its usage is quite simple, for example you can count the number
397 /// of undirected edges in a graph \c g of type \c Graph as follows:
400 /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
402 class UndirEdgeIt : public UndirEdge {
404 /// Default constructor
406 /// @warning The default constructor sets the iterator
407 /// to an undefined value.
409 /// Copy constructor.
411 /// Copy constructor.
413 UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
414 /// Initialize the iterator to be invalid.
416 /// Initialize the iterator to be invalid.
418 UndirEdgeIt(Invalid) { }
419 /// This constructor sets the iterator to the first undirected edge.
421 /// This constructor sets the iterator to the first undirected edge.
422 UndirEdgeIt(const UndirGraph&) { }
423 /// UndirEdge -> UndirEdgeIt conversion
425 /// Sets the iterator to the value of the trivial iterator.
426 /// This feature necessitates that each time we
427 /// iterate the undirected edge-set, the iteration order is the
429 UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
430 /// Next undirected edge
432 /// Assign the iterator to the next undirected edge.
433 UndirEdgeIt& operator++() { return *this; }
436 /// \brief This iterator goes trough the incident undirected
439 /// This iterator goes trough the incident undirected edges
440 /// of a certain node
442 /// Its usage is quite simple, for example you can compute the
443 /// degree (i.e. count the number
444 /// of incident edges of a node \c n
445 /// in graph \c g of type \c Graph as follows.
448 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
450 class IncEdgeIt : public UndirEdge {
452 /// Default constructor
454 /// @warning The default constructor sets the iterator
455 /// to an undefined value.
457 /// Copy constructor.
459 /// Copy constructor.
461 IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
462 /// Initialize the iterator to be invalid.
464 /// Initialize the iterator to be invalid.
466 IncEdgeIt(Invalid) { }
467 /// This constructor sets the iterator to first incident edge.
469 /// This constructor set the iterator to the first incident edge of
471 IncEdgeIt(const UndirGraph&, const Node&) { }
472 /// UndirEdge -> IncEdgeIt conversion
474 /// Sets the iterator to the value of the trivial iterator \c e.
475 /// This feature necessitates that each time we
476 /// iterate the edge-set, the iteration order is the same.
477 IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
478 /// Next incident edge
480 /// Assign the iterator to the next incident edge
481 /// of the corresponding node.
482 IncEdgeIt& operator++() { return *this; }
485 /// The directed edge type.
487 /// The directed edge type. It can be converted to the
489 class Edge : public UndirEdge {
491 /// Default constructor
493 /// @warning The default constructor sets the iterator
494 /// to an undefined value.
496 /// Copy constructor.
498 /// Copy constructor.
500 Edge(const Edge& e) : UndirEdge(e) { }
501 /// Initialize the iterator to be invalid.
503 /// Initialize the iterator to be invalid.
506 /// Equality operator
508 /// Two iterators are equal if and only if they point to the
509 /// same object or both are invalid.
510 bool operator==(Edge) const { return true; }
511 /// Inequality operator
513 /// \sa operator==(Edge n)
515 bool operator!=(Edge) const { return true; }
517 /// Artificial ordering operator.
519 /// To allow the use of graph descriptors as key type in std::map or
520 /// similar associative container we require this.
522 /// \note This operator only have to define some strict ordering of
523 /// the items; this order has nothing to do with the iteration
524 /// ordering of the items.
526 /// \bug This is a technical requirement. Do we really need this?
527 bool operator<(Edge) const { return false; }
530 /// This iterator goes through each directed edge.
532 /// This iterator goes through each edge of a graph.
533 /// Its usage is quite simple, for example you can count the number
534 /// of edges in a graph \c g of type \c Graph as follows:
537 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
539 class EdgeIt : public Edge {
541 /// Default constructor
543 /// @warning The default constructor sets the iterator
544 /// to an undefined value.
546 /// Copy constructor.
548 /// Copy constructor.
550 EdgeIt(const EdgeIt& e) : Edge(e) { }
551 /// Initialize the iterator to be invalid.
553 /// Initialize the iterator to be invalid.
556 /// This constructor sets the iterator to the first edge.
558 /// This constructor sets the iterator to the first edge of \c g.
559 ///@param g the graph
560 EdgeIt(const UndirGraph &g) { ignore_unused_variable_warning(g); }
561 /// Edge -> EdgeIt conversion
563 /// Sets the iterator to the value of the trivial iterator \c e.
564 /// This feature necessitates that each time we
565 /// iterate the edge-set, the iteration order is the same.
566 EdgeIt(const UndirGraph&, const Edge&) { }
569 /// Assign the iterator to the next edge.
570 EdgeIt& operator++() { return *this; }
573 /// This iterator goes trough the outgoing directed edges of a node.
575 /// This iterator goes trough the \e outgoing edges of a certain node
577 /// Its usage is quite simple, for example you can count the number
578 /// of outgoing edges of a node \c n
579 /// in graph \c g of type \c Graph as follows.
582 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
585 class OutEdgeIt : public Edge {
587 /// Default constructor
589 /// @warning The default constructor sets the iterator
590 /// to an undefined value.
592 /// Copy constructor.
594 /// Copy constructor.
596 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
597 /// Initialize the iterator to be invalid.
599 /// Initialize the iterator to be invalid.
601 OutEdgeIt(Invalid) { }
602 /// This constructor sets the iterator to the first outgoing edge.
604 /// This constructor sets the iterator to the first outgoing edge of
607 ///@param g the graph
608 OutEdgeIt(const UndirGraph& n, const Node& g) {
609 ignore_unused_variable_warning(n);
610 ignore_unused_variable_warning(g);
612 /// Edge -> OutEdgeIt conversion
614 /// Sets the iterator to the value of the trivial iterator.
615 /// This feature necessitates that each time we
616 /// iterate the edge-set, the iteration order is the same.
617 OutEdgeIt(const UndirGraph&, const Edge&) { }
618 ///Next outgoing edge
620 /// Assign the iterator to the next
621 /// outgoing edge of the corresponding node.
622 OutEdgeIt& operator++() { return *this; }
625 /// This iterator goes trough the incoming directed edges of a node.
627 /// This iterator goes trough the \e incoming edges of a certain node
629 /// Its usage is quite simple, for example you can count the number
630 /// of outgoing edges of a node \c n
631 /// in graph \c g of type \c Graph as follows.
634 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
637 class InEdgeIt : public Edge {
639 /// Default constructor
641 /// @warning The default constructor sets the iterator
642 /// to an undefined value.
644 /// Copy constructor.
646 /// Copy constructor.
648 InEdgeIt(const InEdgeIt& e) : Edge(e) { }
649 /// Initialize the iterator to be invalid.
651 /// Initialize the iterator to be invalid.
653 InEdgeIt(Invalid) { }
654 /// This constructor sets the iterator to first incoming edge.
656 /// This constructor set the iterator to the first incoming edge of
659 ///@param g the graph
660 InEdgeIt(const UndirGraph& g, const Node& n) {
661 ignore_unused_variable_warning(n);
662 ignore_unused_variable_warning(g);
664 /// Edge -> InEdgeIt conversion
666 /// Sets the iterator to the value of the trivial iterator \c e.
667 /// This feature necessitates that each time we
668 /// iterate the edge-set, the iteration order is the same.
669 InEdgeIt(const UndirGraph&, const Edge&) { }
670 /// Next incoming edge
672 /// Assign the iterator to the next inedge of the corresponding node.
674 InEdgeIt& operator++() { return *this; }
677 /// \brief Read write map of the nodes to type \c T.
679 /// ReadWrite map of the nodes to type \c T.
681 /// \warning Making maps that can handle bool type (NodeMap<bool>)
682 /// needs some extra attention!
683 /// \todo Wrong documentation
685 class NodeMap : public ReadWriteMap< Node, T >
690 NodeMap(const UndirGraph&) { }
692 NodeMap(const UndirGraph&, T) { }
695 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
696 ///Assignment operator
697 NodeMap& operator=(const NodeMap&) { return *this; }
698 // \todo fix this concept
701 /// \brief Read write map of the directed edges to type \c T.
703 /// Reference map of the directed edges to type \c T.
705 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
706 /// needs some extra attention!
707 /// \todo Wrong documentation
709 class EdgeMap : public ReadWriteMap<Edge,T>
714 EdgeMap(const UndirGraph&) { }
716 EdgeMap(const UndirGraph&, T) { }
718 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
719 ///Assignment operator
720 EdgeMap& operator=(const EdgeMap&) { return *this; }
721 // \todo fix this concept
724 /// Read write map of the undirected edges to type \c T.
726 /// Reference map of the edges to type \c T.
728 /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
729 /// needs some extra attention!
730 /// \todo Wrong documentation
732 class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
737 UndirEdgeMap(const UndirGraph&) { }
739 UndirEdgeMap(const UndirGraph&, T) { }
741 UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
742 ///Assignment operator
743 UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
744 // \todo fix this concept
747 /// \brief Direct the given undirected edge.
749 /// Direct the given undirected edge. The returned edge source
750 /// will be the given edge.
751 Edge direct(const UndirEdge&, const Node&) const {
755 /// \brief Direct the given undirected edge.
757 /// Direct the given undirected edge. The returned edge source
758 /// will be the source of the undirected edge if the given bool
760 Edge direct(const UndirEdge&, bool) const {
764 /// \brief Returns true if the edge has default orientation.
766 /// Returns whether the given directed edge is same orientation as
767 /// the corresponding undirected edge.
768 bool direction(Edge) const { return true; }
770 /// \brief Returns the opposite directed edge.
772 /// Returns the opposite directed edge.
773 Edge oppositeEdge(Edge) const { return INVALID; }
775 /// \brief Opposite node on an edge
777 /// \return the opposite of the given Node on the given Edge
778 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
780 /// \brief First node of the undirected edge.
782 /// \return the first node of the given UndirEdge.
784 /// Naturally undirectected edges don't have direction and thus
785 /// don't have source and target node. But we use these two methods
786 /// to query the two endnodes of the edge. The direction of the edge
787 /// which arises this way is called the inherent direction of the
788 /// undirected edge, and is used to define the "default" direction
789 /// of the directed versions of the edges.
791 Node source(UndirEdge) const { return INVALID; }
793 /// \brief Second node of the undirected edge.
794 Node target(UndirEdge) const { return INVALID; }
796 /// \brief Source node of the directed edge.
797 Node source(Edge) const { return INVALID; }
799 /// \brief Target node of the directed edge.
800 Node target(Edge) const { return INVALID; }
802 // /// \brief First node of the graph
804 // /// \note This method is part of so called \ref
805 // /// developpers_interface "Developpers' interface", so it shouldn't
806 // /// be used in an end-user program.
807 void first(Node&) const {}
808 // /// \brief Next node of the graph
810 // /// \note This method is part of so called \ref
811 // /// developpers_interface "Developpers' interface", so it shouldn't
812 // /// be used in an end-user program.
813 void next(Node&) const {}
815 // /// \brief First undirected edge of the graph
817 // /// \note This method is part of so called \ref
818 // /// developpers_interface "Developpers' interface", so it shouldn't
819 // /// be used in an end-user program.
820 void first(UndirEdge&) const {}
821 // /// \brief Next undirected edge of the graph
823 // /// \note This method is part of so called \ref
824 // /// developpers_interface "Developpers' interface", so it shouldn't
825 // /// be used in an end-user program.
826 void next(UndirEdge&) const {}
828 // /// \brief First directed edge of the graph
830 // /// \note This method is part of so called \ref
831 // /// developpers_interface "Developpers' interface", so it shouldn't
832 // /// be used in an end-user program.
833 void first(Edge&) const {}
834 // /// \brief Next directed edge of the graph
836 // /// \note This method is part of so called \ref
837 // /// developpers_interface "Developpers' interface", so it shouldn't
838 // /// be used in an end-user program.
839 void next(Edge&) const {}
841 // /// \brief First outgoing edge from a given node
843 // /// \note This method is part of so called \ref
844 // /// developpers_interface "Developpers' interface", so it shouldn't
845 // /// be used in an end-user program.
846 void firstOut(Edge&, Node) const {}
847 // /// \brief Next outgoing edge to a node
849 // /// \note This method is part of so called \ref
850 // /// developpers_interface "Developpers' interface", so it shouldn't
851 // /// be used in an end-user program.
852 void nextOut(Edge&) const {}
854 // /// \brief First incoming edge to a given node
856 // /// \note This method is part of so called \ref
857 // /// developpers_interface "Developpers' interface", so it shouldn't
858 // /// be used in an end-user program.
859 void firstIn(Edge&, Node) const {}
860 // /// \brief Next incoming edge to a node
862 // /// \note This method is part of so called \ref
863 // /// developpers_interface "Developpers' interface", so it shouldn't
864 // /// be used in an end-user program.
865 void nextIn(Edge&) const {}
868 /// \brief Base node of the iterator
870 /// Returns the base node (the source in this case) of the iterator
871 Node baseNode(OutEdgeIt e) const {
874 /// \brief Running node of the iterator
876 /// Returns the running node (the target in this case) of the
878 Node runningNode(OutEdgeIt e) const {
882 /// \brief Base node of the iterator
884 /// Returns the base node (the target in this case) of the iterator
885 Node baseNode(InEdgeIt e) const {
888 /// \brief Running node of the iterator
890 /// Returns the running node (the source in this case) of the
892 Node runningNode(InEdgeIt e) const {
896 /// \brief Base node of the iterator
898 /// Returns the base node of the iterator
899 Node baseNode(IncEdgeIt) const {
903 /// \brief Running node of the iterator
905 /// Returns the running node of the iterator
906 Node runningNode(IncEdgeIt) const {
910 template <typename Graph>
913 checkConcept<BaseIterableUndirGraphConcept, Graph>();
914 checkConcept<IterableUndirGraphConcept, Graph>();
915 checkConcept<MappableUndirGraphConcept, Graph>();
921 /// \brief An empty non-static undirected graph class.
923 /// This class provides everything that \ref UndirGraph does.
924 /// Additionally it enables building graphs from scratch.
925 class ExtendableUndirGraph : public UndirGraph {
928 /// \brief Add a new node to the graph.
930 /// Add a new node to the graph.
931 /// \return the new node.
934 /// \brief Add a new undirected edge to the graph.
936 /// Add a new undirected edge to the graph.
937 /// \return the new edge.
938 UndirEdge addEdge(const Node& from, const Node& to);
940 /// \brief Resets the graph.
942 /// This function deletes all undirected edges and nodes of the graph.
943 /// It also frees the memory allocated to store them.
946 template <typename Graph>
949 checkConcept<BaseIterableUndirGraphConcept, Graph>();
950 checkConcept<IterableUndirGraphConcept, Graph>();
951 checkConcept<MappableUndirGraphConcept, Graph>();
953 checkConcept<UndirGraph, Graph>();
954 checkConcept<ExtendableUndirGraphConcept, Graph>();
955 checkConcept<ClearableGraphComponent, Graph>();
961 /// \brief An empty erasable undirected graph class.
963 /// This class is an extension of \ref ExtendableUndirGraph. It makes it
964 /// possible to erase undirected edges or nodes.
965 class ErasableUndirGraph : public ExtendableUndirGraph {
968 /// \brief Deletes a node.
973 /// \brief Deletes an undirected edge.
975 /// Deletes an undirected edge.
977 void erase(UndirEdge) { }
979 template <typename Graph>
982 checkConcept<ExtendableUndirGraph, Graph>();
983 checkConcept<ErasableUndirGraphConcept, Graph>();