COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/bpugraph.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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