# HG changeset patch # User Peter Kovacs # Date 1258311422 -3600 # 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 -r 1a7fe3bef514 -r c2230649a493 lemon/adaptors.h --- a/lemon/adaptors.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/adaptors.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/bfs.h --- a/lemon/bfs.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/bfs.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 b.run(s) 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 b.run(s) is just a shortcut of the following code. ///\code diff -r 1a7fe3bef514 -r c2230649a493 lemon/dfs.h --- a/lemon/dfs.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/dfs.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 d.run() 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 d.run() is just a shortcut of the following code. ///\code diff -r 1a7fe3bef514 -r c2230649a493 lemon/dijkstra.h --- a/lemon/dijkstra.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/dijkstra.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/edge_set.h --- a/lemon/edge_set.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/edge_set.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 class ListArcSet : public ArcSetExtender > { typedef ArcSetExtender > 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 class ListEdgeSet : public EdgeSetExtender > { typedef EdgeSetExtender > 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 class SmartArcSet : public ArcSetExtender > { typedef ArcSetExtender > 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 class SmartEdgeSet : public EdgeSetExtender > { typedef EdgeSetExtender > Parent; diff -r 1a7fe3bef514 -r c2230649a493 lemon/full_graph.h --- a/lemon/full_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/full_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 [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); } @@ -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 [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); } @@ -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 [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); } @@ -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 [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); } diff -r 1a7fe3bef514 -r c2230649a493 lemon/grid_graph.h --- a/lemon/grid_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/grid_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/hypercube_graph.h --- a/lemon/hypercube_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/hypercube_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/list_graph.h --- a/lemon/list_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/list_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/smart_graph.h --- a/lemon/smart_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/smart_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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 -r 1a7fe3bef514 -r c2230649a493 lemon/static_graph.h --- a/lemon/static_graph.h Thu Nov 05 15:50:01 2009 +0100 +++ b/lemon/static_graph.h Sun Nov 15 19:57:02 2009 +0100 @@ -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: