lemon/concepts/graph_components.h
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 06 May 2012 17:18:39 +0200
changeset 989 38e1d4383262
parent 877 141f9c0db4a3
parent 975 b873350e6258
child 1000 404b98971e1f
permissions -rw-r--r--
Merge bugfix #441
     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 
    31 namespace 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           b = (ia == ib) && (ia != ib);
   112           b = (ia == INVALID) && (ib != INVALID);
   113           b = (ia < ib);
   114         }
   115 
   116         const _GraphItem &ia;
   117         const _GraphItem &ib;
   118         Constraints() {}
   119       };
   120     };
   121 
   122     /// \brief Base skeleton class for directed graphs.
   123     ///
   124     /// This class describes the base interface of directed graph types.
   125     /// All digraph %concepts have to conform to this class.
   126     /// It just provides types for nodes and arcs and functions
   127     /// to get the source and the target nodes of arcs.
   128     class BaseDigraphComponent {
   129     public:
   130 
   131       typedef BaseDigraphComponent Digraph;
   132 
   133       /// \brief Node class of the digraph.
   134       ///
   135       /// This class represents the nodes of the digraph.
   136       typedef GraphItem<'n'> Node;
   137 
   138       /// \brief Arc class of the digraph.
   139       ///
   140       /// This class represents the arcs of the digraph.
   141       typedef GraphItem<'a'> Arc;
   142 
   143       /// \brief Return the source node of an arc.
   144       ///
   145       /// This function returns the source node of an arc.
   146       Node source(const Arc&) const { return INVALID; }
   147 
   148       /// \brief Return the target node of an arc.
   149       ///
   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.
   154       ///
   155       /// This function returns the opposite node on the given arc.
   156       Node oppositeNode(const Node&, const Arc&) const {
   157         return INVALID;
   158       }
   159 
   160       template <typename _Digraph>
   161       struct Constraints {
   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);
   173             n = digraph.oppositeNode(n, e);
   174           }
   175         }
   176 
   177         const _Digraph& digraph;
   178         Constraints() {}
   179       };
   180     };
   181 
   182     /// \brief Base skeleton class for undirected graphs.
   183     ///
   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.
   189     class BaseGraphComponent : public BaseDigraphComponent {
   190     public:
   191 
   192       typedef BaseGraphComponent Graph;
   193 
   194       typedef BaseDigraphComponent::Node Node;
   195       typedef BaseDigraphComponent::Arc Arc;
   196 
   197       /// \brief Undirected edge class of the graph.
   198       ///
   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 
   205       public:
   206         /// \brief Default constructor.
   207         ///
   208         /// Default constructor.
   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() {}
   213 
   214         /// \brief Copy constructor.
   215         ///
   216         /// Copy constructor.
   217         Edge(const Edge &) : Parent() {}
   218 
   219         /// \brief Constructor for conversion from \c INVALID.
   220         ///
   221         /// Constructor for conversion from \c INVALID.
   222         /// It initializes the item to be invalid.
   223         /// \sa Invalid for more details.
   224         Edge(Invalid) {}
   225 
   226         /// \brief Constructor for conversion from an arc.
   227         ///
   228         /// Constructor for conversion from an arc.
   229         /// Besides the core graph item functionality each arc should
   230         /// be convertible to the represented edge.
   231         Edge(const Arc&) {}
   232      };
   233 
   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.
   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 
   263       /// \brief Return the opposite arc.
   264       ///
   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; }
   268 
   269       template <typename _Graph>
   270       struct Constraints {
   271         typedef typename _Graph::Node Node;
   272         typedef typename _Graph::Arc Arc;
   273         typedef typename _Graph::Edge Edge;
   274 
   275         void constraints() {
   276           checkConcept<BaseDigraphComponent, _Graph>();
   277           checkConcept<GraphItem<'e'>, Edge>();
   278           {
   279             Node n;
   280             Edge ue(INVALID);
   281             Arc e;
   282             n = graph.u(ue);
   283             n = graph.v(ue);
   284             e = graph.direct(ue, true);
   285             e = graph.direct(ue, false);
   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);
   291           }
   292         }
   293 
   294         const _Graph& graph;
   295       Constraints() {}
   296       };
   297 
   298     };
   299 
   300     /// \brief Skeleton class for \e idable directed graphs.
   301     ///
   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.
   306     template <typename BAS = BaseDigraphComponent>
   307     class IDableDigraphComponent : public BAS {
   308     public:
   309 
   310       typedef BAS Base;
   311       typedef typename Base::Node Node;
   312       typedef typename Base::Arc Arc;
   313 
   314       /// \brief Return a unique integer id for the given node.
   315       ///
   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.
   320       ///
   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; }
   325 
   326       /// \brief Return a unique integer id for the given arc.
   327       ///
   328       /// This function returns a unique integer id for the given arc.
   329       int id(const Arc&) const { return -1; }
   330 
   331       /// \brief Return the arc by its unique id.
   332       ///
   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.
   340       ///
   341       /// This function returns an integer greater or equal to the
   342       /// maximum node id.
   343       int maxNodeId() const { return -1; }
   344 
   345       /// \brief Return an integer greater or equal to the maximum
   346       /// arc id.
   347       ///
   348       /// This function returns an integer greater or equal to the
   349       /// maximum arc id.
   350       int maxArcId() const { return -1; }
   351 
   352       template <typename _Digraph>
   353       struct Constraints {
   354 
   355         void constraints() {
   356           checkConcept<Base, _Digraph >();
   357           typename _Digraph::Node node;
   358           node=INVALID;
   359           int nid = digraph.id(node);
   360           nid = digraph.id(node);
   361           node = digraph.nodeFromId(nid);
   362           typename _Digraph::Arc arc;
   363           arc=INVALID;
   364           int eid = digraph.id(arc);
   365           eid = digraph.id(arc);
   366           arc = digraph.arcFromId(eid);
   367 
   368           nid = digraph.maxNodeId();
   369           ignore_unused_variable_warning(nid);
   370           eid = digraph.maxArcId();
   371           ignore_unused_variable_warning(eid);
   372         }
   373 
   374         const _Digraph& digraph;
   375         Constraints() {}
   376       };
   377     };
   378 
   379     /// \brief Skeleton class for \e idable undirected graphs.
   380     ///
   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.
   386     template <typename BAS = BaseGraphComponent>
   387     class IDableGraphComponent : public IDableDigraphComponent<BAS> {
   388     public:
   389 
   390       typedef BAS Base;
   391       typedef typename Base::Edge Edge;
   392 
   393       using IDableDigraphComponent<Base>::id;
   394 
   395       /// \brief Return a unique integer id for the given edge.
   396       ///
   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.
   401       ///
   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; }
   406 
   407       /// \brief Return an integer greater or equal to the maximum
   408       /// edge id.
   409       ///
   410       /// This function returns an integer greater or equal to the
   411       /// maximum edge id.
   412       int maxEdgeId() const { return -1; }
   413 
   414       template <typename _Graph>
   415       struct Constraints {
   416 
   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         }
   426 
   427         const _Graph& graph;
   428         Constraints() {}
   429       };
   430     };
   431 
   432     /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
   433     ///
   434     /// This class describes the concept of \c NodeIt, \c ArcIt and
   435     /// \c EdgeIt subtypes of digraph and graph types.
   436     template <typename GR, typename Item>
   437     class GraphItemIt : public Item {
   438     public:
   439       /// \brief Default constructor.
   440       ///
   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.
   445       GraphItemIt() {}
   446 
   447       /// \brief Copy constructor.
   448       ///
   449       /// Copy constructor.
   450       GraphItemIt(const GraphItemIt& it) : Item(it) {}
   451 
   452       /// \brief Constructor that sets the iterator to the first item.
   453       ///
   454       /// Constructor that sets the iterator to the first item.
   455       explicit GraphItemIt(const GR&) {}
   456 
   457       /// \brief Constructor for conversion from \c INVALID.
   458       ///
   459       /// Constructor for conversion from \c INVALID.
   460       /// It initializes the iterator to be invalid.
   461       /// \sa Invalid for more details.
   462       GraphItemIt(Invalid) {}
   463 
   464       /// \brief Assignment operator.
   465       ///
   466       /// Assignment operator for the iterator.
   467       GraphItemIt& operator=(const GraphItemIt&) { return *this; }
   468 
   469       /// \brief Increment the iterator.
   470       ///
   471       /// This operator increments the iterator, i.e. assigns it to the
   472       /// next item.
   473       GraphItemIt& operator++() { return *this; }
   474 
   475       /// \brief Equality operator
   476       ///
   477       /// Equality operator.
   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;}
   481 
   482       /// \brief Inequality operator
   483       ///
   484       /// Inequality operator.
   485       /// Two iterators are equal if and only if they point to the
   486       /// same object or both are invalid.
   487       bool operator!=(const GraphItemIt&) const { return true;}
   488 
   489       template<typename _GraphItemIt>
   490       struct Constraints {
   491         void constraints() {
   492           checkConcept<GraphItem<>, _GraphItemIt>();
   493           _GraphItemIt it1(g);
   494           _GraphItemIt it2;
   495           _GraphItemIt it3 = it1;
   496           _GraphItemIt it4 = INVALID;
   497 
   498           it2 = ++it1;
   499           ++it2 = it1;
   500           ++(++it1);
   501 
   502           Item bi = it1;
   503           bi = it2;
   504         }
   505         const GR& g;
   506         Constraints() {}
   507       };
   508     };
   509 
   510     /// \brief Concept class for \c InArcIt, \c OutArcIt and
   511     /// \c IncEdgeIt types.
   512     ///
   513     /// This class describes the concept of \c InArcIt, \c OutArcIt
   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)
   518     /// \c sel. For \c InArcIt you should instantiate it with character
   519     /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
   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 {
   525     public:
   526       /// \brief Default constructor.
   527       ///
   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.
   532       GraphIncIt() {}
   533 
   534       /// \brief Copy constructor.
   535       ///
   536       /// Copy constructor.
   537       GraphIncIt(const GraphIncIt& it) : Item(it) {}
   538 
   539       /// \brief Constructor that sets the iterator to the first
   540       /// incoming or outgoing arc.
   541       ///
   542       /// Constructor that sets the iterator to the first arc
   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.
   547       ///
   548       /// Constructor for conversion from \c INVALID.
   549       /// It initializes the iterator to be invalid.
   550       /// \sa Invalid for more details.
   551       GraphIncIt(Invalid) {}
   552 
   553       /// \brief Assignment operator.
   554       ///
   555       /// Assignment operator for the iterator.
   556       GraphIncIt& operator=(const GraphIncIt&) { return *this; }
   557 
   558       /// \brief Increment the iterator.
   559       ///
   560       /// This operator increments the iterator, i.e. assigns it to the
   561       /// next arc incoming to or outgoing from the given node.
   562       GraphIncIt& operator++() { return *this; }
   563 
   564       /// \brief Equality operator
   565       ///
   566       /// Equality operator.
   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       ///
   573       /// Inequality operator.
   574       /// Two iterators are equal if and only if they point to the
   575       /// same object or both are invalid.
   576       bool operator!=(const GraphIncIt&) const { return true;}
   577 
   578       template <typename _GraphIncIt>
   579       struct Constraints {
   580         void constraints() {
   581           checkConcept<GraphItem<sel>, _GraphIncIt>();
   582           _GraphIncIt it1(graph, node);
   583           _GraphIncIt it2;
   584           _GraphIncIt it3 = it1;
   585           _GraphIncIt it4 = INVALID;
   586 
   587           it2 = ++it1;
   588           ++it2 = it1;
   589           ++(++it1);
   590           Item e = it1;
   591           e = it2;
   592         }
   593         const Base& node;
   594         const GR& graph;
   595         Constraints() {}
   596       };
   597     };
   598 
   599     /// \brief Skeleton class for iterable directed graphs.
   600     ///
   601     /// This class describes the interface of iterable directed
   602     /// graphs. It extends \ref BaseDigraphComponent with the core
   603     /// iterable interface.
   604     /// This concept is part of the Digraph concept.
   605     template <typename BAS = BaseDigraphComponent>
   606     class IterableDigraphComponent : public BAS {
   607 
   608     public:
   609 
   610       typedef BAS Base;
   611       typedef typename Base::Node Node;
   612       typedef typename Base::Arc Arc;
   613 
   614       typedef IterableDigraphComponent Digraph;
   615 
   616       /// \name Base Iteration
   617       ///
   618       /// This interface provides functions for iteration on digraph items.
   619       ///
   620       /// @{
   621 
   622       /// \brief Return the first node.
   623       ///
   624       /// This function gives back the first node in the iteration order.
   625       void first(Node&) const {}
   626 
   627       /// \brief Return the next node.
   628       ///
   629       /// This function gives back the next node in the iteration order.
   630       void next(Node&) const {}
   631 
   632       /// \brief Return the first arc.
   633       ///
   634       /// This function gives back the first arc in the iteration order.
   635       void first(Arc&) const {}
   636 
   637       /// \brief Return the next arc.
   638       ///
   639       /// This function gives back the next arc in the iteration order.
   640       void next(Arc&) const {}
   641 
   642       /// \brief Return the first arc incomming to the given node.
   643       ///
   644       /// This function gives back the first arc incomming to the
   645       /// given node.
   646       void firstIn(Arc&, const Node&) const {}
   647 
   648       /// \brief Return the next arc incomming to the given node.
   649       ///
   650       /// This function gives back the next arc incomming to the
   651       /// given node.
   652       void nextIn(Arc&) const {}
   653 
   654       /// \brief Return the first arc outgoing form the given node.
   655       ///
   656       /// This function gives back the first arc outgoing form the
   657       /// given node.
   658       void firstOut(Arc&, const Node&) const {}
   659 
   660       /// \brief Return the next arc outgoing form the given node.
   661       ///
   662       /// This function gives back the next arc outgoing form the
   663       /// given node.
   664       void nextOut(Arc&) const {}
   665 
   666       /// @}
   667 
   668       /// \name Class Based Iteration
   669       ///
   670       /// This interface provides iterator classes for digraph items.
   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 
   680       /// \brief This iterator goes through each arc.
   681       ///
   682       /// This iterator goes through each arc.
   683       ///
   684       typedef GraphItemIt<Digraph, Arc> ArcIt;
   685 
   686       /// \brief This iterator goes trough the incoming arcs of a node.
   687       ///
   688       /// This iterator goes trough the \e incoming arcs of a certain node
   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       ///
   700       /// This function gives back the base node of the iterator.
   701       /// It is always the target node of the pointed arc.
   702       Node baseNode(const InArcIt&) const { return INVALID; }
   703 
   704       /// \brief The running node of the iterator.
   705       ///
   706       /// This function gives back the running node of the iterator.
   707       /// It is always the source node of the pointed arc.
   708       Node runningNode(const InArcIt&) const { return INVALID; }
   709 
   710       /// \brief The base node of the iterator.
   711       ///
   712       /// This function gives back the base node of the iterator.
   713       /// It is always the source node of the pointed arc.
   714       Node baseNode(const OutArcIt&) const { return INVALID; }
   715 
   716       /// \brief The running node of the iterator.
   717       ///
   718       /// This function gives back the running node of the iterator.
   719       /// It is always the target node of the pointed arc.
   720       Node runningNode(const OutArcIt&) const { return INVALID; }
   721 
   722       /// @}
   723 
   724       template <typename _Digraph>
   725       struct Constraints {
   726         void constraints() {
   727           checkConcept<Base, _Digraph>();
   728 
   729           {
   730             typename _Digraph::Node node(INVALID);
   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             }
   748           }
   749 
   750           {
   751             checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
   752               typename _Digraph::ArcIt >();
   753             checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
   754               typename _Digraph::NodeIt >();
   755             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
   756               typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
   757             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
   758               typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
   759 
   760             typename _Digraph::Node n;
   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);
   767             ignore_unused_variable_warning(n);
   768           }
   769         }
   770 
   771         const _Digraph& digraph;
   772         Constraints() {}
   773       };
   774     };
   775 
   776     /// \brief Skeleton class for iterable undirected graphs.
   777     ///
   778     /// This class describes the interface of iterable undirected
   779     /// graphs. It extends \ref IterableDigraphComponent with the core
   780     /// iterable interface of undirected graphs.
   781     /// This concept is part of the Graph concept.
   782     template <typename BAS = BaseGraphComponent>
   783     class IterableGraphComponent : public IterableDigraphComponent<BAS> {
   784     public:
   785 
   786       typedef BAS Base;
   787       typedef typename Base::Node Node;
   788       typedef typename Base::Arc Arc;
   789       typedef typename Base::Edge Edge;
   790 
   791 
   792       typedef IterableGraphComponent Graph;
   793 
   794       /// \name Base Iteration
   795       ///
   796       /// This interface provides functions for iteration on edges.
   797       ///
   798       /// @{
   799 
   800       using IterableDigraphComponent<Base>::first;
   801       using IterableDigraphComponent<Base>::next;
   802 
   803       /// \brief Return the first edge.
   804       ///
   805       /// This function gives back the first edge in the iteration order.
   806       void first(Edge&) const {}
   807 
   808       /// \brief Return the next edge.
   809       ///
   810       /// This function gives back the next edge in the iteration order.
   811       void next(Edge&) const {}
   812 
   813       /// \brief Return the first edge incident to the given node.
   814       ///
   815       /// This function gives back the first edge incident to the given
   816       /// node. The bool parameter gives back the direction for which the
   817       /// source node of the directed arc representing the edge is the
   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       ///
   824       /// This function gives back the next edge incident to the given
   825       /// node. The bool parameter should be used as \c firstInc() use it.
   826       void nextInc(Edge&, bool&) const {}
   827 
   828       using IterableDigraphComponent<Base>::baseNode;
   829       using IterableDigraphComponent<Base>::runningNode;
   830 
   831       /// @}
   832 
   833       /// \name Class Based Iteration
   834       ///
   835       /// This interface provides iterator classes for edges.
   836       ///
   837       /// @{
   838 
   839       /// \brief This iterator goes through each edge.
   840       ///
   841       /// This iterator goes through each edge.
   842       typedef GraphItemIt<Graph, Edge> EdgeIt;
   843 
   844       /// \brief This iterator goes trough the incident edges of a
   845       /// node.
   846       ///
   847       /// This iterator goes trough the incident edges of a certain
   848       /// node of a graph.
   849       typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
   850 
   851       /// \brief The base node of the iterator.
   852       ///
   853       /// This function gives back the base node of the iterator.
   854       Node baseNode(const IncEdgeIt&) const { return INVALID; }
   855 
   856       /// \brief The running node of the iterator.
   857       ///
   858       /// This function gives back the running node of the iterator.
   859       Node runningNode(const IncEdgeIt&) const { return INVALID; }
   860 
   861       /// @}
   862 
   863       template <typename _Graph>
   864       struct Constraints {
   865         void constraints() {
   866           checkConcept<IterableDigraphComponent<Base>, _Graph>();
   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             }
   880 
   881           }
   882 
   883           {
   884             checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
   885               typename _Graph::EdgeIt >();
   886             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
   887               typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
   888 
   889             typename _Graph::Node n;
   890             const typename _Graph::IncEdgeIt ieit(INVALID);
   891             n = graph.baseNode(ieit);
   892             n = graph.runningNode(ieit);
   893           }
   894         }
   895 
   896         const _Graph& graph;
   897         Constraints() {}
   898       };
   899     };
   900 
   901     /// \brief Skeleton class for alterable directed graphs.
   902     ///
   903     /// This class describes the interface of alterable directed
   904     /// graphs. It extends \ref BaseDigraphComponent with the alteration
   905     /// notifier interface. It implements
   906     /// an observer-notifier pattern for each digraph item. More
   907     /// obsevers can be registered into the notifier and whenever an
   908     /// alteration occured in the digraph all the observers will be
   909     /// notified about it.
   910     template <typename BAS = BaseDigraphComponent>
   911     class AlterableDigraphComponent : public BAS {
   912     public:
   913 
   914       typedef BAS Base;
   915       typedef typename Base::Node Node;
   916       typedef typename Base::Arc Arc;
   917 
   918 
   919       /// Node alteration notifier class.
   920       typedef AlterationNotifier<AlterableDigraphComponent, Node>
   921       NodeNotifier;
   922       /// Arc alteration notifier class.
   923       typedef AlterationNotifier<AlterableDigraphComponent, Arc>
   924       ArcNotifier;
   925 
   926       /// \brief Return the node alteration notifier.
   927       ///
   928       /// This function gives back the node alteration notifier.
   929       NodeNotifier& notifier(Node) const {
   930          return NodeNotifier();
   931       }
   932 
   933       /// \brief Return the arc alteration notifier.
   934       ///
   935       /// This function gives back the arc alteration notifier.
   936       ArcNotifier& notifier(Arc) const {
   937         return ArcNotifier();
   938       }
   939 
   940       template <typename _Digraph>
   941       struct Constraints {
   942         void constraints() {
   943           checkConcept<Base, _Digraph>();
   944           typename _Digraph::NodeNotifier& nn
   945             = digraph.notifier(typename _Digraph::Node());
   946 
   947           typename _Digraph::ArcNotifier& en
   948             = digraph.notifier(typename _Digraph::Arc());
   949 
   950           ignore_unused_variable_warning(nn);
   951           ignore_unused_variable_warning(en);
   952         }
   953 
   954         const _Digraph& digraph;
   955         Constraints() {}
   956       };
   957     };
   958 
   959     /// \brief Skeleton class for alterable undirected graphs.
   960     ///
   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
   965     /// obsevers can be registered into the notifier and whenever an
   966     /// alteration occured in the graph all the observers will be
   967     /// notified about it.
   968     template <typename BAS = BaseGraphComponent>
   969     class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
   970     public:
   971 
   972       typedef BAS Base;
   973       typedef typename Base::Edge Edge;
   974 
   975 
   976       /// Edge alteration notifier class.
   977       typedef AlterationNotifier<AlterableGraphComponent, Edge>
   978       EdgeNotifier;
   979 
   980       /// \brief Return the edge alteration notifier.
   981       ///
   982       /// This function gives back the edge alteration notifier.
   983       EdgeNotifier& notifier(Edge) const {
   984         return EdgeNotifier();
   985       }
   986 
   987       template <typename _Graph>
   988       struct Constraints {
   989         void constraints() {
   990           checkConcept<AlterableDigraphComponent<Base>, _Graph>();
   991           typename _Graph::EdgeNotifier& uen
   992             = graph.notifier(typename _Graph::Edge());
   993           ignore_unused_variable_warning(uen);
   994         }
   995 
   996         const _Graph& graph;
   997         Constraints() {}
   998       };
   999     };
  1000 
  1001     /// \brief Concept class for standard graph maps.
  1002     ///
  1003     /// This class describes the concept of standard graph maps, i.e.
  1004     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
  1005     /// graph types, which can be used for associating data to graph items.
  1006     /// The standard graph maps must conform to the ReferenceMap concept.
  1007     template <typename GR, typename K, typename V>
  1008     class GraphMap : public ReferenceMap<K, V, V&, const V&> {
  1009       typedef ReferenceMap<K, V, V&, const V&> Parent;
  1010 
  1011     public:
  1012 
  1013       /// The key type of the map.
  1014       typedef K Key;
  1015       /// The value type of the map.
  1016       typedef V Value;
  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;
  1024 
  1025       /// \brief Construct a new map.
  1026       ///
  1027       /// Construct a new map for the graph.
  1028       explicit GraphMap(const GR&) {}
  1029       /// \brief Construct a new map with default value.
  1030       ///
  1031       /// Construct a new map for the graph and initalize the values.
  1032       GraphMap(const GR&, const Value&) {}
  1033 
  1034     private:
  1035       /// \brief Copy constructor.
  1036       ///
  1037       /// Copy Constructor.
  1038       GraphMap(const GraphMap&) : Parent() {}
  1039 
  1040       /// \brief Assignment operator.
  1041       ///
  1042       /// Assignment operator. It does not mofify the underlying graph,
  1043       /// it just iterates on the current item set and set the  map
  1044       /// with the value returned by the assigned map.
  1045       template <typename CMap>
  1046       GraphMap& operator=(const CMap&) {
  1047         checkConcept<ReadMap<Key, Value>, CMap>();
  1048         return *this;
  1049       }
  1050 
  1051     public:
  1052       template<typename _Map>
  1053       struct Constraints {
  1054         void constraints() {
  1055           checkConcept
  1056             <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
  1057           _Map m1(g);
  1058           _Map m2(g,t);
  1059 
  1060           // Copy constructor
  1061           // _Map m3(m);
  1062 
  1063           // Assignment operator
  1064           // ReadMap<Key, Value> cmap;
  1065           // m3 = cmap;
  1066 
  1067           ignore_unused_variable_warning(m1);
  1068           ignore_unused_variable_warning(m2);
  1069           // ignore_unused_variable_warning(m3);
  1070         }
  1071 
  1072         const _Map &m;
  1073         const GR &g;
  1074         const typename GraphMap::Value &t;
  1075         Constraints() {}
  1076       };
  1077 
  1078     };
  1079 
  1080     /// \brief Skeleton class for mappable directed graphs.
  1081     ///
  1082     /// This class describes the interface of mappable directed graphs.
  1083     /// It extends \ref BaseDigraphComponent with the standard digraph
  1084     /// map classes, namely \c NodeMap and \c ArcMap.
  1085     /// This concept is part of the Digraph concept.
  1086     template <typename BAS = BaseDigraphComponent>
  1087     class MappableDigraphComponent : public BAS  {
  1088     public:
  1089 
  1090       typedef BAS Base;
  1091       typedef typename Base::Node Node;
  1092       typedef typename Base::Arc Arc;
  1093 
  1094       typedef MappableDigraphComponent Digraph;
  1095 
  1096       /// \brief Standard graph map for the nodes.
  1097       ///
  1098       /// Standard graph map for the nodes.
  1099       /// It conforms to the ReferenceMap concept.
  1100       template <typename V>
  1101       class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
  1102         typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
  1103 
  1104       public:
  1105         /// \brief Construct a new map.
  1106         ///
  1107         /// Construct a new map for the digraph.
  1108         explicit NodeMap(const MappableDigraphComponent& digraph)
  1109           : Parent(digraph) {}
  1110 
  1111         /// \brief Construct a new map with default value.
  1112         ///
  1113         /// Construct a new map for the digraph and initalize the values.
  1114         NodeMap(const MappableDigraphComponent& digraph, const V& value)
  1115           : Parent(digraph, value) {}
  1116 
  1117       private:
  1118         /// \brief Copy constructor.
  1119         ///
  1120         /// Copy Constructor.
  1121         NodeMap(const NodeMap& nm) : Parent(nm) {}
  1122 
  1123         /// \brief Assignment operator.
  1124         ///
  1125         /// Assignment operator.
  1126         template <typename CMap>
  1127         NodeMap& operator=(const CMap&) {
  1128           checkConcept<ReadMap<Node, V>, CMap>();
  1129           return *this;
  1130         }
  1131 
  1132       };
  1133 
  1134       /// \brief Standard graph map for the arcs.
  1135       ///
  1136       /// Standard graph map for the arcs.
  1137       /// It conforms to the ReferenceMap concept.
  1138       template <typename V>
  1139       class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
  1140         typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
  1141 
  1142       public:
  1143         /// \brief Construct a new map.
  1144         ///
  1145         /// Construct a new map for the digraph.
  1146         explicit ArcMap(const MappableDigraphComponent& digraph)
  1147           : Parent(digraph) {}
  1148 
  1149         /// \brief Construct a new map with default value.
  1150         ///
  1151         /// Construct a new map for the digraph and initalize the values.
  1152         ArcMap(const MappableDigraphComponent& digraph, const V& value)
  1153           : Parent(digraph, value) {}
  1154 
  1155       private:
  1156         /// \brief Copy constructor.
  1157         ///
  1158         /// Copy Constructor.
  1159         ArcMap(const ArcMap& nm) : Parent(nm) {}
  1160 
  1161         /// \brief Assignment operator.
  1162         ///
  1163         /// Assignment operator.
  1164         template <typename CMap>
  1165         ArcMap& operator=(const CMap&) {
  1166           checkConcept<ReadMap<Arc, V>, CMap>();
  1167           return *this;
  1168         }
  1169 
  1170       };
  1171 
  1172 
  1173       template <typename _Digraph>
  1174       struct Constraints {
  1175 
  1176         struct Dummy {
  1177           int value;
  1178           Dummy() : value(0) {}
  1179           Dummy(int _v) : value(_v) {}
  1180         };
  1181 
  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           }
  1197 
  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         }
  1212 
  1213         const _Digraph& digraph;
  1214         Constraints() {}
  1215       };
  1216     };
  1217 
  1218     /// \brief Skeleton class for mappable undirected graphs.
  1219     ///
  1220     /// This class describes the interface of mappable undirected graphs.
  1221     /// It extends \ref MappableDigraphComponent with the standard graph
  1222     /// map class for edges (\c EdgeMap).
  1223     /// This concept is part of the Graph concept.
  1224     template <typename BAS = BaseGraphComponent>
  1225     class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
  1226     public:
  1227 
  1228       typedef BAS Base;
  1229       typedef typename Base::Edge Edge;
  1230 
  1231       typedef MappableGraphComponent Graph;
  1232 
  1233       /// \brief Standard graph map for the edges.
  1234       ///
  1235       /// Standard graph map for the edges.
  1236       /// It conforms to the ReferenceMap concept.
  1237       template <typename V>
  1238       class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
  1239         typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
  1240 
  1241       public:
  1242         /// \brief Construct a new map.
  1243         ///
  1244         /// Construct a new map for the graph.
  1245         explicit EdgeMap(const MappableGraphComponent& graph)
  1246           : Parent(graph) {}
  1247 
  1248         /// \brief Construct a new map with default value.
  1249         ///
  1250         /// Construct a new map for the graph and initalize the values.
  1251         EdgeMap(const MappableGraphComponent& graph, const V& value)
  1252           : Parent(graph, value) {}
  1253 
  1254       private:
  1255         /// \brief Copy constructor.
  1256         ///
  1257         /// Copy Constructor.
  1258         EdgeMap(const EdgeMap& nm) : Parent(nm) {}
  1259 
  1260         /// \brief Assignment operator.
  1261         ///
  1262         /// Assignment operator.
  1263         template <typename CMap>
  1264         EdgeMap& operator=(const CMap&) {
  1265           checkConcept<ReadMap<Edge, V>, CMap>();
  1266           return *this;
  1267         }
  1268 
  1269       };
  1270 
  1271 
  1272       template <typename _Graph>
  1273       struct Constraints {
  1274 
  1275         struct Dummy {
  1276           int value;
  1277           Dummy() : value(0) {}
  1278           Dummy(int _v) : value(_v) {}
  1279         };
  1280 
  1281         void constraints() {
  1282           checkConcept<MappableDigraphComponent<Base>, _Graph>();
  1283 
  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         }
  1298 
  1299         const _Graph& graph;
  1300         Constraints() {}
  1301       };
  1302     };
  1303 
  1304     /// \brief Skeleton class for extendable directed graphs.
  1305     ///
  1306     /// This class describes the interface of extendable directed graphs.
  1307     /// It extends \ref BaseDigraphComponent with functions for adding
  1308     /// nodes and arcs to the digraph.
  1309     /// This concept requires \ref AlterableDigraphComponent.
  1310     template <typename BAS = BaseDigraphComponent>
  1311     class ExtendableDigraphComponent : public BAS {
  1312     public:
  1313       typedef BAS Base;
  1314 
  1315       typedef typename Base::Node Node;
  1316       typedef typename Base::Arc Arc;
  1317 
  1318       /// \brief Add a new node to the digraph.
  1319       ///
  1320       /// This function adds a new node to the digraph.
  1321       Node addNode() {
  1322         return INVALID;
  1323       }
  1324 
  1325       /// \brief Add a new arc connecting the given two nodes.
  1326       ///
  1327       /// This function adds a new arc connecting the given two nodes
  1328       /// of the digraph.
  1329       Arc addArc(const Node&, const Node&) {
  1330         return INVALID;
  1331       }
  1332 
  1333       template <typename _Digraph>
  1334       struct Constraints {
  1335         void constraints() {
  1336           checkConcept<Base, _Digraph>();
  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         }
  1343 
  1344         _Digraph& digraph;
  1345         Constraints() {}
  1346       };
  1347     };
  1348 
  1349     /// \brief Skeleton class for extendable undirected graphs.
  1350     ///
  1351     /// This class describes the interface of extendable undirected graphs.
  1352     /// It extends \ref BaseGraphComponent with functions for adding
  1353     /// nodes and edges to the graph.
  1354     /// This concept requires \ref AlterableGraphComponent.
  1355     template <typename BAS = BaseGraphComponent>
  1356     class ExtendableGraphComponent : public BAS {
  1357     public:
  1358 
  1359       typedef BAS Base;
  1360       typedef typename Base::Node Node;
  1361       typedef typename Base::Edge Edge;
  1362 
  1363       /// \brief Add a new node to the digraph.
  1364       ///
  1365       /// This function adds a new node to the digraph.
  1366       Node addNode() {
  1367         return INVALID;
  1368       }
  1369 
  1370       /// \brief Add a new edge connecting the given two nodes.
  1371       ///
  1372       /// This function adds a new edge connecting the given two nodes
  1373       /// of the graph.
  1374       Edge addEdge(const Node&, const Node&) {
  1375         return INVALID;
  1376       }
  1377 
  1378       template <typename _Graph>
  1379       struct Constraints {
  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         }
  1388 
  1389         _Graph& graph;
  1390         Constraints() {}
  1391       };
  1392     };
  1393 
  1394     /// \brief Skeleton class for erasable directed graphs.
  1395     ///
  1396     /// This class describes the interface of erasable directed graphs.
  1397     /// It extends \ref BaseDigraphComponent with functions for removing
  1398     /// nodes and arcs from the digraph.
  1399     /// This concept requires \ref AlterableDigraphComponent.
  1400     template <typename BAS = BaseDigraphComponent>
  1401     class ErasableDigraphComponent : public BAS {
  1402     public:
  1403 
  1404       typedef BAS Base;
  1405       typedef typename Base::Node Node;
  1406       typedef typename Base::Arc Arc;
  1407 
  1408       /// \brief Erase a node from the digraph.
  1409       ///
  1410       /// This function erases the given node from the digraph and all arcs
  1411       /// connected to the node.
  1412       void erase(const Node&) {}
  1413 
  1414       /// \brief Erase an arc from the digraph.
  1415       ///
  1416       /// This function erases the given arc from the digraph.
  1417       void erase(const Arc&) {}
  1418 
  1419       template <typename _Digraph>
  1420       struct Constraints {
  1421         void constraints() {
  1422           checkConcept<Base, _Digraph>();
  1423           const typename _Digraph::Node node(INVALID);
  1424           digraph.erase(node);
  1425           const typename _Digraph::Arc arc(INVALID);
  1426           digraph.erase(arc);
  1427         }
  1428 
  1429         _Digraph& digraph;
  1430         Constraints() {}
  1431       };
  1432     };
  1433 
  1434     /// \brief Skeleton class for erasable undirected graphs.
  1435     ///
  1436     /// This class describes the interface of erasable undirected graphs.
  1437     /// It extends \ref BaseGraphComponent with functions for removing
  1438     /// nodes and edges from the graph.
  1439     /// This concept requires \ref AlterableGraphComponent.
  1440     template <typename BAS = BaseGraphComponent>
  1441     class ErasableGraphComponent : public BAS {
  1442     public:
  1443 
  1444       typedef BAS Base;
  1445       typedef typename Base::Node Node;
  1446       typedef typename Base::Edge Edge;
  1447 
  1448       /// \brief Erase a node from the graph.
  1449       ///
  1450       /// This function erases the given node from the graph and all edges
  1451       /// connected to the node.
  1452       void erase(const Node&) {}
  1453 
  1454       /// \brief Erase an edge from the digraph.
  1455       ///
  1456       /// This function erases the given edge from the digraph.
  1457       void erase(const Edge&) {}
  1458 
  1459       template <typename _Graph>
  1460       struct Constraints {
  1461         void constraints() {
  1462           checkConcept<Base, _Graph>();
  1463           const typename _Graph::Node node(INVALID);
  1464           graph.erase(node);
  1465           const typename _Graph::Edge edge(INVALID);
  1466           graph.erase(edge);
  1467         }
  1468 
  1469         _Graph& graph;
  1470         Constraints() {}
  1471       };
  1472     };
  1473 
  1474     /// \brief Skeleton class for clearable directed graphs.
  1475     ///
  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.
  1480     template <typename BAS = BaseDigraphComponent>
  1481     class ClearableDigraphComponent : public BAS {
  1482     public:
  1483 
  1484       typedef BAS Base;
  1485 
  1486       /// \brief Erase all nodes and arcs from the digraph.
  1487       ///
  1488       /// This function erases all nodes and arcs from the digraph.
  1489       void clear() {}
  1490 
  1491       template <typename _Digraph>
  1492       struct Constraints {
  1493         void constraints() {
  1494           checkConcept<Base, _Digraph>();
  1495           digraph.clear();
  1496         }
  1497 
  1498         _Digraph& digraph;
  1499         Constraints() {}
  1500       };
  1501     };
  1502 
  1503     /// \brief Skeleton class for clearable undirected graphs.
  1504     ///
  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.
  1509     template <typename BAS = BaseGraphComponent>
  1510     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
  1511     public:
  1512 
  1513       typedef BAS Base;
  1514 
  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 
  1520       template <typename _Graph>
  1521       struct Constraints {
  1522         void constraints() {
  1523           checkConcept<Base, _Graph>();
  1524           graph.clear();
  1525         }
  1526 
  1527         _Graph& graph;
  1528         Constraints() {}
  1529       };
  1530     };
  1531 
  1532   }
  1533 
  1534 }
  1535 
  1536 #endif