COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/bpgraph.h @ 1186:2e959a5a0c2d

Last change on this file since 1186:2e959a5a0c2d was 1186:2e959a5a0c2d, checked in by Balazs Dezso <deba@…>, 9 years ago

Add bipartite graph concepts (#69)

File size: 31.7 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 RedIt and BlueIt in the two
52    /// node sets. With RedMap and BlueMap values can be assigned to
53    /// 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        /// Constructor for conversion from a node.
153
154        /// Constructor for conversion from a node. The conversion can
155        /// be invalid, since the Node can be member of the blue
156        /// set.
157        RedNode(const Node&) {}
158      };
159
160      /// Class to represent blue nodes.
161
162      /// This class represents the blue nodes of the graph. It does
163      /// not supposed to be used directly, because the nodes can be
164      /// represented as Node instances. This class can be used as
165      /// template parameter for special map classes.
166      class BlueNode : public Node {
167      public:
168        /// Default constructor
169
170        /// Default constructor.
171        /// \warning It sets the object to an undefined value.
172        BlueNode() { }
173        /// Copy constructor.
174
175        /// Copy constructor.
176        ///
177        BlueNode(const BlueNode&) : Node() { }
178
179        /// %Invalid constructor \& conversion.
180
181        /// Initializes the object to be invalid.
182        /// \sa Invalid for more details.
183        BlueNode(Invalid) { }
184
185        /// Constructor for conversion from a node.
186
187        /// Constructor for conversion from a node. The conversion can
188        /// be invalid, since the Node can be member of the red
189        /// set.
190        BlueNode(const Node&) {}
191      };
192
193      /// Iterator class for the red nodes.
194
195      /// This iterator goes through each red node of the graph.
196      /// Its usage is quite simple, for example, you can count the number
197      /// of red nodes in a graph \c g of type \c %BpGraph like this:
198      ///\code
199      /// int count=0;
200      /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
201      ///\endcode
202      class RedIt : public Node {
203      public:
204        /// Default constructor
205
206        /// Default constructor.
207        /// \warning It sets the iterator to an undefined value.
208        RedIt() { }
209        /// Copy constructor.
210
211        /// Copy constructor.
212        ///
213        RedIt(const RedIt& n) : Node(n) { }
214        /// %Invalid constructor \& conversion.
215
216        /// Initializes the iterator to be invalid.
217        /// \sa Invalid for more details.
218        RedIt(Invalid) { }
219        /// Sets the iterator to the first red node.
220
221        /// Sets the iterator to the first red node of the given
222        /// digraph.
223        explicit RedIt(const BpGraph&) { }
224        /// Sets the iterator to the given red node.
225
226        /// Sets the iterator to the given red node of the given
227        /// digraph.
228        RedIt(const BpGraph&, const Node&) { }
229        /// Next node.
230
231        /// Assign the iterator to the next red node.
232        ///
233        RedIt& operator++() { return *this; }
234      };
235
236      /// Iterator class for the blue nodes.
237
238      /// This iterator goes through each blue node of the graph.
239      /// Its usage is quite simple, for example, you can count the number
240      /// of blue nodes in a graph \c g of type \c %BpGraph like this:
241      ///\code
242      /// int count=0;
243      /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
244      ///\endcode
245      class BlueIt : public Node {
246      public:
247        /// Default constructor
248
249        /// Default constructor.
250        /// \warning It sets the iterator to an undefined value.
251        BlueIt() { }
252        /// Copy constructor.
253
254        /// Copy constructor.
255        ///
256        BlueIt(const BlueIt& n) : Node(n) { }
257        /// %Invalid constructor \& conversion.
258
259        /// Initializes the iterator to be invalid.
260        /// \sa Invalid for more details.
261        BlueIt(Invalid) { }
262        /// Sets the iterator to the first blue node.
263
264        /// Sets the iterator to the first blue node of the given
265        /// digraph.
266        explicit BlueIt(const BpGraph&) { }
267        /// Sets the iterator to the given blue node.
268
269        /// Sets the iterator to the given blue node of the given
270        /// digraph.
271        BlueIt(const BpGraph&, const Node&) { }
272        /// Next node.
273
274        /// Assign the iterator to the next blue node.
275        ///
276        BlueIt& operator++() { return *this; }
277      };
278
279      /// Iterator class for the nodes.
280
281      /// This iterator goes through each node of the graph.
282      /// Its usage is quite simple, for example, you can count the number
283      /// of nodes in a graph \c g of type \c %BpGraph like this:
284      ///\code
285      /// int count=0;
286      /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
287      ///\endcode
288      class NodeIt : public Node {
289      public:
290        /// Default constructor
291
292        /// Default constructor.
293        /// \warning It sets the iterator to an undefined value.
294        NodeIt() { }
295        /// Copy constructor.
296
297        /// Copy constructor.
298        ///
299        NodeIt(const NodeIt& n) : Node(n) { }
300        /// %Invalid constructor \& conversion.
301
302        /// Initializes the iterator to be invalid.
303        /// \sa Invalid for more details.
304        NodeIt(Invalid) { }
305        /// Sets the iterator to the first node.
306
307        /// Sets the iterator to the first node of the given digraph.
308        ///
309        explicit NodeIt(const BpGraph&) { }
310        /// Sets the iterator to the given node.
311
312        /// Sets the iterator to the given node of the given digraph.
313        ///
314        NodeIt(const BpGraph&, const Node&) { }
315        /// Next node.
316
317        /// Assign the iterator to the next node.
318        ///
319        NodeIt& operator++() { return *this; }
320      };
321
322
323      /// The edge type of the graph
324
325      /// This class identifies an edge of the graph. It also serves
326      /// as a base class of the edge iterators,
327      /// thus they will convert to this type.
328      class Edge {
329      public:
330        /// Default constructor
331
332        /// Default constructor.
333        /// \warning It sets the object to an undefined value.
334        Edge() { }
335        /// Copy constructor.
336
337        /// Copy constructor.
338        ///
339        Edge(const Edge&) { }
340        /// %Invalid constructor \& conversion.
341
342        /// Initializes the object to be invalid.
343        /// \sa Invalid for more details.
344        Edge(Invalid) { }
345        /// Equality operator
346
347        /// Equality operator.
348        ///
349        /// Two iterators are equal if and only if they point to the
350        /// same object or both are \c INVALID.
351        bool operator==(Edge) const { return true; }
352        /// Inequality operator
353
354        /// Inequality operator.
355        bool operator!=(Edge) const { return true; }
356
357        /// Artificial ordering operator.
358
359        /// Artificial ordering operator.
360        ///
361        /// \note This operator only has to define some strict ordering of
362        /// the edges; this order has nothing to do with the iteration
363        /// ordering of the edges.
364        bool operator<(Edge) const { return false; }
365      };
366
367      /// Iterator class for the edges.
368
369      /// This iterator goes through each edge of the graph.
370      /// Its usage is quite simple, for example, you can count the number
371      /// of edges in a graph \c g of type \c %BpGraph as follows:
372      ///\code
373      /// int count=0;
374      /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
375      ///\endcode
376      class EdgeIt : public Edge {
377      public:
378        /// Default constructor
379
380        /// Default constructor.
381        /// \warning It sets the iterator to an undefined value.
382        EdgeIt() { }
383        /// Copy constructor.
384
385        /// Copy constructor.
386        ///
387        EdgeIt(const EdgeIt& e) : Edge(e) { }
388        /// %Invalid constructor \& conversion.
389
390        /// Initializes the iterator to be invalid.
391        /// \sa Invalid for more details.
392        EdgeIt(Invalid) { }
393        /// Sets the iterator to the first edge.
394
395        /// Sets the iterator to the first edge of the given graph.
396        ///
397        explicit EdgeIt(const BpGraph&) { }
398        /// Sets the iterator to the given edge.
399
400        /// Sets the iterator to the given edge of the given graph.
401        ///
402        EdgeIt(const BpGraph&, const Edge&) { }
403        /// Next edge
404
405        /// Assign the iterator to the next edge.
406        ///
407        EdgeIt& operator++() { return *this; }
408      };
409
410      /// Iterator class for the incident edges of a node.
411
412      /// This iterator goes trough the incident undirected edges
413      /// of a certain node of a graph.
414      /// Its usage is quite simple, for example, you can compute the
415      /// degree (i.e. the number of incident edges) of a node \c n
416      /// in a graph \c g of type \c %BpGraph as follows.
417      ///
418      ///\code
419      /// int count=0;
420      /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
421      ///\endcode
422      ///
423      /// \warning Loop edges will be iterated twice.
424      class IncEdgeIt : public Edge {
425      public:
426        /// Default constructor
427
428        /// Default constructor.
429        /// \warning It sets the iterator to an undefined value.
430        IncEdgeIt() { }
431        /// Copy constructor.
432
433        /// Copy constructor.
434        ///
435        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
436        /// %Invalid constructor \& conversion.
437
438        /// Initializes the iterator to be invalid.
439        /// \sa Invalid for more details.
440        IncEdgeIt(Invalid) { }
441        /// Sets the iterator to the first incident edge.
442
443        /// Sets the iterator to the first incident edge of the given node.
444        ///
445        IncEdgeIt(const BpGraph&, const Node&) { }
446        /// Sets the iterator to the given edge.
447
448        /// Sets the iterator to the given edge of the given graph.
449        ///
450        IncEdgeIt(const BpGraph&, const Edge&) { }
451        /// Next incident edge
452
453        /// Assign the iterator to the next incident edge
454        /// of the corresponding node.
455        IncEdgeIt& operator++() { return *this; }
456      };
457
458      /// The arc type of the graph
459
460      /// This class identifies a directed arc of the graph. It also serves
461      /// as a base class of the arc iterators,
462      /// thus they will convert to this type.
463      class Arc {
464      public:
465        /// Default constructor
466
467        /// Default constructor.
468        /// \warning It sets the object to an undefined value.
469        Arc() { }
470        /// Copy constructor.
471
472        /// Copy constructor.
473        ///
474        Arc(const Arc&) { }
475        /// %Invalid constructor \& conversion.
476
477        /// Initializes the object to be invalid.
478        /// \sa Invalid for more details.
479        Arc(Invalid) { }
480        /// Equality operator
481
482        /// Equality operator.
483        ///
484        /// Two iterators are equal if and only if they point to the
485        /// same object or both are \c INVALID.
486        bool operator==(Arc) const { return true; }
487        /// Inequality operator
488
489        /// Inequality operator.
490        bool operator!=(Arc) const { return true; }
491
492        /// Artificial ordering operator.
493
494        /// Artificial ordering operator.
495        ///
496        /// \note This operator only has to define some strict ordering of
497        /// the arcs; this order has nothing to do with the iteration
498        /// ordering of the arcs.
499        bool operator<(Arc) const { return false; }
500
501        /// Converison to \c Edge
502
503        /// Converison to \c Edge.
504        ///
505        operator Edge() const { return Edge(); }
506      };
507
508      /// Iterator class for the arcs.
509
510      /// This iterator goes through each directed arc of the graph.
511      /// Its usage is quite simple, for example, you can count the number
512      /// of arcs in a graph \c g of type \c %BpGraph as follows:
513      ///\code
514      /// int count=0;
515      /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
516      ///\endcode
517      class ArcIt : public Arc {
518      public:
519        /// Default constructor
520
521        /// Default constructor.
522        /// \warning It sets the iterator to an undefined value.
523        ArcIt() { }
524        /// Copy constructor.
525
526        /// Copy constructor.
527        ///
528        ArcIt(const ArcIt& e) : Arc(e) { }
529        /// %Invalid constructor \& conversion.
530
531        /// Initializes the iterator to be invalid.
532        /// \sa Invalid for more details.
533        ArcIt(Invalid) { }
534        /// Sets the iterator to the first arc.
535
536        /// Sets the iterator to the first arc of the given graph.
537        ///
538        explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
539        /// Sets the iterator to the given arc.
540
541        /// Sets the iterator to the given arc of the given graph.
542        ///
543        ArcIt(const BpGraph&, const Arc&) { }
544        /// Next arc
545
546        /// Assign the iterator to the next arc.
547        ///
548        ArcIt& operator++() { return *this; }
549      };
550
551      /// Iterator class for the outgoing arcs of a node.
552
553      /// This iterator goes trough the \e outgoing directed arcs of a
554      /// certain node of a graph.
555      /// Its usage is quite simple, for example, you can count the number
556      /// of outgoing arcs of a node \c n
557      /// in a graph \c g of type \c %BpGraph as follows.
558      ///\code
559      /// int count=0;
560      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
561      ///\endcode
562      class OutArcIt : public Arc {
563      public:
564        /// Default constructor
565
566        /// Default constructor.
567        /// \warning It sets the iterator to an undefined value.
568        OutArcIt() { }
569        /// Copy constructor.
570
571        /// Copy constructor.
572        ///
573        OutArcIt(const OutArcIt& e) : Arc(e) { }
574        /// %Invalid constructor \& conversion.
575
576        /// Initializes the iterator to be invalid.
577        /// \sa Invalid for more details.
578        OutArcIt(Invalid) { }
579        /// Sets the iterator to the first outgoing arc.
580
581        /// Sets the iterator to the first outgoing arc of the given node.
582        ///
583        OutArcIt(const BpGraph& n, const Node& g) {
584          ignore_unused_variable_warning(n);
585          ignore_unused_variable_warning(g);
586        }
587        /// Sets the iterator to the given arc.
588
589        /// Sets the iterator to the given arc of the given graph.
590        ///
591        OutArcIt(const BpGraph&, const Arc&) { }
592        /// Next outgoing arc
593
594        /// Assign the iterator to the next
595        /// outgoing arc of the corresponding node.
596        OutArcIt& operator++() { return *this; }
597      };
598
599      /// Iterator class for the incoming arcs of a node.
600
601      /// This iterator goes trough the \e incoming directed arcs of a
602      /// certain node of a graph.
603      /// Its usage is quite simple, for example, you can count the number
604      /// of incoming arcs of a node \c n
605      /// in a graph \c g of type \c %BpGraph as follows.
606      ///\code
607      /// int count=0;
608      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
609      ///\endcode
610      class InArcIt : public Arc {
611      public:
612        /// Default constructor
613
614        /// Default constructor.
615        /// \warning It sets the iterator to an undefined value.
616        InArcIt() { }
617        /// Copy constructor.
618
619        /// Copy constructor.
620        ///
621        InArcIt(const InArcIt& e) : Arc(e) { }
622        /// %Invalid constructor \& conversion.
623
624        /// Initializes the iterator to be invalid.
625        /// \sa Invalid for more details.
626        InArcIt(Invalid) { }
627        /// Sets the iterator to the first incoming arc.
628
629        /// Sets the iterator to the first incoming arc of the given node.
630        ///
631        InArcIt(const BpGraph& g, const Node& n) {
632          ignore_unused_variable_warning(n);
633          ignore_unused_variable_warning(g);
634        }
635        /// Sets the iterator to the given arc.
636
637        /// Sets the iterator to the given arc of the given graph.
638        ///
639        InArcIt(const BpGraph&, const Arc&) { }
640        /// Next incoming arc
641
642        /// Assign the iterator to the next
643        /// incoming arc of the corresponding node.
644        InArcIt& operator++() { return *this; }
645      };
646
647      /// \brief Standard graph map type for the nodes.
648      ///
649      /// Standard graph map type for the nodes.
650      /// It conforms to the ReferenceMap concept.
651      template<class T>
652      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
653      {
654      public:
655
656        /// Constructor
657        explicit NodeMap(const BpGraph&) { }
658        /// Constructor with given initial value
659        NodeMap(const BpGraph&, T) { }
660
661      private:
662        ///Copy constructor
663        NodeMap(const NodeMap& nm) :
664          ReferenceMap<Node, T, T&, const T&>(nm) { }
665        ///Assignment operator
666        template <typename CMap>
667        NodeMap& operator=(const CMap&) {
668          checkConcept<ReadMap<Node, T>, CMap>();
669          return *this;
670        }
671      };
672
673      /// \brief Standard graph map type for the red nodes.
674      ///
675      /// Standard graph map type for the red nodes.
676      /// It conforms to the ReferenceMap concept.
677      template<class T>
678      class RedMap : public ReferenceMap<Node, T, T&, const T&>
679      {
680      public:
681
682        /// Constructor
683        explicit RedMap(const BpGraph&) { }
684        /// Constructor with given initial value
685        RedMap(const BpGraph&, T) { }
686
687      private:
688        ///Copy constructor
689        RedMap(const RedMap& nm) :
690          ReferenceMap<Node, T, T&, const T&>(nm) { }
691        ///Assignment operator
692        template <typename CMap>
693        RedMap& operator=(const CMap&) {
694          checkConcept<ReadMap<Node, T>, CMap>();
695          return *this;
696        }
697      };
698
699      /// \brief Standard graph map type for the blue nodes.
700      ///
701      /// Standard graph map type for the blue nodes.
702      /// It conforms to the ReferenceMap concept.
703      template<class T>
704      class BlueMap : public ReferenceMap<Node, T, T&, const T&>
705      {
706      public:
707
708        /// Constructor
709        explicit BlueMap(const BpGraph&) { }
710        /// Constructor with given initial value
711        BlueMap(const BpGraph&, T) { }
712
713      private:
714        ///Copy constructor
715        BlueMap(const BlueMap& nm) :
716          ReferenceMap<Node, T, T&, const T&>(nm) { }
717        ///Assignment operator
718        template <typename CMap>
719        BlueMap& operator=(const CMap&) {
720          checkConcept<ReadMap<Node, T>, CMap>();
721          return *this;
722        }
723      };
724
725      /// \brief Standard graph map type for the arcs.
726      ///
727      /// Standard graph map type for the arcs.
728      /// It conforms to the ReferenceMap concept.
729      template<class T>
730      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
731      {
732      public:
733
734        /// Constructor
735        explicit ArcMap(const BpGraph&) { }
736        /// Constructor with given initial value
737        ArcMap(const BpGraph&, T) { }
738
739      private:
740        ///Copy constructor
741        ArcMap(const ArcMap& em) :
742          ReferenceMap<Arc, T, T&, const T&>(em) { }
743        ///Assignment operator
744        template <typename CMap>
745        ArcMap& operator=(const CMap&) {
746          checkConcept<ReadMap<Arc, T>, CMap>();
747          return *this;
748        }
749      };
750
751      /// \brief Standard graph map type for the edges.
752      ///
753      /// Standard graph map type for the edges.
754      /// It conforms to the ReferenceMap concept.
755      template<class T>
756      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
757      {
758      public:
759
760        /// Constructor
761        explicit EdgeMap(const BpGraph&) { }
762        /// Constructor with given initial value
763        EdgeMap(const BpGraph&, T) { }
764
765      private:
766        ///Copy constructor
767        EdgeMap(const EdgeMap& em) :
768          ReferenceMap<Edge, T, T&, const T&>(em) {}
769        ///Assignment operator
770        template <typename CMap>
771        EdgeMap& operator=(const CMap&) {
772          checkConcept<ReadMap<Edge, T>, CMap>();
773          return *this;
774        }
775      };
776
777      /// \brief Gives back %true for red nodes.
778      ///
779      /// Gives back %true for red nodes.
780      bool red(const Node&) const { return true; }
781
782      /// \brief Gives back %true for blue nodes.
783      ///
784      /// Gives back %true for blue nodes.
785      bool blue(const Node&) const { return true; }
786
787      /// \brief Gives back the red end node of the edge.
788      ///
789      /// Gives back the red end node of the edge.
790      Node redNode(const Edge&) const { return Node(); }
791
792      /// \brief Gives back the blue end node of the edge.
793      ///
794      /// Gives back the blue end node of the edge.
795      Node blueNode(const Edge&) const { return Node(); }
796
797      /// \brief The first node of the edge.
798      ///
799      /// It is a synonim for the \c redNode().
800      Node u(Edge) const { return INVALID; }
801
802      /// \brief The second node of the edge.
803      ///
804      /// It is a synonim for the \c blueNode().
805      Node v(Edge) const { return INVALID; }
806
807      /// \brief The source node of the arc.
808      ///
809      /// Returns the source node of the given arc.
810      Node source(Arc) const { return INVALID; }
811
812      /// \brief The target node of the arc.
813      ///
814      /// Returns the target node of the given arc.
815      Node target(Arc) const { return INVALID; }
816
817      /// \brief The ID of the node.
818      ///
819      /// Returns the ID of the given node.
820      int id(Node) const { return -1; }
821
822      /// \brief The red ID of the node.
823      ///
824      /// Returns the red ID of the given node.
825      int redId(Node) const { return -1; }
826
827      /// \brief The red ID of the node.
828      ///
829      /// Returns the red ID of the given node.
830      int id(RedNode) const { return -1; }
831
832      /// \brief The blue ID of the node.
833      ///
834      /// Returns the blue ID of the given node.
835      int blueId(Node) const { return -1; }
836
837      /// \brief The blue ID of the node.
838      ///
839      /// Returns the blue ID of the given node.
840      int id(BlueNode) const { return -1; }
841
842      /// \brief The ID of the edge.
843      ///
844      /// Returns the ID of the given edge.
845      int id(Edge) const { return -1; }
846
847      /// \brief The ID of the arc.
848      ///
849      /// Returns the ID of the given arc.
850      int id(Arc) const { return -1; }
851
852      /// \brief The node with the given ID.
853      ///
854      /// Returns the node with the given ID.
855      /// \pre The argument should be a valid node ID in the graph.
856      Node nodeFromId(int) const { return INVALID; }
857
858      /// \brief The edge with the given ID.
859      ///
860      /// Returns the edge with the given ID.
861      /// \pre The argument should be a valid edge ID in the graph.
862      Edge edgeFromId(int) const { return INVALID; }
863
864      /// \brief The arc with the given ID.
865      ///
866      /// Returns the arc with the given ID.
867      /// \pre The argument should be a valid arc ID in the graph.
868      Arc arcFromId(int) const { return INVALID; }
869
870      /// \brief An upper bound on the node IDs.
871      ///
872      /// Returns an upper bound on the node IDs.
873      int maxNodeId() const { return -1; }
874
875      /// \brief An upper bound on the red IDs.
876      ///
877      /// Returns an upper bound on the red IDs.
878      int maxRedId() const { return -1; }
879
880      /// \brief An upper bound on the blue IDs.
881      ///
882      /// Returns an upper bound on the blue IDs.
883      int maxBlueId() const { return -1; }
884
885      /// \brief An upper bound on the edge IDs.
886      ///
887      /// Returns an upper bound on the edge IDs.
888      int maxEdgeId() const { return -1; }
889
890      /// \brief An upper bound on the arc IDs.
891      ///
892      /// Returns an upper bound on the arc IDs.
893      int maxArcId() const { return -1; }
894
895      /// \brief The direction of the arc.
896      ///
897      /// Returns \c true if the given arc goes from a red node to a blue node.
898      bool direction(Arc) const { return true; }
899
900      /// \brief Direct the edge.
901      ///
902      /// Direct the given edge. The returned arc
903      /// represents the given edge and its direction comes
904      /// from the bool parameter. If it is \c true, then the source of the node
905      /// will be a red node.
906      Arc direct(Edge, bool) const {
907        return INVALID;
908      }
909
910      /// \brief Direct the edge.
911      ///
912      /// Direct the given edge. The returned arc represents the given
913      /// edge and its source node is the given node.
914      Arc direct(Edge, Node) const {
915        return INVALID;
916      }
917
918      /// \brief The oppositely directed arc.
919      ///
920      /// Returns the oppositely directed arc representing the same edge.
921      Arc oppositeArc(Arc) const { return INVALID; }
922
923      /// \brief The opposite node on the edge.
924      ///
925      /// Returns the opposite node on the given edge.
926      Node oppositeNode(Node, Edge) const { return INVALID; }
927
928      void first(Node&) const {}
929      void next(Node&) const {}
930
931      void firstRed(Node&) const {}
932      void nextRed(Node&) const {}
933
934      void firstBlue(Node&) const {}
935      void nextBlue(Node&) const {}
936
937      void first(Edge&) const {}
938      void next(Edge&) const {}
939
940      void first(Arc&) const {}
941      void next(Arc&) const {}
942
943      void firstOut(Arc&, Node) const {}
944      void nextOut(Arc&) const {}
945
946      void firstIn(Arc&, Node) const {}
947      void nextIn(Arc&) const {}
948
949      void firstInc(Edge &, bool &, const Node &) const {}
950      void nextInc(Edge &, bool &) const {}
951
952      // The second parameter is dummy.
953      Node fromId(int, Node) const { return INVALID; }
954      // The second parameter is dummy.
955      Edge fromId(int, Edge) const { return INVALID; }
956      // The second parameter is dummy.
957      Arc fromId(int, Arc) const { return INVALID; }
958
959      // Dummy parameter.
960      int maxId(Node) const { return -1; }
961      // Dummy parameter.
962      int maxId(RedNode) const { return -1; }
963      // Dummy parameter.
964      int maxId(BlueNode) const { return -1; }
965      // Dummy parameter.
966      int maxId(Edge) const { return -1; }
967      // Dummy parameter.
968      int maxId(Arc) const { return -1; }
969
970      /// \brief The base node of the iterator.
971      ///
972      /// Returns the base node of the given incident edge iterator.
973      Node baseNode(IncEdgeIt) const { return INVALID; }
974
975      /// \brief The running node of the iterator.
976      ///
977      /// Returns the running node of the given incident edge iterator.
978      Node runningNode(IncEdgeIt) const { return INVALID; }
979
980      /// \brief The base node of the iterator.
981      ///
982      /// Returns the base node of the given outgoing arc iterator
983      /// (i.e. the source node of the corresponding arc).
984      Node baseNode(OutArcIt) const { return INVALID; }
985
986      /// \brief The running node of the iterator.
987      ///
988      /// Returns the running node of the given outgoing arc iterator
989      /// (i.e. the target node of the corresponding arc).
990      Node runningNode(OutArcIt) const { return INVALID; }
991
992      /// \brief The base node of the iterator.
993      ///
994      /// Returns the base node of the given incomming arc iterator
995      /// (i.e. the target node of the corresponding arc).
996      Node baseNode(InArcIt) const { return INVALID; }
997
998      /// \brief The running node of the iterator.
999      ///
1000      /// Returns the running node of the given incomming arc iterator
1001      /// (i.e. the source node of the corresponding arc).
1002      Node runningNode(InArcIt) const { return INVALID; }
1003
1004      template <typename _BpGraph>
1005      struct Constraints {
1006        void constraints() {
1007          checkConcept<BaseBpGraphComponent, _BpGraph>();
1008          checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1009          checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1010          checkConcept<MappableBpGraphComponent<>, _BpGraph>();
1011        }
1012      };
1013
1014    };
1015
1016  }
1017
1018}
1019
1020#endif
Note: See TracBrowser for help on using the repository browser.