lemon/concepts/graph_components.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 07 Aug 2013 07:08:38 +0200
changeset 1262 dd1443e4a34c
parent 1261 97f1760dcd13
child 1270 dceba191c00d
permissions -rw-r--r--
Further ignore_unused_variable_warning() explicit namespaces (#294)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup graph_concepts
    20 ///\file
    21 ///\brief The concepts of graph components.
    22 
    23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    25 
    26 #include <lemon/core.h>
    27 #include <lemon/concepts/maps.h>
    28 
    29 #include <lemon/bits/alteration_notifier.h>
    30 
    31 namespace lemon {
    32   namespace concepts {
    33 
    34     /// \brief Concept class for \c Node, \c Arc and \c Edge types.
    35     ///
    36     /// This class describes the concept of \c Node, \c Arc and \c Edge
    37     /// subtypes of digraph and graph types.
    38     ///
    39     /// \note This class is a template class so that we can use it to
    40     /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same
    42     /// base class. For \c Node you should instantiate it with character
    43     /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    44 #ifndef DOXYGEN
    45     template <char sel = '0'>
    46 #endif
    47     class GraphItem {
    48     public:
    49       /// \brief Default constructor.
    50       ///
    51       /// Default constructor.
    52       /// \warning The default constructor is not required to set
    53       /// the item to some well-defined value. So you should consider it
    54       /// as uninitialized.
    55       GraphItem() {}
    56 
    57       /// \brief Copy constructor.
    58       ///
    59       /// Copy constructor.
    60       GraphItem(const GraphItem &) {}
    61 
    62       /// \brief Constructor for conversion from \c INVALID.
    63       ///
    64       /// Constructor for conversion from \c INVALID.
    65       /// It initializes the item to be invalid.
    66       /// \sa Invalid for more details.
    67       GraphItem(Invalid) {}
    68 
    69       /// \brief Assignment operator.
    70       ///
    71       /// Assignment operator for the item.
    72       GraphItem& operator=(const GraphItem&) { return *this; }
    73 
    74       /// \brief Assignment operator for INVALID.
    75       ///
    76       /// This operator makes the item invalid.
    77       GraphItem& operator=(Invalid) { return *this; }
    78 
    79       /// \brief Equality operator.
    80       ///
    81       /// Equality operator.
    82       bool operator==(const GraphItem&) const { return false; }
    83 
    84       /// \brief Inequality operator.
    85       ///
    86       /// Inequality operator.
    87       bool operator!=(const GraphItem&) const { return false; }
    88 
    89       /// \brief Ordering operator.
    90       ///
    91       /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in
    93       /// associative containers (e.g. \c std::map).
    94       ///
    95       /// \note This operator only has to define some strict ordering of
    96       /// the items; this order has nothing to do with the iteration
    97       /// ordering of the items.
    98       bool operator<(const GraphItem&) const { return false; }
    99 
   100       template<typename _GraphItem>
   101       struct Constraints {
   102         void constraints() {
   103           _GraphItem i1;
   104           i1=INVALID;
   105           _GraphItem i2 = i1;
   106           _GraphItem i3 = INVALID;
   107 
   108           i1 = i2 = i3;
   109 
   110           bool b;
   111           ::lemon::ignore_unused_variable_warning(b);
   112 
   113           b = (ia == ib) && (ia != ib);
   114           b = (ia == INVALID) && (ib != INVALID);
   115           b = (ia < ib);
   116         }
   117 
   118         const _GraphItem &ia;
   119         const _GraphItem &ib;
   120         Constraints() {}
   121       };
   122     };
   123 
   124     /// \brief Base skeleton class for directed graphs.
   125     ///
   126     /// This class describes the base interface of directed graph types.
   127     /// All digraph %concepts have to conform to this class.
   128     /// It just provides types for nodes and arcs and functions
   129     /// to get the source and the target nodes of arcs.
   130     class BaseDigraphComponent {
   131     public:
   132 
   133       typedef BaseDigraphComponent Digraph;
   134 
   135       /// \brief Node class of the digraph.
   136       ///
   137       /// This class represents the nodes of the digraph.
   138       typedef GraphItem<'n'> Node;
   139 
   140       /// \brief Arc class of the digraph.
   141       ///
   142       /// This class represents the arcs of the digraph.
   143       typedef GraphItem<'a'> Arc;
   144 
   145       /// \brief Return the source node of an arc.
   146       ///
   147       /// This function returns the source node of an arc.
   148       Node source(const Arc&) const { return INVALID; }
   149 
   150       /// \brief Return the target node of an arc.
   151       ///
   152       /// This function returns the target node of an arc.
   153       Node target(const Arc&) const { return INVALID; }
   154 
   155       /// \brief Return the opposite node on the given arc.
   156       ///
   157       /// This function returns the opposite node on the given arc.
   158       Node oppositeNode(const Node&, const Arc&) const {
   159         return INVALID;
   160       }
   161 
   162       template <typename _Digraph>
   163       struct Constraints {
   164         typedef typename _Digraph::Node Node;
   165         typedef typename _Digraph::Arc Arc;
   166 
   167         void constraints() {
   168           checkConcept<GraphItem<'n'>, Node>();
   169           checkConcept<GraphItem<'a'>, Arc>();
   170           {
   171             Node n;
   172             Arc e(INVALID);
   173             n = digraph.source(e);
   174             n = digraph.target(e);
   175             n = digraph.oppositeNode(n, e);
   176           }
   177         }
   178 
   179         const _Digraph& digraph;
   180         Constraints() {}
   181       };
   182     };
   183 
   184     /// \brief Base skeleton class for undirected graphs.
   185     ///
   186     /// This class describes the base interface of undirected graph types.
   187     /// All graph %concepts have to conform to this class.
   188     /// It extends the interface of \ref BaseDigraphComponent with an
   189     /// \c Edge type and functions to get the end nodes of edges,
   190     /// to convert from arcs to edges and to get both direction of edges.
   191     class BaseGraphComponent : public BaseDigraphComponent {
   192     public:
   193 
   194       typedef BaseGraphComponent Graph;
   195 
   196       typedef BaseDigraphComponent::Node Node;
   197       typedef BaseDigraphComponent::Arc Arc;
   198 
   199       /// \brief Undirected edge class of the graph.
   200       ///
   201       /// This class represents the undirected edges of the graph.
   202       /// Undirected graphs can be used as directed graphs, each edge is
   203       /// represented by two opposite directed arcs.
   204       class Edge : public GraphItem<'e'> {
   205         typedef GraphItem<'e'> Parent;
   206 
   207       public:
   208         /// \brief Default constructor.
   209         ///
   210         /// Default constructor.
   211         /// \warning The default constructor is not required to set
   212         /// the item to some well-defined value. So you should consider it
   213         /// as uninitialized.
   214         Edge() {}
   215 
   216         /// \brief Copy constructor.
   217         ///
   218         /// Copy constructor.
   219         Edge(const Edge &) : Parent() {}
   220 
   221         /// \brief Constructor for conversion from \c INVALID.
   222         ///
   223         /// Constructor for conversion from \c INVALID.
   224         /// It initializes the item to be invalid.
   225         /// \sa Invalid for more details.
   226         Edge(Invalid) {}
   227 
   228         /// \brief Constructor for conversion from an arc.
   229         ///
   230         /// Constructor for conversion from an arc.
   231         /// Besides the core graph item functionality each arc should
   232         /// be convertible to the represented edge.
   233         Edge(const Arc&) {}
   234      };
   235 
   236       /// \brief Return one end node of an edge.
   237       ///
   238       /// This function returns one end node of an edge.
   239       Node u(const Edge&) const { return INVALID; }
   240 
   241       /// \brief Return the other end node of an edge.
   242       ///
   243       /// This function returns the other end node of an edge.
   244       Node v(const Edge&) const { return INVALID; }
   245 
   246       /// \brief Return a directed arc related to an edge.
   247       ///
   248       /// This function returns a directed arc from its direction and the
   249       /// represented edge.
   250       Arc direct(const Edge&, bool) const { return INVALID; }
   251 
   252       /// \brief Return a directed arc related to an edge.
   253       ///
   254       /// This function returns a directed arc from its source node and the
   255       /// represented edge.
   256       Arc direct(const Edge&, const Node&) const { return INVALID; }
   257 
   258       /// \brief Return the direction of the arc.
   259       ///
   260       /// Returns the direction of the arc. Each arc represents an
   261       /// edge with a direction. It gives back the
   262       /// direction.
   263       bool direction(const Arc&) const { return true; }
   264 
   265       /// \brief Return the opposite arc.
   266       ///
   267       /// This function returns the opposite arc, i.e. the arc representing
   268       /// the same edge and has opposite direction.
   269       Arc oppositeArc(const Arc&) const { return INVALID; }
   270 
   271       template <typename _Graph>
   272       struct Constraints {
   273         typedef typename _Graph::Node Node;
   274         typedef typename _Graph::Arc Arc;
   275         typedef typename _Graph::Edge Edge;
   276 
   277         void constraints() {
   278           checkConcept<BaseDigraphComponent, _Graph>();
   279           checkConcept<GraphItem<'e'>, Edge>();
   280           {
   281             Node n;
   282             Edge ue(INVALID);
   283             Arc e;
   284             n = graph.u(ue);
   285             n = graph.v(ue);
   286             e = graph.direct(ue, true);
   287             e = graph.direct(ue, false);
   288             e = graph.direct(ue, n);
   289             e = graph.oppositeArc(e);
   290             ue = e;
   291             bool d = graph.direction(e);
   292             ::lemon::ignore_unused_variable_warning(d);
   293           }
   294         }
   295 
   296         const _Graph& graph;
   297       Constraints() {}
   298       };
   299 
   300     };
   301 
   302     /// \brief Base skeleton class for undirected bipartite graphs.
   303     ///
   304     /// This class describes the base interface of undirected
   305     /// bipartite graph types.  All bipartite graph %concepts have to
   306     /// conform to this class.  It extends the interface of \ref
   307     /// BaseGraphComponent with an \c Edge type and functions to get
   308     /// the end nodes of edges, to convert from arcs to edges and to
   309     /// get both direction of edges.
   310     class BaseBpGraphComponent : public BaseGraphComponent {
   311     public:
   312 
   313       typedef BaseBpGraphComponent BpGraph;
   314 
   315       typedef BaseDigraphComponent::Node Node;
   316       typedef BaseDigraphComponent::Arc Arc;
   317 
   318       /// \brief Class to represent red nodes.
   319       ///
   320       /// This class represents the red nodes of the graph. The red
   321       /// nodes can also be used as normal nodes.
   322       class RedNode : public Node {
   323         typedef Node Parent;
   324 
   325       public:
   326         /// \brief Default constructor.
   327         ///
   328         /// Default constructor.
   329         /// \warning The default constructor is not required to set
   330         /// the item to some well-defined value. So you should consider it
   331         /// as uninitialized.
   332         RedNode() {}
   333 
   334         /// \brief Copy constructor.
   335         ///
   336         /// Copy constructor.
   337         RedNode(const RedNode &) : Parent() {}
   338 
   339         /// \brief Constructor for conversion from \c INVALID.
   340         ///
   341         /// Constructor for conversion from \c INVALID.
   342         /// It initializes the item to be invalid.
   343         /// \sa Invalid for more details.
   344         RedNode(Invalid) {}
   345       };
   346 
   347       /// \brief Class to represent blue nodes.
   348       ///
   349       /// This class represents the blue nodes of the graph. The blue
   350       /// nodes can also be used as normal nodes.
   351       class BlueNode : public Node {
   352         typedef Node Parent;
   353 
   354       public:
   355         /// \brief Default constructor.
   356         ///
   357         /// Default constructor.
   358         /// \warning The default constructor is not required to set
   359         /// the item to some well-defined value. So you should consider it
   360         /// as uninitialized.
   361         BlueNode() {}
   362 
   363         /// \brief Copy constructor.
   364         ///
   365         /// Copy constructor.
   366         BlueNode(const BlueNode &) : Parent() {}
   367 
   368         /// \brief Constructor for conversion from \c INVALID.
   369         ///
   370         /// Constructor for conversion from \c INVALID.
   371         /// It initializes the item to be invalid.
   372         /// \sa Invalid for more details.
   373         BlueNode(Invalid) {}
   374 
   375         /// \brief Constructor for conversion from a node.
   376         ///
   377         /// Constructor for conversion from a node. The conversion can
   378         /// be invalid, since the Node can be member of the red
   379         /// set.
   380         BlueNode(const Node&) {}
   381       };
   382 
   383       /// \brief Gives back %true for red nodes.
   384       ///
   385       /// Gives back %true for red nodes.
   386       bool red(const Node&) const { return true; }
   387 
   388       /// \brief Gives back %true for blue nodes.
   389       ///
   390       /// Gives back %true for blue nodes.
   391       bool blue(const Node&) const { return true; }
   392 
   393       /// \brief Gives back the red end node of the edge.
   394       /// 
   395       /// Gives back the red end node of the edge.
   396       RedNode redNode(const Edge&) const { return RedNode(); }
   397 
   398       /// \brief Gives back the blue end node of the edge.
   399       /// 
   400       /// Gives back the blue end node of the edge.
   401       BlueNode blueNode(const Edge&) const { return BlueNode(); }
   402 
   403       /// \brief Converts the node to red node object.
   404       ///
   405       /// This function converts unsafely the node to red node
   406       /// object. It should be called only if the node is from the red
   407       /// partition or INVALID.
   408       RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
   409 
   410       /// \brief Converts the node to blue node object.
   411       ///
   412       /// This function converts unsafely the node to blue node
   413       /// object. It should be called only if the node is from the red
   414       /// partition or INVALID.
   415       BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
   416 
   417       /// \brief Converts the node to red node object.
   418       ///
   419       /// This function converts safely the node to red node
   420       /// object. If the node is not from the red partition, then it
   421       /// returns INVALID.
   422       RedNode asRedNode(const Node&) const { return RedNode(); }
   423 
   424       /// \brief Converts the node to blue node object.
   425       ///
   426       /// This function converts unsafely the node to blue node
   427       /// object. If the node is not from the blue partition, then it
   428       /// returns INVALID.
   429       BlueNode asBlueNode(const Node&) const { return BlueNode(); }
   430 
   431       template <typename _BpGraph>
   432       struct Constraints {
   433         typedef typename _BpGraph::Node Node;
   434         typedef typename _BpGraph::RedNode RedNode;
   435         typedef typename _BpGraph::BlueNode BlueNode;
   436         typedef typename _BpGraph::Arc Arc;
   437         typedef typename _BpGraph::Edge Edge;
   438 
   439         void constraints() {
   440           checkConcept<BaseGraphComponent, _BpGraph>();
   441           checkConcept<GraphItem<'n'>, RedNode>();
   442           checkConcept<GraphItem<'n'>, BlueNode>();
   443           {
   444             Node n;
   445             RedNode rn;
   446             BlueNode bn;
   447             Node rnan = rn;
   448             Node bnan = bn;
   449             Edge e;
   450             bool b;
   451             b = bpgraph.red(rnan);
   452             b = bpgraph.blue(bnan);
   453             rn = bpgraph.redNode(e);
   454             bn = bpgraph.blueNode(e);
   455             rn = bpgraph.asRedNodeUnsafe(rnan);
   456             bn = bpgraph.asBlueNodeUnsafe(bnan);
   457             rn = bpgraph.asRedNode(rnan);
   458             bn = bpgraph.asBlueNode(bnan);
   459             ::lemon::ignore_unused_variable_warning(b);
   460           }
   461         }
   462 
   463         const _BpGraph& bpgraph;
   464       };
   465 
   466     };
   467 
   468     /// \brief Skeleton class for \e idable directed graphs.
   469     ///
   470     /// This class describes the interface of \e idable directed graphs.
   471     /// It extends \ref BaseDigraphComponent with the core ID functions.
   472     /// The ids of the items must be unique and immutable.
   473     /// This concept is part of the Digraph concept.
   474     template <typename BAS = BaseDigraphComponent>
   475     class IDableDigraphComponent : public BAS {
   476     public:
   477 
   478       typedef BAS Base;
   479       typedef typename Base::Node Node;
   480       typedef typename Base::Arc Arc;
   481 
   482       /// \brief Return a unique integer id for the given node.
   483       ///
   484       /// This function returns a unique integer id for the given node.
   485       int id(const Node&) const { return -1; }
   486 
   487       /// \brief Return the node by its unique id.
   488       ///
   489       /// This function returns the node by its unique id.
   490       /// If the digraph does not contain a node with the given id,
   491       /// then the result of the function is undefined.
   492       Node nodeFromId(int) const { return INVALID; }
   493 
   494       /// \brief Return a unique integer id for the given arc.
   495       ///
   496       /// This function returns a unique integer id for the given arc.
   497       int id(const Arc&) const { return -1; }
   498 
   499       /// \brief Return the arc by its unique id.
   500       ///
   501       /// This function returns the arc by its unique id.
   502       /// If the digraph does not contain an arc with the given id,
   503       /// then the result of the function is undefined.
   504       Arc arcFromId(int) const { return INVALID; }
   505 
   506       /// \brief Return an integer greater or equal to the maximum
   507       /// node id.
   508       ///
   509       /// This function returns an integer greater or equal to the
   510       /// maximum node id.
   511       int maxNodeId() const { return -1; }
   512 
   513       /// \brief Return an integer greater or equal to the maximum
   514       /// arc id.
   515       ///
   516       /// This function returns an integer greater or equal to the
   517       /// maximum arc id.
   518       int maxArcId() const { return -1; }
   519 
   520       template <typename _Digraph>
   521       struct Constraints {
   522 
   523         void constraints() {
   524           checkConcept<Base, _Digraph >();
   525           typename _Digraph::Node node;
   526           node=INVALID;
   527           int nid = digraph.id(node);
   528           nid = digraph.id(node);
   529           node = digraph.nodeFromId(nid);
   530           typename _Digraph::Arc arc;
   531           arc=INVALID;
   532           int eid = digraph.id(arc);
   533           eid = digraph.id(arc);
   534           arc = digraph.arcFromId(eid);
   535 
   536           nid = digraph.maxNodeId();
   537           ::lemon::ignore_unused_variable_warning(nid);
   538           eid = digraph.maxArcId();
   539           ::lemon::ignore_unused_variable_warning(eid);
   540         }
   541 
   542         const _Digraph& digraph;
   543         Constraints() {}
   544       };
   545     };
   546 
   547     /// \brief Skeleton class for \e idable undirected graphs.
   548     ///
   549     /// This class describes the interface of \e idable undirected
   550     /// graphs. It extends \ref IDableDigraphComponent with the core ID
   551     /// functions of undirected graphs.
   552     /// The ids of the items must be unique and immutable.
   553     /// This concept is part of the Graph concept.
   554     template <typename BAS = BaseGraphComponent>
   555     class IDableGraphComponent : public IDableDigraphComponent<BAS> {
   556     public:
   557 
   558       typedef BAS Base;
   559       typedef typename Base::Edge Edge;
   560 
   561       using IDableDigraphComponent<Base>::id;
   562 
   563       /// \brief Return a unique integer id for the given edge.
   564       ///
   565       /// This function returns a unique integer id for the given edge.
   566       int id(const Edge&) const { return -1; }
   567 
   568       /// \brief Return the edge by its unique id.
   569       ///
   570       /// This function returns the edge by its unique id.
   571       /// If the graph does not contain an edge with the given id,
   572       /// then the result of the function is undefined.
   573       Edge edgeFromId(int) const { return INVALID; }
   574 
   575       /// \brief Return an integer greater or equal to the maximum
   576       /// edge id.
   577       ///
   578       /// This function returns an integer greater or equal to the
   579       /// maximum edge id.
   580       int maxEdgeId() const { return -1; }
   581 
   582       template <typename _Graph>
   583       struct Constraints {
   584 
   585         void constraints() {
   586           checkConcept<IDableDigraphComponent<Base>, _Graph >();
   587           typename _Graph::Edge edge;
   588           int ueid = graph.id(edge);
   589           ueid = graph.id(edge);
   590           edge = graph.edgeFromId(ueid);
   591           ueid = graph.maxEdgeId();
   592           ::lemon::ignore_unused_variable_warning(ueid);
   593         }
   594 
   595         const _Graph& graph;
   596         Constraints() {}
   597       };
   598     };
   599 
   600     /// \brief Skeleton class for \e idable undirected bipartite graphs.
   601     ///
   602     /// This class describes the interface of \e idable undirected
   603     /// bipartite graphs. It extends \ref IDableGraphComponent with
   604     /// the core ID functions of undirected bipartite graphs. Beside
   605     /// the regular node ids, this class also provides ids within the
   606     /// the red and blue sets of the nodes. This concept is part of
   607     /// the BpGraph concept.
   608     template <typename BAS = BaseBpGraphComponent>
   609     class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
   610     public:
   611 
   612       typedef BAS Base;
   613       typedef IDableGraphComponent<BAS> Parent;
   614       typedef typename Base::Node Node;
   615       typedef typename Base::RedNode RedNode;
   616       typedef typename Base::BlueNode BlueNode;
   617 
   618       using Parent::id;
   619 
   620       /// \brief Return a unique integer id for the given node in the red set.
   621       ///
   622       /// Return a unique integer id for the given node in the red set.
   623       int id(const RedNode&) const { return -1; }
   624 
   625       /// \brief Return a unique integer id for the given node in the blue set.
   626       ///
   627       /// Return a unique integer id for the given node in the blue set.
   628       int id(const BlueNode&) const { return -1; }
   629 
   630       /// \brief Return an integer greater or equal to the maximum
   631       /// node id in the red set.
   632       ///
   633       /// Return an integer greater or equal to the maximum
   634       /// node id in the red set.
   635       int maxRedId() const { return -1; }
   636 
   637       /// \brief Return an integer greater or equal to the maximum
   638       /// node id in the blue set.
   639       ///
   640       /// Return an integer greater or equal to the maximum
   641       /// node id in the blue set.
   642       int maxBlueId() const { return -1; }
   643 
   644       template <typename _BpGraph>
   645       struct Constraints {
   646 
   647         void constraints() {
   648           checkConcept<IDableGraphComponent<Base>, _BpGraph>();
   649           typename _BpGraph::Node node;
   650           typename _BpGraph::RedNode red;
   651           typename _BpGraph::BlueNode blue;
   652           int rid = bpgraph.id(red);
   653           int bid = bpgraph.id(blue);
   654           rid = bpgraph.maxRedId();
   655           bid = bpgraph.maxBlueId();
   656           ::lemon::ignore_unused_variable_warning(rid);
   657           ::lemon::ignore_unused_variable_warning(bid);
   658         }
   659 
   660         const _BpGraph& bpgraph;
   661       };
   662     };
   663 
   664     /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
   665     ///
   666     /// This class describes the concept of \c NodeIt, \c ArcIt and
   667     /// \c EdgeIt subtypes of digraph and graph types.
   668     template <typename GR, typename Item>
   669     class GraphItemIt : public Item {
   670     public:
   671       /// \brief Default constructor.
   672       ///
   673       /// Default constructor.
   674       /// \warning The default constructor is not required to set
   675       /// the iterator to some well-defined value. So you should consider it
   676       /// as uninitialized.
   677       GraphItemIt() {}
   678 
   679       /// \brief Copy constructor.
   680       ///
   681       /// Copy constructor.
   682       GraphItemIt(const GraphItemIt& it) : Item(it) {}
   683 
   684       /// \brief Constructor that sets the iterator to the first item.
   685       ///
   686       /// Constructor that sets the iterator to the first item.
   687       explicit GraphItemIt(const GR&) {}
   688 
   689       /// \brief Constructor for conversion from \c INVALID.
   690       ///
   691       /// Constructor for conversion from \c INVALID.
   692       /// It initializes the iterator to be invalid.
   693       /// \sa Invalid for more details.
   694       GraphItemIt(Invalid) {}
   695 
   696       /// \brief Assignment operator.
   697       ///
   698       /// Assignment operator for the iterator.
   699       GraphItemIt& operator=(const GraphItemIt&) { return *this; }
   700 
   701       /// \brief Increment the iterator.
   702       ///
   703       /// This operator increments the iterator, i.e. assigns it to the
   704       /// next item.
   705       GraphItemIt& operator++() { return *this; }
   706 
   707       /// \brief Equality operator
   708       ///
   709       /// Equality operator.
   710       /// Two iterators are equal if and only if they point to the
   711       /// same object or both are invalid.
   712       bool operator==(const GraphItemIt&) const { return true;}
   713 
   714       /// \brief Inequality operator
   715       ///
   716       /// Inequality operator.
   717       /// Two iterators are equal if and only if they point to the
   718       /// same object or both are invalid.
   719       bool operator!=(const GraphItemIt&) const { return true;}
   720 
   721       template<typename _GraphItemIt>
   722       struct Constraints {
   723         void constraints() {
   724           checkConcept<GraphItem<>, _GraphItemIt>();
   725           _GraphItemIt it1(g);
   726           _GraphItemIt it2;
   727           _GraphItemIt it3 = it1;
   728           _GraphItemIt it4 = INVALID;
   729           ::lemon::ignore_unused_variable_warning(it3);
   730           ::lemon::ignore_unused_variable_warning(it4);
   731 
   732           it2 = ++it1;
   733           ++it2 = it1;
   734           ++(++it1);
   735 
   736           Item bi = it1;
   737           bi = it2;
   738         }
   739         const GR& g;
   740         Constraints() {}
   741       };
   742     };
   743 
   744     /// \brief Concept class for \c InArcIt, \c OutArcIt and
   745     /// \c IncEdgeIt types.
   746     ///
   747     /// This class describes the concept of \c InArcIt, \c OutArcIt
   748     /// and \c IncEdgeIt subtypes of digraph and graph types.
   749     ///
   750     /// \note Since these iterator classes do not inherit from the same
   751     /// base class, there is an additional template parameter (selector)
   752     /// \c sel. For \c InArcIt you should instantiate it with character
   753     /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
   754     template <typename GR,
   755               typename Item = typename GR::Arc,
   756               typename Base = typename GR::Node,
   757               char sel = '0'>
   758     class GraphIncIt : public Item {
   759     public:
   760       /// \brief Default constructor.
   761       ///
   762       /// Default constructor.
   763       /// \warning The default constructor is not required to set
   764       /// the iterator to some well-defined value. So you should consider it
   765       /// as uninitialized.
   766       GraphIncIt() {}
   767 
   768       /// \brief Copy constructor.
   769       ///
   770       /// Copy constructor.
   771       GraphIncIt(const GraphIncIt& it) : Item(it) {}
   772 
   773       /// \brief Constructor that sets the iterator to the first
   774       /// incoming or outgoing arc.
   775       ///
   776       /// Constructor that sets the iterator to the first arc
   777       /// incoming to or outgoing from the given node.
   778       explicit GraphIncIt(const GR&, const Base&) {}
   779 
   780       /// \brief Constructor for conversion from \c INVALID.
   781       ///
   782       /// Constructor for conversion from \c INVALID.
   783       /// It initializes the iterator to be invalid.
   784       /// \sa Invalid for more details.
   785       GraphIncIt(Invalid) {}
   786 
   787       /// \brief Assignment operator.
   788       ///
   789       /// Assignment operator for the iterator.
   790       GraphIncIt& operator=(const GraphIncIt&) { return *this; }
   791 
   792       /// \brief Increment the iterator.
   793       ///
   794       /// This operator increments the iterator, i.e. assigns it to the
   795       /// next arc incoming to or outgoing from the given node.
   796       GraphIncIt& operator++() { return *this; }
   797 
   798       /// \brief Equality operator
   799       ///
   800       /// Equality operator.
   801       /// Two iterators are equal if and only if they point to the
   802       /// same object or both are invalid.
   803       bool operator==(const GraphIncIt&) const { return true;}
   804 
   805       /// \brief Inequality operator
   806       ///
   807       /// Inequality operator.
   808       /// Two iterators are equal if and only if they point to the
   809       /// same object or both are invalid.
   810       bool operator!=(const GraphIncIt&) const { return true;}
   811 
   812       template <typename _GraphIncIt>
   813       struct Constraints {
   814         void constraints() {
   815           checkConcept<GraphItem<sel>, _GraphIncIt>();
   816           _GraphIncIt it1(graph, node);
   817           _GraphIncIt it2;
   818           _GraphIncIt it3 = it1;
   819           _GraphIncIt it4 = INVALID;
   820           ::lemon::ignore_unused_variable_warning(it3);
   821           ::lemon::ignore_unused_variable_warning(it4);
   822 
   823           it2 = ++it1;
   824           ++it2 = it1;
   825           ++(++it1);
   826           Item e = it1;
   827           e = it2;
   828         }
   829         const Base& node;
   830         const GR& graph;
   831         Constraints() {}
   832       };
   833     };
   834 
   835     /// \brief Skeleton class for iterable directed graphs.
   836     ///
   837     /// This class describes the interface of iterable directed
   838     /// graphs. It extends \ref BaseDigraphComponent with the core
   839     /// iterable interface.
   840     /// This concept is part of the Digraph concept.
   841     template <typename BAS = BaseDigraphComponent>
   842     class IterableDigraphComponent : public BAS {
   843 
   844     public:
   845 
   846       typedef BAS Base;
   847       typedef typename Base::Node Node;
   848       typedef typename Base::Arc Arc;
   849 
   850       typedef IterableDigraphComponent Digraph;
   851 
   852       /// \name Base Iteration
   853       ///
   854       /// This interface provides functions for iteration on digraph items.
   855       ///
   856       /// @{
   857 
   858       /// \brief Return the first node.
   859       ///
   860       /// This function gives back the first node in the iteration order.
   861       void first(Node&) const {}
   862 
   863       /// \brief Return the next node.
   864       ///
   865       /// This function gives back the next node in the iteration order.
   866       void next(Node&) const {}
   867 
   868       /// \brief Return the first arc.
   869       ///
   870       /// This function gives back the first arc in the iteration order.
   871       void first(Arc&) const {}
   872 
   873       /// \brief Return the next arc.
   874       ///
   875       /// This function gives back the next arc in the iteration order.
   876       void next(Arc&) const {}
   877 
   878       /// \brief Return the first arc incoming to the given node.
   879       ///
   880       /// This function gives back the first arc incoming to the
   881       /// given node.
   882       void firstIn(Arc&, const Node&) const {}
   883 
   884       /// \brief Return the next arc incoming to the given node.
   885       ///
   886       /// This function gives back the next arc incoming to the
   887       /// given node.
   888       void nextIn(Arc&) const {}
   889 
   890       /// \brief Return the first arc outgoing form the given node.
   891       ///
   892       /// This function gives back the first arc outgoing form the
   893       /// given node.
   894       void firstOut(Arc&, const Node&) const {}
   895 
   896       /// \brief Return the next arc outgoing form the given node.
   897       ///
   898       /// This function gives back the next arc outgoing form the
   899       /// given node.
   900       void nextOut(Arc&) const {}
   901 
   902       /// @}
   903 
   904       /// \name Class Based Iteration
   905       ///
   906       /// This interface provides iterator classes for digraph items.
   907       ///
   908       /// @{
   909 
   910       /// \brief This iterator goes through each node.
   911       ///
   912       /// This iterator goes through each node.
   913       ///
   914       typedef GraphItemIt<Digraph, Node> NodeIt;
   915 
   916       /// \brief This iterator goes through each arc.
   917       ///
   918       /// This iterator goes through each arc.
   919       ///
   920       typedef GraphItemIt<Digraph, Arc> ArcIt;
   921 
   922       /// \brief This iterator goes trough the incoming arcs of a node.
   923       ///
   924       /// This iterator goes trough the \e incoming arcs of a certain node
   925       /// of a digraph.
   926       typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
   927 
   928       /// \brief This iterator goes trough the outgoing arcs of a node.
   929       ///
   930       /// This iterator goes trough the \e outgoing arcs of a certain node
   931       /// of a digraph.
   932       typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
   933 
   934       /// \brief The base node of the iterator.
   935       ///
   936       /// This function gives back the base node of the iterator.
   937       /// It is always the target node of the pointed arc.
   938       Node baseNode(const InArcIt&) const { return INVALID; }
   939 
   940       /// \brief The running node of the iterator.
   941       ///
   942       /// This function gives back the running node of the iterator.
   943       /// It is always the source node of the pointed arc.
   944       Node runningNode(const InArcIt&) const { return INVALID; }
   945 
   946       /// \brief The base node of the iterator.
   947       ///
   948       /// This function gives back the base node of the iterator.
   949       /// It is always the source node of the pointed arc.
   950       Node baseNode(const OutArcIt&) const { return INVALID; }
   951 
   952       /// \brief The running node of the iterator.
   953       ///
   954       /// This function gives back the running node of the iterator.
   955       /// It is always the target node of the pointed arc.
   956       Node runningNode(const OutArcIt&) const { return INVALID; }
   957 
   958       /// @}
   959 
   960       template <typename _Digraph>
   961       struct Constraints {
   962         void constraints() {
   963           checkConcept<Base, _Digraph>();
   964 
   965           {
   966             typename _Digraph::Node node(INVALID);
   967             typename _Digraph::Arc arc(INVALID);
   968             {
   969               digraph.first(node);
   970               digraph.next(node);
   971             }
   972             {
   973               digraph.first(arc);
   974               digraph.next(arc);
   975             }
   976             {
   977               digraph.firstIn(arc, node);
   978               digraph.nextIn(arc);
   979             }
   980             {
   981               digraph.firstOut(arc, node);
   982               digraph.nextOut(arc);
   983             }
   984           }
   985 
   986           {
   987             checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
   988               typename _Digraph::ArcIt >();
   989             checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
   990               typename _Digraph::NodeIt >();
   991             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
   992               typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
   993             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
   994               typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
   995 
   996             typename _Digraph::Node n;
   997             const typename _Digraph::InArcIt iait(INVALID);
   998             const typename _Digraph::OutArcIt oait(INVALID);
   999             n = digraph.baseNode(iait);
  1000             n = digraph.runningNode(iait);
  1001             n = digraph.baseNode(oait);
  1002             n = digraph.runningNode(oait);
  1003             ::lemon::ignore_unused_variable_warning(n);
  1004           }
  1005         }
  1006 
  1007         const _Digraph& digraph;
  1008         Constraints() {}
  1009       };
  1010     };
  1011 
  1012     /// \brief Skeleton class for iterable undirected graphs.
  1013     ///
  1014     /// This class describes the interface of iterable undirected
  1015     /// graphs. It extends \ref IterableDigraphComponent with the core
  1016     /// iterable interface of undirected graphs.
  1017     /// This concept is part of the Graph concept.
  1018     template <typename BAS = BaseGraphComponent>
  1019     class IterableGraphComponent : public IterableDigraphComponent<BAS> {
  1020     public:
  1021 
  1022       typedef BAS Base;
  1023       typedef typename Base::Node Node;
  1024       typedef typename Base::Arc Arc;
  1025       typedef typename Base::Edge Edge;
  1026 
  1027 
  1028       typedef IterableGraphComponent Graph;
  1029 
  1030       /// \name Base Iteration
  1031       ///
  1032       /// This interface provides functions for iteration on edges.
  1033       ///
  1034       /// @{
  1035 
  1036       using IterableDigraphComponent<Base>::first;
  1037       using IterableDigraphComponent<Base>::next;
  1038 
  1039       /// \brief Return the first edge.
  1040       ///
  1041       /// This function gives back the first edge in the iteration order.
  1042       void first(Edge&) const {}
  1043 
  1044       /// \brief Return the next edge.
  1045       ///
  1046       /// This function gives back the next edge in the iteration order.
  1047       void next(Edge&) const {}
  1048 
  1049       /// \brief Return the first edge incident to the given node.
  1050       ///
  1051       /// This function gives back the first edge incident to the given
  1052       /// node. The bool parameter gives back the direction for which the
  1053       /// source node of the directed arc representing the edge is the
  1054       /// given node.
  1055       void firstInc(Edge&, bool&, const Node&) const {}
  1056 
  1057       /// \brief Gives back the next of the edges from the
  1058       /// given node.
  1059       ///
  1060       /// This function gives back the next edge incident to the given
  1061       /// node. The bool parameter should be used as \c firstInc() use it.
  1062       void nextInc(Edge&, bool&) const {}
  1063 
  1064       using IterableDigraphComponent<Base>::baseNode;
  1065       using IterableDigraphComponent<Base>::runningNode;
  1066 
  1067       /// @}
  1068 
  1069       /// \name Class Based Iteration
  1070       ///
  1071       /// This interface provides iterator classes for edges.
  1072       ///
  1073       /// @{
  1074 
  1075       /// \brief This iterator goes through each edge.
  1076       ///
  1077       /// This iterator goes through each edge.
  1078       typedef GraphItemIt<Graph, Edge> EdgeIt;
  1079 
  1080       /// \brief This iterator goes trough the incident edges of a
  1081       /// node.
  1082       ///
  1083       /// This iterator goes trough the incident edges of a certain
  1084       /// node of a graph.
  1085       typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
  1086 
  1087       /// \brief The base node of the iterator.
  1088       ///
  1089       /// This function gives back the base node of the iterator.
  1090       Node baseNode(const IncEdgeIt&) const { return INVALID; }
  1091 
  1092       /// \brief The running node of the iterator.
  1093       ///
  1094       /// This function gives back the running node of the iterator.
  1095       Node runningNode(const IncEdgeIt&) const { return INVALID; }
  1096 
  1097       /// @}
  1098 
  1099       template <typename _Graph>
  1100       struct Constraints {
  1101         void constraints() {
  1102           checkConcept<IterableDigraphComponent<Base>, _Graph>();
  1103 
  1104           {
  1105             typename _Graph::Node node(INVALID);
  1106             typename _Graph::Edge edge(INVALID);
  1107             bool dir;
  1108             {
  1109               graph.first(edge);
  1110               graph.next(edge);
  1111             }
  1112             {
  1113               graph.firstInc(edge, dir, node);
  1114               graph.nextInc(edge, dir);
  1115             }
  1116 
  1117           }
  1118 
  1119           {
  1120             checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
  1121               typename _Graph::EdgeIt >();
  1122             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
  1123               typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
  1124 
  1125             typename _Graph::Node n;
  1126             const typename _Graph::IncEdgeIt ieit(INVALID);
  1127             n = graph.baseNode(ieit);
  1128             n = graph.runningNode(ieit);
  1129           }
  1130         }
  1131 
  1132         const _Graph& graph;
  1133         Constraints() {}
  1134       };
  1135     };
  1136 
  1137     /// \brief Skeleton class for iterable undirected bipartite graphs.
  1138     ///
  1139     /// This class describes the interface of iterable undirected
  1140     /// bipartite graphs. It extends \ref IterableGraphComponent with
  1141     /// the core iterable interface of undirected bipartite graphs.
  1142     /// This concept is part of the BpGraph concept.
  1143     template <typename BAS = BaseBpGraphComponent>
  1144     class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
  1145     public:
  1146 
  1147       typedef BAS Base;
  1148       typedef typename Base::Node Node;
  1149       typedef typename Base::RedNode RedNode;
  1150       typedef typename Base::BlueNode BlueNode;
  1151       typedef typename Base::Arc Arc;
  1152       typedef typename Base::Edge Edge;
  1153       
  1154       typedef IterableBpGraphComponent BpGraph;
  1155 
  1156       using IterableGraphComponent<BAS>::first;
  1157       using IterableGraphComponent<BAS>::next;
  1158 
  1159       /// \name Base Iteration
  1160       ///
  1161       /// This interface provides functions for iteration on red and blue nodes.
  1162       ///
  1163       /// @{
  1164 
  1165       /// \brief Return the first red node.
  1166       ///
  1167       /// This function gives back the first red node in the iteration order.
  1168       void first(RedNode&) const {}
  1169 
  1170       /// \brief Return the next red node.
  1171       ///
  1172       /// This function gives back the next red node in the iteration order.
  1173       void next(RedNode&) const {}
  1174 
  1175       /// \brief Return the first blue node.
  1176       ///
  1177       /// This function gives back the first blue node in the iteration order.
  1178       void first(BlueNode&) const {}
  1179 
  1180       /// \brief Return the next blue node.
  1181       ///
  1182       /// This function gives back the next blue node in the iteration order.
  1183       void next(BlueNode&) const {}
  1184 
  1185 
  1186       /// @}
  1187 
  1188       /// \name Class Based Iteration
  1189       ///
  1190       /// This interface provides iterator classes for red and blue nodes.
  1191       ///
  1192       /// @{
  1193 
  1194       /// \brief This iterator goes through each red node.
  1195       ///
  1196       /// This iterator goes through each red node.
  1197       typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
  1198 
  1199       /// \brief This iterator goes through each blue node.
  1200       ///
  1201       /// This iterator goes through each blue node.
  1202       typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
  1203 
  1204       /// @}
  1205 
  1206       template <typename _BpGraph>
  1207       struct Constraints {
  1208         void constraints() {
  1209           checkConcept<IterableGraphComponent<Base>, _BpGraph>();
  1210 
  1211           typename _BpGraph::RedNode rn(INVALID);
  1212           bpgraph.first(rn);
  1213           bpgraph.next(rn); 
  1214           typename _BpGraph::BlueNode bn(INVALID);
  1215           bpgraph.first(bn);
  1216           bpgraph.next(bn);
  1217 
  1218           checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
  1219             typename _BpGraph::RedNodeIt>();
  1220           checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
  1221             typename _BpGraph::BlueNodeIt>();
  1222         }
  1223 
  1224         const _BpGraph& bpgraph;
  1225       };
  1226     };
  1227 
  1228     /// \brief Skeleton class for alterable directed graphs.
  1229     ///
  1230     /// This class describes the interface of alterable directed
  1231     /// graphs. It extends \ref BaseDigraphComponent with the alteration
  1232     /// notifier interface. It implements
  1233     /// an observer-notifier pattern for each digraph item. More
  1234     /// obsevers can be registered into the notifier and whenever an
  1235     /// alteration occured in the digraph all the observers will be
  1236     /// notified about it.
  1237     template <typename BAS = BaseDigraphComponent>
  1238     class AlterableDigraphComponent : public BAS {
  1239     public:
  1240 
  1241       typedef BAS Base;
  1242       typedef typename Base::Node Node;
  1243       typedef typename Base::Arc Arc;
  1244 
  1245 
  1246       /// Node alteration notifier class.
  1247       typedef AlterationNotifier<AlterableDigraphComponent, Node>
  1248       NodeNotifier;
  1249       /// Arc alteration notifier class.
  1250       typedef AlterationNotifier<AlterableDigraphComponent, Arc>
  1251       ArcNotifier;
  1252 
  1253       mutable NodeNotifier node_notifier;
  1254       mutable ArcNotifier arc_notifier;
  1255 
  1256       /// \brief Return the node alteration notifier.
  1257       ///
  1258       /// This function gives back the node alteration notifier.
  1259       NodeNotifier& notifier(Node) const {
  1260         return node_notifier;
  1261       }
  1262 
  1263       /// \brief Return the arc alteration notifier.
  1264       ///
  1265       /// This function gives back the arc alteration notifier.
  1266       ArcNotifier& notifier(Arc) const {
  1267         return arc_notifier;
  1268       }
  1269 
  1270       template <typename _Digraph>
  1271       struct Constraints {
  1272         void constraints() {
  1273           checkConcept<Base, _Digraph>();
  1274           typename _Digraph::NodeNotifier& nn
  1275             = digraph.notifier(typename _Digraph::Node());
  1276 
  1277           typename _Digraph::ArcNotifier& en
  1278             = digraph.notifier(typename _Digraph::Arc());
  1279 
  1280           ::lemon::ignore_unused_variable_warning(nn);
  1281           ::lemon::ignore_unused_variable_warning(en);
  1282         }
  1283 
  1284         const _Digraph& digraph;
  1285         Constraints() {}
  1286       };
  1287     };
  1288 
  1289     /// \brief Skeleton class for alterable undirected graphs.
  1290     ///
  1291     /// This class describes the interface of alterable undirected
  1292     /// graphs. It extends \ref AlterableDigraphComponent with the alteration
  1293     /// notifier interface of undirected graphs. It implements
  1294     /// an observer-notifier pattern for the edges. More
  1295     /// obsevers can be registered into the notifier and whenever an
  1296     /// alteration occured in the graph all the observers will be
  1297     /// notified about it.
  1298     template <typename BAS = BaseGraphComponent>
  1299     class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
  1300     public:
  1301 
  1302       typedef BAS Base;
  1303       typedef AlterableDigraphComponent<Base> Parent;
  1304       typedef typename Base::Edge Edge;
  1305 
  1306 
  1307       /// Edge alteration notifier class.
  1308       typedef AlterationNotifier<AlterableGraphComponent, Edge>
  1309       EdgeNotifier;
  1310 
  1311       mutable EdgeNotifier edge_notifier;
  1312 
  1313       using Parent::notifier;
  1314 
  1315       /// \brief Return the edge alteration notifier.
  1316       ///
  1317       /// This function gives back the edge alteration notifier.
  1318       EdgeNotifier& notifier(Edge) const {
  1319         return edge_notifier;
  1320       }
  1321 
  1322       template <typename _Graph>
  1323       struct Constraints {
  1324         void constraints() {
  1325           checkConcept<AlterableDigraphComponent<Base>, _Graph>();
  1326           typename _Graph::EdgeNotifier& uen
  1327             = graph.notifier(typename _Graph::Edge());
  1328           ::lemon::ignore_unused_variable_warning(uen);
  1329         }
  1330 
  1331         const _Graph& graph;
  1332         Constraints() {}
  1333       };
  1334     };
  1335 
  1336     /// \brief Skeleton class for alterable undirected bipartite graphs.
  1337     ///
  1338     /// This class describes the interface of alterable undirected
  1339     /// bipartite graphs. It extends \ref AlterableGraphComponent with
  1340     /// the alteration notifier interface of bipartite graphs. It
  1341     /// implements an observer-notifier pattern for the red and blue
  1342     /// nodes. More obsevers can be registered into the notifier and
  1343     /// whenever an alteration occured in the graph all the observers
  1344     /// will be notified about it.
  1345     template <typename BAS = BaseBpGraphComponent>
  1346     class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
  1347     public:
  1348 
  1349       typedef BAS Base;
  1350       typedef AlterableGraphComponent<Base> Parent;
  1351       typedef typename Base::RedNode RedNode;
  1352       typedef typename Base::BlueNode BlueNode;
  1353 
  1354 
  1355       /// Red node alteration notifier class.
  1356       typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
  1357       RedNodeNotifier;
  1358 
  1359       /// Blue node alteration notifier class.
  1360       typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
  1361       BlueNodeNotifier;
  1362 
  1363       mutable RedNodeNotifier red_node_notifier;
  1364       mutable BlueNodeNotifier blue_node_notifier;
  1365 
  1366       using Parent::notifier;
  1367 
  1368       /// \brief Return the red node alteration notifier.
  1369       ///
  1370       /// This function gives back the red node alteration notifier.
  1371       RedNodeNotifier& notifier(RedNode) const {
  1372         return red_node_notifier;
  1373       }
  1374 
  1375       /// \brief Return the blue node alteration notifier.
  1376       ///
  1377       /// This function gives back the blue node alteration notifier.
  1378       BlueNodeNotifier& notifier(BlueNode) const {
  1379         return blue_node_notifier;
  1380       }
  1381 
  1382       template <typename _BpGraph>
  1383       struct Constraints {
  1384         void constraints() {
  1385           checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
  1386           typename _BpGraph::RedNodeNotifier& rnn
  1387             = bpgraph.notifier(typename _BpGraph::RedNode());
  1388           typename _BpGraph::BlueNodeNotifier& bnn
  1389             = bpgraph.notifier(typename _BpGraph::BlueNode());
  1390           ::lemon::ignore_unused_variable_warning(rnn);
  1391           ::lemon::ignore_unused_variable_warning(bnn);
  1392         }
  1393 
  1394         const _BpGraph& bpgraph;
  1395       };
  1396     };
  1397 
  1398     /// \brief Concept class for standard graph maps.
  1399     ///
  1400     /// This class describes the concept of standard graph maps, i.e.
  1401     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
  1402     /// graph types, which can be used for associating data to graph items.
  1403     /// The standard graph maps must conform to the ReferenceMap concept.
  1404     template <typename GR, typename K, typename V>
  1405     class GraphMap : public ReferenceMap<K, V, V&, const V&> {
  1406       typedef ReferenceMap<K, V, V&, const V&> Parent;
  1407 
  1408     public:
  1409 
  1410       /// The key type of the map.
  1411       typedef K Key;
  1412       /// The value type of the map.
  1413       typedef V Value;
  1414       /// The reference type of the map.
  1415       typedef Value& Reference;
  1416       /// The const reference type of the map.
  1417       typedef const Value& ConstReference;
  1418 
  1419       // The reference map tag.
  1420       typedef True ReferenceMapTag;
  1421 
  1422       /// \brief Construct a new map.
  1423       ///
  1424       /// Construct a new map for the graph.
  1425       explicit GraphMap(const GR&) {}
  1426       /// \brief Construct a new map with default value.
  1427       ///
  1428       /// Construct a new map for the graph and initalize the values.
  1429       GraphMap(const GR&, const Value&) {}
  1430 
  1431     private:
  1432       /// \brief Copy constructor.
  1433       ///
  1434       /// Copy Constructor.
  1435       GraphMap(const GraphMap&) : Parent() {}
  1436 
  1437       /// \brief Assignment operator.
  1438       ///
  1439       /// Assignment operator. It does not mofify the underlying graph,
  1440       /// it just iterates on the current item set and set the  map
  1441       /// with the value returned by the assigned map.
  1442       template <typename CMap>
  1443       GraphMap& operator=(const CMap&) {
  1444         checkConcept<ReadMap<Key, Value>, CMap>();
  1445         return *this;
  1446       }
  1447 
  1448     public:
  1449       template<typename _Map>
  1450       struct Constraints {
  1451         void constraints() {
  1452           checkConcept
  1453             <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
  1454           _Map m1(g);
  1455           _Map m2(g,t);
  1456 
  1457           // Copy constructor
  1458           // _Map m3(m);
  1459 
  1460           // Assignment operator
  1461           // ReadMap<Key, Value> cmap;
  1462           // m3 = cmap;
  1463 
  1464           ::lemon::ignore_unused_variable_warning(m1);
  1465           ::lemon::ignore_unused_variable_warning(m2);
  1466           // ::lemon::ignore_unused_variable_warning(m3);
  1467         }
  1468 
  1469         const _Map &m;
  1470         const GR &g;
  1471         const typename GraphMap::Value &t;
  1472         Constraints() {}
  1473       };
  1474 
  1475     };
  1476 
  1477     /// \brief Skeleton class for mappable directed graphs.
  1478     ///
  1479     /// This class describes the interface of mappable directed graphs.
  1480     /// It extends \ref BaseDigraphComponent with the standard digraph
  1481     /// map classes, namely \c NodeMap and \c ArcMap.
  1482     /// This concept is part of the Digraph concept.
  1483     template <typename BAS = BaseDigraphComponent>
  1484     class MappableDigraphComponent : public BAS  {
  1485     public:
  1486 
  1487       typedef BAS Base;
  1488       typedef typename Base::Node Node;
  1489       typedef typename Base::Arc Arc;
  1490 
  1491       typedef MappableDigraphComponent Digraph;
  1492 
  1493       /// \brief Standard graph map for the nodes.
  1494       ///
  1495       /// Standard graph map for the nodes.
  1496       /// It conforms to the ReferenceMap concept.
  1497       template <typename V>
  1498       class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
  1499         typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
  1500 
  1501       public:
  1502         /// \brief Construct a new map.
  1503         ///
  1504         /// Construct a new map for the digraph.
  1505         explicit NodeMap(const MappableDigraphComponent& digraph)
  1506           : Parent(digraph) {}
  1507 
  1508         /// \brief Construct a new map with default value.
  1509         ///
  1510         /// Construct a new map for the digraph and initalize the values.
  1511         NodeMap(const MappableDigraphComponent& digraph, const V& value)
  1512           : Parent(digraph, value) {}
  1513 
  1514       private:
  1515         /// \brief Copy constructor.
  1516         ///
  1517         /// Copy Constructor.
  1518         NodeMap(const NodeMap& nm) : Parent(nm) {}
  1519 
  1520         /// \brief Assignment operator.
  1521         ///
  1522         /// Assignment operator.
  1523         template <typename CMap>
  1524         NodeMap& operator=(const CMap&) {
  1525           checkConcept<ReadMap<Node, V>, CMap>();
  1526           return *this;
  1527         }
  1528 
  1529       };
  1530 
  1531       /// \brief Standard graph map for the arcs.
  1532       ///
  1533       /// Standard graph map for the arcs.
  1534       /// It conforms to the ReferenceMap concept.
  1535       template <typename V>
  1536       class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
  1537         typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
  1538 
  1539       public:
  1540         /// \brief Construct a new map.
  1541         ///
  1542         /// Construct a new map for the digraph.
  1543         explicit ArcMap(const MappableDigraphComponent& digraph)
  1544           : Parent(digraph) {}
  1545 
  1546         /// \brief Construct a new map with default value.
  1547         ///
  1548         /// Construct a new map for the digraph and initalize the values.
  1549         ArcMap(const MappableDigraphComponent& digraph, const V& value)
  1550           : Parent(digraph, value) {}
  1551 
  1552       private:
  1553         /// \brief Copy constructor.
  1554         ///
  1555         /// Copy Constructor.
  1556         ArcMap(const ArcMap& nm) : Parent(nm) {}
  1557 
  1558         /// \brief Assignment operator.
  1559         ///
  1560         /// Assignment operator.
  1561         template <typename CMap>
  1562         ArcMap& operator=(const CMap&) {
  1563           checkConcept<ReadMap<Arc, V>, CMap>();
  1564           return *this;
  1565         }
  1566 
  1567       };
  1568 
  1569 
  1570       template <typename _Digraph>
  1571       struct Constraints {
  1572 
  1573         struct Dummy {
  1574           int value;
  1575           Dummy() : value(0) {}
  1576           Dummy(int _v) : value(_v) {}
  1577         };
  1578 
  1579         void constraints() {
  1580           checkConcept<Base, _Digraph>();
  1581           { // int map test
  1582             typedef typename _Digraph::template NodeMap<int> IntNodeMap;
  1583             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
  1584               IntNodeMap >();
  1585           } { // bool map test
  1586             typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
  1587             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
  1588               BoolNodeMap >();
  1589           } { // Dummy map test
  1590             typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
  1591             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
  1592               DummyNodeMap >();
  1593           }
  1594 
  1595           { // int map test
  1596             typedef typename _Digraph::template ArcMap<int> IntArcMap;
  1597             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
  1598               IntArcMap >();
  1599           } { // bool map test
  1600             typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
  1601             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
  1602               BoolArcMap >();
  1603           } { // Dummy map test
  1604             typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
  1605             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
  1606               DummyArcMap >();
  1607           }
  1608         }
  1609 
  1610         const _Digraph& digraph;
  1611         Constraints() {}
  1612       };
  1613     };
  1614 
  1615     /// \brief Skeleton class for mappable undirected graphs.
  1616     ///
  1617     /// This class describes the interface of mappable undirected graphs.
  1618     /// It extends \ref MappableDigraphComponent with the standard graph
  1619     /// map class for edges (\c EdgeMap).
  1620     /// This concept is part of the Graph concept.
  1621     template <typename BAS = BaseGraphComponent>
  1622     class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
  1623     public:
  1624 
  1625       typedef BAS Base;
  1626       typedef typename Base::Edge Edge;
  1627 
  1628       typedef MappableGraphComponent Graph;
  1629 
  1630       /// \brief Standard graph map for the edges.
  1631       ///
  1632       /// Standard graph map for the edges.
  1633       /// It conforms to the ReferenceMap concept.
  1634       template <typename V>
  1635       class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
  1636         typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
  1637 
  1638       public:
  1639         /// \brief Construct a new map.
  1640         ///
  1641         /// Construct a new map for the graph.
  1642         explicit EdgeMap(const MappableGraphComponent& graph)
  1643           : Parent(graph) {}
  1644 
  1645         /// \brief Construct a new map with default value.
  1646         ///
  1647         /// Construct a new map for the graph and initalize the values.
  1648         EdgeMap(const MappableGraphComponent& graph, const V& value)
  1649           : Parent(graph, value) {}
  1650 
  1651       private:
  1652         /// \brief Copy constructor.
  1653         ///
  1654         /// Copy Constructor.
  1655         EdgeMap(const EdgeMap& nm) : Parent(nm) {}
  1656 
  1657         /// \brief Assignment operator.
  1658         ///
  1659         /// Assignment operator.
  1660         template <typename CMap>
  1661         EdgeMap& operator=(const CMap&) {
  1662           checkConcept<ReadMap<Edge, V>, CMap>();
  1663           return *this;
  1664         }
  1665 
  1666       };
  1667 
  1668 
  1669       template <typename _Graph>
  1670       struct Constraints {
  1671 
  1672         struct Dummy {
  1673           int value;
  1674           Dummy() : value(0) {}
  1675           Dummy(int _v) : value(_v) {}
  1676         };
  1677 
  1678         void constraints() {
  1679           checkConcept<MappableDigraphComponent<Base>, _Graph>();
  1680 
  1681           { // int map test
  1682             typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
  1683             checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
  1684               IntEdgeMap >();
  1685           } { // bool map test
  1686             typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
  1687             checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
  1688               BoolEdgeMap >();
  1689           } { // Dummy map test
  1690             typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
  1691             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
  1692               DummyEdgeMap >();
  1693           }
  1694         }
  1695 
  1696         const _Graph& graph;
  1697         Constraints() {}
  1698       };
  1699     };
  1700 
  1701     /// \brief Skeleton class for mappable undirected bipartite graphs.
  1702     ///
  1703     /// This class describes the interface of mappable undirected
  1704     /// bipartite graphs.  It extends \ref MappableGraphComponent with
  1705     /// the standard graph map class for red and blue nodes (\c
  1706     /// RedNodeMap and BlueNodeMap). This concept is part of the
  1707     /// BpGraph concept.
  1708     template <typename BAS = BaseBpGraphComponent>
  1709     class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
  1710     public:
  1711 
  1712       typedef BAS Base;
  1713       typedef typename Base::Node Node;
  1714 
  1715       typedef MappableBpGraphComponent BpGraph;
  1716 
  1717       /// \brief Standard graph map for the red nodes.
  1718       ///
  1719       /// Standard graph map for the red nodes.
  1720       /// It conforms to the ReferenceMap concept.
  1721       template <typename V>
  1722       class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
  1723         typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
  1724 
  1725       public:
  1726         /// \brief Construct a new map.
  1727         ///
  1728         /// Construct a new map for the graph.
  1729         explicit RedNodeMap(const MappableBpGraphComponent& graph)
  1730           : Parent(graph) {}
  1731 
  1732         /// \brief Construct a new map with default value.
  1733         ///
  1734         /// Construct a new map for the graph and initalize the values.
  1735         RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
  1736           : Parent(graph, value) {}
  1737 
  1738       private:
  1739         /// \brief Copy constructor.
  1740         ///
  1741         /// Copy Constructor.
  1742         RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
  1743 
  1744         /// \brief Assignment operator.
  1745         ///
  1746         /// Assignment operator.
  1747         template <typename CMap>
  1748         RedNodeMap& operator=(const CMap&) {
  1749           checkConcept<ReadMap<Node, V>, CMap>();
  1750           return *this;
  1751         }
  1752 
  1753       };
  1754 
  1755       /// \brief Standard graph map for the blue nodes.
  1756       ///
  1757       /// Standard graph map for the blue nodes.
  1758       /// It conforms to the ReferenceMap concept.
  1759       template <typename V>
  1760       class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
  1761         typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
  1762 
  1763       public:
  1764         /// \brief Construct a new map.
  1765         ///
  1766         /// Construct a new map for the graph.
  1767         explicit BlueNodeMap(const MappableBpGraphComponent& graph)
  1768           : Parent(graph) {}
  1769 
  1770         /// \brief Construct a new map with default value.
  1771         ///
  1772         /// Construct a new map for the graph and initalize the values.
  1773         BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
  1774           : Parent(graph, value) {}
  1775 
  1776       private:
  1777         /// \brief Copy constructor.
  1778         ///
  1779         /// Copy Constructor.
  1780         BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
  1781 
  1782         /// \brief Assignment operator.
  1783         ///
  1784         /// Assignment operator.
  1785         template <typename CMap>
  1786         BlueNodeMap& operator=(const CMap&) {
  1787           checkConcept<ReadMap<Node, V>, CMap>();
  1788           return *this;
  1789         }
  1790 
  1791       };
  1792 
  1793 
  1794       template <typename _BpGraph>
  1795       struct Constraints {
  1796 
  1797         struct Dummy {
  1798           int value;
  1799           Dummy() : value(0) {}
  1800           Dummy(int _v) : value(_v) {}
  1801         };
  1802 
  1803         void constraints() {
  1804           checkConcept<MappableGraphComponent<Base>, _BpGraph>();
  1805 
  1806           { // int map test
  1807             typedef typename _BpGraph::template RedNodeMap<int>
  1808               IntRedNodeMap;
  1809             checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
  1810               IntRedNodeMap >();
  1811           } { // bool map test
  1812             typedef typename _BpGraph::template RedNodeMap<bool>
  1813               BoolRedNodeMap;
  1814             checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
  1815               BoolRedNodeMap >();
  1816           } { // Dummy map test
  1817             typedef typename _BpGraph::template RedNodeMap<Dummy>
  1818               DummyRedNodeMap;
  1819             checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
  1820               DummyRedNodeMap >();
  1821           }
  1822 
  1823           { // int map test
  1824             typedef typename _BpGraph::template BlueNodeMap<int>
  1825               IntBlueNodeMap;
  1826             checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
  1827               IntBlueNodeMap >();
  1828           } { // bool map test
  1829             typedef typename _BpGraph::template BlueNodeMap<bool>
  1830               BoolBlueNodeMap;
  1831             checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
  1832               BoolBlueNodeMap >();
  1833           } { // Dummy map test
  1834             typedef typename _BpGraph::template BlueNodeMap<Dummy>
  1835               DummyBlueNodeMap;
  1836             checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
  1837               DummyBlueNodeMap >();
  1838           }
  1839         }
  1840 
  1841         const _BpGraph& bpgraph;
  1842       };
  1843     };
  1844 
  1845     /// \brief Skeleton class for extendable directed graphs.
  1846     ///
  1847     /// This class describes the interface of extendable directed graphs.
  1848     /// It extends \ref BaseDigraphComponent with functions for adding
  1849     /// nodes and arcs to the digraph.
  1850     /// This concept requires \ref AlterableDigraphComponent.
  1851     template <typename BAS = BaseDigraphComponent>
  1852     class ExtendableDigraphComponent : public BAS {
  1853     public:
  1854       typedef BAS Base;
  1855 
  1856       typedef typename Base::Node Node;
  1857       typedef typename Base::Arc Arc;
  1858 
  1859       /// \brief Add a new node to the digraph.
  1860       ///
  1861       /// This function adds a new node to the digraph.
  1862       Node addNode() {
  1863         return INVALID;
  1864       }
  1865 
  1866       /// \brief Add a new arc connecting the given two nodes.
  1867       ///
  1868       /// This function adds a new arc connecting the given two nodes
  1869       /// of the digraph.
  1870       Arc addArc(const Node&, const Node&) {
  1871         return INVALID;
  1872       }
  1873 
  1874       template <typename _Digraph>
  1875       struct Constraints {
  1876         void constraints() {
  1877           checkConcept<Base, _Digraph>();
  1878           typename _Digraph::Node node_a, node_b;
  1879           node_a = digraph.addNode();
  1880           node_b = digraph.addNode();
  1881           typename _Digraph::Arc arc;
  1882           arc = digraph.addArc(node_a, node_b);
  1883         }
  1884 
  1885         _Digraph& digraph;
  1886         Constraints() {}
  1887       };
  1888     };
  1889 
  1890     /// \brief Skeleton class for extendable undirected graphs.
  1891     ///
  1892     /// This class describes the interface of extendable undirected graphs.
  1893     /// It extends \ref BaseGraphComponent with functions for adding
  1894     /// nodes and edges to the graph.
  1895     /// This concept requires \ref AlterableGraphComponent.
  1896     template <typename BAS = BaseGraphComponent>
  1897     class ExtendableGraphComponent : public BAS {
  1898     public:
  1899 
  1900       typedef BAS Base;
  1901       typedef typename Base::Node Node;
  1902       typedef typename Base::Edge Edge;
  1903 
  1904       /// \brief Add a new node to the digraph.
  1905       ///
  1906       /// This function adds a new node to the digraph.
  1907       Node addNode() {
  1908         return INVALID;
  1909       }
  1910 
  1911       /// \brief Add a new edge connecting the given two nodes.
  1912       ///
  1913       /// This function adds a new edge connecting the given two nodes
  1914       /// of the graph.
  1915       Edge addEdge(const Node&, const Node&) {
  1916         return INVALID;
  1917       }
  1918 
  1919       template <typename _Graph>
  1920       struct Constraints {
  1921         void constraints() {
  1922           checkConcept<Base, _Graph>();
  1923           typename _Graph::Node node_a, node_b;
  1924           node_a = graph.addNode();
  1925           node_b = graph.addNode();
  1926           typename _Graph::Edge edge;
  1927           edge = graph.addEdge(node_a, node_b);
  1928         }
  1929 
  1930         _Graph& graph;
  1931         Constraints() {}
  1932       };
  1933     };
  1934 
  1935     /// \brief Skeleton class for extendable undirected bipartite graphs.
  1936     ///
  1937     /// This class describes the interface of extendable undirected
  1938     /// bipartite graphs. It extends \ref BaseGraphComponent with
  1939     /// functions for adding nodes and edges to the graph. This
  1940     /// concept requires \ref AlterableBpGraphComponent.
  1941     template <typename BAS = BaseBpGraphComponent>
  1942     class ExtendableBpGraphComponent : public BAS {
  1943     public:
  1944 
  1945       typedef BAS Base;
  1946       typedef typename Base::Node Node;
  1947       typedef typename Base::RedNode RedNode;
  1948       typedef typename Base::BlueNode BlueNode;
  1949       typedef typename Base::Edge Edge;
  1950 
  1951       /// \brief Add a new red node to the digraph.
  1952       ///
  1953       /// This function adds a red new node to the digraph.
  1954       RedNode addRedNode() {
  1955         return INVALID;
  1956       }
  1957 
  1958       /// \brief Add a new blue node to the digraph.
  1959       ///
  1960       /// This function adds a blue new node to the digraph.
  1961       BlueNode addBlueNode() {
  1962         return INVALID;
  1963       }
  1964 
  1965       /// \brief Add a new edge connecting the given two nodes.
  1966       ///
  1967       /// This function adds a new edge connecting the given two nodes
  1968       /// of the graph. The first node has to be a red node, and the
  1969       /// second one a blue node.
  1970       Edge addEdge(const RedNode&, const BlueNode&) {
  1971         return INVALID;
  1972       }
  1973       Edge addEdge(const BlueNode&, const RedNode&) {
  1974         return INVALID;
  1975       }
  1976 
  1977       template <typename _BpGraph>
  1978       struct Constraints {
  1979         void constraints() {
  1980           checkConcept<Base, _BpGraph>();
  1981           typename _BpGraph::RedNode red_node;
  1982           typename _BpGraph::BlueNode blue_node;
  1983           red_node = bpgraph.addRedNode();
  1984           blue_node = bpgraph.addBlueNode();
  1985           typename _BpGraph::Edge edge;
  1986           edge = bpgraph.addEdge(red_node, blue_node);
  1987           edge = bpgraph.addEdge(blue_node, red_node);
  1988         }
  1989 
  1990         _BpGraph& bpgraph;
  1991       };
  1992     };
  1993 
  1994     /// \brief Skeleton class for erasable directed graphs.
  1995     ///
  1996     /// This class describes the interface of erasable directed graphs.
  1997     /// It extends \ref BaseDigraphComponent with functions for removing
  1998     /// nodes and arcs from the digraph.
  1999     /// This concept requires \ref AlterableDigraphComponent.
  2000     template <typename BAS = BaseDigraphComponent>
  2001     class ErasableDigraphComponent : public BAS {
  2002     public:
  2003 
  2004       typedef BAS Base;
  2005       typedef typename Base::Node Node;
  2006       typedef typename Base::Arc Arc;
  2007 
  2008       /// \brief Erase a node from the digraph.
  2009       ///
  2010       /// This function erases the given node from the digraph and all arcs
  2011       /// connected to the node.
  2012       void erase(const Node&) {}
  2013 
  2014       /// \brief Erase an arc from the digraph.
  2015       ///
  2016       /// This function erases the given arc from the digraph.
  2017       void erase(const Arc&) {}
  2018 
  2019       template <typename _Digraph>
  2020       struct Constraints {
  2021         void constraints() {
  2022           checkConcept<Base, _Digraph>();
  2023           const typename _Digraph::Node node(INVALID);
  2024           digraph.erase(node);
  2025           const typename _Digraph::Arc arc(INVALID);
  2026           digraph.erase(arc);
  2027         }
  2028 
  2029         _Digraph& digraph;
  2030         Constraints() {}
  2031       };
  2032     };
  2033 
  2034     /// \brief Skeleton class for erasable undirected graphs.
  2035     ///
  2036     /// This class describes the interface of erasable undirected graphs.
  2037     /// It extends \ref BaseGraphComponent with functions for removing
  2038     /// nodes and edges from the graph.
  2039     /// This concept requires \ref AlterableGraphComponent.
  2040     template <typename BAS = BaseGraphComponent>
  2041     class ErasableGraphComponent : public BAS {
  2042     public:
  2043 
  2044       typedef BAS Base;
  2045       typedef typename Base::Node Node;
  2046       typedef typename Base::Edge Edge;
  2047 
  2048       /// \brief Erase a node from the graph.
  2049       ///
  2050       /// This function erases the given node from the graph and all edges
  2051       /// connected to the node.
  2052       void erase(const Node&) {}
  2053 
  2054       /// \brief Erase an edge from the digraph.
  2055       ///
  2056       /// This function erases the given edge from the digraph.
  2057       void erase(const Edge&) {}
  2058 
  2059       template <typename _Graph>
  2060       struct Constraints {
  2061         void constraints() {
  2062           checkConcept<Base, _Graph>();
  2063           const typename _Graph::Node node(INVALID);
  2064           graph.erase(node);
  2065           const typename _Graph::Edge edge(INVALID);
  2066           graph.erase(edge);
  2067         }
  2068 
  2069         _Graph& graph;
  2070         Constraints() {}
  2071       };
  2072     };
  2073 
  2074     /// \brief Skeleton class for erasable undirected graphs.
  2075     ///
  2076     /// This class describes the interface of erasable undirected
  2077     /// bipartite graphs. It extends \ref BaseBpGraphComponent with
  2078     /// functions for removing nodes and edges from the graph. This
  2079     /// concept requires \ref AlterableBpGraphComponent.
  2080     template <typename BAS = BaseBpGraphComponent>
  2081     class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
  2082 
  2083     /// \brief Skeleton class for clearable directed graphs.
  2084     ///
  2085     /// This class describes the interface of clearable directed graphs.
  2086     /// It extends \ref BaseDigraphComponent with a function for clearing
  2087     /// the digraph.
  2088     /// This concept requires \ref AlterableDigraphComponent.
  2089     template <typename BAS = BaseDigraphComponent>
  2090     class ClearableDigraphComponent : public BAS {
  2091     public:
  2092 
  2093       typedef BAS Base;
  2094 
  2095       /// \brief Erase all nodes and arcs from the digraph.
  2096       ///
  2097       /// This function erases all nodes and arcs from the digraph.
  2098       void clear() {}
  2099 
  2100       template <typename _Digraph>
  2101       struct Constraints {
  2102         void constraints() {
  2103           checkConcept<Base, _Digraph>();
  2104           digraph.clear();
  2105         }
  2106 
  2107         _Digraph& digraph;
  2108         Constraints() {}
  2109       };
  2110     };
  2111 
  2112     /// \brief Skeleton class for clearable undirected graphs.
  2113     ///
  2114     /// This class describes the interface of clearable undirected graphs.
  2115     /// It extends \ref BaseGraphComponent with a function for clearing
  2116     /// the graph.
  2117     /// This concept requires \ref AlterableGraphComponent.
  2118     template <typename BAS = BaseGraphComponent>
  2119     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
  2120 
  2121     /// \brief Skeleton class for clearable undirected biparite graphs.
  2122     ///
  2123     /// This class describes the interface of clearable undirected
  2124     /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
  2125     /// function for clearing the graph.  This concept requires \ref
  2126     /// AlterableBpGraphComponent.
  2127     template <typename BAS = BaseBpGraphComponent>
  2128     class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
  2129 
  2130   }
  2131 
  2132 }
  2133 
  2134 #endif