Merge back the whole branches/hugo++ to trunk.
2 #ifndef HUGO_SKELETON_GRAPH_H
3 #define HUGO_SKELETON_GRAPH_H
6 ///\brief Declaration of GraphSkeleton.
8 #include <hugo/invalid.h>
9 #include <hugo/skeletons/maps.h>
11 /// The namespace of HugoLib
15 // @defgroup empty_graph The GraphSkeleton class
18 /// An empty static graph class.
20 /// This class provides all the common features of a graph structure,
21 /// however completely without implementations and real data structures
22 /// behind the interface.
23 /// All graph algorithms should compile with this class, but it will not
24 /// run properly, of course.
26 /// It can be used for checking the interface compatibility,
27 /// or it can serve as a skeleton of a new graph structure.
29 /// Also, you will find here the full documentation of a certain graph
30 /// feature, the documentation of a real graph imlementation
31 /// like @ref ListGraph or
32 /// @ref SmartGraph will just refer to this structure.
33 class StaticGraphSkeleton
36 /// Defalult constructor.
37 StaticGraphSkeleton() { }
40 ///\todo It is not clear, what we expect from a copy constructor.
41 ///E.g. How to assign the nodes/edges to each other? What about maps?
42 StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
44 /// The base type of node iterators,
45 /// or in other words, the trivial node iterator.
47 /// This is the base type of each node iterator,
48 /// thus each kind of node iterator converts to this.
49 /// More precisely each kind of node iterator have to be inherited
50 /// from the trivial node iterator.
53 /// @warning The default constructor sets the iterator
54 /// to an undefined value.
58 /// Invalid constructor \& conversion.
60 /// This constructor initializes the iterator to be invalid.
61 /// \sa Invalid for more details.
63 /// Two iterators are equal if and only if they point to the
64 /// same object or both are invalid.
65 bool operator==(Node) const { return true; }
67 /// \sa \ref operator==(Node n)
69 bool operator!=(Node) const { return true; }
71 bool operator<(Node) const { return true; }
74 /// This iterator goes through each node.
76 /// This iterator goes through each node.
77 /// Its usage is quite simple, for example you can count the number
78 /// of nodes in graph \c g of type \c Graph like this:
81 /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;
83 class NodeIt : public Node {
85 /// @warning The default constructor sets the iterator
86 /// to an undefined value.
89 NodeIt(const NodeIt&) { }
90 /// Invalid constructor \& conversion.
92 /// Initialize the iterator to be invalid.
93 /// \sa Invalid for more details.
95 /// Sets the iterator to the first node of \c g.
96 NodeIt(const StaticGraphSkeleton& g) { }
97 /// Sets the iterator to the node of \c g pointed by the trivial
98 /// iterator n. This feature necessitates that each time we
99 /// iterate the node-set, the iteration order is the same.
100 NodeIt(const StaticGraphSkeleton& g, const Node& n) { }
101 /// Assign the iterator to the next node.
102 NodeIt& operator++() { return *this; }
106 /// The base type of the edge iterators.
109 /// @warning The default constructor sets the iterator
110 /// to an undefined value.
112 /// Copy constructor.
113 Edge(const Edge&) { }
114 /// Initialize the iterator to be invalid.
116 /// Two iterators are equal if and only if they point to the
117 /// same object or both are invalid.
118 bool operator==(Edge) const { return true; }
119 bool operator!=(Edge) const { return true; }
120 bool operator<(Edge) const { return true; }
123 /// This iterator goes trough the outgoing edges of a node.
125 /// This iterator goes trough the \e outgoing edges of a certain node
127 /// Its usage is quite simple, for example you can count the number
128 /// of outgoing edges of a node \c n
129 /// in graph \c g of type \c Graph as follows.
132 /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;
135 class OutEdgeIt : public Edge {
137 /// @warning The default constructor sets the iterator
138 /// to an undefined value.
140 /// Copy constructor.
141 OutEdgeIt(const OutEdgeIt&) { }
142 /// Initialize the iterator to be invalid.
143 OutEdgeIt(Invalid) { }
144 /// This constructor sets the iterator to first outgoing edge.
146 /// This constructor set the iterator to the first outgoing edge of
149 ///@param g the graph
150 OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
151 /// Sets the iterator to the value of the trivial iterator \c e.
152 /// This feature necessitates that each time we
153 /// iterate the edge-set, the iteration order is the same.
154 OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }
155 /// Assign the iterator to the next outedge of the corresponding node.
156 OutEdgeIt& operator++() { return *this; }
159 /// This iterator goes trough the incoming edges of a node.
161 /// This iterator goes trough the \e incoming edges of a certain node
163 /// Its usage is quite simple, for example you can count the number
164 /// of outgoing edges of a node \c n
165 /// in graph \c g of type \c Graph as follows.
168 /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;
171 class InEdgeIt : public Edge {
173 /// @warning The default constructor sets the iterator
174 /// to an undefined value.
176 /// Copy constructor.
177 InEdgeIt(const InEdgeIt&) { }
178 /// Initialize the iterator to be invalid.
179 InEdgeIt(Invalid) { }
181 InEdgeIt(const StaticGraphSkeleton&, const Node&) { }
183 InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }
184 /// Assign the iterator to the next inedge of the corresponding node.
185 InEdgeIt& operator++() { return *this; }
187 // class SymEdgeIt : public Edge {};
189 /// This iterator goes through each edge.
191 /// This iterator goes through each edge of a graph.
192 /// Its usage is quite simple, for example you can count the number
193 /// of edges in a graph \c g of type \c Graph as follows:
196 /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;
198 class EdgeIt : public Edge {
200 /// @warning The default constructor sets the iterator
201 /// to an undefined value.
203 /// Copy constructor.
204 EdgeIt(const EdgeIt&) { }
205 /// Initialize the iterator to be invalid.
208 EdgeIt(const StaticGraphSkeleton&) { }
210 EdgeIt(const StaticGraphSkeleton&, const Edge&) { }
211 EdgeIt& operator++() { return *this; }
214 /// First node of the graph.
216 /// \retval i the first node.
217 /// \return the first node.
219 NodeIt& first(NodeIt& i) const { return i; }
221 /// The first incoming edge.
222 InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
223 /// The first outgoing edge.
224 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
225 // SymEdgeIt& first(SymEdgeIt&, Node) const { return i; }
226 /// The first edge of the Graph.
227 EdgeIt& first(EdgeIt& i) const { return i; }
229 // Node getNext(Node) const {}
230 // InEdgeIt getNext(InEdgeIt) const {}
231 // OutEdgeIt getNext(OutEdgeIt) const {}
232 // //SymEdgeIt getNext(SymEdgeIt) const {}
233 // EdgeIt getNext(EdgeIt) const {}
235 /// Go to the next node.
236 NodeIt& next(NodeIt& i) const { return i; }
237 /// Go to the next incoming edge.
238 InEdgeIt& next(InEdgeIt& i) const { return i; }
239 /// Go to the next outgoing edge.
240 OutEdgeIt& next(OutEdgeIt& i) const { return i; }
241 //SymEdgeIt& next(SymEdgeIt&) const { }
242 /// Go to the next edge.
243 EdgeIt& next(EdgeIt& i) const { return i; }
245 ///Gives back the head node of an edge.
246 Node head(Edge) const { return INVALID; }
247 ///Gives back the tail node of an edge.
248 Node tail(Edge) const { return INVALID; }
250 // Node aNode(InEdgeIt) const {}
251 // Node aNode(OutEdgeIt) const {}
252 // Node aNode(SymEdgeIt) const {}
254 // Node bNode(InEdgeIt) const {}
255 // Node bNode(OutEdgeIt) const {}
256 // Node bNode(SymEdgeIt) const {}
258 /// Checks if a node iterator is valid
260 ///\todo Maybe, it would be better if iterator converted to
261 ///bool directly, as Jacint prefers.
262 bool valid(const Node&) const { return true; }
263 /// Checks if an edge iterator is valid
265 ///\todo Maybe, it would be better if iterator converted to
266 ///bool directly, as Jacint prefers.
267 bool valid(const Edge&) const { return true; }
269 ///Gives back the \e id of a node.
271 ///\warning Not all graph structures provide this feature.
273 int id(const Node&) const { return 0; }
274 ///Gives back the \e id of an edge.
276 ///\warning Not all graph structures provide this feature.
278 int id(const Edge&) const { return 0; }
280 /// Resets the graph.
282 /// This function deletes all edges and nodes of the graph.
283 /// It also frees the memory allocated to store them.
286 int nodeNum() const { return 0; }
287 int edgeNum() const { return 0; }
290 ///Reference map of the nodes to type \c T.
292 ///Reference map of the nodes to type \c T.
293 /// \sa ReferenceSkeleton
294 /// \warning Making maps that can handle bool type (NodeMap<bool>)
295 /// needs extra attention!
297 template<class T> class NodeMap
298 : public ReferenceMap< Node, T >
302 NodeMap(const StaticGraphSkeleton&) { }
303 NodeMap(const StaticGraphSkeleton&, T) { }
306 template<typename TT> NodeMap(const NodeMap<TT>&) { }
307 ///Assignment operator
308 template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
312 ///Reference map of the edges to type \c T.
314 ///Reference map of the edges to type \c T.
315 /// \sa ReferenceSkeleton
316 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
317 /// needs extra attention!
318 template<class T> class EdgeMap
319 : public ReferenceMap<Edge,T>
323 typedef Edge KeyType;
325 EdgeMap(const StaticGraphSkeleton&) { }
326 EdgeMap(const StaticGraphSkeleton&, T) { }
329 template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
330 ///Assignment operator
331 template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
338 /// An empty graph class.
340 /// This class provides everything that \c StaticGraphSkeleton
341 /// with additional functionality which enables to build a
342 /// graph from scratch.
343 class GraphSkeleton : public StaticGraphSkeleton
346 /// Defalult constructor.
350 ///\todo It is not clear, what we expect from a copy constructor.
351 ///E.g. How to assign the nodes/edges to each other? What about maps?
352 GraphSkeleton(const GraphSkeleton&) { }
354 ///Add a new node to the graph.
356 /// \return the new node.
358 Node addNode() { return INVALID; }
359 ///Add a new edge to the graph.
361 ///Add a new edge to the graph with tail node \c tail
362 ///and head node \c head.
363 ///\return the new edge.
364 Edge addEdge(Node, Node) { return INVALID; }
366 /// Resets the graph.
368 /// This function deletes all edges and nodes of the graph.
369 /// It also frees the memory allocated to store them.
370 /// \todo It might belong to \c EraseableGraphSkeleton.
374 /// An empty eraseable graph class.
376 /// This class is an extension of \c GraphSkeleton. It also makes it
377 /// possible to erase edges or nodes.
378 class EraseableGraphSkeleton : public GraphSkeleton
382 void erase(Node n) { }
384 void erase(Edge e) { }
386 /// Defalult constructor.
387 EraseableGraphSkeleton() { }
389 EraseableGraphSkeleton(const GraphSkeleton&) { }
393 } //namespace skeleton
399 // class EmptyBipGraph : public Graph Skeleton
404 // ANode &next(ANode &) {}
405 // BNode &next(BNode &) {}
407 // ANode &getFirst(ANode &) const {}
408 // BNode &getFirst(BNode &) const {}
410 // enum NodeClass { A = 0, B = 1 };
411 // NodeClass getClass(Node n) {}
415 #endif // HUGO_SKELETON_GRAPH_H