1.1 --- a/lemon/concepts/digraph.h Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/lemon/concepts/digraph.h Wed Dec 09 11:14:06 2009 +0100
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 - /// Its usage is quite simple, for example you can count the number
1.119 - /// of nodes in digraph \c g of type \c Digraph like this:
1.120 + /// This iterator goes through each node of the digraph.
1.121 + /// Its usage is quite simple, for example, you can count the number
1.122 + /// of nodes in a digraph \c g of type \c %Digraph like this:
1.123 ///\code
1.124 /// int count=0;
1.125 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.126 @@ -124,30 +117,28 @@
1.127 public:
1.128 /// Default constructor
1.129
1.130 - /// @warning The default constructor sets the iterator
1.131 - /// to an undefined value.
1.132 + /// Default constructor.
1.133 + /// \warning It sets the iterator to an undefined value.
1.134 NodeIt() { }
1.135 /// Copy constructor.
1.136
1.137 /// Copy constructor.
1.138 ///
1.139 NodeIt(const NodeIt& n) : Node(n) { }
1.140 - /// Invalid constructor \& conversion.
1.141 + /// %Invalid constructor \& conversion.
1.142
1.143 - /// Initialize the iterator to be invalid.
1.144 + /// Initializes the iterator to be invalid.
1.145 /// \sa Invalid for more details.
1.146 NodeIt(Invalid) { }
1.147 /// Sets the iterator to the first node.
1.148
1.149 - /// Sets the iterator to the first node of \c g.
1.150 + /// Sets the iterator to the first node of the given digraph.
1.151 ///
1.152 - NodeIt(const Digraph&) { }
1.153 - /// Node -> NodeIt conversion.
1.154 + explicit NodeIt(const Digraph&) { }
1.155 + /// Sets the iterator to the given node.
1.156
1.157 - /// Sets the iterator to the node of \c the digraph pointed by
1.158 - /// the trivial iterator.
1.159 - /// This feature necessitates that each time we
1.160 - /// iterate the arc-set, the iteration order is the same.
1.161 + /// Sets the iterator to the given node of the given digraph.
1.162 + ///
1.163 NodeIt(const Digraph&, const Node&) { }
1.164 /// Next node.
1.165
1.166 @@ -157,7 +148,7 @@
1.167 };
1.168
1.169
1.170 - /// Class for identifying an arc of the digraph
1.171 + /// The arc type of the digraph
1.172
1.173 /// This class identifies an arc of the digraph. It also serves
1.174 /// as a base class of the arc iterators,
1.175 @@ -166,207 +157,214 @@
1.176 public:
1.177 /// Default constructor
1.178
1.179 - /// @warning The default constructor sets the iterator
1.180 - /// to an undefined value.
1.181 + /// Default constructor.
1.182 + /// \warning It sets the object to an undefined value.
1.183 Arc() { }
1.184 /// Copy constructor.
1.185
1.186 /// Copy constructor.
1.187 ///
1.188 Arc(const Arc&) { }
1.189 - /// Initialize the iterator to be invalid.
1.190 + /// %Invalid constructor \& conversion.
1.191
1.192 - /// Initialize the iterator to be invalid.
1.193 - ///
1.194 + /// Initializes the object to be invalid.
1.195 + /// \sa Invalid for more details.
1.196 Arc(Invalid) { }
1.197 /// Equality operator
1.198
1.199 + /// Equality operator.
1.200 + ///
1.201 /// Two iterators are equal if and only if they point to the
1.202 - /// same object or both are invalid.
1.203 + /// same object or both are \c INVALID.
1.204 bool operator==(Arc) const { return true; }
1.205 /// Inequality operator
1.206
1.207 - /// \sa operator==(Arc n)
1.208 - ///
1.209 + /// Inequality operator.
1.210 bool operator!=(Arc) const { return true; }
1.211
1.212 /// Artificial ordering operator.
1.213
1.214 - /// To allow the use of digraph descriptors as key type in std::map or
1.215 - /// similar associative container we require this.
1.216 + /// Artificial ordering operator.
1.217 ///
1.218 - /// \note This operator only have to define some strict ordering of
1.219 - /// the items; this order has nothing to do with the iteration
1.220 - /// ordering of the items.
1.221 + /// \note This operator only has to define some strict ordering of
1.222 + /// the arcs; this order has nothing to do with the iteration
1.223 + /// ordering of the arcs.
1.224 bool operator<(Arc) const { return false; }
1.225 };
1.226
1.227 - /// This iterator goes trough the outgoing arcs of a node.
1.228 + /// Iterator class for the outgoing arcs of a node.
1.229
1.230 /// This iterator goes trough the \e outgoing arcs of a certain node
1.231 /// of a digraph.
1.232 - /// Its usage is quite simple, for example you can count the number
1.233 + /// Its usage is quite simple, for example, you can count the number
1.234 /// of outgoing arcs of a node \c n
1.235 - /// in digraph \c g of type \c Digraph as follows.
1.236 + /// in a digraph \c g of type \c %Digraph as follows.
1.237 ///\code
1.238 /// int count=0;
1.239 - /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
1.240 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.241 ///\endcode
1.242 -
1.243 class OutArcIt : public Arc {
1.244 public:
1.245 /// Default constructor
1.246
1.247 - /// @warning The default constructor sets the iterator
1.248 - /// to an undefined value.
1.249 + /// Default constructor.
1.250 + /// \warning It sets the iterator to an undefined value.
1.251 OutArcIt() { }
1.252 /// Copy constructor.
1.253
1.254 /// Copy constructor.
1.255 ///
1.256 OutArcIt(const OutArcIt& e) : Arc(e) { }
1.257 - /// Initialize the iterator to be invalid.
1.258 + /// %Invalid constructor \& conversion.
1.259
1.260 - /// Initialize the iterator to be invalid.
1.261 + /// Initializes the iterator to be invalid.
1.262 + /// \sa Invalid for more details.
1.263 + OutArcIt(Invalid) { }
1.264 + /// Sets the iterator to the first outgoing arc.
1.265 +
1.266 + /// Sets the iterator to the first outgoing arc of the given node.
1.267 ///
1.268 - OutArcIt(Invalid) { }
1.269 - /// This constructor sets the iterator to the first outgoing arc.
1.270 + OutArcIt(const Digraph&, const Node&) { }
1.271 + /// Sets the iterator to the given arc.
1.272
1.273 - /// This constructor sets the iterator to the first outgoing arc of
1.274 - /// the node.
1.275 - OutArcIt(const Digraph&, const Node&) { }
1.276 - /// Arc -> OutArcIt conversion
1.277 -
1.278 - /// Sets the iterator to the value of the trivial iterator.
1.279 - /// This feature necessitates that each time we
1.280 - /// iterate the arc-set, the iteration order is the same.
1.281 + /// Sets the iterator to the given arc of the given digraph.
1.282 + ///
1.283 OutArcIt(const Digraph&, const Arc&) { }
1.284 - ///Next outgoing arc
1.285 + /// Next outgoing arc
1.286
1.287 /// Assign the iterator to the next
1.288 /// outgoing arc of the corresponding node.
1.289 OutArcIt& operator++() { return *this; }
1.290 };
1.291
1.292 - /// This iterator goes trough the incoming arcs of a node.
1.293 + /// Iterator class for the incoming arcs of a node.
1.294
1.295 /// This iterator goes trough the \e incoming arcs of a certain node
1.296 /// of a digraph.
1.297 - /// Its usage is quite simple, for example you can count the number
1.298 - /// of outgoing arcs of a node \c n
1.299 - /// in digraph \c g of type \c Digraph as follows.
1.300 + /// Its usage is quite simple, for example, you can count the number
1.301 + /// of incoming arcs of a node \c n
1.302 + /// in a digraph \c g of type \c %Digraph as follows.
1.303 ///\code
1.304 /// int count=0;
1.305 - /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
1.306 + /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.307 ///\endcode
1.308 -
1.309 class InArcIt : public Arc {
1.310 public:
1.311 /// Default constructor
1.312
1.313 - /// @warning The default constructor sets the iterator
1.314 - /// to an undefined value.
1.315 + /// Default constructor.
1.316 + /// \warning It sets the iterator to an undefined value.
1.317 InArcIt() { }
1.318 /// Copy constructor.
1.319
1.320 /// Copy constructor.
1.321 ///
1.322 InArcIt(const InArcIt& e) : Arc(e) { }
1.323 - /// Initialize the iterator to be invalid.
1.324 + /// %Invalid constructor \& conversion.
1.325
1.326 - /// Initialize the iterator to be invalid.
1.327 + /// Initializes the iterator to be invalid.
1.328 + /// \sa Invalid for more details.
1.329 + InArcIt(Invalid) { }
1.330 + /// Sets the iterator to the first incoming arc.
1.331 +
1.332 + /// Sets the iterator to the first incoming arc of the given node.
1.333 ///
1.334 - InArcIt(Invalid) { }
1.335 - /// This constructor sets the iterator to first incoming arc.
1.336 + InArcIt(const Digraph&, const Node&) { }
1.337 + /// Sets the iterator to the given arc.
1.338
1.339 - /// This constructor set the iterator to the first incoming arc of
1.340 - /// the node.
1.341 - InArcIt(const Digraph&, const Node&) { }
1.342 - /// Arc -> InArcIt conversion
1.343 -
1.344 - /// Sets the iterator to the value of the trivial iterator \c e.
1.345 - /// This feature necessitates that each time we
1.346 - /// iterate the arc-set, the iteration order is the same.
1.347 + /// Sets the iterator to the given arc of the given digraph.
1.348 + ///
1.349 InArcIt(const Digraph&, const Arc&) { }
1.350 /// Next incoming arc
1.351
1.352 - /// Assign the iterator to the next inarc of the corresponding node.
1.353 - ///
1.354 + /// Assign the iterator to the next
1.355 + /// incoming arc of the corresponding node.
1.356 InArcIt& operator++() { return *this; }
1.357 };
1.358 - /// This iterator goes through each arc.
1.359
1.360 - /// This iterator goes through each arc of a 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 + /// Iterator class for the arcs.
1.364 +
1.365 + /// This iterator goes through each arc of the digraph.
1.366 + /// Its usage is quite simple, for example, you can count the number
1.367 + /// of arcs in a digraph \c g of type \c %Digraph as follows:
1.368 ///\code
1.369 /// int count=0;
1.370 - /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
1.371 + /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.372 ///\endcode
1.373 class ArcIt : public Arc {
1.374 public:
1.375 /// Default constructor
1.376
1.377 - /// @warning The default constructor sets the iterator
1.378 - /// to an undefined value.
1.379 + /// Default constructor.
1.380 + /// \warning It sets the iterator to an undefined value.
1.381 ArcIt() { }
1.382 /// Copy constructor.
1.383
1.384 /// Copy constructor.
1.385 ///
1.386 ArcIt(const ArcIt& e) : Arc(e) { }
1.387 - /// Initialize the iterator to be invalid.
1.388 + /// %Invalid constructor \& conversion.
1.389
1.390 - /// Initialize the iterator to be invalid.
1.391 + /// Initializes the iterator to be invalid.
1.392 + /// \sa Invalid for more details.
1.393 + ArcIt(Invalid) { }
1.394 + /// Sets the iterator to the first arc.
1.395 +
1.396 + /// Sets the iterator to the first arc of the given digraph.
1.397 ///
1.398 - ArcIt(Invalid) { }
1.399 - /// This constructor sets the iterator to the first arc.
1.400 + explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.401 + /// Sets the iterator to the given arc.
1.402
1.403 - /// This constructor sets the iterator to the first arc of \c g.
1.404 - ///@param g the digraph
1.405 - ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.406 - /// Arc -> ArcIt conversion
1.407 -
1.408 - /// Sets the iterator to the value of the trivial iterator \c e.
1.409 - /// This feature necessitates that each time we
1.410 - /// iterate the arc-set, the iteration order is the same.
1.411 + /// Sets the iterator to the given arc of the given digraph.
1.412 + ///
1.413 ArcIt(const Digraph&, const Arc&) { }
1.414 - ///Next arc
1.415 + /// Next arc
1.416
1.417 /// Assign the iterator to the next arc.
1.418 + ///
1.419 ArcIt& operator++() { return *this; }
1.420 };
1.421 - ///Gives back the target node of an arc.
1.422
1.423 - ///Gives back the target node of an arc.
1.424 + /// \brief The source node of the arc.
1.425 ///
1.426 - Node target(Arc) const { return INVALID; }
1.427 - ///Gives back the source node of an arc.
1.428 -
1.429 - ///Gives back the source node of an arc.
1.430 - ///
1.431 + /// Returns the source node of the given arc.
1.432 Node source(Arc) const { return INVALID; }
1.433
1.434 - /// \brief Returns the ID of the node.
1.435 + /// \brief The target node of the arc.
1.436 + ///
1.437 + /// Returns the target node of the given arc.
1.438 + Node target(Arc) const { return INVALID; }
1.439 +
1.440 + /// \brief The ID of the node.
1.441 + ///
1.442 + /// Returns the ID of the given node.
1.443 int id(Node) const { return -1; }
1.444
1.445 - /// \brief Returns the ID of the arc.
1.446 + /// \brief The ID of the arc.
1.447 + ///
1.448 + /// Returns the ID of the given arc.
1.449 int id(Arc) const { return -1; }
1.450
1.451 - /// \brief Returns the node with the given ID.
1.452 + /// \brief The node with the given ID.
1.453 ///
1.454 - /// \pre The argument should be a valid node ID in the graph.
1.455 + /// Returns the node with the given ID.
1.456 + /// \pre The argument should be a valid node ID in the digraph.
1.457 Node nodeFromId(int) const { return INVALID; }
1.458
1.459 - /// \brief Returns the arc with the given ID.
1.460 + /// \brief The arc with the given ID.
1.461 ///
1.462 - /// \pre The argument should be a valid arc ID in the graph.
1.463 + /// Returns the arc with the given ID.
1.464 + /// \pre The argument should be a valid arc ID in the digraph.
1.465 Arc arcFromId(int) const { return INVALID; }
1.466
1.467 - /// \brief Returns an upper bound on the node IDs.
1.468 + /// \brief An upper bound on the node IDs.
1.469 + ///
1.470 + /// Returns an upper bound on the node IDs.
1.471 int maxNodeId() const { return -1; }
1.472
1.473 - /// \brief Returns an upper bound on the arc IDs.
1.474 + /// \brief An upper bound on the arc IDs.
1.475 + ///
1.476 + /// Returns an upper bound on the arc IDs.
1.477 int maxArcId() const { return -1; }
1.478
1.479 void first(Node&) const {}
1.480 @@ -392,45 +390,46 @@
1.481 // Dummy parameter.
1.482 int maxId(Arc) const { return -1; }
1.483
1.484 + /// \brief The opposite node on the arc.
1.485 + ///
1.486 + /// Returns the opposite node on the given arc.
1.487 + Node oppositeNode(Node, Arc) const { return INVALID; }
1.488 +
1.489 /// \brief The base node of the iterator.
1.490 ///
1.491 - /// Gives back the base node of the iterator.
1.492 - /// It is always the target of the pointed arc.
1.493 - Node baseNode(const InArcIt&) const { return INVALID; }
1.494 + /// Returns the base node of the given outgoing arc iterator
1.495 + /// (i.e. the source node of the corresponding arc).
1.496 + Node baseNode(OutArcIt) const { return INVALID; }
1.497
1.498 /// \brief The running node of the iterator.
1.499 ///
1.500 - /// Gives back the running node of the iterator.
1.501 - /// It is always the source of the pointed arc.
1.502 - Node runningNode(const InArcIt&) const { return INVALID; }
1.503 + /// Returns the running node of the given outgoing arc iterator
1.504 + /// (i.e. the target node of the corresponding arc).
1.505 + Node runningNode(OutArcIt) const { return INVALID; }
1.506
1.507 /// \brief The base node of the iterator.
1.508 ///
1.509 - /// Gives back the base node of the iterator.
1.510 - /// It is always the source of the pointed arc.
1.511 - Node baseNode(const OutArcIt&) const { return INVALID; }
1.512 + /// Returns the base node of the given incomming arc iterator
1.513 + /// (i.e. the target node of the corresponding arc).
1.514 + Node baseNode(InArcIt) const { return INVALID; }
1.515
1.516 /// \brief The running node of the iterator.
1.517 ///
1.518 - /// Gives back the running node of the iterator.
1.519 - /// It is always the target of the pointed arc.
1.520 - Node runningNode(const OutArcIt&) const { return INVALID; }
1.521 + /// Returns the running node of the given incomming arc iterator
1.522 + /// (i.e. the source node of the corresponding arc).
1.523 + Node runningNode(InArcIt) const { return INVALID; }
1.524
1.525 - /// \brief The opposite node on the given arc.
1.526 + /// \brief Standard graph map type for the nodes.
1.527 ///
1.528 - /// Gives back the opposite node on the given arc.
1.529 - Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
1.530 -
1.531 - /// \brief Reference map of the nodes to type \c T.
1.532 - ///
1.533 - /// Reference map of the nodes to type \c T.
1.534 + /// Standard graph map type for the nodes.
1.535 + /// It conforms to the ReferenceMap concept.
1.536 template<class T>
1.537 class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
1.538 public:
1.539
1.540 - ///\e
1.541 - NodeMap(const Digraph&) { }
1.542 - ///\e
1.543 + /// Constructor
1.544 + explicit NodeMap(const Digraph&) { }
1.545 + /// Constructor with given initial value
1.546 NodeMap(const Digraph&, T) { }
1.547
1.548 private:
1.549 @@ -445,17 +444,19 @@
1.550 }
1.551 };
1.552
1.553 - /// \brief Reference map of the arcs to type \c T.
1.554 + /// \brief Standard graph map type for the arcs.
1.555 ///
1.556 - /// Reference map of the arcs to type \c T.
1.557 + /// Standard graph map type for the arcs.
1.558 + /// It conforms to the ReferenceMap concept.
1.559 template<class T>
1.560 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
1.561 public:
1.562
1.563 - ///\e
1.564 - ArcMap(const Digraph&) { }
1.565 - ///\e
1.566 + /// Constructor
1.567 + explicit ArcMap(const Digraph&) { }
1.568 + /// Constructor with given initial value
1.569 ArcMap(const Digraph&, T) { }
1.570 +
1.571 private:
1.572 ///Copy constructor
1.573 ArcMap(const ArcMap& em) :