1.1 --- a/lemon/concept/graph.h Wed Aug 10 19:23:51 2005 +0000
1.2 +++ b/lemon/concept/graph.h Thu Aug 11 13:07:54 2005 +0000
1.3 @@ -31,9 +31,6 @@
1.4 namespace concept {
1.5
1.6
1.7 - /// \addtogroup graph_concepts
1.8 - /// @{
1.9 -
1.10 /**************** The full-featured graph concepts ****************/
1.11
1.12
1.13 @@ -101,6 +98,9 @@
1.14 };
1.15 };
1.16
1.17 + /// \addtogroup graph_concepts
1.18 + /// @{
1.19 +
1.20 /// An empty static graph class.
1.21
1.22 /// This class provides all the common features of a graph structure,
1.23 @@ -252,7 +252,7 @@
1.24 bool operator==(Edge) const { return true; }
1.25 /// Inequality operator
1.26
1.27 - /// \sa operator==(Node n)
1.28 + /// \sa operator==(Edge n)
1.29 ///
1.30 bool operator!=(Edge) const { return true; }
1.31 };
2.1 --- a/lemon/concept/graph_component.h Wed Aug 10 19:23:51 2005 +0000
2.2 +++ b/lemon/concept/graph_component.h Thu Aug 11 13:07:54 2005 +0000
2.3 @@ -30,9 +30,6 @@
2.4 namespace lemon {
2.5 namespace concept {
2.6
2.7 - /// \addtogroup graph_concepts
2.8 - /// @{
2.9 -
2.10 /**************** Graph iterator concepts ****************/
2.11
2.12 /// Skeleton class for graph Node and Edge types
2.13 @@ -996,8 +993,6 @@
2.14 };
2.15 };
2.16
2.17 - /// @}
2.18 -
2.19 }
2.20
2.21 }
3.1 --- a/lemon/concept/undir_graph.h Wed Aug 10 19:23:51 2005 +0000
3.2 +++ b/lemon/concept/undir_graph.h Thu Aug 11 13:07:54 2005 +0000
3.3 @@ -26,15 +26,12 @@
3.4 #define LEMON_CONCEPT_UNDIR_GRAPH_H
3.5
3.6 #include <lemon/concept/graph_component.h>
3.7 +#include <lemon/concept/graph.h>
3.8 #include <lemon/utility.h>
3.9
3.10 namespace lemon {
3.11 namespace concept {
3.12
3.13 - /// \addtogroup graph_concepts
3.14 - /// @{
3.15 -
3.16 -
3.17 /// Skeleton class which describes an edge with direction in \ref
3.18 /// UndirGraph "undirected graph".
3.19 template <typename UndirGraph>
3.20 @@ -108,7 +105,7 @@
3.21 void constraints() {
3.22 checkConcept<BaseIterableGraphComponent, Graph>();
3.23 checkConcept<GraphItem<>, UndirEdge>();
3.24 - checkConcept<UndirGraphEdge<Graph>, Edge>();
3.25 + //checkConcept<UndirGraphEdge<Graph>, Edge>();
3.26
3.27 graph.first(ue);
3.28 graph.next(ue);
3.29 @@ -217,6 +214,10 @@
3.30
3.31 };
3.32
3.33 + /// \addtogroup graph_concepts
3.34 + /// @{
3.35 +
3.36 +
3.37 /// Class describing the concept of Undirected Graphs.
3.38
3.39 /// This class describes the common interface of all Undirected
3.40 @@ -232,7 +233,7 @@
3.41 /// explanation of this and more see also the page \ref undir_graphs,
3.42 /// a tutorial about undirected graphs.
3.43
3.44 - class UndirGraph {
3.45 + class UndirGraph : public StaticGraph {
3.46 public:
3.47 ///\e
3.48
3.49 @@ -240,105 +241,163 @@
3.50 ///
3.51 typedef True UndirTag;
3.52
3.53 - /// Type describing a node in the graph
3.54 - typedef GraphNode Node;
3.55 + /// The base type of the undirected edge iterators.
3.56 +
3.57 + /// The base type of the undirected edge iterators.
3.58 + ///
3.59 + class UndirEdge {
3.60 + public:
3.61 + /// Default constructor
3.62
3.63 - /// Type describing an undirected edge
3.64 - typedef GraphItem<'u'> UndirEdge;
3.65 + /// @warning The default constructor sets the iterator
3.66 + /// to an undefined value.
3.67 + UndirEdge() { }
3.68 + /// Copy constructor.
3.69
3.70 - /// Type describing an UndirEdge with direction
3.71 -#ifndef DOXYGEN
3.72 - typedef UndirGraphEdge<UndirGraph> Edge;
3.73 -#else
3.74 - typedef UndirGraphEdge Edge;
3.75 -#endif
3.76 + /// Copy constructor.
3.77 + ///
3.78 + UndirEdge(const UndirEdge&) { }
3.79 + /// Edge -> UndirEdge conversion
3.80
3.81 - /// Iterator type which iterates over all nodes
3.82 -#ifndef DOXYGEN
3.83 - typedef GraphIterator<UndirGraph, Node> NodeIt;
3.84 -#else
3.85 - typedef GraphIterator NodeIt;
3.86 -#endif
3.87 + /// Edge -> UndirEdge conversion
3.88 + ///
3.89 + UndirEdge(const Edge&) { }
3.90 + /// Initialize the iterator to be invalid.
3.91
3.92 - /// Iterator type which iterates over all undirected edges
3.93 -#ifndef DOXYGEN
3.94 - typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
3.95 -#else
3.96 - typedef GraphIterator UndirEdgeIt;
3.97 -#endif
3.98 + /// Initialize the iterator to be invalid.
3.99 + ///
3.100 + UndirEdge(Invalid) { }
3.101 + /// Equality operator
3.102
3.103 - /// Iterator type which iterates over all directed edges.
3.104 + /// Two iterators are equal if and only if they point to the
3.105 + /// same object or both are invalid.
3.106 + bool operator==(UndirEdge) const { return true; }
3.107 + /// Inequality operator
3.108
3.109 - /// Iterator type which iterates over all edges (each undirected
3.110 - /// edge occurs twice with both directions.
3.111 -#ifndef DOXYGEN
3.112 - typedef GraphIterator<UndirGraph, Edge> EdgeIt;
3.113 -#else
3.114 - typedef GraphIterator EdgeIt;
3.115 -#endif
3.116 + /// \sa operator==(UndirEdge n)
3.117 + ///
3.118 + bool operator!=(UndirEdge) const { return true; }
3.119
3.120 + ///\e
3.121
3.122 - /// Iterator of undirected edges incident to a node
3.123 -#ifndef DOXYGEN
3.124 - typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
3.125 -#else
3.126 - typedef GraphIncIterator IncEdgeIt;
3.127 -#endif
3.128 + ///\todo Do we need this?
3.129 + ///
3.130 + bool operator<(const UndirEdge &that) const { return true; }
3.131 + };
3.132 +
3.133 + /// This iterator goes through each undirected edge.
3.134
3.135 - /// Iterator of edges incoming to a node
3.136 -#ifndef DOXYGEN
3.137 - typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
3.138 -#else
3.139 - typedef GraphIncIterator InEdgeIt;
3.140 -#endif
3.141 + /// This iterator goes through each undirected edge of a graph.
3.142 + /// Its usage is quite simple, for example you can count the number
3.143 + /// of edges in a graph \c g of type \c Graph as follows:
3.144 + /// \code
3.145 + /// int count=0;
3.146 + /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
3.147 + /// \endcode
3.148 + class UndirEdgeIt : public UndirEdge {
3.149 + public:
3.150 + /// Default constructor
3.151 +
3.152 + /// @warning The default constructor sets the iterator
3.153 + /// to an undefined value.
3.154 + UndirEdgeIt() { }
3.155 + /// Copy constructor.
3.156 +
3.157 + /// Copy constructor.
3.158 + ///
3.159 + UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
3.160 + /// Initialize the iterator to be invalid.
3.161
3.162 - /// Iterator of edges outgoing from a node
3.163 -#ifndef DOXYGEN
3.164 - typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
3.165 -#else
3.166 - typedef GraphIncIterator OutEdgeIt;
3.167 -#endif
3.168 + /// Initialize the iterator to be invalid.
3.169 + ///
3.170 + UndirEdgeIt(Invalid) { }
3.171 + /// This constructor sets the iterator to the first edge.
3.172 +
3.173 + /// This constructor sets the iterator to the first edge of \c g.
3.174 + ///@param g the graph
3.175 + UndirEdgeIt(const UndirGraph&) { }
3.176 + /// UndirEdge -> UndirEdgeIt conversion
3.177
3.178 - /// NodeMap template
3.179 -#ifdef DOXYGEN
3.180 - typedef GraphMap NodeMap<T>;
3.181 -#endif
3.182 + /// Sets the iterator to the value of the trivial iterator \c e.
3.183 + /// This feature necessitates that each time we
3.184 + /// iterate the edge-set, the iteration order is the same.
3.185 + UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
3.186 + ///Next edge
3.187 +
3.188 + /// Assign the iterator to the next edge.
3.189 + UndirEdgeIt& operator++() { return *this; }
3.190 + };
3.191
3.192 - /// UndirEdgeMap template
3.193 -#ifdef DOXYGEN
3.194 - typedef GraphMap UndirEdgeMap<T>;
3.195 -#endif
3.196 + /// This iterator goes trough the incident undirected edges of a node.
3.197
3.198 - /// EdgeMap template
3.199 -#ifdef DOXYGEN
3.200 - typedef GraphMap EdgeMap<T>;
3.201 -#endif
3.202 + /// This iterator goes trough the incident undirected edges
3.203 + /// of a certain node
3.204 + /// of a graph.
3.205 + /// Its usage is quite simple, for example you can compute the
3.206 + /// degree (i.e. count the number
3.207 + /// of incident edges of a node \c n
3.208 + /// in graph \c g of type \c Graph as follows.
3.209 + /// \code
3.210 + /// int count=0;
3.211 + /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
3.212 + /// \endcode
3.213 + class IncEdgeIt : public UndirEdge {
3.214 + public:
3.215 + /// Default constructor
3.216
3.217 - template <typename T>
3.218 - class NodeMap : public GraphMap<UndirGraph, Node, T> {
3.219 - typedef GraphMap<UndirGraph, Node, T> Parent;
3.220 + /// @warning The default constructor sets the iterator
3.221 + /// to an undefined value.
3.222 + IncEdgeIt() { }
3.223 + /// Copy constructor.
3.224 +
3.225 + /// Copy constructor.
3.226 + ///
3.227 + IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
3.228 + /// Initialize the iterator to be invalid.
3.229 +
3.230 + /// Initialize the iterator to be invalid.
3.231 + ///
3.232 + IncEdgeIt(Invalid) { }
3.233 + /// This constructor sets the iterator to first incident edge.
3.234 +
3.235 + /// This constructor set the iterator to the first incident edge of
3.236 + /// the node.
3.237 + ///@param n the node
3.238 + ///@param g the graph
3.239 + IncEdgeIt(const UndirGraph&, const Node&) { }
3.240 + /// UndirEdge -> IncEdgeIt conversion
3.241 +
3.242 + /// Sets the iterator to the value of the trivial iterator \c e.
3.243 + /// This feature necessitates that each time we
3.244 + /// iterate the edge-set, the iteration order is the same.
3.245 + IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
3.246 + /// Next incident edge
3.247 +
3.248 + /// Assign the iterator to the next incident edge
3.249 + /// of the corresponding node.
3.250 + IncEdgeIt& operator++() { return *this; }
3.251 + };
3.252 +
3.253 + /// Read write map of the undirected edges to type \c T.
3.254 +
3.255 + /// Reference map of the edges to type \c T.
3.256 + /// \sa Reference
3.257 + /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
3.258 + /// needs some extra attention!
3.259 + template<class T>
3.260 + class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
3.261 + {
3.262 public:
3.263
3.264 - explicit NodeMap(const UndirGraph &g) : Parent(g) {}
3.265 - NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
3.266 - };
3.267 -
3.268 - template <typename T>
3.269 - class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
3.270 - typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
3.271 - public:
3.272 -
3.273 - explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
3.274 - UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
3.275 - };
3.276 -
3.277 - template <typename T>
3.278 - class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
3.279 - typedef GraphMap<UndirGraph, Edge, T> Parent;
3.280 - public:
3.281 -
3.282 - explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
3.283 - EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
3.284 + ///\e
3.285 + UndirEdgeMap(const UndirGraph&) { }
3.286 + ///\e
3.287 + UndirEdgeMap(const UndirGraph&, T) { }
3.288 + ///Copy constructor
3.289 + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
3.290 + ///Assignment operator
3.291 + UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
3.292 + // \todo fix this concept
3.293 };
3.294
3.295 /// Is the Edge oriented "forward"?