|
1 // -*- c++ -*- |
|
2 #ifndef HUGO_GRAPH_H |
|
3 #define HUGO_GRAPH_H |
|
4 |
|
5 ///\file |
|
6 ///\brief Declaration of GraphSkeleton. |
|
7 |
|
8 #include <invalid.h> |
|
9 |
|
10 /// The namespace of HugoLib |
|
11 namespace hugo { |
|
12 |
|
13 // @defgroup empty_graph The GraphSkeleton class |
|
14 // @{ |
|
15 |
|
16 /// An empty graph class. |
|
17 |
|
18 /// This class provides all the common features of a graph structure, |
|
19 /// however completely without implementations and real data structures |
|
20 /// behind the interface. |
|
21 /// All graph algorithms should compile with this class, but it will not |
|
22 /// run properly, of course. |
|
23 /// |
|
24 /// It can be used for checking the interface compatibility, |
|
25 /// or it can serve as a skeleton of a new graph structure. |
|
26 /// |
|
27 /// Also, you will find here the full documentation of a certain graph |
|
28 /// feature, the documentation of a real graph imlementation |
|
29 /// like @ref ListGraph or |
|
30 /// @ref SmartGraph will just refer to this structure. |
|
31 class GraphSkeleton |
|
32 { |
|
33 public: |
|
34 /// Defalult constructor. |
|
35 GraphSkeleton() {} |
|
36 ///Copy consructor. |
|
37 |
|
38 ///\todo It is not clear, what we expect from a copy constructor. |
|
39 ///E.g. How to assign the nodes/edges to each other? What about maps? |
|
40 GraphSkeleton(const GraphSkeleton &G) {} |
|
41 |
|
42 /// The base type of the node iterators. |
|
43 |
|
44 /// This is the base type of each node iterators, |
|
45 /// thus each kind of node iterator will convert to this. |
|
46 class Node { |
|
47 public: |
|
48 /// @warning The default constructor sets the iterator |
|
49 /// to an undefined value. |
|
50 Node() {} //FIXME |
|
51 /// Invalid constructor \& conversion. |
|
52 |
|
53 /// This constructor initializes the iterator to be invalid. |
|
54 /// \sa Invalid for more details. |
|
55 |
|
56 Node(Invalid) {} |
|
57 //Node(const Node &) {} |
|
58 |
|
59 /// Two iterators are equal if and only if they point to the |
|
60 /// same object or both are invalid. |
|
61 bool operator==(Node n) const { return true; } |
|
62 |
|
63 /// \sa \ref operator==(Node n) |
|
64 /// |
|
65 bool operator!=(Node n) const { return true; } |
|
66 |
|
67 bool operator<(Node n) const { return true; } |
|
68 }; |
|
69 |
|
70 /// This iterator goes through each node. |
|
71 |
|
72 /// This iterator goes through each node. |
|
73 /// Its usage is quite simple, for example you can count the number |
|
74 /// of nodes in graph \c G of type \c Graph like this: |
|
75 /// \code |
|
76 ///int count=0; |
|
77 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; |
|
78 /// \endcode |
|
79 class NodeIt : public Node { |
|
80 public: |
|
81 /// @warning The default constructor sets the iterator |
|
82 /// to an undefined value. |
|
83 NodeIt() {} //FIXME |
|
84 /// Invalid constructor \& conversion. |
|
85 |
|
86 /// Initialize the iterator to be invalid |
|
87 /// \sa Invalid for more details. |
|
88 NodeIt(Invalid) {} |
|
89 /// Sets the iterator to the first node of \c G. |
|
90 NodeIt(const GraphSkeleton &G) {} |
|
91 /// @warning The default constructor sets the iterator |
|
92 /// to an undefined value. |
|
93 NodeIt(const NodeIt &) {} |
|
94 }; |
|
95 |
|
96 |
|
97 /// The base type of the edge iterators. |
|
98 class Edge { |
|
99 public: |
|
100 /// @warning The default constructor sets the iterator |
|
101 /// to an undefined value. |
|
102 Edge() {} //FIXME |
|
103 /// Initialize the iterator to be invalid |
|
104 Edge(Invalid) {} |
|
105 /// Two iterators are equal if and only if they point to the |
|
106 /// same object or both are invalid. |
|
107 bool operator==(Edge n) const { return true; } |
|
108 bool operator!=(Edge n) const { return true; } |
|
109 bool operator<(Edge n) const { return true; } |
|
110 }; |
|
111 |
|
112 /// This iterator goes trough the outgoing edges of a node. |
|
113 |
|
114 /// This iterator goes trough the \e outgoing edges of a certain node |
|
115 /// of a graph. |
|
116 /// Its usage is quite simple, for example you can count the number |
|
117 /// of outgoing edges of a node \c n |
|
118 /// in graph \c G of type \c Graph as follows. |
|
119 /// \code |
|
120 ///int count=0; |
|
121 ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
122 /// \endcode |
|
123 |
|
124 class OutEdgeIt : public Edge { |
|
125 public: |
|
126 /// @warning The default constructor sets the iterator |
|
127 /// to an undefined value. |
|
128 OutEdgeIt() {} |
|
129 /// Initialize the iterator to be invalid |
|
130 OutEdgeIt(Invalid) {} |
|
131 /// This constructor sets the iterator to first outgoing edge. |
|
132 |
|
133 /// This constructor set the iterator to the first outgoing edge of |
|
134 /// node |
|
135 ///@param n the node |
|
136 ///@param G the graph |
|
137 OutEdgeIt(const GraphSkeleton & G, Node n) {} |
|
138 }; |
|
139 |
|
140 /// This iterator goes trough the incoming edges of a node. |
|
141 |
|
142 /// This iterator goes trough the \e incoming edges of a certain node |
|
143 /// of a graph. |
|
144 /// Its usage is quite simple, for example you can count the number |
|
145 /// of outgoing edges of a node \c n |
|
146 /// in graph \c G of type \c Graph as follows. |
|
147 /// \code |
|
148 ///int count=0; |
|
149 ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; |
|
150 /// \endcode |
|
151 |
|
152 class InEdgeIt : public Edge { |
|
153 public: |
|
154 /// @warning The default constructor sets the iterator |
|
155 /// to an undefined value. |
|
156 InEdgeIt() {} |
|
157 /// Initialize the iterator to be invalid |
|
158 InEdgeIt(Invalid) {} |
|
159 InEdgeIt(const GraphSkeleton &, Node) {} |
|
160 }; |
|
161 // class SymEdgeIt : public Edge {}; |
|
162 |
|
163 /// This iterator goes through each edge. |
|
164 |
|
165 /// This iterator goes through each edge of a graph. |
|
166 /// Its usage is quite simple, for example you can count the number |
|
167 /// of edges in a graph \c G of type \c Graph as follows: |
|
168 /// \code |
|
169 ///int count=0; |
|
170 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; |
|
171 /// \endcode |
|
172 class EdgeIt : public Edge { |
|
173 public: |
|
174 /// @warning The default constructor sets the iterator |
|
175 /// to an undefined value. |
|
176 EdgeIt() {} |
|
177 /// Initialize the iterator to be invalid |
|
178 EdgeIt(Invalid) {} |
|
179 EdgeIt(const GraphSkeleton &) {} |
|
180 }; |
|
181 |
|
182 /// First node of the graph. |
|
183 |
|
184 /// \post \c i and the return value will be the first node. |
|
185 /// |
|
186 NodeIt &first(NodeIt &i) const { return i;} |
|
187 |
|
188 /// The first incoming edge. |
|
189 InEdgeIt &first(InEdgeIt &i, Node n) const { return i;} |
|
190 /// The first outgoing edge. |
|
191 OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;} |
|
192 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} |
|
193 /// The first edge of the Graph. |
|
194 EdgeIt &first(EdgeIt &i) const { return i;} |
|
195 |
|
196 // Node getNext(Node) const {} |
|
197 // InEdgeIt getNext(InEdgeIt) const {} |
|
198 // OutEdgeIt getNext(OutEdgeIt) const {} |
|
199 // //SymEdgeIt getNext(SymEdgeIt) const {} |
|
200 // EdgeIt getNext(EdgeIt) const {} |
|
201 |
|
202 /// Go to the next node. |
|
203 NodeIt &next(NodeIt &i) const { return i;} |
|
204 /// Go to the next incoming edge. |
|
205 InEdgeIt &next(InEdgeIt &i) const { return i;} |
|
206 /// Go to the next outgoing edge. |
|
207 OutEdgeIt &next(OutEdgeIt &i) const { return i;} |
|
208 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
209 /// Go to the next edge. |
|
210 EdgeIt &next(EdgeIt &i) const { return i;} |
|
211 |
|
212 ///Gives back the head node of an edge. |
|
213 Node head(Edge) const { return INVALID; } |
|
214 ///Gives back the tail node of an edge. |
|
215 Node tail(Edge) const { return INVALID; } |
|
216 |
|
217 // Node aNode(InEdgeIt) const {} |
|
218 // Node aNode(OutEdgeIt) const {} |
|
219 // Node aNode(SymEdgeIt) const {} |
|
220 |
|
221 // Node bNode(InEdgeIt) const {} |
|
222 // Node bNode(OutEdgeIt) const {} |
|
223 // Node bNode(SymEdgeIt) const {} |
|
224 |
|
225 /// Checks if a node iterator is valid |
|
226 |
|
227 ///\todo Maybe, it would be better if iterator converted to |
|
228 ///bool directly, as Jacint prefers. |
|
229 bool valid(const Node&) const { return true;} |
|
230 /// Checks if an edge iterator is valid |
|
231 |
|
232 ///\todo Maybe, it would be better if iterator converted to |
|
233 ///bool directly, as Jacint prefers. |
|
234 bool valid(const Edge&) const { return true;} |
|
235 |
|
236 ///Gives back the \e id of a node. |
|
237 |
|
238 ///\warning Not all graph structures provide this feature. |
|
239 /// |
|
240 int id(const Node&) const { return 0;} |
|
241 ///Gives back the \e id of an edge. |
|
242 |
|
243 ///\warning Not all graph structures provide this feature. |
|
244 /// |
|
245 int id(const Edge&) const { return 0;} |
|
246 |
|
247 //void setInvalid(Node &) const {}; |
|
248 //void setInvalid(Edge &) const {}; |
|
249 |
|
250 ///Add a new node to the graph. |
|
251 |
|
252 /// \return the new node. |
|
253 /// |
|
254 Node addNode() { return INVALID;} |
|
255 ///Add a new edge to the graph. |
|
256 |
|
257 ///Add a new edge to the graph with tail node \c tail |
|
258 ///and head node \c head. |
|
259 ///\return the new edge. |
|
260 Edge addEdge(Node tail, Node head) { return INVALID;} |
|
261 |
|
262 /// Resets the graph. |
|
263 |
|
264 /// This function deletes all edges and nodes of the graph. |
|
265 /// It also frees the memory allocated to store them. |
|
266 void clear() {} |
|
267 |
|
268 ///Read/write/reference map of the nodes to type \c T. |
|
269 |
|
270 ///Read/write/reference map of the nodes to type \c T. |
|
271 /// \sa MemoryMapSkeleton |
|
272 /// \todo We may need copy constructor |
|
273 /// \todo We may need conversion from other nodetype |
|
274 /// \todo We may need operator= |
|
275 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
276 /// needs extra attention! |
|
277 |
|
278 template<class T> class NodeMap |
|
279 { |
|
280 public: |
|
281 typedef T ValueType; |
|
282 typedef Node KeyType; |
|
283 |
|
284 NodeMap(const GraphSkeleton &G) {} |
|
285 NodeMap(const GraphSkeleton &G, T t) {} |
|
286 |
|
287 template<typename TT> NodeMap(const NodeMap<TT> &m) {} |
|
288 |
|
289 /// Sets the value of a node. |
|
290 |
|
291 /// Sets the value associated with node \c i to the value \c t. |
|
292 /// |
|
293 void set(Node i, T t) {} |
|
294 /// Gets the value of a node. |
|
295 T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary |
|
296 T &operator[](Node i) {return *(T*)0;} |
|
297 const T &operator[](Node i) const {return *(T*)0;} |
|
298 |
|
299 /// Updates the map if the graph has been changed |
|
300 |
|
301 /// \todo Do we need this? |
|
302 /// |
|
303 void update() {} |
|
304 void update(T a) {} //FIXME: Is it necessary |
|
305 }; |
|
306 |
|
307 ///Read/write/reference map of the edges to type \c T. |
|
308 |
|
309 ///Read/write/reference map of the edges to type \c T. |
|
310 ///It behaves exactly in the same way as \ref NodeMap. |
|
311 /// \sa NodeMap |
|
312 /// \sa MemoryMapSkeleton |
|
313 /// \todo We may need copy constructor |
|
314 /// \todo We may need conversion from other edgetype |
|
315 /// \todo We may need operator= |
|
316 template<class T> class EdgeMap |
|
317 { |
|
318 public: |
|
319 typedef T ValueType; |
|
320 typedef Edge KeyType; |
|
321 |
|
322 EdgeMap(const GraphSkeleton &G) {} |
|
323 EdgeMap(const GraphSkeleton &G, T t) {} |
|
324 |
|
325 void set(Edge i, T t) {} |
|
326 T get(Edge i) const {return *(T*)0;} |
|
327 T &operator[](Edge i) {return *(T*)0;} |
|
328 |
|
329 void update() {} |
|
330 void update(T a) {} //FIXME: Is it necessary |
|
331 }; |
|
332 }; |
|
333 |
|
334 /// An empty eraseable graph class. |
|
335 |
|
336 /// This class provides all the common features of an \e eraseable graph |
|
337 /// structure, |
|
338 /// however completely without implementations and real data structures |
|
339 /// behind the interface. |
|
340 /// All graph algorithms should compile with this class, but it will not |
|
341 /// run properly, of course. |
|
342 /// |
|
343 /// \todo This blabla could be replaced by a sepatate description about |
|
344 /// Skeletons. |
|
345 /// |
|
346 /// It can be used for checking the interface compatibility, |
|
347 /// or it can serve as a skeleton of a new graph structure. |
|
348 /// |
|
349 /// Also, you will find here the full documentation of a certain graph |
|
350 /// feature, the documentation of a real graph imlementation |
|
351 /// like @ref ListGraph or |
|
352 /// @ref SmartGraph will just refer to this structure. |
|
353 class EraseableGraphSkeleton : public GraphSkeleton |
|
354 { |
|
355 public: |
|
356 /// Deletes a node. |
|
357 void erase(Node n) {} |
|
358 /// Deletes an edge. |
|
359 void erase(Edge e) {} |
|
360 |
|
361 /// Defalult constructor. |
|
362 GraphSkeleton() {} |
|
363 ///Copy consructor. |
|
364 GraphSkeleton(const GraphSkeleton &G) {} |
|
365 }; |
|
366 |
|
367 |
|
368 // @} |
|
369 |
|
370 |
|
371 /// An empty graph class which provides a function to get the number |
|
372 /// of its nodes. |
|
373 |
|
374 /// This graph class provides a function for getting the number of its |
|
375 /// nodes. |
|
376 /// Clearly, for physical graph structures it can be expected to have such a |
|
377 /// function. For wrappers or graphs which are given in an implicit way, |
|
378 /// the implementation can be circumstantial, that is why this composes a |
|
379 /// separate concept. |
|
380 class NodeCountingGraphSkeleton |
|
381 { |
|
382 public: |
|
383 /// Returns the number of nodes. |
|
384 int nodeNum() const { return 0;} |
|
385 }; |
|
386 |
|
387 /// An empty graph class which provides a function to get the number of its |
|
388 /// edges. |
|
389 |
|
390 /// This graph class provides a function for getting the number of its |
|
391 /// edges. |
|
392 /// Clearly, for physical graph structures it can be expected to have such a |
|
393 /// function. For wrappers or graphs which are given in an implicit way, |
|
394 /// the implementation can be circumstantial, that is why this composes a |
|
395 /// separate concept. |
|
396 class EdgeCountingGraphSkeleton |
|
397 { |
|
398 public: |
|
399 /// Returns the number of edges. |
|
400 int edgeNum() const { return 0;} |
|
401 }; |
|
402 |
|
403 } //namespace hugo |
|
404 |
|
405 |
|
406 // class EmptyBipGraph : public Graph Skeleton |
|
407 // { |
|
408 // class ANode {}; |
|
409 // class BNode {}; |
|
410 |
|
411 // ANode &next(ANode &) {} |
|
412 // BNode &next(BNode &) {} |
|
413 |
|
414 // ANode &getFirst(ANode &) const {} |
|
415 // BNode &getFirst(BNode &) const {} |
|
416 |
|
417 // enum NodeClass { A = 0, B = 1 }; |
|
418 // NodeClass getClass(Node n) {} |
|
419 |
|
420 // } |
|
421 |
|
422 #endif // HUGO_GRAPH_H |