Changes in / [716:f47b6c94577e:717:684964884a2e] in lemon-1.2
- Files:
-
- 9 added
- 22 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r663 r715 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 247 239 any kind of path structure. 248 240 249 \sa lemon::concepts::Path 241 \sa \ref concepts::Path "Path concept" 242 */ 243 244 /** 245 @defgroup heaps Heap Structures 246 @ingroup datas 247 \brief %Heap structures implemented in LEMON. 248 249 This group contains the heap structures implemented in LEMON. 250 251 LEMON provides several heap classes. They are efficient implementations 252 of the abstract data type \e priority \e queue. They store items with 253 specified values called \e priorities in such a way that finding and 254 removing the item with minimum priority are efficient. 255 The basic operations are adding and erasing items, changing the priority 256 of an item, etc. 257 258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 259 The heap implementations have the same interface, thus any of them can be 260 used easily in such algorithms. 261 262 \sa \ref concepts::Heap "Heap concept" 263 */ 264 265 /** 266 @defgroup matrices Matrices 267 @ingroup datas 268 \brief Two dimensional data storages implemented in LEMON. 269 270 This group contains two dimensional data storages implemented in LEMON. 250 271 */ 251 272 … … 257 278 This group contains some data structures implemented in LEMON in 258 279 order to make it easier to implement combinatorial algorithms. 280 */ 281 282 /** 283 @defgroup geomdat Geometric Data Structures 284 @ingroup auxdat 285 \brief Geometric data structures implemented in LEMON. 286 287 This group contains geometric data structures implemented in LEMON. 288 289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 290 vector with the usual operations. 291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the 292 rectangular bounding box of a set of \ref lemon::dim2::Point 293 "dim2::Point"'s. 294 */ 295 296 /** 297 @defgroup matrices Matrices 298 @ingroup auxdat 299 \brief Two dimensional data storages implemented in LEMON. 300 301 This group contains two dimensional data storages implemented in LEMON. 259 302 */ 260 303 … … 299 342 300 343 /** 344 @defgroup spantree Minimum Spanning Tree Algorithms 345 @ingroup algs 346 \brief Algorithms for finding minimum cost spanning trees and arborescences. 347 348 This group contains the algorithms for finding minimum cost spanning 349 trees and arborescences. 350 */ 351 352 /** 301 353 @defgroup max_flow Maximum Flow Algorithms 302 354 @ingroup algs … … 376 428 377 429 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 378 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]430 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 379 431 380 432 LEMON contains several algorithms related to minimum cut problems: … … 389 441 If you want to find minimum cut just between two distinict nodes, 390 442 see the \ref max_flow "maximum flow problem". 391 */392 393 /**394 @defgroup graph_properties Connectivity and Other Graph Properties395 @ingroup algs396 \brief Algorithms for discovering the graph properties397 398 This group contains the algorithms for discovering the graph properties399 like connectivity, bipartiteness, euler property, simplicity etc.400 401 \image html edge_biconnected_components.png402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth403 */404 405 /**406 @defgroup planar Planarity Embedding and Drawing407 @ingroup algs408 \brief Algorithms for planarity checking, embedding and drawing409 410 This group contains the algorithms for planarity checking,411 embedding and drawing.412 413 \image html planar.png414 \image latex planar.eps "Plane graph" width=\textwidth415 443 */ 416 444 … … 456 484 457 485 /** 458 @defgroup spantree Minimum Spanning Tree Algorithms 459 @ingroup algs 460 \brief Algorithms for finding minimum cost spanning trees and arborescences. 461 462 This group contains the algorithms for finding minimum cost spanning 463 trees and arborescences. 486 @defgroup graph_properties Connectivity and Other Graph Properties 487 @ingroup algs 488 \brief Algorithms for discovering the graph properties 489 490 This group contains the algorithms for discovering the graph properties 491 like connectivity, bipartiteness, euler property, simplicity etc. 492 493 \image html connected_components.png 494 \image latex connected_components.eps "Connected components" width=\textwidth 495 */ 496 497 /** 498 @defgroup planar Planarity Embedding and Drawing 499 @ingroup algs 500 \brief Algorithms for planarity checking, embedding and drawing 501 502 This group contains the algorithms for planarity checking, 503 embedding and drawing. 504 505 \image html planar.png 506 \image latex planar.eps "Plane graph" width=\textwidth 507 */ 508 509 /** 510 @defgroup approx Approximation Algorithms 511 @ingroup algs 512 \brief Approximation algorithms. 513 514 This group contains the approximation and heuristic algorithms 515 implemented in LEMON. 464 516 */ 465 517 … … 471 523 This group contains some algorithms implemented in LEMON 472 524 in order to make it easier to implement complex algorithms. 473 */474 475 /**476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 525 */ 483 526 … … 588 631 589 632 /** 590 @defgroup dimacs_group DIMACS format633 @defgroup dimacs_group DIMACS Format 591 634 @ingroup io_group 592 635 \brief Read and write files in DIMACS format … … 650 693 651 694 /** 695 @defgroup tools Standalone Utility Applications 696 697 Some utility applications are listed here. 698 699 The standard compilation procedure (<tt>./configure;make</tt>) will compile 700 them, as well. 701 */ 702 703 /** 652 704 \anchor demoprograms 653 705 … … 661 713 */ 662 714 663 /**664 @defgroup tools Standalone Utility Applications665 666 Some utility applications are listed here.667 668 The standard compilation procedure (<tt>./configure;make</tt>) will compile669 them, as well.670 */671 672 715 } -
lemon/Makefile.am
r667 r708 58 58 lemon/arg_parser.h \ 59 59 lemon/assert.h \ 60 lemon/bellman_ford.h \ 60 61 lemon/bfs.h \ 61 62 lemon/bin_heap.h \ 63 lemon/binom_heap.h \ 64 lemon/bucket_heap.h \ 62 65 lemon/cbc.h \ 63 66 lemon/circulation.h \ … … 77 80 lemon/error.h \ 78 81 lemon/euler.h \ 82 lemon/fib_heap.h \ 83 lemon/fourary_heap.h \ 79 84 lemon/full_graph.h \ 80 85 lemon/glpk.h \ … … 83 88 lemon/grid_graph.h \ 84 89 lemon/hypercube_graph.h \ 90 lemon/kary_heap.h \ 85 91 lemon/kruskal.h \ 86 92 lemon/hao_orlin.h \ … … 91 97 lemon/lp_base.h \ 92 98 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \94 99 lemon/maps.h \ 95 100 lemon/matching.h \ … … 98 103 lemon/nauty_reader.h \ 99 104 lemon/network_simplex.h \ 105 lemon/pairing_heap.h \ 100 106 lemon/path.h \ 101 107 lemon/preflow.h \ 108 lemon/radix_heap.h \ 102 109 lemon/radix_sort.h \ 103 110 lemon/random.h \ -
lemon/bfs.h
r716 r717 415 415 ///The simplest way to execute the BFS algorithm is to use one of the 416 416 ///member functions called \ref run(Node) "run()".\n 417 ///If you need more control on the execution, firstyou have to call418 ///\ref init() , then you can add several source nodes with417 ///If you need better control on the execution, you have to call 418 ///\ref init() first, then you can add several source nodes with 419 419 ///\ref addSource(). Finally the actual path computation can be 420 420 ///performed with one of the \ref start() functions. … … 1423 1423 /// The simplest way to execute the BFS algorithm is to use one of the 1424 1424 /// member functions called \ref run(Node) "run()".\n 1425 /// If you need more control on the execution, firstyou have to call1426 /// \ref init() , then you can add several source nodes with1425 /// If you need better control on the execution, you have to call 1426 /// \ref init() first, then you can add several source nodes with 1427 1427 /// \ref addSource(). Finally the actual path computation can be 1428 1428 /// performed with one of the \ref start() functions. -
lemon/bin_heap.h
r584 r711 20 20 #define LEMON_BIN_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Binary Heap implementation.24 ///\brief Binary heap implementation. 25 25 26 26 #include <vector> … … 30 30 namespace lemon { 31 31 32 /// \ingroup auxdat32 /// \ingroup heaps 33 33 /// 34 /// \brief A Binary Heap implementation.34 /// \brief Binary heap data structure. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 38 ///A \e heap is a data structure for storing items with specified values 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c Comp specifies the ordering of the priorities. 41 ///In a heap one can change the priority of an item, add or erase an 42 ///item, etc. 36 /// This class implements the \e binary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 43 38 /// 44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 46 ///to handle the cross references. 47 ///\tparam Comp A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 49 /// 50 ///\sa FibHeap 51 ///\sa Dijkstra 52 template <typename PR, typename IM, typename Comp = std::less<PR> > 39 /// \tparam PR Type of the priorities of the items. 40 /// \tparam IM A read-writable item map with \c int values, used 41 /// internally to handle the cross references. 42 /// \tparam CMP A functor class for comparing the priorities. 43 /// The default is \c std::less<PR>. 44 #ifdef DOXYGEN 45 template <typename PR, typename IM, typename CMP> 46 #else 47 template <typename PR, typename IM, typename CMP = std::less<PR> > 48 #endif 53 49 class BinHeap { 54 55 50 public: 56 ///\e 51 52 /// Type of the item-int map. 57 53 typedef IM ItemIntMap; 58 /// \e54 /// Type of the priorities. 59 55 typedef PR Prio; 60 /// \e56 /// Type of the items stored in the heap. 61 57 typedef typename ItemIntMap::Key Item; 62 /// \e58 /// Type of the item-priority pairs. 63 59 typedef std::pair<Item,Prio> Pair; 64 /// \e65 typedef C ompCompare;66 67 /// \brief Type to represent the items states.68 /// 69 /// Each Item element have a state associated to it. It maybe "in heap",70 /// "pre heap" or "postheap". The latter two are indifferent from the60 /// Functor type for comparing the priorities. 61 typedef CMP Compare; 62 63 /// \brief Type to represent the states of the items. 64 /// 65 /// Each item has a state associated to it. It can be "in heap", 66 /// "pre-heap" or "post-heap". The latter two are indifferent from the 71 67 /// heap's point of view, but may be useful to the user. 72 68 /// … … 85 81 86 82 public: 87 /// \brief The constructor. 88 /// 89 /// The constructor. 90 /// \param map should be given to the constructor, since it is used 91 /// internally to handle the cross references. The value of the map 92 /// must be \c PRE_HEAP (<tt>-1</tt>) for every item. 83 84 /// \brief Constructor. 85 /// 86 /// Constructor. 87 /// \param map A map that assigns \c int values to the items. 88 /// It is used internally to handle the cross references. 89 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 93 90 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 91 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 99 /// internally to handle the cross references. The value of the map 100 /// should be PRE_HEAP (-1) for each element. 101 /// 102 /// \param comp The comparator function object. 92 /// \brief Constructor. 93 /// 94 /// Constructor. 95 /// \param map A map that assigns \c int values to the items. 96 /// It is used internally to handle the cross references. 97 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 98 /// \param comp The function object used for comparing the priorities. 103 99 BinHeap(ItemIntMap &map, const Compare &comp) 104 100 : _iim(map), _comp(comp) {} 105 101 106 102 107 /// The number of items stored in the heap.108 /// 109 /// \brief Returns the number of items stored in the heap.103 /// \brief The number of items stored in the heap. 104 /// 105 /// This function returns the number of items stored in the heap. 110 106 int size() const { return _data.size(); } 111 107 112 /// \brief Check s if the heap stores no items.113 /// 114 /// Returns \c true if and only if the heap stores no items.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 115 111 bool empty() const { return _data.empty(); } 116 112 117 /// \brief Make empty this heap. 118 /// 119 /// Make empty this heap. It does not change the cross reference map. 120 /// If you want to reuse what is not surely empty you should first clear 121 /// the heap and after that you should set the cross reference map for 122 /// each item to \c PRE_HEAP. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 123 120 void clear() { 124 121 _data.clear(); … … 128 125 static int parent(int i) { return (i-1)/2; } 129 126 130 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 131 128 bool less(const Pair &p1, const Pair &p2) const { 132 129 return _comp(p1.second, p2.second); 133 130 } 134 131 135 int bubble _up(int hole, Pair p) {132 int bubbleUp(int hole, Pair p) { 136 133 int par = parent(hole); 137 134 while( hole>0 && less(p,_data[par]) ) { … … 144 141 } 145 142 146 int bubble _down(int hole, Pair p, int length) {147 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 148 145 while(child < length) { 149 146 if( less(_data[child-1], _data[child]) ) { … … 154 151 move(_data[child], hole); 155 152 hole = child; 156 child = second _child(hole);153 child = secondChild(hole); 157 154 } 158 155 child--; … … 172 169 173 170 public: 171 174 172 /// \brief Insert a pair of item and priority into the heap. 175 173 /// 176 /// Adds \c p.first to the heap with priority \c p.second. 174 /// This function inserts \c p.first to the heap with priority 175 /// \c p.second. 177 176 /// \param p The pair to insert. 177 /// \pre \c p.first must not be stored in the heap. 178 178 void push(const Pair &p) { 179 179 int n = _data.size(); 180 180 _data.resize(n+1); 181 bubble_up(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given heap. 185 /// 186 /// Adds \c i to the heap with priority \c p. 181 bubbleUp(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given priority. 185 /// 186 /// This function inserts the given item into the heap with the 187 /// given priority. 187 188 /// \param i The item to insert. 188 189 /// \param p The priority of the item. 190 /// \pre \e i must not be stored in the heap. 189 191 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 190 192 191 /// \brief Returns the item with minimum priority relative to \c Compare. 192 /// 193 /// This method returns the item with minimum priority relative to \c 194 /// Compare. 195 /// \pre The heap must be nonempty. 193 /// \brief Return the item having minimum priority. 194 /// 195 /// This function returns the item having minimum priority. 196 /// \pre The heap must be non-empty. 196 197 Item top() const { 197 198 return _data[0].first; 198 199 } 199 200 200 /// \brief Returns the minimum priority relative to \c Compare.201 /// 202 /// It returns the minimum priority relative to \c Compare.203 /// \pre The heap must be non empty.201 /// \brief The minimum priority. 202 /// 203 /// This function returns the minimum priority. 204 /// \pre The heap must be non-empty. 204 205 Prio prio() const { 205 206 return _data[0].second; 206 207 } 207 208 208 /// \brief Deletes the item with minimum priority relative to \c Compare. 209 /// 210 /// This method deletes the item with minimum priority relative to \c 211 /// Compare from the heap. 209 /// \brief Remove the item having minimum priority. 210 /// 211 /// This function removes the item having minimum priority. 212 212 /// \pre The heap must be non-empty. 213 213 void pop() { … … 215 215 _iim.set(_data[0].first, POST_HEAP); 216 216 if (n > 0) { 217 bubble _down(0, _data[n], n);217 bubbleDown(0, _data[n], n); 218 218 } 219 219 _data.pop_back(); 220 220 } 221 221 222 /// \brief Deletes \c i from the heap. 223 /// 224 /// This method deletes item \c i from the heap. 225 /// \param i The item to erase. 226 /// \pre The item should be in the heap. 222 /// \brief Remove the given item from the heap. 223 /// 224 /// This function removes the given item from the heap if it is 225 /// already stored. 226 /// \param i The item to delete. 227 /// \pre \e i must be in the heap. 227 228 void erase(const Item &i) { 228 229 int h = _iim[i]; … … 230 231 _iim.set(_data[h].first, POST_HEAP); 231 232 if( h < n ) { 232 if ( bubble _up(h, _data[n]) == h) {233 bubble _down(h, _data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 234 235 } 235 236 } … … 237 238 } 238 239 239 240 /// \brief Returns the priority of \c i. 241 /// 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 244 /// \pre \c i must be in the heap. 240 /// \brief The priority of the given item. 241 /// 242 /// This function returns the priority of the given item. 243 /// \param i The item. 244 /// \pre \e i must be in the heap. 245 245 Prio operator[](const Item &i) const { 246 246 int idx = _iim[i]; … … 248 248 } 249 249 250 /// \brief \c i gets to the heap with priority \c p independently 251 /// if \c i was already there. 252 /// 253 /// This method calls \ref push(\c i, \c p) if \c i is not stored 254 /// in the heap and sets the priority of \c i to \c p otherwise. 250 /// \brief Set the priority of an item or insert it, if it is 251 /// not stored in the heap. 252 /// 253 /// This method sets the priority of the given item if it is 254 /// already stored in the heap. Otherwise it inserts the given 255 /// item into the heap with the given priority. 255 256 /// \param i The item. 256 257 /// \param p The priority. … … 261 262 } 262 263 else if( _comp(p, _data[idx].second) ) { 263 bubble _up(idx, Pair(i,p));264 bubbleUp(idx, Pair(i,p)); 264 265 } 265 266 else { 266 bubble _down(idx, Pair(i,p), _data.size());267 } 268 } 269 270 /// \brief Decrease s the priority of \c i to \c p.271 /// 272 /// This method decreases the priority of item \c i to \c p.267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 } 270 271 /// \brief Decrease the priority of an item to the given value. 272 /// 273 /// This function decreases the priority of an item to the given value. 273 274 /// \param i The item. 274 275 /// \param p The priority. 275 /// \pre \c i must be stored in the heap with priority at least \c 276 /// p relative to \c Compare. 276 /// \pre \e i must be stored in the heap with priority at least \e p. 277 277 void decrease(const Item &i, const Prio &p) { 278 278 int idx = _iim[i]; 279 bubble _up(idx, Pair(i,p));280 } 281 282 /// \brief Increase s the priority of \c i to \c p.283 /// 284 /// This method sets the priority of item \c i to \c p.279 bubbleUp(idx, Pair(i,p)); 280 } 281 282 /// \brief Increase the priority of an item to the given value. 283 /// 284 /// This function increases the priority of an item to the given value. 285 285 /// \param i The item. 286 286 /// \param p The priority. 287 /// \pre \c i must be stored in the heap with priority at most \c 288 /// p relative to \c Compare. 287 /// \pre \e i must be stored in the heap with priority at most \e p. 289 288 void increase(const Item &i, const Prio &p) { 290 289 int idx = _iim[i]; 291 bubble _down(idx, Pair(i,p), _data.size());292 } 293 294 /// \brief Return s if \c item is in, has already been in, or has295 /// never been in the heap.296 /// 297 /// This method returns PRE_HEAP if \c item has never been in the298 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP299 /// otherwise. In the latter case it is possible that \c item will300 /// get backto the heap again.290 bubbleDown(idx, Pair(i,p), _data.size()); 291 } 292 293 /// \brief Return the state of an item. 294 /// 295 /// This method returns \c PRE_HEAP if the given item has never 296 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 297 /// and \c POST_HEAP otherwise. 298 /// In the latter case it is possible that the item will get back 299 /// to the heap again. 301 300 /// \param i The item. 302 301 State state(const Item &i) const { … … 307 306 } 308 307 309 /// \brief Set s the state of the \citem in the heap.310 /// 311 /// Sets the state of the \c item in the heap. It can be used to312 /// manually clear the heap when it is important to achive the313 /// better time complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 314 313 /// \param i The item. 315 314 /// \param st The state. It should not be \c IN_HEAP. … … 328 327 } 329 328 330 /// \brief Replaces an item in the heap. 331 /// 332 /// The \c i item is replaced with \c j item. The \c i item should 333 /// be in the heap, while the \c j should be out of the heap. The 334 /// \c i item will out of the heap and \c j will be in the heap 335 /// with the same prioriority as prevoiusly the \c i item. 329 /// \brief Replace an item in the heap. 330 /// 331 /// This function replaces item \c i with item \c j. 332 /// Item \c i must be in the heap, while \c j must be out of the heap. 333 /// After calling this method, item \c i will be out of the 334 /// heap and \c j will be in the heap with the same prioriority 335 /// as item \c i had before. 336 336 void replace(const Item& i, const Item& j) { 337 337 int idx = _iim[i]; -
lemon/bits/edge_set_extender.h
r617 r685 538 538 539 539 public: 540 ArcMap(const Graph& _g)540 explicit ArcMap(const Graph& _g) 541 541 : Parent(_g) {} 542 542 ArcMap(const Graph& _g, const _Value& _v) … … 562 562 563 563 public: 564 EdgeMap(const Graph& _g)564 explicit EdgeMap(const Graph& _g) 565 565 : Parent(_g) {} 566 566 -
lemon/bits/graph_extender.h
r617 r685 605 605 606 606 public: 607 NodeMap(const Graph& graph)607 explicit NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 ArcMap(const Graph& graph)631 explicit ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 EdgeMap(const Graph& graph)655 explicit EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/circulation.h
r641 r715 73 73 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" 74 74 /// concept. 75 #ifdef DOXYGEN 76 typedef GR::ArcMap<Value> FlowMap; 77 #else 75 78 typedef typename Digraph::template ArcMap<Value> FlowMap; 79 #endif 76 80 77 81 /// \brief Instantiates a FlowMap. … … 88 92 /// The elevator type used by the algorithm. 89 93 /// 90 /// \sa Elevator 91 /// \sa LinkedElevator 94 /// \sa Elevator, LinkedElevator 95 #ifdef DOXYGEN 96 typedef lemon::Elevator<GR, GR::Node> Elevator; 97 #else 92 98 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 99 #endif 93 100 94 101 /// \brief Instantiates an Elevator. … … 451 458 } 452 459 453 /// \brief Sets the tolerance used by algorithm. 454 /// 455 /// Sets the tolerance used by algorithm. 456 Circulation& tolerance(const Tolerance& tolerance) const { 460 /// \brief Sets the tolerance used by the algorithm. 461 /// 462 /// Sets the tolerance object used by the algorithm. 463 /// \return <tt>(*this)</tt> 464 Circulation& tolerance(const Tolerance& tolerance) { 457 465 _tol = tolerance; 458 466 return *this; … … 461 469 /// \brief Returns a const reference to the tolerance. 462 470 /// 463 /// Returns a const reference to the tolerance. 471 /// Returns a const reference to the tolerance object used by 472 /// the algorithm. 464 473 const Tolerance& tolerance() const { 465 return tolerance;474 return _tol; 466 475 } 467 476 468 477 /// \name Execution Control 469 478 /// The simplest way to execute the algorithm is to call \ref run().\n 470 /// If you need morecontrol on the initial solution or the execution,471 /// first you have to call one of the \ref init() functions, then479 /// If you need better control on the initial solution or the execution, 480 /// you have to call one of the \ref init() functions first, then 472 481 /// the \ref start() function. 473 482 -
lemon/concepts/heap.h
r584 r710 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H 20 #define LEMON_CONCEPTS_HEAP_H 21 19 22 ///\ingroup concept 20 23 ///\file 21 24 ///\brief The concept of heaps. 22 25 23 #ifndef LEMON_CONCEPTS_HEAP_H24 #define LEMON_CONCEPTS_HEAP_H25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 38 /// This concept class describes the main interface of heaps. 39 /// The various \ref heaps "heap structures" are efficient 40 /// implementations of the abstract data type \e priority \e queue. 41 /// They store items with specified values called \e priorities 42 /// in such a way that finding and removing the item with minimum 43 /// priority are efficient. The basic operations are adding and 44 /// erasing items, changing the priority of an item, etc. 43 45 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 47 /// Any class that conforms to this concept can be used easily in such 48 /// algorithms. 49 /// 50 /// \tparam PR Type of the priorities of the items. 51 /// \tparam IM A read-writable item map with \c int values, used 46 52 /// internally to handle the cross references. 47 /// \tparam C omp A functor class for the ordering ofthe priorities.53 /// \tparam CMP A functor class for comparing the priorities. 48 54 /// The default is \c std::less<PR>. 49 55 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename C omp = std::less<PR>>56 template <typename PR, typename IM, typename CMP> 51 57 #else 52 template <typename PR, typename IM >58 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 59 #endif 54 60 class Heap { … … 65 71 /// 66 72 /// Each item has a state associated to it. It can be "in heap", 67 /// "pre heap" or "post heap". The later two are indifferent 68 /// from the point of view of the heap, but may be useful for 69 /// the user. 73 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 70 75 /// 71 76 /// The item-int map must be initialized in such way that it assigns … … 73 78 enum State { 74 79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = -1, ///< = -1. The "pre 76 POST_HEAP = -2 ///< = -2. The "post 80 PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. 81 POST_HEAP = -2 ///< = -2. The "post-heap" state constant. 77 82 }; 78 83 79 /// \brief The constructor.80 /// 81 /// The constructor.84 /// \brief Constructor. 85 /// 86 /// Constructor. 82 87 /// \param map A map that assigns \c int values to keys of type 83 88 /// \c Item. It is used internally by the heap implementations to 84 89 /// handle the cross references. The assigned value must be 85 /// \c PRE_HEAP (<tt>-1</tt>) for e veryitem.90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 86 91 explicit Heap(ItemIntMap &map) {} 87 92 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to keys of type 97 /// \c Item. It is used internally by the heap implementations to 98 /// handle the cross references. The assigned value must be 99 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 100 /// \param comp The function object used for comparing the priorities. 101 explicit Heap(ItemIntMap &map, const CMP &comp) {} 102 88 103 /// \brief The number of items stored in the heap. 89 104 /// 90 /// Returns the number of items stored in the heap.105 /// This function returns the number of items stored in the heap. 91 106 int size() const { return 0; } 92 107 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 96 111 bool empty() const { return false; } 97 112 98 /// \brief Makes the heap empty. 99 /// 100 /// Makes the heap empty. 101 void clear(); 102 103 /// \brief Inserts an item into the heap with the given priority. 104 /// 105 /// Inserts the given item into the heap with the given priority. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 120 void clear() {} 121 122 /// \brief Insert an item into the heap with the given priority. 123 /// 124 /// This function inserts the given item into the heap with the 125 /// given priority. 106 126 /// \param i The item to insert. 107 127 /// \param p The priority of the item. 128 /// \pre \e i must not be stored in the heap. 108 129 void push(const Item &i, const Prio &p) {} 109 130 110 /// \brief Return sthe item having minimum priority.111 /// 112 /// Returns the item having minimum priority.131 /// \brief Return the item having minimum priority. 132 /// 133 /// This function returns the item having minimum priority. 113 134 /// \pre The heap must be non-empty. 114 135 Item top() const {} … … 116 137 /// \brief The minimum priority. 117 138 /// 118 /// Returns the minimum priority.139 /// This function returns the minimum priority. 119 140 /// \pre The heap must be non-empty. 120 141 Prio prio() const {} 121 142 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.143 /// \brief Remove the item having minimum priority. 144 /// 145 /// This function removes the item having minimum priority. 125 146 /// \pre The heap must be non-empty. 126 147 void pop() {} 127 148 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 149 /// \brief Remove the given item from the heap. 150 /// 151 /// This function removes the given item from the heap if it is 152 /// already stored. 131 153 /// \param i The item to delete. 154 /// \pre \e i must be in the heap. 132 155 void erase(const Item &i) {} 133 156 134 /// \brief The priority of an item.135 /// 136 /// Returns the priority of the given item.137 /// \param i The item. 138 /// \pre \ ci must be in the heap.157 /// \brief The priority of the given item. 158 /// 159 /// This function returns the priority of the given item. 160 /// \param i The item. 161 /// \pre \e i must be in the heap. 139 162 Prio operator[](const Item &i) const {} 140 163 141 /// \brief Set s the priority of an item or insertsit, if it is164 /// \brief Set the priority of an item or insert it, if it is 142 165 /// not stored in the heap. 143 166 /// 144 167 /// This method sets the priority of the given item if it is 145 /// already stored in the heap. 146 /// Otherwise it inserts the given itemwith the given priority.168 /// already stored in the heap. Otherwise it inserts the given 169 /// item into the heap with the given priority. 147 170 /// 148 171 /// \param i The item. … … 150 173 void set(const Item &i, const Prio &p) {} 151 174 152 /// \brief Decrease sthe priority of an item to the given value.153 /// 154 /// Decreases the priority of an item to the given value.175 /// \brief Decrease the priority of an item to the given value. 176 /// 177 /// This function decreases the priority of an item to the given value. 155 178 /// \param i The item. 156 179 /// \param p The priority. 157 /// \pre \ c i must be stored in the heap with priority at least \cp.180 /// \pre \e i must be stored in the heap with priority at least \e p. 158 181 void decrease(const Item &i, const Prio &p) {} 159 182 160 /// \brief Increase sthe priority of an item to the given value.161 /// 162 /// Increases the priority of an item to the given value.183 /// \brief Increase the priority of an item to the given value. 184 /// 185 /// This function increases the priority of an item to the given value. 163 186 /// \param i The item. 164 187 /// \param p The priority. 165 /// \pre \ c i must be stored in the heap with priority at most \cp.188 /// \pre \e i must be stored in the heap with priority at most \e p. 166 189 void increase(const Item &i, const Prio &p) {} 167 190 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 191 /// \brief Return the state of an item. 170 192 /// 171 193 /// This method returns \c PRE_HEAP if the given item has never … … 177 199 State state(const Item &i) const {} 178 200 179 /// \brief Set sthe state of an item in the heap.180 /// 181 /// Sets the state of the given item in the heap. It can be used182 /// to manually clear the heap when it is important to achive the183 /// better time complexity.201 /// \brief Set the state of an item in the heap. 202 /// 203 /// This function sets the state of the given item in the heap. 204 /// It can be used to manually clear the heap when it is important 205 /// to achive better time complexity. 184 206 /// \param i The item. 185 207 /// \param st The state. It should not be \c IN_HEAP. -
lemon/dfs.h
r716 r717 413 413 ///The simplest way to execute the DFS algorithm is to use one of the 414 414 ///member functions called \ref run(Node) "run()".\n 415 ///If you need more control on the execution, firstyou have to call416 ///\ref init() , then you can add a source node with \ref addSource()415 ///If you need better control on the execution, you have to call 416 ///\ref init() first, then you can add a source node with \ref addSource() 417 417 ///and perform the actual computation with \ref start(). 418 418 ///This procedure can be repeated if there are nodes that have not … … 1365 1365 /// The simplest way to execute the DFS algorithm is to use one of the 1366 1366 /// member functions called \ref run(Node) "run()".\n 1367 /// If you need more control on the execution, firstyou have to call1368 /// \ref init() , then you can add a source node with \ref addSource()1367 /// If you need better control on the execution, you have to call 1368 /// \ref init() first, then you can add a source node with \ref addSource() 1369 1369 /// and perform the actual computation with \ref start(). 1370 1370 /// This procedure can be repeated if there are nodes that have not -
lemon/dijkstra.h
r716 r717 590 590 ///The simplest way to execute the %Dijkstra algorithm is to use 591 591 ///one of the member functions called \ref run(Node) "run()".\n 592 ///If you need more control on the execution, firstyou have to call593 ///\ref init() , then you can add several source nodes with592 ///If you need better control on the execution, you have to call 593 ///\ref init() first, then you can add several source nodes with 594 594 ///\ref addSource(). Finally the actual path computation can be 595 595 ///performed with one of the \ref start() functions. -
lemon/dim2.h
r440 r714 22 22 #include <iostream> 23 23 24 ///\ingroup misc24 ///\ingroup geomdat 25 25 ///\file 26 26 ///\brief A simple two dimensional vector and a bounding box implementation 27 ///28 /// The class \ref lemon::dim2::Point "dim2::Point" implements29 /// a two dimensional vector with the usual operations.30 ///31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine32 /// the rectangular bounding box of a set of33 /// \ref lemon::dim2::Point "dim2::Point"'s.34 27 35 28 namespace lemon { … … 41 34 namespace dim2 { 42 35 43 /// \addtogroup misc36 /// \addtogroup geomdat 44 37 /// @{ 45 38 -
lemon/gomory_hu.h
r596 r713 360 360 /// \c t. 361 361 /// \code 362 /// Gomor uHu<Graph> gom(g, capacities);362 /// GomoryHu<Graph> gom(g, capacities); 363 363 /// gom.run(); 364 364 /// int cnt=0; 365 /// for(Gomor uHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;365 /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; 366 366 /// \endcode 367 367 class MinCutNodeIt … … 457 457 /// \c t. 458 458 /// \code 459 /// Gomor uHu<Graph> gom(g, capacities);459 /// GomoryHu<Graph> gom(g, capacities); 460 460 /// gom.run(); 461 461 /// int value=0; 462 /// for(Gomor uHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)462 /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) 463 463 /// value+=capacities[e]; 464 464 /// \endcode -
lemon/maps.h
r716 r717 23 23 #include <functional> 24 24 #include <vector> 25 #include <map> 25 26 26 27 #include <lemon/core.h> … … 29 30 ///\ingroup maps 30 31 ///\brief Miscellaneous property maps 31 32 #include <map>33 32 34 33 namespace lemon { … … 1819 1818 /// 1820 1819 /// IdMap provides a unique and immutable id for each item of the 1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1820 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1822 1821 /// - \b unique: different items get different ids, 1823 1822 /// - \b immutable: the id of an item does not change (even if you … … 1903 1902 1904 1903 /// This class provides simple invertable graph maps. 1905 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" 1906 /// and if a key is set to a new value then store it 1907 /// in the inverse map. 1908 /// 1904 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) 1905 /// and if a key is set to a new value, then stores it in the inverse map. 1909 1906 /// The values of the map can be accessed 1910 1907 /// with stl compatible forward iterator. 1908 /// 1909 /// This type is not reference map, so it cannot be modified with 1910 /// the subscript operator. 1911 1911 /// 1912 1912 /// \tparam GR The graph type. … … 1924 1924 template Map<V>::Type Map; 1925 1925 1926 typedef std::m ap<V, K> Container;1926 typedef std::multimap<V, K> Container; 1927 1927 Container _inv_map; 1928 1928 … … 1949 1949 /// iterator on the values of the map. The values can 1950 1950 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1951 /// They are considered with multiplicity, so each value is 1952 /// traversed for each item it is assigned to. 1951 1953 class ValueIterator 1952 1954 : public std::iterator<std::forward_iterator_tag, Value> { … … 2001 2003 void set(const Key& key, const Value& val) { 2002 2004 Value oldval = Map::operator[](key); 2003 typename Container::iterator it = _inv_map.find(oldval); 2004 if (it != _inv_map.end() && it->second == key) { 2005 _inv_map.erase(it); 2006 } 2007 _inv_map.insert(make_pair(val, key)); 2005 typename Container::iterator it; 2006 for (it = _inv_map.equal_range(oldval).first; 2007 it != _inv_map.equal_range(oldval).second; ++it) { 2008 if (it->second == key) { 2009 _inv_map.erase(it); 2010 break; 2011 } 2012 } 2013 _inv_map.insert(std::make_pair(val, key)); 2008 2014 Map::set(key, val); 2009 2015 } … … 2017 2023 } 2018 2024 2019 /// \brief Gives back the item by its value. 2020 /// 2021 /// Gives back the item by its value. 2022 Key operator()(const Value& key) const { 2023 typename Container::const_iterator it = _inv_map.find(key); 2025 /// \brief Gives back an item by its value. 2026 /// 2027 /// This function gives back an item that is assigned to 2028 /// the given value or \c INVALID if no such item exists. 2029 /// If there are more items with the same associated value, 2030 /// only one of them is returned. 2031 Key operator()(const Value& val) const { 2032 typename Container::const_iterator it = _inv_map.find(val); 2024 2033 return it != _inv_map.end() ? it->second : INVALID; 2025 2034 } … … 2033 2042 virtual void erase(const Key& key) { 2034 2043 Value val = Map::operator[](key); 2035 typename Container::iterator it = _inv_map.find(val); 2036 if (it != _inv_map.end() && it->second == key) { 2037 _inv_map.erase(it); 2044 typename Container::iterator it; 2045 for (it = _inv_map.equal_range(val).first; 2046 it != _inv_map.equal_range(val).second; ++it) { 2047 if (it->second == key) { 2048 _inv_map.erase(it); 2049 break; 2050 } 2038 2051 } 2039 2052 Map::erase(key); … … 2047 2060 for (int i = 0; i < int(keys.size()); ++i) { 2048 2061 Value val = Map::operator[](keys[i]); 2049 typename Container::iterator it = _inv_map.find(val); 2050 if (it != _inv_map.end() && it->second == keys[i]) { 2051 _inv_map.erase(it); 2062 typename Container::iterator it; 2063 for (it = _inv_map.equal_range(val).first; 2064 it != _inv_map.equal_range(val).second; ++it) { 2065 if (it->second == keys[i]) { 2066 _inv_map.erase(it); 2067 break; 2068 } 2052 2069 } 2053 2070 } … … 2085 2102 /// \brief Subscript operator. 2086 2103 /// 2087 /// Subscript operator. It gives back the item 2088 /// that was last assigned to the given value. 2104 /// Subscript operator. It gives back an item 2105 /// that is assigned to the given value or \c INVALID 2106 /// if no such item exists. 2089 2107 Value operator[](const Key& key) const { 2090 2108 return _inverted(key); … … 2255 2273 2256 2274 /// \brief Gives back the item belonging to a \e RangeId 2257 /// 2275 /// 2258 2276 /// Gives back the item belonging to a \e RangeId. 2259 2277 Item operator()(int id) const { … … 2312 2330 }; 2313 2331 2332 /// \brief Dynamic iterable \c bool map. 2333 /// 2334 /// This class provides a special graph map type which can store a 2335 /// \c bool value for graph items (\c Node, \c Arc or \c Edge). 2336 /// For both \c true and \c false values it is possible to iterate on 2337 /// the keys. 2338 /// 2339 /// This type is a reference map, so it can be modified with the 2340 /// subscript operator. 2341 /// 2342 /// \tparam GR The graph type. 2343 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2344 /// \c GR::Edge). 2345 /// 2346 /// \see IterableIntMap, IterableValueMap 2347 /// \see CrossRefMap 2348 template <typename GR, typename K> 2349 class IterableBoolMap 2350 : protected ItemSetTraits<GR, K>::template Map<int>::Type { 2351 private: 2352 typedef GR Graph; 2353 2354 typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt; 2355 typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent; 2356 2357 std::vector<K> _array; 2358 int _sep; 2359 2360 public: 2361 2362 /// Indicates that the map is reference map. 2363 typedef True ReferenceMapTag; 2364 2365 /// The key type 2366 typedef K Key; 2367 /// The value type 2368 typedef bool Value; 2369 /// The const reference type. 2370 typedef const Value& ConstReference; 2371 2372 private: 2373 2374 int position(const Key& key) const { 2375 return Parent::operator[](key); 2376 } 2377 2378 public: 2379 2380 /// \brief Reference to the value of the map. 2381 /// 2382 /// This class is similar to the \c bool type. It can be converted to 2383 /// \c bool and it provides the same operators. 2384 class Reference { 2385 friend class IterableBoolMap; 2386 private: 2387 Reference(IterableBoolMap& map, const Key& key) 2388 : _key(key), _map(map) {} 2389 public: 2390 2391 Reference& operator=(const Reference& value) { 2392 _map.set(_key, static_cast<bool>(value)); 2393 return *this; 2394 } 2395 2396 operator bool() const { 2397 return static_cast<const IterableBoolMap&>(_map)[_key]; 2398 } 2399 2400 Reference& operator=(bool value) { 2401 _map.set(_key, value); 2402 return *this; 2403 } 2404 Reference& operator&=(bool value) { 2405 _map.set(_key, _map[_key] & value); 2406 return *this; 2407 } 2408 Reference& operator|=(bool value) { 2409 _map.set(_key, _map[_key] | value); 2410 return *this; 2411 } 2412 Reference& operator^=(bool value) { 2413 _map.set(_key, _map[_key] ^ value); 2414 return *this; 2415 } 2416 private: 2417 Key _key; 2418 IterableBoolMap& _map; 2419 }; 2420 2421 /// \brief Constructor of the map with a default value. 2422 /// 2423 /// Constructor of the map with a default value. 2424 explicit IterableBoolMap(const Graph& graph, bool def = false) 2425 : Parent(graph) { 2426 typename Parent::Notifier* nf = Parent::notifier(); 2427 Key it; 2428 for (nf->first(it); it != INVALID; nf->next(it)) { 2429 Parent::set(it, _array.size()); 2430 _array.push_back(it); 2431 } 2432 _sep = (def ? _array.size() : 0); 2433 } 2434 2435 /// \brief Const subscript operator of the map. 2436 /// 2437 /// Const subscript operator of the map. 2438 bool operator[](const Key& key) const { 2439 return position(key) < _sep; 2440 } 2441 2442 /// \brief Subscript operator of the map. 2443 /// 2444 /// Subscript operator of the map. 2445 Reference operator[](const Key& key) { 2446 return Reference(*this, key); 2447 } 2448 2449 /// \brief Set operation of the map. 2450 /// 2451 /// Set operation of the map. 2452 void set(const Key& key, bool value) { 2453 int pos = position(key); 2454 if (value) { 2455 if (pos < _sep) return; 2456 Key tmp = _array[_sep]; 2457 _array[_sep] = key; 2458 Parent::set(key, _sep); 2459 _array[pos] = tmp; 2460 Parent::set(tmp, pos); 2461 ++_sep; 2462 } else { 2463 if (pos >= _sep) return; 2464 --_sep; 2465 Key tmp = _array[_sep]; 2466 _array[_sep] = key; 2467 Parent::set(key, _sep); 2468 _array[pos] = tmp; 2469 Parent::set(tmp, pos); 2470 } 2471 } 2472 2473 /// \brief Set all items. 2474 /// 2475 /// Set all items in the map. 2476 /// \note Constant time operation. 2477 void setAll(bool value) { 2478 _sep = (value ? _array.size() : 0); 2479 } 2480 2481 /// \brief Returns the number of the keys mapped to \c true. 2482 /// 2483 /// Returns the number of the keys mapped to \c true. 2484 int trueNum() const { 2485 return _sep; 2486 } 2487 2488 /// \brief Returns the number of the keys mapped to \c false. 2489 /// 2490 /// Returns the number of the keys mapped to \c false. 2491 int falseNum() const { 2492 return _array.size() - _sep; 2493 } 2494 2495 /// \brief Iterator for the keys mapped to \c true. 2496 /// 2497 /// Iterator for the keys mapped to \c true. It works 2498 /// like a graph item iterator, it can be converted to 2499 /// the key type of the map, incremented with \c ++ operator, and 2500 /// if the iterator leaves the last valid key, it will be equal to 2501 /// \c INVALID. 2502 class TrueIt : public Key { 2503 public: 2504 typedef Key Parent; 2505 2506 /// \brief Creates an iterator. 2507 /// 2508 /// Creates an iterator. It iterates on the 2509 /// keys mapped to \c true. 2510 /// \param map The IterableBoolMap. 2511 explicit TrueIt(const IterableBoolMap& map) 2512 : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), 2513 _map(&map) {} 2514 2515 /// \brief Invalid constructor \& conversion. 2516 /// 2517 /// This constructor initializes the iterator to be invalid. 2518 /// \sa Invalid for more details. 2519 TrueIt(Invalid) : Parent(INVALID), _map(0) {} 2520 2521 /// \brief Increment operator. 2522 /// 2523 /// Increment operator. 2524 TrueIt& operator++() { 2525 int pos = _map->position(*this); 2526 Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID); 2527 return *this; 2528 } 2529 2530 private: 2531 const IterableBoolMap* _map; 2532 }; 2533 2534 /// \brief Iterator for the keys mapped to \c false. 2535 /// 2536 /// Iterator for the keys mapped to \c false. It works 2537 /// like a graph item iterator, it can be converted to 2538 /// the key type of the map, incremented with \c ++ operator, and 2539 /// if the iterator leaves the last valid key, it will be equal to 2540 /// \c INVALID. 2541 class FalseIt : public Key { 2542 public: 2543 typedef Key Parent; 2544 2545 /// \brief Creates an iterator. 2546 /// 2547 /// Creates an iterator. It iterates on the 2548 /// keys mapped to \c false. 2549 /// \param map The IterableBoolMap. 2550 explicit FalseIt(const IterableBoolMap& map) 2551 : Parent(map._sep < int(map._array.size()) ? 2552 map._array.back() : INVALID), _map(&map) {} 2553 2554 /// \brief Invalid constructor \& conversion. 2555 /// 2556 /// This constructor initializes the iterator to be invalid. 2557 /// \sa Invalid for more details. 2558 FalseIt(Invalid) : Parent(INVALID), _map(0) {} 2559 2560 /// \brief Increment operator. 2561 /// 2562 /// Increment operator. 2563 FalseIt& operator++() { 2564 int pos = _map->position(*this); 2565 Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID); 2566 return *this; 2567 } 2568 2569 private: 2570 const IterableBoolMap* _map; 2571 }; 2572 2573 /// \brief Iterator for the keys mapped to a given value. 2574 /// 2575 /// Iterator for the keys mapped to a given value. It works 2576 /// like a graph item iterator, it can be converted to 2577 /// the key type of the map, incremented with \c ++ operator, and 2578 /// if the iterator leaves the last valid key, it will be equal to 2579 /// \c INVALID. 2580 class ItemIt : public Key { 2581 public: 2582 typedef Key Parent; 2583 2584 /// \brief Creates an iterator with a value. 2585 /// 2586 /// Creates an iterator with a value. It iterates on the 2587 /// keys mapped to the given value. 2588 /// \param map The IterableBoolMap. 2589 /// \param value The value. 2590 ItemIt(const IterableBoolMap& map, bool value) 2591 : Parent(value ? 2592 (map._sep > 0 ? 2593 map._array[map._sep - 1] : INVALID) : 2594 (map._sep < int(map._array.size()) ? 2595 map._array.back() : INVALID)), _map(&map) {} 2596 2597 /// \brief Invalid constructor \& conversion. 2598 /// 2599 /// This constructor initializes the iterator to be invalid. 2600 /// \sa Invalid for more details. 2601 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 2602 2603 /// \brief Increment operator. 2604 /// 2605 /// Increment operator. 2606 ItemIt& operator++() { 2607 int pos = _map->position(*this); 2608 int _sep = pos >= _map->_sep ? _map->_sep : 0; 2609 Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID); 2610 return *this; 2611 } 2612 2613 private: 2614 const IterableBoolMap* _map; 2615 }; 2616 2617 protected: 2618 2619 virtual void add(const Key& key) { 2620 Parent::add(key); 2621 Parent::set(key, _array.size()); 2622 _array.push_back(key); 2623 } 2624 2625 virtual void add(const std::vector<Key>& keys) { 2626 Parent::add(keys); 2627 for (int i = 0; i < int(keys.size()); ++i) { 2628 Parent::set(keys[i], _array.size()); 2629 _array.push_back(keys[i]); 2630 } 2631 } 2632 2633 virtual void erase(const Key& key) { 2634 int pos = position(key); 2635 if (pos < _sep) { 2636 --_sep; 2637 Parent::set(_array[_sep], pos); 2638 _array[pos] = _array[_sep]; 2639 Parent::set(_array.back(), _sep); 2640 _array[_sep] = _array.back(); 2641 _array.pop_back(); 2642 } else { 2643 Parent::set(_array.back(), pos); 2644 _array[pos] = _array.back(); 2645 _array.pop_back(); 2646 } 2647 Parent::erase(key); 2648 } 2649 2650 virtual void erase(const std::vector<Key>& keys) { 2651 for (int i = 0; i < int(keys.size()); ++i) { 2652 int pos = position(keys[i]); 2653 if (pos < _sep) { 2654 --_sep; 2655 Parent::set(_array[_sep], pos); 2656 _array[pos] = _array[_sep]; 2657 Parent::set(_array.back(), _sep); 2658 _array[_sep] = _array.back(); 2659 _array.pop_back(); 2660 } else { 2661 Parent::set(_array.back(), pos); 2662 _array[pos] = _array.back(); 2663 _array.pop_back(); 2664 } 2665 } 2666 Parent::erase(keys); 2667 } 2668 2669 virtual void build() { 2670 Parent::build(); 2671 typename Parent::Notifier* nf = Parent::notifier(); 2672 Key it; 2673 for (nf->first(it); it != INVALID; nf->next(it)) { 2674 Parent::set(it, _array.size()); 2675 _array.push_back(it); 2676 } 2677 _sep = 0; 2678 } 2679 2680 virtual void clear() { 2681 _array.clear(); 2682 _sep = 0; 2683 Parent::clear(); 2684 } 2685 2686 }; 2687 2688 2689 namespace _maps_bits { 2690 template <typename Item> 2691 struct IterableIntMapNode { 2692 IterableIntMapNode() : value(-1) {} 2693 IterableIntMapNode(int _value) : value(_value) {} 2694 Item prev, next; 2695 int value; 2696 }; 2697 } 2698 2699 /// \brief Dynamic iterable integer map. 2700 /// 2701 /// This class provides a special graph map type which can store an 2702 /// integer value for graph items (\c Node, \c Arc or \c Edge). 2703 /// For each non-negative value it is possible to iterate on the keys 2704 /// mapped to the value. 2705 /// 2706 /// This type is a reference map, so it can be modified with the 2707 /// subscript operator. 2708 /// 2709 /// \note The size of the data structure depends on the largest 2710 /// value in the map. 2711 /// 2712 /// \tparam GR The graph type. 2713 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2714 /// \c GR::Edge). 2715 /// 2716 /// \see IterableBoolMap, IterableValueMap 2717 /// \see CrossRefMap 2718 template <typename GR, typename K> 2719 class IterableIntMap 2720 : protected ItemSetTraits<GR, K>:: 2721 template Map<_maps_bits::IterableIntMapNode<K> >::Type { 2722 public: 2723 typedef typename ItemSetTraits<GR, K>:: 2724 template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent; 2725 2726 /// The key type 2727 typedef K Key; 2728 /// The value type 2729 typedef int Value; 2730 /// The graph type 2731 typedef GR Graph; 2732 2733 /// \brief Constructor of the map. 2734 /// 2735 /// Constructor of the map. It sets all values to -1. 2736 explicit IterableIntMap(const Graph& graph) 2737 : Parent(graph) {} 2738 2739 /// \brief Constructor of the map with a given value. 2740 /// 2741 /// Constructor of the map with a given value. 2742 explicit IterableIntMap(const Graph& graph, int value) 2743 : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) { 2744 if (value >= 0) { 2745 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 2746 lace(it); 2747 } 2748 } 2749 } 2750 2751 private: 2752 2753 void unlace(const Key& key) { 2754 typename Parent::Value& node = Parent::operator[](key); 2755 if (node.value < 0) return; 2756 if (node.prev != INVALID) { 2757 Parent::operator[](node.prev).next = node.next; 2758 } else { 2759 _first[node.value] = node.next; 2760 } 2761 if (node.next != INVALID) { 2762 Parent::operator[](node.next).prev = node.prev; 2763 } 2764 while (!_first.empty() && _first.back() == INVALID) { 2765 _first.pop_back(); 2766 } 2767 } 2768 2769 void lace(const Key& key) { 2770 typename Parent::Value& node = Parent::operator[](key); 2771 if (node.value < 0) return; 2772 if (node.value >= int(_first.size())) { 2773 _first.resize(node.value + 1, INVALID); 2774 } 2775 node.prev = INVALID; 2776 node.next = _first[node.value]; 2777 if (node.next != INVALID) { 2778 Parent::operator[](node.next).prev = key; 2779 } 2780 _first[node.value] = key; 2781 } 2782 2783 public: 2784 2785 /// Indicates that the map is reference map. 2786 typedef True ReferenceMapTag; 2787 2788 /// \brief Reference to the value of the map. 2789 /// 2790 /// This class is similar to the \c int type. It can 2791 /// be converted to \c int and it has the same operators. 2792 class Reference { 2793 friend class IterableIntMap; 2794 private: 2795 Reference(IterableIntMap& map, const Key& key) 2796 : _key(key), _map(map) {} 2797 public: 2798 2799 Reference& operator=(const Reference& value) { 2800 _map.set(_key, static_cast<const int&>(value)); 2801 return *this; 2802 } 2803 2804 operator const int&() const { 2805 return static_cast<const IterableIntMap&>(_map)[_key]; 2806 } 2807 2808 Reference& operator=(int value) { 2809 _map.set(_key, value); 2810 return *this; 2811 } 2812 Reference& operator++() { 2813 _map.set(_key, _map[_key] + 1); 2814 return *this; 2815 } 2816 int operator++(int) { 2817 int value = _map[_key]; 2818 _map.set(_key, value + 1); 2819 return value; 2820 } 2821 Reference& operator--() { 2822 _map.set(_key, _map[_key] - 1); 2823 return *this; 2824 } 2825 int operator--(int) { 2826 int value = _map[_key]; 2827 _map.set(_key, value - 1); 2828 return value; 2829 } 2830 Reference& operator+=(int value) { 2831 _map.set(_key, _map[_key] + value); 2832 return *this; 2833 } 2834 Reference& operator-=(int value) { 2835 _map.set(_key, _map[_key] - value); 2836 return *this; 2837 } 2838 Reference& operator*=(int value) { 2839 _map.set(_key, _map[_key] * value); 2840 return *this; 2841 } 2842 Reference& operator/=(int value) { 2843 _map.set(_key, _map[_key] / value); 2844 return *this; 2845 } 2846 Reference& operator%=(int value) { 2847 _map.set(_key, _map[_key] % value); 2848 return *this; 2849 } 2850 Reference& operator&=(int value) { 2851 _map.set(_key, _map[_key] & value); 2852 return *this; 2853 } 2854 Reference& operator|=(int value) { 2855 _map.set(_key, _map[_key] | value); 2856 return *this; 2857 } 2858 Reference& operator^=(int value) { 2859 _map.set(_key, _map[_key] ^ value); 2860 return *this; 2861 } 2862 Reference& operator<<=(int value) { 2863 _map.set(_key, _map[_key] << value); 2864 return *this; 2865 } 2866 Reference& operator>>=(int value) { 2867 _map.set(_key, _map[_key] >> value); 2868 return *this; 2869 } 2870 2871 private: 2872 Key _key; 2873 IterableIntMap& _map; 2874 }; 2875 2876 /// The const reference type. 2877 typedef const Value& ConstReference; 2878 2879 /// \brief Gives back the maximal value plus one. 2880 /// 2881 /// Gives back the maximal value plus one. 2882 int size() const { 2883 return _first.size(); 2884 } 2885 2886 /// \brief Set operation of the map. 2887 /// 2888 /// Set operation of the map. 2889 void set(const Key& key, const Value& value) { 2890 unlace(key); 2891 Parent::operator[](key).value = value; 2892 lace(key); 2893 } 2894 2895 /// \brief Const subscript operator of the map. 2896 /// 2897 /// Const subscript operator of the map. 2898 const Value& operator[](const Key& key) const { 2899 return Parent::operator[](key).value; 2900 } 2901 2902 /// \brief Subscript operator of the map. 2903 /// 2904 /// Subscript operator of the map. 2905 Reference operator[](const Key& key) { 2906 return Reference(*this, key); 2907 } 2908 2909 /// \brief Iterator for the keys with the same value. 2910 /// 2911 /// Iterator for the keys with the same value. It works 2912 /// like a graph item iterator, it can be converted to 2913 /// the item type of the map, incremented with \c ++ operator, and 2914 /// if the iterator leaves the last valid item, it will be equal to 2915 /// \c INVALID. 2916 class ItemIt : public Key { 2917 public: 2918 typedef Key Parent; 2919 2920 /// \brief Invalid constructor \& conversion. 2921 /// 2922 /// This constructor initializes the iterator to be invalid. 2923 /// \sa Invalid for more details. 2924 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 2925 2926 /// \brief Creates an iterator with a value. 2927 /// 2928 /// Creates an iterator with a value. It iterates on the 2929 /// keys mapped to the given value. 2930 /// \param map The IterableIntMap. 2931 /// \param value The value. 2932 ItemIt(const IterableIntMap& map, int value) : _map(&map) { 2933 if (value < 0 || value >= int(_map->_first.size())) { 2934 Parent::operator=(INVALID); 2935 } else { 2936 Parent::operator=(_map->_first[value]); 2937 } 2938 } 2939 2940 /// \brief Increment operator. 2941 /// 2942 /// Increment operator. 2943 ItemIt& operator++() { 2944 Parent::operator=(_map->IterableIntMap::Parent:: 2945 operator[](static_cast<Parent&>(*this)).next); 2946 return *this; 2947 } 2948 2949 private: 2950 const IterableIntMap* _map; 2951 }; 2952 2953 protected: 2954 2955 virtual void erase(const Key& key) { 2956 unlace(key); 2957 Parent::erase(key); 2958 } 2959 2960 virtual void erase(const std::vector<Key>& keys) { 2961 for (int i = 0; i < int(keys.size()); ++i) { 2962 unlace(keys[i]); 2963 } 2964 Parent::erase(keys); 2965 } 2966 2967 virtual void clear() { 2968 _first.clear(); 2969 Parent::clear(); 2970 } 2971 2972 private: 2973 std::vector<Key> _first; 2974 }; 2975 2976 namespace _maps_bits { 2977 template <typename Item, typename Value> 2978 struct IterableValueMapNode { 2979 IterableValueMapNode(Value _value = Value()) : value(_value) {} 2980 Item prev, next; 2981 Value value; 2982 }; 2983 } 2984 2985 /// \brief Dynamic iterable map for comparable values. 2986 /// 2987 /// This class provides a special graph map type which can store an 2988 /// comparable value for graph items (\c Node, \c Arc or \c Edge). 2989 /// For each value it is possible to iterate on the keys mapped to 2990 /// the value. 2991 /// 2992 /// The map stores for each value a linked list with 2993 /// the items which mapped to the value, and the values are stored 2994 /// in balanced binary tree. The values of the map can be accessed 2995 /// with stl compatible forward iterator. 2996 /// 2997 /// This type is not reference map, so it cannot be modified with 2998 /// the subscript operator. 2999 /// 3000 /// \tparam GR The graph type. 3001 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 3002 /// \c GR::Edge). 3003 /// \tparam V The value type of the map. It can be any comparable 3004 /// value type. 3005 /// 3006 /// \see IterableBoolMap, IterableIntMap 3007 /// \see CrossRefMap 3008 template <typename GR, typename K, typename V> 3009 class IterableValueMap 3010 : protected ItemSetTraits<GR, K>:: 3011 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type { 3012 public: 3013 typedef typename ItemSetTraits<GR, K>:: 3014 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent; 3015 3016 /// The key type 3017 typedef K Key; 3018 /// The value type 3019 typedef V Value; 3020 /// The graph type 3021 typedef GR Graph; 3022 3023 public: 3024 3025 /// \brief Constructor of the map with a given value. 3026 /// 3027 /// Constructor of the map with a given value. 3028 explicit IterableValueMap(const Graph& graph, 3029 const Value& value = Value()) 3030 : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) { 3031 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 3032 lace(it); 3033 } 3034 } 3035 3036 protected: 3037 3038 void unlace(const Key& key) { 3039 typename Parent::Value& node = Parent::operator[](key); 3040 if (node.prev != INVALID) { 3041 Parent::operator[](node.prev).next = node.next; 3042 } else { 3043 if (node.next != INVALID) { 3044 _first[node.value] = node.next; 3045 } else { 3046 _first.erase(node.value); 3047 } 3048 } 3049 if (node.next != INVALID) { 3050 Parent::operator[](node.next).prev = node.prev; 3051 } 3052 } 3053 3054 void lace(const Key& key) { 3055 typename Parent::Value& node = Parent::operator[](key); 3056 typename std::map<Value, Key>::iterator it = _first.find(node.value); 3057 if (it == _first.end()) { 3058 node.prev = node.next = INVALID; 3059 _first.insert(std::make_pair(node.value, key)); 3060 } else { 3061 node.prev = INVALID; 3062 node.next = it->second; 3063 if (node.next != INVALID) { 3064 Parent::operator[](node.next).prev = key; 3065 } 3066 it->second = key; 3067 } 3068 } 3069 3070 public: 3071 3072 /// \brief Forward iterator for values. 3073 /// 3074 /// This iterator is an stl compatible forward 3075 /// iterator on the values of the map. The values can 3076 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 3077 class ValueIterator 3078 : public std::iterator<std::forward_iterator_tag, Value> { 3079 friend class IterableValueMap; 3080 private: 3081 ValueIterator(typename std::map<Value, Key>::const_iterator _it) 3082 : it(_it) {} 3083 public: 3084 3085 ValueIterator() {} 3086 3087 ValueIterator& operator++() { ++it; return *this; } 3088 ValueIterator operator++(int) { 3089 ValueIterator tmp(*this); 3090 operator++(); 3091 return tmp; 3092 } 3093 3094 const Value& operator*() const { return it->first; } 3095 const Value* operator->() const { return &(it->first); } 3096 3097 bool operator==(ValueIterator jt) const { return it == jt.it; } 3098 bool operator!=(ValueIterator jt) const { return it != jt.it; } 3099 3100 private: 3101 typename std::map<Value, Key>::const_iterator it; 3102 }; 3103 3104 /// \brief Returns an iterator to the first value. 3105 /// 3106 /// Returns an stl compatible iterator to the 3107 /// first value of the map. The values of the 3108 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3109 /// range. 3110 ValueIterator beginValue() const { 3111 return ValueIterator(_first.begin()); 3112 } 3113 3114 /// \brief Returns an iterator after the last value. 3115 /// 3116 /// Returns an stl compatible iterator after the 3117 /// last value of the map. The values of the 3118 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3119 /// range. 3120 ValueIterator endValue() const { 3121 return ValueIterator(_first.end()); 3122 } 3123 3124 /// \brief Set operation of the map. 3125 /// 3126 /// Set operation of the map. 3127 void set(const Key& key, const Value& value) { 3128 unlace(key); 3129 Parent::operator[](key).value = value; 3130 lace(key); 3131 } 3132 3133 /// \brief Const subscript operator of the map. 3134 /// 3135 /// Const subscript operator of the map. 3136 const Value& operator[](const Key& key) const { 3137 return Parent::operator[](key).value; 3138 } 3139 3140 /// \brief Iterator for the keys with the same value. 3141 /// 3142 /// Iterator for the keys with the same value. It works 3143 /// like a graph item iterator, it can be converted to 3144 /// the item type of the map, incremented with \c ++ operator, and 3145 /// if the iterator leaves the last valid item, it will be equal to 3146 /// \c INVALID. 3147 class ItemIt : public Key { 3148 public: 3149 typedef Key Parent; 3150 3151 /// \brief Invalid constructor \& conversion. 3152 /// 3153 /// This constructor initializes the iterator to be invalid. 3154 /// \sa Invalid for more details. 3155 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 3156 3157 /// \brief Creates an iterator with a value. 3158 /// 3159 /// Creates an iterator with a value. It iterates on the 3160 /// keys which have the given value. 3161 /// \param map The IterableValueMap 3162 /// \param value The value 3163 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { 3164 typename std::map<Value, Key>::const_iterator it = 3165 map._first.find(value); 3166 if (it == map._first.end()) { 3167 Parent::operator=(INVALID); 3168 } else { 3169 Parent::operator=(it->second); 3170 } 3171 } 3172 3173 /// \brief Increment operator. 3174 /// 3175 /// Increment Operator. 3176 ItemIt& operator++() { 3177 Parent::operator=(_map->IterableValueMap::Parent:: 3178 operator[](static_cast<Parent&>(*this)).next); 3179 return *this; 3180 } 3181 3182 3183 private: 3184 const IterableValueMap* _map; 3185 }; 3186 3187 protected: 3188 3189 virtual void add(const Key& key) { 3190 Parent::add(key); 3191 unlace(key); 3192 } 3193 3194 virtual void add(const std::vector<Key>& keys) { 3195 Parent::add(keys); 3196 for (int i = 0; i < int(keys.size()); ++i) { 3197 lace(keys[i]); 3198 } 3199 } 3200 3201 virtual void erase(const Key& key) { 3202 unlace(key); 3203 Parent::erase(key); 3204 } 3205 3206 virtual void erase(const std::vector<Key>& keys) { 3207 for (int i = 0; i < int(keys.size()); ++i) { 3208 unlace(keys[i]); 3209 } 3210 Parent::erase(keys); 3211 } 3212 3213 virtual void build() { 3214 Parent::build(); 3215 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 3216 lace(it); 3217 } 3218 } 3219 3220 virtual void clear() { 3221 _first.clear(); 3222 Parent::clear(); 3223 } 3224 3225 private: 3226 std::map<Value, Key> _first; 3227 }; 3228 2314 3229 /// \brief Map of the source nodes of arcs in a digraph. 2315 3230 /// … … 2481 3396 /// whenever the digraph changes. 2482 3397 /// 2483 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3398 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2484 3399 /// may provide alternative ways to modify the digraph. 2485 3400 /// The correct behavior of InDegMap is not guarantied if these additional … … 2497 3412 2498 3413 public: 2499 3414 2500 3415 /// The graph type of InDegMap 2501 3416 typedef GR Graph; … … 2611 3526 /// whenever the digraph changes. 2612 3527 /// 2613 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3528 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2614 3529 /// may provide alternative ways to modify the digraph. 2615 3530 /// The correct behavior of OutDegMap is not guarantied if these additional -
lemon/min_cost_arborescence.h
r625 r713 489 489 /// The simplest way to execute the algorithm is to use 490 490 /// one of the member functions called \c run(...). \n 491 /// If you need morecontrol on the execution,492 /// first you must call \ref init(), then you can add several491 /// If you need better control on the execution, 492 /// you have to call \ref init() first, then you can add several 493 493 /// source nodes with \ref addSource(). 494 494 /// Finally \ref start() will perform the arborescence -
lemon/preflow.h
r641 r715 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 #ifdef DOXYGEN 56 typedef GR::ArcMap<Value> FlowMap; 57 #else 55 58 typedef typename Digraph::template ArcMap<Value> FlowMap; 59 #endif 56 60 57 61 /// \brief Instantiates a FlowMap. … … 68 72 /// The elevator type used by Preflow algorithm. 69 73 /// 70 /// \sa Elevator 71 /// \sa LinkedElevator 72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; 74 /// \sa Elevator, LinkedElevator 75 #ifdef DOXYGEN 76 typedef lemon::Elevator<GR, GR::Node> Elevator; 77 #else 78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 79 #endif 73 80 74 81 /// \brief Instantiates an Elevator. … … 98 105 /// "flow of maximum value" in a digraph. 99 106 /// The preflow algorithms are the fastest known maximum 100 /// flow algorithms. The current implementation use a mixture of the107 /// flow algorithms. The current implementation uses a mixture of the 101 108 /// \e "highest label" and the \e "bound decrease" heuristics. 102 109 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. … … 372 379 } 373 380 374 /// \brief Sets the tolerance used by algorithm. 375 /// 376 /// Sets the tolerance used by algorithm. 377 Preflow& tolerance(const Tolerance& tolerance) const { 381 /// \brief Sets the tolerance used by the algorithm. 382 /// 383 /// Sets the tolerance object used by the algorithm. 384 /// \return <tt>(*this)</tt> 385 Preflow& tolerance(const Tolerance& tolerance) { 378 386 _tolerance = tolerance; 379 387 return *this; … … 382 390 /// \brief Returns a const reference to the tolerance. 383 391 /// 384 /// Returns a const reference to the tolerance. 392 /// Returns a const reference to the tolerance object used by 393 /// the algorithm. 385 394 const Tolerance& tolerance() const { 386 return tolerance;395 return _tolerance; 387 396 } 388 397 … … 390 399 /// The simplest way to execute the preflow algorithm is to use 391 400 /// \ref run() or \ref runMinCut().\n 392 /// If you need morecontrol on the initial solution or the execution,393 /// first you have to call one of the \ref init() functions, then401 /// If you need better control on the initial solution or the execution, 402 /// you have to call one of the \ref init() functions first, then 394 403 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). 395 404 -
test/CMakeLists.txt
r679 r698 10 10 SET(TESTS 11 11 adaptors_test 12 bellman_ford_test 12 13 bfs_test 13 14 circulation_test -
test/Makefile.am
r649 r698 8 8 check_PROGRAMS += \ 9 9 test/adaptors_test \ 10 test/bellman_ford_test \ 10 11 test/bfs_test \ 11 12 test/circulation_test \ … … 53 54 54 55 test_adaptors_test_SOURCES = test/adaptors_test.cc 56 test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc 55 57 test_bfs_test_SOURCES = test/bfs_test.cc 56 58 test_circulation_test_SOURCES = test/circulation_test.cc -
test/circulation_test.cc
r611 r689 88 88 .supplyMap(supply) 89 89 .flowMap(flow); 90 91 const CirculationType::Elevator& elev = const_circ_test.elevator(); 92 circ_test.elevator(const_cast<CirculationType::Elevator&>(elev)); 93 CirculationType::Tolerance tol = const_circ_test.tolerance(); 94 circ_test.tolerance(tol); 90 95 91 96 circ_test.init(); -
test/heap_test.cc
r440 r702 26 26 27 27 #include <lemon/smart_graph.h> 28 29 28 #include <lemon/lgf_reader.h> 30 29 #include <lemon/dijkstra.h> … … 32 31 33 32 #include <lemon/bin_heap.h> 33 #include <lemon/fourary_heap.h> 34 #include <lemon/kary_heap.h> 35 #include <lemon/fib_heap.h> 36 #include <lemon/pairing_heap.h> 37 #include <lemon/radix_heap.h> 38 #include <lemon/binom_heap.h> 39 #include <lemon/bucket_heap.h> 34 40 35 41 #include "test_tools.h" … … 87 93 void heapSortTest() { 88 94 RangeMap<int> map(test_len, -1); 89 90 95 Heap heap(map); 91 96 92 97 std::vector<int> v(test_len); 93 94 98 for (int i = 0; i < test_len; ++i) { 95 99 v[i] = test_seq[i]; … … 98 102 std::sort(v.begin(), v.end()); 99 103 for (int i = 0; i < test_len; ++i) { 100 check(v[i] == heap.prio() ,"Wrong order in heap sort.");104 check(v[i] == heap.prio(), "Wrong order in heap sort."); 101 105 heap.pop(); 102 106 } … … 110 114 111 115 std::vector<int> v(test_len); 112 113 116 for (int i = 0; i < test_len; ++i) { 114 117 v[i] = test_seq[i]; … … 121 124 std::sort(v.begin(), v.end()); 122 125 for (int i = 0; i < test_len; ++i) { 123 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");126 check(v[i] == heap.prio(), "Wrong order in heap increase test."); 124 127 heap.pop(); 125 128 } 126 129 } 127 128 129 130 130 131 template <typename Heap> … … 142 143 if (dijkstra.reached(s)) { 143 144 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], 144 "Error in a shortest path tree!");145 "Error in shortest path tree."); 145 146 } 146 147 } … … 151 152 Node s = digraph.source(a); 152 153 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], 153 "Error in a shortest path tree!");154 "Error in shortest path tree."); 154 155 } 155 156 } … … 173 174 run(); 174 175 176 // BinHeap 175 177 { 176 178 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 184 186 } 185 187 188 // FouraryHeap 189 { 190 typedef FouraryHeap<Prio, ItemIntMap> IntHeap; 191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 192 heapSortTest<IntHeap>(); 193 heapIncreaseTest<IntHeap>(); 194 195 typedef FouraryHeap<Prio, IntNodeMap > NodeHeap; 196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 197 dijkstraHeapTest<NodeHeap>(digraph, length, source); 198 } 199 200 // KaryHeap 201 { 202 typedef KaryHeap<Prio, ItemIntMap> IntHeap; 203 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 204 heapSortTest<IntHeap>(); 205 heapIncreaseTest<IntHeap>(); 206 207 typedef KaryHeap<Prio, IntNodeMap > NodeHeap; 208 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 209 dijkstraHeapTest<NodeHeap>(digraph, length, source); 210 } 211 212 // FibHeap 213 { 214 typedef FibHeap<Prio, ItemIntMap> IntHeap; 215 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 216 heapSortTest<IntHeap>(); 217 heapIncreaseTest<IntHeap>(); 218 219 typedef FibHeap<Prio, IntNodeMap > NodeHeap; 220 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 221 dijkstraHeapTest<NodeHeap>(digraph, length, source); 222 } 223 224 // PairingHeap 225 { 226 typedef PairingHeap<Prio, ItemIntMap> IntHeap; 227 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 228 heapSortTest<IntHeap>(); 229 heapIncreaseTest<IntHeap>(); 230 231 typedef PairingHeap<Prio, IntNodeMap > NodeHeap; 232 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 233 dijkstraHeapTest<NodeHeap>(digraph, length, source); 234 } 235 236 // RadixHeap 237 { 238 typedef RadixHeap<ItemIntMap> IntHeap; 239 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 240 heapSortTest<IntHeap>(); 241 heapIncreaseTest<IntHeap>(); 242 243 typedef RadixHeap<IntNodeMap > NodeHeap; 244 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 245 dijkstraHeapTest<NodeHeap>(digraph, length, source); 246 } 247 248 // BinomHeap 249 { 250 typedef BinomHeap<Prio, ItemIntMap> IntHeap; 251 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 252 heapSortTest<IntHeap>(); 253 heapIncreaseTest<IntHeap>(); 254 255 typedef BinomHeap<Prio, IntNodeMap > NodeHeap; 256 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 257 dijkstraHeapTest<NodeHeap>(digraph, length, source); 258 } 259 260 // BucketHeap, SimpleBucketHeap 261 { 262 typedef BucketHeap<ItemIntMap> IntHeap; 263 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 264 heapSortTest<IntHeap>(); 265 heapIncreaseTest<IntHeap>(); 266 267 typedef BucketHeap<IntNodeMap > NodeHeap; 268 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 269 dijkstraHeapTest<NodeHeap>(digraph, length, source); 270 271 typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; 272 heapSortTest<SimpleIntHeap>(); 273 } 274 186 275 return 0; 187 276 } -
test/maps_test.cc
r507 r695 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/smart_graph.h> 25 26 26 27 #include "test_tools.h" … … 350 351 } 351 352 353 // CrossRefMap 354 { 355 typedef SmartDigraph Graph; 356 DIGRAPH_TYPEDEFS(Graph); 357 358 checkConcept<ReadWriteMap<Node, int>, 359 CrossRefMap<Graph, Node, int> >(); 360 361 Graph gr; 362 typedef CrossRefMap<Graph, Node, char> CRMap; 363 typedef CRMap::ValueIterator ValueIt; 364 CRMap map(gr); 365 366 Node n0 = gr.addNode(); 367 Node n1 = gr.addNode(); 368 Node n2 = gr.addNode(); 369 370 map.set(n0, 'A'); 371 map.set(n1, 'B'); 372 map.set(n2, 'C'); 373 map.set(n2, 'A'); 374 map.set(n0, 'C'); 375 376 check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A', 377 "Wrong CrossRefMap"); 378 check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap"); 379 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 380 check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); 381 382 ValueIt it = map.beginValue(); 383 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 384 it == map.endValue(), "Wrong value iterator"); 385 } 386 387 // Iterable bool map 388 { 389 typedef SmartGraph Graph; 390 typedef SmartGraph::Node Item; 391 392 typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm; 393 checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>(); 394 395 const int num = 10; 396 Graph g; 397 std::vector<Item> items; 398 for (int i = 0; i < num; ++i) { 399 items.push_back(g.addNode()); 400 } 401 402 Ibm map1(g, true); 403 int n = 0; 404 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 405 check(map1[static_cast<Item>(it)], "Wrong TrueIt"); 406 ++n; 407 } 408 check(n == num, "Wrong number"); 409 410 n = 0; 411 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 412 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 413 ++n; 414 } 415 check(n == num, "Wrong number"); 416 check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt"); 417 check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false"); 418 419 map1[items[5]] = true; 420 421 n = 0; 422 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 423 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 424 ++n; 425 } 426 check(n == num, "Wrong number"); 427 428 map1[items[num / 2]] = false; 429 check(map1[items[num / 2]] == false, "Wrong map value"); 430 431 n = 0; 432 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 433 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 434 ++n; 435 } 436 check(n == num - 1, "Wrong number"); 437 438 n = 0; 439 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 440 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 441 ++n; 442 } 443 check(n == 1, "Wrong number"); 444 445 map1[items[0]] = false; 446 check(map1[items[0]] == false, "Wrong map value"); 447 448 map1[items[num - 1]] = false; 449 check(map1[items[num - 1]] == false, "Wrong map value"); 450 451 n = 0; 452 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 453 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 454 ++n; 455 } 456 check(n == num - 3, "Wrong number"); 457 check(map1.trueNum() == num - 3, "Wrong number"); 458 459 n = 0; 460 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 461 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 462 ++n; 463 } 464 check(n == 3, "Wrong number"); 465 check(map1.falseNum() == 3, "Wrong number"); 466 } 467 468 // Iterable int map 469 { 470 typedef SmartGraph Graph; 471 typedef SmartGraph::Node Item; 472 typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim; 473 474 checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>(); 475 476 const int num = 10; 477 Graph g; 478 std::vector<Item> items; 479 for (int i = 0; i < num; ++i) { 480 items.push_back(g.addNode()); 481 } 482 483 Iim map1(g); 484 check(map1.size() == 0, "Wrong size"); 485 486 for (int i = 0; i < num; ++i) { 487 map1[items[i]] = i; 488 } 489 check(map1.size() == num, "Wrong size"); 490 491 for (int i = 0; i < num; ++i) { 492 Iim::ItemIt it(map1, i); 493 check(static_cast<Item>(it) == items[i], "Wrong value"); 494 ++it; 495 check(static_cast<Item>(it) == INVALID, "Wrong value"); 496 } 497 498 for (int i = 0; i < num; ++i) { 499 map1[items[i]] = i % 2; 500 } 501 check(map1.size() == 2, "Wrong size"); 502 503 int n = 0; 504 for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { 505 check(map1[static_cast<Item>(it)] == 0, "Wrong value"); 506 ++n; 507 } 508 check(n == (num + 1) / 2, "Wrong number"); 509 510 for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { 511 check(map1[static_cast<Item>(it)] == 1, "Wrong value"); 512 ++n; 513 } 514 check(n == num, "Wrong number"); 515 516 } 517 518 // Iterable value map 519 { 520 typedef SmartGraph Graph; 521 typedef SmartGraph::Node Item; 522 typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm; 523 524 checkConcept<ReadWriteMap<Item, double>, Ivm>(); 525 526 const int num = 10; 527 Graph g; 528 std::vector<Item> items; 529 for (int i = 0; i < num; ++i) { 530 items.push_back(g.addNode()); 531 } 532 533 Ivm map1(g, 0.0); 534 check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size"); 535 check(*map1.beginValue() == 0.0, "Wrong value"); 536 537 for (int i = 0; i < num; ++i) { 538 map1.set(items[i], static_cast<double>(i)); 539 } 540 check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size"); 541 542 for (int i = 0; i < num; ++i) { 543 Ivm::ItemIt it(map1, static_cast<double>(i)); 544 check(static_cast<Item>(it) == items[i], "Wrong value"); 545 ++it; 546 check(static_cast<Item>(it) == INVALID, "Wrong value"); 547 } 548 549 for (Ivm::ValueIterator vit = map1.beginValue(); 550 vit != map1.endValue(); ++vit) { 551 check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit, 552 "Wrong ValueIterator"); 553 } 554 555 for (int i = 0; i < num; ++i) { 556 map1.set(items[i], static_cast<double>(i % 2)); 557 } 558 check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size"); 559 560 int n = 0; 561 for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { 562 check(map1[static_cast<Item>(it)] == 0.0, "Wrong value"); 563 ++n; 564 } 565 check(n == (num + 1) / 2, "Wrong number"); 566 567 for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { 568 check(map1[static_cast<Item>(it)] == 1.0, "Wrong value"); 569 ++n; 570 } 571 check(n == num, "Wrong number"); 572 573 } 352 574 return 0; 353 575 } -
test/preflow_test.cc
r585 r689 95 95 PreflowType preflow_test(g, cap, n, n); 96 96 const PreflowType& const_preflow_test = preflow_test; 97 98 const PreflowType::Elevator& elev = const_preflow_test.elevator(); 99 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); 100 PreflowType::Tolerance tol = const_preflow_test.tolerance(); 101 preflow_test.tolerance(tol); 97 102 98 103 preflow_test -
tools/lemon-0.x-to-1.x.sh
r574 r691 36 36 -e "s/Edge\>/_Ar_c_label_/g"\ 37 37 -e "s/\<edge\>/_ar_c_label_/g"\ 38 -e "s/_edge\>/_ ar_c_label_/g"\38 -e "s/_edge\>/__ar_c_label_/g"\ 39 39 -e "s/Edges\>/_Ar_c_label_s/g"\ 40 40 -e "s/\<edges\>/_ar_c_label_s/g"\ 41 -e "s/_edges\>/_ ar_c_label_s/g"\41 -e "s/_edges\>/__ar_c_label_s/g"\ 42 42 -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\ 43 43 -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\ … … 69 69 -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ 70 70 -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ 71 -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\ 72 -e "s/\<digraph_utils\.h\>/core.h/g"\ 73 -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\ 74 -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\ 75 -e "s/\<topology\.h\>/connectivity.h/g"\ 71 76 -e "s/DigraphToEps/GraphToEps/g"\ 72 77 -e "s/digraphToEps/graphToEps/g"\
Note: See TracChangeset
for help on using the changeset viewer.