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