Changes in lemon/concepts/digraph.h [956:141f9c0db4a3:627:2313edd0db0b] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/digraph.h
r956 r627 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 105 * Copyright (C) 2003-2009 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 common interface of all directed39 /// graphs (digraphs).38 /// This class describes the \ref concept "concept" of the 39 /// immutable directed digraphs. 40 40 /// 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. 41 /// Note that actual digraph implementation like @ref ListDigraph or 42 /// @ref SmartDigraph may have several additional functionality. 47 43 /// 48 /// \sa Graph44 /// \sa concept 49 45 class Digraph { 50 46 private: 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. 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 55 58 void operator=(const Digraph &) {} 56 57 59 public: 58 /// Default constructor. 60 ///\e 61 62 /// Defalult constructor. 63 64 /// Defalult constructor. 65 /// 59 66 Digraph() { } 60 61 /// The node type of the digraph 67 /// Class for identifying a node of the digraph 62 68 63 69 /// This class identifies a node of the digraph. It also serves 64 70 /// as a base class of the node iterators, 65 /// thus they convert to this type.71 /// thus they will convert to this type. 66 72 class Node { 67 73 public: 68 74 /// Default constructor 69 75 70 /// Default constructor.71 /// \warning It sets the objectto an undefined value.76 /// @warning The default constructor sets the iterator 77 /// to an undefined value. 72 78 Node() { } 73 79 /// Copy constructor. … … 77 83 Node(const Node&) { } 78 84 79 /// %Invalid constructor \& conversion.80 81 /// Initializes the objectto be invalid.85 /// Invalid constructor \& conversion. 86 87 /// This constructor initializes the iterator to be invalid. 82 88 /// \sa Invalid for more details. 83 89 Node(Invalid) { } 84 90 /// Equality operator 85 91 86 /// Equality operator.87 ///88 92 /// Two iterators are equal if and only if they point to the 89 /// same object or both are \c INVALID.93 /// same object or both are invalid. 90 94 bool operator==(Node) const { return true; } 91 95 92 96 /// Inequality operator 93 97 94 /// Inequality operator. 98 /// \sa operator==(Node n) 99 /// 95 100 bool operator!=(Node) const { return true; } 96 101 97 102 /// Artificial ordering operator. 98 103 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. 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. 104 110 bool operator<(Node) const { return false; } 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: 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: 112 119 ///\code 113 120 /// int count=0; … … 118 125 /// Default constructor 119 126 120 /// Default constructor.121 /// \warning It sets the iteratorto an undefined value.127 /// @warning The default constructor sets the iterator 128 /// to an undefined value. 122 129 NodeIt() { } 123 130 /// Copy constructor. … … 126 133 /// 127 134 NodeIt(const NodeIt& n) : Node(n) { } 128 /// %Invalid constructor \& conversion.129 130 /// Initialize sthe iterator to be invalid.135 /// Invalid constructor \& conversion. 136 137 /// Initialize the iterator to be invalid. 131 138 /// \sa Invalid for more details. 132 139 NodeIt(Invalid) { } 133 140 /// Sets the iterator to the first node. 134 141 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 /// 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. 142 151 NodeIt(const Digraph&, const Node&) { } 143 152 /// Next node. … … 149 158 150 159 151 /// The arc typeof the digraph160 /// Class for identifying an arc of the digraph 152 161 153 162 /// This class identifies an arc of the digraph. It also serves … … 158 167 /// Default constructor 159 168 160 /// Default constructor.161 /// \warning It sets the objectto an undefined value.169 /// @warning The default constructor sets the iterator 170 /// to an undefined value. 162 171 Arc() { } 163 172 /// Copy constructor. … … 166 175 /// 167 176 Arc(const Arc&) { } 168 /// %Invalid constructor \& conversion.169 170 /// Initialize s the objectto be invalid.171 /// \sa Invalid for more details.177 /// Initialize the iterator to be invalid. 178 179 /// Initialize the iterator to be invalid. 180 /// 172 181 Arc(Invalid) { } 173 182 /// Equality operator 174 183 175 /// Equality operator.176 ///177 184 /// Two iterators are equal if and only if they point to the 178 /// same object or both are \c INVALID.185 /// same object or both are invalid. 179 186 bool operator==(Arc) const { return true; } 180 187 /// Inequality operator 181 188 182 /// Inequality operator. 189 /// \sa operator==(Arc n) 190 /// 183 191 bool operator!=(Arc) const { return true; } 184 192 185 193 /// Artificial ordering operator. 186 194 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. 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. 192 201 bool operator<(Arc) const { return false; } 193 202 }; 194 203 195 /// Iterator class forthe outgoing arcs of a node.204 /// This iterator goes trough the outgoing arcs of a node. 196 205 197 206 /// This iterator goes trough the \e outgoing arcs of a certain node 198 207 /// of a digraph. 199 /// Its usage is quite simple, for example ,you can count the number208 /// Its usage is quite simple, for example you can count the number 200 209 /// of outgoing arcs of a node \c n 201 /// in a digraph \c g of type \c %Digraph as follows.210 /// in digraph \c g of type \c Digraph as follows. 202 211 ///\code 203 212 /// int count=0; 204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; 205 214 ///\endcode 215 206 216 class OutArcIt : public Arc { 207 217 public: 208 218 /// Default constructor 209 219 210 /// Default constructor.211 /// \warning It sets the iteratorto an undefined value.220 /// @warning The default constructor sets the iterator 221 /// to an undefined value. 212 222 OutArcIt() { } 213 223 /// Copy constructor. … … 216 226 /// 217 227 OutArcIt(const OutArcIt& e) : Arc(e) { } 218 /// %Invalid constructor \& conversion.219 220 /// Initialize sthe iterator to be invalid.221 /// \sa Invalid for more details.228 /// Initialize the iterator to be invalid. 229 230 /// Initialize the iterator to be invalid. 231 /// 222 232 OutArcIt(Invalid) { } 223 /// Sets the iterator to the first outgoing arc.224 225 /// Sets the iterator to the first outgoing arc of the given node.226 /// 233 /// This constructor sets the iterator to the first outgoing arc. 234 235 /// This constructor sets the iterator to the first outgoing arc of 236 /// the node. 227 237 OutArcIt(const Digraph&, const Node&) { } 228 /// Sets the iterator to the given arc. 229 230 /// Sets the iterator to the given arc of the given digraph. 231 /// 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. 232 243 OutArcIt(const Digraph&, const Arc&) { } 233 /// 244 ///Next outgoing arc 234 245 235 246 /// Assign the iterator to the next … … 238 249 }; 239 250 240 /// Iterator class forthe incoming arcs of a node.251 /// This iterator goes trough the incoming arcs of a node. 241 252 242 253 /// This iterator goes trough the \e incoming arcs of a certain node 243 254 /// of a digraph. 244 /// Its usage is quite simple, for example ,you can count the number245 /// of incoming arcs of a node \c n246 /// in a digraph \c g of type \c %Digraph as follows.255 /// Its usage is quite simple, for example you can count the number 256 /// of outgoing arcs of a node \c n 257 /// in digraph \c g of type \c Digraph as follows. 247 258 ///\code 248 259 /// int count=0; 249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; 250 261 ///\endcode 262 251 263 class InArcIt : public Arc { 252 264 public: 253 265 /// Default constructor 254 266 255 /// Default constructor.256 /// \warning It sets the iteratorto an undefined value.267 /// @warning The default constructor sets the iterator 268 /// to an undefined value. 257 269 InArcIt() { } 258 270 /// Copy constructor. … … 261 273 /// 262 274 InArcIt(const InArcIt& e) : Arc(e) { } 263 /// %Invalid constructor \& conversion.264 265 /// Initialize sthe iterator to be invalid.266 /// \sa Invalid for more details.275 /// Initialize the iterator to be invalid. 276 277 /// Initialize the iterator to be invalid. 278 /// 267 279 InArcIt(Invalid) { } 268 /// Sets the iterator to thefirst incoming arc.269 270 /// Sets the iterator to the first incoming arc of the given node.271 /// 280 /// This constructor sets the iterator to first incoming arc. 281 282 /// This constructor set the iterator to the first incoming arc of 283 /// the node. 272 284 InArcIt(const Digraph&, const Node&) { } 273 /// Sets the iterator to the given arc. 274 275 /// Sets the iterator to the given arc of the given digraph. 276 /// 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. 277 290 InArcIt(const Digraph&, const Arc&) { } 278 291 /// Next incoming arc 279 292 280 /// Assign the iterator to the next 281 /// incoming arc of the corresponding node.293 /// Assign the iterator to the next inarc of the corresponding node. 294 /// 282 295 InArcIt& operator++() { return *this; } 283 296 }; 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: 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: 290 302 ///\code 291 303 /// int count=0; 292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; 293 305 ///\endcode 294 306 class ArcIt : public Arc { … … 296 308 /// Default constructor 297 309 298 /// Default constructor.299 /// \warning It sets the iteratorto an undefined value.310 /// @warning The default constructor sets the iterator 311 /// to an undefined value. 300 312 ArcIt() { } 301 313 /// Copy constructor. … … 304 316 /// 305 317 ArcIt(const ArcIt& e) : Arc(e) { } 306 /// %Invalid constructor \& conversion.307 308 /// Initialize sthe iterator to be invalid.309 /// \sa Invalid for more details.318 /// Initialize the iterator to be invalid. 319 320 /// Initialize the iterator to be invalid. 321 /// 310 322 ArcIt(Invalid) { } 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) { 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 /// 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) { 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. 320 333 ArcIt(const Digraph&, const Arc&) { } 321 /// 334 ///Next arc 322 335 323 336 /// Assign the iterator to the next arc. 324 ///325 337 ArcIt& operator++() { return *this; } 326 338 }; 327 328 /// \brief The source node of the arc. 329 /// 330 /// Returns the source node of the given arc. 339 ///Gives back the target node of an arc. 340 341 ///Gives back the target node of an arc. 342 /// 343 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 /// 331 348 Node source(Arc) const { return INVALID; } 332 349 333 /// \brief The target node of the arc. 334 /// 335 /// Returns the target node of the given arc. 336 Node target(Arc) const { return INVALID; } 337 338 /// \brief The ID of the node. 339 /// 340 /// Returns the ID of the given node. 350 /// \brief Returns the ID of the node. 341 351 int id(Node) const { return -1; } 342 352 343 /// \brief The ID of the arc. 344 /// 345 /// Returns the ID of the given arc. 353 /// \brief Returns the ID of the arc. 346 354 int id(Arc) const { return -1; } 347 355 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. 356 /// \brief Returns the node with the given ID. 357 /// 358 /// \pre The argument should be a valid node ID in the graph. 352 359 Node nodeFromId(int) const { return INVALID; } 353 360 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. 361 /// \brief Returns the arc with the given ID. 362 /// 363 /// \pre The argument should be a valid arc ID in the graph. 358 364 Arc arcFromId(int) const { return INVALID; } 359 365 360 /// \brief An upper bound on the node IDs. 361 /// 362 /// Returns an upper bound on the node IDs. 366 /// \brief Returns an upper bound on the node IDs. 363 367 int maxNodeId() const { return -1; } 364 368 365 /// \brief An upper bound on the arc IDs. 366 /// 367 /// Returns an upper bound on the arc IDs. 369 /// \brief Returns an upper bound on the arc IDs. 368 370 int maxArcId() const { return -1; } 369 371 … … 391 393 int maxId(Arc) const { return -1; } 392 394 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 398 395 /// \brief The base node of the iterator. 399 396 /// 400 /// Returns the base node of the given outgoing arc iterator401 /// (i.e. the source node of the corresponding arc).402 Node baseNode( OutArcIt) const { return INVALID; }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; } 403 400 404 401 /// \brief The running node of the iterator. 405 402 /// 406 /// Returns the running node of the given outgoing arc iterator407 /// (i.e. the target node of the corresponding arc).408 Node runningNode( OutArcIt) const { return INVALID; }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; } 409 406 410 407 /// \brief The base node of the iterator. 411 408 /// 412 /// Returns the base node of the given incomming arc iterator413 /// (i.e. the target node of the corresponding arc).414 Node baseNode( InArcIt) const { return INVALID; }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; } 415 412 416 413 /// \brief The running node of the iterator. 417 414 /// 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. 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. 426 427 template<class T> 427 428 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 428 429 public: 429 430 430 /// Constructor431 explicitNodeMap(const Digraph&) { }432 /// Constructor with given initial value431 ///\e 432 NodeMap(const Digraph&) { } 433 ///\e 433 434 NodeMap(const Digraph&, T) { } 434 435 435 436 private: 436 437 ///Copy constructor 437 NodeMap(const NodeMap& nm) : 438 NodeMap(const NodeMap& nm) : 438 439 ReferenceMap<Node, T, T&, const T&>(nm) { } 439 440 ///Assignment operator … … 445 446 }; 446 447 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. 448 /// \brief Reference map of the arcs to type \c T. 449 /// 450 /// Reference map of the arcs to type \c T. 451 451 template<class T> 452 452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 453 453 public: 454 454 455 /// Constructor456 explicitArcMap(const Digraph&) { }457 /// Constructor with given initial value455 ///\e 456 ArcMap(const Digraph&) { } 457 ///\e 458 458 ArcMap(const Digraph&, T) { } 459 460 459 private: 461 460 ///Copy constructor
Note: See TracChangeset
for help on using the changeset viewer.