COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/bpgraph.h @ 1217:7bf489cf624e

Last change on this file since 1217:7bf489cf624e was 1217:7bf489cf624e, checked in by Peter Kovacs <kpeter@…>, 7 years ago

Minor fixes and improvements in the doc (#459)

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-2010
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) { ignore_unused_variable_warning(g); }
527        /// Sets the iterator to the given arc.
528
529        /// Sets the iterator to the given arc of the given graph.
530        ///
531        ArcIt(const BpGraph&, const Arc&) { }
532        /// Next arc
533
534        /// Assign the iterator to the next arc.
535        ///
536        ArcIt& operator++() { return *this; }
537      };
538
539      /// Iterator class for the outgoing arcs of a node.
540
541      /// This iterator goes trough the \e outgoing directed arcs of a
542      /// certain node of a graph.
543      /// Its usage is quite simple, for example, you can count the number
544      /// of outgoing arcs of a node \c n
545      /// in a graph \c g of type \c %BpGraph as follows.
546      ///\code
547      /// int count=0;
548      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
549      ///\endcode
550      class OutArcIt : public Arc {
551      public:
552        /// Default constructor
553
554        /// Default constructor.
555        /// \warning It sets the iterator to an undefined value.
556        OutArcIt() { }
557        /// Copy constructor.
558
559        /// Copy constructor.
560        ///
561        OutArcIt(const OutArcIt& e) : Arc(e) { }
562        /// %Invalid constructor \& conversion.
563
564        /// Initializes the iterator to be invalid.
565        /// \sa Invalid for more details.
566        OutArcIt(Invalid) { }
567        /// Sets the iterator to the first outgoing arc.
568
569        /// Sets the iterator to the first outgoing arc of the given node.
570        ///
571        OutArcIt(const BpGraph& n, const Node& g) {
572          ignore_unused_variable_warning(n);
573          ignore_unused_variable_warning(g);
574        }
575        /// Sets the iterator to the given arc.
576
577        /// Sets the iterator to the given arc of the given graph.
578        ///
579        OutArcIt(const BpGraph&, const Arc&) { }
580        /// Next outgoing arc
581
582        /// Assign the iterator to the next
583        /// outgoing arc of the corresponding node.
584        OutArcIt& operator++() { return *this; }
585      };
586
587      /// Iterator class for the incoming arcs of a node.
588
589      /// This iterator goes trough the \e incoming directed arcs of a
590      /// certain node of a graph.
591      /// Its usage is quite simple, for example, you can count the number
592      /// of incoming arcs of a node \c n
593      /// in a graph \c g of type \c %BpGraph as follows.
594      ///\code
595      /// int count=0;
596      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
597      ///\endcode
598      class InArcIt : public Arc {
599      public:
600        /// Default constructor
601
602        /// Default constructor.
603        /// \warning It sets the iterator to an undefined value.
604        InArcIt() { }
605        /// Copy constructor.
606
607        /// Copy constructor.
608        ///
609        InArcIt(const InArcIt& e) : Arc(e) { }
610        /// %Invalid constructor \& conversion.
611
612        /// Initializes the iterator to be invalid.
613        /// \sa Invalid for more details.
614        InArcIt(Invalid) { }
615        /// Sets the iterator to the first incoming arc.
616
617        /// Sets the iterator to the first incoming arc of the given node.
618        ///
619        InArcIt(const BpGraph& g, const Node& n) {
620          ignore_unused_variable_warning(n);
621          ignore_unused_variable_warning(g);
622        }
623        /// Sets the iterator to the given arc.
624
625        /// Sets the iterator to the given arc of the given graph.
626        ///
627        InArcIt(const BpGraph&, const Arc&) { }
628        /// Next incoming arc
629
630        /// Assign the iterator to the next
631        /// incoming arc of the corresponding node.
632        InArcIt& operator++() { return *this; }
633      };
634
635      /// \brief Standard graph map type for the nodes.
636      ///
637      /// Standard graph map type for the nodes.
638      /// It conforms to the ReferenceMap concept.
639      template<class T>
640      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
641      {
642      public:
643
644        /// Constructor
645        explicit NodeMap(const BpGraph&) { }
646        /// Constructor with given initial value
647        NodeMap(const BpGraph&, T) { }
648
649      private:
650        ///Copy constructor
651        NodeMap(const NodeMap& nm) :
652          ReferenceMap<Node, T, T&, const T&>(nm) { }
653        ///Assignment operator
654        template <typename CMap>
655        NodeMap& operator=(const CMap&) {
656          checkConcept<ReadMap<Node, T>, CMap>();
657          return *this;
658        }
659      };
660
661      /// \brief Standard graph map type for the red nodes.
662      ///
663      /// Standard graph map type for the red nodes.
664      /// It conforms to the ReferenceMap concept.
665      template<class T>
666      class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
667      {
668      public:
669
670        /// Constructor
671        explicit RedNodeMap(const BpGraph&) { }
672        /// Constructor with given initial value
673        RedNodeMap(const BpGraph&, T) { }
674
675      private:
676        ///Copy constructor
677        RedNodeMap(const RedNodeMap& nm) :
678          ReferenceMap<Node, T, T&, const T&>(nm) { }
679        ///Assignment operator
680        template <typename CMap>
681        RedNodeMap& operator=(const CMap&) {
682          checkConcept<ReadMap<Node, T>, CMap>();
683          return *this;
684        }
685      };
686
687      /// \brief Standard graph map type for the blue nodes.
688      ///
689      /// Standard graph map type for the blue nodes.
690      /// It conforms to the ReferenceMap concept.
691      template<class T>
692      class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
693      {
694      public:
695
696        /// Constructor
697        explicit BlueNodeMap(const BpGraph&) { }
698        /// Constructor with given initial value
699        BlueNodeMap(const BpGraph&, T) { }
700
701      private:
702        ///Copy constructor
703        BlueNodeMap(const BlueNodeMap& nm) :
704          ReferenceMap<Node, T, T&, const T&>(nm) { }
705        ///Assignment operator
706        template <typename CMap>
707        BlueNodeMap& operator=(const CMap&) {
708          checkConcept<ReadMap<Node, T>, CMap>();
709          return *this;
710        }
711      };
712
713      /// \brief Standard graph map type for the arcs.
714      ///
715      /// Standard graph map type for the arcs.
716      /// It conforms to the ReferenceMap concept.
717      template<class T>
718      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
719      {
720      public:
721
722        /// Constructor
723        explicit ArcMap(const BpGraph&) { }
724        /// Constructor with given initial value
725        ArcMap(const BpGraph&, T) { }
726
727      private:
728        ///Copy constructor
729        ArcMap(const ArcMap& em) :
730          ReferenceMap<Arc, T, T&, const T&>(em) { }
731        ///Assignment operator
732        template <typename CMap>
733        ArcMap& operator=(const CMap&) {
734          checkConcept<ReadMap<Arc, T>, CMap>();
735          return *this;
736        }
737      };
738
739      /// \brief Standard graph map type for the edges.
740      ///
741      /// Standard graph map type for the edges.
742      /// It conforms to the ReferenceMap concept.
743      template<class T>
744      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
745      {
746      public:
747
748        /// Constructor
749        explicit EdgeMap(const BpGraph&) { }
750        /// Constructor with given initial value
751        EdgeMap(const BpGraph&, T) { }
752
753      private:
754        ///Copy constructor
755        EdgeMap(const EdgeMap& em) :
756          ReferenceMap<Edge, T, T&, const T&>(em) {}
757        ///Assignment operator
758        template <typename CMap>
759        EdgeMap& operator=(const CMap&) {
760          checkConcept<ReadMap<Edge, T>, CMap>();
761          return *this;
762        }
763      };
764
765      /// \brief Gives back %true for red nodes.
766      ///
767      /// Gives back %true for red nodes.
768      bool red(const Node&) const { return true; }
769
770      /// \brief Gives back %true for blue nodes.
771      ///
772      /// Gives back %true for blue nodes.
773      bool blue(const Node&) const { return true; }
774
775      /// \brief Converts the node to red node object.
776      ///
777      /// This function converts unsafely the node to red node
778      /// object. It should be called only if the node is from the red
779      /// partition or INVALID.
780      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
781
782      /// \brief Converts the node to blue node object.
783      ///
784      /// This function converts unsafely the node to blue node
785      /// object. It should be called only if the node is from the red
786      /// partition or INVALID.
787      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
788
789      /// \brief Converts the node to red node object.
790      ///
791      /// This function converts safely the node to red node
792      /// object. If the node is not from the red partition, then it
793      /// returns INVALID.
794      RedNode asRedNode(const Node&) const { return RedNode(); }
795
796      /// \brief Converts the node to blue node object.
797      ///
798      /// This function converts unsafely the node to blue node
799      /// object. If the node is not from the blue partition, then it
800      /// returns INVALID.
801      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
802
803      /// \brief Gives back the red end node of the edge.
804      ///
805      /// Gives back the red end node of the edge.
806      RedNode redNode(const Edge&) const { return RedNode(); }
807
808      /// \brief Gives back the blue end node of the edge.
809      ///
810      /// Gives back the blue end node of the edge.
811      BlueNode blueNode(const Edge&) const { return BlueNode(); }
812
813      /// \brief The first node of the edge.
814      ///
815      /// It is a synonim for the \c redNode().
816      Node u(Edge) const { return INVALID; }
817
818      /// \brief The second node of the edge.
819      ///
820      /// It is a synonim for the \c blueNode().
821      Node v(Edge) const { return INVALID; }
822
823      /// \brief The source node of the arc.
824      ///
825      /// Returns the source node of the given arc.
826      Node source(Arc) const { return INVALID; }
827
828      /// \brief The target node of the arc.
829      ///
830      /// Returns the target node of the given arc.
831      Node target(Arc) const { return INVALID; }
832
833      /// \brief The ID of the node.
834      ///
835      /// Returns the ID of the given node.
836      int id(Node) const { return -1; }
837
838      /// \brief The red ID of the node.
839      ///
840      /// Returns the red ID of the given node.
841      int id(RedNode) const { return -1; }
842
843      /// \brief The blue ID of the node.
844      ///
845      /// Returns the blue ID of the given node.
846      int id(BlueNode) const { return -1; }
847
848      /// \brief The ID of the edge.
849      ///
850      /// Returns the ID of the given edge.
851      int id(Edge) const { return -1; }
852
853      /// \brief The ID of the arc.
854      ///
855      /// Returns the ID of the given arc.
856      int id(Arc) const { return -1; }
857
858      /// \brief The node with the given ID.
859      ///
860      /// Returns the node with the given ID.
861      /// \pre The argument should be a valid node ID in the graph.
862      Node nodeFromId(int) const { return INVALID; }
863
864      /// \brief The edge with the given ID.
865      ///
866      /// Returns the edge with the given ID.
867      /// \pre The argument should be a valid edge ID in the graph.
868      Edge edgeFromId(int) const { return INVALID; }
869
870      /// \brief The arc with the given ID.
871      ///
872      /// Returns the arc with the given ID.
873      /// \pre The argument should be a valid arc ID in the graph.
874      Arc arcFromId(int) const { return INVALID; }
875
876      /// \brief An upper bound on the node IDs.
877      ///
878      /// Returns an upper bound on the node IDs.
879      int maxNodeId() const { return -1; }
880
881      /// \brief An upper bound on the red IDs.
882      ///
883      /// Returns an upper bound on the red IDs.
884      int maxRedId() const { return -1; }
885
886      /// \brief An upper bound on the blue IDs.
887      ///
888      /// Returns an upper bound on the blue IDs.
889      int maxBlueId() const { return -1; }
890
891      /// \brief An upper bound on the edge IDs.
892      ///
893      /// Returns an upper bound on the edge IDs.
894      int maxEdgeId() const { return -1; }
895
896      /// \brief An upper bound on the arc IDs.
897      ///
898      /// Returns an upper bound on the arc IDs.
899      int maxArcId() const { return -1; }
900
901      /// \brief The direction of the arc.
902      ///
903      /// Returns \c true if the given arc goes from a red node to a blue node.
904      bool direction(Arc) const { return true; }
905
906      /// \brief Direct the edge.
907      ///
908      /// Direct the given edge. The returned arc
909      /// represents the given edge and its direction comes
910      /// from the bool parameter. If it is \c true, then the source of the node
911      /// will be a red node.
912      Arc direct(Edge, bool) const {
913        return INVALID;
914      }
915
916      /// \brief Direct the edge.
917      ///
918      /// Direct the given edge. The returned arc represents the given
919      /// edge and its source node is the given node.
920      Arc direct(Edge, Node) const {
921        return INVALID;
922      }
923
924      /// \brief The oppositely directed arc.
925      ///
926      /// Returns the oppositely directed arc representing the same edge.
927      Arc oppositeArc(Arc) const { return INVALID; }
928
929      /// \brief The opposite node on the edge.
930      ///
931      /// Returns the opposite node on the given edge.
932      Node oppositeNode(Node, Edge) const { return INVALID; }
933
934      void first(Node&) const {}
935      void next(Node&) const {}
936
937      void firstRed(RedNode&) const {}
938      void nextRed(RedNode&) const {}
939
940      void firstBlue(BlueNode&) const {}
941      void nextBlue(BlueNode&) const {}
942
943      void first(Edge&) const {}
944      void next(Edge&) const {}
945
946      void first(Arc&) const {}
947      void next(Arc&) const {}
948
949      void firstOut(Arc&, Node) const {}
950      void nextOut(Arc&) const {}
951
952      void firstIn(Arc&, Node) const {}
953      void nextIn(Arc&) const {}
954
955      void firstInc(Edge &, bool &, const Node &) const {}
956      void nextInc(Edge &, bool &) const {}
957
958      // The second parameter is dummy.
959      Node fromId(int, Node) const { return INVALID; }
960      // The second parameter is dummy.
961      Edge fromId(int, Edge) const { return INVALID; }
962      // The second parameter is dummy.
963      Arc fromId(int, Arc) const { return INVALID; }
964
965      // Dummy parameter.
966      int maxId(Node) const { return -1; }
967      // Dummy parameter.
968      int maxId(RedNode) const { return -1; }
969      // Dummy parameter.
970      int maxId(BlueNode) const { return -1; }
971      // Dummy parameter.
972      int maxId(Edge) const { return -1; }
973      // Dummy parameter.
974      int maxId(Arc) const { return -1; }
975
976      /// \brief The base node of the iterator.
977      ///
978      /// Returns the base node of the given incident edge iterator.
979      Node baseNode(IncEdgeIt) const { return INVALID; }
980
981      /// \brief The running node of the iterator.
982      ///
983      /// Returns the running node of the given incident edge iterator.
984      Node runningNode(IncEdgeIt) const { return INVALID; }
985
986      /// \brief The base node of the iterator.
987      ///
988      /// Returns the base node of the given outgoing arc iterator
989      /// (i.e. the source node of the corresponding arc).
990      Node baseNode(OutArcIt) const { return INVALID; }
991
992      /// \brief The running node of the iterator.
993      ///
994      /// Returns the running node of the given outgoing arc iterator
995      /// (i.e. the target node of the corresponding arc).
996      Node runningNode(OutArcIt) const { return INVALID; }
997
998      /// \brief The base node of the iterator.
999      ///
1000      /// Returns the base node of the given incoming arc iterator
1001      /// (i.e. the target node of the corresponding arc).
1002      Node baseNode(InArcIt) const { return INVALID; }
1003
1004      /// \brief The running node of the iterator.
1005      ///
1006      /// Returns the running node of the given incoming arc iterator
1007      /// (i.e. the source node of the corresponding arc).
1008      Node runningNode(InArcIt) const { return INVALID; }
1009
1010      template <typename _BpGraph>
1011      struct Constraints {
1012        void constraints() {
1013          checkConcept<BaseBpGraphComponent, _BpGraph>();
1014          checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1015          checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1016          checkConcept<MappableBpGraphComponent<>, _BpGraph>();
1017        }
1018      };
1019
1020    };
1021
1022  }
1023
1024}
1025
1026#endif
Note: See TracBrowser for help on using the repository browser.