Correction in doc: skeleton/path.h has been moved to the 'skeletons' module.
2 #ifndef HUGO_SKELETON_GRAPH_H
3 #define HUGO_SKELETON_GRAPH_H
7 ///\brief Declaration of GraphSkeleton.
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.
34 class StaticGraphSkeleton
37 /// Defalult constructor.
39 /// Defalult constructor.
41 StaticGraphSkeleton() { }
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 // StaticGraphSkeleton(const StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton& 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 StaticGraphSkeleton&, 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 What is this?
375 int nodeNum() const { return 0; }
377 ///\todo What is this?
379 int edgeNum() const { return 0; }
382 ///Reference map of the nodes to type \c T.
384 ///Reference map of the nodes to type \c T.
385 /// \sa ReferenceSkeleton
386 /// \warning Making maps that can handle bool type (NodeMap<bool>)
387 /// needs some extra attention!
388 template<class T> class NodeMap: public ReferenceMap< Node, T >
393 NodeMap(const StaticGraphSkeleton&) { }
395 NodeMap(const StaticGraphSkeleton&, T) { }
398 template<typename TT> NodeMap(const NodeMap<TT>&) { }
399 ///Assignment operator
400 template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
404 ///Reference map of the edges to type \c T.
406 ///Reference map of the edges to type \c T.
407 /// \sa ReferenceSkeleton
408 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
409 /// needs some extra attention!
410 template<class T> class EdgeMap
411 : public ReferenceMap<Edge,T>
416 EdgeMap(const StaticGraphSkeleton&) { }
418 EdgeMap(const StaticGraphSkeleton&, T) { }
421 template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
422 ///Assignment operator
423 template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
430 /// An empty non-static graph class.
432 /// This class provides everything that \c StaticGraphSkeleton
433 /// with additional functionality which enables to build a
434 /// graph from scratch.
435 class GraphSkeleton : public StaticGraphSkeleton
438 /// Defalult constructor.
440 /// Defalult constructor.
443 ///Add a new node to the graph.
445 /// \return the new node.
447 Node addNode() { return INVALID; }
448 ///Add a new edge to the graph.
450 ///Add a new edge to the graph with tail node \c tail
451 ///and head node \c head.
452 ///\return the new edge.
453 Edge addEdge(Node, Node) { return INVALID; }
455 /// Resets the graph.
457 /// This function deletes all edges and nodes of the graph.
458 /// It also frees the memory allocated to store them.
459 /// \todo It might belong to \c EraseableGraphSkeleton.
463 /// An empty eraseable graph class.
465 /// This class is an extension of \c GraphSkeleton. It also makes it
466 /// possible to erase edges or nodes.
467 class EraseableGraphSkeleton : public GraphSkeleton
470 /// Defalult constructor.
472 /// Defalult constructor.
474 EraseableGraphSkeleton() { }
477 /// Deletes node \c n node.
479 void erase(Node n) { }
482 /// Deletes edge \c e edge.
484 void erase(Edge e) { }
488 } //namespace skeleton
493 #endif // HUGO_SKELETON_GRAPH_H