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