|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 /// \ingroup graph_concepts |
|
20 /// \file |
|
21 /// \brief Undirected bipartite graphs and components of. |
|
22 |
|
23 |
|
24 #ifndef LEMON_CONCEPT_BPUGRAPH_H |
|
25 #define LEMON_CONCEPT_BPUGRAPH_H |
|
26 |
|
27 #include <lemon/concepts/graph_components.h> |
|
28 |
|
29 #include <lemon/concepts/graph.h> |
|
30 #include <lemon/concepts/ugraph.h> |
|
31 |
|
32 #include <lemon/bits/utility.h> |
|
33 |
|
34 namespace lemon { |
|
35 namespace concepts { |
|
36 |
|
37 /// \addtogroup graph_concepts |
|
38 /// @{ |
|
39 |
|
40 |
|
41 /// \brief Class describing the concept of Bipartite Undirected Graphs. |
|
42 /// |
|
43 /// This class describes the common interface of all |
|
44 /// Undirected Bipartite Graphs. |
|
45 /// |
|
46 /// As all concept describing classes it provides only interface |
|
47 /// without any sensible implementation. So any algorithm for |
|
48 /// bipartite undirected graph should compile with this class, but it |
|
49 /// will not run properly, of course. |
|
50 /// |
|
51 /// In LEMON bipartite undirected graphs also fulfill the concept of |
|
52 /// the undirected graphs (\ref lemon::concepts::UGraph "UGraph Concept"). |
|
53 /// |
|
54 /// You can assume that all undirected bipartite graph can be handled |
|
55 /// as an undirected graph and consequently as a static graph. |
|
56 /// |
|
57 /// The bipartite graph stores two types of nodes which are named |
|
58 /// ANode and BNode. The graph type contains two types ANode and |
|
59 /// BNode which are inherited from Node type. Moreover they have |
|
60 /// constructor which converts Node to either ANode or BNode when |
|
61 /// it is possible. Therefor everywhere the Node type can be used |
|
62 /// instead of ANode and BNode. So the usage of the ANode and |
|
63 /// BNode is not suggested. |
|
64 /// |
|
65 /// The iteration on the partition can be done with the ANodeIt and |
|
66 /// BNodeIt classes. The node map can be used to map values to the nodes |
|
67 /// and similarly we can use to map values for just the ANodes and |
|
68 /// BNodes the ANodeMap and BNodeMap template classes. |
|
69 |
|
70 class BpUGraph { |
|
71 public: |
|
72 /// \brief The undirected graph should be tagged by the |
|
73 /// UndirectedTag. |
|
74 /// |
|
75 /// The undirected graph should be tagged by the UndirectedTag. This |
|
76 /// tag helps the enable_if technics to make compile time |
|
77 /// specializations for undirected graphs. |
|
78 typedef True UndirectedTag; |
|
79 |
|
80 /// \brief The base type of node iterators, |
|
81 /// or in other words, the trivial node iterator. |
|
82 /// |
|
83 /// This is the base type of each node iterator, |
|
84 /// thus each kind of node iterator converts to this. |
|
85 /// More precisely each kind of node iterator should be inherited |
|
86 /// from the trivial node iterator. The Node class represents |
|
87 /// both of two types of nodes. |
|
88 class Node { |
|
89 public: |
|
90 /// Default constructor |
|
91 |
|
92 /// @warning The default constructor sets the iterator |
|
93 /// to an undefined value. |
|
94 Node() { } |
|
95 /// Copy constructor. |
|
96 |
|
97 /// Copy constructor. |
|
98 /// |
|
99 Node(const Node&) { } |
|
100 |
|
101 /// Invalid constructor \& conversion. |
|
102 |
|
103 /// This constructor initializes the iterator to be invalid. |
|
104 /// \sa Invalid for more details. |
|
105 Node(Invalid) { } |
|
106 /// Equality operator |
|
107 |
|
108 /// Two iterators are equal if and only if they point to the |
|
109 /// same object or both are invalid. |
|
110 bool operator==(Node) const { return true; } |
|
111 |
|
112 /// Inequality operator |
|
113 |
|
114 /// \sa operator==(Node n) |
|
115 /// |
|
116 bool operator!=(Node) const { return true; } |
|
117 |
|
118 /// Artificial ordering operator. |
|
119 |
|
120 /// To allow the use of graph descriptors as key type in std::map or |
|
121 /// similar associative container we require this. |
|
122 /// |
|
123 /// \note This operator only have to define some strict ordering of |
|
124 /// the items; this order has nothing to do with the iteration |
|
125 /// ordering of the items. |
|
126 bool operator<(Node) const { return false; } |
|
127 |
|
128 }; |
|
129 |
|
130 /// \brief Helper class for ANodes. |
|
131 /// |
|
132 /// This class is just a helper class for ANodes, it is not |
|
133 /// suggested to use it directly. It can be converted easily to |
|
134 /// node and vice versa. The usage of this class is limited |
|
135 /// to use just as template parameters for special map types. |
|
136 class ANode : public Node { |
|
137 public: |
|
138 /// Default constructor |
|
139 |
|
140 /// @warning The default constructor sets the iterator |
|
141 /// to an undefined value. |
|
142 ANode() : Node() { } |
|
143 /// Copy constructor. |
|
144 |
|
145 /// Copy constructor. |
|
146 /// |
|
147 ANode(const ANode&) : Node() { } |
|
148 |
|
149 /// Construct the same node as ANode. |
|
150 |
|
151 /// Construct the same node as ANode. It may throws assertion |
|
152 /// when the given node is from the BNode set. |
|
153 ANode(const Node&) : Node() { } |
|
154 |
|
155 /// Assign node to A-node. |
|
156 |
|
157 /// Besides the core graph item functionality each node should |
|
158 /// be convertible to the represented A-node if it is it possible. |
|
159 ANode& operator=(const Node&) { return *this; } |
|
160 |
|
161 /// Invalid constructor \& conversion. |
|
162 |
|
163 /// This constructor initializes the iterator to be invalid. |
|
164 /// \sa Invalid for more details. |
|
165 ANode(Invalid) { } |
|
166 /// Equality operator |
|
167 |
|
168 /// Two iterators are equal if and only if they point to the |
|
169 /// same object or both are invalid. |
|
170 bool operator==(ANode) const { return true; } |
|
171 |
|
172 /// Inequality operator |
|
173 |
|
174 /// \sa operator==(ANode n) |
|
175 /// |
|
176 bool operator!=(ANode) const { return true; } |
|
177 |
|
178 /// Artificial ordering operator. |
|
179 |
|
180 /// To allow the use of graph descriptors as key type in std::map or |
|
181 /// similar associative container we require this. |
|
182 /// |
|
183 /// \note This operator only have to define some strict ordering of |
|
184 /// the items; this order has nothing to do with the iteration |
|
185 /// ordering of the items. |
|
186 bool operator<(ANode) const { return false; } |
|
187 |
|
188 }; |
|
189 |
|
190 /// \brief Helper class for BNodes. |
|
191 /// |
|
192 /// This class is just a helper class for BNodes, it is not |
|
193 /// suggested to use it directly. It can be converted easily to |
|
194 /// node and vice versa. The usage of this class is limited |
|
195 /// to use just as template parameters for special map types. |
|
196 class BNode : public Node { |
|
197 public: |
|
198 /// Default constructor |
|
199 |
|
200 /// @warning The default constructor sets the iterator |
|
201 /// to an undefined value. |
|
202 BNode() : Node() { } |
|
203 /// Copy constructor. |
|
204 |
|
205 /// Copy constructor. |
|
206 /// |
|
207 BNode(const BNode&) : Node() { } |
|
208 |
|
209 /// Construct the same node as BNode. |
|
210 |
|
211 /// Construct the same node as BNode. It may throws assertion |
|
212 /// when the given node is from the ANode set. |
|
213 BNode(const Node&) : Node() { } |
|
214 |
|
215 /// Assign node to B-node. |
|
216 |
|
217 /// Besides the core graph item functionality each node should |
|
218 /// be convertible to the represented B-node if it is it possible. |
|
219 BNode& operator=(const Node&) { return *this; } |
|
220 |
|
221 /// Invalid constructor \& conversion. |
|
222 |
|
223 /// This constructor initializes the iterator to be invalid. |
|
224 /// \sa Invalid for more details. |
|
225 BNode(Invalid) { } |
|
226 /// Equality operator |
|
227 |
|
228 /// Two iterators are equal if and only if they point to the |
|
229 /// same object or both are invalid. |
|
230 bool operator==(BNode) const { return true; } |
|
231 |
|
232 /// Inequality operator |
|
233 |
|
234 /// \sa operator==(BNode n) |
|
235 /// |
|
236 bool operator!=(BNode) const { return true; } |
|
237 |
|
238 /// Artificial ordering operator. |
|
239 |
|
240 /// To allow the use of graph descriptors as key type in std::map or |
|
241 /// similar associative container we require this. |
|
242 /// |
|
243 /// \note This operator only have to define some strict ordering of |
|
244 /// the items; this order has nothing to do with the iteration |
|
245 /// ordering of the items. |
|
246 bool operator<(BNode) const { return false; } |
|
247 |
|
248 }; |
|
249 |
|
250 /// This iterator goes through each node. |
|
251 |
|
252 /// This iterator goes through each node. |
|
253 /// Its usage is quite simple, for example you can count the number |
|
254 /// of nodes in graph \c g of type \c Graph like this: |
|
255 ///\code |
|
256 /// int count=0; |
|
257 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
|
258 ///\endcode |
|
259 class NodeIt : public Node { |
|
260 public: |
|
261 /// Default constructor |
|
262 |
|
263 /// @warning The default constructor sets the iterator |
|
264 /// to an undefined value. |
|
265 NodeIt() { } |
|
266 /// Copy constructor. |
|
267 |
|
268 /// Copy constructor. |
|
269 /// |
|
270 NodeIt(const NodeIt& n) : Node(n) { } |
|
271 /// Invalid constructor \& conversion. |
|
272 |
|
273 /// Initialize the iterator to be invalid. |
|
274 /// \sa Invalid for more details. |
|
275 NodeIt(Invalid) { } |
|
276 /// Sets the iterator to the first node. |
|
277 |
|
278 /// Sets the iterator to the first node of \c g. |
|
279 /// |
|
280 NodeIt(const BpUGraph&) { } |
|
281 /// Node -> NodeIt conversion. |
|
282 |
|
283 /// Sets the iterator to the node of \c the graph pointed by |
|
284 /// the trivial iterator. |
|
285 /// This feature necessitates that each time we |
|
286 /// iterate the edge-set, the iteration order is the same. |
|
287 NodeIt(const BpUGraph&, const Node&) { } |
|
288 /// Next node. |
|
289 |
|
290 /// Assign the iterator to the next node. |
|
291 /// |
|
292 NodeIt& operator++() { return *this; } |
|
293 }; |
|
294 |
|
295 /// This iterator goes through each ANode. |
|
296 |
|
297 /// This iterator goes through each ANode. |
|
298 /// Its usage is quite simple, for example you can count the number |
|
299 /// of nodes in graph \c g of type \c Graph like this: |
|
300 ///\code |
|
301 /// int count=0; |
|
302 /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count; |
|
303 ///\endcode |
|
304 class ANodeIt : public Node { |
|
305 public: |
|
306 /// Default constructor |
|
307 |
|
308 /// @warning The default constructor sets the iterator |
|
309 /// to an undefined value. |
|
310 ANodeIt() { } |
|
311 /// Copy constructor. |
|
312 |
|
313 /// Copy constructor. |
|
314 /// |
|
315 ANodeIt(const ANodeIt& n) : Node(n) { } |
|
316 /// Invalid constructor \& conversion. |
|
317 |
|
318 /// Initialize the iterator to be invalid. |
|
319 /// \sa Invalid for more details. |
|
320 ANodeIt(Invalid) { } |
|
321 /// Sets the iterator to the first node. |
|
322 |
|
323 /// Sets the iterator to the first node of \c g. |
|
324 /// |
|
325 ANodeIt(const BpUGraph&) { } |
|
326 /// Node -> ANodeIt conversion. |
|
327 |
|
328 /// Sets the iterator to the node of \c the graph pointed by |
|
329 /// the trivial iterator. |
|
330 /// This feature necessitates that each time we |
|
331 /// iterate the edge-set, the iteration order is the same. |
|
332 ANodeIt(const BpUGraph&, const Node&) { } |
|
333 /// Next node. |
|
334 |
|
335 /// Assign the iterator to the next node. |
|
336 /// |
|
337 ANodeIt& operator++() { return *this; } |
|
338 }; |
|
339 |
|
340 /// This iterator goes through each BNode. |
|
341 |
|
342 /// This iterator goes through each BNode. |
|
343 /// Its usage is quite simple, for example you can count the number |
|
344 /// of nodes in graph \c g of type \c Graph like this: |
|
345 ///\code |
|
346 /// int count=0; |
|
347 /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count; |
|
348 ///\endcode |
|
349 class BNodeIt : public Node { |
|
350 public: |
|
351 /// Default constructor |
|
352 |
|
353 /// @warning The default constructor sets the iterator |
|
354 /// to an undefined value. |
|
355 BNodeIt() { } |
|
356 /// Copy constructor. |
|
357 |
|
358 /// Copy constructor. |
|
359 /// |
|
360 BNodeIt(const BNodeIt& n) : Node(n) { } |
|
361 /// Invalid constructor \& conversion. |
|
362 |
|
363 /// Initialize the iterator to be invalid. |
|
364 /// \sa Invalid for more details. |
|
365 BNodeIt(Invalid) { } |
|
366 /// Sets the iterator to the first node. |
|
367 |
|
368 /// Sets the iterator to the first node of \c g. |
|
369 /// |
|
370 BNodeIt(const BpUGraph&) { } |
|
371 /// Node -> BNodeIt conversion. |
|
372 |
|
373 /// Sets the iterator to the node of \c the graph pointed by |
|
374 /// the trivial iterator. |
|
375 /// This feature necessitates that each time we |
|
376 /// iterate the edge-set, the iteration order is the same. |
|
377 BNodeIt(const BpUGraph&, const Node&) { } |
|
378 /// Next node. |
|
379 |
|
380 /// Assign the iterator to the next node. |
|
381 /// |
|
382 BNodeIt& operator++() { return *this; } |
|
383 }; |
|
384 |
|
385 |
|
386 /// The base type of the undirected edge iterators. |
|
387 |
|
388 /// The base type of the undirected edge iterators. |
|
389 /// |
|
390 class UEdge { |
|
391 public: |
|
392 /// Default constructor |
|
393 |
|
394 /// @warning The default constructor sets the iterator |
|
395 /// to an undefined value. |
|
396 UEdge() { } |
|
397 /// Copy constructor. |
|
398 |
|
399 /// Copy constructor. |
|
400 /// |
|
401 UEdge(const UEdge&) { } |
|
402 /// Initialize the iterator to be invalid. |
|
403 |
|
404 /// Initialize the iterator to be invalid. |
|
405 /// |
|
406 UEdge(Invalid) { } |
|
407 /// Equality operator |
|
408 |
|
409 /// Two iterators are equal if and only if they point to the |
|
410 /// same object or both are invalid. |
|
411 bool operator==(UEdge) const { return true; } |
|
412 /// Inequality operator |
|
413 |
|
414 /// \sa operator==(UEdge n) |
|
415 /// |
|
416 bool operator!=(UEdge) const { return true; } |
|
417 |
|
418 /// Artificial ordering operator. |
|
419 |
|
420 /// To allow the use of graph descriptors as key type in std::map or |
|
421 /// similar associative container we require this. |
|
422 /// |
|
423 /// \note This operator only have to define some strict ordering of |
|
424 /// the items; this order has nothing to do with the iteration |
|
425 /// ordering of the items. |
|
426 bool operator<(UEdge) const { return false; } |
|
427 }; |
|
428 |
|
429 /// This iterator goes through each undirected edge. |
|
430 |
|
431 /// This iterator goes through each undirected edge of a graph. |
|
432 /// Its usage is quite simple, for example you can count the number |
|
433 /// of undirected edges in a graph \c g of type \c Graph as follows: |
|
434 ///\code |
|
435 /// int count=0; |
|
436 /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count; |
|
437 ///\endcode |
|
438 class UEdgeIt : public UEdge { |
|
439 public: |
|
440 /// Default constructor |
|
441 |
|
442 /// @warning The default constructor sets the iterator |
|
443 /// to an undefined value. |
|
444 UEdgeIt() { } |
|
445 /// Copy constructor. |
|
446 |
|
447 /// Copy constructor. |
|
448 /// |
|
449 UEdgeIt(const UEdgeIt& e) : UEdge(e) { } |
|
450 /// Initialize the iterator to be invalid. |
|
451 |
|
452 /// Initialize the iterator to be invalid. |
|
453 /// |
|
454 UEdgeIt(Invalid) { } |
|
455 /// This constructor sets the iterator to the first undirected edge. |
|
456 |
|
457 /// This constructor sets the iterator to the first undirected edge. |
|
458 UEdgeIt(const BpUGraph&) { } |
|
459 /// UEdge -> UEdgeIt conversion |
|
460 |
|
461 /// Sets the iterator to the value of the trivial iterator. |
|
462 /// This feature necessitates that each time we |
|
463 /// iterate the undirected edge-set, the iteration order is the |
|
464 /// same. |
|
465 UEdgeIt(const BpUGraph&, const UEdge&) { } |
|
466 /// Next undirected edge |
|
467 |
|
468 /// Assign the iterator to the next undirected edge. |
|
469 UEdgeIt& operator++() { return *this; } |
|
470 }; |
|
471 |
|
472 /// \brief This iterator goes trough the incident undirected |
|
473 /// edges of a node. |
|
474 /// |
|
475 /// This iterator goes trough the incident undirected edges |
|
476 /// of a certain node |
|
477 /// of a graph. |
|
478 /// Its usage is quite simple, for example you can compute the |
|
479 /// degree (i.e. count the number |
|
480 /// of incident edges of a node \c n |
|
481 /// in graph \c g of type \c Graph as follows. |
|
482 ///\code |
|
483 /// int count=0; |
|
484 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
485 ///\endcode |
|
486 class IncEdgeIt : public UEdge { |
|
487 public: |
|
488 /// Default constructor |
|
489 |
|
490 /// @warning The default constructor sets the iterator |
|
491 /// to an undefined value. |
|
492 IncEdgeIt() { } |
|
493 /// Copy constructor. |
|
494 |
|
495 /// Copy constructor. |
|
496 /// |
|
497 IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { } |
|
498 /// Initialize the iterator to be invalid. |
|
499 |
|
500 /// Initialize the iterator to be invalid. |
|
501 /// |
|
502 IncEdgeIt(Invalid) { } |
|
503 /// This constructor sets the iterator to first incident edge. |
|
504 |
|
505 /// This constructor set the iterator to the first incident edge of |
|
506 /// the node. |
|
507 IncEdgeIt(const BpUGraph&, const Node&) { } |
|
508 /// UEdge -> IncEdgeIt conversion |
|
509 |
|
510 /// Sets the iterator to the value of the trivial iterator \c e. |
|
511 /// This feature necessitates that each time we |
|
512 /// iterate the edge-set, the iteration order is the same. |
|
513 IncEdgeIt(const BpUGraph&, const UEdge&) { } |
|
514 /// Next incident edge |
|
515 |
|
516 /// Assign the iterator to the next incident edge |
|
517 /// of the corresponding node. |
|
518 IncEdgeIt& operator++() { return *this; } |
|
519 }; |
|
520 |
|
521 /// The directed edge type. |
|
522 |
|
523 /// The directed edge type. It can be converted to the |
|
524 /// undirected edge. |
|
525 class Edge : public UEdge { |
|
526 public: |
|
527 /// Default constructor |
|
528 |
|
529 /// @warning The default constructor sets the iterator |
|
530 /// to an undefined value. |
|
531 Edge() { } |
|
532 /// Copy constructor. |
|
533 |
|
534 /// Copy constructor. |
|
535 /// |
|
536 Edge(const Edge& e) : UEdge(e) { } |
|
537 /// Initialize the iterator to be invalid. |
|
538 |
|
539 /// Initialize the iterator to be invalid. |
|
540 /// |
|
541 Edge(Invalid) { } |
|
542 /// Equality operator |
|
543 |
|
544 /// Two iterators are equal if and only if they point to the |
|
545 /// same object or both are invalid. |
|
546 bool operator==(Edge) const { return true; } |
|
547 /// Inequality operator |
|
548 |
|
549 /// \sa operator==(Edge n) |
|
550 /// |
|
551 bool operator!=(Edge) const { return true; } |
|
552 |
|
553 /// Artificial ordering operator. |
|
554 |
|
555 /// To allow the use of graph descriptors as key type in std::map or |
|
556 /// similar associative container we require this. |
|
557 /// |
|
558 /// \note This operator only have to define some strict ordering of |
|
559 /// the items; this order has nothing to do with the iteration |
|
560 /// ordering of the items. |
|
561 bool operator<(Edge) const { return false; } |
|
562 |
|
563 }; |
|
564 /// This iterator goes through each directed edge. |
|
565 |
|
566 /// This iterator goes through each edge of a graph. |
|
567 /// Its usage is quite simple, for example you can count the number |
|
568 /// of edges in a graph \c g of type \c Graph as follows: |
|
569 ///\code |
|
570 /// int count=0; |
|
571 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
|
572 ///\endcode |
|
573 class EdgeIt : public Edge { |
|
574 public: |
|
575 /// Default constructor |
|
576 |
|
577 /// @warning The default constructor sets the iterator |
|
578 /// to an undefined value. |
|
579 EdgeIt() { } |
|
580 /// Copy constructor. |
|
581 |
|
582 /// Copy constructor. |
|
583 /// |
|
584 EdgeIt(const EdgeIt& e) : Edge(e) { } |
|
585 /// Initialize the iterator to be invalid. |
|
586 |
|
587 /// Initialize the iterator to be invalid. |
|
588 /// |
|
589 EdgeIt(Invalid) { } |
|
590 /// This constructor sets the iterator to the first edge. |
|
591 |
|
592 /// This constructor sets the iterator to the first edge of \c g. |
|
593 ///@param g the graph |
|
594 EdgeIt(const BpUGraph &g) { ignore_unused_variable_warning(g); } |
|
595 /// Edge -> EdgeIt conversion |
|
596 |
|
597 /// Sets the iterator to the value of the trivial iterator \c e. |
|
598 /// This feature necessitates that each time we |
|
599 /// iterate the edge-set, the iteration order is the same. |
|
600 EdgeIt(const BpUGraph&, const Edge&) { } |
|
601 ///Next edge |
|
602 |
|
603 /// Assign the iterator to the next edge. |
|
604 EdgeIt& operator++() { return *this; } |
|
605 }; |
|
606 |
|
607 /// This iterator goes trough the outgoing directed edges of a node. |
|
608 |
|
609 /// This iterator goes trough the \e outgoing edges of a certain node |
|
610 /// of a graph. |
|
611 /// Its usage is quite simple, for example you can count the number |
|
612 /// of outgoing edges of a node \c n |
|
613 /// in graph \c g of type \c Graph as follows. |
|
614 ///\code |
|
615 /// int count=0; |
|
616 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
617 ///\endcode |
|
618 |
|
619 class OutEdgeIt : public Edge { |
|
620 public: |
|
621 /// Default constructor |
|
622 |
|
623 /// @warning The default constructor sets the iterator |
|
624 /// to an undefined value. |
|
625 OutEdgeIt() { } |
|
626 /// Copy constructor. |
|
627 |
|
628 /// Copy constructor. |
|
629 /// |
|
630 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { } |
|
631 /// Initialize the iterator to be invalid. |
|
632 |
|
633 /// Initialize the iterator to be invalid. |
|
634 /// |
|
635 OutEdgeIt(Invalid) { } |
|
636 /// This constructor sets the iterator to the first outgoing edge. |
|
637 |
|
638 /// This constructor sets the iterator to the first outgoing edge of |
|
639 /// the node. |
|
640 ///@param n the node |
|
641 ///@param g the graph |
|
642 OutEdgeIt(const BpUGraph& n, const Node& g) { |
|
643 ignore_unused_variable_warning(n); |
|
644 ignore_unused_variable_warning(g); |
|
645 } |
|
646 /// Edge -> OutEdgeIt conversion |
|
647 |
|
648 /// Sets the iterator to the value of the trivial iterator. |
|
649 /// This feature necessitates that each time we |
|
650 /// iterate the edge-set, the iteration order is the same. |
|
651 OutEdgeIt(const BpUGraph&, const Edge&) { } |
|
652 ///Next outgoing edge |
|
653 |
|
654 /// Assign the iterator to the next |
|
655 /// outgoing edge of the corresponding node. |
|
656 OutEdgeIt& operator++() { return *this; } |
|
657 }; |
|
658 |
|
659 /// This iterator goes trough the incoming directed edges of a node. |
|
660 |
|
661 /// This iterator goes trough the \e incoming edges of a certain node |
|
662 /// of a graph. |
|
663 /// Its usage is quite simple, for example you can count the number |
|
664 /// of outgoing edges of a node \c n |
|
665 /// in graph \c g of type \c Graph as follows. |
|
666 ///\code |
|
667 /// int count=0; |
|
668 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
669 ///\endcode |
|
670 |
|
671 class InEdgeIt : public Edge { |
|
672 public: |
|
673 /// Default constructor |
|
674 |
|
675 /// @warning The default constructor sets the iterator |
|
676 /// to an undefined value. |
|
677 InEdgeIt() { } |
|
678 /// Copy constructor. |
|
679 |
|
680 /// Copy constructor. |
|
681 /// |
|
682 InEdgeIt(const InEdgeIt& e) : Edge(e) { } |
|
683 /// Initialize the iterator to be invalid. |
|
684 |
|
685 /// Initialize the iterator to be invalid. |
|
686 /// |
|
687 InEdgeIt(Invalid) { } |
|
688 /// This constructor sets the iterator to first incoming edge. |
|
689 |
|
690 /// This constructor set the iterator to the first incoming edge of |
|
691 /// the node. |
|
692 ///@param n the node |
|
693 ///@param g the graph |
|
694 InEdgeIt(const BpUGraph& g, const Node& n) { |
|
695 ignore_unused_variable_warning(n); |
|
696 ignore_unused_variable_warning(g); |
|
697 } |
|
698 /// Edge -> InEdgeIt conversion |
|
699 |
|
700 /// Sets the iterator to the value of the trivial iterator \c e. |
|
701 /// This feature necessitates that each time we |
|
702 /// iterate the edge-set, the iteration order is the same. |
|
703 InEdgeIt(const BpUGraph&, const Edge&) { } |
|
704 /// Next incoming edge |
|
705 |
|
706 /// Assign the iterator to the next inedge of the corresponding node. |
|
707 /// |
|
708 InEdgeIt& operator++() { return *this; } |
|
709 }; |
|
710 |
|
711 /// \brief Read write map of the nodes to type \c T. |
|
712 /// |
|
713 /// ReadWrite map of the nodes to type \c T. |
|
714 /// \sa Reference |
|
715 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
716 /// needs some extra attention! |
|
717 /// \todo Wrong documentation |
|
718 template<class T> |
|
719 class NodeMap : public ReadWriteMap< Node, T > |
|
720 { |
|
721 public: |
|
722 |
|
723 ///\e |
|
724 NodeMap(const BpUGraph&) { } |
|
725 ///\e |
|
726 NodeMap(const BpUGraph&, T) { } |
|
727 |
|
728 ///Copy constructor |
|
729 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
|
730 ///Assignment operator |
|
731 NodeMap& operator=(const NodeMap&) { return *this; } |
|
732 ///Assignment operator |
|
733 template <typename CMap> |
|
734 NodeMap& operator=(const CMap&) { |
|
735 checkConcept<ReadMap<Node, T>, CMap>(); |
|
736 return *this; |
|
737 } |
|
738 }; |
|
739 |
|
740 /// \brief Read write map of the ANodes to type \c T. |
|
741 /// |
|
742 /// ReadWrite map of the ANodes to type \c T. |
|
743 /// \sa Reference |
|
744 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
745 /// needs some extra attention! |
|
746 /// \todo Wrong documentation |
|
747 template<class T> |
|
748 class ANodeMap : public ReadWriteMap< Node, T > |
|
749 { |
|
750 public: |
|
751 |
|
752 ///\e |
|
753 ANodeMap(const BpUGraph&) { } |
|
754 ///\e |
|
755 ANodeMap(const BpUGraph&, T) { } |
|
756 |
|
757 ///Copy constructor |
|
758 ANodeMap(const ANodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
|
759 ///Assignment operator |
|
760 ANodeMap& operator=(const ANodeMap&) { return *this; } |
|
761 ///Assignment operator |
|
762 template <typename CMap> |
|
763 ANodeMap& operator=(const CMap&) { |
|
764 checkConcept<ReadMap<Node, T>, CMap>(); |
|
765 return *this; |
|
766 } |
|
767 }; |
|
768 |
|
769 /// \brief Read write map of the BNodes to type \c T. |
|
770 /// |
|
771 /// ReadWrite map of the BNodes to type \c T. |
|
772 /// \sa Reference |
|
773 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
774 /// needs some extra attention! |
|
775 /// \todo Wrong documentation |
|
776 template<class T> |
|
777 class BNodeMap : public ReadWriteMap< Node, T > |
|
778 { |
|
779 public: |
|
780 |
|
781 ///\e |
|
782 BNodeMap(const BpUGraph&) { } |
|
783 ///\e |
|
784 BNodeMap(const BpUGraph&, T) { } |
|
785 |
|
786 ///Copy constructor |
|
787 BNodeMap(const BNodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
|
788 ///Assignment operator |
|
789 BNodeMap& operator=(const BNodeMap&) { return *this; } |
|
790 ///Assignment operator |
|
791 template <typename CMap> |
|
792 BNodeMap& operator=(const CMap&) { |
|
793 checkConcept<ReadMap<Node, T>, CMap>(); |
|
794 return *this; |
|
795 } |
|
796 }; |
|
797 |
|
798 /// \brief Read write map of the directed edges to type \c T. |
|
799 /// |
|
800 /// Reference map of the directed edges to type \c T. |
|
801 /// \sa Reference |
|
802 /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
|
803 /// needs some extra attention! |
|
804 /// \todo Wrong documentation |
|
805 template<class T> |
|
806 class EdgeMap : public ReadWriteMap<Edge,T> |
|
807 { |
|
808 public: |
|
809 |
|
810 ///\e |
|
811 EdgeMap(const BpUGraph&) { } |
|
812 ///\e |
|
813 EdgeMap(const BpUGraph&, T) { } |
|
814 ///Copy constructor |
|
815 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { } |
|
816 ///Assignment operator |
|
817 EdgeMap& operator=(const EdgeMap&) { return *this; } |
|
818 ///Assignment operator |
|
819 template <typename CMap> |
|
820 EdgeMap& operator=(const CMap&) { |
|
821 checkConcept<ReadMap<Edge, T>, CMap>(); |
|
822 return *this; |
|
823 } |
|
824 }; |
|
825 |
|
826 /// Read write map of the undirected edges to type \c T. |
|
827 |
|
828 /// Reference map of the edges to type \c T. |
|
829 /// \sa Reference |
|
830 /// \warning Making maps that can handle bool type (UEdgeMap<bool>) |
|
831 /// needs some extra attention! |
|
832 /// \todo Wrong documentation |
|
833 template<class T> |
|
834 class UEdgeMap : public ReadWriteMap<UEdge,T> |
|
835 { |
|
836 public: |
|
837 |
|
838 ///\e |
|
839 UEdgeMap(const BpUGraph&) { } |
|
840 ///\e |
|
841 UEdgeMap(const BpUGraph&, T) { } |
|
842 ///Copy constructor |
|
843 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {} |
|
844 ///Assignment operator |
|
845 UEdgeMap &operator=(const UEdgeMap&) { return *this; } |
|
846 ///Assignment operator |
|
847 template <typename CMap> |
|
848 UEdgeMap& operator=(const CMap&) { |
|
849 checkConcept<ReadMap<UEdge, T>, CMap>(); |
|
850 return *this; |
|
851 } |
|
852 }; |
|
853 |
|
854 /// \brief Direct the given undirected edge. |
|
855 /// |
|
856 /// Direct the given undirected edge. The returned edge source |
|
857 /// will be the given node. |
|
858 Edge direct(const UEdge&, const Node&) const { |
|
859 return INVALID; |
|
860 } |
|
861 |
|
862 /// \brief Direct the given undirected edge. |
|
863 /// |
|
864 /// Direct the given undirected edge. The returned edge |
|
865 /// represents the given undireted edge and the direction comes |
|
866 /// from the given bool. The source of the undirected edge and |
|
867 /// the directed edge is the same when the given bool is true. |
|
868 Edge direct(const UEdge&, bool) const { |
|
869 return INVALID; |
|
870 } |
|
871 |
|
872 /// \brief Returns true when the given node is an ANode. |
|
873 /// |
|
874 /// Returns true when the given node is an ANode. |
|
875 bool aNode(Node) const { return true;} |
|
876 |
|
877 /// \brief Returns true when the given node is an BNode. |
|
878 /// |
|
879 /// Returns true when the given node is an BNode. |
|
880 bool bNode(Node) const { return true;} |
|
881 |
|
882 /// \brief Returns the edge's end node which is in the ANode set. |
|
883 /// |
|
884 /// Returns the edge's end node which is in the ANode set. |
|
885 Node aNode(UEdge) const { return INVALID;} |
|
886 |
|
887 /// \brief Returns the edge's end node which is in the BNode set. |
|
888 /// |
|
889 /// Returns the edge's end node which is in the BNode set. |
|
890 Node bNode(UEdge) const { return INVALID;} |
|
891 |
|
892 /// \brief Returns true if the edge has default orientation. |
|
893 /// |
|
894 /// Returns whether the given directed edge is same orientation as |
|
895 /// the corresponding undirected edge's default orientation. |
|
896 bool direction(Edge) const { return true; } |
|
897 |
|
898 /// \brief Returns the opposite directed edge. |
|
899 /// |
|
900 /// Returns the opposite directed edge. |
|
901 Edge oppositeEdge(Edge) const { return INVALID; } |
|
902 |
|
903 /// \brief Opposite node on an edge |
|
904 /// |
|
905 /// \return the opposite of the given Node on the given UEdge |
|
906 Node oppositeNode(Node, UEdge) const { return INVALID; } |
|
907 |
|
908 /// \brief First node of the undirected edge. |
|
909 /// |
|
910 /// \return the first node of the given UEdge. |
|
911 /// |
|
912 /// Naturally undirected edges don't have direction and thus |
|
913 /// don't have source and target node. But we use these two methods |
|
914 /// to query the two endnodes of the edge. The direction of the edge |
|
915 /// which arises this way is called the inherent direction of the |
|
916 /// undirected edge, and is used to define the "default" direction |
|
917 /// of the directed versions of the edges. |
|
918 /// \sa direction |
|
919 Node source(UEdge) const { return INVALID; } |
|
920 |
|
921 /// \brief Second node of the undirected edge. |
|
922 Node target(UEdge) const { return INVALID; } |
|
923 |
|
924 /// \brief Source node of the directed edge. |
|
925 Node source(Edge) const { return INVALID; } |
|
926 |
|
927 /// \brief Target node of the directed edge. |
|
928 Node target(Edge) const { return INVALID; } |
|
929 |
|
930 /// \brief Base node of the iterator |
|
931 /// |
|
932 /// Returns the base node (the source in this case) of the iterator |
|
933 Node baseNode(OutEdgeIt e) const { |
|
934 return source(e); |
|
935 } |
|
936 |
|
937 /// \brief Running node of the iterator |
|
938 /// |
|
939 /// Returns the running node (the target in this case) of the |
|
940 /// iterator |
|
941 Node runningNode(OutEdgeIt e) const { |
|
942 return target(e); |
|
943 } |
|
944 |
|
945 /// \brief Base node of the iterator |
|
946 /// |
|
947 /// Returns the base node (the target in this case) of the iterator |
|
948 Node baseNode(InEdgeIt e) const { |
|
949 return target(e); |
|
950 } |
|
951 /// \brief Running node of the iterator |
|
952 /// |
|
953 /// Returns the running node (the source in this case) of the |
|
954 /// iterator |
|
955 Node runningNode(InEdgeIt e) const { |
|
956 return source(e); |
|
957 } |
|
958 |
|
959 /// \brief Base node of the iterator |
|
960 /// |
|
961 /// Returns the base node of the iterator |
|
962 Node baseNode(IncEdgeIt) const { |
|
963 return INVALID; |
|
964 } |
|
965 |
|
966 /// \brief Running node of the iterator |
|
967 /// |
|
968 /// Returns the running node of the iterator |
|
969 Node runningNode(IncEdgeIt) const { |
|
970 return INVALID; |
|
971 } |
|
972 |
|
973 void first(Node&) const {} |
|
974 void next(Node&) const {} |
|
975 |
|
976 void first(Edge&) const {} |
|
977 void next(Edge&) const {} |
|
978 |
|
979 void first(UEdge&) const {} |
|
980 void next(UEdge&) const {} |
|
981 |
|
982 void firstANode(Node&) const {} |
|
983 void nextANode(Node&) const {} |
|
984 |
|
985 void firstBNode(Node&) const {} |
|
986 void nextBNode(Node&) const {} |
|
987 |
|
988 void firstIn(Edge&, const Node&) const {} |
|
989 void nextIn(Edge&) const {} |
|
990 |
|
991 void firstOut(Edge&, const Node&) const {} |
|
992 void nextOut(Edge&) const {} |
|
993 |
|
994 void firstInc(UEdge &, bool &, const Node &) const {} |
|
995 void nextInc(UEdge &, bool &) const {} |
|
996 |
|
997 void firstFromANode(UEdge&, const Node&) const {} |
|
998 void nextFromANode(UEdge&) const {} |
|
999 |
|
1000 void firstFromBNode(UEdge&, const Node&) const {} |
|
1001 void nextFromBNode(UEdge&) const {} |
|
1002 |
|
1003 template <typename Graph> |
|
1004 struct Constraints { |
|
1005 void constraints() { |
|
1006 checkConcept<IterableBpUGraphComponent<>, Graph>(); |
|
1007 checkConcept<MappableBpUGraphComponent<>, Graph>(); |
|
1008 } |
|
1009 }; |
|
1010 |
|
1011 }; |
|
1012 |
|
1013 |
|
1014 /// @} |
|
1015 |
|
1016 } |
|
1017 |
|
1018 } |
|
1019 |
|
1020 #endif |