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