Changes in / [549:f53d641aa967:551:49a39bae067c] in lemon-1.1
- Files:
-
- 33 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r455 r550 21 21 /** 22 22 @defgroup datas Data Structures 23 This group describes the several data structures implemented in LEMON.23 This group contains the several data structures implemented in LEMON. 24 24 */ 25 25 … … 143 143 \brief Graph types between real graphs and graph adaptors. 144 144 145 This group describes some graph types between real graphs and graph adaptors.145 This group contains some graph types between real graphs and graph adaptors. 146 146 These classes wrap graphs to give new functionality as the adaptors do it. 147 147 On the other hand they are not light-weight structures as the adaptors. … … 153 153 \brief Map structures implemented in LEMON. 154 154 155 This group describes the map structures implemented in LEMON.155 This group contains the map structures implemented in LEMON. 156 156 157 157 LEMON provides several special purpose maps and map adaptors that e.g. combine … … 166 166 \brief Special graph-related maps. 167 167 168 This group describes maps that are specifically designed to assign168 This group contains maps that are specifically designed to assign 169 169 values to the nodes and arcs/edges of graphs. 170 170 … … 178 178 \brief Tools to create new maps from existing ones 179 179 180 This group describes map adaptors that are used to create "implicit"180 This group contains map adaptors that are used to create "implicit" 181 181 maps from other maps. 182 182 … … 241 241 \brief Two dimensional data storages implemented in LEMON. 242 242 243 This group describes two dimensional data storages implemented in LEMON.243 This group contains two dimensional data storages implemented in LEMON. 244 244 */ 245 245 … … 249 249 \brief %Path structures implemented in LEMON. 250 250 251 This group describes the path structures implemented in LEMON.251 This group contains the path structures implemented in LEMON. 252 252 253 253 LEMON provides flexible data structures to work with paths. … … 265 265 \brief Auxiliary data structures implemented in LEMON. 266 266 267 This group describes some data structures implemented in LEMON in267 This group contains some data structures implemented in LEMON in 268 268 order to make it easier to implement combinatorial algorithms. 269 269 */ … … 271 271 /** 272 272 @defgroup algs Algorithms 273 \brief This group describes the several algorithms273 \brief This group contains the several algorithms 274 274 implemented in LEMON. 275 275 276 This group describes the several algorithms276 This group contains the several algorithms 277 277 implemented in LEMON. 278 278 */ … … 283 283 \brief Common graph search algorithms. 284 284 285 This group describes the common graph search algorithms, namely285 This group contains the common graph search algorithms, namely 286 286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 287 287 */ … … 292 292 \brief Algorithms for finding shortest paths. 293 293 294 This group describes the algorithms for finding shortest paths in digraphs.294 This group contains the algorithms for finding shortest paths in digraphs. 295 295 296 296 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 313 313 \brief Algorithms for finding maximum flows. 314 314 315 This group describes the algorithms for finding maximum flows and315 This group contains the algorithms for finding maximum flows and 316 316 feasible circulations. 317 317 … … 346 346 \brief Algorithms for finding minimum cost flows and circulations. 347 347 348 This group describes the algorithms for finding minimum cost flows and348 This group contains the algorithms for finding minimum cost flows and 349 349 circulations. 350 350 … … 383 383 \brief Algorithms for finding minimum cut in graphs. 384 384 385 This group describes the algorithms for finding minimum cut in graphs.385 This group contains the algorithms for finding minimum cut in graphs. 386 386 387 387 The \e minimum \e cut \e problem is to find a non-empty and non-complete … … 400 400 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 401 401 calculating minimum cut in undirected graphs. 402 - \ref GomoryHu Tree"Gomory-Hu tree computation" for calculating402 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 403 403 all-pairs minimum cut in undirected graphs. 404 404 … … 412 412 \brief Algorithms for discovering the graph properties 413 413 414 This group describes the algorithms for discovering the graph properties414 This group contains the algorithms for discovering the graph properties 415 415 like connectivity, bipartiteness, euler property, simplicity etc. 416 416 … … 424 424 \brief Algorithms for planarity checking, embedding and drawing 425 425 426 This group describes the algorithms for planarity checking,426 This group contains the algorithms for planarity checking, 427 427 embedding and drawing. 428 428 … … 475 475 \brief Algorithms for finding a minimum cost spanning tree in a graph. 476 476 477 This group describes the algorithms for finding a minimum cost spanning477 This group contains the algorithms for finding a minimum cost spanning 478 478 tree in a graph. 479 479 */ … … 484 484 \brief Auxiliary algorithms implemented in LEMON. 485 485 486 This group describes some algorithms implemented in LEMON486 This group contains some algorithms implemented in LEMON 487 487 in order to make it easier to implement complex algorithms. 488 488 */ … … 493 493 \brief Approximation algorithms. 494 494 495 This group describes the approximation and heuristic algorithms495 This group contains the approximation and heuristic algorithms 496 496 implemented in LEMON. 497 497 */ … … 499 499 /** 500 500 @defgroup gen_opt_group General Optimization Tools 501 \brief This group describes some general optimization frameworks501 \brief This group contains some general optimization frameworks 502 502 implemented in LEMON. 503 503 504 This group describes some general optimization frameworks504 This group contains some general optimization frameworks 505 505 implemented in LEMON. 506 506 */ … … 511 511 \brief Lp and Mip solver interfaces for LEMON. 512 512 513 This group describes Lp and Mip solver interfaces for LEMON. The513 This group contains Lp and Mip solver interfaces for LEMON. The 514 514 various LP solvers could be used in the same manner with this 515 515 interface. … … 530 530 \brief Metaheuristics for LEMON library. 531 531 532 This group describes some metaheuristic optimization tools.532 This group contains some metaheuristic optimization tools. 533 533 */ 534 534 … … 545 545 \brief Simple basic graph utilities. 546 546 547 This group describes some simple basic graph utilities.547 This group contains some simple basic graph utilities. 548 548 */ 549 549 … … 553 553 \brief Tools for development, debugging and testing. 554 554 555 This group describes several useful tools for development,555 This group contains several useful tools for development, 556 556 debugging and testing. 557 557 */ … … 562 562 \brief Simple tools for measuring the performance of algorithms. 563 563 564 This group describes simple tools for measuring the performance564 This group contains simple tools for measuring the performance 565 565 of algorithms. 566 566 */ … … 571 571 \brief Exceptions defined in LEMON. 572 572 573 This group describes the exceptions defined in LEMON.573 This group contains the exceptions defined in LEMON. 574 574 */ 575 575 … … 578 578 \brief Graph Input-Output methods 579 579 580 This group describes the tools for importing and exporting graphs580 This group contains the tools for importing and exporting graphs 581 581 and graph related data. Now it supports the \ref lgf-format 582 582 "LEMON Graph Format", the \c DIMACS format and the encapsulated … … 589 589 \brief Reading and writing LEMON Graph Format. 590 590 591 This group describes methods for reading and writing591 This group contains methods for reading and writing 592 592 \ref lgf-format "LEMON Graph Format". 593 593 */ … … 598 598 \brief General \c EPS drawer and graph exporter 599 599 600 This group describes general \c EPS drawing methods and special600 This group contains general \c EPS drawing methods and special 601 601 graph exporting tools. 602 602 */ … … 622 622 \brief Skeleton classes and concept checking classes 623 623 624 This group describes the data/algorithm skeletons and concept checking624 This group contains the data/algorithm skeletons and concept checking 625 625 classes implemented in LEMON. 626 626 … … 652 652 \brief Skeleton and concept checking classes for graph structures 653 653 654 This group describes the skeletons and concept checking classes of LEMON's654 This group contains the skeletons and concept checking classes of LEMON's 655 655 graph structures and helper classes used to implement these. 656 656 */ … … 661 661 \brief Skeleton and concept checking classes for maps 662 662 663 This group describes the skeletons and concept checking classes of maps.663 This group contains the skeletons and concept checking classes of maps. 664 664 */ 665 665 -
doc/mainpage.dox
r440 r550 46 46 "Quick Tour to LEMON" which will guide you along. 47 47 48 If you already feel like using our library, see the page that tells you 49 \ref getstart "How to start using LEMON". 50 51 If you 52 want to see how LEMON works, see 53 some \ref demoprograms "demo programs". 48 If you already feel like using our library, see the 49 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. 54 50 55 51 If you know what you are looking for then try to find it under the 56 <a class="el" href="modules.html">Modules</a> 57 section. 52 <a class="el" href="modules.html">Modules</a> section. 58 53 59 54 If you are a user of the old (0.x) series of LEMON, please check out the -
lemon/adaptors.h
r503 r550 2255 2255 /// This map adaptor class adapts two arc maps of the underlying 2256 2256 /// digraph to get an arc map of the undirected graph. 2257 /// Its value type is inherited from the first arc map type 2258 /// (\c %ForwardMap). 2259 template <typename ForwardMap, typename BackwardMap> 2257 /// Its value type is inherited from the first arc map type (\c FW). 2258 /// \tparam FW The type of the "foward" arc map. 2259 /// \tparam BK The type of the "backward" arc map. 2260 template <typename FW, typename BK> 2260 2261 class CombinedArcMap { 2261 2262 public: … … 2264 2265 typedef typename Parent::Arc Key; 2265 2266 /// The value type of the map 2266 typedef typename F orwardMap::Value Value;2267 2268 typedef typename MapTraits<F orwardMap>::ReferenceMapTag ReferenceMapTag;2269 2270 typedef typename MapTraits<F orwardMap>::ReturnValue ReturnValue;2271 typedef typename MapTraits<F orwardMap>::ConstReturnValue ConstReturnValue;2272 typedef typename MapTraits<F orwardMap>::ReturnValue Reference;2273 typedef typename MapTraits<F orwardMap>::ConstReturnValue ConstReference;2267 typedef typename FW::Value Value; 2268 2269 typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag; 2270 2271 typedef typename MapTraits<FW>::ReturnValue ReturnValue; 2272 typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue; 2273 typedef typename MapTraits<FW>::ReturnValue Reference; 2274 typedef typename MapTraits<FW>::ConstReturnValue ConstReference; 2274 2275 2275 2276 /// Constructor 2276 CombinedArcMap(F orwardMap& forward, BackwardMap& backward)2277 CombinedArcMap(FW& forward, BK& backward) 2277 2278 : _forward(&forward), _backward(&backward) {} 2278 2279 … … 2306 2307 protected: 2307 2308 2308 F orwardMap* _forward;2309 B ackwardMap* _backward;2309 FW* _forward; 2310 BK* _backward; 2310 2311 2311 2312 }; … … 2314 2315 /// 2315 2316 /// This function just returns a combined arc map. 2316 template <typename ForwardMap, typename BackwardMap> 2317 static CombinedArcMap<ForwardMap, BackwardMap> 2318 combinedArcMap(ForwardMap& forward, BackwardMap& backward) { 2319 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward); 2320 } 2321 2322 template <typename ForwardMap, typename BackwardMap> 2323 static CombinedArcMap<const ForwardMap, BackwardMap> 2324 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { 2325 return CombinedArcMap<const ForwardMap, 2326 BackwardMap>(forward, backward); 2327 } 2328 2329 template <typename ForwardMap, typename BackwardMap> 2330 static CombinedArcMap<ForwardMap, const BackwardMap> 2331 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { 2332 return CombinedArcMap<ForwardMap, 2333 const BackwardMap>(forward, backward); 2334 } 2335 2336 template <typename ForwardMap, typename BackwardMap> 2337 static CombinedArcMap<const ForwardMap, const BackwardMap> 2338 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { 2339 return CombinedArcMap<const ForwardMap, 2340 const BackwardMap>(forward, backward); 2317 template <typename FW, typename BK> 2318 static CombinedArcMap<FW, BK> 2319 combinedArcMap(FW& forward, BK& backward) { 2320 return CombinedArcMap<FW, BK>(forward, backward); 2321 } 2322 2323 template <typename FW, typename BK> 2324 static CombinedArcMap<const FW, BK> 2325 combinedArcMap(const FW& forward, BK& backward) { 2326 return CombinedArcMap<const FW, BK>(forward, backward); 2327 } 2328 2329 template <typename FW, typename BK> 2330 static CombinedArcMap<FW, const BK> 2331 combinedArcMap(FW& forward, const BK& backward) { 2332 return CombinedArcMap<FW, const BK>(forward, backward); 2333 } 2334 2335 template <typename FW, typename BK> 2336 static CombinedArcMap<const FW, const BK> 2337 combinedArcMap(const FW& forward, const BK& backward) { 2338 return CombinedArcMap<const FW, const BK>(forward, backward); 2341 2339 } 2342 2340 … … 3407 3405 /// This map adaptor class adapts two node maps of the original digraph 3408 3406 /// to get a node map of the split digraph. 3409 /// Its value type is inherited from the first node map type 3410 /// (\c InNodeMap). 3411 template <typename InNodeMap, typename OutNodeMap> 3407 /// Its value type is inherited from the first node map type (\c IN). 3408 /// \tparam IN The type of the node map for the in-nodes. 3409 /// \tparam OUT The type of the node map for the out-nodes. 3410 template <typename IN, typename OUT> 3412 3411 class CombinedNodeMap { 3413 3412 public: … … 3416 3415 typedef Node Key; 3417 3416 /// The value type of the map 3418 typedef typename I nNodeMap::Value Value;3419 3420 typedef typename MapTraits<I nNodeMap>::ReferenceMapTag ReferenceMapTag;3421 typedef typename MapTraits<I nNodeMap>::ReturnValue ReturnValue;3422 typedef typename MapTraits<I nNodeMap>::ConstReturnValue ConstReturnValue;3423 typedef typename MapTraits<I nNodeMap>::ReturnValue Reference;3424 typedef typename MapTraits<I nNodeMap>::ConstReturnValue ConstReference;3417 typedef typename IN::Value Value; 3418 3419 typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag; 3420 typedef typename MapTraits<IN>::ReturnValue ReturnValue; 3421 typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue; 3422 typedef typename MapTraits<IN>::ReturnValue Reference; 3423 typedef typename MapTraits<IN>::ConstReturnValue ConstReference; 3425 3424 3426 3425 /// Constructor 3427 CombinedNodeMap(I nNodeMap& in_map, OutNodeMap& out_map)3426 CombinedNodeMap(IN& in_map, OUT& out_map) 3428 3427 : _in_map(in_map), _out_map(out_map) {} 3429 3428 … … 3457 3456 private: 3458 3457 3459 I nNodeMap& _in_map;3460 O utNodeMap& _out_map;3458 IN& _in_map; 3459 OUT& _out_map; 3461 3460 3462 3461 }; … … 3466 3465 /// 3467 3466 /// This function just returns a combined node map. 3468 template <typename InNodeMap, typename OutNodeMap> 3469 static CombinedNodeMap<InNodeMap, OutNodeMap> 3470 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { 3471 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map); 3472 } 3473 3474 template <typename InNodeMap, typename OutNodeMap> 3475 static CombinedNodeMap<const InNodeMap, OutNodeMap> 3476 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { 3477 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map); 3478 } 3479 3480 template <typename InNodeMap, typename OutNodeMap> 3481 static CombinedNodeMap<InNodeMap, const OutNodeMap> 3482 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { 3483 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map); 3484 } 3485 3486 template <typename InNodeMap, typename OutNodeMap> 3487 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 3488 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { 3489 return CombinedNodeMap<const InNodeMap, 3490 const OutNodeMap>(in_map, out_map); 3467 template <typename IN, typename OUT> 3468 static CombinedNodeMap<IN, OUT> 3469 combinedNodeMap(IN& in_map, OUT& out_map) { 3470 return CombinedNodeMap<IN, OUT>(in_map, out_map); 3471 } 3472 3473 template <typename IN, typename OUT> 3474 static CombinedNodeMap<const IN, OUT> 3475 combinedNodeMap(const IN& in_map, OUT& out_map) { 3476 return CombinedNodeMap<const IN, OUT>(in_map, out_map); 3477 } 3478 3479 template <typename IN, typename OUT> 3480 static CombinedNodeMap<IN, const OUT> 3481 combinedNodeMap(IN& in_map, const OUT& out_map) { 3482 return CombinedNodeMap<IN, const OUT>(in_map, out_map); 3483 } 3484 3485 template <typename IN, typename OUT> 3486 static CombinedNodeMap<const IN, const OUT> 3487 combinedNodeMap(const IN& in_map, const OUT& out_map) { 3488 return CombinedNodeMap<const IN, const OUT>(in_map, out_map); 3491 3489 } 3492 3490 … … 3496 3494 /// This map adaptor class adapts an arc map and a node map of the 3497 3495 /// original digraph to get an arc map of the split digraph. 3498 /// Its value type is inherited from the original arc map type 3499 /// (\c ArcMap). 3500 template <typename ArcMap, typename NodeMap> 3496 /// Its value type is inherited from the original arc map type (\c AM). 3497 /// \tparam AM The type of the arc map. 3498 /// \tparam NM the type of the node map. 3499 template <typename AM, typename NM> 3501 3500 class CombinedArcMap { 3502 3501 public: … … 3505 3504 typedef Arc Key; 3506 3505 /// The value type of the map 3507 typedef typename A rcMap::Value Value;3508 3509 typedef typename MapTraits<A rcMap>::ReferenceMapTag ReferenceMapTag;3510 typedef typename MapTraits<A rcMap>::ReturnValue ReturnValue;3511 typedef typename MapTraits<A rcMap>::ConstReturnValue ConstReturnValue;3512 typedef typename MapTraits<A rcMap>::ReturnValue Reference;3513 typedef typename MapTraits<A rcMap>::ConstReturnValue ConstReference;3506 typedef typename AM::Value Value; 3507 3508 typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag; 3509 typedef typename MapTraits<AM>::ReturnValue ReturnValue; 3510 typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue; 3511 typedef typename MapTraits<AM>::ReturnValue Reference; 3512 typedef typename MapTraits<AM>::ConstReturnValue ConstReference; 3514 3513 3515 3514 /// Constructor 3516 CombinedArcMap(A rcMap& arc_map, NodeMap& node_map)3515 CombinedArcMap(AM& arc_map, NM& node_map) 3517 3516 : _arc_map(arc_map), _node_map(node_map) {} 3518 3517 … … 3545 3544 3546 3545 private: 3547 ArcMap& _arc_map; 3548 NodeMap& _node_map; 3546 3547 AM& _arc_map; 3548 NM& _node_map; 3549 3549 3550 }; 3550 3551 -
lemon/bin_heap.h
r440 r550 34 34 ///\brief A Binary Heap implementation. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. A \e heap 37 ///is a data structure for storing items with specified values called \e 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 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. 41 43 /// 42 ///\tparam _PrioType of the priority of the items.43 ///\tparam _ItemIntMap A read and writable Item int map, used internally44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 44 46 ///to handle the cross references. 45 ///\tparam _Compare A class for the ordering of the priorities. The46 /// default is \c std::less<_Prio>.47 ///\tparam Comp A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 47 49 /// 48 50 ///\sa FibHeap 49 51 ///\sa Dijkstra 50 template <typename _Prio, typename _ItemIntMap, 51 typename _Compare = std::less<_Prio> > 52 template <typename PR, typename IM, typename Comp = std::less<PR> > 52 53 class BinHeap { 53 54 54 55 public: 55 56 ///\e 56 typedef _ItemIntMapItemIntMap;57 ///\e 58 typedef _PrioPrio;57 typedef IM ItemIntMap; 58 ///\e 59 typedef PR Prio; 59 60 ///\e 60 61 typedef typename ItemIntMap::Key Item; … … 62 63 typedef std::pair<Item,Prio> Pair; 63 64 ///\e 64 typedef _CompareCompare;65 typedef Comp Compare; 65 66 66 67 /// \brief Type to represent the items states. … … 70 71 /// heap's point of view, but may be useful to the user. 71 72 /// 72 /// The ItemIntMap \e should be initialized in such way that it maps73 /// PRE_HEAP (-1) to any element to be put in the heap...73 /// The item-int map must be initialized in such way that it assigns 74 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 74 75 enum State { 75 IN_HEAP = 0, 76 PRE_HEAP = -1, 77 POST_HEAP = -2 76 IN_HEAP = 0, ///< \e 77 PRE_HEAP = -1, ///< \e 78 POST_HEAP = -2 ///< \e 78 79 }; 79 80 80 81 private: 81 std::vector<Pair> data;82 Compare comp;83 ItemIntMap & iim;82 std::vector<Pair> _data; 83 Compare _comp; 84 ItemIntMap &_iim; 84 85 85 86 public: … … 87 88 /// 88 89 /// The constructor. 89 /// \param _iim should be given to the constructor, since it is used 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. 93 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 90 99 /// internally to handle the cross references. The value of the map 91 100 /// should be PRE_HEAP (-1) for each element. 92 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 93 94 /// \brief The constructor. 95 /// 96 /// The constructor. 97 /// \param _iim should be given to the constructor, since it is used 98 /// internally to handle the cross references. The value of the map 99 /// should be PRE_HEAP (-1) for each element. 100 /// 101 /// \param _comp The comparator function object. 102 BinHeap(ItemIntMap &_iim, const Compare &_comp) 103 : iim(_iim), comp(_comp) {} 101 /// 102 /// \param comp The comparator function object. 103 BinHeap(ItemIntMap &map, const Compare &comp) 104 : _iim(map), _comp(comp) {} 104 105 105 106 … … 107 108 /// 108 109 /// \brief Returns the number of items stored in the heap. 109 int size() const { return data.size(); }110 int size() const { return _data.size(); } 110 111 111 112 /// \brief Checks if the heap stores no items. 112 113 /// 113 114 /// Returns \c true if and only if the heap stores no items. 114 bool empty() const { return data.empty(); }115 bool empty() const { return _data.empty(); } 115 116 116 117 /// \brief Make empty this heap. … … 121 122 /// each item to \c PRE_HEAP. 122 123 void clear() { 123 data.clear();124 _data.clear(); 124 125 } 125 126 … … 129 130 static int second_child(int i) { return 2*i+2; } 130 131 bool less(const Pair &p1, const Pair &p2) const { 131 return comp(p1.second, p2.second);132 return _comp(p1.second, p2.second); 132 133 } 133 134 134 135 int bubble_up(int hole, Pair p) { 135 136 int par = parent(hole); 136 while( hole>0 && less(p, data[par]) ) {137 move( data[par],hole);137 while( hole>0 && less(p,_data[par]) ) { 138 move(_data[par],hole); 138 139 hole = par; 139 140 par = parent(hole); … … 146 147 int child = second_child(hole); 147 148 while(child < length) { 148 if( less( data[child-1],data[child]) ) {149 if( less(_data[child-1], _data[child]) ) { 149 150 --child; 150 151 } 151 if( !less( data[child], p) )152 if( !less(_data[child], p) ) 152 153 goto ok; 153 move( data[child], hole);154 move(_data[child], hole); 154 155 hole = child; 155 156 child = second_child(hole); 156 157 } 157 158 child--; 158 if( child<length && less( data[child], p) ) {159 move( data[child], hole);159 if( child<length && less(_data[child], p) ) { 160 move(_data[child], hole); 160 161 hole=child; 161 162 } … … 166 167 167 168 void move(const Pair &p, int i) { 168 data[i] = p;169 iim.set(p.first, i);169 _data[i] = p; 170 _iim.set(p.first, i); 170 171 } 171 172 … … 176 177 /// \param p The pair to insert. 177 178 void push(const Pair &p) { 178 int n = data.size();179 data.resize(n+1);179 int n = _data.size(); 180 _data.resize(n+1); 180 181 bubble_up(n, p); 181 182 } … … 194 195 /// \pre The heap must be nonempty. 195 196 Item top() const { 196 return data[0].first;197 return _data[0].first; 197 198 } 198 199 … … 202 203 /// \pre The heap must be nonempty. 203 204 Prio prio() const { 204 return data[0].second;205 return _data[0].second; 205 206 } 206 207 … … 211 212 /// \pre The heap must be non-empty. 212 213 void pop() { 213 int n = data.size()-1;214 iim.set(data[0].first, POST_HEAP);214 int n = _data.size()-1; 215 _iim.set(_data[0].first, POST_HEAP); 215 216 if (n > 0) { 216 bubble_down(0, data[n], n);217 } 218 data.pop_back();217 bubble_down(0, _data[n], n); 218 } 219 _data.pop_back(); 219 220 } 220 221 … … 225 226 /// \pre The item should be in the heap. 226 227 void erase(const Item &i) { 227 int h = iim[i];228 int n = data.size()-1;229 iim.set(data[h].first, POST_HEAP);228 int h = _iim[i]; 229 int n = _data.size()-1; 230 _iim.set(_data[h].first, POST_HEAP); 230 231 if( h < n ) { 231 if ( bubble_up(h, data[n]) == h) {232 bubble_down(h, data[n], n);232 if ( bubble_up(h, _data[n]) == h) { 233 bubble_down(h, _data[n], n); 233 234 } 234 235 } 235 data.pop_back();236 _data.pop_back(); 236 237 } 237 238 … … 240 241 /// 241 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 242 244 /// \pre \c i must be in the heap. 243 /// \param i The item.244 245 Prio operator[](const Item &i) const { 245 int idx = iim[i];246 return data[idx].second;246 int idx = _iim[i]; 247 return _data[idx].second; 247 248 } 248 249 … … 255 256 /// \param p The priority. 256 257 void set(const Item &i, const Prio &p) { 257 int idx = iim[i];258 int idx = _iim[i]; 258 259 if( idx < 0 ) { 259 260 push(i,p); 260 261 } 261 else if( comp(p,data[idx].second) ) {262 else if( _comp(p, _data[idx].second) ) { 262 263 bubble_up(idx, Pair(i,p)); 263 264 } 264 265 else { 265 bubble_down(idx, Pair(i,p), data.size());266 bubble_down(idx, Pair(i,p), _data.size()); 266 267 } 267 268 } … … 270 271 /// 271 272 /// This method decreases the priority of item \c i to \c p. 273 /// \param i The item. 274 /// \param p The priority. 272 275 /// \pre \c i must be stored in the heap with priority at least \c 273 276 /// p relative to \c Compare. 277 void decrease(const Item &i, const Prio &p) { 278 int idx = _iim[i]; 279 bubble_up(idx, Pair(i,p)); 280 } 281 282 /// \brief Increases the priority of \c i to \c p. 283 /// 284 /// This method sets the priority of item \c i to \c p. 274 285 /// \param i The item. 275 286 /// \param p The priority. 276 void decrease(const Item &i, const Prio &p) {277 int idx = iim[i];278 bubble_up(idx, Pair(i,p));279 }280 281 /// \brief Increases the priority of \c i to \c p.282 ///283 /// This method sets the priority of item \c i to \c p.284 287 /// \pre \c i must be stored in the heap with priority at most \c 285 288 /// p relative to \c Compare. 286 /// \param i The item.287 /// \param p The priority.288 289 void increase(const Item &i, const Prio &p) { 289 int idx = iim[i];290 bubble_down(idx, Pair(i,p), data.size());290 int idx = _iim[i]; 291 bubble_down(idx, Pair(i,p), _data.size()); 291 292 } 292 293 … … 300 301 /// \param i The item. 301 302 State state(const Item &i) const { 302 int s = iim[i];303 int s = _iim[i]; 303 304 if( s>=0 ) 304 305 s=0; … … 320 321 erase(i); 321 322 } 322 iim[i] = st;323 _iim[i] = st; 323 324 break; 324 325 case IN_HEAP: … … 334 335 /// with the same prioriority as prevoiusly the \c i item. 335 336 void replace(const Item& i, const Item& j) { 336 int idx = iim[i];337 iim.set(i,iim[j]);338 iim.set(j, idx);339 data[idx].first = j;337 int idx = _iim[i]; 338 _iim.set(i, _iim[j]); 339 _iim.set(j, idx); 340 _data[idx].first = j; 340 341 } 341 342 -
lemon/bits/edge_set_extender.h
r503 r550 25 25 #include <lemon/bits/map_extender.h> 26 26 27 // /\ingroup digraphbits28 // /\file29 // /\brief Extenders for the arc set types27 //\ingroup digraphbits 28 //\file 29 //\brief Extenders for the arc set types 30 30 namespace lemon { 31 31 32 // /\ingroup digraphbits33 // /34 // /\brief Extender for the ArcSets32 // \ingroup digraphbits 33 // 34 // \brief Extender for the ArcSets 35 35 template <typename Base> 36 36 class ArcSetExtender : public Base { … … 73 73 // Alteration notifier extensions 74 74 75 // /The arc observer registry.75 // The arc observer registry. 76 76 typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier; 77 77 … … 84 84 using Parent::notifier; 85 85 86 /// \brief Gives back the arc alteration notifier. 87 /// 88 /// Gives back the arc alteration notifier. 86 // Gives back the arc alteration notifier. 89 87 ArcNotifier& notifier(Arc) const { 90 88 return arc_notifier; … … 186 184 }; 187 185 188 // /\brief Base node of the iterator189 // /190 // /Returns the base node (ie. the source in this case) of the iterator186 // \brief Base node of the iterator 187 // 188 // Returns the base node (ie. the source in this case) of the iterator 191 189 Node baseNode(const OutArcIt &e) const { 192 190 return Parent::source(static_cast<const Arc&>(e)); 193 191 } 194 // /\brief Running node of the iterator195 // /196 // /Returns the running node (ie. the target in this case) of the197 // /iterator192 // \brief Running node of the iterator 193 // 194 // Returns the running node (ie. the target in this case) of the 195 // iterator 198 196 Node runningNode(const OutArcIt &e) const { 199 197 return Parent::target(static_cast<const Arc&>(e)); 200 198 } 201 199 202 // /\brief Base node of the iterator203 // /204 // /Returns the base node (ie. the target in this case) of the iterator200 // \brief Base node of the iterator 201 // 202 // Returns the base node (ie. the target in this case) of the iterator 205 203 Node baseNode(const InArcIt &e) const { 206 204 return Parent::target(static_cast<const Arc&>(e)); 207 205 } 208 // /\brief Running node of the iterator209 // /210 // /Returns the running node (ie. the source in this case) of the211 // /iterator206 // \brief Running node of the iterator 207 // 208 // Returns the running node (ie. the source in this case) of the 209 // iterator 212 210 Node runningNode(const InArcIt &e) const { 213 211 return Parent::source(static_cast<const Arc&>(e)); … … 272 270 273 271 274 // /\ingroup digraphbits275 // /276 // /\brief Extender for the EdgeSets272 // \ingroup digraphbits 273 // 274 // \brief Extender for the EdgeSets 277 275 template <typename Base> 278 276 class EdgeSetExtender : public Base { … … 493 491 }; 494 492 495 // /\brief Base node of the iterator496 // /497 // /Returns the base node (ie. the source in this case) of the iterator493 // \brief Base node of the iterator 494 // 495 // Returns the base node (ie. the source in this case) of the iterator 498 496 Node baseNode(const OutArcIt &e) const { 499 497 return Parent::source(static_cast<const Arc&>(e)); 500 498 } 501 // /\brief Running node of the iterator502 // /503 // /Returns the running node (ie. the target in this case) of the504 // /iterator499 // \brief Running node of the iterator 500 // 501 // Returns the running node (ie. the target in this case) of the 502 // iterator 505 503 Node runningNode(const OutArcIt &e) const { 506 504 return Parent::target(static_cast<const Arc&>(e)); 507 505 } 508 506 509 // /\brief Base node of the iterator510 // /511 // /Returns the base node (ie. the target in this case) of the iterator507 // \brief Base node of the iterator 508 // 509 // Returns the base node (ie. the target in this case) of the iterator 512 510 Node baseNode(const InArcIt &e) const { 513 511 return Parent::target(static_cast<const Arc&>(e)); 514 512 } 515 // /\brief Running node of the iterator516 // /517 // /Returns the running node (ie. the source in this case) of the518 // /iterator513 // \brief Running node of the iterator 514 // 515 // Returns the running node (ie. the source in this case) of the 516 // iterator 519 517 Node runningNode(const InArcIt &e) const { 520 518 return Parent::source(static_cast<const Arc&>(e)); 521 519 } 522 520 523 // /Base node of the iterator524 // /525 // /Returns the base node of the iterator521 // Base node of the iterator 522 // 523 // Returns the base node of the iterator 526 524 Node baseNode(const IncEdgeIt &e) const { 527 525 return e.direction ? u(e) : v(e); 528 526 } 529 // /Running node of the iterator530 // /531 // /Returns the running node of the iterator527 // Running node of the iterator 528 // 529 // Returns the running node of the iterator 532 530 Node runningNode(const IncEdgeIt &e) const { 533 531 return e.direction ? v(e) : u(e); -
lemon/circulation.h
r519 r550 216 216 ///@{ 217 217 218 template <typename _FlowMap>218 template <typename T> 219 219 struct SetFlowMapTraits : public Traits { 220 typedef _FlowMapFlowMap;220 typedef T FlowMap; 221 221 static FlowMap *createFlowMap(const Digraph&) { 222 222 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 230 230 /// \ref named-templ-param "Named parameter" for setting FlowMap 231 231 /// type. 232 template <typename _FlowMap>232 template <typename T> 233 233 struct SetFlowMap 234 234 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 235 SetFlowMapTraits< _FlowMap> > {235 SetFlowMapTraits<T> > { 236 236 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 237 SetFlowMapTraits< _FlowMap> > Create;237 SetFlowMapTraits<T> > Create; 238 238 }; 239 239 240 template <typename _Elevator>240 template <typename T> 241 241 struct SetElevatorTraits : public Traits { 242 typedef _ElevatorElevator;242 typedef T Elevator; 243 243 static Elevator *createElevator(const Digraph&, int) { 244 244 LEMON_ASSERT(false, "Elevator is not initialized"); … … 256 256 /// \ref run() or \ref init(). 257 257 /// \sa SetStandardElevator 258 template <typename _Elevator>258 template <typename T> 259 259 struct SetElevator 260 260 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 261 SetElevatorTraits< _Elevator> > {261 SetElevatorTraits<T> > { 262 262 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 263 SetElevatorTraits< _Elevator> > Create;263 SetElevatorTraits<T> > Create; 264 264 }; 265 265 266 template <typename _Elevator>266 template <typename T> 267 267 struct SetStandardElevatorTraits : public Traits { 268 typedef _ElevatorElevator;268 typedef T Elevator; 269 269 static Elevator *createElevator(const Digraph& digraph, int max_level) { 270 270 return new Elevator(digraph, max_level); … … 284 284 /// before calling \ref run() or \ref init(). 285 285 /// \sa SetElevator 286 template <typename _Elevator>286 template <typename T> 287 287 struct SetStandardElevator 288 288 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 289 SetStandardElevatorTraits< _Elevator> > {289 SetStandardElevatorTraits<T> > { 290 290 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 291 SetStandardElevatorTraits< _Elevator> > Create;291 SetStandardElevatorTraits<T> > Create; 292 292 }; 293 293 … … 683 683 /// 684 684 /// \note This function calls \ref barrier() for each node, 685 /// so it runs in \f$O(n)\f$time.685 /// so it runs in O(n) time. 686 686 /// 687 687 /// \pre Either \ref run() or \ref init() must be called before -
lemon/concepts/graph.h
r514 r550 602 602 /// \brief Opposite node on an arc 603 603 /// 604 /// \return the opposite of the given Node on the given Edge604 /// \return The opposite of the given node on the given edge. 605 605 Node oppositeNode(Node, Edge) const { return INVALID; } 606 606 607 607 /// \brief First node of the edge. 608 608 /// 609 /// \return the first node of the given Edge.609 /// \return The first node of the given edge. 610 610 /// 611 611 /// Naturally edges don't have direction and thus 612 /// don't have source and target node. But we use these two methods613 /// to query the two nodes of the arc. The direction of the arc614 /// which arises this way is called the inherent direction of the612 /// don't have source and target node. However we use \c u() and \c v() 613 /// methods to query the two nodes of the arc. The direction of the 614 /// arc which arises this way is called the inherent direction of the 615 615 /// edge, and is used to define the "default" direction 616 616 /// of the directed versions of the arcs. 617 /// \sa direction 617 /// \sa v() 618 /// \sa direction() 618 619 Node u(Edge) const { return INVALID; } 619 620 620 621 /// \brief Second node of the edge. 622 /// 623 /// \return The second node of the given edge. 624 /// 625 /// Naturally edges don't have direction and thus 626 /// don't have source and target node. However we use \c u() and \c v() 627 /// methods to query the two nodes of the arc. The direction of the 628 /// arc which arises this way is called the inherent direction of the 629 /// edge, and is used to define the "default" direction 630 /// of the directed versions of the arcs. 631 /// \sa u() 632 /// \sa direction() 621 633 Node v(Edge) const { return INVALID; } 622 634 -
lemon/concepts/graph_components.h
r521 r550 21 21 ///\brief The concept of graph components. 22 22 23 24 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H 25 24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 45 44 46 45 #ifndef DOXYGEN 47 template <char _selector= '0'>46 template <char sel = '0'> 48 47 #endif 49 48 class GraphItem { … … 297 296 /// The most of the base digraphs should conform to this concept. 298 297 /// The id's are unique and immutable. 299 template <typename _Base= BaseDigraphComponent>300 class IDableDigraphComponent : public _Base{301 public: 302 303 typedef _BaseBase;298 template <typename BAS = BaseDigraphComponent> 299 class IDableDigraphComponent : public BAS { 300 public: 301 302 typedef BAS Base; 304 303 typedef typename Base::Node Node; 305 304 typedef typename Base::Arc Arc; … … 375 374 /// most of the base undirected graphs should conform to this 376 375 /// concept. The id's are unique and immutable. 377 template <typename _Base= BaseGraphComponent>378 class IDableGraphComponent : public IDableDigraphComponent< _Base> {379 public: 380 381 typedef _BaseBase;376 template <typename BAS = BaseGraphComponent> 377 class IDableGraphComponent : public IDableDigraphComponent<BAS> { 378 public: 379 380 typedef BAS Base; 382 381 typedef typename Base::Edge Edge; 383 382 384 using IDableDigraphComponent< _Base>::id;383 using IDableDigraphComponent<Base>::id; 385 384 386 385 /// \brief Gives back an unique integer id for the Edge. … … 426 425 /// Skeleton class for graph NodeIt and ArcIt. 427 426 /// 428 template <typename _Graph, typename _Item>429 class GraphItemIt : public _Item {427 template <typename GR, typename Item> 428 class GraphItemIt : public Item { 430 429 public: 431 430 /// \brief Default constructor. … … 443 442 /// Sets the iterator to the first item of \c the graph. 444 443 /// 445 explicit GraphItemIt(const _Graph&) {}444 explicit GraphItemIt(const GR&) {} 446 445 /// \brief Invalid constructor \& conversion. 447 446 /// … … 480 479 ++(++it1); 481 480 482 _Item bi = it1;481 Item bi = it1; 483 482 bi = it2; 484 483 } 485 _Graph& g;484 GR& g; 486 485 }; 487 486 }; … … 490 489 /// 491 490 /// \note Because InArcIt and OutArcIt may not inherit from the same 492 /// base class, the _selector is a additional template parameter. For493 /// InArcIt you should instantiate it with character 'i' and for491 /// base class, the \c sel is a additional template parameter (selector). 492 /// For InArcIt you should instantiate it with character 'i' and for 494 493 /// OutArcIt with 'o'. 495 template <typename _Graph,496 typename _Item = typename _Graph::Arc,497 typename _Base = typename _Graph::Node,498 char _selector= '0'>499 class GraphIncIt : public _Item {494 template <typename GR, 495 typename Item = typename GR::Arc, 496 typename Base = typename GR::Node, 497 char sel = '0'> 498 class GraphIncIt : public Item { 500 499 public: 501 500 /// \brief Default constructor. … … 508 507 /// Copy constructor. 509 508 /// 510 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}509 GraphIncIt(GraphIncIt const& gi) : Item(gi) {} 511 510 /// \brief Sets the iterator to the first arc incoming into or outgoing 512 511 /// from the node. … … 515 514 /// from the node. 516 515 /// 517 explicit GraphIncIt(const _Graph&, const _Base&) {}516 explicit GraphIncIt(const GR&, const Base&) {} 518 517 /// \brief Invalid constructor \& conversion. 519 518 /// … … 547 546 struct Constraints { 548 547 void constraints() { 549 checkConcept<GraphItem< _selector>, _GraphIncIt>();548 checkConcept<GraphItem<sel>, _GraphIncIt>(); 550 549 _GraphIncIt it1(graph, node); 551 550 _GraphIncIt it2; … … 554 553 ++it2 = it1; 555 554 ++(++it1); 556 _Item e = it1;555 Item e = it1; 557 556 e = it2; 558 557 559 558 } 560 559 561 _Item arc;562 _Base node;563 _Graphgraph;560 Item arc; 561 Base node; 562 GR graph; 564 563 _GraphIncIt it; 565 564 }; … … 572 571 /// iterator based iterable interface for the digraph structure. 573 572 /// This concept is part of the Digraph concept. 574 template <typename _Base= BaseDigraphComponent>575 class IterableDigraphComponent : public _Base{576 577 public: 578 579 typedef _BaseBase;573 template <typename BAS = BaseDigraphComponent> 574 class IterableDigraphComponent : public BAS { 575 576 public: 577 578 typedef BAS Base; 580 579 typedef typename Base::Node Node; 581 580 typedef typename Base::Arc Arc; … … 757 756 /// based iterable interface for the undirected graph structure. 758 757 /// This concept is part of the Graph concept. 759 template <typename _Base= BaseGraphComponent>760 class IterableGraphComponent : public IterableDigraphComponent< _Base> {761 public: 762 763 typedef _BaseBase;758 template <typename BAS = BaseGraphComponent> 759 class IterableGraphComponent : public IterableDigraphComponent<BAS> { 760 public: 761 762 typedef BAS Base; 764 763 typedef typename Base::Node Node; 765 764 typedef typename Base::Arc Arc; … … 774 773 /// @{ 775 774 776 using IterableDigraphComponent< _Base>::first;777 using IterableDigraphComponent< _Base>::next;775 using IterableDigraphComponent<Base>::first; 776 using IterableDigraphComponent<Base>::next; 778 777 779 778 /// \brief Gives back the first edge in the iterating … … 809 808 void nextInc(Edge&, bool&) const {} 810 809 811 using IterableDigraphComponent< _Base>::baseNode;812 using IterableDigraphComponent< _Base>::runningNode;810 using IterableDigraphComponent<Base>::baseNode; 811 using IterableDigraphComponent<Base>::runningNode; 813 812 814 813 /// @} … … 876 875 877 876 const _Graph& graph; 878 879 877 }; 880 878 }; … … 888 886 /// alteration occured in the digraph all the observers will 889 887 /// notified about it. 890 template <typename _Base= BaseDigraphComponent>891 class AlterableDigraphComponent : public _Base{892 public: 893 894 typedef _BaseBase;888 template <typename BAS = BaseDigraphComponent> 889 class AlterableDigraphComponent : public BAS { 890 public: 891 892 typedef BAS Base; 895 893 typedef typename Base::Node Node; 896 894 typedef typename Base::Arc Arc; … … 946 944 /// alteration occured in the graph all the observers will 947 945 /// notified about it. 948 template <typename _Base= BaseGraphComponent>949 class AlterableGraphComponent : public AlterableDigraphComponent< _Base> {950 public: 951 952 typedef _BaseBase;946 template <typename BAS = BaseGraphComponent> 947 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> { 948 public: 949 950 typedef BAS Base; 953 951 typedef typename Base::Edge Edge; 954 952 … … 975 973 976 974 const _Graph& graph; 977 978 }; 979 975 }; 980 976 }; 981 977 … … 985 981 /// (NodeMap, ArcMap), that is maps that can be used to 986 982 /// associate data to graph descriptors (nodes or arcs). 987 template <typename _Graph, typename _Item, typename _Value>988 class GraphMap : public ReadWriteMap< _Item, _Value> {989 public: 990 991 typedef ReadWriteMap< _Item, _Value> Parent;983 template <typename GR, typename K, typename V> 984 class GraphMap : public ReadWriteMap<K, V> { 985 public: 986 987 typedef ReadWriteMap<K, V> Parent; 992 988 993 989 /// The graph type of the map. 994 typedef _GraphGraph;990 typedef GR Graph; 995 991 /// The key type of the map. 996 typedef _ItemKey;992 typedef K Key; 997 993 /// The value type of the map. 998 typedef _ValueValue;994 typedef V Value; 999 995 1000 996 /// \brief Construct a new map. … … 1056 1052 /// map interface for the digraph structure. 1057 1053 /// This concept is part of the Digraph concept. 1058 template <typename _Base= BaseDigraphComponent>1059 class MappableDigraphComponent : public _Base{1060 public: 1061 1062 typedef _BaseBase;1054 template <typename BAS = BaseDigraphComponent> 1055 class MappableDigraphComponent : public BAS { 1056 public: 1057 1058 typedef BAS Base; 1063 1059 typedef typename Base::Node Node; 1064 1060 typedef typename Base::Arc Arc; … … 1070 1066 /// ReadWrite map of the nodes. 1071 1067 /// 1072 template <typename _Value>1073 class NodeMap : public GraphMap<Digraph, Node, _Value> {1068 template <typename V> 1069 class NodeMap : public GraphMap<Digraph, Node, V> { 1074 1070 public: 1075 typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;1071 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; 1076 1072 1077 1073 /// \brief Construct a new map. … … 1084 1080 /// 1085 1081 /// Construct a new map for the digraph and initalise the values. 1086 NodeMap(const MappableDigraphComponent& digraph, const _Value& value)1082 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1087 1083 : Parent(digraph, value) {} 1088 1084 … … 1098 1094 template <typename CMap> 1099 1095 NodeMap& operator=(const CMap&) { 1100 checkConcept<ReadMap<Node, _Value>, CMap>();1096 checkConcept<ReadMap<Node, V>, CMap>(); 1101 1097 return *this; 1102 1098 } … … 1108 1104 /// ReadWrite map of the arcs. 1109 1105 /// 1110 template <typename _Value>1111 class ArcMap : public GraphMap<Digraph, Arc, _Value> {1106 template <typename V> 1107 class ArcMap : public GraphMap<Digraph, Arc, V> { 1112 1108 public: 1113 typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;1109 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; 1114 1110 1115 1111 /// \brief Construct a new map. … … 1122 1118 /// 1123 1119 /// Construct a new map for the digraph and initalise the values. 1124 ArcMap(const MappableDigraphComponent& digraph, const _Value& value)1120 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1125 1121 : Parent(digraph, value) {} 1126 1122 … … 1136 1132 template <typename CMap> 1137 1133 ArcMap& operator=(const CMap&) { 1138 checkConcept<ReadMap<Arc, _Value>, CMap>();1134 checkConcept<ReadMap<Arc, V>, CMap>(); 1139 1135 return *this; 1140 1136 } … … 1192 1188 /// map interface for the graph structure. 1193 1189 /// This concept is part of the Graph concept. 1194 template <typename _Base= BaseGraphComponent>1195 class MappableGraphComponent : public MappableDigraphComponent< _Base> {1196 public: 1197 1198 typedef _BaseBase;1190 template <typename BAS = BaseGraphComponent> 1191 class MappableGraphComponent : public MappableDigraphComponent<BAS> { 1192 public: 1193 1194 typedef BAS Base; 1199 1195 typedef typename Base::Edge Edge; 1200 1196 … … 1205 1201 /// ReadWrite map of the edges. 1206 1202 /// 1207 template <typename _Value>1208 class EdgeMap : public GraphMap<Graph, Edge, _Value> {1203 template <typename V> 1204 class EdgeMap : public GraphMap<Graph, Edge, V> { 1209 1205 public: 1210 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;1206 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; 1211 1207 1212 1208 /// \brief Construct a new map. … … 1219 1215 /// 1220 1216 /// Construct a new map for the graph and initalise the values. 1221 EdgeMap(const MappableGraphComponent& graph, const _Value& value)1217 EdgeMap(const MappableGraphComponent& graph, const V& value) 1222 1218 : Parent(graph, value) {} 1223 1219 … … 1233 1229 template <typename CMap> 1234 1230 EdgeMap& operator=(const CMap&) { 1235 checkConcept<ReadMap<Edge, _Value>, CMap>();1231 checkConcept<ReadMap<Edge, V>, CMap>(); 1236 1232 return *this; 1237 1233 } … … 1277 1273 /// difference between the base and this interface is that the 1278 1274 /// digraph alterations should handled already on this level. 1279 template <typename _Base= BaseDigraphComponent>1280 class ExtendableDigraphComponent : public _Base{1281 public: 1282 typedef _BaseBase;1283 1284 typedef typename _Base::Node Node;1285 typedef typename _Base::Arc Arc;1275 template <typename BAS = BaseDigraphComponent> 1276 class ExtendableDigraphComponent : public BAS { 1277 public: 1278 typedef BAS Base; 1279 1280 typedef typename Base::Node Node; 1281 typedef typename Base::Arc Arc; 1286 1282 1287 1283 /// \brief Adds a new node to the digraph. … … 1322 1318 /// that the graph alterations should handled already on this 1323 1319 /// level. 1324 template <typename _Base= BaseGraphComponent>1325 class ExtendableGraphComponent : public _Base{1326 public: 1327 1328 typedef _BaseBase;1329 typedef typename _Base::Node Node;1330 typedef typename _Base::Edge Edge;1320 template <typename BAS = BaseGraphComponent> 1321 class ExtendableGraphComponent : public BAS { 1322 public: 1323 1324 typedef BAS Base; 1325 typedef typename Base::Node Node; 1326 typedef typename Base::Edge Edge; 1331 1327 1332 1328 /// \brief Adds a new node to the graph. … … 1366 1362 /// the base and this interface is that the digraph alterations 1367 1363 /// should handled already on this level. 1368 template <typename _Base= BaseDigraphComponent>1369 class ErasableDigraphComponent : public _Base{1370 public: 1371 1372 typedef _BaseBase;1364 template <typename BAS = BaseDigraphComponent> 1365 class ErasableDigraphComponent : public BAS { 1366 public: 1367 1368 typedef BAS Base; 1373 1369 typedef typename Base::Node Node; 1374 1370 typedef typename Base::Arc Arc; … … 1406 1402 /// main difference between the base and this interface is that 1407 1403 /// the graph alterations should handled already on this level. 1408 template <typename _Base= BaseGraphComponent>1409 class ErasableGraphComponent : public _Base{1410 public: 1411 1412 typedef _BaseBase;1404 template <typename BAS = BaseGraphComponent> 1405 class ErasableGraphComponent : public BAS { 1406 public: 1407 1408 typedef BAS Base; 1413 1409 typedef typename Base::Node Node; 1414 1410 typedef typename Base::Edge Edge; … … 1446 1442 /// the base and this interface is that the digraph alterations 1447 1443 /// should handled already on this level. 1448 template <typename _Base= BaseDigraphComponent>1449 class ClearableDigraphComponent : public _Base{1450 public: 1451 1452 typedef _BaseBase;1444 template <typename BAS = BaseDigraphComponent> 1445 class ClearableDigraphComponent : public BAS { 1446 public: 1447 1448 typedef BAS Base; 1453 1449 1454 1450 /// \brief Erase all nodes and arcs from the digraph. … … 1475 1471 /// main difference between the base and this interface is that 1476 1472 /// the graph alterations should handled already on this level. 1477 template <typename _Base= BaseGraphComponent>1478 class ClearableGraphComponent : public ClearableDigraphComponent< _Base> {1479 public: 1480 1481 typedef _BaseBase;1473 template <typename BAS = BaseGraphComponent> 1474 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { 1475 public: 1476 1477 typedef BAS Base; 1482 1478 1483 1479 template <typename _Graph> -
lemon/concepts/heap.h
r514 r550 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. 39 template <typename Priority, typename ItemIntMap> 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. 43 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// internally 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 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename Comp = std::less<PR> > 51 #else 52 template <typename PR, typename IM> 53 #endif 40 54 class Heap { 41 55 public: 42 56 57 /// Type of the item-int map. 58 typedef IM ItemIntMap; 59 /// Type of the priorities. 60 typedef PR Prio; 43 61 /// Type of the items stored in the heap. 44 62 typedef typename ItemIntMap::Key Item; 45 46 /// Type of the priorities.47 typedef Priority Prio;48 63 49 64 /// \brief Type to represent the states of the items. … … 54 69 /// the user. 55 70 /// 56 /// The \c ItemIntMap must be initialized in such a way, that it57 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.71 /// The item-int map must be initialized in such way that it assigns 72 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 58 73 enum State { 59 IN_HEAP = 0, 60 PRE_HEAP = -1, 61 POST_HEAP = -2 74 IN_HEAP = 0, ///< The "in heap" state constant. 75 PRE_HEAP = -1, ///< The "pre heap" state constant. 76 POST_HEAP = -2 ///< The "post heap" state constant. 62 77 }; 63 78 … … 120 135 /// 121 136 /// Returns the priority of the given item. 137 /// \param i The item. 122 138 /// \pre \c i must be in the heap. 123 /// \param i The item.124 139 Prio operator[](const Item &i) const {} 125 140 … … 138 153 /// 139 154 /// Decreases the priority of an item to the given value. 155 /// \param i The item. 156 /// \param p The priority. 140 157 /// \pre \c i must be stored in the heap with priority at least \c p. 158 void decrease(const Item &i, const Prio &p) {} 159 160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 141 163 /// \param i The item. 142 164 /// \param p The priority. 143 void decrease(const Item &i, const Prio &p) {}144 145 /// \brief Increases the priority of an item to the given value.146 ///147 /// Increases the priority of an item to the given value.148 165 /// \pre \c i must be stored in the heap with priority at most \c p. 149 /// \param i The item.150 /// \param p The priority.151 166 void increase(const Item &i, const Prio &p) {} 152 167 -
lemon/concepts/path.h
r514 r550 39 39 /// A skeleton structure for representing directed paths in a 40 40 /// digraph. 41 /// \tparam _DigraphThe digraph type in which the path is.41 /// \tparam GR The digraph type in which the path is. 42 42 /// 43 43 /// In a sense, the path can be treated as a list of arcs. The … … 46 46 /// paths cannot store the source. 47 47 /// 48 template <typename _Digraph>48 template <typename GR> 49 49 class Path { 50 50 public: 51 51 52 52 /// Type of the underlying digraph. 53 typedef _DigraphDigraph;53 typedef GR Digraph; 54 54 /// Arc type of the underlying digraph. 55 55 typedef typename Digraph::Arc Arc; … … 206 206 /// assigned to a real path and the dumpers can be implemented as 207 207 /// an adaptor class to the predecessor map. 208 209 /// \tparam _DigraphThe digraph type in which the path is.208 /// 209 /// \tparam GR The digraph type in which the path is. 210 210 /// 211 211 /// The paths can be constructed from any path type by a 212 212 /// template constructor or a template assignment operator. 213 /// 214 template <typename _Digraph> 213 template <typename GR> 215 214 class PathDumper { 216 215 public: 217 216 218 217 /// Type of the underlying digraph. 219 typedef _DigraphDigraph;218 typedef GR Digraph; 220 219 /// Arc type of the underlying digraph. 221 220 typedef typename Digraph::Arc Arc; -
lemon/connectivity.h
r440 r550 47 47 /// Check whether the given undirected graph is connected. 48 48 /// \param graph The undirected graph. 49 /// \return %True when there is path between any two nodes in the graph.49 /// \return \c true when there is path between any two nodes in the graph. 50 50 /// \note By definition, the empty graph is connected. 51 51 template <typename Graph> … … 235 235 /// graph is strongly connected when any two nodes of the graph are 236 236 /// connected with directed paths in both direction. 237 /// \return %False when the graph is not strongly connected.237 /// \return \c false when the graph is not strongly connected. 238 238 /// \see connected 239 239 /// … … 710 710 /// 711 711 /// \param graph The graph. 712 /// \return %True when the graph bi-node-connected.712 /// \return \c true when the graph bi-node-connected. 713 713 template <typename Graph> 714 714 bool biNodeConnected(const Graph& graph) { … … 1231 1231 /// of the map will be set exactly once, the values will be set descending 1232 1232 /// order. 1233 /// \return %False when the graph is not DAG.1233 /// \return \c false when the graph is not DAG. 1234 1234 /// 1235 1235 /// \see topologicalSort … … 1280 1280 /// Check that the given directed graph is a DAG. The DAG is 1281 1281 /// an Directed Acyclic Digraph. 1282 /// \return %False when the graph is not DAG.1282 /// \return \c false when the graph is not DAG. 1283 1283 /// \see acyclic 1284 1284 template <typename Digraph> … … 1322 1322 /// Check that the given undirected graph acyclic. 1323 1323 /// \param graph The undirected graph. 1324 /// \return %True when there is no circle in the graph.1324 /// \return \c true when there is no circle in the graph. 1325 1325 /// \see dag 1326 1326 template <typename Graph> … … 1356 1356 /// Check that the given undirected graph is tree. 1357 1357 /// \param graph The undirected graph. 1358 /// \return %True when the graph is acyclic and connected.1358 /// \return \c true when the graph is acyclic and connected. 1359 1359 template <typename Graph> 1360 1360 bool tree(const Graph& graph) { … … 1449 1449 /// or not. The \ref Bfs algorithm is used to calculate the result. 1450 1450 /// \param graph The undirected graph. 1451 /// \return %True if \c graph is bipartite, %false otherwise.1451 /// \return \c true if \c graph is bipartite, \c false otherwise. 1452 1452 /// \sa bipartitePartitions 1453 1453 template<typename Graph> … … 1490 1490 /// \retval partMap A writable bool map of nodes. It will be set as the 1491 1491 /// two partitions of the graph. 1492 /// \return %True if \c graph is bipartite, %false otherwise.1492 /// \return \c true if \c graph is bipartite, \c false otherwise. 1493 1493 template<typename Graph, typename NodeMap> 1494 1494 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ -
lemon/core.h
r522 r550 1035 1035 ///\sa findArc() 1036 1036 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1037 template <typename _Graph>1038 class ConArcIt : public _Graph::Arc {1037 template <typename GR> 1038 class ConArcIt : public GR::Arc { 1039 1039 public: 1040 1040 1041 typedef _GraphGraph;1041 typedef GR Graph; 1042 1042 typedef typename Graph::Arc Parent; 1043 1043 … … 1158 1158 /// 1159 1159 ///\sa findEdge() 1160 template <typename _Graph>1161 class ConEdgeIt : public _Graph::Edge {1160 template <typename GR> 1161 class ConEdgeIt : public GR::Edge { 1162 1162 public: 1163 1163 1164 typedef _GraphGraph;1164 typedef GR Graph; 1165 1165 typedef typename Graph::Edge Parent; 1166 1166 … … 1212 1212 ///queries. 1213 1213 /// 1214 ///\tparam G The type of the underlying digraph.1214 ///\tparam GR The type of the underlying digraph. 1215 1215 /// 1216 1216 ///\sa ArcLookUp 1217 1217 ///\sa AllArcLookUp 1218 template <class G>1218 template <typename GR> 1219 1219 class DynArcLookUp 1220 : protected ItemSetTraits<G , typename G::Arc>::ItemNotifier::ObserverBase1220 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1221 1221 { 1222 1222 public: 1223 typedef typename ItemSetTraits<G , typename G::Arc>1223 typedef typename ItemSetTraits<GR, typename GR::Arc> 1224 1224 ::ItemNotifier::ObserverBase Parent; 1225 1225 1226 TEMPLATE_DIGRAPH_TYPEDEFS(G );1227 typedef G Digraph;1226 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1227 typedef GR Digraph; 1228 1228 1229 1229 protected: 1230 1230 1231 class AutoNodeMap : public ItemSetTraits<G , Node>::template Map<Arc>::Type {1231 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1232 1232 public: 1233 1233 1234 typedef typename ItemSetTraits<G , Node>::template Map<Arc>::Type Parent;1235 1236 AutoNodeMap(const G & digraph) : Parent(digraph, INVALID) {}1234 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1235 1236 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {} 1237 1237 1238 1238 virtual void add(const Node& node) { … … 1624 1624 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1625 1625 /// 1626 ///\tparam G The type of the underlying digraph.1626 ///\tparam GR The type of the underlying digraph. 1627 1627 /// 1628 1628 ///\sa DynArcLookUp 1629 1629 ///\sa AllArcLookUp 1630 template<class G >1630 template<class GR> 1631 1631 class ArcLookUp 1632 1632 { 1633 1633 public: 1634 TEMPLATE_DIGRAPH_TYPEDEFS(G );1635 typedef G Digraph;1634 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1635 typedef GR Digraph; 1636 1636 1637 1637 protected: … … 1734 1734 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1735 1735 /// 1736 ///\tparam G The type of the underlying digraph.1736 ///\tparam GR The type of the underlying digraph. 1737 1737 /// 1738 1738 ///\sa DynArcLookUp 1739 1739 ///\sa ArcLookUp 1740 template<class G >1741 class AllArcLookUp : public ArcLookUp<G >1740 template<class GR> 1741 class AllArcLookUp : public ArcLookUp<GR> 1742 1742 { 1743 using ArcLookUp<G >::_g;1744 using ArcLookUp<G >::_right;1745 using ArcLookUp<G >::_left;1746 using ArcLookUp<G >::_head;1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(G );1749 typedef G Digraph;1743 using ArcLookUp<GR>::_g; 1744 using ArcLookUp<GR>::_right; 1745 using ArcLookUp<GR>::_left; 1746 using ArcLookUp<GR>::_head; 1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1749 typedef GR Digraph; 1750 1750 1751 1751 typename Digraph::template ArcMap<Arc> _next; … … 1774 1774 ///It builds up the search database, which remains valid until the digraph 1775 1775 ///changes. 1776 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1776 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1777 1777 1778 1778 ///Refresh the data structure at a node. … … 1784 1784 void refresh(Node n) 1785 1785 { 1786 ArcLookUp<G >::refresh(n);1786 ArcLookUp<GR>::refresh(n); 1787 1787 refreshNext(_head[n]); 1788 1788 } … … 1831 1831 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1832 1832 #else 1833 using ArcLookUp<G >::operator() ;1833 using ArcLookUp<GR>::operator() ; 1834 1834 Arc operator()(Node s, Node t, Arc prev) const 1835 1835 { -
lemon/dijkstra.h
r519 r550 39 39 /// This operation traits class defines all computational operations and 40 40 /// constants which are used in the Dijkstra algorithm. 41 template <typename V alue>41 template <typename V> 42 42 struct DijkstraDefaultOperationTraits { 43 /// \e 44 typedef V Value; 43 45 /// \brief Gives back the zero value of the type. 44 46 static Value zero() { … … 59 61 ///Default traits class of Dijkstra class. 60 62 ///\tparam GR The type of the digraph. 61 ///\tparam L MThe type of the length map.62 template< class GR, class LM>63 ///\tparam LEN The type of the length map. 64 template<typename GR, typename LEN> 63 65 struct DijkstraDefaultTraits 64 66 { … … 70 72 ///The type of the map that stores the arc lengths. 71 73 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 72 typedef L MLengthMap;74 typedef LEN LengthMap; 73 75 ///The type of the length of the arcs. 74 typedef typename L M::Value Value;76 typedef typename LEN::Value Value; 75 77 76 78 /// Operation traits for %Dijkstra algorithm. … … 101 103 ///\sa BinHeap 102 104 ///\sa Dijkstra 103 typedef BinHeap<typename L M::Value, HeapCrossRef, std::less<Value> > Heap;105 typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap; 104 106 ///Instantiates a \c Heap. 105 107 … … 151 153 ///The type of the map that stores the distances of the nodes. 152 154 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 153 typedef typename Digraph::template NodeMap<typename L M::Value> DistMap;155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 154 156 ///Instantiates a \c DistMap. 155 157 … … 181 183 ///\tparam GR The type of the digraph the algorithm runs on. 182 184 ///The default type is \ref ListDigraph. 183 ///\tparam L MA \ref concepts::ReadMap "readable" arc map that specifies185 ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies 184 186 ///the lengths of the arcs. 185 187 ///It is read once for each arc, so the map may involve in … … 188 190 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 189 191 #ifdef DOXYGEN 190 template <typename GR, typename L M, typename TR>192 template <typename GR, typename LEN, typename TR> 191 193 #else 192 194 template <typename GR=ListDigraph, 193 typename L M=typename GR::template ArcMap<int>,194 typename TR=DijkstraDefaultTraits<GR,L M> >195 typename LEN=typename GR::template ArcMap<int>, 196 typename TR=DijkstraDefaultTraits<GR,LEN> > 195 197 #endif 196 198 class Dijkstra { … … 914 916 ///Default traits class of dijkstra() function. 915 917 ///\tparam GR The type of the digraph. 916 ///\tparam L MThe type of the length map.917 template<class GR, class L M>918 ///\tparam LEN The type of the length map. 919 template<class GR, class LEN> 918 920 struct DijkstraWizardDefaultTraits 919 921 { … … 924 926 ///The type of the map that stores the arc lengths. 925 927 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. 926 typedef L MLengthMap;928 typedef LEN LengthMap; 927 929 ///The type of the length of the arcs. 928 typedef typename L M::Value Value;930 typedef typename LEN::Value Value; 929 931 930 932 /// Operation traits for Dijkstra algorithm. … … 1008 1010 ///The type of the map that stores the distances of the nodes. 1009 1011 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1010 typedef typename Digraph::template NodeMap<typename L M::Value> DistMap;1012 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1011 1013 ///Instantiates a DistMap. 1012 1014 … … 1034 1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1035 1037 /// \ref DijkstraWizard class. 1036 template< class GR,class LM>1037 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,L M>1038 template<typename GR, typename LEN> 1039 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> 1038 1040 { 1039 typedef DijkstraWizardDefaultTraits<GR,L M> Base;1041 typedef DijkstraWizardDefaultTraits<GR,LEN> Base; 1040 1042 protected: 1041 1043 //The type of the nodes in the digraph. … … 1071 1073 /// \param g The digraph the algorithm runs on. 1072 1074 /// \param l The length map. 1073 DijkstraWizardBase(const GR &g,const L M&l) :1075 DijkstraWizardBase(const GR &g,const LEN &l) : 1074 1076 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 1075 _length(reinterpret_cast<void*>(const_cast<L M*>(&l))),1077 _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))), 1076 1078 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 1077 1079 … … 1282 1284 ///\sa DijkstraWizard 1283 1285 ///\sa Dijkstra 1284 template< class GR, class LM>1285 DijkstraWizard<DijkstraWizardBase<GR,L M> >1286 dijkstra(const GR &digraph, const L M&length)1286 template<typename GR, typename LEN> 1287 DijkstraWizard<DijkstraWizardBase<GR,LEN> > 1288 dijkstra(const GR &digraph, const LEN &length) 1287 1289 { 1288 return DijkstraWizard<DijkstraWizardBase<GR,L M> >(digraph,length);1290 return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length); 1289 1291 } 1290 1292 -
lemon/edge_set.h
r488 r550 256 256 /// concept. 257 257 /// 258 /// This class is fully conformto the \ref concepts::Digraph258 /// This class fully conforms to the \ref concepts::Digraph 259 259 /// "Digraph" concept. 260 260 template <typename GR> … … 337 337 /// Add a new arc to the digraph with source node \c s 338 338 /// and target node \c t. 339 /// \return the new arc.339 /// \return The new arc. 340 340 Arc addArc(const Node& s, const Node& t) { 341 341 return Parent::addArc(s, t); … … 685 685 /// concept. 686 686 /// 687 /// This class is fully conformto the \ref concepts::Graph "Graph"687 /// This class fully conforms to the \ref concepts::Graph "Graph" 688 688 /// concept. 689 689 template <typename GR> … … 762 762 /// Add a new edge to the graph with node \c u 763 763 /// and node \c v endpoints. 764 /// \return the new edge.764 /// \return The new edge. 765 765 Edge addEdge(const Node& u, const Node& v) { 766 766 return Parent::addEdge(u, v); … … 953 953 /// validity can be checked with the \c valid() member function. 954 954 /// 955 /// This class is fully conformto the \ref concepts::Digraph955 /// This class fully conforms to the \ref concepts::Digraph 956 956 /// "Digraph" concept. 957 957 template <typename GR> … … 1042 1042 /// Add a new arc to the digraph with source node \c s 1043 1043 /// and target node \c t. 1044 /// \return the new arc.1044 /// \return The new arc. 1045 1045 Arc addArc(const Node& s, const Node& t) { 1046 1046 return Parent::addArc(s, t); … … 1301 1301 /// be checked with the \c valid() member function. 1302 1302 /// 1303 /// This class is fully conformto the \ref concepts::Graph1303 /// This class fully conforms to the \ref concepts::Graph 1304 1304 /// "Graph" concept. 1305 1305 template <typename GR> … … 1390 1390 /// Add a new edge to the graph with node \c u 1391 1391 /// and node \c v endpoints. 1392 /// \return the new edge.1392 /// \return The new edge. 1393 1393 Edge addEdge(const Node& u, const Node& v) { 1394 1394 return Parent::addEdge(u, v); -
lemon/elevator.h
r503 r550 47 47 ///\sa LinkedElevator 48 48 /// 49 ///\param G raphType of the underlying graph.50 ///\param Item Type of the items the data is assigned to ( Graph::Node,51 /// Graph::Arc, Graph::Edge).52 template<class G raph, class Item>49 ///\param GR Type of the underlying graph. 50 ///\param Item Type of the items the data is assigned to (\c GR::Node, 51 ///\c GR::Arc or \c GR::Edge). 52 template<class GR, class Item> 53 53 class Elevator 54 54 { … … 61 61 62 62 typedef Item *Vit; 63 typedef typename ItemSetTraits<G raph,Item>::template Map<Vit>::Type VitMap;64 typedef typename ItemSetTraits<G raph,Item>::template Map<int>::Type IntMap;65 66 const G raph&_g;63 typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap; 64 typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap; 65 66 const GR &_g; 67 67 int _max_level; 68 68 int _item_num; … … 106 106 ///\param max_level The maximum allowed level. 107 107 ///Set the range of the possible labels to <tt>[0..max_level]</tt>. 108 Elevator(const G raph&graph,int max_level) :108 Elevator(const GR &graph,int max_level) : 109 109 _g(graph), 110 110 _max_level(max_level), … … 123 123 ///Set the range of the possible labels to <tt>[0..max_level]</tt>, 124 124 ///where \c max_level is equal to the number of labeled items in the graph. 125 Elevator(const G raph&graph) :125 Elevator(const GR &graph) : 126 126 _g(graph), 127 _max_level(countItems<G raph, Item>(graph)),127 _max_level(countItems<GR, Item>(graph)), 128 128 _item_num(_max_level), 129 129 _where(graph), … … 431 431 _last_active[0]=&_items[0]-1; 432 432 Vit n=&_items[0]; 433 for(typename ItemSetTraits<G raph,Item>::ItemIt i(_g);i!=INVALID;++i)433 for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i) 434 434 { 435 435 *n=i; … … 490 490 ///\sa Elevator 491 491 /// 492 ///\param G raphType of the underlying graph.493 ///\param Item Type of the items the data is assigned to ( Graph::Node,494 /// Graph::Arc, Graph::Edge).495 template <class G raph, class Item>492 ///\param GR Type of the underlying graph. 493 ///\param Item Type of the items the data is assigned to (\c GR::Node, 494 ///\c GR::Arc or \c GR::Edge). 495 template <class GR, class Item> 496 496 class LinkedElevator { 497 497 public: … … 502 502 private: 503 503 504 typedef typename ItemSetTraits<G raph,Item>::504 typedef typename ItemSetTraits<GR,Item>:: 505 505 template Map<Item>::Type ItemMap; 506 typedef typename ItemSetTraits<G raph,Item>::506 typedef typename ItemSetTraits<GR,Item>:: 507 507 template Map<int>::Type IntMap; 508 typedef typename ItemSetTraits<G raph,Item>::508 typedef typename ItemSetTraits<GR,Item>:: 509 509 template Map<bool>::Type BoolMap; 510 510 511 const G raph&_graph;511 const GR &_graph; 512 512 int _max_level; 513 513 int _item_num; … … 526 526 ///\param max_level The maximum allowed level. 527 527 ///Set the range of the possible labels to <tt>[0..max_level]</tt>. 528 LinkedElevator(const G raph& graph, int max_level)528 LinkedElevator(const GR& graph, int max_level) 529 529 : _graph(graph), _max_level(max_level), _item_num(_max_level), 530 530 _first(_max_level + 1), _last(_max_level + 1), … … 539 539 ///Set the range of the possible labels to <tt>[0..max_level]</tt>, 540 540 ///where \c max_level is equal to the number of labeled items in the graph. 541 LinkedElevator(const G raph& graph)542 : _graph(graph), _max_level(countItems<G raph, Item>(graph)),541 LinkedElevator(const GR& graph) 542 : _graph(graph), _max_level(countItems<GR, Item>(graph)), 543 543 _item_num(_max_level), 544 544 _first(_max_level + 1), _last(_max_level + 1), … … 936 936 } 937 937 _init_level = 0; 938 for(typename ItemSetTraits<G raph,Item>::ItemIt i(_graph);938 for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph); 939 939 i != INVALID; ++i) { 940 940 _level.set(i, _max_level); -
lemon/euler.h
r506 r550 55 55 ///If \c g is not Euler then the resulted tour will not be full or closed. 56 56 ///\sa EulerIt 57 template< class Digraph>57 template<typename GR> 58 58 class DiEulerIt 59 59 { 60 typedef typename Digraph::Node Node;61 typedef typename Digraph::NodeIt NodeIt;62 typedef typename Digraph::Arc Arc;63 typedef typename Digraph::ArcIt ArcIt;64 typedef typename Digraph::OutArcIt OutArcIt;65 typedef typename Digraph::InArcIt InArcIt;66 67 const Digraph&g;68 typename Digraph::template NodeMap<OutArcIt> nedge;60 typedef typename GR::Node Node; 61 typedef typename GR::NodeIt NodeIt; 62 typedef typename GR::Arc Arc; 63 typedef typename GR::ArcIt ArcIt; 64 typedef typename GR::OutArcIt OutArcIt; 65 typedef typename GR::InArcIt InArcIt; 66 67 const GR &g; 68 typename GR::template NodeMap<OutArcIt> nedge; 69 69 std::list<Arc> euler; 70 70 … … 73 73 ///Constructor 74 74 75 ///\param _gA digraph.75 ///\param gr A digraph. 76 76 ///\param start The starting point of the tour. If it is not given 77 77 /// the tour will start from the first node. 78 DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)79 : g( _g), nedge(g)78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) 79 : g(gr), nedge(g) 80 80 { 81 81 if(start==INVALID) start=NodeIt(g); … … 146 146 ///If \c g is not Euler then the resulted tour will not be full or closed. 147 147 ///\sa EulerIt 148 template< class Digraph>148 template<typename GR> 149 149 class EulerIt 150 150 { 151 typedef typename Digraph::Node Node;152 typedef typename Digraph::NodeIt NodeIt;153 typedef typename Digraph::Arc Arc;154 typedef typename Digraph::Edge Edge;155 typedef typename Digraph::ArcIt ArcIt;156 typedef typename Digraph::OutArcIt OutArcIt;157 typedef typename Digraph::InArcIt InArcIt;158 159 const Digraph&g;160 typename Digraph::template NodeMap<OutArcIt> nedge;161 typename Digraph::template EdgeMap<bool> visited;151 typedef typename GR::Node Node; 152 typedef typename GR::NodeIt NodeIt; 153 typedef typename GR::Arc Arc; 154 typedef typename GR::Edge Edge; 155 typedef typename GR::ArcIt ArcIt; 156 typedef typename GR::OutArcIt OutArcIt; 157 typedef typename GR::InArcIt InArcIt; 158 159 const GR &g; 160 typename GR::template NodeMap<OutArcIt> nedge; 161 typename GR::template EdgeMap<bool> visited; 162 162 std::list<Arc> euler; 163 163 … … 166 166 ///Constructor 167 167 168 ///\param _gAn graph.168 ///\param gr An graph. 169 169 ///\param start The starting point of the tour. If it is not given 170 170 /// the tour will start from the first node. 171 EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)172 : g( _g), nedge(g), visited(g,false)171 EulerIt(const GR &gr, typename GR::Node start = INVALID) 172 : g(gr), nedge(g), visited(g, false) 173 173 { 174 174 if(start==INVALID) start=NodeIt(g); … … 239 239 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, 240 240 ///but still have an Euler tour</em>. 241 template< class Digraph>241 template<typename GR> 242 242 #ifdef DOXYGEN 243 243 bool 244 244 #else 245 typename enable_if<UndirectedTagIndicator< Digraph>,bool>::type246 eulerian(const Digraph&g)247 { 248 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)245 typename enable_if<UndirectedTagIndicator<GR>,bool>::type 246 eulerian(const GR &g) 247 { 248 for(typename GR::NodeIt n(g);n!=INVALID;++n) 249 249 if(countIncEdges(g,n)%2) return false; 250 250 return connected(g); 251 251 } 252 template<class Digraph>253 typename disable_if<UndirectedTagIndicator< Digraph>,bool>::type252 template<class GR> 253 typename disable_if<UndirectedTagIndicator<GR>,bool>::type 254 254 #endif 255 eulerian(const Digraph&g)256 { 257 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)255 eulerian(const GR &g) 256 { 257 for(typename GR::NodeIt n(g);n!=INVALID;++n) 258 258 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; 259 return connected(Undirector<const Digraph>(g));259 return connected(Undirector<const GR>(g)); 260 260 } 261 261 -
lemon/graph_to_eps.h
r492 r550 65 65 ///Default traits class of \ref GraphToEps. 66 66 /// 67 ///\ c Gis the type of the underlying graph.68 template<class G >67 ///\param GR is the type of the underlying graph. 68 template<class GR> 69 69 struct DefaultGraphToEpsTraits 70 70 { 71 typedef G Graph;71 typedef GR Graph; 72 72 typedef typename Graph::Node Node; 73 73 typedef typename Graph::NodeIt NodeIt; … … 140 140 141 141 ///Constructor 142 ///\param _g Reference to the graph to be printed. 143 ///\param _os Reference to the output stream. 144 ///\param _os Reference to the output stream. 142 ///\param gr Reference to the graph to be printed. 143 ///\param ost Reference to the output stream. 145 144 ///By default it is <tt>std::cout</tt>. 146 ///\param _pros If it is \c true, then the \c ostream referenced by \c _os145 ///\param pros If it is \c true, then the \c ostream referenced by \c os 147 146 ///will be explicitly deallocated by the destructor. 148 DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,149 bool _pros=false) :150 g( _g), os(_os),147 DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout, 148 bool pros = false) : 149 g(gr), os(ost), 151 150 _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0), 152 151 _nodeColors(WHITE), _arcColors(BLACK), … … 159 158 _showNodeText(false), _nodeTexts(false), _nodeTextSize(1), 160 159 _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0), 161 _undirected(lemon::UndirectedTagIndicator<G >::value),162 _pleaseRemoveOsStream( _pros), _scaleToA4(false),160 _undirected(lemon::UndirectedTagIndicator<GR>::value), 161 _pleaseRemoveOsStream(pros), _scaleToA4(false), 163 162 _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK), 164 163 _autoNodeScale(false), … … 1135 1134 ///to the end of the parameter list. 1136 1135 ///\sa GraphToEps 1137 ///\sa graphToEps(G &g, const char *file_name)1138 template<class G >1139 GraphToEps<DefaultGraphToEpsTraits<G > >1140 graphToEps(G &g, std::ostream& os=std::cout)1136 ///\sa graphToEps(GR &g, const char *file_name) 1137 template<class GR> 1138 GraphToEps<DefaultGraphToEpsTraits<GR> > 1139 graphToEps(GR &g, std::ostream& os=std::cout) 1141 1140 { 1142 1141 return 1143 GraphToEps<DefaultGraphToEpsTraits<G > >(DefaultGraphToEpsTraits<G>(g,os));1142 GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os)); 1144 1143 } 1145 1144 … … 1148 1147 ///\ingroup eps_io 1149 1148 ///This function does the same as 1150 ///\ref graphToEps(G &g,std::ostream& os)1149 ///\ref graphToEps(GR &g,std::ostream& os) 1151 1150 ///but it writes its output into the file \c file_name 1152 1151 ///instead of a stream. 1153 ///\sa graphToEps(G &g, std::ostream& os)1154 template<class G >1155 GraphToEps<DefaultGraphToEpsTraits<G > >1156 graphToEps(G &g,const char *file_name)1152 ///\sa graphToEps(GR &g, std::ostream& os) 1153 template<class GR> 1154 GraphToEps<DefaultGraphToEpsTraits<GR> > 1155 graphToEps(GR &g,const char *file_name) 1157 1156 { 1158 1157 std::ostream* os = new std::ofstream(file_name); … … 1161 1160 throw IoError("Cannot write file", file_name); 1162 1161 } 1163 return GraphToEps<DefaultGraphToEpsTraits<G > >1164 (DefaultGraphToEpsTraits<G >(g,*os,true));1162 return GraphToEps<DefaultGraphToEpsTraits<GR> > 1163 (DefaultGraphToEpsTraits<GR>(g,*os,true)); 1165 1164 } 1166 1165 … … 1169 1168 ///\ingroup eps_io 1170 1169 ///This function does the same as 1171 ///\ref graphToEps(G &g,std::ostream& os)1170 ///\ref graphToEps(GR &g,std::ostream& os) 1172 1171 ///but it writes its output into the file \c file_name 1173 1172 ///instead of a stream. 1174 ///\sa graphToEps(G &g, std::ostream& os)1175 template<class G >1176 GraphToEps<DefaultGraphToEpsTraits<G > >1177 graphToEps(G &g,const std::string& file_name)1173 ///\sa graphToEps(GR &g, std::ostream& os) 1174 template<class GR> 1175 GraphToEps<DefaultGraphToEpsTraits<GR> > 1176 graphToEps(GR &g,const std::string& file_name) 1178 1177 { 1179 1178 std::ostream* os = new std::ofstream(file_name.c_str()); … … 1182 1181 throw IoError("Cannot write file", file_name); 1183 1182 } 1184 return GraphToEps<DefaultGraphToEpsTraits<G > >1185 (DefaultGraphToEpsTraits<G >(g,*os,true));1183 return GraphToEps<DefaultGraphToEpsTraits<GR> > 1184 (DefaultGraphToEpsTraits<GR>(g,*os,true)); 1186 1185 } 1187 1186 -
lemon/grid_graph.h
r440 r550 497 497 ///\endcode 498 498 /// 499 /// This graph type is fully conformto the \ref concepts::Graph499 /// This graph type fully conforms to the \ref concepts::Graph 500 500 /// "Graph" concept, and it also has an important extra feature 501 501 /// that its maps are real \ref concepts::ReferenceMap -
lemon/hao_orlin.h
r440 r550 58 58 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki 59 59 /// which solves the undirected problem in 60 /// \f$ O(nm + n^2 \log (n)) \f$ time: it is implemented in the60 /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the 61 61 /// NagamochiIbaraki algorithm class. 62 62 /// 63 /// \param _Digraph is the graph type of the algorithm.64 /// \param _CapacityMap is an edge map of capacities which should65 /// be any numreric type. The default type is _Digraph::ArcMap<int>.66 /// \param _Tolerance is the handler of the inexact computation. The67 /// default t ype for this is Tolerance<CapacityMap::Value>.63 /// \param GR The digraph class the algorithm runs on. 64 /// \param CAP An arc map of capacities which can be any numreric type. 65 /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 66 /// \param TOL Tolerance class for handling inexact computations. The 67 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". 68 68 #ifdef DOXYGEN 69 template <typename _Digraph, typename _CapacityMap, typename _Tolerance>69 template <typename GR, typename CAP, typename TOL> 70 70 #else 71 template <typename _Digraph,72 typename _CapacityMap = typename _Digraph::template ArcMap<int>,73 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >71 template <typename GR, 72 typename CAP = typename GR::template ArcMap<int>, 73 typename TOL = Tolerance<typename CAP::Value> > 74 74 #endif 75 75 class HaoOrlin { 76 76 private: 77 77 78 typedef _DigraphDigraph;79 typedef _CapacityMapCapacityMap;80 typedef _ToleranceTolerance;78 typedef GR Digraph; 79 typedef CAP CapacityMap; 80 typedef TOL Tolerance; 81 81 82 82 typedef typename CapacityMap::Value Value; … … 818 818 /// \name Execution control 819 819 /// The simplest way to execute the algorithm is to use 820 /// one of the member functions called \ c run(...).820 /// one of the member functions called \ref run(). 821 821 /// \n 822 822 /// If you need more control on the execution, -
lemon/hypercube_graph.h
r440 r550 292 292 /// (assuming that the size of \c int is 32 bit). 293 293 /// 294 /// This graph type is fully conformto the \ref concepts::Graph294 /// This graph type fully conforms to the \ref concepts::Graph 295 295 /// "Graph" concept, and it also has an important extra feature 296 296 /// that its maps are real \ref concepts::ReferenceMap -
lemon/lgf_reader.h
r500 r550 449 449 /// a single pass, because the arcs are not constructed when the node 450 450 /// maps are read. 451 template <typename _Digraph>451 template <typename GR> 452 452 class DigraphReader { 453 453 public: 454 454 455 typedef _Digraph Digraph; 455 typedef GR Digraph; 456 457 private: 458 456 459 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 457 458 private:459 460 460 461 461 std::istream* _is; … … 1247 1247 /// arc map. Similarly, an attribute can be read into an arc, if 1248 1248 /// it's value is an edge label prefixed with \c '+' or \c '-'. 1249 template <typename _Graph>1249 template <typename GR> 1250 1250 class GraphReader { 1251 1251 public: 1252 1252 1253 typedef _Graph Graph; 1253 typedef GR Graph; 1254 1255 private: 1256 1254 1257 TEMPLATE_GRAPH_TYPEDEFS(Graph); 1255 1256 private:1257 1258 1258 1259 std::istream* _is; … … 1357 1358 1358 1359 private: 1359 template <typename G R>1360 friend GraphReader<G R> graphReader(GR& graph, std::istream& is);1361 template <typename G R>1362 friend GraphReader<G R> graphReader(GR& graph, const std::string& fn);1363 template <typename G R>1364 friend GraphReader<G R> graphReader(GR& graph, const char *fn);1360 template <typename Graph> 1361 friend GraphReader<Graph> graphReader(Graph& graph, std::istream& is); 1362 template <typename Graph> 1363 friend GraphReader<Graph> graphReader(Graph& graph, const std::string& fn); 1364 template <typename Graph> 1365 friend GraphReader<Graph> graphReader(Graph& graph, const char *fn); 1365 1366 1366 1367 GraphReader(GraphReader& other) -
lemon/lgf_writer.h
r500 r550 407 407 /// the \c ostream() function, hence the second pass can append its 408 408 /// output to the output of the first pass. 409 template <typename _Digraph>409 template <typename GR> 410 410 class DigraphWriter { 411 411 public: 412 412 413 typedef _DigraphDigraph;413 typedef GR Digraph; 414 414 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 415 415 … … 975 975 /// section as a \c '+' or a \c '-' prefix (depends on the direction 976 976 /// of the arc) and the label of corresponding edge. 977 template <typename _Graph>977 template <typename GR> 978 978 class GraphWriter { 979 979 public: 980 980 981 typedef _GraphGraph;981 typedef GR Graph; 982 982 TEMPLATE_GRAPH_TYPEDEFS(Graph); 983 983 … … 1074 1074 private: 1075 1075 1076 template <typename G R>1077 friend GraphWriter<G R> graphWriter(const GR& graph,1078 std::ostream& os);1079 template <typename G R>1080 friend GraphWriter<G R> graphWriter(const GR& graph,1081 const std::string& fn);1082 template <typename G R>1083 friend GraphWriter<G R> graphWriter(const GR& graph,1084 const char *fn);1076 template <typename Graph> 1077 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1078 std::ostream& os); 1079 template <typename Graph> 1080 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1081 const std::string& fn); 1082 template <typename Graph> 1083 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1084 const char *fn); 1085 1085 1086 1086 GraphWriter(GraphWriter& other) -
lemon/list_graph.h
r440 r550 352 352 353 353 ///Add a new node to the digraph. 354 ///\return the new node.354 ///\return The new node. 355 355 Node addNode() { return Parent::addNode(); } 356 356 … … 359 359 ///Add a new arc to the digraph with source node \c s 360 360 ///and target node \c t. 361 ///\return the new arc.361 ///\return The new arc. 362 362 Arc addArc(const Node& s, const Node& t) { 363 363 return Parent::addArc(s, t); … … 1209 1209 /// 1210 1210 /// Add a new node to the graph. 1211 /// \return the new node.1211 /// \return The new node. 1212 1212 Node addNode() { return Parent::addNode(); } 1213 1213 … … 1216 1216 /// Add a new edge to the graph with source node \c s 1217 1217 /// and target node \c t. 1218 /// \return the new edge.1218 /// \return The new edge. 1219 1219 Edge addEdge(const Node& s, const Node& t) { 1220 1220 return Parent::addEdge(s, t); -
lemon/maps.h
r440 r550 64 64 class NullMap : public MapBase<K, V> { 65 65 public: 66 typedef MapBase<K, V> Parent; 67 typedef typename Parent::Key Key; 68 typedef typename Parent::Value Value; 66 ///\e 67 typedef K Key; 68 ///\e 69 typedef V Value; 69 70 70 71 /// Gives back a default constructed element. … … 103 104 V _value; 104 105 public: 105 typedef MapBase<K, V> Parent; 106 typedef typename Parent::Key Key; 107 typedef typename Parent::Value Value; 106 ///\e 107 typedef K Key; 108 ///\e 109 typedef V Value; 108 110 109 111 /// Default constructor … … 169 171 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { 170 172 public: 171 typedef MapBase<K, V> Parent; 172 typedef typename Parent::Key Key; 173 typedef typename Parent::Value Value; 173 ///\e 174 typedef K Key; 175 ///\e 176 typedef V Value; 174 177 175 178 /// Constructor. … … 203 206 class IdentityMap : public MapBase<T, T> { 204 207 public: 205 typedef MapBase<T, T> Parent; 206 typedef typename Parent::Key Key; 207 typedef typename Parent::Value Value; 208 ///\e 209 typedef T Key; 210 ///\e 211 typedef T Value; 208 212 209 213 /// Gives back the given value without any modification. … … 246 250 public: 247 251 248 typedef MapBase<int, V> Parent;249 252 /// Key type 250 typedef typename Parent::KeyKey;253 typedef int Key; 251 254 /// Value type 252 typedef typename Parent::ValueValue;255 typedef V Value; 253 256 /// Reference type 254 257 typedef typename Vector::reference Reference; … … 354 357 /// The simplest way of using this map is through the sparseMap() 355 358 /// function. 356 template <typename K, typename V, typename Comp are= std::less<K> >359 template <typename K, typename V, typename Comp = std::less<K> > 357 360 class SparseMap : public MapBase<K, V> { 358 361 template <typename K1, typename V1, typename C1> … … 360 363 public: 361 364 362 typedef MapBase<K, V> Parent;363 365 /// Key type 364 typedef typename Parent::KeyKey;366 typedef K Key; 365 367 /// Value type 366 typedef typename Parent::ValueValue;368 typedef V Value; 367 369 /// Reference type 368 370 typedef Value& Reference; … … 374 376 private: 375 377 376 typedef std::map<K, V, Comp are> Map;378 typedef std::map<K, V, Comp> Map; 377 379 Map _map; 378 380 Value _value; … … 490 492 const M2 &_m2; 491 493 public: 492 typedef MapBase<typename M2::Key, typename M1::Value> Parent; 493 typedef typename Parent::Key Key; 494 typedef typename Parent::Value Value; 494 ///\e 495 typedef typename M2::Key Key; 496 ///\e 497 typedef typename M1::Value Value; 495 498 496 499 /// Constructor 497 500 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 498 501 499 /// 502 ///\e 500 503 typename MapTraits<M1>::ConstReturnValue 501 504 operator[](const Key &k) const { return _m1[_m2[k]]; } … … 546 549 F _f; 547 550 public: 548 typedef MapBase<typename M1::Key, V> Parent; 549 typedef typename Parent::Key Key; 550 typedef typename Parent::Value Value; 551 ///\e 552 typedef typename M1::Key Key; 553 ///\e 554 typedef V Value; 551 555 552 556 /// Constructor 553 557 CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) 554 558 : _m1(m1), _m2(m2), _f(f) {} 555 /// 559 ///\e 556 560 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } 557 561 }; … … 616 620 F _f; 617 621 public: 618 typedef MapBase<K, V> Parent; 619 typedef typename Parent::Key Key; 620 typedef typename Parent::Value Value; 622 ///\e 623 typedef K Key; 624 ///\e 625 typedef V Value; 621 626 622 627 /// Constructor 623 628 FunctorToMap(const F &f = F()) : _f(f) {} 624 /// 629 ///\e 625 630 Value operator[](const Key &k) const { return _f(k); } 626 631 }; … … 670 675 const M &_m; 671 676 public: 672 typedef MapBase<typename M::Key, typename M::Value> Parent; 673 typedef typename Parent::Key Key; 674 typedef typename Parent::Value Value; 675 676 typedef typename Parent::Key argument_type; 677 typedef typename Parent::Value result_type; 677 ///\e 678 typedef typename M::Key Key; 679 ///\e 680 typedef typename M::Value Value; 681 682 typedef typename M::Key argument_type; 683 typedef typename M::Value result_type; 678 684 679 685 /// Constructor 680 686 MapToFunctor(const M &m) : _m(m) {} 681 /// 687 ///\e 682 688 Value operator()(const Key &k) const { return _m[k]; } 683 /// 689 ///\e 684 690 Value operator[](const Key &k) const { return _m[k]; } 685 691 }; … … 710 716 const M &_m; 711 717 public: 712 typedef MapBase<typename M::Key, V> Parent; 713 typedef typename Parent::Key Key; 714 typedef typename Parent::Value Value; 718 ///\e 719 typedef typename M::Key Key; 720 ///\e 721 typedef V Value; 715 722 716 723 /// Constructor … … 720 727 ConvertMap(const M &m) : _m(m) {} 721 728 722 /// 729 ///\e 723 730 Value operator[](const Key &k) const { return _m[k]; } 724 731 }; … … 752 759 M2 &_m2; 753 760 public: 754 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 755 typedef typename Parent::Key Key; 756 typedef typename Parent::Value Value; 761 ///\e 762 typedef typename M1::Key Key; 763 ///\e 764 typedef typename M1::Value Value; 757 765 758 766 /// Constructor … … 798 806 const M2 &_m2; 799 807 public: 800 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 801 typedef typename Parent::Key Key; 802 typedef typename Parent::Value Value; 808 ///\e 809 typedef typename M1::Key Key; 810 ///\e 811 typedef typename M1::Value Value; 803 812 804 813 /// Constructor 805 814 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 806 /// 815 ///\e 807 816 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } 808 817 }; … … 846 855 const M2 &_m2; 847 856 public: 848 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 849 typedef typename Parent::Key Key; 850 typedef typename Parent::Value Value; 857 ///\e 858 typedef typename M1::Key Key; 859 ///\e 860 typedef typename M1::Value Value; 851 861 852 862 /// Constructor 853 863 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 854 /// 864 ///\e 855 865 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } 856 866 }; … … 895 905 const M2 &_m2; 896 906 public: 897 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 898 typedef typename Parent::Key Key; 899 typedef typename Parent::Value Value; 907 ///\e 908 typedef typename M1::Key Key; 909 ///\e 910 typedef typename M1::Value Value; 900 911 901 912 /// Constructor 902 913 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 903 /// 914 ///\e 904 915 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } 905 916 }; … … 943 954 const M2 &_m2; 944 955 public: 945 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 946 typedef typename Parent::Key Key; 947 typedef typename Parent::Value Value; 956 ///\e 957 typedef typename M1::Key Key; 958 ///\e 959 typedef typename M1::Value Value; 948 960 949 961 /// Constructor 950 962 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 951 /// 963 ///\e 952 964 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } 953 965 }; … … 993 1005 C _v; 994 1006 public: 995 typedef MapBase<typename M::Key, typename M::Value> Parent; 996 typedef typename Parent::Key Key; 997 typedef typename Parent::Value Value; 1007 ///\e 1008 typedef typename M::Key Key; 1009 ///\e 1010 typedef typename M::Value Value; 998 1011 999 1012 /// Constructor … … 1003 1016 /// \param v The constant value. 1004 1017 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} 1005 /// 1018 ///\e 1006 1019 Value operator[](const Key &k) const { return _m[k]+_v; } 1007 1020 }; … … 1023 1036 C _v; 1024 1037 public: 1025 typedef MapBase<typename M::Key, typename M::Value> Parent; 1026 typedef typename Parent::Key Key; 1027 typedef typename Parent::Value Value; 1038 ///\e 1039 typedef typename M::Key Key; 1040 ///\e 1041 typedef typename M::Value Value; 1028 1042 1029 1043 /// Constructor … … 1033 1047 /// \param v The constant value. 1034 1048 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1035 /// 1049 ///\e 1036 1050 Value operator[](const Key &k) const { return _m[k]+_v; } 1037 /// 1051 ///\e 1038 1052 void set(const Key &k, const Value &v) { _m.set(k, v-_v); } 1039 1053 }; … … 1094 1108 C _v; 1095 1109 public: 1096 typedef MapBase<typename M::Key, typename M::Value> Parent; 1097 typedef typename Parent::Key Key; 1098 typedef typename Parent::Value Value; 1110 ///\e 1111 typedef typename M::Key Key; 1112 ///\e 1113 typedef typename M::Value Value; 1099 1114 1100 1115 /// Constructor … … 1104 1119 /// \param v The constant value. 1105 1120 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} 1106 /// 1121 ///\e 1107 1122 Value operator[](const Key &k) const { return _v*_m[k]; } 1108 1123 }; … … 1125 1140 C _v; 1126 1141 public: 1127 typedef MapBase<typename M::Key, typename M::Value> Parent; 1128 typedef typename Parent::Key Key; 1129 typedef typename Parent::Value Value; 1142 ///\e 1143 typedef typename M::Key Key; 1144 ///\e 1145 typedef typename M::Value Value; 1130 1146 1131 1147 /// Constructor … … 1135 1151 /// \param v The constant value. 1136 1152 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1137 /// 1153 ///\e 1138 1154 Value operator[](const Key &k) const { return _v*_m[k]; } 1139 /// 1155 ///\e 1140 1156 void set(const Key &k, const Value &v) { _m.set(k, v/_v); } 1141 1157 }; … … 1194 1210 const M& _m; 1195 1211 public: 1196 typedef MapBase<typename M::Key, typename M::Value> Parent; 1197 typedef typename Parent::Key Key; 1198 typedef typename Parent::Value Value; 1212 ///\e 1213 typedef typename M::Key Key; 1214 ///\e 1215 typedef typename M::Value Value; 1199 1216 1200 1217 /// Constructor 1201 1218 NegMap(const M &m) : _m(m) {} 1202 /// 1219 ///\e 1203 1220 Value operator[](const Key &k) const { return -_m[k]; } 1204 1221 }; … … 1229 1246 M &_m; 1230 1247 public: 1231 typedef MapBase<typename M::Key, typename M::Value> Parent; 1232 typedef typename Parent::Key Key; 1233 typedef typename Parent::Value Value; 1248 ///\e 1249 typedef typename M::Key Key; 1250 ///\e 1251 typedef typename M::Value Value; 1234 1252 1235 1253 /// Constructor 1236 1254 NegWriteMap(M &m) : _m(m) {} 1237 /// 1255 ///\e 1238 1256 Value operator[](const Key &k) const { return -_m[k]; } 1239 /// 1257 ///\e 1240 1258 void set(const Key &k, const Value &v) { _m.set(k, -v); } 1241 1259 }; … … 1283 1301 const M &_m; 1284 1302 public: 1285 typedef MapBase<typename M::Key, typename M::Value> Parent; 1286 typedef typename Parent::Key Key; 1287 typedef typename Parent::Value Value; 1303 ///\e 1304 typedef typename M::Key Key; 1305 ///\e 1306 typedef typename M::Value Value; 1288 1307 1289 1308 /// Constructor 1290 1309 AbsMap(const M &m) : _m(m) {} 1291 /// 1310 ///\e 1292 1311 Value operator[](const Key &k) const { 1293 1312 Value tmp = _m[k]; … … 1338 1357 class TrueMap : public MapBase<K, bool> { 1339 1358 public: 1340 typedef MapBase<K, bool> Parent; 1341 typedef typename Parent::Key Key; 1342 typedef typename Parent::Value Value; 1359 ///\e 1360 typedef K Key; 1361 ///\e 1362 typedef bool Value; 1343 1363 1344 1364 /// Gives back \c true. … … 1375 1395 class FalseMap : public MapBase<K, bool> { 1376 1396 public: 1377 typedef MapBase<K, bool> Parent; 1378 typedef typename Parent::Key Key; 1379 typedef typename Parent::Value Value; 1397 ///\e 1398 typedef K Key; 1399 ///\e 1400 typedef bool Value; 1380 1401 1381 1402 /// Gives back \c false. … … 1420 1441 const M2 &_m2; 1421 1442 public: 1422 typedef MapBase<typename M1::Key, bool> Parent; 1423 typedef typename Parent::Key Key; 1424 typedef typename Parent::Value Value; 1443 ///\e 1444 typedef typename M1::Key Key; 1445 ///\e 1446 typedef bool Value; 1425 1447 1426 1448 /// Constructor 1427 1449 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1428 /// 1450 ///\e 1429 1451 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } 1430 1452 }; … … 1468 1490 const M2 &_m2; 1469 1491 public: 1470 typedef MapBase<typename M1::Key, bool> Parent; 1471 typedef typename Parent::Key Key; 1472 typedef typename Parent::Value Value; 1492 ///\e 1493 typedef typename M1::Key Key; 1494 ///\e 1495 typedef bool Value; 1473 1496 1474 1497 /// Constructor 1475 1498 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1476 /// 1499 ///\e 1477 1500 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } 1478 1501 }; … … 1507 1530 const M &_m; 1508 1531 public: 1509 typedef MapBase<typename M::Key, bool> Parent; 1510 typedef typename Parent::Key Key; 1511 typedef typename Parent::Value Value; 1532 ///\e 1533 typedef typename M::Key Key; 1534 ///\e 1535 typedef bool Value; 1512 1536 1513 1537 /// Constructor 1514 1538 NotMap(const M &m) : _m(m) {} 1515 /// 1539 ///\e 1516 1540 Value operator[](const Key &k) const { return !_m[k]; } 1517 1541 }; … … 1533 1557 M &_m; 1534 1558 public: 1535 typedef MapBase<typename M::Key, bool> Parent; 1536 typedef typename Parent::Key Key; 1537 typedef typename Parent::Value Value; 1559 ///\e 1560 typedef typename M::Key Key; 1561 ///\e 1562 typedef bool Value; 1538 1563 1539 1564 /// Constructor 1540 1565 NotWriteMap(M &m) : _m(m) {} 1541 /// 1566 ///\e 1542 1567 Value operator[](const Key &k) const { return !_m[k]; } 1543 /// 1568 ///\e 1544 1569 void set(const Key &k, bool v) { _m.set(k, !v); } 1545 1570 }; … … 1596 1621 const M2 &_m2; 1597 1622 public: 1598 typedef MapBase<typename M1::Key, bool> Parent; 1599 typedef typename Parent::Key Key; 1600 typedef typename Parent::Value Value; 1623 ///\e 1624 typedef typename M1::Key Key; 1625 ///\e 1626 typedef bool Value; 1601 1627 1602 1628 /// Constructor 1603 1629 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1604 /// 1630 ///\e 1605 1631 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } 1606 1632 }; … … 1644 1670 const M2 &_m2; 1645 1671 public: 1646 typedef MapBase<typename M1::Key, bool> Parent; 1647 typedef typename Parent::Key Key; 1648 typedef typename Parent::Value Value; 1672 ///\e 1673 typedef typename M1::Key Key; 1674 ///\e 1675 typedef bool Value; 1649 1676 1650 1677 /// Constructor 1651 1678 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1652 /// 1679 ///\e 1653 1680 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } 1654 1681 }; … … 1706 1733 /// function. 1707 1734 /// 1708 /// \tparam I tThe type of the iterator.1709 /// \tparam K eThe key type of the map. The default value set1735 /// \tparam IT The type of the iterator. 1736 /// \tparam KEY The key type of the map. The default value set 1710 1737 /// according to the iterator type should work in most cases. 1711 1738 /// … … 1713 1740 /// for the elements or the iterator should be an inserter iterator. 1714 1741 #ifdef DOXYGEN 1715 template <typename I t, typename Ke>1742 template <typename IT, typename KEY> 1716 1743 #else 1717 template <typename I t,1718 typename K e=typename _maps_bits::IteratorTraits<It>::Value>1744 template <typename IT, 1745 typename KEY = typename _maps_bits::IteratorTraits<IT>::Value> 1719 1746 #endif 1720 class LoggerBoolMap { 1721 public: 1722 typedef It Iterator; 1723 1724 typedef Ke Key; 1747 class LoggerBoolMap : public MapBase<KEY, bool> { 1748 public: 1749 1750 ///\e 1751 typedef KEY Key; 1752 ///\e 1725 1753 typedef bool Value; 1754 ///\e 1755 typedef IT Iterator; 1726 1756 1727 1757 /// Constructor … … 1786 1816 /// @{ 1787 1817 1788 /// Provides an immutable and unique id for each item in the graph. 1789 1790 /// The IdMap class provides a unique and immutable id for each item of the 1791 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: 1792 /// different items (nodes) get different ids <li>\b immutable: the id of an 1793 /// item (node) does not change (even if you delete other nodes). </ul> 1794 /// Through this map you get access (i.e. can read) the inner id values of 1795 /// the items stored in the graph. This map can be inverted with its member 1818 /// \brief Provides an immutable and unique id for each item in a graph. 1819 /// 1820 /// 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 1822 /// - \b unique: different items get different ids, 1823 /// - \b immutable: the id of an item does not change (even if you 1824 /// delete other nodes). 1825 /// 1826 /// Using this map you get access (i.e. can read) the inner id values of 1827 /// the items stored in the graph, which is returned by the \c id() 1828 /// function of the graph. This map can be inverted with its member 1796 1829 /// class \c InverseMap or with the \c operator() member. 1797 1830 /// 1798 template <typename _Graph, typename _Item> 1799 class IdMap { 1800 public: 1801 typedef _Graph Graph; 1831 /// \tparam GR The graph type. 1832 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 1833 /// \c GR::Edge). 1834 /// 1835 /// \see DescriptorMap 1836 template <typename GR, typename K> 1837 class IdMap : public MapBase<K, int> { 1838 public: 1839 /// The graph type of IdMap. 1840 typedef GR Graph; 1841 /// The key type of IdMap (\c Node, \c Arc or \c Edge). 1842 typedef K Item; 1843 /// The key type of IdMap (\c Node, \c Arc or \c Edge). 1844 typedef K Key; 1845 /// The value type of IdMap. 1802 1846 typedef int Value; 1803 typedef _Item Item;1804 typedef _Item Key;1805 1847 1806 1848 /// \brief Constructor. … … 1814 1856 int operator[](const Item& item) const { return _graph->id(item);} 1815 1857 1816 /// \brief Gives back the item by its id.1817 /// 1818 /// Gives back the item by its id.1858 /// \brief Gives back the \e item by its id. 1859 /// 1860 /// Gives back the \e item by its id. 1819 1861 Item operator()(int id) { return _graph->fromId(id, Item()); } 1820 1862 … … 1824 1866 public: 1825 1867 1826 /// \brief Th eclass represents the inverse of its owner (IdMap).1827 /// 1828 /// Th eclass represents the inverse of its owner (IdMap).1868 /// \brief This class represents the inverse of its owner (IdMap). 1869 /// 1870 /// This class represents the inverse of its owner (IdMap). 1829 1871 /// \see inverse() 1830 1872 class InverseMap { … … 1844 1886 /// 1845 1887 /// Gives back the given item from its id. 1846 ///1847 1888 Item operator[](int id) const { return _graph->fromId(id, Item());} 1848 1889 … … 1855 1896 /// Gives back the inverse of the IdMap. 1856 1897 InverseMap inverse() const { return InverseMap(*_graph);} 1857 1858 }; 1859 1860 1861 /// \brief General invertable graph-map type. 1862 1863 /// This type provides simple invertable graph-maps. 1864 /// The InvertableMap wraps an arbitrary ReadWriteMap 1898 }; 1899 1900 1901 /// \brief General invertable graph map type. 1902 1903 /// This class provides simple invertable graph maps. 1904 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" 1865 1905 /// and if a key is set to a new value then store it 1866 1906 /// in the inverse map. … … 1869 1909 /// with stl compatible forward iterator. 1870 1910 /// 1871 /// \tparam _Graph The graph type. 1872 /// \tparam _Item The item type of the graph. 1873 /// \tparam _Value The value type of the map. 1911 /// \tparam GR The graph type. 1912 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 1913 /// \c GR::Edge). 1914 /// \tparam V The value type of the map. 1874 1915 /// 1875 1916 /// \see IterableValueMap 1876 template <typename _Graph, typename _Item, typename _Value>1917 template <typename GR, typename K, typename V> 1877 1918 class InvertableMap 1878 : protected ItemSetTraits< _Graph, _Item>::template Map<_Value>::Type {1919 : protected ItemSetTraits<GR, K>::template Map<V>::Type { 1879 1920 private: 1880 1921 1881 typedef typename ItemSetTraits<_Graph, _Item>:: 1882 template Map<_Value>::Type Map; 1883 typedef _Graph Graph; 1884 1885 typedef std::map<_Value, _Item> Container; 1922 typedef typename ItemSetTraits<GR, K>:: 1923 template Map<V>::Type Map; 1924 1925 typedef std::map<V, K> Container; 1886 1926 Container _inv_map; 1887 1927 1888 1928 public: 1889 1929 1890 /// The key type of InvertableMap (Node, Arc, Edge). 1891 typedef typename Map::Key Key; 1892 /// The value type of the InvertableMap. 1893 typedef typename Map::Value Value; 1930 /// The graph type of InvertableMap. 1931 typedef GR Graph; 1932 /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). 1933 typedef K Item; 1934 /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). 1935 typedef K Key; 1936 /// The value type of InvertableMap. 1937 typedef V Value; 1894 1938 1895 1939 /// \brief Constructor. 1896 1940 /// 1897 /// Construct a new InvertableMap for the graph. 1898 /// 1941 /// Construct a new InvertableMap for the given graph. 1899 1942 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1900 1943 … … 1903 1946 /// This iterator is an stl compatible forward 1904 1947 /// iterator on the values of the map. The values can 1905 /// be accessed in the [beginValue, endValue) range. 1906 /// 1948 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1907 1949 class ValueIterator 1908 1950 : public std::iterator<std::forward_iterator_tag, Value> { … … 1936 1978 /// Returns an stl compatible iterator to the 1937 1979 /// first value of the map. The values of the 1938 /// map can be accessed in the [beginValue, endValue)1980 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 1939 1981 /// range. 1940 1982 ValueIterator beginValue() const { … … 1946 1988 /// Returns an stl compatible iterator after the 1947 1989 /// last value of the map. The values of the 1948 /// map can be accessed in the [beginValue, endValue)1990 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 1949 1991 /// range. 1950 1992 ValueIterator endValue() const { … … 1952 1994 } 1953 1995 1954 /// \brief The setter function of the map.1955 /// 1956 /// Sets the mapped value.1996 /// \brief Sets the value associated with the given key. 1997 /// 1998 /// Sets the value associated with the given key. 1957 1999 void set(const Key& key, const Value& val) { 1958 2000 Value oldval = Map::operator[](key); … … 1965 2007 } 1966 2008 1967 /// \brief The getter function of the map.1968 /// 1969 /// It gives back the value associated with thekey.2009 /// \brief Returns the value associated with the given key. 2010 /// 2011 /// Returns the value associated with the given key. 1970 2012 typename MapTraits<Map>::ConstReturnValue 1971 2013 operator[](const Key& key) const { … … 1983 2025 protected: 1984 2026 1985 /// \brief Erase the key from the map .1986 /// 1987 /// Erase the key to the map. It is called by the2027 /// \brief Erase the key from the map and the inverse map. 2028 /// 2029 /// Erase the key from the map and the inverse map. It is called by the 1988 2030 /// \c AlterationNotifier. 1989 2031 virtual void erase(const Key& key) { … … 1996 2038 } 1997 2039 1998 /// \brief Erase more keys from the map .1999 /// 2000 /// Erase more keys from the map . It is called by the2040 /// \brief Erase more keys from the map and the inverse map. 2041 /// 2042 /// Erase more keys from the map and the inverse map. It is called by the 2001 2043 /// \c AlterationNotifier. 2002 2044 virtual void erase(const std::vector<Key>& keys) { … … 2011 2053 } 2012 2054 2013 /// \brief Clear the keys from the map and inverse map.2014 /// 2015 /// Clear the keys from the map and inverse map. It is called by the2055 /// \brief Clear the keys from the map and the inverse map. 2056 /// 2057 /// Clear the keys from the map and the inverse map. It is called by the 2016 2058 /// \c AlterationNotifier. 2017 2059 virtual void clear() { … … 2025 2067 /// 2026 2068 /// The inverse of this map. The subscript operator of the map 2027 /// gives back always the item what was last assigned to the value.2069 /// gives back the item that was last assigned to the value. 2028 2070 class InverseMap { 2029 2071 public: 2030 /// \brief Constructor of the InverseMap.2072 /// \brief Constructor 2031 2073 /// 2032 2074 /// Constructor of the InverseMap. … … 2041 2083 /// \brief Subscript operator. 2042 2084 /// 2043 /// Subscript operator. It gives back alwaysthe item2044 /// what was last assigned to thevalue.2085 /// Subscript operator. It gives back the item 2086 /// that was last assigned to the given value. 2045 2087 Value operator[](const Key& key) const { 2046 2088 return _inverted(key); … … 2051 2093 }; 2052 2094 2053 /// \brief It gives back the just readableinverse map.2054 /// 2055 /// It gives back the just readableinverse map.2095 /// \brief It gives back the read-only inverse map. 2096 /// 2097 /// It gives back the read-only inverse map. 2056 2098 InverseMap inverse() const { 2057 2099 return InverseMap(*this); … … 2061 2103 2062 2104 /// \brief Provides a mutable, continuous and unique descriptor for each 2063 /// item in the graph. 2064 /// 2065 /// The DescriptorMap class provides a unique and continuous (but mutable) 2066 /// descriptor (id) for each item of the same type (e.g. node) in the 2067 /// graph. This id is <ul><li>\b unique: different items (nodes) get 2068 /// different ids <li>\b continuous: the range of the ids is the set of 2069 /// integers between 0 and \c n-1, where \c n is the number of the items of 2070 /// this type (e.g. nodes) (so the id of a node can change if you delete an 2071 /// other node, i.e. this id is mutable). </ul> This map can be inverted 2072 /// with its member class \c InverseMap, or with the \c operator() member. 2073 /// 2074 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. 2075 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 2076 /// Edge. 2077 template <typename _Graph, typename _Item> 2105 /// item in a graph. 2106 /// 2107 /// DescriptorMap provides a unique and continuous (but mutable) 2108 /// descriptor (id) for each item of the same type (\c Node, \c Arc or 2109 /// \c Edge) in a graph. This id is 2110 /// - \b unique: different items get different ids, 2111 /// - \b continuous: the range of the ids is the set of integers 2112 /// between 0 and \c n-1, where \c n is the number of the items of 2113 /// this type (\c Node, \c Arc or \c Edge). So the id of an item can 2114 /// change if you delete an other item of the same type, i.e. this 2115 /// id is mutable. 2116 /// 2117 /// Thus this id is not (necessarily) the same as what can get using 2118 /// the \c id() function of the graph or \ref IdMap. 2119 /// This map can be inverted with its member class \c InverseMap, 2120 /// or with the \c operator() member. 2121 /// 2122 /// \tparam GR The graph type. 2123 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2124 /// \c GR::Edge). 2125 /// 2126 /// \see IdMap 2127 template <typename GR, typename K> 2078 2128 class DescriptorMap 2079 : protected ItemSetTraits< _Graph, _Item>::template Map<int>::Type {2080 2081 typedef _Item Item;2082 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map; 2083 2084 public:2085 /// The graph class of DescriptorMap.2086 typedef _Graph Graph;2087 2088 /// The key type of DescriptorMap ( Node, Arc,Edge).2089 typedef typename Map::KeyKey;2129 : protected ItemSetTraits<GR, K>::template Map<int>::Type { 2130 2131 typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map; 2132 2133 public: 2134 /// The graph type of DescriptorMap. 2135 typedef GR Graph; 2136 /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). 2137 typedef K Item; 2138 /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). 2139 typedef K Key; 2090 2140 /// The value type of DescriptorMap. 2091 typedef typename Map::ValueValue;2141 typedef int Value; 2092 2142 2093 2143 /// \brief Constructor. 2094 2144 /// 2095 2145 /// Constructor for descriptor map. 2096 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {2146 explicit DescriptorMap(const Graph& gr) : Map(gr) { 2097 2147 Item it; 2098 2148 const typename Map::Notifier* nf = Map::notifier(); … … 2105 2155 protected: 2106 2156 2107 /// \brief Add a new key to the map.2157 /// \brief Adds a new key to the map. 2108 2158 /// 2109 2159 /// Add a new key to the map. It is called by the … … 2215 2265 2216 2266 public: 2267 2217 2268 /// \brief The inverse map type of DescriptorMap. 2218 2269 /// … … 2220 2271 class InverseMap { 2221 2272 public: 2222 /// \brief Constructor of the InverseMap.2273 /// \brief Constructor 2223 2274 /// 2224 2275 /// Constructor of the InverseMap. … … 2235 2286 /// 2236 2287 /// Subscript operator. It gives back the item 2237 /// that the descriptor belongs to currently.2288 /// that the descriptor currently belongs to. 2238 2289 Value operator[](const Key& key) const { 2239 2290 return _inverted(key); … … 2259 2310 }; 2260 2311 2261 /// \brief Returns the source of the given arc. 2262 /// 2263 /// The SourceMap gives back the source Node of the given arc. 2312 /// \brief Map of the source nodes of arcs in a digraph. 2313 /// 2314 /// SourceMap provides access for the source node of each arc in a digraph, 2315 /// which is returned by the \c source() function of the digraph. 2316 /// \tparam GR The digraph type. 2264 2317 /// \see TargetMap 2265 template <typename Digraph>2318 template <typename GR> 2266 2319 class SourceMap { 2267 2320 public: 2268 2321 2269 typedef typename Digraph::Node Value; 2270 typedef typename Digraph::Arc Key; 2322 ///\e 2323 typedef typename GR::Arc Key; 2324 ///\e 2325 typedef typename GR::Node Value; 2271 2326 2272 2327 /// \brief Constructor 2273 2328 /// 2274 /// Constructor 2329 /// Constructor. 2275 2330 /// \param digraph The digraph that the map belongs to. 2276 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} 2277 2278 /// \brief The subscript operator. 2279 /// 2280 /// The subscript operator. 2281 /// \param arc The arc 2282 /// \return The source of the arc 2331 explicit SourceMap(const GR& digraph) : _graph(digraph) {} 2332 2333 /// \brief Returns the source node of the given arc. 2334 /// 2335 /// Returns the source node of the given arc. 2283 2336 Value operator[](const Key& arc) const { 2284 return _ digraph.source(arc);2337 return _graph.source(arc); 2285 2338 } 2286 2339 2287 2340 private: 2288 const Digraph& _digraph;2341 const GR& _graph; 2289 2342 }; 2290 2343 … … 2293 2346 /// This function just returns an \c SourceMap class. 2294 2347 /// \relates SourceMap 2295 template <typename Digraph> 2296 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) { 2297 return SourceMap<Digraph>(digraph); 2298 } 2299 2300 /// \brief Returns the target of the given arc. 2301 /// 2302 /// The TargetMap gives back the target Node of the given arc. 2348 template <typename GR> 2349 inline SourceMap<GR> sourceMap(const GR& graph) { 2350 return SourceMap<GR>(graph); 2351 } 2352 2353 /// \brief Map of the target nodes of arcs in a digraph. 2354 /// 2355 /// TargetMap provides access for the target node of each arc in a digraph, 2356 /// which is returned by the \c target() function of the digraph. 2357 /// \tparam GR The digraph type. 2303 2358 /// \see SourceMap 2304 template <typename Digraph>2359 template <typename GR> 2305 2360 class TargetMap { 2306 2361 public: 2307 2362 2308 typedef typename Digraph::Node Value; 2309 typedef typename Digraph::Arc Key; 2363 ///\e 2364 typedef typename GR::Arc Key; 2365 ///\e 2366 typedef typename GR::Node Value; 2310 2367 2311 2368 /// \brief Constructor 2312 2369 /// 2313 /// Constructor 2370 /// Constructor. 2314 2371 /// \param digraph The digraph that the map belongs to. 2315 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} 2316 2317 /// \brief The subscript operator. 2318 /// 2319 /// The subscript operator. 2320 /// \param e The arc 2321 /// \return The target of the arc 2372 explicit TargetMap(const GR& digraph) : _graph(digraph) {} 2373 2374 /// \brief Returns the target node of the given arc. 2375 /// 2376 /// Returns the target node of the given arc. 2322 2377 Value operator[](const Key& e) const { 2323 return _ digraph.target(e);2378 return _graph.target(e); 2324 2379 } 2325 2380 2326 2381 private: 2327 const Digraph& _digraph;2382 const GR& _graph; 2328 2383 }; 2329 2384 … … 2332 2387 /// This function just returns a \c TargetMap class. 2333 2388 /// \relates TargetMap 2334 template <typename Digraph> 2335 inline TargetMap<Digraph> targetMap(const Digraph& digraph) { 2336 return TargetMap<Digraph>(digraph); 2337 } 2338 2339 /// \brief Returns the "forward" directed arc view of an edge. 2340 /// 2341 /// Returns the "forward" directed arc view of an edge. 2389 template <typename GR> 2390 inline TargetMap<GR> targetMap(const GR& graph) { 2391 return TargetMap<GR>(graph); 2392 } 2393 2394 /// \brief Map of the "forward" directed arc view of edges in a graph. 2395 /// 2396 /// ForwardMap provides access for the "forward" directed arc view of 2397 /// each edge in a graph, which is returned by the \c direct() function 2398 /// of the graph with \c true parameter. 2399 /// \tparam GR The graph type. 2342 2400 /// \see BackwardMap 2343 template <typename G raph>2401 template <typename GR> 2344 2402 class ForwardMap { 2345 2403 public: 2346 2404 2347 typedef typename G raph::Arc Value;2348 typedef typename G raph::Edge Key;2405 typedef typename GR::Arc Value; 2406 typedef typename GR::Edge Key; 2349 2407 2350 2408 /// \brief Constructor 2351 2409 /// 2352 /// Constructor 2410 /// Constructor. 2353 2411 /// \param graph The graph that the map belongs to. 2354 explicit ForwardMap(const Graph& graph) : _graph(graph) {} 2355 2356 /// \brief The subscript operator. 2357 /// 2358 /// The subscript operator. 2359 /// \param key An edge 2360 /// \return The "forward" directed arc view of edge 2412 explicit ForwardMap(const GR& graph) : _graph(graph) {} 2413 2414 /// \brief Returns the "forward" directed arc view of the given edge. 2415 /// 2416 /// Returns the "forward" directed arc view of the given edge. 2361 2417 Value operator[](const Key& key) const { 2362 2418 return _graph.direct(key, true); … … 2364 2420 2365 2421 private: 2366 const G raph& _graph;2422 const GR& _graph; 2367 2423 }; 2368 2424 … … 2371 2427 /// This function just returns an \c ForwardMap class. 2372 2428 /// \relates ForwardMap 2373 template <typename Graph> 2374 inline ForwardMap<Graph> forwardMap(const Graph& graph) { 2375 return ForwardMap<Graph>(graph); 2376 } 2377 2378 /// \brief Returns the "backward" directed arc view of an edge. 2379 /// 2380 /// Returns the "backward" directed arc view of an edge. 2429 template <typename GR> 2430 inline ForwardMap<GR> forwardMap(const GR& graph) { 2431 return ForwardMap<GR>(graph); 2432 } 2433 2434 /// \brief Map of the "backward" directed arc view of edges in a graph. 2435 /// 2436 /// BackwardMap provides access for the "backward" directed arc view of 2437 /// each edge in a graph, which is returned by the \c direct() function 2438 /// of the graph with \c false parameter. 2439 /// \tparam GR The graph type. 2381 2440 /// \see ForwardMap 2382 template <typename G raph>2441 template <typename GR> 2383 2442 class BackwardMap { 2384 2443 public: 2385 2444 2386 typedef typename G raph::Arc Value;2387 typedef typename G raph::Edge Key;2445 typedef typename GR::Arc Value; 2446 typedef typename GR::Edge Key; 2388 2447 2389 2448 /// \brief Constructor 2390 2449 /// 2391 /// Constructor 2450 /// Constructor. 2392 2451 /// \param graph The graph that the map belongs to. 2393 explicit BackwardMap(const Graph& graph) : _graph(graph) {} 2394 2395 /// \brief The subscript operator. 2396 /// 2397 /// The subscript operator. 2398 /// \param key An edge 2399 /// \return The "backward" directed arc view of edge 2452 explicit BackwardMap(const GR& graph) : _graph(graph) {} 2453 2454 /// \brief Returns the "backward" directed arc view of the given edge. 2455 /// 2456 /// Returns the "backward" directed arc view of the given edge. 2400 2457 Value operator[](const Key& key) const { 2401 2458 return _graph.direct(key, false); … … 2403 2460 2404 2461 private: 2405 const G raph& _graph;2462 const GR& _graph; 2406 2463 }; 2407 2464 … … 2410 2467 /// This function just returns a \c BackwardMap class. 2411 2468 /// \relates BackwardMap 2412 template <typename Graph> 2413 inline BackwardMap<Graph> backwardMap(const Graph& graph) { 2414 return BackwardMap<Graph>(graph); 2415 } 2416 2417 /// \brief Potential difference map 2418 /// 2419 /// If there is an potential map on the nodes then we 2420 /// can get an arc map as we get the substraction of the 2421 /// values of the target and source. 2422 template <typename Digraph, typename NodeMap> 2423 class PotentialDifferenceMap { 2424 public: 2425 typedef typename Digraph::Arc Key; 2426 typedef typename NodeMap::Value Value; 2427 2428 /// \brief Constructor 2429 /// 2430 /// Contructor of the map 2431 explicit PotentialDifferenceMap(const Digraph& digraph, 2432 const NodeMap& potential) 2433 : _digraph(digraph), _potential(potential) {} 2434 2435 /// \brief Const subscription operator 2436 /// 2437 /// Const subscription operator 2438 Value operator[](const Key& arc) const { 2439 return _potential[_digraph.target(arc)] - 2440 _potential[_digraph.source(arc)]; 2441 } 2442 2443 private: 2444 const Digraph& _digraph; 2445 const NodeMap& _potential; 2446 }; 2447 2448 /// \brief Returns a PotentialDifferenceMap. 2449 /// 2450 /// This function just returns a PotentialDifferenceMap. 2451 /// \relates PotentialDifferenceMap 2452 template <typename Digraph, typename NodeMap> 2453 PotentialDifferenceMap<Digraph, NodeMap> 2454 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { 2455 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential); 2456 } 2457 2458 /// \brief Map of the node in-degrees. 2469 template <typename GR> 2470 inline BackwardMap<GR> backwardMap(const GR& graph) { 2471 return BackwardMap<GR>(graph); 2472 } 2473 2474 /// \brief Map of the in-degrees of nodes in a digraph. 2459 2475 /// 2460 2476 /// This map returns the in-degree of a node. Once it is constructed, 2461 /// the degrees are stored in a standard NodeMap, so each query is done2477 /// the degrees are stored in a standard \c NodeMap, so each query is done 2462 2478 /// in constant time. On the other hand, the values are updated automatically 2463 2479 /// whenever the digraph changes. 2464 2480 /// 2465 /// \warning Besides addNode() and addArc(), a digraph structure may provide 2466 /// alternative ways to modify the digraph. The correct behavior of InDegMap 2467 /// is not guarantied if these additional features are used. For example 2468 /// the functions \ref ListDigraph::changeSource() "changeSource()", 2481 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2482 /// may provide alternative ways to modify the digraph. 2483 /// The correct behavior of InDegMap is not guarantied if these additional 2484 /// features are used. For example the functions 2485 /// \ref ListDigraph::changeSource() "changeSource()", 2469 2486 /// \ref ListDigraph::changeTarget() "changeTarget()" and 2470 2487 /// \ref ListDigraph::reverseArc() "reverseArc()" … … 2472 2489 /// 2473 2490 /// \sa OutDegMap 2474 2475 template <typename _Digraph> 2491 template <typename GR> 2476 2492 class InDegMap 2477 : protected ItemSetTraits< _Digraph, typename _Digraph::Arc>2493 : protected ItemSetTraits<GR, typename GR::Arc> 2478 2494 ::ItemNotifier::ObserverBase { 2479 2495 2480 2496 public: 2481 2482 typedef _Digraph Digraph; 2497 2498 /// The digraph type 2499 typedef GR Digraph; 2500 /// The key type 2501 typedef typename Digraph::Node Key; 2502 /// The value type 2483 2503 typedef int Value; 2484 typedef typename Digraph::Node Key;2485 2504 2486 2505 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> … … 2524 2543 /// \brief Constructor. 2525 2544 /// 2526 /// Constructor for creating in-degree map.2527 explicit InDegMap(const Digraph& digraph)2528 : _digraph( digraph), _deg(digraph) {2545 /// Constructor for creating an in-degree map. 2546 explicit InDegMap(const Digraph& graph) 2547 : _digraph(graph), _deg(graph) { 2529 2548 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2530 2549 … … 2534 2553 } 2535 2554 2555 /// \brief Gives back the in-degree of a Node. 2556 /// 2536 2557 /// Gives back the in-degree of a Node. 2537 2558 int operator[](const Key& key) const { … … 2580 2601 }; 2581 2602 2582 /// \brief Map of the node out-degrees.2603 /// \brief Map of the out-degrees of nodes in a digraph. 2583 2604 /// 2584 2605 /// This map returns the out-degree of a node. Once it is constructed, 2585 /// the degrees are stored in a standard NodeMap, so each query is done2606 /// the degrees are stored in a standard \c NodeMap, so each query is done 2586 2607 /// in constant time. On the other hand, the values are updated automatically 2587 2608 /// whenever the digraph changes. 2588 2609 /// 2589 /// \warning Besides addNode() and addArc(), a digraph structure may provide 2590 /// alternative ways to modify the digraph. The correct behavior of OutDegMap 2591 /// is not guarantied if these additional features are used. For example 2592 /// the functions \ref ListDigraph::changeSource() "changeSource()", 2610 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2611 /// may provide alternative ways to modify the digraph. 2612 /// The correct behavior of OutDegMap is not guarantied if these additional 2613 /// features are used. For example the functions 2614 /// \ref ListDigraph::changeSource() "changeSource()", 2593 2615 /// \ref ListDigraph::changeTarget() "changeTarget()" and 2594 2616 /// \ref ListDigraph::reverseArc() "reverseArc()" … … 2596 2618 /// 2597 2619 /// \sa InDegMap 2598 2599 template <typename _Digraph> 2620 template <typename GR> 2600 2621 class OutDegMap 2601 : protected ItemSetTraits< _Digraph, typename _Digraph::Arc>2622 : protected ItemSetTraits<GR, typename GR::Arc> 2602 2623 ::ItemNotifier::ObserverBase { 2603 2624 2604 2625 public: 2605 2626 2606 typedef _Digraph Digraph; 2627 /// The digraph type 2628 typedef GR Digraph; 2629 /// The key type 2630 typedef typename Digraph::Node Key; 2631 /// The value type 2607 2632 typedef int Value; 2608 typedef typename Digraph::Node Key;2609 2633 2610 2634 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> … … 2646 2670 /// \brief Constructor. 2647 2671 /// 2648 /// Constructor for creating out-degree map.2649 explicit OutDegMap(const Digraph& digraph)2650 : _digraph( digraph), _deg(digraph) {2672 /// Constructor for creating an out-degree map. 2673 explicit OutDegMap(const Digraph& graph) 2674 : _digraph(graph), _deg(graph) { 2651 2675 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2652 2676 … … 2656 2680 } 2657 2681 2682 /// \brief Gives back the out-degree of a Node. 2683 /// 2658 2684 /// Gives back the out-degree of a Node. 2659 2685 int operator[](const Key& key) const { … … 2702 2728 }; 2703 2729 2730 /// \brief Potential difference map 2731 /// 2732 /// PotentialMap returns the difference between the potentials of the 2733 /// source and target nodes of each arc in a digraph, i.e. it returns 2734 /// \code 2735 /// potential[gr.target(arc)] - potential[gr.source(arc)]. 2736 /// \endcode 2737 /// \tparam GR The digraph type. 2738 /// \tparam POT A node map storing the potentials. 2739 template <typename GR, typename POT> 2740 class PotentialDifferenceMap { 2741 public: 2742 /// Key type 2743 typedef typename GR::Arc Key; 2744 /// Value type 2745 typedef typename POT::Value Value; 2746 2747 /// \brief Constructor 2748 /// 2749 /// Contructor of the map. 2750 explicit PotentialDifferenceMap(const GR& gr, 2751 const POT& potential) 2752 : _digraph(gr), _potential(potential) {} 2753 2754 /// \brief Returns the potential difference for the given arc. 2755 /// 2756 /// Returns the potential difference for the given arc, i.e. 2757 /// \code 2758 /// potential[gr.target(arc)] - potential[gr.source(arc)]. 2759 /// \endcode 2760 Value operator[](const Key& arc) const { 2761 return _potential[_digraph.target(arc)] - 2762 _potential[_digraph.source(arc)]; 2763 } 2764 2765 private: 2766 const GR& _digraph; 2767 const POT& _potential; 2768 }; 2769 2770 /// \brief Returns a PotentialDifferenceMap. 2771 /// 2772 /// This function just returns a PotentialDifferenceMap. 2773 /// \relates PotentialDifferenceMap 2774 template <typename GR, typename POT> 2775 PotentialDifferenceMap<GR, POT> 2776 potentialDifferenceMap(const GR& gr, const POT& potential) { 2777 return PotentialDifferenceMap<GR, POT>(gr, potential); 2778 } 2779 2704 2780 /// @} 2705 2781 } -
lemon/max_matching.h
r440 r550 56 56 /// decomposition() after running the algorithm. 57 57 /// 58 /// \param _GraphThe graph type the algorithm runs on.59 template <typename _Graph>58 /// \param GR The graph type the algorithm runs on. 59 template <typename GR> 60 60 class MaxMatching { 61 61 public: 62 62 63 typedef _GraphGraph;63 typedef GR Graph; 64 64 typedef typename Graph::template NodeMap<typename Graph::Arc> 65 65 MatchingMap; … … 464 464 /// map must have the property that there are no two incident edges 465 465 /// with true value, ie. it contains a matching. 466 /// \return %True if the map contains a matching.466 /// \return \c true if the map contains a matching. 467 467 template <typename MatchingMap> 468 468 bool matchingInit(const MatchingMap& matching) { … … 614 614 /// maximum weighted matching algorithm. The implementation is based 615 615 /// on extensive use of priority queues and provides 616 /// \f$O(nm\log (n))\f$ time complexity.616 /// \f$O(nm\log n)\f$ time complexity. 617 617 /// 618 618 /// The maximum weighted matching problem is to find undirected … … 648 648 /// of a blossom. If the value type is integral then the dual 649 649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". 650 template <typename _Graph,651 typename _WeightMap = typename _Graph::template EdgeMap<int> >650 template <typename GR, 651 typename WM = typename GR::template EdgeMap<int> > 652 652 class MaxWeightedMatching { 653 653 public: 654 654 655 typedef _Graph Graph; 656 typedef _WeightMap WeightMap; 655 ///\e 656 typedef GR Graph; 657 ///\e 658 typedef WM WeightMap; 659 ///\e 657 660 typedef typename WeightMap::Value Value; 658 661 … … 1958 1961 /// maximum weighted perfect matching algorithm. The implementation 1959 1962 /// is based on extensive use of priority queues and provides 1960 /// \f$O(nm\log (n))\f$ time complexity.1963 /// \f$O(nm\log n)\f$ time complexity. 1961 1964 /// 1962 1965 /// The maximum weighted matching problem is to find undirected … … 1991 1994 /// of a blossom. If the value type is integral then the dual 1992 1995 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". 1993 template <typename _Graph,1994 typename _WeightMap = typename _Graph::template EdgeMap<int> >1996 template <typename GR, 1997 typename WM = typename GR::template EdgeMap<int> > 1995 1998 class MaxWeightedPerfectMatching { 1996 1999 public: 1997 2000 1998 typedef _GraphGraph;1999 typedef _WeightMapWeightMap;2001 typedef GR Graph; 2002 typedef WM WeightMap; 2000 2003 typedef typename WeightMap::Value Value; 2001 2004 -
lemon/min_cost_arborescence.h
r512 r550 36 36 /// 37 37 /// Default traits class for MinCostArborescence class. 38 /// \param _DigraphDigraph type.39 /// \param _CostMapType of cost map.40 template <class _Digraph, class _CostMap>38 /// \param GR Digraph type. 39 /// \param CM Type of cost map. 40 template <class GR, class CM> 41 41 struct MinCostArborescenceDefaultTraits{ 42 42 43 43 /// \brief The digraph type the algorithm runs on. 44 typedef _DigraphDigraph;44 typedef GR Digraph; 45 45 46 46 /// \brief The type of the map that stores the arc costs. … … 48 48 /// The type of the map that stores the arc costs. 49 49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 50 typedef _CostMapCostMap;50 typedef CM CostMap; 51 51 52 52 /// \brief The value type of the costs. … … 64 64 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; 65 65 66 /// \brief Instantiates a ArborescenceMap.67 /// 68 /// This function instantiates a \ refArborescenceMap.66 /// \brief Instantiates a \c ArborescenceMap. 67 /// 68 /// This function instantiates a \c ArborescenceMap. 69 69 /// \param digraph is the graph, to which we would like to 70 /// calculate the ArborescenceMap.70 /// calculate the \c ArborescenceMap. 71 71 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ 72 72 return new ArborescenceMap(digraph); 73 73 } 74 74 75 /// \brief The type of the PredMap76 /// 77 /// The type of the PredMap. It is a node map with an arc value type.75 /// \brief The type of the \c PredMap 76 /// 77 /// The type of the \c PredMap. It is a node map with an arc value type. 78 78 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 79 79 80 /// \brief Instantiates a PredMap.81 /// 82 /// This function instantiates a \ refPredMap.83 /// \param _digraph is the digraph,to which we would like to define the84 /// PredMap.80 /// \brief Instantiates a \c PredMap. 81 /// 82 /// This function instantiates a \c PredMap. 83 /// \param digraph The digraph to which we would like to define the 84 /// \c PredMap. 85 85 static PredMap *createPredMap(const Digraph &digraph){ 86 86 return new PredMap(digraph); … … 99 99 /// the minimum cost subgraph which are union of arborescences with the 100 100 /// given sources and spans all the nodes which are reachable from the 101 /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.101 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). 102 102 /// 103 103 /// The algorithm provides also an optimal dual solution, therefore 104 104 /// the optimality of the solution can be checked. 105 105 /// 106 /// \param _DigraphThe digraph type the algorithm runs on. The default value106 /// \param GR The digraph type the algorithm runs on. The default value 107 107 /// is \ref ListDigraph. 108 /// \param _CostMapThis read-only ArcMap determines the costs of the108 /// \param CM This read-only ArcMap determines the costs of the 109 109 /// arcs. It is read once for each arc, so the map may involve in 110 110 /// relatively time consuming process to compute the arc cost if 111 111 /// it is necessary. The default map type is \ref 112 112 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 113 /// \param _TraitsTraits class to set various data types used113 /// \param TR Traits class to set various data types used 114 114 /// by the algorithm. The default traits class is 115 115 /// \ref MinCostArborescenceDefaultTraits 116 /// "MinCostArborescenceDefaultTraits< _Digraph, _CostMap>". See \ref116 /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref 117 117 /// MinCostArborescenceDefaultTraits for the documentation of a 118 118 /// MinCostArborescence traits class. 119 ///120 /// \author Balazs Dezso121 119 #ifndef DOXYGEN 122 template <typename _Digraph= ListDigraph,123 typename _CostMap = typename _Digraph::template ArcMap<int>,124 typename _Traits=125 MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >120 template <typename GR = ListDigraph, 121 typename CM = typename GR::template ArcMap<int>, 122 typename TR = 123 MinCostArborescenceDefaultTraits<GR, CM> > 126 124 #else 127 template <typename _Digraph, typename _CostMap, typedef _Traits>125 template <typename GR, typename CM, typedef TR> 128 126 #endif 129 127 class MinCostArborescence { … … 131 129 132 130 /// The traits. 133 typedef _TraitsTraits;131 typedef TR Traits; 134 132 /// The type of the underlying digraph. 135 133 typedef typename Traits::Digraph Digraph; … … 441 439 /// \brief Constructor. 442 440 /// 443 /// \param _digraph The digraph the algorithm will run on.444 /// \param _cost The cost map used by the algorithm.441 /// \param digraph The digraph the algorithm will run on. 442 /// \param cost The cost map used by the algorithm. 445 443 MinCostArborescence(const Digraph& digraph, const CostMap& cost) 446 444 : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false), … … 457 455 /// 458 456 /// Sets the arborescence map. 459 /// \return \c (*this)457 /// \return <tt>(*this)</tt> 460 458 MinCostArborescence& arborescenceMap(ArborescenceMap& m) { 461 459 if (local_arborescence) { … … 470 468 /// 471 469 /// Sets the arborescence map. 472 /// \return \c (*this)470 /// \return <tt>(*this)</tt> 473 471 MinCostArborescence& predMap(PredMap& m) { 474 472 if (local_pred) { -
lemon/path.h
r500 r550 41 41 /// 42 42 /// A structure for representing directed path in a digraph. 43 /// \tparam _DigraphThe digraph type in which the path is.43 /// \tparam GR The digraph type in which the path is. 44 44 /// 45 45 /// In a sense, the path can be treated as a list of arcs. The … … 53 53 /// implementation uses two vectors for storing the front and back 54 54 /// insertions. 55 template <typename _Digraph>55 template <typename GR> 56 56 class Path { 57 57 public: 58 58 59 typedef _DigraphDigraph;59 typedef GR Digraph; 60 60 typedef typename Digraph::Arc Arc; 61 61 … … 138 138 /// \brief The nth arc. 139 139 /// 140 /// \pre n is in the [0..length() - 1] range140 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 141 141 const Arc& nth(int n) const { 142 142 return n < int(head.size()) ? *(head.rbegin() + n) : … … 146 146 /// \brief Initialize arc iterator to point to the nth arc 147 147 /// 148 /// \pre n is in the [0..length() - 1] range148 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 149 149 ArcIt nthIt(int n) const { 150 150 return ArcIt(*this, n); … … 229 229 /// 230 230 /// A structure for representing directed path in a digraph. 231 /// \tparam _DigraphThe digraph type in which the path is.231 /// \tparam GR The digraph type in which the path is. 232 232 /// 233 233 /// In a sense, the path can be treated as a list of arcs. The … … 241 241 /// then the \c Path type because it use just one vector for the 242 242 /// arcs. 243 template <typename _Digraph>243 template <typename GR> 244 244 class SimplePath { 245 245 public: 246 246 247 typedef _DigraphDigraph;247 typedef GR Digraph; 248 248 typedef typename Digraph::Arc Arc; 249 249 … … 330 330 /// \brief The nth arc. 331 331 /// 332 /// \pre n is in the [0..length() - 1] range332 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 333 333 const Arc& nth(int n) const { 334 334 return data[n]; … … 393 393 /// 394 394 /// A structure for representing directed path in a digraph. 395 /// \tparam _DigraphThe digraph type in which the path is.395 /// \tparam GR The digraph type in which the path is. 396 396 /// 397 397 /// In a sense, the path can be treated as a list of arcs. The … … 405 405 /// time. The front and back insertion and erasure is O(1) time 406 406 /// and it can be splited and spliced in O(1) time. 407 template <typename _Digraph>407 template <typename GR> 408 408 class ListPath { 409 409 public: 410 410 411 typedef _DigraphDigraph;411 typedef GR Digraph; 412 412 typedef typename Digraph::Arc Arc; 413 413 … … 508 508 /// 509 509 /// This function looks for the nth arc in O(n) time. 510 /// \pre n is in the [0..length() - 1] range510 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 511 511 const Arc& nth(int n) const { 512 512 Node *node = first; … … 733 733 /// 734 734 /// A structure for representing directed path in a digraph. 735 /// \tparam _DigraphThe digraph type in which the path is.735 /// \tparam GR The digraph type in which the path is. 736 736 /// 737 737 /// In a sense, the path can be treated as a list of arcs. The … … 747 747 /// it is intented to be 748 748 /// used when you want to store a large number of paths. 749 template <typename _Digraph>749 template <typename GR> 750 750 class StaticPath { 751 751 public: 752 752 753 typedef _DigraphDigraph;753 typedef GR Digraph; 754 754 typedef typename Digraph::Arc Arc; 755 755 … … 834 834 /// \brief The nth arc. 835 835 /// 836 /// \pre n is in the [0..length() - 1] range836 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 837 837 const Arc& nth(int n) const { 838 838 return arcs[n]; -
lemon/preflow.h
r519 r550 33 33 /// Default traits class of Preflow class. 34 34 /// \tparam GR Digraph type. 35 /// \tparam C MCapacity map type.36 template <typename GR, typename C M>35 /// \tparam CAP Capacity map type. 36 template <typename GR, typename CAP> 37 37 struct PreflowDefaultTraits { 38 38 … … 44 44 /// The type of the map that stores the arc capacities. 45 45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 46 typedef C MCapacityMap;46 typedef CAP CapacityMap; 47 47 48 48 /// \brief The type of the flow values. … … 95 95 /// 96 96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 97 /// \e push-relabel algorithm producing a flow of maximum value in a 98 /// digraph. The preflow algorithms are the fastest known maximum 97 /// \e push-relabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 99 /// The preflow algorithms are the fastest known maximum 99 100 /// flow algorithms. The current implementation use a mixture of the 100 101 /// \e "highest label" and the \e "bound decrease" heuristics. … … 106 107 /// 107 108 /// \tparam GR The type of the digraph the algorithm runs on. 108 /// \tparam C MThe type of the capacity map. The default map109 /// \tparam CAP The type of the capacity map. The default map 109 110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 110 111 #ifdef DOXYGEN 111 template <typename GR, typename C M, typename TR>112 template <typename GR, typename CAP, typename TR> 112 113 #else 113 114 template <typename GR, 114 typename C M= typename GR::template ArcMap<int>,115 typename TR = PreflowDefaultTraits<GR, C M> >115 typename CAP = typename GR::template ArcMap<int>, 116 typename TR = PreflowDefaultTraits<GR, CAP> > 116 117 #endif 117 118 class Preflow { … … 195 196 ///@{ 196 197 197 template <typename _FlowMap>198 template <typename T> 198 199 struct SetFlowMapTraits : public Traits { 199 typedef _FlowMapFlowMap;200 typedef T FlowMap; 200 201 static FlowMap *createFlowMap(const Digraph&) { 201 202 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 209 210 /// \ref named-templ-param "Named parameter" for setting FlowMap 210 211 /// type. 211 template <typename _FlowMap>212 template <typename T> 212 213 struct SetFlowMap 213 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits< _FlowMap> > {214 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > { 214 215 typedef Preflow<Digraph, CapacityMap, 215 SetFlowMapTraits< _FlowMap> > Create;216 SetFlowMapTraits<T> > Create; 216 217 }; 217 218 218 template <typename _Elevator>219 template <typename T> 219 220 struct SetElevatorTraits : public Traits { 220 typedef _ElevatorElevator;221 typedef T Elevator; 221 222 static Elevator *createElevator(const Digraph&, int) { 222 223 LEMON_ASSERT(false, "Elevator is not initialized"); … … 234 235 /// \ref run() or \ref init(). 235 236 /// \sa SetStandardElevator 236 template <typename _Elevator>237 template <typename T> 237 238 struct SetElevator 238 : public Preflow<Digraph, CapacityMap, SetElevatorTraits< _Elevator> > {239 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > { 239 240 typedef Preflow<Digraph, CapacityMap, 240 SetElevatorTraits< _Elevator> > Create;241 SetElevatorTraits<T> > Create; 241 242 }; 242 243 243 template <typename _Elevator>244 template <typename T> 244 245 struct SetStandardElevatorTraits : public Traits { 245 typedef _ElevatorElevator;246 typedef T Elevator; 246 247 static Elevator *createElevator(const Digraph& digraph, int max_level) { 247 248 return new Elevator(digraph, max_level); … … 261 262 /// before calling \ref run() or \ref init(). 262 263 /// \sa SetElevator 263 template <typename _Elevator>264 template <typename T> 264 265 struct SetStandardElevator 265 266 : public Preflow<Digraph, CapacityMap, 266 SetStandardElevatorTraits< _Elevator> > {267 SetStandardElevatorTraits<T> > { 267 268 typedef Preflow<Digraph, CapacityMap, 268 SetStandardElevatorTraits< _Elevator> > Create;269 SetStandardElevatorTraits<T> > Create; 269 270 }; 270 271 … … 947 948 /// 948 949 /// \note This function calls \ref minCut() for each node, so it runs in 949 /// \f$O(n)\f$time.950 /// O(n) time. 950 951 /// 951 952 /// \pre Either \ref run() or \ref init() must be called before -
lemon/radix_sort.h
r444 r550 206 206 /// 207 207 /// This is a special quick sort algorithm where the pivot 208 /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.209 /// Therefore, the time complexity of the210 /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,211 /// additional space, where \c c is the maximal value and \c n is the212 /// number of the items in the container.208 /// values to split the items are choosen to be 2<sup>k</sup> 209 /// for each \c k. 210 /// Therefore, the time complexity of the algorithm is O(log(c)*n) and 211 /// it uses O(log(c)) additional space, where \c c is the maximal value 212 /// and \c n is the number of the items in the container. 213 213 /// 214 214 /// \param first The begin of the given range. … … 431 431 /// byte-by-byte. First, it counts how many times a byte value occurs 432 432 /// in the container, then it copies the corresponding items to 433 /// another container in asceding order in \cO(n) time.434 /// 435 /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$and436 /// it uses \f$ O(n) \f$,additional space, where \c c is the433 /// another container in asceding order in O(n) time. 434 /// 435 /// The time complexity of the algorithm is O(log(c)*n) and 436 /// it uses O(n) additional space, where \c c is the 437 437 /// maximal value and \c n is the number of the items in the 438 438 /// container. -
lemon/random.h
r500 r550 604 604 /// function with the <tt>/dev/urandom</tt> file. If it does not success, 605 605 /// it uses the \c seedFromTime(). 606 /// \return Currently always true.606 /// \return Currently always \c true. 607 607 bool seed() { 608 608 #ifndef WIN32 … … 625 625 /// \param file The source file 626 626 /// \param offset The offset, from the file read. 627 /// \return True when the seeding successes.627 /// \return \c true when the seeding successes. 628 628 #ifndef WIN32 629 629 bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0) … … 646 646 /// current process id and the current time for initialize the 647 647 /// random sequence. 648 /// \return Currently always true.648 /// \return Currently always \c true. 649 649 bool seedFromTime() { 650 650 #ifndef WIN32 -
lemon/smart_graph.h
r440 r550 226 226 ///Add a new node to the digraph. 227 227 228 /// \return the new node.229 /// 228 /// Add a new node to the digraph. 229 /// \return The new node. 230 230 Node addNode() { return Parent::addNode(); } 231 231 … … 234 234 ///Add a new arc to the digraph with source node \c s 235 235 ///and target node \c t. 236 ///\return the new arc.236 ///\return The new arc. 237 237 Arc addArc(const Node& s, const Node& t) { 238 238 return Parent::addArc(s, t); … … 667 667 ///Add a new node to the graph. 668 668 669 /// \return the new node.670 /// 669 /// Add a new node to the graph. 670 /// \return The new node. 671 671 Node addNode() { return Parent::addNode(); } 672 672 … … 675 675 ///Add a new edge to the graph with node \c s 676 676 ///and \c t. 677 ///\return the new edge.677 ///\return The new edge. 678 678 Edge addEdge(const Node& s, const Node& t) { 679 679 return Parent::addEdge(s, t); -
lemon/suurballe.h
r503 r550 46 46 /// \ref CapacityScaling "successive shortest path" algorithm. 47 47 /// 48 /// \tparam DigraphThe digraph type the algorithm runs on.48 /// \tparam GR The digraph type the algorithm runs on. 49 49 /// The default value is \c ListDigraph. 50 /// \tparam L engthMapThe type of the length (cost) map.50 /// \tparam LEN The type of the length (cost) map. 51 51 /// The default value is <tt>Digraph::ArcMap<int></tt>. 52 52 /// … … 56 56 /// with \ref SplitNodes. 57 57 #ifdef DOXYGEN 58 template <typename Digraph, typename LengthMap>58 template <typename GR, typename LEN> 59 59 #else 60 template < typename Digraph= ListDigraph,61 typename L engthMap = typename Digraph::template ArcMap<int> >60 template < typename GR = ListDigraph, 61 typename LEN = typename GR::template ArcMap<int> > 62 62 #endif 63 63 class Suurballe 64 64 { 65 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 66 65 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 66 67 typedef ConstMap<Arc, int> ConstArcMap; 68 typedef typename GR::template NodeMap<Arc> PredMap; 69 70 public: 71 72 /// The type of the digraph the algorithm runs on. 73 typedef GR Digraph; 74 /// The type of the length map. 75 typedef LEN LengthMap; 76 /// The type of the lengths. 67 77 typedef typename LengthMap::Value Length; 68 typedef ConstMap<Arc, int> ConstArcMap;69 typedef typename Digraph::template NodeMap<Arc> PredMap;70 71 public:72 73 78 /// The type of the flow map. 74 79 typedef typename Digraph::template ArcMap<int> FlowMap; … … 257 262 /// the found arc-disjoint paths. 258 263 /// 259 /// \return \c (*this)264 /// \return <tt>(*this)</tt> 260 265 Suurballe& flowMap(FlowMap &map) { 261 266 if (_local_flow) { … … 274 279 /// minimum cost flow problem. 275 280 /// 276 /// \return \c (*this)281 /// \return <tt>(*this)</tt> 277 282 Suurballe& potentialMap(PotentialMap &map) { 278 283 if (_local_potential) { … … 459 464 /// 460 465 /// This function returns the total length (cost) of the found paths 461 /// (flow). The complexity of the function is \f$ O(e) \f$.466 /// (flow). The complexity of the function is O(e). 462 467 /// 463 468 /// \pre \ref run() or \ref findFlow() must be called before using -
lemon/unionfind.h
r440 r550 52 52 /// \pre You need to add all the elements by the \ref insert() 53 53 /// method. 54 template <typename _ItemIntMap>54 template <typename IM> 55 55 class UnionFind { 56 56 public: 57 57 58 typedef _ItemIntMap ItemIntMap; 58 ///\e 59 typedef IM ItemIntMap; 60 ///\e 59 61 typedef typename ItemIntMap::Key Item; 60 62 … … 171 173 /// method. 172 174 /// 173 template <typename _ItemIntMap>175 template <typename IM> 174 176 class UnionFindEnum { 175 177 public: 176 178 177 typedef _ItemIntMap ItemIntMap; 179 ///\e 180 typedef IM ItemIntMap; 181 ///\e 178 182 typedef typename ItemIntMap::Key Item; 179 183 … … 628 632 /// \pre You need to add all the elements by the \ref insert() 629 633 /// method. 630 template <typename _ItemIntMap>634 template <typename IM> 631 635 class ExtendFindEnum { 632 636 public: 633 637 634 typedef _ItemIntMap ItemIntMap; 638 ///\e 639 typedef IM ItemIntMap; 640 ///\e 635 641 typedef typename ItemIntMap::Key Item; 636 642 … … 949 955 /// \pre You need to add all the elements by the \ref insert() 950 956 /// method. 951 /// 952 template <typename _Value, typename _ItemIntMap, 953 typename _Comp = std::less<_Value> > 957 template <typename V, typename IM, typename Comp = std::less<V> > 954 958 class HeapUnionFind { 955 959 public: 956 960 957 typedef _Value Value; 958 typedef typename _ItemIntMap::Key Item; 959 960 typedef _ItemIntMap ItemIntMap; 961 962 typedef _Comp Comp; 961 ///\e 962 typedef V Value; 963 ///\e 964 typedef typename IM::Key Item; 965 ///\e 966 typedef IM ItemIntMap; 967 ///\e 968 typedef Comp Compare; 963 969 964 970 private: … … 1602 1608 /// \brief Gives back the priority of the current item. 1603 1609 /// 1604 /// \returnGives back the priority of the current item.1610 /// Gives back the priority of the current item. 1605 1611 const Value& operator[](const Item& item) const { 1606 1612 return nodes[index[item]].prio; … … 1647 1653 /// \brief Gives back the minimum priority of the class. 1648 1654 /// 1649 /// \returnGives back the minimum priority of the class.1655 /// Gives back the minimum priority of the class. 1650 1656 const Value& classPrio(int cls) const { 1651 1657 return nodes[~(classes[cls].parent)].prio; … … 1661 1667 /// \brief Gives back a representant item of the class. 1662 1668 /// 1669 /// Gives back a representant item of the class. 1663 1670 /// The representant is indpendent from the priorities of the 1664 1671 /// items. 1665 /// \return Gives back a representant item of the class.1666 1672 const Item& classRep(int id) const { 1667 1673 int parent = classes[id].parent;
Note: See TracChangeset
for help on using the changeset viewer.