lemon/concepts/bpgraph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 13:16:27 +0100
changeset 1050 d9d1cb759951
parent 1028 4441b066368c
child 1087 dd1443e4a34c
permissions -rw-r--r--
Add images to the doc of two groups (#459)
     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 concept of undirected graphs.
    22 
    23 #ifndef LEMON_CONCEPTS_BPGRAPH_H
    24 #define LEMON_CONCEPTS_BPGRAPH_H
    25 
    26 #include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/maps.h>
    28 #include <lemon/concept_check.h>
    29 #include <lemon/core.h>
    30 
    31 namespace lemon {
    32   namespace concepts {
    33 
    34     /// \ingroup graph_concepts
    35     ///
    36     /// \brief Class describing the concept of undirected bipartite graphs.
    37     ///
    38     /// This class describes the common interface of all undirected
    39     /// bipartite graphs.
    40     ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// undirected bipartite graphs should compile with this class,
    44     /// but it will not run properly, of course.
    45     /// An actual graph implementation like \ref ListBpGraph or
    46     /// \ref SmartBpGraph may have additional functionality.
    47     ///
    48     /// The bipartite graphs also fulfill the concept of \ref Graph
    49     /// "undirected graphs". Bipartite graphs provide a bipartition of
    50     /// the node set, namely a red and blue set of the nodes. The
    51     /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
    52     /// two node sets. With RedNodeMap and BlueNodeMap values can be
    53     /// assigned to the nodes in the two sets.
    54     ///
    55     /// The edges of the graph cannot connect two nodes of the same
    56     /// set. The edges inherent orientation is from the red nodes to
    57     /// the blue nodes.
    58     ///
    59     /// \sa Graph
    60     class BpGraph {
    61     private:
    62       /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
    63       BpGraph(const BpGraph&) {}
    64       /// \brief Assignment of a graph to another one is \e not allowed.
    65       /// Use bpGraphCopy instead.
    66       void operator=(const BpGraph&) {}
    67 
    68     public:
    69       /// Default constructor.
    70       BpGraph() {}
    71 
    72       /// \brief Undirected graphs should be tagged with \c UndirectedTag.
    73       ///
    74       /// Undirected graphs should be tagged with \c UndirectedTag.
    75       ///
    76       /// This tag helps the \c enable_if technics to make compile time
    77       /// specializations for undirected graphs.
    78       typedef True UndirectedTag;
    79 
    80       /// The node type of the graph
    81 
    82       /// This class identifies a node of the graph. It also serves
    83       /// as a base class of the node iterators,
    84       /// thus they convert to this type.
    85       class Node {
    86       public:
    87         /// Default constructor
    88 
    89         /// Default constructor.
    90         /// \warning It sets the object to an undefined value.
    91         Node() { }
    92         /// Copy constructor.
    93 
    94         /// Copy constructor.
    95         ///
    96         Node(const Node&) { }
    97 
    98         /// %Invalid constructor \& conversion.
    99 
   100         /// Initializes the object to be invalid.
   101         /// \sa Invalid for more details.
   102         Node(Invalid) { }
   103         /// Equality operator
   104 
   105         /// Equality operator.
   106         ///
   107         /// Two iterators are equal if and only if they point to the
   108         /// same object or both are \c INVALID.
   109         bool operator==(Node) const { return true; }
   110 
   111         /// Inequality operator
   112 
   113         /// Inequality operator.
   114         bool operator!=(Node) const { return true; }
   115 
   116         /// Artificial ordering operator.
   117 
   118         /// Artificial ordering operator.
   119         ///
   120         /// \note This operator only has to define some strict ordering of
   121         /// the items; this order has nothing to do with the iteration
   122         /// ordering of the items.
   123         bool operator<(Node) const { return false; }
   124 
   125       };
   126 
   127       /// Class to represent red nodes.
   128 
   129       /// This class represents the red nodes of the graph. It does
   130       /// not supposed to be used directly, because the nodes can be
   131       /// represented as Node instances. This class can be used as
   132       /// template parameter for special map classes.
   133       class RedNode : public Node {
   134       public:
   135         /// Default constructor
   136 
   137         /// Default constructor.
   138         /// \warning It sets the object to an undefined value.
   139         RedNode() { }
   140         /// Copy constructor.
   141 
   142         /// Copy constructor.
   143         ///
   144         RedNode(const RedNode&) : Node() { }
   145 
   146         /// %Invalid constructor \& conversion.
   147 
   148         /// Initializes the object to be invalid.
   149         /// \sa Invalid for more details.
   150         RedNode(Invalid) { }
   151 
   152       };
   153 
   154       /// Class to represent blue nodes.
   155 
   156       /// This class represents the blue nodes of the graph. It does
   157       /// not supposed to be used directly, because the nodes can be
   158       /// represented as Node instances. This class can be used as
   159       /// template parameter for special map classes.
   160       class BlueNode : public Node {
   161       public:
   162         /// Default constructor
   163 
   164         /// Default constructor.
   165         /// \warning It sets the object to an undefined value.
   166         BlueNode() { }
   167         /// Copy constructor.
   168 
   169         /// Copy constructor.
   170         ///
   171         BlueNode(const BlueNode&) : Node() { }
   172 
   173         /// %Invalid constructor \& conversion.
   174 
   175         /// Initializes the object to be invalid.
   176         /// \sa Invalid for more details.
   177         BlueNode(Invalid) { }
   178 
   179       };
   180 
   181       /// Iterator class for the red nodes.
   182 
   183       /// This iterator goes through each red node of the graph.
   184       /// Its usage is quite simple, for example, you can count the number
   185       /// of red nodes in a graph \c g of type \c %BpGraph like this:
   186       ///\code
   187       /// int count=0;
   188       /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
   189       ///\endcode
   190       class RedNodeIt : public RedNode {
   191       public:
   192         /// Default constructor
   193 
   194         /// Default constructor.
   195         /// \warning It sets the iterator to an undefined value.
   196         RedNodeIt() { }
   197         /// Copy constructor.
   198 
   199         /// Copy constructor.
   200         ///
   201         RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
   202         /// %Invalid constructor \& conversion.
   203 
   204         /// Initializes the iterator to be invalid.
   205         /// \sa Invalid for more details.
   206         RedNodeIt(Invalid) { }
   207         /// Sets the iterator to the first red node.
   208 
   209         /// Sets the iterator to the first red node of the given
   210         /// digraph.
   211         explicit RedNodeIt(const BpGraph&) { }
   212         /// Sets the iterator to the given red node.
   213 
   214         /// Sets the iterator to the given red node of the given
   215         /// digraph.
   216         RedNodeIt(const BpGraph&, const RedNode&) { }
   217         /// Next node.
   218 
   219         /// Assign the iterator to the next red node.
   220         ///
   221         RedNodeIt& operator++() { return *this; }
   222       };
   223 
   224       /// Iterator class for the blue nodes.
   225 
   226       /// This iterator goes through each blue node of the graph.
   227       /// Its usage is quite simple, for example, you can count the number
   228       /// of blue nodes in a graph \c g of type \c %BpGraph like this:
   229       ///\code
   230       /// int count=0;
   231       /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
   232       ///\endcode
   233       class BlueNodeIt : public BlueNode {
   234       public:
   235         /// Default constructor
   236 
   237         /// Default constructor.
   238         /// \warning It sets the iterator to an undefined value.
   239         BlueNodeIt() { }
   240         /// Copy constructor.
   241 
   242         /// Copy constructor.
   243         ///
   244         BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
   245         /// %Invalid constructor \& conversion.
   246 
   247         /// Initializes the iterator to be invalid.
   248         /// \sa Invalid for more details.
   249         BlueNodeIt(Invalid) { }
   250         /// Sets the iterator to the first blue node.
   251 
   252         /// Sets the iterator to the first blue node of the given
   253         /// digraph.
   254         explicit BlueNodeIt(const BpGraph&) { }
   255         /// Sets the iterator to the given blue node.
   256 
   257         /// Sets the iterator to the given blue node of the given
   258         /// digraph.
   259         BlueNodeIt(const BpGraph&, const BlueNode&) { }
   260         /// Next node.
   261 
   262         /// Assign the iterator to the next blue node.
   263         ///
   264         BlueNodeIt& operator++() { return *this; }
   265       };
   266 
   267       /// Iterator class for the nodes.
   268 
   269       /// This iterator goes through each node of the graph.
   270       /// Its usage is quite simple, for example, you can count the number
   271       /// of nodes in a graph \c g of type \c %BpGraph like this:
   272       ///\code
   273       /// int count=0;
   274       /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
   275       ///\endcode
   276       class NodeIt : public Node {
   277       public:
   278         /// Default constructor
   279 
   280         /// Default constructor.
   281         /// \warning It sets the iterator to an undefined value.
   282         NodeIt() { }
   283         /// Copy constructor.
   284 
   285         /// Copy constructor.
   286         ///
   287         NodeIt(const NodeIt& n) : Node(n) { }
   288         /// %Invalid constructor \& conversion.
   289 
   290         /// Initializes the iterator to be invalid.
   291         /// \sa Invalid for more details.
   292         NodeIt(Invalid) { }
   293         /// Sets the iterator to the first node.
   294 
   295         /// Sets the iterator to the first node of the given digraph.
   296         ///
   297         explicit NodeIt(const BpGraph&) { }
   298         /// Sets the iterator to the given node.
   299 
   300         /// Sets the iterator to the given node of the given digraph.
   301         ///
   302         NodeIt(const BpGraph&, const Node&) { }
   303         /// Next node.
   304 
   305         /// Assign the iterator to the next node.
   306         ///
   307         NodeIt& operator++() { return *this; }
   308       };
   309 
   310 
   311       /// The edge type of the graph
   312 
   313       /// This class identifies an edge of the graph. It also serves
   314       /// as a base class of the edge iterators,
   315       /// thus they will convert to this type.
   316       class Edge {
   317       public:
   318         /// Default constructor
   319 
   320         /// Default constructor.
   321         /// \warning It sets the object to an undefined value.
   322         Edge() { }
   323         /// Copy constructor.
   324 
   325         /// Copy constructor.
   326         ///
   327         Edge(const Edge&) { }
   328         /// %Invalid constructor \& conversion.
   329 
   330         /// Initializes the object to be invalid.
   331         /// \sa Invalid for more details.
   332         Edge(Invalid) { }
   333         /// Equality operator
   334 
   335         /// Equality operator.
   336         ///
   337         /// Two iterators are equal if and only if they point to the
   338         /// same object or both are \c INVALID.
   339         bool operator==(Edge) const { return true; }
   340         /// Inequality operator
   341 
   342         /// Inequality operator.
   343         bool operator!=(Edge) const { return true; }
   344 
   345         /// Artificial ordering operator.
   346 
   347         /// Artificial ordering operator.
   348         ///
   349         /// \note This operator only has to define some strict ordering of
   350         /// the edges; this order has nothing to do with the iteration
   351         /// ordering of the edges.
   352         bool operator<(Edge) const { return false; }
   353       };
   354 
   355       /// Iterator class for the edges.
   356 
   357       /// This iterator goes through each edge of the graph.
   358       /// Its usage is quite simple, for example, you can count the number
   359       /// of edges in a graph \c g of type \c %BpGraph as follows:
   360       ///\code
   361       /// int count=0;
   362       /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
   363       ///\endcode
   364       class EdgeIt : public Edge {
   365       public:
   366         /// Default constructor
   367 
   368         /// Default constructor.
   369         /// \warning It sets the iterator to an undefined value.
   370         EdgeIt() { }
   371         /// Copy constructor.
   372 
   373         /// Copy constructor.
   374         ///
   375         EdgeIt(const EdgeIt& e) : Edge(e) { }
   376         /// %Invalid constructor \& conversion.
   377 
   378         /// Initializes the iterator to be invalid.
   379         /// \sa Invalid for more details.
   380         EdgeIt(Invalid) { }
   381         /// Sets the iterator to the first edge.
   382 
   383         /// Sets the iterator to the first edge of the given graph.
   384         ///
   385         explicit EdgeIt(const BpGraph&) { }
   386         /// Sets the iterator to the given edge.
   387 
   388         /// Sets the iterator to the given edge of the given graph.
   389         ///
   390         EdgeIt(const BpGraph&, const Edge&) { }
   391         /// Next edge
   392 
   393         /// Assign the iterator to the next edge.
   394         ///
   395         EdgeIt& operator++() { return *this; }
   396       };
   397 
   398       /// Iterator class for the incident edges of a node.
   399 
   400       /// This iterator goes trough the incident undirected edges
   401       /// of a certain node of a graph.
   402       /// Its usage is quite simple, for example, you can compute the
   403       /// degree (i.e. the number of incident edges) of a node \c n
   404       /// in a graph \c g of type \c %BpGraph as follows.
   405       ///
   406       ///\code
   407       /// int count=0;
   408       /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
   409       ///\endcode
   410       ///
   411       /// \warning Loop edges will be iterated twice.
   412       class IncEdgeIt : public Edge {
   413       public:
   414         /// Default constructor
   415 
   416         /// Default constructor.
   417         /// \warning It sets the iterator to an undefined value.
   418         IncEdgeIt() { }
   419         /// Copy constructor.
   420 
   421         /// Copy constructor.
   422         ///
   423         IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
   424         /// %Invalid constructor \& conversion.
   425 
   426         /// Initializes the iterator to be invalid.
   427         /// \sa Invalid for more details.
   428         IncEdgeIt(Invalid) { }
   429         /// Sets the iterator to the first incident edge.
   430 
   431         /// Sets the iterator to the first incident edge of the given node.
   432         ///
   433         IncEdgeIt(const BpGraph&, const Node&) { }
   434         /// Sets the iterator to the given edge.
   435 
   436         /// Sets the iterator to the given edge of the given graph.
   437         ///
   438         IncEdgeIt(const BpGraph&, const Edge&) { }
   439         /// Next incident edge
   440 
   441         /// Assign the iterator to the next incident edge
   442         /// of the corresponding node.
   443         IncEdgeIt& operator++() { return *this; }
   444       };
   445 
   446       /// The arc type of the graph
   447 
   448       /// This class identifies a directed arc of the graph. It also serves
   449       /// as a base class of the arc iterators,
   450       /// thus they will convert to this type.
   451       class Arc {
   452       public:
   453         /// Default constructor
   454 
   455         /// Default constructor.
   456         /// \warning It sets the object to an undefined value.
   457         Arc() { }
   458         /// Copy constructor.
   459 
   460         /// Copy constructor.
   461         ///
   462         Arc(const Arc&) { }
   463         /// %Invalid constructor \& conversion.
   464 
   465         /// Initializes the object to be invalid.
   466         /// \sa Invalid for more details.
   467         Arc(Invalid) { }
   468         /// Equality operator
   469 
   470         /// Equality operator.
   471         ///
   472         /// Two iterators are equal if and only if they point to the
   473         /// same object or both are \c INVALID.
   474         bool operator==(Arc) const { return true; }
   475         /// Inequality operator
   476 
   477         /// Inequality operator.
   478         bool operator!=(Arc) const { return true; }
   479 
   480         /// Artificial ordering operator.
   481 
   482         /// Artificial ordering operator.
   483         ///
   484         /// \note This operator only has to define some strict ordering of
   485         /// the arcs; this order has nothing to do with the iteration
   486         /// ordering of the arcs.
   487         bool operator<(Arc) const { return false; }
   488 
   489         /// Converison to \c Edge
   490 
   491         /// Converison to \c Edge.
   492         ///
   493         operator Edge() const { return Edge(); }
   494       };
   495 
   496       /// Iterator class for the arcs.
   497 
   498       /// This iterator goes through each directed arc of the graph.
   499       /// Its usage is quite simple, for example, you can count the number
   500       /// of arcs in a graph \c g of type \c %BpGraph as follows:
   501       ///\code
   502       /// int count=0;
   503       /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
   504       ///\endcode
   505       class ArcIt : public Arc {
   506       public:
   507         /// Default constructor
   508 
   509         /// Default constructor.
   510         /// \warning It sets the iterator to an undefined value.
   511         ArcIt() { }
   512         /// Copy constructor.
   513 
   514         /// Copy constructor.
   515         ///
   516         ArcIt(const ArcIt& e) : Arc(e) { }
   517         /// %Invalid constructor \& conversion.
   518 
   519         /// Initializes the iterator to be invalid.
   520         /// \sa Invalid for more details.
   521         ArcIt(Invalid) { }
   522         /// Sets the iterator to the first arc.
   523 
   524         /// Sets the iterator to the first arc of the given graph.
   525         ///
   526         explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
   527         /// Sets the iterator to the given arc.
   528 
   529         /// Sets the iterator to the given arc of the given graph.
   530         ///
   531         ArcIt(const BpGraph&, const Arc&) { }
   532         /// Next arc
   533 
   534         /// Assign the iterator to the next arc.
   535         ///
   536         ArcIt& operator++() { return *this; }
   537       };
   538 
   539       /// Iterator class for the outgoing arcs of a node.
   540 
   541       /// This iterator goes trough the \e outgoing directed arcs of a
   542       /// certain node of a graph.
   543       /// Its usage is quite simple, for example, you can count the number
   544       /// of outgoing arcs of a node \c n
   545       /// in a graph \c g of type \c %BpGraph as follows.
   546       ///\code
   547       /// int count=0;
   548       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
   549       ///\endcode
   550       class OutArcIt : public Arc {
   551       public:
   552         /// Default constructor
   553 
   554         /// Default constructor.
   555         /// \warning It sets the iterator to an undefined value.
   556         OutArcIt() { }
   557         /// Copy constructor.
   558 
   559         /// Copy constructor.
   560         ///
   561         OutArcIt(const OutArcIt& e) : Arc(e) { }
   562         /// %Invalid constructor \& conversion.
   563 
   564         /// Initializes the iterator to be invalid.
   565         /// \sa Invalid for more details.
   566         OutArcIt(Invalid) { }
   567         /// Sets the iterator to the first outgoing arc.
   568 
   569         /// Sets the iterator to the first outgoing arc of the given node.
   570         ///
   571         OutArcIt(const BpGraph& n, const Node& g) {
   572           ignore_unused_variable_warning(n);
   573           ignore_unused_variable_warning(g);
   574         }
   575         /// Sets the iterator to the given arc.
   576 
   577         /// Sets the iterator to the given arc of the given graph.
   578         ///
   579         OutArcIt(const BpGraph&, const Arc&) { }
   580         /// Next outgoing arc
   581 
   582         /// Assign the iterator to the next
   583         /// outgoing arc of the corresponding node.
   584         OutArcIt& operator++() { return *this; }
   585       };
   586 
   587       /// Iterator class for the incoming arcs of a node.
   588 
   589       /// This iterator goes trough the \e incoming directed arcs of a
   590       /// certain node of a graph.
   591       /// Its usage is quite simple, for example, you can count the number
   592       /// of incoming arcs of a node \c n
   593       /// in a graph \c g of type \c %BpGraph as follows.
   594       ///\code
   595       /// int count=0;
   596       /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
   597       ///\endcode
   598       class InArcIt : public Arc {
   599       public:
   600         /// Default constructor
   601 
   602         /// Default constructor.
   603         /// \warning It sets the iterator to an undefined value.
   604         InArcIt() { }
   605         /// Copy constructor.
   606 
   607         /// Copy constructor.
   608         ///
   609         InArcIt(const InArcIt& e) : Arc(e) { }
   610         /// %Invalid constructor \& conversion.
   611 
   612         /// Initializes the iterator to be invalid.
   613         /// \sa Invalid for more details.
   614         InArcIt(Invalid) { }
   615         /// Sets the iterator to the first incoming arc.
   616 
   617         /// Sets the iterator to the first incoming arc of the given node.
   618         ///
   619         InArcIt(const BpGraph& g, const Node& n) {
   620           ignore_unused_variable_warning(n);
   621           ignore_unused_variable_warning(g);
   622         }
   623         /// Sets the iterator to the given arc.
   624 
   625         /// Sets the iterator to the given arc of the given graph.
   626         ///
   627         InArcIt(const BpGraph&, const Arc&) { }
   628         /// Next incoming arc
   629 
   630         /// Assign the iterator to the next
   631         /// incoming arc of the corresponding node.
   632         InArcIt& operator++() { return *this; }
   633       };
   634 
   635       /// \brief Standard graph map type for the nodes.
   636       ///
   637       /// Standard graph map type for the nodes.
   638       /// It conforms to the ReferenceMap concept.
   639       template<class T>
   640       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
   641       {
   642       public:
   643 
   644         /// Constructor
   645         explicit NodeMap(const BpGraph&) { }
   646         /// Constructor with given initial value
   647         NodeMap(const BpGraph&, T) { }
   648 
   649       private:
   650         ///Copy constructor
   651         NodeMap(const NodeMap& nm) :
   652           ReferenceMap<Node, T, T&, const T&>(nm) { }
   653         ///Assignment operator
   654         template <typename CMap>
   655         NodeMap& operator=(const CMap&) {
   656           checkConcept<ReadMap<Node, T>, CMap>();
   657           return *this;
   658         }
   659       };
   660 
   661       /// \brief Standard graph map type for the red nodes.
   662       ///
   663       /// Standard graph map type for the red nodes.
   664       /// It conforms to the ReferenceMap concept.
   665       template<class T>
   666       class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
   667       {
   668       public:
   669 
   670         /// Constructor
   671         explicit RedNodeMap(const BpGraph&) { }
   672         /// Constructor with given initial value
   673         RedNodeMap(const BpGraph&, T) { }
   674 
   675       private:
   676         ///Copy constructor
   677         RedNodeMap(const RedNodeMap& nm) :
   678           ReferenceMap<Node, T, T&, const T&>(nm) { }
   679         ///Assignment operator
   680         template <typename CMap>
   681         RedNodeMap& operator=(const CMap&) {
   682           checkConcept<ReadMap<Node, T>, CMap>();
   683           return *this;
   684         }
   685       };
   686 
   687       /// \brief Standard graph map type for the blue nodes.
   688       ///
   689       /// Standard graph map type for the blue nodes.
   690       /// It conforms to the ReferenceMap concept.
   691       template<class T>
   692       class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
   693       {
   694       public:
   695 
   696         /// Constructor
   697         explicit BlueNodeMap(const BpGraph&) { }
   698         /// Constructor with given initial value
   699         BlueNodeMap(const BpGraph&, T) { }
   700 
   701       private:
   702         ///Copy constructor
   703         BlueNodeMap(const BlueNodeMap& nm) :
   704           ReferenceMap<Node, T, T&, const T&>(nm) { }
   705         ///Assignment operator
   706         template <typename CMap>
   707         BlueNodeMap& operator=(const CMap&) {
   708           checkConcept<ReadMap<Node, T>, CMap>();
   709           return *this;
   710         }
   711       };
   712 
   713       /// \brief Standard graph map type for the arcs.
   714       ///
   715       /// Standard graph map type for the arcs.
   716       /// It conforms to the ReferenceMap concept.
   717       template<class T>
   718       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
   719       {
   720       public:
   721 
   722         /// Constructor
   723         explicit ArcMap(const BpGraph&) { }
   724         /// Constructor with given initial value
   725         ArcMap(const BpGraph&, T) { }
   726 
   727       private:
   728         ///Copy constructor
   729         ArcMap(const ArcMap& em) :
   730           ReferenceMap<Arc, T, T&, const T&>(em) { }
   731         ///Assignment operator
   732         template <typename CMap>
   733         ArcMap& operator=(const CMap&) {
   734           checkConcept<ReadMap<Arc, T>, CMap>();
   735           return *this;
   736         }
   737       };
   738 
   739       /// \brief Standard graph map type for the edges.
   740       ///
   741       /// Standard graph map type for the edges.
   742       /// It conforms to the ReferenceMap concept.
   743       template<class T>
   744       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
   745       {
   746       public:
   747 
   748         /// Constructor
   749         explicit EdgeMap(const BpGraph&) { }
   750         /// Constructor with given initial value
   751         EdgeMap(const BpGraph&, T) { }
   752 
   753       private:
   754         ///Copy constructor
   755         EdgeMap(const EdgeMap& em) :
   756           ReferenceMap<Edge, T, T&, const T&>(em) {}
   757         ///Assignment operator
   758         template <typename CMap>
   759         EdgeMap& operator=(const CMap&) {
   760           checkConcept<ReadMap<Edge, T>, CMap>();
   761           return *this;
   762         }
   763       };
   764 
   765       /// \brief Gives back %true for red nodes.
   766       ///
   767       /// Gives back %true for red nodes.
   768       bool red(const Node&) const { return true; }
   769 
   770       /// \brief Gives back %true for blue nodes.
   771       ///
   772       /// Gives back %true for blue nodes.
   773       bool blue(const Node&) const { return true; }
   774 
   775       /// \brief Converts the node to red node object.
   776       ///
   777       /// This function converts unsafely the node to red node
   778       /// object. It should be called only if the node is from the red
   779       /// partition or INVALID.
   780       RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
   781 
   782       /// \brief Converts the node to blue node object.
   783       ///
   784       /// This function converts unsafely the node to blue node
   785       /// object. It should be called only if the node is from the red
   786       /// partition or INVALID.
   787       BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
   788 
   789       /// \brief Converts the node to red node object.
   790       ///
   791       /// This function converts safely the node to red node
   792       /// object. If the node is not from the red partition, then it
   793       /// returns INVALID.
   794       RedNode asRedNode(const Node&) const { return RedNode(); }
   795 
   796       /// \brief Converts the node to blue node object.
   797       ///
   798       /// This function converts unsafely the node to blue node
   799       /// object. If the node is not from the blue partition, then it
   800       /// returns INVALID.
   801       BlueNode asBlueNode(const Node&) const { return BlueNode(); }
   802 
   803       /// \brief Gives back the red end node of the edge.
   804       /// 
   805       /// Gives back the red end node of the edge.
   806       RedNode redNode(const Edge&) const { return RedNode(); }
   807 
   808       /// \brief Gives back the blue end node of the edge.
   809       /// 
   810       /// Gives back the blue end node of the edge.
   811       BlueNode blueNode(const Edge&) const { return BlueNode(); }
   812 
   813       /// \brief The first node of the edge.
   814       ///
   815       /// It is a synonim for the \c redNode().
   816       Node u(Edge) const { return INVALID; }
   817 
   818       /// \brief The second node of the edge.
   819       ///
   820       /// It is a synonim for the \c blueNode().
   821       Node v(Edge) const { return INVALID; }
   822 
   823       /// \brief The source node of the arc.
   824       ///
   825       /// Returns the source node of the given arc.
   826       Node source(Arc) const { return INVALID; }
   827 
   828       /// \brief The target node of the arc.
   829       ///
   830       /// Returns the target node of the given arc.
   831       Node target(Arc) const { return INVALID; }
   832 
   833       /// \brief The ID of the node.
   834       ///
   835       /// Returns the ID of the given node.
   836       int id(Node) const { return -1; }
   837 
   838       /// \brief The red ID of the node.
   839       ///
   840       /// Returns the red ID of the given node.
   841       int id(RedNode) const { return -1; }
   842 
   843       /// \brief The blue ID of the node.
   844       ///
   845       /// Returns the blue ID of the given node.
   846       int id(BlueNode) const { return -1; }
   847 
   848       /// \brief The ID of the edge.
   849       ///
   850       /// Returns the ID of the given edge.
   851       int id(Edge) const { return -1; }
   852 
   853       /// \brief The ID of the arc.
   854       ///
   855       /// Returns the ID of the given arc.
   856       int id(Arc) const { return -1; }
   857 
   858       /// \brief The node with the given ID.
   859       ///
   860       /// Returns the node with the given ID.
   861       /// \pre The argument should be a valid node ID in the graph.
   862       Node nodeFromId(int) const { return INVALID; }
   863 
   864       /// \brief The edge with the given ID.
   865       ///
   866       /// Returns the edge with the given ID.
   867       /// \pre The argument should be a valid edge ID in the graph.
   868       Edge edgeFromId(int) const { return INVALID; }
   869 
   870       /// \brief The arc with the given ID.
   871       ///
   872       /// Returns the arc with the given ID.
   873       /// \pre The argument should be a valid arc ID in the graph.
   874       Arc arcFromId(int) const { return INVALID; }
   875 
   876       /// \brief An upper bound on the node IDs.
   877       ///
   878       /// Returns an upper bound on the node IDs.
   879       int maxNodeId() const { return -1; }
   880 
   881       /// \brief An upper bound on the red IDs.
   882       ///
   883       /// Returns an upper bound on the red IDs.
   884       int maxRedId() const { return -1; }
   885 
   886       /// \brief An upper bound on the blue IDs.
   887       ///
   888       /// Returns an upper bound on the blue IDs.
   889       int maxBlueId() const { return -1; }
   890 
   891       /// \brief An upper bound on the edge IDs.
   892       ///
   893       /// Returns an upper bound on the edge IDs.
   894       int maxEdgeId() const { return -1; }
   895 
   896       /// \brief An upper bound on the arc IDs.
   897       ///
   898       /// Returns an upper bound on the arc IDs.
   899       int maxArcId() const { return -1; }
   900 
   901       /// \brief The direction of the arc.
   902       ///
   903       /// Returns \c true if the given arc goes from a red node to a blue node.
   904       bool direction(Arc) const { return true; }
   905 
   906       /// \brief Direct the edge.
   907       ///
   908       /// Direct the given edge. The returned arc
   909       /// represents the given edge and its direction comes
   910       /// from the bool parameter. If it is \c true, then the source of the node
   911       /// will be a red node.
   912       Arc direct(Edge, bool) const {
   913         return INVALID;
   914       }
   915 
   916       /// \brief Direct the edge.
   917       ///
   918       /// Direct the given edge. The returned arc represents the given
   919       /// edge and its source node is the given node.
   920       Arc direct(Edge, Node) const {
   921         return INVALID;
   922       }
   923 
   924       /// \brief The oppositely directed arc.
   925       ///
   926       /// Returns the oppositely directed arc representing the same edge.
   927       Arc oppositeArc(Arc) const { return INVALID; }
   928 
   929       /// \brief The opposite node on the edge.
   930       ///
   931       /// Returns the opposite node on the given edge.
   932       Node oppositeNode(Node, Edge) const { return INVALID; }
   933 
   934       void first(Node&) const {}
   935       void next(Node&) const {}
   936 
   937       void firstRed(RedNode&) const {}
   938       void nextRed(RedNode&) const {}
   939 
   940       void firstBlue(BlueNode&) const {}
   941       void nextBlue(BlueNode&) const {}
   942 
   943       void first(Edge&) const {}
   944       void next(Edge&) const {}
   945 
   946       void first(Arc&) const {}
   947       void next(Arc&) const {}
   948 
   949       void firstOut(Arc&, Node) const {}
   950       void nextOut(Arc&) const {}
   951 
   952       void firstIn(Arc&, Node) const {}
   953       void nextIn(Arc&) const {}
   954 
   955       void firstInc(Edge &, bool &, const Node &) const {}
   956       void nextInc(Edge &, bool &) const {}
   957 
   958       // The second parameter is dummy.
   959       Node fromId(int, Node) const { return INVALID; }
   960       // The second parameter is dummy.
   961       Edge fromId(int, Edge) const { return INVALID; }
   962       // The second parameter is dummy.
   963       Arc fromId(int, Arc) const { return INVALID; }
   964 
   965       // Dummy parameter.
   966       int maxId(Node) const { return -1; }
   967       // Dummy parameter.
   968       int maxId(RedNode) const { return -1; }
   969       // Dummy parameter.
   970       int maxId(BlueNode) const { return -1; }
   971       // Dummy parameter.
   972       int maxId(Edge) const { return -1; }
   973       // Dummy parameter.
   974       int maxId(Arc) const { return -1; }
   975 
   976       /// \brief The base node of the iterator.
   977       ///
   978       /// Returns the base node of the given incident edge iterator.
   979       Node baseNode(IncEdgeIt) const { return INVALID; }
   980 
   981       /// \brief The running node of the iterator.
   982       ///
   983       /// Returns the running node of the given incident edge iterator.
   984       Node runningNode(IncEdgeIt) const { return INVALID; }
   985 
   986       /// \brief The base node of the iterator.
   987       ///
   988       /// Returns the base node of the given outgoing arc iterator
   989       /// (i.e. the source node of the corresponding arc).
   990       Node baseNode(OutArcIt) const { return INVALID; }
   991 
   992       /// \brief The running node of the iterator.
   993       ///
   994       /// Returns the running node of the given outgoing arc iterator
   995       /// (i.e. the target node of the corresponding arc).
   996       Node runningNode(OutArcIt) const { return INVALID; }
   997 
   998       /// \brief The base node of the iterator.
   999       ///
  1000       /// Returns the base node of the given incoming arc iterator
  1001       /// (i.e. the target node of the corresponding arc).
  1002       Node baseNode(InArcIt) const { return INVALID; }
  1003 
  1004       /// \brief The running node of the iterator.
  1005       ///
  1006       /// Returns the running node of the given incoming arc iterator
  1007       /// (i.e. the source node of the corresponding arc).
  1008       Node runningNode(InArcIt) const { return INVALID; }
  1009 
  1010       template <typename _BpGraph>
  1011       struct Constraints {
  1012         void constraints() {
  1013           checkConcept<BaseBpGraphComponent, _BpGraph>();
  1014           checkConcept<IterableBpGraphComponent<>, _BpGraph>();
  1015           checkConcept<IDableBpGraphComponent<>, _BpGraph>();
  1016           checkConcept<MappableBpGraphComponent<>, _BpGraph>();
  1017         }
  1018       };
  1019 
  1020     };
  1021 
  1022   }
  1023 
  1024 }
  1025 
  1026 #endif