1.1 --- a/lemon/concept/undir_graph.h Wed Aug 10 19:23:51 2005 +0000
1.2 +++ b/lemon/concept/undir_graph.h Thu Aug 11 13:07:54 2005 +0000
1.3 @@ -26,15 +26,12 @@
1.4 #define LEMON_CONCEPT_UNDIR_GRAPH_H
1.5
1.6 #include <lemon/concept/graph_component.h>
1.7 +#include <lemon/concept/graph.h>
1.8 #include <lemon/utility.h>
1.9
1.10 namespace lemon {
1.11 namespace concept {
1.12
1.13 - /// \addtogroup graph_concepts
1.14 - /// @{
1.15 -
1.16 -
1.17 /// Skeleton class which describes an edge with direction in \ref
1.18 /// UndirGraph "undirected graph".
1.19 template <typename UndirGraph>
1.20 @@ -108,7 +105,7 @@
1.21 void constraints() {
1.22 checkConcept<BaseIterableGraphComponent, Graph>();
1.23 checkConcept<GraphItem<>, UndirEdge>();
1.24 - checkConcept<UndirGraphEdge<Graph>, Edge>();
1.25 + //checkConcept<UndirGraphEdge<Graph>, Edge>();
1.26
1.27 graph.first(ue);
1.28 graph.next(ue);
1.29 @@ -217,6 +214,10 @@
1.30
1.31 };
1.32
1.33 + /// \addtogroup graph_concepts
1.34 + /// @{
1.35 +
1.36 +
1.37 /// Class describing the concept of Undirected Graphs.
1.38
1.39 /// This class describes the common interface of all Undirected
1.40 @@ -232,7 +233,7 @@
1.41 /// explanation of this and more see also the page \ref undir_graphs,
1.42 /// a tutorial about undirected graphs.
1.43
1.44 - class UndirGraph {
1.45 + class UndirGraph : public StaticGraph {
1.46 public:
1.47 ///\e
1.48
1.49 @@ -240,105 +241,163 @@
1.50 ///
1.51 typedef True UndirTag;
1.52
1.53 - /// Type describing a node in the graph
1.54 - typedef GraphNode Node;
1.55 + /// The base type of the undirected edge iterators.
1.56 +
1.57 + /// The base type of the undirected edge iterators.
1.58 + ///
1.59 + class UndirEdge {
1.60 + public:
1.61 + /// Default constructor
1.62
1.63 - /// Type describing an undirected edge
1.64 - typedef GraphItem<'u'> UndirEdge;
1.65 + /// @warning The default constructor sets the iterator
1.66 + /// to an undefined value.
1.67 + UndirEdge() { }
1.68 + /// Copy constructor.
1.69
1.70 - /// Type describing an UndirEdge with direction
1.71 -#ifndef DOXYGEN
1.72 - typedef UndirGraphEdge<UndirGraph> Edge;
1.73 -#else
1.74 - typedef UndirGraphEdge Edge;
1.75 -#endif
1.76 + /// Copy constructor.
1.77 + ///
1.78 + UndirEdge(const UndirEdge&) { }
1.79 + /// Edge -> UndirEdge conversion
1.80
1.81 - /// Iterator type which iterates over all nodes
1.82 -#ifndef DOXYGEN
1.83 - typedef GraphIterator<UndirGraph, Node> NodeIt;
1.84 -#else
1.85 - typedef GraphIterator NodeIt;
1.86 -#endif
1.87 + /// Edge -> UndirEdge conversion
1.88 + ///
1.89 + UndirEdge(const Edge&) { }
1.90 + /// Initialize the iterator to be invalid.
1.91
1.92 - /// Iterator type which iterates over all undirected edges
1.93 -#ifndef DOXYGEN
1.94 - typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
1.95 -#else
1.96 - typedef GraphIterator UndirEdgeIt;
1.97 -#endif
1.98 + /// Initialize the iterator to be invalid.
1.99 + ///
1.100 + UndirEdge(Invalid) { }
1.101 + /// Equality operator
1.102
1.103 - /// Iterator type which iterates over all directed edges.
1.104 + /// Two iterators are equal if and only if they point to the
1.105 + /// same object or both are invalid.
1.106 + bool operator==(UndirEdge) const { return true; }
1.107 + /// Inequality operator
1.108
1.109 - /// Iterator type which iterates over all edges (each undirected
1.110 - /// edge occurs twice with both directions.
1.111 -#ifndef DOXYGEN
1.112 - typedef GraphIterator<UndirGraph, Edge> EdgeIt;
1.113 -#else
1.114 - typedef GraphIterator EdgeIt;
1.115 -#endif
1.116 + /// \sa operator==(UndirEdge n)
1.117 + ///
1.118 + bool operator!=(UndirEdge) const { return true; }
1.119
1.120 + ///\e
1.121
1.122 - /// Iterator of undirected edges incident to a node
1.123 -#ifndef DOXYGEN
1.124 - typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
1.125 -#else
1.126 - typedef GraphIncIterator IncEdgeIt;
1.127 -#endif
1.128 + ///\todo Do we need this?
1.129 + ///
1.130 + bool operator<(const UndirEdge &that) const { return true; }
1.131 + };
1.132 +
1.133 + /// This iterator goes through each undirected edge.
1.134
1.135 - /// Iterator of edges incoming to a node
1.136 -#ifndef DOXYGEN
1.137 - typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
1.138 -#else
1.139 - typedef GraphIncIterator InEdgeIt;
1.140 -#endif
1.141 + /// This iterator goes through each undirected edge of a graph.
1.142 + /// Its usage is quite simple, for example you can count the number
1.143 + /// of edges in a graph \c g of type \c Graph as follows:
1.144 + /// \code
1.145 + /// int count=0;
1.146 + /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
1.147 + /// \endcode
1.148 + class UndirEdgeIt : public UndirEdge {
1.149 + public:
1.150 + /// Default constructor
1.151 +
1.152 + /// @warning The default constructor sets the iterator
1.153 + /// to an undefined value.
1.154 + UndirEdgeIt() { }
1.155 + /// Copy constructor.
1.156 +
1.157 + /// Copy constructor.
1.158 + ///
1.159 + UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
1.160 + /// Initialize the iterator to be invalid.
1.161
1.162 - /// Iterator of edges outgoing from a node
1.163 -#ifndef DOXYGEN
1.164 - typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
1.165 -#else
1.166 - typedef GraphIncIterator OutEdgeIt;
1.167 -#endif
1.168 + /// Initialize the iterator to be invalid.
1.169 + ///
1.170 + UndirEdgeIt(Invalid) { }
1.171 + /// This constructor sets the iterator to the first edge.
1.172 +
1.173 + /// This constructor sets the iterator to the first edge of \c g.
1.174 + ///@param g the graph
1.175 + UndirEdgeIt(const UndirGraph&) { }
1.176 + /// UndirEdge -> UndirEdgeIt conversion
1.177
1.178 - /// NodeMap template
1.179 -#ifdef DOXYGEN
1.180 - typedef GraphMap NodeMap<T>;
1.181 -#endif
1.182 + /// Sets the iterator to the value of the trivial iterator \c e.
1.183 + /// This feature necessitates that each time we
1.184 + /// iterate the edge-set, the iteration order is the same.
1.185 + UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
1.186 + ///Next edge
1.187 +
1.188 + /// Assign the iterator to the next edge.
1.189 + UndirEdgeIt& operator++() { return *this; }
1.190 + };
1.191
1.192 - /// UndirEdgeMap template
1.193 -#ifdef DOXYGEN
1.194 - typedef GraphMap UndirEdgeMap<T>;
1.195 -#endif
1.196 + /// This iterator goes trough the incident undirected edges of a node.
1.197
1.198 - /// EdgeMap template
1.199 -#ifdef DOXYGEN
1.200 - typedef GraphMap EdgeMap<T>;
1.201 -#endif
1.202 + /// This iterator goes trough the incident undirected edges
1.203 + /// of a certain node
1.204 + /// of a graph.
1.205 + /// Its usage is quite simple, for example you can compute the
1.206 + /// degree (i.e. count the number
1.207 + /// of incident edges of a node \c n
1.208 + /// in graph \c g of type \c Graph as follows.
1.209 + /// \code
1.210 + /// int count=0;
1.211 + /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.212 + /// \endcode
1.213 + class IncEdgeIt : public UndirEdge {
1.214 + public:
1.215 + /// Default constructor
1.216
1.217 - template <typename T>
1.218 - class NodeMap : public GraphMap<UndirGraph, Node, T> {
1.219 - typedef GraphMap<UndirGraph, Node, T> Parent;
1.220 + /// @warning The default constructor sets the iterator
1.221 + /// to an undefined value.
1.222 + IncEdgeIt() { }
1.223 + /// Copy constructor.
1.224 +
1.225 + /// Copy constructor.
1.226 + ///
1.227 + IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
1.228 + /// Initialize the iterator to be invalid.
1.229 +
1.230 + /// Initialize the iterator to be invalid.
1.231 + ///
1.232 + IncEdgeIt(Invalid) { }
1.233 + /// This constructor sets the iterator to first incident edge.
1.234 +
1.235 + /// This constructor set the iterator to the first incident edge of
1.236 + /// the node.
1.237 + ///@param n the node
1.238 + ///@param g the graph
1.239 + IncEdgeIt(const UndirGraph&, const Node&) { }
1.240 + /// UndirEdge -> IncEdgeIt conversion
1.241 +
1.242 + /// Sets the iterator to the value of the trivial iterator \c e.
1.243 + /// This feature necessitates that each time we
1.244 + /// iterate the edge-set, the iteration order is the same.
1.245 + IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
1.246 + /// Next incident edge
1.247 +
1.248 + /// Assign the iterator to the next incident edge
1.249 + /// of the corresponding node.
1.250 + IncEdgeIt& operator++() { return *this; }
1.251 + };
1.252 +
1.253 + /// Read write map of the undirected edges to type \c T.
1.254 +
1.255 + /// Reference map of the edges to type \c T.
1.256 + /// \sa Reference
1.257 + /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
1.258 + /// needs some extra attention!
1.259 + template<class T>
1.260 + class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
1.261 + {
1.262 public:
1.263
1.264 - explicit NodeMap(const UndirGraph &g) : Parent(g) {}
1.265 - NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.266 - };
1.267 -
1.268 - template <typename T>
1.269 - class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
1.270 - typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
1.271 - public:
1.272 -
1.273 - explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
1.274 - UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.275 - };
1.276 -
1.277 - template <typename T>
1.278 - class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
1.279 - typedef GraphMap<UndirGraph, Edge, T> Parent;
1.280 - public:
1.281 -
1.282 - explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
1.283 - EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
1.284 + ///\e
1.285 + UndirEdgeMap(const UndirGraph&) { }
1.286 + ///\e
1.287 + UndirEdgeMap(const UndirGraph&, T) { }
1.288 + ///Copy constructor
1.289 + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
1.290 + ///Assignment operator
1.291 + UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
1.292 + // \todo fix this concept
1.293 };
1.294
1.295 /// Is the Edge oriented "forward"?