1.1 --- a/lemon/concepts/digraph.h Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/lemon/concepts/digraph.h Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -35,46 +35,40 @@
1.13 ///
1.14 /// \brief Class describing the concept of directed graphs.
1.15 ///
1.16 - /// This class describes the \ref concept "concept" of the
1.17 - /// immutable directed digraphs.
1.18 + /// This class describes the common interface of all directed
1.19 + /// graphs (digraphs).
1.20 ///
1.21 - /// Note that actual digraph implementation like @ref ListDigraph or
1.22 - /// @ref SmartDigraph may have several additional functionality.
1.23 + /// Like all concept classes, it only provides an interface
1.24 + /// without any sensible implementation. So any general algorithm for
1.25 + /// directed graphs should compile with this class, but it will not
1.26 + /// run properly, of course.
1.27 + /// An actual digraph implementation like \ref ListDigraph or
1.28 + /// \ref SmartDigraph may have additional functionality.
1.29 ///
1.30 - /// \sa concept
1.31 + /// \sa Graph
1.32 class Digraph {
1.33 private:
1.34 - ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
1.35 + /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
1.36 + Digraph(const Digraph &) {}
1.37 + /// \brief Assignment of a digraph to another one is \e not allowed.
1.38 + /// Use DigraphCopy instead.
1.39 + void operator=(const Digraph &) {}
1.40
1.41 - ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
1.42 - ///
1.43 - Digraph(const Digraph &) {};
1.44 - ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
1.45 - ///\e not allowed. Use DigraphCopy() instead.
1.46 + public:
1.47 + /// Default constructor.
1.48 + Digraph() { }
1.49
1.50 - ///Assignment of \ref Digraph "Digraph"s to another ones are
1.51 - ///\e not allowed. Use DigraphCopy() instead.
1.52 -
1.53 - void operator=(const Digraph &) {}
1.54 - public:
1.55 - ///\e
1.56 -
1.57 - /// Defalult constructor.
1.58 -
1.59 - /// Defalult constructor.
1.60 - ///
1.61 - Digraph() { }
1.62 - /// Class for identifying a node of the digraph
1.63 + /// The node type of the digraph
1.64
1.65 /// This class identifies a node of the digraph. It also serves
1.66 /// as a base class of the node iterators,
1.67 - /// thus they will convert to this type.
1.68 + /// thus they convert to this type.
1.69 class Node {
1.70 public:
1.71 /// Default constructor
1.72
1.73 - /// @warning The default constructor sets the iterator
1.74 - /// to an undefined value.
1.75 + /// Default constructor.
1.76 + /// \warning It sets the object to an undefined value.
1.77 Node() { }
1.78 /// Copy constructor.
1.79
1.80 @@ -82,40 +76,39 @@
1.81 ///
1.82 Node(const Node&) { }
1.83
1.84 - /// Invalid constructor \& conversion.
1.85 + /// %Invalid constructor \& conversion.
1.86
1.87 - /// This constructor initializes the iterator to be invalid.
1.88 + /// Initializes the object to be invalid.
1.89 /// \sa Invalid for more details.
1.90 Node(Invalid) { }
1.91 /// Equality operator
1.92
1.93 + /// Equality operator.
1.94 + ///
1.95 /// Two iterators are equal if and only if they point to the
1.96 - /// same object or both are invalid.
1.97 + /// same object or both are \c INVALID.
1.98 bool operator==(Node) const { return true; }
1.99
1.100 /// Inequality operator
1.101
1.102 - /// \sa operator==(Node n)
1.103 - ///
1.104 + /// Inequality operator.
1.105 bool operator!=(Node) const { return true; }
1.106
1.107 /// Artificial ordering operator.
1.108
1.109 - /// To allow the use of digraph descriptors as key type in std::map or
1.110 - /// similar associative container we require this.
1.111 + /// Artificial ordering operator.
1.112 ///
1.113 - /// \note This operator only have to define some strict ordering of
1.114 - /// the items; this order has nothing to do with the iteration
1.115 - /// ordering of the items.
1.116 + /// \note This operator only has to define some strict ordering of
1.117 + /// the nodes; this order has nothing to do with the iteration
1.118 + /// ordering of the nodes.
1.119 bool operator<(Node) const { return false; }
1.120 -
1.121 };
1.122
1.123 - /// This iterator goes through each node.
1.124 + /// Iterator class for the nodes.
1.125
1.126 - /// This iterator goes through each node.
1.127 - /// Its usage is quite simple, for example you can count the number
1.128 - /// of nodes in digraph \c g of type \c Digraph like this:
1.129 + /// This iterator goes through each node of the digraph.
1.130 + /// Its usage is quite simple, for example, you can count the number
1.131 + /// of nodes in a digraph \c g of type \c %Digraph like this:
1.132 ///\code
1.133 /// int count=0;
1.134 /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.135 @@ -124,30 +117,28 @@
1.136 public:
1.137 /// Default constructor
1.138
1.139 - /// @warning The default constructor sets the iterator
1.140 - /// to an undefined value.
1.141 + /// Default constructor.
1.142 + /// \warning It sets the iterator to an undefined value.
1.143 NodeIt() { }
1.144 /// Copy constructor.
1.145
1.146 /// Copy constructor.
1.147 ///
1.148 NodeIt(const NodeIt& n) : Node(n) { }
1.149 - /// Invalid constructor \& conversion.
1.150 + /// %Invalid constructor \& conversion.
1.151
1.152 - /// Initialize the iterator to be invalid.
1.153 + /// Initializes the iterator to be invalid.
1.154 /// \sa Invalid for more details.
1.155 NodeIt(Invalid) { }
1.156 /// Sets the iterator to the first node.
1.157
1.158 - /// Sets the iterator to the first node of \c g.
1.159 + /// Sets the iterator to the first node of the given digraph.
1.160 ///
1.161 - NodeIt(const Digraph&) { }
1.162 - /// Node -> NodeIt conversion.
1.163 + explicit NodeIt(const Digraph&) { }
1.164 + /// Sets the iterator to the given node.
1.165
1.166 - /// Sets the iterator to the node of \c the digraph pointed by
1.167 - /// the trivial iterator.
1.168 - /// This feature necessitates that each time we
1.169 - /// iterate the arc-set, the iteration order is the same.
1.170 + /// Sets the iterator to the given node of the given digraph.
1.171 + ///
1.172 NodeIt(const Digraph&, const Node&) { }
1.173 /// Next node.
1.174
1.175 @@ -157,7 +148,7 @@
1.176 };
1.177
1.178
1.179 - /// Class for identifying an arc of the digraph
1.180 + /// The arc type of the digraph
1.181
1.182 /// This class identifies an arc of the digraph. It also serves
1.183 /// as a base class of the arc iterators,
1.184 @@ -166,207 +157,214 @@
1.185 public:
1.186 /// Default constructor
1.187
1.188 - /// @warning The default constructor sets the iterator
1.189 - /// to an undefined value.
1.190 + /// Default constructor.
1.191 + /// \warning It sets the object to an undefined value.
1.192 Arc() { }
1.193 /// Copy constructor.
1.194
1.195 /// Copy constructor.
1.196 ///
1.197 Arc(const Arc&) { }
1.198 - /// Initialize the iterator to be invalid.
1.199 + /// %Invalid constructor \& conversion.
1.200
1.201 - /// Initialize the iterator to be invalid.
1.202 - ///
1.203 + /// Initializes the object to be invalid.
1.204 + /// \sa Invalid for more details.
1.205 Arc(Invalid) { }
1.206 /// Equality operator
1.207
1.208 + /// Equality operator.
1.209 + ///
1.210 /// Two iterators are equal if and only if they point to the
1.211 - /// same object or both are invalid.
1.212 + /// same object or both are \c INVALID.
1.213 bool operator==(Arc) const { return true; }
1.214 /// Inequality operator
1.215
1.216 - /// \sa operator==(Arc n)
1.217 - ///
1.218 + /// Inequality operator.
1.219 bool operator!=(Arc) const { return true; }
1.220
1.221 /// Artificial ordering operator.
1.222
1.223 - /// To allow the use of digraph descriptors as key type in std::map or
1.224 - /// similar associative container we require this.
1.225 + /// Artificial ordering operator.
1.226 ///
1.227 - /// \note This operator only have to define some strict ordering of
1.228 - /// the items; this order has nothing to do with the iteration
1.229 - /// ordering of the items.
1.230 + /// \note This operator only has to define some strict ordering of
1.231 + /// the arcs; this order has nothing to do with the iteration
1.232 + /// ordering of the arcs.
1.233 bool operator<(Arc) const { return false; }
1.234 };
1.235
1.236 - /// This iterator goes trough the outgoing arcs of a node.
1.237 + /// Iterator class for the outgoing arcs of a node.
1.238
1.239 /// This iterator goes trough the \e outgoing arcs of a certain node
1.240 /// of a digraph.
1.241 - /// Its usage is quite simple, for example you can count the number
1.242 + /// Its usage is quite simple, for example, you can count the number
1.243 /// of outgoing arcs of a node \c n
1.244 - /// in digraph \c g of type \c Digraph as follows.
1.245 + /// in a digraph \c g of type \c %Digraph as follows.
1.246 ///\code
1.247 /// int count=0;
1.248 - /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
1.249 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.250 ///\endcode
1.251 -
1.252 class OutArcIt : public Arc {
1.253 public:
1.254 /// Default constructor
1.255
1.256 - /// @warning The default constructor sets the iterator
1.257 - /// to an undefined value.
1.258 + /// Default constructor.
1.259 + /// \warning It sets the iterator to an undefined value.
1.260 OutArcIt() { }
1.261 /// Copy constructor.
1.262
1.263 /// Copy constructor.
1.264 ///
1.265 OutArcIt(const OutArcIt& e) : Arc(e) { }
1.266 - /// Initialize the iterator to be invalid.
1.267 + /// %Invalid constructor \& conversion.
1.268
1.269 - /// Initialize the iterator to be invalid.
1.270 + /// Initializes the iterator to be invalid.
1.271 + /// \sa Invalid for more details.
1.272 + OutArcIt(Invalid) { }
1.273 + /// Sets the iterator to the first outgoing arc.
1.274 +
1.275 + /// Sets the iterator to the first outgoing arc of the given node.
1.276 ///
1.277 - OutArcIt(Invalid) { }
1.278 - /// This constructor sets the iterator to the first outgoing arc.
1.279 + OutArcIt(const Digraph&, const Node&) { }
1.280 + /// Sets the iterator to the given arc.
1.281
1.282 - /// This constructor sets the iterator to the first outgoing arc of
1.283 - /// the node.
1.284 - OutArcIt(const Digraph&, const Node&) { }
1.285 - /// Arc -> OutArcIt conversion
1.286 -
1.287 - /// Sets the iterator to the value of the trivial iterator.
1.288 - /// This feature necessitates that each time we
1.289 - /// iterate the arc-set, the iteration order is the same.
1.290 + /// Sets the iterator to the given arc of the given digraph.
1.291 + ///
1.292 OutArcIt(const Digraph&, const Arc&) { }
1.293 - ///Next outgoing arc
1.294 + /// Next outgoing arc
1.295
1.296 /// Assign the iterator to the next
1.297 /// outgoing arc of the corresponding node.
1.298 OutArcIt& operator++() { return *this; }
1.299 };
1.300
1.301 - /// This iterator goes trough the incoming arcs of a node.
1.302 + /// Iterator class for the incoming arcs of a node.
1.303
1.304 /// This iterator goes trough the \e incoming arcs of a certain node
1.305 /// of a digraph.
1.306 - /// Its usage is quite simple, for example you can count the number
1.307 - /// of outgoing arcs of a node \c n
1.308 - /// in digraph \c g of type \c Digraph as follows.
1.309 + /// Its usage is quite simple, for example, you can count the number
1.310 + /// of incoming arcs of a node \c n
1.311 + /// in a digraph \c g of type \c %Digraph as follows.
1.312 ///\code
1.313 /// int count=0;
1.314 - /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
1.315 + /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.316 ///\endcode
1.317 -
1.318 class InArcIt : public Arc {
1.319 public:
1.320 /// Default constructor
1.321
1.322 - /// @warning The default constructor sets the iterator
1.323 - /// to an undefined value.
1.324 + /// Default constructor.
1.325 + /// \warning It sets the iterator to an undefined value.
1.326 InArcIt() { }
1.327 /// Copy constructor.
1.328
1.329 /// Copy constructor.
1.330 ///
1.331 InArcIt(const InArcIt& e) : Arc(e) { }
1.332 - /// Initialize the iterator to be invalid.
1.333 + /// %Invalid constructor \& conversion.
1.334
1.335 - /// Initialize the iterator to be invalid.
1.336 + /// Initializes the iterator to be invalid.
1.337 + /// \sa Invalid for more details.
1.338 + InArcIt(Invalid) { }
1.339 + /// Sets the iterator to the first incoming arc.
1.340 +
1.341 + /// Sets the iterator to the first incoming arc of the given node.
1.342 ///
1.343 - InArcIt(Invalid) { }
1.344 - /// This constructor sets the iterator to first incoming arc.
1.345 + InArcIt(const Digraph&, const Node&) { }
1.346 + /// Sets the iterator to the given arc.
1.347
1.348 - /// This constructor set the iterator to the first incoming arc of
1.349 - /// the node.
1.350 - InArcIt(const Digraph&, const Node&) { }
1.351 - /// Arc -> InArcIt conversion
1.352 -
1.353 - /// Sets the iterator to the value of the trivial iterator \c e.
1.354 - /// This feature necessitates that each time we
1.355 - /// iterate the arc-set, the iteration order is the same.
1.356 + /// Sets the iterator to the given arc of the given digraph.
1.357 + ///
1.358 InArcIt(const Digraph&, const Arc&) { }
1.359 /// Next incoming arc
1.360
1.361 - /// Assign the iterator to the next inarc of the corresponding node.
1.362 - ///
1.363 + /// Assign the iterator to the next
1.364 + /// incoming arc of the corresponding node.
1.365 InArcIt& operator++() { return *this; }
1.366 };
1.367 - /// This iterator goes through each arc.
1.368
1.369 - /// This iterator goes through each arc of a digraph.
1.370 - /// Its usage is quite simple, for example you can count the number
1.371 - /// of arcs in a digraph \c g of type \c Digraph as follows:
1.372 + /// Iterator class for the arcs.
1.373 +
1.374 + /// This iterator goes through each arc of the digraph.
1.375 + /// Its usage is quite simple, for example, you can count the number
1.376 + /// of arcs in a digraph \c g of type \c %Digraph as follows:
1.377 ///\code
1.378 /// int count=0;
1.379 - /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
1.380 + /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.381 ///\endcode
1.382 class ArcIt : public Arc {
1.383 public:
1.384 /// Default constructor
1.385
1.386 - /// @warning The default constructor sets the iterator
1.387 - /// to an undefined value.
1.388 + /// Default constructor.
1.389 + /// \warning It sets the iterator to an undefined value.
1.390 ArcIt() { }
1.391 /// Copy constructor.
1.392
1.393 /// Copy constructor.
1.394 ///
1.395 ArcIt(const ArcIt& e) : Arc(e) { }
1.396 - /// Initialize the iterator to be invalid.
1.397 + /// %Invalid constructor \& conversion.
1.398
1.399 - /// Initialize the iterator to be invalid.
1.400 + /// Initializes the iterator to be invalid.
1.401 + /// \sa Invalid for more details.
1.402 + ArcIt(Invalid) { }
1.403 + /// Sets the iterator to the first arc.
1.404 +
1.405 + /// Sets the iterator to the first arc of the given digraph.
1.406 ///
1.407 - ArcIt(Invalid) { }
1.408 - /// This constructor sets the iterator to the first arc.
1.409 + explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.410 + /// Sets the iterator to the given arc.
1.411
1.412 - /// This constructor sets the iterator to the first arc of \c g.
1.413 - ///@param g the digraph
1.414 - ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
1.415 - /// Arc -> ArcIt conversion
1.416 -
1.417 - /// Sets the iterator to the value of the trivial iterator \c e.
1.418 - /// This feature necessitates that each time we
1.419 - /// iterate the arc-set, the iteration order is the same.
1.420 + /// Sets the iterator to the given arc of the given digraph.
1.421 + ///
1.422 ArcIt(const Digraph&, const Arc&) { }
1.423 - ///Next arc
1.424 + /// Next arc
1.425
1.426 /// Assign the iterator to the next arc.
1.427 + ///
1.428 ArcIt& operator++() { return *this; }
1.429 };
1.430 - ///Gives back the target node of an arc.
1.431
1.432 - ///Gives back the target node of an arc.
1.433 + /// \brief The source node of the arc.
1.434 ///
1.435 - Node target(Arc) const { return INVALID; }
1.436 - ///Gives back the source node of an arc.
1.437 -
1.438 - ///Gives back the source node of an arc.
1.439 - ///
1.440 + /// Returns the source node of the given arc.
1.441 Node source(Arc) const { return INVALID; }
1.442
1.443 - /// \brief Returns the ID of the node.
1.444 + /// \brief The target node of the arc.
1.445 + ///
1.446 + /// Returns the target node of the given arc.
1.447 + Node target(Arc) const { return INVALID; }
1.448 +
1.449 + /// \brief The ID of the node.
1.450 + ///
1.451 + /// Returns the ID of the given node.
1.452 int id(Node) const { return -1; }
1.453
1.454 - /// \brief Returns the ID of the arc.
1.455 + /// \brief The ID of the arc.
1.456 + ///
1.457 + /// Returns the ID of the given arc.
1.458 int id(Arc) const { return -1; }
1.459
1.460 - /// \brief Returns the node with the given ID.
1.461 + /// \brief The node with the given ID.
1.462 ///
1.463 - /// \pre The argument should be a valid node ID in the graph.
1.464 + /// Returns the node with the given ID.
1.465 + /// \pre The argument should be a valid node ID in the digraph.
1.466 Node nodeFromId(int) const { return INVALID; }
1.467
1.468 - /// \brief Returns the arc with the given ID.
1.469 + /// \brief The arc with the given ID.
1.470 ///
1.471 - /// \pre The argument should be a valid arc ID in the graph.
1.472 + /// Returns the arc with the given ID.
1.473 + /// \pre The argument should be a valid arc ID in the digraph.
1.474 Arc arcFromId(int) const { return INVALID; }
1.475
1.476 - /// \brief Returns an upper bound on the node IDs.
1.477 + /// \brief An upper bound on the node IDs.
1.478 + ///
1.479 + /// Returns an upper bound on the node IDs.
1.480 int maxNodeId() const { return -1; }
1.481
1.482 - /// \brief Returns an upper bound on the arc IDs.
1.483 + /// \brief An upper bound on the arc IDs.
1.484 + ///
1.485 + /// Returns an upper bound on the arc IDs.
1.486 int maxArcId() const { return -1; }
1.487
1.488 void first(Node&) const {}
1.489 @@ -392,50 +390,51 @@
1.490 // Dummy parameter.
1.491 int maxId(Arc) const { return -1; }
1.492
1.493 + /// \brief The opposite node on the arc.
1.494 + ///
1.495 + /// Returns the opposite node on the given arc.
1.496 + Node oppositeNode(Node, Arc) const { return INVALID; }
1.497 +
1.498 /// \brief The base node of the iterator.
1.499 ///
1.500 - /// Gives back the base node of the iterator.
1.501 - /// It is always the target of the pointed arc.
1.502 - Node baseNode(const InArcIt&) const { return INVALID; }
1.503 + /// Returns the base node of the given outgoing arc iterator
1.504 + /// (i.e. the source node of the corresponding arc).
1.505 + Node baseNode(OutArcIt) const { return INVALID; }
1.506
1.507 /// \brief The running node of the iterator.
1.508 ///
1.509 - /// Gives back the running node of the iterator.
1.510 - /// It is always the source of the pointed arc.
1.511 - Node runningNode(const InArcIt&) const { return INVALID; }
1.512 + /// Returns the running node of the given outgoing arc iterator
1.513 + /// (i.e. the target node of the corresponding arc).
1.514 + Node runningNode(OutArcIt) const { return INVALID; }
1.515
1.516 /// \brief The base node of the iterator.
1.517 ///
1.518 - /// Gives back the base node of the iterator.
1.519 - /// It is always the source of the pointed arc.
1.520 - Node baseNode(const OutArcIt&) const { return INVALID; }
1.521 + /// Returns the base node of the given incomming arc iterator
1.522 + /// (i.e. the target node of the corresponding arc).
1.523 + Node baseNode(InArcIt) const { return INVALID; }
1.524
1.525 /// \brief The running node of the iterator.
1.526 ///
1.527 - /// Gives back the running node of the iterator.
1.528 - /// It is always the target of the pointed arc.
1.529 - Node runningNode(const OutArcIt&) const { return INVALID; }
1.530 + /// Returns the running node of the given incomming arc iterator
1.531 + /// (i.e. the source node of the corresponding arc).
1.532 + Node runningNode(InArcIt) const { return INVALID; }
1.533
1.534 - /// \brief The opposite node on the given arc.
1.535 + /// \brief Standard graph map type for the nodes.
1.536 ///
1.537 - /// Gives back the opposite node on the given arc.
1.538 - Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
1.539 -
1.540 - /// \brief Reference map of the nodes to type \c T.
1.541 - ///
1.542 - /// Reference map of the nodes to type \c T.
1.543 + /// Standard graph map type for the nodes.
1.544 + /// It conforms to the ReferenceMap concept.
1.545 template<class T>
1.546 class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
1.547 public:
1.548
1.549 - ///\e
1.550 - NodeMap(const Digraph&) { }
1.551 - ///\e
1.552 + /// Constructor
1.553 + explicit NodeMap(const Digraph&) { }
1.554 + /// Constructor with given initial value
1.555 NodeMap(const Digraph&, T) { }
1.556
1.557 private:
1.558 ///Copy constructor
1.559 - NodeMap(const NodeMap& nm) :
1.560 + NodeMap(const NodeMap& nm) :
1.561 ReferenceMap<Node, T, T&, const T&>(nm) { }
1.562 ///Assignment operator
1.563 template <typename CMap>
1.564 @@ -445,17 +444,19 @@
1.565 }
1.566 };
1.567
1.568 - /// \brief Reference map of the arcs to type \c T.
1.569 + /// \brief Standard graph map type for the arcs.
1.570 ///
1.571 - /// Reference map of the arcs to type \c T.
1.572 + /// Standard graph map type for the arcs.
1.573 + /// It conforms to the ReferenceMap concept.
1.574 template<class T>
1.575 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
1.576 public:
1.577
1.578 - ///\e
1.579 - ArcMap(const Digraph&) { }
1.580 - ///\e
1.581 + /// Constructor
1.582 + explicit ArcMap(const Digraph&) { }
1.583 + /// Constructor with given initial value
1.584 ArcMap(const Digraph&, T) { }
1.585 +
1.586 private:
1.587 ///Copy constructor
1.588 ArcMap(const ArcMap& em) :