Index: lemon/concepts/digraph.h
===================================================================
 lemon/concepts/digraph.h (revision 877)
+++ lemon/concepts/digraph.h (revision 580)
@@ 3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
 * Copyright (C) 20032010
+ * Copyright (C) 20032009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ 36,38 +36,44 @@
/// \brief Class describing the concept of directed graphs.
///
 /// This class describes the common interface of all directed
 /// graphs (digraphs).
+ /// This class describes the \ref concept "concept" of the
+ /// immutable directed digraphs.
///
 /// Like all concept classes, it only provides an interface
 /// without any sensible implementation. So any general algorithm for
 /// directed graphs should compile with this class, but it will not
 /// run properly, of course.
 /// An actual digraph implementation like \ref ListDigraph or
 /// \ref SmartDigraph may have additional functionality.
+ /// Note that actual digraph implementation like @ref ListDigraph or
+ /// @ref SmartDigraph may have several additional functionality.
///
 /// \sa Graph
+ /// \sa concept
class Digraph {
private:
 /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
 Digraph(const Digraph &) {}
 /// \brief Assignment of a digraph to another one is \e not allowed.
 /// Use DigraphCopy instead.
+ ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
+
+ ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
+ ///
+ Digraph(const Digraph &) {};
+ ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
+ ///\e not allowed. Use DigraphCopy() instead.
+
+ ///Assignment of \ref Digraph "Digraph"s to another ones are
+ ///\e not allowed. Use DigraphCopy() instead.
+
void operator=(const Digraph &) {}

public:
 /// Default constructor.
+ ///\e
+
+ /// Defalult constructor.
+
+ /// Defalult constructor.
+ ///
Digraph() { }

 /// The node type of the digraph
+ /// Class for identifying a node of the digraph
/// This class identifies a node of the digraph. It also serves
/// as a base class of the node iterators,
 /// thus they convert to this type.
+ /// thus they will convert to this type.
class Node {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the object to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
Node() { }
/// Copy constructor.
@@ 77,37 +83,38 @@
Node(const Node&) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the object to be invalid.
+ /// Invalid constructor \& conversion.
+
+ /// This constructor initializes the iterator to be invalid.
/// \sa Invalid for more details.
Node(Invalid) { }
/// Equality operator
 /// Equality operator.
 ///
/// Two iterators are equal if and only if they point to the
 /// same object or both are \c INVALID.
+ /// same object or both are invalid.
bool operator==(Node) const { return true; }
/// Inequality operator
 /// Inequality operator.
+ /// \sa operator==(Node n)
+ ///
bool operator!=(Node) const { return true; }
/// Artificial ordering operator.
 /// Artificial ordering operator.
 ///
 /// \note This operator only has to define some strict ordering of
 /// the nodes; this order has nothing to do with the iteration
 /// ordering of the nodes.
+ /// To allow the use of digraph descriptors as key type in std::map or
+ /// similar associative container we require this.
+ ///
+ /// \note This operator only have to define some strict ordering of
+ /// the items; this order has nothing to do with the iteration
+ /// ordering of the items.
bool operator<(Node) const { return false; }
 };

 /// Iterator class for the nodes.

 /// This iterator goes through each node of the digraph.
 /// Its usage is quite simple, for example, you can count the number
 /// of nodes in a digraph \c g of type \c %Digraph like this:
+
+ };
+
+ /// This iterator goes through each node.
+
+ /// This iterator goes through each node.
+ /// Its usage is quite simple, for example you can count the number
+ /// of nodes in digraph \c g of type \c Digraph like this:
///\code
/// int count=0;
@@ 118,6 +125,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
NodeIt() { }
/// Copy constructor.
@@ 126,18 +133,20 @@
///
NodeIt(const NodeIt& n) : Node(n) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
+ /// Invalid constructor \& conversion.
+
+ /// Initialize the iterator to be invalid.
/// \sa Invalid for more details.
NodeIt(Invalid) { }
/// Sets the iterator to the first node.
 /// Sets the iterator to the first node of the given digraph.
 ///
 explicit NodeIt(const Digraph&) { }
 /// Sets the iterator to the given node.

 /// Sets the iterator to the given node of the given digraph.
 ///
+ /// Sets the iterator to the first node of \c g.
+ ///
+ NodeIt(const Digraph&) { }
+ /// Node > NodeIt conversion.
+
+ /// Sets the iterator to the node of \c the digraph pointed by
+ /// the trivial iterator.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
NodeIt(const Digraph&, const Node&) { }
/// Next node.
@@ 149,5 +158,5 @@
 /// The arc type of the digraph
+ /// Class for identifying an arc of the digraph
/// This class identifies an arc of the digraph. It also serves
@@ 158,6 +167,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the object to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
Arc() { }
/// Copy constructor.
@@ 166,48 +175,49 @@
///
Arc(const Arc&) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the object to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
Arc(Invalid) { }
/// Equality operator
 /// Equality operator.
 ///
/// Two iterators are equal if and only if they point to the
 /// same object or both are \c INVALID.
+ /// same object or both are invalid.
bool operator==(Arc) const { return true; }
/// Inequality operator
 /// Inequality operator.
+ /// \sa operator==(Arc n)
+ ///
bool operator!=(Arc) const { return true; }
/// Artificial ordering operator.
 /// Artificial ordering operator.
 ///
 /// \note This operator only has to define some strict ordering of
 /// the arcs; this order has nothing to do with the iteration
 /// ordering of the arcs.
+ /// To allow the use of digraph descriptors as key type in std::map or
+ /// similar associative container we require this.
+ ///
+ /// \note This operator only have to define some strict ordering of
+ /// the items; this order has nothing to do with the iteration
+ /// ordering of the items.
bool operator<(Arc) const { return false; }
};
 /// Iterator class for the outgoing arcs of a node.
+ /// This iterator goes trough the outgoing arcs of a node.
/// This iterator goes trough the \e outgoing arcs of a certain node
/// of a digraph.
 /// Its usage is quite simple, for example, you can count the number
+ /// Its usage is quite simple, for example you can count the number
/// of outgoing arcs of a node \c n
 /// in a digraph \c g of type \c %Digraph as follows.
+ /// in digraph \c g of type \c Digraph as follows.
///\code
/// int count=0;
 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
+ /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
+
class OutArcIt : public Arc {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
OutArcIt() { }
/// Copy constructor.
@@ 216,20 +226,21 @@
///
OutArcIt(const OutArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
OutArcIt(Invalid) { }
 /// Sets the iterator to the first outgoing arc.

 /// Sets the iterator to the first outgoing arc of the given node.
 ///
+ /// This constructor sets the iterator to the first outgoing arc.
+
+ /// This constructor sets the iterator to the first outgoing arc of
+ /// the node.
OutArcIt(const Digraph&, const Node&) { }
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given digraph.
 ///
+ /// Arc > OutArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
OutArcIt(const Digraph&, const Arc&) { }
 /// Next outgoing arc
+ ///Next outgoing arc
/// Assign the iterator to the next
@@ 238,21 +249,22 @@
};
 /// Iterator class for the incoming arcs of a node.
+ /// This iterator goes trough the incoming arcs of a node.
/// This iterator goes trough the \e incoming arcs of a certain node
/// of a digraph.
 /// Its usage is quite simple, for example, you can count the number
 /// of incoming arcs of a node \c n
 /// in a digraph \c g of type \c %Digraph as follows.
+ /// Its usage is quite simple, for example you can count the number
+ /// of outgoing arcs of a node \c n
+ /// in digraph \c g of type \c Digraph as follows.
///\code
/// int count=0;
 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
+ /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
+
class InArcIt : public Arc {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
InArcIt() { }
/// Copy constructor.
@@ 261,34 +273,34 @@
///
InArcIt(const InArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
InArcIt(Invalid) { }
 /// Sets the iterator to the first incoming arc.

 /// Sets the iterator to the first incoming arc of the given node.
 ///
+ /// This constructor sets the iterator to first incoming arc.
+
+ /// This constructor set the iterator to the first incoming arc of
+ /// the node.
InArcIt(const Digraph&, const Node&) { }
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given digraph.
 ///
+ /// Arc > InArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator \c e.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
InArcIt(const Digraph&, const Arc&) { }
/// Next incoming arc
 /// Assign the iterator to the next
 /// incoming arc of the corresponding node.
+ /// Assign the iterator to the next inarc of the corresponding node.
+ ///
InArcIt& operator++() { return *this; }
};

