lemon/concepts/graph.h
changeset 770 432c54cec63c
parent 657 bf7928412136
child 786 e20173729589
     1.1 --- a/lemon/concepts/graph.h	Tue Aug 18 10:08:28 2009 +0200
     1.2 +++ b/lemon/concepts/graph.h	Thu Nov 05 08:39:49 2009 +0100
     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 {