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