Changeset 1270:806451fd084b in lemon-0.x for src/lemon
- Timestamp:
- 03/29/05 09:35:09 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1698
- Location:
- src/lemon
- Files:
-
- 6 edited
-
bfs.h (modified) (9 diffs)
-
bin_heap.h (modified) (8 diffs)
-
concept/path.h (modified) (5 diffs)
-
fib_heap.h (modified) (1 diff)
-
min_cost_flow.h (modified) (3 diffs)
-
utility.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/bfs.h
r1236 r1270 136 136 ///a Bfs traits class. 137 137 /// 138 ///\author Jacint Szabo andAlpar Juttner138 ///\author Alpar Juttner 139 139 ///\todo A compare object would be nice. 140 140 … … 349 349 ///\ref named-templ-param "Named parameter" 350 350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. 351 ///If you don't set it explicit ely, it will be automatically allocated.351 ///If you don't set it explicitly, it will be automatically allocated. 352 352 template <class T> 353 353 class DefProcessedMapToBeDefaultMap : … … 386 386 ///Sets the map storing the predecessor edges. 387 387 ///If you don't use this function before calling \ref run(), 388 ///it will allocate one. The dest uctor deallocates this388 ///it will allocate one. The destructor deallocates this 389 389 ///automatically allocated map, of course. 390 390 ///\return <tt> (*this) </tt> … … 403 403 ///Sets the map indicating the reached nodes. 404 404 ///If you don't use this function before calling \ref run(), 405 ///it will allocate one. The dest uctor deallocates this405 ///it will allocate one. The destructor deallocates this 406 406 ///automatically allocated map, of course. 407 407 ///\return <tt> (*this) </tt> … … 420 420 ///Sets the map indicating the processed nodes. 421 421 ///If you don't use this function before calling \ref run(), 422 ///it will allocate one. The dest uctor deallocates this422 ///it will allocate one. The destructor deallocates this 423 423 ///automatically allocated map, of course. 424 424 ///\return <tt> (*this) </tt> … … 437 437 // ///Sets the map storing the predecessor nodes. 438 438 // ///If you don't use this function before calling \ref run(), 439 // ///it will allocate one. The dest uctor deallocates this439 // ///it will allocate one. The destructor deallocates this 440 440 // ///automatically allocated map, of course. 441 441 // ///\return <tt> (*this) </tt> … … 454 454 ///Sets the map storing the distances calculated by the algorithm. 455 455 ///If you don't use this function before calling \ref run(), 456 ///it will allocate one. The dest uctor deallocates this456 ///it will allocate one. The destructor deallocates this 457 457 ///automatically allocated map, of course. 458 458 ///\return <tt> (*this) </tt> … … 659 659 ///\pre \ref run() must be called before using this function. 660 660 ///\warning If node \c v in unreachable from the root(s) the return value 661 ///of this func ion is undefined.661 ///of this function is undefined. 662 662 int dist(Node v) const { return (*_dist)[v]; } 663 663 … … 716 716 717 717 ///Returns \c true if \c v is reachable from the root. 718 ///\warning The source nodes are indi tated as unreached.718 ///\warning The source nodes are indicated as unreached. 719 719 ///\pre Either \ref run() or \ref start() 720 720 ///must be called before using this function. -
src/lemon/bin_heap.h
r1191 r1270 21 21 ///\file 22 22 ///\brief Binary Heap implementation. 23 ///\todo It should be documented.24 23 25 24 #include <vector> … … 32 31 /// @{ 33 32 34 33 /// A Binary Heap implementation. 35 34 36 ///\todo Please document... 35 ///This class implements the \e binary \e heap data structure. A \e heap 36 ///is a data structure for storing items with specified values called \e 37 ///priorities in such a way that finding the item with minimum priority is 38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 39 ///one can change the priority of an item, add or erase an item, etc. 40 /// 41 ///\param Item Type of the items to be stored. 42 ///\param Prio Type of the priority of the items. 43 ///\param ItemIntMap A read and writable Item int map, used internally 44 ///to handle the cross references. 45 ///\param Compare A class for the ordering of the priorities. The 46 ///default is \c std::less<Prio>. 37 47 /// 38 48 ///\sa FibHeap … … 73 83 74 84 public: 75 ///\e 85 ///The constructor 86 87 /** 88 \c _iim should be given to the constructor, since it is used 89 internally to handle the cross references. 90 */ 76 91 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 77 ///\e 92 93 ///The constructor 94 95 /** 96 \c _iim should be given to the constructor, since it is used 97 internally to handle the cross references. \c _comp is an 98 object for ordering of the priorities. 99 */ 78 100 BinHeap(ItemIntMap &_iim, const Compare &_comp) 79 101 : iim(_iim), comp(_comp) {} 80 102 81 103 82 ///\e 104 ///The number of items stored in the heap. 105 106 /** 107 Returns the number of items stored in the heap. 108 */ 83 109 int size() const { return data.size(); } 84 ///\e 110 111 ///Checks if the heap stores no items. 112 113 /** 114 Returns \c true if and only if the heap stores no items. 115 */ 85 116 bool empty() const { return data.empty(); } 86 117 … … 112 143 113 144 public: 114 ///\e 145 ///Adds \c p.first to the heap with priority \c p.second. 146 147 /** 148 Adds \c p.first to the heap with priority \c p.second. 149 \c p.first must not be stored in the heap. 150 */ 115 151 void push(const PairType &p) { 116 152 int n = data.size(); … … 118 154 bubble_up(n, p); 119 155 } 120 ///\e 156 157 ///Adds \c i to the heap with priority \c p. 158 159 /** 160 Adds \c i to the heap with priority \c p. 161 \pre \c i must not be stored in the heap. 162 */ 121 163 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } 122 164 123 ///\e 165 ///Returns the item with minimum priority relative to \c Compare. 166 167 /** 168 This method returns the item with minimum priority relative to \c 169 Compare. 170 \pre The heap must be nonempty. 171 */ 124 172 Item top() const { 125 173 return data[0].first; 126 174 } 127 /// Returns the prio of the top element of the heap. 175 176 ///Returns the minimum priority relative to \c Compare. 177 178 /** 179 It returns the minimum priority relative to \c Compare. 180 \pre The heap must be nonempty. 181 */ 128 182 Prio prio() const { 129 183 return data[0].second; 130 184 } 131 185 132 ///\e 186 ///Deletes the item with minimum priority relative to \c Compare. 187 188 /** 189 This method deletes the item with minimum priority relative to \c 190 Compare from the heap. 191 \pre The heap must be non-empty. 192 */ 133 193 void pop() { 134 194 rmidx(0); 135 195 } 136 196 137 ///\e 197 ///Deletes \c i from the heap. 198 199 /** 200 This method deletes item \c i from the heap, if \c i was 201 already stored in the heap. 202 */ 138 203 void erase(const Item &i) { 139 204 rmidx(iim[i]); 140 205 } 141 206 142 ///\e 207 208 ///Returns the priority of \c i. 209 210 /** 211 This function returns the priority of item \c i. 212 \pre \c i must be in the heap. 213 */ 143 214 Prio operator[](const Item &i) const { 144 215 int idx = iim[i]; … … 146 217 } 147 218 148 ///\e 219 ///\c i gets to the heap with priority \c p independently if \c i was already there. 220 221 /** 222 This method calls \ref push(\c i, \c p) if \c i is not stored 223 in the heap and sets the priority of \c i to \c p otherwise. 224 */ 149 225 void set(const Item &i, const Prio &p) { 150 226 int idx = iim[i]; … … 160 236 } 161 237 162 ///\e 238 ///Decreases the priority of \c i to \c p. 239 240 /** 241 This method decreases the priority of item \c i to \c p. 242 \pre \c i must be stored in the heap with priority at least \c 243 p relative to \c Compare. 244 */ 163 245 void decrease(const Item &i, const Prio &p) { 164 246 int idx = iim[i]; 165 247 bubble_up(idx, PairType(i,p)); 166 248 } 167 ///\e 249 250 ///Increases the priority of \c i to \c p. 251 252 /** 253 This method sets the priority of item \c i to \c p. 254 \pre \c i must be stored in the heap with priority at most \c 255 p relative to \c Compare. 256 */ 168 257 void increase(const Item &i, const Prio &p) { 169 258 int idx = iim[i]; … … 171 260 } 172 261 173 ///\e 262 ///Returns if \c item is in, has already been in, or has never been in the heap. 263 264 /** 265 This method returns PRE_HEAP if \c item has never been in the 266 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 267 otherwise. In the latter case it is possible that \c item will 268 get back to the heap again. 269 */ 174 270 state_enum state(const Item &i) const { 175 271 int s = iim[i]; -
src/lemon/concept/path.h
r1228 r1270 37 37 //! \param GR The graph type in which the path is. 38 38 //! 39 //! In a sense, the path can be treated as a graph, for i shas \c NodeIt39 //! In a sense, the path can be treated as a graph, for it has \c NodeIt 40 40 //! and \c EdgeIt with the same usage. These types converts to the \c Node 41 41 //! and \c Edge of the original graph. … … 173 173 * 174 174 * While the builder is active (after the first modifying 175 * operation and until the call of \ref commit()) 176 * the underlining Path is in a177 * "transitional" state (operations onit have undefined result).175 * operation and until the call of \ref commit()) the 176 * underlining Path is in a "transitional" state (operations on 177 * it have undefined result). 178 178 */ 179 179 class Builder { … … 191 191 /// Sets the starting node of the path. Edge added to the path 192 192 /// afterwards have to be incident to this node. 193 /// You \em must start building an emp ry path with thisfunctions.193 /// You \em must start building an empty path with these functions. 194 194 /// (And you \em must \em not use it later). 195 195 /// \sa pushFront() … … 216 216 ///Reserve (front) storage for the builder in advance. 217 217 218 ///If you know a n reasonable upper bound ofthe number of the edges218 ///If you know a reasonable upper bound on the number of the edges 219 219 ///to add to the front of the path, 220 220 ///using this function you may speed up the building. … … 222 222 ///Reserve (back) storage for the builder in advance. 223 223 224 ///If you know a n reasonable upper bound ofthe number of the edges224 ///If you know a reasonable upper bound on the number of the edges 225 225 ///to add to the back of the path, 226 226 ///using this function you may speed up the building. -
src/lemon/fib_heap.h
r1204 r1270 89 89 }; 90 90 91 ///The constructor 92 93 /** 94 \c _iimap should be given to the constructor, since it is 95 used internally to handle the cross references. 96 */ 91 97 explicit FibHeap(ItemIntMap &_iimap) 92 98 : minimum(0), iimap(_iimap), num_items() {} 99 100 ///The constructor 101 102 /** 103 \c _iimap should be given to the constructor, since it is used 104 internally to handle the cross references. \c _comp is an 105 object for ordering of the priorities. 106 */ 93 107 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 94 108 iimap(_iimap), comp(_comp), num_items() {} 95 109 96 110 ///The number of items stored in the heap. -
src/lemon/min_cost_flow.h
r1164 r1270 37 37 /// 38 38 /// 39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements 40 /// an algorithm for finding a flow of value \c k 41 /// having minimal total cost 42 /// from a given source node to a given target node in an 43 /// edge-weighted directed graph. To this end, 44 /// the edge-capacities and edge-weitghs have to be nonnegative. 45 /// The edge-capacities should be integers, but the edge-weights can be 46 /// integers, reals or of other comparable numeric type. 47 /// This algorithm is intended to use only for small values of \c k, 48 /// since it is only polynomial in k, 49 /// not in the length of k (which is log k). 50 /// In order to find the minimum cost flow of value \c k it 51 /// finds the minimum cost flow of value \c i for every 52 /// \c i between 0 and \c k. 39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an 40 /// algorithm for finding a flow of value \c k having minimal total 41 /// cost from a given source node to a given target node in an 42 /// edge-weighted directed graph. To this end, the edge-capacities 43 /// and edge-weights have to be nonnegative. The edge-capacities 44 /// should be integers, but the edge-weights can be integers, reals 45 /// or of other comparable numeric type. This algorithm is intended 46 /// to be used only for small values of \c k, since it is only 47 /// polynomial in k, not in the length of k (which is log k): in 48 /// order to find the minimum cost flow of value \c k it finds the 49 /// minimum cost flow of value \c i for every \c i between 0 and \c 50 /// k. 53 51 /// 54 52 ///\param Graph The directed graph type the algorithm runs on. … … 150 148 potential.set(n, potential[n]+dijkstra.distMap()[n]); 151 149 152 //Augmenting on the s ortest path150 //Augmenting on the shortest path 153 151 Node n=t; 154 152 ResGraphEdge e; … … 227 225 228 226 This function checks, whether the given flow and potential 229 satisf iy the complementary slackness cnditions (i.e. these are optimal).227 satisfy the complementary slackness conditions (i.e. these are optimal). 230 228 This function only checks optimality, doesn't bother with feasibility. 231 229 For testing purpose. -
src/lemon/utility.h
r1256 r1270 38 38 { 39 39 40 /// Basic type for defining "tags". A "YES" condi dion for enable_if.40 /// Basic type for defining "tags". A "YES" condition for enable_if. 41 41 42 42 /// \todo This should go to a separate "basic_types.h" (or something) … … 46 46 }; 47 47 48 /// Basic type for defining "tags". A "NO" condi dion for enable_if.48 /// Basic type for defining "tags". A "NO" condition for enable_if. 49 49 struct False { 50 50 static const bool value = false;
Note: See TracChangeset
for help on using the changeset viewer.
