COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/bpgraph.h @ 1270:dceba191c00d

Last change on this file since 1270:dceba191c00d was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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