Various doc improvements (#331)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Nov 2009 19:57:02 +0100
changeset 834c2230649a493
parent 831 1a7fe3bef514
child 835 c92296660262
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.
lemon/adaptors.h
lemon/bfs.h
lemon/dfs.h
lemon/dijkstra.h
lemon/edge_set.h
lemon/full_graph.h
lemon/grid_graph.h
lemon/hypercube_graph.h
lemon/list_graph.h
lemon/smart_graph.h
lemon/static_graph.h
     1.1 --- a/lemon/adaptors.h	Thu Nov 05 15:50:01 2009 +0100
     1.2 +++ b/lemon/adaptors.h	Sun Nov 15 19:57:02 2009 +0100
     1.3 @@ -360,6 +360,9 @@
     1.4    /// by adding or removing nodes or arcs, unless the \c GR template
     1.5    /// parameter is set to be \c const.
     1.6    ///
     1.7 +  /// This class provides item counting in the same time as the adapted
     1.8 +  /// digraph structure.
     1.9 +  ///
    1.10    /// \tparam DGR The type of the adapted digraph.
    1.11    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.12    /// It can also be specified to be \c const.
    1.13 @@ -719,6 +722,8 @@
    1.14    /// by adding or removing nodes or arcs, unless the \c GR template
    1.15    /// parameter is set to be \c const.
    1.16    ///
    1.17 +  /// This class provides only linear time counting for nodes and arcs.
    1.18 +  ///
    1.19    /// \tparam DGR The type of the adapted digraph.
    1.20    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.21    /// It can also be specified to be \c const.
    1.22 @@ -1314,6 +1319,8 @@
    1.23    /// by adding or removing nodes or edges, unless the \c GR template
    1.24    /// parameter is set to be \c const.
    1.25    ///
    1.26 +  /// This class provides only linear time counting for nodes, edges and arcs.
    1.27 +  ///
    1.28    /// \tparam GR The type of the adapted graph.
    1.29    /// It must conform to the \ref concepts::Graph "Graph" concept.
    1.30    /// It can also be specified to be \c const.
    1.31 @@ -1471,6 +1478,8 @@
    1.32    /// by adding or removing nodes or arcs/edges, unless the \c GR template
    1.33    /// parameter is set to be \c const.
    1.34    ///
    1.35 +  /// This class provides only linear time item counting.
    1.36 +  ///
    1.37    /// \tparam GR The type of the adapted digraph or graph.
    1.38    /// It must conform to the \ref concepts::Digraph "Digraph" concept
    1.39    /// or the \ref concepts::Graph "Graph" concept.
    1.40 @@ -1619,6 +1628,8 @@
    1.41    /// by adding or removing nodes or arcs, unless the \c GR template
    1.42    /// parameter is set to be \c const.
    1.43    ///
    1.44 +  /// This class provides only linear time counting for nodes and arcs.
    1.45 +  ///
    1.46    /// \tparam DGR The type of the adapted digraph.
    1.47    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.48    /// It can also be specified to be \c const.
    1.49 @@ -1729,6 +1740,8 @@
    1.50    /// by adding or removing nodes or edges, unless the \c GR template
    1.51    /// parameter is set to be \c const.
    1.52    ///
    1.53 +  /// This class provides only linear time counting for nodes, edges and arcs.
    1.54 +  ///
    1.55    /// \tparam GR The type of the adapted graph.
    1.56    /// It must conform to the \ref concepts::Graph "Graph" concept.
    1.57    /// It can also be specified to be \c const.
    1.58 @@ -2232,6 +2245,9 @@
    1.59    /// by adding or removing nodes or edges, unless the \c GR template
    1.60    /// parameter is set to be \c const.
    1.61    ///
    1.62 +  /// This class provides item counting in the same time as the adapted
    1.63 +  /// digraph structure.
    1.64 +  ///
    1.65    /// \tparam DGR The type of the adapted digraph.
    1.66    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.67    /// It can also be specified to be \c const.
    1.68 @@ -2535,6 +2551,9 @@
    1.69    /// by adding or removing nodes or arcs, unless the \c GR template
    1.70    /// parameter is set to be \c const.
    1.71    ///
    1.72 +  /// This class provides item counting in the same time as the adapted
    1.73 +  /// graph structure.
    1.74 +  ///
    1.75    /// \tparam GR The type of the adapted graph.
    1.76    /// It must conform to the \ref concepts::Graph "Graph" concept.
    1.77    /// It can also be specified to be \c const.
    1.78 @@ -2678,6 +2697,8 @@
    1.79    /// arcs).
    1.80    /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    1.81    ///
    1.82 +  /// This class provides only linear time counting for nodes and arcs.
    1.83 +  ///
    1.84    /// \tparam DGR The type of the adapted digraph.
    1.85    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.86    /// It is implicitly \c const.
    1.87 @@ -3325,6 +3346,9 @@
    1.88    /// costs/capacities of the original digraph to the \e bind \e arcs
    1.89    /// in the adaptor.
    1.90    ///
    1.91 +  /// This class provides item counting in the same time as the adapted
    1.92 +  /// digraph structure.
    1.93 +  ///
    1.94    /// \tparam DGR The type of the adapted digraph.
    1.95    /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1.96    /// It is implicitly \c const.
     2.1 --- a/lemon/bfs.h	Thu Nov 05 15:50:01 2009 +0100
     2.2 +++ b/lemon/bfs.h	Sun Nov 15 19:57:02 2009 +0100
     2.3 @@ -701,12 +701,8 @@
     2.4  
     2.5      ///Runs the algorithm to visit all nodes in the digraph.
     2.6  
     2.7 -    ///This method runs the %BFS algorithm in order to
     2.8 -    ///compute the shortest path to each node.
     2.9 -    ///
    2.10 -    ///The algorithm computes
    2.11 -    ///- the shortest path tree (forest),
    2.12 -    ///- the distance of each node from the root(s).
    2.13 +    ///This method runs the %BFS algorithm in order to visit all nodes
    2.14 +    ///in the digraph.
    2.15      ///
    2.16      ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    2.17      ///\code
    2.18 @@ -1046,8 +1042,8 @@
    2.19  
    2.20      ///Runs BFS algorithm to visit all nodes in the digraph.
    2.21  
    2.22 -    ///This method runs BFS algorithm in order to compute
    2.23 -    ///the shortest path to each node.
    2.24 +    ///This method runs BFS algorithm in order to visit all nodes
    2.25 +    ///in the digraph.
    2.26      void run()
    2.27      {
    2.28        run(INVALID);
    2.29 @@ -1695,12 +1691,8 @@
    2.30  
    2.31      /// \brief Runs the algorithm to visit all nodes in the digraph.
    2.32      ///
    2.33 -    /// This method runs the %BFS algorithm in order to
    2.34 -    /// compute the shortest path to each node.
    2.35 -    ///
    2.36 -    /// The algorithm computes
    2.37 -    /// - the shortest path tree (forest),
    2.38 -    /// - the distance of each node from the root(s).
    2.39 +    /// This method runs the %BFS algorithm in order to visit all nodes
    2.40 +    /// in the digraph.
    2.41      ///
    2.42      /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    2.43      ///\code
     3.1 --- a/lemon/dfs.h	Thu Nov 05 15:50:01 2009 +0100
     3.2 +++ b/lemon/dfs.h	Sun Nov 15 19:57:02 2009 +0100
     3.3 @@ -633,12 +633,8 @@
     3.4  
     3.5      ///Runs the algorithm to visit all nodes in the digraph.
     3.6  
     3.7 -    ///This method runs the %DFS algorithm in order to compute the
     3.8 -    ///%DFS path to each node.
     3.9 -    ///
    3.10 -    ///The algorithm computes
    3.11 -    ///- the %DFS tree (forest),
    3.12 -    ///- the distance of each node from the root(s) in the %DFS tree.
    3.13 +    ///This method runs the %DFS algorithm in order to visit all nodes
    3.14 +    ///in the digraph.
    3.15      ///
    3.16      ///\note <tt>d.run()</tt> is just a shortcut of the following code.
    3.17      ///\code
    3.18 @@ -976,8 +972,8 @@
    3.19  
    3.20      ///Runs DFS algorithm to visit all nodes in the digraph.
    3.21  
    3.22 -    ///This method runs DFS algorithm in order to compute
    3.23 -    ///the DFS path to each node.
    3.24 +    ///This method runs DFS algorithm in order to visit all nodes
    3.25 +    ///in the digraph.
    3.26      void run()
    3.27      {
    3.28        run(INVALID);
    3.29 @@ -1578,12 +1574,8 @@
    3.30  
    3.31      /// \brief Runs the algorithm to visit all nodes in the digraph.
    3.32  
    3.33 -    /// This method runs the %DFS algorithm in order to
    3.34 -    /// compute the %DFS path to each node.
    3.35 -    ///
    3.36 -    /// The algorithm computes
    3.37 -    /// - the %DFS tree (forest),
    3.38 -    /// - the distance of each node from the root(s) in the %DFS tree.
    3.39 +    /// This method runs the %DFS algorithm in order to visit all nodes
    3.40 +    /// in the digraph.
    3.41      ///
    3.42      /// \note <tt>d.run()</tt> is just a shortcut of the following code.
    3.43      ///\code
     4.1 --- a/lemon/dijkstra.h	Thu Nov 05 15:50:01 2009 +0100
     4.2 +++ b/lemon/dijkstra.h	Sun Nov 15 19:57:02 2009 +0100
     4.3 @@ -206,7 +206,7 @@
     4.4      typedef typename TR::Digraph Digraph;
     4.5  
     4.6      ///The type of the arc lengths.
     4.7 -    typedef typename TR::LengthMap::Value Value;
     4.8 +    typedef typename TR::Value Value;
     4.9      ///The type of the map that stores the arc lengths.
    4.10      typedef typename TR::LengthMap LengthMap;
    4.11      ///\brief The type of the map that stores the predecessor arcs of the
     5.1 --- a/lemon/edge_set.h	Thu Nov 05 15:50:01 2009 +0100
     5.2 +++ b/lemon/edge_set.h	Sun Nov 15 19:57:02 2009 +0100
     5.3 @@ -255,13 +255,14 @@
     5.4    /// that node can be removed from the underlying graph, in this case
     5.5    /// all arcs incident to the given node is erased from the arc set.
     5.6    ///
     5.7 +  /// This class fully conforms to the \ref concepts::Digraph
     5.8 +  /// "Digraph" concept.
     5.9 +  /// It provides only linear time counting for nodes and arcs.
    5.10 +  ///
    5.11    /// \param GR The type of the graph which shares its node set with
    5.12    /// this class. Its interface must conform to the
    5.13    /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    5.14    /// concept.
    5.15 -  ///
    5.16 -  /// This class fully conforms to the \ref concepts::Digraph
    5.17 -  /// "Digraph" concept.
    5.18    template <typename GR>
    5.19    class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
    5.20      typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
    5.21 @@ -685,13 +686,14 @@
    5.22    /// be removed from the underlying graph, in this case all edges
    5.23    /// incident to the given node is erased from the arc set.
    5.24    ///
    5.25 +  /// This class fully conforms to the \ref concepts::Graph "Graph"
    5.26 +  /// concept.
    5.27 +  /// It provides only linear time counting for nodes, edges and arcs.
    5.28 +  ///
    5.29    /// \param GR The type of the graph which shares its node set
    5.30    /// with this class. Its interface must conform to the
    5.31    /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    5.32    /// concept.
    5.33 -  ///
    5.34 -  /// This class fully conforms to the \ref concepts::Graph "Graph"
    5.35 -  /// concept.
    5.36    template <typename GR>
    5.37    class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
    5.38      typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
    5.39 @@ -954,13 +956,14 @@
    5.40    /// single-linked lists for enumerate outgoing and incoming
    5.41    /// arcs. Therefore the arcs cannot be erased from the arc sets.
    5.42    ///
    5.43 +  /// This class fully conforms to the \ref concepts::Digraph "Digraph"
    5.44 +  /// concept.
    5.45 +  /// It provides only linear time counting for nodes and arcs.
    5.46 +  ///
    5.47    /// \warning If a node is erased from the underlying graph and this
    5.48    /// node is the source or target of one arc in the arc set, then
    5.49    /// the arc set is invalidated, and it cannot be used anymore. The
    5.50    /// validity can be checked with the \c valid() member function.
    5.51 -  ///
    5.52 -  /// This class fully conforms to the \ref concepts::Digraph
    5.53 -  /// "Digraph" concept.
    5.54    template <typename GR>
    5.55    class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
    5.56      typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
    5.57 @@ -1304,13 +1307,14 @@
    5.58    /// single-linked lists for enumerate incident edges. Therefore the
    5.59    /// edges cannot be erased from the edge sets.
    5.60    ///
    5.61 +  /// This class fully conforms to the \ref concepts::Graph "Graph"
    5.62 +  /// concept.
    5.63 +  /// It provides only linear time counting for nodes, edges and arcs.
    5.64 +  ///
    5.65    /// \warning If a node is erased from the underlying graph and this
    5.66    /// node is incident to one edge in the edge set, then the edge set
    5.67    /// is invalidated, and it cannot be used anymore. The validity can
    5.68    /// be checked with the \c valid() member function.
    5.69 -  ///
    5.70 -  /// This class fully conforms to the \ref concepts::Graph
    5.71 -  /// "Graph" concept.
    5.72    template <typename GR>
    5.73    class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
    5.74      typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
     6.1 --- a/lemon/full_graph.h	Thu Nov 05 15:50:01 2009 +0100
     6.2 +++ b/lemon/full_graph.h	Sun Nov 15 19:57:02 2009 +0100
     6.3 @@ -162,6 +162,8 @@
     6.4    /// Most of its member functions and nested classes are documented
     6.5    /// only in the concept class.
     6.6    ///
     6.7 +  /// This class provides constant time counting for nodes and arcs.
     6.8 +  ///
     6.9    /// \note FullDigraph and FullGraph classes are very similar,
    6.10    /// but there are two differences. While this class conforms only
    6.11    /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
    6.12 @@ -204,6 +206,7 @@
    6.13      /// Returns the node with the given index. Since this structure is 
    6.14      /// completely static, the nodes can be indexed with integers from
    6.15      /// the range <tt>[0..nodeNum()-1]</tt>.
    6.16 +    /// The index of a node is the same as its ID.
    6.17      /// \sa index()
    6.18      Node operator()(int ix) const { return Parent::operator()(ix); }
    6.19  
    6.20 @@ -212,6 +215,7 @@
    6.21      /// Returns the index of the given node. Since this structure is 
    6.22      /// completely static, the nodes can be indexed with integers from
    6.23      /// the range <tt>[0..nodeNum()-1]</tt>.
    6.24 +    /// The index of a node is the same as its ID.
    6.25      /// \sa operator()()
    6.26      static int index(const Node& node) { return Parent::index(node); }
    6.27  
    6.28 @@ -535,6 +539,8 @@
    6.29    /// Most of its member functions and nested classes are documented
    6.30    /// only in the concept class.
    6.31    ///
    6.32 +  /// This class provides constant time counting for nodes, edges and arcs.
    6.33 +  ///
    6.34    /// \note FullDigraph and FullGraph classes are very similar,
    6.35    /// but there are two differences. While FullDigraph
    6.36    /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    6.37 @@ -579,6 +585,7 @@
    6.38      /// Returns the node with the given index. Since this structure is 
    6.39      /// completely static, the nodes can be indexed with integers from
    6.40      /// the range <tt>[0..nodeNum()-1]</tt>.
    6.41 +    /// The index of a node is the same as its ID.
    6.42      /// \sa index()
    6.43      Node operator()(int ix) const { return Parent::operator()(ix); }
    6.44  
    6.45 @@ -587,6 +594,7 @@
    6.46      /// Returns the index of the given node. Since this structure is 
    6.47      /// completely static, the nodes can be indexed with integers from
    6.48      /// the range <tt>[0..nodeNum()-1]</tt>.
    6.49 +    /// The index of a node is the same as its ID.
    6.50      /// \sa operator()()
    6.51      static int index(const Node& node) { return Parent::index(node); }
    6.52  
     7.1 --- a/lemon/grid_graph.h	Thu Nov 05 15:50:01 2009 +0100
     7.2 +++ b/lemon/grid_graph.h	Sun Nov 15 19:57:02 2009 +0100
     7.3 @@ -503,6 +503,8 @@
     7.4    /// This type fully conforms to the \ref concepts::Graph "Graph concept".
     7.5    /// Most of its member functions and nested classes are documented
     7.6    /// only in the concept class.
     7.7 +  ///
     7.8 +  /// This class provides constant time counting for nodes, edges and arcs.
     7.9    class GridGraph : public ExtendedGridGraphBase {
    7.10      typedef ExtendedGridGraphBase Parent;
    7.11  
     8.1 --- a/lemon/hypercube_graph.h	Thu Nov 05 15:50:01 2009 +0100
     8.2 +++ b/lemon/hypercube_graph.h	Sun Nov 15 19:57:02 2009 +0100
     8.3 @@ -294,6 +294,8 @@
     8.4    /// Most of its member functions and nested classes are documented
     8.5    /// only in the concept class.
     8.6    ///
     8.7 +  /// This class provides constant time counting for nodes, edges and arcs.
     8.8 +  ///
     8.9    /// \note The type of the indices is chosen to \c int for efficiency
    8.10    /// reasons. Thus the maximum dimension of this implementation is 26
    8.11    /// (assuming that the size of \c int is 32 bit).
     9.1 --- a/lemon/list_graph.h	Thu Nov 05 15:50:01 2009 +0100
     9.2 +++ b/lemon/list_graph.h	Sun Nov 15 19:57:02 2009 +0100
     9.3 @@ -324,6 +324,8 @@
     9.4    ///Most of its member functions and nested classes are documented
     9.5    ///only in the concept class.
     9.6    ///
     9.7 +  ///This class provides only linear time counting for nodes and arcs.
     9.8 +  ///
     9.9    ///\sa concepts::Digraph
    9.10    ///\sa ListGraph
    9.11    class ListDigraph : public ExtendedListDigraphBase {
    9.12 @@ -360,12 +362,19 @@
    9.13  
    9.14      ///\brief Erase a node from the digraph.
    9.15      ///
    9.16 -    ///This function erases the given node from the digraph.
    9.17 +    ///This function erases the given node along with its outgoing and
    9.18 +    ///incoming arcs from the digraph.
    9.19 +    ///
    9.20 +    ///\note All iterators referencing the removed node or the connected
    9.21 +    ///arcs are invalidated, of course.
    9.22      void erase(Node n) { Parent::erase(n); }
    9.23  
    9.24      ///\brief Erase an arc from the digraph.
    9.25      ///
    9.26      ///This function erases the given arc from the digraph.
    9.27 +    ///
    9.28 +    ///\note All iterators referencing the removed arc are invalidated,
    9.29 +    ///of course.
    9.30      void erase(Arc a) { Parent::erase(a); }
    9.31  
    9.32      /// Node validity check
    9.33 @@ -510,6 +519,7 @@
    9.34  
    9.35      ///This function erases all nodes and arcs from the digraph.
    9.36      ///
    9.37 +    ///\note All iterators of the digraph are invalidated, of course.
    9.38      void clear() {
    9.39        Parent::clear();
    9.40      }
    9.41 @@ -1179,6 +1189,8 @@
    9.42    ///Most of its member functions and nested classes are documented
    9.43    ///only in the concept class.
    9.44    ///
    9.45 +  ///This class provides only linear time counting for nodes, edges and arcs.
    9.46 +  ///
    9.47    ///\sa concepts::Graph
    9.48    ///\sa ListDigraph
    9.49    class ListGraph : public ExtendedListGraphBase {
    9.50 @@ -1217,12 +1229,19 @@
    9.51  
    9.52      ///\brief Erase a node from the graph.
    9.53      ///
    9.54 -    /// This function erases the given node from the graph.
    9.55 +    /// This function erases the given node along with its incident arcs
    9.56 +    /// from the graph.
    9.57 +    ///
    9.58 +    /// \note All iterators referencing the removed node or the incident
    9.59 +    /// edges are invalidated, of course.
    9.60      void erase(Node n) { Parent::erase(n); }
    9.61  
    9.62      ///\brief Erase an edge from the graph.
    9.63      ///
    9.64      /// This function erases the given edge from the graph.
    9.65 +    ///
    9.66 +    /// \note All iterators referencing the removed edge are invalidated,
    9.67 +    /// of course.
    9.68      void erase(Edge e) { Parent::erase(e); }
    9.69      /// Node validity check
    9.70  
    9.71 @@ -1312,6 +1331,7 @@
    9.72  
    9.73      ///This function erases all nodes and arcs from the graph.
    9.74      ///
    9.75 +    ///\note All iterators of the graph are invalidated, of course.
    9.76      void clear() {
    9.77        Parent::clear();
    9.78      }
    10.1 --- a/lemon/smart_graph.h	Thu Nov 05 15:50:01 2009 +0100
    10.2 +++ b/lemon/smart_graph.h	Sun Nov 15 19:57:02 2009 +0100
    10.3 @@ -194,6 +194,8 @@
    10.4    ///Most of its member functions and nested classes are documented
    10.5    ///only in the concept class.
    10.6    ///
    10.7 +  ///This class provides constant time counting for nodes and arcs.
    10.8 +  ///
    10.9    ///\sa concepts::Digraph
   10.10    ///\sa SmartGraph
   10.11    class SmartDigraph : public ExtendedSmartDigraphBase {
   10.12 @@ -620,6 +622,8 @@
   10.13    /// Most of its member functions and nested classes are documented
   10.14    /// only in the concept class.
   10.15    ///
   10.16 +  /// This class provides constant time counting for nodes, edges and arcs.
   10.17 +  ///
   10.18    /// \sa concepts::Graph
   10.19    /// \sa SmartDigraph
   10.20    class SmartGraph : public ExtendedSmartGraphBase {
    11.1 --- a/lemon/static_graph.h	Thu Nov 05 15:50:01 2009 +0100
    11.2 +++ b/lemon/static_graph.h	Sun Nov 15 19:57:02 2009 +0100
    11.3 @@ -292,6 +292,8 @@
    11.4    /// Most of its member functions and nested classes are documented
    11.5    /// only in the concept class.
    11.6    ///
    11.7 +  /// This class provides constant time counting for nodes and arcs.
    11.8 +  ///
    11.9    /// \sa concepts::Digraph
   11.10    class StaticDigraph : public ExtendedStaticDigraphBase {
   11.11    public: