Changeset 1136:8d066154b66a in lemon0.x for src/lemon/concept/graph.h
 Timestamp:
 02/07/05 12:28:37 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1535
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/concept/graph.h
r1030 r1136 29 29 namespace lemon { 30 30 namespace concept { 31 31 32 32 33 /// \addtogroup graph_concepts 33 34 /// @{ 34 35 35 // /// An empty static graph class.36 37 // /// This class provides all the common features of a graph structure,38 // /// however completely without implementations and real data structures39 // /// behind the interface.40 // /// All graph algorithms should compile with this class, but it will not41 // /// run properly, of course.42 // ///43 // /// It can be used for checking the interface compatibility,44 // /// or it can serve as a skeleton of a new graph structure.45 // ///46 // /// Also, you will find here the full documentation of a certain graph47 // /// feature, the documentation of a real graph imlementation48 // /// like @ref ListGraph or49 // /// @ref SmartGraph will just refer to this structure.50 // ///51 // /// \todo A pages describing the concept of concept description would52 // /// be nice.53 // class StaticGraph54 // {55 // public:56 // /// Defalult constructor.57 58 // /// Defalult constructor.59 // ///60 // StaticGraph() { }61 // ///Copy consructor.62 63 // // ///\todo It is not clear, what we expect from a copy constructor.64 // // ///E.g. How to assign the nodes/edges to each other? What about maps?65 // // StaticGraph(const StaticGraph& g) { }66 67 // /// The base type of node iterators,68 // /// or in other words, the trivial node iterator.69 70 // /// This is the base type of each node iterator,71 // /// thus each kind of node iterator converts to this.72 // /// More precisely each kind of node iterator should be inherited73 // /// from the trivial node iterator.74 // class Node {75 // public:76 // /// Default constructor77 78 // /// @warning The default constructor sets the iterator79 // /// to an undefined value.80 // Node() { }81 // /// Copy constructor.82 83 // /// Copy constructor.84 // ///85 // Node(const Node&) { }86 87 // /// Invalid constructor \& conversion.88 89 // /// This constructor initializes the iterator to be invalid.90 // /// \sa Invalid for more details.91 // Node(Invalid) { }92 // /// Equality operator93 94 // /// Two iterators are equal if and only if they point to the95 // /// same object or both are invalid.96 // bool operator==(Node) const { return true; }97 98 // /// Inequality operator99 100 // /// \sa operator==(Node n)101 // ///102 // bool operator!=(Node) const { return true; }103 104 // };105 106 // /// This iterator goes through each node.107 108 // /// This iterator goes through each node.109 // /// Its usage is quite simple, for example you can count the number110 // /// of nodes in graph \c g of type \c Graph like this:111 // /// \code112 // /// int count=0;113 // /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;114 // /// \endcode115 // class NodeIt : public Node {116 // public:117 // /// Default constructor118 119 // /// @warning The default constructor sets the iterator120 // /// to an undefined value.121 // NodeIt() { }122 // /// Copy constructor.123 124 // /// Copy constructor.125 // ///126 // NodeIt(const NodeIt&) { }127 // /// Invalid constructor \& conversion.128 129 // /// Initialize the iterator to be invalid.130 // /// \sa Invalid for more details.131 // NodeIt(Invalid) { }132 // /// Sets the iterator to the first node.133 134 // /// Sets the iterator to the first node of \c g.135 // ///136 // NodeIt(const StaticGraph& g) { }137 // /// Node > NodeIt conversion.138 139 // /// Sets the iterator to the node of \c g pointed by the trivial140 // /// iterator n.141 // /// This feature necessitates that each time we142 // /// iterate the edgeset, the iteration order is the same.143 // NodeIt(const StaticGraph& g, const Node& n) { }144 // /// Next node.145 146 // /// Assign the iterator to the next node.147 // ///148 // NodeIt& operator++() { return *this; }149 // };150 151 152 // /// The base type of the edge iterators.153 154 // /// The base type of the edge iterators.155 // ///156 // class Edge {157 // public:158 // /// Default constructor159 160 // /// @warning The default constructor sets the iterator161 // /// to an undefined value.162 // Edge() { }163 // /// Copy constructor.164 165 // /// Copy constructor.166 // ///167 // Edge(const Edge&) { }168 // /// Initialize the iterator to be invalid.169 170 // /// Initialize the iterator to be invalid.171 // ///172 // Edge(Invalid) { }173 // /// Equality operator174 175 // /// Two iterators are equal if and only if they point to the176 // /// same object or both are invalid.177 // bool operator==(Edge) const { return true; }178 // /// Inequality operator179 180 // /// \sa operator==(Node n)181 // ///182 // bool operator!=(Edge) const { return true; }183 // };184 185 // /// This iterator goes trough the outgoing edges of a node.186 187 // /// This iterator goes trough the \e outgoing edges of a certain node188 // /// of a graph.189 // /// Its usage is quite simple, for example you can count the number190 // /// of outgoing edges of a node \c n191 // /// in graph \c g of type \c Graph as follows.192 // /// \code193 // /// int count=0;194 // /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;195 // /// \endcode196 197 // class OutEdgeIt : public Edge {198 // public:199 // /// Default constructor200 201 // /// @warning The default constructor sets the iterator202 // /// to an undefined value.203 // OutEdgeIt() { }204 // /// Copy constructor.205 206 // /// Copy constructor.207 // ///208 // OutEdgeIt(const OutEdgeIt&) { }209 // /// Initialize the iterator to be invalid.210 211 // /// Initialize the iterator to be invalid.212 // ///213 // OutEdgeIt(Invalid) { }214 // /// This constructor sets the iterator to first outgoing edge.215 216 // /// This constructor set the iterator to the first outgoing edge of217 // /// node218 // ///@param n the node219 // ///@param g the graph220 // OutEdgeIt(const StaticGraph& g, const Node& n) { }221 // /// Edge > OutEdgeIt conversion222 223 // /// Sets the iterator to the value of the trivial iterator \c e.224 // /// This feature necessitates that each time we225 // /// iterate the edgeset, the iteration order is the same.226 // OutEdgeIt(const StaticGraph& g, const Edge& e) { }227 // ///Next outgoing edge228 229 // /// Assign the iterator to the next230 // /// outgoing edge of the corresponding node.231 // OutEdgeIt& operator++() { return *this; }232 // };233 234 // /// This iterator goes trough the incoming edges of a node.235 236 // /// This iterator goes trough the \e incoming edges of a certain node237 // /// of a graph.238 // /// Its usage is quite simple, for example you can count the number239 // /// of outgoing edges of a node \c n240 // /// in graph \c g of type \c Graph as follows.241 // /// \code242 // /// int count=0;243 // /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;244 // /// \endcode245 246 // class InEdgeIt : public Edge {247 // public:248 // /// Default constructor249 250 // /// @warning The default constructor sets the iterator251 // /// to an undefined value.252 // InEdgeIt() { }253 // /// Copy constructor.254 255 // /// Copy constructor.256 // ///257 // InEdgeIt(const InEdgeIt&) { }258 // /// Initialize the iterator to be invalid.259 260 // /// Initialize the iterator to be invalid.261 // ///262 // InEdgeIt(Invalid) { }263 // /// This constructor sets the iterator to first incoming edge.264 265 // /// This constructor set the iterator to the first incoming edge of266 // /// node267 // ///@param n the node268 // ///@param g the graph269 // InEdgeIt(const StaticGraph& g, const Node& n) { }270 // /// Edge > InEdgeIt conversion271 272 // /// Sets the iterator to the value of the trivial iterator \c e.273 // /// This feature necessitates that each time we274 // /// iterate the edgeset, the iteration order is the same.275 // InEdgeIt(const StaticGraph& g, const Edge& n) { }276 // /// Next incoming edge277 278 // /// Assign the iterator to the next inedge of the corresponding node.279 // ///280 // InEdgeIt& operator++() { return *this; }281 // };282 // /// This iterator goes through each edge.283 284 // /// This iterator goes through each edge of a graph.285 // /// Its usage is quite simple, for example you can count the number286 // /// of edges in a graph \c g of type \c Graph as follows:287 // /// \code288 // /// int count=0;289 // /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;290 // /// \endcode291 // class EdgeIt : public Edge {292 // public:293 // /// Default constructor294 295 // /// @warning The default constructor sets the iterator296 // /// to an undefined value.297 // EdgeIt() { }298 // /// Copy constructor.299 300 // /// Copy constructor.301 // ///302 // EdgeIt(const EdgeIt&) { }303 // /// Initialize the iterator to be invalid.304 305 // /// Initialize the iterator to be invalid.306 // ///307 // EdgeIt(Invalid) { }308 // /// This constructor sets the iterator to first edge.309 310 // /// This constructor set the iterator to the first edge of311 // /// node312 // ///@param g the graph313 // EdgeIt(const StaticGraph& g) { }314 // /// Edge > EdgeIt conversion315 316 // /// Sets the iterator to the value of the trivial iterator \c e.317 // /// This feature necessitates that each time we318 // /// iterate the edgeset, the iteration order is the same.319 // EdgeIt(const StaticGraph&, const Edge&) { }320 // ///Next edge321 322 // /// Assign the iterator to the next323 // /// edge of the corresponding node.324 // EdgeIt& operator++() { return *this; }325 // };326 // ///Gives back the target node of an edge.327 328 // ///Gives back the target node of an edge.329 // ///330 // Node target(Edge) const { return INVALID; }331 // ///Gives back the source node of an edge.332 333 // ///Gives back the source node of an edge.334 // ///335 // Node source(Edge) const { return INVALID; }336 // /// Read write map of the nodes to type \c T.337 338 // /// \ingroup concept339 // /// ReadWrite map of the nodes to type \c T.340 // /// \sa Reference341 // /// \warning Making maps that can handle bool type (NodeMap<bool>)342 // /// needs some extra attention!343 // template<class T>344 // class NodeMap : public ReadWriteMap< Node, T >345 // {346 // public:347 348 // ///\e349 // NodeMap(const StaticGraph&) { }350 // ///\e351 // NodeMap(const StaticGraph&, T) { }352 353 // ///Copy constructor354 // NodeMap(const NodeMap&) { }355 // ///Assignment operator356 // NodeMap& operator=(const NodeMap&) { return *this; }357 // // \todo fix this concept358 // };359 360 // /// Read write map of the edges to type \c T.361 362 // /// \ingroup concept363 // ///Reference map of the edges to type \c T.364 // /// \sa Reference365 // /// \warning Making maps that can handle bool type (EdgeMap<bool>)366 // /// needs some extra attention!367 // template<class T>368 // class EdgeMap : public ReadWriteMap<Edge,T>369 // {370 // public:371 372 // ///\e373 // EdgeMap(const StaticGraph&) { }374 // ///\e375 // EdgeMap(const StaticGraph&, T) { }376 // ///Copy constructor377 // EdgeMap(const EdgeMap&) { }378 // ///Assignment operator379 // EdgeMap& operator=(const EdgeMap&) { return *this; }380 // // \todo fix this concept381 // };382 // };383 384 // /// An empty nonstatic graph class.385 386 // /// This class provides everything that \ref StaticGraph387 // /// with additional functionality which enables to build a388 // /// graph from scratch.389 // class ExtendableGraph : public StaticGraph390 // {391 // public:392 // /// Defalult constructor.393 394 // /// Defalult constructor.395 // ///396 // ExtendableGraph() { }397 // ///Add a new node to the graph.398 399 // /// \return the new node.400 // ///401 // Node addNode() { return INVALID; }402 // ///Add a new edge to the graph.403 404 // ///Add a new edge to the graph with source node \c s405 // ///and target node \c t.406 // ///\return the new edge.407 // Edge addEdge(Node s, Node t) { return INVALID; }408 409 // /// Resets the graph.410 411 // /// This function deletes all edges and nodes of the graph.412 // /// It also frees the memory allocated to store them.413 // /// \todo It might belong to \ref ErasableGraph.414 // void clear() { }415 // };416 417 // /// An empty erasable graph class.418 419 // /// This class is an extension of \ref ExtendableGraph. It also makes it420 // /// possible to erase edges or nodes.421 // class ErasableGraph : public ExtendableGraph422 // {423 // public:424 // /// Defalult constructor.425 426 // /// Defalult constructor.427 // ///428 // ErasableGraph() { }429 // /// Deletes a node.430 431 // /// Deletes node \c n node.432 // ///433 // void erase(Node n) { }434 // /// Deletes an edge.435 436 // /// Deletes edge \c e edge.437 // ///438 // void erase(Edge e) { }439 // };440 441 442 /************* New GraphBase stuff **************/443 444 445 /// A minimal GraphBase concept446 447 /// This class describes a minimal concept which can be extended to a448 /// fullfeatured graph with \ref GraphFactory.449 class GraphBase {450 public:451 452 GraphBase() {}453 454 /// \bug Should we demand that Node and Edge be subclasses of the455 /// Graph class???456 457 typedef GraphItem<'n'> Node;458 typedef GraphItem<'e'> Edge;459 460 // class Node : public BaseGraphItem<'n'> {};461 // class Edge : public BaseGraphItem<'e'> {};462 463 // Graph operation464 void firstNode(Node &n) const { }465 void firstEdge(Edge &e) const { }466 467 void firstOutEdge(Edge &e, Node) const { }468 void firstInEdge(Edge &e, Node) const { }469 470 void nextNode(Node &n) const { }471 void nextEdge(Edge &e) const { }472 473 474 // Question: isn't it reasonable if this methods have a Node475 // parameter? Like this:476 // Edge& nextOut(Edge &e, Node) const { return e; }477 void nextOutEdge(Edge &e) const { }478 void nextInEdge(Edge &e) const { }479 480 Node target(Edge) const { return Node(); }481 Node source(Edge) const { return Node(); }482 483 484 // Do we need id, nodeNum, edgeNum and co. in this basic graphbase485 // concept?486 487 488 // Maps.489 //490 // We need a special slimer concept which does not provide maps (it491 // wouldn't be strictly slimer, cause for mapfactory id() & friends492 // a required...)493 494 template<typename T>495 class NodeMap : public GraphMap<GraphBase, Node, T> {};496 497 template<typename T>498 class EdgeMap : public GraphMap<GraphBase, Node, T> {};499 };500 501 502 503 504 36 /**************** The fullfeatured graph concepts ****************/ 505 37 506 507 class StaticGraph 38 39 /// \brief Modular builded static graph class. 40 /// 41 /// It should be the same as the \c StaticGraph class. 42 class _StaticGraph 508 43 : virtual public BaseGraphComponent, 509 44 public IterableGraphComponent, public MappableGraphComponent { … … 521 56 }; 522 57 523 class ExtendableGraph 524 : virtual public BaseGraphComponent, public StaticGraph, 58 /// \brief Modular builded extendable graph class. 59 /// 60 /// It should be the same as the \c ExtendableGraph class. 61 class _ExtendableGraph 62 : virtual public BaseGraphComponent, public _StaticGraph, 525 63 public ExtendableGraphComponent, public ClearableGraphComponent { 526 64 public: … … 531 69 struct Constraints { 532 70 void constraints() { 533 checkConcept< StaticGraph, _Graph >();71 checkConcept<_StaticGraph, _Graph >(); 534 72 checkConcept<ExtendableGraphComponent, _Graph >(); 535 73 checkConcept<ClearableGraphComponent, _Graph >(); … … 538 76 }; 539 77 540 class ErasableGraph 541 : virtual public BaseGraphComponent, public ExtendableGraph, 78 /// \brief Modular builded erasable graph class. 79 /// 80 /// It should be the same as the \c ErasableGraph class. 81 class _ErasableGraph 82 : virtual public BaseGraphComponent, public _ExtendableGraph, 542 83 public ErasableGraphComponent { 543 84 public: … … 548 89 struct Constraints { 549 90 void constraints() { 550 checkConcept< ExtendableGraph, _Graph >();91 checkConcept<_ExtendableGraph, _Graph >(); 551 92 checkConcept<ErasableGraphComponent, _Graph >(); 552 93 } 553 94 }; 554 95 }; 96 97 /// An empty static graph class. 98 99 /// This class provides all the common features of a graph structure, 100 /// however completely without implementations and real data structures 101 /// behind the interface. 102 /// All graph algorithms should compile with this class, but it will not 103 /// run properly, of course. 104 /// 105 /// It can be used for checking the interface compatibility, 106 /// or it can serve as a skeleton of a new graph structure. 107 /// 108 /// Also, you will find here the full documentation of a certain graph 109 /// feature, the documentation of a real graph imlementation 110 /// like @ref ListGraph or 111 /// @ref SmartGraph will just refer to this structure. 112 /// 113 /// \todo A pages describing the concept of concept description would 114 /// be nice. 115 class StaticGraph 116 { 117 public: 118 /// Defalult constructor. 119 120 /// Defalult constructor. 121 /// 122 StaticGraph() { } 123 ///Copy consructor. 124 125 // ///\todo It is not clear, what we expect from a copy constructor. 126 // ///E.g. How to assign the nodes/edges to each other? What about maps? 127 // StaticGraph(const StaticGraph& g) { } 128 129 /// The base type of node iterators, 130 /// or in other words, the trivial node iterator. 131 132 /// This is the base type of each node iterator, 133 /// thus each kind of node iterator converts to this. 134 /// More precisely each kind of node iterator should be inherited 135 /// from the trivial node iterator. 136 class Node { 137 public: 138 /// Default constructor 139 140 /// @warning The default constructor sets the iterator 141 /// to an undefined value. 142 Node() { } 143 /// Copy constructor. 144 145 /// Copy constructor. 146 /// 147 Node(const Node&) { } 148 149 /// Invalid constructor \& conversion. 150 151 /// This constructor initializes the iterator to be invalid. 152 /// \sa Invalid for more details. 153 Node(Invalid) { } 154 /// Equality operator 155 156 /// Two iterators are equal if and only if they point to the 157 /// same object or both are invalid. 158 bool operator==(Node) const { return true; } 159 160 /// Inequality operator 161 162 /// \sa operator==(Node n) 163 /// 164 bool operator!=(Node) const { return true; } 165 166 }; 167 168 /// This iterator goes through each node. 169 170 /// This iterator goes through each node. 171 /// Its usage is quite simple, for example you can count the number 172 /// of nodes in graph \c g of type \c Graph like this: 173 /// \code 174 /// int count=0; 175 /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; 176 /// \endcode 177 class NodeIt : public Node { 178 public: 179 /// Default constructor 180 181 /// @warning The default constructor sets the iterator 182 /// to an undefined value. 183 NodeIt() { } 184 /// Copy constructor. 185 186 /// Copy constructor. 187 /// 188 NodeIt(const NodeIt&) { } 189 /// Invalid constructor \& conversion. 190 191 /// Initialize the iterator to be invalid. 192 /// \sa Invalid for more details. 193 NodeIt(Invalid) { } 194 /// Sets the iterator to the first node. 195 196 /// Sets the iterator to the first node of \c g. 197 /// 198 NodeIt(const StaticGraph& g) { } 199 /// Node > NodeIt conversion. 200 201 /// Sets the iterator to the node of \c g pointed by the trivial 202 /// iterator n. 203 /// This feature necessitates that each time we 204 /// iterate the edgeset, the iteration order is the same. 205 NodeIt(const StaticGraph& g, const Node& n) { } 206 /// Next node. 207 208 /// Assign the iterator to the next node. 209 /// 210 NodeIt& operator++() { return *this; } 211 }; 212 213 214 /// The base type of the edge iterators. 215 216 /// The base type of the edge iterators. 217 /// 218 class Edge { 219 public: 220 /// Default constructor 221 222 /// @warning The default constructor sets the iterator 223 /// to an undefined value. 224 Edge() { } 225 /// Copy constructor. 226 227 /// Copy constructor. 228 /// 229 Edge(const Edge&) { } 230 /// Initialize the iterator to be invalid. 231 232 /// Initialize the iterator to be invalid. 233 /// 234 Edge(Invalid) { } 235 /// Equality operator 236 237 /// Two iterators are equal if and only if they point to the 238 /// same object or both are invalid. 239 bool operator==(Edge) const { return true; } 240 /// Inequality operator 241 242 /// \sa operator==(Node n) 243 /// 244 bool operator!=(Edge) const { return true; } 245 }; 246 247 /// This iterator goes trough the outgoing edges of a node. 248 249 /// This iterator goes trough the \e outgoing edges of a certain node 250 /// of a graph. 251 /// Its usage is quite simple, for example you can count the number 252 /// of outgoing edges of a node \c n 253 /// in graph \c g of type \c Graph as follows. 254 /// \code 255 /// int count=0; 256 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; 257 /// \endcode 258 259 class OutEdgeIt : public Edge { 260 public: 261 /// Default constructor 262 263 /// @warning The default constructor sets the iterator 264 /// to an undefined value. 265 OutEdgeIt() { } 266 /// Copy constructor. 267 268 /// Copy constructor. 269 /// 270 OutEdgeIt(const OutEdgeIt&) { } 271 /// Initialize the iterator to be invalid. 272 273 /// Initialize the iterator to be invalid. 274 /// 275 OutEdgeIt(Invalid) { } 276 /// This constructor sets the iterator to first outgoing edge. 277 278 /// This constructor set the iterator to the first outgoing edge of 279 /// node 280 ///@param n the node 281 ///@param g the graph 282 OutEdgeIt(const StaticGraph& g, const Node& n) { } 283 /// Edge > OutEdgeIt conversion 284 285 /// Sets the iterator to the value of the trivial iterator \c e. 286 /// This feature necessitates that each time we 287 /// iterate the edgeset, the iteration order is the same. 288 OutEdgeIt(const StaticGraph& g, const Edge& e) { } 289 ///Next outgoing edge 290 291 /// Assign the iterator to the next 292 /// outgoing edge of the corresponding node. 293 OutEdgeIt& operator++() { return *this; } 294 }; 295 296 /// This iterator goes trough the incoming edges of a node. 297 298 /// This iterator goes trough the \e incoming edges of a certain node 299 /// of a graph. 300 /// Its usage is quite simple, for example you can count the number 301 /// of outgoing edges of a node \c n 302 /// in graph \c g of type \c Graph as follows. 303 /// \code 304 /// int count=0; 305 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; 306 /// \endcode 307 308 class InEdgeIt : public Edge { 309 public: 310 /// Default constructor 311 312 /// @warning The default constructor sets the iterator 313 /// to an undefined value. 314 InEdgeIt() { } 315 /// Copy constructor. 316 317 /// Copy constructor. 318 /// 319 InEdgeIt(const InEdgeIt&) { } 320 /// Initialize the iterator to be invalid. 321 322 /// Initialize the iterator to be invalid. 323 /// 324 InEdgeIt(Invalid) { } 325 /// This constructor sets the iterator to first incoming edge. 326 327 /// This constructor set the iterator to the first incoming edge of 328 /// node 329 ///@param n the node 330 ///@param g the graph 331 InEdgeIt(const StaticGraph& g, const Node& n) { } 332 /// Edge > InEdgeIt conversion 333 334 /// Sets the iterator to the value of the trivial iterator \c e. 335 /// This feature necessitates that each time we 336 /// iterate the edgeset, the iteration order is the same. 337 InEdgeIt(const StaticGraph& g, const Edge& n) { } 338 /// Next incoming edge 339 340 /// Assign the iterator to the next inedge of the corresponding node. 341 /// 342 InEdgeIt& operator++() { return *this; } 343 }; 344 /// This iterator goes through each edge. 345 346 /// This iterator goes through each edge of a graph. 347 /// Its usage is quite simple, for example you can count the number 348 /// of edges in a graph \c g of type \c Graph as follows: 349 /// \code 350 /// int count=0; 351 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; 352 /// \endcode 353 class EdgeIt : public Edge { 354 public: 355 /// Default constructor 356 357 /// @warning The default constructor sets the iterator 358 /// to an undefined value. 359 EdgeIt() { } 360 /// Copy constructor. 361 362 /// Copy constructor. 363 /// 364 EdgeIt(const EdgeIt&) { } 365 /// Initialize the iterator to be invalid. 366 367 /// Initialize the iterator to be invalid. 368 /// 369 EdgeIt(Invalid) { } 370 /// This constructor sets the iterator to first edge. 371 372 /// This constructor set the iterator to the first edge of 373 /// node 374 ///@param g the graph 375 EdgeIt(const StaticGraph& g) { } 376 /// Edge > EdgeIt conversion 377 378 /// Sets the iterator to the value of the trivial iterator \c e. 379 /// This feature necessitates that each time we 380 /// iterate the edgeset, the iteration order is the same. 381 EdgeIt(const StaticGraph&, const Edge&) { } 382 ///Next edge 383 384 /// Assign the iterator to the next 385 /// edge of the corresponding node. 386 EdgeIt& operator++() { return *this; } 387 }; 388 ///Gives back the target node of an edge. 389 390 ///Gives back the target node of an edge. 391 /// 392 Node target(Edge) const { return INVALID; } 393 ///Gives back the source node of an edge. 394 395 ///Gives back the source node of an edge. 396 /// 397 Node source(Edge) const { return INVALID; } 398 /// Read write map of the nodes to type \c T. 399 400 /// \ingroup concept 401 /// ReadWrite map of the nodes to type \c T. 402 /// \sa Reference 403 /// \warning Making maps that can handle bool type (NodeMap<bool>) 404 /// needs some extra attention! 405 template<class T> 406 class NodeMap : public ReadWriteMap< Node, T > 407 { 408 public: 409 410 ///\e 411 NodeMap(const StaticGraph&) { } 412 ///\e 413 NodeMap(const StaticGraph&, T) { } 414 415 ///Copy constructor 416 NodeMap(const NodeMap&) { } 417 ///Assignment operator 418 NodeMap& operator=(const NodeMap&) { return *this; } 419 // \todo fix this concept 420 }; 421 422 /// Read write map of the edges to type \c T. 423 424 /// \ingroup concept 425 ///Reference map of the edges to type \c T. 426 /// \sa Reference 427 /// \warning Making maps that can handle bool type (EdgeMap<bool>) 428 /// needs some extra attention! 429 template<class T> 430 class EdgeMap : public ReadWriteMap<Edge,T> 431 { 432 public: 433 434 ///\e 435 EdgeMap(const StaticGraph&) { } 436 ///\e 437 EdgeMap(const StaticGraph&, T) { } 438 ///Copy constructor 439 EdgeMap(const EdgeMap&) { } 440 ///Assignment operator 441 EdgeMap& operator=(const EdgeMap&) { return *this; } 442 // \todo fix this concept 443 }; 444 445 template <typename _Graph> 446 struct Constraints : public _StaticGraph::Constraints<_Graph> {}; 447 448 }; 449 450 /// An empty nonstatic graph class. 451 452 /// This class provides everything that \ref StaticGraph 453 /// with additional functionality which enables to build a 454 /// graph from scratch. 455 class ExtendableGraph : public StaticGraph 456 { 457 public: 458 /// Defalult constructor. 459 460 /// Defalult constructor. 461 /// 462 ExtendableGraph() { } 463 ///Add a new node to the graph. 464 465 /// \return the new node. 466 /// 467 Node addNode() { return INVALID; } 468 ///Add a new edge to the graph. 469 470 ///Add a new edge to the graph with source node \c s 471 ///and target node \c t. 472 ///\return the new edge. 473 Edge addEdge(Node s, Node t) { return INVALID; } 474 475 /// Resets the graph. 476 477 /// This function deletes all edges and nodes of the graph. 478 /// It also frees the memory allocated to store them. 479 /// \todo It might belong to \ref ErasableGraph. 480 void clear() { } 481 482 template <typename _Graph> 483 struct Constraints : public _ExtendableGraph::Constraints<_Graph> {}; 484 485 }; 486 487 /// An empty erasable graph class. 488 489 /// This class is an extension of \ref ExtendableGraph. It also makes it 490 /// possible to erase edges or nodes. 491 class ErasableGraph : public ExtendableGraph 492 { 493 public: 494 /// Defalult constructor. 495 496 /// Defalult constructor. 497 /// 498 ErasableGraph() { } 499 /// Deletes a node. 500 501 /// Deletes node \c n node. 502 /// 503 void erase(Node n) { } 504 /// Deletes an edge. 505 506 /// Deletes edge \c e edge. 507 /// 508 void erase(Edge e) { } 509 510 template <typename _Graph> 511 struct Constraints : public _ErasableGraph::Constraints<_Graph> {}; 512 513 }; 514 515 516 /************* New GraphBase stuff **************/ 517 518 519 // /// A minimal GraphBase concept 520 521 // /// This class describes a minimal concept which can be extended to a 522 // /// fullfeatured graph with \ref GraphFactory. 523 // class GraphBase { 524 // public: 525 526 // GraphBase() {} 527 528 // /// \bug Should we demand that Node and Edge be subclasses of the 529 // /// Graph class??? 530 531 // typedef GraphItem<'n'> Node; 532 // typedef GraphItem<'e'> Edge; 533 534 // // class Node : public BaseGraphItem<'n'> {}; 535 // // class Edge : public BaseGraphItem<'e'> {}; 536 537 // // Graph operation 538 // void firstNode(Node &n) const { } 539 // void firstEdge(Edge &e) const { } 540 541 // void firstOutEdge(Edge &e, Node) const { } 542 // void firstInEdge(Edge &e, Node) const { } 543 544 // void nextNode(Node &n) const { } 545 // void nextEdge(Edge &e) const { } 546 547 548 // // Question: isn't it reasonable if this methods have a Node 549 // // parameter? Like this: 550 // // Edge& nextOut(Edge &e, Node) const { return e; } 551 // void nextOutEdge(Edge &e) const { } 552 // void nextInEdge(Edge &e) const { } 553 554 // Node target(Edge) const { return Node(); } 555 // Node source(Edge) const { return Node(); } 556 557 558 // // Do we need id, nodeNum, edgeNum and co. in this basic graphbase 559 // // concept? 560 561 562 // // Maps. 563 // // 564 // // We need a special slimer concept which does not provide maps (it 565 // // wouldn't be strictly slimer, cause for mapfactory id() & friends 566 // // a required...) 567 568 // template<typename T> 569 // class NodeMap : public GraphMap<GraphBase, Node, T> {}; 570 571 // template<typename T> 572 // class EdgeMap : public GraphMap<GraphBase, Node, T> {}; 573 // }; 555 574 556 575 // @}
Note: See TracChangeset
for help on using the changeset viewer.