COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/graph_components.h @ 1193:c8fa41fcc4a7

Last change on this file since 1193:c8fa41fcc4a7 was 1193:c8fa41fcc4a7, checked in by Balazs Dezso <deba@…>, 8 years ago

Type safe red and blue node set (#69)

File size: 69.2 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 concepts of graph components.
22
23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
25
26#include <lemon/core.h>
27#include <lemon/concepts/maps.h>
28
29#include <lemon/bits/alteration_notifier.h>
30
31namespace lemon {
32  namespace concepts {
33
34    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
35    ///
36    /// This class describes the concept of \c Node, \c Arc and \c Edge
37    /// subtypes of digraph and graph types.
38    ///
39    /// \note This class is a template class so that we can use it to
40    /// create graph skeleton classes. The reason for this is that \c Node
41    /// and \c Arc (or \c Edge) types should \e not derive from the same
42    /// base class. For \c Node you should instantiate it with character
43    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
44#ifndef DOXYGEN
45    template <char sel = '0'>
46#endif
47    class GraphItem {
48    public:
49      /// \brief Default constructor.
50      ///
51      /// Default constructor.
52      /// \warning The default constructor is not required to set
53      /// the item to some well-defined value. So you should consider it
54      /// as uninitialized.
55      GraphItem() {}
56
57      /// \brief Copy constructor.
58      ///
59      /// Copy constructor.
60      GraphItem(const GraphItem &) {}
61
62      /// \brief Constructor for conversion from \c INVALID.
63      ///
64      /// Constructor for conversion from \c INVALID.
65      /// It initializes the item to be invalid.
66      /// \sa Invalid for more details.
67      GraphItem(Invalid) {}
68
69      /// \brief Assignment operator.
70      ///
71      /// Assignment operator for the item.
72      GraphItem& operator=(const GraphItem&) { return *this; }
73
74      /// \brief Assignment operator for INVALID.
75      ///
76      /// This operator makes the item invalid.
77      GraphItem& operator=(Invalid) { return *this; }
78
79      /// \brief Equality operator.
80      ///
81      /// Equality operator.
82      bool operator==(const GraphItem&) const { return false; }
83
84      /// \brief Inequality operator.
85      ///
86      /// Inequality operator.
87      bool operator!=(const GraphItem&) const { return false; }
88
89      /// \brief Ordering operator.
90      ///
91      /// This operator defines an ordering of the items.
92      /// It makes possible to use graph item types as key types in
93      /// associative containers (e.g. \c std::map).
94      ///
95      /// \note This operator only has to define some strict ordering of
96      /// the items; this order has nothing to do with the iteration
97      /// ordering of the items.
98      bool operator<(const GraphItem&) const { return false; }
99
100      template<typename _GraphItem>
101      struct Constraints {
102        void constraints() {
103          _GraphItem i1;
104          i1=INVALID;
105          _GraphItem i2 = i1;
106          _GraphItem i3 = INVALID;
107
108          i1 = i2 = i3;
109
110          bool b;
111          ignore_unused_variable_warning(b);
112
113          b = (ia == ib) && (ia != ib);
114          b = (ia == INVALID) && (ib != INVALID);
115          b = (ia < ib);
116        }
117
118        const _GraphItem &ia;
119        const _GraphItem &ib;
120        Constraints() {}
121      };
122    };
123
124    /// \brief Base skeleton class for directed graphs.
125    ///
126    /// This class describes the base interface of directed graph types.
127    /// All digraph %concepts have to conform to this class.
128    /// It just provides types for nodes and arcs and functions
129    /// to get the source and the target nodes of arcs.
130    class BaseDigraphComponent {
131    public:
132
133      typedef BaseDigraphComponent Digraph;
134
135      /// \brief Node class of the digraph.
136      ///
137      /// This class represents the nodes of the digraph.
138      typedef GraphItem<'n'> Node;
139
140      /// \brief Arc class of the digraph.
141      ///
142      /// This class represents the arcs of the digraph.
143      typedef GraphItem<'a'> Arc;
144
145      /// \brief Return the source node of an arc.
146      ///
147      /// This function returns the source node of an arc.
148      Node source(const Arc&) const { return INVALID; }
149
150      /// \brief Return the target node of an arc.
151      ///
152      /// This function returns the target node of an arc.
153      Node target(const Arc&) const { return INVALID; }
154
155      /// \brief Return the opposite node on the given arc.
156      ///
157      /// This function returns the opposite node on the given arc.
158      Node oppositeNode(const Node&, const Arc&) const {
159        return INVALID;
160      }
161
162      template <typename _Digraph>
163      struct Constraints {
164        typedef typename _Digraph::Node Node;
165        typedef typename _Digraph::Arc Arc;
166
167        void constraints() {
168          checkConcept<GraphItem<'n'>, Node>();
169          checkConcept<GraphItem<'a'>, Arc>();
170          {
171            Node n;
172            Arc e(INVALID);
173            n = digraph.source(e);
174            n = digraph.target(e);
175            n = digraph.oppositeNode(n, e);
176          }
177        }
178
179        const _Digraph& digraph;
180        Constraints() {}
181      };
182    };
183
184    /// \brief Base skeleton class for undirected graphs.
185    ///
186    /// This class describes the base interface of undirected graph types.
187    /// All graph %concepts have to conform to this class.
188    /// It extends the interface of \ref BaseDigraphComponent with an
189    /// \c Edge type and functions to get the end nodes of edges,
190    /// to convert from arcs to edges and to get both direction of edges.
191    class BaseGraphComponent : public BaseDigraphComponent {
192    public:
193
194      typedef BaseGraphComponent Graph;
195
196      typedef BaseDigraphComponent::Node Node;
197      typedef BaseDigraphComponent::Arc Arc;
198
199      /// \brief Undirected edge class of the graph.
200      ///
201      /// This class represents the undirected edges of the graph.
202      /// Undirected graphs can be used as directed graphs, each edge is
203      /// represented by two opposite directed arcs.
204      class Edge : public GraphItem<'e'> {
205        typedef GraphItem<'e'> Parent;
206
207      public:
208        /// \brief Default constructor.
209        ///
210        /// Default constructor.
211        /// \warning The default constructor is not required to set
212        /// the item to some well-defined value. So you should consider it
213        /// as uninitialized.
214        Edge() {}
215
216        /// \brief Copy constructor.
217        ///
218        /// Copy constructor.
219        Edge(const Edge &) : Parent() {}
220
221        /// \brief Constructor for conversion from \c INVALID.
222        ///
223        /// Constructor for conversion from \c INVALID.
224        /// It initializes the item to be invalid.
225        /// \sa Invalid for more details.
226        Edge(Invalid) {}
227
228        /// \brief Constructor for conversion from an arc.
229        ///
230        /// Constructor for conversion from an arc.
231        /// Besides the core graph item functionality each arc should
232        /// be convertible to the represented edge.
233        Edge(const Arc&) {}
234     };
235
236      /// \brief Return one end node of an edge.
237      ///
238      /// This function returns one end node of an edge.
239      Node u(const Edge&) const { return INVALID; }
240
241      /// \brief Return the other end node of an edge.
242      ///
243      /// This function returns the other end node of an edge.
244      Node v(const Edge&) const { return INVALID; }
245
246      /// \brief Return a directed arc related to an edge.
247      ///
248      /// This function returns a directed arc from its direction and the
249      /// represented edge.
250      Arc direct(const Edge&, bool) const { return INVALID; }
251
252      /// \brief Return a directed arc related to an edge.
253      ///
254      /// This function returns a directed arc from its source node and the
255      /// represented edge.
256      Arc direct(const Edge&, const Node&) const { return INVALID; }
257
258      /// \brief Return the direction of the arc.
259      ///
260      /// Returns the direction of the arc. Each arc represents an
261      /// edge with a direction. It gives back the
262      /// direction.
263      bool direction(const Arc&) const { return true; }
264
265      /// \brief Return the opposite arc.
266      ///
267      /// This function returns the opposite arc, i.e. the arc representing
268      /// the same edge and has opposite direction.
269      Arc oppositeArc(const Arc&) const { return INVALID; }
270
271      template <typename _Graph>
272      struct Constraints {
273        typedef typename _Graph::Node Node;
274        typedef typename _Graph::Arc Arc;
275        typedef typename _Graph::Edge Edge;
276
277        void constraints() {
278          checkConcept<BaseDigraphComponent, _Graph>();
279          checkConcept<GraphItem<'e'>, Edge>();
280          {
281            Node n;
282            Edge ue(INVALID);
283            Arc e;
284            n = graph.u(ue);
285            n = graph.v(ue);
286            e = graph.direct(ue, true);
287            e = graph.direct(ue, false);
288            e = graph.direct(ue, n);
289            e = graph.oppositeArc(e);
290            ue = e;
291            bool d = graph.direction(e);
292            ignore_unused_variable_warning(d);
293          }
294        }
295
296        const _Graph& graph;
297      Constraints() {}
298      };
299
300    };
301
302    /// \brief Base skeleton class for undirected bipartite graphs.
303    ///
304    /// This class describes the base interface of undirected
305    /// bipartite graph types.  All bipartite graph %concepts have to
306    /// conform to this class.  It extends the interface of \ref
307    /// BaseGraphComponent with an \c Edge type and functions to get
308    /// the end nodes of edges, to convert from arcs to edges and to
309    /// get both direction of edges.
310    class BaseBpGraphComponent : public BaseGraphComponent {
311    public:
312
313      typedef BaseBpGraphComponent BpGraph;
314
315      typedef BaseDigraphComponent::Node Node;
316      typedef BaseDigraphComponent::Arc Arc;
317
318      /// \brief Class to represent red nodes.
319      ///
320      /// This class represents the red nodes of the graph. The red
321      /// nodes can be used also as normal nodes.
322      class RedNode : public Node {
323        typedef Node Parent;
324
325      public:
326        /// \brief Default constructor.
327        ///
328        /// Default constructor.
329        /// \warning The default constructor is not required to set
330        /// the item to some well-defined value. So you should consider it
331        /// as uninitialized.
332        RedNode() {}
333
334        /// \brief Copy constructor.
335        ///
336        /// Copy constructor.
337        RedNode(const RedNode &) : Parent() {}
338
339        /// \brief Constructor for conversion from \c INVALID.
340        ///
341        /// Constructor for conversion from \c INVALID.
342        /// It initializes the item to be invalid.
343        /// \sa Invalid for more details.
344        RedNode(Invalid) {}
345      };
346
347      /// \brief Class to represent blue nodes.
348      ///
349      /// This class represents the blue nodes of the graph. The blue
350      /// nodes can be used also as normal nodes.
351      class BlueNode : public Node {
352        typedef Node Parent;
353
354      public:
355        /// \brief Default constructor.
356        ///
357        /// Default constructor.
358        /// \warning The default constructor is not required to set
359        /// the item to some well-defined value. So you should consider it
360        /// as uninitialized.
361        BlueNode() {}
362
363        /// \brief Copy constructor.
364        ///
365        /// Copy constructor.
366        BlueNode(const BlueNode &) : Parent() {}
367
368        /// \brief Constructor for conversion from \c INVALID.
369        ///
370        /// Constructor for conversion from \c INVALID.
371        /// It initializes the item to be invalid.
372        /// \sa Invalid for more details.
373        BlueNode(Invalid) {}
374
375        /// \brief Constructor for conversion from a node.
376        ///
377        /// Constructor for conversion from a node. The conversion can
378        /// be invalid, since the Node can be member of the red
379        /// set.
380        BlueNode(const Node&) {}
381      };
382
383      /// \brief Gives back %true for red nodes.
384      ///
385      /// Gives back %true for red nodes.
386      bool red(const Node&) const { return true; }
387
388      /// \brief Gives back %true for blue nodes.
389      ///
390      /// Gives back %true for blue nodes.
391      bool blue(const Node&) const { return true; }
392
393      /// \brief Gives back the red end node of the edge.
394      ///
395      /// Gives back the red end node of the edge.
396      RedNode redNode(const Edge&) const { return RedNode(); }
397
398      /// \brief Gives back the blue end node of the edge.
399      ///
400      /// Gives back the blue end node of the edge.
401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
402
403      /// \brief Converts the node to red node object.
404      ///
405      /// This class is converts unsafely the node to red node
406      /// object. It should be called only if the node is from the red
407      /// partition or INVALID.
408      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
409
410      /// \brief Converts the node to blue node object.
411      ///
412      /// This class is converts unsafely the node to blue node
413      /// object. It should be called only if the node is from the red
414      /// partition or INVALID.
415      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
416
417      /// \brief Converts the node to red node object.
418      ///
419      /// This class is converts safely the node to red node
420      /// object. If the node is not from the red partition, then it
421      /// returns INVALID.
422      RedNode asRedNode(const Node&) const { return RedNode(); }
423
424      /// \brief Converts the node to blue node object.
425      ///
426      /// This class is converts unsafely the node to blue node
427      /// object. If the node is not from the blue partition, then it
428      /// returns INVALID.
429      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
430
431      /// \brief Convert the node to either red or blue node.
432      ///
433      /// If the node is from the red partition then it is returned in
434      /// first and second is INVALID. If the node is from the blue
435      /// partition then it is returned in second and first is
436      /// INVALID. If the node INVALID then both first and second are
437      /// INVALID in the return value.
438      std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
439        return std::make_pair(RedNode(), BlueNode());
440      }
441
442      template <typename _BpGraph>
443      struct Constraints {
444        typedef typename _BpGraph::Node Node;
445        typedef typename _BpGraph::RedNode RedNode;
446        typedef typename _BpGraph::BlueNode BlueNode;
447        typedef typename _BpGraph::Arc Arc;
448        typedef typename _BpGraph::Edge Edge;
449
450        void constraints() {
451          checkConcept<BaseGraphComponent, _BpGraph>();
452          checkConcept<GraphItem<'n'>, RedNode>();
453          checkConcept<GraphItem<'n'>, BlueNode>();
454          {
455            Node n;
456            RedNode rn;
457            BlueNode bn;
458            Node rnan = rn;
459            Node bnan = bn;
460            Edge e;
461            bool b;
462            b = bpgraph.red(rnan);
463            b = bpgraph.blue(bnan);
464            rn = bpgraph.redNode(e);
465            bn = bpgraph.blueNode(e);
466            rn = bpgraph.asRedNodeUnsafe(rnan);
467            bn = bpgraph.asBlueNodeUnsafe(bnan);
468            rn = bpgraph.asRedNode(rnan);
469            bn = bpgraph.asBlueNode(bnan);
470            std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
471            ignore_unused_variable_warning(b,p);
472          }
473        }
474
475        const _BpGraph& bpgraph;
476      };
477
478    };
479
480    /// \brief Skeleton class for \e idable directed graphs.
481    ///
482    /// This class describes the interface of \e idable directed graphs.
483    /// It extends \ref BaseDigraphComponent with the core ID functions.
484    /// The ids of the items must be unique and immutable.
485    /// This concept is part of the Digraph concept.
486    template <typename BAS = BaseDigraphComponent>
487    class IDableDigraphComponent : public BAS {
488    public:
489
490      typedef BAS Base;
491      typedef typename Base::Node Node;
492      typedef typename Base::Arc Arc;
493
494      /// \brief Return a unique integer id for the given node.
495      ///
496      /// This function returns a unique integer id for the given node.
497      int id(const Node&) const { return -1; }
498
499      /// \brief Return the node by its unique id.
500      ///
501      /// This function returns the node by its unique id.
502      /// If the digraph does not contain a node with the given id,
503      /// then the result of the function is undefined.
504      Node nodeFromId(int) const { return INVALID; }
505
506      /// \brief Return a unique integer id for the given arc.
507      ///
508      /// This function returns a unique integer id for the given arc.
509      int id(const Arc&) const { return -1; }
510
511      /// \brief Return the arc by its unique id.
512      ///
513      /// This function returns the arc by its unique id.
514      /// If the digraph does not contain an arc with the given id,
515      /// then the result of the function is undefined.
516      Arc arcFromId(int) const { return INVALID; }
517
518      /// \brief Return an integer greater or equal to the maximum
519      /// node id.
520      ///
521      /// This function returns an integer greater or equal to the
522      /// maximum node id.
523      int maxNodeId() const { return -1; }
524
525      /// \brief Return an integer greater or equal to the maximum
526      /// arc id.
527      ///
528      /// This function returns an integer greater or equal to the
529      /// maximum arc id.
530      int maxArcId() const { return -1; }
531
532      template <typename _Digraph>
533      struct Constraints {
534
535        void constraints() {
536          checkConcept<Base, _Digraph >();
537          typename _Digraph::Node node;
538          node=INVALID;
539          int nid = digraph.id(node);
540          nid = digraph.id(node);
541          node = digraph.nodeFromId(nid);
542          typename _Digraph::Arc arc;
543          arc=INVALID;
544          int eid = digraph.id(arc);
545          eid = digraph.id(arc);
546          arc = digraph.arcFromId(eid);
547
548          nid = digraph.maxNodeId();
549          ignore_unused_variable_warning(nid);
550          eid = digraph.maxArcId();
551          ignore_unused_variable_warning(eid);
552        }
553
554        const _Digraph& digraph;
555        Constraints() {}
556      };
557    };
558
559    /// \brief Skeleton class for \e idable undirected graphs.
560    ///
561    /// This class describes the interface of \e idable undirected
562    /// graphs. It extends \ref IDableDigraphComponent with the core ID
563    /// functions of undirected graphs.
564    /// The ids of the items must be unique and immutable.
565    /// This concept is part of the Graph concept.
566    template <typename BAS = BaseGraphComponent>
567    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
568    public:
569
570      typedef BAS Base;
571      typedef typename Base::Edge Edge;
572
573      using IDableDigraphComponent<Base>::id;
574
575      /// \brief Return a unique integer id for the given edge.
576      ///
577      /// This function returns a unique integer id for the given edge.
578      int id(const Edge&) const { return -1; }
579
580      /// \brief Return the edge by its unique id.
581      ///
582      /// This function returns the edge by its unique id.
583      /// If the graph does not contain an edge with the given id,
584      /// then the result of the function is undefined.
585      Edge edgeFromId(int) const { return INVALID; }
586
587      /// \brief Return an integer greater or equal to the maximum
588      /// edge id.
589      ///
590      /// This function returns an integer greater or equal to the
591      /// maximum edge id.
592      int maxEdgeId() const { return -1; }
593
594      template <typename _Graph>
595      struct Constraints {
596
597        void constraints() {
598          checkConcept<IDableDigraphComponent<Base>, _Graph >();
599          typename _Graph::Edge edge;
600          int ueid = graph.id(edge);
601          ueid = graph.id(edge);
602          edge = graph.edgeFromId(ueid);
603          ueid = graph.maxEdgeId();
604          ignore_unused_variable_warning(ueid);
605        }
606
607        const _Graph& graph;
608        Constraints() {}
609      };
610    };
611
612    /// \brief Skeleton class for \e idable undirected bipartite graphs.
613    ///
614    /// This class describes the interface of \e idable undirected
615    /// bipartite graphs. It extends \ref IDableGraphComponent with
616    /// the core ID functions of undirected bipartite graphs. Beside
617    /// the regular node ids, this class also provides ids within the
618    /// the red and blue sets of the nodes. This concept is part of
619    /// the BpGraph concept.
620    template <typename BAS = BaseBpGraphComponent>
621    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
622    public:
623
624      typedef BAS Base;
625      typedef IDableGraphComponent<BAS> Parent;
626      typedef typename Base::Node Node;
627      typedef typename Base::RedNode RedNode;
628      typedef typename Base::BlueNode BlueNode;
629
630      using Parent::id;
631
632      /// \brief Return a unique integer id for the given node in the red set.
633      ///
634      /// Return a unique integer id for the given node in the red set.
635      int id(const RedNode&) const { return -1; }
636
637      /// \brief Return a unique integer id for the given node in the blue set.
638      ///
639      /// Return a unique integer id for the given node in the blue set.
640      int id(const BlueNode&) const { return -1; }
641
642      /// \brief Return an integer greater or equal to the maximum
643      /// node id in the red set.
644      ///
645      /// Return an integer greater or equal to the maximum
646      /// node id in the red set.
647      int maxRedId() const { return -1; }
648
649      /// \brief Return an integer greater or equal to the maximum
650      /// node id in the blue set.
651      ///
652      /// Return an integer greater or equal to the maximum
653      /// node id in the blue set.
654      int maxBlueId() const { return -1; }
655
656      template <typename _BpGraph>
657      struct Constraints {
658
659        void constraints() {
660          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
661          typename _BpGraph::Node node;
662          typename _BpGraph::RedNode red;
663          typename _BpGraph::BlueNode blue;
664          int rid = bpgraph.id(red);
665          int bid = bpgraph.id(blue);
666          rid = bpgraph.maxRedId();
667          bid = bpgraph.maxBlueId();
668          ignore_unused_variable_warning(rid);
669          ignore_unused_variable_warning(bid);
670        }
671
672        const _BpGraph& bpgraph;
673      };
674    };
675
676    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
677    ///
678    /// This class describes the concept of \c NodeIt, \c ArcIt and
679    /// \c EdgeIt subtypes of digraph and graph types.
680    template <typename GR, typename Item>
681    class GraphItemIt : public Item {
682    public:
683      /// \brief Default constructor.
684      ///
685      /// Default constructor.
686      /// \warning The default constructor is not required to set
687      /// the iterator to some well-defined value. So you should consider it
688      /// as uninitialized.
689      GraphItemIt() {}
690
691      /// \brief Copy constructor.
692      ///
693      /// Copy constructor.
694      GraphItemIt(const GraphItemIt& it) : Item(it) {}
695
696      /// \brief Constructor that sets the iterator to the first item.
697      ///
698      /// Constructor that sets the iterator to the first item.
699      explicit GraphItemIt(const GR&) {}
700
701      /// \brief Constructor for conversion from \c INVALID.
702      ///
703      /// Constructor for conversion from \c INVALID.
704      /// It initializes the iterator to be invalid.
705      /// \sa Invalid for more details.
706      GraphItemIt(Invalid) {}
707
708      /// \brief Assignment operator.
709      ///
710      /// Assignment operator for the iterator.
711      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
712
713      /// \brief Increment the iterator.
714      ///
715      /// This operator increments the iterator, i.e. assigns it to the
716      /// next item.
717      GraphItemIt& operator++() { return *this; }
718
719      /// \brief Equality operator
720      ///
721      /// Equality operator.
722      /// Two iterators are equal if and only if they point to the
723      /// same object or both are invalid.
724      bool operator==(const GraphItemIt&) const { return true;}
725
726      /// \brief Inequality operator
727      ///
728      /// Inequality operator.
729      /// Two iterators are equal if and only if they point to the
730      /// same object or both are invalid.
731      bool operator!=(const GraphItemIt&) const { return true;}
732
733      template<typename _GraphItemIt>
734      struct Constraints {
735        void constraints() {
736          checkConcept<GraphItem<>, _GraphItemIt>();
737          _GraphItemIt it1(g);
738          _GraphItemIt it2;
739          _GraphItemIt it3 = it1;
740          _GraphItemIt it4 = INVALID;
741          ignore_unused_variable_warning(it3);
742          ignore_unused_variable_warning(it4);
743
744          it2 = ++it1;
745          ++it2 = it1;
746          ++(++it1);
747
748          Item bi = it1;
749          bi = it2;
750        }
751        const GR& g;
752        Constraints() {}
753      };
754    };
755
756    /// \brief Concept class for \c InArcIt, \c OutArcIt and
757    /// \c IncEdgeIt types.
758    ///
759    /// This class describes the concept of \c InArcIt, \c OutArcIt
760    /// and \c IncEdgeIt subtypes of digraph and graph types.
761    ///
762    /// \note Since these iterator classes do not inherit from the same
763    /// base class, there is an additional template parameter (selector)
764    /// \c sel. For \c InArcIt you should instantiate it with character
765    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
766    template <typename GR,
767              typename Item = typename GR::Arc,
768              typename Base = typename GR::Node,
769              char sel = '0'>
770    class GraphIncIt : public Item {
771    public:
772      /// \brief Default constructor.
773      ///
774      /// Default constructor.
775      /// \warning The default constructor is not required to set
776      /// the iterator to some well-defined value. So you should consider it
777      /// as uninitialized.
778      GraphIncIt() {}
779
780      /// \brief Copy constructor.
781      ///
782      /// Copy constructor.
783      GraphIncIt(const GraphIncIt& it) : Item(it) {}
784
785      /// \brief Constructor that sets the iterator to the first
786      /// incoming or outgoing arc.
787      ///
788      /// Constructor that sets the iterator to the first arc
789      /// incoming to or outgoing from the given node.
790      explicit GraphIncIt(const GR&, const Base&) {}
791
792      /// \brief Constructor for conversion from \c INVALID.
793      ///
794      /// Constructor for conversion from \c INVALID.
795      /// It initializes the iterator to be invalid.
796      /// \sa Invalid for more details.
797      GraphIncIt(Invalid) {}
798
799      /// \brief Assignment operator.
800      ///
801      /// Assignment operator for the iterator.
802      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
803
804      /// \brief Increment the iterator.
805      ///
806      /// This operator increments the iterator, i.e. assigns it to the
807      /// next arc incoming to or outgoing from the given node.
808      GraphIncIt& operator++() { return *this; }
809
810      /// \brief Equality operator
811      ///
812      /// Equality operator.
813      /// Two iterators are equal if and only if they point to the
814      /// same object or both are invalid.
815      bool operator==(const GraphIncIt&) const { return true;}
816
817      /// \brief Inequality operator
818      ///
819      /// Inequality operator.
820      /// Two iterators are equal if and only if they point to the
821      /// same object or both are invalid.
822      bool operator!=(const GraphIncIt&) const { return true;}
823
824      template <typename _GraphIncIt>
825      struct Constraints {
826        void constraints() {
827          checkConcept<GraphItem<sel>, _GraphIncIt>();
828          _GraphIncIt it1(graph, node);
829          _GraphIncIt it2;
830          _GraphIncIt it3 = it1;
831          _GraphIncIt it4 = INVALID;
832          ignore_unused_variable_warning(it3);
833          ignore_unused_variable_warning(it4);
834
835          it2 = ++it1;
836          ++it2 = it1;
837          ++(++it1);
838          Item e = it1;
839          e = it2;
840        }
841        const Base& node;
842        const GR& graph;
843        Constraints() {}
844      };
845    };
846
847    /// \brief Skeleton class for iterable directed graphs.
848    ///
849    /// This class describes the interface of iterable directed
850    /// graphs. It extends \ref BaseDigraphComponent with the core
851    /// iterable interface.
852    /// This concept is part of the Digraph concept.
853    template <typename BAS = BaseDigraphComponent>
854    class IterableDigraphComponent : public BAS {
855
856    public:
857
858      typedef BAS Base;
859      typedef typename Base::Node Node;
860      typedef typename Base::Arc Arc;
861
862      typedef IterableDigraphComponent Digraph;
863
864      /// \name Base Iteration
865      ///
866      /// This interface provides functions for iteration on digraph items.
867      ///
868      /// @{
869
870      /// \brief Return the first node.
871      ///
872      /// This function gives back the first node in the iteration order.
873      void first(Node&) const {}
874
875      /// \brief Return the next node.
876      ///
877      /// This function gives back the next node in the iteration order.
878      void next(Node&) const {}
879
880      /// \brief Return the first arc.
881      ///
882      /// This function gives back the first arc in the iteration order.
883      void first(Arc&) const {}
884
885      /// \brief Return the next arc.
886      ///
887      /// This function gives back the next arc in the iteration order.
888      void next(Arc&) const {}
889
890      /// \brief Return the first arc incomming to the given node.
891      ///
892      /// This function gives back the first arc incomming to the
893      /// given node.
894      void firstIn(Arc&, const Node&) const {}
895
896      /// \brief Return the next arc incomming to the given node.
897      ///
898      /// This function gives back the next arc incomming to the
899      /// given node.
900      void nextIn(Arc&) const {}
901
902      /// \brief Return the first arc outgoing form the given node.
903      ///
904      /// This function gives back the first arc outgoing form the
905      /// given node.
906      void firstOut(Arc&, const Node&) const {}
907
908      /// \brief Return the next arc outgoing form the given node.
909      ///
910      /// This function gives back the next arc outgoing form the
911      /// given node.
912      void nextOut(Arc&) const {}
913
914      /// @}
915
916      /// \name Class Based Iteration
917      ///
918      /// This interface provides iterator classes for digraph items.
919      ///
920      /// @{
921
922      /// \brief This iterator goes through each node.
923      ///
924      /// This iterator goes through each node.
925      ///
926      typedef GraphItemIt<Digraph, Node> NodeIt;
927
928      /// \brief This iterator goes through each arc.
929      ///
930      /// This iterator goes through each arc.
931      ///
932      typedef GraphItemIt<Digraph, Arc> ArcIt;
933
934      /// \brief This iterator goes trough the incoming arcs of a node.
935      ///
936      /// This iterator goes trough the \e incoming arcs of a certain node
937      /// of a digraph.
938      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
939
940      /// \brief This iterator goes trough the outgoing arcs of a node.
941      ///
942      /// This iterator goes trough the \e outgoing arcs of a certain node
943      /// of a digraph.
944      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
945
946      /// \brief The base node of the iterator.
947      ///
948      /// This function gives back the base node of the iterator.
949      /// It is always the target node of the pointed arc.
950      Node baseNode(const InArcIt&) const { return INVALID; }
951
952      /// \brief The running node of the iterator.
953      ///
954      /// This function gives back the running node of the iterator.
955      /// It is always the source node of the pointed arc.
956      Node runningNode(const InArcIt&) const { return INVALID; }
957
958      /// \brief The base node of the iterator.
959      ///
960      /// This function gives back the base node of the iterator.
961      /// It is always the source node of the pointed arc.
962      Node baseNode(const OutArcIt&) const { return INVALID; }
963
964      /// \brief The running node of the iterator.
965      ///
966      /// This function gives back the running node of the iterator.
967      /// It is always the target node of the pointed arc.
968      Node runningNode(const OutArcIt&) const { return INVALID; }
969
970      /// @}
971
972      template <typename _Digraph>
973      struct Constraints {
974        void constraints() {
975          checkConcept<Base, _Digraph>();
976
977          {
978            typename _Digraph::Node node(INVALID);
979            typename _Digraph::Arc arc(INVALID);
980            {
981              digraph.first(node);
982              digraph.next(node);
983            }
984            {
985              digraph.first(arc);
986              digraph.next(arc);
987            }
988            {
989              digraph.firstIn(arc, node);
990              digraph.nextIn(arc);
991            }
992            {
993              digraph.firstOut(arc, node);
994              digraph.nextOut(arc);
995            }
996          }
997
998          {
999            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
1000              typename _Digraph::ArcIt >();
1001            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
1002              typename _Digraph::NodeIt >();
1003            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1004              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
1005            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1006              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
1007
1008            typename _Digraph::Node n;
1009            const typename _Digraph::InArcIt iait(INVALID);
1010            const typename _Digraph::OutArcIt oait(INVALID);
1011            n = digraph.baseNode(iait);
1012            n = digraph.runningNode(iait);
1013            n = digraph.baseNode(oait);
1014            n = digraph.runningNode(oait);
1015            ignore_unused_variable_warning(n);
1016          }
1017        }
1018
1019        const _Digraph& digraph;
1020        Constraints() {}
1021      };
1022    };
1023
1024    /// \brief Skeleton class for iterable undirected graphs.
1025    ///
1026    /// This class describes the interface of iterable undirected
1027    /// graphs. It extends \ref IterableDigraphComponent with the core
1028    /// iterable interface of undirected graphs.
1029    /// This concept is part of the Graph concept.
1030    template <typename BAS = BaseGraphComponent>
1031    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
1032    public:
1033
1034      typedef BAS Base;
1035      typedef typename Base::Node Node;
1036      typedef typename Base::Arc Arc;
1037      typedef typename Base::Edge Edge;
1038
1039
1040      typedef IterableGraphComponent Graph;
1041
1042      /// \name Base Iteration
1043      ///
1044      /// This interface provides functions for iteration on edges.
1045      ///
1046      /// @{
1047
1048      using IterableDigraphComponent<Base>::first;
1049      using IterableDigraphComponent<Base>::next;
1050
1051      /// \brief Return the first edge.
1052      ///
1053      /// This function gives back the first edge in the iteration order.
1054      void first(Edge&) const {}
1055
1056      /// \brief Return the next edge.
1057      ///
1058      /// This function gives back the next edge in the iteration order.
1059      void next(Edge&) const {}
1060
1061      /// \brief Return the first edge incident to the given node.
1062      ///
1063      /// This function gives back the first edge incident to the given
1064      /// node. The bool parameter gives back the direction for which the
1065      /// source node of the directed arc representing the edge is the
1066      /// given node.
1067      void firstInc(Edge&, bool&, const Node&) const {}
1068
1069      /// \brief Gives back the next of the edges from the
1070      /// given node.
1071      ///
1072      /// This function gives back the next edge incident to the given
1073      /// node. The bool parameter should be used as \c firstInc() use it.
1074      void nextInc(Edge&, bool&) const {}
1075
1076      using IterableDigraphComponent<Base>::baseNode;
1077      using IterableDigraphComponent<Base>::runningNode;
1078
1079      /// @}
1080
1081      /// \name Class Based Iteration
1082      ///
1083      /// This interface provides iterator classes for edges.
1084      ///
1085      /// @{
1086
1087      /// \brief This iterator goes through each edge.
1088      ///
1089      /// This iterator goes through each edge.
1090      typedef GraphItemIt<Graph, Edge> EdgeIt;
1091
1092      /// \brief This iterator goes trough the incident edges of a
1093      /// node.
1094      ///
1095      /// This iterator goes trough the incident edges of a certain
1096      /// node of a graph.
1097      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
1098
1099      /// \brief The base node of the iterator.
1100      ///
1101      /// This function gives back the base node of the iterator.
1102      Node baseNode(const IncEdgeIt&) const { return INVALID; }
1103
1104      /// \brief The running node of the iterator.
1105      ///
1106      /// This function gives back the running node of the iterator.
1107      Node runningNode(const IncEdgeIt&) const { return INVALID; }
1108
1109      /// @}
1110
1111      template <typename _Graph>
1112      struct Constraints {
1113        void constraints() {
1114          checkConcept<IterableDigraphComponent<Base>, _Graph>();
1115
1116          {
1117            typename _Graph::Node node(INVALID);
1118            typename _Graph::Edge edge(INVALID);
1119            bool dir;
1120            {
1121              graph.first(edge);
1122              graph.next(edge);
1123            }
1124            {
1125              graph.firstInc(edge, dir, node);
1126              graph.nextInc(edge, dir);
1127            }
1128
1129          }
1130
1131          {
1132            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1133              typename _Graph::EdgeIt >();
1134            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1135              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
1136
1137            typename _Graph::Node n;
1138            const typename _Graph::IncEdgeIt ieit(INVALID);
1139            n = graph.baseNode(ieit);
1140            n = graph.runningNode(ieit);
1141          }
1142        }
1143
1144        const _Graph& graph;
1145        Constraints() {}
1146      };
1147    };
1148
1149    /// \brief Skeleton class for iterable undirected bipartite graphs.
1150    ///
1151    /// This class describes the interface of iterable undirected
1152    /// bipartite graphs. It extends \ref IterableGraphComponent with
1153    /// the core iterable interface of undirected bipartite graphs.
1154    /// This concept is part of the BpGraph concept.
1155    template <typename BAS = BaseBpGraphComponent>
1156    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
1157    public:
1158
1159      typedef BAS Base;
1160      typedef typename Base::Node Node;
1161      typedef typename Base::RedNode RedNode;
1162      typedef typename Base::BlueNode BlueNode;
1163      typedef typename Base::Arc Arc;
1164      typedef typename Base::Edge Edge;
1165     
1166      typedef IterableBpGraphComponent BpGraph;
1167
1168      using IterableGraphComponent<BAS>::first;
1169      using IterableGraphComponent<BAS>::next;
1170
1171      /// \name Base Iteration
1172      ///
1173      /// This interface provides functions for iteration on red and blue nodes.
1174      ///
1175      /// @{
1176
1177      /// \brief Return the first red node.
1178      ///
1179      /// This function gives back the first red node in the iteration order.
1180      void first(RedNode&) const {}
1181
1182      /// \brief Return the next red node.
1183      ///
1184      /// This function gives back the next red node in the iteration order.
1185      void next(RedNode&) const {}
1186
1187      /// \brief Return the first blue node.
1188      ///
1189      /// This function gives back the first blue node in the iteration order.
1190      void first(BlueNode&) const {}
1191
1192      /// \brief Return the next blue node.
1193      ///
1194      /// This function gives back the next blue node in the iteration order.
1195      void next(BlueNode&) const {}
1196
1197
1198      /// @}
1199
1200      /// \name Class Based Iteration
1201      ///
1202      /// This interface provides iterator classes for red and blue nodes.
1203      ///
1204      /// @{
1205
1206      /// \brief This iterator goes through each red node.
1207      ///
1208      /// This iterator goes through each red node.
1209      typedef GraphItemIt<BpGraph, RedNode> RedIt;
1210
1211      /// \brief This iterator goes through each blue node.
1212      ///
1213      /// This iterator goes through each blue node.
1214      typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
1215
1216      /// @}
1217
1218      template <typename _BpGraph>
1219      struct Constraints {
1220        void constraints() {
1221          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1222
1223          typename _BpGraph::RedNode rn(INVALID);
1224          bpgraph.first(rn);
1225          bpgraph.next(rn);
1226          typename _BpGraph::BlueNode bn(INVALID);
1227          bpgraph.first(bn);
1228          bpgraph.next(bn);
1229
1230          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
1231            typename _BpGraph::RedIt>();
1232          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
1233            typename _BpGraph::BlueIt>();
1234        }
1235
1236        const _BpGraph& bpgraph;
1237      };
1238    };
1239
1240    /// \brief Skeleton class for alterable directed graphs.
1241    ///
1242    /// This class describes the interface of alterable directed
1243    /// graphs. It extends \ref BaseDigraphComponent with the alteration
1244    /// notifier interface. It implements
1245    /// an observer-notifier pattern for each digraph item. More
1246    /// obsevers can be registered into the notifier and whenever an
1247    /// alteration occured in the digraph all the observers will be
1248    /// notified about it.
1249    template <typename BAS = BaseDigraphComponent>
1250    class AlterableDigraphComponent : public BAS {
1251    public:
1252
1253      typedef BAS Base;
1254      typedef typename Base::Node Node;
1255      typedef typename Base::Arc Arc;
1256
1257
1258      /// Node alteration notifier class.
1259      typedef AlterationNotifier<AlterableDigraphComponent, Node>
1260      NodeNotifier;
1261      /// Arc alteration notifier class.
1262      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
1263      ArcNotifier;
1264
1265      mutable NodeNotifier node_notifier;
1266      mutable ArcNotifier arc_notifier;
1267
1268      /// \brief Return the node alteration notifier.
1269      ///
1270      /// This function gives back the node alteration notifier.
1271      NodeNotifier& notifier(Node) const {
1272        return node_notifier;
1273      }
1274
1275      /// \brief Return the arc alteration notifier.
1276      ///
1277      /// This function gives back the arc alteration notifier.
1278      ArcNotifier& notifier(Arc) const {
1279        return arc_notifier;
1280      }
1281
1282      template <typename _Digraph>
1283      struct Constraints {
1284        void constraints() {
1285          checkConcept<Base, _Digraph>();
1286          typename _Digraph::NodeNotifier& nn
1287            = digraph.notifier(typename _Digraph::Node());
1288
1289          typename _Digraph::ArcNotifier& en
1290            = digraph.notifier(typename _Digraph::Arc());
1291
1292          ignore_unused_variable_warning(nn);
1293          ignore_unused_variable_warning(en);
1294        }
1295
1296        const _Digraph& digraph;
1297        Constraints() {}
1298      };
1299    };
1300
1301    /// \brief Skeleton class for alterable undirected graphs.
1302    ///
1303    /// This class describes the interface of alterable undirected
1304    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
1305    /// notifier interface of undirected graphs. It implements
1306    /// an observer-notifier pattern for the edges. More
1307    /// obsevers can be registered into the notifier and whenever an
1308    /// alteration occured in the graph all the observers will be
1309    /// notified about it.
1310    template <typename BAS = BaseGraphComponent>
1311    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
1312    public:
1313
1314      typedef BAS Base;
1315      typedef AlterableDigraphComponent<Base> Parent;
1316      typedef typename Base::Edge Edge;
1317
1318
1319      /// Edge alteration notifier class.
1320      typedef AlterationNotifier<AlterableGraphComponent, Edge>
1321      EdgeNotifier;
1322
1323      mutable EdgeNotifier edge_notifier;
1324
1325      using Parent::notifier;
1326
1327      /// \brief Return the edge alteration notifier.
1328      ///
1329      /// This function gives back the edge alteration notifier.
1330      EdgeNotifier& notifier(Edge) const {
1331        return edge_notifier;
1332      }
1333
1334      template <typename _Graph>
1335      struct Constraints {
1336        void constraints() {
1337          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
1338          typename _Graph::EdgeNotifier& uen
1339            = graph.notifier(typename _Graph::Edge());
1340          ignore_unused_variable_warning(uen);
1341        }
1342
1343        const _Graph& graph;
1344        Constraints() {}
1345      };
1346    };
1347
1348    /// \brief Skeleton class for alterable undirected bipartite graphs.
1349    ///
1350    /// This class describes the interface of alterable undirected
1351    /// bipartite graphs. It extends \ref AlterableGraphComponent with
1352    /// the alteration notifier interface of bipartite graphs. It
1353    /// implements an observer-notifier pattern for the red and blue
1354    /// nodes. More obsevers can be registered into the notifier and
1355    /// whenever an alteration occured in the graph all the observers
1356    /// will be notified about it.
1357    template <typename BAS = BaseBpGraphComponent>
1358    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
1359    public:
1360
1361      typedef BAS Base;
1362      typedef AlterableGraphComponent<Base> Parent;
1363      typedef typename Base::RedNode RedNode;
1364      typedef typename Base::BlueNode BlueNode;
1365
1366
1367      /// Red node alteration notifier class.
1368      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
1369      RedNodeNotifier;
1370
1371      /// Blue node alteration notifier class.
1372      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
1373      BlueNodeNotifier;
1374
1375      mutable RedNodeNotifier red_node_notifier;
1376      mutable BlueNodeNotifier blue_node_notifier;
1377
1378      using Parent::notifier;
1379
1380      /// \brief Return the red node alteration notifier.
1381      ///
1382      /// This function gives back the red node alteration notifier.
1383      RedNodeNotifier& notifier(RedNode) const {
1384        return red_node_notifier;
1385      }
1386
1387      /// \brief Return the blue node alteration notifier.
1388      ///
1389      /// This function gives back the blue node alteration notifier.
1390      BlueNodeNotifier& notifier(BlueNode) const {
1391        return blue_node_notifier;
1392      }
1393
1394      template <typename _BpGraph>
1395      struct Constraints {
1396        void constraints() {
1397          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
1398          typename _BpGraph::RedNodeNotifier& rnn
1399            = bpgraph.notifier(typename _BpGraph::RedNode());
1400          typename _BpGraph::BlueNodeNotifier& bnn
1401            = bpgraph.notifier(typename _BpGraph::BlueNode());
1402          ignore_unused_variable_warning(rnn);
1403          ignore_unused_variable_warning(bnn);
1404        }
1405
1406        const _BpGraph& bpgraph;
1407      };
1408    };
1409
1410    /// \brief Concept class for standard graph maps.
1411    ///
1412    /// This class describes the concept of standard graph maps, i.e.
1413    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
1414    /// graph types, which can be used for associating data to graph items.
1415    /// The standard graph maps must conform to the ReferenceMap concept.
1416    template <typename GR, typename K, typename V>
1417    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
1418      typedef ReferenceMap<K, V, V&, const V&> Parent;
1419
1420    public:
1421
1422      /// The key type of the map.
1423      typedef K Key;
1424      /// The value type of the map.
1425      typedef V Value;
1426      /// The reference type of the map.
1427      typedef Value& Reference;
1428      /// The const reference type of the map.
1429      typedef const Value& ConstReference;
1430
1431      // The reference map tag.
1432      typedef True ReferenceMapTag;
1433
1434      /// \brief Construct a new map.
1435      ///
1436      /// Construct a new map for the graph.
1437      explicit GraphMap(const GR&) {}
1438      /// \brief Construct a new map with default value.
1439      ///
1440      /// Construct a new map for the graph and initalize the values.
1441      GraphMap(const GR&, const Value&) {}
1442
1443    private:
1444      /// \brief Copy constructor.
1445      ///
1446      /// Copy Constructor.
1447      GraphMap(const GraphMap&) : Parent() {}
1448
1449      /// \brief Assignment operator.
1450      ///
1451      /// Assignment operator. It does not mofify the underlying graph,
1452      /// it just iterates on the current item set and set the  map
1453      /// with the value returned by the assigned map.
1454      template <typename CMap>
1455      GraphMap& operator=(const CMap&) {
1456        checkConcept<ReadMap<Key, Value>, CMap>();
1457        return *this;
1458      }
1459
1460    public:
1461      template<typename _Map>
1462      struct Constraints {
1463        void constraints() {
1464          checkConcept
1465            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
1466          _Map m1(g);
1467          _Map m2(g,t);
1468
1469          // Copy constructor
1470          // _Map m3(m);
1471
1472          // Assignment operator
1473          // ReadMap<Key, Value> cmap;
1474          // m3 = cmap;
1475
1476          ignore_unused_variable_warning(m1);
1477          ignore_unused_variable_warning(m2);
1478          // ignore_unused_variable_warning(m3);
1479        }
1480
1481        const _Map &m;
1482        const GR &g;
1483        const typename GraphMap::Value &t;
1484        Constraints() {}
1485      };
1486
1487    };
1488
1489    /// \brief Skeleton class for mappable directed graphs.
1490    ///
1491    /// This class describes the interface of mappable directed graphs.
1492    /// It extends \ref BaseDigraphComponent with the standard digraph
1493    /// map classes, namely \c NodeMap and \c ArcMap.
1494    /// This concept is part of the Digraph concept.
1495    template <typename BAS = BaseDigraphComponent>
1496    class MappableDigraphComponent : public BAS  {
1497    public:
1498
1499      typedef BAS Base;
1500      typedef typename Base::Node Node;
1501      typedef typename Base::Arc Arc;
1502
1503      typedef MappableDigraphComponent Digraph;
1504
1505      /// \brief Standard graph map for the nodes.
1506      ///
1507      /// Standard graph map for the nodes.
1508      /// It conforms to the ReferenceMap concept.
1509      template <typename V>
1510      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
1511        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1512
1513      public:
1514        /// \brief Construct a new map.
1515        ///
1516        /// Construct a new map for the digraph.
1517        explicit NodeMap(const MappableDigraphComponent& digraph)
1518          : Parent(digraph) {}
1519
1520        /// \brief Construct a new map with default value.
1521        ///
1522        /// Construct a new map for the digraph and initalize the values.
1523        NodeMap(const MappableDigraphComponent& digraph, const V& value)
1524          : Parent(digraph, value) {}
1525
1526      private:
1527        /// \brief Copy constructor.
1528        ///
1529        /// Copy Constructor.
1530        NodeMap(const NodeMap& nm) : Parent(nm) {}
1531
1532        /// \brief Assignment operator.
1533        ///
1534        /// Assignment operator.
1535        template <typename CMap>
1536        NodeMap& operator=(const CMap&) {
1537          checkConcept<ReadMap<Node, V>, CMap>();
1538          return *this;
1539        }
1540
1541      };
1542
1543      /// \brief Standard graph map for the arcs.
1544      ///
1545      /// Standard graph map for the arcs.
1546      /// It conforms to the ReferenceMap concept.
1547      template <typename V>
1548      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
1549        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1550
1551      public:
1552        /// \brief Construct a new map.
1553        ///
1554        /// Construct a new map for the digraph.
1555        explicit ArcMap(const MappableDigraphComponent& digraph)
1556          : Parent(digraph) {}
1557
1558        /// \brief Construct a new map with default value.
1559        ///
1560        /// Construct a new map for the digraph and initalize the values.
1561        ArcMap(const MappableDigraphComponent& digraph, const V& value)
1562          : Parent(digraph, value) {}
1563
1564      private:
1565        /// \brief Copy constructor.
1566        ///
1567        /// Copy Constructor.
1568        ArcMap(const ArcMap& nm) : Parent(nm) {}
1569
1570        /// \brief Assignment operator.
1571        ///
1572        /// Assignment operator.
1573        template <typename CMap>
1574        ArcMap& operator=(const CMap&) {
1575          checkConcept<ReadMap<Arc, V>, CMap>();
1576          return *this;
1577        }
1578
1579      };
1580
1581
1582      template <typename _Digraph>
1583      struct Constraints {
1584
1585        struct Dummy {
1586          int value;
1587          Dummy() : value(0) {}
1588          Dummy(int _v) : value(_v) {}
1589        };
1590
1591        void constraints() {
1592          checkConcept<Base, _Digraph>();
1593          { // int map test
1594            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1595            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1596              IntNodeMap >();
1597          } { // bool map test
1598            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1599            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1600              BoolNodeMap >();
1601          } { // Dummy map test
1602            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1603            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1604              DummyNodeMap >();
1605          }
1606
1607          { // int map test
1608            typedef typename _Digraph::template ArcMap<int> IntArcMap;
1609            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1610              IntArcMap >();
1611          } { // bool map test
1612            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1613            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1614              BoolArcMap >();
1615          } { // Dummy map test
1616            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1617            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1618              DummyArcMap >();
1619          }
1620        }
1621
1622        const _Digraph& digraph;
1623        Constraints() {}
1624      };
1625    };
1626
1627    /// \brief Skeleton class for mappable undirected graphs.
1628    ///
1629    /// This class describes the interface of mappable undirected graphs.
1630    /// It extends \ref MappableDigraphComponent with the standard graph
1631    /// map class for edges (\c EdgeMap).
1632    /// This concept is part of the Graph concept.
1633    template <typename BAS = BaseGraphComponent>
1634    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
1635    public:
1636
1637      typedef BAS Base;
1638      typedef typename Base::Edge Edge;
1639
1640      typedef MappableGraphComponent Graph;
1641
1642      /// \brief Standard graph map for the edges.
1643      ///
1644      /// Standard graph map for the edges.
1645      /// It conforms to the ReferenceMap concept.
1646      template <typename V>
1647      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
1648        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1649
1650      public:
1651        /// \brief Construct a new map.
1652        ///
1653        /// Construct a new map for the graph.
1654        explicit EdgeMap(const MappableGraphComponent& graph)
1655          : Parent(graph) {}
1656
1657        /// \brief Construct a new map with default value.
1658        ///
1659        /// Construct a new map for the graph and initalize the values.
1660        EdgeMap(const MappableGraphComponent& graph, const V& value)
1661          : Parent(graph, value) {}
1662
1663      private:
1664        /// \brief Copy constructor.
1665        ///
1666        /// Copy Constructor.
1667        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1668
1669        /// \brief Assignment operator.
1670        ///
1671        /// Assignment operator.
1672        template <typename CMap>
1673        EdgeMap& operator=(const CMap&) {
1674          checkConcept<ReadMap<Edge, V>, CMap>();
1675          return *this;
1676        }
1677
1678      };
1679
1680
1681      template <typename _Graph>
1682      struct Constraints {
1683
1684        struct Dummy {
1685          int value;
1686          Dummy() : value(0) {}
1687          Dummy(int _v) : value(_v) {}
1688        };
1689
1690        void constraints() {
1691          checkConcept<MappableDigraphComponent<Base>, _Graph>();
1692
1693          { // int map test
1694            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1695            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1696              IntEdgeMap >();
1697          } { // bool map test
1698            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1699            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1700              BoolEdgeMap >();
1701          } { // Dummy map test
1702            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1703            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1704              DummyEdgeMap >();
1705          }
1706        }
1707
1708        const _Graph& graph;
1709        Constraints() {}
1710      };
1711    };
1712
1713    /// \brief Skeleton class for mappable undirected bipartite graphs.
1714    ///
1715    /// This class describes the interface of mappable undirected
1716    /// bipartite graphs.  It extends \ref MappableGraphComponent with
1717    /// the standard graph map class for red and blue nodes (\c
1718    /// RedMap and BlueMap). This concept is part of the BpGraph concept.
1719    template <typename BAS = BaseBpGraphComponent>
1720    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
1721    public:
1722
1723      typedef BAS Base;
1724      typedef typename Base::Node Node;
1725
1726      typedef MappableBpGraphComponent BpGraph;
1727
1728      /// \brief Standard graph map for the red nodes.
1729      ///
1730      /// Standard graph map for the red nodes.
1731      /// It conforms to the ReferenceMap concept.
1732      template <typename V>
1733      class RedMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1734        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1735
1736      public:
1737        /// \brief Construct a new map.
1738        ///
1739        /// Construct a new map for the graph.
1740        explicit RedMap(const MappableBpGraphComponent& graph)
1741          : Parent(graph) {}
1742
1743        /// \brief Construct a new map with default value.
1744        ///
1745        /// Construct a new map for the graph and initalize the values.
1746        RedMap(const MappableBpGraphComponent& graph, const V& value)
1747          : Parent(graph, value) {}
1748
1749      private:
1750        /// \brief Copy constructor.
1751        ///
1752        /// Copy Constructor.
1753        RedMap(const RedMap& nm) : Parent(nm) {}
1754
1755        /// \brief Assignment operator.
1756        ///
1757        /// Assignment operator.
1758        template <typename CMap>
1759        RedMap& operator=(const CMap&) {
1760          checkConcept<ReadMap<Node, V>, CMap>();
1761          return *this;
1762        }
1763
1764      };
1765
1766      /// \brief Standard graph map for the blue nodes.
1767      ///
1768      /// Standard graph map for the blue nodes.
1769      /// It conforms to the ReferenceMap concept.
1770      template <typename V>
1771      class BlueMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1772        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1773
1774      public:
1775        /// \brief Construct a new map.
1776        ///
1777        /// Construct a new map for the graph.
1778        explicit BlueMap(const MappableBpGraphComponent& graph)
1779          : Parent(graph) {}
1780
1781        /// \brief Construct a new map with default value.
1782        ///
1783        /// Construct a new map for the graph and initalize the values.
1784        BlueMap(const MappableBpGraphComponent& graph, const V& value)
1785          : Parent(graph, value) {}
1786
1787      private:
1788        /// \brief Copy constructor.
1789        ///
1790        /// Copy Constructor.
1791        BlueMap(const BlueMap& nm) : Parent(nm) {}
1792
1793        /// \brief Assignment operator.
1794        ///
1795        /// Assignment operator.
1796        template <typename CMap>
1797        BlueMap& operator=(const CMap&) {
1798          checkConcept<ReadMap<Node, V>, CMap>();
1799          return *this;
1800        }
1801
1802      };
1803
1804
1805      template <typename _BpGraph>
1806      struct Constraints {
1807
1808        struct Dummy {
1809          int value;
1810          Dummy() : value(0) {}
1811          Dummy(int _v) : value(_v) {}
1812        };
1813
1814        void constraints() {
1815          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
1816
1817          { // int map test
1818            typedef typename _BpGraph::template RedMap<int> IntRedMap;
1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
1820              IntRedMap >();
1821          } { // bool map test
1822            typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
1823            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
1824              BoolRedMap >();
1825          } { // Dummy map test
1826            typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
1827            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
1828              DummyRedMap >();
1829          }
1830
1831          { // int map test
1832            typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
1833            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
1834              IntBlueMap >();
1835          } { // bool map test
1836            typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
1837            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
1838              BoolBlueMap >();
1839          } { // Dummy map test
1840            typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
1841            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
1842              DummyBlueMap >();
1843          }
1844        }
1845
1846        const _BpGraph& bpgraph;
1847      };
1848    };
1849
1850    /// \brief Skeleton class for extendable directed graphs.
1851    ///
1852    /// This class describes the interface of extendable directed graphs.
1853    /// It extends \ref BaseDigraphComponent with functions for adding
1854    /// nodes and arcs to the digraph.
1855    /// This concept requires \ref AlterableDigraphComponent.
1856    template <typename BAS = BaseDigraphComponent>
1857    class ExtendableDigraphComponent : public BAS {
1858    public:
1859      typedef BAS Base;
1860
1861      typedef typename Base::Node Node;
1862      typedef typename Base::Arc Arc;
1863
1864      /// \brief Add a new node to the digraph.
1865      ///
1866      /// This function adds a new node to the digraph.
1867      Node addNode() {
1868        return INVALID;
1869      }
1870
1871      /// \brief Add a new arc connecting the given two nodes.
1872      ///
1873      /// This function adds a new arc connecting the given two nodes
1874      /// of the digraph.
1875      Arc addArc(const Node&, const Node&) {
1876        return INVALID;
1877      }
1878
1879      template <typename _Digraph>
1880      struct Constraints {
1881        void constraints() {
1882          checkConcept<Base, _Digraph>();
1883          typename _Digraph::Node node_a, node_b;
1884          node_a = digraph.addNode();
1885          node_b = digraph.addNode();
1886          typename _Digraph::Arc arc;
1887          arc = digraph.addArc(node_a, node_b);
1888        }
1889
1890        _Digraph& digraph;
1891        Constraints() {}
1892      };
1893    };
1894
1895    /// \brief Skeleton class for extendable undirected graphs.
1896    ///
1897    /// This class describes the interface of extendable undirected graphs.
1898    /// It extends \ref BaseGraphComponent with functions for adding
1899    /// nodes and edges to the graph.
1900    /// This concept requires \ref AlterableGraphComponent.
1901    template <typename BAS = BaseGraphComponent>
1902    class ExtendableGraphComponent : public BAS {
1903    public:
1904
1905      typedef BAS Base;
1906      typedef typename Base::Node Node;
1907      typedef typename Base::Edge Edge;
1908
1909      /// \brief Add a new node to the digraph.
1910      ///
1911      /// This function adds a new node to the digraph.
1912      Node addNode() {
1913        return INVALID;
1914      }
1915
1916      /// \brief Add a new edge connecting the given two nodes.
1917      ///
1918      /// This function adds a new edge connecting the given two nodes
1919      /// of the graph.
1920      Edge addEdge(const Node&, const Node&) {
1921        return INVALID;
1922      }
1923
1924      template <typename _Graph>
1925      struct Constraints {
1926        void constraints() {
1927          checkConcept<Base, _Graph>();
1928          typename _Graph::Node node_a, node_b;
1929          node_a = graph.addNode();
1930          node_b = graph.addNode();
1931          typename _Graph::Edge edge;
1932          edge = graph.addEdge(node_a, node_b);
1933        }
1934
1935        _Graph& graph;
1936        Constraints() {}
1937      };
1938    };
1939
1940    /// \brief Skeleton class for extendable undirected bipartite graphs.
1941    ///
1942    /// This class describes the interface of extendable undirected
1943    /// bipartite graphs. It extends \ref BaseGraphComponent with
1944    /// functions for adding nodes and edges to the graph. This
1945    /// concept requires \ref AlterableBpGraphComponent.
1946    template <typename BAS = BaseBpGraphComponent>
1947    class ExtendableBpGraphComponent : public BAS {
1948    public:
1949
1950      typedef BAS Base;
1951      typedef typename Base::Node Node;
1952      typedef typename Base::RedNode RedNode;
1953      typedef typename Base::BlueNode BlueNode;
1954      typedef typename Base::Edge Edge;
1955
1956      /// \brief Add a new red node to the digraph.
1957      ///
1958      /// This function adds a red new node to the digraph.
1959      RedNode addRedNode() {
1960        return INVALID;
1961      }
1962
1963      /// \brief Add a new blue node to the digraph.
1964      ///
1965      /// This function adds a blue new node to the digraph.
1966      BlueNode addBlueNode() {
1967        return INVALID;
1968      }
1969
1970      /// \brief Add a new edge connecting the given two nodes.
1971      ///
1972      /// This function adds a new edge connecting the given two nodes
1973      /// of the graph. The first node has to be a red node, and the
1974      /// second one a blue node.
1975      Edge addEdge(const RedNode&, const BlueNode&) {
1976        return INVALID;
1977      }
1978      Edge addEdge(const BlueNode&, const RedNode&) {
1979        return INVALID;
1980      }
1981
1982      template <typename _BpGraph>
1983      struct Constraints {
1984        void constraints() {
1985          checkConcept<Base, _BpGraph>();
1986          typename _BpGraph::RedNode red_node;
1987          typename _BpGraph::BlueNode blue_node;
1988          red_node = bpgraph.addRedNode();
1989          blue_node = bpgraph.addBlueNode();
1990          typename _BpGraph::Edge edge;
1991          edge = bpgraph.addEdge(red_node, blue_node);
1992          edge = bpgraph.addEdge(blue_node, red_node);
1993        }
1994
1995        _BpGraph& bpgraph;
1996      };
1997    };
1998
1999    /// \brief Skeleton class for erasable directed graphs.
2000    ///
2001    /// This class describes the interface of erasable directed graphs.
2002    /// It extends \ref BaseDigraphComponent with functions for removing
2003    /// nodes and arcs from the digraph.
2004    /// This concept requires \ref AlterableDigraphComponent.
2005    template <typename BAS = BaseDigraphComponent>
2006    class ErasableDigraphComponent : public BAS {
2007    public:
2008
2009      typedef BAS Base;
2010      typedef typename Base::Node Node;
2011      typedef typename Base::Arc Arc;
2012
2013      /// \brief Erase a node from the digraph.
2014      ///
2015      /// This function erases the given node from the digraph and all arcs
2016      /// connected to the node.
2017      void erase(const Node&) {}
2018
2019      /// \brief Erase an arc from the digraph.
2020      ///
2021      /// This function erases the given arc from the digraph.
2022      void erase(const Arc&) {}
2023
2024      template <typename _Digraph>
2025      struct Constraints {
2026        void constraints() {
2027          checkConcept<Base, _Digraph>();
2028          const typename _Digraph::Node node(INVALID);
2029          digraph.erase(node);
2030          const typename _Digraph::Arc arc(INVALID);
2031          digraph.erase(arc);
2032        }
2033
2034        _Digraph& digraph;
2035        Constraints() {}
2036      };
2037    };
2038
2039    /// \brief Skeleton class for erasable undirected graphs.
2040    ///
2041    /// This class describes the interface of erasable undirected graphs.
2042    /// It extends \ref BaseGraphComponent with functions for removing
2043    /// nodes and edges from the graph.
2044    /// This concept requires \ref AlterableGraphComponent.
2045    template <typename BAS = BaseGraphComponent>
2046    class ErasableGraphComponent : public BAS {
2047    public:
2048
2049      typedef BAS Base;
2050      typedef typename Base::Node Node;
2051      typedef typename Base::Edge Edge;
2052
2053      /// \brief Erase a node from the graph.
2054      ///
2055      /// This function erases the given node from the graph and all edges
2056      /// connected to the node.
2057      void erase(const Node&) {}
2058
2059      /// \brief Erase an edge from the digraph.
2060      ///
2061      /// This function erases the given edge from the digraph.
2062      void erase(const Edge&) {}
2063
2064      template <typename _Graph>
2065      struct Constraints {
2066        void constraints() {
2067          checkConcept<Base, _Graph>();
2068          const typename _Graph::Node node(INVALID);
2069          graph.erase(node);
2070          const typename _Graph::Edge edge(INVALID);
2071          graph.erase(edge);
2072        }
2073
2074        _Graph& graph;
2075        Constraints() {}
2076      };
2077    };
2078
2079    /// \brief Skeleton class for erasable undirected graphs.
2080    ///
2081    /// This class describes the interface of erasable undirected
2082    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
2083    /// functions for removing nodes and edges from the graph. This
2084    /// concept requires \ref AlterableBpGraphComponent.
2085    template <typename BAS = BaseBpGraphComponent>
2086    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
2087
2088    /// \brief Skeleton class for clearable directed graphs.
2089    ///
2090    /// This class describes the interface of clearable directed graphs.
2091    /// It extends \ref BaseDigraphComponent with a function for clearing
2092    /// the digraph.
2093    /// This concept requires \ref AlterableDigraphComponent.
2094    template <typename BAS = BaseDigraphComponent>
2095    class ClearableDigraphComponent : public BAS {
2096    public:
2097
2098      typedef BAS Base;
2099
2100      /// \brief Erase all nodes and arcs from the digraph.
2101      ///
2102      /// This function erases all nodes and arcs from the digraph.
2103      void clear() {}
2104
2105      template <typename _Digraph>
2106      struct Constraints {
2107        void constraints() {
2108          checkConcept<Base, _Digraph>();
2109          digraph.clear();
2110        }
2111
2112        _Digraph& digraph;
2113        Constraints() {}
2114      };
2115    };
2116
2117    /// \brief Skeleton class for clearable undirected graphs.
2118    ///
2119    /// This class describes the interface of clearable undirected graphs.
2120    /// It extends \ref BaseGraphComponent with a function for clearing
2121    /// the graph.
2122    /// This concept requires \ref AlterableGraphComponent.
2123    template <typename BAS = BaseGraphComponent>
2124    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
2125
2126    /// \brief Skeleton class for clearable undirected biparite graphs.
2127    ///
2128    /// This class describes the interface of clearable undirected
2129    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
2130    /// function for clearing the graph.  This concept requires \ref
2131    /// AlterableBpGraphComponent.
2132    template <typename BAS = BaseBpGraphComponent>
2133    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
2134
2135  }
2136
2137}
2138
2139#endif
Note: See TracBrowser for help on using the repository browser.