[959] | 1 | /* -*- C++ -*- |
---|
| 2 | * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library |
---|
| 3 | * |
---|
[1164] | 4 | * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
[959] | 5 | * (Egervary Combinatorial Optimization Research Group, EGRES). |
---|
| 6 | * |
---|
| 7 | * Permission to use, modify and distribute this software is granted |
---|
| 8 | * provided that this copyright notice appears in all copies. For |
---|
| 9 | * precise terms see the accompanying LICENSE file. |
---|
| 10 | * |
---|
| 11 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 12 | * express or implied, and with no claim as to its suitability for any |
---|
| 13 | * purpose. |
---|
| 14 | * |
---|
| 15 | */ |
---|
| 16 | |
---|
| 17 | #ifndef LEMON_CONCEPT_SYM_GRAPH_H |
---|
| 18 | #define LEMON_CONCEPT_SYM_GRAPH_H |
---|
| 19 | |
---|
| 20 | ///\ingroup concept |
---|
| 21 | ///\file |
---|
| 22 | ///\brief Declaration of SymGraph. |
---|
| 23 | |
---|
| 24 | #include <lemon/invalid.h> |
---|
| 25 | #include <lemon/concept/graph.h> |
---|
| 26 | #include <lemon/concept/maps.h> |
---|
| 27 | |
---|
| 28 | namespace lemon { |
---|
| 29 | namespace concept { |
---|
| 30 | |
---|
| 31 | /// \addtogroup concept |
---|
| 32 | /// @{ |
---|
| 33 | |
---|
| 34 | /// An empty static graph class. |
---|
| 35 | |
---|
| 36 | /// This class provides all the common features of a symmetric |
---|
| 37 | /// graph structure, however completely without implementations and |
---|
| 38 | /// real data structures behind the interface. |
---|
| 39 | /// All graph algorithms should compile with this class, but it will not |
---|
| 40 | /// run properly, of course. |
---|
| 41 | /// |
---|
| 42 | /// It can be used for checking the interface compatibility, |
---|
| 43 | /// or it can serve as a skeleton of a new symmetric graph structure. |
---|
| 44 | /// |
---|
| 45 | /// Also, you will find here the full documentation of a certain graph |
---|
| 46 | /// feature, the documentation of a real symmetric graph imlementation |
---|
| 47 | /// like @ref SymListGraph or |
---|
| 48 | /// @ref lemon::SymSmartGraph will just refer to this structure. |
---|
| 49 | class StaticSymGraph |
---|
| 50 | { |
---|
| 51 | public: |
---|
| 52 | /// Defalult constructor. |
---|
| 53 | |
---|
| 54 | /// Defalult constructor. |
---|
| 55 | /// |
---|
| 56 | StaticSymGraph() { } |
---|
| 57 | ///Copy consructor. |
---|
| 58 | |
---|
| 59 | // ///\todo It is not clear, what we expect from a copy constructor. |
---|
| 60 | // ///E.g. How to assign the nodes/edges to each other? What about maps? |
---|
| 61 | // StaticGraph(const StaticGraph& g) { } |
---|
| 62 | |
---|
| 63 | /// The base type of node iterators, |
---|
| 64 | /// or in other words, the trivial node iterator. |
---|
| 65 | |
---|
| 66 | /// This is the base type of each node iterator, |
---|
| 67 | /// thus each kind of node iterator converts to this. |
---|
| 68 | /// More precisely each kind of node iterator should be inherited |
---|
| 69 | /// from the trivial node iterator. |
---|
| 70 | class Node { |
---|
| 71 | public: |
---|
| 72 | /// Default constructor |
---|
| 73 | |
---|
| 74 | /// @warning The default constructor sets the iterator |
---|
| 75 | /// to an undefined value. |
---|
| 76 | Node() { } |
---|
| 77 | /// Copy constructor. |
---|
| 78 | |
---|
| 79 | /// Copy constructor. |
---|
| 80 | /// |
---|
| 81 | Node(const Node&) { } |
---|
| 82 | |
---|
| 83 | /// Invalid constructor \& conversion. |
---|
| 84 | |
---|
| 85 | /// This constructor initializes the iterator to be invalid. |
---|
| 86 | /// \sa Invalid for more details. |
---|
| 87 | Node(Invalid) { } |
---|
| 88 | /// Equality operator |
---|
| 89 | |
---|
| 90 | /// Two iterators are equal if and only if they point to the |
---|
| 91 | /// same object or both are invalid. |
---|
| 92 | bool operator==(Node) const { return true; } |
---|
| 93 | |
---|
| 94 | /// Inequality operator |
---|
| 95 | |
---|
| 96 | /// \sa operator==(Node n) |
---|
| 97 | /// |
---|
| 98 | bool operator!=(Node) const { return true; } |
---|
| 99 | |
---|
| 100 | ///Comparison operator. |
---|
| 101 | |
---|
| 102 | ///This is a strict ordering between the nodes. |
---|
| 103 | /// |
---|
| 104 | ///This ordering can be different from the order in which NodeIt |
---|
| 105 | ///goes through the nodes. |
---|
| 106 | ///\todo Possibly we don't need it. |
---|
| 107 | bool operator<(Node) const { return true; } |
---|
| 108 | }; |
---|
| 109 | |
---|
| 110 | /// This iterator goes through each node. |
---|
| 111 | |
---|
| 112 | /// This iterator goes through each node. |
---|
| 113 | /// Its usage is quite simple, for example you can count the number |
---|
| 114 | /// of nodes in graph \c g of type \c Graph like this: |
---|
| 115 | /// \code |
---|
| 116 | /// int count=0; |
---|
| 117 | /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
---|
| 118 | /// \endcode |
---|
| 119 | class NodeIt : public Node { |
---|
| 120 | public: |
---|
| 121 | /// Default constructor |
---|
| 122 | |
---|
| 123 | /// @warning The default constructor sets the iterator |
---|
| 124 | /// to an undefined value. |
---|
| 125 | NodeIt() { } |
---|
| 126 | /// Copy constructor. |
---|
| 127 | |
---|
| 128 | /// Copy constructor. |
---|
| 129 | /// |
---|
| 130 | NodeIt(const NodeIt&) { } |
---|
| 131 | /// Invalid constructor \& conversion. |
---|
| 132 | |
---|
| 133 | /// Initialize the iterator to be invalid. |
---|
| 134 | /// \sa Invalid for more details. |
---|
| 135 | NodeIt(Invalid) { } |
---|
| 136 | /// Sets the iterator to the first node. |
---|
| 137 | |
---|
| 138 | /// Sets the iterator to the first node of \c g. |
---|
| 139 | /// |
---|
| 140 | NodeIt(const StaticSymGraph& g) { } |
---|
| 141 | /// Node -> NodeIt conversion. |
---|
| 142 | |
---|
| 143 | /// Sets the iterator to the node of \c g pointed by the trivial |
---|
| 144 | /// iterator n. |
---|
| 145 | /// This feature necessitates that each time we |
---|
| 146 | /// iterate the edge-set, the iteration order is the same. |
---|
| 147 | NodeIt(const StaticSymGraph& g, const Node& n) { } |
---|
| 148 | /// Next node. |
---|
| 149 | |
---|
| 150 | /// Assign the iterator to the next node. |
---|
| 151 | /// |
---|
| 152 | NodeIt& operator++() { return *this; } |
---|
| 153 | }; |
---|
| 154 | |
---|
| 155 | |
---|
| 156 | /// The base type of the symmetric edge iterators. |
---|
| 157 | |
---|
| 158 | /// The base type of the symmetric edge iterators. |
---|
| 159 | /// |
---|
| 160 | class SymEdge { |
---|
| 161 | public: |
---|
| 162 | /// Default constructor |
---|
| 163 | |
---|
| 164 | /// @warning The default constructor sets the iterator |
---|
| 165 | /// to an undefined value. |
---|
| 166 | SymEdge() { } |
---|
| 167 | /// Copy constructor. |
---|
| 168 | |
---|
| 169 | /// Copy constructor. |
---|
| 170 | /// |
---|
| 171 | SymEdge(const SymEdge&) { } |
---|
| 172 | /// Initialize the iterator to be invalid. |
---|
| 173 | |
---|
| 174 | /// Initialize the iterator to be invalid. |
---|
| 175 | /// |
---|
| 176 | SymEdge(Invalid) { } |
---|
| 177 | /// Equality operator |
---|
| 178 | |
---|
| 179 | /// Two iterators are equal if and only if they point to the |
---|
| 180 | /// same object or both are invalid. |
---|
| 181 | bool operator==(SymEdge) const { return true; } |
---|
| 182 | /// Inequality operator |
---|
| 183 | |
---|
| 184 | /// \sa operator==(Node n) |
---|
| 185 | /// |
---|
| 186 | bool operator!=(SymEdge) const { return true; } |
---|
| 187 | ///Comparison operator. |
---|
| 188 | |
---|
| 189 | ///This is a strict ordering between the nodes. |
---|
| 190 | /// |
---|
| 191 | ///This ordering can be different from the order in which NodeIt |
---|
| 192 | ///goes through the nodes. |
---|
| 193 | ///\todo Possibly we don't need it. |
---|
| 194 | bool operator<(SymEdge) const { return true; } |
---|
| 195 | }; |
---|
| 196 | |
---|
| 197 | |
---|
| 198 | /// The base type of the edge iterators. |
---|
| 199 | |
---|
| 200 | /// The base type of the edge iterators. |
---|
| 201 | /// |
---|
| 202 | class Edge : public SymEdge { |
---|
| 203 | public: |
---|
| 204 | /// Default constructor |
---|
| 205 | |
---|
| 206 | /// @warning The default constructor sets the iterator |
---|
| 207 | /// to an undefined value. |
---|
| 208 | Edge() { } |
---|
| 209 | /// Copy constructor. |
---|
| 210 | |
---|
| 211 | /// Copy constructor. |
---|
| 212 | /// |
---|
| 213 | Edge(const Edge&) { } |
---|
| 214 | /// Initialize the iterator to be invalid. |
---|
| 215 | |
---|
| 216 | /// Initialize the iterator to be invalid. |
---|
| 217 | /// |
---|
| 218 | Edge(Invalid) { } |
---|
| 219 | /// Equality operator |
---|
| 220 | |
---|
| 221 | /// Two iterators are equal if and only if they point to the |
---|
| 222 | /// same object or both are invalid. |
---|
| 223 | bool operator==(Edge) const { return true; } |
---|
| 224 | /// Inequality operator |
---|
| 225 | |
---|
| 226 | /// \sa operator==(Node n) |
---|
| 227 | /// |
---|
| 228 | bool operator!=(Edge) const { return true; } |
---|
| 229 | ///Comparison operator. |
---|
| 230 | |
---|
| 231 | ///This is a strict ordering between the nodes. |
---|
| 232 | /// |
---|
| 233 | ///This ordering can be different from the order in which NodeIt |
---|
| 234 | ///goes through the nodes. |
---|
| 235 | ///\todo Possibly we don't need it. |
---|
| 236 | bool operator<(Edge) const { return true; } |
---|
| 237 | }; |
---|
| 238 | |
---|
| 239 | /// This iterator goes trough the outgoing edges of a node. |
---|
| 240 | |
---|
| 241 | /// This iterator goes trough the \e outgoing edges of a certain node |
---|
| 242 | /// of a graph. |
---|
| 243 | /// Its usage is quite simple, for example you can count the number |
---|
| 244 | /// of outgoing edges of a node \c n |
---|
| 245 | /// in graph \c g of type \c Graph as follows. |
---|
| 246 | /// \code |
---|
| 247 | /// int count=0; |
---|
| 248 | /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
---|
| 249 | /// \endcode |
---|
| 250 | |
---|
| 251 | class OutEdgeIt : public Edge { |
---|
| 252 | public: |
---|
| 253 | /// Default constructor |
---|
| 254 | |
---|
| 255 | /// @warning The default constructor sets the iterator |
---|
| 256 | /// to an undefined value. |
---|
| 257 | OutEdgeIt() { } |
---|
| 258 | /// Copy constructor. |
---|
| 259 | |
---|
| 260 | /// Copy constructor. |
---|
| 261 | /// |
---|
| 262 | OutEdgeIt(const OutEdgeIt&) { } |
---|
| 263 | /// Initialize the iterator to be invalid. |
---|
| 264 | |
---|
| 265 | /// Initialize the iterator to be invalid. |
---|
| 266 | /// |
---|
| 267 | OutEdgeIt(Invalid) { } |
---|
| 268 | /// This constructor sets the iterator to first outgoing edge. |
---|
| 269 | |
---|
| 270 | /// This constructor set the iterator to the first outgoing edge of |
---|
| 271 | /// node |
---|
| 272 | ///@param n the node |
---|
| 273 | ///@param g the graph |
---|
| 274 | OutEdgeIt(const StaticSymGraph& g, const Node& n) { } |
---|
| 275 | /// Edge -> OutEdgeIt conversion |
---|
| 276 | |
---|
| 277 | /// Sets the iterator to the value of the trivial iterator \c e. |
---|
| 278 | /// This feature necessitates that each time we |
---|
| 279 | /// iterate the edge-set, the iteration order is the same. |
---|
| 280 | OutEdgeIt(const StaticSymGraph& g, const Edge& e) { } |
---|
| 281 | ///Next outgoing edge |
---|
| 282 | |
---|
| 283 | /// Assign the iterator to the next |
---|
| 284 | /// outgoing edge of the corresponding node. |
---|
| 285 | OutEdgeIt& operator++() { return *this; } |
---|
| 286 | }; |
---|
| 287 | |
---|
| 288 | /// This iterator goes trough the incoming edges of a node. |
---|
| 289 | |
---|
| 290 | /// This iterator goes trough the \e incoming edges of a certain node |
---|
| 291 | /// of a graph. |
---|
| 292 | /// Its usage is quite simple, for example you can count the number |
---|
| 293 | /// of outgoing edges of a node \c n |
---|
| 294 | /// in graph \c g of type \c Graph as follows. |
---|
| 295 | /// \code |
---|
| 296 | /// int count=0; |
---|
| 297 | /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
---|
| 298 | /// \endcode |
---|
| 299 | |
---|
| 300 | class InEdgeIt : public Edge { |
---|
| 301 | public: |
---|
| 302 | /// Default constructor |
---|
| 303 | |
---|
| 304 | /// @warning The default constructor sets the iterator |
---|
| 305 | /// to an undefined value. |
---|
| 306 | InEdgeIt() { } |
---|
| 307 | /// Copy constructor. |
---|
| 308 | |
---|
| 309 | /// Copy constructor. |
---|
| 310 | /// |
---|
| 311 | InEdgeIt(const InEdgeIt&) { } |
---|
| 312 | /// Initialize the iterator to be invalid. |
---|
| 313 | |
---|
| 314 | /// Initialize the iterator to be invalid. |
---|
| 315 | /// |
---|
| 316 | InEdgeIt(Invalid) { } |
---|
| 317 | /// This constructor sets the iterator to first incoming edge. |
---|
| 318 | |
---|
| 319 | /// This constructor set the iterator to the first incoming edge of |
---|
| 320 | /// node |
---|
| 321 | ///@param n the node |
---|
| 322 | ///@param g the graph |
---|
| 323 | InEdgeIt(const StaticSymGraph& g, const Node& n) { } |
---|
| 324 | /// Edge -> InEdgeIt conversion |
---|
| 325 | |
---|
| 326 | /// Sets the iterator to the value of the trivial iterator \c e. |
---|
| 327 | /// This feature necessitates that each time we |
---|
| 328 | /// iterate the edge-set, the iteration order is the same. |
---|
| 329 | InEdgeIt(const StaticSymGraph& g, const Edge& n) { } |
---|
| 330 | /// Next incoming edge |
---|
| 331 | |
---|
| 332 | /// Assign the iterator to the next inedge of the corresponding node. |
---|
| 333 | /// |
---|
| 334 | InEdgeIt& operator++() { return *this; } |
---|
| 335 | }; |
---|
| 336 | /// This iterator goes through each symmetric edge. |
---|
| 337 | |
---|
| 338 | /// This iterator goes through each symmetric edge of a graph. |
---|
| 339 | /// Its usage is quite simple, for example you can count the number |
---|
| 340 | /// of symmetric edges in a graph \c g of type \c Graph as follows: |
---|
| 341 | /// \code |
---|
| 342 | /// int count=0; |
---|
| 343 | /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count; |
---|
| 344 | /// \endcode |
---|
| 345 | class SymEdgeIt : public SymEdge { |
---|
| 346 | public: |
---|
| 347 | /// Default constructor |
---|
| 348 | |
---|
| 349 | /// @warning The default constructor sets the iterator |
---|
| 350 | /// to an undefined value. |
---|
| 351 | SymEdgeIt() { } |
---|
| 352 | /// Copy constructor. |
---|
| 353 | |
---|
| 354 | /// Copy constructor. |
---|
| 355 | /// |
---|
| 356 | SymEdgeIt(const SymEdgeIt&) { } |
---|
| 357 | /// Initialize the iterator to be invalid. |
---|
| 358 | |
---|
| 359 | /// Initialize the iterator to be invalid. |
---|
| 360 | /// |
---|
| 361 | SymEdgeIt(Invalid) { } |
---|
| 362 | /// This constructor sets the iterator to first edge. |
---|
| 363 | |
---|
| 364 | /// This constructor set the iterator to the first edge of |
---|
| 365 | /// node |
---|
| 366 | ///@param g the graph |
---|
| 367 | SymEdgeIt(const StaticSymGraph& g) { } |
---|
| 368 | /// Edge -> EdgeIt conversion |
---|
| 369 | |
---|
| 370 | /// Sets the iterator to the value of the trivial iterator \c e. |
---|
| 371 | /// This feature necessitates that each time we |
---|
| 372 | /// iterate the edge-set, the iteration order is the same. |
---|
| 373 | SymEdgeIt(const StaticSymGraph&, const SymEdge&) { } |
---|
| 374 | ///Next edge |
---|
| 375 | |
---|
| 376 | /// Assign the iterator to the next |
---|
| 377 | /// edge of the corresponding node. |
---|
| 378 | SymEdgeIt& operator++() { return *this; } |
---|
| 379 | }; |
---|
| 380 | /// This iterator goes through each edge. |
---|
| 381 | |
---|
| 382 | /// This iterator goes through each edge of a graph. |
---|
| 383 | /// Its usage is quite simple, for example you can count the number |
---|
| 384 | /// of edges in a graph \c g of type \c Graph as follows: |
---|
| 385 | /// \code |
---|
| 386 | /// int count=0; |
---|
| 387 | /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
---|
| 388 | /// \endcode |
---|
| 389 | class EdgeIt : public Edge { |
---|
| 390 | public: |
---|
| 391 | /// Default constructor |
---|
| 392 | |
---|
| 393 | /// @warning The default constructor sets the iterator |
---|
| 394 | /// to an undefined value. |
---|
| 395 | EdgeIt() { } |
---|
| 396 | /// Copy constructor. |
---|
| 397 | |
---|
| 398 | /// Copy constructor. |
---|
| 399 | /// |
---|
| 400 | EdgeIt(const EdgeIt&) { } |
---|
| 401 | /// Initialize the iterator to be invalid. |
---|
| 402 | |
---|
| 403 | /// Initialize the iterator to be invalid. |
---|
| 404 | /// |
---|
| 405 | EdgeIt(Invalid) { } |
---|
| 406 | /// This constructor sets the iterator to first edge. |
---|
| 407 | |
---|
| 408 | /// This constructor set the iterator to the first edge of |
---|
| 409 | /// node |
---|
| 410 | ///@param g the graph |
---|
| 411 | EdgeIt(const StaticSymGraph& g) { } |
---|
| 412 | /// Edge -> EdgeIt conversion |
---|
| 413 | |
---|
| 414 | /// Sets the iterator to the value of the trivial iterator \c e. |
---|
| 415 | /// This feature necessitates that each time we |
---|
| 416 | /// iterate the edge-set, the iteration order is the same. |
---|
| 417 | EdgeIt(const StaticSymGraph&, const Edge&) { } |
---|
| 418 | ///Next edge |
---|
| 419 | |
---|
| 420 | /// Assign the iterator to the next |
---|
| 421 | /// edge of the corresponding node. |
---|
| 422 | EdgeIt& operator++() { return *this; } |
---|
| 423 | }; |
---|
| 424 | |
---|
| 425 | /// First node of the graph. |
---|
| 426 | |
---|
| 427 | /// \retval i the first node. |
---|
| 428 | /// \return the first node. |
---|
| 429 | /// |
---|
| 430 | NodeIt& first(NodeIt& i) const { return i; } |
---|
| 431 | |
---|
| 432 | /// The first incoming edge. |
---|
| 433 | |
---|
| 434 | /// The first incoming edge. |
---|
| 435 | /// |
---|
| 436 | InEdgeIt& first(InEdgeIt &i, Node) const { return i; } |
---|
| 437 | /// The first outgoing edge. |
---|
| 438 | |
---|
| 439 | /// The first outgoing edge. |
---|
| 440 | /// |
---|
| 441 | OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } |
---|
| 442 | /// The first edge of the Graph. |
---|
| 443 | |
---|
| 444 | /// The first edge of the Graph. |
---|
| 445 | /// |
---|
| 446 | EdgeIt& first(EdgeIt& i) const { return i; } |
---|
| 447 | /// The first symmetric edge of the Graph. |
---|
| 448 | |
---|
| 449 | /// The first symmetric edge of the Graph. |
---|
| 450 | /// |
---|
| 451 | SymEdgeIt& first(SymEdgeIt& i) const { return i; } |
---|
| 452 | |
---|
[986] | 453 | ///Gives back the target node of an edge. |
---|
[959] | 454 | |
---|
[986] | 455 | ///Gives back the target node of an edge. |
---|
[959] | 456 | /// |
---|
[986] | 457 | Node target(Edge) const { return INVALID; } |
---|
| 458 | ///Gives back the source node of an edge. |
---|
[959] | 459 | |
---|
[986] | 460 | ///Gives back the source node of an edge. |
---|
[959] | 461 | /// |
---|
[986] | 462 | Node source(Edge) const { return INVALID; } |
---|
[959] | 463 | |
---|
| 464 | ///Gives back the first node of an symmetric edge. |
---|
| 465 | |
---|
| 466 | ///Gives back the first node of an symmetric edge. |
---|
| 467 | /// |
---|
[986] | 468 | Node target(SymEdge) const { return INVALID; } |
---|
[959] | 469 | ///Gives back the second node of an symmetric edge. |
---|
| 470 | |
---|
| 471 | ///Gives back the second node of an symmetric edge. |
---|
| 472 | /// |
---|
[986] | 473 | Node source(SymEdge) const { return INVALID; } |
---|
[959] | 474 | ///Gives back the \e id of a node. |
---|
| 475 | |
---|
| 476 | ///\warning Not all graph structures provide this feature. |
---|
| 477 | /// |
---|
| 478 | ///\todo Should each graph provide \c id? |
---|
| 479 | int id(const Node&) const { return 0; } |
---|
| 480 | ///Gives back the \e id of an edge. |
---|
| 481 | |
---|
| 482 | ///\warning Not all graph structures provide this feature. |
---|
| 483 | /// |
---|
| 484 | ///\todo Should each graph provide \c id? |
---|
| 485 | int id(const Edge&) const { return 0; } |
---|
| 486 | |
---|
| 487 | ///\warning Not all graph structures provide this feature. |
---|
| 488 | /// |
---|
| 489 | ///\todo Should each graph provide \c id? |
---|
| 490 | int id(const SymEdge&) const { return 0; } |
---|
| 491 | |
---|
| 492 | ///\e |
---|
| 493 | |
---|
| 494 | ///\todo Should it be in the concept? |
---|
| 495 | /// |
---|
| 496 | int nodeNum() const { return 0; } |
---|
| 497 | ///\e |
---|
| 498 | |
---|
| 499 | ///\todo Should it be in the concept? |
---|
| 500 | /// |
---|
| 501 | int edgeNum() const { return 0; } |
---|
| 502 | |
---|
| 503 | ///\todo Should it be in the concept? |
---|
| 504 | /// |
---|
| 505 | int symEdgeNum() const { return 0; } |
---|
| 506 | |
---|
| 507 | |
---|
| 508 | /// Gives back the forward directed edge of the symmetric edge. |
---|
| 509 | Edge forward(SymEdge) const {return INVALID;} |
---|
| 510 | |
---|
| 511 | /// Gives back the backward directed edge of the symmetric edge. |
---|
| 512 | Edge backward(SymEdge) const {return INVALID;}; |
---|
| 513 | |
---|
| 514 | /// Gives back the opposite of the edge. |
---|
| 515 | Edge opposite(Edge) const {return INVALID;} |
---|
| 516 | |
---|
| 517 | ///Reference map of the nodes to type \c T. |
---|
| 518 | /// \ingroup concept |
---|
| 519 | ///Reference map of the nodes to type \c T. |
---|
| 520 | /// \sa Reference |
---|
| 521 | /// \warning Making maps that can handle bool type (NodeMap<bool>) |
---|
| 522 | /// needs some extra attention! |
---|
| 523 | template<class T> class NodeMap : public ReferenceMap< Node, T > |
---|
| 524 | { |
---|
| 525 | public: |
---|
| 526 | |
---|
| 527 | ///\e |
---|
| 528 | NodeMap(const StaticSymGraph&) { } |
---|
| 529 | ///\e |
---|
| 530 | NodeMap(const StaticSymGraph&, T) { } |
---|
| 531 | |
---|
| 532 | ///Copy constructor |
---|
| 533 | template<typename TT> NodeMap(const NodeMap<TT>&) { } |
---|
| 534 | ///Assignment operator |
---|
| 535 | template<typename TT> NodeMap& operator=(const NodeMap<TT>&) |
---|
| 536 | { return *this; } |
---|
| 537 | }; |
---|
| 538 | |
---|
| 539 | ///Reference map of the edges to type \c T. |
---|
| 540 | |
---|
| 541 | /// \ingroup concept |
---|
| 542 | ///Reference map of the edges to type \c T. |
---|
| 543 | /// \sa Reference |
---|
| 544 | /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
---|
| 545 | /// needs some extra attention! |
---|
| 546 | template<class T> class EdgeMap |
---|
| 547 | : public ReferenceMap<Edge,T> |
---|
| 548 | { |
---|
| 549 | public: |
---|
| 550 | |
---|
| 551 | ///\e |
---|
| 552 | EdgeMap(const StaticSymGraph&) { } |
---|
| 553 | ///\e |
---|
| 554 | EdgeMap(const StaticSymGraph&, T) { } |
---|
| 555 | |
---|
| 556 | ///Copy constructor |
---|
| 557 | template<typename TT> EdgeMap(const EdgeMap<TT>&) { } |
---|
| 558 | ///Assignment operator |
---|
| 559 | template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&) |
---|
| 560 | { return *this; } |
---|
| 561 | }; |
---|
| 562 | |
---|
| 563 | ///Reference map of the edges to type \c T. |
---|
| 564 | |
---|
| 565 | /// \ingroup concept |
---|
| 566 | ///Reference map of the symmetric edges to type \c T. |
---|
| 567 | /// \sa Reference |
---|
| 568 | /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
---|
| 569 | /// needs some extra attention! |
---|
| 570 | template<class T> class SymEdgeMap |
---|
| 571 | : public ReferenceMap<SymEdge,T> |
---|
| 572 | { |
---|
| 573 | public: |
---|
| 574 | |
---|
| 575 | ///\e |
---|
| 576 | SymEdgeMap(const StaticSymGraph&) { } |
---|
| 577 | ///\e |
---|
| 578 | SymEdgeMap(const StaticSymGraph&, T) { } |
---|
| 579 | |
---|
| 580 | ///Copy constructor |
---|
| 581 | template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { } |
---|
| 582 | ///Assignment operator |
---|
| 583 | template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&) |
---|
| 584 | { return *this; } |
---|
| 585 | }; |
---|
| 586 | }; |
---|
| 587 | |
---|
| 588 | |
---|
| 589 | |
---|
| 590 | /// An empty non-static graph class. |
---|
| 591 | |
---|
| 592 | /// This class provides everything that \ref StaticGraph |
---|
| 593 | /// with additional functionality which enables to build a |
---|
| 594 | /// graph from scratch. |
---|
| 595 | class ExtendableSymGraph : public StaticSymGraph |
---|
| 596 | { |
---|
| 597 | public: |
---|
| 598 | /// Defalult constructor. |
---|
| 599 | |
---|
| 600 | /// Defalult constructor. |
---|
| 601 | /// |
---|
| 602 | ExtendableSymGraph() { } |
---|
| 603 | ///Add a new node to the graph. |
---|
| 604 | |
---|
| 605 | /// \return the new node. |
---|
| 606 | /// |
---|
| 607 | Node addNode() { return INVALID; } |
---|
| 608 | ///Add a new edge to the graph. |
---|
| 609 | |
---|
[986] | 610 | ///Add a new symmetric edge to the graph with source node \c t |
---|
| 611 | ///and target node \c h. |
---|
[959] | 612 | ///\return the new edge. |
---|
| 613 | SymEdge addEdge(Node h, Node t) { return INVALID; } |
---|
| 614 | |
---|
| 615 | /// Resets the graph. |
---|
| 616 | |
---|
| 617 | /// This function deletes all edges and nodes of the graph. |
---|
| 618 | /// It also frees the memory allocated to store them. |
---|
| 619 | /// \todo It might belong to \ref ErasableGraph. |
---|
| 620 | void clear() { } |
---|
| 621 | }; |
---|
| 622 | |
---|
| 623 | /// An empty erasable graph class. |
---|
| 624 | |
---|
| 625 | /// This class is an extension of \ref ExtendableGraph. It also makes it |
---|
| 626 | /// possible to erase edges or nodes. |
---|
| 627 | class ErasableSymGraph : public ExtendableSymGraph |
---|
| 628 | { |
---|
| 629 | public: |
---|
| 630 | /// Defalult constructor. |
---|
| 631 | |
---|
| 632 | /// Defalult constructor. |
---|
| 633 | /// |
---|
| 634 | ErasableSymGraph() { } |
---|
| 635 | /// Deletes a node. |
---|
| 636 | |
---|
| 637 | /// Deletes node \c n node. |
---|
| 638 | /// |
---|
| 639 | void erase(Node n) { } |
---|
| 640 | /// Deletes an edge. |
---|
| 641 | |
---|
| 642 | /// Deletes edge \c e edge. |
---|
| 643 | /// |
---|
| 644 | void erase(SymEdge e) { } |
---|
| 645 | }; |
---|
| 646 | |
---|
| 647 | // @} |
---|
| 648 | } //namespace concept |
---|
| 649 | } //namespace lemon |
---|
| 650 | |
---|
| 651 | |
---|
| 652 | |
---|
| 653 | #endif // LEMON_CONCEPT_GRAPH_H |
---|