COIN-OR::LEMON - Graph Library

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

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

Add bipartite graph concepts (#69)

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