COIN-OR::LEMON - Graph Library

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

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

Apply unify-sources.sh to the source tree

File size: 69.0 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\ingroup graph_concepts
20///\file
21///\brief The 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          ::lemon::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            ::lemon::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 also be used 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 also be used 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 function 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 function 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 function 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 function 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      template <typename _BpGraph>
432      struct Constraints {
433        typedef typename _BpGraph::Node Node;
434        typedef typename _BpGraph::RedNode RedNode;
435        typedef typename _BpGraph::BlueNode BlueNode;
436        typedef typename _BpGraph::Arc Arc;
437        typedef typename _BpGraph::Edge Edge;
438
439        void constraints() {
440          checkConcept<BaseGraphComponent, _BpGraph>();
441          checkConcept<GraphItem<'n'>, RedNode>();
442          checkConcept<GraphItem<'n'>, BlueNode>();
443          {
444            Node n;
445            RedNode rn;
446            BlueNode bn;
447            Node rnan = rn;
448            Node bnan = bn;
449            Edge e;
450            bool b;
451            b = bpgraph.red(rnan);
452            b = bpgraph.blue(bnan);
453            rn = bpgraph.redNode(e);
454            bn = bpgraph.blueNode(e);
455            rn = bpgraph.asRedNodeUnsafe(rnan);
456            bn = bpgraph.asBlueNodeUnsafe(bnan);
457            rn = bpgraph.asRedNode(rnan);
458            bn = bpgraph.asBlueNode(bnan);
459            ::lemon::ignore_unused_variable_warning(b);
460          }
461        }
462
463        const _BpGraph& bpgraph;
464      };
465
466    };
467
468    /// \brief Skeleton class for \e idable directed graphs.
469    ///
470    /// This class describes the interface of \e idable directed graphs.
471    /// It extends \ref BaseDigraphComponent with the core ID functions.
472    /// The ids of the items must be unique and immutable.
473    /// This concept is part of the Digraph concept.
474    template <typename BAS = BaseDigraphComponent>
475    class IDableDigraphComponent : public BAS {
476    public:
477
478      typedef BAS Base;
479      typedef typename Base::Node Node;
480      typedef typename Base::Arc Arc;
481
482      /// \brief Return a unique integer id for the given node.
483      ///
484      /// This function returns a unique integer id for the given node.
485      int id(const Node&) const { return -1; }
486
487      /// \brief Return the node by its unique id.
488      ///
489      /// This function returns the node by its unique id.
490      /// If the digraph does not contain a node with the given id,
491      /// then the result of the function is undefined.
492      Node nodeFromId(int) const { return INVALID; }
493
494      /// \brief Return a unique integer id for the given arc.
495      ///
496      /// This function returns a unique integer id for the given arc.
497      int id(const Arc&) const { return -1; }
498
499      /// \brief Return the arc by its unique id.
500      ///
501      /// This function returns the arc by its unique id.
502      /// If the digraph does not contain an arc with the given id,
503      /// then the result of the function is undefined.
504      Arc arcFromId(int) const { return INVALID; }
505
506      /// \brief Return an integer greater or equal to the maximum
507      /// node id.
508      ///
509      /// This function returns an integer greater or equal to the
510      /// maximum node id.
511      int maxNodeId() const { return -1; }
512
513      /// \brief Return an integer greater or equal to the maximum
514      /// arc id.
515      ///
516      /// This function returns an integer greater or equal to the
517      /// maximum arc id.
518      int maxArcId() const { return -1; }
519
520      template <typename _Digraph>
521      struct Constraints {
522
523        void constraints() {
524          checkConcept<Base, _Digraph >();
525          typename _Digraph::Node node;
526          node=INVALID;
527          int nid = digraph.id(node);
528          nid = digraph.id(node);
529          node = digraph.nodeFromId(nid);
530          typename _Digraph::Arc arc;
531          arc=INVALID;
532          int eid = digraph.id(arc);
533          eid = digraph.id(arc);
534          arc = digraph.arcFromId(eid);
535
536          nid = digraph.maxNodeId();
537          ::lemon::ignore_unused_variable_warning(nid);
538          eid = digraph.maxArcId();
539          ::lemon::ignore_unused_variable_warning(eid);
540        }
541
542        const _Digraph& digraph;
543        Constraints() {}
544      };
545    };
546
547    /// \brief Skeleton class for \e idable undirected graphs.
548    ///
549    /// This class describes the interface of \e idable undirected
550    /// graphs. It extends \ref IDableDigraphComponent with the core ID
551    /// functions of undirected graphs.
552    /// The ids of the items must be unique and immutable.
553    /// This concept is part of the Graph concept.
554    template <typename BAS = BaseGraphComponent>
555    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
556    public:
557
558      typedef BAS Base;
559      typedef typename Base::Edge Edge;
560
561      using IDableDigraphComponent<Base>::id;
562
563      /// \brief Return a unique integer id for the given edge.
564      ///
565      /// This function returns a unique integer id for the given edge.
566      int id(const Edge&) const { return -1; }
567
568      /// \brief Return the edge by its unique id.
569      ///
570      /// This function returns the edge by its unique id.
571      /// If the graph does not contain an edge with the given id,
572      /// then the result of the function is undefined.
573      Edge edgeFromId(int) const { return INVALID; }
574
575      /// \brief Return an integer greater or equal to the maximum
576      /// edge id.
577      ///
578      /// This function returns an integer greater or equal to the
579      /// maximum edge id.
580      int maxEdgeId() const { return -1; }
581
582      template <typename _Graph>
583      struct Constraints {
584
585        void constraints() {
586          checkConcept<IDableDigraphComponent<Base>, _Graph >();
587          typename _Graph::Edge edge;
588          int ueid = graph.id(edge);
589          ueid = graph.id(edge);
590          edge = graph.edgeFromId(ueid);
591          ueid = graph.maxEdgeId();
592          ::lemon::ignore_unused_variable_warning(ueid);
593        }
594
595        const _Graph& graph;
596        Constraints() {}
597      };
598    };
599
600    /// \brief Skeleton class for \e idable undirected bipartite graphs.
601    ///
602    /// This class describes the interface of \e idable undirected
603    /// bipartite graphs. It extends \ref IDableGraphComponent with
604    /// the core ID functions of undirected bipartite graphs. Beside
605    /// the regular node ids, this class also provides ids within the
606    /// the red and blue sets of the nodes. This concept is part of
607    /// the BpGraph concept.
608    template <typename BAS = BaseBpGraphComponent>
609    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
610    public:
611
612      typedef BAS Base;
613      typedef IDableGraphComponent<BAS> Parent;
614      typedef typename Base::Node Node;
615      typedef typename Base::RedNode RedNode;
616      typedef typename Base::BlueNode BlueNode;
617
618      using Parent::id;
619
620      /// \brief Return a unique integer id for the given node in the red set.
621      ///
622      /// Return a unique integer id for the given node in the red set.
623      int id(const RedNode&) const { return -1; }
624
625      /// \brief Return a unique integer id for the given node in the blue set.
626      ///
627      /// Return a unique integer id for the given node in the blue set.
628      int id(const BlueNode&) const { return -1; }
629
630      /// \brief Return an integer greater or equal to the maximum
631      /// node id in the red set.
632      ///
633      /// Return an integer greater or equal to the maximum
634      /// node id in the red set.
635      int maxRedId() const { return -1; }
636
637      /// \brief Return an integer greater or equal to the maximum
638      /// node id in the blue set.
639      ///
640      /// Return an integer greater or equal to the maximum
641      /// node id in the blue set.
642      int maxBlueId() const { return -1; }
643
644      template <typename _BpGraph>
645      struct Constraints {
646
647        void constraints() {
648          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
649          typename _BpGraph::Node node;
650          typename _BpGraph::RedNode red;
651          typename _BpGraph::BlueNode blue;
652          int rid = bpgraph.id(red);
653          int bid = bpgraph.id(blue);
654          rid = bpgraph.maxRedId();
655          bid = bpgraph.maxBlueId();
656          ::lemon::ignore_unused_variable_warning(rid);
657          ::lemon::ignore_unused_variable_warning(bid);
658        }
659
660        const _BpGraph& bpgraph;
661      };
662    };
663
664    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
665    ///
666    /// This class describes the concept of \c NodeIt, \c ArcIt and
667    /// \c EdgeIt subtypes of digraph and graph types.
668    template <typename GR, typename Item>
669    class GraphItemIt : public Item {
670    public:
671      /// \brief Default constructor.
672      ///
673      /// Default constructor.
674      /// \warning The default constructor is not required to set
675      /// the iterator to some well-defined value. So you should consider it
676      /// as uninitialized.
677      GraphItemIt() {}
678
679      /// \brief Copy constructor.
680      ///
681      /// Copy constructor.
682      GraphItemIt(const GraphItemIt& it) : Item(it) {}
683
684      /// \brief Constructor that sets the iterator to the first item.
685      ///
686      /// Constructor that sets the iterator to the first item.
687      explicit GraphItemIt(const GR&) {}
688
689      /// \brief Constructor for conversion from \c INVALID.
690      ///
691      /// Constructor for conversion from \c INVALID.
692      /// It initializes the iterator to be invalid.
693      /// \sa Invalid for more details.
694      GraphItemIt(Invalid) {}
695
696      /// \brief Assignment operator.
697      ///
698      /// Assignment operator for the iterator.
699      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
700
701      /// \brief Increment the iterator.
702      ///
703      /// This operator increments the iterator, i.e. assigns it to the
704      /// next item.
705      GraphItemIt& operator++() { return *this; }
706
707      /// \brief Equality operator
708      ///
709      /// Equality operator.
710      /// Two iterators are equal if and only if they point to the
711      /// same object or both are invalid.
712      bool operator==(const GraphItemIt&) const { return true;}
713
714      /// \brief Inequality operator
715      ///
716      /// Inequality operator.
717      /// Two iterators are equal if and only if they point to the
718      /// same object or both are invalid.
719      bool operator!=(const GraphItemIt&) const { return true;}
720
721      template<typename _GraphItemIt>
722      struct Constraints {
723        void constraints() {
724          checkConcept<GraphItem<>, _GraphItemIt>();
725          _GraphItemIt it1(g);
726          _GraphItemIt it2;
727          _GraphItemIt it3 = it1;
728          _GraphItemIt it4 = INVALID;
729          ::lemon::ignore_unused_variable_warning(it3);
730          ::lemon::ignore_unused_variable_warning(it4);
731
732          it2 = ++it1;
733          ++it2 = it1;
734          ++(++it1);
735
736          Item bi = it1;
737          bi = it2;
738        }
739        const GR& g;
740        Constraints() {}
741      };
742    };
743
744    /// \brief Concept class for \c InArcIt, \c OutArcIt and
745    /// \c IncEdgeIt types.
746    ///
747    /// This class describes the concept of \c InArcIt, \c OutArcIt
748    /// and \c IncEdgeIt subtypes of digraph and graph types.
749    ///
750    /// \note Since these iterator classes do not inherit from the same
751    /// base class, there is an additional template parameter (selector)
752    /// \c sel. For \c InArcIt you should instantiate it with character
753    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
754    template <typename GR,
755              typename Item = typename GR::Arc,
756              typename Base = typename GR::Node,
757              char sel = '0'>
758    class GraphIncIt : public Item {
759    public:
760      /// \brief Default constructor.
761      ///
762      /// Default constructor.
763      /// \warning The default constructor is not required to set
764      /// the iterator to some well-defined value. So you should consider it
765      /// as uninitialized.
766      GraphIncIt() {}
767
768      /// \brief Copy constructor.
769      ///
770      /// Copy constructor.
771      GraphIncIt(const GraphIncIt& it) : Item(it) {}
772
773      /// \brief Constructor that sets the iterator to the first
774      /// incoming or outgoing arc.
775      ///
776      /// Constructor that sets the iterator to the first arc
777      /// incoming to or outgoing from the given node.
778      explicit GraphIncIt(const GR&, const Base&) {}
779
780      /// \brief Constructor for conversion from \c INVALID.
781      ///
782      /// Constructor for conversion from \c INVALID.
783      /// It initializes the iterator to be invalid.
784      /// \sa Invalid for more details.
785      GraphIncIt(Invalid) {}
786
787      /// \brief Assignment operator.
788      ///
789      /// Assignment operator for the iterator.
790      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
791
792      /// \brief Increment the iterator.
793      ///
794      /// This operator increments the iterator, i.e. assigns it to the
795      /// next arc incoming to or outgoing from the given node.
796      GraphIncIt& operator++() { return *this; }
797
798      /// \brief Equality operator
799      ///
800      /// Equality operator.
801      /// Two iterators are equal if and only if they point to the
802      /// same object or both are invalid.
803      bool operator==(const GraphIncIt&) const { return true;}
804
805      /// \brief Inequality operator
806      ///
807      /// Inequality operator.
808      /// Two iterators are equal if and only if they point to the
809      /// same object or both are invalid.
810      bool operator!=(const GraphIncIt&) const { return true;}
811
812      template <typename _GraphIncIt>
813      struct Constraints {
814        void constraints() {
815          checkConcept<GraphItem<sel>, _GraphIncIt>();
816          _GraphIncIt it1(graph, node);
817          _GraphIncIt it2;
818          _GraphIncIt it3 = it1;
819          _GraphIncIt it4 = INVALID;
820          ::lemon::ignore_unused_variable_warning(it3);
821          ::lemon::ignore_unused_variable_warning(it4);
822
823          it2 = ++it1;
824          ++it2 = it1;
825          ++(++it1);
826          Item e = it1;
827          e = it2;
828        }
829        const Base& node;
830        const GR& graph;
831        Constraints() {}
832      };
833    };
834
835    /// \brief Skeleton class for iterable directed graphs.
836    ///
837    /// This class describes the interface of iterable directed
838    /// graphs. It extends \ref BaseDigraphComponent with the core
839    /// iterable interface.
840    /// This concept is part of the Digraph concept.
841    template <typename BAS = BaseDigraphComponent>
842    class IterableDigraphComponent : public BAS {
843
844    public:
845
846      typedef BAS Base;
847      typedef typename Base::Node Node;
848      typedef typename Base::Arc Arc;
849
850      typedef IterableDigraphComponent Digraph;
851
852      /// \name Base Iteration
853      ///
854      /// This interface provides functions for iteration on digraph items.
855      ///
856      /// @{
857
858      /// \brief Return the first node.
859      ///
860      /// This function gives back the first node in the iteration order.
861      void first(Node&) const {}
862
863      /// \brief Return the next node.
864      ///
865      /// This function gives back the next node in the iteration order.
866      void next(Node&) const {}
867
868      /// \brief Return the first arc.
869      ///
870      /// This function gives back the first arc in the iteration order.
871      void first(Arc&) const {}
872
873      /// \brief Return the next arc.
874      ///
875      /// This function gives back the next arc in the iteration order.
876      void next(Arc&) const {}
877
878      /// \brief Return the first arc incoming to the given node.
879      ///
880      /// This function gives back the first arc incoming to the
881      /// given node.
882      void firstIn(Arc&, const Node&) const {}
883
884      /// \brief Return the next arc incoming to the given node.
885      ///
886      /// This function gives back the next arc incoming to the
887      /// given node.
888      void nextIn(Arc&) const {}
889
890      /// \brief Return the first arc outgoing form the given node.
891      ///
892      /// This function gives back the first arc outgoing form the
893      /// given node.
894      void firstOut(Arc&, const Node&) const {}
895
896      /// \brief Return the next arc outgoing form the given node.
897      ///
898      /// This function gives back the next arc outgoing form the
899      /// given node.
900      void nextOut(Arc&) const {}
901
902      /// @}
903
904      /// \name Class Based Iteration
905      ///
906      /// This interface provides iterator classes for digraph items.
907      ///
908      /// @{
909
910      /// \brief This iterator goes through each node.
911      ///
912      /// This iterator goes through each node.
913      ///
914      typedef GraphItemIt<Digraph, Node> NodeIt;
915
916      /// \brief This iterator goes through each arc.
917      ///
918      /// This iterator goes through each arc.
919      ///
920      typedef GraphItemIt<Digraph, Arc> ArcIt;
921
922      /// \brief This iterator goes trough the incoming arcs of a node.
923      ///
924      /// This iterator goes trough the \e incoming arcs of a certain node
925      /// of a digraph.
926      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
927
928      /// \brief This iterator goes trough the outgoing arcs of a node.
929      ///
930      /// This iterator goes trough the \e outgoing arcs of a certain node
931      /// of a digraph.
932      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
933
934      /// \brief The base node of the iterator.
935      ///
936      /// This function gives back the base node of the iterator.
937      /// It is always the target node of the pointed arc.
938      Node baseNode(const InArcIt&) const { return INVALID; }
939
940      /// \brief The running node of the iterator.
941      ///
942      /// This function gives back the running node of the iterator.
943      /// It is always the source node of the pointed arc.
944      Node runningNode(const InArcIt&) const { return INVALID; }
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 source node of the pointed arc.
950      Node baseNode(const OutArcIt&) 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 target node of the pointed arc.
956      Node runningNode(const OutArcIt&) const { return INVALID; }
957
958      /// @}
959
960      template <typename _Digraph>
961      struct Constraints {
962        void constraints() {
963          checkConcept<Base, _Digraph>();
964
965          {
966            typename _Digraph::Node node(INVALID);
967            typename _Digraph::Arc arc(INVALID);
968            {
969              digraph.first(node);
970              digraph.next(node);
971            }
972            {
973              digraph.first(arc);
974              digraph.next(arc);
975            }
976            {
977              digraph.firstIn(arc, node);
978              digraph.nextIn(arc);
979            }
980            {
981              digraph.firstOut(arc, node);
982              digraph.nextOut(arc);
983            }
984          }
985
986          {
987            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
988              typename _Digraph::ArcIt >();
989            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
990              typename _Digraph::NodeIt >();
991            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
992              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
993            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
994              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
995
996            typename _Digraph::Node n;
997            const typename _Digraph::InArcIt iait(INVALID);
998            const typename _Digraph::OutArcIt oait(INVALID);
999            n = digraph.baseNode(iait);
1000            n = digraph.runningNode(iait);
1001            n = digraph.baseNode(oait);
1002            n = digraph.runningNode(oait);
1003            ::lemon::ignore_unused_variable_warning(n);
1004          }
1005        }
1006
1007        const _Digraph& digraph;
1008        Constraints() {}
1009      };
1010    };
1011
1012    /// \brief Skeleton class for iterable undirected graphs.
1013    ///
1014    /// This class describes the interface of iterable undirected
1015    /// graphs. It extends \ref IterableDigraphComponent with the core
1016    /// iterable interface of undirected graphs.
1017    /// This concept is part of the Graph concept.
1018    template <typename BAS = BaseGraphComponent>
1019    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
1020    public:
1021
1022      typedef BAS Base;
1023      typedef typename Base::Node Node;
1024      typedef typename Base::Arc Arc;
1025      typedef typename Base::Edge Edge;
1026
1027
1028      typedef IterableGraphComponent Graph;
1029
1030      /// \name Base Iteration
1031      ///
1032      /// This interface provides functions for iteration on edges.
1033      ///
1034      /// @{
1035
1036      using IterableDigraphComponent<Base>::first;
1037      using IterableDigraphComponent<Base>::next;
1038
1039      /// \brief Return the first edge.
1040      ///
1041      /// This function gives back the first edge in the iteration order.
1042      void first(Edge&) const {}
1043
1044      /// \brief Return the next edge.
1045      ///
1046      /// This function gives back the next edge in the iteration order.
1047      void next(Edge&) const {}
1048
1049      /// \brief Return the first edge incident to the given node.
1050      ///
1051      /// This function gives back the first edge incident to the given
1052      /// node. The bool parameter gives back the direction for which the
1053      /// source node of the directed arc representing the edge is the
1054      /// given node.
1055      void firstInc(Edge&, bool&, const Node&) const {}
1056
1057      /// \brief Gives back the next of the edges from the
1058      /// given node.
1059      ///
1060      /// This function gives back the next edge incident to the given
1061      /// node. The bool parameter should be used as \c firstInc() use it.
1062      void nextInc(Edge&, bool&) const {}
1063
1064      using IterableDigraphComponent<Base>::baseNode;
1065      using IterableDigraphComponent<Base>::runningNode;
1066
1067      /// @}
1068
1069      /// \name Class Based Iteration
1070      ///
1071      /// This interface provides iterator classes for edges.
1072      ///
1073      /// @{
1074
1075      /// \brief This iterator goes through each edge.
1076      ///
1077      /// This iterator goes through each edge.
1078      typedef GraphItemIt<Graph, Edge> EdgeIt;
1079
1080      /// \brief This iterator goes trough the incident edges of a
1081      /// node.
1082      ///
1083      /// This iterator goes trough the incident edges of a certain
1084      /// node of a graph.
1085      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
1086
1087      /// \brief The base node of the iterator.
1088      ///
1089      /// This function gives back the base node of the iterator.
1090      Node baseNode(const IncEdgeIt&) const { return INVALID; }
1091
1092      /// \brief The running node of the iterator.
1093      ///
1094      /// This function gives back the running node of the iterator.
1095      Node runningNode(const IncEdgeIt&) const { return INVALID; }
1096
1097      /// @}
1098
1099      template <typename _Graph>
1100      struct Constraints {
1101        void constraints() {
1102          checkConcept<IterableDigraphComponent<Base>, _Graph>();
1103
1104          {
1105            typename _Graph::Node node(INVALID);
1106            typename _Graph::Edge edge(INVALID);
1107            bool dir;
1108            {
1109              graph.first(edge);
1110              graph.next(edge);
1111            }
1112            {
1113              graph.firstInc(edge, dir, node);
1114              graph.nextInc(edge, dir);
1115            }
1116
1117          }
1118
1119          {
1120            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1121              typename _Graph::EdgeIt >();
1122            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1123              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
1124
1125            typename _Graph::Node n;
1126            const typename _Graph::IncEdgeIt ieit(INVALID);
1127            n = graph.baseNode(ieit);
1128            n = graph.runningNode(ieit);
1129          }
1130        }
1131
1132        const _Graph& graph;
1133        Constraints() {}
1134      };
1135    };
1136
1137    /// \brief Skeleton class for iterable undirected bipartite graphs.
1138    ///
1139    /// This class describes the interface of iterable undirected
1140    /// bipartite graphs. It extends \ref IterableGraphComponent with
1141    /// the core iterable interface of undirected bipartite graphs.
1142    /// This concept is part of the BpGraph concept.
1143    template <typename BAS = BaseBpGraphComponent>
1144    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
1145    public:
1146
1147      typedef BAS Base;
1148      typedef typename Base::Node Node;
1149      typedef typename Base::RedNode RedNode;
1150      typedef typename Base::BlueNode BlueNode;
1151      typedef typename Base::Arc Arc;
1152      typedef typename Base::Edge Edge;
1153
1154      typedef IterableBpGraphComponent BpGraph;
1155
1156      using IterableGraphComponent<BAS>::first;
1157      using IterableGraphComponent<BAS>::next;
1158
1159      /// \name Base Iteration
1160      ///
1161      /// This interface provides functions for iteration on red and blue nodes.
1162      ///
1163      /// @{
1164
1165      /// \brief Return the first red node.
1166      ///
1167      /// This function gives back the first red node in the iteration order.
1168      void first(RedNode&) const {}
1169
1170      /// \brief Return the next red node.
1171      ///
1172      /// This function gives back the next red node in the iteration order.
1173      void next(RedNode&) const {}
1174
1175      /// \brief Return the first blue node.
1176      ///
1177      /// This function gives back the first blue node in the iteration order.
1178      void first(BlueNode&) const {}
1179
1180      /// \brief Return the next blue node.
1181      ///
1182      /// This function gives back the next blue node in the iteration order.
1183      void next(BlueNode&) const {}
1184
1185
1186      /// @}
1187
1188      /// \name Class Based Iteration
1189      ///
1190      /// This interface provides iterator classes for red and blue nodes.
1191      ///
1192      /// @{
1193
1194      /// \brief This iterator goes through each red node.
1195      ///
1196      /// This iterator goes through each red node.
1197      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
1198
1199      /// \brief This iterator goes through each blue node.
1200      ///
1201      /// This iterator goes through each blue node.
1202      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
1203
1204      /// @}
1205
1206      template <typename _BpGraph>
1207      struct Constraints {
1208        void constraints() {
1209          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1210
1211          typename _BpGraph::RedNode rn(INVALID);
1212          bpgraph.first(rn);
1213          bpgraph.next(rn);
1214          typename _BpGraph::BlueNode bn(INVALID);
1215          bpgraph.first(bn);
1216          bpgraph.next(bn);
1217
1218          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
1219            typename _BpGraph::RedNodeIt>();
1220          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
1221            typename _BpGraph::BlueNodeIt>();
1222        }
1223
1224        const _BpGraph& bpgraph;
1225      };
1226    };
1227
1228    /// \brief Skeleton class for alterable directed graphs.
1229    ///
1230    /// This class describes the interface of alterable directed
1231    /// graphs. It extends \ref BaseDigraphComponent with the alteration
1232    /// notifier interface. It implements
1233    /// an observer-notifier pattern for each digraph item. More
1234    /// obsevers can be registered into the notifier and whenever an
1235    /// alteration occured in the digraph all the observers will be
1236    /// notified about it.
1237    template <typename BAS = BaseDigraphComponent>
1238    class AlterableDigraphComponent : public BAS {
1239    public:
1240
1241      typedef BAS Base;
1242      typedef typename Base::Node Node;
1243      typedef typename Base::Arc Arc;
1244
1245
1246      /// Node alteration notifier class.
1247      typedef AlterationNotifier<AlterableDigraphComponent, Node>
1248      NodeNotifier;
1249      /// Arc alteration notifier class.
1250      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
1251      ArcNotifier;
1252
1253      mutable NodeNotifier node_notifier;
1254      mutable ArcNotifier arc_notifier;
1255
1256      /// \brief Return the node alteration notifier.
1257      ///
1258      /// This function gives back the node alteration notifier.
1259      NodeNotifier& notifier(Node) const {
1260        return node_notifier;
1261      }
1262
1263      /// \brief Return the arc alteration notifier.
1264      ///
1265      /// This function gives back the arc alteration notifier.
1266      ArcNotifier& notifier(Arc) const {
1267        return arc_notifier;
1268      }
1269
1270      template <typename _Digraph>
1271      struct Constraints {
1272        void constraints() {
1273          checkConcept<Base, _Digraph>();
1274          typename _Digraph::NodeNotifier& nn
1275            = digraph.notifier(typename _Digraph::Node());
1276
1277          typename _Digraph::ArcNotifier& en
1278            = digraph.notifier(typename _Digraph::Arc());
1279
1280          ::lemon::ignore_unused_variable_warning(nn);
1281          ::lemon::ignore_unused_variable_warning(en);
1282        }
1283
1284        const _Digraph& digraph;
1285        Constraints() {}
1286      };
1287    };
1288
1289    /// \brief Skeleton class for alterable undirected graphs.
1290    ///
1291    /// This class describes the interface of alterable undirected
1292    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
1293    /// notifier interface of undirected graphs. It implements
1294    /// an observer-notifier pattern for the edges. More
1295    /// obsevers can be registered into the notifier and whenever an
1296    /// alteration occured in the graph all the observers will be
1297    /// notified about it.
1298    template <typename BAS = BaseGraphComponent>
1299    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
1300    public:
1301
1302      typedef BAS Base;
1303      typedef AlterableDigraphComponent<Base> Parent;
1304      typedef typename Base::Edge Edge;
1305
1306
1307      /// Edge alteration notifier class.
1308      typedef AlterationNotifier<AlterableGraphComponent, Edge>
1309      EdgeNotifier;
1310
1311      mutable EdgeNotifier edge_notifier;
1312
1313      using Parent::notifier;
1314
1315      /// \brief Return the edge alteration notifier.
1316      ///
1317      /// This function gives back the edge alteration notifier.
1318      EdgeNotifier& notifier(Edge) const {
1319        return edge_notifier;
1320      }
1321
1322      template <typename _Graph>
1323      struct Constraints {
1324        void constraints() {
1325          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
1326          typename _Graph::EdgeNotifier& uen
1327            = graph.notifier(typename _Graph::Edge());
1328          ::lemon::ignore_unused_variable_warning(uen);
1329        }
1330
1331        const _Graph& graph;
1332        Constraints() {}
1333      };
1334    };
1335
1336    /// \brief Skeleton class for alterable undirected bipartite graphs.
1337    ///
1338    /// This class describes the interface of alterable undirected
1339    /// bipartite graphs. It extends \ref AlterableGraphComponent with
1340    /// the alteration notifier interface of bipartite graphs. It
1341    /// implements an observer-notifier pattern for the red and blue
1342    /// nodes. More obsevers can be registered into the notifier and
1343    /// whenever an alteration occured in the graph all the observers
1344    /// will be notified about it.
1345    template <typename BAS = BaseBpGraphComponent>
1346    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
1347    public:
1348
1349      typedef BAS Base;
1350      typedef AlterableGraphComponent<Base> Parent;
1351      typedef typename Base::RedNode RedNode;
1352      typedef typename Base::BlueNode BlueNode;
1353
1354
1355      /// Red node alteration notifier class.
1356      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
1357      RedNodeNotifier;
1358
1359      /// Blue node alteration notifier class.
1360      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
1361      BlueNodeNotifier;
1362
1363      mutable RedNodeNotifier red_node_notifier;
1364      mutable BlueNodeNotifier blue_node_notifier;
1365
1366      using Parent::notifier;
1367
1368      /// \brief Return the red node alteration notifier.
1369      ///
1370      /// This function gives back the red node alteration notifier.
1371      RedNodeNotifier& notifier(RedNode) const {
1372        return red_node_notifier;
1373      }
1374
1375      /// \brief Return the blue node alteration notifier.
1376      ///
1377      /// This function gives back the blue node alteration notifier.
1378      BlueNodeNotifier& notifier(BlueNode) const {
1379        return blue_node_notifier;
1380      }
1381
1382      template <typename _BpGraph>
1383      struct Constraints {
1384        void constraints() {
1385          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
1386          typename _BpGraph::RedNodeNotifier& rnn
1387            = bpgraph.notifier(typename _BpGraph::RedNode());
1388          typename _BpGraph::BlueNodeNotifier& bnn
1389            = bpgraph.notifier(typename _BpGraph::BlueNode());
1390          ::lemon::ignore_unused_variable_warning(rnn);
1391          ::lemon::ignore_unused_variable_warning(bnn);
1392        }
1393
1394        const _BpGraph& bpgraph;
1395      };
1396    };
1397
1398    /// \brief Concept class for standard graph maps.
1399    ///
1400    /// This class describes the concept of standard graph maps, i.e.
1401    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
1402    /// graph types, which can be used for associating data to graph items.
1403    /// The standard graph maps must conform to the ReferenceMap concept.
1404    template <typename GR, typename K, typename V>
1405    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
1406      typedef ReferenceMap<K, V, V&, const V&> Parent;
1407
1408    public:
1409
1410      /// The key type of the map.
1411      typedef K Key;
1412      /// The value type of the map.
1413      typedef V Value;
1414      /// The reference type of the map.
1415      typedef Value& Reference;
1416      /// The const reference type of the map.
1417      typedef const Value& ConstReference;
1418
1419      // The reference map tag.
1420      typedef True ReferenceMapTag;
1421
1422      /// \brief Construct a new map.
1423      ///
1424      /// Construct a new map for the graph.
1425      explicit GraphMap(const GR&) {}
1426      /// \brief Construct a new map with default value.
1427      ///
1428      /// Construct a new map for the graph and initalize the values.
1429      GraphMap(const GR&, const Value&) {}
1430
1431    private:
1432      /// \brief Copy constructor.
1433      ///
1434      /// Copy Constructor.
1435      GraphMap(const GraphMap&) : Parent() {}
1436
1437      /// \brief Assignment operator.
1438      ///
1439      /// Assignment operator. It does not mofify the underlying graph,
1440      /// it just iterates on the current item set and set the  map
1441      /// with the value returned by the assigned map.
1442      template <typename CMap>
1443      GraphMap& operator=(const CMap&) {
1444        checkConcept<ReadMap<Key, Value>, CMap>();
1445        return *this;
1446      }
1447
1448    public:
1449      template<typename _Map>
1450      struct Constraints {
1451        void constraints() {
1452          checkConcept
1453            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
1454          _Map m1(g);
1455          _Map m2(g,t);
1456
1457          // Copy constructor
1458          // _Map m3(m);
1459
1460          // Assignment operator
1461          // ReadMap<Key, Value> cmap;
1462          // m3 = cmap;
1463
1464          ::lemon::ignore_unused_variable_warning(m1);
1465          ::lemon::ignore_unused_variable_warning(m2);
1466          // ::lemon::ignore_unused_variable_warning(m3);
1467        }
1468
1469        const _Map &m;
1470        const GR &g;
1471        const typename GraphMap::Value &t;
1472        Constraints() {}
1473      };
1474
1475    };
1476
1477    /// \brief Skeleton class for mappable directed graphs.
1478    ///
1479    /// This class describes the interface of mappable directed graphs.
1480    /// It extends \ref BaseDigraphComponent with the standard digraph
1481    /// map classes, namely \c NodeMap and \c ArcMap.
1482    /// This concept is part of the Digraph concept.
1483    template <typename BAS = BaseDigraphComponent>
1484    class MappableDigraphComponent : public BAS  {
1485    public:
1486
1487      typedef BAS Base;
1488      typedef typename Base::Node Node;
1489      typedef typename Base::Arc Arc;
1490
1491      typedef MappableDigraphComponent Digraph;
1492
1493      /// \brief Standard graph map for the nodes.
1494      ///
1495      /// Standard graph map for the nodes.
1496      /// It conforms to the ReferenceMap concept.
1497      template <typename V>
1498      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
1499        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1500
1501      public:
1502        /// \brief Construct a new map.
1503        ///
1504        /// Construct a new map for the digraph.
1505        explicit NodeMap(const MappableDigraphComponent& digraph)
1506          : Parent(digraph) {}
1507
1508        /// \brief Construct a new map with default value.
1509        ///
1510        /// Construct a new map for the digraph and initalize the values.
1511        NodeMap(const MappableDigraphComponent& digraph, const V& value)
1512          : Parent(digraph, value) {}
1513
1514      private:
1515        /// \brief Copy constructor.
1516        ///
1517        /// Copy Constructor.
1518        NodeMap(const NodeMap& nm) : Parent(nm) {}
1519
1520        /// \brief Assignment operator.
1521        ///
1522        /// Assignment operator.
1523        template <typename CMap>
1524        NodeMap& operator=(const CMap&) {
1525          checkConcept<ReadMap<Node, V>, CMap>();
1526          return *this;
1527        }
1528
1529      };
1530
1531      /// \brief Standard graph map for the arcs.
1532      ///
1533      /// Standard graph map for the arcs.
1534      /// It conforms to the ReferenceMap concept.
1535      template <typename V>
1536      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
1537        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1538
1539      public:
1540        /// \brief Construct a new map.
1541        ///
1542        /// Construct a new map for the digraph.
1543        explicit ArcMap(const MappableDigraphComponent& digraph)
1544          : Parent(digraph) {}
1545
1546        /// \brief Construct a new map with default value.
1547        ///
1548        /// Construct a new map for the digraph and initalize the values.
1549        ArcMap(const MappableDigraphComponent& digraph, const V& value)
1550          : Parent(digraph, value) {}
1551
1552      private:
1553        /// \brief Copy constructor.
1554        ///
1555        /// Copy Constructor.
1556        ArcMap(const ArcMap& nm) : Parent(nm) {}
1557
1558        /// \brief Assignment operator.
1559        ///
1560        /// Assignment operator.
1561        template <typename CMap>
1562        ArcMap& operator=(const CMap&) {
1563          checkConcept<ReadMap<Arc, V>, CMap>();
1564          return *this;
1565        }
1566
1567      };
1568
1569
1570      template <typename _Digraph>
1571      struct Constraints {
1572
1573        struct Dummy {
1574          int value;
1575          Dummy() : value(0) {}
1576          Dummy(int _v) : value(_v) {}
1577        };
1578
1579        void constraints() {
1580          checkConcept<Base, _Digraph>();
1581          { // int map test
1582            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1583            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1584              IntNodeMap >();
1585          } { // bool map test
1586            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1587            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1588              BoolNodeMap >();
1589          } { // Dummy map test
1590            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1591            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1592              DummyNodeMap >();
1593          }
1594
1595          { // int map test
1596            typedef typename _Digraph::template ArcMap<int> IntArcMap;
1597            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1598              IntArcMap >();
1599          } { // bool map test
1600            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1601            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1602              BoolArcMap >();
1603          } { // Dummy map test
1604            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1605            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1606              DummyArcMap >();
1607          }
1608        }
1609
1610        const _Digraph& digraph;
1611        Constraints() {}
1612      };
1613    };
1614
1615    /// \brief Skeleton class for mappable undirected graphs.
1616    ///
1617    /// This class describes the interface of mappable undirected graphs.
1618    /// It extends \ref MappableDigraphComponent with the standard graph
1619    /// map class for edges (\c EdgeMap).
1620    /// This concept is part of the Graph concept.
1621    template <typename BAS = BaseGraphComponent>
1622    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
1623    public:
1624
1625      typedef BAS Base;
1626      typedef typename Base::Edge Edge;
1627
1628      typedef MappableGraphComponent Graph;
1629
1630      /// \brief Standard graph map for the edges.
1631      ///
1632      /// Standard graph map for the edges.
1633      /// It conforms to the ReferenceMap concept.
1634      template <typename V>
1635      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
1636        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1637
1638      public:
1639        /// \brief Construct a new map.
1640        ///
1641        /// Construct a new map for the graph.
1642        explicit EdgeMap(const MappableGraphComponent& graph)
1643          : Parent(graph) {}
1644
1645        /// \brief Construct a new map with default value.
1646        ///
1647        /// Construct a new map for the graph and initalize the values.
1648        EdgeMap(const MappableGraphComponent& graph, const V& value)
1649          : Parent(graph, value) {}
1650
1651      private:
1652        /// \brief Copy constructor.
1653        ///
1654        /// Copy Constructor.
1655        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1656
1657        /// \brief Assignment operator.
1658        ///
1659        /// Assignment operator.
1660        template <typename CMap>
1661        EdgeMap& operator=(const CMap&) {
1662          checkConcept<ReadMap<Edge, V>, CMap>();
1663          return *this;
1664        }
1665
1666      };
1667
1668
1669      template <typename _Graph>
1670      struct Constraints {
1671
1672        struct Dummy {
1673          int value;
1674          Dummy() : value(0) {}
1675          Dummy(int _v) : value(_v) {}
1676        };
1677
1678        void constraints() {
1679          checkConcept<MappableDigraphComponent<Base>, _Graph>();
1680
1681          { // int map test
1682            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1683            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1684              IntEdgeMap >();
1685          } { // bool map test
1686            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1687            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1688              BoolEdgeMap >();
1689          } { // Dummy map test
1690            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1691            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1692              DummyEdgeMap >();
1693          }
1694        }
1695
1696        const _Graph& graph;
1697        Constraints() {}
1698      };
1699    };
1700
1701    /// \brief Skeleton class for mappable undirected bipartite graphs.
1702    ///
1703    /// This class describes the interface of mappable undirected
1704    /// bipartite graphs.  It extends \ref MappableGraphComponent with
1705    /// the standard graph map class for red and blue nodes (\c
1706    /// RedNodeMap and BlueNodeMap). This concept is part of the
1707    /// BpGraph concept.
1708    template <typename BAS = BaseBpGraphComponent>
1709    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
1710    public:
1711
1712      typedef BAS Base;
1713      typedef typename Base::Node Node;
1714
1715      typedef MappableBpGraphComponent BpGraph;
1716
1717      /// \brief Standard graph map for the red nodes.
1718      ///
1719      /// Standard graph map for the red nodes.
1720      /// It conforms to the ReferenceMap concept.
1721      template <typename V>
1722      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1723        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1724
1725      public:
1726        /// \brief Construct a new map.
1727        ///
1728        /// Construct a new map for the graph.
1729        explicit RedNodeMap(const MappableBpGraphComponent& graph)
1730          : Parent(graph) {}
1731
1732        /// \brief Construct a new map with default value.
1733        ///
1734        /// Construct a new map for the graph and initalize the values.
1735        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
1736          : Parent(graph, value) {}
1737
1738      private:
1739        /// \brief Copy constructor.
1740        ///
1741        /// Copy Constructor.
1742        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
1743
1744        /// \brief Assignment operator.
1745        ///
1746        /// Assignment operator.
1747        template <typename CMap>
1748        RedNodeMap& operator=(const CMap&) {
1749          checkConcept<ReadMap<Node, V>, CMap>();
1750          return *this;
1751        }
1752
1753      };
1754
1755      /// \brief Standard graph map for the blue nodes.
1756      ///
1757      /// Standard graph map for the blue nodes.
1758      /// It conforms to the ReferenceMap concept.
1759      template <typename V>
1760      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1761        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1762
1763      public:
1764        /// \brief Construct a new map.
1765        ///
1766        /// Construct a new map for the graph.
1767        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
1768          : Parent(graph) {}
1769
1770        /// \brief Construct a new map with default value.
1771        ///
1772        /// Construct a new map for the graph and initalize the values.
1773        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
1774          : Parent(graph, value) {}
1775
1776      private:
1777        /// \brief Copy constructor.
1778        ///
1779        /// Copy Constructor.
1780        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
1781
1782        /// \brief Assignment operator.
1783        ///
1784        /// Assignment operator.
1785        template <typename CMap>
1786        BlueNodeMap& operator=(const CMap&) {
1787          checkConcept<ReadMap<Node, V>, CMap>();
1788          return *this;
1789        }
1790
1791      };
1792
1793
1794      template <typename _BpGraph>
1795      struct Constraints {
1796
1797        struct Dummy {
1798          int value;
1799          Dummy() : value(0) {}
1800          Dummy(int _v) : value(_v) {}
1801        };
1802
1803        void constraints() {
1804          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
1805
1806          { // int map test
1807            typedef typename _BpGraph::template RedNodeMap<int>
1808              IntRedNodeMap;
1809            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
1810              IntRedNodeMap >();
1811          } { // bool map test
1812            typedef typename _BpGraph::template RedNodeMap<bool>
1813              BoolRedNodeMap;
1814            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
1815              BoolRedNodeMap >();
1816          } { // Dummy map test
1817            typedef typename _BpGraph::template RedNodeMap<Dummy>
1818              DummyRedNodeMap;
1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
1820              DummyRedNodeMap >();
1821          }
1822
1823          { // int map test
1824            typedef typename _BpGraph::template BlueNodeMap<int>
1825              IntBlueNodeMap;
1826            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
1827              IntBlueNodeMap >();
1828          } { // bool map test
1829            typedef typename _BpGraph::template BlueNodeMap<bool>
1830              BoolBlueNodeMap;
1831            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
1832              BoolBlueNodeMap >();
1833          } { // Dummy map test
1834            typedef typename _BpGraph::template BlueNodeMap<Dummy>
1835              DummyBlueNodeMap;
1836            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
1837              DummyBlueNodeMap >();
1838          }
1839        }
1840
1841        const _BpGraph& bpgraph;
1842      };
1843    };
1844
1845    /// \brief Skeleton class for extendable directed graphs.
1846    ///
1847    /// This class describes the interface of extendable directed graphs.
1848    /// It extends \ref BaseDigraphComponent with functions for adding
1849    /// nodes and arcs to the digraph.
1850    /// This concept requires \ref AlterableDigraphComponent.
1851    template <typename BAS = BaseDigraphComponent>
1852    class ExtendableDigraphComponent : public BAS {
1853    public:
1854      typedef BAS Base;
1855
1856      typedef typename Base::Node Node;
1857      typedef typename Base::Arc Arc;
1858
1859      /// \brief Add a new node to the digraph.
1860      ///
1861      /// This function adds a new node to the digraph.
1862      Node addNode() {
1863        return INVALID;
1864      }
1865
1866      /// \brief Add a new arc connecting the given two nodes.
1867      ///
1868      /// This function adds a new arc connecting the given two nodes
1869      /// of the digraph.
1870      Arc addArc(const Node&, const Node&) {
1871        return INVALID;
1872      }
1873
1874      template <typename _Digraph>
1875      struct Constraints {
1876        void constraints() {
1877          checkConcept<Base, _Digraph>();
1878          typename _Digraph::Node node_a, node_b;
1879          node_a = digraph.addNode();
1880          node_b = digraph.addNode();
1881          typename _Digraph::Arc arc;
1882          arc = digraph.addArc(node_a, node_b);
1883        }
1884
1885        _Digraph& digraph;
1886        Constraints() {}
1887      };
1888    };
1889
1890    /// \brief Skeleton class for extendable undirected graphs.
1891    ///
1892    /// This class describes the interface of extendable undirected graphs.
1893    /// It extends \ref BaseGraphComponent with functions for adding
1894    /// nodes and edges to the graph.
1895    /// This concept requires \ref AlterableGraphComponent.
1896    template <typename BAS = BaseGraphComponent>
1897    class ExtendableGraphComponent : public BAS {
1898    public:
1899
1900      typedef BAS Base;
1901      typedef typename Base::Node Node;
1902      typedef typename Base::Edge Edge;
1903
1904      /// \brief Add a new node to the digraph.
1905      ///
1906      /// This function adds a new node to the digraph.
1907      Node addNode() {
1908        return INVALID;
1909      }
1910
1911      /// \brief Add a new edge connecting the given two nodes.
1912      ///
1913      /// This function adds a new edge connecting the given two nodes
1914      /// of the graph.
1915      Edge addEdge(const Node&, const Node&) {
1916        return INVALID;
1917      }
1918
1919      template <typename _Graph>
1920      struct Constraints {
1921        void constraints() {
1922          checkConcept<Base, _Graph>();
1923          typename _Graph::Node node_a, node_b;
1924          node_a = graph.addNode();
1925          node_b = graph.addNode();
1926          typename _Graph::Edge edge;
1927          edge = graph.addEdge(node_a, node_b);
1928        }
1929
1930        _Graph& graph;
1931        Constraints() {}
1932      };
1933    };
1934
1935    /// \brief Skeleton class for extendable undirected bipartite graphs.
1936    ///
1937    /// This class describes the interface of extendable undirected
1938    /// bipartite graphs. It extends \ref BaseGraphComponent with
1939    /// functions for adding nodes and edges to the graph. This
1940    /// concept requires \ref AlterableBpGraphComponent.
1941    template <typename BAS = BaseBpGraphComponent>
1942    class ExtendableBpGraphComponent : public BAS {
1943    public:
1944
1945      typedef BAS Base;
1946      typedef typename Base::Node Node;
1947      typedef typename Base::RedNode RedNode;
1948      typedef typename Base::BlueNode BlueNode;
1949      typedef typename Base::Edge Edge;
1950
1951      /// \brief Add a new red node to the digraph.
1952      ///
1953      /// This function adds a red new node to the digraph.
1954      RedNode addRedNode() {
1955        return INVALID;
1956      }
1957
1958      /// \brief Add a new blue node to the digraph.
1959      ///
1960      /// This function adds a blue new node to the digraph.
1961      BlueNode addBlueNode() {
1962        return INVALID;
1963      }
1964
1965      /// \brief Add a new edge connecting the given two nodes.
1966      ///
1967      /// This function adds a new edge connecting the given two nodes
1968      /// of the graph. The first node has to be a red node, and the
1969      /// second one a blue node.
1970      Edge addEdge(const RedNode&, const BlueNode&) {
1971        return INVALID;
1972      }
1973      Edge addEdge(const BlueNode&, const RedNode&) {
1974        return INVALID;
1975      }
1976
1977      template <typename _BpGraph>
1978      struct Constraints {
1979        void constraints() {
1980          checkConcept<Base, _BpGraph>();
1981          typename _BpGraph::RedNode red_node;
1982          typename _BpGraph::BlueNode blue_node;
1983          red_node = bpgraph.addRedNode();
1984          blue_node = bpgraph.addBlueNode();
1985          typename _BpGraph::Edge edge;
1986          edge = bpgraph.addEdge(red_node, blue_node);
1987          edge = bpgraph.addEdge(blue_node, red_node);
1988        }
1989
1990        _BpGraph& bpgraph;
1991      };
1992    };
1993
1994    /// \brief Skeleton class for erasable directed graphs.
1995    ///
1996    /// This class describes the interface of erasable directed graphs.
1997    /// It extends \ref BaseDigraphComponent with functions for removing
1998    /// nodes and arcs from the digraph.
1999    /// This concept requires \ref AlterableDigraphComponent.
2000    template <typename BAS = BaseDigraphComponent>
2001    class ErasableDigraphComponent : public BAS {
2002    public:
2003
2004      typedef BAS Base;
2005      typedef typename Base::Node Node;
2006      typedef typename Base::Arc Arc;
2007
2008      /// \brief Erase a node from the digraph.
2009      ///
2010      /// This function erases the given node from the digraph and all arcs
2011      /// connected to the node.
2012      void erase(const Node&) {}
2013
2014      /// \brief Erase an arc from the digraph.
2015      ///
2016      /// This function erases the given arc from the digraph.
2017      void erase(const Arc&) {}
2018
2019      template <typename _Digraph>
2020      struct Constraints {
2021        void constraints() {
2022          checkConcept<Base, _Digraph>();
2023          const typename _Digraph::Node node(INVALID);
2024          digraph.erase(node);
2025          const typename _Digraph::Arc arc(INVALID);
2026          digraph.erase(arc);
2027        }
2028
2029        _Digraph& digraph;
2030        Constraints() {}
2031      };
2032    };
2033
2034    /// \brief Skeleton class for erasable undirected graphs.
2035    ///
2036    /// This class describes the interface of erasable undirected graphs.
2037    /// It extends \ref BaseGraphComponent with functions for removing
2038    /// nodes and edges from the graph.
2039    /// This concept requires \ref AlterableGraphComponent.
2040    template <typename BAS = BaseGraphComponent>
2041    class ErasableGraphComponent : public BAS {
2042    public:
2043
2044      typedef BAS Base;
2045      typedef typename Base::Node Node;
2046      typedef typename Base::Edge Edge;
2047
2048      /// \brief Erase a node from the graph.
2049      ///
2050      /// This function erases the given node from the graph and all edges
2051      /// connected to the node.
2052      void erase(const Node&) {}
2053
2054      /// \brief Erase an edge from the digraph.
2055      ///
2056      /// This function erases the given edge from the digraph.
2057      void erase(const Edge&) {}
2058
2059      template <typename _Graph>
2060      struct Constraints {
2061        void constraints() {
2062          checkConcept<Base, _Graph>();
2063          const typename _Graph::Node node(INVALID);
2064          graph.erase(node);
2065          const typename _Graph::Edge edge(INVALID);
2066          graph.erase(edge);
2067        }
2068
2069        _Graph& graph;
2070        Constraints() {}
2071      };
2072    };
2073
2074    /// \brief Skeleton class for erasable undirected graphs.
2075    ///
2076    /// This class describes the interface of erasable undirected
2077    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
2078    /// functions for removing nodes and edges from the graph. This
2079    /// concept requires \ref AlterableBpGraphComponent.
2080    template <typename BAS = BaseBpGraphComponent>
2081    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
2082
2083    /// \brief Skeleton class for clearable directed graphs.
2084    ///
2085    /// This class describes the interface of clearable directed graphs.
2086    /// It extends \ref BaseDigraphComponent with a function for clearing
2087    /// the digraph.
2088    /// This concept requires \ref AlterableDigraphComponent.
2089    template <typename BAS = BaseDigraphComponent>
2090    class ClearableDigraphComponent : public BAS {
2091    public:
2092
2093      typedef BAS Base;
2094
2095      /// \brief Erase all nodes and arcs from the digraph.
2096      ///
2097      /// This function erases all nodes and arcs from the digraph.
2098      void clear() {}
2099
2100      template <typename _Digraph>
2101      struct Constraints {
2102        void constraints() {
2103          checkConcept<Base, _Digraph>();
2104          digraph.clear();
2105        }
2106
2107        _Digraph& digraph;
2108        Constraints() {}
2109      };
2110    };
2111
2112    /// \brief Skeleton class for clearable undirected graphs.
2113    ///
2114    /// This class describes the interface of clearable undirected graphs.
2115    /// It extends \ref BaseGraphComponent with a function for clearing
2116    /// the graph.
2117    /// This concept requires \ref AlterableGraphComponent.
2118    template <typename BAS = BaseGraphComponent>
2119    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
2120
2121    /// \brief Skeleton class for clearable undirected biparite graphs.
2122    ///
2123    /// This class describes the interface of clearable undirected
2124    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
2125    /// function for clearing the graph.  This concept requires \ref
2126    /// AlterableBpGraphComponent.
2127    template <typename BAS = BaseBpGraphComponent>
2128    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
2129
2130  }
2131
2132}
2133
2134#endif
Note: See TracBrowser for help on using the repository browser.