 /// Iterator class for the arcs.

 /// This iterator goes through each arc of the digraph.
 /// Its usage is quite simple, for example, you can count the number
 /// of arcs in a digraph \c g of type \c %Digraph as follows:
+ /// This iterator goes through each arc.
+
+ /// This iterator goes through each arc of a digraph.
+ /// Its usage is quite simple, for example you can count the number
+ /// of arcs in a digraph \c g of type \c Digraph as follows:
///\code
/// int count=0;
 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
+ /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
///\endcode
class ArcIt : public Arc {
@@ 296,6 +308,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
ArcIt() { }
/// Copy constructor.
@@ 304,66 +316,56 @@
///
ArcIt(const ArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
ArcIt(Invalid) { }
 /// Sets the iterator to the first arc.

 /// Sets the iterator to the first arc of the given digraph.
 ///
 explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given digraph.
 ///
+ /// This constructor sets the iterator to the first arc.
+
+ /// This constructor sets the iterator to the first arc of \c g.
+ ///@param g the digraph
+ ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+ /// Arc > ArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator \c e.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
ArcIt(const Digraph&, const Arc&) { }
 /// Next arc
+ ///Next arc
/// Assign the iterator to the next arc.
 ///
ArcIt& operator++() { return *this; }
};

 /// \brief The source node of the arc.
 ///
 /// Returns the source node of the given arc.
+ ///Gives back the target node of an arc.
+
+ ///Gives back the target node of an arc.
+ ///
+ Node target(Arc) const { return INVALID; }
+ ///Gives back the source node of an arc.
+
+ ///Gives back the source node of an arc.
+ ///
Node source(Arc) const { return INVALID; }
 /// \brief The target node of the arc.
 ///
 /// Returns the target node of the given arc.
 Node target(Arc) const { return INVALID; }

 /// \brief The ID of the node.
 ///
 /// Returns the ID of the given node.
+ /// \brief Returns the ID of the node.
int id(Node) const { return 1; }
 /// \brief The ID of the arc.
 ///
 /// Returns the ID of the given arc.
+ /// \brief Returns the ID of the arc.
int id(Arc) const { return 1; }
 /// \brief The node with the given ID.
 ///
 /// Returns the node with the given ID.
 /// \pre The argument should be a valid node ID in the digraph.
+ /// \brief Returns the node with the given ID.
+ ///
+ /// \pre The argument should be a valid node ID in the graph.
Node nodeFromId(int) const { return INVALID; }
 /// \brief The arc with the given ID.
 ///
 /// Returns the arc with the given ID.
 /// \pre The argument should be a valid arc ID in the digraph.
+ /// \brief Returns the arc with the given ID.
+ ///
+ /// \pre The argument should be a valid arc ID in the graph.
Arc arcFromId(int) const { return INVALID; }
 /// \brief An upper bound on the node IDs.
 ///
 /// Returns an upper bound on the node IDs.
+ /// \brief Returns an upper bound on the node IDs.
int maxNodeId() const { return 1; }
 /// \brief An upper bound on the arc IDs.
 ///
 /// Returns an upper bound on the arc IDs.
+ /// \brief Returns an upper bound on the arc IDs.
int maxArcId() const { return 1; }
@@ 391,49 +393,48 @@
int maxId(Arc) const { return 1; }
 /// \brief The opposite node on the arc.
 ///
 /// Returns the opposite node on the given arc.
 Node oppositeNode(Node, Arc) const { return INVALID; }

/// \brief The base node of the iterator.
///
 /// Returns the base node of the given outgoing arc iterator
 /// (i.e. the source node of the corresponding arc).
 Node baseNode(OutArcIt) const { return INVALID; }
+ /// Gives back the base node of the iterator.
+ /// It is always the target of the pointed arc.
+ Node baseNode(const InArcIt&) const { return INVALID; }
/// \brief The running node of the iterator.
///
 /// Returns the running node of the given outgoing arc iterator
 /// (i.e. the target node of the corresponding arc).
 Node runningNode(OutArcIt) const { return INVALID; }
+ /// Gives back the running node of the iterator.
+ /// It is always the source of the pointed arc.
+ Node runningNode(const InArcIt&) const { return INVALID; }
/// \brief The base node of the iterator.
///
 /// Returns the base node of the given incomming arc iterator
 /// (i.e. the target node of the corresponding arc).
 Node baseNode(InArcIt) const { return INVALID; }
+ /// Gives back the base node of the iterator.
+ /// It is always the source of the pointed arc.
+ Node baseNode(const OutArcIt&) const { return INVALID; }
/// \brief The running node of the iterator.
///
 /// Returns the running node of the given incomming arc iterator
 /// (i.e. the source node of the corresponding arc).
 Node runningNode(InArcIt) const { return INVALID; }

