COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/bpugraph.h @ 2126:2c8adbee9fa6

Last change on this file since 2126:2c8adbee9fa6 was 2126:2c8adbee9fa6, checked in by Balazs Dezso, 16 years ago

Renameing file: graph_component.h => graph_components.h

File size: 30.3 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 BNode
59    /// which are inherited from Node type. Moreover they have
60    /// constructor which converts Node to either ANode or BNode when it is
61    /// possible. Therefor everywhere the Node type can be used instead of
62    /// ANode and BNode. So the usage of the ANode and BNode is suggested. 
63    ///
64    /// The iteration on the partition can be done with the ANodeIt and
65    /// BNodeIt classes. The node map can be used to map values to the nodes
66    /// and similarly we can use to map values for just the ANodes and
67    /// BNodes the ANodeMap and BNodeMap template classes.
68
69    class BpUGraph {
70    public:
71      /// \todo undocumented
72      ///
73      typedef True UndirectedTag;
74
75      /// \brief The base type of node iterators,
76      /// or in other words, the trivial node iterator.
77      ///
78      /// This is the base type of each node iterator,
79      /// thus each kind of node iterator converts to this.
80      /// More precisely each kind of node iterator should be inherited
81      /// from the trivial node iterator. The Node class represents
82      /// both of two types of nodes.
83      class Node {
84      public:
85        /// Default constructor
86
87        /// @warning The default constructor sets the iterator
88        /// to an undefined value.
89        Node() { }
90        /// Copy constructor.
91
92        /// Copy constructor.
93        ///
94        Node(const Node&) { }
95
96        /// Invalid constructor \& conversion.
97
98        /// This constructor initializes the iterator to be invalid.
99        /// \sa Invalid for more details.
100        Node(Invalid) { }
101        /// Equality operator
102
103        /// Two iterators are equal if and only if they point to the
104        /// same object or both are invalid.
105        bool operator==(Node) const { return true; }
106
107        /// Inequality operator
108       
109        /// \sa operator==(Node n)
110        ///
111        bool operator!=(Node) const { return true; }
112
113        /// Artificial ordering operator.
114       
115        /// To allow the use of graph descriptors as key type in std::map or
116        /// similar associative container we require this.
117        ///
118        /// \note This operator only have to define some strict ordering of
119        /// the items; this order has nothing to do with the iteration
120        /// ordering of the items.
121        bool operator<(Node) const { return false; }
122
123      };
124
125      /// \brief The base type of anode iterators,
126      /// or in other words, the trivial anode iterator.
127      ///
128      /// This is the base type of each anode iterator,
129      /// thus each kind of anode iterator converts to this.
130      /// More precisely each kind of node iterator should be inherited
131      /// from the trivial anode iterator. The ANode class should be used
132      /// only in special cases. Usually the Node type should be used insted
133      /// of it.
134      class ANode {
135      public:
136        /// Default constructor
137
138        /// @warning The default constructor sets the iterator
139        /// to an undefined value.
140        ANode() { }
141        /// Copy constructor.
142
143        /// Copy constructor.
144        ///
145        ANode(const ANode&) { }
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&) { }
152
153        /// Invalid constructor \& conversion.
154
155        /// This constructor initializes the iterator to be invalid.
156        /// \sa Invalid for more details.
157        ANode(Invalid) { }
158        /// Equality operator
159
160        /// Two iterators are equal if and only if they point to the
161        /// same object or both are invalid.
162        bool operator==(ANode) const { return true; }
163
164        /// Inequality operator
165       
166        /// \sa operator==(ANode n)
167        ///
168        bool operator!=(ANode) const { return true; }
169
170        /// Artificial ordering operator.
171       
172        /// To allow the use of graph descriptors as key type in std::map or
173        /// similar associative container we require this.
174        ///
175        /// \note This operator only have to define some strict ordering of
176        /// the items; this order has nothing to do with the iteration
177        /// ordering of the items.
178        bool operator<(ANode) const { return false; }
179
180      };
181
182      /// \brief The base type of bnode iterators,
183      /// or in other words, the trivial bnode iterator.
184      ///
185      /// This is the base type of each anode iterator,
186      /// thus each kind of anode iterator converts to this.
187      /// More precisely each kind of node iterator should be inherited
188      /// from the trivial anode iterator. The BNode class should be used
189      /// only in special cases. Usually the Node type should be used insted
190      /// of it.
191      class BNode {
192      public:
193        /// Default constructor
194
195        /// @warning The default constructor sets the iterator
196        /// to an undefined value.
197        BNode() { }
198        /// Copy constructor.
199
200        /// Copy constructor.
201        ///
202        BNode(const BNode&) { }
203
204        /// Construct the same node as BNode.
205
206        /// Construct the same node as BNode. It may throws assertion
207        /// when the given node is from the ANode set.
208        BNode(const Node&) { }
209
210        /// Invalid constructor \& conversion.
211
212        /// This constructor initializes the iterator to be invalid.
213        /// \sa Invalid for more details.
214        BNode(Invalid) { }
215        /// Equality operator
216
217        /// Two iterators are equal if and only if they point to the
218        /// same object or both are invalid.
219        bool operator==(BNode) const { return true; }
220
221        /// Inequality operator
222       
223        /// \sa operator==(BNode n)
224        ///
225        bool operator!=(BNode) const { return true; }
226
227        /// Artificial ordering operator.
228       
229        /// To allow the use of graph descriptors as key type in std::map or
230        /// similar associative container we require this.
231        ///
232        /// \note This operator only have to define some strict ordering of
233        /// the items; this order has nothing to do with the iteration
234        /// ordering of the items.
235        bool operator<(BNode) const { return false; }
236
237      };
238   
239      /// This iterator goes through each node.
240
241      /// This iterator goes through each node.
242      /// Its usage is quite simple, for example you can count the number
243      /// of nodes in graph \c g of type \c Graph like this:
244      ///\code
245      /// int count=0;
246      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
247      ///\endcode
248      class NodeIt : public Node {
249      public:
250        /// Default constructor
251
252        /// @warning The default constructor sets the iterator
253        /// to an undefined value.
254        NodeIt() { }
255        /// Copy constructor.
256       
257        /// Copy constructor.
258        ///
259        NodeIt(const NodeIt& n) : Node(n) { }
260        /// Invalid constructor \& conversion.
261
262        /// Initialize the iterator to be invalid.
263        /// \sa Invalid for more details.
264        NodeIt(Invalid) { }
265        /// Sets the iterator to the first node.
266
267        /// Sets the iterator to the first node of \c g.
268        ///
269        NodeIt(const BpUGraph&) { }
270        /// Node -> NodeIt conversion.
271
272        /// Sets the iterator to the node of \c the graph pointed by
273        /// the trivial iterator.
274        /// This feature necessitates that each time we
275        /// iterate the edge-set, the iteration order is the same.
276        NodeIt(const BpUGraph&, const Node&) { }
277        /// Next node.
278
279        /// Assign the iterator to the next node.
280        ///
281        NodeIt& operator++() { return *this; }
282      };
283
284      /// This iterator goes through each ANode.
285
286      /// This iterator goes through each ANode.
287      /// Its usage is quite simple, for example you can count the number
288      /// of nodes in graph \c g of type \c Graph like this:
289      ///\code
290      /// int count=0;
291      /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count;
292      ///\endcode
293      class ANodeIt : public ANode {
294      public:
295        /// Default constructor
296
297        /// @warning The default constructor sets the iterator
298        /// to an undefined value.
299        ANodeIt() { }
300        /// Copy constructor.
301       
302        /// Copy constructor.
303        ///
304        ANodeIt(const ANodeIt& n) : Node(n) { }
305        /// Invalid constructor \& conversion.
306
307        /// Initialize the iterator to be invalid.
308        /// \sa Invalid for more details.
309        ANodeIt(Invalid) { }
310        /// Sets the iterator to the first node.
311
312        /// Sets the iterator to the first node of \c g.
313        ///
314        ANodeIt(const BpUGraph&) { }
315        /// Node -> ANodeIt conversion.
316
317        /// Sets the iterator to the node of \c the graph pointed by
318        /// the trivial iterator.
319        /// This feature necessitates that each time we
320        /// iterate the edge-set, the iteration order is the same.
321        ANodeIt(const BpUGraph&, const Node&) { }
322        /// Next node.
323
324        /// Assign the iterator to the next node.
325        ///
326        ANodeIt& operator++() { return *this; }
327      };
328
329      /// This iterator goes through each BNode.
330
331      /// This iterator goes through each BNode.
332      /// Its usage is quite simple, for example you can count the number
333      /// of nodes in graph \c g of type \c Graph like this:
334      ///\code
335      /// int count=0;
336      /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count;
337      ///\endcode
338      class BNodeIt : public BNode {
339      public:
340        /// Default constructor
341
342        /// @warning The default constructor sets the iterator
343        /// to an undefined value.
344        BNodeIt() { }
345        /// Copy constructor.
346       
347        /// Copy constructor.
348        ///
349        BNodeIt(const BNodeIt& n) : Node(n) { }
350        /// Invalid constructor \& conversion.
351
352        /// Initialize the iterator to be invalid.
353        /// \sa Invalid for more details.
354        BNodeIt(Invalid) { }
355        /// Sets the iterator to the first node.
356
357        /// Sets the iterator to the first node of \c g.
358        ///
359        BNodeIt(const BpUGraph&) { }
360        /// Node -> BNodeIt conversion.
361
362        /// Sets the iterator to the node of \c the graph pointed by
363        /// the trivial iterator.
364        /// This feature necessitates that each time we
365        /// iterate the edge-set, the iteration order is the same.
366        BNodeIt(const BpUGraph&, const Node&) { }
367        /// Next node.
368
369        /// Assign the iterator to the next node.
370        ///
371        BNodeIt& operator++() { return *this; }
372      };
373   
374   
375      /// The base type of the undirected edge iterators.
376
377      /// The base type of the undirected edge iterators.
378      ///
379      class UEdge {
380      public:
381        /// Default constructor
382
383        /// @warning The default constructor sets the iterator
384        /// to an undefined value.
385        UEdge() { }
386        /// Copy constructor.
387
388        /// Copy constructor.
389        ///
390        UEdge(const UEdge&) { }
391        /// Initialize the iterator to be invalid.
392
393        /// Initialize the iterator to be invalid.
394        ///
395        UEdge(Invalid) { }
396        /// Equality operator
397
398        /// Two iterators are equal if and only if they point to the
399        /// same object or both are invalid.
400        bool operator==(UEdge) const { return true; }
401        /// Inequality operator
402
403        /// \sa operator==(UEdge n)
404        ///
405        bool operator!=(UEdge) const { return true; }
406
407        /// Artificial ordering operator.
408       
409        /// To allow the use of graph descriptors as key type in std::map or
410        /// similar associative container we require this.
411        ///
412        /// \note This operator only have to define some strict ordering of
413        /// the items; this order has nothing to do with the iteration
414        /// ordering of the items.
415        bool operator<(UEdge) const { return false; }
416      };
417
418      /// This iterator goes through each undirected edge.
419
420      /// This iterator goes through each undirected edge of a graph.
421      /// Its usage is quite simple, for example you can count the number
422      /// of undirected edges in a graph \c g of type \c Graph as follows:
423      ///\code
424      /// int count=0;
425      /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
426      ///\endcode
427      class UEdgeIt : public UEdge {
428      public:
429        /// Default constructor
430
431        /// @warning The default constructor sets the iterator
432        /// to an undefined value.
433        UEdgeIt() { }
434        /// Copy constructor.
435
436        /// Copy constructor.
437        ///
438        UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
439        /// Initialize the iterator to be invalid.
440
441        /// Initialize the iterator to be invalid.
442        ///
443        UEdgeIt(Invalid) { }
444        /// This constructor sets the iterator to the first undirected edge.
445   
446        /// This constructor sets the iterator to the first undirected edge.
447        UEdgeIt(const BpUGraph&) { }
448        /// UEdge -> UEdgeIt conversion
449
450        /// Sets the iterator to the value of the trivial iterator.
451        /// This feature necessitates that each time we
452        /// iterate the undirected edge-set, the iteration order is the
453        /// same.
454        UEdgeIt(const BpUGraph&, const UEdge&) { }
455        /// Next undirected edge
456       
457        /// Assign the iterator to the next undirected edge.
458        UEdgeIt& operator++() { return *this; }
459      };
460
461      /// \brief This iterator goes trough the incident undirected
462      /// edges of a node.
463      ///
464      /// This iterator goes trough the incident undirected edges
465      /// of a certain node
466      /// of a graph.
467      /// Its usage is quite simple, for example you can compute the
468      /// degree (i.e. count the number
469      /// of incident edges of a node \c n
470      /// in graph \c g of type \c Graph as follows.
471      ///\code
472      /// int count=0;
473      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
474      ///\endcode
475      class IncEdgeIt : public UEdge {
476      public:
477        /// Default constructor
478
479        /// @warning The default constructor sets the iterator
480        /// to an undefined value.
481        IncEdgeIt() { }
482        /// Copy constructor.
483
484        /// Copy constructor.
485        ///
486        IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
487        /// Initialize the iterator to be invalid.
488
489        /// Initialize the iterator to be invalid.
490        ///
491        IncEdgeIt(Invalid) { }
492        /// This constructor sets the iterator to first incident edge.
493   
494        /// This constructor set the iterator to the first incident edge of
495        /// the node.
496        IncEdgeIt(const BpUGraph&, const Node&) { }
497        /// UEdge -> IncEdgeIt conversion
498
499        /// Sets the iterator to the value of the trivial iterator \c e.
500        /// This feature necessitates that each time we
501        /// iterate the edge-set, the iteration order is the same.
502        IncEdgeIt(const BpUGraph&, const UEdge&) { }
503        /// Next incident edge
504
505        /// Assign the iterator to the next incident edge
506        /// of the corresponding node.
507        IncEdgeIt& operator++() { return *this; }
508      };
509
510      /// The directed edge type.
511
512      /// The directed edge type. It can be converted to the
513      /// undirected edge.
514      class Edge : public UEdge {
515      public:
516        /// Default constructor
517
518        /// @warning The default constructor sets the iterator
519        /// to an undefined value.
520        Edge() { }
521        /// Copy constructor.
522
523        /// Copy constructor.
524        ///
525        Edge(const Edge& e) : UEdge(e) { }
526        /// Initialize the iterator to be invalid.
527
528        /// Initialize the iterator to be invalid.
529        ///
530        Edge(Invalid) { }
531        /// Equality operator
532
533        /// Two iterators are equal if and only if they point to the
534        /// same object or both are invalid.
535        bool operator==(Edge) const { return true; }
536        /// Inequality operator
537
538        /// \sa operator==(Edge n)
539        ///
540        bool operator!=(Edge) const { return true; }
541
542        /// Artificial ordering operator.
543       
544        /// To allow the use of graph descriptors as key type in std::map or
545        /// similar associative container we require this.
546        ///
547        /// \note This operator only have to define some strict ordering of
548        /// the items; this order has nothing to do with the iteration
549        /// ordering of the items.
550        bool operator<(Edge) const { return false; }
551       
552      };
553      /// This iterator goes through each directed edge.
554
555      /// This iterator goes through each edge of a graph.
556      /// Its usage is quite simple, for example you can count the number
557      /// of edges in a graph \c g of type \c Graph as follows:
558      ///\code
559      /// int count=0;
560      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
561      ///\endcode
562      class EdgeIt : public Edge {
563      public:
564        /// Default constructor
565
566        /// @warning The default constructor sets the iterator
567        /// to an undefined value.
568        EdgeIt() { }
569        /// Copy constructor.
570
571        /// Copy constructor.
572        ///
573        EdgeIt(const EdgeIt& e) : Edge(e) { }
574        /// Initialize the iterator to be invalid.
575
576        /// Initialize the iterator to be invalid.
577        ///
578        EdgeIt(Invalid) { }
579        /// This constructor sets the iterator to the first edge.
580   
581        /// This constructor sets the iterator to the first edge of \c g.
582        ///@param g the graph
583        EdgeIt(const BpUGraph &g) { ignore_unused_variable_warning(g); }
584        /// Edge -> EdgeIt conversion
585
586        /// Sets the iterator to the value of the trivial iterator \c e.
587        /// This feature necessitates that each time we
588        /// iterate the edge-set, the iteration order is the same.
589        EdgeIt(const BpUGraph&, const Edge&) { }
590        ///Next edge
591       
592        /// Assign the iterator to the next edge.
593        EdgeIt& operator++() { return *this; }
594      };
595   
596      /// This iterator goes trough the outgoing directed edges of a node.
597
598      /// This iterator goes trough the \e outgoing edges of a certain node
599      /// of a graph.
600      /// Its usage is quite simple, for example you can count the number
601      /// of outgoing edges of a node \c n
602      /// in graph \c g of type \c Graph as follows.
603      ///\code
604      /// int count=0;
605      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
606      ///\endcode
607   
608      class OutEdgeIt : public Edge {
609      public:
610        /// Default constructor
611
612        /// @warning The default constructor sets the iterator
613        /// to an undefined value.
614        OutEdgeIt() { }
615        /// Copy constructor.
616
617        /// Copy constructor.
618        ///
619        OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
620        /// Initialize the iterator to be invalid.
621
622        /// Initialize the iterator to be invalid.
623        ///
624        OutEdgeIt(Invalid) { }
625        /// This constructor sets the iterator to the first outgoing edge.
626   
627        /// This constructor sets the iterator to the first outgoing edge of
628        /// the node.
629        ///@param n the node
630        ///@param g the graph
631        OutEdgeIt(const BpUGraph& n, const Node& g) {
632          ignore_unused_variable_warning(n);
633          ignore_unused_variable_warning(g);
634        }
635        /// Edge -> OutEdgeIt conversion
636
637        /// Sets the iterator to the value of the trivial iterator.
638        /// This feature necessitates that each time we
639        /// iterate the edge-set, the iteration order is the same.
640        OutEdgeIt(const BpUGraph&, const Edge&) { }
641        ///Next outgoing edge
642       
643        /// Assign the iterator to the next
644        /// outgoing edge of the corresponding node.
645        OutEdgeIt& operator++() { return *this; }
646      };
647
648      /// This iterator goes trough the incoming directed edges of a node.
649
650      /// This iterator goes trough the \e incoming edges of a certain node
651      /// of a graph.
652      /// Its usage is quite simple, for example you can count the number
653      /// of outgoing edges of a node \c n
654      /// in graph \c g of type \c Graph as follows.
655      ///\code
656      /// int count=0;
657      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
658      ///\endcode
659
660      class InEdgeIt : public Edge {
661      public:
662        /// Default constructor
663
664        /// @warning The default constructor sets the iterator
665        /// to an undefined value.
666        InEdgeIt() { }
667        /// Copy constructor.
668
669        /// Copy constructor.
670        ///
671        InEdgeIt(const InEdgeIt& e) : Edge(e) { }
672        /// Initialize the iterator to be invalid.
673
674        /// Initialize the iterator to be invalid.
675        ///
676        InEdgeIt(Invalid) { }
677        /// This constructor sets the iterator to first incoming edge.
678   
679        /// This constructor set the iterator to the first incoming edge of
680        /// the node.
681        ///@param n the node
682        ///@param g the graph
683        InEdgeIt(const BpUGraph& g, const Node& n) {
684          ignore_unused_variable_warning(n);
685          ignore_unused_variable_warning(g);
686        }
687        /// Edge -> InEdgeIt conversion
688
689        /// Sets the iterator to the value of the trivial iterator \c e.
690        /// This feature necessitates that each time we
691        /// iterate the edge-set, the iteration order is the same.
692        InEdgeIt(const BpUGraph&, const Edge&) { }
693        /// Next incoming edge
694
695        /// Assign the iterator to the next inedge of the corresponding node.
696        ///
697        InEdgeIt& operator++() { return *this; }
698      };
699
700      /// \brief Read write map of the nodes to type \c T.
701      ///
702      /// ReadWrite map of the nodes to type \c T.
703      /// \sa Reference
704      /// \warning Making maps that can handle bool type (NodeMap<bool>)
705      /// needs some extra attention!
706      /// \todo Wrong documentation
707      template<class T>
708      class NodeMap : public ReadWriteMap< Node, T >
709      {
710      public:
711
712        ///\e
713        NodeMap(const BpUGraph&) { }
714        ///\e
715        NodeMap(const BpUGraph&, T) { }
716
717        ///Copy constructor
718        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
719        ///Assignment operator
720        NodeMap& operator=(const NodeMap&) { return *this; }
721        // \todo fix this concept
722      };
723
724      /// \brief Read write map of the ANodes to type \c T.
725      ///
726      /// ReadWrite map of the ANodes to type \c T.
727      /// \sa Reference
728      /// \warning Making maps that can handle bool type (NodeMap<bool>)
729      /// needs some extra attention!
730      /// \todo Wrong documentation
731      template<class T>
732      class ANodeMap : public ReadWriteMap< Node, T >
733      {
734      public:
735
736        ///\e
737        ANodeMap(const BpUGraph&) { }
738        ///\e
739        ANodeMap(const BpUGraph&, T) { }
740
741        ///Copy constructor
742        ANodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
743        ///Assignment operator
744        ANodeMap& operator=(const NodeMap&) { return *this; }
745        // \todo fix this concept
746      };
747
748      /// \brief Read write map of the BNodes to type \c T.
749      ///
750      /// ReadWrite map of the BNodes to type \c T.
751      /// \sa Reference
752      /// \warning Making maps that can handle bool type (NodeMap<bool>)
753      /// needs some extra attention!
754      /// \todo Wrong documentation
755      template<class T>
756      class BNodeMap : public ReadWriteMap< Node, T >
757      {
758      public:
759
760        ///\e
761        BNodeMap(const BpUGraph&) { }
762        ///\e
763        BNodeMap(const BpUGraph&, T) { }
764
765        ///Copy constructor
766        BNodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
767        ///Assignment operator
768        BNodeMap& operator=(const NodeMap&) { return *this; }
769        // \todo fix this concept
770      };
771
772      /// \brief Read write map of the directed edges to type \c T.
773      ///
774      /// Reference map of the directed edges to type \c T.
775      /// \sa Reference
776      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
777      /// needs some extra attention!
778      /// \todo Wrong documentation
779      template<class T>
780      class EdgeMap : public ReadWriteMap<Edge,T>
781      {
782      public:
783
784        ///\e
785        EdgeMap(const BpUGraph&) { }
786        ///\e
787        EdgeMap(const BpUGraph&, T) { }
788        ///Copy constructor
789        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
790        ///Assignment operator
791        EdgeMap& operator=(const EdgeMap&) { return *this; }
792        // \todo fix this concept   
793      };
794
795      /// Read write map of the undirected edges to type \c T.
796
797      /// Reference map of the edges to type \c T.
798      /// \sa Reference
799      /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
800      /// needs some extra attention!
801      /// \todo Wrong documentation
802      template<class T>
803      class UEdgeMap : public ReadWriteMap<UEdge,T>
804      {
805      public:
806
807        ///\e
808        UEdgeMap(const BpUGraph&) { }
809        ///\e
810        UEdgeMap(const BpUGraph&, T) { }
811        ///Copy constructor
812        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
813        ///Assignment operator
814        UEdgeMap &operator=(const UEdgeMap&) { return *this; }
815        // \todo fix this concept   
816      };
817
818      /// \brief Direct the given undirected edge.
819      ///
820      /// Direct the given undirected edge. The returned edge source
821      /// will be the given edge.
822      Edge direct(const UEdge&, const Node&) const {
823        return INVALID;
824      }
825
826      /// \brief Direct the given undirected edge.
827      ///
828      /// Direct the given undirected edge. The returned edge source
829      /// will be the source of the undirected edge if the given bool
830      /// 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.
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 Edge
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 uectected 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.