lemon/concepts/graph_components.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 12 May 2009 12:06:40 +0200
changeset 663 8b0df68370a4
parent 584 33c6b6e755cd
child 666 1993af615e68
permissions -rw-r--r--
Fix the GEQ/LEQ handling in NetworkSimplex + improve doc (#291)

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