 /// \brief Standard graph map type for the nodes.
 ///
 /// Standard graph map type for the nodes.
 /// It conforms to the ReferenceMap concept.
+ /// Gives back the running node of the iterator.
+ /// It is always the target of the pointed arc.
+ Node runningNode(const OutArcIt&) const { return INVALID; }
+
+ /// \brief The opposite node on the given arc.
+ ///
+ /// Gives back the opposite node on the given arc.
+ Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
+
+ /// \brief Reference map of the nodes to type \c T.
+ ///
+ /// Reference map of the nodes to type \c T.
template
class NodeMap : public ReferenceMap {
public:
 /// Constructor
 explicit NodeMap(const Digraph&) { }
 /// Constructor with given initial value
+ ///\e
+ NodeMap(const Digraph&) { }
+ ///\e
NodeMap(const Digraph&, T) { }
private:
///Copy constructor
 NodeMap(const NodeMap& nm) :
+ NodeMap(const NodeMap& nm) :
ReferenceMap(nm) { }
///Assignment operator
@@ 445,17 +446,15 @@
};
 /// \brief Standard graph map type for the arcs.
 ///
 /// Standard graph map type for the arcs.
 /// It conforms to the ReferenceMap concept.
+ /// \brief Reference map of the arcs to type \c T.
+ ///
+ /// Reference map of the arcs to type \c T.
template
class ArcMap : public ReferenceMap {
public:
 /// Constructor
 explicit ArcMap(const Digraph&) { }
 /// Constructor with given initial value
+ ///\e
+ ArcMap(const Digraph&) { }
+ ///\e
ArcMap(const Digraph&, T) { }

private:
///Copy constructor
Index: lemon/concepts/graph.h
===================================================================
 lemon/concepts/graph.h (revision 877)
+++ lemon/concepts/graph.h (revision 657)
@@ 3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
 * Copyright (C) 20032010
+ * Copyright (C) 20032009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ 19,5 +19,5 @@
///\ingroup graph_concepts
///\file
///\brief The concept of undirected graphs.
+///\brief The concept of Undirected Graphs.
#ifndef LEMON_CONCEPTS_GRAPH_H
@@ 25,6 +25,4 @@
#include
#include
#include
#include
@@ 34,72 +32,61 @@
/// \ingroup graph_concepts
///
 /// \brief Class describing the concept of undirected graphs.
+ /// \brief Class describing the concept of Undirected Graphs.
///
 /// This class describes the common interface of all undirected
 /// graphs.
+ /// This class describes the common interface of all Undirected
+ /// Graphs.
///
 /// Like all concept classes, it only provides an interface
 /// without any sensible implementation. So any general algorithm for
 /// undirected graphs should compile with this class, but it will not
+ /// As all concept describing classes it provides only interface
+ /// without any sensible implementation. So any algorithm for
+ /// undirected graph should compile with this class, but it will not
/// run properly, of course.
 /// An actual graph implementation like \ref ListGraph or
 /// \ref SmartGraph may have additional functionality.
///
 /// The undirected graphs also fulfill the concept of \ref Digraph
 /// "directed graphs", since each edge can also be regarded as two
 /// oppositely directed arcs.
 /// Undirected graphs provide an Edge type for the undirected edges and
 /// an Arc type for the directed arcs. The Arc type is convertible to
 /// Edge or inherited from it, i.e. the corresponding edge can be
 /// obtained from an arc.
 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
 /// and ArcMap classes can be used for the arcs (just like in digraphs).
 /// Both InArcIt and OutArcIt iterates on the same edges but with
 /// opposite direction. IncEdgeIt also iterates on the same edges
 /// as OutArcIt and InArcIt, but it is not convertible to Arc,
 /// only to Edge.
+ /// The LEMON undirected graphs also fulfill the concept of
+ /// directed graphs (\ref lemon::concepts::Digraph "Digraph
+ /// Concept"). Each edges can be seen as two opposite
+ /// directed arc and consequently the undirected graph can be
+ /// seen as the direceted graph of these directed arcs. The
+ /// Graph has the Edge inner class for the edges and
+ /// the Arc type for the directed arcs. The Arc type is
+ /// convertible to Edge or inherited from it so from a directed
+ /// arc we can get the represented edge.
///
 /// In LEMON, each undirected edge has an inherent orientation.
 /// Thus it can defined if an arc is forward or backward oriented in
 /// an undirected graph with respect to this default oriantation of
 /// the represented edge.
 /// With the direction() and direct() functions the direction
 /// of an arc can be obtained and set, respectively.
+ /// In the sense of the LEMON each edge has a default
+ /// direction (it should be in every computer implementation,
+ /// because the order of edge's nodes defines an
+ /// orientation). With the default orientation we can define that
+ /// the directed arc is forward or backward directed. With the \c
+ /// direction() and \c direct() function we can get the direction
+ /// of the directed arc and we can direct an edge.
///
 /// Only nodes and edges can be added to or removed from an undirected
 /// graph and the corresponding arcs are added or removed automatically.
 ///
 /// \sa Digraph
+ /// The EdgeIt is an iterator for the edges. We can use
+ /// the EdgeMap to map values for the edges. The InArcIt and
+ /// OutArcIt iterates on the same edges but with opposite
+ /// direction. The IncEdgeIt iterates also on the same edges
+ /// as the OutArcIt and InArcIt but it is not convertible to Arc just
+ /// to Edge.
class Graph {
 private:
 /// Graphs are \e not copy constructible. Use DigraphCopy instead.
 Graph(const Graph&) {}
 /// \brief Assignment of a graph to another one is \e not allowed.
 /// Use DigraphCopy instead.
 void operator=(const Graph&) {}

public:
 /// Default constructor.
 Graph() {}

 /// \brief Undirected graphs should be tagged with \c UndirectedTag.
 ///
 /// Undirected graphs should be tagged with \c UndirectedTag.
 ///
 /// This tag helps the \c enable_if technics to make compile time
+ /// \brief The undirected graph should be tagged by the
+ /// UndirectedTag.
+ ///
+ /// The undirected graph should be tagged by the UndirectedTag. This
+ /// tag helps the enable_if technics to make compile time
/// specializations for undirected graphs.
typedef True UndirectedTag;
 /// The node type of the graph

 /// This class identifies a node of the graph. It also serves
 /// as a base class of the node iterators,
 /// thus they convert to this type.
+ /// \brief The base type of node iterators,
+ /// or in other words, the trivial node iterator.
+ ///
+ /// This is the base type of each node iterator,
+ /// thus each kind of node iterator converts to this.
+ /// More precisely each kind of node iterator should be inherited
+ /// from the trivial node iterator.
class Node {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the object to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
Node() { }
/// Copy constructor.
@@ 109,27 +96,27 @@
Node(const Node&) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the object to be invalid.
+ /// Invalid constructor \& conversion.
+
+ /// This constructor initializes the iterator to be invalid.
/// \sa Invalid for more details.
Node(Invalid) { }
/// Equality operator
 /// Equality operator.
 ///
/// Two iterators are equal if and only if they point to the
 /// same object or both are \c INVALID.
+ /// same object or both are invalid.
bool operator==(Node) const { return true; }
/// Inequality operator
 /// Inequality operator.
+ /// \sa operator==(Node n)
+ ///
bool operator!=(Node) const { return true; }
/// Artificial ordering operator.
 /// Artificial ordering operator.
 ///
 /// \note This operator only has to define some strict ordering of
+ /// To allow the use of graph descriptors as key type in std::map or
+ /// similar associative container we require this.
+ ///
+ /// \note This operator only have to define some strict ordering of
/// the items; this order has nothing to do with the iteration
/// ordering of the items.
@@ 138,9 +125,9 @@
};
 /// Iterator class for the nodes.

 /// This iterator goes through each node of the graph.
 /// Its usage is quite simple, for example, you can count the number
 /// of nodes in a graph \c g of type \c %Graph like this:
+ /// This iterator goes through each node.
+
+ /// This iterator goes through each node.
+ /// Its usage is quite simple, for example you can count the number
+ /// of nodes in graph \c g of type \c Graph like this:
///\code
/// int count=0;
@@ 151,6 +138,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
NodeIt() { }
/// Copy constructor.
@@ 159,18 +146,20 @@
///
NodeIt(const NodeIt& n) : Node(n) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
+ /// Invalid constructor \& conversion.
+
+ /// Initialize the iterator to be invalid.
/// \sa Invalid for more details.
NodeIt(Invalid) { }
/// Sets the iterator to the first node.
 /// Sets the iterator to the first node of the given digraph.
 ///
 explicit NodeIt(const Graph&) { }
 /// Sets the iterator to the given node.

 /// Sets the iterator to the given node of the given digraph.
 ///
+ /// Sets the iterator to the first node of \c g.
+ ///
+ NodeIt(const Graph&) { }
+ /// Node > NodeIt conversion.
+
+ /// Sets the iterator to the node of \c the graph pointed by
+ /// the trivial iterator.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
NodeIt(const Graph&, const Node&) { }
/// Next node.
@@ 182,15 +171,14 @@
 /// The edge type of the graph

 /// This class identifies an edge of the graph. It also serves
 /// as a base class of the edge iterators,
 /// thus they will convert to this type.
+ /// The base type of the edge iterators.
+
+ /// The base type of the edge iterators.
+ ///
class Edge {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the object to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
Edge() { }
/// Copy constructor.
@@ 199,36 +187,36 @@
///
Edge(const Edge&) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the object to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
Edge(Invalid) { }
/// Equality operator
 /// Equality operator.
 ///
/// Two iterators are equal if and only if they point to the
 /// same object or both are \c INVALID.
+ /// same object or both are invalid.
bool operator==(Edge) const { return true; }
/// Inequality operator
 /// Inequality operator.
+ /// \sa operator==(Edge n)
+ ///
bool operator!=(Edge) const { return true; }
/// Artificial ordering operator.
 /// Artificial ordering operator.
 ///
 /// \note This operator only has to define some strict ordering of
 /// the edges; this order has nothing to do with the iteration
 /// ordering of the edges.
+ /// To allow the use of graph descriptors as key type in std::map or
+ /// similar associative container we require this.
+ ///
+ /// \note This operator only have to define some strict ordering of
+ /// the items; this order has nothing to do with the iteration
+ /// ordering of the items.
bool operator<(Edge) const { return false; }
};
 /// Iterator class for the edges.

 /// This iterator goes through each edge of the graph.
 /// Its usage is quite simple, for example, you can count the number
 /// of edges in a graph \c g of type \c %Graph as follows:
+ /// This iterator goes through each edge.
+
+ /// This iterator goes through each edge of a graph.
+ /// Its usage is quite simple, for example you can count the number
+ /// of edges in a graph \c g of type \c Graph as follows:
///\code
/// int count=0;
@@ 239,6 +227,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
EdgeIt() { }
/// Copy constructor.
@@ 247,33 +235,36 @@
///
EdgeIt(const EdgeIt& e) : Edge(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
EdgeIt(Invalid) { }
 /// Sets the iterator to the first edge.

 /// Sets the iterator to the first edge of the given graph.
 ///
 explicit EdgeIt(const Graph&) { }
 /// Sets the iterator to the given edge.

 /// Sets the iterator to the given edge of the given graph.
 ///
+ /// This constructor sets the iterator to the first edge.
+
+ /// This constructor sets the iterator to the first edge.
+ EdgeIt(const Graph&) { }
+ /// Edge > EdgeIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator.
+ /// This feature necessitates that each time we
+ /// iterate the edgeset, the iteration order is the
+ /// same.
EdgeIt(const Graph&, const Edge&) { }
/// Next edge
/// Assign the iterator to the next edge.
 ///
EdgeIt& operator++() { return *this; }
};
 /// Iterator class for the incident edges of a node.

 /// This iterator goes trough the incident undirected edges
 /// of a certain node of a graph.
 /// Its usage is quite simple, for example, you can compute the
 /// degree (i.e. the number of incident edges) of a node \c n
 /// in a graph \c g of type \c %Graph as follows.
+ /// \brief This iterator goes trough the incident undirected
+ /// arcs of a node.
+ ///
+ /// This iterator goes trough the incident edges
+ /// of a certain node of a graph. You should assume that the
+ /// loop arcs will be iterated twice.
+ ///
+ /// Its usage is quite simple, for example you can compute the
+ /// degree (i.e. count the number of incident arcs of a node \c n
+ /// in graph \c g of type \c Graph as follows.
///
///\code
@@ 281,12 +272,10 @@
/// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
 ///
 /// \warning Loop edges will be iterated twice.
class IncEdgeIt : public Edge {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
IncEdgeIt() { }
/// Copy constructor.
@@ 295,37 +284,38 @@
///
IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
IncEdgeIt(Invalid) { }
 /// Sets the iterator to the first incident edge.

 /// Sets the iterator to the first incident edge of the given node.
 ///
+ /// This constructor sets the iterator to first incident arc.
+
+ /// This constructor set the iterator to the first incident arc of
+ /// the node.
IncEdgeIt(const Graph&, const Node&) { }
 /// Sets the iterator to the given edge.

 /// Sets the iterator to the given edge of the given graph.
 ///
+ /// Edge > IncEdgeIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator \c e.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
IncEdgeIt(const Graph&, const Edge&) { }
 /// Next incident edge

 /// Assign the iterator to the next incident edge
+ /// Next incident arc
+
+ /// Assign the iterator to the next incident arc
/// of the corresponding node.
IncEdgeIt& operator++() { return *this; }
};
 /// The arc type of the graph

 /// This class identifies a directed arc of the graph. It also serves
 /// as a base class of the arc iterators,
 /// thus they will convert to this type.
+ /// The directed arc type.
+
+ /// The directed arc type. It can be converted to the
+ /// edge or it should be inherited from the undirected
+ /// edge.
class Arc {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the object to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
Arc() { }
/// Copy constructor.
@@ 334,45 +324,41 @@
///
Arc(const Arc&) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the object to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
Arc(Invalid) { }
/// Equality operator
 /// Equality operator.
 ///
/// Two iterators are equal if and only if they point to the
 /// same object or both are \c INVALID.
+ /// same object or both are invalid.
bool operator==(Arc) const { return true; }
/// Inequality operator
 /// Inequality operator.
+ /// \sa operator==(Arc n)
+ ///
bool operator!=(Arc) const { return true; }
/// Artificial ordering operator.
 /// Artificial ordering operator.
 ///
 /// \note This operator only has to define some strict ordering of
 /// the arcs; this order has nothing to do with the iteration
 /// ordering of the arcs.
+ /// To allow the use of graph descriptors as key type in std::map or
+ /// similar associative container we require this.
+ ///
+ /// \note This operator only have to define some strict ordering of
+ /// the items; this order has nothing to do with the iteration
+ /// ordering of the items.
bool operator<(Arc) const { return false; }
 /// Converison to \c Edge

 /// Converison to \c Edge.
 ///
+ /// Converison to Edge
operator Edge() const { return Edge(); }
};

 /// Iterator class for the arcs.

 /// This iterator goes through each directed arc of the graph.
 /// Its usage is quite simple, for example, you can count the number
 /// of arcs in a graph \c g of type \c %Graph as follows:
+ /// This iterator goes through each directed arc.
+
+ /// This iterator goes through each arc of a graph.
+ /// Its usage is quite simple, for example you can count the number
+ /// of arcs in a graph \c g of type \c Graph as follows:
///\code
/// int count=0;
 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
+ /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
///\endcode
class ArcIt : public Arc {
@@ 380,6 +366,6 @@
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
ArcIt() { }
/// Copy constructor.
@@ 388,43 +374,44 @@
///
ArcIt(const ArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
ArcIt(Invalid) { }
 /// Sets the iterator to the first arc.

 /// Sets the iterator to the first arc of the given graph.
 ///
 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given graph.
 ///
+ /// This constructor sets the iterator to the first arc.
+
+ /// This constructor sets the iterator to the first arc of \c g.
+ ///@param g the graph
+ ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+ /// Arc > ArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator \c e.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
ArcIt(const Graph&, const Arc&) { }
 /// Next arc
+ ///Next arc
/// Assign the iterator to the next arc.
 ///
ArcIt& operator++() { return *this; }
};
 /// Iterator class for the outgoing arcs of a node.

 /// This iterator goes trough the \e outgoing directed arcs of a
 /// certain node of a graph.
 /// Its usage is quite simple, for example, you can count the number
+ /// This iterator goes trough the outgoing directed arcs of a node.
+
+ /// This iterator goes trough the \e outgoing arcs of a certain node
+ /// of a graph.
+ /// Its usage is quite simple, for example you can count the number
/// of outgoing arcs of a node \c n
 /// in a graph \c g of type \c %Graph as follows.
+ /// in graph \c g of type \c Graph as follows.
///\code
/// int count=0;
 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
+ /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
+
class OutArcIt : public Arc {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
OutArcIt() { }
/// Copy constructor.
@@ 433,23 +420,26 @@
///
OutArcIt(const OutArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
OutArcIt(Invalid) { }
 /// Sets the iterator to the first outgoing arc.

 /// Sets the iterator to the first outgoing arc of the given node.
 ///
+ /// This constructor sets the iterator to the first outgoing arc.
+
+ /// This constructor sets the iterator to the first outgoing arc of
+ /// the node.
+ ///@param n the node
+ ///@param g the graph
OutArcIt(const Graph& n, const Node& g) {
ignore_unused_variable_warning(n);
ignore_unused_variable_warning(g);
}
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given graph.
 ///
+ /// Arc > OutArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
OutArcIt(const Graph&, const Arc&) { }
 /// Next outgoing arc
+ ///Next outgoing arc
/// Assign the iterator to the next
@@ 458,21 +448,22 @@
};
 /// Iterator class for the incoming arcs of a node.

 /// This iterator goes trough the \e incoming directed arcs of a
 /// certain node of a graph.
 /// Its usage is quite simple, for example, you can count the number
 /// of incoming arcs of a node \c n
 /// in a graph \c g of type \c %Graph as follows.
+ /// This iterator goes trough the incoming directed arcs of a node.
+
+ /// This iterator goes trough the \e incoming arcs of a certain node
+ /// of a graph.
+ /// Its usage is quite simple, for example you can count the number
+ /// of outgoing arcs of a node \c n
+ /// in graph \c g of type \c Graph as follows.
///\code
/// int count=0;
 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
+ /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
+
class InArcIt : public Arc {
public:
/// Default constructor
 /// Default constructor.
 /// \warning It sets the iterator to an undefined value.
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
InArcIt() { }
/// Copy constructor.
@@ 481,33 +472,35 @@
///
InArcIt(const InArcIt& e) : Arc(e) { }
 /// %Invalid constructor \& conversion.

 /// Initializes the iterator to be invalid.
 /// \sa Invalid for more details.
+ /// Initialize the iterator to be invalid.
+
+ /// Initialize the iterator to be invalid.
+ ///
InArcIt(Invalid) { }
 /// Sets the iterator to the first incoming arc.

 /// Sets the iterator to the first incoming arc of the given node.
 ///
+ /// This constructor sets the iterator to first incoming arc.
+
+ /// This constructor set the iterator to the first incoming arc of
+ /// the node.
+ ///@param n the node
+ ///@param g the graph
InArcIt(const Graph& g, const Node& n) {
ignore_unused_variable_warning(n);
ignore_unused_variable_warning(g);
}
 /// Sets the iterator to the given arc.

 /// Sets the iterator to the given arc of the given graph.
 ///
+ /// Arc > InArcIt conversion
+
+ /// Sets the iterator to the value of the trivial iterator \c e.
+ /// This feature necessitates that each time we
+ /// iterate the arcset, the iteration order is the same.
InArcIt(const Graph&, const Arc&) { }
/// Next incoming arc
 /// Assign the iterator to the next
 /// incoming arc of the corresponding node.
+ /// Assign the iterator to the next inarc of the corresponding node.
+ ///
InArcIt& operator++() { return *this; }
};
 /// \brief Standard graph map type for the nodes.
 ///
 /// Standard graph map type for the nodes.
 /// It conforms to the ReferenceMap concept.
+ /// \brief Reference map of the nodes to type \c T.
+ ///
+ /// Reference map of the nodes to type \c T.
template
class NodeMap : public ReferenceMap
@@ 515,7 +508,7 @@
public:
 /// Constructor
 explicit NodeMap(const Graph&) { }
 /// Constructor with given initial value
+ ///\e
+ NodeMap(const Graph&) { }
+ ///\e
NodeMap(const Graph&, T) { }
@@ 532,8 +525,7 @@
};
 /// \brief Standard graph map type for the arcs.
 ///
 /// Standard graph map type for the arcs.
 /// It conforms to the ReferenceMap concept.
+ /// \brief Reference map of the arcs to type \c T.
+ ///
+ /// Reference map of the arcs to type \c T.
template
class ArcMap : public ReferenceMap
@@ 541,9 +533,8 @@
public:
 /// Constructor
 explicit ArcMap(const Graph&) { }
 /// Constructor with given initial value
+ ///\e
+ ArcMap(const Graph&) { }
+ ///\e
ArcMap(const Graph&, T) { }

private:
///Copy constructor
@@ 558,8 +549,7 @@
};
 /// \brief Standard graph map type for the edges.
 ///
 /// Standard graph map type for the edges.
 /// It conforms to the ReferenceMap concept.
+ /// Reference map of the edges to type \c T.
+
+ /// Reference map of the edges to type \c T.
template
class EdgeMap : public ReferenceMap
@@ 567,9 +557,8 @@
public:
 /// Constructor
 explicit EdgeMap(const Graph&) { }
 /// Constructor with given initial value
+ ///\e
+ EdgeMap(const Graph&) { }
+ ///\e
EdgeMap(const Graph&, T) { }

private:
///Copy constructor
@@ 584,121 +573,104 @@
};
 /// \brief The first node of the edge.
 ///
 /// Returns the first node of the given edge.
 ///
 /// Edges don't have source and target nodes, however, methods
 /// u() and v() are used to query the two endnodes of an edge.
 /// The orientation of an edge that arises this way is called
 /// the inherent direction, it is used to define the default
 /// direction for the corresponding arcs.
+ /// \brief Direct the given edge.
+ ///
+ /// Direct the given edge. The returned arc source
+ /// will be the given node.
+ Arc direct(const Edge&, const Node&) const {
+ return INVALID;
+ }
+
+ /// \brief Direct the given edge.
+ ///
+ /// Direct the given edge. The returned arc
+ /// represents the given edge and the direction comes
+ /// from the bool parameter. The source of the edge and
+ /// the directed arc is the same when the given bool is true.
+ Arc direct(const Edge&, bool) const {
+ return INVALID;
+ }
+
+ /// \brief Returns true if the arc has default orientation.
+ ///
+ /// Returns whether the given directed arc is same orientation as
+ /// the corresponding edge's default orientation.
+ bool direction(Arc) const { return true; }
+
+ /// \brief Returns the opposite directed arc.
+ ///
+ /// Returns the opposite directed arc.
+ Arc oppositeArc(Arc) const { return INVALID; }
+
+ /// \brief Opposite node on an arc
+ ///
+ /// \return The opposite of the given node on the given edge.
+ Node oppositeNode(Node, Edge) const { return INVALID; }
+
+ /// \brief First node of the edge.
+ ///
+ /// \return The first node of the given edge.
+ ///
+ /// Naturally edges don't have direction and thus
+ /// don't have source and target node. However we use \c u() and \c v()
+ /// methods to query the two nodes of the arc. The direction of the
+ /// arc which arises this way is called the inherent direction of the
+ /// edge, and is used to define the "default" direction
+ /// of the directed versions of the arcs.
/// \sa v()
/// \sa direction()
Node u(Edge) const { return INVALID; }
 /// \brief The second node of the edge.
 ///
 /// Returns the second node of the given edge.
 ///
 /// Edges don't have source and target nodes, however, methods
 /// u() and v() are used to query the two endnodes of an edge.
 /// The orientation of an edge that arises this way is called
 /// the inherent direction, it is used to define the default
 /// direction for the corresponding arcs.
+ /// \brief Second node of the edge.
+ ///
+ /// \return The second node of the given edge.
+ ///
+ /// Naturally edges don't have direction and thus
+ /// don't have source and target node. However we use \c u() and \c v()
+ /// methods to query the two nodes of the arc. The direction of the
+ /// arc which arises this way is called the inherent direction of the
+ /// edge, and is used to define the "default" direction
+ /// of the directed versions of the arcs.
/// \sa u()
/// \sa direction()
Node v(Edge) const { return INVALID; }
 /// \brief The source node of the arc.
 ///
 /// Returns the source node of the given arc.
+ /// \brief Source node of the directed arc.
Node source(Arc) const { return INVALID; }
 /// \brief The target node of the arc.
 ///
 /// Returns the target node of the given arc.
+ /// \brief Target node of the directed arc.
Node target(Arc) const { return INVALID; }
 /// \brief The ID of the node.
 ///
 /// Returns the ID of the given node.
+ /// \brief Returns the id of the node.
int id(Node) const { return 1; }
 /// \brief The ID of the edge.
 ///
 /// Returns the ID of the given edge.
+ /// \brief Returns the id of the edge.
int id(Edge) const { return 1; }
 /// \brief The ID of the arc.
 ///
 /// Returns the ID of the given arc.
+ /// \brief Returns the id of the arc.
int id(Arc) const { return 1; }
 /// \brief The node with the given ID.
 ///
 /// Returns the node with the given ID.
 /// \pre The argument should be a valid node ID in the graph.
+ /// \brief Returns the node with the given id.
+ ///
+ /// \pre The argument should be a valid node id in the graph.
Node nodeFromId(int) const { return INVALID; }
 /// \brief The edge with the given ID.
 ///
 /// Returns the edge with the given ID.
 /// \pre The argument should be a valid edge ID in the graph.
+ /// \brief Returns the edge with the given id.
+ ///
+ /// \pre The argument should be a valid edge id in the graph.
Edge edgeFromId(int) const { return INVALID; }
 /// \brief The arc with the given ID.
 ///
 /// Returns the arc with the given ID.
 /// \pre The argument should be a valid arc ID in the graph.
+ /// \brief Returns the arc with the given id.
+ ///
+ /// \pre The argument should be a valid arc id in the graph.
Arc arcFromId(int) const { return INVALID; }
 /// \brief An upper bound on the node IDs.
 ///
 /// Returns an upper bound on the node IDs.
+ /// \brief Returns an upper bound on the node IDs.
int maxNodeId() const { return 1; }
 /// \brief An upper bound on the edge IDs.
 ///
 /// Returns an upper bound on the edge IDs.
+ /// \brief Returns an upper bound on the edge IDs.
int maxEdgeId() const { return 1; }
 /// \brief An upper bound on the arc IDs.
 ///
 /// Returns an upper bound on the arc IDs.
+ /// \brief Returns an upper bound on the arc IDs.
int maxArcId() const { return 1; }

 /// \brief The direction of the arc.
 ///
 /// Returns \c true if the direction of the given arc is the same as
 /// the inherent orientation of the represented edge.
 bool direction(Arc) const { return true; }

 /// \brief Direct the edge.
 ///
 /// Direct the given edge. The returned arc
 /// represents the given edge and its direction comes
 /// from the bool parameter. If it is \c true, then the direction
 /// of the arc is the same as the inherent orientation of the edge.
 Arc direct(Edge, bool) const {
 return INVALID;
 }

 /// \brief Direct the edge.
 ///
 /// Direct the given edge. The returned arc represents the given
 /// edge and its source node is the given node.
 Arc direct(Edge, Node) const {
 return INVALID;
 }

 /// \brief The oppositely directed arc.
 ///
 /// Returns the oppositely directed arc representing the same edge.
 Arc oppositeArc(Arc) const { return INVALID; }

 /// \brief The opposite node on the edge.
 ///
 /// Returns the opposite node on the given edge.
 Node oppositeNode(Node, Edge) const { return INVALID; }
void first(Node&) const {}
@@ 734,37 +706,45 @@
int maxId(Arc) const { return 1; }
 /// \brief The base node of the iterator.
 ///
 /// Returns the base node of the given incident edge iterator.
 Node baseNode(IncEdgeIt) const { return INVALID; }

 /// \brief The running node of the iterator.
 ///
 /// Returns the running node of the given incident edge iterator.
 Node runningNode(IncEdgeIt) const { return INVALID; }

 /// \brief The base node of the iterator.
 ///
 /// Returns the base node of the given outgoing arc iterator
 /// (i.e. the source node of the corresponding arc).
 Node baseNode(OutArcIt) const { return INVALID; }

 /// \brief The running node of the iterator.
 ///
 /// Returns the running node of the given outgoing arc iterator
 /// (i.e. the target node of the corresponding arc).
 Node runningNode(OutArcIt) const { return INVALID; }

 /// \brief The base node of the iterator.
 ///
 /// Returns the base node of the given incomming arc iterator
 /// (i.e. the target node of the corresponding arc).
 Node baseNode(InArcIt) const { return INVALID; }

 /// \brief The running node of the iterator.
 ///
 /// Returns the running node of the given incomming arc iterator
 /// (i.e. the source node of the corresponding arc).
 Node runningNode(InArcIt) const { return INVALID; }
+ /// \brief Base node of the iterator
+ ///
+ /// Returns the base node (the source in this case) of the iterator
+ Node baseNode(OutArcIt e) const {
+ return source(e);
+ }
+ /// \brief Running node of the iterator
+ ///
+ /// Returns the running node (the target in this case) of the
+ /// iterator
+ Node runningNode(OutArcIt e) const {
+ return target(e);
+ }
+
+ /// \brief Base node of the iterator
+ ///
+ /// Returns the base node (the target in this case) of the iterator
+ Node baseNode(InArcIt e) const {
+ return target(e);
+ }
+ /// \brief Running node of the iterator
+ ///
+ /// Returns the running node (the source in this case) of the
+ /// iterator
+ Node runningNode(InArcIt e) const {
+ return source(e);
+ }
+
+ /// \brief Base node of the iterator
+ ///
+ /// Returns the base node of the iterator
+ Node baseNode(IncEdgeIt) const {
+ return INVALID;
+ }
+
+ /// \brief Running node of the iterator
+ ///
+ /// Returns the running node of the iterator
+ Node runningNode(IncEdgeIt) const {
+ return INVALID;
+ }
template
Index: lemon/concepts/graph_components.h
===================================================================
 lemon/concepts/graph_components.h (revision 954)
+++ lemon/concepts/graph_components.h (revision 963)
@@ 3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
 * Copyright (C) 20032010
+ * Copyright (C) 20032009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ 19,5 +19,5 @@
///\ingroup graph_concepts
///\file
///\brief The concepts of graph components.
+///\brief The concept of graph components.
#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
@@ 39,5 +39,5 @@
/// \note This class is a template class so that we can use it to
/// create graph skeleton classes. The reason for this is that \c Node
 /// and \c Arc (or \c Edge) types should \e not derive from the same
+ /// and \c Arc (or \c Edge) types should \e not derive from the same
/// base class. For \c Node you should instantiate it with character
/// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
@@ 90,8 +90,8 @@
///
/// This operator defines an ordering of the items.
 /// It makes possible to use graph item types as key types in
+ /// It makes possible to use graph item types as key types in
/// associative containers (e.g. \c std::map).
///
 /// \note This operator only has to define some strict ordering of
+ /// \note This operator only have to define some strict ordering of
/// the items; this order has nothing to do with the iteration
/// ordering of the items.
@@ 124,5 +124,5 @@
/// This class describes the base interface of directed graph types.
/// All digraph %concepts have to conform to this class.
 /// It just provides types for nodes and arcs and functions
+ /// It just provides types for nodes and arcs and functions
/// to get the source and the target nodes of arcs.
class BaseDigraphComponent {
@@ 432,5 +432,5 @@
/// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
///
 /// This class describes the concept of \c NodeIt, \c ArcIt and
+ /// This class describes the concept of \c NodeIt, \c ArcIt and
/// \c EdgeIt subtypes of digraph and graph types.
template
@@ 472,5 +472,5 @@
/// next item.
GraphItemIt& operator++() { return *this; }

+
/// \brief Equality operator
///
@@ 495,4 +495,6 @@
_GraphItemIt it3 = it1;
_GraphItemIt it4 = INVALID;
+ ignore_unused_variable_warning(it3);
+ ignore_unused_variable_warning(it4);
it2 = ++it1;
@@ 508,13 +510,13 @@
};
 /// \brief Concept class for \c InArcIt, \c OutArcIt and
+ /// \brief Concept class for \c InArcIt, \c OutArcIt and
/// \c IncEdgeIt types.
///
 /// This class describes the concept of \c InArcIt, \c OutArcIt
+ /// This class describes the concept of \c InArcIt, \c OutArcIt
/// and \c IncEdgeIt subtypes of digraph and graph types.
///
/// \note Since these iterator classes do not inherit from the same
/// base class, there is an additional template parameter (selector)
 /// \c sel. For \c InArcIt you should instantiate it with character
+ /// \c sel. For \c InArcIt you should instantiate it with character
/// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
template
#include
@@ 36,25 +36,19 @@
/// \brief The heap concept.
///
 /// This concept class describes the main interface of heaps.
 /// The various \ref heaps "heap structures" are efficient
 /// implementations of the abstract data type \e priority \e queue.
 /// They store items with specified values called \e priorities
 /// in such a way that finding and removing the item with minimum
 /// priority are efficient. The basic operations are adding and
 /// erasing items, changing the priority of an item, etc.
+ /// Concept class describing the main interface of heaps. A \e heap
+ /// is a data structure for storing items with specified values called
+ /// \e priorities in such a way that finding the item with minimum
+ /// priority is efficient. In a heap one can change the priority of an
+ /// item, add or erase an item, etc.
///
 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 /// Any class that conforms to this concept can be used easily in such
 /// algorithms.
 ///
 /// \tparam PR Type of the priorities of the items.
 /// \tparam IM A readwritable item map with \c int values, used
+ /// \tparam PR Type of the priority of the items.
+ /// \tparam IM A read and writable item map with int values, used
/// internally to handle the cross references.
 /// \tparam CMP A functor class for comparing the priorities.
+ /// \tparam Comp A functor class for the ordering of the priorities.
/// The default is \c std::less.
#ifdef DOXYGEN
 template
+ template >
#else
 template >
+ template
#endif
class Heap {
@@ 71,6 +65,7 @@
///
/// Each item has a state associated to it. It can be "in heap",
 /// "preheap" or "postheap". The latter two are indifferent from the
 /// heap's point of view, but may be useful to the user.
+ /// "pre heap" or "post heap". The later two are indifferent
+ /// from the point of view of the heap, but may be useful for
+ /// the user.
///
/// The itemint map must be initialized in such way that it assigns
@@ 78,148 +73,99 @@
enum State {
IN_HEAP = 0, ///< = 0. The "in heap" state constant.
 PRE_HEAP = 1, ///< = 1. The "preheap" state constant.
 POST_HEAP = 2 ///< = 2. The "postheap" state constant.
+ PRE_HEAP = 1, ///< = 1. The "pre heap" state constant.
+ POST_HEAP = 2 ///< = 2. The "post heap" state constant.
};
 /// \brief Constructor.
 ///
 /// Constructor.
+ /// \brief The constructor.
+ ///
+ /// The constructor.
/// \param map A map that assigns \c int values to keys of type
/// \c Item. It is used internally by the heap implementations to
/// handle the cross references. The assigned value must be
 /// \c PRE_HEAP (1) for each item.
#ifdef DOXYGEN
+ /// \c PRE_HEAP (1) for every item.
explicit Heap(ItemIntMap &map) {}
#else
 explicit Heap(ItemIntMap&) {}
#endif

 /// \brief Constructor.
 ///
 /// Constructor.
 /// \param map A map that assigns \c int values to keys of type
 /// \c Item. It is used internally by the heap implementations to
 /// handle the cross references. The assigned value must be
 /// \c PRE_HEAP (1) for each item.
 /// \param comp The function object used for comparing the priorities.
#ifdef DOXYGEN
 explicit Heap(ItemIntMap &map, const CMP &comp) {}
#else
 explicit Heap(ItemIntMap&, const CMP&) {}
#endif
/// \brief The number of items stored in the heap.
///
 /// This function returns the number of items stored in the heap.
+ /// Returns the number of items stored in the heap.
int size() const { return 0; }
 /// \brief Check if the heap is empty.
 ///
 /// This function returns \c true if the heap is empty.
+ /// \brief Checks if the heap is empty.
+ ///
+ /// Returns \c true if the heap is empty.
bool empty() const { return false; }
 /// \brief Make the heap empty.
 ///
 /// This functon makes the heap empty.
 /// It does not change the cross reference map. If you want to reuse
 /// a heap that is not surely empty, you should first clear it and
 /// then you should set the cross reference map to \c PRE_HEAP
 /// for each item.
 void clear() {}

 /// \brief Insert an item into the heap with the given priority.
 ///
 /// This function inserts the given item into the heap with the
 /// given priority.
+ /// \brief Makes the heap empty.
+ ///
+ /// Makes the heap empty.
+ void clear();
+
+ /// \brief Inserts an item into the heap with the given priority.
+ ///
+ /// Inserts the given item into the heap with the given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
 /// \pre \e i must not be stored in the heap.
#ifdef DOXYGEN
void push(const Item &i, const Prio &p) {}
#else
 void push(const Item&, const Prio&) {}
#endif

 /// \brief Return the item having minimum priority.
 ///
 /// This function returns the item having minimum priority.
+
+ /// \brief Returns the item having minimum priority.
+ ///
+ /// Returns the item having minimum priority.
/// \pre The heap must be nonempty.
 Item top() const { return Item(); }
+ Item top() const {}
/// \brief The minimum priority.
///
 /// This function returns the minimum priority.
+ /// Returns the minimum priority.
/// \pre The heap must be nonempty.
 Prio prio() const { return Prio(); }

 /// \brief Remove the item having minimum priority.
 ///
 /// This function removes the item having minimum priority.
+ Prio prio() const {}
+
+ /// \brief Removes the item having minimum priority.
+ ///
+ /// Removes the item having minimum priority.
/// \pre The heap must be nonempty.
void pop() {}
 /// \brief Remove the given item from the heap.
 ///
 /// This function removes the given item from the heap if it is
 /// already stored.
+ /// \brief Removes an item from the heap.
+ ///
+ /// Removes the given item from the heap if it is already stored.
/// \param i The item to delete.
 /// \pre \e i must be in the heap.
#ifdef DOXYGEN
void erase(const Item &i) {}
#else
 void erase(const Item&) {}
#endif

 /// \brief The priority of the given item.
 ///
 /// This function returns the priority of the given item.
 /// \param i The item.
 /// \pre \e i must be in the heap.
#ifdef DOXYGEN
+
+ /// \brief The priority of an item.
+ ///
+ /// Returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \c i must be in the heap.
Prio operator[](const Item &i) const {}
#else
 Prio operator[](const Item&) const { return Prio(); }
#endif

 /// \brief Set the priority of an item or insert it, if it is
+
+ /// \brief Sets the priority of an item or inserts it, if it is
/// not stored in the heap.
///
/// This method sets the priority of the given item if it is
 /// already stored in the heap. Otherwise it inserts the given
 /// item into the heap with the given priority.
+ /// already stored in the heap.
+ /// Otherwise it inserts the given item with the given priority.
///
/// \param i The item.
/// \param p The priority.
#ifdef DOXYGEN
void set(const Item &i, const Prio &p) {}
#else
 void set(const Item&, const Prio&) {}
#endif

 /// \brief Decrease the priority of an item to the given value.
 ///
 /// This function decreases the priority of an item to the given value.
+
+ /// \brief Decreases the priority of an item to the given value.
+ ///
+ /// Decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
 /// \pre \e i must be stored in the heap with priority at least \e p.
#ifdef DOXYGEN
+ /// \pre \c i must be stored in the heap with priority at least \c p.
void decrease(const Item &i, const Prio &p) {}
#else
 void decrease(const Item&, const Prio&) {}
#endif

