summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | bz2 | zip | gz |
help

author | Peter Kovacs <kpeter@inf.elte.hu> |

Sun, 15 Nov 2009 19:57:02 +0100 | |

changeset 834 | c2230649a493 |

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.

- 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 | file | annotate | diff | comparison | revisions | |

lemon/bfs.h | file | annotate | diff | comparison | revisions | |

lemon/dfs.h | file | annotate | diff | comparison | revisions | |

lemon/dijkstra.h | file | annotate | diff | comparison | revisions | |

lemon/edge_set.h | file | annotate | diff | comparison | revisions | |

lemon/full_graph.h | file | annotate | diff | comparison | revisions | |

lemon/grid_graph.h | file | annotate | diff | comparison | revisions | |

lemon/hypercube_graph.h | file | annotate | diff | comparison | revisions | |

lemon/list_graph.h | file | annotate | diff | comparison | revisions | |

lemon/smart_graph.h | file | annotate | diff | comparison | revisions | |

lemon/static_graph.h | file | annotate | diff | comparison | revisions |

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: