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) :