2 #ifndef HUGO_SKELETON_GRAPH_H
3 #define HUGO_SKELETON_GRAPH_H
7 ///\brief Declaration of Graph.
9 #include <hugo/invalid.h>
10 #include <hugo/skeletons/maps.h>
12 /// The namespace of HugoLib
16 /// \addtogroup skeletons
19 /// An empty static graph class.
21 /// This class provides all the common features of a graph structure,
22 /// however completely without implementations and real data structures
23 /// behind the interface.
24 /// All graph algorithms should compile with this class, but it will not
25 /// run properly, of course.
27 /// It can be used for checking the interface compatibility,
28 /// or it can serve as a skeleton of a new graph structure.
30 /// Also, you will find here the full documentation of a certain graph
31 /// feature, the documentation of a real graph imlementation
32 /// like @ref ListGraph or
33 /// @ref SmartGraph will just refer to this structure.
37 /// Defalult constructor.
39 /// Defalult constructor.
44 // ///\todo It is not clear, what we expect from a copy constructor.
45 // ///E.g. How to assign the nodes/edges to each other? What about maps?
46 // StaticGraph(const StaticGraph& g) { }
48 /// The base type of node iterators,
49 /// or in other words, the trivial node iterator.
51 /// This is the base type of each node iterator,
52 /// thus each kind of node iterator converts to this.
53 /// More precisely each kind of node iterator should be inherited
54 /// from the trivial node iterator.
57 /// Default constructor
59 /// @warning The default constructor sets the iterator
60 /// to an undefined value.
68 /// Invalid constructor \& conversion.
70 /// This constructor initializes the iterator to be invalid.
71 /// \sa Invalid for more details.
75 /// Two iterators are equal if and only if they point to the
76 /// same object or both are invalid.
77 bool operator==(Node) const { return true; }
79 /// Inequality operator
81 /// \sa \ref operator==(Node n)
83 bool operator!=(Node) const { return true; }
85 ///Comparison operator.
87 ///This is a strict ordering between the nodes.
89 ///This ordering can be different from the order in which NodeIt
90 ///goes through the nodes.
91 ///\todo Possibly we don't need it.
92 bool operator<(Node) const { return true; }
95 /// This iterator goes through each node.
97 /// This iterator goes through each node.
98 /// Its usage is quite simple, for example you can count the number
99 /// of nodes in graph \c g of type \c Graph like this:
102 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
104 class NodeIt : public Node {
106 /// Default constructor
108 /// @warning The default constructor sets the iterator
109 /// to an undefined value.
111 /// Copy constructor.
113 /// Copy constructor.
115 NodeIt(const NodeIt&) { }
116 /// Invalid constructor \& conversion.
118 /// Initialize the iterator to be invalid.
119 /// \sa Invalid for more details.
121 /// Sets the iterator to the first node.
123 /// Sets the iterator to the first node of \c g.
125 NodeIt(const StaticGraph& g) { }
126 /// Node -> NodeIt conversion.
128 /// Sets the iterator to the node of \c g pointed by the trivial
130 /// This feature necessitates that each time we
131 /// iterate the edge-set, the iteration order is the same.
132 NodeIt(const StaticGraph& g, const Node& n) { }
135 /// Assign the iterator to the next node.
137 NodeIt& operator++() { return *this; }
141 /// The base type of the edge iterators.
143 /// The base type of the edge iterators.
147 /// Default constructor
149 /// @warning The default constructor sets the iterator
150 /// to an undefined value.
152 /// Copy constructor.
154 /// Copy constructor.
156 Edge(const Edge&) { }
157 /// Initialize the iterator to be invalid.
159 /// Initialize the iterator to be invalid.
162 /// Equality operator
164 /// Two iterators are equal if and only if they point to the
165 /// same object or both are invalid.
166 bool operator==(Edge) const { return true; }
167 /// Inequality operator
169 /// \sa \ref operator==(Node n)
171 bool operator!=(Edge) const { return true; }
172 ///Comparison operator.
174 ///This is a strict ordering between the nodes.
176 ///This ordering can be different from the order in which NodeIt
177 ///goes through the nodes.
178 ///\todo Possibly we don't need it.
179 bool operator<(Edge) const { return true; }
182 /// This iterator goes trough the outgoing edges of a node.
184 /// This iterator goes trough the \e outgoing edges of a certain node
186 /// Its usage is quite simple, for example you can count the number
187 /// of outgoing edges of a node \c n
188 /// in graph \c g of type \c Graph as follows.
191 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
194 class OutEdgeIt : public Edge {
196 /// Default constructor
198 /// @warning The default constructor sets the iterator
199 /// to an undefined value.
201 /// Copy constructor.
203 /// Copy constructor.
205 OutEdgeIt(const OutEdgeIt&) { }
206 /// Initialize the iterator to be invalid.
208 /// Initialize the iterator to be invalid.
210 OutEdgeIt(Invalid) { }
211 /// This constructor sets the iterator to first outgoing edge.
213 /// This constructor set the iterator to the first outgoing edge of
216 ///@param g the graph
217 OutEdgeIt(const StaticGraph& g, const Node& n) { }
218 /// Edge -> OutEdgeIt conversion
220 /// Sets the iterator to the value of the trivial iterator \c e.
221 /// This feature necessitates that each time we
222 /// iterate the edge-set, the iteration order is the same.
223 OutEdgeIt(const StaticGraph& g, const Edge& e) { }
224 ///Next outgoing edge
226 /// Assign the iterator to the next
227 /// outgoing edge of the corresponding node.
228 OutEdgeIt& operator++() { return *this; }
231 /// This iterator goes trough the incoming edges of a node.
233 /// This iterator goes trough the \e incoming edges of a certain node
235 /// Its usage is quite simple, for example you can count the number
236 /// of outgoing edges of a node \c n
237 /// in graph \c g of type \c Graph as follows.
240 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
243 class InEdgeIt : public Edge {
245 /// Default constructor
247 /// @warning The default constructor sets the iterator
248 /// to an undefined value.
250 /// Copy constructor.
252 /// Copy constructor.
254 InEdgeIt(const InEdgeIt&) { }
255 /// Initialize the iterator to be invalid.
257 /// Initialize the iterator to be invalid.
259 InEdgeIt(Invalid) { }
260 /// This constructor sets the iterator to first incoming edge.
262 /// This constructor set the iterator to the first incoming edge of
265 ///@param g the graph
266 InEdgeIt(const StaticGraph& g, const Node& n) { }
267 /// Edge -> InEdgeIt conversion
269 /// Sets the iterator to the value of the trivial iterator \c e.
270 /// This feature necessitates that each time we
271 /// iterate the edge-set, the iteration order is the same.
272 InEdgeIt(const StaticGraph& g, const Edge& n) { }
273 /// Next incoming edge
275 /// Assign the iterator to the next inedge of the corresponding node.
277 InEdgeIt& operator++() { return *this; }
279 /// This iterator goes through each edge.
281 /// This iterator goes through each edge of a graph.
282 /// Its usage is quite simple, for example you can count the number
283 /// of edges in a graph \c g of type \c Graph as follows:
286 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
288 class EdgeIt : public Edge {
290 /// Default constructor
292 /// @warning The default constructor sets the iterator
293 /// to an undefined value.
295 /// Copy constructor.
297 /// Copy constructor.
299 EdgeIt(const EdgeIt&) { }
300 /// Initialize the iterator to be invalid.
302 /// Initialize the iterator to be invalid.
305 /// This constructor sets the iterator to first edge.
307 /// This constructor set the iterator to the first edge of
309 ///@param g the graph
310 EdgeIt(const StaticGraph& g) { }
311 /// Edge -> EdgeIt conversion
313 /// Sets the iterator to the value of the trivial iterator \c e.
314 /// This feature necessitates that each time we
315 /// iterate the edge-set, the iteration order is the same.
316 EdgeIt(const StaticGraph&, const Edge&) { }
319 /// Assign the iterator to the next
320 /// edge of the corresponding node.
321 EdgeIt& operator++() { return *this; }
324 /// First node of the graph.
326 /// \retval i the first node.
327 /// \return the first node.
329 NodeIt& first(NodeIt& i) const { return i; }
331 /// The first incoming edge.
333 /// The first incoming edge.
335 InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
336 /// The first outgoing edge.
338 /// The first outgoing edge.
340 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
341 /// The first edge of the Graph.
343 /// The first edge of the Graph.
345 EdgeIt& first(EdgeIt& i) const { return i; }
347 ///Gives back the head node of an edge.
349 ///Gives back the head node of an edge.
351 Node head(Edge) const { return INVALID; }
352 ///Gives back the tail node of an edge.
354 ///Gives back the tail node of an edge.
356 Node tail(Edge) const { return INVALID; }
358 ///Gives back the \e id of a node.
360 ///\warning Not all graph structures provide this feature.
362 ///\todo Should each graph provide \c id?
363 int id(const Node&) const { return 0; }
364 ///Gives back the \e id of an edge.
366 ///\warning Not all graph structures provide this feature.
368 ///\todo Should each graph provide \c id?
369 int id(const Edge&) const { return 0; }
373 ///\todo Should it be in the concept?
375 int nodeNum() const { return 0; }
378 ///\todo Should it be in the concept?
380 int edgeNum() const { return 0; }
383 ///Reference map of the nodes to type \c T.
385 /// \ingroup skeletons
386 ///Reference map of the nodes to type \c T.
388 /// \warning Making maps that can handle bool type (NodeMap<bool>)
389 /// needs some extra attention!
390 template<class T> class NodeMap : public ReferenceMap< Node, T >
395 NodeMap(const StaticGraph&) { }
397 NodeMap(const StaticGraph&, T) { }
400 template<typename TT> NodeMap(const NodeMap<TT>&) { }
401 ///Assignment operator
402 template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
406 ///Reference map of the edges to type \c T.
408 /// \ingroup skeletons
409 ///Reference map of the edges to type \c T.
411 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
412 /// needs some extra attention!
413 template<class T> class EdgeMap
414 : public ReferenceMap<Edge,T>
419 EdgeMap(const StaticGraph&) { }
421 EdgeMap(const StaticGraph&, T) { }
424 template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
425 ///Assignment operator
426 template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
433 /// An empty non-static graph class.
435 /// This class provides everything that \ref StaticGraph
436 /// with additional functionality which enables to build a
437 /// graph from scratch.
438 class ExtendableGraph : public StaticGraph
441 /// Defalult constructor.
443 /// Defalult constructor.
445 ExtendableGraph() { }
446 ///Add a new node to the graph.
448 /// \return the new node.
450 Node addNode() { return INVALID; }
451 ///Add a new edge to the graph.
453 ///Add a new edge to the graph with tail node \c t
454 ///and head node \c h.
455 ///\return the new edge.
456 Edge addEdge(Node h, Node t) { return INVALID; }
458 /// Resets the graph.
460 /// This function deletes all edges and nodes of the graph.
461 /// It also frees the memory allocated to store them.
462 /// \todo It might belong to \ref ErasableGraph.
466 /// An empty erasable graph class.
468 /// This class is an extension of \ref ExtendableGraph. It also makes it
469 /// possible to erase edges or nodes.
470 class ErasableGraph : public ExtendableGraph
473 /// Defalult constructor.
475 /// Defalult constructor.
480 /// Deletes node \c n node.
482 void erase(Node n) { }
485 /// Deletes edge \c e edge.
487 void erase(Edge e) { }
491 } //namespace skeleton
496 #endif // HUGO_SKELETON_GRAPH_H