1.1 --- a/src/lemon/bfs.h Mon Mar 28 23:34:26 2005 +0000
1.2 +++ b/src/lemon/bfs.h Tue Mar 29 07:35:09 2005 +0000
1.3 @@ -135,7 +135,7 @@
1.4 ///See \ref BfsDefaultTraits for the documentation of
1.5 ///a Bfs traits class.
1.6 ///
1.7 - ///\author Jacint Szabo and Alpar Juttner
1.8 + ///\author Alpar Juttner
1.9 ///\todo A compare object would be nice.
1.10
1.11 #ifdef DOXYGEN
1.12 @@ -348,7 +348,7 @@
1.13 ///
1.14 ///\ref named-templ-param "Named parameter"
1.15 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.16 - ///If you don't set it explicitely, it will be automatically allocated.
1.17 + ///If you don't set it explicitly, it will be automatically allocated.
1.18 template <class T>
1.19 class DefProcessedMapToBeDefaultMap :
1.20 public Bfs< Graph,
1.21 @@ -385,7 +385,7 @@
1.22
1.23 ///Sets the map storing the predecessor edges.
1.24 ///If you don't use this function before calling \ref run(),
1.25 - ///it will allocate one. The destuctor deallocates this
1.26 + ///it will allocate one. The destructor deallocates this
1.27 ///automatically allocated map, of course.
1.28 ///\return <tt> (*this) </tt>
1.29 Bfs &predMap(PredMap &m)
1.30 @@ -402,7 +402,7 @@
1.31
1.32 ///Sets the map indicating the reached nodes.
1.33 ///If you don't use this function before calling \ref run(),
1.34 - ///it will allocate one. The destuctor deallocates this
1.35 + ///it will allocate one. The destructor deallocates this
1.36 ///automatically allocated map, of course.
1.37 ///\return <tt> (*this) </tt>
1.38 Bfs &reachedMap(ReachedMap &m)
1.39 @@ -419,7 +419,7 @@
1.40
1.41 ///Sets the map indicating the processed nodes.
1.42 ///If you don't use this function before calling \ref run(),
1.43 - ///it will allocate one. The destuctor deallocates this
1.44 + ///it will allocate one. The destructor deallocates this
1.45 ///automatically allocated map, of course.
1.46 ///\return <tt> (*this) </tt>
1.47 Bfs &processedMap(ProcessedMap &m)
1.48 @@ -436,7 +436,7 @@
1.49
1.50 // ///Sets the map storing the predecessor nodes.
1.51 // ///If you don't use this function before calling \ref run(),
1.52 -// ///it will allocate one. The destuctor deallocates this
1.53 +// ///it will allocate one. The destructor deallocates this
1.54 // ///automatically allocated map, of course.
1.55 // ///\return <tt> (*this) </tt>
1.56 // Bfs &predNodeMap(PredNodeMap &m)
1.57 @@ -453,7 +453,7 @@
1.58
1.59 ///Sets the map storing the distances calculated by the algorithm.
1.60 ///If you don't use this function before calling \ref run(),
1.61 - ///it will allocate one. The destuctor deallocates this
1.62 + ///it will allocate one. The destructor deallocates this
1.63 ///automatically allocated map, of course.
1.64 ///\return <tt> (*this) </tt>
1.65 Bfs &distMap(DistMap &m)
1.66 @@ -658,7 +658,7 @@
1.67 ///Returns the distance of a node from the root(s).
1.68 ///\pre \ref run() must be called before using this function.
1.69 ///\warning If node \c v in unreachable from the root(s) the return value
1.70 - ///of this funcion is undefined.
1.71 + ///of this function is undefined.
1.72 int dist(Node v) const { return (*_dist)[v]; }
1.73
1.74 ///Returns the 'previous edge' of the shortest path tree.
1.75 @@ -715,7 +715,7 @@
1.76 ///Checks if a node is reachable from the root.
1.77
1.78 ///Returns \c true if \c v is reachable from the root.
1.79 - ///\warning The source nodes are inditated as unreached.
1.80 + ///\warning The source nodes are indicated as unreached.
1.81 ///\pre Either \ref run() or \ref start()
1.82 ///must be called before using this function.
1.83 ///
2.1 --- a/src/lemon/bin_heap.h Mon Mar 28 23:34:26 2005 +0000
2.2 +++ b/src/lemon/bin_heap.h Tue Mar 29 07:35:09 2005 +0000
2.3 @@ -20,7 +20,6 @@
2.4 ///\ingroup auxdat
2.5 ///\file
2.6 ///\brief Binary Heap implementation.
2.7 -///\todo It should be documented.
2.8
2.9 #include <vector>
2.10 #include <utility>
2.11 @@ -31,9 +30,20 @@
2.12 /// \addtogroup auxdat
2.13 /// @{
2.14
2.15 - /// A Binary Heap implementation.
2.16 + /// A Binary Heap implementation.
2.17
2.18 - ///\todo Please document...
2.19 + ///This class implements the \e binary \e heap data structure. A \e heap
2.20 + ///is a data structure for storing items with specified values called \e
2.21 + ///priorities in such a way that finding the item with minimum priority is
2.22 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
2.23 + ///one can change the priority of an item, add or erase an item, etc.
2.24 + ///
2.25 + ///\param Item Type of the items to be stored.
2.26 + ///\param Prio Type of the priority of the items.
2.27 + ///\param ItemIntMap A read and writable Item int map, used internally
2.28 + ///to handle the cross references.
2.29 + ///\param Compare A class for the ordering of the priorities. The
2.30 + ///default is \c std::less<Prio>.
2.31 ///
2.32 ///\sa FibHeap
2.33 ///\sa Dijkstra
2.34 @@ -72,16 +82,37 @@
2.35 ItemIntMap &iim;
2.36
2.37 public:
2.38 - ///\e
2.39 + ///The constructor
2.40 +
2.41 + /**
2.42 + \c _iim should be given to the constructor, since it is used
2.43 + internally to handle the cross references.
2.44 + */
2.45 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
2.46 - ///\e
2.47 +
2.48 + ///The constructor
2.49 +
2.50 + /**
2.51 + \c _iim should be given to the constructor, since it is used
2.52 + internally to handle the cross references. \c _comp is an
2.53 + object for ordering of the priorities.
2.54 + */
2.55 BinHeap(ItemIntMap &_iim, const Compare &_comp)
2.56 : iim(_iim), comp(_comp) {}
2.57
2.58
2.59 - ///\e
2.60 + ///The number of items stored in the heap.
2.61 +
2.62 + /**
2.63 + Returns the number of items stored in the heap.
2.64 + */
2.65 int size() const { return data.size(); }
2.66 - ///\e
2.67 +
2.68 + ///Checks if the heap stores no items.
2.69 +
2.70 + /**
2.71 + Returns \c true if and only if the heap stores no items.
2.72 + */
2.73 bool empty() const { return data.empty(); }
2.74
2.75 private:
2.76 @@ -111,41 +142,86 @@
2.77 }
2.78
2.79 public:
2.80 - ///\e
2.81 + ///Adds \c p.first to the heap with priority \c p.second.
2.82 +
2.83 + /**
2.84 + Adds \c p.first to the heap with priority \c p.second.
2.85 + \c p.first must not be stored in the heap.
2.86 + */
2.87 void push(const PairType &p) {
2.88 int n = data.size();
2.89 data.resize(n+1);
2.90 bubble_up(n, p);
2.91 }
2.92 - ///\e
2.93 +
2.94 + ///Adds \c i to the heap with priority \c p.
2.95 +
2.96 + /**
2.97 + Adds \c i to the heap with priority \c p.
2.98 + \pre \c i must not be stored in the heap.
2.99 + */
2.100 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
2.101
2.102 - ///\e
2.103 + ///Returns the item with minimum priority relative to \c Compare.
2.104 +
2.105 + /**
2.106 + This method returns the item with minimum priority relative to \c
2.107 + Compare.
2.108 + \pre The heap must be nonempty.
2.109 + */
2.110 Item top() const {
2.111 return data[0].first;
2.112 }
2.113 - /// Returns the prio of the top element of the heap.
2.114 +
2.115 + ///Returns the minimum priority relative to \c Compare.
2.116 +
2.117 + /**
2.118 + It returns the minimum priority relative to \c Compare.
2.119 + \pre The heap must be nonempty.
2.120 + */
2.121 Prio prio() const {
2.122 return data[0].second;
2.123 }
2.124
2.125 - ///\e
2.126 + ///Deletes the item with minimum priority relative to \c Compare.
2.127 +
2.128 + /**
2.129 + This method deletes the item with minimum priority relative to \c
2.130 + Compare from the heap.
2.131 + \pre The heap must be non-empty.
2.132 + */
2.133 void pop() {
2.134 rmidx(0);
2.135 }
2.136
2.137 - ///\e
2.138 + ///Deletes \c i from the heap.
2.139 +
2.140 + /**
2.141 + This method deletes item \c i from the heap, if \c i was
2.142 + already stored in the heap.
2.143 + */
2.144 void erase(const Item &i) {
2.145 rmidx(iim[i]);
2.146 }
2.147
2.148 - ///\e
2.149 +
2.150 + ///Returns the priority of \c i.
2.151 +
2.152 + /**
2.153 + This function returns the priority of item \c i.
2.154 + \pre \c i must be in the heap.
2.155 + */
2.156 Prio operator[](const Item &i) const {
2.157 int idx = iim[i];
2.158 return data[idx].second;
2.159 }
2.160
2.161 - ///\e
2.162 + ///\c i gets to the heap with priority \c p independently if \c i was already there.
2.163 +
2.164 + /**
2.165 + This method calls \ref push(\c i, \c p) if \c i is not stored
2.166 + in the heap and sets the priority of \c i to \c p otherwise.
2.167 + */
2.168 void set(const Item &i, const Prio &p) {
2.169 int idx = iim[i];
2.170 if( idx < 0 ) {
2.171 @@ -159,18 +235,38 @@
2.172 }
2.173 }
2.174
2.175 - ///\e
2.176 + ///Decreases the priority of \c i to \c p.
2.177 +
2.178 + /**
2.179 + This method decreases the priority of item \c i to \c p.
2.180 + \pre \c i must be stored in the heap with priority at least \c
2.181 + p relative to \c Compare.
2.182 + */
2.183 void decrease(const Item &i, const Prio &p) {
2.184 int idx = iim[i];
2.185 bubble_up(idx, PairType(i,p));
2.186 }
2.187 - ///\e
2.188 +
2.189 + ///Increases the priority of \c i to \c p.
2.190 +
2.191 + /**
2.192 + This method sets the priority of item \c i to \c p.
2.193 + \pre \c i must be stored in the heap with priority at most \c
2.194 + p relative to \c Compare.
2.195 + */
2.196 void increase(const Item &i, const Prio &p) {
2.197 int idx = iim[i];
2.198 bubble_down(idx, PairType(i,p), data.size());
2.199 }
2.200
2.201 - ///\e
2.202 + ///Returns if \c item is in, has already been in, or has never been in the heap.
2.203 +
2.204 + /**
2.205 + This method returns PRE_HEAP if \c item has never been in the
2.206 + heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.207 + otherwise. In the latter case it is possible that \c item will
2.208 + get back to the heap again.
2.209 + */
2.210 state_enum state(const Item &i) const {
2.211 int s = iim[i];
2.212 if( s>=0 )
3.1 --- a/src/lemon/concept/path.h Mon Mar 28 23:34:26 2005 +0000
3.2 +++ b/src/lemon/concept/path.h Tue Mar 29 07:35:09 2005 +0000
3.3 @@ -36,7 +36,7 @@
3.4 //! A skeleton structure for representing directed paths in a graph.
3.5 //! \param GR The graph type in which the path is.
3.6 //!
3.7 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
3.8 + //! In a sense, the path can be treated as a graph, for it has \c NodeIt
3.9 //! and \c EdgeIt with the same usage. These types converts to the \c Node
3.10 //! and \c Edge of the original graph.
3.11 template<typename GR>
3.12 @@ -172,9 +172,9 @@
3.13 * arbitrary order then you should commit these changes to the graph.
3.14 *
3.15 * While the builder is active (after the first modifying
3.16 - * operation and until the call of \ref commit())
3.17 - * the underlining Path is in a
3.18 - * "transitional" state (operations on it have undefined result).
3.19 + * operation and until the call of \ref commit()) the
3.20 + * underlining Path is in a "transitional" state (operations on
3.21 + * it have undefined result).
3.22 */
3.23 class Builder {
3.24 public:
3.25 @@ -190,7 +190,7 @@
3.26
3.27 /// Sets the starting node of the path. Edge added to the path
3.28 /// afterwards have to be incident to this node.
3.29 - /// You \em must start building an empry path with this functions.
3.30 + /// You \em must start building an empty path with these functions.
3.31 /// (And you \em must \em not use it later).
3.32 /// \sa pushFront()
3.33 /// \sa pushBack()
3.34 @@ -215,13 +215,13 @@
3.35
3.36 ///Reserve (front) storage for the builder in advance.
3.37
3.38 - ///If you know an reasonable upper bound of the number of the edges
3.39 + ///If you know a reasonable upper bound on the number of the edges
3.40 ///to add to the front of the path,
3.41 ///using this function you may speed up the building.
3.42 void reserveFront(size_t r) {}
3.43 ///Reserve (back) storage for the builder in advance.
3.44
3.45 - ///If you know an reasonable upper bound of the number of the edges
3.46 + ///If you know a reasonable upper bound on the number of the edges
3.47 ///to add to the back of the path,
3.48 ///using this function you may speed up the building.
3.49 void reserveBack(size_t r) {}
4.1 --- a/src/lemon/fib_heap.h Mon Mar 28 23:34:26 2005 +0000
4.2 +++ b/src/lemon/fib_heap.h Tue Mar 29 07:35:09 2005 +0000
4.3 @@ -88,10 +88,24 @@
4.4 POST_HEAP = -2
4.5 };
4.6
4.7 + ///The constructor
4.8 +
4.9 + /**
4.10 + \c _iimap should be given to the constructor, since it is
4.11 + used internally to handle the cross references.
4.12 + */
4.13 explicit FibHeap(ItemIntMap &_iimap)
4.14 : minimum(0), iimap(_iimap), num_items() {}
4.15 +
4.16 + ///The constructor
4.17 +
4.18 + /**
4.19 + \c _iimap should be given to the constructor, since it is used
4.20 + internally to handle the cross references. \c _comp is an
4.21 + object for ordering of the priorities.
4.22 + */
4.23 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
4.24 - iimap(_iimap), comp(_comp), num_items() {}
4.25 + iimap(_iimap), comp(_comp), num_items() {}
4.26
4.27 ///The number of items stored in the heap.
4.28
5.1 --- a/src/lemon/min_cost_flow.h Mon Mar 28 23:34:26 2005 +0000
5.2 +++ b/src/lemon/min_cost_flow.h Tue Mar 29 07:35:09 2005 +0000
5.3 @@ -36,20 +36,18 @@
5.4 ///(for small values of \c k) having minimal total cost between 2 nodes
5.5 ///
5.6 ///
5.7 - /// The class \ref lemon::MinCostFlow "MinCostFlow" implements
5.8 - /// an algorithm for finding a flow of value \c k
5.9 - /// having minimal total cost
5.10 - /// from a given source node to a given target node in an
5.11 - /// edge-weighted directed graph. To this end,
5.12 - /// the edge-capacities and edge-weitghs have to be nonnegative.
5.13 - /// The edge-capacities should be integers, but the edge-weights can be
5.14 - /// integers, reals or of other comparable numeric type.
5.15 - /// This algorithm is intended to use only for small values of \c k,
5.16 - /// since it is only polynomial in k,
5.17 - /// not in the length of k (which is log k).
5.18 - /// In order to find the minimum cost flow of value \c k it
5.19 - /// finds the minimum cost flow of value \c i for every
5.20 - /// \c i between 0 and \c k.
5.21 + /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an
5.22 + /// algorithm for finding a flow of value \c k having minimal total
5.23 + /// cost from a given source node to a given target node in an
5.24 + /// edge-weighted directed graph. To this end, the edge-capacities
5.25 + /// and edge-weights have to be nonnegative. The edge-capacities
5.26 + /// should be integers, but the edge-weights can be integers, reals
5.27 + /// or of other comparable numeric type. This algorithm is intended
5.28 + /// to be used only for small values of \c k, since it is only
5.29 + /// polynomial in k, not in the length of k (which is log k): in
5.30 + /// order to find the minimum cost flow of value \c k it finds the
5.31 + /// minimum cost flow of value \c i for every \c i between 0 and \c
5.32 + /// k.
5.33 ///
5.34 ///\param Graph The directed graph type the algorithm runs on.
5.35 ///\param LengthMap The type of the length map.
5.36 @@ -149,7 +147,7 @@
5.37 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
5.38 potential.set(n, potential[n]+dijkstra.distMap()[n]);
5.39
5.40 - //Augmenting on the sortest path
5.41 + //Augmenting on the shortest path
5.42 Node n=t;
5.43 ResGraphEdge e;
5.44 while (n!=s){
5.45 @@ -226,7 +224,7 @@
5.46 /*! \brief Checking the complementary slackness optimality criteria.
5.47
5.48 This function checks, whether the given flow and potential
5.49 - satisfiy the complementary slackness cnditions (i.e. these are optimal).
5.50 + satisfy the complementary slackness conditions (i.e. these are optimal).
5.51 This function only checks optimality, doesn't bother with feasibility.
5.52 For testing purpose.
5.53 */
6.1 --- a/src/lemon/utility.h Mon Mar 28 23:34:26 2005 +0000
6.2 +++ b/src/lemon/utility.h Tue Mar 29 07:35:09 2005 +0000
6.3 @@ -37,7 +37,7 @@
6.4 namespace lemon
6.5 {
6.6
6.7 - /// Basic type for defining "tags". A "YES" condidion for enable_if.
6.8 + /// Basic type for defining "tags". A "YES" condition for enable_if.
6.9
6.10 /// \todo This should go to a separate "basic_types.h" (or something)
6.11 /// file.
6.12 @@ -45,7 +45,7 @@
6.13 static const bool value = true;
6.14 };
6.15
6.16 - /// Basic type for defining "tags". A "NO" condidion for enable_if.
6.17 + /// Basic type for defining "tags". A "NO" condition for enable_if.
6.18 struct False {
6.19 static const bool value = false;
6.20 };