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