1.1 --- a/lemon/graph_utils.h Mon Jul 04 17:51:07 2005 +0000
1.2 +++ b/lemon/graph_utils.h Tue Jul 05 14:36:10 2005 +0000
1.3 @@ -30,8 +30,6 @@
1.4 ///\file
1.5 ///\brief Graph utilities.
1.6 ///
1.7 -///\todo Please
1.8 -///revise the documentation.
1.9 ///
1.10
1.11
1.12 @@ -42,7 +40,7 @@
1.13
1.14 /// \brief Function to count the items in the graph.
1.15 ///
1.16 - /// This function counts the items in the graph.
1.17 + /// This function counts the items (nodes, edges etc) in the graph.
1.18 /// The complexity of the function is O(n) because
1.19 /// it iterates on all of the items.
1.20
1.21 @@ -125,7 +123,7 @@
1.22 ///
1.23 /// This function counts the undirected edges in the graph.
1.24 /// The complexity of the function is O(e) but for some
1.25 - /// graph structure it is specialized to run in O(1).
1.26 + /// graph structures it is specialized to run in O(1).
1.27
1.28 template <typename Graph>
1.29 inline int countUndirEdges(const Graph& g) {
1.30 @@ -193,11 +191,11 @@
1.31 return e;
1.32 }
1.33
1.34 - /// \brief Copy the source map to the target map.
1.35 + /// \brief Copy a map.
1.36 ///
1.37 - /// Copy the \c source map to the \c target map. It uses the given iterator
1.38 - /// to iterate on the data structure and it use the \c ref mapping to
1.39 - /// convert the source's keys to the target's keys.
1.40 + /// Thsi function copies the \c source map to the \c target map. It uses the
1.41 + /// given iterator to iterate on the data structure and it uses the \c ref
1.42 + /// mapping to convert the source's keys to the target's keys.
1.43 template <typename Target, typename Source,
1.44 typename ItemIt, typename Ref>
1.45 void copyMap(Target& target, const Source& source,
1.46 @@ -220,10 +218,10 @@
1.47 }
1.48
1.49
1.50 - /// \brief Class to copy a graph to an other graph.
1.51 + /// \brief Class to copy a graph.
1.52 ///
1.53 - /// Class to copy a graph to an other graph. It can be used easier
1.54 - /// with the \c copyGraph() function.
1.55 + /// Class to copy a graph to an other graph (duplicate a graph). The
1.56 + /// simplest way of using it is through the \c copyGraph() function.
1.57 template <typename Target, typename Source>
1.58 class GraphCopy {
1.59 public:
1.60 @@ -354,7 +352,7 @@
1.61 ///
1.62 /// After the copy the \c nr map will contain the mapping from the
1.63 /// source graph's nodes to the target graph's nodes and the \c ecr will
1.64 - /// contain the mapping from the target graph's edge to the source's
1.65 + /// contain the mapping from the target graph's edges to the source's
1.66 /// edges.
1.67 template <typename Target, typename Source>
1.68 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
1.69 @@ -458,8 +456,13 @@
1.70
1.71 /// Provides an immutable and unique id for each item in the graph.
1.72
1.73 - /// The IdMap class provides a unique and immutable mapping for each item
1.74 - /// in the graph.
1.75 + /// The IdMap class provides a unique and immutable id for each item of the
1.76 + /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1.77 + /// different items (nodes) get different ids <li>\b immutable: the id of an
1.78 + /// item (node) does not change (even if you delete other nodes). </ul>
1.79 + /// Through this map you get access (i.e. can read) the inner id values of
1.80 + /// the items stored in the graph. This map can be inverted with its member
1.81 + /// class \c InverseMap.
1.82 ///
1.83 template <typename _Graph, typename _Item>
1.84 class IdMap {
1.85 @@ -487,9 +490,9 @@
1.86
1.87 public:
1.88
1.89 - /// \brief The class represents the inverse of the map.
1.90 + /// \brief The class represents the inverse of its owner (IdMap).
1.91 ///
1.92 - /// The class represents the inverse of the map.
1.93 + /// The class represents the inverse of its owner (IdMap).
1.94 /// \see inverse()
1.95 class InverseMap {
1.96 public:
1.97 @@ -517,7 +520,7 @@
1.98
1.99 /// \brief Gives back the inverse of the map.
1.100 ///
1.101 - /// Gives back the inverse of the map.
1.102 + /// Gives back the inverse of the IdMap.
1.103 InverseMap inverse() const { return InverseMap(*graph);}
1.104
1.105 };
1.106 @@ -525,7 +528,7 @@
1.107
1.108 /// \brief General invertable graph-map type.
1.109
1.110 - /// This type provides simple invertable map functions.
1.111 + /// This type provides simple invertable graph-maps.
1.112 /// The InvertableMap wraps an arbitrary ReadWriteMap
1.113 /// and if a key is set to a new value then store it
1.114 /// in the inverse map.
1.115 @@ -658,9 +661,14 @@
1.116 /// \brief Provides a mutable, continuous and unique descriptor for each
1.117 /// item in the graph.
1.118 ///
1.119 - /// The DescriptorMap class provides a mutable, continuous and immutable
1.120 - /// mapping for each item in the graph. The value for an item may mutated
1.121 - /// on each operation when the an item erased or added to graph.
1.122 + /// The DescriptorMap class provides a unique and continuous (but mutable)
1.123 + /// descriptor (id) for each item of the same type (e.g. node) in the
1.124 + /// graph. This id is <ul><li>\b unique: different items (nodes) get
1.125 + /// different ids <li>\b continuous: the range of the ids is the set of
1.126 + /// integers between 0 and \c n-1, where \c n is the number of the items of
1.127 + /// this type (e.g. nodes) (so the id of a node can change if you delete an
1.128 + /// other node, i.e. this id is mutable). </ul> This map can be inverted
1.129 + /// with its member class \c InverseMap.
1.130 ///
1.131 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.132 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1.133 @@ -754,9 +762,9 @@
1.134 Container invMap;
1.135
1.136 public:
1.137 - /// \brief The inverse map type.
1.138 + /// \brief The inverse map type of DescriptorMap.
1.139 ///
1.140 - /// The inverse map type.
1.141 + /// The inverse map type of DescriptorMap.
1.142 class InverseMap {
1.143 public:
1.144 /// \brief Constructor of the InverseMap.
1.145 @@ -873,16 +881,16 @@
1.146
1.147 /// \brief Returns a \ref TargetMap class
1.148 ///
1.149 - /// This function just returns an \ref TargetMap class.
1.150 + /// This function just returns a \ref TargetMap class.
1.151 /// \relates TargetMap
1.152 template <typename Graph>
1.153 inline TargetMap<Graph> targetMap(const Graph& graph) {
1.154 return TargetMap<Graph>(graph);
1.155 }
1.156
1.157 - /// \brief Returns the "forward" directed edge view of undirected edge.
1.158 + /// \brief Returns the "forward" directed edge view of an undirected edge.
1.159 ///
1.160 - /// Returns the "forward" directed edge view of undirected edge.
1.161 + /// Returns the "forward" directed edge view of an undirected edge.
1.162 /// \author Balazs Dezso
1.163 template <typename Graph>
1.164 class ForwardMap {
1.165 @@ -921,9 +929,9 @@
1.166 return ForwardMap<Graph>(graph);
1.167 }
1.168
1.169 - /// \brief Returns the "backward" directed edge view of undirected edge.
1.170 + /// \brief Returns the "backward" directed edge view of an undirected edge.
1.171 ///
1.172 - /// Returns the "backward" directed edge view of undirected edge.
1.173 + /// Returns the "backward" directed edge view of an undirected edge.
1.174 /// \author Balazs Dezso
1.175 template <typename Graph>
1.176 class BackwardMap {
1.177 @@ -954,7 +962,7 @@
1.178
1.179 /// \brief Returns a \ref BackwardMap class
1.180
1.181 - /// This function just returns an \ref BackwardMap class.
1.182 + /// This function just returns a \ref BackwardMap class.
1.183 /// \relates BackwardMap
1.184 template <typename Graph>
1.185 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1.186 @@ -975,9 +983,9 @@
1.187
1.188 /// \brief Map of the node in-degrees.
1.189 ///
1.190 - /// This map returns the in-degree of a node. Ones it is constructed,
1.191 + /// This map returns the in-degree of a node. Once it is constructed,
1.192 /// the degrees are stored in a standard NodeMap, so each query is done
1.193 - /// in constant time. On the other hand, the values updates automatically
1.194 + /// in constant time. On the other hand, the values are updated automatically
1.195 /// whenever the graph changes.
1.196 ///
1.197 /// \sa OutDegMap
1.198 @@ -1067,9 +1075,9 @@
1.199
1.200 /// \brief Map of the node out-degrees.
1.201 ///
1.202 - /// This map returns the out-degree of a node. One it is constructed,
1.203 + /// This map returns the out-degree of a node. Once it is constructed,
1.204 /// the degrees are stored in a standard NodeMap, so each query is done
1.205 - /// in constant time. On the other hand, the values updates automatically
1.206 + /// in constant time. On the other hand, the values are updated automatically
1.207 /// whenever the graph changes.
1.208 ///
1.209 /// \sa OutDegMap