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