Changes in / [741:10c9c3a35b83:742:8e68671af789] in lemon-main
- Files:
-
- 7 added
- 29 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r735 r742 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 247 239 any kind of path structure. 248 240 249 \sa lemon::concepts::Path 241 \sa \ref concepts::Path "Path concept" 242 */ 243 244 /** 245 @defgroup heaps Heap Structures 246 @ingroup datas 247 \brief %Heap structures implemented in LEMON. 248 249 This group contains the heap structures implemented in LEMON. 250 251 LEMON provides several heap classes. They are efficient implementations 252 of the abstract data type \e priority \e queue. They store items with 253 specified values called \e priorities in such a way that finding and 254 removing the item with minimum priority are efficient. 255 The basic operations are adding and erasing items, changing the priority 256 of an item, etc. 257 258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 259 The heap implementations have the same interface, thus any of them can be 260 used easily in such algorithms. 261 262 \sa \ref concepts::Heap "Heap concept" 263 */ 264 265 /** 266 @defgroup matrices Matrices 267 @ingroup datas 268 \brief Two dimensional data storages implemented in LEMON. 269 270 This group contains two dimensional data storages implemented in LEMON. 250 271 */ 251 272 … … 257 278 This group contains some data structures implemented in LEMON in 258 279 order to make it easier to implement combinatorial algorithms. 280 */ 281 282 /** 283 @defgroup geomdat Geometric Data Structures 284 @ingroup auxdat 285 \brief Geometric data structures implemented in LEMON. 286 287 This group contains geometric data structures implemented in LEMON. 288 289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 290 vector with the usual operations. 291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the 292 rectangular bounding box of a set of \ref lemon::dim2::Point 293 "dim2::Point"'s. 294 */ 295 296 /** 297 @defgroup matrices Matrices 298 @ingroup auxdat 299 \brief Two dimensional data storages implemented in LEMON. 300 301 This group contains two dimensional data storages implemented in LEMON. 259 302 */ 260 303 … … 299 342 300 343 /** 344 @defgroup spantree Minimum Spanning Tree Algorithms 345 @ingroup algs 346 \brief Algorithms for finding minimum cost spanning trees and arborescences. 347 348 This group contains the algorithms for finding minimum cost spanning 349 trees and arborescences. 350 */ 351 352 /** 301 353 @defgroup max_flow Maximum Flow Algorithms 302 354 @ingroup algs … … 376 428 377 429 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 378 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]430 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 379 431 380 432 LEMON contains several algorithms related to minimum cut problems: … … 389 441 If you want to find minimum cut just between two distinict nodes, 390 442 see the \ref max_flow "maximum flow problem". 391 */392 393 /**394 @defgroup graph_properties Connectivity and Other Graph Properties395 @ingroup algs396 \brief Algorithms for discovering the graph properties397 398 This group contains the algorithms for discovering the graph properties399 like connectivity, bipartiteness, euler property, simplicity etc.400 401 \image html edge_biconnected_components.png402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth403 */404 405 /**406 @defgroup planar Planarity Embedding and Drawing407 @ingroup algs408 \brief Algorithms for planarity checking, embedding and drawing409 410 This group contains the algorithms for planarity checking,411 embedding and drawing.412 413 \image html planar.png414 \image latex planar.eps "Plane graph" width=\textwidth415 443 */ 416 444 … … 456 484 457 485 /** 458 @defgroup spantree Minimum Spanning Tree Algorithms 459 @ingroup algs 460 \brief Algorithms for finding minimum cost spanning trees and arborescences. 461 462 This group contains the algorithms for finding minimum cost spanning 463 trees and arborescences. 486 @defgroup graph_properties Connectivity and Other Graph Properties 487 @ingroup algs 488 \brief Algorithms for discovering the graph properties 489 490 This group contains the algorithms for discovering the graph properties 491 like connectivity, bipartiteness, euler property, simplicity etc. 492 493 \image html connected_components.png 494 \image latex connected_components.eps "Connected components" width=\textwidth 495 */ 496 497 /** 498 @defgroup planar Planarity Embedding and Drawing 499 @ingroup algs 500 \brief Algorithms for planarity checking, embedding and drawing 501 502 This group contains the algorithms for planarity checking, 503 embedding and drawing. 504 505 \image html planar.png 506 \image latex planar.eps "Plane graph" width=\textwidth 507 */ 508 509 /** 510 @defgroup approx Approximation Algorithms 511 @ingroup algs 512 \brief Approximation algorithms. 513 514 This group contains the approximation and heuristic algorithms 515 implemented in LEMON. 464 516 */ 465 517 … … 471 523 This group contains some algorithms implemented in LEMON 472 524 in order to make it easier to implement complex algorithms. 473 */474 475 /**476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 525 */ 483 526 … … 588 631 589 632 /** 590 @defgroup dimacs_group DIMACS format633 @defgroup dimacs_group DIMACS Format 591 634 @ingroup io_group 592 635 \brief Read and write files in DIMACS format … … 650 693 651 694 /** 695 @defgroup tools Standalone Utility Applications 696 697 Some utility applications are listed here. 698 699 The standard compilation procedure (<tt>./configure;make</tt>) will compile 700 them, as well. 701 */ 702 703 /** 652 704 \anchor demoprograms 653 705 … … 661 713 */ 662 714 663 /**664 @defgroup tools Standalone Utility Applications665 666 Some utility applications are listed here.667 668 The standard compilation procedure (<tt>./configure;make</tt>) will compile669 them, as well.670 */671 672 715 } -
lemon/Makefile.am
r686 r708 58 58 lemon/arg_parser.h \ 59 59 lemon/assert.h \ 60 lemon/bellman_ford.h \ 60 61 lemon/bfs.h \ 61 62 lemon/bin_heap.h \ 63 lemon/binom_heap.h \ 62 64 lemon/bucket_heap.h \ 63 65 lemon/cbc.h \ … … 79 81 lemon/euler.h \ 80 82 lemon/fib_heap.h \ 83 lemon/fourary_heap.h \ 81 84 lemon/full_graph.h \ 82 85 lemon/glpk.h \ … … 85 88 lemon/grid_graph.h \ 86 89 lemon/hypercube_graph.h \ 90 lemon/kary_heap.h \ 87 91 lemon/kruskal.h \ 88 92 lemon/hao_orlin.h \ … … 99 103 lemon/nauty_reader.h \ 100 104 lemon/network_simplex.h \ 105 lemon/pairing_heap.h \ 101 106 lemon/path.h \ 102 107 lemon/preflow.h \ -
lemon/bfs.h
r503 r717 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 226 227 ///\ref named-templ-param "Named parameter" for setting 227 228 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.229 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 230 template <class T> 230 231 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 247 ///\ref named-templ-param "Named parameter" for setting 247 248 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.249 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 250 template <class T> 250 251 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 267 ///\ref named-templ-param "Named parameter" for setting 267 268 ///\c ReachedMap type. 268 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.269 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 270 template <class T> 270 271 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 287 ///\ref named-templ-param "Named parameter" for setting 287 288 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.289 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 290 template <class T> 290 291 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 415 ///The simplest way to execute the BFS algorithm is to use one of the 415 416 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, firstyou have to call417 ///\ref init() , then you can add several source nodes with417 ///If you need better control on the execution, you have to call 418 ///\ref init() first, then you can add several source nodes with 418 419 ///\ref addSource(). Finally the actual path computation can be 419 420 ///performed with one of the \ref start() functions. … … 738 739 ///@{ 739 740 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.741 ///The shortest path to the given node. 742 743 ///Returns the shortest path to the given node from the root(s). 743 744 /// 744 745 ///\warning \c t should be reached from the root(s). … … 748 749 Path path(Node t) const { return Path(*G, *_pred, t); } 749 750 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).751 ///The distance of the given node from the root(s). 752 753 ///Returns the distance of the given node from the root(s). 753 754 /// 754 755 ///\warning If node \c v is not reached from the root(s), then … … 759 760 int dist(Node v) const { return (*_dist)[v]; } 760 761 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 762 ///\brief Returns the 'previous arc' of the shortest path tree for 763 ///the given node. 764 /// 763 765 ///This function returns the 'previous arc' of the shortest path 764 766 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 769 /// 768 770 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .771 ///tree used in \ref predNode() and \ref predMap(). 770 772 /// 771 773 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 775 Arc predArc(Node v) const { return (*_pred)[v];} 774 776 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 777 ///\brief Returns the 'previous node' of the shortest path tree for 778 ///the given node. 779 /// 777 780 ///This function returns the 'previous node' of the shortest path 778 781 ///tree for the node \c v, i.e. it returns the last but one node 779 /// froma shortest path from a root to \c v. It is \c INVALID782 ///of a shortest path from a root to \c v. It is \c INVALID 780 783 ///if \c v is not reached from the root(s) or if \c v is a root. 781 784 /// 782 785 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .786 ///tree used in \ref predArc() and \ref predMap(). 784 787 /// 785 788 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 805 /// 803 806 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .807 ///arcs, which form the shortest path tree (forest). 805 808 /// 806 809 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 811 const PredMap &predMap() const { return *_pred;} 809 812 810 ///Checks if anode is reached from the root(s).813 ///Checks if the given node is reached from the root(s). 811 814 812 815 ///Returns \c true if \c v is reached from the root(s). … … 834 837 ///The type of the map that stores the predecessor 835 838 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.839 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 840 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 841 ///Instantiates a PredMap. … … 849 852 850 853 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.854 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 852 855 ///By default it is a NullMap. 853 856 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 869 872 870 873 ///The type of the map that indicates which nodes are reached. 871 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.874 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 875 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 876 ///Instantiates a ReachedMap. … … 884 887 885 888 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.889 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 890 typedef typename Digraph::template NodeMap<int> DistMap; 888 891 ///Instantiates a DistMap. … … 899 902 900 903 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.904 ///It must conform to the \ref concepts::Path "Path" concept. 902 905 typedef lemon::Path<Digraph> Path; 903 906 }; … … 905 908 /// Default traits class used by BfsWizard 906 909 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 910 /// Default traits class used by BfsWizard. 911 /// \tparam GR The type of the digraph. 913 912 template<class GR> 914 913 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 937 /// Constructor. 939 938 940 /// This constructor does not require parameters, thereforeit initiates939 /// This constructor does not require parameters, it initiates 941 940 /// all of the attributes to \c 0. 942 941 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 968 967 typedef TR Base; 969 968 970 ///The type of the digraph the algorithm runs on.971 969 typedef typename TR::Digraph Digraph; 972 970 … … 976 974 typedef typename Digraph::OutArcIt OutArcIt; 977 975 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 976 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 977 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 978 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 979 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 980 typedef typename TR::Path Path; 989 981 … … 1068 1060 SetPredMapBase(const TR &b) : TR(b) {} 1069 1061 }; 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1062 1063 ///\brief \ref named-templ-param "Named parameter" for setting 1064 ///the predecessor map. 1065 /// 1066 ///\ref named-templ-param "Named parameter" function for setting 1067 ///the map that stores the predecessor arcs of the nodes. 1075 1068 template<class T> 1076 1069 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1079 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1080 }; 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1081 1082 ///\brief \ref named-templ-param "Named parameter" for setting 1083 ///the reached map. 1084 /// 1085 ///\ref named-templ-param "Named parameter" function for setting 1086 ///the map that indicates which nodes are reached. 1093 1087 template<class T> 1094 1088 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1098 SetDistMapBase(const TR &b) : TR(b) {} 1105 1099 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1100 1101 ///\brief \ref named-templ-param "Named parameter" for setting 1102 ///the distance map. 1103 /// 1104 ///\ref named-templ-param "Named parameter" function for setting 1105 ///the map that stores the distances of the nodes calculated 1106 ///by the algorithm. 1111 1107 template<class T> 1112 1108 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1118 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1119 }; 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1120 1121 ///\brief \ref named-func-param "Named parameter" for setting 1122 ///the processed map. 1123 /// 1124 ///\ref named-templ-param "Named parameter" function for setting 1125 ///the map that indicates which nodes are processed. 1129 1126 template<class T> 1130 1127 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1265 1262 /// 1266 1263 /// The type of the map that indicates which nodes are reached. 1267 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1264 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1265 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1266 … … 1426 1423 /// The simplest way to execute the BFS algorithm is to use one of the 1427 1424 /// member functions called \ref run(Node) "run()".\n 1428 /// If you need more control on the execution, firstyou have to call1429 /// \ref init() , then you can add several source nodes with1425 /// If you need better control on the execution, you have to call 1426 /// \ref init() first, then you can add several source nodes with 1430 1427 /// \ref addSource(). Finally the actual path computation can be 1431 1428 /// performed with one of the \ref start() functions. … … 1736 1733 ///@{ 1737 1734 1738 /// \brief Checks if anode is reached from the root(s).1735 /// \brief Checks if the given node is reached from the root(s). 1739 1736 /// 1740 1737 /// Returns \c true if \c v is reached from the root(s). -
lemon/bin_heap.h
r683 r711 20 20 #define LEMON_BIN_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Binary Heap implementation.24 ///\brief Binary heap implementation. 25 25 26 26 #include <vector> … … 30 30 namespace lemon { 31 31 32 /// \ingroup auxdat32 /// \ingroup heaps 33 33 /// 34 /// \brief A Binary Heap implementation.34 /// \brief Binary heap data structure. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 36 /// This class implements the \e binary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 37 38 /// 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 CMP 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. 43 /// 44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 46 ///to handle the cross references. 47 ///\tparam CMP A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 49 /// 50 ///\sa FibHeap 51 ///\sa Dijkstra 39 /// \tparam PR Type of the priorities of the items. 40 /// \tparam IM A read-writable item map with \c int values, used 41 /// internally to handle the cross references. 42 /// \tparam CMP A functor class for comparing the priorities. 43 /// The default is \c std::less<PR>. 44 #ifdef DOXYGEN 45 template <typename PR, typename IM, typename CMP> 46 #else 52 47 template <typename PR, typename IM, typename CMP = std::less<PR> > 48 #endif 53 49 class BinHeap { 54 55 50 public: 56 ///\e 51 52 /// Type of the item-int map. 57 53 typedef IM ItemIntMap; 58 /// \e54 /// Type of the priorities. 59 55 typedef PR Prio; 60 /// \e56 /// Type of the items stored in the heap. 61 57 typedef typename ItemIntMap::Key Item; 62 /// \e58 /// Type of the item-priority pairs. 63 59 typedef std::pair<Item,Prio> Pair; 64 /// \e60 /// Functor type for comparing the priorities. 65 61 typedef CMP Compare; 66 62 67 /// \brief Type to represent the items states.68 /// 69 /// Each Item element have a state associated to it. It maybe "in heap",70 /// "pre heap" or "postheap". The latter two are indifferent from the63 /// \brief Type to represent the states of the items. 64 /// 65 /// Each item has a state associated to it. It can be "in heap", 66 /// "pre-heap" or "post-heap". The latter two are indifferent from the 71 67 /// heap's point of view, but may be useful to the user. 72 68 /// … … 85 81 86 82 public: 87 /// \brief The constructor. 88 /// 89 /// The constructor. 90 /// \param map should be given to the constructor, since it is used 91 /// internally to handle the cross references. The value of the map 92 /// must be \c PRE_HEAP (<tt>-1</tt>) for every item. 83 84 /// \brief Constructor. 85 /// 86 /// Constructor. 87 /// \param map A map that assigns \c int values to the items. 88 /// It is used internally to handle the cross references. 89 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 93 90 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 91 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 99 /// internally to handle the cross references. The value of the map 100 /// should be PRE_HEAP (-1) for each element. 101 /// 102 /// \param comp The comparator function object. 92 /// \brief Constructor. 93 /// 94 /// Constructor. 95 /// \param map A map that assigns \c int values to the items. 96 /// It is used internally to handle the cross references. 97 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 98 /// \param comp The function object used for comparing the priorities. 103 99 BinHeap(ItemIntMap &map, const Compare &comp) 104 100 : _iim(map), _comp(comp) {} 105 101 106 102 107 /// The number of items stored in the heap.108 /// 109 /// \brief Returns the number of items stored in the heap.103 /// \brief The number of items stored in the heap. 104 /// 105 /// This function returns the number of items stored in the heap. 110 106 int size() const { return _data.size(); } 111 107 112 /// \brief Check s if the heap stores no items.113 /// 114 /// Returns \c true if and only if the heap stores no items.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 115 111 bool empty() const { return _data.empty(); } 116 112 117 /// \brief Make empty this heap. 118 /// 119 /// Make empty this heap. It does not change the cross reference map. 120 /// If you want to reuse what is not surely empty you should first clear 121 /// the heap and after that you should set the cross reference map for 122 /// each item to \c PRE_HEAP. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 123 120 void clear() { 124 121 _data.clear(); … … 128 125 static int parent(int i) { return (i-1)/2; } 129 126 130 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 131 128 bool less(const Pair &p1, const Pair &p2) const { 132 129 return _comp(p1.second, p2.second); 133 130 } 134 131 135 int bubble _up(int hole, Pair p) {132 int bubbleUp(int hole, Pair p) { 136 133 int par = parent(hole); 137 134 while( hole>0 && less(p,_data[par]) ) { … … 144 141 } 145 142 146 int bubble _down(int hole, Pair p, int length) {147 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 148 145 while(child < length) { 149 146 if( less(_data[child-1], _data[child]) ) { … … 154 151 move(_data[child], hole); 155 152 hole = child; 156 child = second _child(hole);153 child = secondChild(hole); 157 154 } 158 155 child--; … … 172 169 173 170 public: 171 174 172 /// \brief Insert a pair of item and priority into the heap. 175 173 /// 176 /// Adds \c p.first to the heap with priority \c p.second. 174 /// This function inserts \c p.first to the heap with priority 175 /// \c p.second. 177 176 /// \param p The pair to insert. 177 /// \pre \c p.first must not be stored in the heap. 178 178 void push(const Pair &p) { 179 179 int n = _data.size(); 180 180 _data.resize(n+1); 181 bubble_up(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given heap. 185 /// 186 /// Adds \c i to the heap with priority \c p. 181 bubbleUp(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given priority. 185 /// 186 /// This function inserts the given item into the heap with the 187 /// given priority. 187 188 /// \param i The item to insert. 188 189 /// \param p The priority of the item. 190 /// \pre \e i must not be stored in the heap. 189 191 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 190 192 191 /// \brief Returns the item with minimum priority relative to \c Compare. 192 /// 193 /// This method returns the item with minimum priority relative to \c 194 /// Compare. 195 /// \pre The heap must be nonempty. 193 /// \brief Return the item having minimum priority. 194 /// 195 /// This function returns the item having minimum priority. 196 /// \pre The heap must be non-empty. 196 197 Item top() const { 197 198 return _data[0].first; 198 199 } 199 200 200 /// \brief Returns the minimum priority relative to \c Compare.201 /// 202 /// It returns the minimum priority relative to \c Compare.203 /// \pre The heap must be non empty.201 /// \brief The minimum priority. 202 /// 203 /// This function returns the minimum priority. 204 /// \pre The heap must be non-empty. 204 205 Prio prio() const { 205 206 return _data[0].second; 206 207 } 207 208 208 /// \brief Deletes the item with minimum priority relative to \c Compare. 209 /// 210 /// This method deletes the item with minimum priority relative to \c 211 /// Compare from the heap. 209 /// \brief Remove the item having minimum priority. 210 /// 211 /// This function removes the item having minimum priority. 212 212 /// \pre The heap must be non-empty. 213 213 void pop() { … … 215 215 _iim.set(_data[0].first, POST_HEAP); 216 216 if (n > 0) { 217 bubble _down(0, _data[n], n);217 bubbleDown(0, _data[n], n); 218 218 } 219 219 _data.pop_back(); 220 220 } 221 221 222 /// \brief Deletes \c i from the heap. 223 /// 224 /// This method deletes item \c i from the heap. 225 /// \param i The item to erase. 226 /// \pre The item should be in the heap. 222 /// \brief Remove the given item from the heap. 223 /// 224 /// This function removes the given item from the heap if it is 225 /// already stored. 226 /// \param i The item to delete. 227 /// \pre \e i must be in the heap. 227 228 void erase(const Item &i) { 228 229 int h = _iim[i]; … … 230 231 _iim.set(_data[h].first, POST_HEAP); 231 232 if( h < n ) { 232 if ( bubble _up(h, _data[n]) == h) {233 bubble _down(h, _data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 234 235 } 235 236 } … … 237 238 } 238 239 239 240 /// \brief Returns the priority of \c i. 241 /// 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 244 /// \pre \c i must be in the heap. 240 /// \brief The priority of the given item. 241 /// 242 /// This function returns the priority of the given item. 243 /// \param i The item. 244 /// \pre \e i must be in the heap. 245 245 Prio operator[](const Item &i) const { 246 246 int idx = _iim[i]; … … 248 248 } 249 249 250 /// \brief \c i gets to the heap with priority \c p independently 251 /// if \c i was already there. 252 /// 253 /// This method calls \ref push(\c i, \c p) if \c i is not stored 254 /// in the heap and sets the priority of \c i to \c p otherwise. 250 /// \brief Set the priority of an item or insert it, if it is 251 /// not stored in the heap. 252 /// 253 /// This method sets the priority of the given item if it is 254 /// already stored in the heap. Otherwise it inserts the given 255 /// item into the heap with the given priority. 255 256 /// \param i The item. 256 257 /// \param p The priority. … … 261 262 } 262 263 else if( _comp(p, _data[idx].second) ) { 263 bubble _up(idx, Pair(i,p));264 bubbleUp(idx, Pair(i,p)); 264 265 } 265 266 else { 266 bubble _down(idx, Pair(i,p), _data.size());267 } 268 } 269 270 /// \brief Decrease s the priority of \c i to \c p.271 /// 272 /// This method decreases the priority of item \c i to \c p.267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 } 270 271 /// \brief Decrease the priority of an item to the given value. 272 /// 273 /// This function decreases the priority of an item to the given value. 273 274 /// \param i The item. 274 275 /// \param p The priority. 275 /// \pre \c i must be stored in the heap with priority at least \c 276 /// p relative to \c Compare. 276 /// \pre \e i must be stored in the heap with priority at least \e p. 277 277 void decrease(const Item &i, const Prio &p) { 278 278 int idx = _iim[i]; 279 bubble _up(idx, Pair(i,p));280 } 281 282 /// \brief Increase s the priority of \c i to \c p.283 /// 284 /// This method sets the priority of item \c i to \c p.279 bubbleUp(idx, Pair(i,p)); 280 } 281 282 /// \brief Increase the priority of an item to the given value. 283 /// 284 /// This function increases the priority of an item to the given value. 285 285 /// \param i The item. 286 286 /// \param p The priority. 287 /// \pre \c i must be stored in the heap with priority at most \c 288 /// p relative to \c Compare. 287 /// \pre \e i must be stored in the heap with priority at most \e p. 289 288 void increase(const Item &i, const Prio &p) { 290 289 int idx = _iim[i]; 291 bubble _down(idx, Pair(i,p), _data.size());292 } 293 294 /// \brief Return s if \c item is in, has already been in, or has295 /// never been in the heap.296 /// 297 /// This method returns PRE_HEAP if \c item has never been in the298 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP299 /// otherwise. In the latter case it is possible that \c item will300 /// get backto the heap again.290 bubbleDown(idx, Pair(i,p), _data.size()); 291 } 292 293 /// \brief Return the state of an item. 294 /// 295 /// This method returns \c PRE_HEAP if the given item has never 296 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 297 /// and \c POST_HEAP otherwise. 298 /// In the latter case it is possible that the item will get back 299 /// to the heap again. 301 300 /// \param i The item. 302 301 State state(const Item &i) const { … … 307 306 } 308 307 309 /// \brief Set s the state of the \citem in the heap.310 /// 311 /// Sets the state of the \c item in the heap. It can be used to312 /// manually clear the heap when it is important to achive the313 /// better time complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 314 313 /// \param i The item. 315 314 /// \param st The state. It should not be \c IN_HEAP. … … 328 327 } 329 328 330 /// \brief Replaces an item in the heap. 331 /// 332 /// The \c i item is replaced with \c j item. The \c i item should 333 /// be in the heap, while the \c j should be out of the heap. The 334 /// \c i item will out of the heap and \c j will be in the heap 335 /// with the same prioriority as prevoiusly the \c i item. 329 /// \brief Replace an item in the heap. 330 /// 331 /// This function replaces item \c i with item \c j. 332 /// Item \c i must be in the heap, while \c j must be out of the heap. 333 /// After calling this method, item \c i will be out of the 334 /// heap and \c j will be in the heap with the same prioriority 335 /// as item \c i had before. 336 336 void replace(const Item& i, const Item& j) { 337 337 int idx = _iim[i]; -
lemon/bits/map_extender.h
r617 r718 50 50 typedef typename Parent::ConstReference ConstReference; 51 51 52 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 53 52 54 class MapIt; 53 55 class ConstMapIt; … … 192 194 typedef typename Parent::ConstReference ConstReference; 193 195 196 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 197 194 198 class MapIt; 195 199 class ConstMapIt; -
lemon/bucket_heap.h
r683 r711 20 20 #define LEMON_BUCKET_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Bucket Heap implementation.24 ///\brief Bucket heap implementation. 25 25 26 26 #include <vector> … … 54 54 } 55 55 56 /// \ingroup auxdat 57 /// 58 /// \brief A Bucket Heap implementation. 59 /// 60 /// This class implements the \e bucket \e heap data structure. A \e heap 61 /// is a data structure for storing items with specified values called \e 62 /// priorities in such a way that finding the item with minimum priority is 63 /// efficient. The bucket heap is very simple implementation, it can store 64 /// only integer priorities and it stores for each priority in the 65 /// \f$ [0..C) \f$ range a list of items. So it should be used only when 66 /// the priorities are small. It is not intended to use as dijkstra heap. 67 /// 68 /// \param IM A read and write Item int map, used internally 69 /// to handle the cross references. 70 /// \param MIN If the given parameter is false then instead of the 71 /// minimum value the maximum can be retrivied with the top() and 72 /// prio() member functions. 56 /// \ingroup heaps 57 /// 58 /// \brief Bucket heap data structure. 59 /// 60 /// This class implements the \e bucket \e heap data structure. 61 /// It practically conforms to the \ref concepts::Heap "heap concept", 62 /// but it has some limitations. 63 /// 64 /// The bucket heap is a very simple structure. It can store only 65 /// \c int priorities and it maintains a list of items for each priority 66 /// in the range <tt>[0..C)</tt>. So it should only be used when the 67 /// priorities are small. It is not intended to use as a Dijkstra heap. 68 /// 69 /// \tparam IM A read-writable item map with \c int values, used 70 /// internally to handle the cross references. 71 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. 72 /// The default is \e min-heap. If this parameter is set to \c false, 73 /// then the comparison is reversed, so the top(), prio() and pop() 74 /// functions deal with the item having maximum priority instead of the 75 /// minimum. 76 /// 77 /// \sa SimpleBucketHeap 73 78 template <typename IM, bool MIN = true> 74 79 class BucketHeap { 75 80 76 81 public: 77 /// \e 78 typedef typename IM::Key Item; 79 /// \e 82 83 /// Type of the item-int map. 84 typedef IM ItemIntMap; 85 /// Type of the priorities. 80 86 typedef int Prio; 81 /// \e82 typedef std::pair<Item, Prio> Pair;83 /// \e84 typedef IM ItemIntMap;87 /// Type of the items stored in the heap. 88 typedef typename ItemIntMap::Key Item; 89 /// Type of the item-priority pairs. 90 typedef std::pair<Item,Prio> Pair; 85 91 86 92 private: … … 90 96 public: 91 97 92 /// \brief Type to represent the items states.93 /// 94 /// Each Item element have a state associated to it. It maybe "in heap",95 /// "pre heap" or "postheap". The latter two are indifferent from the98 /// \brief Type to represent the states of the items. 99 /// 100 /// Each item has a state associated to it. It can be "in heap", 101 /// "pre-heap" or "post-heap". The latter two are indifferent from the 96 102 /// heap's point of view, but may be useful to the user. 97 103 /// … … 105 111 106 112 public: 107 /// \brief The constructor. 108 /// 109 /// The constructor. 110 /// \param map should be given to the constructor, since it is used 111 /// internally to handle the cross references. The value of the map 112 /// should be PRE_HEAP (-1) for each element. 113 114 /// \brief Constructor. 115 /// 116 /// Constructor. 117 /// \param map A map that assigns \c int values to the items. 118 /// It is used internally to handle the cross references. 119 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 113 120 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} 114 121 115 /// The number of items stored in the heap.116 /// 117 /// \brief Returns the number of items stored in the heap.122 /// \brief The number of items stored in the heap. 123 /// 124 /// This function returns the number of items stored in the heap. 118 125 int size() const { return _data.size(); } 119 126 120 /// \brief Check s if the heap stores no items.121 /// 122 /// Returns \c true if and only if the heap stores no items.127 /// \brief Check if the heap is empty. 128 /// 129 /// This function returns \c true if the heap is empty. 123 130 bool empty() const { return _data.empty(); } 124 131 125 /// \brief Make empty this heap. 126 /// 127 /// Make empty this heap. It does not change the cross reference 128 /// map. If you want to reuse a heap what is not surely empty you 129 /// should first clear the heap and after that you should set the 130 /// cross reference map for each item to \c PRE_HEAP. 132 /// \brief Make the heap empty. 133 /// 134 /// This functon makes the heap empty. 135 /// It does not change the cross reference map. If you want to reuse 136 /// a heap that is not surely empty, you should first clear it and 137 /// then you should set the cross reference map to \c PRE_HEAP 138 /// for each item. 131 139 void clear() { 132 140 _data.clear(); _first.clear(); _minimum = 0; … … 135 143 private: 136 144 137 void relocate _last(int idx) {145 void relocateLast(int idx) { 138 146 if (idx + 1 < int(_data.size())) { 139 147 _data[idx] = _data.back(); … … 175 183 176 184 public: 185 177 186 /// \brief Insert a pair of item and priority into the heap. 178 187 /// 179 /// Adds \c p.first to the heap with priority \c p.second. 188 /// This function inserts \c p.first to the heap with priority 189 /// \c p.second. 180 190 /// \param p The pair to insert. 191 /// \pre \c p.first must not be stored in the heap. 181 192 void push(const Pair& p) { 182 193 push(p.first, p.second); … … 185 196 /// \brief Insert an item into the heap with the given priority. 186 197 /// 187 /// Adds \c i to the heap with priority \c p. 198 /// This function inserts the given item into the heap with the 199 /// given priority. 188 200 /// \param i The item to insert. 189 201 /// \param p The priority of the item. 202 /// \pre \e i must not be stored in the heap. 190 203 void push(const Item &i, const Prio &p) { 191 204 int idx = _data.size(); … … 198 211 } 199 212 200 /// \brief Return s the item withminimum priority.201 /// 202 /// This method returns the item withminimum priority.203 /// \pre The heap must be non empty.213 /// \brief Return the item having minimum priority. 214 /// 215 /// This function returns the item having minimum priority. 216 /// \pre The heap must be non-empty. 204 217 Item top() const { 205 218 while (_first[_minimum] == -1) { … … 209 222 } 210 223 211 /// \brief Returns the minimum priority.212 /// 213 /// Itreturns the minimum priority.214 /// \pre The heap must be non empty.224 /// \brief The minimum priority. 225 /// 226 /// This function returns the minimum priority. 227 /// \pre The heap must be non-empty. 215 228 Prio prio() const { 216 229 while (_first[_minimum] == -1) { … … 220 233 } 221 234 222 /// \brief Deletes the item withminimum priority.223 /// 224 /// This method deletes the item with minimum priority from the heap.235 /// \brief Remove the item having minimum priority. 236 /// 237 /// This function removes the item having minimum priority. 225 238 /// \pre The heap must be non-empty. 226 239 void pop() { … … 231 244 _iim[_data[idx].item] = -2; 232 245 unlace(idx); 233 relocate_last(idx); 234 } 235 236 /// \brief Deletes \c i from the heap. 237 /// 238 /// This method deletes item \c i from the heap, if \c i was 239 /// already stored in the heap. 240 /// \param i The item to erase. 246 relocateLast(idx); 247 } 248 249 /// \brief Remove the given item from the heap. 250 /// 251 /// This function removes the given item from the heap if it is 252 /// already stored. 253 /// \param i The item to delete. 254 /// \pre \e i must be in the heap. 241 255 void erase(const Item &i) { 242 256 int idx = _iim[i]; 243 257 _iim[_data[idx].item] = -2; 244 258 unlace(idx); 245 relocate_last(idx); 246 } 247 248 249 /// \brief Returns the priority of \c i. 250 /// 251 /// This function returns the priority of item \c i. 252 /// \pre \c i must be in the heap. 253 /// \param i The item. 259 relocateLast(idx); 260 } 261 262 /// \brief The priority of the given item. 263 /// 264 /// This function returns the priority of the given item. 265 /// \param i The item. 266 /// \pre \e i must be in the heap. 254 267 Prio operator[](const Item &i) const { 255 268 int idx = _iim[i]; … … 257 270 } 258 271 259 /// \brief \c i gets to the heap with priority \c p independently 260 /// if \c i was already there. 261 /// 262 /// This method calls \ref push(\c i, \c p) if \c i is not stored 263 /// in the heap and sets the priority of \c i to \c p otherwise. 272 /// \brief Set the priority of an item or insert it, if it is 273 /// not stored in the heap. 274 /// 275 /// This method sets the priority of the given item if it is 276 /// already stored in the heap. Otherwise it inserts the given 277 /// item into the heap with the given priority. 264 278 /// \param i The item. 265 279 /// \param p The priority. … … 275 289 } 276 290 277 /// \brief Decreases the priority of \c i to \c p. 278 /// 279 /// This method decreases the priority of item \c i to \c p. 280 /// \pre \c i must be stored in the heap with priority at least \c 281 /// p relative to \c Compare. 291 /// \brief Decrease the priority of an item to the given value. 292 /// 293 /// This function decreases the priority of an item to the given value. 282 294 /// \param i The item. 283 295 /// \param p The priority. 296 /// \pre \e i must be stored in the heap with priority at least \e p. 284 297 void decrease(const Item &i, const Prio &p) { 285 298 int idx = _iim[i]; … … 292 305 } 293 306 294 /// \brief Increases the priority of \c i to \c p. 295 /// 296 /// This method sets the priority of item \c i to \c p. 297 /// \pre \c i must be stored in the heap with priority at most \c 298 /// p relative to \c Compare. 307 /// \brief Increase the priority of an item to the given value. 308 /// 309 /// This function increases the priority of an item to the given value. 299 310 /// \param i The item. 300 311 /// \param p The priority. 312 /// \pre \e i must be stored in the heap with priority at most \e p. 301 313 void increase(const Item &i, const Prio &p) { 302 314 int idx = _iim[i]; … … 306 318 } 307 319 308 /// \brief Return s if \c item is in, has already been in, or has309 /// never been in the heap.310 /// 311 /// This method returns PRE_HEAP if \c item has never been in the312 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP313 /// otherwise. In the latter case it is possible that \c item will314 /// get backto the heap again.320 /// \brief Return the state of an item. 321 /// 322 /// This method returns \c PRE_HEAP if the given item has never 323 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 324 /// and \c POST_HEAP otherwise. 325 /// In the latter case it is possible that the item will get back 326 /// to the heap again. 315 327 /// \param i The item. 316 328 State state(const Item &i) const { … … 320 332 } 321 333 322 /// \brief Set s the state of the \citem in the heap.323 /// 324 /// Sets the state of the \c item in the heap. It can be used to325 /// manually clear the heap when it is important to achive the326 /// better time complexity.334 /// \brief Set the state of an item in the heap. 335 /// 336 /// This function sets the state of the given item in the heap. 337 /// It can be used to manually clear the heap when it is important 338 /// to achive better time complexity. 327 339 /// \param i The item. 328 340 /// \param st The state. It should not be \c IN_HEAP. … … 360 372 }; // class BucketHeap 361 373 362 /// \ingroup auxdat363 /// 364 /// \brief A Simplified Bucket Heap implementation.374 /// \ingroup heaps 375 /// 376 /// \brief Simplified bucket heap data structure. 365 377 /// 366 378 /// This class implements a simplified \e bucket \e heap data 367 /// structure. It does not provide some functionality but it faster 368 /// and simplier data structure than the BucketHeap. The main 369 /// difference is that the BucketHeap stores for every key a double 370 /// linked list while this class stores just simple lists. In the 371 /// other way it does not support erasing each elements just the 372 /// minimal and it does not supports key increasing, decreasing. 373 /// 374 /// \param IM A read and write Item int map, used internally 375 /// to handle the cross references. 376 /// \param MIN If the given parameter is false then instead of the 377 /// minimum value the maximum can be retrivied with the top() and 378 /// prio() member functions. 379 /// structure. It does not provide some functionality, but it is 380 /// faster and simpler than BucketHeap. The main difference is 381 /// that BucketHeap stores a doubly-linked list for each key while 382 /// this class stores only simply-linked lists. It supports erasing 383 /// only for the item having minimum priority and it does not support 384 /// key increasing and decreasing. 385 /// 386 /// Note that this implementation does not conform to the 387 /// \ref concepts::Heap "heap concept" due to the lack of some 388 /// functionality. 389 /// 390 /// \tparam IM A read-writable item map with \c int values, used 391 /// internally to handle the cross references. 392 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. 393 /// The default is \e min-heap. If this parameter is set to \c false, 394 /// then the comparison is reversed, so the top(), prio() and pop() 395 /// functions deal with the item having maximum priority instead of the 396 /// minimum. 379 397 /// 380 398 /// \sa BucketHeap … … 383 401 384 402 public: 385 typedef typename IM::Key Item; 403 404 /// Type of the item-int map. 405 typedef IM ItemIntMap; 406 /// Type of the priorities. 386 407 typedef int Prio; 387 typedef std::pair<Item, Prio> Pair; 388 typedef IM ItemIntMap; 408 /// Type of the items stored in the heap. 409 typedef typename ItemIntMap::Key Item; 410 /// Type of the item-priority pairs. 411 typedef std::pair<Item,Prio> Pair; 389 412 390 413 private: … … 394 417 public: 395 418 396 /// \brief Type to represent the items states.397 /// 398 /// Each Item element have a state associated to it. It maybe "in heap",399 /// "pre heap" or "postheap". The latter two are indifferent from the419 /// \brief Type to represent the states of the items. 420 /// 421 /// Each item has a state associated to it. It can be "in heap", 422 /// "pre-heap" or "post-heap". The latter two are indifferent from the 400 423 /// heap's point of view, but may be useful to the user. 401 424 /// … … 410 433 public: 411 434 412 /// \brief The constructor.413 /// 414 /// The constructor.415 /// \param map should be given to the constructor, since it is used416 /// internally to handle the cross references. The value of the map417 /// should be PRE_HEAP (-1) for each element.435 /// \brief Constructor. 436 /// 437 /// Constructor. 438 /// \param map A map that assigns \c int values to the items. 439 /// It is used internally to handle the cross references. 440 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 418 441 explicit SimpleBucketHeap(ItemIntMap &map) 419 442 : _iim(map), _free(-1), _num(0), _minimum(0) {} 420 443 421 /// \brief Returns the number of items stored in the heap.422 /// 423 /// Th e number of items stored in the heap.444 /// \brief The number of items stored in the heap. 445 /// 446 /// This function returns the number of items stored in the heap. 424 447 int size() const { return _num; } 425 448 426 /// \brief Check s if the heap stores no items.427 /// 428 /// Returns \c true if and only if the heap stores no items.449 /// \brief Check if the heap is empty. 450 /// 451 /// This function returns \c true if the heap is empty. 429 452 bool empty() const { return _num == 0; } 430 453 431 /// \brief Make empty this heap. 432 /// 433 /// Make empty this heap. It does not change the cross reference 434 /// map. If you want to reuse a heap what is not surely empty you 435 /// should first clear the heap and after that you should set the 436 /// cross reference map for each item to \c PRE_HEAP. 454 /// \brief Make the heap empty. 455 /// 456 /// This functon makes the heap empty. 457 /// It does not change the cross reference map. If you want to reuse 458 /// a heap that is not surely empty, you should first clear it and 459 /// then you should set the cross reference map to \c PRE_HEAP 460 /// for each item. 437 461 void clear() { 438 462 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; … … 441 465 /// \brief Insert a pair of item and priority into the heap. 442 466 /// 443 /// Adds \c p.first to the heap with priority \c p.second. 467 /// This function inserts \c p.first to the heap with priority 468 /// \c p.second. 444 469 /// \param p The pair to insert. 470 /// \pre \c p.first must not be stored in the heap. 445 471 void push(const Pair& p) { 446 472 push(p.first, p.second); … … 449 475 /// \brief Insert an item into the heap with the given priority. 450 476 /// 451 /// Adds \c i to the heap with priority \c p. 477 /// This function inserts the given item into the heap with the 478 /// given priority. 452 479 /// \param i The item to insert. 453 480 /// \param p The priority of the item. 481 /// \pre \e i must not be stored in the heap. 454 482 void push(const Item &i, const Prio &p) { 455 483 int idx; … … 472 500 } 473 501 474 /// \brief Return s the item withminimum priority.475 /// 476 /// This method returns the item withminimum priority.477 /// \pre The heap must be non empty.502 /// \brief Return the item having minimum priority. 503 /// 504 /// This function returns the item having minimum priority. 505 /// \pre The heap must be non-empty. 478 506 Item top() const { 479 507 while (_first[_minimum] == -1) { … … 483 511 } 484 512 485 /// \brief Returns the minimum priority.486 /// 487 /// Itreturns the minimum priority.488 /// \pre The heap must be non empty.513 /// \brief The minimum priority. 514 /// 515 /// This function returns the minimum priority. 516 /// \pre The heap must be non-empty. 489 517 Prio prio() const { 490 518 while (_first[_minimum] == -1) { … … 494 522 } 495 523 496 /// \brief Deletes the item withminimum priority.497 /// 498 /// This method deletes the item with minimum priority from the heap.524 /// \brief Remove the item having minimum priority. 525 /// 526 /// This function removes the item having minimum priority. 499 527 /// \pre The heap must be non-empty. 500 528 void pop() { … … 510 538 } 511 539 512 /// \brief Returns the priority of \c i. 513 /// 514 /// This function returns the priority of item \c i. 515 /// \warning This operator is not a constant time function 516 /// because it scans the whole data structure to find the proper 517 /// value. 518 /// \pre \c i must be in the heap. 519 /// \param i The item. 540 /// \brief The priority of the given item. 541 /// 542 /// This function returns the priority of the given item. 543 /// \param i The item. 544 /// \pre \e i must be in the heap. 545 /// \warning This operator is not a constant time function because 546 /// it scans the whole data structure to find the proper value. 520 547 Prio operator[](const Item &i) const { 521 for (int k = 0; k < _first.size(); ++k) {548 for (int k = 0; k < int(_first.size()); ++k) { 522 549 int idx = _first[k]; 523 550 while (idx != -1) { … … 531 558 } 532 559 533 /// \brief Return s if \c item is in, has already been in, or has534 /// never been in the heap.535 /// 536 /// This method returns PRE_HEAP if \c item has never been in the537 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP538 /// otherwise. In the latter case it is possible that \c item will539 /// get backto the heap again.560 /// \brief Return the state of an item. 561 /// 562 /// This method returns \c PRE_HEAP if the given item has never 563 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 564 /// and \c POST_HEAP otherwise. 565 /// In the latter case it is possible that the item will get back 566 /// to the heap again. 540 567 /// \param i The item. 541 568 State state(const Item &i) const { -
lemon/circulation.h
r641 r715 73 73 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" 74 74 /// concept. 75 #ifdef DOXYGEN 76 typedef GR::ArcMap<Value> FlowMap; 77 #else 75 78 typedef typename Digraph::template ArcMap<Value> FlowMap; 79 #endif 76 80 77 81 /// \brief Instantiates a FlowMap. … … 88 92 /// The elevator type used by the algorithm. 89 93 /// 90 /// \sa Elevator 91 /// \sa LinkedElevator 94 /// \sa Elevator, LinkedElevator 95 #ifdef DOXYGEN 96 typedef lemon::Elevator<GR, GR::Node> Elevator; 97 #else 92 98 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 99 #endif 93 100 94 101 /// \brief Instantiates an Elevator. … … 451 458 } 452 459 453 /// \brief Sets the tolerance used by algorithm. 454 /// 455 /// Sets the tolerance used by algorithm. 456 Circulation& tolerance(const Tolerance& tolerance) const { 460 /// \brief Sets the tolerance used by the algorithm. 461 /// 462 /// Sets the tolerance object used by the algorithm. 463 /// \return <tt>(*this)</tt> 464 Circulation& tolerance(const Tolerance& tolerance) { 457 465 _tol = tolerance; 458 466 return *this; … … 461 469 /// \brief Returns a const reference to the tolerance. 462 470 /// 463 /// Returns a const reference to the tolerance. 471 /// Returns a const reference to the tolerance object used by 472 /// the algorithm. 464 473 const Tolerance& tolerance() const { 465 return tolerance;474 return _tol; 466 475 } 467 476 468 477 /// \name Execution Control 469 478 /// The simplest way to execute the algorithm is to call \ref run().\n 470 /// If you need morecontrol on the initial solution or the execution,471 /// first you have to call one of the \ref init() functions, then479 /// If you need better control on the initial solution or the execution, 480 /// you have to call one of the \ref init() functions first, then 472 481 /// the \ref start() function. 473 482 -
lemon/concepts/heap.h
r584 r710 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H 20 #define LEMON_CONCEPTS_HEAP_H 21 19 22 ///\ingroup concept 20 23 ///\file 21 24 ///\brief The concept of heaps. 22 25 23 #ifndef LEMON_CONCEPTS_HEAP_H24 #define LEMON_CONCEPTS_HEAP_H25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 38 /// This concept class describes the main interface of heaps. 39 /// The various \ref heaps "heap structures" are efficient 40 /// implementations of the abstract data type \e priority \e queue. 41 /// They store items with specified values called \e priorities 42 /// in such a way that finding and removing the item with minimum 43 /// priority are efficient. The basic operations are adding and 44 /// erasing items, changing the priority of an item, etc. 43 45 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 47 /// Any class that conforms to this concept can be used easily in such 48 /// algorithms. 49 /// 50 /// \tparam PR Type of the priorities of the items. 51 /// \tparam IM A read-writable item map with \c int values, used 46 52 /// internally to handle the cross references. 47 /// \tparam C omp A functor class for the ordering ofthe priorities.53 /// \tparam CMP A functor class for comparing the priorities. 48 54 /// The default is \c std::less<PR>. 49 55 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename C omp = std::less<PR>>56 template <typename PR, typename IM, typename CMP> 51 57 #else 52 template <typename PR, typename IM >58 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 59 #endif 54 60 class Heap { … … 65 71 /// 66 72 /// Each item has a state associated to it. It can be "in heap", 67 /// "pre heap" or "post heap". The later two are indifferent 68 /// from the point of view of the heap, but may be useful for 69 /// the user. 73 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 70 75 /// 71 76 /// The item-int map must be initialized in such way that it assigns … … 73 78 enum State { 74 79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = -1, ///< = -1. The "pre 76 POST_HEAP = -2 ///< = -2. The "post 80 PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. 81 POST_HEAP = -2 ///< = -2. The "post-heap" state constant. 77 82 }; 78 83 79 /// \brief The constructor.80 /// 81 /// The constructor.84 /// \brief Constructor. 85 /// 86 /// Constructor. 82 87 /// \param map A map that assigns \c int values to keys of type 83 88 /// \c Item. It is used internally by the heap implementations to 84 89 /// handle the cross references. The assigned value must be 85 /// \c PRE_HEAP (<tt>-1</tt>) for e veryitem.90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 86 91 explicit Heap(ItemIntMap &map) {} 87 92 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to keys of type 97 /// \c Item. It is used internally by the heap implementations to 98 /// handle the cross references. The assigned value must be 99 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 100 /// \param comp The function object used for comparing the priorities. 101 explicit Heap(ItemIntMap &map, const CMP &comp) {} 102 88 103 /// \brief The number of items stored in the heap. 89 104 /// 90 /// Returns the number of items stored in the heap.105 /// This function returns the number of items stored in the heap. 91 106 int size() const { return 0; } 92 107 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 96 111 bool empty() const { return false; } 97 112 98 /// \brief Makes the heap empty. 99 /// 100 /// Makes the heap empty. 101 void clear(); 102 103 /// \brief Inserts an item into the heap with the given priority. 104 /// 105 /// Inserts the given item into the heap with the given priority. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 120 void clear() {} 121 122 /// \brief Insert an item into the heap with the given priority. 123 /// 124 /// This function inserts the given item into the heap with the 125 /// given priority. 106 126 /// \param i The item to insert. 107 127 /// \param p The priority of the item. 128 /// \pre \e i must not be stored in the heap. 108 129 void push(const Item &i, const Prio &p) {} 109 130 110 /// \brief Return sthe item having minimum priority.111 /// 112 /// Returns the item having minimum priority.131 /// \brief Return the item having minimum priority. 132 /// 133 /// This function returns the item having minimum priority. 113 134 /// \pre The heap must be non-empty. 114 135 Item top() const {} … … 116 137 /// \brief The minimum priority. 117 138 /// 118 /// Returns the minimum priority.139 /// This function returns the minimum priority. 119 140 /// \pre The heap must be non-empty. 120 141 Prio prio() const {} 121 142 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.143 /// \brief Remove the item having minimum priority. 144 /// 145 /// This function removes the item having minimum priority. 125 146 /// \pre The heap must be non-empty. 126 147 void pop() {} 127 148 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 149 /// \brief Remove the given item from the heap. 150 /// 151 /// This function removes the given item from the heap if it is 152 /// already stored. 131 153 /// \param i The item to delete. 154 /// \pre \e i must be in the heap. 132 155 void erase(const Item &i) {} 133 156 134 /// \brief The priority of an item.135 /// 136 /// Returns the priority of the given item.137 /// \param i The item. 138 /// \pre \ ci must be in the heap.157 /// \brief The priority of the given item. 158 /// 159 /// This function returns the priority of the given item. 160 /// \param i The item. 161 /// \pre \e i must be in the heap. 139 162 Prio operator[](const Item &i) const {} 140 163 141 /// \brief Set s the priority of an item or insertsit, if it is164 /// \brief Set the priority of an item or insert it, if it is 142 165 /// not stored in the heap. 143 166 /// 144 167 /// This method sets the priority of the given item if it is 145 /// already stored in the heap. 146 /// Otherwise it inserts the given itemwith the given priority.168 /// already stored in the heap. Otherwise it inserts the given 169 /// item into the heap with the given priority. 147 170 /// 148 171 /// \param i The item. … … 150 173 void set(const Item &i, const Prio &p) {} 151 174 152 /// \brief Decrease sthe priority of an item to the given value.153 /// 154 /// Decreases the priority of an item to the given value.175 /// \brief Decrease the priority of an item to the given value. 176 /// 177 /// This function decreases the priority of an item to the given value. 155 178 /// \param i The item. 156 179 /// \param p The priority. 157 /// \pre \ c i must be stored in the heap with priority at least \cp.180 /// \pre \e i must be stored in the heap with priority at least \e p. 158 181 void decrease(const Item &i, const Prio &p) {} 159 182 160 /// \brief Increase sthe priority of an item to the given value.161 /// 162 /// Increases the priority of an item to the given value.183 /// \brief Increase the priority of an item to the given value. 184 /// 185 /// This function increases the priority of an item to the given value. 163 186 /// \param i The item. 164 187 /// \param p The priority. 165 /// \pre \ c i must be stored in the heap with priority at most \cp.188 /// \pre \e i must be stored in the heap with priority at most \e p. 166 189 void increase(const Item &i, const Prio &p) {} 167 190 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 191 /// \brief Return the state of an item. 170 192 /// 171 193 /// This method returns \c PRE_HEAP if the given item has never … … 177 199 State state(const Item &i) const {} 178 200 179 /// \brief Set sthe state of an item in the heap.180 /// 181 /// Sets the state of the given item in the heap. It can be used182 /// to manually clear the heap when it is important to achive the183 /// better time complexity.201 /// \brief Set the state of an item in the heap. 202 /// 203 /// This function sets the state of the given item in the heap. 204 /// It can be used to manually clear the heap when it is important 205 /// to achive better time complexity. 184 206 /// \param i The item. 185 207 /// \param st The state. It should not be \c IN_HEAP. -
lemon/concepts/maps.h
r529 r718 183 183 template<typename _ReferenceMap> 184 184 struct Constraints { 185 void constraints() { 185 typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type 186 constraints() { 186 187 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 187 188 ref = m[key]; -
lemon/dfs.h
r584 r717 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 225 226 ///\ref named-templ-param "Named parameter" for setting 226 227 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.228 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 229 template <class T> 229 230 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 246 ///\ref named-templ-param "Named parameter" for setting 246 247 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.248 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 249 template <class T> 249 250 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 266 ///\ref named-templ-param "Named parameter" for setting 266 267 ///\c ReachedMap type. 267 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.268 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 269 template <class T> 269 270 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 286 ///\ref named-templ-param "Named parameter" for setting 286 287 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.288 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 289 template <class T> 289 290 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 413 ///The simplest way to execute the DFS algorithm is to use one of the 413 414 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, firstyou have to call415 ///\ref init() , then you can add a source node with \ref addSource()415 ///If you need better control on the execution, you have to call 416 ///\ref init() first, then you can add a source node with \ref addSource() 416 417 ///and perform the actual computation with \ref start(). 417 418 ///This procedure can be repeated if there are nodes that have not … … 670 671 ///@{ 671 672 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.673 ///The DFS path to the given node. 674 675 ///Returns the DFS path to the given node from the root(s). 675 676 /// 676 677 ///\warning \c t should be reached from the root(s). … … 680 681 Path path(Node t) const { return Path(*G, *_pred, t); } 681 682 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).683 ///The distance of the given node from the root(s). 684 685 ///Returns the distance of the given node from the root(s). 685 686 /// 686 687 ///\warning If node \c v is not reached from the root(s), then … … 691 692 int dist(Node v) const { return (*_dist)[v]; } 692 693 693 ///Returns the 'previous arc' of the %DFS tree for anode.694 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 695 695 696 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 700 /// 700 701 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .702 ///\ref predNode() and \ref predMap(). 702 703 /// 703 704 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 706 Arc predArc(Node v) const { return (*_pred)[v];} 706 707 707 ///Returns the 'previous node' of the %DFS tree .708 ///Returns the 'previous node' of the %DFS tree for the given node. 708 709 709 710 ///This function returns the 'previous node' of the %DFS 710 711 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID712 ///of a %DFS path from a root to \c v. It is \c INVALID 712 713 ///if \c v is not reached from the root(s) or if \c v is a root. 713 714 /// 714 715 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .716 ///\ref predArc() and \ref predMap(). 716 717 /// 717 718 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 735 /// 735 736 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .737 ///arcs, which form the DFS tree (forest). 737 738 /// 738 739 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 741 const PredMap &predMap() const { return *_pred;} 741 742 742 ///Checks if anode is reached from the root(s).743 ///Checks if the given node. node is reached from the root(s). 743 744 744 745 ///Returns \c true if \c v is reached from the root(s). … … 766 767 ///The type of the map that stores the predecessor 767 768 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.769 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 771 ///Instantiates a PredMap. … … 781 782 782 783 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 784 785 ///By default it is a NullMap. 785 786 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 801 802 802 803 ///The type of the map that indicates which nodes are reached. 803 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.804 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 805 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 806 ///Instantiates a ReachedMap. … … 816 817 817 818 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.819 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 820 typedef typename Digraph::template NodeMap<int> DistMap; 820 821 ///Instantiates a DistMap. … … 831 832 832 833 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.834 ///It must conform to the \ref concepts::Path "Path" concept. 834 835 typedef lemon::Path<Digraph> Path; 835 836 }; … … 837 838 /// Default traits class used by DfsWizard 838 839 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 840 /// Default traits class used by DfsWizard. 841 /// \tparam GR The type of the digraph. 845 842 template<class GR> 846 843 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 867 /// Constructor. 871 868 872 /// This constructor does not require parameters, thereforeit initiates869 /// This constructor does not require parameters, it initiates 873 870 /// all of the attributes to \c 0. 874 871 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 900 897 typedef TR Base; 901 898 902 ///The type of the digraph the algorithm runs on.903 899 typedef typename TR::Digraph Digraph; 904 900 … … 908 904 typedef typename Digraph::OutArcIt OutArcIt; 909 905 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 906 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 907 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 908 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 909 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 910 typedef typename TR::Path Path; 921 911 … … 1000 990 SetPredMapBase(const TR &b) : TR(b) {} 1001 991 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 992 993 ///\brief \ref named-templ-param "Named parameter" for setting 994 ///the predecessor map. 995 /// 996 ///\ref named-templ-param "Named parameter" function for setting 997 ///the map that stores the predecessor arcs of the nodes. 1007 998 template<class T> 1008 999 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1009 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1010 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1011 1012 ///\brief \ref named-templ-param "Named parameter" for setting 1013 ///the reached map. 1014 /// 1015 ///\ref named-templ-param "Named parameter" function for setting 1016 ///the map that indicates which nodes are reached. 1025 1017 template<class T> 1026 1018 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1028 SetDistMapBase(const TR &b) : TR(b) {} 1037 1029 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1030 1031 ///\brief \ref named-templ-param "Named parameter" for setting 1032 ///the distance map. 1033 /// 1034 ///\ref named-templ-param "Named parameter" function for setting 1035 ///the map that stores the distances of the nodes calculated 1036 ///by the algorithm. 1043 1037 template<class T> 1044 1038 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1048 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1049 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1050 1051 ///\brief \ref named-func-param "Named parameter" for setting 1052 ///the processed map. 1053 /// 1054 ///\ref named-templ-param "Named parameter" function for setting 1055 ///the map that indicates which nodes are processed. 1061 1056 template<class T> 1062 1057 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1204 /// 1210 1205 /// The type of the map that indicates which nodes are reached. 1211 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1206 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1207 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1208 … … 1370 1365 /// The simplest way to execute the DFS algorithm is to use one of the 1371 1366 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, firstyou have to call1373 /// \ref init() , then you can add a source node with \ref addSource()1367 /// If you need better control on the execution, you have to call 1368 /// \ref init() first, then you can add a source node with \ref addSource() 1374 1369 /// and perform the actual computation with \ref start(). 1375 1370 /// This procedure can be repeated if there are nodes that have not … … 1621 1616 ///@{ 1622 1617 1623 /// \brief Checks if anode is reached from the root(s).1618 /// \brief Checks if the given node is reached from the root(s). 1624 1619 /// 1625 1620 /// Returns \c true if \c v is reached from the root(s). -
lemon/dijkstra.h
r584 r717 71 71 72 72 ///The type of the map that stores the arc lengths. 73 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.73 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 74 74 typedef LEN LengthMap; 75 ///The type of the length of the arcs.75 ///The type of the arc lengths. 76 76 typedef typename LEN::Value Value; 77 77 … … 117 117 ///The type of the map that stores the predecessor 118 118 ///arcs of the shortest paths. 119 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.119 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 120 120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 121 121 ///Instantiates a \c PredMap. … … 132 132 133 133 ///The type of the map that indicates which nodes are processed. 134 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.134 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 135 135 ///By default it is a NullMap. 136 136 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 152 152 153 153 ///The type of the map that stores the distances of the nodes. 154 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.154 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 155 155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 156 156 ///Instantiates a \c DistMap. … … 169 169 /// \ingroup shortest_path 170 170 ///This class provides an efficient implementation of the %Dijkstra algorithm. 171 /// 172 ///The %Dijkstra algorithm solves the single-source shortest path problem 173 ///when all arc lengths are non-negative. If there are negative lengths, 174 ///the BellmanFord algorithm should be used instead. 171 175 /// 172 176 ///The arc lengths are passed to the algorithm using a … … 202 206 typedef typename TR::Digraph Digraph; 203 207 204 ///The type of the length of the arcs.208 ///The type of the arc lengths. 205 209 typedef typename TR::LengthMap::Value Value; 206 210 ///The type of the map that stores the arc lengths. … … 305 309 ///\ref named-templ-param "Named parameter" for setting 306 310 ///\c PredMap type. 307 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.311 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 308 312 template <class T> 309 313 struct SetPredMap … … 326 330 ///\ref named-templ-param "Named parameter" for setting 327 331 ///\c DistMap type. 328 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.332 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 329 333 template <class T> 330 334 struct SetDistMap … … 347 351 ///\ref named-templ-param "Named parameter" for setting 348 352 ///\c ProcessedMap type. 349 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.353 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 350 354 template <class T> 351 355 struct SetProcessedMap … … 444 448 ///\ref named-templ-param "Named parameter" for setting 445 449 ///\c OperationTraits type. 450 /// For more information see \ref DijkstraDefaultOperationTraits. 446 451 template <class T> 447 452 struct SetOperationTraits … … 585 590 ///The simplest way to execute the %Dijkstra algorithm is to use 586 591 ///one of the member functions called \ref run(Node) "run()".\n 587 ///If you need more control on the execution, firstyou have to call588 ///\ref init() , then you can add several source nodes with592 ///If you need better control on the execution, you have to call 593 ///\ref init() first, then you can add several source nodes with 589 594 ///\ref addSource(). Finally the actual path computation can be 590 595 ///performed with one of the \ref start() functions. … … 802 807 ///The results of the %Dijkstra algorithm can be obtained using these 803 808 ///functions.\n 804 ///Either \ref run(Node) "run()" or \ref start() should be called809 ///Either \ref run(Node) "run()" or \ref init() should be called 805 810 ///before using them. 806 811 807 812 ///@{ 808 813 809 ///The shortest path to anode.810 811 ///Returns the shortest path to a node.814 ///The shortest path to the given node. 815 816 ///Returns the shortest path to the given node from the root(s). 812 817 /// 813 818 ///\warning \c t should be reached from the root(s). … … 817 822 Path path(Node t) const { return Path(*G, *_pred, t); } 818 823 819 ///The distance of anode from the root(s).820 821 ///Returns the distance of anode from the root(s).824 ///The distance of the given node from the root(s). 825 826 ///Returns the distance of the given node from the root(s). 822 827 /// 823 828 ///\warning If node \c v is not reached from the root(s), then … … 828 833 Value dist(Node v) const { return (*_dist)[v]; } 829 834 830 ///Returns the 'previous arc' of the shortest path tree for a node. 831 835 ///\brief Returns the 'previous arc' of the shortest path tree for 836 ///the given node. 837 /// 832 838 ///This function returns the 'previous arc' of the shortest path 833 839 ///tree for the node \c v, i.e. it returns the last arc of a … … 836 842 /// 837 843 ///The shortest path tree used here is equal to the shortest path 838 ///tree used in \ref predNode() .844 ///tree used in \ref predNode() and \ref predMap(). 839 845 /// 840 846 ///\pre Either \ref run(Node) "run()" or \ref init() … … 842 848 Arc predArc(Node v) const { return (*_pred)[v]; } 843 849 844 ///Returns the 'previous node' of the shortest path tree for a node. 845 850 ///\brief Returns the 'previous node' of the shortest path tree for 851 ///the given node. 852 /// 846 853 ///This function returns the 'previous node' of the shortest path 847 854 ///tree for the node \c v, i.e. it returns the last but one node 848 /// froma shortest path from a root to \c v. It is \c INVALID855 ///of a shortest path from a root to \c v. It is \c INVALID 849 856 ///if \c v is not reached from the root(s) or if \c v is a root. 850 857 /// 851 858 ///The shortest path tree used here is equal to the shortest path 852 ///tree used in \ref predArc() .859 ///tree used in \ref predArc() and \ref predMap(). 853 860 /// 854 861 ///\pre Either \ref run(Node) "run()" or \ref init() … … 871 878 /// 872 879 ///Returns a const reference to the node map that stores the predecessor 873 ///arcs, which form the shortest path tree .880 ///arcs, which form the shortest path tree (forest). 874 881 /// 875 882 ///\pre Either \ref run(Node) "run()" or \ref init() … … 877 884 const PredMap &predMap() const { return *_pred;} 878 885 879 ///Checks if anode is reached from the root(s).886 ///Checks if the given node is reached from the root(s). 880 887 881 888 ///Returns \c true if \c v is reached from the root(s). … … 896 903 Heap::POST_HEAP; } 897 904 898 ///The current distance of anode from the root(s).899 900 ///Returns the current distance of anode from the root(s).905 ///The current distance of the given node from the root(s). 906 907 ///Returns the current distance of the given node from the root(s). 901 908 ///It may be decreased in the following processes. 902 909 /// … … 925 932 926 933 ///The type of the map that stores the arc lengths. 927 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.934 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 928 935 typedef LEN LengthMap; 929 ///The type of the length of the arcs.936 ///The type of the arc lengths. 930 937 typedef typename LEN::Value Value; 931 938 … … 974 981 ///The type of the map that stores the predecessor 975 982 ///arcs of the shortest paths. 976 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.983 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 977 984 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 978 985 ///Instantiates a PredMap. … … 989 996 990 997 ///The type of the map that indicates which nodes are processed. 991 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.998 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 992 999 ///By default it is a NullMap. 993 1000 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; … … 1009 1016 1010 1017 ///The type of the map that stores the distances of the nodes. 1011 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.1018 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1012 1019 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1013 1020 ///Instantiates a DistMap. … … 1024 1031 1025 1032 ///The type of the shortest paths. 1026 ///It must meetthe \ref concepts::Path "Path" concept.1033 ///It must conform to the \ref concepts::Path "Path" concept. 1027 1034 typedef lemon::Path<Digraph> Path; 1028 1035 }; … … 1030 1037 /// Default traits class used by DijkstraWizard 1031 1038 1032 /// To make it easier to use Dijkstra algorithm 1033 /// we have created a wizard class. 1034 /// This \ref DijkstraWizard class needs default traits, 1035 /// as well as the \ref Dijkstra class. 1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1037 /// \ref DijkstraWizard class. 1039 /// Default traits class used by DijkstraWizard. 1040 /// \tparam GR The type of the digraph. 1041 /// \tparam LEN The type of the length map. 1038 1042 template<typename GR, typename LEN> 1039 1043 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> … … 1094 1098 typedef TR Base; 1095 1099 1096 ///The type of the digraph the algorithm runs on.1097 1100 typedef typename TR::Digraph Digraph; 1098 1101 … … 1102 1105 typedef typename Digraph::OutArcIt OutArcIt; 1103 1106 1104 ///The type of the map that stores the arc lengths.1105 1107 typedef typename TR::LengthMap LengthMap; 1106 ///The type of the length of the arcs.1107 1108 typedef typename LengthMap::Value Value; 1108 ///\brief The type of the map that stores the predecessor1109 ///arcs of the shortest paths.1110 1109 typedef typename TR::PredMap PredMap; 1111 ///The type of the map that stores the distances of the nodes.1112 1110 typedef typename TR::DistMap DistMap; 1113 ///The type of the map that indicates which nodes are processed.1114 1111 typedef typename TR::ProcessedMap ProcessedMap; 1115 ///The type of the shortest paths1116 1112 typedef typename TR::Path Path; 1117 ///The heap type used by the dijkstra algorithm.1118 1113 typedef typename TR::Heap Heap; 1119 1114 … … 1187 1182 SetPredMapBase(const TR &b) : TR(b) {} 1188 1183 }; 1189 ///\brief \ref named-func-param "Named parameter" 1190 ///for setting PredMap object. 1191 /// 1192 ///\ref named-func-param "Named parameter" 1193 ///for setting PredMap object. 1184 1185 ///\brief \ref named-templ-param "Named parameter" for setting 1186 ///the predecessor map. 1187 /// 1188 ///\ref named-templ-param "Named parameter" function for setting 1189 ///the map that stores the predecessor arcs of the nodes. 1194 1190 template<class T> 1195 1191 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) … … 1205 1201 SetDistMapBase(const TR &b) : TR(b) {} 1206 1202 }; 1207 ///\brief \ref named-func-param "Named parameter" 1208 ///for setting DistMap object. 1209 /// 1210 ///\ref named-func-param "Named parameter" 1211 ///for setting DistMap object. 1203 1204 ///\brief \ref named-templ-param "Named parameter" for setting 1205 ///the distance map. 1206 /// 1207 ///\ref named-templ-param "Named parameter" function for setting 1208 ///the map that stores the distances of the nodes calculated 1209 ///by the algorithm. 1212 1210 template<class T> 1213 1211 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) … … 1223 1221 SetProcessedMapBase(const TR &b) : TR(b) {} 1224 1222 }; 1225 ///\brief \ref named-func-param "Named parameter" 1226 ///for setting ProcessedMap object. 1227 /// 1228 /// \ref named-func-param "Named parameter" 1229 ///for setting ProcessedMap object. 1223 1224 ///\brief \ref named-func-param "Named parameter" for setting 1225 ///the processed map. 1226 /// 1227 ///\ref named-templ-param "Named parameter" function for setting 1228 ///the map that indicates which nodes are processed. 1230 1229 template<class T> 1231 1230 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1240 1239 SetPathBase(const TR &b) : TR(b) {} 1241 1240 }; 1241 1242 1242 ///\brief \ref named-func-param "Named parameter" 1243 1243 ///for getting the shortest path to the target node. -
lemon/dim2.h
r440 r714 22 22 #include <iostream> 23 23 24 ///\ingroup misc24 ///\ingroup geomdat 25 25 ///\file 26 26 ///\brief A simple two dimensional vector and a bounding box implementation 27 ///28 /// The class \ref lemon::dim2::Point "dim2::Point" implements29 /// a two dimensional vector with the usual operations.30 ///31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine32 /// the rectangular bounding box of a set of33 /// \ref lemon::dim2::Point "dim2::Point"'s.34 27 35 28 namespace lemon { … … 41 34 namespace dim2 { 42 35 43 /// \addtogroup misc36 /// \addtogroup geomdat 44 37 /// @{ 45 38 -
lemon/fib_heap.h
r683 r711 21 21 22 22 ///\file 23 ///\ingroup auxdat24 ///\brief Fibonacci Heap implementation.23 ///\ingroup heaps 24 ///\brief Fibonacci heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 30 31 namespace lemon { 31 32 32 /// \ingroup auxdat33 /// \ingroup heaps 33 34 /// 34 /// \brief Fibonacci Heap.35 /// \brief Fibonacci heap data structure. 35 36 /// 36 ///This class implements the \e Fibonacci \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 CMP specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 37 /// This class implements the \e Fibonacci \e heap data structure. 38 /// It fully conforms to the \ref concepts::Heap "heap concept". 41 39 /// 42 /// The methods \ref increase and \ref erase are not efficient in a Fibonacci43 /// heap. In case of many calls to these operations, it is better to use a44 /// \ref BinHeap "binary heap".40 /// The methods \ref increase() and \ref erase() are not efficient in a 41 /// Fibonacci heap. In case of many calls of these operations, it is 42 /// better to use other heap structure, e.g. \ref BinHeap "binary heap". 45 43 /// 46 ///\param PRIO Type of the priority of the items. 47 ///\param IM A read and writable Item int map, used internally 48 ///to handle the cross references. 49 ///\param CMP A class for the ordering of the priorities. The 50 ///default is \c std::less<PRIO>. 51 /// 52 ///\sa BinHeap 53 ///\sa Dijkstra 44 /// \tparam PR Type of the priorities of the items. 45 /// \tparam IM A read-writable item map with \c int values, used 46 /// internally to handle the cross references. 47 /// \tparam CMP A functor class for comparing the priorities. 48 /// The default is \c std::less<PR>. 54 49 #ifdef DOXYGEN 55 template <typename PR IO, typename IM, typename CMP>50 template <typename PR, typename IM, typename CMP> 56 51 #else 57 template <typename PR IO, typename IM, typename CMP = std::less<PRIO> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 58 53 #endif 59 54 class FibHeap { 60 55 public: 61 ///\e 56 57 /// Type of the item-int map. 62 58 typedef IM ItemIntMap; 63 /// \e64 typedef PR IOPrio;65 /// \e59 /// Type of the priorities. 60 typedef PR Prio; 61 /// Type of the items stored in the heap. 66 62 typedef typename ItemIntMap::Key Item; 67 /// \e63 /// Type of the item-priority pairs. 68 64 typedef std::pair<Item,Prio> Pair; 69 /// \e65 /// Functor type for comparing the priorities. 70 66 typedef CMP Compare; 71 67 … … 81 77 public: 82 78 83 /// \brief Type to represent the items states.84 /// 85 /// Each Item element have a state associated to it. It maybe "in heap",86 /// "pre heap" or "postheap". The latter two are indifferent from the79 /// \brief Type to represent the states of the items. 80 /// 81 /// Each item has a state associated to it. It can be "in heap", 82 /// "pre-heap" or "post-heap". The latter two are indifferent from the 87 83 /// heap's point of view, but may be useful to the user. 88 84 /// … … 95 91 }; 96 92 97 /// \brief The constructor 98 /// 99 /// \c map should be given to the constructor, since it is 100 /// used internally to handle the cross references. 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to the items. 97 /// It is used internally to handle the cross references. 98 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 101 99 explicit FibHeap(ItemIntMap &map) 102 100 : _minimum(0), _iim(map), _num() {} 103 101 104 /// \brief The constructor 105 /// 106 /// \c map should be given to the constructor, since it is used 107 /// internally to handle the cross references. \c comp is an 108 /// object for ordering of the priorities. 102 /// \brief Constructor. 103 /// 104 /// Constructor. 105 /// \param map A map that assigns \c int values to the items. 106 /// It is used internally to handle the cross references. 107 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 108 /// \param comp The function object used for comparing the priorities. 109 109 FibHeap(ItemIntMap &map, const Compare &comp) 110 110 : _minimum(0), _iim(map), _comp(comp), _num() {} … … 112 112 /// \brief The number of items stored in the heap. 113 113 /// 114 /// Returns the number of items stored in the heap.114 /// This function returns the number of items stored in the heap. 115 115 int size() const { return _num; } 116 116 117 /// \brief Check s if the heap stores no items.118 /// 119 /// Returns \c true if and only if the heap stores no items.117 /// \brief Check if the heap is empty. 118 /// 119 /// This function returns \c true if the heap is empty. 120 120 bool empty() const { return _num==0; } 121 121 122 /// \brief Make empty this heap. 123 /// 124 /// Make empty this heap. It does not change the cross reference 125 /// map. If you want to reuse a heap what is not surely empty you 126 /// should first clear the heap and after that you should set the 127 /// cross reference map for each item to \c PRE_HEAP. 122 /// \brief Make the heap empty. 123 /// 124 /// This functon makes the heap empty. 125 /// It does not change the cross reference map. If you want to reuse 126 /// a heap that is not surely empty, you should first clear it and 127 /// then you should set the cross reference map to \c PRE_HEAP 128 /// for each item. 128 129 void clear() { 129 130 _data.clear(); _minimum = 0; _num = 0; 130 131 } 131 132 132 /// \brief \c item gets to the heap with priority \c value independently 133 /// if \c item was already there. 134 /// 135 /// This method calls \ref push(\c item, \c value) if \c item is not 136 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 137 /// \ref increase(\c item, \c value) otherwise. 138 void set (const Item& item, const Prio& value) { 139 int i=_iim[item]; 140 if ( i >= 0 && _data[i].in ) { 141 if ( _comp(value, _data[i].prio) ) decrease(item, value); 142 if ( _comp(_data[i].prio, value) ) increase(item, value); 143 } else push(item, value); 144 } 145 146 /// \brief Adds \c item to the heap with priority \c value. 147 /// 148 /// Adds \c item to the heap with priority \c value. 149 /// \pre \c item must not be stored in the heap. 150 void push (const Item& item, const Prio& value) { 133 /// \brief Insert an item into the heap with the given priority. 134 /// 135 /// This function inserts the given item into the heap with the 136 /// given priority. 137 /// \param item The item to insert. 138 /// \param prio The priority of the item. 139 /// \pre \e item must not be stored in the heap. 140 void push (const Item& item, const Prio& prio) { 151 141 int i=_iim[item]; 152 142 if ( i < 0 ) { … … 169 159 _data[_minimum].right_neighbor=i; 170 160 _data[i].left_neighbor=_minimum; 171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i;161 if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; 172 162 } else { 173 163 _data[i].right_neighbor=_data[i].left_neighbor=i; 174 164 _minimum=i; 175 165 } 176 _data[i].prio= value;166 _data[i].prio=prio; 177 167 ++_num; 178 168 } 179 169 180 /// \brief Returns the item with minimum priority relative to \c Compare. 181 /// 182 /// This method returns the item with minimum priority relative to \c 183 /// Compare. 184 /// \pre The heap must be nonempty. 170 /// \brief Return the item having minimum priority. 171 /// 172 /// This function returns the item having minimum priority. 173 /// \pre The heap must be non-empty. 185 174 Item top() const { return _data[_minimum].name; } 186 175 187 /// \brief Returns the minimum priority relative to \c Compare. 188 /// 189 /// It returns the minimum priority relative to \c Compare. 190 /// \pre The heap must be nonempty. 191 const Prio& prio() const { return _data[_minimum].prio; } 192 193 /// \brief Returns the priority of \c item. 194 /// 195 /// It returns the priority of \c item. 196 /// \pre \c item must be in the heap. 197 const Prio& operator[](const Item& item) const { 198 return _data[_iim[item]].prio; 199 } 200 201 /// \brief Deletes the item with minimum priority relative to \c Compare. 202 /// 203 /// This method deletes the item with minimum priority relative to \c 204 /// Compare from the heap. 176 /// \brief The minimum priority. 177 /// 178 /// This function returns the minimum priority. 179 /// \pre The heap must be non-empty. 180 Prio prio() const { return _data[_minimum].prio; } 181 182 /// \brief Remove the item having minimum priority. 183 /// 184 /// This function removes the item having minimum priority. 205 185 /// \pre The heap must be non-empty. 206 186 void pop() { … … 209 189 _data[_minimum].in=false; 210 190 if ( _data[_minimum].degree!=0 ) { 211 make root(_data[_minimum].child);191 makeRoot(_data[_minimum].child); 212 192 _minimum=_data[_minimum].child; 213 193 balance(); … … 222 202 int last_child=_data[child].left_neighbor; 223 203 224 make root(child);204 makeRoot(child); 225 205 226 206 _data[left].right_neighbor=child; … … 235 215 } 236 216 237 /// \brief Deletes \c item from the heap. 238 /// 239 /// This method deletes \c item from the heap, if \c item was already 240 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 217 /// \brief Remove the given item from the heap. 218 /// 219 /// This function removes the given item from the heap if it is 220 /// already stored. 221 /// \param item The item to delete. 222 /// \pre \e item must be in the heap. 241 223 void erase (const Item& item) { 242 224 int i=_iim[item]; … … 253 235 } 254 236 255 /// \brief Decreases the priority of \c item to \c value. 256 /// 257 /// This method decreases the priority of \c item to \c value. 258 /// \pre \c item must be stored in the heap with priority at least \c 259 /// value relative to \c Compare. 260 void decrease (Item item, const Prio& value) { 237 /// \brief The priority of the given item. 238 /// 239 /// This function returns the priority of the given item. 240 /// \param item The item. 241 /// \pre \e item must be in the heap. 242 Prio operator[](const Item& item) const { 243 return _data[_iim[item]].prio; 244 } 245 246 /// \brief Set the priority of an item or insert it, if it is 247 /// not stored in the heap. 248 /// 249 /// This method sets the priority of the given item if it is 250 /// already stored in the heap. Otherwise it inserts the given 251 /// item into the heap with the given priority. 252 /// \param item The item. 253 /// \param prio The priority. 254 void set (const Item& item, const Prio& prio) { 261 255 int i=_iim[item]; 262 _data[i].prio=value; 256 if ( i >= 0 && _data[i].in ) { 257 if ( _comp(prio, _data[i].prio) ) decrease(item, prio); 258 if ( _comp(_data[i].prio, prio) ) increase(item, prio); 259 } else push(item, prio); 260 } 261 262 /// \brief Decrease the priority of an item to the given value. 263 /// 264 /// This function decreases the priority of an item to the given value. 265 /// \param item The item. 266 /// \param prio The priority. 267 /// \pre \e item must be stored in the heap with priority at least \e prio. 268 void decrease (const Item& item, const Prio& prio) { 269 int i=_iim[item]; 270 _data[i].prio=prio; 263 271 int p=_data[i].parent; 264 272 265 if ( p!=-1 && _comp( value, _data[p].prio) ) {273 if ( p!=-1 && _comp(prio, _data[p].prio) ) { 266 274 cut(i,p); 267 275 cascade(p); 268 276 } 269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 270 } 271 272 /// \brief Increases the priority of \c item to \c value. 273 /// 274 /// This method sets the priority of \c item to \c value. Though 275 /// there is no precondition on the priority of \c item, this 276 /// method should be used only if it is indeed necessary to increase 277 /// (relative to \c Compare) the priority of \c item, because this 278 /// method is inefficient. 279 void increase (Item item, const Prio& value) { 277 if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; 278 } 279 280 /// \brief Increase the priority of an item to the given value. 281 /// 282 /// This function increases the priority of an item to the given value. 283 /// \param item The item. 284 /// \param prio The priority. 285 /// \pre \e item must be stored in the heap with priority at most \e prio. 286 void increase (const Item& item, const Prio& prio) { 280 287 erase(item); 281 push(item, value);282 } 283 284 285 /// \brief Returns if \c item is in, has already been in, or has never286 /// been in the heap.287 /// 288 /// This method returns PRE_HEAP if \c item has never been in the289 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP290 /// otherwise. In the latter case it is possible that \c item will291 /// get back to the heap again.288 push(item, prio); 289 } 290 291 /// \brief Return the state of an item. 292 /// 293 /// This method returns \c PRE_HEAP if the given item has never 294 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 295 /// and \c POST_HEAP otherwise. 296 /// In the latter case it is possible that the item will get back 297 /// to the heap again. 298 /// \param item The item. 292 299 State state(const Item &item) const { 293 300 int i=_iim[item]; … … 299 306 } 300 307 301 /// \brief Set s the state of the \citem in the heap.302 /// 303 /// Sets the state of the \c item in the heap. It can be used to304 /// manually clear the heap when it is important to achive the305 /// better time _complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 306 313 /// \param i The item. 307 314 /// \param st The state. It should not be \c IN_HEAP. … … 366 373 } 367 374 368 void make root(int c) {375 void makeRoot(int c) { 369 376 int s=c; 370 377 do { -
lemon/gomory_hu.h
r596 r713 360 360 /// \c t. 361 361 /// \code 362 /// Gomor uHu<Graph> gom(g, capacities);362 /// GomoryHu<Graph> gom(g, capacities); 363 363 /// gom.run(); 364 364 /// int cnt=0; 365 /// for(Gomor uHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;365 /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; 366 366 /// \endcode 367 367 class MinCutNodeIt … … 457 457 /// \c t. 458 458 /// \code 459 /// Gomor uHu<Graph> gom(g, capacities);459 /// GomoryHu<Graph> gom(g, capacities); 460 460 /// gom.run(); 461 461 /// int value=0; 462 /// for(Gomor uHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)462 /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) 463 463 /// value+=capacities[e]; 464 464 /// \endcode -
lemon/maps.h
r684 r726 23 23 #include <functional> 24 24 #include <vector> 25 #include <map> 25 26 26 27 #include <lemon/core.h> … … 29 30 ///\ingroup maps 30 31 ///\brief Miscellaneous property maps 31 32 #include <map>33 32 34 33 namespace lemon { … … 58 57 /// but data written to it is not required (i.e. it will be sent to 59 58 /// <tt>/dev/null</tt>). 60 /// It conforms t he \ref concepts::ReadWriteMap "ReadWriteMap" concept.59 /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 61 60 /// 62 61 /// \sa ConstMap … … 91 90 /// 92 91 /// In other aspects it is equivalent to \c NullMap. 93 /// So it conforms t he \ref concepts::ReadWriteMap "ReadWriteMap"92 /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" 94 93 /// concept, but it absorbs the data written to it. 95 94 /// … … 160 159 /// 161 160 /// In other aspects it is equivalent to \c NullMap. 162 /// So it conforms t he \ref concepts::ReadWriteMap "ReadWriteMap"161 /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" 163 162 /// concept, but it absorbs the data written to it. 164 163 /// … … 234 233 /// It can be used with some data structures, for example 235 234 /// \c UnionFind, \c BinHeap, when the used items are small 236 /// integers. This map conforms t he \ref concepts::ReferenceMap235 /// integers. This map conforms to the \ref concepts::ReferenceMap 237 236 /// "ReferenceMap" concept. 238 237 /// … … 342 341 /// stored actually. This value can be different from the default 343 342 /// contructed value (i.e. \c %Value()). 344 /// This type conforms t he \ref concepts::ReferenceMap "ReferenceMap"343 /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap" 345 344 /// concept. 346 345 /// … … 708 707 /// The \c Key type of it is inherited from \c M and the \c Value 709 708 /// type is \c V. 710 /// This type conforms t he \ref concepts::ReadMap "ReadMap" concept.709 /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. 711 710 /// 712 711 /// The simplest way of using this map is through the convertMap() … … 1791 1790 /// \code 1792 1791 /// std::vector<Node> v; 1793 /// dfs(g ,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();1792 /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); 1794 1793 /// \endcode 1795 1794 /// \code 1796 1795 /// std::vector<Node> v(countNodes(g)); 1797 /// dfs(g ,s).processedMap(loggerBoolMap(v.begin())).run();1796 /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); 1798 1797 /// \endcode 1799 1798 /// … … 1819 1818 /// 1820 1819 /// IdMap provides a unique and immutable id for each item of the 1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1820 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1822 1821 /// - \b unique: different items get different ids, 1823 1822 /// - \b immutable: the id of an item does not change (even if you … … 1827 1826 /// the items stored in the graph, which is returned by the \c id() 1828 1827 /// function of the graph. This map can be inverted with its member 1829 /// class \c InverseMap or with the \c operator() member.1828 /// class \c InverseMap or with the \c operator()() member. 1830 1829 /// 1831 1830 /// \tparam GR The graph type. … … 1867 1866 public: 1868 1867 1869 /// \brief This class represents the inverse of its owner (IdMap). 1870 /// 1871 /// This class represents the inverse of its owner (IdMap). 1868 /// \brief The inverse map type of IdMap. 1869 /// 1870 /// The inverse map type of IdMap. The subscript operator gives back 1871 /// an item by its id. 1872 /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. 1872 1873 /// \see inverse() 1873 1874 class InverseMap { … … 1884 1885 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} 1885 1886 1886 /// \brief Gives back the given item fromits id.1887 /// \brief Gives back an item by its id. 1887 1888 /// 1888 /// Gives back the given item fromits id.1889 /// Gives back an item by its id. 1889 1890 Item operator[](int id) const { return _graph->fromId(id, Item());} 1890 1891 … … 1899 1900 }; 1900 1901 1902 /// \brief Returns an \c IdMap class. 1903 /// 1904 /// This function just returns an \c IdMap class. 1905 /// \relates IdMap 1906 template <typename K, typename GR> 1907 inline IdMap<GR, K> idMap(const GR& graph) { 1908 return IdMap<GR, K>(graph); 1909 } 1901 1910 1902 1911 /// \brief General cross reference graph map type. … … 1905 1914 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) 1906 1915 /// and if a key is set to a new value, then stores it in the inverse map. 1907 /// The values of the map can be accessed 1908 /// with stl compatible forward iterator. 1916 /// The graph items can be accessed by their values either using 1917 /// \c InverseMap or \c operator()(), and the values of the map can be 1918 /// accessed with an STL compatible forward iterator (\c ValueIt). 1919 /// 1920 /// This map is intended to be used when all associated values are 1921 /// different (the map is actually invertable) or there are only a few 1922 /// items with the same value. 1923 /// Otherwise consider to use \c IterableValueMap, which is more 1924 /// suitable and more efficient for such cases. It provides iterators 1925 /// to traverse the items with the same associated value, however 1926 /// it does not have \c InverseMap. 1909 1927 /// 1910 1928 /// This type is not reference map, so it cannot be modified with … … 1947 1965 /// \brief Forward iterator for values. 1948 1966 /// 1949 /// This iterator is an stlcompatible forward1967 /// This iterator is an STL compatible forward 1950 1968 /// iterator on the values of the map. The values can 1951 1969 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1952 1970 /// They are considered with multiplicity, so each value is 1953 1971 /// traversed for each item it is assigned to. 1954 class ValueIt erator1972 class ValueIt 1955 1973 : public std::iterator<std::forward_iterator_tag, Value> { 1956 1974 friend class CrossRefMap; 1957 1975 private: 1958 ValueIt erator(typename Container::const_iterator _it)1976 ValueIt(typename Container::const_iterator _it) 1959 1977 : it(_it) {} 1960 1978 public: 1961 1979 1962 ValueIterator() {} 1963 1964 ValueIterator& operator++() { ++it; return *this; } 1965 ValueIterator operator++(int) { 1966 ValueIterator tmp(*this); 1980 /// Constructor 1981 ValueIt() {} 1982 1983 /// \e 1984 ValueIt& operator++() { ++it; return *this; } 1985 /// \e 1986 ValueIt operator++(int) { 1987 ValueIt tmp(*this); 1967 1988 operator++(); 1968 1989 return tmp; 1969 1990 } 1970 1991 1992 /// \e 1971 1993 const Value& operator*() const { return it->first; } 1994 /// \e 1972 1995 const Value* operator->() const { return &(it->first); } 1973 1996 1974 bool operator==(ValueIterator jt) const { return it == jt.it; } 1975 bool operator!=(ValueIterator jt) const { return it != jt.it; } 1997 /// \e 1998 bool operator==(ValueIt jt) const { return it == jt.it; } 1999 /// \e 2000 bool operator!=(ValueIt jt) const { return it != jt.it; } 1976 2001 1977 2002 private: 1978 2003 typename Container::const_iterator it; 1979 2004 }; 2005 2006 /// Alias for \c ValueIt 2007 typedef ValueIt ValueIterator; 1980 2008 1981 2009 /// \brief Returns an iterator to the first value. 1982 2010 /// 1983 /// Returns an stlcompatible iterator to the2011 /// Returns an STL compatible iterator to the 1984 2012 /// first value of the map. The values of the 1985 2013 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 1986 2014 /// range. 1987 ValueIt eratorbeginValue() const {1988 return ValueIt erator(_inv_map.begin());2015 ValueIt beginValue() const { 2016 return ValueIt(_inv_map.begin()); 1989 2017 } 1990 2018 1991 2019 /// \brief Returns an iterator after the last value. 1992 2020 /// 1993 /// Returns an stlcompatible iterator after the2021 /// Returns an STL compatible iterator after the 1994 2022 /// last value of the map. The values of the 1995 2023 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 1996 2024 /// range. 1997 ValueIt eratorendValue() const {1998 return ValueIt erator(_inv_map.end());2025 ValueIt endValue() const { 2026 return ValueIt(_inv_map.end()); 1999 2027 } 2000 2028 … … 2033 2061 typename Container::const_iterator it = _inv_map.find(val); 2034 2062 return it != _inv_map.end() ? it->second : INVALID; 2063 } 2064 2065 /// \brief Returns the number of items with the given value. 2066 /// 2067 /// This function returns the number of items with the given value 2068 /// associated with it. 2069 int count(const Value &val) const { 2070 return _inv_map.count(val); 2035 2071 } 2036 2072 … … 2084 2120 public: 2085 2121 2086 /// \brief The inverse map type. 2087 /// 2088 /// The inverse of this map. The subscript operator of the map 2089 /// gives back the item that was last assigned to the value. 2122 /// \brief The inverse map type of CrossRefMap. 2123 /// 2124 /// The inverse map type of CrossRefMap. The subscript operator gives 2125 /// back an item by its value. 2126 /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. 2127 /// \see inverse() 2090 2128 class InverseMap { 2091 2129 public: … … 2114 2152 }; 2115 2153 2116 /// \brief It gives back the read-only inverse map.2117 /// 2118 /// It gives back the read-only inverse map.2154 /// \brief Gives back the inverse of the map. 2155 /// 2156 /// Gives back the inverse of the CrossRefMap. 2119 2157 InverseMap inverse() const { 2120 2158 return InverseMap(*this); … … 2123 2161 }; 2124 2162 2125 /// \brief Provides continuous and unique IDfor the2163 /// \brief Provides continuous and unique id for the 2126 2164 /// items of a graph. 2127 2165 /// 2128 2166 /// RangeIdMap provides a unique and continuous 2129 /// IDfor each item of a given type (\c Node, \c Arc or2167 /// id for each item of a given type (\c Node, \c Arc or 2130 2168 /// \c Edge) in a graph. This id is 2131 2169 /// - \b unique: different items get different ids, … … 2138 2176 /// the \c id() function of the graph or \ref IdMap. 2139 2177 /// This map can be inverted with its member class \c InverseMap, 2140 /// or with the \c operator() member.2178 /// or with the \c operator()() member. 2141 2179 /// 2142 2180 /// \tparam GR The graph type. … … 2266 2304 } 2267 2305 2268 /// \brief Gives back the \e RangeId of the item2269 /// 2270 /// Gives back the \e RangeId of the item.2306 /// \brief Gives back the \e range \e id of the item 2307 /// 2308 /// Gives back the \e range \e id of the item. 2271 2309 int operator[](const Item& item) const { 2272 2310 return Map::operator[](item); 2273 2311 } 2274 2312 2275 /// \brief Gives back the item belonging to a \e RangeId2276 /// 2277 /// Gives back the item belonging to a \e RangeId.2313 /// \brief Gives back the item belonging to a \e range \e id 2314 /// 2315 /// Gives back the item belonging to the given \e range \e id. 2278 2316 Item operator()(int id) const { 2279 2317 return _inv_map[id]; … … 2289 2327 /// \brief The inverse map type of RangeIdMap. 2290 2328 /// 2291 /// The inverse map type of RangeIdMap. 2329 /// The inverse map type of RangeIdMap. The subscript operator gives 2330 /// back an item by its \e range \e id. 2331 /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. 2292 2332 class InverseMap { 2293 2333 public: … … 2307 2347 /// 2308 2348 /// Subscript operator. It gives back the item 2309 /// that the descriptorcurrently belongs to.2349 /// that the given \e range \e id currently belongs to. 2310 2350 Value operator[](const Key& key) const { 2311 2351 return _inverted(key); … … 2325 2365 /// \brief Gives back the inverse of the map. 2326 2366 /// 2327 /// Gives back the inverse of the map.2367 /// Gives back the inverse of the RangeIdMap. 2328 2368 const InverseMap inverse() const { 2329 2369 return InverseMap(*this); 2330 2370 } 2371 }; 2372 2373 /// \brief Returns a \c RangeIdMap class. 2374 /// 2375 /// This function just returns an \c RangeIdMap class. 2376 /// \relates RangeIdMap 2377 template <typename K, typename GR> 2378 inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) { 2379 return RangeIdMap<GR, K>(graph); 2380 } 2381 2382 /// \brief Dynamic iterable \c bool map. 2383 /// 2384 /// This class provides a special graph map type which can store a 2385 /// \c bool value for graph items (\c Node, \c Arc or \c Edge). 2386 /// For both \c true and \c false values it is possible to iterate on 2387 /// the keys mapped to the value. 2388 /// 2389 /// This type is a reference map, so it can be modified with the 2390 /// subscript operator. 2391 /// 2392 /// \tparam GR The graph type. 2393 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2394 /// \c GR::Edge). 2395 /// 2396 /// \see IterableIntMap, IterableValueMap 2397 /// \see CrossRefMap 2398 template <typename GR, typename K> 2399 class IterableBoolMap 2400 : protected ItemSetTraits<GR, K>::template Map<int>::Type { 2401 private: 2402 typedef GR Graph; 2403 2404 typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt; 2405 typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent; 2406 2407 std::vector<K> _array; 2408 int _sep; 2409 2410 public: 2411 2412 /// Indicates that the map is reference map. 2413 typedef True ReferenceMapTag; 2414 2415 /// The key type 2416 typedef K Key; 2417 /// The value type 2418 typedef bool Value; 2419 /// The const reference type. 2420 typedef const Value& ConstReference; 2421 2422 private: 2423 2424 int position(const Key& key) const { 2425 return Parent::operator[](key); 2426 } 2427 2428 public: 2429 2430 /// \brief Reference to the value of the map. 2431 /// 2432 /// This class is similar to the \c bool type. It can be converted to 2433 /// \c bool and it provides the same operators. 2434 class Reference { 2435 friend class IterableBoolMap; 2436 private: 2437 Reference(IterableBoolMap& map, const Key& key) 2438 : _key(key), _map(map) {} 2439 public: 2440 2441 Reference& operator=(const Reference& value) { 2442 _map.set(_key, static_cast<bool>(value)); 2443 return *this; 2444 } 2445 2446 operator bool() const { 2447 return static_cast<const IterableBoolMap&>(_map)[_key]; 2448 } 2449 2450 Reference& operator=(bool value) { 2451 _map.set(_key, value); 2452 return *this; 2453 } 2454 Reference& operator&=(bool value) { 2455 _map.set(_key, _map[_key] & value); 2456 return *this; 2457 } 2458 Reference& operator|=(bool value) { 2459 _map.set(_key, _map[_key] | value); 2460 return *this; 2461 } 2462 Reference& operator^=(bool value) { 2463 _map.set(_key, _map[_key] ^ value); 2464 return *this; 2465 } 2466 private: 2467 Key _key; 2468 IterableBoolMap& _map; 2469 }; 2470 2471 /// \brief Constructor of the map with a default value. 2472 /// 2473 /// Constructor of the map with a default value. 2474 explicit IterableBoolMap(const Graph& graph, bool def = false) 2475 : Parent(graph) { 2476 typename Parent::Notifier* nf = Parent::notifier(); 2477 Key it; 2478 for (nf->first(it); it != INVALID; nf->next(it)) { 2479 Parent::set(it, _array.size()); 2480 _array.push_back(it); 2481 } 2482 _sep = (def ? _array.size() : 0); 2483 } 2484 2485 /// \brief Const subscript operator of the map. 2486 /// 2487 /// Const subscript operator of the map. 2488 bool operator[](const Key& key) const { 2489 return position(key) < _sep; 2490 } 2491 2492 /// \brief Subscript operator of the map. 2493 /// 2494 /// Subscript operator of the map. 2495 Reference operator[](const Key& key) { 2496 return Reference(*this, key); 2497 } 2498 2499 /// \brief Set operation of the map. 2500 /// 2501 /// Set operation of the map. 2502 void set(const Key& key, bool value) { 2503 int pos = position(key); 2504 if (value) { 2505 if (pos < _sep) return; 2506 Key tmp = _array[_sep]; 2507 _array[_sep] = key; 2508 Parent::set(key, _sep); 2509 _array[pos] = tmp; 2510 Parent::set(tmp, pos); 2511 ++_sep; 2512 } else { 2513 if (pos >= _sep) return; 2514 --_sep; 2515 Key tmp = _array[_sep]; 2516 _array[_sep] = key; 2517 Parent::set(key, _sep); 2518 _array[pos] = tmp; 2519 Parent::set(tmp, pos); 2520 } 2521 } 2522 2523 /// \brief Set all items. 2524 /// 2525 /// Set all items in the map. 2526 /// \note Constant time operation. 2527 void setAll(bool value) { 2528 _sep = (value ? _array.size() : 0); 2529 } 2530 2531 /// \brief Returns the number of the keys mapped to \c true. 2532 /// 2533 /// Returns the number of the keys mapped to \c true. 2534 int trueNum() const { 2535 return _sep; 2536 } 2537 2538 /// \brief Returns the number of the keys mapped to \c false. 2539 /// 2540 /// Returns the number of the keys mapped to \c false. 2541 int falseNum() const { 2542 return _array.size() - _sep; 2543 } 2544 2545 /// \brief Iterator for the keys mapped to \c true. 2546 /// 2547 /// Iterator for the keys mapped to \c true. It works 2548 /// like a graph item iterator, it can be converted to 2549 /// the key type of the map, incremented with \c ++ operator, and 2550 /// if the iterator leaves the last valid key, it will be equal to 2551 /// \c INVALID. 2552 class TrueIt : public Key { 2553 public: 2554 typedef Key Parent; 2555 2556 /// \brief Creates an iterator. 2557 /// 2558 /// Creates an iterator. It iterates on the 2559 /// keys mapped to \c true. 2560 /// \param map The IterableBoolMap. 2561 explicit TrueIt(const IterableBoolMap& map) 2562 : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), 2563 _map(&map) {} 2564 2565 /// \brief Invalid constructor \& conversion. 2566 /// 2567 /// This constructor initializes the iterator to be invalid. 2568 /// \sa Invalid for more details. 2569 TrueIt(Invalid) : Parent(INVALID), _map(0) {} 2570 2571 /// \brief Increment operator. 2572 /// 2573 /// Increment operator. 2574 TrueIt& operator++() { 2575 int pos = _map->position(*this); 2576 Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID); 2577 return *this; 2578 } 2579 2580 private: 2581 const IterableBoolMap* _map; 2582 }; 2583 2584 /// \brief Iterator for the keys mapped to \c false. 2585 /// 2586 /// Iterator for the keys mapped to \c false. It works 2587 /// like a graph item iterator, it can be converted to 2588 /// the key type of the map, incremented with \c ++ operator, and 2589 /// if the iterator leaves the last valid key, it will be equal to 2590 /// \c INVALID. 2591 class FalseIt : public Key { 2592 public: 2593 typedef Key Parent; 2594 2595 /// \brief Creates an iterator. 2596 /// 2597 /// Creates an iterator. It iterates on the 2598 /// keys mapped to \c false. 2599 /// \param map The IterableBoolMap. 2600 explicit FalseIt(const IterableBoolMap& map) 2601 : Parent(map._sep < int(map._array.size()) ? 2602 map._array.back() : INVALID), _map(&map) {} 2603 2604 /// \brief Invalid constructor \& conversion. 2605 /// 2606 /// This constructor initializes the iterator to be invalid. 2607 /// \sa Invalid for more details. 2608 FalseIt(Invalid) : Parent(INVALID), _map(0) {} 2609 2610 /// \brief Increment operator. 2611 /// 2612 /// Increment operator. 2613 FalseIt& operator++() { 2614 int pos = _map->position(*this); 2615 Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID); 2616 return *this; 2617 } 2618 2619 private: 2620 const IterableBoolMap* _map; 2621 }; 2622 2623 /// \brief Iterator for the keys mapped to a given value. 2624 /// 2625 /// Iterator for the keys mapped to a given value. It works 2626 /// like a graph item iterator, it can be converted to 2627 /// the key type of the map, incremented with \c ++ operator, and 2628 /// if the iterator leaves the last valid key, it will be equal to 2629 /// \c INVALID. 2630 class ItemIt : public Key { 2631 public: 2632 typedef Key Parent; 2633 2634 /// \brief Creates an iterator with a value. 2635 /// 2636 /// Creates an iterator with a value. It iterates on the 2637 /// keys mapped to the given value. 2638 /// \param map The IterableBoolMap. 2639 /// \param value The value. 2640 ItemIt(const IterableBoolMap& map, bool value) 2641 : Parent(value ? 2642 (map._sep > 0 ? 2643 map._array[map._sep - 1] : INVALID) : 2644 (map._sep < int(map._array.size()) ? 2645 map._array.back() : INVALID)), _map(&map) {} 2646 2647 /// \brief Invalid constructor \& conversion. 2648 /// 2649 /// This constructor initializes the iterator to be invalid. 2650 /// \sa Invalid for more details. 2651 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 2652 2653 /// \brief Increment operator. 2654 /// 2655 /// Increment operator. 2656 ItemIt& operator++() { 2657 int pos = _map->position(*this); 2658 int _sep = pos >= _map->_sep ? _map->_sep : 0; 2659 Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID); 2660 return *this; 2661 } 2662 2663 private: 2664 const IterableBoolMap* _map; 2665 }; 2666 2667 protected: 2668 2669 virtual void add(const Key& key) { 2670 Parent::add(key); 2671 Parent::set(key, _array.size()); 2672 _array.push_back(key); 2673 } 2674 2675 virtual void add(const std::vector<Key>& keys) { 2676 Parent::add(keys); 2677 for (int i = 0; i < int(keys.size()); ++i) { 2678 Parent::set(keys[i], _array.size()); 2679 _array.push_back(keys[i]); 2680 } 2681 } 2682 2683 virtual void erase(const Key& key) { 2684 int pos = position(key); 2685 if (pos < _sep) { 2686 --_sep; 2687 Parent::set(_array[_sep], pos); 2688 _array[pos] = _array[_sep]; 2689 Parent::set(_array.back(), _sep); 2690 _array[_sep] = _array.back(); 2691 _array.pop_back(); 2692 } else { 2693 Parent::set(_array.back(), pos); 2694 _array[pos] = _array.back(); 2695 _array.pop_back(); 2696 } 2697 Parent::erase(key); 2698 } 2699 2700 virtual void erase(const std::vector<Key>& keys) { 2701 for (int i = 0; i < int(keys.size()); ++i) { 2702 int pos = position(keys[i]); 2703 if (pos < _sep) { 2704 --_sep; 2705 Parent::set(_array[_sep], pos); 2706 _array[pos] = _array[_sep]; 2707 Parent::set(_array.back(), _sep); 2708 _array[_sep] = _array.back(); 2709 _array.pop_back(); 2710 } else { 2711 Parent::set(_array.back(), pos); 2712 _array[pos] = _array.back(); 2713 _array.pop_back(); 2714 } 2715 } 2716 Parent::erase(keys); 2717 } 2718 2719 virtual void build() { 2720 Parent::build(); 2721 typename Parent::Notifier* nf = Parent::notifier(); 2722 Key it; 2723 for (nf->first(it); it != INVALID; nf->next(it)) { 2724 Parent::set(it, _array.size()); 2725 _array.push_back(it); 2726 } 2727 _sep = 0; 2728 } 2729 2730 virtual void clear() { 2731 _array.clear(); 2732 _sep = 0; 2733 Parent::clear(); 2734 } 2735 2736 }; 2737 2738 2739 namespace _maps_bits { 2740 template <typename Item> 2741 struct IterableIntMapNode { 2742 IterableIntMapNode() : value(-1) {} 2743 IterableIntMapNode(int _value) : value(_value) {} 2744 Item prev, next; 2745 int value; 2746 }; 2747 } 2748 2749 /// \brief Dynamic iterable integer map. 2750 /// 2751 /// This class provides a special graph map type which can store an 2752 /// integer value for graph items (\c Node, \c Arc or \c Edge). 2753 /// For each non-negative value it is possible to iterate on the keys 2754 /// mapped to the value. 2755 /// 2756 /// This map is intended to be used with small integer values, for which 2757 /// it is efficient, and supports iteration only for non-negative values. 2758 /// If you need large values and/or iteration for negative integers, 2759 /// consider to use \ref IterableValueMap instead. 2760 /// 2761 /// This type is a reference map, so it can be modified with the 2762 /// subscript operator. 2763 /// 2764 /// \note The size of the data structure depends on the largest 2765 /// value in the map. 2766 /// 2767 /// \tparam GR The graph type. 2768 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2769 /// \c GR::Edge). 2770 /// 2771 /// \see IterableBoolMap, IterableValueMap 2772 /// \see CrossRefMap 2773 template <typename GR, typename K> 2774 class IterableIntMap 2775 : protected ItemSetTraits<GR, K>:: 2776 template Map<_maps_bits::IterableIntMapNode<K> >::Type { 2777 public: 2778 typedef typename ItemSetTraits<GR, K>:: 2779 template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent; 2780 2781 /// The key type 2782 typedef K Key; 2783 /// The value type 2784 typedef int Value; 2785 /// The graph type 2786 typedef GR Graph; 2787 2788 /// \brief Constructor of the map. 2789 /// 2790 /// Constructor of the map. It sets all values to -1. 2791 explicit IterableIntMap(const Graph& graph) 2792 : Parent(graph) {} 2793 2794 /// \brief Constructor of the map with a given value. 2795 /// 2796 /// Constructor of the map with a given value. 2797 explicit IterableIntMap(const Graph& graph, int value) 2798 : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) { 2799 if (value >= 0) { 2800 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 2801 lace(it); 2802 } 2803 } 2804 } 2805 2806 private: 2807 2808 void unlace(const Key& key) { 2809 typename Parent::Value& node = Parent::operator[](key); 2810 if (node.value < 0) return; 2811 if (node.prev != INVALID) { 2812 Parent::operator[](node.prev).next = node.next; 2813 } else { 2814 _first[node.value] = node.next; 2815 } 2816 if (node.next != INVALID) { 2817 Parent::operator[](node.next).prev = node.prev; 2818 } 2819 while (!_first.empty() && _first.back() == INVALID) { 2820 _first.pop_back(); 2821 } 2822 } 2823 2824 void lace(const Key& key) { 2825 typename Parent::Value& node = Parent::operator[](key); 2826 if (node.value < 0) return; 2827 if (node.value >= int(_first.size())) { 2828 _first.resize(node.value + 1, INVALID); 2829 } 2830 node.prev = INVALID; 2831 node.next = _first[node.value]; 2832 if (node.next != INVALID) { 2833 Parent::operator[](node.next).prev = key; 2834 } 2835 _first[node.value] = key; 2836 } 2837 2838 public: 2839 2840 /// Indicates that the map is reference map. 2841 typedef True ReferenceMapTag; 2842 2843 /// \brief Reference to the value of the map. 2844 /// 2845 /// This class is similar to the \c int type. It can 2846 /// be converted to \c int and it has the same operators. 2847 class Reference { 2848 friend class IterableIntMap; 2849 private: 2850 Reference(IterableIntMap& map, const Key& key) 2851 : _key(key), _map(map) {} 2852 public: 2853 2854 Reference& operator=(const Reference& value) { 2855 _map.set(_key, static_cast<const int&>(value)); 2856 return *this; 2857 } 2858 2859 operator const int&() const { 2860 return static_cast<const IterableIntMap&>(_map)[_key]; 2861 } 2862 2863 Reference& operator=(int value) { 2864 _map.set(_key, value); 2865 return *this; 2866 } 2867 Reference& operator++() { 2868 _map.set(_key, _map[_key] + 1); 2869 return *this; 2870 } 2871 int operator++(int) { 2872 int value = _map[_key]; 2873 _map.set(_key, value + 1); 2874 return value; 2875 } 2876 Reference& operator--() { 2877 _map.set(_key, _map[_key] - 1); 2878 return *this; 2879 } 2880 int operator--(int) { 2881 int value = _map[_key]; 2882 _map.set(_key, value - 1); 2883 return value; 2884 } 2885 Reference& operator+=(int value) { 2886 _map.set(_key, _map[_key] + value); 2887 return *this; 2888 } 2889 Reference& operator-=(int value) { 2890 _map.set(_key, _map[_key] - value); 2891 return *this; 2892 } 2893 Reference& operator*=(int value) { 2894 _map.set(_key, _map[_key] * value); 2895 return *this; 2896 } 2897 Reference& operator/=(int value) { 2898 _map.set(_key, _map[_key] / value); 2899 return *this; 2900 } 2901 Reference& operator%=(int value) { 2902 _map.set(_key, _map[_key] % value); 2903 return *this; 2904 } 2905 Reference& operator&=(int value) { 2906 _map.set(_key, _map[_key] & value); 2907 return *this; 2908 } 2909 Reference& operator|=(int value) { 2910 _map.set(_key, _map[_key] | value); 2911 return *this; 2912 } 2913 Reference& operator^=(int value) { 2914 _map.set(_key, _map[_key] ^ value); 2915 return *this; 2916 } 2917 Reference& operator<<=(int value) { 2918 _map.set(_key, _map[_key] << value); 2919 return *this; 2920 } 2921 Reference& operator>>=(int value) { 2922 _map.set(_key, _map[_key] >> value); 2923 return *this; 2924 } 2925 2926 private: 2927 Key _key; 2928 IterableIntMap& _map; 2929 }; 2930 2931 /// The const reference type. 2932 typedef const Value& ConstReference; 2933 2934 /// \brief Gives back the maximal value plus one. 2935 /// 2936 /// Gives back the maximal value plus one. 2937 int size() const { 2938 return _first.size(); 2939 } 2940 2941 /// \brief Set operation of the map. 2942 /// 2943 /// Set operation of the map. 2944 void set(const Key& key, const Value& value) { 2945 unlace(key); 2946 Parent::operator[](key).value = value; 2947 lace(key); 2948 } 2949 2950 /// \brief Const subscript operator of the map. 2951 /// 2952 /// Const subscript operator of the map. 2953 const Value& operator[](const Key& key) const { 2954 return Parent::operator[](key).value; 2955 } 2956 2957 /// \brief Subscript operator of the map. 2958 /// 2959 /// Subscript operator of the map. 2960 Reference operator[](const Key& key) { 2961 return Reference(*this, key); 2962 } 2963 2964 /// \brief Iterator for the keys with the same value. 2965 /// 2966 /// Iterator for the keys with the same value. It works 2967 /// like a graph item iterator, it can be converted to 2968 /// the item type of the map, incremented with \c ++ operator, and 2969 /// if the iterator leaves the last valid item, it will be equal to 2970 /// \c INVALID. 2971 class ItemIt : public Key { 2972 public: 2973 typedef Key Parent; 2974 2975 /// \brief Invalid constructor \& conversion. 2976 /// 2977 /// This constructor initializes the iterator to be invalid. 2978 /// \sa Invalid for more details. 2979 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 2980 2981 /// \brief Creates an iterator with a value. 2982 /// 2983 /// Creates an iterator with a value. It iterates on the 2984 /// keys mapped to the given value. 2985 /// \param map The IterableIntMap. 2986 /// \param value The value. 2987 ItemIt(const IterableIntMap& map, int value) : _map(&map) { 2988 if (value < 0 || value >= int(_map->_first.size())) { 2989 Parent::operator=(INVALID); 2990 } else { 2991 Parent::operator=(_map->_first[value]); 2992 } 2993 } 2994 2995 /// \brief Increment operator. 2996 /// 2997 /// Increment operator. 2998 ItemIt& operator++() { 2999 Parent::operator=(_map->IterableIntMap::Parent:: 3000 operator[](static_cast<Parent&>(*this)).next); 3001 return *this; 3002 } 3003 3004 private: 3005 const IterableIntMap* _map; 3006 }; 3007 3008 protected: 3009 3010 virtual void erase(const Key& key) { 3011 unlace(key); 3012 Parent::erase(key); 3013 } 3014 3015 virtual void erase(const std::vector<Key>& keys) { 3016 for (int i = 0; i < int(keys.size()); ++i) { 3017 unlace(keys[i]); 3018 } 3019 Parent::erase(keys); 3020 } 3021 3022 virtual void clear() { 3023 _first.clear(); 3024 Parent::clear(); 3025 } 3026 3027 private: 3028 std::vector<Key> _first; 3029 }; 3030 3031 namespace _maps_bits { 3032 template <typename Item, typename Value> 3033 struct IterableValueMapNode { 3034 IterableValueMapNode(Value _value = Value()) : value(_value) {} 3035 Item prev, next; 3036 Value value; 3037 }; 3038 } 3039 3040 /// \brief Dynamic iterable map for comparable values. 3041 /// 3042 /// This class provides a special graph map type which can store a 3043 /// comparable value for graph items (\c Node, \c Arc or \c Edge). 3044 /// For each value it is possible to iterate on the keys mapped to 3045 /// the value (\c ItemIt), and the values of the map can be accessed 3046 /// with an STL compatible forward iterator (\c ValueIt). 3047 /// The map stores a linked list for each value, which contains 3048 /// the items mapped to the value, and the used values are stored 3049 /// in balanced binary tree (\c std::map). 3050 /// 3051 /// \ref IterableBoolMap and \ref IterableIntMap are similar classes 3052 /// specialized for \c bool and \c int values, respectively. 3053 /// 3054 /// This type is not reference map, so it cannot be modified with 3055 /// the subscript operator. 3056 /// 3057 /// \tparam GR The graph type. 3058 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 3059 /// \c GR::Edge). 3060 /// \tparam V The value type of the map. It can be any comparable 3061 /// value type. 3062 /// 3063 /// \see IterableBoolMap, IterableIntMap 3064 /// \see CrossRefMap 3065 template <typename GR, typename K, typename V> 3066 class IterableValueMap 3067 : protected ItemSetTraits<GR, K>:: 3068 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type { 3069 public: 3070 typedef typename ItemSetTraits<GR, K>:: 3071 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent; 3072 3073 /// The key type 3074 typedef K Key; 3075 /// The value type 3076 typedef V Value; 3077 /// The graph type 3078 typedef GR Graph; 3079 3080 public: 3081 3082 /// \brief Constructor of the map with a given value. 3083 /// 3084 /// Constructor of the map with a given value. 3085 explicit IterableValueMap(const Graph& graph, 3086 const Value& value = Value()) 3087 : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) { 3088 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 3089 lace(it); 3090 } 3091 } 3092 3093 protected: 3094 3095 void unlace(const Key& key) { 3096 typename Parent::Value& node = Parent::operator[](key); 3097 if (node.prev != INVALID) { 3098 Parent::operator[](node.prev).next = node.next; 3099 } else { 3100 if (node.next != INVALID) { 3101 _first[node.value] = node.next; 3102 } else { 3103 _first.erase(node.value); 3104 } 3105 } 3106 if (node.next != INVALID) { 3107 Parent::operator[](node.next).prev = node.prev; 3108 } 3109 } 3110 3111 void lace(const Key& key) { 3112 typename Parent::Value& node = Parent::operator[](key); 3113 typename std::map<Value, Key>::iterator it = _first.find(node.value); 3114 if (it == _first.end()) { 3115 node.prev = node.next = INVALID; 3116 _first.insert(std::make_pair(node.value, key)); 3117 } else { 3118 node.prev = INVALID; 3119 node.next = it->second; 3120 if (node.next != INVALID) { 3121 Parent::operator[](node.next).prev = key; 3122 } 3123 it->second = key; 3124 } 3125 } 3126 3127 public: 3128 3129 /// \brief Forward iterator for values. 3130 /// 3131 /// This iterator is an STL compatible forward 3132 /// iterator on the values of the map. The values can 3133 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 3134 class ValueIt 3135 : public std::iterator<std::forward_iterator_tag, Value> { 3136 friend class IterableValueMap; 3137 private: 3138 ValueIt(typename std::map<Value, Key>::const_iterator _it) 3139 : it(_it) {} 3140 public: 3141 3142 /// Constructor 3143 ValueIt() {} 3144 3145 /// \e 3146 ValueIt& operator++() { ++it; return *this; } 3147 /// \e 3148 ValueIt operator++(int) { 3149 ValueIt tmp(*this); 3150 operator++(); 3151 return tmp; 3152 } 3153 3154 /// \e 3155 const Value& operator*() const { return it->first; } 3156 /// \e 3157 const Value* operator->() const { return &(it->first); } 3158 3159 /// \e 3160 bool operator==(ValueIt jt) const { return it == jt.it; } 3161 /// \e 3162 bool operator!=(ValueIt jt) const { return it != jt.it; } 3163 3164 private: 3165 typename std::map<Value, Key>::const_iterator it; 3166 }; 3167 3168 /// \brief Returns an iterator to the first value. 3169 /// 3170 /// Returns an STL compatible iterator to the 3171 /// first value of the map. The values of the 3172 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3173 /// range. 3174 ValueIt beginValue() const { 3175 return ValueIt(_first.begin()); 3176 } 3177 3178 /// \brief Returns an iterator after the last value. 3179 /// 3180 /// Returns an STL compatible iterator after the 3181 /// last value of the map. The values of the 3182 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3183 /// range. 3184 ValueIt endValue() const { 3185 return ValueIt(_first.end()); 3186 } 3187 3188 /// \brief Set operation of the map. 3189 /// 3190 /// Set operation of the map. 3191 void set(const Key& key, const Value& value) { 3192 unlace(key); 3193 Parent::operator[](key).value = value; 3194 lace(key); 3195 } 3196 3197 /// \brief Const subscript operator of the map. 3198 /// 3199 /// Const subscript operator of the map. 3200 const Value& operator[](const Key& key) const { 3201 return Parent::operator[](key).value; 3202 } 3203 3204 /// \brief Iterator for the keys with the same value. 3205 /// 3206 /// Iterator for the keys with the same value. It works 3207 /// like a graph item iterator, it can be converted to 3208 /// the item type of the map, incremented with \c ++ operator, and 3209 /// if the iterator leaves the last valid item, it will be equal to 3210 /// \c INVALID. 3211 class ItemIt : public Key { 3212 public: 3213 typedef Key Parent; 3214 3215 /// \brief Invalid constructor \& conversion. 3216 /// 3217 /// This constructor initializes the iterator to be invalid. 3218 /// \sa Invalid for more details. 3219 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 3220 3221 /// \brief Creates an iterator with a value. 3222 /// 3223 /// Creates an iterator with a value. It iterates on the 3224 /// keys which have the given value. 3225 /// \param map The IterableValueMap 3226 /// \param value The value 3227 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { 3228 typename std::map<Value, Key>::const_iterator it = 3229 map._first.find(value); 3230 if (it == map._first.end()) { 3231 Parent::operator=(INVALID); 3232 } else { 3233 Parent::operator=(it->second); 3234 } 3235 } 3236 3237 /// \brief Increment operator. 3238 /// 3239 /// Increment Operator. 3240 ItemIt& operator++() { 3241 Parent::operator=(_map->IterableValueMap::Parent:: 3242 operator[](static_cast<Parent&>(*this)).next); 3243 return *this; 3244 } 3245 3246 3247 private: 3248 const IterableValueMap* _map; 3249 }; 3250 3251 protected: 3252 3253 virtual void add(const Key& key) { 3254 Parent::add(key); 3255 unlace(key); 3256 } 3257 3258 virtual void add(const std::vector<Key>& keys) { 3259 Parent::add(keys); 3260 for (int i = 0; i < int(keys.size()); ++i) { 3261 lace(keys[i]); 3262 } 3263 } 3264 3265 virtual void erase(const Key& key) { 3266 unlace(key); 3267 Parent::erase(key); 3268 } 3269 3270 virtual void erase(const std::vector<Key>& keys) { 3271 for (int i = 0; i < int(keys.size()); ++i) { 3272 unlace(keys[i]); 3273 } 3274 Parent::erase(keys); 3275 } 3276 3277 virtual void build() { 3278 Parent::build(); 3279 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 3280 lace(it); 3281 } 3282 } 3283 3284 virtual void clear() { 3285 _first.clear(); 3286 Parent::clear(); 3287 } 3288 3289 private: 3290 std::map<Value, Key> _first; 2331 3291 }; 2332 3292 … … 2341 3301 public: 2342 3302 2343 /// \e3303 /// The key type (the \c Arc type of the digraph). 2344 3304 typedef typename GR::Arc Key; 2345 /// \e3305 /// The value type (the \c Node type of the digraph). 2346 3306 typedef typename GR::Node Value; 2347 3307 … … 2382 3342 public: 2383 3343 2384 /// \e3344 /// The key type (the \c Arc type of the digraph). 2385 3345 typedef typename GR::Arc Key; 2386 /// \e3346 /// The value type (the \c Node type of the digraph). 2387 3347 typedef typename GR::Node Value; 2388 3348 … … 2424 3384 public: 2425 3385 3386 /// The key type (the \c Edge type of the digraph). 3387 typedef typename GR::Edge Key; 3388 /// The value type (the \c Arc type of the digraph). 2426 3389 typedef typename GR::Arc Value; 2427 typedef typename GR::Edge Key;2428 3390 2429 3391 /// \brief Constructor … … 2464 3426 public: 2465 3427 3428 /// The key type (the \c Edge type of the digraph). 3429 typedef typename GR::Edge Key; 3430 /// The value type (the \c Arc type of the digraph). 2466 3431 typedef typename GR::Arc Value; 2467 typedef typename GR::Edge Key;2468 3432 2469 3433 /// \brief Constructor … … 2500 3464 /// whenever the digraph changes. 2501 3465 /// 2502 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3466 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2503 3467 /// may provide alternative ways to modify the digraph. 2504 3468 /// The correct behavior of InDegMap is not guarantied if these additional … … 2516 3480 2517 3481 public: 2518 3482 2519 3483 /// The graph type of InDegMap 2520 3484 typedef GR Graph; … … 2630 3594 /// whenever the digraph changes. 2631 3595 /// 2632 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3596 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2633 3597 /// may provide alternative ways to modify the digraph. 2634 3598 /// The correct behavior of OutDegMap is not guarantied if these additional -
lemon/min_cost_arborescence.h
r625 r713 489 489 /// The simplest way to execute the algorithm is to use 490 490 /// one of the member functions called \c run(...). \n 491 /// If you need morecontrol on the execution,492 /// first you must call \ref init(), then you can add several491 /// If you need better control on the execution, 492 /// you have to call \ref init() first, then you can add several 493 493 /// source nodes with \ref addSource(). 494 494 /// Finally \ref start() will perform the arborescence -
lemon/network_simplex.h
r663 r730 162 162 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 163 163 164 typedef std::vector<Arc> ArcVector;165 typedef std::vector<Node> NodeVector;166 164 typedef std::vector<int> IntVector; 167 165 typedef std::vector<bool> BoolVector; … … 365 363 Cost c, min = 0; 366 364 int cnt = _block_size; 367 int e , min_arc = _next_arc;365 int e; 368 366 for (e = _next_arc; e < _search_arc_num; ++e) { 369 367 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 370 368 if (c < min) { 371 369 min = c; 372 min_arc = e;370 _in_arc = e; 373 371 } 374 372 if (--cnt == 0) { 375 if (min < 0) break;373 if (min < 0) goto search_end; 376 374 cnt = _block_size; 377 375 } 378 376 } 379 if (min == 0 || cnt > 0) { 380 for (e = 0; e < _next_arc; ++e) { 381 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 382 if (c < min) { 383 min = c; 384 min_arc = e; 385 } 386 if (--cnt == 0) { 387 if (min < 0) break; 388 cnt = _block_size; 389 } 377 for (e = 0; e < _next_arc; ++e) { 378 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 379 if (c < min) { 380 min = c; 381 _in_arc = e; 382 } 383 if (--cnt == 0) { 384 if (min < 0) goto search_end; 385 cnt = _block_size; 390 386 } 391 387 } 392 388 if (min >= 0) return false; 393 _in_arc = min_arc; 389 390 search_end: 394 391 _next_arc = e; 395 392 return true; … … 429 426 { 430 427 // The main parameters of the pivot rule 431 const double LIST_LENGTH_FACTOR = 1.0;428 const double LIST_LENGTH_FACTOR = 0.25; 432 429 const int MIN_LIST_LENGTH = 10; 433 430 const double MINOR_LIMIT_FACTOR = 0.1; … … 446 443 bool findEnteringArc() { 447 444 Cost min, c; 448 int e , min_arc = _next_arc;445 int e; 449 446 if (_curr_length > 0 && _minor_count < _minor_limit) { 450 447 // Minor iteration: select the best eligible arc from the … … 457 454 if (c < min) { 458 455 min = c; 459 min_arc = e;456 _in_arc = e; 460 457 } 461 if (c >= 0) {458 else if (c >= 0) { 462 459 _candidates[i--] = _candidates[--_curr_length]; 463 460 } 464 461 } 465 if (min < 0) { 466 _in_arc = min_arc; 467 return true; 468 } 462 if (min < 0) return true; 469 463 } 470 464 … … 478 472 if (c < min) { 479 473 min = c; 480 min_arc = e;474 _in_arc = e; 481 475 } 482 if (_curr_length == _list_length) break; 483 } 484 } 485 if (_curr_length < _list_length) { 486 for (e = 0; e < _next_arc; ++e) { 487 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 488 if (c < 0) { 489 _candidates[_curr_length++] = e; 490 if (c < min) { 491 min = c; 492 min_arc = e; 493 } 494 if (_curr_length == _list_length) break; 476 if (_curr_length == _list_length) goto search_end; 477 } 478 } 479 for (e = 0; e < _next_arc; ++e) { 480 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 481 if (c < 0) { 482 _candidates[_curr_length++] = e; 483 if (c < min) { 484 min = c; 485 _in_arc = e; 495 486 } 487 if (_curr_length == _list_length) goto search_end; 496 488 } 497 489 } 498 490 if (_curr_length == 0) return false; 491 492 search_end: 499 493 _minor_count = 1; 500 _in_arc = min_arc;501 494 _next_arc = e; 502 495 return true; … … 550 543 { 551 544 // The main parameters of the pivot rule 552 const double BLOCK_SIZE_FACTOR = 1. 5;545 const double BLOCK_SIZE_FACTOR = 1.0; 553 546 const int MIN_BLOCK_SIZE = 10; 554 547 const double HEAD_LENGTH_FACTOR = 0.1; … … 579 572 // Extend the list 580 573 int cnt = _block_size; 581 int last_arc = 0;582 574 int limit = _head_length; 583 575 584 for ( inte = _next_arc; e < _search_arc_num; ++e) {576 for (e = _next_arc; e < _search_arc_num; ++e) { 585 577 _cand_cost[e] = _state[e] * 586 578 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 587 579 if (_cand_cost[e] < 0) { 588 580 _candidates[_curr_length++] = e; 589 last_arc = e;590 581 } 591 582 if (--cnt == 0) { 592 if (_curr_length > limit) break;583 if (_curr_length > limit) goto search_end; 593 584 limit = 0; 594 585 cnt = _block_size; 595 586 } 596 587 } 597 if (_curr_length <= limit) { 598 for (int e = 0; e < _next_arc; ++e) { 599 _cand_cost[e] = _state[e] * 600 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 601 if (_cand_cost[e] < 0) { 602 _candidates[_curr_length++] = e; 603 last_arc = e; 604 } 605 if (--cnt == 0) { 606 if (_curr_length > limit) break; 607 limit = 0; 608 cnt = _block_size; 609 } 588 for (e = 0; e < _next_arc; ++e) { 589 _cand_cost[e] = _state[e] * 590 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 591 if (_cand_cost[e] < 0) { 592 _candidates[_curr_length++] = e; 593 } 594 if (--cnt == 0) { 595 if (_curr_length > limit) goto search_end; 596 limit = 0; 597 cnt = _block_size; 610 598 } 611 599 } 612 600 if (_curr_length == 0) return false; 613 _next_arc = last_arc + 1; 601 602 search_end: 614 603 615 604 // Make heap of the candidate list (approximating a partial sort) … … 619 608 // Pop the first element of the heap 620 609 _in_arc = _candidates[0]; 610 _next_arc = e; 621 611 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 622 612 _sort_func ); … … 634 624 /// 635 625 /// \param graph The digraph the algorithm runs on. 636 NetworkSimplex(const GR& graph) : 626 /// \param arc_mixing Indicate if the arcs have to be stored in a 627 /// mixed order in the internal data structure. 628 /// In special cases, it could lead to better overall performance, 629 /// but it is usually slower. Therefore it is disabled by default. 630 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 637 631 _graph(graph), _node_id(graph), _arc_id(graph), 638 632 INF(std::numeric_limits<Value>::has_infinity ? … … 672 666 _state.resize(max_arc_num); 673 667 674 // Copy the graph (store the arcs in a mixed order)668 // Copy the graph 675 669 int i = 0; 676 670 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 677 671 _node_id[n] = i; 678 672 } 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 i = 0; 681 for (ArcIt a(_graph); a != INVALID; ++a) { 682 _arc_id[a] = i; 683 _source[i] = _node_id[_graph.source(a)]; 684 _target[i] = _node_id[_graph.target(a)]; 685 if ((i += k) >= _arc_num) i = (i % k) + 1; 673 if (arc_mixing) { 674 // Store the arcs in a mixed order 675 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 676 int i = 0, j = 0; 677 for (ArcIt a(_graph); a != INVALID; ++a) { 678 _arc_id[a] = i; 679 _source[i] = _node_id[_graph.source(a)]; 680 _target[i] = _node_id[_graph.target(a)]; 681 if ((i += k) >= _arc_num) i = ++j; 682 } 683 } else { 684 // Store the arcs in the original order 685 int i = 0; 686 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 687 _arc_id[a] = i; 688 _source[i] = _node_id[_graph.source(a)]; 689 _target[i] = _node_id[_graph.target(a)]; 690 } 686 691 } 687 692 688 // Initialize maps 689 for (int i = 0; i != _node_num; ++i) { 690 _supply[i] = 0; 691 } 692 for (int i = 0; i != _arc_num; ++i) { 693 _lower[i] = 0; 694 _upper[i] = INF; 695 _cost[i] = 1; 696 } 697 _have_lower = false; 698 _stype = GEQ; 693 // Reset parameters 694 reset(); 699 695 } 700 696 … … 769 765 /// If neither this function nor \ref stSupply() is used before 770 766 /// calling \ref run(), the supply of each node will be set to zero. 771 /// (It makes sense only if non-zero lower bounds are given.)772 767 /// 773 768 /// \param map A node map storing the supply values. … … 790 785 /// If neither this function nor \ref supplyMap() is used before 791 786 /// calling \ref run(), the supply of each node will be set to zero. 792 /// (It makes sense only if non-zero lower bounds are given.)793 787 /// 794 788 /// Using this function has the same effect as using \ref supplyMap() -
lemon/preflow.h
r641 r715 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 #ifdef DOXYGEN 56 typedef GR::ArcMap<Value> FlowMap; 57 #else 55 58 typedef typename Digraph::template ArcMap<Value> FlowMap; 59 #endif 56 60 57 61 /// \brief Instantiates a FlowMap. … … 68 72 /// The elevator type used by Preflow algorithm. 69 73 /// 70 /// \sa Elevator 71 /// \sa LinkedElevator 72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; 74 /// \sa Elevator, LinkedElevator 75 #ifdef DOXYGEN 76 typedef lemon::Elevator<GR, GR::Node> Elevator; 77 #else 78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 79 #endif 73 80 74 81 /// \brief Instantiates an Elevator. … … 98 105 /// "flow of maximum value" in a digraph. 99 106 /// The preflow algorithms are the fastest known maximum 100 /// flow algorithms. The current implementation use a mixture of the107 /// flow algorithms. The current implementation uses a mixture of the 101 108 /// \e "highest label" and the \e "bound decrease" heuristics. 102 109 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. … … 372 379 } 373 380 374 /// \brief Sets the tolerance used by algorithm. 375 /// 376 /// Sets the tolerance used by algorithm. 377 Preflow& tolerance(const Tolerance& tolerance) const { 381 /// \brief Sets the tolerance used by the algorithm. 382 /// 383 /// Sets the tolerance object used by the algorithm. 384 /// \return <tt>(*this)</tt> 385 Preflow& tolerance(const Tolerance& tolerance) { 378 386 _tolerance = tolerance; 379 387 return *this; … … 382 390 /// \brief Returns a const reference to the tolerance. 383 391 /// 384 /// Returns a const reference to the tolerance. 392 /// Returns a const reference to the tolerance object used by 393 /// the algorithm. 385 394 const Tolerance& tolerance() const { 386 return tolerance;395 return _tolerance; 387 396 } 388 397 … … 390 399 /// The simplest way to execute the preflow algorithm is to use 391 400 /// \ref run() or \ref runMinCut().\n 392 /// If you need morecontrol on the initial solution or the execution,393 /// first you have to call one of the \ref init() functions, then401 /// If you need better control on the initial solution or the execution, 402 /// you have to call one of the \ref init() functions first, then 394 403 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). 395 404 -
lemon/radix_heap.h
r683 r711 20 20 #define LEMON_RADIX_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Radix Heap implementation.24 ///\brief Radix heap implementation. 25 25 26 26 #include <vector> … … 30 30 31 31 32 /// \ingroup auxdata32 /// \ingroup heaps 33 33 /// 34 /// \brief A Radix Heap implementation.34 /// \brief Radix heap data structure. 35 35 /// 36 /// This class implements the \e radix \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. This heap type can store only items with \e int priority. 40 /// In a heap one can change the priority of an item, add or erase an 41 /// item, but the priority cannot be decreased under the last removed 42 /// item's priority. 36 /// This class implements the \e radix \e heap data structure. 37 /// It practically conforms to the \ref concepts::Heap "heap concept", 38 /// but it has some limitations due its special implementation. 39 /// The type of the priorities must be \c int and the priority of an 40 /// item cannot be decreased under the priority of the last removed item. 43 41 /// 44 /// \param IM A read and writable Item int map, used internally 45 /// to handle the cross references. 46 /// 47 /// \see BinHeap 48 /// \see Dijkstra 42 /// \tparam IM A read-writable item map with \c int values, used 43 /// internally to handle the cross references. 49 44 template <typename IM> 50 45 class RadixHeap { 51 46 52 47 public: 53 typedef typename IM::Key Item; 48 49 /// Type of the item-int map. 50 typedef IM ItemIntMap; 51 /// Type of the priorities. 54 52 typedef int Prio; 55 typedef IM ItemIntMap; 53 /// Type of the items stored in the heap. 54 typedef typename ItemIntMap::Key Item; 56 55 57 56 /// \brief Exception thrown by RadixHeap. 58 57 /// 59 /// This Exception is thrown when a smaller priority60 /// is inserted into the \e RadixHeap then the last time erased.58 /// This exception is thrown when an item is inserted into a 59 /// RadixHeap with a priority smaller than the last erased one. 61 60 /// \see RadixHeap 62 63 class UnderFlowPriorityError : public Exception { 61 class PriorityUnderflowError : public Exception { 64 62 public: 65 63 virtual const char* what() const throw() { 66 return "lemon::RadixHeap:: UnderFlowPriorityError";64 return "lemon::RadixHeap::PriorityUnderflowError"; 67 65 } 68 66 }; 69 67 70 /// \brief Type to represent the items states.71 /// 72 /// Each Item element have a state associated to it. It maybe "in heap",73 /// "pre heap" or "postheap". The latter two are indifferent from the68 /// \brief Type to represent the states of the items. 69 /// 70 /// Each item has a state associated to it. It can be "in heap", 71 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 72 /// heap's point of view, but may be useful to the user. 75 73 /// 76 /// The ItemIntMap \e should be initialized in such way that it maps77 /// PRE_HEAP (-1) to any element to be put in the heap...74 /// The item-int map must be initialized in such way that it assigns 75 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 78 76 enum State { 79 IN_HEAP = 0, 80 PRE_HEAP = -1, 81 POST_HEAP = -2 77 IN_HEAP = 0, ///< = 0. 78 PRE_HEAP = -1, ///< = -1. 79 POST_HEAP = -2 ///< = -2. 82 80 }; 83 81 … … 97 95 }; 98 96 99 std::vector<RadixItem> data;100 std::vector<RadixBox> boxes;97 std::vector<RadixItem> _data; 98 std::vector<RadixBox> _boxes; 101 99 102 100 ItemIntMap &_iim; 103 101 104 105 102 public: 106 /// \brief The constructor. 107 /// 108 /// The constructor.109 /// 110 /// \param map It should be given to the constructor, since it is used111 /// internally to handle the cross references. The value of the map112 /// should be PRE_HEAP (-1) for each element.113 /// 114 /// \param minimal The initial minimal valueof the heap.115 /// \param capacity It determines the initial capacity of the heap.116 RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)117 : _iim(map){118 boxes.push_back(RadixBox(minimal, 1));119 boxes.push_back(RadixBox(minimal+ 1, 1));120 while (lower( boxes.size() - 1, capacity + minimal- 1)) {103 104 /// \brief Constructor. 105 /// 106 /// Constructor. 107 /// \param map A map that assigns \c int values to the items. 108 /// It is used internally to handle the cross references. 109 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 110 /// \param minimum The initial minimum value of the heap. 111 /// \param capacity The initial capacity of the heap. 112 RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0) 113 : _iim(map) 114 { 115 _boxes.push_back(RadixBox(minimum, 1)); 116 _boxes.push_back(RadixBox(minimum + 1, 1)); 117 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 121 118 extend(); 122 119 } 123 120 } 124 121 125 /// The number of items stored in the heap. 126 /// 127 /// \brief Returns the number of items stored in the heap. 128 int size() const { return data.size(); } 129 /// \brief Checks if the heap stores no items. 130 /// 131 /// Returns \c true if and only if the heap stores no items. 132 bool empty() const { return data.empty(); } 133 134 /// \brief Make empty this heap. 135 /// 136 /// Make empty this heap. It does not change the cross reference 137 /// map. If you want to reuse a heap what is not surely empty you 138 /// should first clear the heap and after that you should set the 139 /// cross reference map for each item to \c PRE_HEAP. 140 void clear(int minimal = 0, int capacity = 0) { 141 data.clear(); boxes.clear(); 142 boxes.push_back(RadixBox(minimal, 1)); 143 boxes.push_back(RadixBox(minimal + 1, 1)); 144 while (lower(boxes.size() - 1, capacity + minimal - 1)) { 122 /// \brief The number of items stored in the heap. 123 /// 124 /// This function returns the number of items stored in the heap. 125 int size() const { return _data.size(); } 126 127 /// \brief Check if the heap is empty. 128 /// 129 /// This function returns \c true if the heap is empty. 130 bool empty() const { return _data.empty(); } 131 132 /// \brief Make the heap empty. 133 /// 134 /// This functon makes the heap empty. 135 /// It does not change the cross reference map. If you want to reuse 136 /// a heap that is not surely empty, you should first clear it and 137 /// then you should set the cross reference map to \c PRE_HEAP 138 /// for each item. 139 /// \param minimum The minimum value of the heap. 140 /// \param capacity The capacity of the heap. 141 void clear(int minimum = 0, int capacity = 0) { 142 _data.clear(); _boxes.clear(); 143 _boxes.push_back(RadixBox(minimum, 1)); 144 _boxes.push_back(RadixBox(minimum + 1, 1)); 145 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 145 146 extend(); 146 147 } … … 150 151 151 152 bool upper(int box, Prio pr) { 152 return pr < boxes[box].min;153 return pr < _boxes[box].min; 153 154 } 154 155 155 156 bool lower(int box, Prio pr) { 156 return pr >= boxes[box].min +boxes[box].size;157 } 158 159 // / \brief Remove item from the box list.157 return pr >= _boxes[box].min + _boxes[box].size; 158 } 159 160 // Remove item from the box list 160 161 void remove(int index) { 161 if ( data[index].prev >= 0) {162 data[data[index].prev].next =data[index].next;162 if (_data[index].prev >= 0) { 163 _data[_data[index].prev].next = _data[index].next; 163 164 } else { 164 boxes[data[index].box].first =data[index].next;165 } 166 if ( data[index].next >= 0) {167 data[data[index].next].prev =data[index].prev;168 } 169 } 170 171 // / \brief Insert item into the box list.165 _boxes[_data[index].box].first = _data[index].next; 166 } 167 if (_data[index].next >= 0) { 168 _data[_data[index].next].prev = _data[index].prev; 169 } 170 } 171 172 // Insert item into the box list 172 173 void insert(int box, int index) { 173 if ( boxes[box].first == -1) {174 boxes[box].first = index;175 data[index].next =data[index].prev = -1;174 if (_boxes[box].first == -1) { 175 _boxes[box].first = index; 176 _data[index].next = _data[index].prev = -1; 176 177 } else { 177 data[index].next =boxes[box].first;178 data[boxes[box].first].prev = index;179 data[index].prev = -1;180 boxes[box].first = index;181 } 182 data[index].box = box;183 } 184 185 // / \brief Add a new box to the box list.178 _data[index].next = _boxes[box].first; 179 _data[_boxes[box].first].prev = index; 180 _data[index].prev = -1; 181 _boxes[box].first = index; 182 } 183 _data[index].box = box; 184 } 185 186 // Add a new box to the box list 186 187 void extend() { 187 int min = boxes.back().min +boxes.back().size;188 int bs = 2 * boxes.back().size;189 boxes.push_back(RadixBox(min, bs));190 } 191 192 // / \briefMove an item up into the proper box.193 void bubble _up(int index) {194 if (!lower( data[index].box,data[index].prio)) return;188 int min = _boxes.back().min + _boxes.back().size; 189 int bs = 2 * _boxes.back().size; 190 _boxes.push_back(RadixBox(min, bs)); 191 } 192 193 // Move an item up into the proper box. 194 void bubbleUp(int index) { 195 if (!lower(_data[index].box, _data[index].prio)) return; 195 196 remove(index); 196 int box = findUp( data[index].box,data[index].prio);197 int box = findUp(_data[index].box, _data[index].prio); 197 198 insert(box, index); 198 199 } 199 200 200 // / \brief Find up the proper box for the item with the given prio.201 // Find up the proper box for the item with the given priority 201 202 int findUp(int start, int pr) { 202 203 while (lower(start, pr)) { 203 if (++start == int( boxes.size())) {204 if (++start == int(_boxes.size())) { 204 205 extend(); 205 206 } … … 208 209 } 209 210 210 // / \brief Move an item down into the proper box.211 void bubble _down(int index) {212 if (!upper( data[index].box,data[index].prio)) return;211 // Move an item down into the proper box 212 void bubbleDown(int index) { 213 if (!upper(_data[index].box, _data[index].prio)) return; 213 214 remove(index); 214 int box = findDown( data[index].box,data[index].prio);215 int box = findDown(_data[index].box, _data[index].prio); 215 216 insert(box, index); 216 217 } 217 218 218 // / \brief Find up the proper box for the item with the given prio.219 // Find down the proper box for the item with the given priority 219 220 int findDown(int start, int pr) { 220 221 while (upper(start, pr)) { 221 if (--start < 0) throw UnderFlowPriorityError();222 if (--start < 0) throw PriorityUnderflowError(); 222 223 } 223 224 return start; 224 225 } 225 226 226 // / \brief Find the first not empty box.227 // Find the first non-empty box 227 228 int findFirst() { 228 229 int first = 0; 229 while ( boxes[first].first == -1) ++first;230 while (_boxes[first].first == -1) ++first; 230 231 return first; 231 232 } 232 233 233 // / \brief Gives back the minimal prio of the box.234 // Gives back the minimum priority of the given box 234 235 int minValue(int box) { 235 int min = data[boxes[box].first].prio;236 for (int k = boxes[box].first; k != -1; k =data[k].next) {237 if ( data[k].prio < min) min =data[k].prio;236 int min = _data[_boxes[box].first].prio; 237 for (int k = _boxes[box].first; k != -1; k = _data[k].next) { 238 if (_data[k].prio < min) min = _data[k].prio; 238 239 } 239 240 return min; 240 241 } 241 242 242 /// \brief Rearrange the items of the heap and makes the 243 /// first box not empty. 243 // Rearrange the items of the heap and make the first box non-empty 244 244 void moveDown() { 245 245 int box = findFirst(); … … 247 247 int min = minValue(box); 248 248 for (int i = 0; i <= box; ++i) { 249 boxes[i].min = min;250 min += boxes[i].size;251 } 252 int curr = boxes[box].first, next;249 _boxes[i].min = min; 250 min += _boxes[i].size; 251 } 252 int curr = _boxes[box].first, next; 253 253 while (curr != -1) { 254 next = data[curr].next;255 bubble _down(curr);254 next = _data[curr].next; 255 bubbleDown(curr); 256 256 curr = next; 257 257 } 258 258 } 259 259 260 void relocate _last(int index) {261 if (index != int( data.size()) - 1) {262 data[index] =data.back();263 if ( data[index].prev != -1) {264 data[data[index].prev].next = index;260 void relocateLast(int index) { 261 if (index != int(_data.size()) - 1) { 262 _data[index] = _data.back(); 263 if (_data[index].prev != -1) { 264 _data[_data[index].prev].next = index; 265 265 } else { 266 boxes[data[index].box].first = index;266 _boxes[_data[index].box].first = index; 267 267 } 268 if ( data[index].next != -1) {269 data[data[index].next].prev = index;268 if (_data[index].next != -1) { 269 _data[_data[index].next].prev = index; 270 270 } 271 _iim[ data[index].item] = index;272 } 273 data.pop_back();271 _iim[_data[index].item] = index; 272 } 273 _data.pop_back(); 274 274 } 275 275 … … 278 278 /// \brief Insert an item into the heap with the given priority. 279 279 /// 280 /// Adds \c i to the heap with priority \c p. 280 /// This function inserts the given item into the heap with the 281 /// given priority. 281 282 /// \param i The item to insert. 282 283 /// \param p The priority of the item. 284 /// \pre \e i must not be stored in the heap. 285 /// \warning This method may throw an \c UnderFlowPriorityException. 283 286 void push(const Item &i, const Prio &p) { 284 int n = data.size();287 int n = _data.size(); 285 288 _iim.set(i, n); 286 data.push_back(RadixItem(i, p));287 while (lower( boxes.size() - 1, p)) {289 _data.push_back(RadixItem(i, p)); 290 while (lower(_boxes.size() - 1, p)) { 288 291 extend(); 289 292 } 290 int box = findDown( boxes.size() - 1, p);293 int box = findDown(_boxes.size() - 1, p); 291 294 insert(box, n); 292 295 } 293 296 294 /// \brief Return s the item withminimum priority.295 /// 296 /// This method returns the item withminimum priority.297 /// \pre The heap must be non empty.297 /// \brief Return the item having minimum priority. 298 /// 299 /// This function returns the item having minimum priority. 300 /// \pre The heap must be non-empty. 298 301 Item top() const { 299 302 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 300 return data[boxes[0].first].item;301 } 302 303 /// \brief Returns the minimum priority.304 /// 305 /// Itreturns the minimum priority.306 /// \pre The heap must be non empty.303 return _data[_boxes[0].first].item; 304 } 305 306 /// \brief The minimum priority. 307 /// 308 /// This function returns the minimum priority. 309 /// \pre The heap must be non-empty. 307 310 Prio prio() const { 308 311 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 309 return data[boxes[0].first].prio;312 return _data[_boxes[0].first].prio; 310 313 } 311 314 312 /// \brief Deletes the item withminimum priority.313 /// 314 /// This method deletes the item withminimum priority.315 /// \brief Remove the item having minimum priority. 316 /// 317 /// This function removes the item having minimum priority. 315 318 /// \pre The heap must be non-empty. 316 319 void pop() { 317 320 moveDown(); 318 int index = boxes[0].first;319 _iim[ data[index].item] = POST_HEAP;321 int index = _boxes[0].first; 322 _iim[_data[index].item] = POST_HEAP; 320 323 remove(index); 321 relocate_last(index); 322 } 323 324 /// \brief Deletes \c i from the heap. 325 /// 326 /// This method deletes item \c i from the heap, if \c i was 327 /// already stored in the heap. 328 /// \param i The item to erase. 324 relocateLast(index); 325 } 326 327 /// \brief Remove the given item from the heap. 328 /// 329 /// This function removes the given item from the heap if it is 330 /// already stored. 331 /// \param i The item to delete. 332 /// \pre \e i must be in the heap. 329 333 void erase(const Item &i) { 330 334 int index = _iim[i]; 331 335 _iim[i] = POST_HEAP; 332 336 remove(index); 333 relocate _last(index);337 relocateLast(index); 334 338 } 335 339 336 /// \brief Returns the priority of \c i.337 /// 338 /// This function returns the priority of item \c i.339 /// \p re \c i must be in the heap.340 /// \p aram i The item.340 /// \brief The priority of the given item. 341 /// 342 /// This function returns the priority of the given item. 343 /// \param i The item. 344 /// \pre \e i must be in the heap. 341 345 Prio operator[](const Item &i) const { 342 346 int idx = _iim[i]; 343 return data[idx].prio;344 } 345 346 /// \brief \c i gets to the heap with priority \c p independently347 /// if \c i was already there.348 /// 349 /// This method calls \ref push(\c i, \c p) if \c i is not stored350 /// in the heap and sets the priority of \c i to \c p otherwise.351 /// It may throw an \e UnderFlowPriorityException.347 return _data[idx].prio; 348 } 349 350 /// \brief Set the priority of an item or insert it, if it is 351 /// not stored in the heap. 352 /// 353 /// This method sets the priority of the given item if it is 354 /// already stored in the heap. Otherwise it inserts the given 355 /// item into the heap with the given priority. 352 356 /// \param i The item. 353 357 /// \param p The priority. 358 /// \pre \e i must be in the heap. 359 /// \warning This method may throw an \c UnderFlowPriorityException. 354 360 void set(const Item &i, const Prio &p) { 355 361 int idx = _iim[i]; … … 357 363 push(i, p); 358 364 } 359 else if( p >= data[idx].prio ) {360 data[idx].prio = p;361 bubble _up(idx);365 else if( p >= _data[idx].prio ) { 366 _data[idx].prio = p; 367 bubbleUp(idx); 362 368 } else { 363 data[idx].prio = p; 364 bubble_down(idx); 365 } 366 } 367 368 369 /// \brief Decreases the priority of \c i to \c p. 370 /// 371 /// This method decreases the priority of item \c i to \c p. 372 /// \pre \c i must be stored in the heap with priority at least \c p, and 373 /// \c should be greater or equal to the last removed item's priority. 369 _data[idx].prio = p; 370 bubbleDown(idx); 371 } 372 } 373 374 /// \brief Decrease the priority of an item to the given value. 375 /// 376 /// This function decreases the priority of an item to the given value. 374 377 /// \param i The item. 375 378 /// \param p The priority. 379 /// \pre \e i must be stored in the heap with priority at least \e p. 380 /// \warning This method may throw an \c UnderFlowPriorityException. 376 381 void decrease(const Item &i, const Prio &p) { 377 382 int idx = _iim[i]; 378 data[idx].prio = p; 379 bubble_down(idx); 380 } 381 382 /// \brief Increases the priority of \c i to \c p. 383 /// 384 /// This method sets the priority of item \c i to \c p. 385 /// \pre \c i must be stored in the heap with priority at most \c p 383 _data[idx].prio = p; 384 bubbleDown(idx); 385 } 386 387 /// \brief Increase the priority of an item to the given value. 388 /// 389 /// This function increases the priority of an item to the given value. 386 390 /// \param i The item. 387 391 /// \param p The priority. 392 /// \pre \e i must be stored in the heap with priority at most \e p. 388 393 void increase(const Item &i, const Prio &p) { 389 394 int idx = _iim[i]; 390 data[idx].prio = p;391 bubble _up(idx);392 } 393 394 /// \brief Return s if \c item is in, has already been in, or has395 /// never been in the heap.396 /// 397 /// This method returns PRE_HEAP if \c item has never been in the398 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP399 /// otherwise. In the latter case it is possible that \c item will400 /// get backto the heap again.395 _data[idx].prio = p; 396 bubbleUp(idx); 397 } 398 399 /// \brief Return the state of an item. 400 /// 401 /// This method returns \c PRE_HEAP if the given item has never 402 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 403 /// and \c POST_HEAP otherwise. 404 /// In the latter case it is possible that the item will get back 405 /// to the heap again. 401 406 /// \param i The item. 402 407 State state(const Item &i) const { … … 406 411 } 407 412 408 /// \brief Set s the state of the \citem in the heap.409 /// 410 /// Sets the state of the \c item in the heap. It can be used to411 /// manually clear the heap when it is important to achive the412 /// better time complexity.413 /// \brief Set the state of an item in the heap. 414 /// 415 /// This function sets the state of the given item in the heap. 416 /// It can be used to manually clear the heap when it is important 417 /// to achive better time complexity. 413 418 /// \param i The item. 414 419 /// \param st The state. It should not be \c IN_HEAP. -
scripts/chg-len.py
r422 r733 1 1 #! /usr/bin/env python 2 # 3 # This file is a part of LEMON, a generic C++ optimization library. 4 # 5 # Copyright (C) 2003-2009 6 # Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 # (Egervary Research Group on Combinatorial Optimization, EGRES). 8 # 9 # Permission to use, modify and distribute this software is granted 10 # provided that this copyright notice appears in all copies. For 11 # precise terms see the accompanying LICENSE file. 12 # 13 # This software is provided "AS IS" with no warranty of any kind, 14 # express or implied, and with no claim as to its suitability for any 15 # purpose. 2 16 3 17 import sys -
scripts/mk-release.sh
r564 r733 1 1 #!/bin/bash 2 # 3 # This file is a part of LEMON, a generic C++ optimization library. 4 # 5 # Copyright (C) 2003-2009 6 # Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 # (Egervary Research Group on Combinatorial Optimization, EGRES). 8 # 9 # Permission to use, modify and distribute this software is granted 10 # provided that this copyright notice appears in all copies. For 11 # precise terms see the accompanying LICENSE file. 12 # 13 # This software is provided "AS IS" with no warranty of any kind, 14 # express or implied, and with no claim as to its suitability for any 15 # purpose. 2 16 3 17 set -e -
scripts/unify-sources.sh
r655 r733 1 1 #!/bin/bash 2 # 3 # This file is a part of LEMON, a generic C++ optimization library. 4 # 5 # Copyright (C) 2003-2009 6 # Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 # (Egervary Research Group on Combinatorial Optimization, EGRES). 8 # 9 # Permission to use, modify and distribute this software is granted 10 # provided that this copyright notice appears in all copies. For 11 # precise terms see the accompanying LICENSE file. 12 # 13 # This software is provided "AS IS" with no warranty of any kind, 14 # express or implied, and with no claim as to its suitability for any 15 # purpose. 2 16 3 17 YEAR=`date +%Y` -
test/CMakeLists.txt
r679 r698 10 10 SET(TESTS 11 11 adaptors_test 12 bellman_ford_test 12 13 bfs_test 13 14 circulation_test -
test/Makefile.am
r649 r698 8 8 check_PROGRAMS += \ 9 9 test/adaptors_test \ 10 test/bellman_ford_test \ 10 11 test/bfs_test \ 11 12 test/circulation_test \ … … 53 54 54 55 test_adaptors_test_SOURCES = test/adaptors_test.cc 56 test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc 55 57 test_bfs_test_SOURCES = test/bfs_test.cc 56 58 test_circulation_test_SOURCES = test/circulation_test.cc -
test/circulation_test.cc
r611 r689 88 88 .supplyMap(supply) 89 89 .flowMap(flow); 90 91 const CirculationType::Elevator& elev = const_circ_test.elevator(); 92 circ_test.elevator(const_cast<CirculationType::Elevator&>(elev)); 93 CirculationType::Tolerance tol = const_circ_test.tolerance(); 94 circ_test.tolerance(tol); 90 95 91 96 circ_test.init(); -
test/heap_test.cc
r681 r702 26 26 27 27 #include <lemon/smart_graph.h> 28 29 28 #include <lemon/lgf_reader.h> 30 29 #include <lemon/dijkstra.h> … … 32 31 33 32 #include <lemon/bin_heap.h> 33 #include <lemon/fourary_heap.h> 34 #include <lemon/kary_heap.h> 34 35 #include <lemon/fib_heap.h> 36 #include <lemon/pairing_heap.h> 35 37 #include <lemon/radix_heap.h> 38 #include <lemon/binom_heap.h> 36 39 #include <lemon/bucket_heap.h> 37 40 … … 90 93 void heapSortTest() { 91 94 RangeMap<int> map(test_len, -1); 92 93 95 Heap heap(map); 94 96 95 97 std::vector<int> v(test_len); 96 97 98 for (int i = 0; i < test_len; ++i) { 98 99 v[i] = test_seq[i]; … … 101 102 std::sort(v.begin(), v.end()); 102 103 for (int i = 0; i < test_len; ++i) { 103 check(v[i] == heap.prio() ,"Wrong order in heap sort.");104 check(v[i] == heap.prio(), "Wrong order in heap sort."); 104 105 heap.pop(); 105 106 } … … 113 114 114 115 std::vector<int> v(test_len); 115 116 116 for (int i = 0; i < test_len; ++i) { 117 117 v[i] = test_seq[i]; … … 124 124 std::sort(v.begin(), v.end()); 125 125 for (int i = 0; i < test_len; ++i) { 126 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");126 check(v[i] == heap.prio(), "Wrong order in heap increase test."); 127 127 heap.pop(); 128 128 } 129 129 } 130 131 132 130 133 131 template <typename Heap> … … 145 143 if (dijkstra.reached(s)) { 146 144 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], 147 "Error in a shortest path tree!");145 "Error in shortest path tree."); 148 146 } 149 147 } … … 154 152 Node s = digraph.source(a); 155 153 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], 156 "Error in a shortest path tree!");154 "Error in shortest path tree."); 157 155 } 158 156 } … … 176 174 run(); 177 175 176 // BinHeap 178 177 { 179 178 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 187 186 } 188 187 188 // FouraryHeap 189 { 190 typedef FouraryHeap<Prio, ItemIntMap> IntHeap; 191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 192 heapSortTest<IntHeap>(); 193 heapIncreaseTest<IntHeap>(); 194 195 typedef FouraryHeap<Prio, IntNodeMap > NodeHeap; 196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 197 dijkstraHeapTest<NodeHeap>(digraph, length, source); 198 } 199 200 // KaryHeap 201 { 202 typedef KaryHeap<Prio, ItemIntMap> IntHeap; 203 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 204 heapSortTest<IntHeap>(); 205 heapIncreaseTest<IntHeap>(); 206 207 typedef KaryHeap<Prio, IntNodeMap > NodeHeap; 208 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 209 dijkstraHeapTest<NodeHeap>(digraph, length, source); 210 } 211 212 // FibHeap 189 213 { 190 214 typedef FibHeap<Prio, ItemIntMap> IntHeap; … … 198 222 } 199 223 224 // PairingHeap 225 { 226 typedef PairingHeap<Prio, ItemIntMap> IntHeap; 227 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 228 heapSortTest<IntHeap>(); 229 heapIncreaseTest<IntHeap>(); 230 231 typedef PairingHeap<Prio, IntNodeMap > NodeHeap; 232 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 233 dijkstraHeapTest<NodeHeap>(digraph, length, source); 234 } 235 236 // RadixHeap 200 237 { 201 238 typedef RadixHeap<ItemIntMap> IntHeap; … … 209 246 } 210 247 248 // BinomHeap 249 { 250 typedef BinomHeap<Prio, ItemIntMap> IntHeap; 251 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 252 heapSortTest<IntHeap>(); 253 heapIncreaseTest<IntHeap>(); 254 255 typedef BinomHeap<Prio, IntNodeMap > NodeHeap; 256 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 257 dijkstraHeapTest<NodeHeap>(digraph, length, source); 258 } 259 260 // BucketHeap, SimpleBucketHeap 211 261 { 212 262 typedef BucketHeap<ItemIntMap> IntHeap; … … 218 268 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 219 269 dijkstraHeapTest<NodeHeap>(digraph, length, source); 220 } 221 270 271 typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; 272 heapSortTest<SimpleIntHeap>(); 273 } 222 274 223 275 return 0; -
test/maps_test.cc
r684 r726 24 24 #include <lemon/maps.h> 25 25 #include <lemon/list_graph.h> 26 #include <lemon/smart_graph.h> 27 #include <lemon/adaptors.h> 28 #include <lemon/dfs.h> 26 29 27 30 #include "test_tools.h" … … 61 64 typedef ReadWriteMap<A, bool> BoolWriteMap; 62 65 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap; 66 67 template<typename Map1, typename Map2, typename ItemIt> 68 void compareMap(const Map1& map1, const Map2& map2, ItemIt it) { 69 for (; it != INVALID; ++it) 70 check(map1[it] == map2[it], "The maps are not equal"); 71 } 63 72 64 73 int main() … … 330 339 { 331 340 typedef std::vector<int> vec; 341 checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >(); 342 checkConcept<WriteMap<int, bool>, 343 LoggerBoolMap<std::back_insert_iterator<vec> > >(); 344 332 345 vec v1; 333 346 vec v2(10); … … 349 362 it != map2.end(); ++it ) 350 363 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 364 365 typedef ListDigraph Graph; 366 DIGRAPH_TYPEDEFS(Graph); 367 Graph gr; 368 369 Node n0 = gr.addNode(); 370 Node n1 = gr.addNode(); 371 Node n2 = gr.addNode(); 372 Node n3 = gr.addNode(); 373 374 gr.addArc(n3, n0); 375 gr.addArc(n3, n2); 376 gr.addArc(n0, n2); 377 gr.addArc(n2, n1); 378 gr.addArc(n0, n1); 379 380 { 381 std::vector<Node> v; 382 dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run(); 383 384 check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, 385 "Something is wrong with LoggerBoolMap"); 386 } 387 { 388 std::vector<Node> v(countNodes(gr)); 389 dfs(gr).processedMap(loggerBoolMap(v.begin())).run(); 390 391 check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, 392 "Something is wrong with LoggerBoolMap"); 393 } 394 } 395 396 // IdMap, RangeIdMap 397 { 398 typedef ListDigraph Graph; 399 DIGRAPH_TYPEDEFS(Graph); 400 401 checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >(); 402 checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >(); 403 checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >(); 404 checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >(); 405 406 Graph gr; 407 IdMap<Graph, Node> nmap(gr); 408 IdMap<Graph, Arc> amap(gr); 409 RangeIdMap<Graph, Node> nrmap(gr); 410 RangeIdMap<Graph, Arc> armap(gr); 411 412 Node n0 = gr.addNode(); 413 Node n1 = gr.addNode(); 414 Node n2 = gr.addNode(); 415 416 Arc a0 = gr.addArc(n0, n1); 417 Arc a1 = gr.addArc(n0, n2); 418 Arc a2 = gr.addArc(n2, n1); 419 Arc a3 = gr.addArc(n2, n0); 420