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