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