1.1 --- a/lemon/concepts/digraph.h Thu Aug 20 22:52:16 2009 +0200
1.2 +++ b/lemon/concepts/digraph.h Sun Aug 23 11:07:50 2009 +0200
1.3 @@ -35,46 +35,40 @@
1.4 ///
1.5 /// \brief Class describing the concept of directed graphs.
1.6 ///
1.7 - /// This class describes the \ref concept "concept" of the
1.8 - /// immutable directed digraphs.
1.9 + /// This class describes the common interface of all directed
1.10 + /// graphs (digraphs).
1.11 ///
1.12 - /// Note that actual digraph implementation like @ref ListDigraph or
1.13 - /// @ref SmartDigraph may have several additional functionality.
1.14 + /// Like all concept classes, it only provides an interface
1.15 + /// without any sensible implementation. So any general algorithm for
1.16 + /// directed graphs should compile with this class, but it will not
1.17 + /// run properly, of course.
1.18 + /// An actual digraph implementation like \ref ListDigraph or
1.19 + /// \ref SmartDigraph may have additional functionality.
1.20 ///
1.21 - /// \sa concept
1.22 + /// \sa Graph
1.23 class Digraph {
1.24 private:
1.25 - ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
1.26 + /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
1.27 + Digraph(const Digraph &) {}
1.28 + /// \brief Assignment of a digraph to another one is \e not allowed.
1.29 + /// Use DigraphCopy instead.
1.30 + void operator=(const Digraph &) {}
1.31
1.32 - ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
1.33 - ///
1.34 - Digraph(const Digraph &) {};
1.35 - ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
1.36 - ///\e not allowed. Use DigraphCopy() instead.
1.37 + public:
1.38 + /// Default constructor.
1.39 + Digraph() { }
1.40
1.41 - ///Assignment of \ref Digraph "Digraph"s to another ones are
1.42 - ///\e not allowed. Use DigraphCopy() instead.
1.43 -
1.44 - void operator=(const Digraph &) {}
1.45 - public:
1.46 - ///\e
1.47 -
1.48 - /// Defalult constructor.
1.49 -
1.50 - /// Defalult constructor.
1.51 - ///
1.52 - Digraph() { }
1.53 - /// Class for identifying a node of the digraph
1.54 + /// The node type of the digraph
1.55
1.56 /// This class identifies a node of the digraph. It also serves
1.57 /// as a base class of the node iterators,
1.58 - /// thus they will convert to this type.
1.59 + /// thus they convert to this type.
1.60 class Node {
1.61 public:
1.62 /// Default constructor
1.63
1.64 - /// @warning The default constructor sets the iterator
1.65 - /// to an undefined value.
1.66 + /// Default constructor.
1.67 + /// \warning It sets the object to an undefined value.
1.68 Node() { }
1.69 /// Copy constructor.
1.70
1.71 @@ -82,40 +76,39 @@
1.72 ///
1.73 Node(const Node&) { }
1.74
1.75 - /// Invalid constructor \& conversion.
1.76 + /// %Invalid constructor \& conversion.
1.77
1.78 - /// This constructor initializes the iterator to be invalid.
1.79 + /// Initializes the object to be invalid.
1.80 /// \sa Invalid for more details.
1.81 Node(Invalid) { }
1.82 /// Equality operator
1.83
1.84 + /// Equality operator.
1.85 + ///
1.86 /// Two iterators are equal if and only if they point to the
1.87 - /// same object or both are invalid.
1.88 + /// same object or both are \c INVALID.
1.89 bool operator==(Node) const { return true; }
1.90
1.91 /// Inequality operator
1.92
1.93 - /// \sa operator==(Node n)
1.94 - ///
1.95 + /// Inequality operator.
1.96 bool operator!=(Node) const { return true; }
1.97
1.98 /// Artificial ordering operator.
1.99
1.100 - /// To allow the use of digraph descriptors as key type in std::map or
1.101 - /// similar associative container we require this.
1.102 + /// Artificial ordering operator.
1.103 ///
1.104 - /// \note This operator only have to define some strict ordering of
1.105 - /// the items; this order has nothing to do with the iteration
1.106 - /// ordering of the items.
1.107 + /// \note This operator only has to define some strict ordering of
1.108 + /// the nodes; this order has nothing to do with the iteration
1.109 + /// ordering of the nodes.
1.110 bool operator<(Node) const { return false; }
1.111 -
1.112 };
1.113
1.114 - /// This iterator goes through each node.
1.115 + /// Iterator class for the nodes.
1.116
1.117 - /// This iterator goes through each node.
1.118 + /// This iterator goes through each node of the digraph.
1.119 /// Its usage is quite simple, for example you can count the number
1.120 - /// of nodes in digraph \c g of type \c Digraph like this:
1.121 + /// of nodes in a digraph \c g of type \c %Digraph like this:
1.122 ///\code
1.123 /// int count=0;
1.124 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.125 @@ -124,30 +117,28 @@
1.126 public:
1.127 /// Default constructor
1.128
1.129 - /// @warning The default constructor sets the iterator
1.130 - /// to an undefined value.
1.131 + /// Default constructor.
1.132 + /// \warning It sets the iterator to an undefined value.
1.133 NodeIt() { }
1.134 /// Copy constructor.
1.135
1.136 /// Copy constructor.
1.137 ///
1.138 NodeIt(const NodeIt& n) : Node(n) { }
1.139 - /// Invalid constructor \& conversion.
1.140 + /// %Invalid constructor \& conversion.
1.141
1.142 - /// Initialize the iterator to be invalid.
1.143 + /// Initializes the iterator to be invalid.
1.144 /// \sa Invalid for more details.
1.145 NodeIt(Invalid) { }
1.146 /// Sets the iterator to the first node.
1.147
1.148 - /// Sets the iterator to the first node of \c g.
1.149 + /// Sets the iterator to the first node of the given digraph.
1.150 ///
1.151 - NodeIt(const Digraph&) { }
1.152 - /// Node -> NodeIt conversion.
1.153 + explicit NodeIt(const Digraph&) { }
1.154 + /// Sets the iterator to the given node.
1.155
1.156 - /// Sets the iterator to the node of \c the digraph pointed by
1.157 - /// the trivial iterator.
1.158 - /// This feature necessitates that each time we
1.159 - /// iterate the arc-set, the iteration order is the same.
1.160 + /// Sets the iterator to the given node of the given digraph.
1.161 + ///
1.162 NodeIt(const Digraph&, const Node&) { }
1.163 /// Next node.
1.164
1.165 @@ -157,7 +148,7 @@
1.166 };
1.167
1.168
1.169 - /// Class for identifying an arc of the digraph
1.170 + /// The arc type of the digraph
1.171
1.172 /// This class identifies an arc of the digraph. It also serves
1.173 /// as a base class of the arc iterators,
1.174 @@ -166,207 +157,214 @@
1.175 public:
1.176 /// Default constructor
1.177
1.178 - /// @warning The default constructor sets the iterator
1.179 - /// to an undefined value.
1.180 + /// Default constructor.
1.181 + /// \warning It sets the object to an undefined value.
1.182 Arc() { }
1.183 /// Copy constructor.
1.184
1.185 /// Copy constructor.
1.186 ///
1.187 Arc(const Arc&) { }
1.188 - /// Initialize the iterator to be invalid.
1.189 + /// %Invalid constructor \& conversion.
1.190
1.191 - /// Initialize the iterator to be invalid.
1.192 - ///
1.193 + /// Initializes the object to be invalid.
1.194 + /// \sa Invalid for more details.
1.195 Arc(Invalid) { }
1.196 /// Equality operator
1.197
1.198 + /// Equality operator.
1.199 + ///
1.200 /// Two iterators are equal if and only if they point to the
1.201 - /// same object or both are invalid.
1.202 + /// same object or both are \c INVALID.
1.203 bool operator==(Arc) const { return true; }
1.204 /// Inequality operator
1.205
1.206 - /// \sa operator==(Arc n)
1.207 - ///
1.208 + /// Inequality operator.
1.209 bool operator!=(Arc) const { return true; }
1.210
1.211 /// Artificial ordering operator.
1.212
1.213 - /// To allow the use of digraph descriptors as key type in std::map or
1.214 - /// similar associative container we require this.
1.215 + /// Artificial ordering operator.
1.216 ///
1.217 - /// \note This operator only have to define some strict ordering of
1.218 - /// the items; this order has nothing to do with the iteration
1.219 - /// ordering of the items.
1.220 + /// \note This operator only has to define some strict ordering of
1.221 + /// the arcs; this order has nothing to do with the iteration
1.222 + /// ordering of the arcs.
1.223 bool operator<(Arc) const { return false; }
1.224 };
1.225
1.226 - /// This iterator goes trough the outgoing arcs of a node.
1.227 + /// Iterator class for the outgoing arcs of a node.
1.228
1.229 /// This iterator goes trough the \e outgoing arcs of a certain node
1.230 /// of a digraph.
1.231 /// Its usage is quite simple, for example you can count the number
1.232 /// of outgoing arcs of a node \c n
1.233 - /// in digraph \c g of type \c Digraph as follows.
1.234 + /// in a digraph \c g of type \c %Digraph as follows.
1.235 ///\code
1.236 /// int count=0;
1.237 - /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
1.238 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.239 ///\endcode
1.240 -
1.241 class OutArcIt : public Arc {
1.242 public:
1.243 /// Default constructor
1.244
1.245 - /// @warning The default constructor sets the iterator
1.246 - /// to an undefined value.
1.247 + /// Default constructor.
1.248 + /// \warning It sets the iterator to an undefined value.
1.249 OutArcIt() { }
1.250 /// Copy constructor.
1.251
1.252 /// Copy constructor.
1.253 ///
1.254 OutArcIt(const OutArcIt& e) : Arc(e) { }
1.255 - /// Initialize the iterator to be invalid.
1.256 + /// %Invalid constructor \& conversion.
1.257
1.258 - /// Initialize the iterator to be invalid.
1.259 + /// Initializes the iterator to be invalid.
1.260 + /// \sa Invalid for more details.
1.261 + OutArcIt(Invalid) { }
1.262 + /// Sets the iterator to the first outgoing arc.
1.263 +
1.264 + /// Sets the iterator to the first outgoing arc of the given node.
1.265 ///
1.266 - OutArcIt(Invalid) { }
1.267 - /// This constructor sets the iterator to the first outgoing arc.
1.268 + OutArcIt(const Digraph&, const Node&) { }
1.269 + /// Sets the iterator to the given arc.
1.270
1.271 - /// This constructor sets the iterator to the first outgoing arc of
1.272 - /// the node.
1.273 - OutArcIt(const Digraph&, const Node&) { }
1.274 - /// Arc -> OutArcIt conversion
1.275 -
1.276 - /// Sets the iterator to the value of the trivial iterator.
1.277 - /// This feature necessitates that each time we
1.278 - /// iterate the arc-set, the iteration order is the same.
1.279 + /// Sets the iterator to the given arc of the given digraph.
1.280 + ///
1.281 OutArcIt(const Digraph&, const Arc&) { }
1.282 - ///Next outgoing arc
1.283 + /// Next outgoing arc
1.284
1.285 /// Assign the iterator to the next
1.286 /// outgoing arc of the corresponding node.
1.287 OutArcIt& operator++() { return *this; }
1.288 };
1.289
1.290 - /// This iterator goes trough the incoming arcs of a node.
1.291 + /// Iterator class for the incoming arcs of a node.
1.292
1.293 /// This iterator goes trough the \e incoming arcs of a certain node
1.294 /// of a digraph.
1.295 /// Its usage is quite simple, for example you can count the number
1.296 - /// of outgoing arcs of a node \c n
1.297 - /// in digraph \c g of type \c Digraph as follows.
1.298 + /// of incoming arcs of a node \c n
1.299 + /// in a digraph \c g of type \c %Digraph as follows.
1.300 ///\code
1.301 /// int count=0;
1.302 - /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
1.303 + /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.304 ///\endcode
1.305 -
1.306 class InArcIt : public Arc {
1.307 public:
1.308 /// Default constructor
1.309
1.310 - /// @warning The default constructor sets the iterator
1.311 - /// to an undefined value.
1.312 + /// Default constructor.
1.313 + /// \warning It sets the iterator to an undefined value.
1.314 InArcIt() { }
1.315 /// Copy constructor.
1.316
1.317 /// Copy constructor.
1.318 ///
1.319 InArcIt(const InArcIt& e) : Arc(e) { }
1.320 - /// Initialize the iterator to be invalid.
1.321 + /// %Invalid constructor \& conversion.
1.322
1.323 - /// Initialize the iterator to be invalid.
1.324 + /// Initializes the iterator to be invalid.
1.325 + /// \sa Invalid for more details.
1.326 + InArcIt(Invalid) { }
1.327 + /// Sets the iterator to the first incoming arc.
1.328 +
1.329 + /// Sets the iterator to the first incoming arc of the given node.
1.330 ///
1.331 - InArcIt(Invalid) { }
1.332 - /// This constructor sets the iterator to first incoming arc.
1.333 + InArcIt(const Digraph&, const Node&) { }
1.334 + /// Sets the iterator to the given arc.
1.335
1.336 - /// This constructor set the iterator to the first incoming arc of
1.337 - /// the node.
1.338 - InArcIt(const Digraph&, const Node&) { }
1.339 - /// Arc -> InArcIt conversion
1.340 -
1.341 - /// Sets the iterator to the value of the trivial iterator \c e.
1.342 - /// This feature necessitates that each time we
1.343 - /// iterate the arc-set, the iteration order is the same.
1.344 + /// Sets the iterator to the given arc of the given digraph.
1.345 + ///
1.346 InArcIt(const Digraph&, const Arc&) { }
1.347 /// Next incoming arc
1.348
1.349 - /// Assign the iterator to the next inarc of the corresponding node.
1.350 - ///
1.351 + /// Assign the iterator to the next
1.352 + /// incoming arc of the corresponding node.
1.353 InArcIt& operator++() { return *this; }
1.354 };
1.355 - /// This iterator goes through each arc.
1.356
1.357 - /// This iterator goes through each arc of a digraph.
1.358 + /// Iterator class for the arcs.
1.359 +
1.360 + /// This iterator goes through each arc of the digraph.
1.361 /// Its usage is quite simple, for example you can count the number
1.362 - /// of arcs in a digraph \c g of type \c Digraph as follows:
1.363 + /// of arcs in a digraph \c g of type \c %Digraph as follows:
1.364 ///\code
1.365 /// int count=0;
1.366 - /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
1.367 + /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.368 ///\endcode
1.369 class ArcIt : public Arc {
1.370 public:
1.371 /// Default constructor
1.372
1.373 - /// @warning The default constructor sets the iterator
1.374 - /// to an undefined value.
1.375 + /// Default constructor.
1.376 + /// \warning It sets the iterator to an undefined value.
1.377 ArcIt() { }
1.378 /// Copy constructor.
1.379
1.380 /// Copy constructor.
1.381 ///
1.382 ArcIt(const ArcIt& e) : Arc(e) { }
1.383 - /// Initialize the iterator to be invalid.
1.384 + /// %Invalid constructor \& conversion.
1.385
1.386 - /// Initialize the iterator to be invalid.
1.387 + /// Initializes the iterator to be invalid.
1.388 + /// \sa Invalid for more details.
1.389 + ArcIt(Invalid) { }
1.390 + /// Sets the iterator to the first arc.
1.391 +
1.392 + /// Sets the iterator to the first arc of the given digraph.
1.393 ///
1.394 - ArcIt(Invalid) { }
1.395 - /// This constructor sets the iterator to the first arc.
1.396 + explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.397 + /// Sets the iterator to the given arc.
1.398
1.399 - /// This constructor sets the iterator to the first arc of \c g.
1.400 - ///@param g the digraph
1.401 - ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.402 - /// Arc -> ArcIt conversion
1.403 -
1.404 - /// Sets the iterator to the value of the trivial iterator \c e.
1.405 - /// This feature necessitates that each time we
1.406 - /// iterate the arc-set, the iteration order is the same.
1.407 + /// Sets the iterator to the given arc of the given digraph.
1.408 + ///
1.409 ArcIt(const Digraph&, const Arc&) { }
1.410 - ///Next arc
1.411 + /// Next arc
1.412
1.413 /// Assign the iterator to the next arc.
1.414 + ///
1.415 ArcIt& operator++() { return *this; }
1.416 };
1.417 - ///Gives back the target node of an arc.
1.418
1.419 - ///Gives back the target node of an arc.
1.420 + /// \brief The source node of the arc.
1.421 ///
1.422 - Node target(Arc) const { return INVALID; }
1.423 - ///Gives back the source node of an arc.
1.424 -
1.425 - ///Gives back the source node of an arc.
1.426 - ///
1.427 + /// Returns the source node of the given arc.
1.428 Node source(Arc) const { return INVALID; }
1.429
1.430 - /// \brief Returns the ID of the node.
1.431 + /// \brief The target node of the arc.
1.432 + ///
1.433 + /// Returns the target node of the given arc.
1.434 + Node target(Arc) const { return INVALID; }
1.435 +
1.436 + /// \brief The ID of the node.
1.437 + ///
1.438 + /// Returns the ID of the given node.
1.439 int id(Node) const { return -1; }
1.440
1.441 - /// \brief Returns the ID of the arc.
1.442 + /// \brief The ID of the arc.
1.443 + ///
1.444 + /// Returns the ID of the given arc.
1.445 int id(Arc) const { return -1; }
1.446
1.447 - /// \brief Returns the node with the given ID.
1.448 + /// \brief The node with the given ID.
1.449 ///
1.450 - /// \pre The argument should be a valid node ID in the graph.
1.451 + /// Returns the node with the given ID.
1.452 + /// \pre The argument should be a valid node ID in the digraph.
1.453 Node nodeFromId(int) const { return INVALID; }
1.454
1.455 - /// \brief Returns the arc with the given ID.
1.456 + /// \brief The arc with the given ID.
1.457 ///
1.458 - /// \pre The argument should be a valid arc ID in the graph.
1.459 + /// Returns the arc with the given ID.
1.460 + /// \pre The argument should be a valid arc ID in the digraph.
1.461 Arc arcFromId(int) const { return INVALID; }
1.462
1.463 - /// \brief Returns an upper bound on the node IDs.
1.464 + /// \brief An upper bound on the node IDs.
1.465 + ///
1.466 + /// Returns an upper bound on the node IDs.
1.467 int maxNodeId() const { return -1; }
1.468
1.469 - /// \brief Returns an upper bound on the arc IDs.
1.470 + /// \brief An upper bound on the arc IDs.
1.471 + ///
1.472 + /// Returns an upper bound on the arc IDs.
1.473 int maxArcId() const { return -1; }
1.474
1.475 void first(Node&) const {}
1.476 @@ -392,45 +390,46 @@
1.477 // Dummy parameter.
1.478 int maxId(Arc) const { return -1; }
1.479
1.480 + /// \brief The opposite node on the arc.
1.481 + ///
1.482 + /// Returns the opposite node on the given arc.
1.483 + Node oppositeNode(Node, Arc) const { return INVALID; }
1.484 +
1.485 /// \brief The base node of the iterator.
1.486 ///
1.487 - /// Gives back the base node of the iterator.
1.488 - /// It is always the target of the pointed arc.
1.489 - Node baseNode(const InArcIt&) const { return INVALID; }
1.490 + /// Returns the base node of the given outgoing arc iterator
1.491 + /// (i.e. the source node of the corresponding arc).
1.492 + Node baseNode(OutArcIt) const { return INVALID; }
1.493
1.494 /// \brief The running node of the iterator.
1.495 ///
1.496 - /// Gives back the running node of the iterator.
1.497 - /// It is always the source of the pointed arc.
1.498 - Node runningNode(const InArcIt&) const { return INVALID; }
1.499 + /// Returns the running node of the given outgoing arc iterator
1.500 + /// (i.e. the target node of the corresponding arc).
1.501 + Node runningNode(OutArcIt) const { return INVALID; }
1.502
1.503 /// \brief The base node of the iterator.
1.504 ///
1.505 - /// Gives back the base node of the iterator.
1.506 - /// It is always the source of the pointed arc.
1.507 - Node baseNode(const OutArcIt&) const { return INVALID; }
1.508 + /// Returns the base node of the given incomming arc iterator
1.509 + /// (i.e. the target node of the corresponding arc).
1.510 + Node baseNode(InArcIt) const { return INVALID; }
1.511
1.512 /// \brief The running node of the iterator.
1.513 ///
1.514 - /// Gives back the running node of the iterator.
1.515 - /// It is always the target of the pointed arc.
1.516 - Node runningNode(const OutArcIt&) const { return INVALID; }
1.517 + /// Returns the running node of the given incomming arc iterator
1.518 + /// (i.e. the source node of the corresponding arc).
1.519 + Node runningNode(InArcIt) const { return INVALID; }
1.520
1.521 - /// \brief The opposite node on the given arc.
1.522 + /// \brief Standard graph map type for the nodes.
1.523 ///
1.524 - /// Gives back the opposite node on the given arc.
1.525 - Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
1.526 -
1.527 - /// \brief Reference map of the nodes to type \c T.
1.528 - ///
1.529 - /// Reference map of the nodes to type \c T.
1.530 + /// Standard graph map type for the nodes.
1.531 + /// It conforms to the ReferenceMap concept.
1.532 template<class T>
1.533 class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
1.534 public:
1.535
1.536 - ///\e
1.537 - NodeMap(const Digraph&) { }
1.538 - ///\e
1.539 + /// Constructor
1.540 + explicit NodeMap(const Digraph&) { }
1.541 + /// Constructor with given initial value
1.542 NodeMap(const Digraph&, T) { }
1.543
1.544 private:
1.545 @@ -445,17 +444,19 @@
1.546 }
1.547 };
1.548
1.549 - /// \brief Reference map of the arcs to type \c T.
1.550 + /// \brief Standard graph map type for the arcs.
1.551 ///
1.552 - /// Reference map of the arcs to type \c T.
1.553 + /// Standard graph map type for the arcs.
1.554 + /// It conforms to the ReferenceMap concept.
1.555 template<class T>
1.556 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
1.557 public:
1.558
1.559 - ///\e
1.560 - ArcMap(const Digraph&) { }
1.561 - ///\e
1.562 + /// Constructor
1.563 + explicit ArcMap(const Digraph&) { }
1.564 + /// Constructor with given initial value
1.565 ArcMap(const Digraph&, T) { }
1.566 +
1.567 private:
1.568 ///Copy constructor
1.569 ArcMap(const ArcMap& em) :
2.1 --- a/lemon/concepts/graph.h Thu Aug 20 22:52:16 2009 +0200
2.2 +++ b/lemon/concepts/graph.h Sun Aug 23 11:07:50 2009 +0200
2.3 @@ -18,12 +18,14 @@
2.4
2.5 ///\ingroup graph_concepts
2.6 ///\file
2.7 -///\brief The concept of Undirected Graphs.
2.8 +///\brief The concept of undirected graphs.
2.9
2.10 #ifndef LEMON_CONCEPTS_GRAPH_H
2.11 #define LEMON_CONCEPTS_GRAPH_H
2.12
2.13 #include <lemon/concepts/graph_components.h>
2.14 +#include <lemon/concepts/maps.h>
2.15 +#include <lemon/concept_check.h>
2.16 #include <lemon/core.h>
2.17
2.18 namespace lemon {
2.19 @@ -31,63 +33,74 @@
2.20
2.21 /// \ingroup graph_concepts
2.22 ///
2.23 - /// \brief Class describing the concept of Undirected Graphs.
2.24 + /// \brief Class describing the concept of undirected graphs.
2.25 ///
2.26 - /// This class describes the common interface of all Undirected
2.27 - /// Graphs.
2.28 + /// This class describes the common interface of all undirected
2.29 + /// graphs.
2.30 ///
2.31 - /// As all concept describing classes it provides only interface
2.32 - /// without any sensible implementation. So any algorithm for
2.33 - /// undirected graph should compile with this class, but it will not
2.34 + /// Like all concept classes, it only provides an interface
2.35 + /// without any sensible implementation. So any general algorithm for
2.36 + /// undirected graphs should compile with this class, but it will not
2.37 /// run properly, of course.
2.38 + /// An actual graph implementation like \ref ListGraph or
2.39 + /// \ref SmartGraph may have additional functionality.
2.40 ///
2.41 - /// The LEMON undirected graphs also fulfill the concept of
2.42 - /// directed graphs (\ref lemon::concepts::Digraph "Digraph
2.43 - /// Concept"). Each edges can be seen as two opposite
2.44 - /// directed arc and consequently the undirected graph can be
2.45 - /// seen as the direceted graph of these directed arcs. The
2.46 - /// Graph has the Edge inner class for the edges and
2.47 - /// the Arc type for the directed arcs. The Arc type is
2.48 - /// convertible to Edge or inherited from it so from a directed
2.49 - /// arc we can get the represented edge.
2.50 + /// The undirected graphs also fulfill the concept of \ref Digraph
2.51 + /// "directed graphs", since each edge can also be regarded as two
2.52 + /// oppositely directed arcs.
2.53 + /// Undirected graphs provide an Edge type for the undirected edges and
2.54 + /// an Arc type for the directed arcs. The Arc type is convertible to
2.55 + /// Edge or inherited from it, i.e. the corresponding edge can be
2.56 + /// obtained from an arc.
2.57 + /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
2.58 + /// and ArcMap classes can be used for the arcs (just like in digraphs).
2.59 + /// Both InArcIt and OutArcIt iterates on the same edges but with
2.60 + /// opposite direction. IncEdgeIt also iterates on the same edges
2.61 + /// as OutArcIt and InArcIt, but it is not convertible to Arc,
2.62 + /// only to Edge.
2.63 ///
2.64 - /// In the sense of the LEMON each edge has a default
2.65 - /// direction (it should be in every computer implementation,
2.66 - /// because the order of edge's nodes defines an
2.67 - /// orientation). With the default orientation we can define that
2.68 - /// the directed arc is forward or backward directed. With the \c
2.69 - /// direction() and \c direct() function we can get the direction
2.70 - /// of the directed arc and we can direct an edge.
2.71 + /// In LEMON, each undirected edge has an inherent orientation.
2.72 + /// Thus it can defined if an arc is forward or backward oriented in
2.73 + /// an undirected graph with respect to this default oriantation of
2.74 + /// the represented edge.
2.75 + /// With the direction() and direct() functions the direction
2.76 + /// of an arc can be obtained and set, respectively.
2.77 ///
2.78 - /// The EdgeIt is an iterator for the edges. We can use
2.79 - /// the EdgeMap to map values for the edges. The InArcIt and
2.80 - /// OutArcIt iterates on the same edges but with opposite
2.81 - /// direction. The IncEdgeIt iterates also on the same edges
2.82 - /// as the OutArcIt and InArcIt but it is not convertible to Arc just
2.83 - /// to Edge.
2.84 + /// Only nodes and edges can be added to or removed from an undirected
2.85 + /// graph and the corresponding arcs are added or removed automatically.
2.86 + ///
2.87 + /// \sa Digraph
2.88 class Graph {
2.89 + private:
2.90 + /// Graphs are \e not copy constructible. Use DigraphCopy instead.
2.91 + Graph(const Graph&) {}
2.92 + /// \brief Assignment of a graph to another one is \e not allowed.
2.93 + /// Use DigraphCopy instead.
2.94 + void operator=(const Graph&) {}
2.95 +
2.96 public:
2.97 - /// \brief The undirected graph should be tagged by the
2.98 - /// UndirectedTag.
2.99 + /// Default constructor.
2.100 + Graph() {}
2.101 +
2.102 + /// \brief Undirected graphs should be tagged with \c UndirectedTag.
2.103 ///
2.104 - /// The undirected graph should be tagged by the UndirectedTag. This
2.105 - /// tag helps the enable_if technics to make compile time
2.106 + /// Undirected graphs should be tagged with \c UndirectedTag.
2.107 + ///
2.108 + /// This tag helps the \c enable_if technics to make compile time
2.109 /// specializations for undirected graphs.
2.110 typedef True UndirectedTag;
2.111
2.112 - /// \brief The base type of node iterators,
2.113 - /// or in other words, the trivial node iterator.
2.114 - ///
2.115 - /// This is the base type of each node iterator,
2.116 - /// thus each kind of node iterator converts to this.
2.117 - /// More precisely each kind of node iterator should be inherited
2.118 - /// from the trivial node iterator.
2.119 + /// The node type of the graph
2.120 +
2.121 + /// This class identifies a node of the graph. It also serves
2.122 + /// as a base class of the node iterators,
2.123 + /// thus they convert to this type.
2.124 class Node {
2.125 public:
2.126 /// Default constructor
2.127
2.128 - /// @warning The default constructor sets the iterator
2.129 - /// to an undefined value.
2.130 + /// Default constructor.
2.131 + /// \warning It sets the object to an undefined value.
2.132 Node() { }
2.133 /// Copy constructor.
2.134
2.135 @@ -95,40 +108,40 @@
2.136 ///
2.137 Node(const Node&) { }
2.138
2.139 - /// Invalid constructor \& conversion.
2.140 + /// %Invalid constructor \& conversion.
2.141
2.142 - /// This constructor initializes the iterator to be invalid.
2.143 + /// Initializes the object to be invalid.
2.144 /// \sa Invalid for more details.
2.145 Node(Invalid) { }
2.146 /// Equality operator
2.147
2.148 + /// Equality operator.
2.149 + ///
2.150 /// Two iterators are equal if and only if they point to the
2.151 - /// same object or both are invalid.
2.152 + /// same object or both are \c INVALID.
2.153 bool operator==(Node) const { return true; }
2.154
2.155 /// Inequality operator
2.156
2.157 - /// \sa operator==(Node n)
2.158 - ///
2.159 + /// Inequality operator.
2.160 bool operator!=(Node) const { return true; }
2.161
2.162 /// Artificial ordering operator.
2.163
2.164 - /// To allow the use of graph descriptors as key type in std::map or
2.165 - /// similar associative container we require this.
2.166 + /// Artificial ordering operator.
2.167 ///
2.168 - /// \note This operator only have to define some strict ordering of
2.169 + /// \note This operator only has to define some strict ordering of
2.170 /// the items; this order has nothing to do with the iteration
2.171 /// ordering of the items.
2.172 bool operator<(Node) const { return false; }
2.173
2.174 };
2.175
2.176 - /// This iterator goes through each node.
2.177 + /// Iterator class for the nodes.
2.178
2.179 - /// This iterator goes through each node.
2.180 + /// This iterator goes through each node of the graph.
2.181 /// Its usage is quite simple, for example you can count the number
2.182 - /// of nodes in graph \c g of type \c Graph like this:
2.183 + /// of nodes in a graph \c g of type \c %Graph like this:
2.184 ///\code
2.185 /// int count=0;
2.186 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
2.187 @@ -137,30 +150,28 @@
2.188 public:
2.189 /// Default constructor
2.190
2.191 - /// @warning The default constructor sets the iterator
2.192 - /// to an undefined value.
2.193 + /// Default constructor.
2.194 + /// \warning It sets the iterator to an undefined value.
2.195 NodeIt() { }
2.196 /// Copy constructor.
2.197
2.198 /// Copy constructor.
2.199 ///
2.200 NodeIt(const NodeIt& n) : Node(n) { }
2.201 - /// Invalid constructor \& conversion.
2.202 + /// %Invalid constructor \& conversion.
2.203
2.204 - /// Initialize the iterator to be invalid.
2.205 + /// Initializes the iterator to be invalid.
2.206 /// \sa Invalid for more details.
2.207 NodeIt(Invalid) { }
2.208 /// Sets the iterator to the first node.
2.209
2.210 - /// Sets the iterator to the first node of \c g.
2.211 + /// Sets the iterator to the first node of the given digraph.
2.212 ///
2.213 - NodeIt(const Graph&) { }
2.214 - /// Node -> NodeIt conversion.
2.215 + explicit NodeIt(const Graph&) { }
2.216 + /// Sets the iterator to the given node.
2.217
2.218 - /// Sets the iterator to the node of \c the graph pointed by
2.219 - /// the trivial iterator.
2.220 - /// This feature necessitates that each time we
2.221 - /// iterate the arc-set, the iteration order is the same.
2.222 + /// Sets the iterator to the given node of the given digraph.
2.223 + ///
2.224 NodeIt(const Graph&, const Node&) { }
2.225 /// Next node.
2.226
2.227 @@ -170,54 +181,55 @@
2.228 };
2.229
2.230
2.231 - /// The base type of the edge iterators.
2.232 + /// The edge type of the graph
2.233
2.234 - /// The base type of the edge iterators.
2.235 - ///
2.236 + /// This class identifies an edge of the graph. It also serves
2.237 + /// as a base class of the edge iterators,
2.238 + /// thus they will convert to this type.
2.239 class Edge {
2.240 public:
2.241 /// Default constructor
2.242
2.243 - /// @warning The default constructor sets the iterator
2.244 - /// to an undefined value.
2.245 + /// Default constructor.
2.246 + /// \warning It sets the object to an undefined value.
2.247 Edge() { }
2.248 /// Copy constructor.
2.249
2.250 /// Copy constructor.
2.251 ///
2.252 Edge(const Edge&) { }
2.253 - /// Initialize the iterator to be invalid.
2.254 + /// %Invalid constructor \& conversion.
2.255
2.256 - /// Initialize the iterator to be invalid.
2.257 - ///
2.258 + /// Initializes the object to be invalid.
2.259 + /// \sa Invalid for more details.
2.260 Edge(Invalid) { }
2.261 /// Equality operator
2.262
2.263 + /// Equality operator.
2.264 + ///
2.265 /// Two iterators are equal if and only if they point to the
2.266 - /// same object or both are invalid.
2.267 + /// same object or both are \c INVALID.
2.268 bool operator==(Edge) const { return true; }
2.269 /// Inequality operator
2.270
2.271 - /// \sa operator==(Edge n)
2.272 - ///
2.273 + /// Inequality operator.
2.274 bool operator!=(Edge) const { return true; }
2.275
2.276 /// Artificial ordering operator.
2.277
2.278 - /// To allow the use of graph descriptors as key type in std::map or
2.279 - /// similar associative container we require this.
2.280 + /// Artificial ordering operator.
2.281 ///
2.282 - /// \note This operator only have to define some strict ordering of
2.283 - /// the items; this order has nothing to do with the iteration
2.284 - /// ordering of the items.
2.285 + /// \note This operator only has to define some strict ordering of
2.286 + /// the edges; this order has nothing to do with the iteration
2.287 + /// ordering of the edges.
2.288 bool operator<(Edge) const { return false; }
2.289 };
2.290
2.291 - /// This iterator goes through each edge.
2.292 + /// Iterator class for the edges.
2.293
2.294 - /// This iterator goes through each edge of a graph.
2.295 + /// This iterator goes through each edge of the graph.
2.296 /// Its usage is quite simple, for example you can count the number
2.297 - /// of edges in a graph \c g of type \c Graph as follows:
2.298 + /// of edges in a graph \c g of type \c %Graph as follows:
2.299 ///\code
2.300 /// int count=0;
2.301 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
2.302 @@ -226,290 +238,285 @@
2.303 public:
2.304 /// Default constructor
2.305
2.306 - /// @warning The default constructor sets the iterator
2.307 - /// to an undefined value.
2.308 + /// Default constructor.
2.309 + /// \warning It sets the iterator to an undefined value.
2.310 EdgeIt() { }
2.311 /// Copy constructor.
2.312
2.313 /// Copy constructor.
2.314 ///
2.315 EdgeIt(const EdgeIt& e) : Edge(e) { }
2.316 - /// Initialize the iterator to be invalid.
2.317 + /// %Invalid constructor \& conversion.
2.318
2.319 - /// Initialize the iterator to be invalid.
2.320 + /// Initializes the iterator to be invalid.
2.321 + /// \sa Invalid for more details.
2.322 + EdgeIt(Invalid) { }
2.323 + /// Sets the iterator to the first edge.
2.324 +
2.325 + /// Sets the iterator to the first edge of the given graph.
2.326 ///
2.327 - EdgeIt(Invalid) { }
2.328 - /// This constructor sets the iterator to the first edge.
2.329 + explicit EdgeIt(const Graph&) { }
2.330 + /// Sets the iterator to the given edge.
2.331
2.332 - /// This constructor sets the iterator to the first edge.
2.333 - EdgeIt(const Graph&) { }
2.334 - /// Edge -> EdgeIt conversion
2.335 -
2.336 - /// Sets the iterator to the value of the trivial iterator.
2.337 - /// This feature necessitates that each time we
2.338 - /// iterate the edge-set, the iteration order is the
2.339 - /// same.
2.340 + /// Sets the iterator to the given edge of the given graph.
2.341 + ///
2.342 EdgeIt(const Graph&, const Edge&) { }
2.343 /// Next edge
2.344
2.345 /// Assign the iterator to the next edge.
2.346 + ///
2.347 EdgeIt& operator++() { return *this; }
2.348 };
2.349
2.350 - /// \brief This iterator goes trough the incident undirected
2.351 - /// arcs of a node.
2.352 - ///
2.353 - /// This iterator goes trough the incident edges
2.354 - /// of a certain node of a graph. You should assume that the
2.355 - /// loop arcs will be iterated twice.
2.356 - ///
2.357 + /// Iterator class for the incident edges of a node.
2.358 +
2.359 + /// This iterator goes trough the incident undirected edges
2.360 + /// of a certain node of a graph.
2.361 /// Its usage is quite simple, for example you can compute the
2.362 - /// degree (i.e. count the number of incident arcs of a node \c n
2.363 - /// in graph \c g of type \c Graph as follows.
2.364 + /// degree (i.e. the number of incident edges) of a node \c n
2.365 + /// in a graph \c g of type \c %Graph as follows.
2.366 ///
2.367 ///\code
2.368 /// int count=0;
2.369 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
2.370 ///\endcode
2.371 + ///
2.372 + /// \warning Loop edges will be iterated twice.
2.373 class IncEdgeIt : public Edge {
2.374 public:
2.375 /// Default constructor
2.376
2.377 - /// @warning The default constructor sets the iterator
2.378 - /// to an undefined value.
2.379 + /// Default constructor.
2.380 + /// \warning It sets the iterator to an undefined value.
2.381 IncEdgeIt() { }
2.382 /// Copy constructor.
2.383
2.384 /// Copy constructor.
2.385 ///
2.386 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
2.387 - /// Initialize the iterator to be invalid.
2.388 + /// %Invalid constructor \& conversion.
2.389
2.390 - /// Initialize the iterator to be invalid.
2.391 + /// Initializes the iterator to be invalid.
2.392 + /// \sa Invalid for more details.
2.393 + IncEdgeIt(Invalid) { }
2.394 + /// Sets the iterator to the first incident edge.
2.395 +
2.396 + /// Sets the iterator to the first incident edge of the given node.
2.397 ///
2.398 - IncEdgeIt(Invalid) { }
2.399 - /// This constructor sets the iterator to first incident arc.
2.400 + IncEdgeIt(const Graph&, const Node&) { }
2.401 + /// Sets the iterator to the given edge.
2.402
2.403 - /// This constructor set the iterator to the first incident arc of
2.404 - /// the node.
2.405 - IncEdgeIt(const Graph&, const Node&) { }
2.406 - /// Edge -> IncEdgeIt conversion
2.407 + /// Sets the iterator to the given edge of the given graph.
2.408 + ///
2.409 + IncEdgeIt(const Graph&, const Edge&) { }
2.410 + /// Next incident edge
2.411
2.412 - /// Sets the iterator to the value of the trivial iterator \c e.
2.413 - /// This feature necessitates that each time we
2.414 - /// iterate the arc-set, the iteration order is the same.
2.415 - IncEdgeIt(const Graph&, const Edge&) { }
2.416 - /// Next incident arc
2.417 -
2.418 - /// Assign the iterator to the next incident arc
2.419 + /// Assign the iterator to the next incident edge
2.420 /// of the corresponding node.
2.421 IncEdgeIt& operator++() { return *this; }
2.422 };
2.423
2.424 - /// The directed arc type.
2.425 + /// The arc type of the graph
2.426
2.427 - /// The directed arc type. It can be converted to the
2.428 - /// edge or it should be inherited from the undirected
2.429 - /// edge.
2.430 + /// This class identifies a directed arc of the graph. It also serves
2.431 + /// as a base class of the arc iterators,
2.432 + /// thus they will convert to this type.
2.433 class Arc {
2.434 public:
2.435 /// Default constructor
2.436
2.437 - /// @warning The default constructor sets the iterator
2.438 - /// to an undefined value.
2.439 + /// Default constructor.
2.440 + /// \warning It sets the object to an undefined value.
2.441 Arc() { }
2.442 /// Copy constructor.
2.443
2.444 /// Copy constructor.
2.445 ///
2.446 Arc(const Arc&) { }
2.447 - /// Initialize the iterator to be invalid.
2.448 + /// %Invalid constructor \& conversion.
2.449
2.450 - /// Initialize the iterator to be invalid.
2.451 - ///
2.452 + /// Initializes the object to be invalid.
2.453 + /// \sa Invalid for more details.
2.454 Arc(Invalid) { }
2.455 /// Equality operator
2.456
2.457 + /// Equality operator.
2.458 + ///
2.459 /// Two iterators are equal if and only if they point to the
2.460 - /// same object or both are invalid.
2.461 + /// same object or both are \c INVALID.
2.462 bool operator==(Arc) const { return true; }
2.463 /// Inequality operator
2.464
2.465 - /// \sa operator==(Arc n)
2.466 - ///
2.467 + /// Inequality operator.
2.468 bool operator!=(Arc) const { return true; }
2.469
2.470 /// Artificial ordering operator.
2.471
2.472 - /// To allow the use of graph descriptors as key type in std::map or
2.473 - /// similar associative container we require this.
2.474 + /// Artificial ordering operator.
2.475 ///
2.476 - /// \note This operator only have to define some strict ordering of
2.477 - /// the items; this order has nothing to do with the iteration
2.478 - /// ordering of the items.
2.479 + /// \note This operator only has to define some strict ordering of
2.480 + /// the arcs; this order has nothing to do with the iteration
2.481 + /// ordering of the arcs.
2.482 bool operator<(Arc) const { return false; }
2.483
2.484 - /// Converison to Edge
2.485 + /// Converison to \c Edge
2.486 +
2.487 + /// Converison to \c Edge.
2.488 + ///
2.489 operator Edge() const { return Edge(); }
2.490 };
2.491 - /// This iterator goes through each directed arc.
2.492
2.493 - /// This iterator goes through each arc of a graph.
2.494 + /// Iterator class for the arcs.
2.495 +
2.496 + /// This iterator goes through each directed arc of the graph.
2.497 /// Its usage is quite simple, for example you can count the number
2.498 - /// of arcs in a graph \c g of type \c Graph as follows:
2.499 + /// of arcs in a graph \c g of type \c %Graph as follows:
2.500 ///\code
2.501 /// int count=0;
2.502 - /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
2.503 + /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
2.504 ///\endcode
2.505 class ArcIt : public Arc {
2.506 public:
2.507 /// Default constructor
2.508
2.509 - /// @warning The default constructor sets the iterator
2.510 - /// to an undefined value.
2.511 + /// Default constructor.
2.512 + /// \warning It sets the iterator to an undefined value.
2.513 ArcIt() { }
2.514 /// Copy constructor.
2.515
2.516 /// Copy constructor.
2.517 ///
2.518 ArcIt(const ArcIt& e) : Arc(e) { }
2.519 - /// Initialize the iterator to be invalid.
2.520 + /// %Invalid constructor \& conversion.
2.521
2.522 - /// Initialize the iterator to be invalid.
2.523 + /// Initializes the iterator to be invalid.
2.524 + /// \sa Invalid for more details.
2.525 + ArcIt(Invalid) { }
2.526 + /// Sets the iterator to the first arc.
2.527 +
2.528 + /// Sets the iterator to the first arc of the given graph.
2.529 ///
2.530 - ArcIt(Invalid) { }
2.531 - /// This constructor sets the iterator to the first arc.
2.532 + explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
2.533 + /// Sets the iterator to the given arc.
2.534
2.535 - /// This constructor sets the iterator to the first arc of \c g.
2.536 - ///@param g the graph
2.537 - ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
2.538 - /// Arc -> ArcIt conversion
2.539 -
2.540 - /// Sets the iterator to the value of the trivial iterator \c e.
2.541 - /// This feature necessitates that each time we
2.542 - /// iterate the arc-set, the iteration order is the same.
2.543 + /// Sets the iterator to the given arc of the given graph.
2.544 + ///
2.545 ArcIt(const Graph&, const Arc&) { }
2.546 - ///Next arc
2.547 + /// Next arc
2.548
2.549 /// Assign the iterator to the next arc.
2.550 + ///
2.551 ArcIt& operator++() { return *this; }
2.552 };
2.553
2.554 - /// This iterator goes trough the outgoing directed arcs of a node.
2.555 + /// Iterator class for the outgoing arcs of a node.
2.556
2.557 - /// This iterator goes trough the \e outgoing arcs of a certain node
2.558 - /// of a graph.
2.559 + /// This iterator goes trough the \e outgoing directed arcs of a
2.560 + /// certain node of a graph.
2.561 /// Its usage is quite simple, for example you can count the number
2.562 /// of outgoing arcs of a node \c n
2.563 - /// in graph \c g of type \c Graph as follows.
2.564 + /// in a graph \c g of type \c %Graph as follows.
2.565 ///\code
2.566 /// int count=0;
2.567 - /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
2.568 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
2.569 ///\endcode
2.570 -
2.571 class OutArcIt : public Arc {
2.572 public:
2.573 /// Default constructor
2.574
2.575 - /// @warning The default constructor sets the iterator
2.576 - /// to an undefined value.
2.577 + /// Default constructor.
2.578 + /// \warning It sets the iterator to an undefined value.
2.579 OutArcIt() { }
2.580 /// Copy constructor.
2.581
2.582 /// Copy constructor.
2.583 ///
2.584 OutArcIt(const OutArcIt& e) : Arc(e) { }
2.585 - /// Initialize the iterator to be invalid.
2.586 + /// %Invalid constructor \& conversion.
2.587
2.588 - /// Initialize the iterator to be invalid.
2.589 + /// Initializes the iterator to be invalid.
2.590 + /// \sa Invalid for more details.
2.591 + OutArcIt(Invalid) { }
2.592 + /// Sets the iterator to the first outgoing arc.
2.593 +
2.594 + /// Sets the iterator to the first outgoing arc of the given node.
2.595 ///
2.596 - OutArcIt(Invalid) { }
2.597 - /// This constructor sets the iterator to the first outgoing arc.
2.598 -
2.599 - /// This constructor sets the iterator to the first outgoing arc of
2.600 - /// the node.
2.601 - ///@param n the node
2.602 - ///@param g the graph
2.603 OutArcIt(const Graph& n, const Node& g) {
2.604 ignore_unused_variable_warning(n);
2.605 ignore_unused_variable_warning(g);
2.606 }
2.607 - /// Arc -> OutArcIt conversion
2.608 + /// Sets the iterator to the given arc.
2.609
2.610 - /// Sets the iterator to the value of the trivial iterator.
2.611 - /// This feature necessitates that each time we
2.612 - /// iterate the arc-set, the iteration order is the same.
2.613 + /// Sets the iterator to the given arc of the given graph.
2.614 + ///
2.615 OutArcIt(const Graph&, const Arc&) { }
2.616 - ///Next outgoing arc
2.617 + /// Next outgoing arc
2.618
2.619 /// Assign the iterator to the next
2.620 /// outgoing arc of the corresponding node.
2.621 OutArcIt& operator++() { return *this; }
2.622 };
2.623
2.624 - /// This iterator goes trough the incoming directed arcs of a node.
2.625 + /// Iterator class for the incoming arcs of a node.
2.626
2.627 - /// This iterator goes trough the \e incoming arcs of a certain node
2.628 - /// of a graph.
2.629 + /// This iterator goes trough the \e incoming directed arcs of a
2.630 + /// certain node of a graph.
2.631 /// Its usage is quite simple, for example you can count the number
2.632 - /// of outgoing arcs of a node \c n
2.633 - /// in graph \c g of type \c Graph as follows.
2.634 + /// of incoming arcs of a node \c n
2.635 + /// in a graph \c g of type \c %Graph as follows.
2.636 ///\code
2.637 /// int count=0;
2.638 - /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
2.639 + /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
2.640 ///\endcode
2.641 -
2.642 class InArcIt : public Arc {
2.643 public:
2.644 /// Default constructor
2.645
2.646 - /// @warning The default constructor sets the iterator
2.647 - /// to an undefined value.
2.648 + /// Default constructor.
2.649 + /// \warning It sets the iterator to an undefined value.
2.650 InArcIt() { }
2.651 /// Copy constructor.
2.652
2.653 /// Copy constructor.
2.654 ///
2.655 InArcIt(const InArcIt& e) : Arc(e) { }
2.656 - /// Initialize the iterator to be invalid.
2.657 + /// %Invalid constructor \& conversion.
2.658
2.659 - /// Initialize the iterator to be invalid.
2.660 + /// Initializes the iterator to be invalid.
2.661 + /// \sa Invalid for more details.
2.662 + InArcIt(Invalid) { }
2.663 + /// Sets the iterator to the first incoming arc.
2.664 +
2.665 + /// Sets the iterator to the first incoming arc of the given node.
2.666 ///
2.667 - InArcIt(Invalid) { }
2.668 - /// This constructor sets the iterator to first incoming arc.
2.669 -
2.670 - /// This constructor set the iterator to the first incoming arc of
2.671 - /// the node.
2.672 - ///@param n the node
2.673 - ///@param g the graph
2.674 InArcIt(const Graph& g, const Node& n) {
2.675 ignore_unused_variable_warning(n);
2.676 ignore_unused_variable_warning(g);
2.677 }
2.678 - /// Arc -> InArcIt conversion
2.679 + /// Sets the iterator to the given arc.
2.680
2.681 - /// Sets the iterator to the value of the trivial iterator \c e.
2.682 - /// This feature necessitates that each time we
2.683 - /// iterate the arc-set, the iteration order is the same.
2.684 + /// Sets the iterator to the given arc of the given graph.
2.685 + ///
2.686 InArcIt(const Graph&, const Arc&) { }
2.687 /// Next incoming arc
2.688
2.689 - /// Assign the iterator to the next inarc of the corresponding node.
2.690 - ///
2.691 + /// Assign the iterator to the next
2.692 + /// incoming arc of the corresponding node.
2.693 InArcIt& operator++() { return *this; }
2.694 };
2.695
2.696 - /// \brief Reference map of the nodes to type \c T.
2.697 + /// \brief Standard graph map type for the nodes.
2.698 ///
2.699 - /// Reference map of the nodes to type \c T.
2.700 + /// Standard graph map type for the nodes.
2.701 + /// It conforms to the ReferenceMap concept.
2.702 template<class T>
2.703 class NodeMap : public ReferenceMap<Node, T, T&, const T&>
2.704 {
2.705 public:
2.706
2.707 - ///\e
2.708 - NodeMap(const Graph&) { }
2.709 - ///\e
2.710 + /// Constructor
2.711 + explicit NodeMap(const Graph&) { }
2.712 + /// Constructor with given initial value
2.713 NodeMap(const Graph&, T) { }
2.714
2.715 private:
2.716 @@ -524,18 +531,20 @@
2.717 }
2.718 };
2.719
2.720 - /// \brief Reference map of the arcs to type \c T.
2.721 + /// \brief Standard graph map type for the arcs.
2.722 ///
2.723 - /// Reference map of the arcs to type \c T.
2.724 + /// Standard graph map type for the arcs.
2.725 + /// It conforms to the ReferenceMap concept.
2.726 template<class T>
2.727 class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
2.728 {
2.729 public:
2.730
2.731 - ///\e
2.732 - ArcMap(const Graph&) { }
2.733 - ///\e
2.734 + /// Constructor
2.735 + explicit ArcMap(const Graph&) { }
2.736 + /// Constructor with given initial value
2.737 ArcMap(const Graph&, T) { }
2.738 +
2.739 private:
2.740 ///Copy constructor
2.741 ArcMap(const ArcMap& em) :
2.742 @@ -548,18 +557,20 @@
2.743 }
2.744 };
2.745
2.746 - /// Reference map of the edges to type \c T.
2.747 -
2.748 - /// Reference map of the edges to type \c T.
2.749 + /// \brief Standard graph map type for the edges.
2.750 + ///
2.751 + /// Standard graph map type for the edges.
2.752 + /// It conforms to the ReferenceMap concept.
2.753 template<class T>
2.754 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
2.755 {
2.756 public:
2.757
2.758 - ///\e
2.759 - EdgeMap(const Graph&) { }
2.760 - ///\e
2.761 + /// Constructor
2.762 + explicit EdgeMap(const Graph&) { }
2.763 + /// Constructor with given initial value
2.764 EdgeMap(const Graph&, T) { }
2.765 +
2.766 private:
2.767 ///Copy constructor
2.768 EdgeMap(const EdgeMap& em) :
2.769 @@ -572,107 +583,124 @@
2.770 }
2.771 };
2.772
2.773 - /// \brief Direct the given edge.
2.774 + /// \brief The first node of the edge.
2.775 ///
2.776 - /// Direct the given edge. The returned arc source
2.777 - /// will be the given node.
2.778 - Arc direct(const Edge&, const Node&) const {
2.779 - return INVALID;
2.780 - }
2.781 -
2.782 - /// \brief Direct the given edge.
2.783 + /// Returns the first node of the given edge.
2.784 ///
2.785 - /// Direct the given edge. The returned arc
2.786 - /// represents the given edge and the direction comes
2.787 - /// from the bool parameter. The source of the edge and
2.788 - /// the directed arc is the same when the given bool is true.
2.789 - Arc direct(const Edge&, bool) const {
2.790 - return INVALID;
2.791 - }
2.792 -
2.793 - /// \brief Returns true if the arc has default orientation.
2.794 - ///
2.795 - /// Returns whether the given directed arc is same orientation as
2.796 - /// the corresponding edge's default orientation.
2.797 - bool direction(Arc) const { return true; }
2.798 -
2.799 - /// \brief Returns the opposite directed arc.
2.800 - ///
2.801 - /// Returns the opposite directed arc.
2.802 - Arc oppositeArc(Arc) const { return INVALID; }
2.803 -
2.804 - /// \brief Opposite node on an arc
2.805 - ///
2.806 - /// \return The opposite of the given node on the given edge.
2.807 - Node oppositeNode(Node, Edge) const { return INVALID; }
2.808 -
2.809 - /// \brief First node of the edge.
2.810 - ///
2.811 - /// \return The first node of the given edge.
2.812 - ///
2.813 - /// Naturally edges don't have direction and thus
2.814 - /// don't have source and target node. However we use \c u() and \c v()
2.815 - /// methods to query the two nodes of the arc. The direction of the
2.816 - /// arc which arises this way is called the inherent direction of the
2.817 - /// edge, and is used to define the "default" direction
2.818 - /// of the directed versions of the arcs.
2.819 + /// Edges don't have source and target nodes, however methods
2.820 + /// u() and v() are used to query the two end-nodes of an edge.
2.821 + /// The orientation of an edge that arises this way is called
2.822 + /// the inherent direction, it is used to define the default
2.823 + /// direction for the corresponding arcs.
2.824 /// \sa v()
2.825 /// \sa direction()
2.826 Node u(Edge) const { return INVALID; }
2.827
2.828 - /// \brief Second node of the edge.
2.829 + /// \brief The second node of the edge.
2.830 ///
2.831 - /// \return The second node of the given edge.
2.832 + /// Returns the second node of the given edge.
2.833 ///
2.834 - /// Naturally edges don't have direction and thus
2.835 - /// don't have source and target node. However we use \c u() and \c v()
2.836 - /// methods to query the two nodes of the arc. The direction of the
2.837 - /// arc which arises this way is called the inherent direction of the
2.838 - /// edge, and is used to define the "default" direction
2.839 - /// of the directed versions of the arcs.
2.840 + /// Edges don't have source and target nodes, however methods
2.841 + /// u() and v() are used to query the two end-nodes of an edge.
2.842 + /// The orientation of an edge that arises this way is called
2.843 + /// the inherent direction, it is used to define the default
2.844 + /// direction for the corresponding arcs.
2.845 /// \sa u()
2.846 /// \sa direction()
2.847 Node v(Edge) const { return INVALID; }
2.848
2.849 - /// \brief Source node of the directed arc.
2.850 + /// \brief The source node of the arc.
2.851 + ///
2.852 + /// Returns the source node of the given arc.
2.853 Node source(Arc) const { return INVALID; }
2.854
2.855 - /// \brief Target node of the directed arc.
2.856 + /// \brief The target node of the arc.
2.857 + ///
2.858 + /// Returns the target node of the given arc.
2.859 Node target(Arc) const { return INVALID; }
2.860
2.861 - /// \brief Returns the id of the node.
2.862 + /// \brief The ID of the node.
2.863 + ///
2.864 + /// Returns the ID of the given node.
2.865 int id(Node) const { return -1; }
2.866
2.867 - /// \brief Returns the id of the edge.
2.868 + /// \brief The ID of the edge.
2.869 + ///
2.870 + /// Returns the ID of the given edge.
2.871 int id(Edge) const { return -1; }
2.872
2.873 - /// \brief Returns the id of the arc.
2.874 + /// \brief The ID of the arc.
2.875 + ///
2.876 + /// Returns the ID of the given arc.
2.877 int id(Arc) const { return -1; }
2.878
2.879 - /// \brief Returns the node with the given id.
2.880 + /// \brief The node with the given ID.
2.881 ///
2.882 - /// \pre The argument should be a valid node id in the graph.
2.883 + /// Returns the node with the given ID.
2.884 + /// \pre The argument should be a valid node ID in the graph.
2.885 Node nodeFromId(int) const { return INVALID; }
2.886
2.887 - /// \brief Returns the edge with the given id.
2.888 + /// \brief The edge with the given ID.
2.889 ///
2.890 - /// \pre The argument should be a valid edge id in the graph.
2.891 + /// Returns the edge with the given ID.
2.892 + /// \pre The argument should be a valid edge ID in the graph.
2.893 Edge edgeFromId(int) const { return INVALID; }
2.894
2.895 - /// \brief Returns the arc with the given id.
2.896 + /// \brief The arc with the given ID.
2.897 ///
2.898 - /// \pre The argument should be a valid arc id in the graph.
2.899 + /// Returns the arc with the given ID.
2.900 + /// \pre The argument should be a valid arc ID in the graph.
2.901 Arc arcFromId(int) const { return INVALID; }
2.902
2.903 - /// \brief Returns an upper bound on the node IDs.
2.904 + /// \brief An upper bound on the node IDs.
2.905 + ///
2.906 + /// Returns an upper bound on the node IDs.
2.907 int maxNodeId() const { return -1; }
2.908
2.909 - /// \brief Returns an upper bound on the edge IDs.
2.910 + /// \brief An upper bound on the edge IDs.
2.911 + ///
2.912 + /// Returns an upper bound on the edge IDs.
2.913 int maxEdgeId() const { return -1; }
2.914
2.915 - /// \brief Returns an upper bound on the arc IDs.
2.916 + /// \brief An upper bound on the arc IDs.
2.917 + ///
2.918 + /// Returns an upper bound on the arc IDs.
2.919 int maxArcId() const { return -1; }
2.920
2.921 + /// \brief The direction of the arc.
2.922 + ///
2.923 + /// Returns \c true if the direction of the given arc is the same as
2.924 + /// the inherent orientation of the represented edge.
2.925 + bool direction(Arc) const { return true; }
2.926 +
2.927 + /// \brief Direct the edge.
2.928 + ///
2.929 + /// Direct the given edge. The returned arc
2.930 + /// represents the given edge and its direction comes
2.931 + /// from the bool parameter. If it is \c true, then the direction
2.932 + /// of the arc is the same as the inherent orientation of the edge.
2.933 + Arc direct(Edge, bool) const {
2.934 + return INVALID;
2.935 + }
2.936 +
2.937 + /// \brief Direct the edge.
2.938 + ///
2.939 + /// Direct the given edge. The returned arc represents the given
2.940 + /// edge and its source node is the given node.
2.941 + Arc direct(Edge, Node) const {
2.942 + return INVALID;
2.943 + }
2.944 +
2.945 + /// \brief The oppositely directed arc.
2.946 + ///
2.947 + /// Returns the oppositely directed arc representing the same edge.
2.948 + Arc oppositeArc(Arc) const { return INVALID; }
2.949 +
2.950 + /// \brief The opposite node on the edge.
2.951 + ///
2.952 + /// Returns the opposite node on the given edge.
2.953 + Node oppositeNode(Node, Edge) const { return INVALID; }
2.954 +
2.955 void first(Node&) const {}
2.956 void next(Node&) const {}
2.957
2.958 @@ -705,47 +733,39 @@
2.959 // Dummy parameter.
2.960 int maxId(Arc) const { return -1; }
2.961
2.962 - /// \brief Base node of the iterator
2.963 + /// \brief The base node of the iterator.
2.964 ///
2.965 - /// Returns the base node (the source in this case) of the iterator
2.966 - Node baseNode(OutArcIt e) const {
2.967 - return source(e);
2.968 - }
2.969 - /// \brief Running node of the iterator
2.970 + /// Returns the base node of the given incident edge iterator.
2.971 + Node baseNode(IncEdgeIt) const { return INVALID; }
2.972 +
2.973 + /// \brief The running node of the iterator.
2.974 ///
2.975 - /// Returns the running node (the target in this case) of the
2.976 - /// iterator
2.977 - Node runningNode(OutArcIt e) const {
2.978 - return target(e);
2.979 - }
2.980 + /// Returns the running node of the given incident edge iterator.
2.981 + Node runningNode(IncEdgeIt) const { return INVALID; }
2.982
2.983 - /// \brief Base node of the iterator
2.984 + /// \brief The base node of the iterator.
2.985 ///
2.986 - /// Returns the base node (the target in this case) of the iterator
2.987 - Node baseNode(InArcIt e) const {
2.988 - return target(e);
2.989 - }
2.990 - /// \brief Running node of the iterator
2.991 + /// Returns the base node of the given outgoing arc iterator
2.992 + /// (i.e. the source node of the corresponding arc).
2.993 + Node baseNode(OutArcIt) const { return INVALID; }
2.994 +
2.995 + /// \brief The running node of the iterator.
2.996 ///
2.997 - /// Returns the running node (the source in this case) of the
2.998 - /// iterator
2.999 - Node runningNode(InArcIt e) const {
2.1000 - return source(e);
2.1001 - }
2.1002 + /// Returns the running node of the given outgoing arc iterator
2.1003 + /// (i.e. the target node of the corresponding arc).
2.1004 + Node runningNode(OutArcIt) const { return INVALID; }
2.1005
2.1006 - /// \brief Base node of the iterator
2.1007 + /// \brief The base node of the iterator.
2.1008 ///
2.1009 - /// Returns the base node of the iterator
2.1010 - Node baseNode(IncEdgeIt) const {
2.1011 - return INVALID;
2.1012 - }
2.1013 + /// Returns the base node of the given incomming arc iterator
2.1014 + /// (i.e. the target node of the corresponding arc).
2.1015 + Node baseNode(InArcIt) const { return INVALID; }
2.1016
2.1017 - /// \brief Running node of the iterator
2.1018 + /// \brief The running node of the iterator.
2.1019 ///
2.1020 - /// Returns the running node of the iterator
2.1021 - Node runningNode(IncEdgeIt) const {
2.1022 - return INVALID;
2.1023 - }
2.1024 + /// Returns the running node of the given incomming arc iterator
2.1025 + /// (i.e. the source node of the corresponding arc).
2.1026 + Node runningNode(InArcIt) const { return INVALID; }
2.1027
2.1028 template <typename _Graph>
2.1029 struct Constraints {
3.1 --- a/lemon/concepts/graph_components.h Thu Aug 20 22:52:16 2009 +0200
3.2 +++ b/lemon/concepts/graph_components.h Sun Aug 23 11:07:50 2009 +0200
3.3 @@ -92,7 +92,7 @@
3.4 /// It makes possible to use graph item types as key types in
3.5 /// associative containers (e.g. \c std::map).
3.6 ///
3.7 - /// \note This operator only have to define some strict ordering of
3.8 + /// \note This operator only has to define some strict ordering of
3.9 /// the items; this order has nothing to do with the iteration
3.10 /// ordering of the items.
3.11 bool operator<(const GraphItem&) const { return false; }