3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 ///\ingroup graph_concepts
21 ///\brief The concept of the graph components.
24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
27 #include <lemon/bits/invalid.h>
28 #include <lemon/concept/maps.h>
30 #include <lemon/bits/alteration_notifier.h>
35 /// \brief Skeleton class for graph Node and Edge types
37 /// This class describes the interface of Node and Edge (and UEdge
38 /// in undirected graphs) subtypes of graph types.
40 /// \note This class is a template class so that we can use it to
41 /// create graph skeleton classes. The reason for this is than Node
42 /// and Edge types should \em not derive from the same base class.
43 /// For Node you should instantiate it with character 'n' and for Edge
47 template <char _selector = '0'>
51 /// \brief Default constructor.
53 /// \warning The default constructor is not required to set
54 /// the item to some well-defined value. So you should consider it
57 /// \brief Copy constructor.
61 GraphItem(const GraphItem &) {}
62 /// \brief Invalid constructor \& conversion.
64 /// This constructor initializes the item to be invalid.
65 /// \sa Invalid for more details.
67 /// \brief Assign operator for nodes.
69 /// The nodes are assignable.
71 GraphItem& operator=(GraphItem const&) { return *this; }
72 /// \brief Equality operator.
74 /// Two iterators are equal if and only if they represents the
75 /// same node in the graph or both are invalid.
76 bool operator==(GraphItem) const { return false; }
77 /// \brief Inequality operator.
79 /// \sa operator==(const Node& n)
81 bool operator!=(GraphItem) const { return false; }
83 /// \brief Artificial ordering operator.
85 /// To allow the use of graph descriptors as key type in std::map or
86 /// similar associative container we require this.
88 /// \note This operator only have to define some strict ordering of
89 /// the items; this order has nothing to do with the iteration
90 /// ordering of the items.
91 bool operator<(GraphItem) const { return false; }
93 template<typename _GraphItem>
98 _GraphItem i3 = INVALID;
103 // b = (ia == ib) && (ia != ib) && (ia < ib);
104 b = (ia == ib) && (ia != ib);
105 b = (ia == INVALID) && (ib != INVALID);
109 const _GraphItem &ia;
110 const _GraphItem &ib;
114 /// \brief An empty base graph class.
116 /// This class provides the minimal set of features needed for a graph
117 /// structure. All graph concepts have to be conform to this base
118 /// graph. It just provides types for nodes and edges and functions to
119 /// get the source and the target of the edges.
120 class BaseGraphComponent {
123 typedef BaseGraphComponent Graph;
125 /// \brief Node class of the graph.
127 /// This class represents the Nodes of the graph.
129 typedef GraphItem<'n'> Node;
131 /// \brief Edge class of the graph.
133 /// This class represents the Edges of the graph.
135 typedef GraphItem<'e'> Edge;
137 /// \brief Gives back the target node of an edge.
139 /// Gives back the target node of an edge.
141 Node target(const Edge&) const { return INVALID;}
143 /// \brief Gives back the source node of an edge.
145 /// Gives back the source node of an edge.
147 Node source(const Edge&) const { return INVALID;}
149 /// \brief Gives back the opposite node on the given edge.
151 /// Gives back the opposite node on the given edge.
152 Node oppositeNode(const Node&, const Edge&) const {
156 template <typename _Graph>
158 typedef typename _Graph::Node Node;
159 typedef typename _Graph::Edge Edge;
162 checkConcept<GraphItem<'n'>, Node>();
163 checkConcept<GraphItem<'e'>, Edge>();
169 n = graph.oppositeNode(n, e);
177 /// \brief An empty base undirected graph class.
179 /// This class provides the minimal set of features needed for an
180 /// undirected graph structure. All undirected graph concepts have
181 /// to be conform to this base graph. It just provides types for
182 /// nodes, edges and undirected edges and functions to get the
183 /// source and the target of the edges and undirected edges,
184 /// conversion from edges to undirected edges and function to get
185 /// both direction of the undirected edges.
186 class BaseUGraphComponent : public BaseGraphComponent {
188 typedef BaseGraphComponent::Node Node;
189 typedef BaseGraphComponent::Edge Edge;
190 /// \brief Undirected edge class of the graph.
192 /// This class represents the undirected edges of the graph.
193 /// The undirected graphs can be used as a directed graph which
194 /// for each edge contains the opposite edge too so the graph is
195 /// bidirected. The undirected edge represents two opposite
197 class UEdge : public GraphItem<'u'> {
199 typedef GraphItem<'u'> Parent;
200 /// \brief Default constructor.
202 /// \warning The default constructor is not required to set
203 /// the item to some well-defined value. So you should consider it
204 /// as uninitialized.
206 /// \brief Copy constructor.
208 /// Copy constructor.
210 UEdge(const UEdge &) : Parent() {}
211 /// \brief Invalid constructor \& conversion.
213 /// This constructor initializes the item to be invalid.
214 /// \sa Invalid for more details.
216 /// \brief Converter from edge to undirected edge.
218 /// Besides the core graph item functionality each edge should
219 /// be convertible to the represented undirected edge.
220 UEdge(const Edge&) {}
223 /// \brief Returns the direction of the edge.
225 /// Returns the direction of the edge. Each edge represents an
226 /// undirected edge with a direction. It gives back the
228 bool direction(const Edge&) const { return true; }
230 /// \brief Returns the directed edge.
232 /// Returns the directed edge from its direction and the
233 /// represented undirected edge.
234 Edge direct(const UEdge&, bool) const { return INVALID;}
236 /// \brief Returns the directed edge.
238 /// Returns the directed edge from its source and the
239 /// represented undirected edge.
240 Edge direct(const UEdge&, const Node&) const { return INVALID;}
242 /// \brief Returns the opposite edge.
244 /// Returns the opposite edge. It is the edge representing the
245 /// same undirected edge and has opposite direction.
246 Edge oppositeEdge(const Edge&) const { return INVALID;}
248 /// \brief Gives back the target node of an undirected edge.
250 /// Gives back the target node of an undirected edge. The name
251 /// target is a little confusing because the undirected edge
252 /// does not have target but it just means that one of the end
254 Node target(const UEdge&) const { return INVALID;}
256 /// \brief Gives back the source node of an undirected edge.
258 /// Gives back the source node of an undirected edge. The name
259 /// source is a little confusing because the undirected edge
260 /// does not have source but it just means that one of the end
262 Node source(const UEdge&) const { return INVALID;}
264 template <typename _Graph>
266 typedef typename _Graph::Node Node;
267 typedef typename _Graph::Edge Edge;
268 typedef typename _Graph::UEdge UEdge;
271 checkConcept<BaseGraphComponent, _Graph>();
272 checkConcept<GraphItem<'u'>, UEdge>();
277 n = graph.source(ue);
278 n = graph.target(ue);
279 e = graph.direct(ue, true);
280 e = graph.direct(ue, n);
281 e = graph.oppositeEdge(e);
283 bool d = graph.direction(e);
284 ignore_unused_variable_warning(d);
293 /// \brief An empty iterable base graph class.
295 /// This class provides beside the core graph features
296 /// core iterable interface for the graph structure.
297 /// Most of the base graphs should be conform to this concept.
298 template <typename _Base = BaseGraphComponent>
299 class BaseIterableGraphComponent : public _Base {
303 typedef typename Base::Node Node;
304 typedef typename Base::Edge Edge;
306 /// \brief Gives back the first node in the iterating order.
308 /// Gives back the first node in the iterating order.
310 void first(Node&) const {}
312 /// \brief Gives back the next node in the iterating order.
314 /// Gives back the next node in the iterating order.
316 void next(Node&) const {}
318 /// \brief Gives back the first edge in the iterating order.
320 /// Gives back the first edge in the iterating order.
322 void first(Edge&) const {}
324 /// \brief Gives back the next edge in the iterating order.
326 /// Gives back the next edge in the iterating order.
328 void next(Edge&) const {}
331 /// \brief Gives back the first of the edges point to the given
334 /// Gives back the first of the edges point to the given node.
336 void firstIn(Edge&, const Node&) const {}
338 /// \brief Gives back the next of the edges points to the given
341 /// Gives back the next of the edges points to the given node.
343 void nextIn(Edge&) const {}
345 /// \brief Gives back the first of the edges start from the
348 /// Gives back the first of the edges start from the given node.
350 void firstOut(Edge&, const Node&) const {}
352 /// \brief Gives back the next of the edges start from the given
355 /// Gives back the next of the edges start from the given node.
357 void nextOut(Edge&) const {}
360 template <typename _Graph>
364 checkConcept< BaseGraphComponent, _Graph >();
365 typename _Graph::Node node;
366 typename _Graph::Edge edge;
376 graph.firstIn(edge, node);
380 graph.firstOut(edge, node);
389 /// \brief An empty iterable base undirected graph class.
391 /// This class provides beside the core undirceted graph features
392 /// core iterable interface for the undirected graph structure.
393 /// Most of the base undirected graphs should be conform to this
395 template <typename _Base = BaseUGraphComponent>
396 class BaseIterableUGraphComponent
397 : public BaseIterableGraphComponent<_Base> {
401 typedef typename Base::UEdge UEdge;
402 typedef typename Base::Node Node;
404 using BaseIterableGraphComponent<_Base>::first;
405 using BaseIterableGraphComponent<_Base>::next;
407 /// \brief Gives back the first undirected edge in the iterating
410 /// Gives back the first undirected edge in the iterating order.
412 void first(UEdge&) const {}
414 /// \brief Gives back the next undirected edge in the iterating
417 /// Gives back the next undirected edge in the iterating order.
419 void next(UEdge&) const {}
422 /// \brief Gives back the first of the undirected edges from the
425 /// Gives back the first of the undirected edges from the given
426 /// node. The bool parameter gives back that direction which
427 /// gives a good direction of the uedge so the source of the
428 /// directed edge is the given node.
429 void firstInc(UEdge&, bool&, const Node&) const {}
431 /// \brief Gives back the next of the undirected edges from the
434 /// Gives back the next of the undirected edges from the given
435 /// node. The bool parameter should be used as the \c firstInc()
437 void nextInc(UEdge&, bool&) const {}
439 template <typename _Graph>
443 checkConcept<Base, _Graph >();
444 checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
445 typename _Graph::Node node;
446 typename _Graph::UEdge uedge;
453 graph.firstInc(uedge, dir, node);
454 graph.nextInc(uedge, dir);
462 /// \brief An empty idable base graph class.
464 /// This class provides beside the core graph features
465 /// core id functions for the graph structure.
466 /// The most of the base graphs should be conform to this concept.
467 /// The id's are unique and immutable.
468 template <typename _Base = BaseGraphComponent>
469 class IDableGraphComponent : public _Base {
473 typedef typename Base::Node Node;
474 typedef typename Base::Edge Edge;
476 /// \brief Gives back an unique integer id for the Node.
478 /// Gives back an unique integer id for the Node.
480 int id(const Node&) const { return -1;}
482 /// \brief Gives back the node by the unique id.
484 /// Gives back the node by the unique id.
485 /// If the graph does not contain node with the given id
486 /// then the result of the function is undetermined.
487 Node nodeFromId(int) const { return INVALID;}
489 /// \brief Gives back an unique integer id for the Edge.
491 /// Gives back an unique integer id for the Edge.
493 int id(const Edge&) const { return -1;}
495 /// \brief Gives back the edge by the unique id.
497 /// Gives back the edge by the unique id.
498 /// If the graph does not contain edge with the given id
499 /// then the result of the function is undetermined.
500 Edge edgeFromId(int) const { return INVALID;}
502 /// \brief Gives back an integer greater or equal to the maximum
505 /// Gives back an integer greater or equal to the maximum Node
507 int maxNodeId() const { return -1;}
509 /// \brief Gives back an integer greater or equal to the maximum
512 /// Gives back an integer greater or equal to the maximum Edge
514 int maxEdgeId() const { return -1;}
516 template <typename _Graph>
520 checkConcept< BaseGraphComponent, _Graph >();
521 typename _Graph::Node node;
522 int nid = graph.id(node);
523 nid = graph.id(node);
524 node = graph.nodeFromId(nid);
525 typename _Graph::Edge edge;
526 int eid = graph.id(edge);
527 eid = graph.id(edge);
528 edge = graph.edgeFromId(eid);
530 nid = graph.maxNodeId();
531 ignore_unused_variable_warning(nid);
532 eid = graph.maxEdgeId();
533 ignore_unused_variable_warning(eid);
540 /// \brief An empty idable base undirected graph class.
542 /// This class provides beside the core undirected graph features
543 /// core id functions for the undirected graph structure. The
544 /// most of the base undirected graphs should be conform to this
545 /// concept. The id's are unique and immutable.
546 template <typename _Base = BaseUGraphComponent>
547 class IDableUGraphComponent : public IDableGraphComponent<_Base> {
551 typedef typename Base::UEdge UEdge;
553 using IDableGraphComponent<_Base>::id;
555 /// \brief Gives back an unique integer id for the UEdge.
557 /// Gives back an unique integer id for the UEdge.
559 int id(const UEdge&) const { return -1;}
561 /// \brief Gives back the undirected edge by the unique id.
563 /// Gives back the undirected edge by the unique id. If the
564 /// graph does not contain edge with the given id then the
565 /// result of the function is undetermined.
566 UEdge uEdgeFromId(int) const { return INVALID;}
568 /// \brief Gives back an integer greater or equal to the maximum
571 /// Gives back an integer greater or equal to the maximum UEdge
573 int maxUEdgeId() const { return -1;}
575 template <typename _Graph>
579 checkConcept<Base, _Graph >();
580 checkConcept<IDableGraphComponent<Base>, _Graph >();
581 typename _Graph::UEdge uedge;
582 int ueid = graph.id(uedge);
583 ueid = graph.id(uedge);
584 uedge = graph.uEdgeFromId(ueid);
585 ueid = graph.maxUEdgeId();
586 ignore_unused_variable_warning(ueid);
593 /// \brief An empty extendable base graph class.
595 /// This class provides beside the core graph features
596 /// core graph extend interface for the graph structure.
597 /// The most of the base graphs should be conform to this concept.
598 template <typename _Base = BaseGraphComponent>
599 class BaseExtendableGraphComponent : public _Base {
602 typedef typename _Base::Node Node;
603 typedef typename _Base::Edge Edge;
605 /// \brief Adds a new node to the graph.
607 /// Adds a new node to the graph.
613 /// \brief Adds a new edge connects the given two nodes.
615 /// Adds a new edge connects the the given two nodes.
616 Edge addEdge(const Node&, const Node&) {
620 template <typename _Graph>
623 typename _Graph::Node node_a, node_b;
624 node_a = graph.addNode();
625 node_b = graph.addNode();
626 typename _Graph::Edge edge;
627 edge = graph.addEdge(node_a, node_b);
634 /// \brief An empty extendable base undirected graph class.
636 /// This class provides beside the core undirected graph features
637 /// core undircted graph extend interface for the graph structure.
638 /// The most of the base graphs should be conform to this concept.
639 template <typename _Base = BaseUGraphComponent>
640 class BaseExtendableUGraphComponent : public _Base {
643 typedef typename _Base::Node Node;
644 typedef typename _Base::UEdge UEdge;
646 /// \brief Adds a new node to the graph.
648 /// Adds a new node to the graph.
654 /// \brief Adds a new edge connects the given two nodes.
656 /// Adds a new edge connects the the given two nodes.
657 UEdge addEdge(const Node&, const Node&) {
661 template <typename _Graph>
664 typename _Graph::Node node_a, node_b;
665 node_a = graph.addNode();
666 node_b = graph.addNode();
667 typename _Graph::UEdge uedge;
668 uedge = graph.addUEdge(node_a, node_b);
675 /// \brief An empty erasable base graph class.
677 /// This class provides beside the core graph features
678 /// core erase functions for the graph structure.
679 /// The most of the base graphs should be conform to this concept.
680 template <typename _Base = BaseGraphComponent>
681 class BaseErasableGraphComponent : public _Base {
685 typedef typename Base::Node Node;
686 typedef typename Base::Edge Edge;
688 /// \brief Erase a node from the graph.
690 /// Erase a node from the graph. This function should not
691 /// erase edges connecting to the Node.
692 void erase(const Node&) {}
694 /// \brief Erase an edge from the graph.
696 /// Erase an edge from the graph.
698 void erase(const Edge&) {}
700 template <typename _Graph>
703 typename _Graph::Node node;
705 typename _Graph::Edge edge;
713 /// \brief An empty erasable base undirected graph class.
715 /// This class provides beside the core undirected graph features
716 /// core erase functions for the undirceted graph structure.
717 template <typename _Base = BaseUGraphComponent>
718 class BaseErasableUGraphComponent : public _Base {
722 typedef typename Base::Node Node;
723 typedef typename Base::UEdge UEdge;
725 /// \brief Erase a node from the graph.
727 /// Erase a node from the graph. This function should not
728 /// erase edges connecting to the Node.
729 void erase(const Node&) {}
731 /// \brief Erase an edge from the graph.
733 /// Erase an edge from the graph.
735 void erase(const UEdge&) {}
737 template <typename _Graph>
740 typename _Graph::Node node;
742 typename _Graph::Edge edge;
750 /// \brief An empty clearable base graph class.
752 /// This class provides beside the core graph features
753 /// core clear functions for the graph structure.
754 /// The most of the base graphs should be conform to this concept.
755 template <typename _Base = BaseGraphComponent>
756 class BaseClearableGraphComponent : public _Base {
759 /// \brief Erase all the nodes and edges from the graph.
761 /// Erase all the nodes and edges from the graph.
765 template <typename _Graph>
775 /// \brief An empty clearable base undirected graph class.
777 /// This class provides beside the core undirected graph features
778 /// core clear functions for the undirected graph structure.
779 /// The most of the base graphs should be conform to this concept.
780 template <typename _Base = BaseUGraphComponent>
781 class BaseClearableUGraphComponent : public _Base {
784 /// \brief Erase all the nodes and undirected edges from the graph.
786 /// Erase all the nodes and undirected edges from the graph.
790 template <typename _Graph>
801 /// \brief Skeleton class for graph NodeIt and EdgeIt
803 /// Skeleton class for graph NodeIt and EdgeIt.
805 template <typename _Graph, typename _Item>
806 class GraphItemIt : public _Item {
808 /// \brief Default constructor.
810 /// @warning The default constructor sets the iterator
811 /// to an undefined value.
813 /// \brief Copy constructor.
815 /// Copy constructor.
817 GraphItemIt(const GraphItemIt& ) {}
818 /// \brief Sets the iterator to the first item.
820 /// Sets the iterator to the first item of \c the graph.
822 explicit GraphItemIt(const _Graph&) {}
823 /// \brief Invalid constructor \& conversion.
825 /// This constructor initializes the item to be invalid.
826 /// \sa Invalid for more details.
827 GraphItemIt(Invalid) {}
828 /// \brief Assign operator for items.
830 /// The items are assignable.
832 GraphItemIt& operator=(const GraphItemIt&) { return *this; }
833 /// \brief Next item.
835 /// Assign the iterator to the next item.
837 GraphItemIt& operator++() { return *this; }
838 /// \brief Equality operator
840 /// Two iterators are equal if and only if they point to the
841 /// same object or both are invalid.
842 bool operator==(const GraphItemIt&) const { return true;}
843 /// \brief Inequality operator
845 /// \sa operator==(Node n)
847 bool operator!=(const GraphItemIt&) const { return true;}
849 template<typename _GraphItemIt>
866 /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
868 /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
869 /// base class, the _selector is a additional template parameter. For
870 /// InEdgeIt you should instantiate it with character 'i' and for
871 /// OutEdgeIt with 'o'.
872 template <typename _Graph,
873 typename _Item = typename _Graph::Edge,
874 typename _Base = typename _Graph::Node,
875 char _selector = '0'>
876 class GraphIncIt : public _Item {
878 /// \brief Default constructor.
880 /// @warning The default constructor sets the iterator
881 /// to an undefined value.
883 /// \brief Copy constructor.
885 /// Copy constructor.
887 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
888 /// \brief Sets the iterator to the first edge incoming into or outgoing
891 /// Sets the iterator to the first edge incoming into or outgoing
894 explicit GraphIncIt(const _Graph&, const _Base&) {}
895 /// \brief Invalid constructor \& conversion.
897 /// This constructor initializes the item to be invalid.
898 /// \sa Invalid for more details.
899 GraphIncIt(Invalid) {}
900 /// \brief Assign operator for iterators.
902 /// The iterators are assignable.
904 GraphIncIt& operator=(GraphIncIt const&) { return *this; }
905 /// \brief Next item.
907 /// Assign the iterator to the next item.
909 GraphIncIt& operator++() { return *this; }
911 /// \brief Equality operator
913 /// Two iterators are equal if and only if they point to the
914 /// same object or both are invalid.
915 bool operator==(const GraphIncIt&) const { return true;}
917 /// \brief Inequality operator
919 /// \sa operator==(Node n)
921 bool operator!=(const GraphIncIt&) const { return true;}
923 template <typename _GraphIncIt>
926 checkConcept<GraphItem<_selector>, _GraphIncIt>();
927 _GraphIncIt it1(graph, node);
946 /// \brief An empty iterable graph class.
948 /// This class provides beside the core graph features
949 /// iterator based iterable interface for the graph structure.
950 /// This concept is part of the GraphConcept.
951 template <typename _Base = BaseGraphComponent>
952 class IterableGraphComponent : public _Base {
957 typedef typename Base::Node Node;
958 typedef typename Base::Edge Edge;
960 typedef IterableGraphComponent Graph;
963 /// \brief This iterator goes through each node.
965 /// This iterator goes through each node.
967 typedef GraphItemIt<Graph, Node> NodeIt;
969 /// \brief This iterator goes through each node.
971 /// This iterator goes through each node.
973 typedef GraphItemIt<Graph, Edge> EdgeIt;
975 /// \brief This iterator goes trough the incoming edges of a node.
977 /// This iterator goes trough the \e inccoming edges of a certain node
979 typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
981 /// \brief This iterator goes trough the outgoing edges of a node.
983 /// This iterator goes trough the \e outgoing edges of a certain node
985 typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
987 /// \brief The base node of the iterator.
989 /// Gives back the base node of the iterator.
990 /// It is always the target of the pointed edge.
991 Node baseNode(const InEdgeIt&) const { return INVALID; }
993 /// \brief The running node of the iterator.
995 /// Gives back the running node of the iterator.
996 /// It is always the source of the pointed edge.
997 Node runningNode(const InEdgeIt&) const { return INVALID; }
999 /// \brief The base node of the iterator.
1001 /// Gives back the base node of the iterator.
1002 /// It is always the source of the pointed edge.
1003 Node baseNode(const OutEdgeIt&) const { return INVALID; }
1005 /// \brief The running node of the iterator.
1007 /// Gives back the running node of the iterator.
1008 /// It is always the target of the pointed edge.
1009 Node runningNode(const OutEdgeIt&) const { return INVALID; }
1011 /// \brief The opposite node on the given edge.
1013 /// Gives back the opposite on the given edge.
1014 /// \todo It should not be here.
1015 Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
1018 template <typename _Graph>
1019 struct Constraints {
1020 void constraints() {
1021 checkConcept<Base, _Graph>();
1023 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1024 typename _Graph::EdgeIt >();
1025 checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
1026 typename _Graph::NodeIt >();
1027 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1028 typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
1029 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1030 typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
1032 typename _Graph::Node n;
1033 typename _Graph::InEdgeIt ieit(INVALID);
1034 typename _Graph::OutEdgeIt oeit(INVALID);
1035 n = graph.baseNode(ieit);
1036 n = graph.runningNode(ieit);
1037 n = graph.baseNode(oeit);
1038 n = graph.runningNode(oeit);
1039 ignore_unused_variable_warning(n);
1042 const _Graph& graph;
1047 /// \brief An empty iterable undirected graph class.
1049 /// This class provides beside the core graph features iterator
1050 /// based iterable interface for the undirected graph structure.
1051 /// This concept is part of the GraphConcept.
1052 template <typename _Base = BaseUGraphComponent>
1053 class IterableUGraphComponent : public IterableGraphComponent<_Base> {
1057 typedef typename Base::Node Node;
1058 typedef typename Base::Edge Edge;
1059 typedef typename Base::UEdge UEdge;
1062 typedef IterableUGraphComponent Graph;
1063 using IterableGraphComponent<_Base>::baseNode;
1064 using IterableGraphComponent<_Base>::runningNode;
1067 /// \brief This iterator goes through each node.
1069 /// This iterator goes through each node.
1070 typedef GraphItemIt<Graph, UEdge> UEdgeIt;
1071 /// \brief This iterator goes trough the incident edges of a
1074 /// This iterator goes trough the incident edges of a certain
1075 /// node of a graph.
1076 typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
1077 /// \brief The base node of the iterator.
1079 /// Gives back the base node of the iterator.
1080 Node baseNode(const IncEdgeIt&) const { return INVALID; }
1082 /// \brief The running node of the iterator.
1084 /// Gives back the running node of the iterator.
1085 Node runningNode(const IncEdgeIt&) const { return INVALID; }
1087 template <typename _Graph>
1088 struct Constraints {
1089 void constraints() {
1090 checkConcept<Base, _Graph>();
1091 checkConcept<IterableGraphComponent<Base>, _Graph>();
1093 checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
1094 typename _Graph::UEdgeIt >();
1095 checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
1096 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
1098 typename _Graph::Node n;
1099 typename _Graph::IncEdgeIt ueit(INVALID);
1100 n = graph.baseNode(ueit);
1101 n = graph.runningNode(ueit);
1104 const _Graph& graph;
1109 /// \brief An empty alteration notifier graph class.
1111 /// This class provides beside the core graph features alteration
1112 /// notifier interface for the graph structure. This implements
1113 /// an observer-notifier pattern for each graph item. More
1114 /// obsevers can be registered into the notifier and whenever an
1115 /// alteration occured in the graph all the observers will
1116 /// notified about it.
1117 template <typename _Base = BaseGraphComponent>
1118 class AlterableGraphComponent : public _Base {
1122 typedef typename Base::Node Node;
1123 typedef typename Base::Edge Edge;
1126 /// The node observer registry.
1127 typedef AlterationNotifier<AlterableGraphComponent, Node>
1129 /// The edge observer registry.
1130 typedef AlterationNotifier<AlterableGraphComponent, Edge>
1133 /// \brief Gives back the node alteration notifier.
1135 /// Gives back the node alteration notifier.
1136 NodeNotifier& getNotifier(Node) const {
1137 return NodeNotifier();
1140 /// \brief Gives back the edge alteration notifier.
1142 /// Gives back the edge alteration notifier.
1143 EdgeNotifier& getNotifier(Edge) const {
1144 return EdgeNotifier();
1147 template <typename _Graph>
1148 struct Constraints {
1149 void constraints() {
1150 checkConcept<Base, _Graph>();
1151 typename _Graph::NodeNotifier& nn
1152 = graph.getNotifier(typename _Graph::Node());
1154 typename _Graph::EdgeNotifier& en
1155 = graph.getNotifier(typename _Graph::Edge());
1157 ignore_unused_variable_warning(nn);
1158 ignore_unused_variable_warning(en);
1161 const _Graph& graph;
1167 /// \brief An empty alteration notifier undirected graph class.
1169 /// This class provides beside the core graph features alteration
1170 /// notifier interface for the graph structure. This implements
1171 /// an observer-notifier pattern for each graph item. More
1172 /// obsevers can be registered into the notifier and whenever an
1173 /// alteration occured in the graph all the observers will
1174 /// notified about it.
1175 template <typename _Base = BaseUGraphComponent>
1176 class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
1180 typedef typename Base::UEdge UEdge;
1183 /// The edge observer registry.
1184 typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
1187 /// \brief Gives back the edge alteration notifier.
1189 /// Gives back the edge alteration notifier.
1190 UEdgeNotifier& getNotifier(UEdge) const {
1191 return UEdgeNotifier();
1194 template <typename _Graph>
1195 struct Constraints {
1196 void constraints() {
1197 checkConcept<Base, _Graph>();
1198 checkConcept<AlterableGraphComponent, _Graph>();
1199 typename _Graph::UEdgeNotifier& uen
1200 = graph.getNotifier(typename _Graph::UEdge());
1201 ignore_unused_variable_warning(uen);
1204 const _Graph& graph;
1211 /// \brief Class describing the concept of graph maps
1213 /// This class describes the common interface of the graph maps
1214 /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
1215 /// associate data to graph descriptors (nodes or edges).
1216 template <typename _Graph, typename _Item, typename _Value>
1217 class GraphMap : public ReadWriteMap<_Item, _Value> {
1220 typedef ReadWriteMap<_Item, _Value> Parent;
1222 /// The graph type of the map.
1223 typedef _Graph Graph;
1224 /// The key type of the map.
1226 /// The value type of the map.
1227 typedef _Value Value;
1229 /// \brief Construct a new map.
1231 /// Construct a new map for the graph.
1232 explicit GraphMap(const Graph&) {}
1233 /// \brief Construct a new map with default value.
1235 /// Construct a new map for the graph and initalise the values.
1236 GraphMap(const Graph&, const Value&) {}
1237 /// \brief Copy constructor.
1239 /// Copy Constructor.
1240 GraphMap(const GraphMap&) : Parent() {}
1242 /// \brief Assign operator.
1244 /// Assign operator. It does not mofify the underlying graph,
1245 /// it just iterates on the current item set and set the map
1246 /// with the value returned by the assigned map.
1247 template <typename CMap>
1248 GraphMap& operator=(const CMap&) {
1249 checkConcept<ReadMap<Key, Value>, CMap>();
1253 template<typename _Map>
1254 struct Constraints {
1255 void constraints() {
1256 checkConcept<ReadWriteMap<Key, Value>, _Map >();
1257 // Construction with a graph parameter
1259 // Constructor with a graph and a default value parameter
1261 // Copy constructor.
1264 ReadMap<Key, Value> cmap;
1267 ignore_unused_variable_warning(a2);
1268 ignore_unused_variable_warning(b);
1273 const typename GraphMap::Value &t;
1278 /// \brief An empty mappable graph class.
1280 /// This class provides beside the core graph features
1281 /// map interface for the graph structure.
1282 /// This concept is part of the Graph concept.
1283 template <typename _Base = BaseGraphComponent>
1284 class MappableGraphComponent : public _Base {
1288 typedef typename Base::Node Node;
1289 typedef typename Base::Edge Edge;
1291 typedef MappableGraphComponent Graph;
1293 /// \brief ReadWrite map of the nodes.
1295 /// ReadWrite map of the nodes.
1297 template <typename Value>
1298 class NodeMap : public GraphMap<Graph, Node, Value> {
1302 typedef GraphMap<Graph, Node, Value> Parent;
1304 /// \brief Construct a new map.
1306 /// Construct a new map for the graph.
1307 /// \todo call the right parent class constructor
1308 explicit NodeMap(const Graph& graph) : Parent(graph) {}
1310 /// \brief Construct a new map with default value.
1312 /// Construct a new map for the graph and initalise the values.
1313 NodeMap(const Graph& graph, const Value& value)
1314 : Parent(graph, value) {}
1316 /// \brief Copy constructor.
1318 /// Copy Constructor.
1319 NodeMap(const NodeMap& nm) : Parent(nm) {}
1321 /// \brief Assign operator.
1323 /// Assign operator.
1324 template <typename CMap>
1325 NodeMap& operator=(const CMap&) {
1326 checkConcept<ReadMap<Node, Value>, CMap>();
1332 /// \brief ReadWrite map of the edges.
1334 /// ReadWrite map of the edges.
1336 template <typename Value>
1337 class EdgeMap : public GraphMap<Graph, Edge, Value> {
1341 typedef GraphMap<Graph, Edge, Value> Parent;
1343 /// \brief Construct a new map.
1345 /// Construct a new map for the graph.
1346 /// \todo call the right parent class constructor
1347 explicit EdgeMap(const Graph& graph) : Parent(graph) {}
1349 /// \brief Construct a new map with default value.
1351 /// Construct a new map for the graph and initalise the values.
1352 EdgeMap(const Graph& graph, const Value& value)
1353 : Parent(graph, value) {}
1355 /// \brief Copy constructor.
1357 /// Copy Constructor.
1358 EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1360 /// \brief Assign operator.
1362 /// Assign operator.
1363 template <typename CMap>
1364 EdgeMap& operator=(const CMap&) {
1365 checkConcept<ReadMap<Edge, Value>, CMap>();
1372 template <typename _Graph>
1373 struct Constraints {
1377 Dummy() : value(0) {}
1378 Dummy(int _v) : value(_v) {}
1381 void constraints() {
1382 checkConcept<Base, _Graph>();
1384 typedef typename _Graph::template NodeMap<int> IntNodeMap;
1385 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
1387 } { // bool map test
1388 typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
1389 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
1391 } { // Dummy map test
1392 typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
1393 checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
1398 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1399 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1401 } { // bool map test
1402 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1403 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1405 } { // Dummy map test
1406 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1407 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1416 /// \brief An empty mappable base graph class.
1418 /// This class provides beside the core graph features
1419 /// map interface for the graph structure.
1420 /// This concept is part of the UGraph concept.
1421 template <typename _Base = BaseUGraphComponent>
1422 class MappableUGraphComponent : public MappableGraphComponent<_Base> {
1426 typedef typename Base::UEdge UEdge;
1428 typedef MappableUGraphComponent Graph;
1430 /// \brief ReadWrite map of the uedges.
1432 /// ReadWrite map of the uedges.
1434 template <typename Value>
1435 class UEdgeMap : public GraphMap<Graph, UEdge, Value> {
1437 typedef GraphMap<Graph, UEdge, Value> Parent;
1439 /// \brief Construct a new map.
1441 /// Construct a new map for the graph.
1442 /// \todo call the right parent class constructor
1443 explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
1445 /// \brief Construct a new map with default value.
1447 /// Construct a new map for the graph and initalise the values.
1448 UEdgeMap(const Graph& graph, const Value& value)
1449 : Parent(graph, value) {}
1451 /// \brief Copy constructor.
1453 /// Copy Constructor.
1454 UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
1456 /// \brief Assign operator.
1458 /// Assign operator.
1459 template <typename CMap>
1460 UEdgeMap& operator=(const CMap&) {
1461 checkConcept<ReadMap<UEdge, Value>, CMap>();
1468 template <typename _Graph>
1469 struct Constraints {
1473 Dummy() : value(0) {}
1474 Dummy(int _v) : value(_v) {}
1477 void constraints() {
1478 checkConcept<Base, _Graph>();
1479 checkConcept<MappableGraphComponent<Base>, _Graph>();
1482 typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
1483 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
1485 } { // bool map test
1486 typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
1487 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
1489 } { // Dummy map test
1490 typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
1491 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
1501 /// \brief An empty extendable graph class.
1503 /// This class provides beside the core graph features graph
1504 /// extendable interface for the graph structure. The main
1505 /// difference between the base and this interface is that the
1506 /// graph alterations should handled already on this level.
1507 template <typename _Base = BaseGraphComponent>
1508 class ExtendableGraphComponent : public _Base {
1511 typedef typename _Base::Node Node;
1512 typedef typename _Base::Edge Edge;
1514 /// \brief Adds a new node to the graph.
1516 /// Adds a new node to the graph.
1522 /// \brief Adds a new edge connects the given two nodes.
1524 /// Adds a new edge connects the the given two nodes.
1525 Edge addEdge(const Node&, const Node&) {
1529 template <typename _Graph>
1530 struct Constraints {
1531 void constraints() {
1532 typename _Graph::Node node_a, node_b;
1533 node_a = graph.addNode();
1534 node_b = graph.addNode();
1535 typename _Graph::Edge edge;
1536 edge = graph.addEdge(node_a, node_b);
1543 /// \brief An empty extendable base undirected graph class.
1545 /// This class provides beside the core undirected graph features
1546 /// core undircted graph extend interface for the graph structure.
1547 /// The main difference between the base and this interface is
1548 /// that the graph alterations should handled already on this
1550 template <typename _Base = BaseUGraphComponent>
1551 class ExtendableUGraphComponent : public _Base {
1554 typedef typename _Base::Node Node;
1555 typedef typename _Base::UEdge UEdge;
1557 /// \brief Adds a new node to the graph.
1559 /// Adds a new node to the graph.
1565 /// \brief Adds a new edge connects the given two nodes.
1567 /// Adds a new edge connects the the given two nodes.
1568 UEdge addEdge(const Node&, const Node&) {
1572 template <typename _Graph>
1573 struct Constraints {
1574 void constraints() {
1575 typename _Graph::Node node_a, node_b;
1576 node_a = graph.addNode();
1577 node_b = graph.addNode();
1578 typename _Graph::UEdge uedge;
1579 uedge = graph.addUEdge(node_a, node_b);
1586 /// \brief An empty erasable graph class.
1588 /// This class provides beside the core graph features core erase
1589 /// functions for the graph structure. The main difference between
1590 /// the base and this interface is that the graph alterations
1591 /// should handled already on this level.
1592 template <typename _Base = BaseGraphComponent>
1593 class ErasableGraphComponent : public _Base {
1597 typedef typename Base::Node Node;
1598 typedef typename Base::Edge Edge;
1600 /// \brief Erase a node from the graph.
1602 /// Erase a node from the graph. This function should
1603 /// erase all edges connecting to the node.
1604 void erase(const Node&) {}
1606 /// \brief Erase an edge from the graph.
1608 /// Erase an edge from the graph.
1610 void erase(const Edge&) {}
1612 template <typename _Graph>
1613 struct Constraints {
1614 void constraints() {
1615 typename _Graph::Node node;
1617 typename _Graph::Edge edge;
1625 /// \brief An empty erasable base undirected graph class.
1627 /// This class provides beside the core undirected graph features
1628 /// core erase functions for the undirceted graph structure. The
1629 /// main difference between the base and this interface is that
1630 /// the graph alterations should handled already on this level.
1631 template <typename _Base = BaseUGraphComponent>
1632 class ErasableUGraphComponent : public _Base {
1636 typedef typename Base::Node Node;
1637 typedef typename Base::UEdge UEdge;
1639 /// \brief Erase a node from the graph.
1641 /// Erase a node from the graph. This function should erase
1642 /// edges connecting to the node.
1643 void erase(const Node&) {}
1645 /// \brief Erase an edge from the graph.
1647 /// Erase an edge from the graph.
1649 void erase(const UEdge&) {}
1651 template <typename _Graph>
1652 struct Constraints {
1653 void constraints() {
1654 typename _Graph::Node node;
1656 typename _Graph::Edge edge;
1664 /// \brief An empty clearable base graph class.
1666 /// This class provides beside the core graph features core clear
1667 /// functions for the graph structure. The main difference between
1668 /// the base and this interface is that the graph alterations
1669 /// should handled already on this level.
1670 template <typename _Base = BaseGraphComponent>
1671 class ClearableGraphComponent : public _Base {
1674 /// \brief Erase all nodes and edges from the graph.
1676 /// Erase all nodes and edges from the graph.
1680 template <typename _Graph>
1681 struct Constraints {
1682 void constraints() {
1690 /// \brief An empty clearable base undirected graph class.
1692 /// This class provides beside the core undirected graph features
1693 /// core clear functions for the undirected graph structure. The
1694 /// main difference between the base and this interface is that
1695 /// the graph alterations should handled already on this level.
1696 template <typename _Base = BaseUGraphComponent>
1697 class ClearableUGraphComponent : public _Base {
1700 /// \brief Erase all nodes and undirected edges from the graph.
1702 /// Erase all nodes and undirected edges from the graph.
1706 template <typename _Graph>
1707 struct Constraints {
1708 void constraints() {