# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 2009-11-15 19:57:02
# Node ID c2230649a493e6fd8f19a16372e9fade832c63d5
# Parent  1a7fe3bef5144989cc90fe53f4f0a23337fc493f

Various doc improvements (#331)

 - Add notes to the graph classes about the time of
   item counting.
 - Clarify the doc for run() in BFS and DFS.
 - Other improvements.

diff --git a/lemon/adaptors.h b/lemon/adaptors.h
--- a/lemon/adaptors.h
+++ b/lemon/adaptors.h
@@ -360,6 +360,9 @@
   /// 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
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -719,6 +722,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -1314,6 +1319,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Graph "Graph" concept.
   /// It can also be specified to be \c const.
@@ -1471,6 +1478,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept
   /// or the \ref concepts::Graph "Graph" concept.
@@ -1619,6 +1628,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -1729,6 +1740,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Graph "Graph" concept.
   /// It can also be specified to be \c const.
@@ -2232,6 +2245,9 @@
   /// by adding or removing nodes or edges, unless the \c GR template
   /// 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.
   /// It can also be specified to be \c const.
@@ -2535,6 +2551,9 @@
   /// 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.
   /// It must conform to the \ref concepts::Graph "Graph" concept.
   /// It can also be specified to be \c const.
@@ -2678,6 +2697,8 @@
   /// 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.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It is implicitly \c const.
@@ -3325,6 +3346,9 @@
   /// costs/capacities of the original digraph to the \e bind \e arcs
   /// 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.
   /// It is implicitly \c const.
diff --git a/lemon/bfs.h b/lemon/bfs.h
--- a/lemon/bfs.h
+++ b/lemon/bfs.h
@@ -701,12 +701,8 @@
 
     ///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 <tt>b.run(s)</tt> is just a shortcut of the following code.
     ///\code
@@ -1046,8 +1042,8 @@
 
     ///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()
     {
       run(INVALID);
@@ -1695,12 +1691,8 @@
 
     /// \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 <tt>b.run(s)</tt> is just a shortcut of the following code.
     ///\code
diff --git a/lemon/dfs.h b/lemon/dfs.h
--- a/lemon/dfs.h
+++ b/lemon/dfs.h
@@ -633,12 +633,8 @@
 
     ///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 <tt>d.run()</tt> is just a shortcut of the following code.
     ///\code
@@ -976,8 +972,8 @@
 
     ///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()
     {
       run(INVALID);
@@ -1578,12 +1574,8 @@
 
     /// \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 <tt>d.run()</tt> is just a shortcut of the following code.
     ///\code
diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h
--- a/lemon/dijkstra.h
+++ b/lemon/dijkstra.h
@@ -206,7 +206,7 @@
     typedef typename TR::Digraph Digraph;
 
     ///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;
     ///\brief The type of the map that stores the predecessor arcs of the
diff --git a/lemon/edge_set.h b/lemon/edge_set.h
--- a/lemon/edge_set.h
+++ b/lemon/edge_set.h
@@ -255,13 +255,14 @@
   /// that node can be removed from the underlying graph, in this case
   /// 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 <typename GR>
   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
@@ -685,13 +686,14 @@
   /// be removed from the underlying graph, in this case all edges
   /// 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 <typename GR>
   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
@@ -954,13 +956,14 @@
   /// single-linked lists for enumerate outgoing and incoming
   /// 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 <typename GR>
   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
@@ -1304,13 +1307,14 @@
   /// single-linked lists for enumerate incident edges. Therefore the
   /// 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 <typename GR>
   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
diff --git a/lemon/full_graph.h b/lemon/full_graph.h
--- a/lemon/full_graph.h
+++ b/lemon/full_graph.h
@@ -162,6 +162,8 @@
   /// Most of its member functions and nested classes are documented
   /// 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
   /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
@@ -204,6 +206,7 @@
     /// Returns the node with the given index. Since this structure is 
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
 
@@ -212,6 +215,7 @@
     /// Returns the index of the given node. Since this structure is 
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa operator()()
     static int index(const Node& node) { return Parent::index(node); }
 
@@ -535,6 +539,8 @@
   /// 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 FullDigraph and FullGraph classes are very similar,
   /// but there are two differences. While FullDigraph
   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
@@ -579,6 +585,7 @@
     /// Returns the node with the given index. Since this structure is 
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
 
@@ -587,6 +594,7 @@
     /// Returns the index of the given node. Since this structure is 
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa operator()()
     static int index(const Node& node) { return Parent::index(node); }
 
diff --git a/lemon/grid_graph.h b/lemon/grid_graph.h
--- a/lemon/grid_graph.h
+++ b/lemon/grid_graph.h
@@ -503,6 +503,8 @@
   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   /// 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;
 
diff --git a/lemon/hypercube_graph.h b/lemon/hypercube_graph.h
--- a/lemon/hypercube_graph.h
+++ b/lemon/hypercube_graph.h
@@ -294,6 +294,8 @@
   /// 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
   /// reasons. Thus the maximum dimension of this implementation is 26
   /// (assuming that the size of \c int is 32 bit).
diff --git a/lemon/list_graph.h b/lemon/list_graph.h
--- a/lemon/list_graph.h
+++ b/lemon/list_graph.h
@@ -324,6 +324,8 @@
   ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes and arcs.
+  ///
   ///\sa concepts::Digraph
   ///\sa ListGraph
   class ListDigraph : public ExtendedListDigraphBase {
@@ -360,12 +362,19 @@
 
     ///\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); }
 
     ///\brief Erase an arc from the digraph.
     ///
     ///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); }
 
     /// Node validity check
@@ -510,6 +519,7 @@
 
     ///This function erases all nodes and arcs from the digraph.
     ///
+    ///\note All iterators of the digraph are invalidated, of course.
     void clear() {
       Parent::clear();
     }
@@ -1179,6 +1189,8 @@
   ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes, edges and arcs.
+  ///
   ///\sa concepts::Graph
   ///\sa ListDigraph
   class ListGraph : public ExtendedListGraphBase {
@@ -1217,12 +1229,19 @@
 
     ///\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); }
 
     ///\brief Erase an edge from the graph.
     ///
     /// 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
 
@@ -1312,6 +1331,7 @@
 
     ///This function erases all nodes and arcs from the graph.
     ///
+    ///\note All iterators of the graph are invalidated, of course.
     void clear() {
       Parent::clear();
     }
diff --git a/lemon/smart_graph.h b/lemon/smart_graph.h
--- a/lemon/smart_graph.h
+++ b/lemon/smart_graph.h
@@ -194,6 +194,8 @@
   ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
+  ///This class provides constant time counting for nodes and arcs.
+  ///
   ///\sa concepts::Digraph
   ///\sa SmartGraph
   class SmartDigraph : public ExtendedSmartDigraphBase {
@@ -620,6 +622,8 @@
   /// 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.
+  ///
   /// \sa concepts::Graph
   /// \sa SmartDigraph
   class SmartGraph : public ExtendedSmartGraphBase {
diff --git a/lemon/static_graph.h b/lemon/static_graph.h
--- a/lemon/static_graph.h
+++ b/lemon/static_graph.h
@@ -292,6 +292,8 @@
   /// Most of its member functions and nested classes are documented
   /// only in the concept class.
   ///
+  /// This class provides constant time counting for nodes and arcs.
+  ///
   /// \sa concepts::Digraph
   class StaticDigraph : public ExtendedStaticDigraphBase {
   public: