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