COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/bpugraph.h @ 2204:5617107d27e9

Last change on this file since 2204:5617107d27e9 was 2163:bef3457be038, checked in by Balazs Dezso, 18 years ago

Improving UGraph and BpUGraph concept classes

File size: 30.4 KB
Line 
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/concept/graph_components.h>
28
29#include <lemon/concept/graph.h>
30#include <lemon/concept/ugraph.h>
31
32#include <lemon/bits/utility.h>
33
34namespace lemon {
35  namespace concept {
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::concept::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      /// two use just as template parameters for special map types.
136      class ANode {
137      public:
138        /// Default constructor
139
140        /// @warning The default constructor sets the iterator
141        /// to an undefined value.
142        ANode() { }
143        /// Copy constructor.
144
145        /// Copy constructor.
146        ///
147        ANode(const ANode&) { }
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&) { }
154
155        /// Invalid constructor \& conversion.
156
157        /// This constructor initializes the iterator to be invalid.
158        /// \sa Invalid for more details.
159        ANode(Invalid) { }
160        /// Equality operator
161
162        /// Two iterators are equal if and only if they point to the
163        /// same object or both are invalid.
164        bool operator==(ANode) const { return true; }
165
166        /// Inequality operator
167       
168        /// \sa operator==(ANode n)
169        ///
170        bool operator!=(ANode) const { return true; }
171
172        /// Artificial ordering operator.
173       
174        /// To allow the use of graph descriptors as key type in std::map or
175        /// similar associative container we require this.
176        ///
177        /// \note This operator only have to define some strict ordering of
178        /// the items; this order has nothing to do with the iteration
179        /// ordering of the items.
180        bool operator<(ANode) const { return false; }
181
182      };
183
184      /// \brief Helper class for BNodes.
185      ///
186      /// This class is just a helper class for BNodes, it is not
187      /// suggested to use it directly. It can be converted easily to
188      /// node and vice versa. The usage of this class is limited
189      /// two use just as template parameters for special map types.
190      class BNode {
191      public:
192        /// Default constructor
193
194        /// @warning The default constructor sets the iterator
195        /// to an undefined value.
196        BNode() { }
197        /// Copy constructor.
198
199        /// Copy constructor.
200        ///
201        BNode(const BNode&) { }
202
203        /// Construct the same node as BNode.
204
205        /// Construct the same node as BNode. It may throws assertion
206        /// when the given node is from the ANode set.
207        BNode(const Node&) { }
208
209        /// Invalid constructor \& conversion.
210
211        /// This constructor initializes the iterator to be invalid.
212        /// \sa Invalid for more details.
213        BNode(Invalid) { }
214        /// Equality operator
215
216        /// Two iterators are equal if and only if they point to the
217        /// same object or both are invalid.
218        bool operator==(BNode) const { return true; }
219
220        /// Inequality operator
221       
222        /// \sa operator==(BNode n)
223        ///
224        bool operator!=(BNode) const { return true; }
225
226        /// Artificial ordering operator.
227       
228        /// To allow the use of graph descriptors as key type in std::map or
229        /// similar associative container we require this.
230        ///
231        /// \note This operator only have to define some strict ordering of
232        /// the items; this order has nothing to do with the iteration
233        /// ordering of the items.
234        bool operator<(BNode) const { return false; }
235
236      };
237   
238      /// This iterator goes through each node.
239
240      /// This iterator goes through each node.
241      /// Its usage is quite simple, for example you can count the number
242      /// of nodes in graph \c g of type \c Graph like this:
243      ///\code
244      /// int count=0;
245      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
246      ///\endcode
247      class NodeIt : public Node {
248      public:
249        /// Default constructor
250
251        /// @warning The default constructor sets the iterator
252        /// to an undefined value.
253        NodeIt() { }
254        /// Copy constructor.
255       
256        /// Copy constructor.
257        ///
258        NodeIt(const NodeIt& n) : Node(n) { }
259        /// Invalid constructor \& conversion.
260
261        /// Initialize the iterator to be invalid.
262        /// \sa Invalid for more details.
263        NodeIt(Invalid) { }
264        /// Sets the iterator to the first node.
265
266        /// Sets the iterator to the first node of \c g.
267        ///
268        NodeIt(const BpUGraph&) { }
269        /// Node -> NodeIt conversion.
270
271        /// Sets the iterator to the node of \c the graph pointed by
272        /// the trivial iterator.
273        /// This feature necessitates that each time we
274        /// iterate the edge-set, the iteration order is the same.
275        NodeIt(const BpUGraph&, const Node&) { }
276        /// Next node.
277
278        /// Assign the iterator to the next node.
279        ///
280        NodeIt& operator++() { return *this; }
281      };
282
283      /// This iterator goes through each ANode.
284
285      /// This iterator goes through each ANode.
286      /// Its usage is quite simple, for example you can count the number
287      /// of nodes in graph \c g of type \c Graph like this:
288      ///\code
289      /// int count=0;
290      /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count;
291      ///\endcode
292      class ANodeIt : public Node {
293      public:
294        /// Default constructor
295
296        /// @warning The default constructor sets the iterator
297        /// to an undefined value.
298        ANodeIt() { }
299        /// Copy constructor.
300       
301        /// Copy constructor.
302        ///
303        ANodeIt(const ANodeIt& n) : Node(n) { }
304        /// Invalid constructor \& conversion.
305
306        /// Initialize the iterator to be invalid.
307        /// \sa Invalid for more details.
308        ANodeIt(Invalid) { }
309        /// Sets the iterator to the first node.
310
311        /// Sets the iterator to the first node of \c g.
312        ///
313        ANodeIt(const BpUGraph&) { }
314        /// Node -> ANodeIt conversion.
315
316        /// Sets the iterator to the node of \c the graph pointed by
317        /// the trivial iterator.
318        /// This feature necessitates that each time we
319        /// iterate the edge-set, the iteration order is the same.
320        ANodeIt(const BpUGraph&, const Node&) { }
321        /// Next node.
322
323        /// Assign the iterator to the next node.
324        ///
325        ANodeIt& operator++() { return *this; }
326      };
327
328      /// This iterator goes through each BNode.
329
330      /// This iterator goes through each BNode.
331      /// Its usage is quite simple, for example you can count the number
332      /// of nodes in graph \c g of type \c Graph like this:
333      ///\code
334      /// int count=0;
335      /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count;
336      ///\endcode
337      class BNodeIt : public Node {
338      public:
339        /// Default constructor
340
341        /// @warning The default constructor sets the iterator
342        /// to an undefined value.
343        BNodeIt() { }
344        /// Copy constructor.
345       
346        /// Copy constructor.
347        ///
348        BNodeIt(const BNodeIt& n) : Node(n) { }
349        /// Invalid constructor \& conversion.
350
351        /// Initialize the iterator to be invalid.
352        /// \sa Invalid for more details.
353        BNodeIt(Invalid) { }
354        /// Sets the iterator to the first node.
355
356        /// Sets the iterator to the first node of \c g.
357        ///
358        BNodeIt(const BpUGraph&) { }
359        /// Node -> BNodeIt conversion.
360
361        /// Sets the iterator to the node of \c the graph pointed by
362        /// the trivial iterator.
363        /// This feature necessitates that each time we
364        /// iterate the edge-set, the iteration order is the same.
365        BNodeIt(const BpUGraph&, const Node&) { }
366        /// Next node.
367
368        /// Assign the iterator to the next node.
369        ///
370        BNodeIt& operator++() { return *this; }
371      };
372   
373   
374      /// The base type of the undirected edge iterators.
375
376      /// The base type of the undirected edge iterators.
377      ///
378      class UEdge {
379      public:
380        /// Default constructor
381
382        /// @warning The default constructor sets the iterator
383        /// to an undefined value.
384        UEdge() { }
385        /// Copy constructor.
386
387        /// Copy constructor.
388        ///
389        UEdge(const UEdge&) { }
390        /// Initialize the iterator to be invalid.
391
392        /// Initialize the iterator to be invalid.
393        ///
394        UEdge(Invalid) { }
395        /// Equality operator
396
397        /// Two iterators are equal if and only if they point to the
398        /// same object or both are invalid.
399        bool operator==(UEdge) const { return true; }
400        /// Inequality operator
401
402        /// \sa operator==(UEdge n)
403        ///
404        bool operator!=(UEdge) const { return true; }
405
406        /// Artificial ordering operator.
407       
408        /// To allow the use of graph descriptors as key type in std::map or
409        /// similar associative container we require this.
410        ///
411        /// \note This operator only have to define some strict ordering of
412        /// the items; this order has nothing to do with the iteration
413        /// ordering of the items.
414        bool operator<(UEdge) const { return false; }
415      };
416
417      /// This iterator goes through each undirected edge.
418
419      /// This iterator goes through each undirected edge of a graph.
420      /// Its usage is quite simple, for example you can count the number
421      /// of undirected edges in a graph \c g of type \c Graph as follows:
422      ///\code
423      /// int count=0;
424      /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
425      ///\endcode
426      class UEdgeIt : public UEdge {
427      public:
428        /// Default constructor
429
430        /// @warning The default constructor sets the iterator
431        /// to an undefined value.
432        UEdgeIt() { }
433        /// Copy constructor.
434
435        /// Copy constructor.
436        ///
437        UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
438        /// Initialize the iterator to be invalid.
439
440        /// Initialize the iterator to be invalid.
441        ///
442        UEdgeIt(Invalid) { }
443        /// This constructor sets the iterator to the first undirected edge.
444   
445        /// This constructor sets the iterator to the first undirected edge.
446        UEdgeIt(const BpUGraph&) { }
447        /// UEdge -> UEdgeIt conversion
448
449        /// Sets the iterator to the value of the trivial iterator.
450        /// This feature necessitates that each time we
451        /// iterate the undirected edge-set, the iteration order is the
452        /// same.
453        UEdgeIt(const BpUGraph&, const UEdge&) { }
454        /// Next undirected edge
455       
456        /// Assign the iterator to the next undirected edge.
457        UEdgeIt& operator++() { return *this; }
458      };
459
460      /// \brief This iterator goes trough the incident undirected
461      /// edges of a node.
462      ///
463      /// This iterator goes trough the incident undirected edges
464      /// of a certain node
465      /// of a graph.
466      /// Its usage is quite simple, for example you can compute the
467      /// degree (i.e. count the number
468      /// of incident edges of a node \c n
469      /// in graph \c g of type \c Graph as follows.
470      ///\code
471      /// int count=0;
472      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
473      ///\endcode
474      class IncEdgeIt : public UEdge {
475      public:
476        /// Default constructor
477
478        /// @warning The default constructor sets the iterator
479        /// to an undefined value.
480        IncEdgeIt() { }
481        /// Copy constructor.
482
483        /// Copy constructor.
484        ///
485        IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
486        /// Initialize the iterator to be invalid.
487
488        /// Initialize the iterator to be invalid.
489        ///
490        IncEdgeIt(Invalid) { }
491        /// This constructor sets the iterator to first incident edge.
492   
493        /// This constructor set the iterator to the first incident edge of
494        /// the node.
495        IncEdgeIt(const BpUGraph&, const Node&) { }
496        /// UEdge -> IncEdgeIt conversion
497
498        /// Sets the iterator to the value of the trivial iterator \c e.
499        /// This feature necessitates that each time we
500        /// iterate the edge-set, the iteration order is the same.
501        IncEdgeIt(const BpUGraph&, const UEdge&) { }
502        /// Next incident edge
503
504        /// Assign the iterator to the next incident edge
505        /// of the corresponding node.
506        IncEdgeIt& operator++() { return *this; }
507      };
508
509      /// The directed edge type.
510
511      /// The directed edge type. It can be converted to the
512      /// undirected edge.
513      class Edge : public UEdge {
514      public:
515        /// Default constructor
516
517        /// @warning The default constructor sets the iterator
518        /// to an undefined value.
519        Edge() { }
520        /// Copy constructor.
521
522        /// Copy constructor.
523        ///
524        Edge(const Edge& e) : UEdge(e) { }
525        /// Initialize the iterator to be invalid.
526
527        /// Initialize the iterator to be invalid.
528        ///
529        Edge(Invalid) { }
530        /// Equality operator
531
532        /// Two iterators are equal if and only if they point to the
533        /// same object or both are invalid.
534        bool operator==(Edge) const { return true; }
535        /// Inequality operator
536
537        /// \sa operator==(Edge n)
538        ///
539        bool operator!=(Edge) const { return true; }
540
541        /// Artificial ordering operator.
542       
543        /// To allow the use of graph descriptors as key type in std::map or
544        /// similar associative container we require this.
545        ///
546        /// \note This operator only have to define some strict ordering of
547        /// the items; this order has nothing to do with the iteration
548        /// ordering of the items.
549        bool operator<(Edge) const { return false; }
550       
551      };
552      /// This iterator goes through each directed edge.
553
554      /// This iterator goes through each edge of a graph.
555      /// Its usage is quite simple, for example you can count the number
556      /// of edges in a graph \c g of type \c Graph as follows:
557      ///\code
558      /// int count=0;
559      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
560      ///\endcode
561      class EdgeIt : public Edge {
562      public:
563        /// Default constructor
564
565        /// @warning The default constructor sets the iterator
566        /// to an undefined value.
567        EdgeIt() { }
568        /// Copy constructor.
569
570        /// Copy constructor.
571        ///
572        EdgeIt(const EdgeIt& e) : Edge(e) { }
573        /// Initialize the iterator to be invalid.
574
575        /// Initialize the iterator to be invalid.
576        ///
577        EdgeIt(Invalid) { }
578        /// This constructor sets the iterator to the first edge.
579   
580        /// This constructor sets the iterator to the first edge of \c g.
581        ///@param g the graph
582        EdgeIt(const BpUGraph &g) { ignore_unused_variable_warning(g); }
583        /// Edge -> EdgeIt conversion
584
585        /// Sets the iterator to the value of the trivial iterator \c e.
586        /// This feature necessitates that each time we
587        /// iterate the edge-set, the iteration order is the same.
588        EdgeIt(const BpUGraph&, const Edge&) { }
589        ///Next edge
590       
591        /// Assign the iterator to the next edge.
592        EdgeIt& operator++() { return *this; }
593      };
594   
595      /// This iterator goes trough the outgoing directed edges of a node.
596
597      /// This iterator goes trough the \e outgoing edges of a certain node
598      /// of a graph.
599      /// Its usage is quite simple, for example you can count the number
600      /// of outgoing edges of a node \c n
601      /// in graph \c g of type \c Graph as follows.
602      ///\code
603      /// int count=0;
604      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
605      ///\endcode
606   
607      class OutEdgeIt : public Edge {
608      public:
609        /// Default constructor
610
611        /// @warning The default constructor sets the iterator
612        /// to an undefined value.
613        OutEdgeIt() { }
614        /// Copy constructor.
615
616        /// Copy constructor.
617        ///
618        OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
619        /// Initialize the iterator to be invalid.
620
621        /// Initialize the iterator to be invalid.
622        ///
623        OutEdgeIt(Invalid) { }
624        /// This constructor sets the iterator to the first outgoing edge.
625   
626        /// This constructor sets the iterator to the first outgoing edge of
627        /// the node.
628        ///@param n the node
629        ///@param g the graph
630        OutEdgeIt(const BpUGraph& n, const Node& g) {
631          ignore_unused_variable_warning(n);
632          ignore_unused_variable_warning(g);
633        }
634        /// Edge -> OutEdgeIt conversion
635
636        /// Sets the iterator to the value of the trivial iterator.
637        /// This feature necessitates that each time we
638        /// iterate the edge-set, the iteration order is the same.
639        OutEdgeIt(const BpUGraph&, const Edge&) { }
640        ///Next outgoing edge
641       
642        /// Assign the iterator to the next
643        /// outgoing edge of the corresponding node.
644        OutEdgeIt& operator++() { return *this; }
645      };
646
647      /// This iterator goes trough the incoming directed edges of a node.
648
649      /// This iterator goes trough the \e incoming edges of a certain node
650      /// of a graph.
651      /// Its usage is quite simple, for example you can count the number
652      /// of outgoing edges of a node \c n
653      /// in graph \c g of type \c Graph as follows.
654      ///\code
655      /// int count=0;
656      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
657      ///\endcode
658
659      class InEdgeIt : public Edge {
660      public:
661        /// Default constructor
662
663        /// @warning The default constructor sets the iterator
664        /// to an undefined value.
665        InEdgeIt() { }
666        /// Copy constructor.
667
668        /// Copy constructor.
669        ///
670        InEdgeIt(const InEdgeIt& e) : Edge(e) { }
671        /// Initialize the iterator to be invalid.
672
673        /// Initialize the iterator to be invalid.
674        ///
675        InEdgeIt(Invalid) { }
676        /// This constructor sets the iterator to first incoming edge.
677   
678        /// This constructor set the iterator to the first incoming edge of
679        /// the node.
680        ///@param n the node
681        ///@param g the graph
682        InEdgeIt(const BpUGraph& g, const Node& n) {
683          ignore_unused_variable_warning(n);
684          ignore_unused_variable_warning(g);
685        }
686        /// Edge -> InEdgeIt conversion
687
688        /// Sets the iterator to the value of the trivial iterator \c e.
689        /// This feature necessitates that each time we
690        /// iterate the edge-set, the iteration order is the same.
691        InEdgeIt(const BpUGraph&, const Edge&) { }
692        /// Next incoming edge
693
694        /// Assign the iterator to the next inedge of the corresponding node.
695        ///
696        InEdgeIt& operator++() { return *this; }
697      };
698
699      /// \brief Read write map of the nodes to type \c T.
700      ///
701      /// ReadWrite map of the nodes to type \c T.
702      /// \sa Reference
703      /// \warning Making maps that can handle bool type (NodeMap<bool>)
704      /// needs some extra attention!
705      /// \todo Wrong documentation
706      template<class T>
707      class NodeMap : public ReadWriteMap< Node, T >
708      {
709      public:
710
711        ///\e
712        NodeMap(const BpUGraph&) { }
713        ///\e
714        NodeMap(const BpUGraph&, T) { }
715
716        ///Copy constructor
717        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
718        ///Assignment operator
719        NodeMap& operator=(const NodeMap&) { return *this; }
720        // \todo fix this concept
721      };
722
723      /// \brief Read write map of the ANodes to type \c T.
724      ///
725      /// ReadWrite map of the ANodes to type \c T.
726      /// \sa Reference
727      /// \warning Making maps that can handle bool type (NodeMap<bool>)
728      /// needs some extra attention!
729      /// \todo Wrong documentation
730      template<class T>
731      class ANodeMap : public ReadWriteMap< Node, T >
732      {
733      public:
734
735        ///\e
736        ANodeMap(const BpUGraph&) { }
737        ///\e
738        ANodeMap(const BpUGraph&, T) { }
739
740        ///Copy constructor
741        ANodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
742        ///Assignment operator
743        ANodeMap& operator=(const NodeMap&) { return *this; }
744        // \todo fix this concept
745      };
746
747      /// \brief Read write map of the BNodes to type \c T.
748      ///
749      /// ReadWrite map of the BNodes to type \c T.
750      /// \sa Reference
751      /// \warning Making maps that can handle bool type (NodeMap<bool>)
752      /// needs some extra attention!
753      /// \todo Wrong documentation
754      template<class T>
755      class BNodeMap : public ReadWriteMap< Node, T >
756      {
757      public:
758
759        ///\e
760        BNodeMap(const BpUGraph&) { }
761        ///\e
762        BNodeMap(const BpUGraph&, T) { }
763
764        ///Copy constructor
765        BNodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
766        ///Assignment operator
767        BNodeMap& operator=(const NodeMap&) { return *this; }
768        // \todo fix this concept
769      };
770
771      /// \brief Read write map of the directed edges to type \c T.
772      ///
773      /// Reference map of the directed edges to type \c T.
774      /// \sa Reference
775      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
776      /// needs some extra attention!
777      /// \todo Wrong documentation
778      template<class T>
779      class EdgeMap : public ReadWriteMap<Edge,T>
780      {
781      public:
782
783        ///\e
784        EdgeMap(const BpUGraph&) { }
785        ///\e
786        EdgeMap(const BpUGraph&, T) { }
787        ///Copy constructor
788        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
789        ///Assignment operator
790        EdgeMap& operator=(const EdgeMap&) { return *this; }
791        // \todo fix this concept   
792      };
793
794      /// Read write map of the undirected edges to type \c T.
795
796      /// Reference map of the edges to type \c T.
797      /// \sa Reference
798      /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
799      /// needs some extra attention!
800      /// \todo Wrong documentation
801      template<class T>
802      class UEdgeMap : public ReadWriteMap<UEdge,T>
803      {
804      public:
805
806        ///\e
807        UEdgeMap(const BpUGraph&) { }
808        ///\e
809        UEdgeMap(const BpUGraph&, T) { }
810        ///Copy constructor
811        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
812        ///Assignment operator
813        UEdgeMap &operator=(const UEdgeMap&) { return *this; }
814        // \todo fix this concept   
815      };
816
817      /// \brief Direct the given undirected edge.
818      ///
819      /// Direct the given undirected edge. The returned edge source
820      /// will be the given node.
821      Edge direct(const UEdge&, const Node&) const {
822        return INVALID;
823      }
824
825      /// \brief Direct the given undirected edge.
826      ///
827      /// Direct the given undirected edge. The returned edge
828      /// represents the given undireted edge and the direction comes
829      /// from the given bool.  The source of the undirected edge and
830      /// the directed edge is the same when the given bool is true.
831      Edge direct(const UEdge&, bool) const {
832        return INVALID;
833      }
834
835      /// \brief Returns true when the given node is an ANode.
836      ///
837      /// Returns true when the given node is an ANode.
838      bool aNode(Node) const { return true;}
839
840      /// \brief Returns true when the given node is an BNode.
841      ///
842      /// Returns true when the given node is an BNode.
843      bool bNode(Node) const { return true;}
844
845      /// \brief Returns the edge's end node which is in the ANode set.
846      ///
847      /// Returns the edge's end node which is in the ANode set.
848      Node aNode(UEdge) const { return INVALID;}
849
850      /// \brief Returns the edge's end node which is in the BNode set.
851      ///
852      /// Returns the edge's end node which is in the BNode set.
853      Node bNode(UEdge) const { return INVALID;}
854
855      /// \brief Returns true if the edge has default orientation.
856      ///
857      /// Returns whether the given directed edge is same orientation as
858      /// the corresponding undirected edge's default orientation.
859      bool direction(Edge) const { return true; }
860
861      /// \brief Returns the opposite directed edge.
862      ///
863      /// Returns the opposite directed edge.
864      Edge oppositeEdge(Edge) const { return INVALID; }
865
866      /// \brief Opposite node on an edge
867      ///
868      /// \return the opposite of the given Node on the given UEdge
869      Node oppositeNode(Node, UEdge) const { return INVALID; }
870
871      /// \brief First node of the undirected edge.
872      ///
873      /// \return the first node of the given UEdge.
874      ///
875      /// Naturally undirected edges don't have direction and thus
876      /// don't have source and target node. But we use these two methods
877      /// to query the two endnodes of the edge. The direction of the edge
878      /// which arises this way is called the inherent direction of the
879      /// undirected edge, and is used to define the "default" direction
880      /// of the directed versions of the edges.
881      /// \sa direction
882      Node source(UEdge) const { return INVALID; }
883
884      /// \brief Second node of the undirected edge.
885      Node target(UEdge) const { return INVALID; }
886
887      /// \brief Source node of the directed edge.
888      Node source(Edge) const { return INVALID; }
889
890      /// \brief Target node of the directed edge.
891      Node target(Edge) const { return INVALID; }
892
893      /// \brief Base node of the iterator
894      ///
895      /// Returns the base node (the source in this case) of the iterator
896      Node baseNode(OutEdgeIt e) const {
897        return source(e);
898      }
899
900      /// \brief Running node of the iterator
901      ///
902      /// Returns the running node (the target in this case) of the
903      /// iterator
904      Node runningNode(OutEdgeIt e) const {
905        return target(e);
906      }
907
908      /// \brief Base node of the iterator
909      ///
910      /// Returns the base node (the target in this case) of the iterator
911      Node baseNode(InEdgeIt e) const {
912        return target(e);
913      }
914      /// \brief Running node of the iterator
915      ///
916      /// Returns the running node (the source in this case) of the
917      /// iterator
918      Node runningNode(InEdgeIt e) const {
919        return source(e);
920      }
921
922      /// \brief Base node of the iterator
923      ///
924      /// Returns the base node of the iterator
925      Node baseNode(IncEdgeIt) const {
926        return INVALID;
927      }
928     
929      /// \brief Running node of the iterator
930      ///
931      /// Returns the running node of the iterator
932      Node runningNode(IncEdgeIt) const {
933        return INVALID;
934      }
935
936      template <typename Graph>
937      struct Constraints {
938        void constraints() {
939        }
940      };
941
942    };
943
944
945    /// @}
946
947  }
948
949}
950
951#endif
Note: See TracBrowser for help on using the repository browser.