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