Changeset 781:bd72f8d20f33 in lemon for lemon/concepts/digraph.h
 Timestamp:
 08/23/09 11:07:50 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/digraph.h
r627 r781 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. 105 }; 106 107 /// Iterator class for the nodes. 108 109 /// This iterator goes through each node of the digraph. 117 110 /// Its usage is quite simple, for example you can count the number 118 /// of nodes in digraph \c g of type \cDigraph like this: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 arcset, 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 … … 208 199 /// 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 arcset, 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 244 /// Its usage is quite simple, for example you can count the number 256 /// of outgoing arcs of a node \c n257 /// in digraph \c g of type \cDigraph as follows.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 arcset, 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. 284 285 /// Iterator class for the arcs. 286 287 /// This iterator goes through each arc of the digraph. 300 288 /// 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: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) { 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 arcset, 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) { 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 … … 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
Note: See TracChangeset
for help on using the changeset viewer.