lemon/concepts/graph.h
author Balazs Dezso <deba@inf.elte.hu>
Tue, 02 Dec 2008 23:15:43 +0100
changeset 443 de16f1f2d228
parent 220 a5d8c039f218
child 440 88ed40ad0d4f
permissions -rw-r--r--
Rename counterSort to stableRadixSort
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     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/core.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 IncEdgeIt 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::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
   274       ///\endcode
   275       class IncEdgeIt : public Edge {
   276       public:
   277         /// Default constructor
   278 
   279         /// @warning The default constructor sets the iterator
   280         /// to an undefined value.
   281         IncEdgeIt() { }
   282         /// Copy constructor.
   283 
   284         /// Copy constructor.
   285         ///
   286         IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
   287         /// Initialize the iterator to be invalid.
   288 
   289         /// Initialize the iterator to be invalid.
   290         ///
   291         IncEdgeIt(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         IncEdgeIt(const Graph&, const Node&) { }
   297         /// Edge -> IncEdgeIt 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         IncEdgeIt(const Graph&, const Edge&) { }
   303         /// Next incident arc
   304 
   305         /// Assign the iterator to the next incident arc
   306         /// of the corresponding node.
   307         IncEdgeIt& 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       private:
   516         ///Copy constructor
   517         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   518         ///Assignment operator
   519         template <typename CMap>
   520         NodeMap& operator=(const CMap&) {
   521           checkConcept<ReadMap<Node, T>, CMap>();
   522           return *this;
   523         }
   524       };
   525 
   526       /// \brief Read write map of the directed arcs to type \c T.
   527       ///
   528       /// Reference map of the directed arcs to type \c T.
   529       /// \sa Reference
   530       template<class T>
   531       class ArcMap : public ReadWriteMap<Arc,T>
   532       {
   533       public:
   534 
   535         ///\e
   536         ArcMap(const Graph&) { }
   537         ///\e
   538         ArcMap(const Graph&, T) { }
   539       private:
   540         ///Copy constructor
   541         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   542         ///Assignment operator
   543         template <typename CMap>
   544         ArcMap& operator=(const CMap&) {
   545           checkConcept<ReadMap<Arc, T>, CMap>();
   546           return *this;
   547         }
   548       };
   549 
   550       /// Read write map of the edges to type \c T.
   551 
   552       /// Reference map of the arcs to type \c T.
   553       /// \sa Reference
   554       template<class T>
   555       class EdgeMap : public ReadWriteMap<Edge,T>
   556       {
   557       public:
   558 
   559         ///\e
   560         EdgeMap(const Graph&) { }
   561         ///\e
   562         EdgeMap(const Graph&, T) { }
   563       private:
   564         ///Copy constructor
   565         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
   566         ///Assignment operator
   567         template <typename CMap>
   568         EdgeMap& operator=(const CMap&) {
   569           checkConcept<ReadMap<Edge, T>, CMap>();
   570           return *this;
   571         }
   572       };
   573 
   574       /// \brief Direct the given edge.
   575       ///
   576       /// Direct the given edge. The returned arc source
   577       /// will be the given node.
   578       Arc direct(const Edge&, const Node&) const {
   579         return INVALID;
   580       }
   581 
   582       /// \brief Direct the given edge.
   583       ///
   584       /// Direct the given edge. The returned arc
   585       /// represents the given edge and the direction comes
   586       /// from the bool parameter. The source of the edge and
   587       /// the directed arc is the same when the given bool is true.
   588       Arc direct(const Edge&, bool) const {
   589         return INVALID;
   590       }
   591 
   592       /// \brief Returns true if the arc has default orientation.
   593       ///
   594       /// Returns whether the given directed arc is same orientation as
   595       /// the corresponding edge's default orientation.
   596       bool direction(Arc) const { return true; }
   597 
   598       /// \brief Returns the opposite directed arc.
   599       ///
   600       /// Returns the opposite directed arc.
   601       Arc oppositeArc(Arc) const { return INVALID; }
   602 
   603       /// \brief Opposite node on an arc
   604       ///
   605       /// \return the opposite of the given Node on the given Edge
   606       Node oppositeNode(Node, Edge) const { return INVALID; }
   607 
   608       /// \brief First node of the edge.
   609       ///
   610       /// \return the first node of the given Edge.
   611       ///
   612       /// Naturally edges don't have direction and thus
   613       /// don't have source and target node. But we use these two methods
   614       /// to query the two nodes of the arc. The direction of the arc
   615       /// which arises this way is called the inherent direction of the
   616       /// edge, and is used to define the "default" direction
   617       /// of the directed versions of the arcs.
   618       /// \sa direction
   619       Node u(Edge) const { return INVALID; }
   620 
   621       /// \brief Second node of the edge.
   622       Node v(Edge) const { return INVALID; }
   623 
   624       /// \brief Source node of the directed arc.
   625       Node source(Arc) const { return INVALID; }
   626 
   627       /// \brief Target node of the directed arc.
   628       Node target(Arc) const { return INVALID; }
   629 
   630       /// \brief Returns the id of the node.
   631       int id(Node) const { return -1; }
   632 
   633       /// \brief Returns the id of the edge.
   634       int id(Edge) const { return -1; }
   635 
   636       /// \brief Returns the id of the arc.
   637       int id(Arc) const { return -1; }
   638 
   639       /// \brief Returns the node with the given id.
   640       ///
   641       /// \pre The argument should be a valid node id in the graph.
   642       Node nodeFromId(int) const { return INVALID; }
   643 
   644       /// \brief Returns the edge with the given id.
   645       ///
   646       /// \pre The argument should be a valid edge id in the graph.
   647       Edge edgeFromId(int) const { return INVALID; }
   648 
   649       /// \brief Returns the arc with the given id.
   650       ///
   651       /// \pre The argument should be a valid arc id in the graph.
   652       Arc arcFromId(int) const { return INVALID; }
   653 
   654       /// \brief Returns an upper bound on the node IDs.
   655       int maxNodeId() const { return -1; }
   656 
   657       /// \brief Returns an upper bound on the edge IDs.
   658       int maxEdgeId() const { return -1; }
   659 
   660       /// \brief Returns an upper bound on the arc IDs.
   661       int maxArcId() const { return -1; }
   662 
   663       void first(Node&) const {}
   664       void next(Node&) const {}
   665 
   666       void first(Edge&) const {}
   667       void next(Edge&) const {}
   668 
   669       void first(Arc&) const {}
   670       void next(Arc&) const {}
   671 
   672       void firstOut(Arc&, Node) const {}
   673       void nextOut(Arc&) const {}
   674 
   675       void firstIn(Arc&, Node) const {}
   676       void nextIn(Arc&) const {}
   677 
   678       void firstInc(Edge &, bool &, const Node &) const {}
   679       void nextInc(Edge &, bool &) const {}
   680 
   681       // The second parameter is dummy.
   682       Node fromId(int, Node) const { return INVALID; }
   683       // The second parameter is dummy.
   684       Edge fromId(int, Edge) const { return INVALID; }
   685       // The second parameter is dummy.
   686       Arc fromId(int, Arc) const { return INVALID; }
   687 
   688       // Dummy parameter.
   689       int maxId(Node) const { return -1; }
   690       // Dummy parameter.
   691       int maxId(Edge) const { return -1; }
   692       // Dummy parameter.
   693       int maxId(Arc) const { return -1; }
   694 
   695       /// \brief Base node of the iterator
   696       ///
   697       /// Returns the base node (the source in this case) of the iterator
   698       Node baseNode(OutArcIt e) const {
   699         return source(e);
   700       }
   701       /// \brief Running node of the iterator
   702       ///
   703       /// Returns the running node (the target in this case) of the
   704       /// iterator
   705       Node runningNode(OutArcIt e) const {
   706         return target(e);
   707       }
   708 
   709       /// \brief Base node of the iterator
   710       ///
   711       /// Returns the base node (the target in this case) of the iterator
   712       Node baseNode(InArcIt e) const {
   713         return target(e);
   714       }
   715       /// \brief Running node of the iterator
   716       ///
   717       /// Returns the running node (the source in this case) of the
   718       /// iterator
   719       Node runningNode(InArcIt e) const {
   720         return source(e);
   721       }
   722 
   723       /// \brief Base node of the iterator
   724       ///
   725       /// Returns the base node of the iterator
   726       Node baseNode(IncEdgeIt) const {
   727         return INVALID;
   728       }
   729 
   730       /// \brief Running node of the iterator
   731       ///
   732       /// Returns the running node of the iterator
   733       Node runningNode(IncEdgeIt) const {
   734         return INVALID;
   735       }
   736 
   737       template <typename _Graph>
   738       struct Constraints {
   739         void constraints() {
   740           checkConcept<IterableGraphComponent<>, _Graph>();
   741           checkConcept<IDableGraphComponent<>, _Graph>();
   742           checkConcept<MappableGraphComponent<>, _Graph>();
   743         }
   744       };
   745 
   746     };
   747 
   748   }
   749 
   750 }
   751 
   752 #endif