COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/concepts/graph_components.h @ 976:426a704d7483

Last change on this file since 976:426a704d7483 was 976:426a704d7483, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge Intel C++ compatibility fixes

File size: 48.3 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[877]5 * Copyright (C) 2003-2010
[57]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
[786]21///\brief The concepts of graph components.
[57]22
[529]23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
[57]25
[220]26#include <lemon/core.h>
[57]27#include <lemon/concepts/maps.h>
28
29#include <lemon/bits/alteration_notifier.h>
30
31namespace lemon {
32  namespace concepts {
33
[579]34    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
[57]35    ///
[579]36    /// This class describes the concept of \c Node, \c Arc and \c Edge
37    /// subtypes of digraph and graph types.
[57]38    ///
39    /// \note This class is a template class so that we can use it to
[579]40    /// create graph skeleton classes. The reason for this is that \c Node
[877]41    /// and \c Arc (or \c Edge) types should \e not derive from the same
[579]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'.
[57]44#ifndef DOXYGEN
[559]45    template <char sel = '0'>
[57]46#endif
47    class GraphItem {
48    public:
49      /// \brief Default constructor.
[209]50      ///
[579]51      /// Default constructor.
[57]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() {}
[579]56
[57]57      /// \brief Copy constructor.
58      ///
59      /// Copy constructor.
[579]60      GraphItem(const GraphItem &) {}
61
62      /// \brief Constructor for conversion from \c INVALID.
[57]63      ///
[579]64      /// Constructor for conversion from \c INVALID.
65      /// It initializes the item to be invalid.
[57]66      /// \sa Invalid for more details.
67      GraphItem(Invalid) {}
[579]68
69      /// \brief Assignment operator.
[57]70      ///
[579]71      /// Assignment operator for the item.
72      GraphItem& operator=(const GraphItem&) { return *this; }
73
[666]74      /// \brief Assignment operator for INVALID.
75      ///
76      /// This operator makes the item invalid.
77      GraphItem& operator=(Invalid) { return *this; }
78
[57]79      /// \brief Equality operator.
80      ///
[579]81      /// Equality operator.
82      bool operator==(const GraphItem&) const { return false; }
83
[57]84      /// \brief Inequality operator.
85      ///
[579]86      /// Inequality operator.
87      bool operator!=(const GraphItem&) const { return false; }
88
89      /// \brief Ordering operator.
[57]90      ///
[579]91      /// This operator defines an ordering of the items.
[877]92      /// It makes possible to use graph item types as key types in
[579]93      /// associative containers (e.g. \c std::map).
[57]94      ///
[734]95      /// \note This operator only has to define some strict ordering of
[57]96      /// the items; this order has nothing to do with the iteration
97      /// ordering of the items.
[579]98      bool operator<(const GraphItem&) const { return false; }
[57]99
100      template<typename _GraphItem>
101      struct Constraints {
[209]102        void constraints() {
103          _GraphItem i1;
[666]104          i1=INVALID;
[209]105          _GraphItem i2 = i1;
106          _GraphItem i3 = INVALID;
[57]107
[209]108          i1 = i2 = i3;
109
110          bool b;
111          b = (ia == ib) && (ia != ib);
112          b = (ia == INVALID) && (ib != INVALID);
[57]113          b = (ia < ib);
[209]114        }
[57]115
[209]116        const _GraphItem &ia;
117        const _GraphItem &ib;
[975]118        Constraints() {}
[57]119      };
120    };
121
[579]122    /// \brief Base skeleton class for directed graphs.
[209]123    ///
[579]124    /// This class describes the base interface of directed graph types.
125    /// All digraph %concepts have to conform to this class.
[877]126    /// It just provides types for nodes and arcs and functions
[579]127    /// to get the source and the target nodes of arcs.
[57]128    class BaseDigraphComponent {
129    public:
130
131      typedef BaseDigraphComponent Digraph;
[209]132
[57]133      /// \brief Node class of the digraph.
134      ///
[579]135      /// This class represents the nodes of the digraph.
[57]136      typedef GraphItem<'n'> Node;
137
138      /// \brief Arc class of the digraph.
139      ///
[579]140      /// This class represents the arcs of the digraph.
141      typedef GraphItem<'a'> Arc;
142
143      /// \brief Return the source node of an arc.
[57]144      ///
[579]145      /// This function returns the source node of an arc.
146      Node source(const Arc&) const { return INVALID; }
[57]147
[579]148      /// \brief Return the target node of an arc.
[57]149      ///
[579]150      /// This function returns the target node of an arc.
151      Node target(const Arc&) const { return INVALID; }
152
153      /// \brief Return the opposite node on the given arc.
[57]154      ///
[579]155      /// This function returns the opposite node on the given arc.
[57]156      Node oppositeNode(const Node&, const Arc&) const {
157        return INVALID;
158      }
159
160      template <typename _Digraph>
161      struct Constraints {
[209]162        typedef typename _Digraph::Node Node;
163        typedef typename _Digraph::Arc Arc;
164
165        void constraints() {
166          checkConcept<GraphItem<'n'>, Node>();
167          checkConcept<GraphItem<'a'>, Arc>();
168          {
169            Node n;
170            Arc e(INVALID);
171            n = digraph.source(e);
172            n = digraph.target(e);
[57]173            n = digraph.oppositeNode(n, e);
[209]174          }
175        }
176
177        const _Digraph& digraph;
[975]178        Constraints() {}
[57]179      };
180    };
181
[579]182    /// \brief Base skeleton class for undirected graphs.
[209]183    ///
[579]184    /// This class describes the base interface of undirected graph types.
185    /// All graph %concepts have to conform to this class.
186    /// It extends the interface of \ref BaseDigraphComponent with an
187    /// \c Edge type and functions to get the end nodes of edges,
188    /// to convert from arcs to edges and to get both direction of edges.
[57]189    class BaseGraphComponent : public BaseDigraphComponent {
190    public:
[617]191
192      typedef BaseGraphComponent Graph;
193
[57]194      typedef BaseDigraphComponent::Node Node;
195      typedef BaseDigraphComponent::Arc Arc;
[579]196
197      /// \brief Undirected edge class of the graph.
[57]198      ///
[579]199      /// This class represents the undirected edges of the graph.
200      /// Undirected graphs can be used as directed graphs, each edge is
201      /// represented by two opposite directed arcs.
202      class Edge : public GraphItem<'e'> {
203        typedef GraphItem<'e'> Parent;
204
[617]205      public:
[57]206        /// \brief Default constructor.
[209]207        ///
[579]208        /// Default constructor.
[57]209        /// \warning The default constructor is not required to set
210        /// the item to some well-defined value. So you should consider it
211        /// as uninitialized.
212        Edge() {}
[579]213
[57]214        /// \brief Copy constructor.
215        ///
216        /// Copy constructor.
[579]217        Edge(const Edge &) : Parent() {}
218
219        /// \brief Constructor for conversion from \c INVALID.
[57]220        ///
[579]221        /// Constructor for conversion from \c INVALID.
222        /// It initializes the item to be invalid.
[57]223        /// \sa Invalid for more details.
224        Edge(Invalid) {}
[579]225
226        /// \brief Constructor for conversion from an arc.
[57]227        ///
[579]228        /// Constructor for conversion from an arc.
[57]229        /// Besides the core graph item functionality each arc should
[209]230        /// be convertible to the represented edge.
[57]231        Edge(const Arc&) {}
[666]232     };
[57]233
[579]234      /// \brief Return one end node of an edge.
235      ///
236      /// This function returns one end node of an edge.
237      Node u(const Edge&) const { return INVALID; }
238
239      /// \brief Return the other end node of an edge.
240      ///
241      /// This function returns the other end node of an edge.
242      Node v(const Edge&) const { return INVALID; }
243
244      /// \brief Return a directed arc related to an edge.
245      ///
246      /// This function returns a directed arc from its direction and the
247      /// represented edge.
248      Arc direct(const Edge&, bool) const { return INVALID; }
249
250      /// \brief Return a directed arc related to an edge.
251      ///
252      /// This function returns a directed arc from its source node and the
253      /// represented edge.
254      Arc direct(const Edge&, const Node&) const { return INVALID; }
255
256      /// \brief Return the direction of the arc.
[57]257      ///
258      /// Returns the direction of the arc. Each arc represents an
259      /// edge with a direction. It gives back the
260      /// direction.
261      bool direction(const Arc&) const { return true; }
262
[579]263      /// \brief Return the opposite arc.
[57]264      ///
[579]265      /// This function returns the opposite arc, i.e. the arc representing
266      /// the same edge and has opposite direction.
267      Arc oppositeArc(const Arc&) const { return INVALID; }
[209]268
[57]269      template <typename _Graph>
270      struct Constraints {
[209]271        typedef typename _Graph::Node Node;
272        typedef typename _Graph::Arc Arc;
273        typedef typename _Graph::Edge Edge;
274
275        void constraints() {
[57]276          checkConcept<BaseDigraphComponent, _Graph>();
[579]277          checkConcept<GraphItem<'e'>, Edge>();
[209]278          {
279            Node n;
280            Edge ue(INVALID);
[57]281            Arc e;
[209]282            n = graph.u(ue);
283            n = graph.v(ue);
[57]284            e = graph.direct(ue, true);
[579]285            e = graph.direct(ue, false);
[57]286            e = graph.direct(ue, n);
287            e = graph.oppositeArc(e);
288            ue = e;
289            bool d = graph.direction(e);
290            ignore_unused_variable_warning(d);
[209]291          }
292        }
293
294        const _Graph& graph;
[975]295      Constraints() {}
[57]296      };
297
298    };
299
[579]300    /// \brief Skeleton class for \e idable directed graphs.
[209]301    ///
[579]302    /// This class describes the interface of \e idable directed graphs.
303    /// It extends \ref BaseDigraphComponent with the core ID functions.
304    /// The ids of the items must be unique and immutable.
305    /// This concept is part of the Digraph concept.
[559]306    template <typename BAS = BaseDigraphComponent>
307    class IDableDigraphComponent : public BAS {
[57]308    public:
309
[559]310      typedef BAS Base;
[57]311      typedef typename Base::Node Node;
312      typedef typename Base::Arc Arc;
313
[579]314      /// \brief Return a unique integer id for the given node.
[57]315      ///
[579]316      /// This function returns a unique integer id for the given node.
317      int id(const Node&) const { return -1; }
318
319      /// \brief Return the node by its unique id.
[57]320      ///
[579]321      /// This function returns the node by its unique id.
322      /// If the digraph does not contain a node with the given id,
323      /// then the result of the function is undefined.
324      Node nodeFromId(int) const { return INVALID; }
[57]325
[579]326      /// \brief Return a unique integer id for the given arc.
[57]327      ///
[579]328      /// This function returns a unique integer id for the given arc.
329      int id(const Arc&) const { return -1; }
[57]330
[579]331      /// \brief Return the arc by its unique id.
[57]332      ///
[579]333      /// This function returns the arc by its unique id.
334      /// If the digraph does not contain an arc with the given id,
335      /// then the result of the function is undefined.
336      Arc arcFromId(int) const { return INVALID; }
337
338      /// \brief Return an integer greater or equal to the maximum
339      /// node id.
[57]340      ///
[579]341      /// This function returns an integer greater or equal to the
342      /// maximum node id.
343      int maxNodeId() const { return -1; }
[57]344
[579]345      /// \brief Return an integer greater or equal to the maximum
346      /// arc id.
[57]347      ///
[579]348      /// This function returns an integer greater or equal to the
349      /// maximum arc id.
350      int maxArcId() const { return -1; }
[57]351
352      template <typename _Digraph>
353      struct Constraints {
354
[209]355        void constraints() {
356          checkConcept<Base, _Digraph >();
357          typename _Digraph::Node node;
[666]358          node=INVALID;
[209]359          int nid = digraph.id(node);
360          nid = digraph.id(node);
361          node = digraph.nodeFromId(nid);
362          typename _Digraph::Arc arc;
[666]363          arc=INVALID;
[209]364          int eid = digraph.id(arc);
365          eid = digraph.id(arc);
366          arc = digraph.arcFromId(eid);
[57]367
[209]368          nid = digraph.maxNodeId();
369          ignore_unused_variable_warning(nid);
370          eid = digraph.maxArcId();
371          ignore_unused_variable_warning(eid);
372        }
[57]373
[209]374        const _Digraph& digraph;
[975]375        Constraints() {}
[57]376      };
377    };
378
[579]379    /// \brief Skeleton class for \e idable undirected graphs.
[209]380    ///
[579]381    /// This class describes the interface of \e idable undirected
382    /// graphs. It extends \ref IDableDigraphComponent with the core ID
383    /// functions of undirected graphs.
384    /// The ids of the items must be unique and immutable.
385    /// This concept is part of the Graph concept.
[559]386    template <typename BAS = BaseGraphComponent>
387    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
[57]388    public:
389
[559]390      typedef BAS Base;
[57]391      typedef typename Base::Edge Edge;
392
[559]393      using IDableDigraphComponent<Base>::id;
[57]394
[579]395      /// \brief Return a unique integer id for the given edge.
[57]396      ///
[579]397      /// This function returns a unique integer id for the given edge.
398      int id(const Edge&) const { return -1; }
399
400      /// \brief Return the edge by its unique id.
[57]401      ///
[579]402      /// This function returns the edge by its unique id.
403      /// If the graph does not contain an edge with the given id,
404      /// then the result of the function is undefined.
405      Edge edgeFromId(int) const { return INVALID; }
[57]406
[579]407      /// \brief Return an integer greater or equal to the maximum
408      /// edge id.
[57]409      ///
[579]410      /// This function returns an integer greater or equal to the
411      /// maximum edge id.
412      int maxEdgeId() const { return -1; }
[57]413
414      template <typename _Graph>
415      struct Constraints {
416
[209]417        void constraints() {
418          checkConcept<IDableDigraphComponent<Base>, _Graph >();
419          typename _Graph::Edge edge;
420          int ueid = graph.id(edge);
421          ueid = graph.id(edge);
422          edge = graph.edgeFromId(ueid);
423          ueid = graph.maxEdgeId();
424          ignore_unused_variable_warning(ueid);
425        }
[57]426
[209]427        const _Graph& graph;
[975]428        Constraints() {}
[57]429      };
430    };
431
[579]432    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
[57]433    ///
[877]434    /// This class describes the concept of \c NodeIt, \c ArcIt and
[579]435    /// \c EdgeIt subtypes of digraph and graph types.
[559]436    template <typename GR, typename Item>
437    class GraphItemIt : public Item {
[57]438    public:
439      /// \brief Default constructor.
440      ///
[579]441      /// Default constructor.
442      /// \warning The default constructor is not required to set
443      /// the iterator to some well-defined value. So you should consider it
444      /// as uninitialized.
[57]445      GraphItemIt() {}
[579]446
[57]447      /// \brief Copy constructor.
448      ///
449      /// Copy constructor.
[579]450      GraphItemIt(const GraphItemIt& it) : Item(it) {}
451
452      /// \brief Constructor that sets the iterator to the first item.
[57]453      ///
[579]454      /// Constructor that sets the iterator to the first item.
455      explicit GraphItemIt(const GR&) {}
456
457      /// \brief Constructor for conversion from \c INVALID.
[57]458      ///
[579]459      /// Constructor for conversion from \c INVALID.
460      /// It initializes the iterator to be invalid.
[57]461      /// \sa Invalid for more details.
462      GraphItemIt(Invalid) {}
[579]463
464      /// \brief Assignment operator.
[57]465      ///
[579]466      /// Assignment operator for the iterator.
467      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
468
469      /// \brief Increment the iterator.
[57]470      ///
[579]471      /// This operator increments the iterator, i.e. assigns it to the
472      /// next item.
[57]473      GraphItemIt& operator++() { return *this; }
[877]474
[57]475      /// \brief Equality operator
[209]476      ///
[579]477      /// Equality operator.
[57]478      /// Two iterators are equal if and only if they point to the
479      /// same object or both are invalid.
480      bool operator==(const GraphItemIt&) const { return true;}
[579]481
[57]482      /// \brief Inequality operator
[209]483      ///
[579]484      /// Inequality operator.
485      /// Two iterators are equal if and only if they point to the
486      /// same object or both are invalid.
[57]487      bool operator!=(const GraphItemIt&) const { return true;}
[209]488
[57]489      template<typename _GraphItemIt>
490      struct Constraints {
[209]491        void constraints() {
[579]492          checkConcept<GraphItem<>, _GraphItemIt>();
[209]493          _GraphItemIt it1(g);
494          _GraphItemIt it2;
[579]495          _GraphItemIt it3 = it1;
496          _GraphItemIt it4 = INVALID;
[57]497
[209]498          it2 = ++it1;
499          ++it2 = it1;
500          ++(++it1);
[57]501
[559]502          Item bi = it1;
[209]503          bi = it2;
504        }
[579]505        const GR& g;
[975]506        Constraints() {}
[57]507      };
508    };
509
[877]510    /// \brief Concept class for \c InArcIt, \c OutArcIt and
[579]511    /// \c IncEdgeIt types.
[57]512    ///
[877]513    /// This class describes the concept of \c InArcIt, \c OutArcIt
[579]514    /// and \c IncEdgeIt subtypes of digraph and graph types.
515    ///
516    /// \note Since these iterator classes do not inherit from the same
517    /// base class, there is an additional template parameter (selector)
[877]518    /// \c sel. For \c InArcIt you should instantiate it with character
[579]519    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
[559]520    template <typename GR,
521              typename Item = typename GR::Arc,
522              typename Base = typename GR::Node,
523              char sel = '0'>
524    class GraphIncIt : public Item {
[57]525    public:
526      /// \brief Default constructor.
527      ///
[579]528      /// Default constructor.
529      /// \warning The default constructor is not required to set
530      /// the iterator to some well-defined value. So you should consider it
531      /// as uninitialized.
[57]532      GraphIncIt() {}
[579]533
[57]534      /// \brief Copy constructor.
535      ///
536      /// Copy constructor.
[579]537      GraphIncIt(const GraphIncIt& it) : Item(it) {}
538
[877]539      /// \brief Constructor that sets the iterator to the first
[579]540      /// incoming or outgoing arc.
[57]541      ///
[877]542      /// Constructor that sets the iterator to the first arc
[579]543      /// incoming to or outgoing from the given node.
544      explicit GraphIncIt(const GR&, const Base&) {}
545
546      /// \brief Constructor for conversion from \c INVALID.
[57]547      ///
[579]548      /// Constructor for conversion from \c INVALID.
549      /// It initializes the iterator to be invalid.
[57]550      /// \sa Invalid for more details.
551      GraphIncIt(Invalid) {}
[579]552
553      /// \brief Assignment operator.
[57]554      ///
[579]555      /// Assignment operator for the iterator.
556      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
557
558      /// \brief Increment the iterator.
[57]559      ///
[579]560      /// This operator increments the iterator, i.e. assigns it to the
561      /// next arc incoming to or outgoing from the given node.
[57]562      GraphIncIt& operator++() { return *this; }
563
564      /// \brief Equality operator
565      ///
[579]566      /// Equality operator.
[57]567      /// Two iterators are equal if and only if they point to the
568      /// same object or both are invalid.
569      bool operator==(const GraphIncIt&) const { return true;}
570
571      /// \brief Inequality operator
572      ///
[579]573      /// Inequality operator.
574      /// Two iterators are equal if and only if they point to the
575      /// same object or both are invalid.
[57]576      bool operator!=(const GraphIncIt&) const { return true;}
577
578      template <typename _GraphIncIt>
579      struct Constraints {
[209]580        void constraints() {
[559]581          checkConcept<GraphItem<sel>, _GraphIncIt>();
[209]582          _GraphIncIt it1(graph, node);
583          _GraphIncIt it2;
[579]584          _GraphIncIt it3 = it1;
585          _GraphIncIt it4 = INVALID;
[57]586
[209]587          it2 = ++it1;
588          ++it2 = it1;
589          ++(++it1);
[559]590          Item e = it1;
[209]591          e = it2;
592        }
[579]593        const Base& node;
594        const GR& graph;
[975]595        Constraints() {}
[57]596      };
597    };
598
[579]599    /// \brief Skeleton class for iterable directed graphs.
[57]600    ///
[579]601    /// This class describes the interface of iterable directed
602    /// graphs. It extends \ref BaseDigraphComponent with the core
603    /// iterable interface.
[57]604    /// This concept is part of the Digraph concept.
[559]605    template <typename BAS = BaseDigraphComponent>
606    class IterableDigraphComponent : public BAS {
[57]607
608    public:
[209]609
[559]610      typedef BAS Base;
[57]611      typedef typename Base::Node Node;
612      typedef typename Base::Arc Arc;
613
614      typedef IterableDigraphComponent Digraph;
615
[584]616      /// \name Base Iteration
[209]617      ///
[579]618      /// This interface provides functions for iteration on digraph items.
[57]619      ///
[209]620      /// @{
[57]621
[579]622      /// \brief Return the first node.
[209]623      ///
[579]624      /// This function gives back the first node in the iteration order.
[57]625      void first(Node&) const {}
626
[579]627      /// \brief Return the next node.
[57]628      ///
[579]629      /// This function gives back the next node in the iteration order.
[57]630      void next(Node&) const {}
631
[579]632      /// \brief Return the first arc.
[57]633      ///
[579]634      /// This function gives back the first arc in the iteration order.
[57]635      void first(Arc&) const {}
636
[579]637      /// \brief Return the next arc.
[57]638      ///
[579]639      /// This function gives back the next arc in the iteration order.
[57]640      void next(Arc&) const {}
641
[579]642      /// \brief Return the first arc incomming to the given node.
[57]643      ///
[579]644      /// This function gives back the first arc incomming to the
645      /// given node.
[57]646      void firstIn(Arc&, const Node&) const {}
647
[579]648      /// \brief Return the next arc incomming to the given node.
[57]649      ///
[579]650      /// This function gives back the next arc incomming to the
651      /// given node.
[57]652      void nextIn(Arc&) const {}
653
[579]654      /// \brief Return the first arc outgoing form the given node.
655      ///
656      /// This function gives back the first arc outgoing form the
[57]657      /// given node.
658      void firstOut(Arc&, const Node&) const {}
659
[579]660      /// \brief Return the next arc outgoing form the given node.
[57]661      ///
[579]662      /// This function gives back the next arc outgoing form the
663      /// given node.
[57]664      void nextOut(Arc&) const {}
665
666      /// @}
667
[584]668      /// \name Class Based Iteration
[209]669      ///
[579]670      /// This interface provides iterator classes for digraph items.
[57]671      ///
672      /// @{
673
674      /// \brief This iterator goes through each node.
675      ///
676      /// This iterator goes through each node.
677      ///
678      typedef GraphItemIt<Digraph, Node> NodeIt;
679
[579]680      /// \brief This iterator goes through each arc.
[57]681      ///
[579]682      /// This iterator goes through each arc.
[57]683      ///
684      typedef GraphItemIt<Digraph, Arc> ArcIt;
685
686      /// \brief This iterator goes trough the incoming arcs of a node.
687      ///
[579]688      /// This iterator goes trough the \e incoming arcs of a certain node
[57]689      /// of a digraph.
690      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
691
692      /// \brief This iterator goes trough the outgoing arcs of a node.
693      ///
694      /// This iterator goes trough the \e outgoing arcs of a certain node
695      /// of a digraph.
696      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
697
698      /// \brief The base node of the iterator.
699      ///
[579]700      /// This function gives back the base node of the iterator.
701      /// It is always the target node of the pointed arc.
[57]702      Node baseNode(const InArcIt&) const { return INVALID; }
703
704      /// \brief The running node of the iterator.
705      ///
[579]706      /// This function gives back the running node of the iterator.
707      /// It is always the source node of the pointed arc.
[57]708      Node runningNode(const InArcIt&) const { return INVALID; }
709
710      /// \brief The base node of the iterator.
711      ///
[579]712      /// This function gives back the base node of the iterator.
713      /// It is always the source node of the pointed arc.
[57]714      Node baseNode(const OutArcIt&) const { return INVALID; }
715
716      /// \brief The running node of the iterator.
717      ///
[579]718      /// This function gives back the running node of the iterator.
719      /// It is always the target node of the pointed arc.
[57]720      Node runningNode(const OutArcIt&) const { return INVALID; }
721
722      /// @}
723
[209]724      template <typename _Digraph>
[57]725      struct Constraints {
[209]726        void constraints() {
727          checkConcept<Base, _Digraph>();
[57]728
729          {
[209]730            typename _Digraph::Node node(INVALID);
[57]731            typename _Digraph::Arc arc(INVALID);
732            {
733              digraph.first(node);
734              digraph.next(node);
735            }
736            {
737              digraph.first(arc);
738              digraph.next(arc);
739            }
740            {
741              digraph.firstIn(arc, node);
742              digraph.nextIn(arc);
743            }
744            {
745              digraph.firstOut(arc, node);
746              digraph.nextOut(arc);
747            }
[209]748          }
[57]749
750          {
751            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
752              typename _Digraph::ArcIt >();
753            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
754              typename _Digraph::NodeIt >();
[209]755            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
[57]756              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
[209]757            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
[57]758              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
759
760            typename _Digraph::Node n;
[579]761            const typename _Digraph::InArcIt iait(INVALID);
762            const typename _Digraph::OutArcIt oait(INVALID);
763            n = digraph.baseNode(iait);
764            n = digraph.runningNode(iait);
765            n = digraph.baseNode(oait);
766            n = digraph.runningNode(oait);
[57]767            ignore_unused_variable_warning(n);
768          }
769        }
[209]770
771        const _Digraph& digraph;
[975]772        Constraints() {}
[57]773      };
774    };
775
[579]776    /// \brief Skeleton class for iterable undirected graphs.
[57]777    ///
[579]778    /// This class describes the interface of iterable undirected
779    /// graphs. It extends \ref IterableDigraphComponent with the core
780    /// iterable interface of undirected graphs.
[57]781    /// This concept is part of the Graph concept.
[559]782    template <typename BAS = BaseGraphComponent>
783    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
[57]784    public:
785
[559]786      typedef BAS Base;
[57]787      typedef typename Base::Node Node;
788      typedef typename Base::Arc Arc;
789      typedef typename Base::Edge Edge;
790
[209]791
[57]792      typedef IterableGraphComponent Graph;
793
[584]794      /// \name Base Iteration
[209]795      ///
[579]796      /// This interface provides functions for iteration on edges.
797      ///
[209]798      /// @{
[57]799
[559]800      using IterableDigraphComponent<Base>::first;
801      using IterableDigraphComponent<Base>::next;
[57]802
[579]803      /// \brief Return the first edge.
[57]804      ///
[579]805      /// This function gives back the first edge in the iteration order.
[57]806      void first(Edge&) const {}
807
[579]808      /// \brief Return the next edge.
[57]809      ///
[579]810      /// This function gives back the next edge in the iteration order.
[57]811      void next(Edge&) const {}
812
[579]813      /// \brief Return the first edge incident to the given node.
814      ///
[877]815      /// This function gives back the first edge incident to the given
[579]816      /// node. The bool parameter gives back the direction for which the
[877]817      /// source node of the directed arc representing the edge is the
[57]818      /// given node.
819      void firstInc(Edge&, bool&, const Node&) const {}
820
821      /// \brief Gives back the next of the edges from the
822      /// given node.
823      ///
[877]824      /// This function gives back the next edge incident to the given
[579]825      /// node. The bool parameter should be used as \c firstInc() use it.
[57]826      void nextInc(Edge&, bool&) const {}
827
[559]828      using IterableDigraphComponent<Base>::baseNode;
829      using IterableDigraphComponent<Base>::runningNode;
[57]830
831      /// @}
832
[584]833      /// \name Class Based Iteration
[209]834      ///
[579]835      /// This interface provides iterator classes for edges.
[57]836      ///
837      /// @{
838
[579]839      /// \brief This iterator goes through each edge.
[57]840      ///
[579]841      /// This iterator goes through each edge.
[57]842      typedef GraphItemIt<Graph, Edge> EdgeIt;
[579]843
844      /// \brief This iterator goes trough the incident edges of a
[57]845      /// node.
846      ///
[579]847      /// This iterator goes trough the incident edges of a certain
[57]848      /// node of a graph.
[579]849      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
850
[57]851      /// \brief The base node of the iterator.
852      ///
[579]853      /// This function gives back the base node of the iterator.
[78]854      Node baseNode(const IncEdgeIt&) const { return INVALID; }
[57]855
856      /// \brief The running node of the iterator.
857      ///
[579]858      /// This function gives back the running node of the iterator.
[78]859      Node runningNode(const IncEdgeIt&) const { return INVALID; }
[57]860
861      /// @}
862
[209]863      template <typename _Graph>
[57]864      struct Constraints {
[209]865        void constraints() {
866          checkConcept<IterableDigraphComponent<Base>, _Graph>();
[57]867
868          {
869            typename _Graph::Node node(INVALID);
870            typename _Graph::Edge edge(INVALID);
871            bool dir;
872            {
873              graph.first(edge);
874              graph.next(edge);
875            }
876            {
877              graph.firstInc(edge, dir, node);
878              graph.nextInc(edge, dir);
879            }
[209]880
881          }
882
[57]883          {
884            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
885              typename _Graph::EdgeIt >();
[209]886            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
[579]887              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
[209]888
[57]889            typename _Graph::Node n;
[579]890            const typename _Graph::IncEdgeIt ieit(INVALID);
891            n = graph.baseNode(ieit);
892            n = graph.runningNode(ieit);
[57]893          }
894        }
[209]895
896        const _Graph& graph;
[975]897        Constraints() {}
[57]898      };
899    };
900
[579]901    /// \brief Skeleton class for alterable directed graphs.
[209]902    ///
[579]903    /// This class describes the interface of alterable directed
904    /// graphs. It extends \ref BaseDigraphComponent with the alteration
905    /// notifier interface. It implements
[57]906    /// an observer-notifier pattern for each digraph item. More
907    /// obsevers can be registered into the notifier and whenever an
[579]908    /// alteration occured in the digraph all the observers will be
[57]909    /// notified about it.
[559]910    template <typename BAS = BaseDigraphComponent>
911    class AlterableDigraphComponent : public BAS {
[57]912    public:
913
[559]914      typedef BAS Base;
[57]915      typedef typename Base::Node Node;
916      typedef typename Base::Arc Arc;
917
918
[579]919      /// Node alteration notifier class.
[209]920      typedef AlterationNotifier<AlterableDigraphComponent, Node>
[57]921      NodeNotifier;
[579]922      /// Arc alteration notifier class.
[209]923      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
[57]924      ArcNotifier;
[209]925
[579]926      /// \brief Return the node alteration notifier.
[57]927      ///
[579]928      /// This function gives back the node alteration notifier.
[57]929      NodeNotifier& notifier(Node) const {
[579]930         return NodeNotifier();
[57]931      }
[209]932
[579]933      /// \brief Return the arc alteration notifier.
[57]934      ///
[579]935      /// This function gives back the arc alteration notifier.
[57]936      ArcNotifier& notifier(Arc) const {
[209]937        return ArcNotifier();
[57]938      }
939
[209]940      template <typename _Digraph>
[57]941      struct Constraints {
[209]942        void constraints() {
943          checkConcept<Base, _Digraph>();
944          typename _Digraph::NodeNotifier& nn
[57]945            = digraph.notifier(typename _Digraph::Node());
946
[209]947          typename _Digraph::ArcNotifier& en
[57]948            = digraph.notifier(typename _Digraph::Arc());
[209]949
[57]950          ignore_unused_variable_warning(nn);
951          ignore_unused_variable_warning(en);
[209]952        }
953
954        const _Digraph& digraph;
[975]955        Constraints() {}
[57]956      };
957    };
958
[579]959    /// \brief Skeleton class for alterable undirected graphs.
[209]960    ///
[579]961    /// This class describes the interface of alterable undirected
962    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
963    /// notifier interface of undirected graphs. It implements
964    /// an observer-notifier pattern for the edges. More
[57]965    /// obsevers can be registered into the notifier and whenever an
[579]966    /// alteration occured in the graph all the observers will be
[57]967    /// notified about it.
[559]968    template <typename BAS = BaseGraphComponent>
969    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
[57]970    public:
971
[559]972      typedef BAS Base;
[57]973      typedef typename Base::Edge Edge;
974
975
[579]976      /// Edge alteration notifier class.
[209]977      typedef AlterationNotifier<AlterableGraphComponent, Edge>
[57]978      EdgeNotifier;
[209]979
[579]980      /// \brief Return the edge alteration notifier.
[57]981      ///
[579]982      /// This function gives back the edge alteration notifier.
[57]983      EdgeNotifier& notifier(Edge) const {
[209]984        return EdgeNotifier();
[57]985      }
986
[209]987      template <typename _Graph>
[57]988      struct Constraints {
[209]989        void constraints() {
[579]990          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
[209]991          typename _Graph::EdgeNotifier& uen
[57]992            = graph.notifier(typename _Graph::Edge());
993          ignore_unused_variable_warning(uen);
[209]994        }
995
996        const _Graph& graph;
[975]997        Constraints() {}
[57]998      };
999    };
1000
[579]1001    /// \brief Concept class for standard graph maps.
[209]1002    ///
[579]1003    /// This class describes the concept of standard graph maps, i.e.
[877]1004    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
[579]1005    /// graph types, which can be used for associating data to graph items.
[580]1006    /// The standard graph maps must conform to the ReferenceMap concept.
[559]1007    template <typename GR, typename K, typename V>
[580]1008    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
[617]1009      typedef ReferenceMap<K, V, V&, const V&> Parent;
1010
[57]1011    public:
1012
1013      /// The key type of the map.
[559]1014      typedef K Key;
[57]1015      /// The value type of the map.
[559]1016      typedef V Value;
[580]1017      /// The reference type of the map.
1018      typedef Value& Reference;
1019      /// The const reference type of the map.
1020      typedef const Value& ConstReference;
1021
1022      // The reference map tag.
1023      typedef True ReferenceMapTag;
[57]1024
1025      /// \brief Construct a new map.
1026      ///
1027      /// Construct a new map for the graph.
[617]1028      explicit GraphMap(const GR&) {}
[57]1029      /// \brief Construct a new map with default value.
1030      ///
[579]1031      /// Construct a new map for the graph and initalize the values.
[617]1032      GraphMap(const GR&, const Value&) {}
[263]1033
1034    private:
[57]1035      /// \brief Copy constructor.
1036      ///
1037      /// Copy Constructor.
1038      GraphMap(const GraphMap&) : Parent() {}
[209]1039
[579]1040      /// \brief Assignment operator.
[57]1041      ///
[579]1042      /// Assignment operator. It does not mofify the underlying graph,
[57]1043      /// it just iterates on the current item set and set the  map
[209]1044      /// with the value returned by the assigned map.
[57]1045      template <typename CMap>
[209]1046      GraphMap& operator=(const CMap&) {
[57]1047        checkConcept<ReadMap<Key, Value>, CMap>();
1048        return *this;
1049      }
1050
[263]1051    public:
[57]1052      template<typename _Map>
1053      struct Constraints {
[209]1054        void constraints() {
[580]1055          checkConcept
1056            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
[579]1057          _Map m1(g);
1058          _Map m2(g,t);
[877]1059
[579]1060          // Copy constructor
1061          // _Map m3(m);
[209]1062
[579]1063          // Assignment operator
[263]1064          // ReadMap<Key, Value> cmap;
[579]1065          // m3 = cmap;
[57]1066
[579]1067          ignore_unused_variable_warning(m1);
1068          ignore_unused_variable_warning(m2);
1069          // ignore_unused_variable_warning(m3);
[209]1070        }
[57]1071
[579]1072        const _Map &m;
[617]1073        const GR &g;
[209]1074        const typename GraphMap::Value &t;
[975]1075        Constraints() {}
[57]1076      };
1077
1078    };
1079
[579]1080    /// \brief Skeleton class for mappable directed graphs.
[57]1081    ///
[579]1082    /// This class describes the interface of mappable directed graphs.
[877]1083    /// It extends \ref BaseDigraphComponent with the standard digraph
[579]1084    /// map classes, namely \c NodeMap and \c ArcMap.
[57]1085    /// This concept is part of the Digraph concept.
[559]1086    template <typename BAS = BaseDigraphComponent>
1087    class MappableDigraphComponent : public BAS  {
[57]1088    public:
1089
[559]1090      typedef BAS Base;
[57]1091      typedef typename Base::Node Node;
1092      typedef typename Base::Arc Arc;
1093
1094      typedef MappableDigraphComponent Digraph;
1095
[579]1096      /// \brief Standard graph map for the nodes.
[57]1097      ///
[579]1098      /// Standard graph map for the nodes.
[580]1099      /// It conforms to the ReferenceMap concept.
[559]1100      template <typename V>
[579]1101      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
[559]1102        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
[57]1103
[617]1104      public:
[209]1105        /// \brief Construct a new map.
1106        ///
1107        /// Construct a new map for the digraph.
1108        explicit NodeMap(const MappableDigraphComponent& digraph)
[57]1109          : Parent(digraph) {}
1110
[209]1111        /// \brief Construct a new map with default value.
1112        ///
[579]1113        /// Construct a new map for the digraph and initalize the values.
[559]1114        NodeMap(const MappableDigraphComponent& digraph, const V& value)
[57]1115          : Parent(digraph, value) {}
1116
[263]1117      private:
[209]1118        /// \brief Copy constructor.
1119        ///
1120        /// Copy Constructor.
1121        NodeMap(const NodeMap& nm) : Parent(nm) {}
[57]1122
[579]1123        /// \brief Assignment operator.
[209]1124        ///
[579]1125        /// Assignment operator.
[57]1126        template <typename CMap>
[209]1127        NodeMap& operator=(const CMap&) {
[559]1128          checkConcept<ReadMap<Node, V>, CMap>();
[57]1129          return *this;
1130        }
1131
1132      };
1133
[579]1134      /// \brief Standard graph map for the arcs.
[57]1135      ///
[579]1136      /// Standard graph map for the arcs.
[580]1137      /// It conforms to the ReferenceMap concept.
[559]1138      template <typename V>
[579]1139      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
[559]1140        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
[57]1141
[617]1142      public:
[209]1143        /// \brief Construct a new map.
1144        ///
1145        /// Construct a new map for the digraph.
1146        explicit ArcMap(const MappableDigraphComponent& digraph)
[57]1147          : Parent(digraph) {}
1148
[209]1149        /// \brief Construct a new map with default value.
1150        ///
[579]1151        /// Construct a new map for the digraph and initalize the values.
[559]1152        ArcMap(const MappableDigraphComponent& digraph, const V& value)
[57]1153          : Parent(digraph, value) {}
1154
[263]1155      private:
[209]1156        /// \brief Copy constructor.
1157        ///
1158        /// Copy Constructor.
1159        ArcMap(const ArcMap& nm) : Parent(nm) {}
[57]1160
[579]1161        /// \brief Assignment operator.
[209]1162        ///
[579]1163        /// Assignment operator.
[57]1164        template <typename CMap>
[209]1165        ArcMap& operator=(const CMap&) {
[559]1166          checkConcept<ReadMap<Arc, V>, CMap>();
[57]1167          return *this;
1168        }
1169
1170      };
1171
1172
1173      template <typename _Digraph>
1174      struct Constraints {
1175
[209]1176        struct Dummy {
1177          int value;
1178          Dummy() : value(0) {}
1179          Dummy(int _v) : value(_v) {}
1180        };
[57]1181
[209]1182        void constraints() {
1183          checkConcept<Base, _Digraph>();
1184          { // int map test
1185            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1186            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1187              IntNodeMap >();
1188          } { // bool map test
1189            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1190            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1191              BoolNodeMap >();
1192          } { // Dummy map test
1193            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1194            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1195              DummyNodeMap >();
1196          }
[57]1197
[209]1198          { // int map test
1199            typedef typename _Digraph::template ArcMap<int> IntArcMap;
1200            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1201              IntArcMap >();
1202          } { // bool map test
1203            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1204            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1205              BoolArcMap >();
1206          } { // Dummy map test
1207            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1208            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1209              DummyArcMap >();
1210          }
1211        }
[57]1212
[579]1213        const _Digraph& digraph;
[975]1214        Constraints() {}
[57]1215      };
1216    };
1217
[579]1218    /// \brief Skeleton class for mappable undirected graphs.
[57]1219    ///
[579]1220    /// This class describes the interface of mappable undirected graphs.
[877]1221    /// It extends \ref MappableDigraphComponent with the standard graph
[579]1222    /// map class for edges (\c EdgeMap).
[57]1223    /// This concept is part of the Graph concept.
[559]1224    template <typename BAS = BaseGraphComponent>
1225    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
[57]1226    public:
1227
[559]1228      typedef BAS Base;
[57]1229      typedef typename Base::Edge Edge;
1230
1231      typedef MappableGraphComponent Graph;
1232
[579]1233      /// \brief Standard graph map for the edges.
[57]1234      ///
[579]1235      /// Standard graph map for the edges.
[580]1236      /// It conforms to the ReferenceMap concept.
[559]1237      template <typename V>
[579]1238      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
[559]1239        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
[57]1240
[617]1241      public:
[209]1242        /// \brief Construct a new map.
1243        ///
1244        /// Construct a new map for the graph.
1245        explicit EdgeMap(const MappableGraphComponent& graph)
[57]1246          : Parent(graph) {}
1247
[209]1248        /// \brief Construct a new map with default value.
1249        ///
[579]1250        /// Construct a new map for the graph and initalize the values.
[559]1251        EdgeMap(const MappableGraphComponent& graph, const V& value)
[57]1252          : Parent(graph, value) {}
1253
[263]1254      private:
[209]1255        /// \brief Copy constructor.
1256        ///
1257        /// Copy Constructor.
1258        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
[57]1259
[579]1260        /// \brief Assignment operator.
[209]1261        ///
[579]1262        /// Assignment operator.
[57]1263        template <typename CMap>
[209]1264        EdgeMap& operator=(const CMap&) {
[559]1265          checkConcept<ReadMap<Edge, V>, CMap>();
[57]1266          return *this;
1267        }
1268
1269      };
1270
1271
1272      template <typename _Graph>
1273      struct Constraints {
1274
[209]1275        struct Dummy {
1276          int value;
1277          Dummy() : value(0) {}
1278          Dummy(int _v) : value(_v) {}
1279        };
[57]1280
[209]1281        void constraints() {
[579]1282          checkConcept<MappableDigraphComponent<Base>, _Graph>();
[57]1283
[209]1284          { // int map test
1285            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1286            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1287              IntEdgeMap >();
1288          } { // bool map test
1289            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1290            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1291              BoolEdgeMap >();
1292          } { // Dummy map test
1293            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1294            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1295              DummyEdgeMap >();
1296          }
1297        }
[57]1298
[579]1299        const _Graph& graph;
[975]1300        Constraints() {}
[57]1301      };
1302    };
1303
[579]1304    /// \brief Skeleton class for extendable directed graphs.
[57]1305    ///
[579]1306    /// This class describes the interface of extendable directed graphs.
[877]1307    /// It extends \ref BaseDigraphComponent with functions for adding
[579]1308    /// nodes and arcs to the digraph.
1309    /// This concept requires \ref AlterableDigraphComponent.
[559]1310    template <typename BAS = BaseDigraphComponent>
1311    class ExtendableDigraphComponent : public BAS {
[57]1312    public:
[559]1313      typedef BAS Base;
[57]1314
[559]1315      typedef typename Base::Node Node;
1316      typedef typename Base::Arc Arc;
[57]1317
[579]1318      /// \brief Add a new node to the digraph.
[57]1319      ///
[579]1320      /// This function adds a new node to the digraph.
[57]1321      Node addNode() {
[209]1322        return INVALID;
[57]1323      }
[209]1324
[579]1325      /// \brief Add a new arc connecting the given two nodes.
[57]1326      ///
[579]1327      /// This function adds a new arc connecting the given two nodes
1328      /// of the digraph.
[57]1329      Arc addArc(const Node&, const Node&) {
[209]1330        return INVALID;
[57]1331      }
1332
1333      template <typename _Digraph>
1334      struct Constraints {
[209]1335        void constraints() {
[57]1336          checkConcept<Base, _Digraph>();
[209]1337          typename _Digraph::Node node_a, node_b;
1338          node_a = digraph.addNode();
1339          node_b = digraph.addNode();
1340          typename _Digraph::Arc arc;
1341          arc = digraph.addArc(node_a, node_b);
1342        }
[57]1343
[209]1344        _Digraph& digraph;
[975]1345        Constraints() {}
[57]1346      };
1347    };
1348
[579]1349    /// \brief Skeleton class for extendable undirected graphs.
[57]1350    ///
[579]1351    /// This class describes the interface of extendable undirected graphs.
[877]1352    /// It extends \ref BaseGraphComponent with functions for adding
[579]1353    /// nodes and edges to the graph.
1354    /// This concept requires \ref AlterableGraphComponent.
[559]1355    template <typename BAS = BaseGraphComponent>
1356    class ExtendableGraphComponent : public BAS {
[57]1357    public:
1358
[559]1359      typedef BAS Base;
1360      typedef typename Base::Node Node;
1361      typedef typename Base::Edge Edge;
[57]1362
[579]1363      /// \brief Add a new node to the digraph.
[57]1364      ///
[579]1365      /// This function adds a new node to the digraph.
[57]1366      Node addNode() {
[209]1367        return INVALID;
[57]1368      }
[209]1369
[579]1370      /// \brief Add a new edge connecting the given two nodes.
[57]1371      ///
[579]1372      /// This function adds a new edge connecting the given two nodes
1373      /// of the graph.
1374      Edge addEdge(const Node&, const Node&) {
[209]1375        return INVALID;
[57]1376      }
1377
1378      template <typename _Graph>
1379      struct Constraints {
[209]1380        void constraints() {
1381          checkConcept<Base, _Graph>();
1382          typename _Graph::Node node_a, node_b;
1383          node_a = graph.addNode();
1384          node_b = graph.addNode();
1385          typename _Graph::Edge edge;
1386          edge = graph.addEdge(node_a, node_b);
1387        }
[57]1388
[209]1389        _Graph& graph;
[975]1390        Constraints() {}
[57]1391      };
1392    };
1393
[579]1394    /// \brief Skeleton class for erasable directed graphs.
[209]1395    ///
[579]1396    /// This class describes the interface of erasable directed graphs.
[877]1397    /// It extends \ref BaseDigraphComponent with functions for removing
[579]1398    /// nodes and arcs from the digraph.
1399    /// This concept requires \ref AlterableDigraphComponent.
[559]1400    template <typename BAS = BaseDigraphComponent>
1401    class ErasableDigraphComponent : public BAS {
[57]1402    public:
1403
[559]1404      typedef BAS Base;
[57]1405      typedef typename Base::Node Node;
1406      typedef typename Base::Arc Arc;
1407
1408      /// \brief Erase a node from the digraph.
1409      ///
[877]1410      /// This function erases the given node from the digraph and all arcs
[579]1411      /// connected to the node.
[209]1412      void erase(const Node&) {}
[57]1413
1414      /// \brief Erase an arc from the digraph.
1415      ///
[579]1416      /// This function erases the given arc from the digraph.
[57]1417      void erase(const Arc&) {}
1418
1419      template <typename _Digraph>
1420      struct Constraints {
[209]1421        void constraints() {
[57]1422          checkConcept<Base, _Digraph>();
[579]1423          const typename _Digraph::Node node(INVALID);
[209]1424          digraph.erase(node);
[579]1425          const typename _Digraph::Arc arc(INVALID);
[209]1426          digraph.erase(arc);
1427        }
[57]1428
[209]1429        _Digraph& digraph;
[975]1430        Constraints() {}
[57]1431      };
1432    };
1433
[579]1434    /// \brief Skeleton class for erasable undirected graphs.
[209]1435    ///
[579]1436    /// This class describes the interface of erasable undirected graphs.
[877]1437    /// It extends \ref BaseGraphComponent with functions for removing
[579]1438    /// nodes and edges from the graph.
1439    /// This concept requires \ref AlterableGraphComponent.
[559]1440    template <typename BAS = BaseGraphComponent>
1441    class ErasableGraphComponent : public BAS {
[57]1442    public:
1443
[559]1444      typedef BAS Base;
[57]1445      typedef typename Base::Node Node;
1446      typedef typename Base::Edge Edge;
1447
1448      /// \brief Erase a node from the graph.
1449      ///
[579]1450      /// This function erases the given node from the graph and all edges
1451      /// connected to the node.
[209]1452      void erase(const Node&) {}
[57]1453
[579]1454      /// \brief Erase an edge from the digraph.
[57]1455      ///
[579]1456      /// This function erases the given edge from the digraph.
[57]1457      void erase(const Edge&) {}
1458
1459      template <typename _Graph>
1460      struct Constraints {
[209]1461        void constraints() {
[57]1462          checkConcept<Base, _Graph>();
[579]1463          const typename _Graph::Node node(INVALID);
[209]1464          graph.erase(node);
[579]1465          const typename _Graph::Edge edge(INVALID);
[209]1466          graph.erase(edge);
1467        }
[57]1468
[209]1469        _Graph& graph;
[975]1470        Constraints() {}
[57]1471      };
1472    };
1473
[579]1474    /// \brief Skeleton class for clearable directed graphs.
[57]1475    ///
[579]1476    /// This class describes the interface of clearable directed graphs.
1477    /// It extends \ref BaseDigraphComponent with a function for clearing
1478    /// the digraph.
1479    /// This concept requires \ref AlterableDigraphComponent.
[559]1480    template <typename BAS = BaseDigraphComponent>
1481    class ClearableDigraphComponent : public BAS {
[57]1482    public:
1483
[559]1484      typedef BAS Base;
[57]1485
1486      /// \brief Erase all nodes and arcs from the digraph.
1487      ///
[579]1488      /// This function erases all nodes and arcs from the digraph.
[209]1489      void clear() {}
[57]1490
1491      template <typename _Digraph>
1492      struct Constraints {
[209]1493        void constraints() {
[57]1494          checkConcept<Base, _Digraph>();
[209]1495          digraph.clear();
1496        }
[57]1497
[579]1498        _Digraph& digraph;
[975]1499        Constraints() {}
[57]1500      };
1501    };
1502
[579]1503    /// \brief Skeleton class for clearable undirected graphs.
[57]1504    ///
[579]1505    /// This class describes the interface of clearable undirected graphs.
1506    /// It extends \ref BaseGraphComponent with a function for clearing
1507    /// the graph.
1508    /// This concept requires \ref AlterableGraphComponent.
[559]1509    template <typename BAS = BaseGraphComponent>
1510    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
[57]1511    public:
1512
[559]1513      typedef BAS Base;
[57]1514
[579]1515      /// \brief Erase all nodes and edges from the graph.
1516      ///
1517      /// This function erases all nodes and edges from the graph.
1518      void clear() {}
1519
[57]1520      template <typename _Graph>
1521      struct Constraints {
[209]1522        void constraints() {
[579]1523          checkConcept<Base, _Graph>();
1524          graph.clear();
[209]1525        }
[57]1526
[579]1527        _Graph& graph;
[975]1528        Constraints() {}
[57]1529      };
1530    };
1531
1532  }
1533
1534}
1535
1536#endif
Note: See TracBrowser for help on using the repository browser.