Changeset 983:8b2d4e5d96e4 in lemon-1.2 for lemon
- Timestamp:
- 08/07/13 06:55:05 (11 years ago)
- Branch:
- default
- Parents:
- 971:a26b90a17c81 (diff), 982:3e711ee55d31 (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
- Files:
-
- 16 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/digraph.h
r877 r983 313 313 /// Sets the iterator to the first arc of the given digraph. 314 314 /// 315 explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }315 explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); } 316 316 /// Sets the iterator to the given arc. 317 317 -
lemon/concepts/digraph.h
r982 r983 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). … … 36 36 /// \brief Class describing the concept of directed graphs. 37 37 /// 38 /// This class describes the \ref concept "concept" of the39 /// immutable directed digraphs.38 /// This class describes the common interface of all directed 39 /// graphs (digraphs). 40 40 /// 41 /// Note that actual digraph implementation like @ref ListDigraph or 42 /// @ref SmartDigraph may have several additional functionality. 41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// directed graphs should compile with this class, but it will not 44 /// run properly, of course. 45 /// An actual digraph implementation like \ref ListDigraph or 46 /// \ref SmartDigraph may have additional functionality. 43 47 /// 44 /// \sa concept48 /// \sa Graph 45 49 class Digraph { 46 50 private: 47 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 48 49 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 50 /// 51 Digraph(const Digraph &) {}; 52 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are 53 ///\e not allowed. Use DigraphCopy() instead. 54 55 ///Assignment of \ref Digraph "Digraph"s to another ones are 56 ///\e not allowed. Use DigraphCopy() instead. 57 51 /// Diraphs are \e not copy constructible. Use DigraphCopy instead. 52 Digraph(const Digraph &) {} 53 /// \brief Assignment of a digraph to another one is \e not allowed. 54 /// Use DigraphCopy instead. 58 55 void operator=(const Digraph &) {} 56 59 57 public: 60 ///\e 61 62 /// Defalult constructor. 63 64 /// Defalult constructor. 65 /// 58 /// Default constructor. 66 59 Digraph() { } 67 /// Class for identifying a node of the digraph 60 61 /// The node type of the digraph 68 62 69 63 /// This class identifies a node of the digraph. It also serves 70 64 /// as a base class of the node iterators, 71 /// thus they willconvert to this type.65 /// thus they convert to this type. 72 66 class Node { 73 67 public: 74 68 /// Default constructor 75 69 76 /// @warning The default constructor sets the iterator77 /// to an undefined value.70 /// Default constructor. 71 /// \warning It sets the object to an undefined value. 78 72 Node() { } 79 73 /// Copy constructor. … … 83 77 Node(const Node&) { } 84 78 85 /// Invalid constructor \& conversion.86 87 /// This constructor initializes the iteratorto be invalid.79 /// %Invalid constructor \& conversion. 80 81 /// Initializes the object to be invalid. 88 82 /// \sa Invalid for more details. 89 83 Node(Invalid) { } 90 84 /// Equality operator 91 85 86 /// Equality operator. 87 /// 92 88 /// Two iterators are equal if and only if they point to the 93 /// same object or both are invalid.89 /// same object or both are \c INVALID. 94 90 bool operator==(Node) const { return true; } 95 91 96 92 /// Inequality operator 97 93 98 /// \sa operator==(Node n) 99 /// 94 /// Inequality operator. 100 95 bool operator!=(Node) const { return true; } 101 96 102 97 /// Artificial ordering operator. 103 98 104 /// To allow the use of digraph descriptors as key type in std::map or 105 /// similar associative container we require this. 106 /// 107 /// \note This operator only have to define some strict ordering of 108 /// the items; this order has nothing to do with the iteration 109 /// ordering of the items. 99 /// Artificial ordering operator. 100 /// 101 /// \note This operator only has to define some strict ordering of 102 /// the nodes; this order has nothing to do with the iteration 103 /// ordering of the nodes. 110 104 bool operator<(Node) const { return false; } 111 112 }; 113 114 /// This iterator goes through each node. 115 116 /// This iterator goes through each node. 117 /// Its usage is quite simple, for example you can count the number 118 /// of nodes in digraph \c g of type \c Digraph like this: 105 }; 106 107 /// Iterator class for the nodes. 108 109 /// This iterator goes through each node of the digraph. 110 /// Its usage is quite simple, for example, you can count the number 111 /// of nodes in a digraph \c g of type \c %Digraph like this: 119 112 ///\code 120 113 /// int count=0; … … 125 118 /// Default constructor 126 119 127 /// @warning The default constructor sets the iterator128 /// to an undefined value.120 /// Default constructor. 121 /// \warning It sets the iterator to an undefined value. 129 122 NodeIt() { } 130 123 /// Copy constructor. … … 133 126 /// 134 127 NodeIt(const NodeIt& n) : Node(n) { } 135 /// Invalid constructor \& conversion.136 137 /// Initialize the iterator to be invalid.128 /// %Invalid constructor \& conversion. 129 130 /// Initializes the iterator to be invalid. 138 131 /// \sa Invalid for more details. 139 132 NodeIt(Invalid) { } 140 133 /// Sets the iterator to the first node. 141 134 142 /// Sets the iterator to the first node of \c g. 143 /// 144 NodeIt(const Digraph&) { } 145 /// Node -> NodeIt conversion. 146 147 /// Sets the iterator to the node of \c the digraph pointed by 148 /// the trivial iterator. 149 /// This feature necessitates that each time we 150 /// iterate the arc-set, the iteration order is the same. 135 /// Sets the iterator to the first node of the given digraph. 136 /// 137 explicit NodeIt(const Digraph&) { } 138 /// Sets the iterator to the given node. 139 140 /// Sets the iterator to the given node of the given digraph. 141 /// 151 142 NodeIt(const Digraph&, const Node&) { } 152 143 /// Next node. … … 158 149 159 150 160 /// Class for identifying an arcof the digraph151 /// The arc type of the digraph 161 152 162 153 /// This class identifies an arc of the digraph. It also serves … … 167 158 /// Default constructor 168 159 169 /// @warning The default constructor sets the iterator170 /// to an undefined value.160 /// Default constructor. 161 /// \warning It sets the object to an undefined value. 171 162 Arc() { } 172 163 /// Copy constructor. … … 175 166 /// 176 167 Arc(const Arc&) { } 177 /// Initialize the iterator to be invalid.178 179 /// Initialize the iteratorto be invalid.180 /// 168 /// %Invalid constructor \& conversion. 169 170 /// Initializes the object to be invalid. 171 /// \sa Invalid for more details. 181 172 Arc(Invalid) { } 182 173 /// Equality operator 183 174 175 /// Equality operator. 176 /// 184 177 /// Two iterators are equal if and only if they point to the 185 /// same object or both are invalid.178 /// same object or both are \c INVALID. 186 179 bool operator==(Arc) const { return true; } 187 180 /// Inequality operator 188 181 189 /// \sa operator==(Arc n) 190 /// 182 /// Inequality operator. 191 183 bool operator!=(Arc) const { return true; } 192 184 193 185 /// Artificial ordering operator. 194 186 195 /// To allow the use of digraph descriptors as key type in std::map or 196 /// similar associative container we require this. 197 /// 198 /// \note This operator only have to define some strict ordering of 199 /// the items; this order has nothing to do with the iteration 200 /// ordering of the items. 187 /// Artificial ordering operator. 188 /// 189 /// \note This operator only has to define some strict ordering of 190 /// the arcs; this order has nothing to do with the iteration 191 /// ordering of the arcs. 201 192 bool operator<(Arc) const { return false; } 202 193 }; 203 194 204 /// This iterator goes troughthe outgoing arcs of a node.195 /// Iterator class for the outgoing arcs of a node. 205 196 206 197 /// This iterator goes trough the \e outgoing arcs of a certain node 207 198 /// of a digraph. 208 /// Its usage is quite simple, for example you can count the number199 /// Its usage is quite simple, for example, you can count the number 209 200 /// of outgoing arcs of a node \c n 210 /// in digraph \c g of type \cDigraph as follows.201 /// in a digraph \c g of type \c %Digraph as follows. 211 202 ///\code 212 203 /// int count=0; 213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 214 205 ///\endcode 215 216 206 class OutArcIt : public Arc { 217 207 public: 218 208 /// Default constructor 219 209 220 /// @warning The default constructor sets the iterator221 /// to an undefined value.210 /// Default constructor. 211 /// \warning It sets the iterator to an undefined value. 222 212 OutArcIt() { } 223 213 /// Copy constructor. … … 226 216 /// 227 217 OutArcIt(const OutArcIt& e) : Arc(e) { } 228 /// Initialize the iterator to be invalid.229 230 /// Initialize the iterator to be invalid.231 /// 218 /// %Invalid constructor \& conversion. 219 220 /// Initializes the iterator to be invalid. 221 /// \sa Invalid for more details. 232 222 OutArcIt(Invalid) { } 233 /// This constructor sets the iterator to the first outgoing arc.234 235 /// This constructor sets the iterator to the first outgoing arc of236 /// the node.223 /// Sets the iterator to the first outgoing arc. 224 225 /// Sets the iterator to the first outgoing arc of the given node. 226 /// 237 227 OutArcIt(const Digraph&, const Node&) { } 238 /// Arc -> OutArcIt conversion 239 240 /// Sets the iterator to the value of the trivial iterator. 241 /// This feature necessitates that each time we 242 /// iterate the arc-set, the iteration order is the same. 228 /// Sets the iterator to the given arc. 229 230 /// Sets the iterator to the given arc of the given digraph. 231 /// 243 232 OutArcIt(const Digraph&, const Arc&) { } 244 /// Next outgoing arc233 /// Next outgoing arc 245 234 246 235 /// Assign the iterator to the next … … 249 238 }; 250 239 251 /// This iterator goes troughthe incoming arcs of a node.240 /// Iterator class for the incoming arcs of a node. 252 241 253 242 /// This iterator goes trough the \e incoming arcs of a certain node 254 243 /// of a digraph. 255 /// Its usage is quite simple, for example you can count the number256 /// of outgoing arcs of a node \c n257 /// in digraph \c g of type \cDigraph as follows.244 /// Its usage is quite simple, for example, you can count the number 245 /// of incoming arcs of a node \c n 246 /// in a digraph \c g of type \c %Digraph as follows. 258 247 ///\code 259 248 /// int count=0; 260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 261 250 ///\endcode 262 263 251 class InArcIt : public Arc { 264 252 public: 265 253 /// Default constructor 266 254 267 /// @warning The default constructor sets the iterator268 /// to an undefined value.255 /// Default constructor. 256 /// \warning It sets the iterator to an undefined value. 269 257 InArcIt() { } 270 258 /// Copy constructor. … … 273 261 /// 274 262 InArcIt(const InArcIt& e) : Arc(e) { } 275 /// Initialize the iterator to be invalid.276 277 /// Initialize the iterator to be invalid.278 /// 263 /// %Invalid constructor \& conversion. 264 265 /// Initializes the iterator to be invalid. 266 /// \sa Invalid for more details. 279 267 InArcIt(Invalid) { } 280 /// This constructor sets the iterator tofirst incoming arc.281 282 /// This constructor set the iterator to the first incoming arc of283 /// the node.268 /// Sets the iterator to the first incoming arc. 269 270 /// Sets the iterator to the first incoming arc of the given node. 271 /// 284 272 InArcIt(const Digraph&, const Node&) { } 285 /// Arc -> InArcIt conversion 286 287 /// Sets the iterator to the value of the trivial iterator \c e. 288 /// This feature necessitates that each time we 289 /// iterate the arc-set, the iteration order is the same. 273 /// Sets the iterator to the given arc. 274 275 /// Sets the iterator to the given arc of the given digraph. 276 /// 290 277 InArcIt(const Digraph&, const Arc&) { } 291 278 /// Next incoming arc 292 279 293 /// Assign the iterator to the next inarc of the corresponding node.294 /// 280 /// Assign the iterator to the next 281 /// incoming arc of the corresponding node. 295 282 InArcIt& operator++() { return *this; } 296 283 }; 297 /// This iterator goes through each arc. 298 299 /// This iterator goes through each arc of a digraph. 300 /// Its usage is quite simple, for example you can count the number 301 /// of arcs in a digraph \c g of type \c Digraph as follows: 284 285 /// Iterator class for the arcs. 286 287 /// This iterator goes through each arc of the digraph. 288 /// Its usage is quite simple, for example, you can count the number 289 /// of arcs in a digraph \c g of type \c %Digraph as follows: 302 290 ///\code 303 291 /// int count=0; 304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; 305 293 ///\endcode 306 294 class ArcIt : public Arc { … … 308 296 /// Default constructor 309 297 310 /// @warning The default constructor sets the iterator311 /// to an undefined value.298 /// Default constructor. 299 /// \warning It sets the iterator to an undefined value. 312 300 ArcIt() { } 313 301 /// Copy constructor. … … 316 304 /// 317 305 ArcIt(const ArcIt& e) : Arc(e) { } 318 /// Initialize the iterator to be invalid.319 320 /// Initialize the iterator to be invalid.321 /// 306 /// %Invalid constructor \& conversion. 307 308 /// Initializes the iterator to be invalid. 309 /// \sa Invalid for more details. 322 310 ArcIt(Invalid) { } 323 /// This constructor sets the iterator to the first arc. 324 325 /// This constructor sets the iterator to the first arc of \c g. 326 ///@param g the digraph 327 ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); } 328 /// Arc -> ArcIt conversion 329 330 /// Sets the iterator to the value of the trivial iterator \c e. 331 /// This feature necessitates that each time we 332 /// iterate the arc-set, the iteration order is the same. 311 /// Sets the iterator to the first arc. 312 313 /// Sets the iterator to the first arc of the given digraph. 314 /// 315 explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); } 316 /// Sets the iterator to the given arc. 317 318 /// Sets the iterator to the given arc of the given digraph. 319 /// 333 320 ArcIt(const Digraph&, const Arc&) { } 334 /// Next arc321 /// Next arc 335 322 336 323 /// Assign the iterator to the next arc. 324 /// 337 325 ArcIt& operator++() { return *this; } 338 326 }; 339 ///Gives back the target node of an arc. 340 341 ///Gives back the target node of an arc. 342 /// 327 328 /// \brief The source node of the arc. 329 /// 330 /// Returns the source node of the given arc. 331 Node source(Arc) const { return INVALID; } 332 333 /// \brief The target node of the arc. 334 /// 335 /// Returns the target node of the given arc. 343 336 Node target(Arc) const { return INVALID; } 344 ///Gives back the source node of an arc. 345 346 ///Gives back the source node of an arc. 347 /// 348 Node source(Arc) const { return INVALID; } 349 350 /// \brief Returns the ID of the node. 337 338 /// \brief The ID of the node. 339 /// 340 /// Returns the ID of the given node. 351 341 int id(Node) const { return -1; } 352 342 353 /// \brief Returns the ID of the arc. 343 /// \brief The ID of the arc. 344 /// 345 /// Returns the ID of the given arc. 354 346 int id(Arc) const { return -1; } 355 347 356 /// \brief Returns the node with the given ID. 357 /// 358 /// \pre The argument should be a valid node ID in the graph. 348 /// \brief The node with the given ID. 349 /// 350 /// Returns the node with the given ID. 351 /// \pre The argument should be a valid node ID in the digraph. 359 352 Node nodeFromId(int) const { return INVALID; } 360 353 361 /// \brief Returns the arc with the given ID. 362 /// 363 /// \pre The argument should be a valid arc ID in the graph. 354 /// \brief The arc with the given ID. 355 /// 356 /// Returns the arc with the given ID. 357 /// \pre The argument should be a valid arc ID in the digraph. 364 358 Arc arcFromId(int) const { return INVALID; } 365 359 366 /// \brief Returns an upper bound on the node IDs. 360 /// \brief An upper bound on the node IDs. 361 /// 362 /// Returns an upper bound on the node IDs. 367 363 int maxNodeId() const { return -1; } 368 364 369 /// \brief Returns an upper bound on the arc IDs. 365 /// \brief An upper bound on the arc IDs. 366 /// 367 /// Returns an upper bound on the arc IDs. 370 368 int maxArcId() const { return -1; } 371 369 … … 393 391 int maxId(Arc) const { return -1; } 394 392 393 /// \brief The opposite node on the arc. 394 /// 395 /// Returns the opposite node on the given arc. 396 Node oppositeNode(Node, Arc) const { return INVALID; } 397 395 398 /// \brief The base node of the iterator. 396 399 /// 397 /// Gives back the base node of the iterator.398 /// It is always the target of the pointed arc.399 Node baseNode( const InArcIt&) const { return INVALID; }400 /// Returns the base node of the given outgoing arc iterator 401 /// (i.e. the source node of the corresponding arc). 402 Node baseNode(OutArcIt) const { return INVALID; } 400 403 401 404 /// \brief The running node of the iterator. 402 405 /// 403 /// Gives back the running node of the iterator.404 /// It is always the source of the pointed arc.405 Node runningNode( const InArcIt&) const { return INVALID; }406 /// Returns the running node of the given outgoing arc iterator 407 /// (i.e. the target node of the corresponding arc). 408 Node runningNode(OutArcIt) const { return INVALID; } 406 409 407 410 /// \brief The base node of the iterator. 408 411 /// 409 /// Gives back the base node of the iterator.410 /// It is always the source of the pointed arc.411 Node baseNode( const OutArcIt&) const { return INVALID; }412 /// Returns the base node of the given incomming arc iterator 413 /// (i.e. the target node of the corresponding arc). 414 Node baseNode(InArcIt) const { return INVALID; } 412 415 413 416 /// \brief The running node of the iterator. 414 417 /// 415 /// Gives back the running node of the iterator. 416 /// It is always the target of the pointed arc. 417 Node runningNode(const OutArcIt&) const { return INVALID; } 418 419 /// \brief The opposite node on the given arc. 420 /// 421 /// Gives back the opposite node on the given arc. 422 Node oppositeNode(const Node&, const Arc&) const { return INVALID; } 423 424 /// \brief Reference map of the nodes to type \c T. 425 /// 426 /// Reference map of the nodes to type \c T. 418 /// Returns the running node of the given incomming arc iterator 419 /// (i.e. the source node of the corresponding arc). 420 Node runningNode(InArcIt) const { return INVALID; } 421 422 /// \brief Standard graph map type for the nodes. 423 /// 424 /// Standard graph map type for the nodes. 425 /// It conforms to the ReferenceMap concept. 427 426 template<class T> 428 427 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 429 428 public: 430 429 431 /// \e432 NodeMap(const Digraph&) { }433 /// \e430 /// Constructor 431 explicit NodeMap(const Digraph&) { } 432 /// Constructor with given initial value 434 433 NodeMap(const Digraph&, T) { } 435 434 436 435 private: 437 436 ///Copy constructor 438 NodeMap(const NodeMap& nm) : 437 NodeMap(const NodeMap& nm) : 439 438 ReferenceMap<Node, T, T&, const T&>(nm) { } 440 439 ///Assignment operator … … 446 445 }; 447 446 448 /// \brief Reference map of the arcs to type \c T. 449 /// 450 /// Reference map of the arcs to type \c T. 447 /// \brief Standard graph map type for the arcs. 448 /// 449 /// Standard graph map type for the arcs. 450 /// It conforms to the ReferenceMap concept. 451 451 template<class T> 452 452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 453 453 public: 454 454 455 /// \e456 ArcMap(const Digraph&) { }457 /// \e455 /// Constructor 456 explicit ArcMap(const Digraph&) { } 457 /// Constructor with given initial value 458 458 ArcMap(const Digraph&, T) { } 459 459 460 private: 460 461 ///Copy constructor -
lemon/concepts/graph.h
r877 r983 397 397 /// Sets the iterator to the first arc of the given graph. 398 398 /// 399 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }399 explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); } 400 400 /// Sets the iterator to the given arc. 401 401 … … 443 443 /// 444 444 OutArcIt(const Graph& n, const Node& g) { 445 ignore_unused_variable_warning(n);446 ignore_unused_variable_warning(g);445 ::lemon::ignore_unused_variable_warning(n); 446 ::lemon::ignore_unused_variable_warning(g); 447 447 } 448 448 /// Sets the iterator to the given arc. … … 491 491 /// 492 492 InArcIt(const Graph& g, const Node& n) { 493 ignore_unused_variable_warning(n);494 ignore_unused_variable_warning(g);493 ::lemon::ignore_unused_variable_warning(n); 494 ::lemon::ignore_unused_variable_warning(g); 495 495 } 496 496 /// Sets the iterator to the given arc. -
lemon/concepts/graph.h
r982 r983 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 Undirected Graphs.21 ///\brief The concept of undirected graphs. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_H … … 25 25 26 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/maps.h> 28 #include <lemon/concept_check.h> 27 29 #include <lemon/core.h> 28 30 … … 32 34 /// \ingroup graph_concepts 33 35 /// 34 /// \brief Class describing the concept of Undirected Graphs.36 /// \brief Class describing the concept of undirected graphs. 35 37 /// 36 /// This class describes the common interface of all Undirected37 /// Graphs.38 /// This class describes the common interface of all undirected 39 /// graphs. 38 40 /// 39 /// As all concept describing classes it provides onlyinterface40 /// without any sensible implementation. So any algorithm for41 /// undirected graph should compile with this class, but it will not41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// undirected graphs should compile with this class, but it will not 42 44 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or 46 /// \ref SmartGraph may have additional functionality. 43 47 /// 44 /// The LEMON undirected graphs also fulfill the concept of 45 /// directed graphs (\ref lemon::concepts::Digraph "Digraph 46 /// Concept"). Each edges can be seen as two opposite 47 /// directed arc and consequently the undirected graph can be 48 /// seen as the direceted graph of these directed arcs. The 49 /// Graph has the Edge inner class for the edges and 50 /// the Arc type for the directed arcs. The Arc type is 51 /// convertible to Edge or inherited from it so from a directed 52 /// arc we can get the represented edge. 48 /// The undirected graphs also fulfill the concept of \ref Digraph 49 /// "directed graphs", since each edge can also be regarded as two 50 /// oppositely directed arcs. 51 /// Undirected graphs provide an Edge type for the undirected edges and 52 /// an Arc type for the directed arcs. The Arc type is convertible to 53 /// Edge or inherited from it, i.e. the corresponding edge can be 54 /// obtained from an arc. 55 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt 56 /// and ArcMap classes can be used for the arcs (just like in digraphs). 57 /// Both InArcIt and OutArcIt iterates on the same edges but with 58 /// opposite direction. IncEdgeIt also iterates on the same edges 59 /// as OutArcIt and InArcIt, but it is not convertible to Arc, 60 /// only to Edge. 53 61 /// 54 /// In the sense of the LEMON each edge has a default 55 /// direction (it should be in every computer implementation, 56 /// because the order of edge's nodes defines an 57 /// orientation). With the default orientation we can define that 58 /// the directed arc is forward or backward directed. With the \c 59 /// direction() and \c direct() function we can get the direction 60 /// of the directed arc and we can direct an edge. 62 /// In LEMON, each undirected edge has an inherent orientation. 63 /// Thus it can defined if an arc is forward or backward oriented in 64 /// an undirected graph with respect to this default oriantation of 65 /// the represented edge. 66 /// With the direction() and direct() functions the direction 67 /// of an arc can be obtained and set, respectively. 61 68 /// 62 /// The EdgeIt is an iterator for the edges. We can use 63 /// the EdgeMap to map values for the edges. The InArcIt and 64 /// OutArcIt iterates on the same edges but with opposite 65 /// direction. The IncEdgeIt iterates also on the same edges 66 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 67 /// to Edge. 69 /// Only nodes and edges can be added to or removed from an undirected 70 /// graph and the corresponding arcs are added or removed automatically. 71 /// 72 /// \sa Digraph 68 73 class Graph { 74 private: 75 /// Graphs are \e not copy constructible. Use DigraphCopy instead. 76 Graph(const Graph&) {} 77 /// \brief Assignment of a graph to another one is \e not allowed. 78 /// Use DigraphCopy instead. 79 void operator=(const Graph&) {} 80 69 81 public: 70 /// \brief The undirected graph should be tagged by the 71 /// UndirectedTag. 72 /// 73 /// The undirected graph should be tagged by the UndirectedTag. This 74 /// tag helps the enable_if technics to make compile time 82 /// Default constructor. 83 Graph() {} 84 85 /// \brief Undirected graphs should be tagged with \c UndirectedTag. 86 /// 87 /// Undirected graphs should be tagged with \c UndirectedTag. 88 /// 89 /// This tag helps the \c enable_if technics to make compile time 75 90 /// specializations for undirected graphs. 76 91 typedef True UndirectedTag; 77 92 78 /// \brief The base type of node iterators, 79 /// or in other words, the trivial node iterator. 80 /// 81 /// This is the base type of each node iterator, 82 /// thus each kind of node iterator converts to this. 83 /// More precisely each kind of node iterator should be inherited 84 /// from the trivial node iterator. 93 /// The node type of the graph 94 95 /// This class identifies a node of the graph. It also serves 96 /// as a base class of the node iterators, 97 /// thus they convert to this type. 85 98 class Node { 86 99 public: 87 100 /// Default constructor 88 101 89 /// @warning The default constructor sets the iterator90 /// to an undefined value.102 /// Default constructor. 103 /// \warning It sets the object to an undefined value. 91 104 Node() { } 92 105 /// Copy constructor. … … 96 109 Node(const Node&) { } 97 110 98 /// Invalid constructor \& conversion.99 100 /// This constructor initializes the iteratorto be invalid.111 /// %Invalid constructor \& conversion. 112 113 /// Initializes the object to be invalid. 101 114 /// \sa Invalid for more details. 102 115 Node(Invalid) { } 103 116 /// Equality operator 104 117 118 /// Equality operator. 119 /// 105 120 /// Two iterators are equal if and only if they point to the 106 /// same object or both are invalid.121 /// same object or both are \c INVALID. 107 122 bool operator==(Node) const { return true; } 108 123 109 124 /// Inequality operator 110 125 111 /// \sa operator==(Node n) 112 /// 126 /// Inequality operator. 113 127 bool operator!=(Node) const { return true; } 114 128 115 129 /// Artificial ordering operator. 116 130 117 /// To allow the use of graph descriptors as key type in std::map or 118 /// similar associative container we require this. 119 /// 120 /// \note This operator only have to define some strict ordering of 131 /// Artificial ordering operator. 132 /// 133 /// \note This operator only has to define some strict ordering of 121 134 /// the items; this order has nothing to do with the iteration 122 135 /// ordering of the items. … … 125 138 }; 126 139 127 /// This iterator goes through each node.128 129 /// This iterator goes through each node .130 /// Its usage is quite simple, for example you can count the number131 /// of nodes in graph \c g of type \cGraph like this:140 /// Iterator class for the nodes. 141 142 /// This iterator goes through each node of the graph. 143 /// Its usage is quite simple, for example, you can count the number 144 /// of nodes in a graph \c g of type \c %Graph like this: 132 145 ///\code 133 146 /// int count=0; … … 138 151 /// Default constructor 139 152 140 /// @warning The default constructor sets the iterator141 /// to an undefined value.153 /// Default constructor. 154 /// \warning It sets the iterator to an undefined value. 142 155 NodeIt() { } 143 156 /// Copy constructor. … … 146 159 /// 147 160 NodeIt(const NodeIt& n) : Node(n) { } 148 /// Invalid constructor \& conversion.149 150 /// Initialize the iterator to be invalid.161 /// %Invalid constructor \& conversion. 162 163 /// Initializes the iterator to be invalid. 151 164 /// \sa Invalid for more details. 152 165 NodeIt(Invalid) { } 153 166 /// Sets the iterator to the first node. 154 167 155 /// Sets the iterator to the first node of \c g. 156 /// 157 NodeIt(const Graph&) { } 158 /// Node -> NodeIt conversion. 159 160 /// Sets the iterator to the node of \c the graph pointed by 161 /// the trivial iterator. 162 /// This feature necessitates that each time we 163 /// iterate the arc-set, the iteration order is the same. 168 /// Sets the iterator to the first node of the given digraph. 169 /// 170 explicit NodeIt(const Graph&) { } 171 /// Sets the iterator to the given node. 172 173 /// Sets the iterator to the given node of the given digraph. 174 /// 164 175 NodeIt(const Graph&, const Node&) { } 165 176 /// Next node. … … 171 182 172 183 173 /// The base type of the edge iterators. 174 175 /// The base type of the edge iterators. 176 /// 184 /// The edge type of the graph 185 186 /// This class identifies an edge of the graph. It also serves 187 /// as a base class of the edge iterators, 188 /// thus they will convert to this type. 177 189 class Edge { 178 190 public: 179 191 /// Default constructor 180 192 181 /// @warning The default constructor sets the iterator182 /// to an undefined value.193 /// Default constructor. 194 /// \warning It sets the object to an undefined value. 183 195 Edge() { } 184 196 /// Copy constructor. … … 187 199 /// 188 200 Edge(const Edge&) { } 189 /// Initialize the iterator to be invalid.190 191 /// Initialize the iteratorto be invalid.192 /// 201 /// %Invalid constructor \& conversion. 202 203 /// Initializes the object to be invalid. 204 /// \sa Invalid for more details. 193 205 Edge(Invalid) { } 194 206 /// Equality operator 195 207 208 /// Equality operator. 209 /// 196 210 /// Two iterators are equal if and only if they point to the 197 /// same object or both are invalid.211 /// same object or both are \c INVALID. 198 212 bool operator==(Edge) const { return true; } 199 213 /// Inequality operator 200 214 201 /// \sa operator==(Edge n) 202 /// 215 /// Inequality operator. 203 216 bool operator!=(Edge) const { return true; } 204 217 205 218 /// Artificial ordering operator. 206 219 207 /// To allow the use of graph descriptors as key type in std::map or 208 /// similar associative container we require this. 209 /// 210 /// \note This operator only have to define some strict ordering of 211 /// the items; this order has nothing to do with the iteration 212 /// ordering of the items. 220 /// Artificial ordering operator. 221 /// 222 /// \note This operator only has to define some strict ordering of 223 /// the edges; this order has nothing to do with the iteration 224 /// ordering of the edges. 213 225 bool operator<(Edge) const { return false; } 214 226 }; 215 227 216 /// This iterator goes through each edge.217 218 /// This iterator goes through each edge of agraph.219 /// Its usage is quite simple, for example you can count the number220 /// of edges in a graph \c g of type \c Graph as follows:228 /// Iterator class for the edges. 229 230 /// This iterator goes through each edge of the graph. 231 /// Its usage is quite simple, for example, you can count the number 232 /// of edges in a graph \c g of type \c %Graph as follows: 221 233 ///\code 222 234 /// int count=0; … … 227 239 /// Default constructor 228 240 229 /// @warning The default constructor sets the iterator230 /// to an undefined value.241 /// Default constructor. 242 /// \warning It sets the iterator to an undefined value. 231 243 EdgeIt() { } 232 244 /// Copy constructor. … … 235 247 /// 236 248 EdgeIt(const EdgeIt& e) : Edge(e) { } 237 /// Initialize the iterator to be invalid.238 239 /// Initialize the iterator to be invalid.240 /// 249 /// %Invalid constructor \& conversion. 250 251 /// Initializes the iterator to be invalid. 252 /// \sa Invalid for more details. 241 253 EdgeIt(Invalid) { } 242 /// This constructor sets the iterator to the first edge. 243 244 /// This constructor sets the iterator to the first edge. 245 EdgeIt(const Graph&) { } 246 /// Edge -> EdgeIt conversion 247 248 /// Sets the iterator to the value of the trivial iterator. 249 /// This feature necessitates that each time we 250 /// iterate the edge-set, the iteration order is the 251 /// same. 254 /// Sets the iterator to the first edge. 255 256 /// Sets the iterator to the first edge of the given graph. 257 /// 258 explicit EdgeIt(const Graph&) { } 259 /// Sets the iterator to the given edge. 260 261 /// Sets the iterator to the given edge of the given graph. 262 /// 252 263 EdgeIt(const Graph&, const Edge&) { } 253 264 /// Next edge 254 265 255 266 /// Assign the iterator to the next edge. 267 /// 256 268 EdgeIt& operator++() { return *this; } 257 269 }; 258 270 259 /// \brief This iterator goes trough the incident undirected 260 /// arcs of a node. 261 /// 262 /// This iterator goes trough the incident edges 263 /// of a certain node of a graph. You should assume that the 264 /// loop arcs will be iterated twice. 265 /// 266 /// Its usage is quite simple, for example you can compute the 267 /// degree (i.e. count the number of incident arcs of a node \c n 268 /// in graph \c g of type \c Graph as follows. 271 /// Iterator class for the incident edges of a node. 272 273 /// This iterator goes trough the incident undirected edges 274 /// of a certain node of a graph. 275 /// Its usage is quite simple, for example, you can compute the 276 /// degree (i.e. the number of incident edges) of a node \c n 277 /// in a graph \c g of type \c %Graph as follows. 269 278 /// 270 279 ///\code … … 272 281 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 273 282 ///\endcode 283 /// 284 /// \warning Loop edges will be iterated twice. 274 285 class IncEdgeIt : public Edge { 275 286 public: 276 287 /// Default constructor 277 288 278 /// @warning The default constructor sets the iterator279 /// to an undefined value.289 /// Default constructor. 290 /// \warning It sets the iterator to an undefined value. 280 291 IncEdgeIt() { } 281 292 /// Copy constructor. … … 284 295 /// 285 296 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 286 /// Initialize the iterator to be invalid.287 288 /// Initialize the iterator to be invalid.289 /// 297 /// %Invalid constructor \& conversion. 298 299 /// Initializes the iterator to be invalid. 300 /// \sa Invalid for more details. 290 301 IncEdgeIt(Invalid) { } 291 /// This constructor sets the iterator to first incident arc.292 293 /// This constructor set the iterator to the first incident arc of294 /// the node.302 /// Sets the iterator to the first incident edge. 303 304 /// Sets the iterator to the first incident edge of the given node. 305 /// 295 306 IncEdgeIt(const Graph&, const Node&) { } 296 /// Edge -> IncEdgeIt conversion 297 298 /// Sets the iterator to the value of the trivial iterator \c e. 299 /// This feature necessitates that each time we 300 /// iterate the arc-set, the iteration order is the same. 307 /// Sets the iterator to the given edge. 308 309 /// Sets the iterator to the given edge of the given graph. 310 /// 301 311 IncEdgeIt(const Graph&, const Edge&) { } 302 /// Next incident arc303 304 /// Assign the iterator to the next incident arc312 /// Next incident edge 313 314 /// Assign the iterator to the next incident edge 305 315 /// of the corresponding node. 306 316 IncEdgeIt& operator++() { return *this; } 307 317 }; 308 318 309 /// The directed arc type.310 311 /// Th e directed arc type. It can be converted to the312 /// edge or it should be inherited from the undirected313 /// edge.319 /// The arc type of the graph 320 321 /// This class identifies a directed arc of the graph. It also serves 322 /// as a base class of the arc iterators, 323 /// thus they will convert to this type. 314 324 class Arc { 315 325 public: 316 326 /// Default constructor 317 327 318 /// @warning The default constructor sets the iterator319 /// to an undefined value.328 /// Default constructor. 329 /// \warning It sets the object to an undefined value. 320 330 Arc() { } 321 331 /// Copy constructor. … … 324 334 /// 325 335 Arc(const Arc&) { } 326 /// Initialize the iterator to be invalid.327 328 /// Initialize the iteratorto be invalid.329 /// 336 /// %Invalid constructor \& conversion. 337 338 /// Initializes the object to be invalid. 339 /// \sa Invalid for more details. 330 340 Arc(Invalid) { } 331 341 /// Equality operator 332 342 343 /// Equality operator. 344 /// 333 345 /// Two iterators are equal if and only if they point to the 334 /// same object or both are invalid.346 /// same object or both are \c INVALID. 335 347 bool operator==(Arc) const { return true; } 336 348 /// Inequality operator 337 349 338 /// \sa operator==(Arc n) 339 /// 350 /// Inequality operator. 340 351 bool operator!=(Arc) const { return true; } 341 352 342 353 /// Artificial ordering operator. 343 354 344 /// To allow the use of graph descriptors as key type in std::map or 345 /// similar associative container we require this. 346 /// 347 /// \note This operator only have to define some strict ordering of 348 /// the items; this order has nothing to do with the iteration 349 /// ordering of the items. 355 /// Artificial ordering operator. 356 /// 357 /// \note This operator only has to define some strict ordering of 358 /// the arcs; this order has nothing to do with the iteration 359 /// ordering of the arcs. 350 360 bool operator<(Arc) const { return false; } 351 361 352 /// Converison to Edge 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 353 366 operator Edge() const { return Edge(); } 354 367 }; 355 /// This iterator goes through each directed arc. 356 357 /// This iterator goes through each arc of a graph. 358 /// Its usage is quite simple, for example you can count the number 359 /// of arcs in a graph \c g of type \c Graph as follows: 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 372 /// Its usage is quite simple, for example, you can count the number 373 /// of arcs in a graph \c g of type \c %Graph as follows: 360 374 ///\code 361 375 /// int count=0; 362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; 363 377 ///\endcode 364 378 class ArcIt : public Arc { … … 366 380 /// Default constructor 367 381 368 /// @warning The default constructor sets the iterator369 /// to an undefined value.382 /// Default constructor. 383 /// \warning It sets the iterator to an undefined value. 370 384 ArcIt() { } 371 385 /// Copy constructor. … … 374 388 /// 375 389 ArcIt(const ArcIt& e) : Arc(e) { } 376 /// Initialize the iterator to be invalid.377 378 /// Initialize the iterator to be invalid.379 /// 390 /// %Invalid constructor \& conversion. 391 392 /// Initializes the iterator to be invalid. 393 /// \sa Invalid for more details. 380 394 ArcIt(Invalid) { } 381 /// This constructor sets the iterator to the first arc. 382 383 /// This constructor sets the iterator to the first arc of \c g. 384 ///@param g the graph 385 ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); } 386 /// Arc -> ArcIt conversion 387 388 /// Sets the iterator to the value of the trivial iterator \c e. 389 /// This feature necessitates that each time we 390 /// iterate the arc-set, the iteration order is the same. 395 /// Sets the iterator to the first arc. 396 397 /// Sets the iterator to the first arc of the given graph. 398 /// 399 explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); } 400 /// Sets the iterator to the given arc. 401 402 /// Sets the iterator to the given arc of the given graph. 403 /// 391 404 ArcIt(const Graph&, const Arc&) { } 392 /// Next arc405 /// Next arc 393 406 394 407 /// Assign the iterator to the next arc. 408 /// 395 409 ArcIt& operator++() { return *this; } 396 410 }; 397 411 398 /// This iterator goes trough the outgoing directedarcs of a node.399 400 /// This iterator goes trough the \e outgoing arcs of a certain node401 /// of a graph.402 /// Its usage is quite simple, for example you can count the number412 /// Iterator class for the outgoing arcs of a node. 413 414 /// This iterator goes trough the \e outgoing directed arcs of a 415 /// certain node of a graph. 416 /// Its usage is quite simple, for example, you can count the number 403 417 /// of outgoing arcs of a node \c n 404 /// in graph \c g of type \cGraph as follows.418 /// in a graph \c g of type \c %Graph as follows. 405 419 ///\code 406 420 /// int count=0; 407 /// for ( Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;421 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 408 422 ///\endcode 409 410 423 class OutArcIt : public Arc { 411 424 public: 412 425 /// Default constructor 413 426 414 /// @warning The default constructor sets the iterator415 /// to an undefined value.427 /// Default constructor. 428 /// \warning It sets the iterator to an undefined value. 416 429 OutArcIt() { } 417 430 /// Copy constructor. … … 420 433 /// 421 434 OutArcIt(const OutArcIt& e) : Arc(e) { } 422 /// Initialize the iterator to be invalid.423 424 /// Initialize the iterator to be invalid.425 /// 435 /// %Invalid constructor \& conversion. 436 437 /// Initializes the iterator to be invalid. 438 /// \sa Invalid for more details. 426 439 OutArcIt(Invalid) { } 427 /// This constructor sets the iterator to the first outgoing arc. 428 429 /// This constructor sets the iterator to the first outgoing arc of 430 /// the node. 431 ///@param n the node 432 ///@param g the graph 440 /// Sets the iterator to the first outgoing arc. 441 442 /// Sets the iterator to the first outgoing arc of the given node. 443 /// 433 444 OutArcIt(const Graph& n, const Node& g) { 434 445 ::lemon::ignore_unused_variable_warning(n); 435 446 ::lemon::ignore_unused_variable_warning(g); 436 447 } 437 /// Arc -> OutArcIt conversion 438 439 /// Sets the iterator to the value of the trivial iterator. 440 /// This feature necessitates that each time we 441 /// iterate the arc-set, the iteration order is the same. 448 /// Sets the iterator to the given arc. 449 450 /// Sets the iterator to the given arc of the given graph. 451 /// 442 452 OutArcIt(const Graph&, const Arc&) { } 443 /// Next outgoing arc453 /// Next outgoing arc 444 454 445 455 /// Assign the iterator to the next … … 448 458 }; 449 459 450 /// This iterator goes trough the incoming directedarcs of a node.451 452 /// This iterator goes trough the \e incoming arcs of a certain node453 /// of a graph.454 /// Its usage is quite simple, for example you can count the number455 /// of outgoing arcs of a node \c n456 /// in graph \c g of type \cGraph as follows.460 /// Iterator class for the incoming arcs of a node. 461 462 /// This iterator goes trough the \e incoming directed arcs of a 463 /// certain node of a graph. 464 /// Its usage is quite simple, for example, you can count the number 465 /// of incoming arcs of a node \c n 466 /// in a graph \c g of type \c %Graph as follows. 457 467 ///\code 458 468 /// int count=0; 459 /// for (Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 460 470 ///\endcode 461 462 471 class InArcIt : public Arc { 463 472 public: 464 473 /// Default constructor 465 474 466 /// @warning The default constructor sets the iterator467 /// to an undefined value.475 /// Default constructor. 476 /// \warning It sets the iterator to an undefined value. 468 477 InArcIt() { } 469 478 /// Copy constructor. … … 472 481 /// 473 482 InArcIt(const InArcIt& e) : Arc(e) { } 474 /// Initialize the iterator to be invalid.475 476 /// Initialize the iterator to be invalid.477 /// 483 /// %Invalid constructor \& conversion. 484 485 /// Initializes the iterator to be invalid. 486 /// \sa Invalid for more details. 478 487 InArcIt(Invalid) { } 479 /// This constructor sets the iterator to first incoming arc. 480 481 /// This constructor set the iterator to the first incoming arc of 482 /// the node. 483 ///@param n the node 484 ///@param g the graph 488 /// Sets the iterator to the first incoming arc. 489 490 /// Sets the iterator to the first incoming arc of the given node. 491 /// 485 492 InArcIt(const Graph& g, const Node& n) { 486 493 ::lemon::ignore_unused_variable_warning(n); 487 494 ::lemon::ignore_unused_variable_warning(g); 488 495 } 489 /// Arc -> InArcIt conversion 490 491 /// Sets the iterator to the value of the trivial iterator \c e. 492 /// This feature necessitates that each time we 493 /// iterate the arc-set, the iteration order is the same. 496 /// Sets the iterator to the given arc. 497 498 /// Sets the iterator to the given arc of the given graph. 499 /// 494 500 InArcIt(const Graph&, const Arc&) { } 495 501 /// Next incoming arc 496 502 497 /// Assign the iterator to the next inarc of the corresponding node.498 /// 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node. 499 505 InArcIt& operator++() { return *this; } 500 506 }; 501 507 502 /// \brief Reference map of the nodes to type \c T. 503 /// 504 /// Reference map of the nodes to type \c T. 508 /// \brief Standard graph map type for the nodes. 509 /// 510 /// Standard graph map type for the nodes. 511 /// It conforms to the ReferenceMap concept. 505 512 template<class T> 506 513 class NodeMap : public ReferenceMap<Node, T, T&, const T&> … … 508 515 public: 509 516 510 /// \e511 NodeMap(const Graph&) { }512 /// \e517 /// Constructor 518 explicit NodeMap(const Graph&) { } 519 /// Constructor with given initial value 513 520 NodeMap(const Graph&, T) { } 514 521 … … 525 532 }; 526 533 527 /// \brief Reference map of the arcs to type \c T. 528 /// 529 /// Reference map of the arcs to type \c T. 534 /// \brief Standard graph map type for the arcs. 535 /// 536 /// Standard graph map type for the arcs. 537 /// It conforms to the ReferenceMap concept. 530 538 template<class T> 531 539 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> … … 533 541 public: 534 542 535 /// \e536 ArcMap(const Graph&) { }537 /// \e543 /// Constructor 544 explicit ArcMap(const Graph&) { } 545 /// Constructor with given initial value 538 546 ArcMap(const Graph&, T) { } 547 539 548 private: 540 549 ///Copy constructor … … 549 558 }; 550 559 551 /// Reference map of the edges to type \c T. 552 553 /// Reference map of the edges to type \c T. 560 /// \brief Standard graph map type for the edges. 561 /// 562 /// Standard graph map type for the edges. 563 /// It conforms to the ReferenceMap concept. 554 564 template<class T> 555 565 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> … … 557 567 public: 558 568 559 /// \e560 EdgeMap(const Graph&) { }561 /// \e569 /// Constructor 570 explicit EdgeMap(const Graph&) { } 571 /// Constructor with given initial value 562 572 EdgeMap(const Graph&, T) { } 573 563 574 private: 564 575 ///Copy constructor … … 573 584 }; 574 585 575 /// \brief Direct the given edge. 576 /// 577 /// Direct the given edge. The returned arc source 578 /// will be the given node. 579 Arc direct(const Edge&, const Node&) const { 580 return INVALID; 581 } 582 583 /// \brief Direct the given edge. 584 /// 585 /// Direct the given edge. The returned arc 586 /// represents the given edge and the direction comes 587 /// from the bool parameter. The source of the edge and 588 /// the directed arc is the same when the given bool is true. 589 Arc direct(const Edge&, bool) const { 590 return INVALID; 591 } 592 593 /// \brief Returns true if the arc has default orientation. 594 /// 595 /// Returns whether the given directed arc is same orientation as 596 /// the corresponding edge's default orientation. 597 bool direction(Arc) const { return true; } 598 599 /// \brief Returns the opposite directed arc. 600 /// 601 /// Returns the opposite directed arc. 602 Arc oppositeArc(Arc) const { return INVALID; } 603 604 /// \brief Opposite node on an arc 605 /// 606 /// \return The opposite of the given node on the given edge. 607 Node oppositeNode(Node, Edge) const { return INVALID; } 608 609 /// \brief First node of the edge. 610 /// 611 /// \return The first node of the given edge. 612 /// 613 /// Naturally edges don't have direction and thus 614 /// don't have source and target node. However we use \c u() and \c v() 615 /// methods to query the two nodes of the arc. The direction of the 616 /// arc which arises this way is called the inherent direction of the 617 /// edge, and is used to define the "default" direction 618 /// of the directed versions of the arcs. 586 /// \brief The first node of the edge. 587 /// 588 /// Returns the first node of the given edge. 589 /// 590 /// Edges don't have source and target nodes, however, methods 591 /// u() and v() are used to query the two end-nodes of an edge. 592 /// The orientation of an edge that arises this way is called 593 /// the inherent direction, it is used to define the default 594 /// direction for the corresponding arcs. 619 595 /// \sa v() 620 596 /// \sa direction() 621 597 Node u(Edge) const { return INVALID; } 622 598 623 /// \brief Second node of the edge. 624 /// 625 /// \return The second node of the given edge. 626 /// 627 /// Naturally edges don't have direction and thus 628 /// don't have source and target node. However we use \c u() and \c v() 629 /// methods to query the two nodes of the arc. The direction of the 630 /// arc which arises this way is called the inherent direction of the 631 /// edge, and is used to define the "default" direction 632 /// of the directed versions of the arcs. 599 /// \brief The second node of the edge. 600 /// 601 /// Returns the second node of the given edge. 602 /// 603 /// Edges don't have source and target nodes, however, methods 604 /// u() and v() are used to query the two end-nodes of an edge. 605 /// The orientation of an edge that arises this way is called 606 /// the inherent direction, it is used to define the default 607 /// direction for the corresponding arcs. 633 608 /// \sa u() 634 609 /// \sa direction() 635 610 Node v(Edge) const { return INVALID; } 636 611 637 /// \brief Source node of the directed arc. 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 638 615 Node source(Arc) const { return INVALID; } 639 616 640 /// \brief Target node of the directed arc. 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 641 620 Node target(Arc) const { return INVALID; } 642 621 643 /// \brief Returns the id of the node. 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 644 625 int id(Node) const { return -1; } 645 626 646 /// \brief Returns the id of the edge. 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 647 630 int id(Edge) const { return -1; } 648 631 649 /// \brief Returns the id of the arc. 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 650 635 int id(Arc) const { return -1; } 651 636 652 /// \brief Returns the node with the given id. 653 /// 654 /// \pre The argument should be a valid node id in the graph. 637 /// \brief The node with the given ID. 638 /// 639 /// Returns the node with the given ID. 640 /// \pre The argument should be a valid node ID in the graph. 655 641 Node nodeFromId(int) const { return INVALID; } 656 642 657 /// \brief Returns the edge with the given id. 658 /// 659 /// \pre The argument should be a valid edge id in the graph. 643 /// \brief The edge with the given ID. 644 /// 645 /// Returns the edge with the given ID. 646 /// \pre The argument should be a valid edge ID in the graph. 660 647 Edge edgeFromId(int) const { return INVALID; } 661 648 662 /// \brief Returns the arc with the given id. 663 /// 664 /// \pre The argument should be a valid arc id in the graph. 649 /// \brief The arc with the given ID. 650 /// 651 /// Returns the arc with the given ID. 652 /// \pre The argument should be a valid arc ID in the graph. 665 653 Arc arcFromId(int) const { return INVALID; } 666 654 667 /// \brief Returns an upper bound on the node IDs. 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 668 658 int maxNodeId() const { return -1; } 669 659 670 /// \brief Returns an upper bound on the edge IDs. 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 671 663 int maxEdgeId() const { return -1; } 672 664 673 /// \brief Returns an upper bound on the arc IDs. 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 674 668 int maxArcId() const { return -1; } 669 670 /// \brief The direction of the arc. 671 /// 672 /// Returns \c true if the direction of the given arc is the same as 673 /// the inherent orientation of the represented edge. 674 bool direction(Arc) const { return true; } 675 676 /// \brief Direct the edge. 677 /// 678 /// Direct the given edge. The returned arc 679 /// represents the given edge and its direction comes 680 /// from the bool parameter. If it is \c true, then the direction 681 /// of the arc is the same as the inherent orientation of the edge. 682 Arc direct(Edge, bool) const { 683 return INVALID; 684 } 685 686 /// \brief Direct the edge. 687 /// 688 /// Direct the given edge. The returned arc represents the given 689 /// edge and its source node is the given node. 690 Arc direct(Edge, Node) const { 691 return INVALID; 692 } 693 694 /// \brief The oppositely directed arc. 695 /// 696 /// Returns the oppositely directed arc representing the same edge. 697 Arc oppositeArc(Arc) const { return INVALID; } 698 699 /// \brief The opposite node on the edge. 700 /// 701 /// Returns the opposite node on the given edge. 702 Node oppositeNode(Node, Edge) const { return INVALID; } 675 703 676 704 void first(Node&) const {} … … 706 734 int maxId(Arc) const { return -1; } 707 735 708 /// \brief Base node of the iterator 709 /// 710 /// Returns the base node (the source in this case) of the iterator 711 Node baseNode(OutArcIt e) const { 712 return source(e); 713 } 714 /// \brief Running node of the iterator 715 /// 716 /// Returns the running node (the target in this case) of the 717 /// iterator 718 Node runningNode(OutArcIt e) const { 719 return target(e); 720 } 721 722 /// \brief Base node of the iterator 723 /// 724 /// Returns the base node (the target in this case) of the iterator 725 Node baseNode(InArcIt e) const { 726 return target(e); 727 } 728 /// \brief Running node of the iterator 729 /// 730 /// Returns the running node (the source in this case) of the 731 /// iterator 732 Node runningNode(InArcIt e) const { 733 return source(e); 734 } 735 736 /// \brief Base node of the iterator 737 /// 738 /// Returns the base node of the iterator 739 Node baseNode(IncEdgeIt) const { 740 return INVALID; 741 } 742 743 /// \brief Running node of the iterator 744 /// 745 /// Returns the running node of the iterator 746 Node runningNode(IncEdgeIt) const { 747 return INVALID; 748 } 736 /// \brief The base node of the iterator. 737 /// 738 /// Returns the base node of the given incident edge iterator. 739 Node baseNode(IncEdgeIt) const { return INVALID; } 740 741 /// \brief The running node of the iterator. 742 /// 743 /// Returns the running node of the given incident edge iterator. 744 Node runningNode(IncEdgeIt) const { return INVALID; } 745 746 /// \brief The base node of the iterator. 747 /// 748 /// Returns the base node of the given outgoing arc iterator 749 /// (i.e. the source node of the corresponding arc). 750 Node baseNode(OutArcIt) const { return INVALID; } 751 752 /// \brief The running node of the iterator. 753 /// 754 /// Returns the running node of the given outgoing arc iterator 755 /// (i.e. the target node of the corresponding arc). 756 Node runningNode(OutArcIt) const { return INVALID; } 757 758 /// \brief The base node of the iterator. 759 /// 760 /// Returns the base node of the given incomming arc iterator 761 /// (i.e. the target node of the corresponding arc). 762 Node baseNode(InArcIt) const { return INVALID; } 763 764 /// \brief The running node of the iterator. 765 /// 766 /// Returns the running node of the given incomming arc iterator 767 /// (i.e. the source node of the corresponding arc). 768 Node runningNode(InArcIt) const { return INVALID; } 749 769 750 770 template <typename _Graph> -
lemon/concepts/graph_components.h
r970 r983 109 109 110 110 bool b; 111 ignore_unused_variable_warning(b);111 ::lemon::ignore_unused_variable_warning(b); 112 112 113 113 b = (ia == ib) && (ia != ib); … … 290 290 ue = e; 291 291 bool d = graph.direction(e); 292 ignore_unused_variable_warning(d);292 ::lemon::ignore_unused_variable_warning(d); 293 293 } 294 294 } … … 369 369 370 370 nid = digraph.maxNodeId(); 371 ignore_unused_variable_warning(nid);371 ::lemon::ignore_unused_variable_warning(nid); 372 372 eid = digraph.maxArcId(); 373 ignore_unused_variable_warning(eid);373 ::lemon::ignore_unused_variable_warning(eid); 374 374 } 375 375 … … 424 424 edge = graph.edgeFromId(ueid); 425 425 ueid = graph.maxEdgeId(); 426 ignore_unused_variable_warning(ueid);426 ::lemon::ignore_unused_variable_warning(ueid); 427 427 } 428 428 … … 497 497 _GraphItemIt it3 = it1; 498 498 _GraphItemIt it4 = INVALID; 499 ignore_unused_variable_warning(it3);500 ignore_unused_variable_warning(it4);499 ::lemon::ignore_unused_variable_warning(it3); 500 ::lemon::ignore_unused_variable_warning(it4); 501 501 502 502 it2 = ++it1; … … 588 588 _GraphIncIt it3 = it1; 589 589 _GraphIncIt it4 = INVALID; 590 ignore_unused_variable_warning(it3);591 ignore_unused_variable_warning(it4);590 ::lemon::ignore_unused_variable_warning(it3); 591 ::lemon::ignore_unused_variable_warning(it4); 592 592 593 593 it2 = ++it1; … … 771 771 n = digraph.baseNode(oait); 772 772 n = digraph.runningNode(oait); 773 ignore_unused_variable_warning(n);773 ::lemon::ignore_unused_variable_warning(n); 774 774 } 775 775 } … … 954 954 = digraph.notifier(typename _Digraph::Arc()); 955 955 956 ignore_unused_variable_warning(nn);957 ignore_unused_variable_warning(en);956 ::lemon::ignore_unused_variable_warning(nn); 957 ::lemon::ignore_unused_variable_warning(en); 958 958 } 959 959 … … 997 997 typename _Graph::EdgeNotifier& uen 998 998 = graph.notifier(typename _Graph::Edge()); 999 ignore_unused_variable_warning(uen);999 ::lemon::ignore_unused_variable_warning(uen); 1000 1000 } 1001 1001 … … 1071 1071 // m3 = cmap; 1072 1072 1073 ignore_unused_variable_warning(m1);1074 ignore_unused_variable_warning(m2);1075 // ignore_unused_variable_warning(m3);1073 ::lemon::ignore_unused_variable_warning(m1); 1074 ::lemon::ignore_unused_variable_warning(m2); 1075 // ::lemon::ignore_unused_variable_warning(m3); 1076 1076 } 1077 1077 -
lemon/concepts/graph_components.h
r982 r983 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. … … 126 126 /// This class describes the base interface of directed graph types. 127 127 /// All digraph %concepts have to conform to this class. 128 /// It just provides types for nodes and arcs and functions 128 /// It just provides types for nodes and arcs and functions 129 129 /// to get the source and the target nodes of arcs. 130 130 class BaseDigraphComponent { … … 434 434 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 435 435 /// 436 /// This class describes the concept of \c NodeIt, \c ArcIt and 436 /// This class describes the concept of \c NodeIt, \c ArcIt and 437 437 /// \c EdgeIt subtypes of digraph and graph types. 438 438 template <typename GR, typename Item> … … 474 474 /// next item. 475 475 GraphItemIt& operator++() { return *this; } 476 476 477 477 /// \brief Equality operator 478 478 /// … … 512 512 }; 513 513 514 /// \brief Concept class for \c InArcIt, \c OutArcIt and 514 /// \brief Concept class for \c InArcIt, \c OutArcIt and 515 515 /// \c IncEdgeIt types. 516 516 /// 517 /// This class describes the concept of \c InArcIt, \c OutArcIt 517 /// This class describes the concept of \c InArcIt, \c OutArcIt 518 518 /// and \c IncEdgeIt subtypes of digraph and graph types. 519 519 /// 520 520 /// \note Since these iterator classes do not inherit from the same 521 521 /// base class, there is an additional template parameter (selector) 522 /// \c sel. For \c InArcIt you should instantiate it with character 522 /// \c sel. For \c InArcIt you should instantiate it with character 523 523 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 524 524 template <typename GR, … … 541 541 GraphIncIt(const GraphIncIt& it) : Item(it) {} 542 542 543 /// \brief Constructor that sets the iterator to the first 543 /// \brief Constructor that sets the iterator to the first 544 544 /// incoming or outgoing arc. 545 545 /// 546 /// Constructor that sets the iterator to the first arc 546 /// Constructor that sets the iterator to the first arc 547 547 /// incoming to or outgoing from the given node. 548 548 explicit GraphIncIt(const GR&, const Base&) {} … … 819 819 /// \brief Return the first edge incident to the given node. 820 820 /// 821 /// This function gives back the first edge incident to the given 821 /// This function gives back the first edge incident to the given 822 822 /// node. The bool parameter gives back the direction for which the 823 /// source node of the directed arc representing the edge is the 823 /// source node of the directed arc representing the edge is the 824 824 /// given node. 825 825 void firstInc(Edge&, bool&, const Node&) const {} … … 828 828 /// given node. 829 829 /// 830 /// This function gives back the next edge incident to the given 830 /// This function gives back the next edge incident to the given 831 831 /// node. The bool parameter should be used as \c firstInc() use it. 832 832 void nextInc(Edge&, bool&) const {} … … 1008 1008 /// 1009 1009 /// This class describes the concept of standard graph maps, i.e. 1010 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1010 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1011 1011 /// graph types, which can be used for associating data to graph items. 1012 1012 /// The standard graph maps must conform to the ReferenceMap concept. … … 1063 1063 _Map m1(g); 1064 1064 _Map m2(g,t); 1065 1065 1066 1066 // Copy constructor 1067 1067 // _Map m3(m); … … 1087 1087 /// 1088 1088 /// This class describes the interface of mappable directed graphs. 1089 /// It extends \ref BaseDigraphComponent with the standard digraph 1089 /// It extends \ref BaseDigraphComponent with the standard digraph 1090 1090 /// map classes, namely \c NodeMap and \c ArcMap. 1091 1091 /// This concept is part of the Digraph concept. … … 1225 1225 /// 1226 1226 /// This class describes the interface of mappable undirected graphs. 1227 /// It extends \ref MappableDigraphComponent with the standard graph 1227 /// It extends \ref MappableDigraphComponent with the standard graph 1228 1228 /// map class for edges (\c EdgeMap). 1229 1229 /// This concept is part of the Graph concept. … … 1311 1311 /// 1312 1312 /// This class describes the interface of extendable directed graphs. 1313 /// It extends \ref BaseDigraphComponent with functions for adding 1313 /// It extends \ref BaseDigraphComponent with functions for adding 1314 1314 /// nodes and arcs to the digraph. 1315 1315 /// This concept requires \ref AlterableDigraphComponent. … … 1356 1356 /// 1357 1357 /// This class describes the interface of extendable undirected graphs. 1358 /// It extends \ref BaseGraphComponent with functions for adding 1358 /// It extends \ref BaseGraphComponent with functions for adding 1359 1359 /// nodes and edges to the graph. 1360 1360 /// This concept requires \ref AlterableGraphComponent. … … 1401 1401 /// 1402 1402 /// This class describes the interface of erasable directed graphs. 1403 /// It extends \ref BaseDigraphComponent with functions for removing 1403 /// It extends \ref BaseDigraphComponent with functions for removing 1404 1404 /// nodes and arcs from the digraph. 1405 1405 /// This concept requires \ref AlterableDigraphComponent. … … 1414 1414 /// \brief Erase a node from the digraph. 1415 1415 /// 1416 /// This function erases the given node from the digraph and all arcs 1416 /// This function erases the given node from the digraph and all arcs 1417 1417 /// connected to the node. 1418 1418 void erase(const Node&) {} … … 1441 1441 /// 1442 1442 /// This class describes the interface of erasable undirected graphs. 1443 /// It extends \ref BaseGraphComponent with functions for removing 1443 /// It extends \ref BaseGraphComponent with functions for removing 1444 1444 /// nodes and edges from the graph. 1445 1445 /// This concept requires \ref AlterableGraphComponent. -
lemon/concepts/heap.h
r954 r983 261 261 item=Item(); 262 262 prio=Prio(); 263 ignore_unused_variable_warning(item);264 ignore_unused_variable_warning(prio);263 ::lemon::ignore_unused_variable_warning(item); 264 ::lemon::ignore_unused_variable_warning(prio); 265 265 266 266 OwnItem own_item; … … 269 269 own_item=Item(); 270 270 own_prio=Prio(); 271 ignore_unused_variable_warning(own_item);272 ignore_unused_variable_warning(own_prio);273 ignore_unused_variable_warning(own_state);271 ::lemon::ignore_unused_variable_warning(own_item); 272 ::lemon::ignore_unused_variable_warning(own_prio); 273 ::lemon::ignore_unused_variable_warning(own_state); 274 274 275 275 _Heap heap1(map); 276 276 _Heap heap2 = heap1; 277 ignore_unused_variable_warning(heap1);278 ignore_unused_variable_warning(heap2);277 ::lemon::ignore_unused_variable_warning(heap1); 278 ::lemon::ignore_unused_variable_warning(heap2); 279 279 280 280 int s = heap.size(); 281 ignore_unused_variable_warning(s);281 ::lemon::ignore_unused_variable_warning(s); 282 282 bool e = heap.empty(); 283 ignore_unused_variable_warning(e);283 ::lemon::ignore_unused_variable_warning(e); 284 284 285 285 prio = heap.prio(); -
lemon/concepts/heap.h
r982 r983 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
r954 r983 76 76 template <typename CPath> 77 77 Path& operator=(const CPath& cpath) { 78 ignore_unused_variable_warning(cpath);78 ::lemon::ignore_unused_variable_warning(cpath); 79 79 return *this; 80 80 } … … 136 136 e = (i < ii); 137 137 138 ignore_unused_variable_warning(l);139 ignore_unused_variable_warning(pp);140 ignore_unused_variable_warning(e);141 ignore_unused_variable_warning(id);142 ignore_unused_variable_warning(ii);143 ignore_unused_variable_warning(ed);138 ::lemon::ignore_unused_variable_warning(l); 139 ::lemon::ignore_unused_variable_warning(pp); 140 ::lemon::ignore_unused_variable_warning(e); 141 ::lemon::ignore_unused_variable_warning(id); 142 ::lemon::ignore_unused_variable_warning(ii); 143 ::lemon::ignore_unused_variable_warning(ed); 144 144 } 145 145 }; … … 163 163 e = (i != INVALID); 164 164 165 ignore_unused_variable_warning(l);166 ignore_unused_variable_warning(e);167 ignore_unused_variable_warning(id);168 ignore_unused_variable_warning(ed);165 ::lemon::ignore_unused_variable_warning(l); 166 ::lemon::ignore_unused_variable_warning(e); 167 ::lemon::ignore_unused_variable_warning(id); 168 ::lemon::ignore_unused_variable_warning(ed); 169 169 } 170 170 _Path& p; … … 189 189 e = (i != INVALID); 190 190 191 ignore_unused_variable_warning(l);192 ignore_unused_variable_warning(e);193 ignore_unused_variable_warning(id);194 ignore_unused_variable_warning(ed);191 ::lemon::ignore_unused_variable_warning(l); 192 ::lemon::ignore_unused_variable_warning(e); 193 ::lemon::ignore_unused_variable_warning(id); 194 ::lemon::ignore_unused_variable_warning(ed); 195 195 } 196 196 _Path& p; -
lemon/concepts/path.h
r982 r983 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 -
lemon/core.h
r964 r983 36 36 #ifdef _MSC_VER 37 37 #pragma warning( disable : 4250 4355 4503 4800 4996 ) 38 #endif 39 40 #ifdef __GNUC__ 41 #define GCC_VERSION (__GNUC__ * 10000 \ 42 + __GNUC_MINOR__ * 100 \ 43 + __GNUC_PATCHLEVEL__) 44 #endif 45 46 #if GCC_VERSION >= 40800 47 // Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8 48 #pragma GCC diagnostic ignored "-Wunused-local-typedefs" 38 49 #endif 39 50 -
lemon/core.h
r979 r983 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). … … 1253 1253 protected: 1254 1254 1255 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1255 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type 1256 { 1256 1257 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1257 1258 … … 1292 1293 }; 1293 1294 1294 protected: 1295 protected: 1295 1296 1296 1297 const Digraph &_g; -
lemon/cplex.cc
r956 r974 41 41 int status; 42 42 _cnt = new int; 43 (*_cnt) = 1; 43 44 _env = CPXopenCPLEX(&status); 44 45 if (_env == 0) { -
lemon/cplex.cc
r973 r974 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). … … 113 113 } 114 114 115 int CplexBase::_addRow(Value lb, ExprIterator b, 116 ExprIterator e, Value ub) { 117 int i = CPXgetnumrows(cplexEnv(), _prob); 118 if (lb == -INF) { 119 const char s = 'L'; 120 CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); 121 } else if (ub == INF) { 122 const char s = 'G'; 123 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 124 } else if (lb == ub){ 125 const char s = 'E'; 126 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 127 } else { 128 const char s = 'R'; 129 double len = ub - lb; 130 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0); 131 } 132 133 std::vector<int> indices; 134 std::vector<int> rowlist; 135 std::vector<Value> values; 136 137 for(ExprIterator it=b; it!=e; ++it) { 138 indices.push_back(it->first); 139 values.push_back(it->second); 140 rowlist.push_back(i); 141 } 142 143 CPXchgcoeflist(cplexEnv(), _prob, values.size(), 144 &rowlist.front(), &indices.front(), &values.front()); 145 146 return i; 147 } 115 148 116 149 void CplexBase::_eraseCol(int i) { … … 456 489 457 490 void CplexBase::_applyMessageLevel() { 458 CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 491 CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 459 492 _message_enabled ? CPX_ON : CPX_OFF); 460 493 } -
lemon/graph_to_eps.h
r964 r981 223 223 using T::_copyright; 224 224 225 using typenameT::NodeTextColorType;225 using T::NodeTextColorType; 226 226 using T::CUST_COL; 227 227 using T::DIST_COL; -
lemon/graph_to_eps.h
r980 r981 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). … … 143 143 ///\param gr Reference to the graph to be printed. 144 144 ///\param ost Reference to the output stream. 145 ///By default it is <tt>std::cout</tt>.145 ///By default, it is <tt>std::cout</tt>. 146 146 ///\param pros If it is \c true, then the \c ostream referenced by \c os 147 147 ///will be explicitly deallocated by the destructor. … … 513 513 ///Turn on/off pre-scaling 514 514 515 ///By default graphToEps() rescales the whole image in order to avoid515 ///By default, graphToEps() rescales the whole image in order to avoid 516 516 ///very big or very small bounding boxes. 517 517 /// … … 1115 1115 ///\param g Reference to the graph to be printed. 1116 1116 ///\param os Reference to the output stream. 1117 ///By default it is <tt>std::cout</tt>.1117 ///By default, it is <tt>std::cout</tt>. 1118 1118 /// 1119 1119 ///This function also has a lot of … … 1127 1127 ///\endcode 1128 1128 /// 1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.1129 ///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file. 1130 1130 /// 1131 1131 ///\warning Don't forget to put the \ref GraphToEps::run() "run()"
Note: See TracChangeset
for help on using the changeset viewer.