equal
deleted
inserted
replaced
12 * express or implied, and with no claim as to its suitability for any |
12 * express or implied, and with no claim as to its suitability for any |
13 * purpose. |
13 * purpose. |
14 * |
14 * |
15 */ |
15 */ |
16 |
16 |
17 ///\ingroup concept |
17 ///\ingroup graph_concepts |
18 ///\file |
18 ///\file |
19 ///\brief The graph components. |
19 ///\brief The graph components. |
20 |
20 |
21 |
21 |
22 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H |
22 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H |
26 #include <lemon/concept/maps.h> |
26 #include <lemon/concept/maps.h> |
27 |
27 |
28 namespace lemon { |
28 namespace lemon { |
29 namespace concept { |
29 namespace concept { |
30 |
30 |
|
31 /// \addtogroup graph_concepts |
|
32 /// @{ |
31 |
33 |
32 /**************** Graph iterator concepts ****************/ |
34 /**************** Graph iterator concepts ****************/ |
33 |
35 |
34 /// Skeleton class for graph Node and Edge |
36 /// Skeleton class for graph Node and Edge types |
35 |
37 |
36 /// \note Because Node and Edge are forbidden to inherit from the same |
38 /// This class describes the interface of Node and Edge (and UndirEdge |
37 /// base class, this is a template. For Node you should instantiate it |
39 /// in undirected graphs) subtypes of graph types. |
38 /// with character 'n' and for Edge with 'e'. |
40 /// |
39 |
41 /// \note This class is a template class so that we can use it to |
40 template<char _selector> |
42 /// create graph skeleton classes. The reason for this is than Node |
|
43 /// and Edge types should \em not derive from the same base class. |
|
44 /// For Node you should instantiate it with character 'n' and for Edge |
|
45 /// with 'e'. |
|
46 |
|
47 #ifndef DOXYGEN |
|
48 template <char _selector = '0'> |
|
49 #endif |
41 class GraphItem { |
50 class GraphItem { |
42 public: |
51 public: |
43 /// Default constructor. |
52 /// Default constructor. |
44 |
53 |
45 /// @warning The default constructor sets the item |
54 /// \warning The default constructor is not required to set |
46 /// to an undefined value. |
55 /// the item to some well-defined value. So you should consider it |
|
56 /// as uninitialized. |
47 GraphItem() {} |
57 GraphItem() {} |
48 /// Copy constructor. |
58 /// Copy constructor. |
49 |
59 |
50 /// Copy constructor. |
60 /// Copy constructor. |
51 /// |
61 /// |
69 |
79 |
70 /// \sa operator==(const Node& n) |
80 /// \sa operator==(const Node& n) |
71 /// |
81 /// |
72 bool operator!=(GraphItem) const { return false; } |
82 bool operator!=(GraphItem) const { return false; } |
73 |
83 |
74 // Technical requirement. Do we really need this? |
84 /// Artificial ordering operator. |
75 // bool operator<(GraphItem) const { return false; } |
85 |
76 |
86 /// To allow the use of graph descriptors as key type in std::map or |
|
87 /// similar associative container we require this. |
|
88 /// |
|
89 /// \note This operator only have to define some strict ordering of |
|
90 /// the items; this order has nothing to do with the iteration |
|
91 /// ordering of the items. |
|
92 /// |
|
93 /// \bug This is a technical requirement. Do we really need this? |
|
94 bool operator<(GraphItem) const { return false; } |
77 |
95 |
78 template<typename _GraphItem> |
96 template<typename _GraphItem> |
79 struct Constraints { |
97 struct Constraints { |
80 void constraints() { |
98 void constraints() { |
81 _GraphItem i1; |
99 _GraphItem i1; |
86 |
104 |
87 bool b; |
105 bool b; |
88 // b = (ia == ib) && (ia != ib) && (ia < ib); |
106 // b = (ia == ib) && (ia != ib) && (ia < ib); |
89 b = (ia == ib) && (ia != ib); |
107 b = (ia == ib) && (ia != ib); |
90 b = (ia == INVALID) && (ib != INVALID); |
108 b = (ia == INVALID) && (ib != INVALID); |
|
109 b = (ia < ib); |
91 } |
110 } |
92 |
111 |
93 const _GraphItem &ia; |
112 const _GraphItem &ia; |
94 const _GraphItem &ib; |
113 const _GraphItem &ib; |
95 }; |
114 }; |
96 }; |
115 }; |
|
116 |
|
117 /// A type describing the concept of graph node |
|
118 |
|
119 /// This is an instantiation of \ref GraphItem which can be used as a |
|
120 /// Node subtype in graph skeleton definitions |
|
121 typedef GraphItem<'n'> GraphNode; |
|
122 |
|
123 /// A type describing the concept of graph edge |
|
124 |
|
125 /// This is an instantiation of \ref GraphItem which can be used as a |
|
126 /// Edge subtype in graph skeleton definitions |
|
127 typedef GraphItem<'e'> GraphEdge; |
|
128 |
|
129 |
|
130 /**************** Basic features of graphs ****************/ |
97 |
131 |
98 /// An empty base graph class. |
132 /// An empty base graph class. |
99 |
133 |
100 /// This class provides the minimal set of features needed for a graph |
134 /// This class provides the minimal set of features needed for a graph |
101 /// structure. All graph concepts have to be conform to this base |
135 /// structure. All graph concepts have to be conform to this base |
627 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >(); |
661 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >(); |
628 } |
662 } |
629 }; |
663 }; |
630 |
664 |
631 |
665 |
|
666 /// Class describing the concept of graph maps |
|
667 |
|
668 /// This class describes the common interface of the graph maps |
|
669 /// (NodeMap, EdgeMap), that is \ref maps "maps" which can be used to |
|
670 /// associate data to graph descriptors (nodes or edges). |
632 template <typename Graph, typename Item, typename _Value> |
671 template <typename Graph, typename Item, typename _Value> |
633 class GraphMap : public ReadWriteMap<Item, _Value> { |
672 class GraphMap : public ReadWriteMap<Item, _Value> { |
634 protected: |
673 protected: |
635 GraphMap() {} |
674 GraphMap() {} |
636 public: |
675 public: |
802 |
841 |
803 _Graph& graph; |
842 _Graph& graph; |
804 }; |
843 }; |
805 }; |
844 }; |
806 |
845 |
|
846 /// @} |
|
847 |
807 } |
848 } |
808 |
849 |
809 } |
850 } |
810 |
851 |
811 #endif |
852 #endif |