Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 802)
+++ doc/min_cost_flow.dox (revision 835)
@@ -79,5 +79,5 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)<=0\f$;
+ - \f$\pi(u)\leq 0\f$;
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
@@ -146,5 +146,5 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)>=0\f$;
+ - \f$\pi(u)\geq 0\f$;
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 703)
+++ lemon/adaptors.h (revision 834)
@@ -361,4 +361,7 @@
/// parameter is set to be \c const.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -719,4 +722,6 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes and arcs.
///
/// \tparam DGR The type of the adapted digraph.
@@ -1315,4 +1320,6 @@
/// parameter is set to be \c const.
///
+ /// This class provides only linear time counting for nodes, edges and arcs.
+ ///
/// \tparam GR The type of the adapted graph.
/// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -1471,4 +1478,6 @@
/// by adding or removing nodes or arcs/edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time item counting.
///
/// \tparam GR The type of the adapted digraph or graph.
@@ -1620,4 +1629,6 @@
/// parameter is set to be \c const.
///
+ /// This class provides only linear time counting for nodes and arcs.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -1729,4 +1740,6 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes, edges and arcs.
///
/// \tparam GR The type of the adapted graph.
@@ -2233,4 +2246,7 @@
/// parameter is set to be \c const.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2535,4 +2551,7 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides item counting in the same time as the adapted
+ /// graph structure.
///
/// \tparam GR The type of the adapted graph.
@@ -2678,4 +2697,6 @@
/// arcs).
/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
+ ///
+ /// This class provides only linear time counting for nodes and arcs.
///
/// \tparam DGR The type of the adapted digraph.
@@ -3326,4 +3347,7 @@
/// in the adaptor.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 828)
+++ lemon/bellman_ford.h (revision 835)
@@ -301,5 +301,5 @@
/// \ref named-templ-param "Named parameter" for setting
/// \c OperationTraits type.
- /// For more information see \ref BellmanFordDefaultOperationTraits.
+ /// For more information, see \ref BellmanFordDefaultOperationTraits.
template
struct SetOperationTraits
@@ -719,5 +719,5 @@
///
/// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predNode() and \predMap().
+ /// tree used in \ref predNode() and \ref predMap().
///
/// \pre Either \ref run() or \ref init() must be called before
@@ -734,5 +734,5 @@
///
/// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predArc() and \predMap().
+ /// tree used in \ref predArc() and \ref predMap().
///
/// \pre Either \ref run() or \ref init() must be called before
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 764)
+++ lemon/bfs.h (revision 835)
@@ -64,5 +64,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -702,10 +702,6 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %BFS algorithm in order to
- ///compute the shortest path to each node.
- ///
- ///The algorithm computes
- ///- the shortest path tree (forest),
- ///- the distance of each node from the root(s).
+ ///This method runs the %BFS algorithm in order to visit all nodes
+ ///in the digraph.
///
///\note `b.run(s)` is just a shortcut of the following code.
@@ -853,5 +849,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -1047,6 +1043,6 @@
///Runs BFS algorithm to visit all nodes in the digraph.
- ///This method runs BFS algorithm in order to compute
- ///the shortest path to each node.
+ ///This method runs BFS algorithm in order to visit all nodes
+ ///in the digraph.
void run()
{
@@ -1696,10 +1692,6 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
///
- /// This method runs the %BFS algorithm in order to
- /// compute the shortest path to each node.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
+ /// This method runs the %BFS algorithm in order to visit all nodes
+ /// in the digraph.
///
/// \note `b.run(s)` is just a shortcut of the following code.
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h (revision 762)
+++ lemon/circulation.h (revision 833)
@@ -307,5 +307,5 @@
/// able to automatically created by the algorithm (i.e. the
/// digraph and the maximum level should be passed to it).
- /// However an external elevator object could also be passed to the
+ /// However, an external elevator object could also be passed to the
/// algorithm with the \ref elevator(Elevator&) "elevator()" function
/// before calling \ref run() or \ref init().
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 781)
+++ lemon/concepts/digraph.h (revision 833)
@@ -108,5 +108,5 @@
/// This iterator goes through each node of the 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 nodes in a digraph \c g of type \c %Digraph like this:
///\code
@@ -197,5 +197,5 @@
/// 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.
@@ -242,5 +242,5 @@
/// 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
+ /// 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.
@@ -286,5 +286,5 @@
/// This iterator goes through each arc of the 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 arcs in a digraph \c g of type \c %Digraph as follows:
///\code
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 781)
+++ lemon/concepts/graph.h (revision 833)
@@ -141,5 +141,5 @@
/// This iterator goes through each node of the graph.
- /// 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 nodes in a graph \c g of type \c %Graph like this:
///\code
@@ -229,5 +229,5 @@
/// This iterator goes through each edge of the graph.
- /// 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 edges in a graph \c g of type \c %Graph as follows:
///\code
@@ -273,5 +273,5 @@
/// 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
+ /// 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.
@@ -370,5 +370,5 @@
/// This iterator goes through each directed arc of the graph.
- /// 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 arcs in a graph \c g of type \c %Graph as follows:
///\code
@@ -414,5 +414,5 @@
/// 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
+ /// 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.
@@ -462,5 +462,5 @@
/// 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
+ /// 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.
@@ -588,5 +588,5 @@
/// Returns the first node of the given edge.
///
- /// Edges don't have source and target nodes, however methods
+ /// Edges don't have source and target nodes, however, methods
/// u() and v() are used to query the two end-nodes of an edge.
/// The orientation of an edge that arises this way is called
@@ -601,5 +601,5 @@
/// Returns the second node of the given edge.
///
- /// Edges don't have source and target nodes, however methods
+ /// Edges don't have source and target nodes, however, methods
/// u() and v() are used to query the two end-nodes of an edge.
/// The orientation of an edge that arises this way is called
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 781)
+++ lemon/concepts/graph_components.h (revision 833)
@@ -19,5 +19,5 @@
///\ingroup graph_concepts
///\file
-///\brief The concept of graph components.
+///\brief The concepts of graph components.
#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 606)
+++ lemon/concepts/path.h (revision 832)
@@ -19,5 +19,5 @@
///\ingroup concept
///\file
-///\brief Classes for representing paths in digraphs.
+///\brief The concept of paths
///
@@ -39,11 +39,20 @@
/// 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 {
@@ -60,9 +69,9 @@
Path() {}
- /// \brief Template constructor
+ /// \brief Template copy constructor
template
Path(const CPath& cpath) {}
- /// \brief Template assigment
+ /// \brief Template assigment operator
template
Path& operator=(const CPath& cpath) {
@@ -71,5 +80,5 @@
}
- /// Length of the path ie. the number of arcs in the path.
+ /// Length of the path, i.e. the number of arcs on the path.
int length() const { return 0;}
@@ -80,7 +89,7 @@
void clear() {}
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator for enumerating the arcs of a path.
///
- /// This class is used to iterate on the arcs of the paths.
+ /// LEMON style iterator class for enumerating the arcs of a path.
class ArcIt {
public:
@@ -89,8 +98,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the first arc of the given path
ArcIt(const Path &) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
@@ -193,22 +202,16 @@
///
/// A skeleton structure for path dumpers. The path dumpers are
- /// 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 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 main purpose of this concept is that the shortest path
- /// 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
+ /// 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
/// 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 {
@@ -220,5 +223,5 @@
typedef typename Digraph::Arc Arc;
- /// Length of the path ie. the number of arcs in the path.
+ /// Length of the path, i.e. the number of arcs on the path.
int length() const { return 0;}
@@ -228,13 +231,12 @@
/// \brief Forward or reverse dumping
///
- /// 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.
+ /// 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.
typedef False RevPathTag;
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator for enumerating the arcs of a path.
///
- /// This class is used to iterate on the arcs of the paths.
+ /// LEMON style iterator class for enumerating the arcs of a path.
class ArcIt {
public:
@@ -243,8 +245,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the first arc of the given path
ArcIt(const PathDumper&) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
@@ -261,8 +263,9 @@
};
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator 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.
+ /// LEMON style iterator class for enumerating the arcs of a path
+ /// in reverse direction.
class RevArcIt {
public:
@@ -271,8 +274,8 @@
/// Invalid constructor
RevArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the last arc of the given path
RevArcIt(const PathDumper &) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
Index: lemon/counter.h
===================================================================
--- lemon/counter.h (revision 463)
+++ lemon/counter.h (revision 833)
@@ -213,5 +213,5 @@
/// 'Do nothing' version of Counter.
- /// This class can be used in the same way as \ref Counter however it
+ /// This class can be used in the same way as \ref Counter, but it
/// does not count at all and does not print report on destruction.
///
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h (revision 764)
+++ lemon/dfs.h (revision 835)
@@ -64,5 +64,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -634,10 +634,6 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %DFS algorithm in order to compute the
- ///%DFS path to each node.
- ///
- ///The algorithm computes
- ///- the %DFS tree (forest),
- ///- the distance of each node from the root(s) in the %DFS tree.
+ ///This method runs the %DFS algorithm in order to visit all nodes
+ ///in the digraph.
///
///\note `d.run()` is just a shortcut of the following code.
@@ -783,5 +779,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -977,6 +973,6 @@
///Runs DFS algorithm to visit all nodes in the digraph.
- ///This method runs DFS algorithm in order to compute
- ///the DFS path to each node.
+ ///This method runs DFS algorithm in order to visit all nodes
+ ///in the digraph.
void run()
{
@@ -1579,10 +1575,6 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
- /// This method runs the %DFS algorithm in order to
- /// compute the %DFS path to each node.
- ///
- /// The algorithm computes
- /// - the %DFS tree (forest),
- /// - the distance of each node from the root(s) in the %DFS tree.
+ /// This method runs the %DFS algorithm in order to visit all nodes
+ /// in the digraph.
///
/// \note `d.run()` is just a shortcut of the following code.
Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h (revision 764)
+++ lemon/dijkstra.h (revision 835)
@@ -133,5 +133,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -207,5 +207,5 @@
///The type of the arc lengths.
- typedef typename TR::LengthMap::Value Value;
+ typedef typename TR::Value Value;
///The type of the map that stores the arc lengths.
typedef typename TR::LengthMap LengthMap;
@@ -427,5 +427,5 @@
///passed to the constructor of the cross reference and the cross
///reference should be passed to the constructor of the heap).
- ///However external heap and cross reference objects could also be
+ ///However, external heap and cross reference objects could also be
///passed to the algorithm using the \ref heap() function before
///calling \ref run(Node) "run()" or \ref init().
@@ -448,5 +448,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c OperationTraits type.
- /// For more information see \ref DijkstraDefaultOperationTraits.
+ /// For more information, see \ref DijkstraDefaultOperationTraits.
template
struct SetOperationTraits
@@ -997,5 +997,5 @@
///The type of the map that indicates which nodes are processed.
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
Index: lemon/edge_set.h
===================================================================
--- lemon/edge_set.h (revision 825)
+++ lemon/edge_set.h (revision 834)
@@ -256,11 +256,12 @@
/// all arcs incident to the given node is erased from the arc set.
///
+ /// This class fully conforms to the \ref concepts::Digraph
+ /// "Digraph" concept.
+ /// It provides only linear time counting for nodes and arcs.
+ ///
/// \param GR The type of the graph which shares its node set with
/// this class. Its interface must conform to the
/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
/// concept.
- ///
- /// This class fully conforms to the \ref concepts::Digraph
- /// "Digraph" concept.
template
class ListArcSet : public ArcSetExtender > {
@@ -686,10 +687,11 @@
/// incident to the given node is erased from the arc set.
///
+ /// This class fully conforms to the \ref concepts::Graph "Graph"
+ /// concept.
+ /// It provides only linear time counting for nodes, edges and arcs.
+ ///
/// \param GR The type of the graph which shares its node set
/// with this class. Its interface must conform to the
/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
- /// concept.
- ///
- /// This class fully conforms to the \ref concepts::Graph "Graph"
/// concept.
template
@@ -955,11 +957,12 @@
/// arcs. Therefore the arcs cannot be erased from the arc sets.
///
+ /// This class fully conforms to the \ref concepts::Digraph "Digraph"
+ /// concept.
+ /// It provides only linear time counting for nodes and arcs.
+ ///
/// \warning If a node is erased from the underlying graph and this
/// node is the source or target of one arc in the arc set, then
/// the arc set is invalidated, and it cannot be used anymore. The
/// validity can be checked with the \c valid() member function.
- ///
- /// This class fully conforms to the \ref concepts::Digraph
- /// "Digraph" concept.
template
class SmartArcSet : public ArcSetExtender > {
@@ -1305,11 +1308,12 @@
/// edges cannot be erased from the edge sets.
///
+ /// This class fully conforms to the \ref concepts::Graph "Graph"
+ /// concept.
+ /// It provides only linear time counting for nodes, edges and arcs.
+ ///
/// \warning If a node is erased from the underlying graph and this
/// node is incident to one edge in the edge set, then the edge set
/// is invalidated, and it cannot be used anymore. The validity can
/// be checked with the \c valid() member function.
- ///
- /// This class fully conforms to the \ref concepts::Graph
- /// "Graph" concept.
template
class SmartEdgeSet : public EdgeSetExtender > {
Index: lemon/full_graph.h
===================================================================
--- lemon/full_graph.h (revision 827)
+++ lemon/full_graph.h (revision 834)
@@ -163,4 +163,6 @@
/// only in the concept class.
///
+ /// This class provides constant time counting for nodes and arcs.
+ ///
/// \note FullDigraph and FullGraph classes are very similar,
/// but there are two differences. While this class conforms only
@@ -205,4 +207,5 @@
/// completely static, the nodes can be indexed with integers from
/// the range `[0..nodeNum()-1]`.
+ /// The index of a node is the same as its ID.
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -213,4 +216,5 @@
/// completely static, the nodes can be indexed with integers from
/// the range `[0..nodeNum()-1]`.
+ /// The index of a node is the same as its ID.
/// \sa operator()()
static int index(const Node& node) { return Parent::index(node); }
@@ -536,4 +540,6 @@
/// only in the concept class.
///
+ /// This class provides constant time counting for nodes, edges and arcs.
+ ///
/// \note FullDigraph and FullGraph classes are very similar,
/// but there are two differences. While FullDigraph
@@ -580,4 +586,5 @@
/// completely static, the nodes can be indexed with integers from
/// the range `[0..nodeNum()-1]`.
+ /// The index of a node is the same as its ID.
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -588,4 +595,5 @@
/// completely static, the nodes can be indexed with integers from
/// the range `[0..nodeNum()-1]`.
+ /// The index of a node is the same as its ID.
/// \sa operator()()
static int index(const Node& node) { return Parent::index(node); }
Index: lemon/gomory_hu.h
===================================================================
--- lemon/gomory_hu.h (revision 760)
+++ lemon/gomory_hu.h (revision 833)
@@ -295,9 +295,7 @@
/// \pre \ref run() must be called before using this function.
template
- Value minCutMap(const Node& s, ///<
+ Value minCutMap(const Node& s,
const Node& t,
- ///<
CutMap& cutMap
- ///<
) const {
Node sn = s, tn = t;
@@ -395,5 +393,5 @@
/// \endcode
/// does not necessarily give the same set of nodes.
- /// However it is ensured that
+ /// However, it is ensured that
/// \code
/// MinCutNodeIt(gomory, s, t, true);
Index: lemon/graph_to_eps.h
===================================================================
--- lemon/graph_to_eps.h (revision 664)
+++ lemon/graph_to_eps.h (revision 833)
@@ -143,5 +143,5 @@
///\param gr Reference to the graph to be printed.
///\param ost Reference to the output stream.
- ///By default it is `std::cout`.
+ ///By default, it is `std::cout`.
///\param pros If it is \c true, then the \c ostream referenced by \c os
///will be explicitly deallocated by the destructor.
@@ -513,5 +513,5 @@
///Turn on/off pre-scaling
- ///By default graphToEps() rescales the whole image in order to avoid
+ ///By default, graphToEps() rescales the whole image in order to avoid
///very big or very small bounding boxes.
///
@@ -1115,5 +1115,5 @@
///\param g Reference to the graph to be printed.
///\param os Reference to the output stream.
-///By default it is `std::cout`.
+///By default, it is `std::cout`.
///
///This function also has a lot of
@@ -1127,5 +1127,5 @@
///\endcode
///
-///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
+///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
///
///\warning Don't forget to put the \ref GraphToEps::run() "run()"
Index: lemon/grid_graph.h
===================================================================
--- lemon/grid_graph.h (revision 782)
+++ lemon/grid_graph.h (revision 834)
@@ -504,4 +504,6 @@
/// Most of its member functions and nested classes are documented
/// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes, edges and arcs.
class GridGraph : public ExtendedGridGraphBase {
typedef ExtendedGridGraphBase Parent;
Index: lemon/hypercube_graph.h
===================================================================
--- lemon/hypercube_graph.h (revision 827)
+++ lemon/hypercube_graph.h (revision 835)
@@ -288,5 +288,5 @@
/// differ only on one position in the binary form.
/// This class is completely static and it needs constant memory space.
- /// Thus you can neither add nor delete nodes or edges, however
+ /// Thus you can neither add nor delete nodes or edges, however,
/// the structure can be resized using resize().
///
@@ -294,4 +294,6 @@
/// Most of its member functions and nested classes are documented
/// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes, edges and arcs.
///
/// \note The type of the indices is chosen to \c int for efficiency
Index: lemon/lgf_reader.h
===================================================================
--- lemon/lgf_reader.h (revision 646)
+++ lemon/lgf_reader.h (revision 833)
@@ -428,5 +428,5 @@
///\endcode
///
- /// By default the reader uses the first section in the file of the
+ /// By default, the reader uses the first section in the file of the
/// proper type. If a section has an optional name, then it can be
/// selected for reading by giving an optional name parameter to the
@@ -2222,5 +2222,5 @@
/// whitespaces are trimmed from each processed string.
///
- /// For example let's see a section, which contain several
+ /// For example, let's see a section, which contain several
/// integers, which should be inserted into a vector.
///\code
Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h (revision 788)
+++ lemon/list_graph.h (revision 835)
@@ -325,4 +325,6 @@
///only in the concept class.
///
+ ///This class provides only linear time counting for nodes and arcs.
+ ///
///\sa concepts::Digraph
///\sa ListGraph
@@ -361,5 +363,9 @@
///\brief Erase a node from the digraph.
///
- ///This function erases the given node from the digraph.
+ ///This function erases the given node along with its outgoing and
+ ///incoming arcs from the digraph.
+ ///
+ ///\note All iterators referencing the removed node or the connected
+ ///arcs are invalidated, of course.
void erase(Node n) { Parent::erase(n); }
@@ -367,4 +373,7 @@
///
///This function erases the given arc from the digraph.
+ ///
+ ///\note All iterators referencing the removed arc are invalidated,
+ ///of course.
void erase(Arc a) { Parent::erase(a); }
@@ -392,5 +401,5 @@
///
///\note \c ArcIt and \c OutArcIt iterators referencing the changed
- ///arc remain valid, however \c InArcIt iterators are invalidated.
+ ///arc remain valid, but \c InArcIt iterators are invalidated.
///
///\warning This functionality cannot be used together with the Snapshot
@@ -404,5 +413,5 @@
///
///\note \c InArcIt iterators referencing the changed arc remain
- ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
+ ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
///
///\warning This functionality cannot be used together with the Snapshot
@@ -511,4 +520,5 @@
///This function erases all nodes and arcs from the digraph.
///
+ ///\note All iterators of the digraph are invalidated, of course.
void clear() {
Parent::clear();
@@ -550,5 +560,5 @@
/// reversing, contracting, splitting arcs or nodes) cannot be
/// restored. These events invalidate the snapshot.
- /// However the arcs and nodes that were added to the digraph after
+ /// However, the arcs and nodes that were added to the digraph after
/// making the current snapshot can be removed without invalidating it.
class Snapshot {
@@ -1180,4 +1190,6 @@
///only in the concept class.
///
+ ///This class provides only linear time counting for nodes, edges and arcs.
+ ///
///\sa concepts::Graph
///\sa ListDigraph
@@ -1218,5 +1230,9 @@
///\brief Erase a node from the graph.
///
- /// This function erases the given node from the graph.
+ /// This function erases the given node along with its incident arcs
+ /// from the graph.
+ ///
+ /// \note All iterators referencing the removed node or the incident
+ /// edges are invalidated, of course.
void erase(Node n) { Parent::erase(n); }
@@ -1224,4 +1240,7 @@
///
/// This function erases the given edge from the graph.
+ ///
+ /// \note All iterators referencing the removed edge are invalidated,
+ /// of course.
void erase(Edge e) { Parent::erase(e); }
/// Node validity check
@@ -1268,5 +1287,5 @@
///
///\note \c EdgeIt iterators referencing the changed edge remain
- ///valid, however \c ArcIt iterators referencing the changed edge and
+ ///valid, but \c ArcIt iterators referencing the changed edge and
///all other iterators whose base node is the changed node are also
///invalidated.
@@ -1313,4 +1332,5 @@
///This function erases all nodes and arcs from the graph.
///
+ ///\note All iterators of the graph are invalidated, of course.
void clear() {
Parent::clear();
@@ -1352,5 +1372,5 @@
/// (e.g. changing the end-nodes of edges or contracting nodes)
/// cannot be restored. These events invalidate the snapshot.
- /// However the edges and nodes that were added to the graph after
+ /// However, the edges and nodes that were added to the graph after
/// making the current snapshot can be removed without invalidating it.
class Snapshot {
Index: lemon/lp_base.h
===================================================================
--- lemon/lp_base.h (revision 793)
+++ lemon/lp_base.h (revision 833)
@@ -147,5 +147,5 @@
///Iterator for iterate over the columns of an LP problem
- /// 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 columns in an LP \c lp:
///\code
@@ -242,5 +242,5 @@
///Iterator for iterate over the rows of an LP problem
- /// 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 rows in an LP \c lp:
///\code
Index: lemon/maps.h
===================================================================
--- lemon/maps.h (revision 836)
+++ lemon/maps.h (revision 839)
@@ -231,8 +231,8 @@
/// This map is essentially a wrapper for \c std::vector. It assigns
/// values to integer keys from the range `[0..size-1]`.
- /// It can be used with some data structures, for example
- /// \c UnionFind, \c BinHeap, when the used items are small
+ /// It can be used together with some data structures, e.g.
+ /// heap types and \c UnionFind, when the used items are small
/// integers. This map conforms to the \ref concepts::ReferenceMap
- /// "ReferenceMap" concept.
+ /// "ReferenceMap" concept.
///
/// The simplest way of using this map is through the rangeMap()
@@ -349,7 +349,7 @@
/// The name of this type also refers to this important usage.
///
- /// Apart form that this map can be used in many other cases since it
+ /// Apart form that, this map can be used in many other cases since it
/// is based on \c std::map, which is a general associative container.
- /// However keep in mind that it is usually not as efficient as other
+ /// However, keep in mind that it is usually not as efficient as other
/// maps.
///
@@ -1786,5 +1786,5 @@
/// The most important usage of it is storing certain nodes or arcs
/// that were marked \c true by an algorithm.
- /// For example it makes easier to store the nodes in the processing
+ /// For example, it makes easier to store the nodes in the processing
/// order of Dfs algorithm, as the following examples show.
/// \code
@@ -1801,5 +1801,5 @@
///
/// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
- /// it cannot be used when a readable map is needed, for example as
+ /// it cannot be used when a readable map is needed, for example, as
/// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
///
@@ -1923,5 +1923,5 @@
/// Otherwise consider to use \c IterableValueMap, which is more
/// suitable and more efficient for such cases. It provides iterators
- /// to traverse the items with the same associated value, however
+ /// to traverse the items with the same associated value, but
/// it does not have \c InverseMap.
///
@@ -3467,5 +3467,5 @@
/// may provide alternative ways to modify the digraph.
/// The correct behavior of InDegMap is not guarantied if these additional
- /// features are used. For example the functions
+ /// features are used. For example, the functions
/// \ref ListDigraph::changeSource() "changeSource()",
/// \ref ListDigraph::changeTarget() "changeTarget()" and
@@ -3597,5 +3597,5 @@
/// may provide alternative ways to modify the digraph.
/// The correct behavior of OutDegMap is not guarantied if these additional
- /// features are used. For example the functions
+ /// features are used. For example, the functions
/// \ref ListDigraph::changeSource() "changeSource()",
/// \ref ListDigraph::changeTarget() "changeTarget()" and
Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h (revision 802)
+++ lemon/network_simplex.h (revision 835)
@@ -51,5 +51,5 @@
/// in LEMON for the minimum cost flow problem.
/// Moreover it supports both directions of the supply/demand inequality
- /// constraints. For more information see \ref SupplyType.
+ /// constraints. For more information, see \ref SupplyType.
///
/// Most of the parameters of the problem (except for the digraph)
@@ -60,7 +60,7 @@
/// \tparam GR The digraph type the algorithm runs on.
/// \tparam V The value type used for flow amounts, capacity bounds
- /// and supply values in the algorithm. By default it is \c int.
+ /// and supply values in the algorithm. By default, it is \c int.
/// \tparam C The value type used for costs and potentials in the
- /// algorithm. By default it is the same as \c V.
+ /// algorithm. By default, it is the same as \c V.
///
/// \warning Both value types must be signed and all input data must
@@ -69,5 +69,5 @@
/// \note %NetworkSimplex provides five different pivot rule
/// implementations, from which the most efficient one is used
- /// by default. For more information see \ref PivotRule.
+ /// by default. For more information, see \ref PivotRule.
template
class NetworkSimplex
@@ -125,21 +125,21 @@
/// implementations that significantly affect the running time
/// of the algorithm.
- /// By default \ref BLOCK_SEARCH "Block Search" is used, which
+ /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
/// proved to be the most efficient and the most robust on various
/// test inputs according to our benchmark tests.
- /// However another pivot rule can be selected using the \ref run()
+ /// However, another pivot rule can be selected using the \ref run()
/// function with the proper parameter.
enum PivotRule {
- /// The First Eligible pivot rule.
+ /// The \e First \e Eligible pivot rule.
/// The next eligible arc is selected in a wraparound fashion
/// in every iteration.
FIRST_ELIGIBLE,
- /// The Best Eligible pivot rule.
+ /// The \e Best \e Eligible pivot rule.
/// The best eligible arc is selected in every iteration.
BEST_ELIGIBLE,
- /// The Block Search pivot rule.
+ /// The \e Block \e Search pivot rule.
/// A specified number of arcs are examined in every iteration
/// in a wraparound fashion and the best eligible arc is selected
@@ -147,5 +147,5 @@
BLOCK_SEARCH,
- /// The Candidate List pivot rule.
+ /// The \e Candidate \e List pivot rule.
/// In a major iteration a candidate list is built from eligible arcs
/// in a wraparound fashion and in the following minor iterations
@@ -153,5 +153,5 @@
CANDIDATE_LIST,
- /// The Altering Candidate List pivot rule.
+ /// The \e Altering \e Candidate \e List pivot rule.
/// It is a modified version of the Candidate List method.
/// It keeps only the several best eligible arcs from the former
@@ -813,5 +813,5 @@
/// type will be used.
///
- /// For more information see \ref SupplyType.
+ /// For more information, see \ref SupplyType.
///
/// \return `(*this)`
@@ -845,9 +845,9 @@
/// \ref reset() is called, thus only the modified parameters
/// have to be set again. See \ref reset() for examples.
- /// However the underlying digraph must not be modified after this
+ /// However, the underlying digraph must not be modified after this
/// class have been constructed, since it copies and extends the graph.
///
/// \param pivot_rule The pivot rule that will be used during the
- /// algorithm. For more information see \ref PivotRule.
+ /// algorithm. For more information, see \ref PivotRule.
///
/// \return \c INFEASIBLE if no feasible flow exists,
@@ -874,5 +874,5 @@
/// used, all the parameters given before are kept for the next
/// \ref run() call.
- /// However the underlying digraph must not be modified after this
+ /// However, the underlying digraph must not be modified after this
/// class have been constructed, since it copies and extends the graph.
///
Index: lemon/preflow.h
===================================================================
--- lemon/preflow.h (revision 802)
+++ lemon/preflow.h (revision 835)
@@ -266,5 +266,5 @@
/// able to automatically created by the algorithm (i.e. the
/// digraph and the maximum level should be passed to it).
- /// However an external elevator object could also be passed to the
+ /// However, an external elevator object could also be passed to the
/// algorithm with the \ref elevator(Elevator&) "elevator()" function
/// before calling \ref run() or \ref init().
Index: lemon/smart_graph.h
===================================================================
--- lemon/smart_graph.h (revision 827)
+++ lemon/smart_graph.h (revision 834)
@@ -195,4 +195,6 @@
///only in the concept class.
///
+ ///This class provides constant time counting for nodes and arcs.
+ ///
///\sa concepts::Digraph
///\sa SmartGraph
@@ -621,4 +623,6 @@
/// only in the concept class.
///
+ /// This class provides constant time counting for nodes, edges and arcs.
+ ///
/// \sa concepts::Graph
/// \sa SmartDigraph
Index: lemon/static_graph.h
===================================================================
--- lemon/static_graph.h (revision 826)
+++ lemon/static_graph.h (revision 834)
@@ -293,4 +293,6 @@
/// only in the concept class.
///
+ /// This class provides constant time counting for nodes and arcs.
+ ///
/// \sa concepts::Digraph
class StaticDigraph : public ExtendedStaticDigraphBase {
Index: lemon/time_measure.h
===================================================================
--- lemon/time_measure.h (revision 631)
+++ lemon/time_measure.h (revision 833)
@@ -376,5 +376,5 @@
///This function returns the number of stop() exections that is
///necessary to really stop the timer.
- ///For example the timer
+ ///For example, the timer
///is running if and only if the return value is \c true
///(i.e. greater than
Index: lemon/unionfind.h
===================================================================
--- lemon/unionfind.h (revision 606)
+++ lemon/unionfind.h (revision 833)
@@ -44,5 +44,5 @@
/// This is a very simple but efficient implementation, providing
/// only four methods: join (union), find, insert and size.
- /// For more features see the \ref UnionFindEnum class.
+ /// For more features, see the \ref UnionFindEnum class.
///
/// It is primarily used in Kruskal algorithm for finding minimal