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: