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