Changeset 1084:8b2d4e5d96e4 in lemon-main
- Timestamp:
- 08/07/13 06:55:05 (12 years ago)
- Branch:
- default
- Parents:
- 1009:a26b90a17c81 (diff), 1083: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
- Files:
-
- 50 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/digraph.h
r877 r1084 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
r1083 r1084 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 r1084 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
r1083 r1084 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
r1008 r1084 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
r1083 r1084 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
r976 r1084 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
r1083 r1084 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
r976 r1084 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
r1083 r1084 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
r998 r1084 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
r1077 r1084 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
r989 r1016 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
r1015 r1016 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
r998 r1079 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
r1078 r1079 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()" -
test/adaptors_test.cc
r998 r1084 66 66 Digraph::Arc a2 = digraph.addArc(n1, n3); 67 67 Digraph::Arc a3 = digraph.addArc(n2, n3); 68 ignore_unused_variable_warning(a3);68 ::lemon::ignore_unused_variable_warning(a3); 69 69 70 70 // Check the adaptor … … 101 101 Adaptor::Arc a7 = adaptor.addArc(n1, n4); 102 102 Adaptor::Arc a8 = adaptor.addArc(n1, n2); 103 ignore_unused_variable_warning(a6,a7,a8);103 ::lemon::ignore_unused_variable_warning(a6,a7,a8); 104 104 105 105 adaptor.erase(a1); … … 761 761 Digraph::Arc a2 = digraph.addArc(n1, n3); 762 762 Digraph::Arc a3 = digraph.addArc(n2, n3); 763 ignore_unused_variable_warning(a1,a2,a3);763 ::lemon::ignore_unused_variable_warning(a1,a2,a3); 764 764 765 765 checkGraphNodeList(adaptor, 6); -
test/adaptors_test.cc
r1083 r1084 1375 1375 1376 1376 GridGraph::EdgeMap<bool> dir_map(graph); 1377 dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;1378 dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;1379 dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;1380 dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;1377 dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1; 1378 dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1; 1379 dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4; 1380 dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4; 1381 1381 1382 1382 // Apply several adaptors on the grid graph 1383 typedef SplitNodes< ReverseDigraph< const Orienter< 1384 const GridGraph, GridGraph::EdgeMap<bool> > > > 1385 RevSplitGridGraph; 1386 typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph; 1383 typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> > 1384 OrientedGridGraph; 1385 typedef SplitNodes<OrientedGridGraph> SplitGridGraph; 1387 1386 typedef Undirector<const SplitGridGraph> USplitGridGraph; 1388 typedef Undirector<const USplitGridGraph> UUSplitGridGraph;1389 checkConcept<concepts::Digraph, RevSplitGridGraph>();1390 1387 checkConcept<concepts::Digraph, SplitGridGraph>(); 1391 1388 checkConcept<concepts::Graph, USplitGridGraph>(); 1392 checkConcept<concepts::Graph, UUSplitGridGraph>(); 1393 1394 RevSplitGridGraph rev_adaptor = 1395 splitNodes(reverseDigraph(orienter(graph, dir_map))); 1396 SplitGridGraph adaptor = reverseDigraph(rev_adaptor); 1389 1390 OrientedGridGraph oadaptor = orienter(graph, dir_map); 1391 SplitGridGraph adaptor = splitNodes(oadaptor); 1397 1392 USplitGridGraph uadaptor = undirector(adaptor); 1398 UUSplitGridGraph uuadaptor = undirector(uadaptor);1399 1393 1400 1394 // Check adaptor … … 1403 1397 checkGraphConArcList(adaptor, 8); 1404 1398 1405 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);1406 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);1407 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);1408 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);1409 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);1410 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);1411 checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);1412 checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);1413 1414 checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);1415 checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);1416 checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);1417 checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);1418 checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);1419 checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);1420 checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);1421 checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);1399 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); 1400 checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1); 1401 checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); 1402 checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0); 1403 checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); 1404 checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1); 1405 checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1); 1406 checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2); 1407 1408 checkGraphInArcList(adaptor, adaptor.inNode(n1), 1); 1409 checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); 1410 checkGraphInArcList(adaptor, adaptor.inNode(n2), 2); 1411 checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); 1412 checkGraphInArcList(adaptor, adaptor.inNode(n3), 1); 1413 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); 1414 checkGraphInArcList(adaptor, adaptor.inNode(n4), 0); 1415 checkGraphInArcList(adaptor, adaptor.outNode(n4), 1); 1422 1416 1423 1417 checkNodeIds(adaptor); … … 1442 1436 checkGraphArcMap(uadaptor); 1443 1437 1444 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2); 1445 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2); 1446 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3); 1447 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1); 1448 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2); 1449 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2); 1450 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1); 1451 checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3); 1452 1453 // Check uuadaptor 1454 checkGraphNodeList(uuadaptor, 8); 1455 checkGraphEdgeList(uuadaptor, 16); 1456 checkGraphArcList(uuadaptor, 32); 1457 checkGraphConEdgeList(uuadaptor, 16); 1458 checkGraphConArcList(uuadaptor, 32); 1459 1460 checkNodeIds(uuadaptor); 1461 checkEdgeIds(uuadaptor); 1462 checkArcIds(uuadaptor); 1463 1464 checkGraphNodeMap(uuadaptor); 1465 checkGraphEdgeMap(uuadaptor); 1466 checkGraphArcMap(uuadaptor); 1438 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2); 1439 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2); 1440 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3); 1441 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1); 1442 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2); 1443 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2); 1444 checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1); 1445 checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3); 1467 1446 } 1468 1447 -
test/bfs_test.cc
r1008 r1084 62 62 Arc e; 63 63 int l, i; 64 ignore_unused_variable_warning(l,i);64 ::lemon::ignore_unused_variable_warning(l,i); 65 65 bool b; 66 66 BType::DistMap d(G); … … 152 152 Digraph g; 153 153 bool b; 154 ignore_unused_variable_warning(b);154 ::lemon::ignore_unused_variable_warning(b); 155 155 156 156 bfs(g).run(Node()); -
test/bfs_test.cc
r1083 r1084 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). … … 85 85 b = const_bfs_test.emptyQueue(); 86 86 i = const_bfs_test.queueSize(); 87 87 88 88 bfs_test.start(); 89 89 bfs_test.start(t); … … 106 106 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 107 107 ::Create bfs_test(G); 108 108 109 109 concepts::ReadWriteMap<Node,Arc> pred_map; 110 110 concepts::ReadWriteMap<Node,int> dist_map; 111 111 concepts::ReadWriteMap<Node,bool> reached_map; 112 112 concepts::WriteMap<Node,bool> processed_map; 113 113 114 114 bfs_test 115 115 .predMap(pred_map) … … 121 121 bfs_test.run(s,t); 122 122 bfs_test.run(); 123 123 124 124 bfs_test.init(); 125 125 bfs_test.addSource(s); … … 130 130 b = bfs_test.emptyQueue(); 131 131 i = bfs_test.queueSize(); 132 132 133 133 bfs_test.start(); 134 134 bfs_test.start(t); -
test/circulation_test.cc
r1008 r1084 74 74 VType v; 75 75 bool b; 76 ignore_unused_variable_warning(v,b);76 ::lemon::ignore_unused_variable_warning(v,b); 77 77 78 78 typedef Circulation<Digraph, CapMap, CapMap, SupplyMap> … … 105 105 const_circ_test.barrierMap(bar); 106 106 107 ignore_unused_variable_warning(fm);107 ::lemon::ignore_unused_variable_warning(fm); 108 108 } 109 109 -
test/circulation_test.cc
r1083 r1084 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). … … 83 83 CirculationType circ_test(g, lcap, ucap, supply); 84 84 const CirculationType& const_circ_test = circ_test; 85 85 86 86 circ_test 87 87 .lowerMap(lcap) … … 89 89 .supplyMap(supply) 90 90 .flowMap(flow); 91 92 const CirculationType::Elevator& elev = const_circ_test.elevator(); 93 circ_test.elevator(const_cast<CirculationType::Elevator&>(elev)); 94 CirculationType::Tolerance tol = const_circ_test.tolerance(); 95 circ_test.tolerance(tol); 91 96 92 97 circ_test.init(); … … 99 104 b = const_circ_test.barrier(n); 100 105 const_circ_test.barrierMap(bar); 101 106 102 107 ::lemon::ignore_unused_variable_warning(fm); 103 108 } -
test/connectivity_test.cc
r998 r1084 69 69 Graph g(d); 70 70 Digraph::Node n = d.addNode(); 71 ignore_unused_variable_warning(n);71 ::lemon::ignore_unused_variable_warning(n); 72 72 73 73 check(stronglyConnected(d), "This digraph is strongly connected"); … … 247 247 Digraph::Node watch = d.addNode(); 248 248 Digraph::Node pants = d.addNode(); 249 ignore_unused_variable_warning(watch);249 ::lemon::ignore_unused_variable_warning(watch); 250 250 251 251 d.addArc(socks, shoe); -
test/connectivity_test.cc
r1083 r1084 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). … … 30 30 typedef ListDigraph Digraph; 31 31 typedef Undirector<Digraph> Graph; 32 33 { 34 Digraph d; 35 Digraph::NodeMap<int> order(d); 36 Graph g(d); 37 32 33 { 34 Digraph d; 35 Digraph::NodeMap<int> order(d); 36 Graph g(d); 37 38 38 check(stronglyConnected(d), "The empty digraph is strongly connected"); 39 39 check(countStronglyConnectedComponents(d) == 0, … … 49 49 check(countBiEdgeConnectedComponents(g) == 0, 50 50 "The empty graph has 0 bi-edge-connected component"); 51 51 52 52 check(dag(d), "The empty digraph is DAG."); 53 53 check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); … … 84 84 check(countBiEdgeConnectedComponents(g) == 1, 85 85 "This graph has 1 bi-edge-connected component"); 86 86 87 87 check(dag(d), "This digraph is DAG."); 88 88 check(checkedTopologicalSort(d, order), "This digraph is DAG."); … … 103 103 Digraph::NodeMap<int> order(d); 104 104 Graph g(d); 105 105 106 106 Digraph::Node n1 = d.addNode(); 107 107 Digraph::Node n2 = d.addNode(); … … 110 110 Digraph::Node n5 = d.addNode(); 111 111 Digraph::Node n6 = d.addNode(); 112 112 113 113 d.addArc(n1, n3); 114 114 d.addArc(n3, n2); … … 138 138 check(!parallelFree(g), "This graph is not parallel-free."); 139 139 check(!simpleGraph(g), "This graph is not simple."); 140 140 141 141 d.addArc(n3, n3); 142 142 143 143 check(!loopFree(d), "This digraph is not loop-free."); 144 144 check(!loopFree(g), "This graph is not loop-free."); 145 145 check(!simpleGraph(d), "This digraph is not simple."); 146 146 147 147 d.addArc(n3, n2); 148 148 149 149 check(!parallelFree(d), "This digraph is not parallel-free."); 150 150 } 151 151 152 152 { 153 153 Digraph d; 154 154 Digraph::ArcMap<bool> cutarcs(d, false); 155 155 Graph g(d); 156 156 157 157 Digraph::Node n1 = d.addNode(); 158 158 Digraph::Node n2 = d.addNode(); … … 174 174 d.addArc(n6, n7); 175 175 d.addArc(n7, n6); 176 176 177 177 check(!stronglyConnected(d), "This digraph is not strongly connected"); 178 178 check(countStronglyConnectedComponents(d) == 3, … … 237 237 Digraph d; 238 238 Digraph::NodeMap<int> order(d); 239 239 240 240 Digraph::Node belt = d.addNode(); 241 241 Digraph::Node trousers = d.addNode(); … … 258 258 d.addArc(shirt, necktie); 259 259 d.addArc(necktie, coat); 260 260 261 261 check(dag(d), "This digraph is DAG."); 262 262 topologicalSort(d, order); … … 270 270 ListGraph g; 271 271 ListGraph::NodeMap<bool> map(g); 272 272 273 273 ListGraph::Node n1 = g.addNode(); 274 274 ListGraph::Node n2 = g.addNode(); … … 286 286 g.addEdge(n4, n7); 287 287 g.addEdge(n5, n7); 288 288 289 289 check(bipartite(g), "This graph is bipartite"); 290 290 check(bipartitePartitions(g, map), "This graph is bipartite"); 291 291 292 292 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], 293 293 "Wrong bipartitePartitions()"); -
test/dfs_test.cc
r1008 r1084 68 68 int l, i; 69 69 bool b; 70 ignore_unused_variable_warning(l,i,b);70 ::lemon::ignore_unused_variable_warning(l,i,b); 71 71 72 72 DType::DistMap d(G); … … 154 154 Digraph g; 155 155 bool b; 156 ignore_unused_variable_warning(b);156 ::lemon::ignore_unused_variable_warning(b); 157 157 158 158 dfs(g).run(Node()); -
test/dfs_test.cc
r1083 r1084 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). … … 89 89 b = const_dfs_test.emptyQueue(); 90 90 i = const_dfs_test.queueSize(); 91 91 92 92 dfs_test.start(); 93 93 dfs_test.start(t); … … 115 115 concepts::ReadWriteMap<Node,bool> reached_map; 116 116 concepts::WriteMap<Node,bool> processed_map; 117 117 118 118 dfs_test 119 119 .predMap(pred_map) … … 132 132 b = dfs_test.emptyQueue(); 133 133 i = dfs_test.queueSize(); 134 134 135 135 dfs_test.start(); 136 136 dfs_test.start(t); -
test/digraph_test.cc
r999 r1084 65 65 a3 = G.addArc(n2, n3), 66 66 a4 = G.addArc(n2, n3); 67 ignore_unused_variable_warning(a2,a3,a4);67 ::lemon::ignore_unused_variable_warning(a2,a3,a4); 68 68 69 69 checkGraphNodeList(G, 3); … … 94 94 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 95 95 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 96 ignore_unused_variable_warning(a1,a2,a3,a4);96 ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4); 97 97 98 98 Node n4 = G.split(n2); … … 128 128 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 129 129 a5 = G.addArc(n2, n4); 130 ignore_unused_variable_warning(a1,a2,a3,a5);130 ::lemon::ignore_unused_variable_warning(a1,a2,a3,a5); 131 131 132 132 checkGraphNodeList(G, 4); … … 208 208 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 209 209 a5 = G.addArc(n2, n4); 210 ignore_unused_variable_warning(a2,a3,a4,a5);210 ::lemon::ignore_unused_variable_warning(a2,a3,a4,a5); 211 211 212 212 // Check arc deletion … … 256 256 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 257 257 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 258 ignore_unused_variable_warning(a1,a2,a3,a4);258 ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4); 259 259 260 260 typename Digraph::Snapshot snapshot(G); … … 357 357 e1 = g.addArc(n1, n2), 358 358 e2 = g.addArc(n2, n3); 359 ignore_unused_variable_warning(e2);359 ::lemon::ignore_unused_variable_warning(e2); 360 360 361 361 check(g.valid(n1), "Wrong validity check"); -
test/digraph_test.cc
r1083 r1084 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). … … 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 #include <lemon/static_graph.h> 22 23 #include <lemon/full_graph.h> 23 24 … … 35 36 checkGraphNodeList(G, 0); 36 37 checkGraphArcList(G, 0); 38 39 G.reserveNode(3); 40 G.reserveArc(4); 37 41 38 42 Node … … 289 293 290 294 snapshot.restore(); 295 snapshot.save(G); 296 297 checkGraphNodeList(G, 4); 298 checkGraphArcList(G, 4); 299 300 G.addArc(G.addNode(), G.addNode()); 301 302 snapshot.restore(); 291 303 292 304 checkGraphNodeList(G, 4); … … 323 335 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 324 336 } 337 { // Checking StaticDigraph 338 checkConcept<Digraph, StaticDigraph>(); 339 checkConcept<ClearableDigraphComponent<>, StaticDigraph>(); 340 } 325 341 { // Checking FullDigraph 326 342 checkConcept<Digraph, FullDigraph>(); … … 379 395 } 380 396 397 void checkStaticDigraph() { 398 SmartDigraph g; 399 SmartDigraph::NodeMap<StaticDigraph::Node> nref(g); 400 SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g); 401 402 StaticDigraph G; 403 404 checkGraphNodeList(G, 0); 405 checkGraphArcList(G, 0); 406 407 G.build(g, nref, aref); 408 409 checkGraphNodeList(G, 0); 410 checkGraphArcList(G, 0); 411 412 SmartDigraph::Node 413 n1 = g.addNode(), 414 n2 = g.addNode(), 415 n3 = g.addNode(); 416 417 G.build(g, nref, aref); 418 419 checkGraphNodeList(G, 3); 420 checkGraphArcList(G, 0); 421 422 SmartDigraph::Arc a1 = g.addArc(n1, n2); 423 424 G.build(g, nref, aref); 425 426 check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2], 427 "Wrong arc or wrong references"); 428 checkGraphNodeList(G, 3); 429 checkGraphArcList(G, 1); 430 431 checkGraphOutArcList(G, nref[n1], 1); 432 checkGraphOutArcList(G, nref[n2], 0); 433 checkGraphOutArcList(G, nref[n3], 0); 434 435 checkGraphInArcList(G, nref[n1], 0); 436 checkGraphInArcList(G, nref[n2], 1); 437 checkGraphInArcList(G, nref[n3], 0); 438 439 checkGraphConArcList(G, 1); 440 441 SmartDigraph::Arc 442 a2 = g.addArc(n2, n1), 443 a3 = g.addArc(n2, n3), 444 a4 = g.addArc(n2, n3); 445 ignore_unused_variable_warning(a2,a3,a4); 446 447 digraphCopy(g, G).nodeRef(nref).run(); 448 449 checkGraphNodeList(G, 3); 450 checkGraphArcList(G, 4); 451 452 checkGraphOutArcList(G, nref[n1], 1); 453 checkGraphOutArcList(G, nref[n2], 3); 454 checkGraphOutArcList(G, nref[n3], 0); 455 456 checkGraphInArcList(G, nref[n1], 1); 457 checkGraphInArcList(G, nref[n2], 1); 458 checkGraphInArcList(G, nref[n3], 2); 459 460 checkGraphConArcList(G, 4); 461 462 std::vector<std::pair<int,int> > arcs; 463 arcs.push_back(std::make_pair(0,1)); 464 arcs.push_back(std::make_pair(0,2)); 465 arcs.push_back(std::make_pair(1,3)); 466 arcs.push_back(std::make_pair(1,2)); 467 arcs.push_back(std::make_pair(3,0)); 468 arcs.push_back(std::make_pair(3,3)); 469 arcs.push_back(std::make_pair(4,2)); 470 arcs.push_back(std::make_pair(4,3)); 471 arcs.push_back(std::make_pair(4,1)); 472 473 G.build(6, arcs.begin(), arcs.end()); 474 475 checkGraphNodeList(G, 6); 476 checkGraphArcList(G, 9); 477 478 checkGraphOutArcList(G, G.node(0), 2); 479 checkGraphOutArcList(G, G.node(1), 2); 480 checkGraphOutArcList(G, G.node(2), 0); 481 checkGraphOutArcList(G, G.node(3), 2); 482 checkGraphOutArcList(G, G.node(4), 3); 483 checkGraphOutArcList(G, G.node(5), 0); 484 485 checkGraphInArcList(G, G.node(0), 1); 486 checkGraphInArcList(G, G.node(1), 2); 487 checkGraphInArcList(G, G.node(2), 3); 488 checkGraphInArcList(G, G.node(3), 3); 489 checkGraphInArcList(G, G.node(4), 0); 490 checkGraphInArcList(G, G.node(5), 0); 491 492 checkGraphConArcList(G, 9); 493 494 checkNodeIds(G); 495 checkArcIds(G); 496 checkGraphNodeMap(G); 497 checkGraphArcMap(G); 498 499 int n = G.nodeNum(); 500 int m = G.arcNum(); 501 check(G.index(G.node(n-1)) == n-1, "Wrong index."); 502 check(G.index(G.arc(m-1)) == m-1, "Wrong index."); 503 } 504 381 505 void checkFullDigraph(int num) { 382 506 typedef FullDigraph Digraph; 383 507 DIGRAPH_TYPEDEFS(Digraph); 508 384 509 Digraph G(num); 510 check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); 511 512 G.resize(num); 513 check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); 385 514 386 515 checkGraphNodeList(G, num); … … 426 555 checkDigraphValidity<SmartDigraph>(); 427 556 } 557 { // Checking StaticDigraph 558 checkStaticDigraph(); 559 } 428 560 { // Checking FullDigraph 429 561 checkFullDigraph(8); -
test/dijkstra_test.cc
r1008 r1084 66 66 int i; 67 67 bool b; 68 ignore_unused_variable_warning(l,i,b);68 ::lemon::ignore_unused_variable_warning(l,i,b); 69 69 70 70 DType::DistMap d(G); … … 165 165 Digraph g; 166 166 bool b; 167 ignore_unused_variable_warning(b);167 ::lemon::ignore_unused_variable_warning(b); 168 168 169 169 dijkstra(g,LengthMap()).run(Node()); -
test/dijkstra_test.cc
r1083 r1084 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). … … 88 88 b = const_dijkstra_test.emptyQueue(); 89 89 i = const_dijkstra_test.queueSize(); 90 90 91 91 dijkstra_test.start(); 92 92 dijkstra_test.start(t); … … 112 112 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > 113 113 ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > 114 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 114 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 115 115 concepts::ReadWriteMap<Node,int> > 116 116 ::Create dijkstra_test(G,length); … … 122 122 concepts::ReadWriteMap<Node,int> heap_cross_ref; 123 123 BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref); 124 124 125 125 dijkstra_test 126 126 .lengthMap(length_map) … … 139 139 b = dijkstra_test.emptyQueue(); 140 140 i = dijkstra_test.queueSize(); 141 141 142 142 dijkstra_test.start(); 143 143 dijkstra_test.start(t); -
test/edge_set_test.cc
r998 r1084 45 45 46 46 Digraph::Arc ga1 = digraph.addArc(n1, n2); 47 ignore_unused_variable_warning(ga1);47 ::lemon::ignore_unused_variable_warning(ga1); 48 48 49 49 ArcSet arc_set(digraph); 50 50 51 51 Digraph::Arc ga2 = digraph.addArc(n2, n1); 52 ignore_unused_variable_warning(ga2);52 ::lemon::ignore_unused_variable_warning(ga2); 53 53 54 54 checkGraphNodeList(arc_set, 2); … … 78 78 a3 = arc_set.addArc(n2, n3), 79 79 a4 = arc_set.addArc(n2, n3); 80 ignore_unused_variable_warning(a2,a3,a4);80 ::lemon::ignore_unused_variable_warning(a2,a3,a4); 81 81 82 82 checkGraphNodeList(arc_set, 3); … … 115 115 116 116 Digraph::Arc ga1 = digraph.addArc(n1, n2); 117 ignore_unused_variable_warning(ga1);117 ::lemon::ignore_unused_variable_warning(ga1); 118 118 119 119 ArcSet arc_set(digraph); 120 120 121 121 Digraph::Arc ga2 = digraph.addArc(n2, n1); 122 ignore_unused_variable_warning(ga2);122 ::lemon::ignore_unused_variable_warning(ga2); 123 123 124 124 checkGraphNodeList(arc_set, 2); … … 148 148 a3 = arc_set.addArc(n2, n3), 149 149 a4 = arc_set.addArc(n2, n3); 150 ignore_unused_variable_warning(a2,a3,a4);150 ::lemon::ignore_unused_variable_warning(a2,a3,a4); 151 151 152 152 checkGraphNodeList(arc_set, 3); … … 199 199 200 200 Digraph::Arc ga1 = digraph.addArc(n1, n2); 201 ignore_unused_variable_warning(ga1);201 ::lemon::ignore_unused_variable_warning(ga1); 202 202 203 203 EdgeSet edge_set(digraph); 204 204 205 205 Digraph::Arc ga2 = digraph.addArc(n2, n1); 206 ignore_unused_variable_warning(ga2);206 ::lemon::ignore_unused_variable_warning(ga2); 207 207 208 208 checkGraphNodeList(edge_set, 2); … … 241 241 e3 = edge_set.addEdge(n2, n3), 242 242 e4 = edge_set.addEdge(n2, n3); 243 ignore_unused_variable_warning(e2,e3,e4);243 ::lemon::ignore_unused_variable_warning(e2,e3,e4); 244 244 245 245 checkGraphNodeList(edge_set, 3); … … 287 287 288 288 Digraph::Arc ga1 = digraph.addArc(n1, n2); 289 ignore_unused_variable_warning(ga1);289 ::lemon::ignore_unused_variable_warning(ga1); 290 290 291 291 EdgeSet edge_set(digraph); 292 292 293 293 Digraph::Arc ga2 = digraph.addArc(n2, n1); 294 ignore_unused_variable_warning(ga2);294 ::lemon::ignore_unused_variable_warning(ga2); 295 295 296 296 checkGraphNodeList(edge_set, 2); … … 329 329 e3 = edge_set.addEdge(n2, n3), 330 330 e4 = edge_set.addEdge(n2, n3); 331 ignore_unused_variable_warning(e2,e3,e4);331 ::lemon::ignore_unused_variable_warning(e2,e3,e4); 332 332 333 333 checkGraphNodeList(edge_set, 3); -
test/edge_set_test.cc
r1083 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/euler_test.cc
r998 r1084 102 102 Graph g(d); 103 103 Digraph::Node n = d.addNode(); 104 ignore_unused_variable_warning(n);104 ::lemon::ignore_unused_variable_warning(n); 105 105 106 106 checkDiEulerIt(d); … … 191 191 Digraph::Node n4 = d.addNode(); 192 192 Digraph::Node n5 = d.addNode(); 193 ignore_unused_variable_warning(n0,n4,n5);193 ::lemon::ignore_unused_variable_warning(n0,n4,n5); 194 194 195 195 d.addArc(n1, n2); -
test/euler_test.cc
r1083 r1084 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). … … 86 86 typedef ListDigraph Digraph; 87 87 typedef Undirector<Digraph> Graph; 88 89 { 90 Digraph d; 91 Graph g(d); 92 88 89 { 90 Digraph d; 91 Graph g(d); 92 93 93 checkDiEulerIt(d); 94 94 checkDiEulerIt(g); … … 130 130 Digraph::Node n2 = d.addNode(); 131 131 Digraph::Node n3 = d.addNode(); 132 132 133 133 d.addArc(n1, n2); 134 134 d.addArc(n2, n1); … … 155 155 Digraph::Node n5 = d.addNode(); 156 156 Digraph::Node n6 = d.addNode(); 157 157 158 158 d.addArc(n1, n2); 159 159 d.addArc(n2, n4); … … 214 214 Digraph::Node n2 = d.addNode(); 215 215 Digraph::Node n3 = d.addNode(); 216 216 217 217 d.addArc(n1, n2); 218 218 d.addArc(n2, n3); -
test/gomory_hu_test.cc
r1008 r1084 69 69 Value v; 70 70 int d; 71 ignore_unused_variable_warning(v,d);71 ::lemon::ignore_unused_variable_warning(v,d); 72 72 73 73 GomoryHu<Graph, CapMap> gh_test(g, cap); -
test/gomory_hu_test.cc
r1083 r1084 1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2010 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 1 19 #include <iostream> 2 20 … … 34 52 "source 0\n" 35 53 "target 3\n"; 36 54 37 55 void checkGomoryHuCompile() 38 56 { … … 71 89 72 90 int cutValue(const Graph& graph, const BoolNodeMap& cut, 73 91 const IntEdgeMap& capacity) { 74 92 75 93 int sum = 0; … … 109 127 int sum=0; 110 128 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) 111 sum+=capacity[a]; 129 sum+=capacity[a]; 112 130 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); 113 131 … … 120 138 } 121 139 } 122 140 123 141 return 0; 124 142 } -
test/graph_test.cc
r998 r1084 67 67 Edge e2 = G.addEdge(n2, n1), 68 68 e3 = G.addEdge(n2, n3); 69 ignore_unused_variable_warning(e2,e3);69 ::lemon::ignore_unused_variable_warning(e2,e3); 70 70 71 71 checkGraphNodeList(G, 3); … … 100 100 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 101 101 e5 = G.addEdge(n4, n3); 102 ignore_unused_variable_warning(e1,e3,e4,e5);102 ::lemon::ignore_unused_variable_warning(e1,e3,e4,e5); 103 103 104 104 checkGraphNodeList(G, 4); … … 180 180 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 181 181 e5 = G.addEdge(n4, n3); 182 ignore_unused_variable_warning(e1,e3,e4,e5);182 ::lemon::ignore_unused_variable_warning(e1,e3,e4,e5); 183 183 184 184 // Check edge deletion … … 221 221 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 222 222 e3 = G.addEdge(n2, n3); 223 ignore_unused_variable_warning(e1,e2,e3);223 ::lemon::ignore_unused_variable_warning(e1,e2,e3); 224 224 225 225 checkGraphNodeList(G, 3); … … 386 386 e1 = g.addEdge(n1, n2), 387 387 e2 = g.addEdge(n2, n3); 388 ignore_unused_variable_warning(e2);388 ::lemon::ignore_unused_variable_warning(e2); 389 389 390 390 check(g.valid(n1), "Wrong validity check"); … … 525 525 526 526 Node n = G.nodeFromId(dim); 527 ignore_unused_variable_warning(n);527 ::lemon::ignore_unused_variable_warning(n); 528 528 529 529 for (NodeIt n(G); n != INVALID; ++n) { -
test/graph_test.cc
r1083 r1084 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). … … 39 39 checkGraphArcList(G, 0); 40 40 41 G.reserveNode(3); 42 G.reserveEdge(3); 43 41 44 Node 42 45 n1 = G.addNode(), … … 261 264 262 265 snapshot.restore(); 266 snapshot.save(G); 263 267 264 268 checkGraphNodeList(G, 4); 265 269 checkGraphEdgeList(G, 3); 266 270 checkGraphArcList(G, 6); 271 272 G.addEdge(G.addNode(), G.addNode()); 273 274 snapshot.restore(); 275 276 checkGraphNodeList(G, 4); 277 checkGraphEdgeList(G, 3); 278 checkGraphArcList(G, 6); 267 279 } 268 280 … … 272 284 273 285 Graph G(num); 286 check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2, 287 "Wrong size"); 288 289 G.resize(num); 290 check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2, 291 "Wrong size"); 292 274 293 checkGraphNodeList(G, num); 275 294 checkGraphEdgeList(G, num * (num - 1) / 2); … … 417 436 check(G.height() == height, "Wrong row number"); 418 437 438 G.resize(width, height); 439 check(G.width() == width, "Wrong column number"); 440 check(G.height() == height, "Wrong row number"); 441 419 442 for (int i = 0; i < width; ++i) { 420 443 for (int j = 0; j < height; ++j) { … … 492 515 493 516 HypercubeGraph G(dim); 517 check(G.dimension() == dim, "Wrong dimension"); 518 519 G.resize(dim); 520 check(G.dimension() == dim, "Wrong dimension"); 521 494 522 checkGraphNodeList(G, 1 << dim); 495 523 checkGraphEdgeList(G, dim * (1 << (dim-1))); -
test/hao_orlin_test.cc
r1008 r1084 67 67 CutMap cut; 68 68 Value v; 69 ignore_unused_variable_warning(v);69 ::lemon::ignore_unused_variable_warning(v); 70 70 71 71 HaoOrlin<Digraph, CapMap> ho_test(g, cap); -
test/hao_orlin_test.cc
r1083 r1084 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). … … 85 85 86 86 template <typename Graph, typename CapMap, typename CutMap> 87 typename CapMap::Value 87 typename CapMap::Value 88 88 cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) 89 89 { … … 112 112 ho.run(); 113 113 ho.minCutMap(cut); 114 114 115 115 check(ho.minCutValue() == 1, "Wrong cut value"); 116 116 check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); … … 128 128 ho.run(); 129 129 ho.minCutMap(cut); 130 130 131 131 check(ho.minCutValue() == 1, "Wrong cut value"); 132 132 check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); 133 133 } 134 134 135 135 typedef Undirector<SmartDigraph> UGraph; 136 136 UGraph ugraph(graph); 137 137 138 138 { 139 139 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); 140 140 ho.run(); 141 141 ho.minCutMap(cut); 142 142 143 143 check(ho.minCutValue() == 2, "Wrong cut value"); 144 144 check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); … … 148 148 ho.run(); 149 149 ho.minCutMap(cut); 150 150 151 151 check(ho.minCutValue() == 5, "Wrong cut value"); 152 152 check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); … … 156 156 ho.run(); 157 157 ho.minCutMap(cut); 158 158 159 159 check(ho.minCutValue() == 5, "Wrong cut value"); 160 160 check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); -
test/maps_test.cc
r998 r1084 104 104 NullMap<A,B> map1; 105 105 NullMap<A,B> map2 = map1; 106 ignore_unused_variable_warning(map2);106 ::lemon::ignore_unused_variable_warning(map2); 107 107 map1 = nullMap<A,B>(); 108 108 } … … 115 115 ConstMap<A,B> map2 = B(); 116 116 ConstMap<A,B> map3 = map1; 117 ignore_unused_variable_warning(map2,map3);117 ::lemon::ignore_unused_variable_warning(map2,map3); 118 118 119 119 map1 = constMap<A>(B()); … … 122 122 ConstMap<A,C> map4(C(1)); 123 123 ConstMap<A,C> map5 = map4; 124 ignore_unused_variable_warning(map5);124 ::lemon::ignore_unused_variable_warning(map5); 125 125 126 126 map4 = constMap<A>(C(2)); … … 144 144 IdentityMap<A> map1; 145 145 IdentityMap<A> map2 = map1; 146 ignore_unused_variable_warning(map2);146 ::lemon::ignore_unused_variable_warning(map2); 147 147 148 148 map1 = identityMap<A>(); … … 205 205 checkConcept<ReadMap<B,double>, CompMap>(); 206 206 CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>()); 207 ignore_unused_variable_warning(map1);207 ::lemon::ignore_unused_variable_warning(map1); 208 208 CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>()); 209 ignore_unused_variable_warning(map2);209 ::lemon::ignore_unused_variable_warning(map2); 210 210 211 211 SparseMap<double, bool> m1(false); m1[3.14] = true; … … 220 220 checkConcept<ReadMap<A,double>, CombMap>(); 221 221 CombMap map1 = CombMap(DoubleMap(), DoubleMap()); 222 ignore_unused_variable_warning(map1);222 ::lemon::ignore_unused_variable_warning(map1); 223 223 CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>()); 224 ignore_unused_variable_warning(map2);224 ::lemon::ignore_unused_variable_warning(map2); 225 225 226 226 check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3, … … 234 234 FunctorToMap<F> map1; 235 235 FunctorToMap<F> map2 = FunctorToMap<F>(F()); 236 ignore_unused_variable_warning(map2);236 ::lemon::ignore_unused_variable_warning(map2); 237 237 238 238 B b = functorToMap(F())[A()]; 239 ignore_unused_variable_warning(b);239 ::lemon::ignore_unused_variable_warning(b); 240 240 241 241 checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >(); 242 242 MapToFunctor<ReadMap<A,B> > map = 243 243 MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>()); 244 ignore_unused_variable_warning(map);244 ::lemon::ignore_unused_variable_warning(map); 245 245 246 246 check(functorToMap(&func)[A()] == 3, … … 260 260 ConvertMap<ReadMap<double, int>, double> >(); 261 261 ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true)); 262 ignore_unused_variable_warning(map1);262 ::lemon::ignore_unused_variable_warning(map1); 263 263 ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false)); 264 ignore_unused_variable_warning(map2);264 ::lemon::ignore_unused_variable_warning(map2); 265 265 266 266 } -
test/maps_test.cc
r1083 r1084 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). … … 24 24 #include <lemon/maps.h> 25 25 #include <lemon/list_graph.h> 26 #include <lemon/smart_graph.h> 27 #include <lemon/adaptors.h> 28 #include <lemon/dfs.h> 29 #include <algorithm> 26 30 27 31 #include "test_tools.h" … … 35 39 36 40 class C { 37 int x;41 int _x; 38 42 public: 39 C(int _x) : x(_x) {} 43 C(int x) : _x(x) {} 44 int get() const { return _x; } 45 }; 46 inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); } 47 inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); } 48 49 C createC(int x) { return C(x); } 50 51 template <typename T> 52 class Less { 53 T _t; 54 public: 55 Less(T t): _t(t) {} 56 bool operator()(const T& t) const { return t < _t; } 40 57 }; 41 58 … … 53 70 54 71 int binc(int a, B) { return a+1; } 72 73 template <typename T> 74 class Sum { 75 T& _sum; 76 public: 77 Sum(T& sum) : _sum(sum) {} 78 void operator()(const T& t) { _sum += t; } 79 }; 55 80 56 81 typedef ReadMap<A, double> DoubleMap; … … 349 374 { 350 375 typedef std::vector<int> vec; 376 checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >(); 377 checkConcept<WriteMap<int, bool>, 378 LoggerBoolMap<std::back_insert_iterator<vec> > >(); 379 351 380 vec v1; 352 381 vec v2(10); … … 368 397 it != map2.end(); ++it ) 369 398 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 370 } 371 372 // CrossRefMap 373 { 399 374 400 typedef ListDigraph Graph; 375 401 DIGRAPH_TYPEDEFS(Graph); 402 Graph gr; 403 404 Node n0 = gr.addNode(); 405 Node n1 = gr.addNode(); 406 Node n2 = gr.addNode(); 407 Node n3 = gr.addNode(); 408 409 gr.addArc(n3, n0); 410 gr.addArc(n3, n2); 411 gr.addArc(n0, n2); 412 gr.addArc(n2, n1); 413 gr.addArc(n0, n1); 414 415 { 416 std::vector<Node> v; 417 dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run(); 418 419 check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, 420 "Something is wrong with LoggerBoolMap"); 421 } 422 { 423 std::vector<Node> v(countNodes(gr)); 424 dfs(gr).processedMap(loggerBoolMap(v.begin())).run(); 425 426 check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, 427 "Something is wrong with LoggerBoolMap"); 428 } 429 } 430 431 // IdMap, RangeIdMap 432 { 433 typedef ListDigraph Graph; 434 DIGRAPH_TYPEDEFS(Graph); 435 436 checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >(); 437 checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >(); 438 checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >(); 439 checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >(); 440 441 Graph gr; 442 IdMap<Graph, Node> nmap(gr); 443 IdMap<Graph, Arc> amap(gr); 444 RangeIdMap<Graph, Node> nrmap(gr); 445 RangeIdMap<Graph, Arc> armap(gr); 446 447 Node n0 = gr.addNode(); 448 Node n1 = gr.addNode(); 449 Node n2 = gr.addNode(); 450 451 Arc a0 = gr.addArc(n0, n1); 452 Arc a1 = gr.addArc(n0, n2); 453 Arc a2 = gr.addArc(n2, n1); 454 Arc a3 = gr.addArc(n2, n0); 455 456 check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); 457 check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); 458 check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); 459 460 check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap"); 461 check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap"); 462 check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap"); 463 check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap"); 464 465 check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); 466 check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); 467 468 check(nrmap.size() == 3 && armap.size() == 4, 469 "Wrong RangeIdMap::size()"); 470 471 check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); 472 check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); 473 check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); 474 475 check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); 476 check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 477 check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); 478 check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap"); 479 480 check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); 481 check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); 482 483 gr.erase(n1); 484 485 if (nrmap[n0] == 1) nrmap.swap(n0, n2); 486 nrmap.swap(n2, n0); 487 if (armap[a1] == 1) armap.swap(a1, a3); 488 armap.swap(a3, a1); 489 490 check(nrmap.size() == 2 && armap.size() == 2, 491 "Wrong RangeIdMap::size()"); 492 493 check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); 494 check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); 495 496 check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 497 check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); 498 499 check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); 500 check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); 501 } 502 503 // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap 504 { 505 typedef ListGraph Graph; 506 GRAPH_TYPEDEFS(Graph); 507 508 checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >(); 509 checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >(); 510 checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >(); 511 checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >(); 512 checkConcept<ReadMap<Node, int>, InDegMap<Graph> >(); 513 checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >(); 514 515 Graph gr; 516 Node n0 = gr.addNode(); 517 Node n1 = gr.addNode(); 518 Node n2 = gr.addNode(); 519 520 gr.addEdge(n0,n1); 521 gr.addEdge(n1,n2); 522 gr.addEdge(n0,n2); 523 gr.addEdge(n2,n1); 524 gr.addEdge(n1,n2); 525 gr.addEdge(n0,n1); 526 527 for (EdgeIt e(gr); e != INVALID; ++e) { 528 check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap"); 529 check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap"); 530 } 531 532 check(mapCompare(gr, 533 sourceMap(orienter(gr, constMap<Edge, bool>(true))), 534 targetMap(orienter(gr, constMap<Edge, bool>(false)))), 535 "Wrong SourceMap or TargetMap"); 536 537 typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph; 538 Digraph dgr(gr, constMap<Edge, bool>(true)); 539 OutDegMap<Digraph> odm(dgr); 540 InDegMap<Digraph> idm(dgr); 541 542 check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap"); 543 check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); 544 545 gr.addEdge(n2, n0); 546 547 check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap"); 548 check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); 549 } 550 551 // CrossRefMap 552 { 553 typedef ListDigraph Graph; 554 DIGRAPH_TYPEDEFS(Graph); 376 555 377 556 checkConcept<ReadWriteMap<Node, int>, 378 557 CrossRefMap<Graph, Node, int> >(); 379 558 checkConcept<ReadWriteMap<Node, bool>, 559 CrossRefMap<Graph, Node, bool> >(); 560 checkConcept<ReadWriteMap<Node, double>, 561 CrossRefMap<Graph, Node, double> >(); 562 563 Graph gr; 564 typedef CrossRefMap<Graph, Node, char> CRMap; 565 CRMap map(gr); 566 567 Node n0 = gr.addNode(); 568 Node n1 = gr.addNode(); 569 Node n2 = gr.addNode(); 570 571 map.set(n0, 'A'); 572 map.set(n1, 'B'); 573 map.set(n2, 'C'); 574 575 check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, 576 "Wrong CrossRefMap"); 577 check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, 578 "Wrong CrossRefMap"); 579 check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2, 580 "Wrong CrossRefMap"); 581 check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 582 "Wrong CrossRefMap::count()"); 583 584 CRMap::ValueIt it = map.beginValue(); 585 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 586 it == map.endValue(), "Wrong value iterator"); 587 588 map.set(n2, 'A'); 589 590 check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', 591 "Wrong CrossRefMap"); 592 check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); 593 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 594 check(map('C') == INVALID && map.inverse()['C'] == INVALID, 595 "Wrong CrossRefMap"); 596 check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0, 597 "Wrong CrossRefMap::count()"); 598 599 it = map.beginValue(); 600 check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' && 601 it == map.endValue(), "Wrong value iterator"); 602 603 map.set(n0, 'C'); 604 605 check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A', 606 "Wrong CrossRefMap"); 607 check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap"); 608 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 609 check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); 610 check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 611 "Wrong CrossRefMap::count()"); 612 613 it = map.beginValue(); 614 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 615 it == map.endValue(), "Wrong value iterator"); 616 } 617 618 // CrossRefMap 619 { 620 typedef SmartDigraph Graph; 621 DIGRAPH_TYPEDEFS(Graph); 622 623 checkConcept<ReadWriteMap<Node, int>, 624 CrossRefMap<Graph, Node, int> >(); 625 380 626 Graph gr; 381 627 typedef CrossRefMap<Graph, Node, char> CRMap; 382 628 typedef CRMap::ValueIterator ValueIt; 383 629 CRMap map(gr); 384 630 385 631 Node n0 = gr.addNode(); 386 632 Node n1 = gr.addNode(); 387 633 Node n2 = gr.addNode(); 388 634 389 635 map.set(n0, 'A'); 390 636 map.set(n1, 'B'); … … 404 650 } 405 651 652 // Iterable bool map 653 { 654 typedef SmartGraph Graph; 655 typedef SmartGraph::Node Item; 656 657 typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm; 658 checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>(); 659 660 const int num = 10; 661 Graph g; 662 Ibm map0(g, true); 663 std::vector<Item> items; 664 for (int i = 0; i < num; ++i) { 665 items.push_back(g.addNode()); 666 } 667 668 Ibm map1(g, true); 669 int n = 0; 670 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 671 check(map1[static_cast<Item>(it)], "Wrong TrueIt"); 672 ++n; 673 } 674 check(n == num, "Wrong number"); 675 676 n = 0; 677 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 678 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 679 ++n; 680 } 681 check(n == num, "Wrong number"); 682 check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt"); 683 check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false"); 684 685 map1[items[5]] = true; 686 687 n = 0; 688 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 689 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 690 ++n; 691 } 692 check(n == num, "Wrong number"); 693 694 map1[items[num / 2]] = false; 695 check(map1[items[num / 2]] == false, "Wrong map value"); 696 697 n = 0; 698 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 699 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 700 ++n; 701 } 702 check(n == num - 1, "Wrong number"); 703 704 n = 0; 705 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 706 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 707 ++n; 708 } 709 check(n == 1, "Wrong number"); 710 711 map1[items[0]] = false; 712 check(map1[items[0]] == false, "Wrong map value"); 713 714 map1[items[num - 1]] = false; 715 check(map1[items[num - 1]] == false, "Wrong map value"); 716 717 n = 0; 718 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 719 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 720 ++n; 721 } 722 check(n == num - 3, "Wrong number"); 723 check(map1.trueNum() == num - 3, "Wrong number"); 724 725 n = 0; 726 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 727 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 728 ++n; 729 } 730 check(n == 3, "Wrong number"); 731 check(map1.falseNum() == 3, "Wrong number"); 732 } 733 734 // Iterable int map 735 { 736 typedef SmartGraph Graph; 737 typedef SmartGraph::Node Item; 738 typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim; 739 740 checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>(); 741 742 const int num = 10; 743 Graph g; 744 Iim map0(g, 0); 745 std::vector<Item> items; 746 for (int i = 0; i < num; ++i) { 747 items.push_back(g.addNode()); 748 } 749 750 Iim map1(g); 751 check(map1.size() == 0, "Wrong size"); 752 753 for (int i = 0; i < num; ++i) { 754 map1[items[i]] = i; 755 } 756 check(map1.size() == num, "Wrong size"); 757 758 for (int i = 0; i < num; ++i) { 759 Iim::ItemIt it(map1, i); 760 check(static_cast<Item>(it) == items[i], "Wrong value"); 761 ++it; 762 check(static_cast<Item>(it) == INVALID, "Wrong value"); 763 } 764 765 for (int i = 0; i < num; ++i) { 766 map1[items[i]] = i % 2; 767 } 768 check(map1.size() == 2, "Wrong size"); 769 770 int n = 0; 771 for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { 772 check(map1[static_cast<Item>(it)] == 0, "Wrong value"); 773 ++n; 774 } 775 check(n == (num + 1) / 2, "Wrong number"); 776 777 for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { 778 check(map1[static_cast<Item>(it)] == 1, "Wrong value"); 779 ++n; 780 } 781 check(n == num, "Wrong number"); 782 783 } 784 785 // Iterable value map 786 { 787 typedef SmartGraph Graph; 788 typedef SmartGraph::Node Item; 789 typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm; 790 791 checkConcept<ReadWriteMap<Item, double>, Ivm>(); 792 793 const int num = 10; 794 Graph g; 795 Ivm map0(g, 0.0); 796 std::vector<Item> items; 797 for (int i = 0; i < num; ++i) { 798 items.push_back(g.addNode()); 799 } 800 801 Ivm map1(g, 0.0); 802 check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size"); 803 check(*map1.beginValue() == 0.0, "Wrong value"); 804 805 for (int i = 0; i < num; ++i) { 806 map1.set(items[i], static_cast<double>(i)); 807 } 808 check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size"); 809 810 for (int i = 0; i < num; ++i) { 811 Ivm::ItemIt it(map1, static_cast<double>(i)); 812 check(static_cast<Item>(it) == items[i], "Wrong value"); 813 ++it; 814 check(static_cast<Item>(it) == INVALID, "Wrong value"); 815 } 816 817 for (Ivm::ValueIt vit = map1.beginValue(); 818 vit != map1.endValue(); ++vit) { 819 check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit, 820 "Wrong ValueIt"); 821 } 822 823 for (int i = 0; i < num; ++i) { 824 map1.set(items[i], static_cast<double>(i % 2)); 825 } 826 check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size"); 827 828 int n = 0; 829 for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { 830 check(map1[static_cast<Item>(it)] == 0.0, "Wrong value"); 831 ++n; 832 } 833 check(n == (num + 1) / 2, "Wrong number"); 834 835 for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { 836 check(map1[static_cast<Item>(it)] == 1.0, "Wrong value"); 837 ++n; 838 } 839 check(n == num, "Wrong number"); 840 841 } 842 843 // Graph map utilities: 844 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 845 // mapFind(), mapFindIf(), mapCount(), mapCountIf() 846 // mapCopy(), mapCompare(), mapFill() 847 { 848 DIGRAPH_TYPEDEFS(SmartDigraph); 849 850 SmartDigraph g; 851 Node n1 = g.addNode(); 852 Node n2 = g.addNode(); 853 Node n3 = g.addNode(); 854 855 SmartDigraph::NodeMap<int> map1(g); 856 SmartDigraph::ArcMap<char> map2(g); 857 ConstMap<Node, A> cmap1 = A(); 858 ConstMap<Arc, C> cmap2 = C(0); 859 860 map1[n1] = 10; 861 map1[n2] = 5; 862 map1[n3] = 12; 863 864 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 865 check(mapMin(g, map1) == n2, "Wrong mapMin()"); 866 check(mapMax(g, map1) == n3, "Wrong mapMax()"); 867 check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()"); 868 check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()"); 869 check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()"); 870 check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()"); 871 872 check(mapMin(g, map2) == INVALID, "Wrong mapMin()"); 873 check(mapMax(g, map2) == INVALID, "Wrong mapMax()"); 874 875 check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); 876 check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()"); 877 878 Arc a1 = g.addArc(n1, n2); 879 Arc a2 = g.addArc(n1, n3); 880 Arc a3 = g.addArc(n2, n3); 881 Arc a4 = g.addArc(n3, n1); 882 883 map2[a1] = 'b'; 884 map2[a2] = 'a'; 885 map2[a3] = 'b'; 886 map2[a4] = 'c'; 887 888 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 889 check(mapMin(g, map2) == a2, "Wrong mapMin()"); 890 check(mapMax(g, map2) == a4, "Wrong mapMax()"); 891 check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()"); 892 check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()"); 893 check(mapMinValue(g, map2, std::greater<int>()) == 'c', 894 "Wrong mapMinValue()"); 895 check(mapMaxValue(g, map2, std::greater<int>()) == 'a', 896 "Wrong mapMaxValue()"); 897 898 check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); 899 check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()"); 900 check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()"); 901 902 check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2, 903 "Wrong mapMin()"); 904 check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4, 905 "Wrong mapMax()"); 906 check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'), 907 "Wrong mapMinValue()"); 908 check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'), 909 "Wrong mapMaxValue()"); 910 911 // mapFind(), mapFindIf() 912 check(mapFind(g, map1, 5) == n2, "Wrong mapFind()"); 913 check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()"); 914 check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()"); 915 check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()"); 916 check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()"); 917 check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()"); 918 919 check(mapFindIf(g, map1, Less<int>(7)) == n2, 920 "Wrong mapFindIf()"); 921 check(mapFindIf(g, map1, Less<int>(5)) == INVALID, 922 "Wrong mapFindIf()"); 923 check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g), 924 "Wrong mapFindIf()"); 925 check(mapFindIf(g, map2, Less<char>('a')) == INVALID, 926 "Wrong mapFindIf()"); 927 928 // mapCount(), mapCountIf() 929 check(mapCount(g, map1, 5) == 1, "Wrong mapCount()"); 930 check(mapCount(g, map1, 6) == 0, "Wrong mapCount()"); 931 check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()"); 932 check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()"); 933 check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()"); 934 check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()"); 935 check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()"); 936 937 check(mapCountIf(g, map1, Less<int>(11)) == 2, 938 "Wrong mapCountIf()"); 939 check(mapCountIf(g, map1, Less<int>(13)) == 3, 940 "Wrong mapCountIf()"); 941 check(mapCountIf(g, map1, Less<int>(5)) == 0, 942 "Wrong mapCountIf()"); 943 check(mapCountIf(g, map2, Less<char>('d')) == 4, 944 "Wrong mapCountIf()"); 945 check(mapCountIf(g, map2, Less<char>('c')) == 3, 946 "Wrong mapCountIf()"); 947 check(mapCountIf(g, map2, Less<char>('a')) == 0, 948 "Wrong mapCountIf()"); 949 950 // MapIt, ConstMapIt 951 /* 952 These tests can be used after applying bugfix #330 953 typedef SmartDigraph::NodeMap<int>::MapIt MapIt; 954 typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt; 955 check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5, 956 "Wrong NodeMap<>::MapIt"); 957 check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12, 958 "Wrong NodeMap<>::MapIt"); 959 960 int sum = 0; 961 std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum)); 962 check(sum == 27, "Wrong NodeMap<>::MapIt"); 963 std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum)); 964 check(sum == 54, "Wrong NodeMap<>::ConstMapIt"); 965 */ 966 967 // mapCopy(), mapCompare(), mapFill() 968 check(mapCompare(g, map1, map1), "Wrong mapCompare()"); 969 check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()"); 970 check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()"); 971 check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()"); 972 check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()"); 973 974 SmartDigraph::NodeMap<int> map3(g, 0); 975 SmartDigraph::ArcMap<char> map4(g, 'a'); 976 977 check(!mapCompare(g, map1, map3), "Wrong mapCompare()"); 978 check(!mapCompare(g, map2, map4), "Wrong mapCompare()"); 979 980 mapCopy(g, map1, map3); 981 mapCopy(g, map2, map4); 982 983 check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()"); 984 check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()"); 985 986 Undirector<SmartDigraph> ug(g); 987 Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x'); 988 Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14); 989 990 check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); 991 check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); 992 check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); 993 check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); 994 995 mapCopy(g, map2, umap1); 996 997 check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); 998 check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); 999 check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); 1000 check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); 1001 1002 mapCopy(g, map2, umap1); 1003 mapCopy(g, umap1, map2); 1004 mapCopy(ug, map2, umap1); 1005 mapCopy(ug, umap1, map2); 1006 1007 check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); 1008 mapCopy(ug, umap1, umap2); 1009 check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); 1010 1011 check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()"); 1012 mapFill(g, map1, 2); 1013 check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()"); 1014 1015 check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()"); 1016 mapCopy(g, constMap<Arc>('z'), map2); 1017 check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()"); 1018 } 1019 406 1020 return 0; 407 1021 } -
test/matching_test.cc
r1008 r1084 146 146 MaxMatching<Graph>::Status stat = 147 147 const_mat_test.status(n); 148 ignore_unused_variable_warning(stat);148 ::lemon::ignore_unused_variable_warning(stat); 149 149 const MaxMatching<Graph>::StatusMap& smap = 150 150 const_mat_test.statusMap(); -
test/matching_test.cc
r1083 r1084 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). … … 135 135 mat_test.startDense(); 136 136 mat_test.run(); 137 137 138 138 const_mat_test.matchingSize(); 139 139 const_mat_test.matching(e); … … 144 144 const_mat_test.mate(n); 145 145 146 MaxMatching<Graph>::Status stat = 146 MaxMatching<Graph>::Status stat = 147 147 const_mat_test.status(n); 148 148 ::lemon::ignore_unused_variable_warning(stat); … … 172 172 mat_test.start(); 173 173 mat_test.run(); 174 174 175 175 const_mat_test.matchingWeight(); 176 176 const_mat_test.matchingSize(); … … 181 181 e = mmap[n]; 182 182 const_mat_test.mate(n); 183 183 184 184 int k = 0; 185 185 const_mat_test.dualValue(); … … 209 209 mat_test.start(); 210 210 mat_test.run(); 211 211 212 212 const_mat_test.matchingWeight(); 213 213 const_mat_test.matching(e); … … 217 217 e = mmap[n]; 218 218 const_mat_test.mate(n); 219 219 220 220 int k = 0; 221 221 const_mat_test.dualValue(); … … 403 403 edgeMap("weight", weight).run(); 404 404 405 MaxMatching<SmartGraph> mm(graph); 406 mm.run(); 407 checkMatching(graph, mm); 408 409 MaxWeightedMatching<SmartGraph> mwm(graph, weight); 410 mwm.run(); 411 checkWeightedMatching(graph, weight, mwm); 412 413 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); 414 bool perfect = mwpm.run(); 415 416 check(perfect == (mm.matchingSize() * 2 == countNodes(graph)), 417 "Perfect matching found"); 418 419 if (perfect) { 420 checkWeightedPerfectMatching(graph, weight, mwpm); 405 bool perfect; 406 { 407 MaxMatching<SmartGraph> mm(graph); 408 mm.run(); 409 checkMatching(graph, mm); 410 perfect = 2 * mm.matchingSize() == countNodes(graph); 411 } 412 413 { 414 MaxWeightedMatching<SmartGraph> mwm(graph, weight); 415 mwm.run(); 416 checkWeightedMatching(graph, weight, mwm); 417 } 418 419 { 420 MaxWeightedMatching<SmartGraph> mwm(graph, weight); 421 mwm.init(); 422 mwm.start(); 423 checkWeightedMatching(graph, weight, mwm); 424 } 425 426 { 427 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); 428 bool result = mwpm.run(); 429 430 check(result == perfect, "Perfect matching found"); 431 if (perfect) { 432 checkWeightedPerfectMatching(graph, weight, mwpm); 433 } 434 } 435 436 { 437 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); 438 mwpm.init(); 439 bool result = mwpm.start(); 440 441 check(result == perfect, "Perfect matching found"); 442 if (perfect) { 443 checkWeightedPerfectMatching(graph, weight, mwpm); 444 } 421 445 } 422 446 } -
test/min_cost_arborescence_test.cc
r1008 r1084 92 92 VType c; 93 93 bool b; 94 ignore_unused_variable_warning(c,b);94 ::lemon::ignore_unused_variable_warning(c,b); 95 95 int i; 96 96 CostMap cost; … … 128 128 c = const_mcarb_test.dualValue(i); 129 129 130 ignore_unused_variable_warning(am);131 ignore_unused_variable_warning(pm);130 ::lemon::ignore_unused_variable_warning(am); 131 ::lemon::ignore_unused_variable_warning(pm); 132 132 } 133 133 -
test/min_cost_arborescence_test.cc
r1083 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 112 112 b = const_mcarb_test.emptyQueue(); 113 113 i = const_mcarb_test.queueSize(); 114 114 115 115 c = const_mcarb_test.arborescenceCost(); 116 116 b = const_mcarb_test.arborescence(e); … … 122 122 b = const_mcarb_test.reached(n); 123 123 b = const_mcarb_test.processed(n); 124 124 125 125 i = const_mcarb_test.dualNum(); 126 126 c = const_mcarb_test.dualValue(); 127 127 i = const_mcarb_test.dualSize(i); 128 128 c = const_mcarb_test.dualValue(i); 129 129 130 130 ::lemon::ignore_unused_variable_warning(am); 131 131 ::lemon::ignore_unused_variable_warning(pm); -
test/preflow_test.cc
r1008 r1084 87 87 VType v; 88 88 bool b; 89 ignore_unused_variable_warning(v,b);89 ::lemon::ignore_unused_variable_warning(v,b); 90 90 91 91 typedef Preflow<Digraph, CapMap> … … 121 121 const_preflow_test.minCutMap(cut); 122 122 123 ignore_unused_variable_warning(fm);123 ::lemon::ignore_unused_variable_warning(fm); 124 124 } 125 125 -
test/preflow_test.cc
r1083 r1084 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). … … 97 97 const PreflowType& const_preflow_test = preflow_test; 98 98 99 const PreflowType::Elevator& elev = const_preflow_test.elevator(); 100 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); 101 PreflowType::Tolerance tol = const_preflow_test.tolerance(); 102 preflow_test.tolerance(tol); 103 99 104 preflow_test 100 105 .capacityMap(cap) … … 115 120 b = const_preflow_test.minCut(n); 116 121 const_preflow_test.minCutMap(cut); 117 122 118 123 ::lemon::ignore_unused_variable_warning(fm); 119 124 } -
test/suurballe_test.cc
r1008 r1084 118 118 int f; 119 119 VType c; 120 ignore_unused_variable_warning(f,c);120 ::lemon::ignore_unused_variable_warning(f,c); 121 121 122 122 c = const_suurb_test.totalLength(); … … 130 130 Path<Digraph> p = const_suurb_test.path(k); 131 131 132 ignore_unused_variable_warning(fm);133 ignore_unused_variable_warning(pm);132 ::lemon::ignore_unused_variable_warning(fm); 133 ::lemon::ignore_unused_variable_warning(pm); 134 134 } 135 135 -
test/suurballe_test.cc
r1083 r1084 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). … … 24 24 #include <lemon/suurballe.h> 25 25 #include <lemon/concepts/digraph.h> 26 #include <lemon/concepts/heap.h> 26 27 27 28 #include "test_tools.h" … … 81 82 typedef Digraph::Arc Arc; 82 83 typedef concepts::ReadMap<Arc, VType> LengthMap; 83 84 typedef Suurballe<Digraph, LengthMap> SuurballeType; 84 85 typedef Suurballe<Digraph, LengthMap> ST; 86 typedef Suurballe<Digraph, LengthMap> 87 ::SetFlowMap<ST::FlowMap> 88 ::SetPotentialMap<ST::PotentialMap> 89 ::SetPath<SimplePath<Digraph> > 90 ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > > 91 ::Create SuurballeType; 85 92 86 93 Digraph g; … … 102 109 k = suurb_test.run(n, n, k); 103 110 suurb_test.init(n); 111 suurb_test.fullInit(n); 112 suurb_test.start(n); 113 suurb_test.start(n, k); 104 114 k = suurb_test.findFlow(n); 105 115 k = suurb_test.findFlow(n, k); 106 116 suurb_test.findPaths(); 107 117 108 118 int f; 109 119 VType c; … … 119 129 k = const_suurb_test.pathNum(); 120 130 Path<Digraph> p = const_suurb_test.path(k); 121 131 122 132 ::lemon::ignore_unused_variable_warning(fm); 123 133 ::lemon::ignore_unused_variable_warning(pm); … … 198 208 run(); 199 209 200 // Find 2 paths210 // Check run() 201 211 { 202 212 Suurballe<ListDigraph> suurballe(digraph, length); 213 214 // Find 2 paths 203 215 check(suurballe.run(s, t) == 2, "Wrong number of paths"); 204 216 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), … … 210 222 for (int i = 0; i < suurballe.pathNum(); ++i) 211 223 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 212 } 213 214 // Find 3 paths 215 { 216 Suurballe<ListDigraph> suurballe(digraph, length); 224 225 // Find 3 paths 217 226 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); 218 227 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), … … 224 233 for (int i = 0; i < suurballe.pathNum(); ++i) 225 234 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 226 } 227 228 // Find 5 paths (only 3 can be found) 229 { 230 Suurballe<ListDigraph> suurballe(digraph, length); 235 236 // Find 5 paths (only 3 can be found) 231 237 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); 232 238 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), … … 240 246 } 241 247 248 // Check fullInit() + start() 249 { 250 Suurballe<ListDigraph> suurballe(digraph, length); 251 suurballe.fullInit(s); 252 253 // Find 2 paths 254 check(suurballe.start(t) == 2, "Wrong number of paths"); 255 check(suurballe.totalLength() == 510, "The flow is not optimal"); 256 257 // Find 3 paths 258 check(suurballe.start(t, 3) == 3, "Wrong number of paths"); 259 check(suurballe.totalLength() == 1040, "The flow is not optimal"); 260 261 // Find 5 paths (only 3 can be found) 262 check(suurballe.start(t, 5) == 3, "Wrong number of paths"); 263 check(suurballe.totalLength() == 1040, "The flow is not optimal"); 264 } 265 242 266 return 0; 243 267 }
Note: See TracChangeset
for help on using the changeset viewer.