Removed obsolote todo.
2 * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_CONCEPT_GRAPH_H
18 #define LEMON_CONCEPT_GRAPH_H
20 ///\ingroup graph_concepts
22 ///\brief Declaration of Graph.
24 #include <lemon/invalid.h>
25 #include <lemon/concept/maps.h>
26 #include <lemon/concept_check.h>
27 #include <lemon/concept/graph_component.h>
33 /// \addtogroup graph_concepts
36 /**************** The full-featured graph concepts ****************/
39 /// \brief Modular builded static graph class.
41 /// It should be the same as the \c StaticGraph class.
43 : virtual public BaseGraphComponent,
44 public IterableGraphComponent, public MappableGraphComponent {
46 typedef BaseGraphComponent::Node Node;
47 typedef BaseGraphComponent::Edge Edge;
49 template <typename _Graph>
52 checkConcept<IterableGraphComponent, _Graph>();
53 checkConcept<MappableGraphComponent, _Graph>();
58 /// \brief Modular builded extendable graph class.
60 /// It should be the same as the \c ExtendableGraph class.
61 class _ExtendableGraph
62 : virtual public BaseGraphComponent, public _StaticGraph,
63 public ExtendableGraphComponent, public ClearableGraphComponent {
65 typedef BaseGraphComponent::Node Node;
66 typedef BaseGraphComponent::Edge Edge;
68 template <typename _Graph>
71 checkConcept<_StaticGraph, _Graph >();
72 checkConcept<ExtendableGraphComponent, _Graph >();
73 checkConcept<ClearableGraphComponent, _Graph >();
78 /// \brief Modular builded erasable graph class.
80 /// It should be the same as the \c ErasableGraph class.
82 : virtual public BaseGraphComponent, public _ExtendableGraph,
83 public ErasableGraphComponent {
85 typedef BaseGraphComponent::Node Node;
86 typedef BaseGraphComponent::Edge Edge;
88 template <typename _Graph>
91 checkConcept<_ExtendableGraph, _Graph >();
92 checkConcept<ErasableGraphComponent, _Graph >();
97 /// An empty static graph class.
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.
105 /// It can be used for checking the interface compatibility,
106 /// or it can serve as a skeleton of a new graph structure.
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.
113 /// \todo A pages describing the concept of concept description would
118 /// Defalult constructor.
120 /// Defalult constructor.
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) { }
129 /// The base type of node iterators,
130 /// or in other words, the trivial node iterator.
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.
138 /// Default constructor
140 /// @warning The default constructor sets the iterator
141 /// to an undefined value.
143 /// Copy constructor.
145 /// Copy constructor.
147 Node(const Node&) { }
149 /// Invalid constructor \& conversion.
151 /// This constructor initializes the iterator to be invalid.
152 /// \sa Invalid for more details.
154 /// Equality operator
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; }
160 /// Inequality operator
162 /// \sa operator==(Node n)
164 bool operator!=(Node) const { return true; }
168 /// This iterator goes through each node.
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:
175 /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
177 class NodeIt : public Node {
179 /// Default constructor
181 /// @warning The default constructor sets the iterator
182 /// to an undefined value.
184 /// Copy constructor.
186 /// Copy constructor.
188 NodeIt(const NodeIt&) { }
189 /// Invalid constructor \& conversion.
191 /// Initialize the iterator to be invalid.
192 /// \sa Invalid for more details.
194 /// Sets the iterator to the first node.
196 /// Sets the iterator to the first node of \c g.
198 NodeIt(const StaticGraph& g) { }
199 /// Node -> NodeIt conversion.
201 /// Sets the iterator to the node of \c g pointed by the trivial
203 /// This feature necessitates that each time we
204 /// iterate the edge-set, the iteration order is the same.
205 NodeIt(const StaticGraph& g, const Node& n) { }
208 /// Assign the iterator to the next node.
210 NodeIt& operator++() { return *this; }
214 /// The base type of the edge iterators.
216 /// The base type of the edge iterators.
220 /// Default constructor
222 /// @warning The default constructor sets the iterator
223 /// to an undefined value.
225 /// Copy constructor.
227 /// Copy constructor.
229 Edge(const Edge&) { }
230 /// Initialize the iterator to be invalid.
232 /// Initialize the iterator to be invalid.
235 /// Equality operator
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
242 /// \sa operator==(Node n)
244 bool operator!=(Edge) const { return true; }
247 /// This iterator goes trough the outgoing edges of a node.
249 /// This iterator goes trough the \e outgoing edges of a certain node
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.
256 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
259 class OutEdgeIt : public Edge {
261 /// Default constructor
263 /// @warning The default constructor sets the iterator
264 /// to an undefined value.
266 /// Copy constructor.
268 /// Copy constructor.
270 OutEdgeIt(const OutEdgeIt&) { }
271 /// Initialize the iterator to be invalid.
273 /// Initialize the iterator to be invalid.
275 OutEdgeIt(Invalid) { }
276 /// This constructor sets the iterator to first outgoing edge.
278 /// This constructor set the iterator to the first outgoing edge of
281 ///@param g the graph
282 OutEdgeIt(const StaticGraph& g, const Node& n) { }
283 /// Edge -> OutEdgeIt conversion
285 /// Sets the iterator to the value of the trivial iterator \c e.
286 /// This feature necessitates that each time we
287 /// iterate the edge-set, the iteration order is the same.
288 OutEdgeIt(const StaticGraph& g, const Edge& e) { }
289 ///Next outgoing edge
291 /// Assign the iterator to the next
292 /// outgoing edge of the corresponding node.
293 OutEdgeIt& operator++() { return *this; }
296 /// This iterator goes trough the incoming edges of a node.
298 /// This iterator goes trough the \e incoming edges of a certain node
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.
305 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
308 class InEdgeIt : public Edge {
310 /// Default constructor
312 /// @warning The default constructor sets the iterator
313 /// to an undefined value.
315 /// Copy constructor.
317 /// Copy constructor.
319 InEdgeIt(const InEdgeIt&) { }
320 /// Initialize the iterator to be invalid.
322 /// Initialize the iterator to be invalid.
324 InEdgeIt(Invalid) { }
325 /// This constructor sets the iterator to first incoming edge.
327 /// This constructor set the iterator to the first incoming edge of
330 ///@param g the graph
331 InEdgeIt(const StaticGraph& g, const Node& n) { }
332 /// Edge -> InEdgeIt conversion
334 /// Sets the iterator to the value of the trivial iterator \c e.
335 /// This feature necessitates that each time we
336 /// iterate the edge-set, the iteration order is the same.
337 InEdgeIt(const StaticGraph& g, const Edge& n) { }
338 /// Next incoming edge
340 /// Assign the iterator to the next inedge of the corresponding node.
342 InEdgeIt& operator++() { return *this; }
344 /// This iterator goes through each edge.
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:
351 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
353 class EdgeIt : public Edge {
355 /// Default constructor
357 /// @warning The default constructor sets the iterator
358 /// to an undefined value.
360 /// Copy constructor.
362 /// Copy constructor.
364 EdgeIt(const EdgeIt&) { }
365 /// Initialize the iterator to be invalid.
367 /// Initialize the iterator to be invalid.
370 /// This constructor sets the iterator to first edge.
372 /// This constructor set the iterator to the first edge of
374 ///@param g the graph
375 EdgeIt(const StaticGraph& g) { }
376 /// Edge -> EdgeIt conversion
378 /// Sets the iterator to the value of the trivial iterator \c e.
379 /// This feature necessitates that each time we
380 /// iterate the edge-set, the iteration order is the same.
381 EdgeIt(const StaticGraph&, const Edge&) { }
384 /// Assign the iterator to the next
385 /// edge of the corresponding node.
386 EdgeIt& operator++() { return *this; }
388 ///Gives back the target node of an edge.
390 ///Gives back the target node of an edge.
392 Node target(Edge) const { return INVALID; }
393 ///Gives back the source node of an edge.
395 ///Gives back the source node of an edge.
397 Node source(Edge) const { return INVALID; }
398 /// Read write map of the nodes to type \c T.
401 /// ReadWrite map of the nodes to type \c T.
403 /// \warning Making maps that can handle bool type (NodeMap<bool>)
404 /// needs some extra attention!
406 class NodeMap : public ReadWriteMap< Node, T >
411 NodeMap(const StaticGraph&) { }
413 NodeMap(const StaticGraph&, T) { }
416 NodeMap(const NodeMap&) { }
417 ///Assignment operator
418 NodeMap& operator=(const NodeMap&) { return *this; }
419 // \todo fix this concept
422 /// Read write map of the edges to type \c T.
425 ///Reference map of the edges to type \c T.
427 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
428 /// needs some extra attention!
430 class EdgeMap : public ReadWriteMap<Edge,T>
435 EdgeMap(const StaticGraph&) { }
437 EdgeMap(const StaticGraph&, T) { }
439 EdgeMap(const EdgeMap&) { }
440 ///Assignment operator
441 EdgeMap& operator=(const EdgeMap&) { return *this; }
442 // \todo fix this concept
445 template <typename _Graph>
446 struct Constraints : public _StaticGraph::Constraints<_Graph> {};
450 /// An empty non-static graph class.
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
458 /// Defalult constructor.
460 /// Defalult constructor.
462 ExtendableGraph() { }
463 ///Add a new node to the graph.
465 /// \return the new node.
467 Node addNode() { return INVALID; }
468 ///Add a new edge to the graph.
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; }
475 /// Resets the graph.
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.
482 template <typename _Graph>
483 struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
487 /// An empty erasable graph class.
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
494 /// Defalult constructor.
496 /// Defalult constructor.
501 /// Deletes node \c n node.
503 void erase(Node n) { }
506 /// Deletes edge \c e edge.
508 void erase(Edge e) { }
510 template <typename _Graph>
511 struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
516 /************* New GraphBase stuff **************/
519 // /// A minimal GraphBase concept
521 // /// This class describes a minimal concept which can be extended to a
522 // /// full-featured graph with \ref GraphFactory.
528 // /// \bug Should we demand that Node and Edge be subclasses of the
529 // /// Graph class???
531 // typedef GraphItem<'n'> Node;
532 // typedef GraphItem<'e'> Edge;
534 // // class Node : public BaseGraphItem<'n'> {};
535 // // class Edge : public BaseGraphItem<'e'> {};
537 // // Graph operation
538 // void firstNode(Node &n) const { }
539 // void firstEdge(Edge &e) const { }
541 // void firstOutEdge(Edge &e, Node) const { }
542 // void firstInEdge(Edge &e, Node) const { }
544 // void nextNode(Node &n) const { }
545 // void nextEdge(Edge &e) const { }
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 { }
554 // Node target(Edge) const { return Node(); }
555 // Node source(Edge) const { return Node(); }
558 // // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
564 // // We need a special slimer concept which does not provide maps (it
565 // // wouldn't be strictly slimer, cause for map-factory id() & friends
568 // template<typename T>
569 // class NodeMap : public GraphMap<GraphBase, Node, T> {};
571 // template<typename T>
572 // class EdgeMap : public GraphMap<GraphBase, Node, T> {};
576 } //namespace concept
581 #endif // LEMON_CONCEPT_GRAPH_H