 /// \brief Increase the priority of an item to the given value.
 ///
 /// This function increases the priority of an item to the given value.
+
+ /// \brief Increases the priority of an item to the given value.
+ ///
+ /// Increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
 /// \pre \e i must be stored in the heap with priority at most \e p.
#ifdef DOXYGEN
+ /// \pre \c i must be stored in the heap with priority at most \c p.
void increase(const Item &i, const Prio &p) {}
#else
 void increase(const Item&, const Prio&) {}
#endif

 /// \brief Return the state of an item.
+
+ /// \brief Returns if an item is in, has already been in, or has
+ /// never been in the heap.
///
/// This method returns \c PRE_HEAP if the given item has never
@@ 229,22 +175,14 @@
/// to the heap again.
/// \param i The item.
#ifdef DOXYGEN
State state(const Item &i) const {}
#else
 State state(const Item&) const { return PRE_HEAP; }
#endif

 /// \brief Set the state of an item in the heap.
 ///
 /// This function sets the state of the given item in the heap.
 /// It can be used to manually clear the heap when it is important
 /// to achive better time complexity.
+
+ /// \brief Sets the state of an item in the heap.
+ ///
+ /// Sets the state of the given item in the heap. It can be used
+ /// to manually clear the heap when it is important to achive the
+ /// better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
#ifdef DOXYGEN
void state(const Item& i, State st) {}
#else
 void state(const Item&, State) {}
#endif
Index: lemon/concepts/maps.h
===================================================================
 lemon/concepts/maps.h (revision 953)
+++ lemon/concepts/maps.h (revision 963)
@@ 50,5 +50,5 @@
/// Returns the value associated with the given key.
Value operator[](const Key &) const {
 return *static_cast(0);
+ return *(static_cast(0)+1);
}
Index: lemon/concepts/path.h
===================================================================
 lemon/concepts/path.h (revision 954)
+++ lemon/concepts/path.h (revision 953)
@@ 19,5 +19,5 @@
///\ingroup concept
///\file
///\brief The concept of paths
+///\brief Classes for representing paths in digraphs.
///
@@ 39,20 +39,11 @@
/// A skeleton structure for representing directed paths in a
/// digraph.
 /// In a sense, a path can be treated as a list of arcs.
 /// LEMON path types just store this list. As a consequence, they cannot
 /// enumerate the nodes on the path directly and a zero length path
 /// cannot store its source node.
 ///
 /// The arcs of a path should be stored in the order of their directions,
 /// i.e. the target node of each arc should be the same as the source
 /// node of the next arc. This consistency could be checked using
 /// \ref checkPath().
 /// The source and target nodes of a (consistent) path can be obtained
 /// using \ref pathSource() and \ref pathTarget().
 ///
 /// A path can be constructed from another path of any type using the
 /// copy constructor or the assignment operator.
 ///
/// \tparam GR The digraph type in which the path is.
+ ///
+ /// In a sense, the path can be treated as a list of arcs. The
+ /// lemon path type stores just this list. As a consequence it
+ /// cannot enumerate the nodes in the path and the zero length
+ /// paths cannot store the source.
+ ///
template
class Path {
@@ 69,9 +60,9 @@
Path() {}
 /// \brief Template copy constructor
+ /// \brief Template constructor
template
Path(const CPath& cpath) {}
 /// \brief Template assigment operator
+ /// \brief Template assigment
template
Path& operator=(const CPath& cpath) {
@@ 80,5 +71,5 @@
}
 /// Length of the path, i.e. the number of arcs on the path.
+ /// Length of the path ie. the number of arcs in the path.
int length() const { return 0;}
@@ 89,7 +80,7 @@
void clear() {}
 /// \brief LEMON style iterator for enumerating the arcs of a path.
+ /// \brief LEMON style iterator for path arcs
///
 /// LEMON style iterator class for enumerating the arcs of a path.
+ /// This class is used to iterate on the arcs of the paths.
class ArcIt {
public:
@@ 98,8 +89,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
 /// Sets the iterator to the first arc of the given path
+ /// Constructor for first arc
ArcIt(const Path &) {}
 /// Conversion to \c Arc
+ /// Conversion to Arc
operator Arc() const { return INVALID; }
@@ 204,16 +195,22 @@
///
/// A skeleton structure for path dumpers. The path dumpers are
 /// the generalization of the paths, they can enumerate the arcs
 /// of the path either in forward or in backward order.
 /// These classes are typically not used directly, they are rather
 /// used to be assigned to a real path type.
+ /// the generalization of the paths. The path dumpers can
+ /// enumerate the arcs of the path wheter in forward or in
+ /// backward order. In most time these classes are not used
+ /// directly rather it used to assign a dumped class to a real
+ /// path type.
///
/// The main purpose of this concept is that the shortest path
 /// algorithms can enumerate the arcs easily in reverse order.
 /// In LEMON, such algorithms give back a (reverse) path dumper that
 /// can be assigned to a real path. The dumpers can be implemented as
+ /// algorithms can enumerate easily the arcs in reverse order.
+ /// If we would like to give back a real path from these
+ /// algorithms then we should create a temporarly path object. In
+ /// LEMON such algorithms gives back a path dumper what can
+ /// assigned to a real path and the dumpers can be implemented as
/// an adaptor class to the predecessor map.
///
/// \tparam GR The digraph type in which the path is.
+ ///
+ /// The paths can be constructed from any path type by a
+ /// template constructor or a template assignment operator.
template
class PathDumper {
@@ 225,5 +222,5 @@
typedef typename Digraph::Arc Arc;
 /// Length of the path, i.e. the number of arcs on the path.
+ /// Length of the path ie. the number of arcs in the path.
int length() const { return 0;}
@@ 233,12 +230,13 @@
/// \brief Forward or reverse dumping
///
 /// If this tag is defined to be \c True, then reverse dumping
 /// is provided in the path dumper. In this case, \c RevArcIt
 /// iterator should be implemented instead of \c ArcIt iterator.
+ /// If the RevPathTag is defined and true then reverse dumping
+ /// is provided in the path dumper. In this case instead of the
+ /// ArcIt the RevArcIt iterator should be implemented in the
+ /// dumper.
typedef False RevPathTag;
 /// \brief LEMON style iterator for enumerating the arcs of a path.
+ /// \brief LEMON style iterator for path arcs
///
 /// LEMON style iterator class for enumerating the arcs of a path.
+ /// This class is used to iterate on the arcs of the paths.
class ArcIt {
public:
@@ 247,8 +245,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
 /// Sets the iterator to the first arc of the given path
+ /// Constructor for first arc
ArcIt(const PathDumper&) {}
 /// Conversion to \c Arc
+ /// Conversion to Arc
operator Arc() const { return INVALID; }
@@ 265,9 +263,8 @@
};
 /// \brief LEMON style iterator for enumerating the arcs of a path
 /// in reverse direction.
+ /// \brief LEMON style iterator for path arcs
///
 /// LEMON style iterator class for enumerating the arcs of a path
 /// in reverse direction.
+ /// This class is used to iterate on the arcs of the paths in
+ /// reverse direction.
class RevArcIt {
public:
@@ 276,8 +273,8 @@
/// Invalid constructor
RevArcIt(Invalid) {}
 /// Sets the iterator to the last arc of the given path
+ /// Constructor for first arc
RevArcIt(const PathDumper &) {}
 /// Conversion to \c Arc
+ /// Conversion to Arc
operator Arc() const { return INVALID; }