lemon/concepts/graph.h
changeset 58 5f1f539f912f
child 61 d718974f1290
equal deleted inserted replaced
-1:000000000000 0:1692f534aaea
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2007
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 ///\ingroup graph_concepts
       
    20 ///\file
       
    21 ///\brief The concept of Undirected Graphs.
       
    22 
       
    23 #ifndef LEMON_CONCEPT_GRAPH_H
       
    24 #define LEMON_CONCEPT_GRAPH_H
       
    25 
       
    26 #include <lemon/concepts/graph_components.h>
       
    27 #include <lemon/concepts/graph.h>
       
    28 #include <lemon/bits/utility.h>
       
    29 
       
    30 namespace lemon {
       
    31   namespace concepts {
       
    32 
       
    33     /// \ingroup graph_concepts
       
    34     ///
       
    35     /// \brief Class describing the concept of Undirected Graphs.
       
    36     ///
       
    37     /// This class describes the common interface of all Undirected
       
    38     /// Graphs.
       
    39     ///
       
    40     /// As all concept describing classes it provides only interface
       
    41     /// without any sensible implementation. So any algorithm for
       
    42     /// undirected graph should compile with this class, but it will not
       
    43     /// run properly, of course.
       
    44     ///
       
    45     /// The LEMON undirected graphs also fulfill the concept of
       
    46     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
       
    47     /// Concept"). Each edges can be seen as two opposite
       
    48     /// directed arc and consequently the undirected graph can be
       
    49     /// seen as the direceted graph of these directed arcs. The
       
    50     /// Graph has the Edge inner class for the edges and
       
    51     /// the Arc type for the directed arcs. The Arc type is
       
    52     /// convertible to Edge or inherited from it so from a directed
       
    53     /// arc we can get the represented edge.
       
    54     ///
       
    55     /// In the sense of the LEMON each edge has a default
       
    56     /// direction (it should be in every computer implementation,
       
    57     /// because the order of edge's nodes defines an
       
    58     /// orientation). With the default orientation we can define that
       
    59     /// the directed arc is forward or backward directed. With the \c
       
    60     /// direction() and \c direct() function we can get the direction
       
    61     /// of the directed arc and we can direct an edge.
       
    62     ///
       
    63     /// The EdgeIt is an iterator for the edges. We can use
       
    64     /// the EdgeMap to map values for the edges. The InArcIt and
       
    65     /// OutArcIt iterates on the same edges but with opposite
       
    66     /// direction. The IncArcIt iterates also on the same edges
       
    67     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
       
    68     /// to Edge.  
       
    69     class Graph {
       
    70     public:
       
    71       /// \brief The undirected graph should be tagged by the
       
    72       /// UndirectedTag.
       
    73       ///
       
    74       /// The undirected graph should be tagged by the UndirectedTag. This
       
    75       /// tag helps the enable_if technics to make compile time 
       
    76       /// specializations for undirected graphs.  
       
    77       typedef True UndirectedTag;
       
    78 
       
    79       /// \brief The base type of node iterators, 
       
    80       /// or in other words, the trivial node iterator.
       
    81       ///
       
    82       /// This is the base type of each node iterator,
       
    83       /// thus each kind of node iterator converts to this.
       
    84       /// More precisely each kind of node iterator should be inherited 
       
    85       /// from the trivial node iterator.
       
    86       class Node {
       
    87       public:
       
    88         /// Default constructor
       
    89 
       
    90         /// @warning The default constructor sets the iterator
       
    91         /// to an undefined value.
       
    92         Node() { }
       
    93         /// Copy constructor.
       
    94 
       
    95         /// Copy constructor.
       
    96         ///
       
    97         Node(const Node&) { }
       
    98 
       
    99         /// Invalid constructor \& conversion.
       
   100 
       
   101         /// This constructor initializes the iterator to be invalid.
       
   102         /// \sa Invalid for more details.
       
   103         Node(Invalid) { }
       
   104         /// Equality operator
       
   105 
       
   106         /// Two iterators are equal if and only if they point to the
       
   107         /// same object or both are invalid.
       
   108         bool operator==(Node) const { return true; }
       
   109 
       
   110         /// Inequality operator
       
   111         
       
   112         /// \sa operator==(Node n)
       
   113         ///
       
   114         bool operator!=(Node) const { return true; }
       
   115 
       
   116 	/// Artificial ordering operator.
       
   117 	
       
   118 	/// To allow the use of graph descriptors as key type in std::map or
       
   119 	/// similar associative container we require this.
       
   120 	///
       
   121 	/// \note This operator only have to define some strict ordering of
       
   122 	/// the items; this order has nothing to do with the iteration
       
   123 	/// ordering of the items.
       
   124 	bool operator<(Node) const { return false; }
       
   125 
       
   126       };
       
   127     
       
   128       /// This iterator goes through each node.
       
   129 
       
   130       /// This iterator goes through each node.
       
   131       /// Its usage is quite simple, for example you can count the number
       
   132       /// of nodes in graph \c g of type \c Graph like this:
       
   133       ///\code
       
   134       /// int count=0;
       
   135       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
       
   136       ///\endcode
       
   137       class NodeIt : public Node {
       
   138       public:
       
   139         /// Default constructor
       
   140 
       
   141         /// @warning The default constructor sets the iterator
       
   142         /// to an undefined value.
       
   143         NodeIt() { }
       
   144         /// Copy constructor.
       
   145         
       
   146         /// Copy constructor.
       
   147         ///
       
   148         NodeIt(const NodeIt& n) : Node(n) { }
       
   149         /// Invalid constructor \& conversion.
       
   150 
       
   151         /// Initialize the iterator to be invalid.
       
   152         /// \sa Invalid for more details.
       
   153         NodeIt(Invalid) { }
       
   154         /// Sets the iterator to the first node.
       
   155 
       
   156         /// Sets the iterator to the first node of \c g.
       
   157         ///
       
   158         NodeIt(const Graph&) { }
       
   159         /// Node -> NodeIt conversion.
       
   160 
       
   161         /// Sets the iterator to the node of \c the graph pointed by 
       
   162 	/// the trivial iterator.
       
   163         /// This feature necessitates that each time we 
       
   164         /// iterate the arc-set, the iteration order is the same.
       
   165         NodeIt(const Graph&, const Node&) { }
       
   166         /// Next node.
       
   167 
       
   168         /// Assign the iterator to the next node.
       
   169         ///
       
   170         NodeIt& operator++() { return *this; }
       
   171       };
       
   172     
       
   173     
       
   174       /// The base type of the edge iterators.
       
   175 
       
   176       /// The base type of the edge iterators.
       
   177       ///
       
   178       class Edge {
       
   179       public:
       
   180         /// Default constructor
       
   181 
       
   182         /// @warning The default constructor sets the iterator
       
   183         /// to an undefined value.
       
   184         Edge() { }
       
   185         /// Copy constructor.
       
   186 
       
   187         /// Copy constructor.
       
   188         ///
       
   189         Edge(const Edge&) { }
       
   190         /// Initialize the iterator to be invalid.
       
   191 
       
   192         /// Initialize the iterator to be invalid.
       
   193         ///
       
   194         Edge(Invalid) { }
       
   195         /// Equality operator
       
   196 
       
   197         /// Two iterators are equal if and only if they point to the
       
   198         /// same object or both are invalid.
       
   199         bool operator==(Edge) const { return true; }
       
   200         /// Inequality operator
       
   201 
       
   202         /// \sa operator==(Edge n)
       
   203         ///
       
   204         bool operator!=(Edge) const { return true; }
       
   205 
       
   206 	/// Artificial ordering operator.
       
   207 	
       
   208 	/// To allow the use of graph descriptors as key type in std::map or
       
   209 	/// similar associative container we require this.
       
   210 	///
       
   211 	/// \note This operator only have to define some strict ordering of
       
   212 	/// the items; this order has nothing to do with the iteration
       
   213 	/// ordering of the items.
       
   214 	bool operator<(Edge) const { return false; }
       
   215       };
       
   216 
       
   217       /// This iterator goes through each edge.
       
   218 
       
   219       /// This iterator goes through each edge of a graph.
       
   220       /// Its usage is quite simple, for example you can count the number
       
   221       /// of edges in a graph \c g of type \c Graph as follows:
       
   222       ///\code
       
   223       /// int count=0;
       
   224       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
       
   225       ///\endcode
       
   226       class EdgeIt : public Edge {
       
   227       public:
       
   228         /// Default constructor
       
   229 
       
   230         /// @warning The default constructor sets the iterator
       
   231         /// to an undefined value.
       
   232         EdgeIt() { }
       
   233         /// Copy constructor.
       
   234 
       
   235         /// Copy constructor.
       
   236         ///
       
   237         EdgeIt(const EdgeIt& e) : Edge(e) { }
       
   238         /// Initialize the iterator to be invalid.
       
   239 
       
   240         /// Initialize the iterator to be invalid.
       
   241         ///
       
   242         EdgeIt(Invalid) { }
       
   243         /// This constructor sets the iterator to the first edge.
       
   244     
       
   245         /// This constructor sets the iterator to the first edge.
       
   246         EdgeIt(const Graph&) { }
       
   247         /// Edge -> EdgeIt conversion
       
   248 
       
   249         /// Sets the iterator to the value of the trivial iterator.
       
   250         /// This feature necessitates that each time we
       
   251         /// iterate the edge-set, the iteration order is the 
       
   252 	/// same.
       
   253         EdgeIt(const Graph&, const Edge&) { } 
       
   254         /// Next edge
       
   255         
       
   256         /// Assign the iterator to the next edge.
       
   257         EdgeIt& operator++() { return *this; }
       
   258       };
       
   259 
       
   260       /// \brief This iterator goes trough the incident undirected 
       
   261       /// arcs of a node.
       
   262       ///
       
   263       /// This iterator goes trough the incident edges
       
   264       /// of a certain node of a graph. You should assume that the 
       
   265       /// loop arcs will be iterated twice.
       
   266       /// 
       
   267       /// Its usage is quite simple, for example you can compute the
       
   268       /// degree (i.e. count the number of incident arcs of a node \c n
       
   269       /// in graph \c g of type \c Graph as follows. 
       
   270       ///
       
   271       ///\code
       
   272       /// int count=0;
       
   273       /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
       
   274       ///\endcode
       
   275       class IncArcIt : public Edge {
       
   276       public:
       
   277         /// Default constructor
       
   278 
       
   279         /// @warning The default constructor sets the iterator
       
   280         /// to an undefined value.
       
   281         IncArcIt() { }
       
   282         /// Copy constructor.
       
   283 
       
   284         /// Copy constructor.
       
   285         ///
       
   286         IncArcIt(const IncArcIt& e) : Edge(e) { }
       
   287         /// Initialize the iterator to be invalid.
       
   288 
       
   289         /// Initialize the iterator to be invalid.
       
   290         ///
       
   291         IncArcIt(Invalid) { }
       
   292         /// This constructor sets the iterator to first incident arc.
       
   293     
       
   294         /// This constructor set the iterator to the first incident arc of
       
   295         /// the node.
       
   296         IncArcIt(const Graph&, const Node&) { }
       
   297         /// Edge -> IncArcIt conversion
       
   298 
       
   299         /// Sets the iterator to the value of the trivial iterator \c e.
       
   300         /// This feature necessitates that each time we 
       
   301         /// iterate the arc-set, the iteration order is the same.
       
   302         IncArcIt(const Graph&, const Edge&) { }
       
   303         /// Next incident arc
       
   304 
       
   305         /// Assign the iterator to the next incident arc
       
   306 	/// of the corresponding node.
       
   307         IncArcIt& operator++() { return *this; }
       
   308       };
       
   309 
       
   310       /// The directed arc type.
       
   311 
       
   312       /// The directed arc type. It can be converted to the
       
   313       /// edge or it should be inherited from the undirected
       
   314       /// arc.
       
   315       class Arc : public Edge {
       
   316       public:
       
   317         /// Default constructor
       
   318 
       
   319         /// @warning The default constructor sets the iterator
       
   320         /// to an undefined value.
       
   321         Arc() { }
       
   322         /// Copy constructor.
       
   323 
       
   324         /// Copy constructor.
       
   325         ///
       
   326         Arc(const Arc& e) : Edge(e) { }
       
   327         /// Initialize the iterator to be invalid.
       
   328 
       
   329         /// Initialize the iterator to be invalid.
       
   330         ///
       
   331         Arc(Invalid) { }
       
   332         /// Equality operator
       
   333 
       
   334         /// Two iterators are equal if and only if they point to the
       
   335         /// same object or both are invalid.
       
   336         bool operator==(Arc) const { return true; }
       
   337         /// Inequality operator
       
   338 
       
   339         /// \sa operator==(Arc n)
       
   340         ///
       
   341         bool operator!=(Arc) const { return true; }
       
   342 
       
   343 	/// Artificial ordering operator.
       
   344 	
       
   345 	/// To allow the use of graph descriptors as key type in std::map or
       
   346 	/// similar associative container we require this.
       
   347 	///
       
   348 	/// \note This operator only have to define some strict ordering of
       
   349 	/// the items; this order has nothing to do with the iteration
       
   350 	/// ordering of the items.
       
   351 	bool operator<(Arc) const { return false; }
       
   352 	
       
   353       }; 
       
   354       /// This iterator goes through each directed arc.
       
   355 
       
   356       /// This iterator goes through each arc of a graph.
       
   357       /// Its usage is quite simple, for example you can count the number
       
   358       /// of arcs in a graph \c g of type \c Graph as follows:
       
   359       ///\code
       
   360       /// int count=0;
       
   361       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
       
   362       ///\endcode
       
   363       class ArcIt : public Arc {
       
   364       public:
       
   365         /// Default constructor
       
   366 
       
   367         /// @warning The default constructor sets the iterator
       
   368         /// to an undefined value.
       
   369         ArcIt() { }
       
   370         /// Copy constructor.
       
   371 
       
   372         /// Copy constructor.
       
   373         ///
       
   374         ArcIt(const ArcIt& e) : Arc(e) { }
       
   375         /// Initialize the iterator to be invalid.
       
   376 
       
   377         /// Initialize the iterator to be invalid.
       
   378         ///
       
   379         ArcIt(Invalid) { }
       
   380         /// This constructor sets the iterator to the first arc.
       
   381     
       
   382         /// This constructor sets the iterator to the first arc of \c g.
       
   383         ///@param g the graph
       
   384         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
       
   385         /// Arc -> ArcIt conversion
       
   386 
       
   387         /// Sets the iterator to the value of the trivial iterator \c e.
       
   388         /// This feature necessitates that each time we 
       
   389         /// iterate the arc-set, the iteration order is the same.
       
   390         ArcIt(const Graph&, const Arc&) { } 
       
   391         ///Next arc
       
   392         
       
   393         /// Assign the iterator to the next arc.
       
   394         ArcIt& operator++() { return *this; }
       
   395       };
       
   396    
       
   397       /// This iterator goes trough the outgoing directed arcs of a node.
       
   398 
       
   399       /// This iterator goes trough the \e outgoing arcs of a certain node
       
   400       /// of a graph.
       
   401       /// Its usage is quite simple, for example you can count the number
       
   402       /// of outgoing arcs of a node \c n
       
   403       /// in graph \c g of type \c Graph as follows.
       
   404       ///\code
       
   405       /// int count=0;
       
   406       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
       
   407       ///\endcode
       
   408     
       
   409       class OutArcIt : public Arc {
       
   410       public:
       
   411         /// Default constructor
       
   412 
       
   413         /// @warning The default constructor sets the iterator
       
   414         /// to an undefined value.
       
   415         OutArcIt() { }
       
   416         /// Copy constructor.
       
   417 
       
   418         /// Copy constructor.
       
   419         ///
       
   420         OutArcIt(const OutArcIt& e) : Arc(e) { }
       
   421         /// Initialize the iterator to be invalid.
       
   422 
       
   423         /// Initialize the iterator to be invalid.
       
   424         ///
       
   425         OutArcIt(Invalid) { }
       
   426         /// This constructor sets the iterator to the first outgoing arc.
       
   427     
       
   428         /// This constructor sets the iterator to the first outgoing arc of
       
   429         /// the node.
       
   430         ///@param n the node
       
   431         ///@param g the graph
       
   432         OutArcIt(const Graph& n, const Node& g) {
       
   433 	  ignore_unused_variable_warning(n);
       
   434 	  ignore_unused_variable_warning(g);
       
   435 	}
       
   436         /// Arc -> OutArcIt conversion
       
   437 
       
   438         /// Sets the iterator to the value of the trivial iterator.
       
   439 	/// This feature necessitates that each time we 
       
   440         /// iterate the arc-set, the iteration order is the same.
       
   441         OutArcIt(const Graph&, const Arc&) { }
       
   442         ///Next outgoing arc
       
   443         
       
   444         /// Assign the iterator to the next 
       
   445         /// outgoing arc of the corresponding node.
       
   446         OutArcIt& operator++() { return *this; }
       
   447       };
       
   448 
       
   449       /// This iterator goes trough the incoming directed arcs of a node.
       
   450 
       
   451       /// This iterator goes trough the \e incoming arcs of a certain node
       
   452       /// of a graph.
       
   453       /// Its usage is quite simple, for example you can count the number
       
   454       /// of outgoing arcs of a node \c n
       
   455       /// in graph \c g of type \c Graph as follows.
       
   456       ///\code
       
   457       /// int count=0;
       
   458       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
       
   459       ///\endcode
       
   460 
       
   461       class InArcIt : public Arc {
       
   462       public:
       
   463         /// Default constructor
       
   464 
       
   465         /// @warning The default constructor sets the iterator
       
   466         /// to an undefined value.
       
   467         InArcIt() { }
       
   468         /// Copy constructor.
       
   469 
       
   470         /// Copy constructor.
       
   471         ///
       
   472         InArcIt(const InArcIt& e) : Arc(e) { }
       
   473         /// Initialize the iterator to be invalid.
       
   474 
       
   475         /// Initialize the iterator to be invalid.
       
   476         ///
       
   477         InArcIt(Invalid) { }
       
   478         /// This constructor sets the iterator to first incoming arc.
       
   479     
       
   480         /// This constructor set the iterator to the first incoming arc of
       
   481         /// the node.
       
   482         ///@param n the node
       
   483         ///@param g the graph
       
   484         InArcIt(const Graph& g, const Node& n) { 
       
   485 	  ignore_unused_variable_warning(n);
       
   486 	  ignore_unused_variable_warning(g);
       
   487 	}
       
   488         /// Arc -> InArcIt conversion
       
   489 
       
   490         /// Sets the iterator to the value of the trivial iterator \c e.
       
   491         /// This feature necessitates that each time we 
       
   492         /// iterate the arc-set, the iteration order is the same.
       
   493         InArcIt(const Graph&, const Arc&) { }
       
   494         /// Next incoming arc
       
   495 
       
   496         /// Assign the iterator to the next inarc of the corresponding node.
       
   497         ///
       
   498         InArcIt& operator++() { return *this; }
       
   499       };
       
   500 
       
   501       /// \brief Read write map of the nodes to type \c T.
       
   502       /// 
       
   503       /// ReadWrite map of the nodes to type \c T.
       
   504       /// \sa Reference
       
   505       template<class T> 
       
   506       class NodeMap : public ReadWriteMap< Node, T >
       
   507       {
       
   508       public:
       
   509 
       
   510         ///\e
       
   511         NodeMap(const Graph&) { }
       
   512         ///\e
       
   513         NodeMap(const Graph&, T) { }
       
   514 
       
   515         ///Copy constructor
       
   516         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
       
   517         ///Assignment operator
       
   518         template <typename CMap>
       
   519         NodeMap& operator=(const CMap&) { 
       
   520           checkConcept<ReadMap<Node, T>, CMap>();
       
   521           return *this; 
       
   522         }
       
   523       };
       
   524 
       
   525       /// \brief Read write map of the directed arcs to type \c T.
       
   526       ///
       
   527       /// Reference map of the directed arcs to type \c T.
       
   528       /// \sa Reference
       
   529       template<class T> 
       
   530       class ArcMap : public ReadWriteMap<Arc,T>
       
   531       {
       
   532       public:
       
   533 
       
   534         ///\e
       
   535         ArcMap(const Graph&) { }
       
   536         ///\e
       
   537         ArcMap(const Graph&, T) { }
       
   538         ///Copy constructor
       
   539         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
       
   540         ///Assignment operator
       
   541         template <typename CMap>
       
   542         ArcMap& operator=(const CMap&) { 
       
   543           checkConcept<ReadMap<Arc, T>, CMap>();
       
   544           return *this; 
       
   545         }
       
   546       };
       
   547 
       
   548       /// Read write map of the edges to type \c T.
       
   549 
       
   550       /// Reference map of the arcs to type \c T.
       
   551       /// \sa Reference
       
   552       template<class T> 
       
   553       class EdgeMap : public ReadWriteMap<Edge,T>
       
   554       {
       
   555       public:
       
   556 
       
   557         ///\e
       
   558         EdgeMap(const Graph&) { }
       
   559         ///\e
       
   560         EdgeMap(const Graph&, T) { }
       
   561         ///Copy constructor
       
   562         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
       
   563         ///Assignment operator
       
   564         template <typename CMap>
       
   565         EdgeMap& operator=(const CMap&) { 
       
   566           checkConcept<ReadMap<Edge, T>, CMap>();
       
   567           return *this; 
       
   568         }
       
   569       };
       
   570 
       
   571       /// \brief Direct the given edge.
       
   572       ///
       
   573       /// Direct the given edge. The returned arc source
       
   574       /// will be the given node.
       
   575       Arc direct(const Edge&, const Node&) const {
       
   576 	return INVALID;
       
   577       }
       
   578 
       
   579       /// \brief Direct the given edge.
       
   580       ///
       
   581       /// Direct the given edge. The returned arc
       
   582       /// represents the given edge and the direction comes
       
   583       /// from the bool parameter. The source of the edge and
       
   584       /// the directed arc is the same when the given bool is true.
       
   585       Arc direct(const Edge&, bool) const {
       
   586 	return INVALID;
       
   587       }
       
   588 
       
   589       /// \brief Returns true if the arc has default orientation.
       
   590       ///
       
   591       /// Returns whether the given directed arc is same orientation as
       
   592       /// the corresponding edge's default orientation.
       
   593       bool direction(Arc) const { return true; }
       
   594 
       
   595       /// \brief Returns the opposite directed arc.
       
   596       ///
       
   597       /// Returns the opposite directed arc.
       
   598       Arc oppositeArc(Arc) const { return INVALID; }
       
   599 
       
   600       /// \brief Opposite node on an arc
       
   601       ///
       
   602       /// \return the opposite of the given Node on the given Edge
       
   603       Node oppositeNode(Node, Edge) const { return INVALID; }
       
   604 
       
   605       /// \brief First node of the edge.
       
   606       ///
       
   607       /// \return the first node of the given Edge.
       
   608       ///
       
   609       /// Naturally edges don't have direction and thus
       
   610       /// don't have source and target node. But we use these two methods
       
   611       /// to query the two nodes of the arc. The direction of the arc
       
   612       /// which arises this way is called the inherent direction of the
       
   613       /// edge, and is used to define the "default" direction
       
   614       /// of the directed versions of the arcs.
       
   615       /// \sa direction
       
   616       Node u(Edge) const { return INVALID; }
       
   617 
       
   618       /// \brief Second node of the edge.
       
   619       Node v(Edge) const { return INVALID; }
       
   620 
       
   621       /// \brief Source node of the directed arc.
       
   622       Node source(Arc) const { return INVALID; }
       
   623 
       
   624       /// \brief Target node of the directed arc.
       
   625       Node target(Arc) const { return INVALID; }
       
   626 
       
   627       void first(Node&) const {}
       
   628       void next(Node&) const {}
       
   629 
       
   630       void first(Edge&) const {}
       
   631       void next(Edge&) const {}
       
   632 
       
   633       void first(Arc&) const {}
       
   634       void next(Arc&) const {}
       
   635 
       
   636       void firstOut(Arc&, Node) const {}
       
   637       void nextOut(Arc&) const {}
       
   638 
       
   639       void firstIn(Arc&, Node) const {}
       
   640       void nextIn(Arc&) const {}
       
   641 
       
   642 
       
   643       void firstInc(Edge &, bool &, const Node &) const {}
       
   644       void nextInc(Edge &, bool &) const {}
       
   645 
       
   646       /// \brief Base node of the iterator
       
   647       ///
       
   648       /// Returns the base node (the source in this case) of the iterator
       
   649       Node baseNode(OutArcIt e) const {
       
   650 	return source(e);
       
   651       }
       
   652       /// \brief Running node of the iterator
       
   653       ///
       
   654       /// Returns the running node (the target in this case) of the
       
   655       /// iterator
       
   656       Node runningNode(OutArcIt e) const {
       
   657 	return target(e);
       
   658       }
       
   659 
       
   660       /// \brief Base node of the iterator
       
   661       ///
       
   662       /// Returns the base node (the target in this case) of the iterator
       
   663       Node baseNode(InArcIt e) const {
       
   664 	return target(e);
       
   665       }
       
   666       /// \brief Running node of the iterator
       
   667       ///
       
   668       /// Returns the running node (the source in this case) of the
       
   669       /// iterator
       
   670       Node runningNode(InArcIt e) const {
       
   671 	return source(e);
       
   672       }
       
   673 
       
   674       /// \brief Base node of the iterator
       
   675       ///
       
   676       /// Returns the base node of the iterator
       
   677       Node baseNode(IncArcIt) const {
       
   678 	return INVALID;
       
   679       }
       
   680       
       
   681       /// \brief Running node of the iterator
       
   682       ///
       
   683       /// Returns the running node of the iterator
       
   684       Node runningNode(IncArcIt) const {
       
   685 	return INVALID;
       
   686       }
       
   687 
       
   688       template <typename Graph>
       
   689       struct Constraints {
       
   690 	void constraints() {
       
   691 	  checkConcept<IterableGraphComponent<>, Graph>();
       
   692 	  checkConcept<MappableGraphComponent<>, Graph>();
       
   693 	}
       
   694       };
       
   695 
       
   696     };
       
   697 
       
   698   }
       
   699 
       
   700 }
       
   701 
       
   702 #endif