|
1 /* -*- C++ -*- |
|
2 * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_CONCEPT_GRAPH_H |
|
18 #define LEMON_CONCEPT_GRAPH_H |
|
19 |
|
20 ///\ingroup concept |
|
21 ///\file |
|
22 ///\brief Declaration of Graph. |
|
23 |
|
24 #include <lemon/invalid.h> |
|
25 #include <lemon/concept/maps.h> |
|
26 #include <lemon/concept_check.h> |
|
27 #include <lemon/concept/graph_component.h> |
|
28 |
|
29 namespace lemon { |
|
30 namespace concept { |
|
31 |
|
32 /// \addtogroup concept |
|
33 /// @{ |
|
34 |
|
35 // /// An empty static graph class. |
|
36 |
|
37 // /// This class provides all the common features of a graph structure, |
|
38 // /// however completely without implementations and real data structures |
|
39 // /// behind the interface. |
|
40 // /// All graph algorithms should compile with this class, but it will not |
|
41 // /// run properly, of course. |
|
42 // /// |
|
43 // /// It can be used for checking the interface compatibility, |
|
44 // /// or it can serve as a skeleton of a new graph structure. |
|
45 // /// |
|
46 // /// Also, you will find here the full documentation of a certain graph |
|
47 // /// feature, the documentation of a real graph imlementation |
|
48 // /// like @ref ListGraph or |
|
49 // /// @ref SmartGraph will just refer to this structure. |
|
50 // /// |
|
51 // /// \todo A pages describing the concept of concept description would |
|
52 // /// be nice. |
|
53 // class StaticGraph |
|
54 // { |
|
55 // public: |
|
56 // /// Defalult constructor. |
|
57 |
|
58 // /// Defalult constructor. |
|
59 // /// |
|
60 // StaticGraph() { } |
|
61 // ///Copy consructor. |
|
62 |
|
63 // // ///\todo It is not clear, what we expect from a copy constructor. |
|
64 // // ///E.g. How to assign the nodes/edges to each other? What about maps? |
|
65 // // StaticGraph(const StaticGraph& g) { } |
|
66 |
|
67 // /// The base type of node iterators, |
|
68 // /// or in other words, the trivial node iterator. |
|
69 |
|
70 // /// This is the base type of each node iterator, |
|
71 // /// thus each kind of node iterator converts to this. |
|
72 // /// More precisely each kind of node iterator should be inherited |
|
73 // /// from the trivial node iterator. |
|
74 // class Node { |
|
75 // public: |
|
76 // /// Default constructor |
|
77 |
|
78 // /// @warning The default constructor sets the iterator |
|
79 // /// to an undefined value. |
|
80 // Node() { } |
|
81 // /// Copy constructor. |
|
82 |
|
83 // /// Copy constructor. |
|
84 // /// |
|
85 // Node(const Node&) { } |
|
86 |
|
87 // /// Invalid constructor \& conversion. |
|
88 |
|
89 // /// This constructor initializes the iterator to be invalid. |
|
90 // /// \sa Invalid for more details. |
|
91 // Node(Invalid) { } |
|
92 // /// Equality operator |
|
93 |
|
94 // /// Two iterators are equal if and only if they point to the |
|
95 // /// same object or both are invalid. |
|
96 // bool operator==(Node) const { return true; } |
|
97 |
|
98 // /// Inequality operator |
|
99 |
|
100 // /// \sa operator==(Node n) |
|
101 // /// |
|
102 // bool operator!=(Node) const { return true; } |
|
103 |
|
104 // ///Comparison operator. |
|
105 |
|
106 // ///This is a strict ordering between the nodes. |
|
107 // /// |
|
108 // ///This ordering can be different from the order in which NodeIt |
|
109 // ///goes through the nodes. |
|
110 // ///\todo Possibly we don't need it. |
|
111 // bool operator<(Node) const { return true; } |
|
112 // }; |
|
113 |
|
114 // /// This iterator goes through each node. |
|
115 |
|
116 // /// This iterator goes through each node. |
|
117 // /// Its usage is quite simple, for example you can count the number |
|
118 // /// of nodes in graph \c g of type \c Graph like this: |
|
119 // /// \code |
|
120 // /// int count=0; |
|
121 // /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; |
|
122 // /// \endcode |
|
123 // class NodeIt : public Node { |
|
124 // public: |
|
125 // /// Default constructor |
|
126 |
|
127 // /// @warning The default constructor sets the iterator |
|
128 // /// to an undefined value. |
|
129 // NodeIt() { } |
|
130 // /// Copy constructor. |
|
131 |
|
132 // /// Copy constructor. |
|
133 // /// |
|
134 // NodeIt(const NodeIt&) { } |
|
135 // /// Invalid constructor \& conversion. |
|
136 |
|
137 // /// Initialize the iterator to be invalid. |
|
138 // /// \sa Invalid for more details. |
|
139 // NodeIt(Invalid) { } |
|
140 // /// Sets the iterator to the first node. |
|
141 |
|
142 // /// Sets the iterator to the first node of \c g. |
|
143 // /// |
|
144 // NodeIt(const StaticGraph& g) { } |
|
145 // /// Node -> NodeIt conversion. |
|
146 |
|
147 // /// Sets the iterator to the node of \c g pointed by the trivial |
|
148 // /// iterator n. |
|
149 // /// This feature necessitates that each time we |
|
150 // /// iterate the edge-set, the iteration order is the same. |
|
151 // NodeIt(const StaticGraph& g, const Node& n) { } |
|
152 // /// Next node. |
|
153 |
|
154 // /// Assign the iterator to the next node. |
|
155 // /// |
|
156 // NodeIt& operator++() { return *this; } |
|
157 // }; |
|
158 |
|
159 |
|
160 // /// The base type of the edge iterators. |
|
161 |
|
162 // /// The base type of the edge iterators. |
|
163 // /// |
|
164 // class Edge { |
|
165 // public: |
|
166 // /// Default constructor |
|
167 |
|
168 // /// @warning The default constructor sets the iterator |
|
169 // /// to an undefined value. |
|
170 // Edge() { } |
|
171 // /// Copy constructor. |
|
172 |
|
173 // /// Copy constructor. |
|
174 // /// |
|
175 // Edge(const Edge&) { } |
|
176 // /// Initialize the iterator to be invalid. |
|
177 |
|
178 // /// Initialize the iterator to be invalid. |
|
179 // /// |
|
180 // Edge(Invalid) { } |
|
181 // /// Equality operator |
|
182 |
|
183 // /// Two iterators are equal if and only if they point to the |
|
184 // /// same object or both are invalid. |
|
185 // bool operator==(Edge) const { return true; } |
|
186 // /// Inequality operator |
|
187 |
|
188 // /// \sa operator==(Node n) |
|
189 // /// |
|
190 // bool operator!=(Edge) const { return true; } |
|
191 // ///Comparison operator. |
|
192 |
|
193 // ///This is a strict ordering between the nodes. |
|
194 // /// |
|
195 // ///This ordering can be different from the order in which NodeIt |
|
196 // ///goes through the nodes. |
|
197 // ///\todo Possibly we don't need it. |
|
198 // bool operator<(Edge) const { return true; } |
|
199 // }; |
|
200 |
|
201 // /// This iterator goes trough the outgoing edges of a node. |
|
202 |
|
203 // /// This iterator goes trough the \e outgoing edges of a certain node |
|
204 // /// of a graph. |
|
205 // /// Its usage is quite simple, for example you can count the number |
|
206 // /// of outgoing edges of a node \c n |
|
207 // /// in graph \c g of type \c Graph as follows. |
|
208 // /// \code |
|
209 // /// int count=0; |
|
210 // /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
211 // /// \endcode |
|
212 |
|
213 // class OutEdgeIt : public Edge { |
|
214 // public: |
|
215 // /// Default constructor |
|
216 |
|
217 // /// @warning The default constructor sets the iterator |
|
218 // /// to an undefined value. |
|
219 // OutEdgeIt() { } |
|
220 // /// Copy constructor. |
|
221 |
|
222 // /// Copy constructor. |
|
223 // /// |
|
224 // OutEdgeIt(const OutEdgeIt&) { } |
|
225 // /// Initialize the iterator to be invalid. |
|
226 |
|
227 // /// Initialize the iterator to be invalid. |
|
228 // /// |
|
229 // OutEdgeIt(Invalid) { } |
|
230 // /// This constructor sets the iterator to first outgoing edge. |
|
231 |
|
232 // /// This constructor set the iterator to the first outgoing edge of |
|
233 // /// node |
|
234 // ///@param n the node |
|
235 // ///@param g the graph |
|
236 // OutEdgeIt(const StaticGraph& g, const Node& n) { } |
|
237 // /// Edge -> OutEdgeIt conversion |
|
238 |
|
239 // /// Sets the iterator to the value of the trivial iterator \c e. |
|
240 // /// This feature necessitates that each time we |
|
241 // /// iterate the edge-set, the iteration order is the same. |
|
242 // OutEdgeIt(const StaticGraph& g, const Edge& e) { } |
|
243 // ///Next outgoing edge |
|
244 |
|
245 // /// Assign the iterator to the next |
|
246 // /// outgoing edge of the corresponding node. |
|
247 // OutEdgeIt& operator++() { return *this; } |
|
248 // }; |
|
249 |
|
250 // /// This iterator goes trough the incoming edges of a node. |
|
251 |
|
252 // /// This iterator goes trough the \e incoming edges of a certain node |
|
253 // /// of a graph. |
|
254 // /// Its usage is quite simple, for example you can count the number |
|
255 // /// of outgoing edges of a node \c n |
|
256 // /// in graph \c g of type \c Graph as follows. |
|
257 // /// \code |
|
258 // /// int count=0; |
|
259 // /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
260 // /// \endcode |
|
261 |
|
262 // class InEdgeIt : public Edge { |
|
263 // public: |
|
264 // /// Default constructor |
|
265 |
|
266 // /// @warning The default constructor sets the iterator |
|
267 // /// to an undefined value. |
|
268 // InEdgeIt() { } |
|
269 // /// Copy constructor. |
|
270 |
|
271 // /// Copy constructor. |
|
272 // /// |
|
273 // InEdgeIt(const InEdgeIt&) { } |
|
274 // /// Initialize the iterator to be invalid. |
|
275 |
|
276 // /// Initialize the iterator to be invalid. |
|
277 // /// |
|
278 // InEdgeIt(Invalid) { } |
|
279 // /// This constructor sets the iterator to first incoming edge. |
|
280 |
|
281 // /// This constructor set the iterator to the first incoming edge of |
|
282 // /// node |
|
283 // ///@param n the node |
|
284 // ///@param g the graph |
|
285 // InEdgeIt(const StaticGraph& g, const Node& n) { } |
|
286 // /// Edge -> InEdgeIt conversion |
|
287 |
|
288 // /// Sets the iterator to the value of the trivial iterator \c e. |
|
289 // /// This feature necessitates that each time we |
|
290 // /// iterate the edge-set, the iteration order is the same. |
|
291 // InEdgeIt(const StaticGraph& g, const Edge& n) { } |
|
292 // /// Next incoming edge |
|
293 |
|
294 // /// Assign the iterator to the next inedge of the corresponding node. |
|
295 // /// |
|
296 // InEdgeIt& operator++() { return *this; } |
|
297 // }; |
|
298 // /// This iterator goes through each edge. |
|
299 |
|
300 // /// This iterator goes through each edge of a graph. |
|
301 // /// Its usage is quite simple, for example you can count the number |
|
302 // /// of edges in a graph \c g of type \c Graph as follows: |
|
303 // /// \code |
|
304 // /// int count=0; |
|
305 // /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
|
306 // /// \endcode |
|
307 // class EdgeIt : public Edge { |
|
308 // public: |
|
309 // /// Default constructor |
|
310 |
|
311 // /// @warning The default constructor sets the iterator |
|
312 // /// to an undefined value. |
|
313 // EdgeIt() { } |
|
314 // /// Copy constructor. |
|
315 |
|
316 // /// Copy constructor. |
|
317 // /// |
|
318 // EdgeIt(const EdgeIt&) { } |
|
319 // /// Initialize the iterator to be invalid. |
|
320 |
|
321 // /// Initialize the iterator to be invalid. |
|
322 // /// |
|
323 // EdgeIt(Invalid) { } |
|
324 // /// This constructor sets the iterator to first edge. |
|
325 |
|
326 // /// This constructor set the iterator to the first edge of |
|
327 // /// node |
|
328 // ///@param g the graph |
|
329 // EdgeIt(const StaticGraph& g) { } |
|
330 // /// Edge -> EdgeIt conversion |
|
331 |
|
332 // /// Sets the iterator to the value of the trivial iterator \c e. |
|
333 // /// This feature necessitates that each time we |
|
334 // /// iterate the edge-set, the iteration order is the same. |
|
335 // EdgeIt(const StaticGraph&, const Edge&) { } |
|
336 // ///Next edge |
|
337 |
|
338 // /// Assign the iterator to the next |
|
339 // /// edge of the corresponding node. |
|
340 // EdgeIt& operator++() { return *this; } |
|
341 // }; |
|
342 |
|
343 // /// First node of the graph. |
|
344 |
|
345 // /// \retval i the first node. |
|
346 // /// \return the first node. |
|
347 // /// |
|
348 // NodeIt& first(NodeIt& i) const { return i; } |
|
349 |
|
350 // /// The first incoming edge. |
|
351 |
|
352 // /// The first incoming edge. |
|
353 // /// |
|
354 // InEdgeIt& first(InEdgeIt &i, Node) const { return i; } |
|
355 // /// The first outgoing edge. |
|
356 |
|
357 // /// The first outgoing edge. |
|
358 // /// |
|
359 // OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } |
|
360 // /// The first edge of the Graph. |
|
361 |
|
362 // /// The first edge of the Graph. |
|
363 // /// |
|
364 // EdgeIt& first(EdgeIt& i) const { return i; } |
|
365 |
|
366 // ///Gives back the head node of an edge. |
|
367 |
|
368 // ///Gives back the head node of an edge. |
|
369 // /// |
|
370 // Node head(Edge) const { return INVALID; } |
|
371 // ///Gives back the tail node of an edge. |
|
372 |
|
373 // ///Gives back the tail node of an edge. |
|
374 // /// |
|
375 // Node tail(Edge) const { return INVALID; } |
|
376 |
|
377 // ///Gives back the \e id of a node. |
|
378 |
|
379 // ///\warning Not all graph structures provide this feature. |
|
380 // /// |
|
381 // ///\todo Should each graph provide \c id? |
|
382 // int id(const Node&) const { return 0; } |
|
383 // ///Gives back the \e id of an edge. |
|
384 |
|
385 // ///\warning Not all graph structures provide this feature. |
|
386 // /// |
|
387 // ///\todo Should each graph provide \c id? |
|
388 // int id(const Edge&) const { return 0; } |
|
389 |
|
390 // ///\e |
|
391 |
|
392 // ///\todo Should it be in the concept? |
|
393 // /// |
|
394 // int nodeNum() const { return 0; } |
|
395 // ///\e |
|
396 |
|
397 // ///\todo Should it be in the concept? |
|
398 // /// |
|
399 // int edgeNum() const { return 0; } |
|
400 |
|
401 |
|
402 // ///Reference map of the nodes to type \c T. |
|
403 |
|
404 // /// \ingroup concept |
|
405 // ///Reference map of the nodes to type \c T. |
|
406 // /// \sa Reference |
|
407 // /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
408 // /// needs some extra attention! |
|
409 // template<class T> class NodeMap : public ReferenceMap< Node, T > |
|
410 // { |
|
411 // public: |
|
412 |
|
413 // ///\e |
|
414 // NodeMap(const StaticGraph&) { } |
|
415 // ///\e |
|
416 // NodeMap(const StaticGraph&, T) { } |
|
417 |
|
418 // ///Copy constructor |
|
419 // template<typename TT> NodeMap(const NodeMap<TT>&) { } |
|
420 // ///Assignment operator |
|
421 // template<typename TT> NodeMap& operator=(const NodeMap<TT>&) |
|
422 // { return *this; } |
|
423 // }; |
|
424 |
|
425 // ///Reference map of the edges to type \c T. |
|
426 |
|
427 // /// \ingroup concept |
|
428 // ///Reference map of the edges to type \c T. |
|
429 // /// \sa Reference |
|
430 // /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
|
431 // /// needs some extra attention! |
|
432 // template<class T> class EdgeMap |
|
433 // : public ReferenceMap<Edge,T> |
|
434 // { |
|
435 // public: |
|
436 |
|
437 // ///\e |
|
438 // EdgeMap(const StaticGraph&) { } |
|
439 // ///\e |
|
440 // EdgeMap(const StaticGraph&, T) { } |
|
441 |
|
442 // ///Copy constructor |
|
443 // template<typename TT> EdgeMap(const EdgeMap<TT>&) { } |
|
444 // ///Assignment operator |
|
445 // template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&) |
|
446 // { return *this; } |
|
447 // }; |
|
448 // }; |
|
449 |
|
450 // struct DummyType { |
|
451 // int value; |
|
452 // DummyType() {} |
|
453 // DummyType(int p) : value(p) {} |
|
454 // DummyType& operator=(int p) { value = p; return *this;} |
|
455 // }; |
|
456 |
|
457 // ///\brief Checks whether \c G meets the |
|
458 // ///\ref lemon::concept::StaticGraph "StaticGraph" concept |
|
459 // template<class Graph> void checkCompileStaticGraph(Graph &G) |
|
460 // { |
|
461 // typedef typename Graph::Node Node; |
|
462 // typedef typename Graph::NodeIt NodeIt; |
|
463 // typedef typename Graph::Edge Edge; |
|
464 // typedef typename Graph::EdgeIt EdgeIt; |
|
465 // typedef typename Graph::InEdgeIt InEdgeIt; |
|
466 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
467 |
|
468 // { |
|
469 // Node i; Node j(i); Node k(INVALID); |
|
470 // i=j; |
|
471 // bool b; b=true; |
|
472 // b=(i==INVALID); b=(i!=INVALID); |
|
473 // b=(i==j); b=(i!=j); b=(i<j); |
|
474 // } |
|
475 // { |
|
476 // NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
|
477 // i=j; |
|
478 // j=G.first(i); |
|
479 // j=++i; |
|
480 // bool b; b=true; |
|
481 // b=(i==INVALID); b=(i!=INVALID); |
|
482 // Node n(i); |
|
483 // n=i; |
|
484 // b=(i==j); b=(i!=j); b=(i<j); |
|
485 // //Node ->NodeIt conversion |
|
486 // NodeIt ni(G,n); |
|
487 // } |
|
488 // { |
|
489 // Edge i; Edge j(i); Edge k(INVALID); |
|
490 // i=j; |
|
491 // bool b; b=true; |
|
492 // b=(i==INVALID); b=(i!=INVALID); |
|
493 // b=(i==j); b=(i!=j); b=(i<j); |
|
494 // } |
|
495 // { |
|
496 // EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
|
497 // i=j; |
|
498 // j=G.first(i); |
|
499 // j=++i; |
|
500 // bool b; b=true; |
|
501 // b=(i==INVALID); b=(i!=INVALID); |
|
502 // Edge e(i); |
|
503 // e=i; |
|
504 // b=(i==j); b=(i!=j); b=(i<j); |
|
505 // //Edge ->EdgeIt conversion |
|
506 // EdgeIt ei(G,e); |
|
507 // } |
|
508 // { |
|
509 // Node n; |
|
510 // InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
|
511 // i=j; |
|
512 // j=G.first(i,n); |
|
513 // j=++i; |
|
514 // bool b; b=true; |
|
515 // b=(i==INVALID); b=(i!=INVALID); |
|
516 // Edge e(i); |
|
517 // e=i; |
|
518 // b=(i==j); b=(i!=j); b=(i<j); |
|
519 // //Edge ->InEdgeIt conversion |
|
520 // InEdgeIt ei(G,e); |
|
521 // } |
|
522 // { |
|
523 // Node n; |
|
524 // OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
|
525 // i=j; |
|
526 // j=G.first(i,n); |
|
527 // j=++i; |
|
528 // bool b; b=true; |
|
529 // b=(i==INVALID); b=(i!=INVALID); |
|
530 // Edge e(i); |
|
531 // e=i; |
|
532 // b=(i==j); b=(i!=j); b=(i<j); |
|
533 // //Edge ->OutEdgeIt conversion |
|
534 // OutEdgeIt ei(G,e); |
|
535 // } |
|
536 // { |
|
537 // Node n,m; |
|
538 // n=m=INVALID; |
|
539 // Edge e; |
|
540 // e=INVALID; |
|
541 // n=G.tail(e); |
|
542 // n=G.head(e); |
|
543 // } |
|
544 // // id tests |
|
545 // { Node n; int i=G.id(n); i=i; } |
|
546 // { Edge e; int i=G.id(e); i=i; } |
|
547 // //NodeMap tests |
|
548 // { |
|
549 // Node k; |
|
550 // typename Graph::template NodeMap<int> m(G); |
|
551 // //Const map |
|
552 // typename Graph::template NodeMap<int> const &cm = m; |
|
553 // //Inicialize with default value |
|
554 // typename Graph::template NodeMap<int> mdef(G,12); |
|
555 // //Copy |
|
556 // typename Graph::template NodeMap<int> mm(cm); |
|
557 // //Copy from another type |
|
558 // typename Graph::template NodeMap<double> dm(cm); |
|
559 // //Copy to more complex type |
|
560 // typename Graph::template NodeMap<DummyType> em(cm); |
|
561 // int v; |
|
562 // v=m[k]; m[k]=v; m.set(k,v); |
|
563 // v=cm[k]; |
|
564 |
|
565 // m=cm; |
|
566 // dm=cm; //Copy from another type |
|
567 // em=cm; //Copy to more complex type |
|
568 // { |
|
569 // //Check the typedef's |
|
570 // typename Graph::template NodeMap<int>::ValueType val; |
|
571 // val=1; |
|
572 // typename Graph::template NodeMap<int>::KeyType key; |
|
573 // key = typename Graph::NodeIt(G); |
|
574 // } |
|
575 // } |
|
576 // { //bool NodeMap |
|
577 // Node k; |
|
578 // typename Graph::template NodeMap<bool> m(G); |
|
579 // typename Graph::template NodeMap<bool> const &cm = m; //Const map |
|
580 // //Inicialize with default value |
|
581 // typename Graph::template NodeMap<bool> mdef(G,12); |
|
582 // typename Graph::template NodeMap<bool> mm(cm); //Copy |
|
583 // typename Graph::template NodeMap<int> dm(cm); //Copy from another type |
|
584 // bool v; |
|
585 // v=m[k]; m[k]=v; m.set(k,v); |
|
586 // v=cm[k]; |
|
587 |
|
588 // m=cm; |
|
589 // dm=cm; //Copy from another type |
|
590 // m=dm; //Copy to another type |
|
591 |
|
592 // { |
|
593 // //Check the typedef's |
|
594 // typename Graph::template NodeMap<bool>::ValueType val; |
|
595 // val=true; |
|
596 // typename Graph::template NodeMap<bool>::KeyType key; |
|
597 // key= typename Graph::NodeIt(G); |
|
598 // } |
|
599 // } |
|
600 // //EdgeMap tests |
|
601 // { |
|
602 // Edge k; |
|
603 // typename Graph::template EdgeMap<int> m(G); |
|
604 // typename Graph::template EdgeMap<int> const &cm = m; //Const map |
|
605 // //Inicialize with default value |
|
606 // typename Graph::template EdgeMap<int> mdef(G,12); |
|
607 // typename Graph::template EdgeMap<int> mm(cm); //Copy |
|
608 // typename Graph::template EdgeMap<double> dm(cm);//Copy from another type |
|
609 // int v; |
|
610 // v=m[k]; m[k]=v; m.set(k,v); |
|
611 // v=cm[k]; |
|
612 |
|
613 // m=cm; |
|
614 // dm=cm; //Copy from another type |
|
615 // { |
|
616 // //Check the typedef's |
|
617 // typename Graph::template EdgeMap<int>::ValueType val; |
|
618 // val=1; |
|
619 // typename Graph::template EdgeMap<int>::KeyType key; |
|
620 // key= typename Graph::EdgeIt(G); |
|
621 // } |
|
622 // } |
|
623 // { //bool EdgeMap |
|
624 // Edge k; |
|
625 // typename Graph::template EdgeMap<bool> m(G); |
|
626 // typename Graph::template EdgeMap<bool> const &cm = m; //Const map |
|
627 // //Inicialize with default value |
|
628 // typename Graph::template EdgeMap<bool> mdef(G,12); |
|
629 // typename Graph::template EdgeMap<bool> mm(cm); //Copy |
|
630 // typename Graph::template EdgeMap<int> dm(cm); //Copy from another type |
|
631 // bool v; |
|
632 // v=m[k]; m[k]=v; m.set(k,v); |
|
633 // v=cm[k]; |
|
634 |
|
635 // m=cm; |
|
636 // dm=cm; //Copy from another type |
|
637 // m=dm; //Copy to another type |
|
638 // { |
|
639 // //Check the typedef's |
|
640 // typename Graph::template EdgeMap<bool>::ValueType val; |
|
641 // val=true; |
|
642 // typename Graph::template EdgeMap<bool>::KeyType key; |
|
643 // key= typename Graph::EdgeIt(G); |
|
644 // } |
|
645 // } |
|
646 // } |
|
647 |
|
648 // /// An empty non-static graph class. |
|
649 |
|
650 // /// This class provides everything that \ref StaticGraph |
|
651 // /// with additional functionality which enables to build a |
|
652 // /// graph from scratch. |
|
653 // class ExtendableGraph : public StaticGraph |
|
654 // { |
|
655 // public: |
|
656 // /// Defalult constructor. |
|
657 |
|
658 // /// Defalult constructor. |
|
659 // /// |
|
660 // ExtendableGraph() { } |
|
661 // ///Add a new node to the graph. |
|
662 |
|
663 // /// \return the new node. |
|
664 // /// |
|
665 // Node addNode() { return INVALID; } |
|
666 // ///Add a new edge to the graph. |
|
667 |
|
668 // ///Add a new edge to the graph with tail node \c t |
|
669 // ///and head node \c h. |
|
670 // ///\return the new edge. |
|
671 // Edge addEdge(Node h, Node t) { return INVALID; } |
|
672 |
|
673 // /// Resets the graph. |
|
674 |
|
675 // /// This function deletes all edges and nodes of the graph. |
|
676 // /// It also frees the memory allocated to store them. |
|
677 // /// \todo It might belong to \ref ErasableGraph. |
|
678 // void clear() { } |
|
679 // }; |
|
680 |
|
681 |
|
682 // ///\brief Checks whether \c G meets the |
|
683 // ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept |
|
684 // template<class Graph> void checkCompileExtendableGraph(Graph &G) |
|
685 // { |
|
686 // checkCompileStaticGraph(G); |
|
687 |
|
688 // typedef typename Graph::Node Node; |
|
689 // typedef typename Graph::NodeIt NodeIt; |
|
690 // typedef typename Graph::Edge Edge; |
|
691 // typedef typename Graph::EdgeIt EdgeIt; |
|
692 // typedef typename Graph::InEdgeIt InEdgeIt; |
|
693 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
694 |
|
695 // Node n,m; |
|
696 // n=G.addNode(); |
|
697 // m=G.addNode(); |
|
698 // Edge e; |
|
699 // e=G.addEdge(n,m); |
|
700 |
|
701 // // G.clear(); |
|
702 // } |
|
703 |
|
704 |
|
705 // /// An empty erasable graph class. |
|
706 |
|
707 // /// This class is an extension of \ref ExtendableGraph. It also makes it |
|
708 // /// possible to erase edges or nodes. |
|
709 // class ErasableGraph : public ExtendableGraph |
|
710 // { |
|
711 // public: |
|
712 // /// Defalult constructor. |
|
713 |
|
714 // /// Defalult constructor. |
|
715 // /// |
|
716 // ErasableGraph() { } |
|
717 // /// Deletes a node. |
|
718 |
|
719 // /// Deletes node \c n node. |
|
720 // /// |
|
721 // void erase(Node n) { } |
|
722 // /// Deletes an edge. |
|
723 |
|
724 // /// Deletes edge \c e edge. |
|
725 // /// |
|
726 // void erase(Edge e) { } |
|
727 // }; |
|
728 |
|
729 // template<class Graph> void checkCompileGraphEraseEdge(Graph &G) |
|
730 // { |
|
731 // typename Graph::Edge e; |
|
732 // G.erase(e); |
|
733 // } |
|
734 |
|
735 // template<class Graph> void checkCompileGraphEraseNode(Graph &G) |
|
736 // { |
|
737 // typename Graph::Node n; |
|
738 // G.erase(n); |
|
739 // } |
|
740 |
|
741 // ///\brief Checks whether \c G meets the |
|
742 // ///\ref lemon::concept::EresableGraph "EresableGraph" concept |
|
743 // template<class Graph> void checkCompileErasableGraph(Graph &G) |
|
744 // { |
|
745 // checkCompileExtendableGraph(G); |
|
746 // checkCompileGraphEraseNode(G); |
|
747 // checkCompileGraphEraseEdge(G); |
|
748 // } |
|
749 |
|
750 // ///Checks whether a graph has findEdge() member function. |
|
751 |
|
752 // ///\todo findEdge() might be a global function. |
|
753 // /// |
|
754 // template<class Graph> void checkCompileGraphFindEdge(Graph &G) |
|
755 // { |
|
756 // typedef typename Graph::NodeIt Node; |
|
757 // typedef typename Graph::NodeIt NodeIt; |
|
758 |
|
759 // G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); |
|
760 // G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); |
|
761 // } |
|
762 |
|
763 |
|
764 |
|
765 /************* New GraphBase stuff **************/ |
|
766 |
|
767 |
|
768 /// \bug The nodes and edges are not allowed to inherit from the |
|
769 /// same baseclass. |
|
770 |
|
771 class BaseGraphItem { |
|
772 public: |
|
773 BaseGraphItem() {} |
|
774 BaseGraphItem(Invalid) {} |
|
775 |
|
776 // We explicitely list these: |
|
777 BaseGraphItem(BaseGraphItem const&) {} |
|
778 BaseGraphItem& operator=(BaseGraphItem const&) { return *this; } |
|
779 |
|
780 bool operator==(BaseGraphItem) const { return false; } |
|
781 bool operator!=(BaseGraphItem) const { return false; } |
|
782 |
|
783 // Technical requirement. Do we really need this? |
|
784 bool operator<(BaseGraphItem) const { return false; } |
|
785 }; |
|
786 |
|
787 |
|
788 /// A minimal GraphBase concept |
|
789 |
|
790 /// This class describes a minimal concept which can be extended to a |
|
791 /// full-featured graph with \ref GraphFactory. |
|
792 class GraphBase { |
|
793 public: |
|
794 |
|
795 GraphBase() {} |
|
796 |
|
797 |
|
798 /// \bug Nodes and Edges are comparable each other |
|
799 |
|
800 class Node : public BaseGraphItem {}; |
|
801 class Edge : public BaseGraphItem {}; |
|
802 |
|
803 // Graph operation |
|
804 void firstNode(Node &n) const { } |
|
805 void firstEdge(Edge &e) const { } |
|
806 |
|
807 void firstOutEdge(Edge &e, Node) const { } |
|
808 void firstInEdge(Edge &e, Node) const { } |
|
809 |
|
810 void nextNode(Node &n) const { } |
|
811 void nextEdge(Edge &e) const { } |
|
812 |
|
813 |
|
814 // Question: isn't it reasonable if this methods have a Node |
|
815 // parameter? Like this: |
|
816 // Edge& nextOut(Edge &e, Node) const { return e; } |
|
817 void nextOutEdge(Edge &e) const { } |
|
818 void nextInEdge(Edge &e) const { } |
|
819 |
|
820 Node head(Edge) const { return Node(); } |
|
821 Node tail(Edge) const { return Node(); } |
|
822 |
|
823 |
|
824 // Do we need id, nodeNum, edgeNum and co. in this basic graphbase |
|
825 // concept? |
|
826 |
|
827 |
|
828 // Maps. |
|
829 // |
|
830 // We need a special slimer concept which does not provide maps (it |
|
831 // wouldn't be strictly slimer, cause for map-factory id() & friends |
|
832 // a required...) |
|
833 |
|
834 template<typename T> |
|
835 class NodeMap : public GraphMap<Node, T, GraphBase> {}; |
|
836 |
|
837 template<typename T> |
|
838 class EdgeMap : public GraphMap<Edge, T, GraphBase> {}; |
|
839 }; |
|
840 |
|
841 |
|
842 |
|
843 /**************** Concept checking classes ****************/ |
|
844 |
|
845 template<typename BGI> |
|
846 struct BaseGraphItemConcept { |
|
847 void constraints() { |
|
848 BGI i1; |
|
849 BGI i2 = i1; |
|
850 BGI i3 = INVALID; |
|
851 |
|
852 i1 = i3; |
|
853 if( i1 == i3 ) { |
|
854 if ( i2 != i3 && i3 < i2 ) |
|
855 return; |
|
856 } |
|
857 } |
|
858 }; |
|
859 |
|
860 |
|
861 |
|
862 class StaticGraph |
|
863 : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { |
|
864 public: |
|
865 typedef BaseGraphComponent::Node Node; |
|
866 typedef BaseGraphComponent::Edge Edge; |
|
867 }; |
|
868 |
|
869 template <typename Graph> |
|
870 struct StaticGraphConcept { |
|
871 void constraints() { |
|
872 function_requires<BaseGraphComponentConcept<Graph> >(); |
|
873 function_requires<IterableGraphComponentConcept<Graph> >(); |
|
874 function_requires<MappableGraphComponentConcept<Graph> >(); |
|
875 } |
|
876 Graph& graph; |
|
877 }; |
|
878 |
|
879 class ExtendableGraph |
|
880 : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { |
|
881 public: |
|
882 typedef BaseGraphComponent::Node Node; |
|
883 typedef BaseGraphComponent::Edge Edge; |
|
884 }; |
|
885 |
|
886 template <typename Graph> |
|
887 struct ExtendableGraphConcept { |
|
888 void constraints() { |
|
889 function_requires<StaticGraphConcept<Graph> >(); |
|
890 function_requires<ExtendableGraphComponentConcept<Graph> >(); |
|
891 function_requires<ClearableGraphComponentConcept<Graph> >(); |
|
892 } |
|
893 Graph& graph; |
|
894 }; |
|
895 |
|
896 class ErasableGraph |
|
897 : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { |
|
898 public: |
|
899 typedef BaseGraphComponent::Node Node; |
|
900 typedef BaseGraphComponent::Edge Edge; |
|
901 }; |
|
902 |
|
903 template <typename Graph> |
|
904 struct ErasableGraphConcept { |
|
905 void constraints() { |
|
906 function_requires<ExtendableGraphConcept<Graph> >(); |
|
907 function_requires<ErasableGraphComponentConcept<Graph> >(); |
|
908 } |
|
909 Graph& graph; |
|
910 }; |
|
911 |
|
912 // @} |
|
913 } //namespace concept |
|
914 } //namespace lemon |
|
915 |
|
916 |
|
917 |
|
918 #endif // LEMON_CONCEPT_GRAPH_H |