COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/bpugraph.h @ 2474:e6368948d5f7

Last change on this file since 2474:e6368948d5f7 was 2474:e6368948d5f7, checked in by Peter Kovacs, 12 years ago

Small bug fixes and changes in the documentation.

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