1.1 --- a/lemon/concepts/graph.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/concepts/graph.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -18,13 +18,14 @@
1.4
1.5 ///\ingroup graph_concepts
1.6 ///\file
1.7 -///\brief The concept of Undirected Graphs.
1.8 +///\brief The concept of undirected graphs.
1.9
1.10 -#ifndef LEMON_CONCEPT_GRAPH_H
1.11 -#define LEMON_CONCEPT_GRAPH_H
1.12 +#ifndef LEMON_CONCEPTS_GRAPH_H
1.13 +#define LEMON_CONCEPTS_GRAPH_H
1.14
1.15 #include <lemon/concepts/graph_components.h>
1.16 -#include <lemon/concepts/graph.h>
1.17 +#include <lemon/concepts/maps.h>
1.18 +#include <lemon/concept_check.h>
1.19 #include <lemon/core.h>
1.20
1.21 namespace lemon {
1.22 @@ -32,63 +33,74 @@
1.23
1.24 /// \ingroup graph_concepts
1.25 ///
1.26 - /// \brief Class describing the concept of Undirected Graphs.
1.27 + /// \brief Class describing the concept of undirected graphs.
1.28 ///
1.29 - /// This class describes the common interface of all Undirected
1.30 - /// Graphs.
1.31 + /// This class describes the common interface of all undirected
1.32 + /// graphs.
1.33 ///
1.34 - /// As all concept describing classes it provides only interface
1.35 - /// without any sensible implementation. So any algorithm for
1.36 - /// undirected graph should compile with this class, but it will not
1.37 + /// Like all concept classes, it only provides an interface
1.38 + /// without any sensible implementation. So any general algorithm for
1.39 + /// undirected graphs should compile with this class, but it will not
1.40 /// run properly, of course.
1.41 + /// An actual graph implementation like \ref ListGraph or
1.42 + /// \ref SmartGraph may have additional functionality.
1.43 ///
1.44 - /// The LEMON undirected graphs also fulfill the concept of
1.45 - /// directed graphs (\ref lemon::concepts::Digraph "Digraph
1.46 - /// Concept"). Each edges can be seen as two opposite
1.47 - /// directed arc and consequently the undirected graph can be
1.48 - /// seen as the direceted graph of these directed arcs. The
1.49 - /// Graph has the Edge inner class for the edges and
1.50 - /// the Arc type for the directed arcs. The Arc type is
1.51 - /// convertible to Edge or inherited from it so from a directed
1.52 - /// arc we can get the represented edge.
1.53 + /// The undirected graphs also fulfill the concept of \ref Digraph
1.54 + /// "directed graphs", since each edge can also be regarded as two
1.55 + /// oppositely directed arcs.
1.56 + /// Undirected graphs provide an Edge type for the undirected edges and
1.57 + /// an Arc type for the directed arcs. The Arc type is convertible to
1.58 + /// Edge or inherited from it, i.e. the corresponding edge can be
1.59 + /// obtained from an arc.
1.60 + /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
1.61 + /// and ArcMap classes can be used for the arcs (just like in digraphs).
1.62 + /// Both InArcIt and OutArcIt iterates on the same edges but with
1.63 + /// opposite direction. IncEdgeIt also iterates on the same edges
1.64 + /// as OutArcIt and InArcIt, but it is not convertible to Arc,
1.65 + /// only to Edge.
1.66 ///
1.67 - /// In the sense of the LEMON each edge has a default
1.68 - /// direction (it should be in every computer implementation,
1.69 - /// because the order of edge's nodes defines an
1.70 - /// orientation). With the default orientation we can define that
1.71 - /// the directed arc is forward or backward directed. With the \c
1.72 - /// direction() and \c direct() function we can get the direction
1.73 - /// of the directed arc and we can direct an edge.
1.74 + /// In LEMON, each undirected edge has an inherent orientation.
1.75 + /// Thus it can defined if an arc is forward or backward oriented in
1.76 + /// an undirected graph with respect to this default oriantation of
1.77 + /// the represented edge.
1.78 + /// With the direction() and direct() functions the direction
1.79 + /// of an arc can be obtained and set, respectively.
1.80 ///
1.81 - /// The EdgeIt is an iterator for the edges. We can use
1.82 - /// the EdgeMap to map values for the edges. The InArcIt and
1.83 - /// OutArcIt iterates on the same edges but with opposite
1.84 - /// direction. The IncEdgeIt iterates also on the same edges
1.85 - /// as the OutArcIt and InArcIt but it is not convertible to Arc just
1.86 - /// to Edge.
1.87 + /// Only nodes and edges can be added to or removed from an undirected
1.88 + /// graph and the corresponding arcs are added or removed automatically.
1.89 + ///
1.90 + /// \sa Digraph
1.91 class Graph {
1.92 + private:
1.93 + /// Graphs are \e not copy constructible. Use DigraphCopy instead.
1.94 + Graph(const Graph&) {}
1.95 + /// \brief Assignment of a graph to another one is \e not allowed.
1.96 + /// Use DigraphCopy instead.
1.97 + void operator=(const Graph&) {}
1.98 +
1.99 public:
1.100 - /// \brief The undirected graph should be tagged by the
1.101 - /// UndirectedTag.
1.102 + /// Default constructor.
1.103 + Graph() {}
1.104 +
1.105 + /// \brief Undirected graphs should be tagged with \c UndirectedTag.
1.106 ///
1.107 - /// The undirected graph should be tagged by the UndirectedTag. This
1.108 - /// tag helps the enable_if technics to make compile time
1.109 + /// Undirected graphs should be tagged with \c UndirectedTag.
1.110 + ///
1.111 + /// This tag helps the \c enable_if technics to make compile time
1.112 /// specializations for undirected graphs.
1.113 typedef True UndirectedTag;
1.114
1.115 - /// \brief The base type of node iterators,
1.116 - /// or in other words, the trivial node iterator.
1.117 - ///
1.118 - /// This is the base type of each node iterator,
1.119 - /// thus each kind of node iterator converts to this.
1.120 - /// More precisely each kind of node iterator should be inherited
1.121 - /// from the trivial node iterator.
1.122 + /// The node type of the graph
1.123 +
1.124 + /// This class identifies a node of the graph. It also serves
1.125 + /// as a base class of the node iterators,
1.126 + /// thus they convert to this type.
1.127 class Node {
1.128 public:
1.129 /// Default constructor
1.130
1.131 - /// @warning The default constructor sets the iterator
1.132 - /// to an undefined value.
1.133 + /// Default constructor.
1.134 + /// \warning It sets the object to an undefined value.
1.135 Node() { }
1.136 /// Copy constructor.
1.137
1.138 @@ -96,40 +108,40 @@
1.139 ///
1.140 Node(const Node&) { }
1.141
1.142 - /// Invalid constructor \& conversion.
1.143 + /// %Invalid constructor \& conversion.
1.144
1.145 - /// This constructor initializes the iterator to be invalid.
1.146 + /// Initializes the object to be invalid.
1.147 /// \sa Invalid for more details.
1.148 Node(Invalid) { }
1.149 /// Equality operator
1.150
1.151 + /// Equality operator.
1.152 + ///
1.153 /// Two iterators are equal if and only if they point to the
1.154 - /// same object or both are invalid.
1.155 + /// same object or both are \c INVALID.
1.156 bool operator==(Node) const { return true; }
1.157
1.158 /// Inequality operator
1.159
1.160 - /// \sa operator==(Node n)
1.161 - ///
1.162 + /// Inequality operator.
1.163 bool operator!=(Node) const { return true; }
1.164
1.165 /// Artificial ordering operator.
1.166
1.167 - /// To allow the use of graph descriptors as key type in std::map or
1.168 - /// similar associative container we require this.
1.169 + /// Artificial ordering operator.
1.170 ///
1.171 - /// \note This operator only have to define some strict ordering of
1.172 + /// \note This operator only has to define some strict ordering of
1.173 /// the items; this order has nothing to do with the iteration
1.174 /// ordering of the items.
1.175 bool operator<(Node) const { return false; }
1.176
1.177 };
1.178
1.179 - /// This iterator goes through each node.
1.180 + /// Iterator class for the nodes.
1.181
1.182 - /// This iterator goes through each node.
1.183 + /// This iterator goes through each node of the graph.
1.184 /// Its usage is quite simple, for example you can count the number
1.185 - /// of nodes in graph \c g of type \c Graph like this:
1.186 + /// of nodes in a graph \c g of type \c %Graph like this:
1.187 ///\code
1.188 /// int count=0;
1.189 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.190 @@ -138,30 +150,28 @@
1.191 public:
1.192 /// Default constructor
1.193
1.194 - /// @warning The default constructor sets the iterator
1.195 - /// to an undefined value.
1.196 + /// Default constructor.
1.197 + /// \warning It sets the iterator to an undefined value.
1.198 NodeIt() { }
1.199 /// Copy constructor.
1.200
1.201 /// Copy constructor.
1.202 ///
1.203 NodeIt(const NodeIt& n) : Node(n) { }
1.204 - /// Invalid constructor \& conversion.
1.205 + /// %Invalid constructor \& conversion.
1.206
1.207 - /// Initialize the iterator to be invalid.
1.208 + /// Initializes the iterator to be invalid.
1.209 /// \sa Invalid for more details.
1.210 NodeIt(Invalid) { }
1.211 /// Sets the iterator to the first node.
1.212
1.213 - /// Sets the iterator to the first node of \c g.
1.214 + /// Sets the iterator to the first node of the given digraph.
1.215 ///
1.216 - NodeIt(const Graph&) { }
1.217 - /// Node -> NodeIt conversion.
1.218 + explicit NodeIt(const Graph&) { }
1.219 + /// Sets the iterator to the given node.
1.220
1.221 - /// Sets the iterator to the node of \c the graph pointed by
1.222 - /// the trivial iterator.
1.223 - /// This feature necessitates that each time we
1.224 - /// iterate the arc-set, the iteration order is the same.
1.225 + /// Sets the iterator to the given node of the given digraph.
1.226 + ///
1.227 NodeIt(const Graph&, const Node&) { }
1.228 /// Next node.
1.229
1.230 @@ -171,54 +181,55 @@
1.231 };
1.232
1.233
1.234 - /// The base type of the edge iterators.
1.235 + /// The edge type of the graph
1.236
1.237 - /// The base type of the edge iterators.
1.238 - ///
1.239 + /// This class identifies an edge of the graph. It also serves
1.240 + /// as a base class of the edge iterators,
1.241 + /// thus they will convert to this type.
1.242 class Edge {
1.243 public:
1.244 /// Default constructor
1.245
1.246 - /// @warning The default constructor sets the iterator
1.247 - /// to an undefined value.
1.248 + /// Default constructor.
1.249 + /// \warning It sets the object to an undefined value.
1.250 Edge() { }
1.251 /// Copy constructor.
1.252
1.253 /// Copy constructor.
1.254 ///
1.255 Edge(const Edge&) { }
1.256 - /// Initialize the iterator to be invalid.
1.257 + /// %Invalid constructor \& conversion.
1.258
1.259 - /// Initialize the iterator to be invalid.
1.260 - ///
1.261 + /// Initializes the object to be invalid.
1.262 + /// \sa Invalid for more details.
1.263 Edge(Invalid) { }
1.264 /// Equality operator
1.265
1.266 + /// Equality operator.
1.267 + ///
1.268 /// Two iterators are equal if and only if they point to the
1.269 - /// same object or both are invalid.
1.270 + /// same object or both are \c INVALID.
1.271 bool operator==(Edge) const { return true; }
1.272 /// Inequality operator
1.273
1.274 - /// \sa operator==(Edge n)
1.275 - ///
1.276 + /// Inequality operator.
1.277 bool operator!=(Edge) const { return true; }
1.278
1.279 /// Artificial ordering operator.
1.280
1.281 - /// To allow the use of graph descriptors as key type in std::map or
1.282 - /// similar associative container we require this.
1.283 + /// Artificial ordering operator.
1.284 ///
1.285 - /// \note This operator only have to define some strict ordering of
1.286 - /// the items; this order has nothing to do with the iteration
1.287 - /// ordering of the items.
1.288 + /// \note This operator only has to define some strict ordering of
1.289 + /// the edges; this order has nothing to do with the iteration
1.290 + /// ordering of the edges.
1.291 bool operator<(Edge) const { return false; }
1.292 };
1.293
1.294 - /// This iterator goes through each edge.
1.295 + /// Iterator class for the edges.
1.296
1.297 - /// This iterator goes through each edge of a graph.
1.298 + /// This iterator goes through each edge of the graph.
1.299 /// Its usage is quite simple, for example you can count the number
1.300 - /// of edges in a graph \c g of type \c Graph as follows:
1.301 + /// of edges in a graph \c g of type \c %Graph as follows:
1.302 ///\code
1.303 /// int count=0;
1.304 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.305 @@ -227,294 +238,291 @@
1.306 public:
1.307 /// Default constructor
1.308
1.309 - /// @warning The default constructor sets the iterator
1.310 - /// to an undefined value.
1.311 + /// Default constructor.
1.312 + /// \warning It sets the iterator to an undefined value.
1.313 EdgeIt() { }
1.314 /// Copy constructor.
1.315
1.316 /// Copy constructor.
1.317 ///
1.318 EdgeIt(const EdgeIt& e) : Edge(e) { }
1.319 - /// Initialize the iterator to be invalid.
1.320 + /// %Invalid constructor \& conversion.
1.321
1.322 - /// Initialize the iterator to be invalid.
1.323 + /// Initializes the iterator to be invalid.
1.324 + /// \sa Invalid for more details.
1.325 + EdgeIt(Invalid) { }
1.326 + /// Sets the iterator to the first edge.
1.327 +
1.328 + /// Sets the iterator to the first edge of the given graph.
1.329 ///
1.330 - EdgeIt(Invalid) { }
1.331 - /// This constructor sets the iterator to the first edge.
1.332 + explicit EdgeIt(const Graph&) { }
1.333 + /// Sets the iterator to the given edge.
1.334
1.335 - /// This constructor sets the iterator to the first edge.
1.336 - EdgeIt(const Graph&) { }
1.337 - /// Edge -> EdgeIt conversion
1.338 -
1.339 - /// Sets the iterator to the value of the trivial iterator.
1.340 - /// This feature necessitates that each time we
1.341 - /// iterate the edge-set, the iteration order is the
1.342 - /// same.
1.343 + /// Sets the iterator to the given edge of the given graph.
1.344 + ///
1.345 EdgeIt(const Graph&, const Edge&) { }
1.346 /// Next edge
1.347
1.348 /// Assign the iterator to the next edge.
1.349 + ///
1.350 EdgeIt& operator++() { return *this; }
1.351 };
1.352
1.353 - /// \brief This iterator goes trough the incident undirected
1.354 - /// arcs of a node.
1.355 - ///
1.356 - /// This iterator goes trough the incident edges
1.357 - /// of a certain node of a graph. You should assume that the
1.358 - /// loop arcs will be iterated twice.
1.359 - ///
1.360 + /// Iterator class for the incident edges of a node.
1.361 +
1.362 + /// This iterator goes trough the incident undirected edges
1.363 + /// of a certain node of a graph.
1.364 /// Its usage is quite simple, for example you can compute the
1.365 - /// degree (i.e. count the number of incident arcs of a node \c n
1.366 - /// in graph \c g of type \c Graph as follows.
1.367 + /// degree (i.e. the number of incident edges) of a node \c n
1.368 + /// in a graph \c g of type \c %Graph as follows.
1.369 ///
1.370 ///\code
1.371 /// int count=0;
1.372 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.373 ///\endcode
1.374 + ///
1.375 + /// \warning Loop edges will be iterated twice.
1.376 class IncEdgeIt : public Edge {
1.377 public:
1.378 /// Default constructor
1.379
1.380 - /// @warning The default constructor sets the iterator
1.381 - /// to an undefined value.
1.382 + /// Default constructor.
1.383 + /// \warning It sets the iterator to an undefined value.
1.384 IncEdgeIt() { }
1.385 /// Copy constructor.
1.386
1.387 /// Copy constructor.
1.388 ///
1.389 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
1.390 - /// Initialize the iterator to be invalid.
1.391 + /// %Invalid constructor \& conversion.
1.392
1.393 - /// Initialize the iterator to be invalid.
1.394 + /// Initializes the iterator to be invalid.
1.395 + /// \sa Invalid for more details.
1.396 + IncEdgeIt(Invalid) { }
1.397 + /// Sets the iterator to the first incident edge.
1.398 +
1.399 + /// Sets the iterator to the first incident edge of the given node.
1.400 ///
1.401 - IncEdgeIt(Invalid) { }
1.402 - /// This constructor sets the iterator to first incident arc.
1.403 + IncEdgeIt(const Graph&, const Node&) { }
1.404 + /// Sets the iterator to the given edge.
1.405
1.406 - /// This constructor set the iterator to the first incident arc of
1.407 - /// the node.
1.408 - IncEdgeIt(const Graph&, const Node&) { }
1.409 - /// Edge -> IncEdgeIt conversion
1.410 + /// Sets the iterator to the given edge of the given graph.
1.411 + ///
1.412 + IncEdgeIt(const Graph&, const Edge&) { }
1.413 + /// Next incident edge
1.414
1.415 - /// Sets the iterator to the value of the trivial iterator \c e.
1.416 - /// This feature necessitates that each time we
1.417 - /// iterate the arc-set, the iteration order is the same.
1.418 - IncEdgeIt(const Graph&, const Edge&) { }
1.419 - /// Next incident arc
1.420 -
1.421 - /// Assign the iterator to the next incident arc
1.422 + /// Assign the iterator to the next incident edge
1.423 /// of the corresponding node.
1.424 IncEdgeIt& operator++() { return *this; }
1.425 };
1.426
1.427 - /// The directed arc type.
1.428 + /// The arc type of the graph
1.429
1.430 - /// The directed arc type. It can be converted to the
1.431 - /// edge or it should be inherited from the undirected
1.432 - /// arc.
1.433 - class Arc : public Edge {
1.434 + /// This class identifies a directed arc of the graph. It also serves
1.435 + /// as a base class of the arc iterators,
1.436 + /// thus they will convert to this type.
1.437 + class Arc {
1.438 public:
1.439 /// Default constructor
1.440
1.441 - /// @warning The default constructor sets the iterator
1.442 - /// to an undefined value.
1.443 + /// Default constructor.
1.444 + /// \warning It sets the object to an undefined value.
1.445 Arc() { }
1.446 /// Copy constructor.
1.447
1.448 /// Copy constructor.
1.449 ///
1.450 - Arc(const Arc& e) : Edge(e) { }
1.451 - /// Initialize the iterator to be invalid.
1.452 + Arc(const Arc&) { }
1.453 + /// %Invalid constructor \& conversion.
1.454
1.455 - /// Initialize the iterator to be invalid.
1.456 - ///
1.457 + /// Initializes the object to be invalid.
1.458 + /// \sa Invalid for more details.
1.459 Arc(Invalid) { }
1.460 /// Equality operator
1.461
1.462 + /// Equality operator.
1.463 + ///
1.464 /// Two iterators are equal if and only if they point to the
1.465 - /// same object or both are invalid.
1.466 + /// same object or both are \c INVALID.
1.467 bool operator==(Arc) const { return true; }
1.468 /// Inequality operator
1.469
1.470 - /// \sa operator==(Arc n)
1.471 - ///
1.472 + /// Inequality operator.
1.473 bool operator!=(Arc) const { return true; }
1.474
1.475 /// Artificial ordering operator.
1.476
1.477 - /// To allow the use of graph descriptors as key type in std::map or
1.478 - /// similar associative container we require this.
1.479 + /// Artificial ordering operator.
1.480 ///
1.481 - /// \note This operator only have to define some strict ordering of
1.482 - /// the items; this order has nothing to do with the iteration
1.483 - /// ordering of the items.
1.484 + /// \note This operator only has to define some strict ordering of
1.485 + /// the arcs; this order has nothing to do with the iteration
1.486 + /// ordering of the arcs.
1.487 bool operator<(Arc) const { return false; }
1.488
1.489 + /// Converison to \c Edge
1.490 +
1.491 + /// Converison to \c Edge.
1.492 + ///
1.493 + operator Edge() const { return Edge(); }
1.494 };
1.495 - /// This iterator goes through each directed arc.
1.496
1.497 - /// This iterator goes through each arc of a graph.
1.498 + /// Iterator class for the arcs.
1.499 +
1.500 + /// This iterator goes through each directed arc of the graph.
1.501 /// Its usage is quite simple, for example you can count the number
1.502 - /// of arcs in a graph \c g of type \c Graph as follows:
1.503 + /// of arcs in a graph \c g of type \c %Graph as follows:
1.504 ///\code
1.505 /// int count=0;
1.506 - /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
1.507 + /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.508 ///\endcode
1.509 class ArcIt : public Arc {
1.510 public:
1.511 /// Default constructor
1.512
1.513 - /// @warning The default constructor sets the iterator
1.514 - /// to an undefined value.
1.515 + /// Default constructor.
1.516 + /// \warning It sets the iterator to an undefined value.
1.517 ArcIt() { }
1.518 /// Copy constructor.
1.519
1.520 /// Copy constructor.
1.521 ///
1.522 ArcIt(const ArcIt& e) : Arc(e) { }
1.523 - /// Initialize the iterator to be invalid.
1.524 + /// %Invalid constructor \& conversion.
1.525
1.526 - /// Initialize the iterator to be invalid.
1.527 + /// Initializes the iterator to be invalid.
1.528 + /// \sa Invalid for more details.
1.529 + ArcIt(Invalid) { }
1.530 + /// Sets the iterator to the first arc.
1.531 +
1.532 + /// Sets the iterator to the first arc of the given graph.
1.533 ///
1.534 - ArcIt(Invalid) { }
1.535 - /// This constructor sets the iterator to the first arc.
1.536 + explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
1.537 + /// Sets the iterator to the given arc.
1.538
1.539 - /// This constructor sets the iterator to the first arc of \c g.
1.540 - ///@param g the graph
1.541 - ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
1.542 - /// Arc -> ArcIt conversion
1.543 -
1.544 - /// Sets the iterator to the value of the trivial iterator \c e.
1.545 - /// This feature necessitates that each time we
1.546 - /// iterate the arc-set, the iteration order is the same.
1.547 + /// Sets the iterator to the given arc of the given graph.
1.548 + ///
1.549 ArcIt(const Graph&, const Arc&) { }
1.550 - ///Next arc
1.551 + /// Next arc
1.552
1.553 /// Assign the iterator to the next arc.
1.554 + ///
1.555 ArcIt& operator++() { return *this; }
1.556 };
1.557
1.558 - /// This iterator goes trough the outgoing directed arcs of a node.
1.559 + /// Iterator class for the outgoing arcs of a node.
1.560
1.561 - /// This iterator goes trough the \e outgoing arcs of a certain node
1.562 - /// of a graph.
1.563 + /// This iterator goes trough the \e outgoing directed arcs of a
1.564 + /// certain node of a graph.
1.565 /// Its usage is quite simple, for example you can count the number
1.566 /// of outgoing arcs of a node \c n
1.567 - /// in graph \c g of type \c Graph as follows.
1.568 + /// in a graph \c g of type \c %Graph as follows.
1.569 ///\code
1.570 /// int count=0;
1.571 - /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
1.572 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.573 ///\endcode
1.574 -
1.575 class OutArcIt : public Arc {
1.576 public:
1.577 /// Default constructor
1.578
1.579 - /// @warning The default constructor sets the iterator
1.580 - /// to an undefined value.
1.581 + /// Default constructor.
1.582 + /// \warning It sets the iterator to an undefined value.
1.583 OutArcIt() { }
1.584 /// Copy constructor.
1.585
1.586 /// Copy constructor.
1.587 ///
1.588 OutArcIt(const OutArcIt& e) : Arc(e) { }
1.589 - /// Initialize the iterator to be invalid.
1.590 + /// %Invalid constructor \& conversion.
1.591
1.592 - /// Initialize the iterator to be invalid.
1.593 + /// Initializes the iterator to be invalid.
1.594 + /// \sa Invalid for more details.
1.595 + OutArcIt(Invalid) { }
1.596 + /// Sets the iterator to the first outgoing arc.
1.597 +
1.598 + /// Sets the iterator to the first outgoing arc of the given node.
1.599 ///
1.600 - OutArcIt(Invalid) { }
1.601 - /// This constructor sets the iterator to the first outgoing arc.
1.602 -
1.603 - /// This constructor sets the iterator to the first outgoing arc of
1.604 - /// the node.
1.605 - ///@param n the node
1.606 - ///@param g the graph
1.607 OutArcIt(const Graph& n, const Node& g) {
1.608 ignore_unused_variable_warning(n);
1.609 ignore_unused_variable_warning(g);
1.610 }
1.611 - /// Arc -> OutArcIt conversion
1.612 + /// Sets the iterator to the given arc.
1.613
1.614 - /// Sets the iterator to the value of the trivial iterator.
1.615 - /// This feature necessitates that each time we
1.616 - /// iterate the arc-set, the iteration order is the same.
1.617 + /// Sets the iterator to the given arc of the given graph.
1.618 + ///
1.619 OutArcIt(const Graph&, const Arc&) { }
1.620 - ///Next outgoing arc
1.621 + /// Next outgoing arc
1.622
1.623 /// Assign the iterator to the next
1.624 /// outgoing arc of the corresponding node.
1.625 OutArcIt& operator++() { return *this; }
1.626 };
1.627
1.628 - /// This iterator goes trough the incoming directed arcs of a node.
1.629 + /// Iterator class for the incoming arcs of a node.
1.630
1.631 - /// This iterator goes trough the \e incoming arcs of a certain node
1.632 - /// of a graph.
1.633 + /// This iterator goes trough the \e incoming directed arcs of a
1.634 + /// certain node of a graph.
1.635 /// Its usage is quite simple, for example you can count the number
1.636 - /// of outgoing arcs of a node \c n
1.637 - /// in graph \c g of type \c Graph as follows.
1.638 + /// of incoming arcs of a node \c n
1.639 + /// in a graph \c g of type \c %Graph as follows.
1.640 ///\code
1.641 /// int count=0;
1.642 - /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
1.643 + /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.644 ///\endcode
1.645 -
1.646 class InArcIt : public Arc {
1.647 public:
1.648 /// Default constructor
1.649
1.650 - /// @warning The default constructor sets the iterator
1.651 - /// to an undefined value.
1.652 + /// Default constructor.
1.653 + /// \warning It sets the iterator to an undefined value.
1.654 InArcIt() { }
1.655 /// Copy constructor.
1.656
1.657 /// Copy constructor.
1.658 ///
1.659 InArcIt(const InArcIt& e) : Arc(e) { }
1.660 - /// Initialize the iterator to be invalid.
1.661 + /// %Invalid constructor \& conversion.
1.662
1.663 - /// Initialize the iterator to be invalid.
1.664 + /// Initializes the iterator to be invalid.
1.665 + /// \sa Invalid for more details.
1.666 + InArcIt(Invalid) { }
1.667 + /// Sets the iterator to the first incoming arc.
1.668 +
1.669 + /// Sets the iterator to the first incoming arc of the given node.
1.670 ///
1.671 - InArcIt(Invalid) { }
1.672 - /// This constructor sets the iterator to first incoming arc.
1.673 -
1.674 - /// This constructor set the iterator to the first incoming arc of
1.675 - /// the node.
1.676 - ///@param n the node
1.677 - ///@param g the graph
1.678 InArcIt(const Graph& g, const Node& n) {
1.679 ignore_unused_variable_warning(n);
1.680 ignore_unused_variable_warning(g);
1.681 }
1.682 - /// Arc -> InArcIt conversion
1.683 + /// Sets the iterator to the given arc.
1.684
1.685 - /// Sets the iterator to the value of the trivial iterator \c e.
1.686 - /// This feature necessitates that each time we
1.687 - /// iterate the arc-set, the iteration order is the same.
1.688 + /// Sets the iterator to the given arc of the given graph.
1.689 + ///
1.690 InArcIt(const Graph&, const Arc&) { }
1.691 /// Next incoming arc
1.692
1.693 - /// Assign the iterator to the next inarc of the corresponding node.
1.694 - ///
1.695 + /// Assign the iterator to the next
1.696 + /// incoming arc of the corresponding node.
1.697 InArcIt& operator++() { return *this; }
1.698 };
1.699
1.700 - /// \brief Read write map of the nodes to type \c T.
1.701 + /// \brief Standard graph map type for the nodes.
1.702 ///
1.703 - /// ReadWrite map of the nodes to type \c T.
1.704 - /// \sa Reference
1.705 + /// Standard graph map type for the nodes.
1.706 + /// It conforms to the ReferenceMap concept.
1.707 template<class T>
1.708 - class NodeMap : public ReadWriteMap< Node, T >
1.709 + class NodeMap : public ReferenceMap<Node, T, T&, const T&>
1.710 {
1.711 public:
1.712
1.713 - ///\e
1.714 - NodeMap(const Graph&) { }
1.715 - ///\e
1.716 + /// Constructor
1.717 + explicit NodeMap(const Graph&) { }
1.718 + /// Constructor with given initial value
1.719 NodeMap(const Graph&, T) { }
1.720
1.721 private:
1.722 ///Copy constructor
1.723 - NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.724 + NodeMap(const NodeMap& nm) :
1.725 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.726 ///Assignment operator
1.727 template <typename CMap>
1.728 NodeMap& operator=(const CMap&) {
1.729 @@ -523,22 +531,24 @@
1.730 }
1.731 };
1.732
1.733 - /// \brief Read write map of the directed arcs to type \c T.
1.734 + /// \brief Standard graph map type for the arcs.
1.735 ///
1.736 - /// Reference map of the directed arcs to type \c T.
1.737 - /// \sa Reference
1.738 + /// Standard graph map type for the arcs.
1.739 + /// It conforms to the ReferenceMap concept.
1.740 template<class T>
1.741 - class ArcMap : public ReadWriteMap<Arc,T>
1.742 + class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
1.743 {
1.744 public:
1.745
1.746 - ///\e
1.747 - ArcMap(const Graph&) { }
1.748 - ///\e
1.749 + /// Constructor
1.750 + explicit ArcMap(const Graph&) { }
1.751 + /// Constructor with given initial value
1.752 ArcMap(const Graph&, T) { }
1.753 +
1.754 private:
1.755 ///Copy constructor
1.756 - ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
1.757 + ArcMap(const ArcMap& em) :
1.758 + ReferenceMap<Arc, T, T&, const T&>(em) { }
1.759 ///Assignment operator
1.760 template <typename CMap>
1.761 ArcMap& operator=(const CMap&) {
1.762 @@ -547,22 +557,24 @@
1.763 }
1.764 };
1.765
1.766 - /// Read write map of the edges to type \c T.
1.767 -
1.768 - /// Reference map of the arcs to type \c T.
1.769 - /// \sa Reference
1.770 + /// \brief Standard graph map type for the edges.
1.771 + ///
1.772 + /// Standard graph map type for the edges.
1.773 + /// It conforms to the ReferenceMap concept.
1.774 template<class T>
1.775 - class EdgeMap : public ReadWriteMap<Edge,T>
1.776 + class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
1.777 {
1.778 public:
1.779
1.780 - ///\e
1.781 - EdgeMap(const Graph&) { }
1.782 - ///\e
1.783 + /// Constructor
1.784 + explicit EdgeMap(const Graph&) { }
1.785 + /// Constructor with given initial value
1.786 EdgeMap(const Graph&, T) { }
1.787 +
1.788 private:
1.789 ///Copy constructor
1.790 - EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
1.791 + EdgeMap(const EdgeMap& em) :
1.792 + ReferenceMap<Edge, T, T&, const T&>(em) {}
1.793 ///Assignment operator
1.794 template <typename CMap>
1.795 EdgeMap& operator=(const CMap&) {
1.796 @@ -571,95 +583,124 @@
1.797 }
1.798 };
1.799
1.800 - /// \brief Direct the given edge.
1.801 + /// \brief The first node of the edge.
1.802 ///
1.803 - /// Direct the given edge. The returned arc source
1.804 - /// will be the given node.
1.805 - Arc direct(const Edge&, const Node&) const {
1.806 + /// Returns the first node of the given edge.
1.807 + ///
1.808 + /// Edges don't have source and target nodes, however methods
1.809 + /// u() and v() are used to query the two end-nodes of an edge.
1.810 + /// The orientation of an edge that arises this way is called
1.811 + /// the inherent direction, it is used to define the default
1.812 + /// direction for the corresponding arcs.
1.813 + /// \sa v()
1.814 + /// \sa direction()
1.815 + Node u(Edge) const { return INVALID; }
1.816 +
1.817 + /// \brief The second node of the edge.
1.818 + ///
1.819 + /// Returns the second node of the given edge.
1.820 + ///
1.821 + /// Edges don't have source and target nodes, however methods
1.822 + /// u() and v() are used to query the two end-nodes of an edge.
1.823 + /// The orientation of an edge that arises this way is called
1.824 + /// the inherent direction, it is used to define the default
1.825 + /// direction for the corresponding arcs.
1.826 + /// \sa u()
1.827 + /// \sa direction()
1.828 + Node v(Edge) const { return INVALID; }
1.829 +
1.830 + /// \brief The source node of the arc.
1.831 + ///
1.832 + /// Returns the source node of the given arc.
1.833 + Node source(Arc) const { return INVALID; }
1.834 +
1.835 + /// \brief The target node of the arc.
1.836 + ///
1.837 + /// Returns the target node of the given arc.
1.838 + Node target(Arc) const { return INVALID; }
1.839 +
1.840 + /// \brief The ID of the node.
1.841 + ///
1.842 + /// Returns the ID of the given node.
1.843 + int id(Node) const { return -1; }
1.844 +
1.845 + /// \brief The ID of the edge.
1.846 + ///
1.847 + /// Returns the ID of the given edge.
1.848 + int id(Edge) const { return -1; }
1.849 +
1.850 + /// \brief The ID of the arc.
1.851 + ///
1.852 + /// Returns the ID of the given arc.
1.853 + int id(Arc) const { return -1; }
1.854 +
1.855 + /// \brief The node with the given ID.
1.856 + ///
1.857 + /// Returns the node with the given ID.
1.858 + /// \pre The argument should be a valid node ID in the graph.
1.859 + Node nodeFromId(int) const { return INVALID; }
1.860 +
1.861 + /// \brief The edge with the given ID.
1.862 + ///
1.863 + /// Returns the edge with the given ID.
1.864 + /// \pre The argument should be a valid edge ID in the graph.
1.865 + Edge edgeFromId(int) const { return INVALID; }
1.866 +
1.867 + /// \brief The arc with the given ID.
1.868 + ///
1.869 + /// Returns the arc with the given ID.
1.870 + /// \pre The argument should be a valid arc ID in the graph.
1.871 + Arc arcFromId(int) const { return INVALID; }
1.872 +
1.873 + /// \brief An upper bound on the node IDs.
1.874 + ///
1.875 + /// Returns an upper bound on the node IDs.
1.876 + int maxNodeId() const { return -1; }
1.877 +
1.878 + /// \brief An upper bound on the edge IDs.
1.879 + ///
1.880 + /// Returns an upper bound on the edge IDs.
1.881 + int maxEdgeId() const { return -1; }
1.882 +
1.883 + /// \brief An upper bound on the arc IDs.
1.884 + ///
1.885 + /// Returns an upper bound on the arc IDs.
1.886 + int maxArcId() const { return -1; }
1.887 +
1.888 + /// \brief The direction of the arc.
1.889 + ///
1.890 + /// Returns \c true if the direction of the given arc is the same as
1.891 + /// the inherent orientation of the represented edge.
1.892 + bool direction(Arc) const { return true; }
1.893 +
1.894 + /// \brief Direct the edge.
1.895 + ///
1.896 + /// Direct the given edge. The returned arc
1.897 + /// represents the given edge and its direction comes
1.898 + /// from the bool parameter. If it is \c true, then the direction
1.899 + /// of the arc is the same as the inherent orientation of the edge.
1.900 + Arc direct(Edge, bool) const {
1.901 return INVALID;
1.902 }
1.903
1.904 - /// \brief Direct the given edge.
1.905 + /// \brief Direct the edge.
1.906 ///
1.907 - /// Direct the given edge. The returned arc
1.908 - /// represents the given edge and the direction comes
1.909 - /// from the bool parameter. The source of the edge and
1.910 - /// the directed arc is the same when the given bool is true.
1.911 - Arc direct(const Edge&, bool) const {
1.912 + /// Direct the given edge. The returned arc represents the given
1.913 + /// edge and its source node is the given node.
1.914 + Arc direct(Edge, Node) const {
1.915 return INVALID;
1.916 }
1.917
1.918 - /// \brief Returns true if the arc has default orientation.
1.919 + /// \brief The oppositely directed arc.
1.920 ///
1.921 - /// Returns whether the given directed arc is same orientation as
1.922 - /// the corresponding edge's default orientation.
1.923 - bool direction(Arc) const { return true; }
1.924 -
1.925 - /// \brief Returns the opposite directed arc.
1.926 - ///
1.927 - /// Returns the opposite directed arc.
1.928 + /// Returns the oppositely directed arc representing the same edge.
1.929 Arc oppositeArc(Arc) const { return INVALID; }
1.930
1.931 - /// \brief Opposite node on an arc
1.932 + /// \brief The opposite node on the edge.
1.933 ///
1.934 - /// \return the opposite of the given Node on the given Edge
1.935 + /// Returns the opposite node on the given edge.
1.936 Node oppositeNode(Node, Edge) const { return INVALID; }
1.937
1.938 - /// \brief First node of the edge.
1.939 - ///
1.940 - /// \return the first node of the given Edge.
1.941 - ///
1.942 - /// Naturally edges don't have direction and thus
1.943 - /// don't have source and target node. But we use these two methods
1.944 - /// to query the two nodes of the arc. The direction of the arc
1.945 - /// which arises this way is called the inherent direction of the
1.946 - /// edge, and is used to define the "default" direction
1.947 - /// of the directed versions of the arcs.
1.948 - /// \sa direction
1.949 - Node u(Edge) const { return INVALID; }
1.950 -
1.951 - /// \brief Second node of the edge.
1.952 - Node v(Edge) const { return INVALID; }
1.953 -
1.954 - /// \brief Source node of the directed arc.
1.955 - Node source(Arc) const { return INVALID; }
1.956 -
1.957 - /// \brief Target node of the directed arc.
1.958 - Node target(Arc) const { return INVALID; }
1.959 -
1.960 - /// \brief Returns the id of the node.
1.961 - int id(Node) const { return -1; }
1.962 -
1.963 - /// \brief Returns the id of the edge.
1.964 - int id(Edge) const { return -1; }
1.965 -
1.966 - /// \brief Returns the id of the arc.
1.967 - int id(Arc) const { return -1; }
1.968 -
1.969 - /// \brief Returns the node with the given id.
1.970 - ///
1.971 - /// \pre The argument should be a valid node id in the graph.
1.972 - Node nodeFromId(int) const { return INVALID; }
1.973 -
1.974 - /// \brief Returns the edge with the given id.
1.975 - ///
1.976 - /// \pre The argument should be a valid edge id in the graph.
1.977 - Edge edgeFromId(int) const { return INVALID; }
1.978 -
1.979 - /// \brief Returns the arc with the given id.
1.980 - ///
1.981 - /// \pre The argument should be a valid arc id in the graph.
1.982 - Arc arcFromId(int) const { return INVALID; }
1.983 -
1.984 - /// \brief Returns an upper bound on the node IDs.
1.985 - int maxNodeId() const { return -1; }
1.986 -
1.987 - /// \brief Returns an upper bound on the edge IDs.
1.988 - int maxEdgeId() const { return -1; }
1.989 -
1.990 - /// \brief Returns an upper bound on the arc IDs.
1.991 - int maxArcId() const { return -1; }
1.992 -
1.993 void first(Node&) const {}
1.994 void next(Node&) const {}
1.995
1.996 @@ -692,51 +733,44 @@
1.997 // Dummy parameter.
1.998 int maxId(Arc) const { return -1; }
1.999
1.1000 - /// \brief Base node of the iterator
1.1001 + /// \brief The base node of the iterator.
1.1002 ///
1.1003 - /// Returns the base node (the source in this case) of the iterator
1.1004 - Node baseNode(OutArcIt e) const {
1.1005 - return source(e);
1.1006 - }
1.1007 - /// \brief Running node of the iterator
1.1008 + /// Returns the base node of the given incident edge iterator.
1.1009 + Node baseNode(IncEdgeIt) const { return INVALID; }
1.1010 +
1.1011 + /// \brief The running node of the iterator.
1.1012 ///
1.1013 - /// Returns the running node (the target in this case) of the
1.1014 - /// iterator
1.1015 - Node runningNode(OutArcIt e) const {
1.1016 - return target(e);
1.1017 - }
1.1018 + /// Returns the running node of the given incident edge iterator.
1.1019 + Node runningNode(IncEdgeIt) const { return INVALID; }
1.1020
1.1021 - /// \brief Base node of the iterator
1.1022 + /// \brief The base node of the iterator.
1.1023 ///
1.1024 - /// Returns the base node (the target in this case) of the iterator
1.1025 - Node baseNode(InArcIt e) const {
1.1026 - return target(e);
1.1027 - }
1.1028 - /// \brief Running node of the iterator
1.1029 + /// Returns the base node of the given outgoing arc iterator
1.1030 + /// (i.e. the source node of the corresponding arc).
1.1031 + Node baseNode(OutArcIt) const { return INVALID; }
1.1032 +
1.1033 + /// \brief The running node of the iterator.
1.1034 ///
1.1035 - /// Returns the running node (the source in this case) of the
1.1036 - /// iterator
1.1037 - Node runningNode(InArcIt e) const {
1.1038 - return source(e);
1.1039 - }
1.1040 + /// Returns the running node of the given outgoing arc iterator
1.1041 + /// (i.e. the target node of the corresponding arc).
1.1042 + Node runningNode(OutArcIt) const { return INVALID; }
1.1043
1.1044 - /// \brief Base node of the iterator
1.1045 + /// \brief The base node of the iterator.
1.1046 ///
1.1047 - /// Returns the base node of the iterator
1.1048 - Node baseNode(IncEdgeIt) const {
1.1049 - return INVALID;
1.1050 - }
1.1051 + /// Returns the base node of the given incomming arc iterator
1.1052 + /// (i.e. the target node of the corresponding arc).
1.1053 + Node baseNode(InArcIt) const { return INVALID; }
1.1054
1.1055 - /// \brief Running node of the iterator
1.1056 + /// \brief The running node of the iterator.
1.1057 ///
1.1058 - /// Returns the running node of the iterator
1.1059 - Node runningNode(IncEdgeIt) const {
1.1060 - return INVALID;
1.1061 - }
1.1062 + /// Returns the running node of the given incomming arc iterator
1.1063 + /// (i.e. the source node of the corresponding arc).
1.1064 + Node runningNode(InArcIt) const { return INVALID; }
1.1065
1.1066 template <typename _Graph>
1.1067 struct Constraints {
1.1068 void constraints() {
1.1069 + checkConcept<BaseGraphComponent, _Graph>();
1.1070 checkConcept<IterableGraphComponent<>, _Graph>();
1.1071 checkConcept<IDableGraphComponent<>, _Graph>();
1.1072 checkConcept<MappableGraphComponent<>, _Graph>();