Changeset 1128:426a704d7483 in lemon for lemon/concepts
- Timestamp:
- 01/20/12 19:23:48 (12 years ago)
- Branch:
- default
- Parents:
- 1124:b1744d7bdb47 (diff), 1125:b873350e6258 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Location:
- lemon/concepts
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/graph_components.h
r956 r1127 116 116 const _GraphItem &ia; 117 117 const _GraphItem &ib; 118 Constraints() {} 118 119 }; 119 120 }; … … 175 176 176 177 const _Digraph& digraph; 178 Constraints() {} 177 179 }; 178 180 }; … … 291 293 292 294 const _Graph& graph; 295 Constraints() {} 293 296 }; 294 297 … … 370 373 371 374 const _Digraph& digraph; 375 Constraints() {} 372 376 }; 373 377 }; … … 422 426 423 427 const _Graph& graph; 428 Constraints() {} 424 429 }; 425 430 }; … … 499 504 } 500 505 const GR& g; 506 Constraints() {} 501 507 }; 502 508 }; … … 587 593 const Base& node; 588 594 const GR& graph; 595 Constraints() {} 589 596 }; 590 597 }; … … 763 770 764 771 const _Digraph& digraph; 772 Constraints() {} 765 773 }; 766 774 }; … … 887 895 888 896 const _Graph& graph; 897 Constraints() {} 889 898 }; 890 899 }; … … 944 953 945 954 const _Digraph& digraph; 955 Constraints() {} 946 956 }; 947 957 }; … … 985 995 986 996 const _Graph& graph; 997 Constraints() {} 987 998 }; 988 999 }; … … 1062 1073 const GR &g; 1063 1074 const typename GraphMap::Value &t; 1075 Constraints() {} 1064 1076 }; 1065 1077 … … 1200 1212 1201 1213 const _Digraph& digraph; 1214 Constraints() {} 1202 1215 }; 1203 1216 }; … … 1285 1298 1286 1299 const _Graph& graph; 1300 Constraints() {} 1287 1301 }; 1288 1302 }; … … 1329 1343 1330 1344 _Digraph& digraph; 1345 Constraints() {} 1331 1346 }; 1332 1347 }; … … 1373 1388 1374 1389 _Graph& graph; 1390 Constraints() {} 1375 1391 }; 1376 1392 }; … … 1412 1428 1413 1429 _Digraph& digraph; 1430 Constraints() {} 1414 1431 }; 1415 1432 }; … … 1451 1468 1452 1469 _Graph& graph; 1470 Constraints() {} 1453 1471 }; 1454 1472 }; … … 1479 1497 1480 1498 _Digraph& digraph; 1499 Constraints() {} 1481 1500 }; 1482 1501 }; … … 1507 1526 1508 1527 _Graph& graph; 1528 Constraints() {} 1509 1529 }; 1510 1530 }; -
lemon/concepts/graph_components.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of graph components.21 ///\brief The concepts of graph components. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 39 39 /// \note This class is a template class so that we can use it to 40 40 /// create graph skeleton classes. The reason for this is that \c Node 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 42 42 /// base class. For \c Node you should instantiate it with character 43 43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. … … 90 90 /// 91 91 /// This operator defines an ordering of the items. 92 /// It makes possible to use graph item types as key types in 92 /// It makes possible to use graph item types as key types in 93 93 /// associative containers (e.g. \c std::map). 94 94 /// 95 /// \note This operator only ha veto define some strict ordering of95 /// \note This operator only has to define some strict ordering of 96 96 /// the items; this order has nothing to do with the iteration 97 97 /// ordering of the items. … … 124 124 /// This class describes the base interface of directed graph types. 125 125 /// All digraph %concepts have to conform to this class. 126 /// It just provides types for nodes and arcs and functions 126 /// It just provides types for nodes and arcs and functions 127 127 /// to get the source and the target nodes of arcs. 128 128 class BaseDigraphComponent { … … 432 432 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 433 433 /// 434 /// This class describes the concept of \c NodeIt, \c ArcIt and 434 /// This class describes the concept of \c NodeIt, \c ArcIt and 435 435 /// \c EdgeIt subtypes of digraph and graph types. 436 436 template <typename GR, typename Item> … … 472 472 /// next item. 473 473 GraphItemIt& operator++() { return *this; } 474 474 475 475 /// \brief Equality operator 476 476 /// … … 508 508 }; 509 509 510 /// \brief Concept class for \c InArcIt, \c OutArcIt and 510 /// \brief Concept class for \c InArcIt, \c OutArcIt and 511 511 /// \c IncEdgeIt types. 512 512 /// 513 /// This class describes the concept of \c InArcIt, \c OutArcIt 513 /// This class describes the concept of \c InArcIt, \c OutArcIt 514 514 /// and \c IncEdgeIt subtypes of digraph and graph types. 515 515 /// 516 516 /// \note Since these iterator classes do not inherit from the same 517 517 /// base class, there is an additional template parameter (selector) 518 /// \c sel. For \c InArcIt you should instantiate it with character 518 /// \c sel. For \c InArcIt you should instantiate it with character 519 519 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 520 520 template <typename GR, … … 537 537 GraphIncIt(const GraphIncIt& it) : Item(it) {} 538 538 539 /// \brief Constructor that sets the iterator to the first 539 /// \brief Constructor that sets the iterator to the first 540 540 /// incoming or outgoing arc. 541 541 /// 542 /// Constructor that sets the iterator to the first arc 542 /// Constructor that sets the iterator to the first arc 543 543 /// incoming to or outgoing from the given node. 544 544 explicit GraphIncIt(const GR&, const Base&) {} … … 813 813 /// \brief Return the first edge incident to the given node. 814 814 /// 815 /// This function gives back the first edge incident to the given 815 /// This function gives back the first edge incident to the given 816 816 /// node. The bool parameter gives back the direction for which the 817 /// source node of the directed arc representing the edge is the 817 /// source node of the directed arc representing the edge is the 818 818 /// given node. 819 819 void firstInc(Edge&, bool&, const Node&) const {} … … 822 822 /// given node. 823 823 /// 824 /// This function gives back the next edge incident to the given 824 /// This function gives back the next edge incident to the given 825 825 /// node. The bool parameter should be used as \c firstInc() use it. 826 826 void nextInc(Edge&, bool&) const {} … … 1002 1002 /// 1003 1003 /// This class describes the concept of standard graph maps, i.e. 1004 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1004 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1005 1005 /// graph types, which can be used for associating data to graph items. 1006 1006 /// The standard graph maps must conform to the ReferenceMap concept. … … 1057 1057 _Map m1(g); 1058 1058 _Map m2(g,t); 1059 1059 1060 1060 // Copy constructor 1061 1061 // _Map m3(m); … … 1081 1081 /// 1082 1082 /// This class describes the interface of mappable directed graphs. 1083 /// It extends \ref BaseDigraphComponent with the standard digraph 1083 /// It extends \ref BaseDigraphComponent with the standard digraph 1084 1084 /// map classes, namely \c NodeMap and \c ArcMap. 1085 1085 /// This concept is part of the Digraph concept. … … 1219 1219 /// 1220 1220 /// This class describes the interface of mappable undirected graphs. 1221 /// It extends \ref MappableDigraphComponent with the standard graph 1221 /// It extends \ref MappableDigraphComponent with the standard graph 1222 1222 /// map class for edges (\c EdgeMap). 1223 1223 /// This concept is part of the Graph concept. … … 1305 1305 /// 1306 1306 /// This class describes the interface of extendable directed graphs. 1307 /// It extends \ref BaseDigraphComponent with functions for adding 1307 /// It extends \ref BaseDigraphComponent with functions for adding 1308 1308 /// nodes and arcs to the digraph. 1309 1309 /// This concept requires \ref AlterableDigraphComponent. … … 1350 1350 /// 1351 1351 /// This class describes the interface of extendable undirected graphs. 1352 /// It extends \ref BaseGraphComponent with functions for adding 1352 /// It extends \ref BaseGraphComponent with functions for adding 1353 1353 /// nodes and edges to the graph. 1354 1354 /// This concept requires \ref AlterableGraphComponent. … … 1395 1395 /// 1396 1396 /// This class describes the interface of erasable directed graphs. 1397 /// It extends \ref BaseDigraphComponent with functions for removing 1397 /// It extends \ref BaseDigraphComponent with functions for removing 1398 1398 /// nodes and arcs from the digraph. 1399 1399 /// This concept requires \ref AlterableDigraphComponent. … … 1408 1408 /// \brief Erase a node from the digraph. 1409 1409 /// 1410 /// This function erases the given node from the digraph and all arcs 1410 /// This function erases the given node from the digraph and all arcs 1411 1411 /// connected to the node. 1412 1412 void erase(const Node&) {} … … 1435 1435 /// 1436 1436 /// This class describes the interface of erasable undirected graphs. 1437 /// It extends \ref BaseGraphComponent with functions for removing 1437 /// It extends \ref BaseGraphComponent with functions for removing 1438 1438 /// nodes and edges from the graph. 1439 1439 /// This concept requires \ref AlterableGraphComponent. -
lemon/concepts/heap.h
r956 r1127 315 315 _Heap& heap; 316 316 ItemIntMap& map; 317 Constraints() {} 317 318 }; 318 319 }; -
lemon/concepts/heap.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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>>51 #else 52 template <typename PR, typename IM >56 template <typename PR, typename IM, typename CMP> 57 #else 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 every item. 90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 91 #ifdef DOXYGEN 86 92 explicit Heap(ItemIntMap &map) {} 93 #else 94 explicit Heap(ItemIntMap&) {} 95 #endif 96 97 /// \brief Constructor. 98 /// 99 /// Constructor. 100 /// \param map A map that assigns \c int values to keys of type 101 /// \c Item. It is used internally by the heap implementations to 102 /// handle the cross references. The assigned value must be 103 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 104 /// \param comp The function object used for comparing the priorities. 105 #ifdef DOXYGEN 106 explicit Heap(ItemIntMap &map, const CMP &comp) {} 107 #else 108 explicit Heap(ItemIntMap&, const CMP&) {} 109 #endif 87 110 88 111 /// \brief The number of items stored in the heap. 89 112 /// 90 /// Returns the number of items stored in the heap.113 /// This function returns the number of items stored in the heap. 91 114 int size() const { return 0; } 92 115 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.116 /// \brief Check if the heap is empty. 117 /// 118 /// This function returns \c true if the heap is empty. 96 119 bool empty() const { return false; } 97 120 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. 121 /// \brief Make the heap empty. 122 /// 123 /// This functon makes the heap empty. 124 /// It does not change the cross reference map. If you want to reuse 125 /// a heap that is not surely empty, you should first clear it and 126 /// then you should set the cross reference map to \c PRE_HEAP 127 /// for each item. 128 void clear() {} 129 130 /// \brief Insert an item into the heap with the given priority. 131 /// 132 /// This function inserts the given item into the heap with the 133 /// given priority. 106 134 /// \param i The item to insert. 107 135 /// \param p The priority of the item. 136 /// \pre \e i must not be stored in the heap. 137 #ifdef DOXYGEN 108 138 void push(const Item &i, const Prio &p) {} 109 110 /// \brief Returns the item having minimum priority. 111 /// 112 /// Returns the item having minimum priority. 139 #else 140 void push(const Item&, const Prio&) {} 141 #endif 142 143 /// \brief Return the item having minimum priority. 144 /// 145 /// This function returns the item having minimum priority. 113 146 /// \pre The heap must be non-empty. 114 Item top() const { }147 Item top() const { return Item(); } 115 148 116 149 /// \brief The minimum priority. 117 150 /// 118 /// Returns the minimum priority.151 /// This function returns the minimum priority. 119 152 /// \pre The heap must be non-empty. 120 Prio prio() const { }121 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.153 Prio prio() const { return Prio(); } 154 155 /// \brief Remove the item having minimum priority. 156 /// 157 /// This function removes the item having minimum priority. 125 158 /// \pre The heap must be non-empty. 126 159 void pop() {} 127 160 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 161 /// \brief Remove the given item from the heap. 162 /// 163 /// This function removes the given item from the heap if it is 164 /// already stored. 131 165 /// \param i The item to delete. 166 /// \pre \e i must be in the heap. 167 #ifdef DOXYGEN 132 168 void erase(const Item &i) {} 133 134 /// \brief The priority of an item. 135 /// 136 /// Returns the priority of the given item. 137 /// \param i The item. 138 /// \pre \c i must be in the heap. 169 #else 170 void erase(const Item&) {} 171 #endif 172 173 /// \brief The priority of the given item. 174 /// 175 /// This function returns the priority of the given item. 176 /// \param i The item. 177 /// \pre \e i must be in the heap. 178 #ifdef DOXYGEN 139 179 Prio operator[](const Item &i) const {} 140 141 /// \brief Sets the priority of an item or inserts it, if it is 180 #else 181 Prio operator[](const Item&) const { return Prio(); } 182 #endif 183 184 /// \brief Set the priority of an item or insert it, if it is 142 185 /// not stored in the heap. 143 186 /// 144 187 /// 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.188 /// already stored in the heap. Otherwise it inserts the given 189 /// item into the heap with the given priority. 147 190 /// 148 191 /// \param i The item. 149 192 /// \param p The priority. 193 #ifdef DOXYGEN 150 194 void set(const Item &i, const Prio &p) {} 151 152 /// \brief Decreases the priority of an item to the given value. 153 /// 154 /// Decreases the priority of an item to the given value. 195 #else 196 void set(const Item&, const Prio&) {} 197 #endif 198 199 /// \brief Decrease the priority of an item to the given value. 200 /// 201 /// This function decreases the priority of an item to the given value. 155 202 /// \param i The item. 156 203 /// \param p The priority. 157 /// \pre \c i must be stored in the heap with priority at least \c p. 204 /// \pre \e i must be stored in the heap with priority at least \e p. 205 #ifdef DOXYGEN 158 206 void decrease(const Item &i, const Prio &p) {} 159 160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 207 #else 208 void decrease(const Item&, const Prio&) {} 209 #endif 210 211 /// \brief Increase the priority of an item to the given value. 212 /// 213 /// This function increases the priority of an item to the given value. 163 214 /// \param i The item. 164 215 /// \param p The priority. 165 /// \pre \c i must be stored in the heap with priority at most \c p. 216 /// \pre \e i must be stored in the heap with priority at most \e p. 217 #ifdef DOXYGEN 166 218 void increase(const Item &i, const Prio &p) {} 167 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 219 #else 220 void increase(const Item&, const Prio&) {} 221 #endif 222 223 /// \brief Return the state of an item. 170 224 /// 171 225 /// This method returns \c PRE_HEAP if the given item has never … … 175 229 /// to the heap again. 176 230 /// \param i The item. 231 #ifdef DOXYGEN 177 232 State state(const Item &i) const {} 178 179 /// \brief Sets the state of an item in the heap. 180 /// 181 /// Sets the state of the given item in the heap. It can be used 182 /// to manually clear the heap when it is important to achive the 183 /// better time complexity. 233 #else 234 State state(const Item&) const { return PRE_HEAP; } 235 #endif 236 237 /// \brief Set the state of an item in the heap. 238 /// 239 /// This function sets the state of the given item in the heap. 240 /// It can be used to manually clear the heap when it is important 241 /// to achive better time complexity. 184 242 /// \param i The item. 185 243 /// \param st The state. It should not be \c IN_HEAP. 244 #ifdef DOXYGEN 186 245 void state(const Item& i, State st) {} 246 #else 247 void state(const Item&, State) {} 248 #endif 187 249 188 250 -
lemon/concepts/path.h
r832 r1127 169 169 } 170 170 _Path& p; 171 PathDumperConstraints() {} 171 172 }; 172 173 … … 194 195 } 195 196 _Path& p; 197 PathDumperConstraints() {} 196 198 }; 197 199 -
lemon/concepts/path.h
r1125 r1127 19 19 ///\ingroup concept 20 20 ///\file 21 ///\brief Classes for representing paths in digraphs.21 ///\brief The concept of paths 22 22 /// 23 23 … … 39 39 /// A skeleton structure for representing directed paths in a 40 40 /// digraph. 41 /// In a sense, a path can be treated as a list of arcs. 42 /// LEMON path types just store this list. As a consequence, they cannot 43 /// enumerate the nodes on the path directly and a zero length path 44 /// cannot store its source node. 45 /// 46 /// The arcs of a path should be stored in the order of their directions, 47 /// i.e. the target node of each arc should be the same as the source 48 /// node of the next arc. This consistency could be checked using 49 /// \ref checkPath(). 50 /// The source and target nodes of a (consistent) path can be obtained 51 /// using \ref pathSource() and \ref pathTarget(). 52 /// 53 /// A path can be constructed from another path of any type using the 54 /// copy constructor or the assignment operator. 55 /// 41 56 /// \tparam GR The digraph type in which the path is. 42 ///43 /// In a sense, the path can be treated as a list of arcs. The44 /// lemon path type stores just this list. As a consequence it45 /// cannot enumerate the nodes in the path and the zero length46 /// paths cannot store the source.47 ///48 57 template <typename GR> 49 58 class Path { … … 60 69 Path() {} 61 70 62 /// \brief Template co nstructor71 /// \brief Template copy constructor 63 72 template <typename CPath> 64 73 Path(const CPath& cpath) {} 65 74 66 /// \brief Template assigment 75 /// \brief Template assigment operator 67 76 template <typename CPath> 68 77 Path& operator=(const CPath& cpath) { … … 71 80 } 72 81 73 /// Length of the path ie. the number of arcs in the path.82 /// Length of the path, i.e. the number of arcs on the path. 74 83 int length() const { return 0;} 75 84 … … 80 89 void clear() {} 81 90 82 /// \brief LEMON style iterator for path arcs91 /// \brief LEMON style iterator for enumerating the arcs of a path. 83 92 /// 84 /// This class is used to iterate on the arcs of the paths.93 /// LEMON style iterator class for enumerating the arcs of a path. 85 94 class ArcIt { 86 95 public: … … 89 98 /// Invalid constructor 90 99 ArcIt(Invalid) {} 91 /// Constructor for first arc100 /// Sets the iterator to the first arc of the given path 92 101 ArcIt(const Path &) {} 93 102 94 /// Conversion to Arc103 /// Conversion to \c Arc 95 104 operator Arc() const { return INVALID; } 96 105 … … 195 204 /// 196 205 /// A skeleton structure for path dumpers. The path dumpers are 197 /// the generalization of the paths. The path dumpers can 198 /// enumerate the arcs of the path wheter in forward or in 199 /// backward order. In most time these classes are not used 200 /// directly rather it used to assign a dumped class to a real 201 /// path type. 206 /// the generalization of the paths, they can enumerate the arcs 207 /// of the path either in forward or in backward order. 208 /// These classes are typically not used directly, they are rather 209 /// used to be assigned to a real path type. 202 210 /// 203 211 /// The main purpose of this concept is that the shortest path 204 /// algorithms can enumerate easily the arcs in reverse order. 205 /// If we would like to give back a real path from these 206 /// algorithms then we should create a temporarly path object. In 207 /// LEMON such algorithms gives back a path dumper what can 208 /// assigned to a real path and the dumpers can be implemented as 212 /// algorithms can enumerate the arcs easily in reverse order. 213 /// In LEMON, such algorithms give back a (reverse) path dumper that 214 /// can be assigned to a real path. The dumpers can be implemented as 209 215 /// an adaptor class to the predecessor map. 210 216 /// 211 217 /// \tparam GR The digraph type in which the path is. 212 ///213 /// The paths can be constructed from any path type by a214 /// template constructor or a template assignment operator.215 218 template <typename GR> 216 219 class PathDumper { … … 222 225 typedef typename Digraph::Arc Arc; 223 226 224 /// Length of the path ie. the number of arcs in the path.227 /// Length of the path, i.e. the number of arcs on the path. 225 228 int length() const { return 0;} 226 229 … … 230 233 /// \brief Forward or reverse dumping 231 234 /// 232 /// If the RevPathTag is defined and true then reverse dumping 233 /// is provided in the path dumper. In this case instead of the 234 /// ArcIt the RevArcIt iterator should be implemented in the 235 /// dumper. 235 /// If this tag is defined to be \c True, then reverse dumping 236 /// is provided in the path dumper. In this case, \c RevArcIt 237 /// iterator should be implemented instead of \c ArcIt iterator. 236 238 typedef False RevPathTag; 237 239 238 /// \brief LEMON style iterator for path arcs240 /// \brief LEMON style iterator for enumerating the arcs of a path. 239 241 /// 240 /// This class is used to iterate on the arcs of the paths.242 /// LEMON style iterator class for enumerating the arcs of a path. 241 243 class ArcIt { 242 244 public: … … 245 247 /// Invalid constructor 246 248 ArcIt(Invalid) {} 247 /// Constructor for first arc249 /// Sets the iterator to the first arc of the given path 248 250 ArcIt(const PathDumper&) {} 249 251 250 /// Conversion to Arc252 /// Conversion to \c Arc 251 253 operator Arc() const { return INVALID; } 252 254 … … 263 265 }; 264 266 265 /// \brief LEMON style iterator for path arcs 267 /// \brief LEMON style iterator for enumerating the arcs of a path 268 /// in reverse direction. 266 269 /// 267 /// This class is used to iterate on the arcs of the paths in268 /// reverse direction.270 /// LEMON style iterator class for enumerating the arcs of a path 271 /// in reverse direction. 269 272 class RevArcIt { 270 273 public: … … 273 276 /// Invalid constructor 274 277 RevArcIt(Invalid) {} 275 /// Constructor for first arc278 /// Sets the iterator to the last arc of the given path 276 279 RevArcIt(const PathDumper &) {} 277 280 278 /// Conversion to Arc281 /// Conversion to \c Arc 279 282 operator Arc() const { return INVALID; } 280 283
Note: See TracChangeset
for help on using the changeset viewer.