1.1 --- a/lemon/concept/graph.h Wed Jul 05 16:59:45 2006 +0000
1.2 +++ b/lemon/concept/graph.h Mon Jul 10 19:04:17 2006 +0000
1.3 @@ -32,30 +32,6 @@
1.4 namespace lemon {
1.5 namespace concept {
1.6
1.7 -
1.8 - /**************** The full-featured graph concepts ****************/
1.9 -
1.10 -
1.11 - // \brief Modular static graph class.
1.12 - //
1.13 - // It should be the same as the \c Graph class.
1.14 - class _Graph
1.15 - : virtual public BaseGraphComponent,
1.16 - public IterableGraphComponent, public MappableGraphComponent {
1.17 - public:
1.18 -
1.19 - typedef BaseGraphComponent::Node Node;
1.20 - typedef BaseGraphComponent::Edge Edge;
1.21 -
1.22 - template <typename _Graph>
1.23 - struct Constraints {
1.24 - void constraints() {
1.25 - checkConcept<IterableGraphComponent, _Graph>();
1.26 - checkConcept<MappableGraphComponent, _Graph>();
1.27 - }
1.28 - };
1.29 - };
1.30 -
1.31 /// \addtogroup graph_concepts
1.32 /// @{
1.33
1.34 @@ -410,10 +386,8 @@
1.35 /// \sa Reference
1.36 /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.37 /// needs some extra attention!
1.38 - /// \todo Wrong documentation
1.39 template<class T>
1.40 - class NodeMap : public ReadWriteMap< Node, T >
1.41 - {
1.42 + class NodeMap : public ReadWriteMap< Node, T > {
1.43 public:
1.44
1.45 ///\e
1.46 @@ -424,8 +398,11 @@
1.47 ///Copy constructor
1.48 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.49 ///Assignment operator
1.50 - NodeMap& operator=(const NodeMap&) { return *this; }
1.51 - // \todo fix this concept
1.52 + template <typename CMap>
1.53 + NodeMap& operator=(const CMap&) {
1.54 + checkConcept<ReadMap<Node, T>, CMap>();
1.55 + return *this;
1.56 + }
1.57 };
1.58
1.59 /// \brief Read write map of the edges to type \c T.
1.60 @@ -434,10 +411,8 @@
1.61 /// \sa Reference
1.62 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.63 /// needs some extra attention!
1.64 - /// \todo Wrong documentation
1.65 template<class T>
1.66 - class EdgeMap : public ReadWriteMap<Edge,T>
1.67 - {
1.68 + class EdgeMap : public ReadWriteMap<Edge,T> {
1.69 public:
1.70
1.71 ///\e
1.72 @@ -447,12 +422,21 @@
1.73 ///Copy constructor
1.74 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
1.75 ///Assignment operator
1.76 - EdgeMap& operator=(const EdgeMap&) { return *this; }
1.77 - // \todo fix this concept
1.78 + template <typename CMap>
1.79 + EdgeMap& operator=(const CMap&) {
1.80 + checkConcept<ReadMap<Edge, T>, CMap>();
1.81 + return *this;
1.82 + }
1.83 };
1.84
1.85 template <typename RGraph>
1.86 - struct Constraints : public _Graph::Constraints<RGraph> {};
1.87 + struct Constraints {
1.88 + void constraints() {
1.89 + checkConcept<BaseIterableGraphComponent<>, Graph>();
1.90 + checkConcept<IterableGraphComponent<>, Graph>();
1.91 + checkConcept<MappableGraphComponent<>, Graph>();
1.92 + }
1.93 + };
1.94
1.95 };
1.96
2.1 --- a/lemon/concept/graph_component.h Wed Jul 05 16:59:45 2006 +0000
2.2 +++ b/lemon/concept/graph_component.h Mon Jul 10 19:04:17 2006 +0000
2.3 @@ -32,10 +32,8 @@
2.4 namespace lemon {
2.5 namespace concept {
2.6
2.7 - /**************** Graph iterator concepts ****************/
2.8 -
2.9 - /// Skeleton class for graph Node and Edge types
2.10 -
2.11 + /// \brief Skeleton class for graph Node and Edge types
2.12 + ///
2.13 /// This class describes the interface of Node and Edge (and UEdge
2.14 /// in undirected graphs) subtypes of graph types.
2.15 ///
2.16 @@ -50,48 +48,46 @@
2.17 #endif
2.18 class GraphItem {
2.19 public:
2.20 - /// Default constructor.
2.21 -
2.22 + /// \brief Default constructor.
2.23 + ///
2.24 /// \warning The default constructor is not required to set
2.25 /// the item to some well-defined value. So you should consider it
2.26 /// as uninitialized.
2.27 GraphItem() {}
2.28 - /// Copy constructor.
2.29 -
2.30 + /// \brief Copy constructor.
2.31 + ///
2.32 /// Copy constructor.
2.33 ///
2.34 - GraphItem(GraphItem const&) {}
2.35 - /// Invalid constructor \& conversion.
2.36 -
2.37 + GraphItem(const GraphItem &) {}
2.38 + /// \brief Invalid constructor \& conversion.
2.39 + ///
2.40 /// This constructor initializes the item to be invalid.
2.41 /// \sa Invalid for more details.
2.42 GraphItem(Invalid) {}
2.43 - /// Assign operator for nodes.
2.44 -
2.45 + /// \brief Assign operator for nodes.
2.46 + ///
2.47 /// The nodes are assignable.
2.48 ///
2.49 GraphItem& operator=(GraphItem const&) { return *this; }
2.50 - /// Equality operator.
2.51 -
2.52 + /// \brief Equality operator.
2.53 + ///
2.54 /// Two iterators are equal if and only if they represents the
2.55 /// same node in the graph or both are invalid.
2.56 bool operator==(GraphItem) const { return false; }
2.57 - /// Inequality operator.
2.58 -
2.59 + /// \brief Inequality operator.
2.60 + ///
2.61 /// \sa operator==(const Node& n)
2.62 ///
2.63 bool operator!=(GraphItem) const { return false; }
2.64
2.65 - /// Artificial ordering operator.
2.66 -
2.67 + /// \brief Artificial ordering operator.
2.68 + ///
2.69 /// To allow the use of graph descriptors as key type in std::map or
2.70 /// similar associative container we require this.
2.71 ///
2.72 /// \note This operator only have to define some strict ordering of
2.73 /// the items; this order has nothing to do with the iteration
2.74 /// ordering of the items.
2.75 - ///
2.76 - /// \bug This is a technical requirement. Do we really need this?
2.77 bool operator<(GraphItem) const { return false; }
2.78
2.79 template<typename _GraphItem>
2.80 @@ -107,7 +103,7 @@
2.81 // b = (ia == ib) && (ia != ib) && (ia < ib);
2.82 b = (ia == ib) && (ia != ib);
2.83 b = (ia == INVALID) && (ib != INVALID);
2.84 - // b = (ia < ib);
2.85 + b = (ia < ib);
2.86 }
2.87
2.88 const _GraphItem &ia;
2.89 @@ -115,59 +111,47 @@
2.90 };
2.91 };
2.92
2.93 - /// A type describing the concept of graph node
2.94 -
2.95 - /// This is an instantiation of \ref GraphItem which can be used as a
2.96 - /// Node subtype in graph skeleton definitions
2.97 - typedef GraphItem<'n'> GraphNode;
2.98 -
2.99 - /// A type describing the concept of graph edge
2.100 -
2.101 - /// This is an instantiation of \ref GraphItem which can be used as a
2.102 - /// Edge subtype in graph skeleton definitions
2.103 - typedef GraphItem<'e'> GraphEdge;
2.104 -
2.105 -
2.106 - /**************** Basic features of graphs ****************/
2.107 -
2.108 - /// An empty base graph class.
2.109 -
2.110 + /// \brief An empty base graph class.
2.111 + ///
2.112 /// This class provides the minimal set of features needed for a graph
2.113 /// structure. All graph concepts have to be conform to this base
2.114 - /// graph.
2.115 - ///
2.116 - /// \bug This is not true. The minimal graph concept is the
2.117 - /// BaseIterableGraphComponent.
2.118 -
2.119 + /// graph. It just provides types for nodes and edges and functions to
2.120 + /// get the source and the target of the edges.
2.121 class BaseGraphComponent {
2.122 public:
2.123
2.124 typedef BaseGraphComponent Graph;
2.125
2.126 - /// Node class of the graph.
2.127 -
2.128 + /// \brief Node class of the graph.
2.129 + ///
2.130 /// This class represents the Nodes of the graph.
2.131 ///
2.132 typedef GraphItem<'n'> Node;
2.133
2.134 - /// Edge class of the graph.
2.135 -
2.136 + /// \brief Edge class of the graph.
2.137 + ///
2.138 /// This class represents the Edges of the graph.
2.139 ///
2.140 typedef GraphItem<'e'> Edge;
2.141
2.142 - ///Gives back the target node of an edge.
2.143 -
2.144 - ///Gives back the target node of an edge.
2.145 + /// \brief Gives back the target node of an edge.
2.146 + ///
2.147 + /// Gives back the target node of an edge.
2.148 ///
2.149 Node target(const Edge&) const { return INVALID;}
2.150
2.151 - ///Gives back the source node of an edge.
2.152 -
2.153 - ///Gives back the source node of an edge.
2.154 + /// \brief Gives back the source node of an edge.
2.155 + ///
2.156 + /// Gives back the source node of an edge.
2.157 ///
2.158 Node source(const Edge&) const { return INVALID;}
2.159
2.160 + /// \brief Gives back the opposite node on the given edge.
2.161 + ///
2.162 + /// Gives back the opposite node on the given edge.
2.163 + Node oppositeNode(const Node&, const Edge&) const {
2.164 + return INVALID;
2.165 + }
2.166
2.167 template <typename _Graph>
2.168 struct Constraints {
2.169 @@ -182,6 +166,7 @@
2.170 Edge e(INVALID);
2.171 n = graph.source(e);
2.172 n = graph.target(e);
2.173 + n = graph.oppositeNode(n, e);
2.174 }
2.175 }
2.176
2.177 @@ -189,64 +174,185 @@
2.178 };
2.179 };
2.180
2.181 - /// An empty iterable base graph class.
2.182 -
2.183 + /// \brief An empty base undirected graph class.
2.184 + ///
2.185 + /// This class provides the minimal set of features needed for an
2.186 + /// undirected graph structure. All undirected graph concepts have
2.187 + /// to be conform to this base graph. It just provides types for
2.188 + /// nodes, edges and undirected edges and functions to get the
2.189 + /// source and the target of the edges and undirected edges,
2.190 + /// conversion from edges to undirected edges and function to get
2.191 + /// both direction of the undirected edges.
2.192 + class BaseUGraphComponent : public BaseGraphComponent {
2.193 + public:
2.194 + typedef BaseGraphComponent::Node Node;
2.195 + typedef BaseGraphComponent::Edge Edge;
2.196 + /// \brief Undirected edge class of the graph.
2.197 + ///
2.198 + /// This class represents the undirected edges of the graph.
2.199 + /// The undirected graphs can be used as a directed graph which
2.200 + /// for each edge contains the opposite edge too so the graph is
2.201 + /// bidirected. The undirected edge represents two opposite
2.202 + /// directed edges.
2.203 + class UEdge : public GraphItem<'u'> {
2.204 + public:
2.205 + typedef GraphItem<'u'> Parent;
2.206 + /// \brief Default constructor.
2.207 + ///
2.208 + /// \warning The default constructor is not required to set
2.209 + /// the item to some well-defined value. So you should consider it
2.210 + /// as uninitialized.
2.211 + UEdge() {}
2.212 + /// \brief Copy constructor.
2.213 + ///
2.214 + /// Copy constructor.
2.215 + ///
2.216 + UEdge(const UEdge &) : Parent() {}
2.217 + /// \brief Invalid constructor \& conversion.
2.218 + ///
2.219 + /// This constructor initializes the item to be invalid.
2.220 + /// \sa Invalid for more details.
2.221 + UEdge(Invalid) {}
2.222 + /// \brief Converter from edge to undirected edge.
2.223 + ///
2.224 + /// Besides the core graph item functionality each edge should
2.225 + /// be convertible to the represented undirected edge.
2.226 + UEdge(const Edge&) {}
2.227 + };
2.228 +
2.229 + /// \brief Returns the direction of the edge.
2.230 + ///
2.231 + /// Returns the direction of the edge. Each edge represents an
2.232 + /// undirected edge with a direction. It gives back the
2.233 + /// direction.
2.234 + bool direction(const Edge&) const { return true; }
2.235 +
2.236 + /// \brief Returns the directed edge.
2.237 + ///
2.238 + /// Returns the directed edge from its direction and the
2.239 + /// represented undirected edge.
2.240 + Edge direct(const UEdge&, bool) const { return INVALID;}
2.241 +
2.242 + /// \brief Returns the directed edge.
2.243 + ///
2.244 + /// Returns the directed edge from its source and the
2.245 + /// represented undirected edge.
2.246 + Edge direct(const UEdge&, const Node&) const { return INVALID;}
2.247 +
2.248 + /// \brief Returns the opposite edge.
2.249 + ///
2.250 + /// Returns the opposite edge. It is the edge representing the
2.251 + /// same undirected edge and has opposite direction.
2.252 + Edge oppositeEdge(const Edge&) const { return INVALID;}
2.253 +
2.254 + /// \brief Gives back the target node of an undirected edge.
2.255 + ///
2.256 + /// Gives back the target node of an undirected edge. The name
2.257 + /// target is a little confusing because the undirected edge
2.258 + /// does not have target but it just means that one of the end
2.259 + /// node.
2.260 + Node target(const UEdge&) const { return INVALID;}
2.261 +
2.262 + /// \brief Gives back the source node of an undirected edge.
2.263 + ///
2.264 + /// Gives back the source node of an undirected edge. The name
2.265 + /// source is a little confusing because the undirected edge
2.266 + /// does not have source but it just means that one of the end
2.267 + /// node.
2.268 + Node source(const UEdge&) const { return INVALID;}
2.269 +
2.270 + template <typename _Graph>
2.271 + struct Constraints {
2.272 + typedef typename _Graph::Node Node;
2.273 + typedef typename _Graph::Edge Edge;
2.274 + typedef typename _Graph::UEdge UEdge;
2.275 +
2.276 + void constraints() {
2.277 + checkConcept<BaseGraphComponent, _Graph>();
2.278 + checkConcept<GraphItem<'u'>, UEdge>();
2.279 + {
2.280 + Node n;
2.281 + UEdge ue(INVALID);
2.282 + Edge e;
2.283 + n = graph.source(ue);
2.284 + n = graph.target(ue);
2.285 + e = graph.direct(ue, true);
2.286 + e = graph.direct(ue, n);
2.287 + e = graph.oppositeEdge(e);
2.288 + ue = e;
2.289 + bool d = graph.direction(e);
2.290 + ignore_unused_variable_warning(d);
2.291 + }
2.292 + }
2.293 +
2.294 + const _Graph& graph;
2.295 + };
2.296 +
2.297 + };
2.298 +
2.299 + /// \brief An empty iterable base graph class.
2.300 + ///
2.301 /// This class provides beside the core graph features
2.302 /// core iterable interface for the graph structure.
2.303 /// Most of the base graphs should be conform to this concept.
2.304 -
2.305 - class BaseIterableGraphComponent : virtual public BaseGraphComponent {
2.306 + template <typename _Base = BaseGraphComponent>
2.307 + class BaseIterableGraphComponent : public _Base {
2.308 public:
2.309
2.310 - typedef BaseGraphComponent::Node Node;
2.311 - typedef BaseGraphComponent::Edge Edge;
2.312 + typedef _Base Base;
2.313 + typedef typename Base::Node Node;
2.314 + typedef typename Base::Edge Edge;
2.315
2.316 - /// Gives back the first Node in the iterating order.
2.317 -
2.318 - /// Gives back the first Node in the iterating order.
2.319 + /// \brief Gives back the first node in the iterating order.
2.320 + ///
2.321 + /// Gives back the first node in the iterating order.
2.322 ///
2.323 void first(Node&) const {}
2.324
2.325 - /// Gives back the next Node in the iterating order.
2.326 -
2.327 - /// Gives back the next Node in the iterating order.
2.328 + /// \brief Gives back the next node in the iterating order.
2.329 + ///
2.330 + /// Gives back the next node in the iterating order.
2.331 ///
2.332 void next(Node&) const {}
2.333
2.334 - /// Gives back the first Edge in the iterating order.
2.335 -
2.336 - /// Gives back the first Edge in the iterating order.
2.337 + /// \brief Gives back the first edge in the iterating order.
2.338 + ///
2.339 + /// Gives back the first edge in the iterating order.
2.340 ///
2.341 void first(Edge&) const {}
2.342 - /// Gives back the next Edge in the iterating order.
2.343 -
2.344 - /// Gives back the next Edge in the iterating order.
2.345 +
2.346 + /// \brief Gives back the next edge in the iterating order.
2.347 + ///
2.348 + /// Gives back the next edge in the iterating order.
2.349 ///
2.350 void next(Edge&) const {}
2.351
2.352
2.353 - /// Gives back the first of the Edges point to the given Node.
2.354 -
2.355 - /// Gives back the first of the Edges point to the given Node.
2.356 + /// \brief Gives back the first of the edges point to the given
2.357 + /// node.
2.358 + ///
2.359 + /// Gives back the first of the edges point to the given node.
2.360 ///
2.361 void firstIn(Edge&, const Node&) const {}
2.362
2.363 - /// Gives back the next of the Edges points to the given Node.
2.364 -
2.365 -
2.366 - /// Gives back the next of the Edges points to the given Node.
2.367 + /// \brief Gives back the next of the edges points to the given
2.368 + /// node.
2.369 + ///
2.370 + /// Gives back the next of the edges points to the given node.
2.371 ///
2.372 void nextIn(Edge&) const {}
2.373
2.374 - /// Gives back the first of the Edges start from the given Node.
2.375 -
2.376 - /// Gives back the first of the Edges start from the given Node.
2.377 + /// \brief Gives back the first of the edges start from the
2.378 + /// given node.
2.379 + ///
2.380 + /// Gives back the first of the edges start from the given node.
2.381 ///
2.382 void firstOut(Edge&, const Node&) const {}
2.383
2.384 - /// Gives back the next of the Edges start from the given Node.
2.385 -
2.386 - /// Gives back the next of the Edges start from the given Node.
2.387 + /// \brief Gives back the next of the edges start from the given
2.388 + /// node.
2.389 + ///
2.390 + /// Gives back the next of the edges start from the given node.
2.391 ///
2.392 void nextOut(Edge&) const {}
2.393
2.394 @@ -280,20 +386,95 @@
2.395 };
2.396 };
2.397
2.398 - /// An empty idable base graph class.
2.399 -
2.400 + /// \brief An empty iterable base undirected graph class.
2.401 + ///
2.402 + /// This class provides beside the core undirceted graph features
2.403 + /// core iterable interface for the undirected graph structure.
2.404 + /// Most of the base undirected graphs should be conform to this
2.405 + /// concept.
2.406 + template <typename _Base = BaseUGraphComponent>
2.407 + class BaseIterableUGraphComponent
2.408 + : public BaseIterableGraphComponent<_Base> {
2.409 + public:
2.410 +
2.411 + typedef _Base Base;
2.412 + typedef typename Base::UEdge UEdge;
2.413 + typedef typename Base::Node Node;
2.414 +
2.415 + using BaseIterableGraphComponent<_Base>::first;
2.416 + using BaseIterableGraphComponent<_Base>::next;
2.417 +
2.418 + /// \brief Gives back the first undirected edge in the iterating
2.419 + /// order.
2.420 + ///
2.421 + /// Gives back the first undirected edge in the iterating order.
2.422 + ///
2.423 + void first(UEdge&) const {}
2.424 +
2.425 + /// \brief Gives back the next undirected edge in the iterating
2.426 + /// order.
2.427 + ///
2.428 + /// Gives back the next undirected edge in the iterating order.
2.429 + ///
2.430 + void next(UEdge&) const {}
2.431 +
2.432 +
2.433 + /// \brief Gives back the first of the undirected edges from the
2.434 + /// given node.
2.435 + ///
2.436 + /// Gives back the first of the undirected edges from the given
2.437 + /// node. The bool parameter gives back that direction which
2.438 + /// gives a good direction of the uedge so the source of the
2.439 + /// directed edge is the given node.
2.440 + void firstInc(UEdge&, bool&, const Node&) const {}
2.441 +
2.442 + /// \brief Gives back the next of the undirected edges from the
2.443 + /// given node.
2.444 + ///
2.445 + /// Gives back the next of the undirected edges from the given
2.446 + /// node. The bool parameter should be used as the \c firstInc()
2.447 + /// use it.
2.448 + void nextInc(UEdge&, bool&) const {}
2.449 +
2.450 + template <typename _Graph>
2.451 + struct Constraints {
2.452 +
2.453 + void constraints() {
2.454 + checkConcept<Base, _Graph >();
2.455 + checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
2.456 + typename _Graph::Node node;
2.457 + typename _Graph::UEdge uedge;
2.458 + bool dir;
2.459 + {
2.460 + graph.first(uedge);
2.461 + graph.next(uedge);
2.462 + }
2.463 + {
2.464 + graph.firstInc(uedge, dir, node);
2.465 + graph.nextInc(uedge, dir);
2.466 + }
2.467 + }
2.468 +
2.469 + const _Graph& graph;
2.470 + };
2.471 + };
2.472 +
2.473 + /// \brief An empty idable base graph class.
2.474 + ///
2.475 /// This class provides beside the core graph features
2.476 /// core id functions for the graph structure.
2.477 /// The most of the base graphs should be conform to this concept.
2.478 /// The id's are unique and immutable.
2.479 - class IDableGraphComponent : virtual public BaseGraphComponent {
2.480 + template <typename _Base = BaseGraphComponent>
2.481 + class IDableGraphComponent : public _Base {
2.482 public:
2.483
2.484 - typedef BaseGraphComponent::Node Node;
2.485 - typedef BaseGraphComponent::Edge Edge;
2.486 + typedef _Base Base;
2.487 + typedef typename Base::Node Node;
2.488 + typedef typename Base::Edge Edge;
2.489
2.490 - /// Gives back an unique integer id for the Node.
2.491 -
2.492 + /// \brief Gives back an unique integer id for the Node.
2.493 + ///
2.494 /// Gives back an unique integer id for the Node.
2.495 ///
2.496 int id(const Node&) const { return -1;}
2.497 @@ -303,7 +484,7 @@
2.498 /// Gives back the node by the unique id.
2.499 /// If the graph does not contain node with the given id
2.500 /// then the result of the function is undetermined.
2.501 - Node fromId(int , Node) const { return INVALID;}
2.502 + Node nodeFromId(int) const { return INVALID;}
2.503
2.504 /// \brief Gives back an unique integer id for the Edge.
2.505 ///
2.506 @@ -316,7 +497,21 @@
2.507 /// Gives back the edge by the unique id.
2.508 /// If the graph does not contain edge with the given id
2.509 /// then the result of the function is undetermined.
2.510 - Edge fromId(int, Edge) const { return INVALID;}
2.511 + Edge edgeFromId(int) const { return INVALID;}
2.512 +
2.513 + /// \brief Gives back an integer greater or equal to the maximum
2.514 + /// Node id.
2.515 + ///
2.516 + /// Gives back an integer greater or equal to the maximum Node
2.517 + /// id.
2.518 + int maxNodeId() const { return -1;}
2.519 +
2.520 + /// \brief Gives back an integer greater or equal to the maximum
2.521 + /// Edge id.
2.522 + ///
2.523 + /// Gives back an integer greater or equal to the maximum Edge
2.524 + /// id.
2.525 + int maxEdgeId() const { return -1;}
2.526
2.527 template <typename _Graph>
2.528 struct Constraints {
2.529 @@ -326,77 +521,98 @@
2.530 typename _Graph::Node node;
2.531 int nid = graph.id(node);
2.532 nid = graph.id(node);
2.533 - node = graph.fromId(nid, Node());
2.534 + node = graph.nodeFromId(nid);
2.535 typename _Graph::Edge edge;
2.536 int eid = graph.id(edge);
2.537 eid = graph.id(edge);
2.538 - edge = graph.fromId(eid, Edge());
2.539 + edge = graph.edgeFromId(eid);
2.540 +
2.541 + nid = graph.maxNodeId();
2.542 + ignore_unused_variable_warning(nid);
2.543 + eid = graph.maxEdgeId();
2.544 + ignore_unused_variable_warning(eid);
2.545 }
2.546
2.547 const _Graph& graph;
2.548 };
2.549 };
2.550
2.551 -
2.552 - /// An empty max-idable base graph class.
2.553 -
2.554 - /// This class provides beside the core graph features
2.555 - /// core max id functions for the graph structure.
2.556 - /// The most of the base graphs should be conform to this concept.
2.557 - /// The id's are unique and immutable.
2.558 - class MaxIDableGraphComponent : virtual public BaseGraphComponent {
2.559 + /// \brief An empty idable base undirected graph class.
2.560 + ///
2.561 + /// This class provides beside the core undirected graph features
2.562 + /// core id functions for the undirected graph structure. The
2.563 + /// most of the base undirected graphs should be conform to this
2.564 + /// concept. The id's are unique and immutable.
2.565 + template <typename _Base = BaseUGraphComponent>
2.566 + class IDableUGraphComponent : public IDableGraphComponent<_Base> {
2.567 public:
2.568
2.569 - /// Gives back an integer greater or equal to the maximum Node id.
2.570 + typedef _Base Base;
2.571 + typedef typename Base::UEdge UEdge;
2.572
2.573 - /// Gives back an integer greater or equal to the maximum Node id.
2.574 + using IDableGraphComponent<_Base>::id;
2.575 +
2.576 + /// \brief Gives back an unique integer id for the UEdge.
2.577 ///
2.578 - int maxId(Node = INVALID) const { return -1;}
2.579 + /// Gives back an unique integer id for the UEdge.
2.580 + ///
2.581 + int id(const UEdge&) const { return -1;}
2.582
2.583 - /// Gives back an integer greater or equal to the maximum Edge id.
2.584 + /// \brief Gives back the undirected edge by the unique id.
2.585 + ///
2.586 + /// Gives back the undirected edge by the unique id. If the
2.587 + /// graph does not contain edge with the given id then the
2.588 + /// result of the function is undetermined.
2.589 + UEdge uEdgeFromId(int) const { return INVALID;}
2.590
2.591 - /// Gives back an integer greater or equal to the maximum Edge id.
2.592 + /// \brief Gives back an integer greater or equal to the maximum
2.593 + /// UEdge id.
2.594 ///
2.595 - int maxId(Edge = INVALID) const { return -1;}
2.596 + /// Gives back an integer greater or equal to the maximum UEdge
2.597 + /// id.
2.598 + int maxUEdgeId() const { return -1;}
2.599
2.600 template <typename _Graph>
2.601 struct Constraints {
2.602
2.603 void constraints() {
2.604 - checkConcept<BaseGraphComponent, _Graph>();
2.605 - int nid = graph.maxId(typename _Graph::Node());
2.606 - ignore_unused_variable_warning(nid);
2.607 - int eid = graph.maxId(typename _Graph::Edge());
2.608 - ignore_unused_variable_warning(eid);
2.609 + checkConcept<Base, _Graph >();
2.610 + checkConcept<IDableGraphComponent<Base>, _Graph >();
2.611 + typename _Graph::UEdge uedge;
2.612 + int ueid = graph.id(uedge);
2.613 + ueid = graph.id(uedge);
2.614 + uedge = graph.uEdgeFromId(ueid);
2.615 + ueid = graph.maxUEdgeId();
2.616 + ignore_unused_variable_warning(ueid);
2.617 }
2.618 -
2.619 +
2.620 const _Graph& graph;
2.621 };
2.622 };
2.623
2.624 - /// An empty extendable base graph class.
2.625 -
2.626 + /// \brief An empty extendable base graph class.
2.627 + ///
2.628 /// This class provides beside the core graph features
2.629 /// core graph extend interface for the graph structure.
2.630 /// The most of the base graphs should be conform to this concept.
2.631 - class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
2.632 + template <typename _Base = BaseGraphComponent>
2.633 + class BaseExtendableGraphComponent : public _Base {
2.634 public:
2.635
2.636 - typedef BaseGraphComponent::Node Node;
2.637 - typedef BaseGraphComponent::Edge Edge;
2.638 + typedef typename _Base::Node Node;
2.639 + typedef typename _Base::Edge Edge;
2.640
2.641 - /// Adds a new Node to the graph.
2.642 -
2.643 - /// Adds a new Node to the graph.
2.644 + /// \brief Adds a new node to the graph.
2.645 + ///
2.646 + /// Adds a new node to the graph.
2.647 ///
2.648 Node addNode() {
2.649 return INVALID;
2.650 }
2.651
2.652 - /// Adds a new Edge connects the two Nodes to the graph.
2.653 -
2.654 - /// Adds a new Edge connects the two Nodes to the graph.
2.655 + /// \brief Adds a new edge connects the given two nodes.
2.656 ///
2.657 + /// Adds a new edge connects the the given two nodes.
2.658 Edge addEdge(const Node&, const Node&) {
2.659 return INVALID;
2.660 }
2.661 @@ -404,7 +620,6 @@
2.662 template <typename _Graph>
2.663 struct Constraints {
2.664 void constraints() {
2.665 - checkConcept<BaseGraphComponent, _Graph >();
2.666 typename _Graph::Node node_a, node_b;
2.667 node_a = graph.addNode();
2.668 node_b = graph.addNode();
2.669 @@ -416,33 +631,75 @@
2.670 };
2.671 };
2.672
2.673 - /// An empty erasable base graph class.
2.674 -
2.675 + /// \brief An empty extendable base undirected graph class.
2.676 + ///
2.677 + /// This class provides beside the core undirected graph features
2.678 + /// core undircted graph extend interface for the graph structure.
2.679 + /// The most of the base graphs should be conform to this concept.
2.680 + template <typename _Base = BaseUGraphComponent>
2.681 + class BaseExtendableUGraphComponent : public _Base {
2.682 + public:
2.683 +
2.684 + typedef typename _Base::Node Node;
2.685 + typedef typename _Base::UEdge UEdge;
2.686 +
2.687 + /// \brief Adds a new node to the graph.
2.688 + ///
2.689 + /// Adds a new node to the graph.
2.690 + ///
2.691 + Node addNode() {
2.692 + return INVALID;
2.693 + }
2.694 +
2.695 + /// \brief Adds a new edge connects the given two nodes.
2.696 + ///
2.697 + /// Adds a new edge connects the the given two nodes.
2.698 + UEdge addEdge(const Node&, const Node&) {
2.699 + return INVALID;
2.700 + }
2.701 +
2.702 + template <typename _Graph>
2.703 + struct Constraints {
2.704 + void constraints() {
2.705 + typename _Graph::Node node_a, node_b;
2.706 + node_a = graph.addNode();
2.707 + node_b = graph.addNode();
2.708 + typename _Graph::UEdge uedge;
2.709 + uedge = graph.addUEdge(node_a, node_b);
2.710 + }
2.711 +
2.712 + _Graph& graph;
2.713 + };
2.714 + };
2.715 +
2.716 + /// \brief An empty erasable base graph class.
2.717 + ///
2.718 /// This class provides beside the core graph features
2.719 /// core erase functions for the graph structure.
2.720 /// The most of the base graphs should be conform to this concept.
2.721 - class BaseErasableGraphComponent : virtual public BaseGraphComponent {
2.722 + template <typename _Base = BaseGraphComponent>
2.723 + class BaseErasableGraphComponent : public _Base {
2.724 public:
2.725
2.726 - typedef BaseGraphComponent::Node Node;
2.727 - typedef BaseGraphComponent::Edge Edge;
2.728 + typedef _Base Base;
2.729 + typedef typename Base::Node Node;
2.730 + typedef typename Base::Edge Edge;
2.731
2.732 - /// Erase a Node from the graph.
2.733 -
2.734 - /// Erase a Node from the graph. This function should not
2.735 + /// \brief Erase a node from the graph.
2.736 + ///
2.737 + /// Erase a node from the graph. This function should not
2.738 /// erase edges connecting to the Node.
2.739 void erase(const Node&) {}
2.740
2.741 - /// Erase an Edge from the graph.
2.742 -
2.743 - /// Erase an Edge from the graph.
2.744 + /// \brief Erase an edge from the graph.
2.745 + ///
2.746 + /// Erase an edge from the graph.
2.747 ///
2.748 void erase(const Edge&) {}
2.749
2.750 template <typename _Graph>
2.751 struct Constraints {
2.752 void constraints() {
2.753 - checkConcept<BaseGraphComponent, _Graph>();
2.754 typename _Graph::Node node;
2.755 graph.erase(node);
2.756 typename _Graph::Edge edge;
2.757 @@ -453,24 +710,61 @@
2.758 };
2.759 };
2.760
2.761 - /// An empty clearable base graph class.
2.762 -
2.763 + /// \brief An empty erasable base undirected graph class.
2.764 + ///
2.765 + /// This class provides beside the core undirected graph features
2.766 + /// core erase functions for the undirceted graph structure.
2.767 + template <typename _Base = BaseUGraphComponent>
2.768 + class BaseErasableUGraphComponent : public _Base {
2.769 + public:
2.770 +
2.771 + typedef _Base Base;
2.772 + typedef typename Base::Node Node;
2.773 + typedef typename Base::UEdge UEdge;
2.774 +
2.775 + /// \brief Erase a node from the graph.
2.776 + ///
2.777 + /// Erase a node from the graph. This function should not
2.778 + /// erase edges connecting to the Node.
2.779 + void erase(const Node&) {}
2.780 +
2.781 + /// \brief Erase an edge from the graph.
2.782 + ///
2.783 + /// Erase an edge from the graph.
2.784 + ///
2.785 + void erase(const UEdge&) {}
2.786 +
2.787 + template <typename _Graph>
2.788 + struct Constraints {
2.789 + void constraints() {
2.790 + typename _Graph::Node node;
2.791 + graph.erase(node);
2.792 + typename _Graph::Edge edge;
2.793 + graph.erase(edge);
2.794 + }
2.795 +
2.796 + _Graph& graph;
2.797 + };
2.798 + };
2.799 +
2.800 + /// \brief An empty clearable base graph class.
2.801 + ///
2.802 /// This class provides beside the core graph features
2.803 /// core clear functions for the graph structure.
2.804 /// The most of the base graphs should be conform to this concept.
2.805 - class BaseClearableGraphComponent : virtual public BaseGraphComponent {
2.806 + template <typename _Base = BaseGraphComponent>
2.807 + class BaseClearableGraphComponent : public _Base {
2.808 public:
2.809
2.810 - /// Erase all the Nodes and Edges from the graph.
2.811 -
2.812 - /// Erase all the Nodes and Edges from the graph.
2.813 + /// \brief Erase all the nodes and edges from the graph.
2.814 + ///
2.815 + /// Erase all the nodes and edges from the graph.
2.816 ///
2.817 void clear() {}
2.818
2.819 template <typename _Graph>
2.820 struct Constraints {
2.821 void constraints() {
2.822 - checkConcept<BaseGraphComponent, _Graph>();
2.823 graph.clear();
2.824 }
2.825
2.826 @@ -478,72 +772,90 @@
2.827 };
2.828 };
2.829
2.830 + /// \brief An empty clearable base undirected graph class.
2.831 + ///
2.832 + /// This class provides beside the core undirected graph features
2.833 + /// core clear functions for the undirected graph structure.
2.834 + /// The most of the base graphs should be conform to this concept.
2.835 + template <typename _Base = BaseUGraphComponent>
2.836 + class BaseClearableUGraphComponent : public _Base {
2.837 + public:
2.838
2.839 - /// Skeleton class for graph NodeIt and EdgeIt
2.840 + /// \brief Erase all the nodes and undirected edges from the graph.
2.841 + ///
2.842 + /// Erase all the nodes and undirected edges from the graph.
2.843 + ///
2.844 + void clear() {}
2.845
2.846 + template <typename _Graph>
2.847 + struct Constraints {
2.848 + void constraints() {
2.849 + graph.clear();
2.850 + }
2.851 +
2.852 + _Graph graph;
2.853 + };
2.854 + };
2.855 +
2.856 +
2.857 + /// \brief Skeleton class for graph NodeIt and EdgeIt
2.858 + ///
2.859 /// Skeleton class for graph NodeIt and EdgeIt.
2.860 ///
2.861 template <typename _Graph, typename _Item>
2.862 - class GraphIterator : public _Item {
2.863 + class GraphItemIt : public _Item {
2.864 public:
2.865 - /// \todo Don't we need the Item type as typedef?
2.866 -
2.867 - /// Default constructor.
2.868 -
2.869 + /// \brief Default constructor.
2.870 + ///
2.871 /// @warning The default constructor sets the iterator
2.872 /// to an undefined value.
2.873 - GraphIterator() {}
2.874 - /// Copy constructor.
2.875 -
2.876 + GraphItemIt() {}
2.877 + /// \brief Copy constructor.
2.878 + ///
2.879 /// Copy constructor.
2.880 ///
2.881 - GraphIterator(GraphIterator const&) {}
2.882 - /// Sets the iterator to the first item.
2.883 -
2.884 + GraphItemIt(const GraphItemIt& ) {}
2.885 + /// \brief Sets the iterator to the first item.
2.886 + ///
2.887 /// Sets the iterator to the first item of \c the graph.
2.888 ///
2.889 - explicit GraphIterator(const _Graph&) {}
2.890 - /// Invalid constructor \& conversion.
2.891 -
2.892 + explicit GraphItemIt(const _Graph&) {}
2.893 + /// \brief Invalid constructor \& conversion.
2.894 + ///
2.895 /// This constructor initializes the item to be invalid.
2.896 /// \sa Invalid for more details.
2.897 - GraphIterator(Invalid) {}
2.898 - /// Assign operator for items.
2.899 -
2.900 + GraphItemIt(Invalid) {}
2.901 + /// \brief Assign operator for items.
2.902 + ///
2.903 /// The items are assignable.
2.904 ///
2.905 - GraphIterator& operator=(GraphIterator const&) { return *this; }
2.906 - /// Next item.
2.907 -
2.908 + GraphItemIt& operator=(const GraphItemIt&) { return *this; }
2.909 + /// \brief Next item.
2.910 + ///
2.911 /// Assign the iterator to the next item.
2.912 ///
2.913 - GraphIterator& operator++() { return *this; }
2.914 - // Node operator*() const { return INVALID; }
2.915 - /// Equality operator
2.916 -
2.917 + GraphItemIt& operator++() { return *this; }
2.918 + /// \brief Equality operator
2.919 + ///
2.920 /// Two iterators are equal if and only if they point to the
2.921 /// same object or both are invalid.
2.922 - bool operator==(const GraphIterator&) const { return true;}
2.923 - /// Inequality operator
2.924 -
2.925 + bool operator==(const GraphItemIt&) const { return true;}
2.926 + /// \brief Inequality operator
2.927 + ///
2.928 /// \sa operator==(Node n)
2.929 ///
2.930 - bool operator!=(const GraphIterator&) const { return true;}
2.931 + bool operator!=(const GraphItemIt&) const { return true;}
2.932
2.933 - template<typename _GraphIterator>
2.934 + template<typename _GraphItemIt>
2.935 struct Constraints {
2.936 void constraints() {
2.937 - // checkConcept< Item, _GraphIterator >();
2.938 - _GraphIterator it1(g);
2.939 -
2.940 - /// \todo Do we need NodeIt(Node) kind of constructor?
2.941 - // _GraphIterator it2(bj);
2.942 - _GraphIterator it2;
2.943 + _GraphItemIt it1(g);
2.944 + _GraphItemIt it2;
2.945
2.946 it2 = ++it1;
2.947 ++it2 = it1;
2.948 ++(++it1);
2.949 - /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
2.950 +
2.951 _Item bi = it1;
2.952 bi = it2;
2.953 }
2.954 @@ -551,131 +863,126 @@
2.955 };
2.956 };
2.957
2.958 - /// Skeleton class for graph InEdgeIt and OutEdgeIt
2.959 -
2.960 + /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt
2.961 + ///
2.962 /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
2.963 /// base class, the _selector is a additional template parameter. For
2.964 /// InEdgeIt you should instantiate it with character 'i' and for
2.965 /// OutEdgeIt with 'o'.
2.966 - /// \todo Is this a good name for this concept?
2.967 - template <typename Graph,
2.968 - typename Edge = typename Graph::Edge,
2.969 + template <typename _Graph,
2.970 + typename _Item = typename _Graph::Edge,
2.971 + typename _Base = typename _Graph::Node,
2.972 char _selector = '0'>
2.973 - class GraphIncIterator : public Edge {
2.974 + class GraphIncIt : public _Item {
2.975 public:
2.976 - /// Default constructor.
2.977 -
2.978 + /// \brief Default constructor.
2.979 + ///
2.980 /// @warning The default constructor sets the iterator
2.981 /// to an undefined value.
2.982 - GraphIncIterator() {}
2.983 - /// Copy constructor.
2.984 -
2.985 + GraphIncIt() {}
2.986 + /// \brief Copy constructor.
2.987 + ///
2.988 /// Copy constructor.
2.989 ///
2.990 - GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {}
2.991 - /// Sets the iterator to the first edge incoming into or outgoing
2.992 + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
2.993 + /// \brief Sets the iterator to the first edge incoming into or outgoing
2.994 /// from the node.
2.995 -
2.996 + ///
2.997 /// Sets the iterator to the first edge incoming into or outgoing
2.998 /// from the node.
2.999 ///
2.1000 - explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
2.1001 - /// Invalid constructor \& conversion.
2.1002 -
2.1003 + explicit GraphIncIt(const _Graph&, const _Base&) {}
2.1004 + /// \brief Invalid constructor \& conversion.
2.1005 + ///
2.1006 /// This constructor initializes the item to be invalid.
2.1007 /// \sa Invalid for more details.
2.1008 - GraphIncIterator(Invalid) {}
2.1009 - /// Assign operator for nodes.
2.1010 + GraphIncIt(Invalid) {}
2.1011 + /// \brief Assign operator for iterators.
2.1012 + ///
2.1013 + /// The iterators are assignable.
2.1014 + ///
2.1015 + GraphIncIt& operator=(GraphIncIt const&) { return *this; }
2.1016 + /// \brief Next item.
2.1017 + ///
2.1018 + /// Assign the iterator to the next item.
2.1019 + ///
2.1020 + GraphIncIt& operator++() { return *this; }
2.1021
2.1022 - /// The nodes are assignable.
2.1023 + /// \brief Equality operator
2.1024 ///
2.1025 - GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }
2.1026 - /// Next edge.
2.1027 -
2.1028 - /// Assign the iterator to the next node.
2.1029 - ///
2.1030 - GraphIncIterator& operator++() { return *this; }
2.1031 -
2.1032 - // Node operator*() const { return INVALID; }
2.1033 -
2.1034 - /// Equality operator
2.1035 -
2.1036 /// Two iterators are equal if and only if they point to the
2.1037 /// same object or both are invalid.
2.1038 - bool operator==(const GraphIncIterator&) const { return true;}
2.1039 + bool operator==(const GraphIncIt&) const { return true;}
2.1040
2.1041 - /// Inequality operator
2.1042 -
2.1043 + /// \brief Inequality operator
2.1044 + ///
2.1045 /// \sa operator==(Node n)
2.1046 ///
2.1047 - bool operator!=(const GraphIncIterator&) const { return true;}
2.1048 + bool operator!=(const GraphIncIt&) const { return true;}
2.1049
2.1050 - template <typename _GraphIncIterator>
2.1051 + template <typename _GraphIncIt>
2.1052 struct Constraints {
2.1053 - typedef typename Graph::Node Node;
2.1054 void constraints() {
2.1055 - checkConcept<GraphItem<'e'>, _GraphIncIterator>();
2.1056 - _GraphIncIterator it1(graph, node);
2.1057 - /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
2.1058 - // _GraphIncIterator it2(edge);
2.1059 - _GraphIncIterator it2;
2.1060 + checkConcept<GraphItem<_selector>, _GraphIncIt>();
2.1061 + _GraphIncIt it1(graph, node);
2.1062 + _GraphIncIt it2;
2.1063
2.1064 it2 = ++it1;
2.1065 ++it2 = it1;
2.1066 ++(++it1);
2.1067 - Edge e = it1;
2.1068 + _Item e = it1;
2.1069 e = it2;
2.1070
2.1071 - const_constraits();
2.1072 }
2.1073
2.1074 - void const_constraits() {
2.1075 - Node n = graph.baseNode(it);
2.1076 - n = graph.runningNode(it);
2.1077 - }
2.1078 -
2.1079 - Edge edge;
2.1080 - Node node;
2.1081 - Graph graph;
2.1082 - _GraphIncIterator it;
2.1083 + _Item edge;
2.1084 + _Base node;
2.1085 + _Graph graph;
2.1086 + _GraphIncIt it;
2.1087 };
2.1088 };
2.1089
2.1090
2.1091 - /// An empty iterable base graph class.
2.1092 -
2.1093 + /// \brief An empty iterable graph class.
2.1094 + ///
2.1095 /// This class provides beside the core graph features
2.1096 /// iterator based iterable interface for the graph structure.
2.1097 /// This concept is part of the GraphConcept.
2.1098 - class IterableGraphComponent : virtual public BaseGraphComponent {
2.1099 + template <typename _Base = BaseGraphComponent>
2.1100 + class IterableGraphComponent : public _Base {
2.1101
2.1102 public:
2.1103
2.1104 + typedef _Base Base;
2.1105 + typedef typename Base::Node Node;
2.1106 + typedef typename Base::Edge Edge;
2.1107 +
2.1108 typedef IterableGraphComponent Graph;
2.1109
2.1110 - typedef BaseGraphComponent::Node Node;
2.1111 - typedef BaseGraphComponent::Edge Edge;
2.1112
2.1113 - /// This iterator goes through each node.
2.1114 -
2.1115 + /// \brief This iterator goes through each node.
2.1116 + ///
2.1117 /// This iterator goes through each node.
2.1118 ///
2.1119 - typedef GraphIterator<Graph, Node> NodeIt;
2.1120 - /// This iterator goes through each node.
2.1121 + typedef GraphItemIt<Graph, Node> NodeIt;
2.1122
2.1123 + /// \brief This iterator goes through each node.
2.1124 + ///
2.1125 /// This iterator goes through each node.
2.1126 ///
2.1127 - typedef GraphIterator<Graph, Edge> EdgeIt;
2.1128 - /// This iterator goes trough the incoming edges of a node.
2.1129 + typedef GraphItemIt<Graph, Edge> EdgeIt;
2.1130
2.1131 + /// \brief This iterator goes trough the incoming edges of a node.
2.1132 + ///
2.1133 /// This iterator goes trough the \e inccoming edges of a certain node
2.1134 /// of a graph.
2.1135 - typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
2.1136 - /// This iterator goes trough the outgoing edges of a node.
2.1137 + typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt;
2.1138
2.1139 + /// \brief This iterator goes trough the outgoing edges of a node.
2.1140 + ///
2.1141 /// This iterator goes trough the \e outgoing edges of a certain node
2.1142 /// of a graph.
2.1143 - typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
2.1144 + typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt;
2.1145
2.1146 /// \brief The base node of the iterator.
2.1147 ///
2.1148 @@ -711,18 +1018,87 @@
2.1149 template <typename _Graph>
2.1150 struct Constraints {
2.1151 void constraints() {
2.1152 - checkConcept< BaseGraphComponent, _Graph>();
2.1153 + checkConcept<Base, _Graph>();
2.1154
2.1155 - checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
2.1156 + checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
2.1157 typename _Graph::EdgeIt >();
2.1158 - checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
2.1159 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
2.1160 typename _Graph::NodeIt >();
2.1161 - checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt>();
2.1162 - checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt>();
2.1163 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
2.1164 + typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
2.1165 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
2.1166 + typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
2.1167
2.1168 - typename _Graph::Node n(INVALID);
2.1169 - typename _Graph::Edge e(INVALID);
2.1170 - n = graph.oppositeNode(n, e);
2.1171 + typename _Graph::Node n;
2.1172 + typename _Graph::InEdgeIt ieit(INVALID);
2.1173 + typename _Graph::OutEdgeIt oeit(INVALID);
2.1174 + n = graph.baseNode(ieit);
2.1175 + n = graph.runningNode(ieit);
2.1176 + n = graph.baseNode(oeit);
2.1177 + n = graph.runningNode(oeit);
2.1178 + ignore_unused_variable_warning(n);
2.1179 + }
2.1180 +
2.1181 + const _Graph& graph;
2.1182 +
2.1183 + };
2.1184 + };
2.1185 +
2.1186 + /// \brief An empty iterable undirected graph class.
2.1187 + ///
2.1188 + /// This class provides beside the core graph features iterator
2.1189 + /// based iterable interface for the undirected graph structure.
2.1190 + /// This concept is part of the GraphConcept.
2.1191 + template <typename _Base = BaseUGraphComponent>
2.1192 + class IterableUGraphComponent : public IterableGraphComponent<_Base> {
2.1193 + public:
2.1194 +
2.1195 + typedef _Base Base;
2.1196 + typedef typename Base::Node Node;
2.1197 + typedef typename Base::Edge Edge;
2.1198 + typedef typename Base::UEdge UEdge;
2.1199 +
2.1200 +
2.1201 + typedef IterableUGraphComponent Graph;
2.1202 + using IterableGraphComponent<_Base>::baseNode;
2.1203 + using IterableGraphComponent<_Base>::runningNode;
2.1204 +
2.1205 +
2.1206 + /// \brief This iterator goes through each node.
2.1207 + ///
2.1208 + /// This iterator goes through each node.
2.1209 + typedef GraphItemIt<Graph, UEdge> UEdgeIt;
2.1210 + /// \brief This iterator goes trough the incident edges of a
2.1211 + /// node.
2.1212 + ///
2.1213 + /// This iterator goes trough the incident edges of a certain
2.1214 + /// node of a graph.
2.1215 + typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt;
2.1216 + /// \brief The base node of the iterator.
2.1217 + ///
2.1218 + /// Gives back the base node of the iterator.
2.1219 + Node baseNode(const IncEdgeIt&) const { return INVALID; }
2.1220 +
2.1221 + /// \brief The running node of the iterator.
2.1222 + ///
2.1223 + /// Gives back the running node of the iterator.
2.1224 + Node runningNode(const IncEdgeIt&) const { return INVALID; }
2.1225 +
2.1226 + template <typename _Graph>
2.1227 + struct Constraints {
2.1228 + void constraints() {
2.1229 + checkConcept<Base, _Graph>();
2.1230 + checkConcept<IterableGraphComponent<Base>, _Graph>();
2.1231 +
2.1232 + checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
2.1233 + typename _Graph::UEdgeIt >();
2.1234 + checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
2.1235 + typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
2.1236 +
2.1237 + typename _Graph::Node n;
2.1238 + typename _Graph::IncEdgeIt ueit(INVALID);
2.1239 + n = graph.baseNode(ueit);
2.1240 + n = graph.runningNode(ueit);
2.1241 }
2.1242
2.1243 const _Graph& graph;
2.1244 @@ -730,50 +1106,126 @@
2.1245 };
2.1246 };
2.1247
2.1248 - /// An empty alteration notifier base graph class.
2.1249 -
2.1250 - /// This class provides beside the core graph features
2.1251 - /// alteration notifier interface for the graph structure.
2.1252 - /// This is an observer-notifier pattern. More Obsevers can
2.1253 - /// be registered into the notifier and whenever an alteration
2.1254 - /// occured in the graph all the observers will notified about it.
2.1255 - class AlterableGraphComponent : virtual public BaseIterableGraphComponent {
2.1256 + /// \brief An empty alteration notifier graph class.
2.1257 + ///
2.1258 + /// This class provides beside the core graph features alteration
2.1259 + /// notifier interface for the graph structure. This implements
2.1260 + /// an observer-notifier pattern for each graph item. More
2.1261 + /// obsevers can be registered into the notifier and whenever an
2.1262 + /// alteration occured in the graph all the observers will
2.1263 + /// notified about it.
2.1264 + template <typename _Base = BaseGraphComponent>
2.1265 + class AlterableGraphComponent : public _Base {
2.1266 public:
2.1267
2.1268 + typedef _Base Base;
2.1269 + typedef typename Base::Node Node;
2.1270 + typedef typename Base::Edge Edge;
2.1271 +
2.1272 +
2.1273 + /// The node observer registry.
2.1274 + typedef AlterationNotifier<AlterableGraphComponent, Node>
2.1275 + NodeNotifier;
2.1276 /// The edge observer registry.
2.1277 typedef AlterationNotifier<AlterableGraphComponent, Edge>
2.1278 EdgeNotifier;
2.1279 - /// The node observer registry.
2.1280 - typedef AlterationNotifier<AlterableGraphComponent, Node>
2.1281 - NodeNotifier;
2.1282 +
2.1283 + /// \brief Gives back the node alteration notifier.
2.1284 + ///
2.1285 + /// Gives back the node alteration notifier.
2.1286 + NodeNotifier& getNotifier(Node) const {
2.1287 + return NodeNotifier();
2.1288 + }
2.1289
2.1290 /// \brief Gives back the edge alteration notifier.
2.1291 ///
2.1292 /// Gives back the edge alteration notifier.
2.1293 - EdgeNotifier getNotifier(Edge) const {
2.1294 + EdgeNotifier& getNotifier(Edge) const {
2.1295 return EdgeNotifier();
2.1296 }
2.1297 -
2.1298 - /// \brief Gives back the node alteration notifier.
2.1299 - ///
2.1300 - /// Gives back the node alteration notifier.
2.1301 - NodeNotifier getNotifier(Node) const {
2.1302 - return NodeNotifier();
2.1303 - }
2.1304 +
2.1305 + template <typename _Graph>
2.1306 + struct Constraints {
2.1307 + void constraints() {
2.1308 + checkConcept<Base, _Graph>();
2.1309 + typename _Graph::NodeNotifier& nn
2.1310 + = graph.getNotifier(typename _Graph::Node());
2.1311 +
2.1312 + typename _Graph::EdgeNotifier& en
2.1313 + = graph.getNotifier(typename _Graph::Edge());
2.1314 +
2.1315 + ignore_unused_variable_warning(nn);
2.1316 + ignore_unused_variable_warning(en);
2.1317 + }
2.1318 +
2.1319 + const _Graph& graph;
2.1320 +
2.1321 + };
2.1322
2.1323 };
2.1324
2.1325 + /// \brief An empty alteration notifier undirected graph class.
2.1326 + ///
2.1327 + /// This class provides beside the core graph features alteration
2.1328 + /// notifier interface for the graph structure. This implements
2.1329 + /// an observer-notifier pattern for each graph item. More
2.1330 + /// obsevers can be registered into the notifier and whenever an
2.1331 + /// alteration occured in the graph all the observers will
2.1332 + /// notified about it.
2.1333 + template <typename _Base = BaseUGraphComponent>
2.1334 + class AlterableUGraphComponent : public AlterableGraphComponent<_Base> {
2.1335 + public:
2.1336
2.1337 - /// Class describing the concept of graph maps
2.1338 + typedef _Base Base;
2.1339 + typedef typename Base::UEdge UEdge;
2.1340
2.1341 +
2.1342 + /// The edge observer registry.
2.1343 + typedef AlterationNotifier<AlterableUGraphComponent, UEdge>
2.1344 + UEdgeNotifier;
2.1345 +
2.1346 + /// \brief Gives back the edge alteration notifier.
2.1347 + ///
2.1348 + /// Gives back the edge alteration notifier.
2.1349 + UEdgeNotifier& getNotifier(UEdge) const {
2.1350 + return UEdgeNotifier();
2.1351 + }
2.1352 +
2.1353 + template <typename _Graph>
2.1354 + struct Constraints {
2.1355 + void constraints() {
2.1356 + checkConcept<Base, _Graph>();
2.1357 + checkConcept<AlterableGraphComponent, _Graph>();
2.1358 + typename _Graph::UEdgeNotifier& uen
2.1359 + = graph.getNotifier(typename _Graph::UEdge());
2.1360 + ignore_unused_variable_warning(uen);
2.1361 + }
2.1362 +
2.1363 + const _Graph& graph;
2.1364 +
2.1365 + };
2.1366 +
2.1367 + };
2.1368 +
2.1369 +
2.1370 + /// \brief Class describing the concept of graph maps
2.1371 + ///
2.1372 /// This class describes the common interface of the graph maps
2.1373 /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to
2.1374 /// associate data to graph descriptors (nodes or edges).
2.1375 - template <typename Graph, typename Item, typename _Value>
2.1376 - class GraphMap : public ReadWriteMap<Item, _Value> {
2.1377 - protected:
2.1378 - GraphMap() {}
2.1379 + template <typename _Graph, typename _Item, typename _Value>
2.1380 + class GraphMap : public ReadWriteMap<_Item, _Value> {
2.1381 public:
2.1382 +
2.1383 + typedef ReadWriteMap<_Item, _Value> Parent;
2.1384 +
2.1385 + /// The graph type of the map.
2.1386 + typedef _Graph Graph;
2.1387 + /// The key type of the map.
2.1388 + typedef _Item Key;
2.1389 + /// The value type of the map.
2.1390 + typedef _Value Value;
2.1391 +
2.1392 /// \brief Construct a new map.
2.1393 ///
2.1394 /// Construct a new map for the graph.
2.1395 @@ -781,29 +1233,39 @@
2.1396 /// \brief Construct a new map with default value.
2.1397 ///
2.1398 /// Construct a new map for the graph and initalise the values.
2.1399 - GraphMap(const Graph&, const _Value&) {}
2.1400 + GraphMap(const Graph&, const Value&) {}
2.1401 /// \brief Copy constructor.
2.1402 ///
2.1403 /// Copy Constructor.
2.1404 - GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
2.1405 + GraphMap(const GraphMap&) : Parent() {}
2.1406
2.1407 /// \brief Assign operator.
2.1408 ///
2.1409 - /// Assign operator.
2.1410 - GraphMap& operator=(const GraphMap&) { return *this;}
2.1411 + /// Assign operator. It does not mofify the underlying graph,
2.1412 + /// it just iterates on the current item set and set the map
2.1413 + /// with the value returned by the assigned map.
2.1414 + template <typename CMap>
2.1415 + GraphMap& operator=(const CMap&) {
2.1416 + checkConcept<ReadMap<Key, Value>, CMap>();
2.1417 + return *this;
2.1418 + }
2.1419
2.1420 template<typename _Map>
2.1421 struct Constraints {
2.1422 void constraints() {
2.1423 - checkConcept<ReadWriteMap<Item, _Value>, _Map >();
2.1424 + checkConcept<ReadWriteMap<Key, Value>, _Map >();
2.1425 // Construction with a graph parameter
2.1426 _Map a(g);
2.1427 // Constructor with a graph and a default value parameter
2.1428 _Map a2(g,t);
2.1429 - // Copy constructor. Do we need it?
2.1430 - _Map b=c;
2.1431 + // Copy constructor.
2.1432 + _Map b(c);
2.1433 +
2.1434 + ReadMap<Key, Value> cmap;
2.1435 + b = cmap;
2.1436
2.1437 ignore_unused_variable_warning(a2);
2.1438 + ignore_unused_variable_warning(b);
2.1439 }
2.1440
2.1441 const _Map &c;
2.1442 @@ -813,90 +1275,111 @@
2.1443
2.1444 };
2.1445
2.1446 - /// An empty mappable base graph class.
2.1447 -
2.1448 + /// \brief An empty mappable graph class.
2.1449 + ///
2.1450 /// This class provides beside the core graph features
2.1451 /// map interface for the graph structure.
2.1452 - /// This concept is part of the GraphConcept.
2.1453 - class MappableGraphComponent : virtual public BaseGraphComponent {
2.1454 + /// This concept is part of the Graph concept.
2.1455 + template <typename _Base = BaseGraphComponent>
2.1456 + class MappableGraphComponent : public _Base {
2.1457 public:
2.1458
2.1459 + typedef _Base Base;
2.1460 + typedef typename Base::Node Node;
2.1461 + typedef typename Base::Edge Edge;
2.1462 +
2.1463 typedef MappableGraphComponent Graph;
2.1464
2.1465 - typedef BaseGraphComponent::Node Node;
2.1466 - typedef BaseGraphComponent::Edge Edge;
2.1467 -
2.1468 - /// ReadWrite map of the nodes.
2.1469 -
2.1470 + /// \brief ReadWrite map of the nodes.
2.1471 + ///
2.1472 /// ReadWrite map of the nodes.
2.1473 ///
2.1474 - template <typename _Value>
2.1475 - class NodeMap : public GraphMap<Graph, Node, _Value> {
2.1476 + template <typename Value>
2.1477 + class NodeMap : public GraphMap<Graph, Node, Value> {
2.1478 private:
2.1479 NodeMap();
2.1480 public:
2.1481 + typedef GraphMap<Graph, Node, Value> Parent;
2.1482 +
2.1483 /// \brief Construct a new map.
2.1484 ///
2.1485 /// Construct a new map for the graph.
2.1486 /// \todo call the right parent class constructor
2.1487 - explicit NodeMap(const Graph&) {}
2.1488 + explicit NodeMap(const Graph& graph) : Parent(graph) {}
2.1489 +
2.1490 /// \brief Construct a new map with default value.
2.1491 ///
2.1492 /// Construct a new map for the graph and initalise the values.
2.1493 - NodeMap(const Graph&, const _Value&) {}
2.1494 + NodeMap(const Graph& graph, const Value& value)
2.1495 + : Parent(graph, value) {}
2.1496 +
2.1497 /// \brief Copy constructor.
2.1498 ///
2.1499 /// Copy Constructor.
2.1500 - NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
2.1501 + NodeMap(const NodeMap& nm) : Parent(nm) {}
2.1502
2.1503 /// \brief Assign operator.
2.1504 ///
2.1505 /// Assign operator.
2.1506 - NodeMap& operator=(const NodeMap&) { return *this;}
2.1507 + template <typename CMap>
2.1508 + NodeMap& operator=(const CMap&) {
2.1509 + checkConcept<ReadMap<Node, Value>, CMap>();
2.1510 + return *this;
2.1511 + }
2.1512
2.1513 };
2.1514
2.1515 - /// ReadWrite map of the edges.
2.1516 -
2.1517 + /// \brief ReadWrite map of the edges.
2.1518 + ///
2.1519 /// ReadWrite map of the edges.
2.1520 ///
2.1521 - template <typename _Value>
2.1522 - class EdgeMap : public GraphMap<Graph, Edge, _Value> {
2.1523 + template <typename Value>
2.1524 + class EdgeMap : public GraphMap<Graph, Edge, Value> {
2.1525 private:
2.1526 EdgeMap();
2.1527 public:
2.1528 + typedef GraphMap<Graph, Edge, Value> Parent;
2.1529 +
2.1530 /// \brief Construct a new map.
2.1531 ///
2.1532 /// Construct a new map for the graph.
2.1533 /// \todo call the right parent class constructor
2.1534 - explicit EdgeMap(const Graph&) {}
2.1535 + explicit EdgeMap(const Graph& graph) : Parent(graph) {}
2.1536 +
2.1537 /// \brief Construct a new map with default value.
2.1538 ///
2.1539 /// Construct a new map for the graph and initalise the values.
2.1540 - EdgeMap(const Graph&, const _Value&) {}
2.1541 + EdgeMap(const Graph& graph, const Value& value)
2.1542 + : Parent(graph, value) {}
2.1543 +
2.1544 /// \brief Copy constructor.
2.1545 ///
2.1546 /// Copy Constructor.
2.1547 - EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
2.1548 + EdgeMap(const EdgeMap& nm) : Parent(nm) {}
2.1549
2.1550 /// \brief Assign operator.
2.1551 ///
2.1552 /// Assign operator.
2.1553 - EdgeMap& operator=(const EdgeMap&) { return *this;}
2.1554 + template <typename CMap>
2.1555 + EdgeMap& operator=(const CMap&) {
2.1556 + checkConcept<ReadMap<Edge, Value>, CMap>();
2.1557 + return *this;
2.1558 + }
2.1559
2.1560 };
2.1561
2.1562 +
2.1563 template <typename _Graph>
2.1564 struct Constraints {
2.1565
2.1566 - struct Type {
2.1567 + struct Dummy {
2.1568 int value;
2.1569 - Type() : value(0) {}
2.1570 - Type(int _v) : value(_v) {}
2.1571 + Dummy() : value(0) {}
2.1572 + Dummy(int _v) : value(_v) {}
2.1573 };
2.1574
2.1575 void constraints() {
2.1576 - checkConcept<BaseGraphComponent, _Graph>();
2.1577 + checkConcept<Base, _Graph>();
2.1578 { // int map test
2.1579 typedef typename _Graph::template NodeMap<int> IntNodeMap;
2.1580 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
2.1581 @@ -905,10 +1388,10 @@
2.1582 typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
2.1583 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
2.1584 BoolNodeMap >();
2.1585 - } { // Type map test
2.1586 - typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
2.1587 - checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
2.1588 - TypeNodeMap >();
2.1589 + } { // Dummy map test
2.1590 + typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap;
2.1591 + checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>,
2.1592 + DummyNodeMap >();
2.1593 }
2.1594
2.1595 { // int map test
2.1596 @@ -919,10 +1402,10 @@
2.1597 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
2.1598 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
2.1599 BoolEdgeMap >();
2.1600 - } { // Type map test
2.1601 - typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
2.1602 - checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
2.1603 - TypeEdgeMap >();
2.1604 + } { // Dummy map test
2.1605 + typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
2.1606 + checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
2.1607 + DummyEdgeMap >();
2.1608 }
2.1609 }
2.1610
2.1611 @@ -930,135 +1413,59 @@
2.1612 };
2.1613 };
2.1614
2.1615 -
2.1616 -// /// Skeleton class which describes an edge with direction in \ref
2.1617 -// /// UGraph "undirected graph".
2.1618 - template <typename UGraph>
2.1619 - class UGraphEdge : public UGraph::UEdge {
2.1620 - typedef typename UGraph::UEdge UEdge;
2.1621 - typedef typename UGraph::Node Node;
2.1622 + /// \brief An empty mappable base graph class.
2.1623 + ///
2.1624 + /// This class provides beside the core graph features
2.1625 + /// map interface for the graph structure.
2.1626 + /// This concept is part of the UGraph concept.
2.1627 + template <typename _Base = BaseUGraphComponent>
2.1628 + class MappableUGraphComponent : public MappableGraphComponent<_Base> {
2.1629 public:
2.1630
2.1631 - /// \e
2.1632 - UGraphEdge() {}
2.1633 + typedef _Base Base;
2.1634 + typedef typename Base::UEdge UEdge;
2.1635
2.1636 - /// \e
2.1637 - UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
2.1638 + typedef MappableUGraphComponent Graph;
2.1639
2.1640 - /// \e
2.1641 - UGraphEdge(Invalid) {}
2.1642 + /// \brief ReadWrite map of the uedges.
2.1643 + ///
2.1644 + /// ReadWrite map of the uedges.
2.1645 + ///
2.1646 + template <typename Value>
2.1647 + class UEdgeMap : public GraphMap<Graph, UEdge, Value> {
2.1648 + public:
2.1649 + typedef GraphMap<Graph, UEdge, Value> Parent;
2.1650
2.1651 - /// \brief Directed edge from undirected edge and a source node.
2.1652 - ///
2.1653 - /// Constructs a directed edge from undirected edge and a source node.
2.1654 - ///
2.1655 - /// \note You have to specify the graph for this constructor.
2.1656 - UGraphEdge(const UGraph &g,
2.1657 - UEdge u_edge, Node n) {
2.1658 - ignore_unused_variable_warning(u_edge);
2.1659 - ignore_unused_variable_warning(g);
2.1660 - ignore_unused_variable_warning(n);
2.1661 - }
2.1662 + /// \brief Construct a new map.
2.1663 + ///
2.1664 + /// Construct a new map for the graph.
2.1665 + /// \todo call the right parent class constructor
2.1666 + explicit UEdgeMap(const Graph& graph) : Parent(graph) {}
2.1667
2.1668 - /// \e
2.1669 - UGraphEdge& operator=(UGraphEdge) { return *this; }
2.1670 + /// \brief Construct a new map with default value.
2.1671 + ///
2.1672 + /// Construct a new map for the graph and initalise the values.
2.1673 + UEdgeMap(const Graph& graph, const Value& value)
2.1674 + : Parent(graph, value) {}
2.1675
2.1676 - /// \e
2.1677 - bool operator==(UGraphEdge) const { return true; }
2.1678 - /// \e
2.1679 - bool operator!=(UGraphEdge) const { return false; }
2.1680 + /// \brief Copy constructor.
2.1681 + ///
2.1682 + /// Copy Constructor.
2.1683 + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {}
2.1684
2.1685 - /// \e
2.1686 - bool operator<(UGraphEdge) const { return false; }
2.1687 + /// \brief Assign operator.
2.1688 + ///
2.1689 + /// Assign operator.
2.1690 + template <typename CMap>
2.1691 + UEdgeMap& operator=(const CMap&) {
2.1692 + checkConcept<ReadMap<UEdge, Value>, CMap>();
2.1693 + return *this;
2.1694 + }
2.1695
2.1696 - template <typename Edge>
2.1697 - struct Constraints {
2.1698 - void constraints() {
2.1699 - const_constraints();
2.1700 - }
2.1701 - void const_constraints() const {
2.1702 - /// \bug This should be is_base_and_derived ...
2.1703 - UEdge ue = e;
2.1704 - ue = e;
2.1705 -
2.1706 - Edge e_with_source(graph,ue,n);
2.1707 - ignore_unused_variable_warning(e_with_source);
2.1708 - }
2.1709 - Edge e;
2.1710 - UEdge ue;
2.1711 - UGraph graph;
2.1712 - Node n;
2.1713 - };
2.1714 - };
2.1715 -
2.1716 -
2.1717 - struct BaseIterableUGraphConcept {
2.1718 -
2.1719 - template <typename Graph>
2.1720 - struct Constraints {
2.1721 -
2.1722 - typedef typename Graph::UEdge UEdge;
2.1723 - typedef typename Graph::Edge Edge;
2.1724 - typedef typename Graph::Node Node;
2.1725 -
2.1726 - void constraints() {
2.1727 - checkConcept<BaseIterableGraphComponent, Graph>();
2.1728 - checkConcept<GraphItem<>, UEdge>();
2.1729 - //checkConcept<UGraphEdge<Graph>, Edge>();
2.1730 -
2.1731 - graph.first(ue);
2.1732 - graph.next(ue);
2.1733 -
2.1734 - const_constraints();
2.1735 - }
2.1736 - void const_constraints() {
2.1737 - Node n;
2.1738 - n = graph.target(ue);
2.1739 - n = graph.source(ue);
2.1740 - n = graph.oppositeNode(n0, ue);
2.1741 -
2.1742 - bool b;
2.1743 - b = graph.direction(e);
2.1744 - Edge e = graph.direct(UEdge(), true);
2.1745 - e = graph.direct(UEdge(), n);
2.1746 -
2.1747 - ignore_unused_variable_warning(b);
2.1748 - }
2.1749 -
2.1750 - Graph graph;
2.1751 - Edge e;
2.1752 - Node n0;
2.1753 - UEdge ue;
2.1754 };
2.1755
2.1756 - };
2.1757
2.1758 -
2.1759 - struct IterableUGraphConcept {
2.1760 -
2.1761 - template <typename Graph>
2.1762 - struct Constraints {
2.1763 - void constraints() {
2.1764 - /// \todo we don't need the iterable component to be base iterable
2.1765 - /// Don't we really???
2.1766 - //checkConcept< BaseIterableUGraphConcept, Graph > ();
2.1767 -
2.1768 - checkConcept<IterableGraphComponent, Graph> ();
2.1769 -
2.1770 - typedef typename Graph::UEdge UEdge;
2.1771 - typedef typename Graph::UEdgeIt UEdgeIt;
2.1772 - typedef typename Graph::IncEdgeIt IncEdgeIt;
2.1773 -
2.1774 - checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
2.1775 - checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
2.1776 - }
2.1777 - };
2.1778 -
2.1779 - };
2.1780 -
2.1781 - struct MappableUGraphConcept {
2.1782 -
2.1783 - template <typename Graph>
2.1784 + template <typename _Graph>
2.1785 struct Constraints {
2.1786
2.1787 struct Dummy {
2.1788 @@ -1068,22 +1475,242 @@
2.1789 };
2.1790
2.1791 void constraints() {
2.1792 - checkConcept<MappableGraphComponent, Graph>();
2.1793 + checkConcept<Base, _Graph>();
2.1794 + checkConcept<MappableGraphComponent<Base>, _Graph>();
2.1795
2.1796 - typedef typename Graph::template UEdgeMap<int> IntMap;
2.1797 - checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
2.1798 - IntMap >();
2.1799 + { // int map test
2.1800 + typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap;
2.1801 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>,
2.1802 + IntUEdgeMap >();
2.1803 + } { // bool map test
2.1804 + typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap;
2.1805 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>,
2.1806 + BoolUEdgeMap >();
2.1807 + } { // Dummy map test
2.1808 + typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap;
2.1809 + checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>,
2.1810 + DummyUEdgeMap >();
2.1811 + }
2.1812 + }
2.1813
2.1814 - typedef typename Graph::template UEdgeMap<bool> BoolMap;
2.1815 - checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
2.1816 - BoolMap >();
2.1817 + _Graph& graph;
2.1818 + };
2.1819 + };
2.1820
2.1821 - typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
2.1822 - checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
2.1823 - DummyMap >();
2.1824 +
2.1825 + /// \brief An empty extendable graph class.
2.1826 + ///
2.1827 + /// This class provides beside the core graph features graph
2.1828 + /// extendable interface for the graph structure. The main
2.1829 + /// difference between the base and this interface is that the
2.1830 + /// graph alterations should handled already on this level.
2.1831 + template <typename _Base = BaseGraphComponent>
2.1832 + class ExtendableGraphComponent : public _Base {
2.1833 + public:
2.1834 +
2.1835 + typedef typename _Base::Node Node;
2.1836 + typedef typename _Base::Edge Edge;
2.1837 +
2.1838 + /// \brief Adds a new node to the graph.
2.1839 + ///
2.1840 + /// Adds a new node to the graph.
2.1841 + ///
2.1842 + Node addNode() {
2.1843 + return INVALID;
2.1844 + }
2.1845 +
2.1846 + /// \brief Adds a new edge connects the given two nodes.
2.1847 + ///
2.1848 + /// Adds a new edge connects the the given two nodes.
2.1849 + Edge addEdge(const Node&, const Node&) {
2.1850 + return INVALID;
2.1851 + }
2.1852 +
2.1853 + template <typename _Graph>
2.1854 + struct Constraints {
2.1855 + void constraints() {
2.1856 + typename _Graph::Node node_a, node_b;
2.1857 + node_a = graph.addNode();
2.1858 + node_b = graph.addNode();
2.1859 + typename _Graph::Edge edge;
2.1860 + edge = graph.addEdge(node_a, node_b);
2.1861 }
2.1862 +
2.1863 + _Graph& graph;
2.1864 };
2.1865 + };
2.1866
2.1867 + /// \brief An empty extendable base undirected graph class.
2.1868 + ///
2.1869 + /// This class provides beside the core undirected graph features
2.1870 + /// core undircted graph extend interface for the graph structure.
2.1871 + /// The main difference between the base and this interface is
2.1872 + /// that the graph alterations should handled already on this
2.1873 + /// level.
2.1874 + template <typename _Base = BaseUGraphComponent>
2.1875 + class ExtendableUGraphComponent : public _Base {
2.1876 + public:
2.1877 +
2.1878 + typedef typename _Base::Node Node;
2.1879 + typedef typename _Base::UEdge UEdge;
2.1880 +
2.1881 + /// \brief Adds a new node to the graph.
2.1882 + ///
2.1883 + /// Adds a new node to the graph.
2.1884 + ///
2.1885 + Node addNode() {
2.1886 + return INVALID;
2.1887 + }
2.1888 +
2.1889 + /// \brief Adds a new edge connects the given two nodes.
2.1890 + ///
2.1891 + /// Adds a new edge connects the the given two nodes.
2.1892 + UEdge addEdge(const Node&, const Node&) {
2.1893 + return INVALID;
2.1894 + }
2.1895 +
2.1896 + template <typename _Graph>
2.1897 + struct Constraints {
2.1898 + void constraints() {
2.1899 + typename _Graph::Node node_a, node_b;
2.1900 + node_a = graph.addNode();
2.1901 + node_b = graph.addNode();
2.1902 + typename _Graph::UEdge uedge;
2.1903 + uedge = graph.addUEdge(node_a, node_b);
2.1904 + }
2.1905 +
2.1906 + _Graph& graph;
2.1907 + };
2.1908 + };
2.1909 +
2.1910 + /// \brief An empty erasable graph class.
2.1911 + ///
2.1912 + /// This class provides beside the core graph features core erase
2.1913 + /// functions for the graph structure. The main difference between
2.1914 + /// the base and this interface is that the graph alterations
2.1915 + /// should handled already on this level.
2.1916 + template <typename _Base = BaseGraphComponent>
2.1917 + class ErasableGraphComponent : public _Base {
2.1918 + public:
2.1919 +
2.1920 + typedef _Base Base;
2.1921 + typedef typename Base::Node Node;
2.1922 + typedef typename Base::Edge Edge;
2.1923 +
2.1924 + /// \brief Erase a node from the graph.
2.1925 + ///
2.1926 + /// Erase a node from the graph. This function should
2.1927 + /// erase all edges connecting to the node.
2.1928 + void erase(const Node&) {}
2.1929 +
2.1930 + /// \brief Erase an edge from the graph.
2.1931 + ///
2.1932 + /// Erase an edge from the graph.
2.1933 + ///
2.1934 + void erase(const Edge&) {}
2.1935 +
2.1936 + template <typename _Graph>
2.1937 + struct Constraints {
2.1938 + void constraints() {
2.1939 + typename _Graph::Node node;
2.1940 + graph.erase(node);
2.1941 + typename _Graph::Edge edge;
2.1942 + graph.erase(edge);
2.1943 + }
2.1944 +
2.1945 + _Graph& graph;
2.1946 + };
2.1947 + };
2.1948 +
2.1949 + /// \brief An empty erasable base undirected graph class.
2.1950 + ///
2.1951 + /// This class provides beside the core undirected graph features
2.1952 + /// core erase functions for the undirceted graph structure. The
2.1953 + /// main difference between the base and this interface is that
2.1954 + /// the graph alterations should handled already on this level.
2.1955 + template <typename _Base = BaseUGraphComponent>
2.1956 + class ErasableUGraphComponent : public _Base {
2.1957 + public:
2.1958 +
2.1959 + typedef _Base Base;
2.1960 + typedef typename Base::Node Node;
2.1961 + typedef typename Base::UEdge UEdge;
2.1962 +
2.1963 + /// \brief Erase a node from the graph.
2.1964 + ///
2.1965 + /// Erase a node from the graph. This function should erase
2.1966 + /// edges connecting to the node.
2.1967 + void erase(const Node&) {}
2.1968 +
2.1969 + /// \brief Erase an edge from the graph.
2.1970 + ///
2.1971 + /// Erase an edge from the graph.
2.1972 + ///
2.1973 + void erase(const UEdge&) {}
2.1974 +
2.1975 + template <typename _Graph>
2.1976 + struct Constraints {
2.1977 + void constraints() {
2.1978 + typename _Graph::Node node;
2.1979 + graph.erase(node);
2.1980 + typename _Graph::Edge edge;
2.1981 + graph.erase(edge);
2.1982 + }
2.1983 +
2.1984 + _Graph& graph;
2.1985 + };
2.1986 + };
2.1987 +
2.1988 + /// \brief An empty clearable base graph class.
2.1989 + ///
2.1990 + /// This class provides beside the core graph features core clear
2.1991 + /// functions for the graph structure. The main difference between
2.1992 + /// the base and this interface is that the graph alterations
2.1993 + /// should handled already on this level.
2.1994 + template <typename _Base = BaseGraphComponent>
2.1995 + class ClearableGraphComponent : public _Base {
2.1996 + public:
2.1997 +
2.1998 + /// \brief Erase all nodes and edges from the graph.
2.1999 + ///
2.2000 + /// Erase all nodes and edges from the graph.
2.2001 + ///
2.2002 + void clear() {}
2.2003 +
2.2004 + template <typename _Graph>
2.2005 + struct Constraints {
2.2006 + void constraints() {
2.2007 + graph.clear();
2.2008 + }
2.2009 +
2.2010 + _Graph graph;
2.2011 + };
2.2012 + };
2.2013 +
2.2014 + /// \brief An empty clearable base undirected graph class.
2.2015 + ///
2.2016 + /// This class provides beside the core undirected graph features
2.2017 + /// core clear functions for the undirected graph structure. The
2.2018 + /// main difference between the base and this interface is that
2.2019 + /// the graph alterations should handled already on this level.
2.2020 + template <typename _Base = BaseUGraphComponent>
2.2021 + class ClearableUGraphComponent : public _Base {
2.2022 + public:
2.2023 +
2.2024 + /// \brief Erase all nodes and undirected edges from the graph.
2.2025 + ///
2.2026 + /// Erase all nodes and undirected edges from the graph.
2.2027 + ///
2.2028 + void clear() {}
2.2029 +
2.2030 + template <typename _Graph>
2.2031 + struct Constraints {
2.2032 + void constraints() {
2.2033 + graph.clear();
2.2034 + }
2.2035 +
2.2036 + _Graph graph;
2.2037 + };
2.2038 };
2.2039
2.2040 }
3.1 --- a/lemon/concept/ugraph.h Wed Jul 05 16:59:45 2006 +0000
3.2 +++ b/lemon/concept/ugraph.h Mon Jul 10 19:04:17 2006 +0000
3.3 @@ -489,7 +489,6 @@
3.4 /// \sa Reference
3.5 /// \warning Making maps that can handle bool type (NodeMap<bool>)
3.6 /// needs some extra attention!
3.7 - /// \todo Wrong documentation
3.8 template<class T>
3.9 class NodeMap : public ReadWriteMap< Node, T >
3.10 {
3.11 @@ -503,8 +502,11 @@
3.12 ///Copy constructor
3.13 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
3.14 ///Assignment operator
3.15 - NodeMap& operator=(const NodeMap&) { return *this; }
3.16 - // \todo fix this concept
3.17 + template <typename CMap>
3.18 + NodeMap& operator=(const CMap&) {
3.19 + checkConcept<ReadMap<Node, T>, CMap>();
3.20 + return *this;
3.21 + }
3.22 };
3.23
3.24 /// \brief Read write map of the directed edges to type \c T.
3.25 @@ -513,7 +515,6 @@
3.26 /// \sa Reference
3.27 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
3.28 /// needs some extra attention!
3.29 - /// \todo Wrong documentation
3.30 template<class T>
3.31 class EdgeMap : public ReadWriteMap<Edge,T>
3.32 {
3.33 @@ -526,8 +527,11 @@
3.34 ///Copy constructor
3.35 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
3.36 ///Assignment operator
3.37 - EdgeMap& operator=(const EdgeMap&) { return *this; }
3.38 - // \todo fix this concept
3.39 + template <typename CMap>
3.40 + EdgeMap& operator=(const CMap&) {
3.41 + checkConcept<ReadMap<Edge, T>, CMap>();
3.42 + return *this;
3.43 + }
3.44 };
3.45
3.46 /// Read write map of the undirected edges to type \c T.
3.47 @@ -536,7 +540,6 @@
3.48 /// \sa Reference
3.49 /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
3.50 /// needs some extra attention!
3.51 - /// \todo Wrong documentation
3.52 template<class T>
3.53 class UEdgeMap : public ReadWriteMap<UEdge,T>
3.54 {
3.55 @@ -549,8 +552,11 @@
3.56 ///Copy constructor
3.57 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
3.58 ///Assignment operator
3.59 - UEdgeMap &operator=(const UEdgeMap&) { return *this; }
3.60 - // \todo fix this concept
3.61 + template <typename CMap>
3.62 + UEdgeMap& operator=(const CMap&) {
3.63 + checkConcept<ReadMap<UEdge, T>, CMap>();
3.64 + return *this;
3.65 + }
3.66 };
3.67
3.68 /// \brief Direct the given undirected edge.
3.69 @@ -672,9 +678,9 @@
3.70 template <typename Graph>
3.71 struct Constraints {
3.72 void constraints() {
3.73 - checkConcept<BaseIterableUGraphConcept, Graph>();
3.74 - checkConcept<IterableUGraphConcept, Graph>();
3.75 - checkConcept<MappableUGraphConcept, Graph>();
3.76 + checkConcept<BaseIterableUGraphComponent<>, Graph>();
3.77 + checkConcept<IterableUGraphComponent<>, Graph>();
3.78 + checkConcept<MappableUGraphComponent<>, Graph>();
3.79 }
3.80 };
3.81
4.1 --- a/test/graph_test.cc Wed Jul 05 16:59:45 2006 +0000
4.2 +++ b/test/graph_test.cc Mon Jul 10 19:04:17 2006 +0000
4.3 @@ -38,21 +38,28 @@
4.4 { // checking graph components
4.5 checkConcept<BaseGraphComponent, BaseGraphComponent >();
4.6
4.7 - checkConcept<BaseIterableGraphComponent, BaseIterableGraphComponent >();
4.8 + checkConcept<BaseIterableGraphComponent<>,
4.9 + BaseIterableGraphComponent<> >();
4.10
4.11 - checkConcept<IDableGraphComponent, IDableGraphComponent >();
4.12 - checkConcept<MaxIDableGraphComponent, MaxIDableGraphComponent >();
4.13 + checkConcept<IDableGraphComponent<>,
4.14 + IDableGraphComponent<> >();
4.15
4.16 - checkConcept<IterableGraphComponent, IterableGraphComponent >();
4.17 + checkConcept<IterableGraphComponent<>,
4.18 + IterableGraphComponent<> >();
4.19
4.20 - checkConcept<MappableGraphComponent, MappableGraphComponent >();
4.21 + checkConcept<MappableGraphComponent<>,
4.22 + MappableGraphComponent<> >();
4.23
4.24 }
4.25 { // checking skeleton graphs
4.26 - checkConcept<Graph, Graph >();
4.27 + checkConcept<Graph, Graph>();
4.28 }
4.29 { // checking list graph
4.30 checkConcept<Graph, ListGraph >();
4.31 + checkConcept<AlterableGraphComponent<>, ListGraph>();
4.32 + checkConcept<ExtendableGraphComponent<>, ListGraph>();
4.33 + checkConcept<ClearableGraphComponent<>, ListGraph>();
4.34 + checkConcept<ErasableGraphComponent<>, ListGraph>();
4.35
4.36 checkGraph<ListGraph>();
4.37 checkGraphNodeMap<ListGraph>();
5.1 --- a/test/ugraph_test.cc Wed Jul 05 16:59:45 2006 +0000
5.2 +++ b/test/ugraph_test.cc Mon Jul 10 19:04:17 2006 +0000
5.3 @@ -32,15 +32,34 @@
5.4 using namespace lemon::concept;
5.5
5.6 void check_concepts() {
5.7 - checkConcept<UGraph, ListUGraph>();
5.8
5.9 - checkConcept<UGraph, SmartUGraph>();
5.10 + { // checking graph components
5.11 + checkConcept<BaseUGraphComponent, BaseUGraphComponent >();
5.12
5.13 - checkConcept<UGraph, FullUGraph>();
5.14 + checkConcept<BaseIterableUGraphComponent<>,
5.15 + BaseIterableUGraphComponent<> >();
5.16
5.17 - checkConcept<UGraph, UGraph>();
5.18 + checkConcept<IDableUGraphComponent<>,
5.19 + IDableUGraphComponent<> >();
5.20
5.21 - checkConcept<UGraph, GridUGraph>();
5.22 + checkConcept<IterableUGraphComponent<>,
5.23 + IterableUGraphComponent<> >();
5.24 +
5.25 + checkConcept<MappableUGraphComponent<>,
5.26 + MappableUGraphComponent<> >();
5.27 +
5.28 + }
5.29 + {
5.30 + checkConcept<UGraph, ListUGraph>();
5.31 +
5.32 + checkConcept<UGraph, SmartUGraph>();
5.33 +
5.34 + checkConcept<UGraph, FullUGraph>();
5.35 +
5.36 + checkConcept<UGraph, UGraph>();
5.37 +
5.38 + checkConcept<UGraph, GridUGraph>();
5.39 + }
5.40 }
5.41
5.42 template <typename Graph>