lemon/concepts/graph.h
changeset 210 81cfc04531e8
parent 125 19e82bda606a
child 220 a5d8c039f218
equal deleted inserted replaced
4:1ff8cf24f3b5 5:0ba6f256cc7a
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    63     /// The EdgeIt is an iterator for the edges. We can use
    63     /// The EdgeIt is an iterator for the edges. We can use
    64     /// the EdgeMap to map values for the edges. The InArcIt and
    64     /// the EdgeMap to map values for the edges. The InArcIt and
    65     /// OutArcIt iterates on the same edges but with opposite
    65     /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncEdgeIt iterates also on the same edges
    66     /// direction. The IncEdgeIt iterates also on the same edges
    67     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    67     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    68     /// to Edge.  
    68     /// to Edge.
    69     class Graph {
    69     class Graph {
    70     public:
    70     public:
    71       /// \brief The undirected graph should be tagged by the
    71       /// \brief The undirected graph should be tagged by the
    72       /// UndirectedTag.
    72       /// UndirectedTag.
    73       ///
    73       ///
    74       /// The undirected graph should be tagged by the UndirectedTag. This
    74       /// The undirected graph should be tagged by the UndirectedTag. This
    75       /// tag helps the enable_if technics to make compile time 
    75       /// tag helps the enable_if technics to make compile time
    76       /// specializations for undirected graphs.  
    76       /// specializations for undirected graphs.
    77       typedef True UndirectedTag;
    77       typedef True UndirectedTag;
    78 
    78 
    79       /// \brief The base type of node iterators, 
    79       /// \brief The base type of node iterators,
    80       /// or in other words, the trivial node iterator.
    80       /// or in other words, the trivial node iterator.
    81       ///
    81       ///
    82       /// This is the base type of each node iterator,
    82       /// This is the base type of each node iterator,
    83       /// thus each kind of node iterator converts to this.
    83       /// thus each kind of node iterator converts to this.
    84       /// More precisely each kind of node iterator should be inherited 
    84       /// More precisely each kind of node iterator should be inherited
    85       /// from the trivial node iterator.
    85       /// from the trivial node iterator.
    86       class Node {
    86       class Node {
    87       public:
    87       public:
    88         /// Default constructor
    88         /// Default constructor
    89 
    89 
   106         /// Two iterators are equal if and only if they point to the
   106         /// Two iterators are equal if and only if they point to the
   107         /// same object or both are invalid.
   107         /// same object or both are invalid.
   108         bool operator==(Node) const { return true; }
   108         bool operator==(Node) const { return true; }
   109 
   109 
   110         /// Inequality operator
   110         /// Inequality operator
   111         
   111 
   112         /// \sa operator==(Node n)
   112         /// \sa operator==(Node n)
   113         ///
   113         ///
   114         bool operator!=(Node) const { return true; }
   114         bool operator!=(Node) const { return true; }
   115 
   115 
   116 	/// Artificial ordering operator.
   116         /// Artificial ordering operator.
   117 	
   117 
   118 	/// To allow the use of graph descriptors as key type in std::map or
   118         /// To allow the use of graph descriptors as key type in std::map or
   119 	/// similar associative container we require this.
   119         /// similar associative container we require this.
   120 	///
   120         ///
   121 	/// \note This operator only have to define some strict ordering of
   121         /// \note This operator only have to define some strict ordering of
   122 	/// the items; this order has nothing to do with the iteration
   122         /// the items; this order has nothing to do with the iteration
   123 	/// ordering of the items.
   123         /// ordering of the items.
   124 	bool operator<(Node) const { return false; }
   124         bool operator<(Node) const { return false; }
   125 
   125 
   126       };
   126       };
   127     
   127 
   128       /// This iterator goes through each node.
   128       /// This iterator goes through each node.
   129 
   129 
   130       /// This iterator goes through each node.
   130       /// This iterator goes through each node.
   131       /// Its usage is quite simple, for example you can count the number
   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:
   132       /// of nodes in graph \c g of type \c Graph like this:
   140 
   140 
   141         /// @warning The default constructor sets the iterator
   141         /// @warning The default constructor sets the iterator
   142         /// to an undefined value.
   142         /// to an undefined value.
   143         NodeIt() { }
   143         NodeIt() { }
   144         /// Copy constructor.
   144         /// Copy constructor.
   145         
   145 
   146         /// Copy constructor.
   146         /// Copy constructor.
   147         ///
   147         ///
   148         NodeIt(const NodeIt& n) : Node(n) { }
   148         NodeIt(const NodeIt& n) : Node(n) { }
   149         /// Invalid constructor \& conversion.
   149         /// Invalid constructor \& conversion.
   150 
   150 
   156         /// Sets the iterator to the first node of \c g.
   156         /// Sets the iterator to the first node of \c g.
   157         ///
   157         ///
   158         NodeIt(const Graph&) { }
   158         NodeIt(const Graph&) { }
   159         /// Node -> NodeIt conversion.
   159         /// Node -> NodeIt conversion.
   160 
   160 
   161         /// Sets the iterator to the node of \c the graph pointed by 
   161         /// Sets the iterator to the node of \c the graph pointed by
   162 	/// the trivial iterator.
   162         /// the trivial iterator.
   163         /// This feature necessitates that each time we 
   163         /// This feature necessitates that each time we
   164         /// iterate the arc-set, the iteration order is the same.
   164         /// iterate the arc-set, the iteration order is the same.
   165         NodeIt(const Graph&, const Node&) { }
   165         NodeIt(const Graph&, const Node&) { }
   166         /// Next node.
   166         /// Next node.
   167 
   167 
   168         /// Assign the iterator to the next node.
   168         /// Assign the iterator to the next node.
   169         ///
   169         ///
   170         NodeIt& operator++() { return *this; }
   170         NodeIt& operator++() { return *this; }
   171       };
   171       };
   172     
   172 
   173     
   173 
   174       /// The base type of the edge iterators.
   174       /// The base type of the edge iterators.
   175 
   175 
   176       /// The base type of the edge iterators.
   176       /// The base type of the edge iterators.
   177       ///
   177       ///
   178       class Edge {
   178       class Edge {
   201 
   201 
   202         /// \sa operator==(Edge n)
   202         /// \sa operator==(Edge n)
   203         ///
   203         ///
   204         bool operator!=(Edge) const { return true; }
   204         bool operator!=(Edge) const { return true; }
   205 
   205 
   206 	/// Artificial ordering operator.
   206         /// Artificial ordering operator.
   207 	
   207 
   208 	/// To allow the use of graph descriptors as key type in std::map or
   208         /// To allow the use of graph descriptors as key type in std::map or
   209 	/// similar associative container we require this.
   209         /// similar associative container we require this.
   210 	///
   210         ///
   211 	/// \note This operator only have to define some strict ordering of
   211         /// \note This operator only have to define some strict ordering of
   212 	/// the items; this order has nothing to do with the iteration
   212         /// the items; this order has nothing to do with the iteration
   213 	/// ordering of the items.
   213         /// ordering of the items.
   214 	bool operator<(Edge) const { return false; }
   214         bool operator<(Edge) const { return false; }
   215       };
   215       };
   216 
   216 
   217       /// This iterator goes through each edge.
   217       /// This iterator goes through each edge.
   218 
   218 
   219       /// This iterator goes through each edge of a graph.
   219       /// This iterator goes through each edge of a graph.
   239 
   239 
   240         /// Initialize the iterator to be invalid.
   240         /// Initialize the iterator to be invalid.
   241         ///
   241         ///
   242         EdgeIt(Invalid) { }
   242         EdgeIt(Invalid) { }
   243         /// This constructor sets the iterator to the first edge.
   243         /// This constructor sets the iterator to the first edge.
   244     
   244 
   245         /// This constructor sets the iterator to the first edge.
   245         /// This constructor sets the iterator to the first edge.
   246         EdgeIt(const Graph&) { }
   246         EdgeIt(const Graph&) { }
   247         /// Edge -> EdgeIt conversion
   247         /// Edge -> EdgeIt conversion
   248 
   248 
   249         /// Sets the iterator to the value of the trivial iterator.
   249         /// Sets the iterator to the value of the trivial iterator.
   250         /// This feature necessitates that each time we
   250         /// This feature necessitates that each time we
   251         /// iterate the edge-set, the iteration order is the 
   251         /// iterate the edge-set, the iteration order is the
   252 	/// same.
   252         /// same.
   253         EdgeIt(const Graph&, const Edge&) { } 
   253         EdgeIt(const Graph&, const Edge&) { }
   254         /// Next edge
   254         /// Next edge
   255         
   255 
   256         /// Assign the iterator to the next edge.
   256         /// Assign the iterator to the next edge.
   257         EdgeIt& operator++() { return *this; }
   257         EdgeIt& operator++() { return *this; }
   258       };
   258       };
   259 
   259 
   260       /// \brief This iterator goes trough the incident undirected 
   260       /// \brief This iterator goes trough the incident undirected
   261       /// arcs of a node.
   261       /// arcs of a node.
   262       ///
   262       ///
   263       /// This iterator goes trough the incident edges
   263       /// This iterator goes trough the incident edges
   264       /// of a certain node of a graph. You should assume that the 
   264       /// of a certain node of a graph. You should assume that the
   265       /// loop arcs will be iterated twice.
   265       /// loop arcs will be iterated twice.
   266       /// 
   266       ///
   267       /// Its usage is quite simple, for example you can compute the
   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
   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. 
   269       /// in graph \c g of type \c Graph as follows.
   270       ///
   270       ///
   271       ///\code
   271       ///\code
   272       /// int count=0;
   272       /// int count=0;
   273       /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
   273       /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
   274       ///\endcode
   274       ///\endcode
   288 
   288 
   289         /// Initialize the iterator to be invalid.
   289         /// Initialize the iterator to be invalid.
   290         ///
   290         ///
   291         IncEdgeIt(Invalid) { }
   291         IncEdgeIt(Invalid) { }
   292         /// This constructor sets the iterator to first incident arc.
   292         /// This constructor sets the iterator to first incident arc.
   293     
   293 
   294         /// This constructor set the iterator to the first incident arc of
   294         /// This constructor set the iterator to the first incident arc of
   295         /// the node.
   295         /// the node.
   296         IncEdgeIt(const Graph&, const Node&) { }
   296         IncEdgeIt(const Graph&, const Node&) { }
   297         /// Edge -> IncEdgeIt conversion
   297         /// Edge -> IncEdgeIt conversion
   298 
   298 
   299         /// Sets the iterator to the value of the trivial iterator \c e.
   299         /// Sets the iterator to the value of the trivial iterator \c e.
   300         /// This feature necessitates that each time we 
   300         /// This feature necessitates that each time we
   301         /// iterate the arc-set, the iteration order is the same.
   301         /// iterate the arc-set, the iteration order is the same.
   302         IncEdgeIt(const Graph&, const Edge&) { }
   302         IncEdgeIt(const Graph&, const Edge&) { }
   303         /// Next incident arc
   303         /// Next incident arc
   304 
   304 
   305         /// Assign the iterator to the next incident arc
   305         /// Assign the iterator to the next incident arc
   306 	/// of the corresponding node.
   306         /// of the corresponding node.
   307         IncEdgeIt& operator++() { return *this; }
   307         IncEdgeIt& operator++() { return *this; }
   308       };
   308       };
   309 
   309 
   310       /// The directed arc type.
   310       /// The directed arc type.
   311 
   311 
   338 
   338 
   339         /// \sa operator==(Arc n)
   339         /// \sa operator==(Arc n)
   340         ///
   340         ///
   341         bool operator!=(Arc) const { return true; }
   341         bool operator!=(Arc) const { return true; }
   342 
   342 
   343 	/// Artificial ordering operator.
   343         /// Artificial ordering operator.
   344 	
   344 
   345 	/// To allow the use of graph descriptors as key type in std::map or
   345         /// To allow the use of graph descriptors as key type in std::map or
   346 	/// similar associative container we require this.
   346         /// similar associative container we require this.
   347 	///
   347         ///
   348 	/// \note This operator only have to define some strict ordering of
   348         /// \note This operator only have to define some strict ordering of
   349 	/// the items; this order has nothing to do with the iteration
   349         /// the items; this order has nothing to do with the iteration
   350 	/// ordering of the items.
   350         /// ordering of the items.
   351 	bool operator<(Arc) const { return false; }
   351         bool operator<(Arc) const { return false; }
   352 	
   352 
   353       }; 
   353       };
   354       /// This iterator goes through each directed arc.
   354       /// This iterator goes through each directed arc.
   355 
   355 
   356       /// This iterator goes through each arc of a graph.
   356       /// This iterator goes through each arc of a graph.
   357       /// Its usage is quite simple, for example you can count the number
   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:
   358       /// of arcs in a graph \c g of type \c Graph as follows:
   376 
   376 
   377         /// Initialize the iterator to be invalid.
   377         /// Initialize the iterator to be invalid.
   378         ///
   378         ///
   379         ArcIt(Invalid) { }
   379         ArcIt(Invalid) { }
   380         /// This constructor sets the iterator to the first arc.
   380         /// This constructor sets the iterator to the first arc.
   381     
   381 
   382         /// This constructor sets the iterator to the first arc of \c g.
   382         /// This constructor sets the iterator to the first arc of \c g.
   383         ///@param g the graph
   383         ///@param g the graph
   384         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
   384         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
   385         /// Arc -> ArcIt conversion
   385         /// Arc -> ArcIt conversion
   386 
   386 
   387         /// Sets the iterator to the value of the trivial iterator \c e.
   387         /// Sets the iterator to the value of the trivial iterator \c e.
   388         /// This feature necessitates that each time we 
   388         /// This feature necessitates that each time we
   389         /// iterate the arc-set, the iteration order is the same.
   389         /// iterate the arc-set, the iteration order is the same.
   390         ArcIt(const Graph&, const Arc&) { } 
   390         ArcIt(const Graph&, const Arc&) { }
   391         ///Next arc
   391         ///Next arc
   392         
   392 
   393         /// Assign the iterator to the next arc.
   393         /// Assign the iterator to the next arc.
   394         ArcIt& operator++() { return *this; }
   394         ArcIt& operator++() { return *this; }
   395       };
   395       };
   396    
   396 
   397       /// This iterator goes trough the outgoing directed arcs of a node.
   397       /// This iterator goes trough the outgoing directed arcs of a node.
   398 
   398 
   399       /// This iterator goes trough the \e outgoing arcs of a certain node
   399       /// This iterator goes trough the \e outgoing arcs of a certain node
   400       /// of a graph.
   400       /// of a graph.
   401       /// Its usage is quite simple, for example you can count the number
   401       /// Its usage is quite simple, for example you can count the number
   403       /// in graph \c g of type \c Graph as follows.
   403       /// in graph \c g of type \c Graph as follows.
   404       ///\code
   404       ///\code
   405       /// int count=0;
   405       /// int count=0;
   406       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   406       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   407       ///\endcode
   407       ///\endcode
   408     
   408 
   409       class OutArcIt : public Arc {
   409       class OutArcIt : public Arc {
   410       public:
   410       public:
   411         /// Default constructor
   411         /// Default constructor
   412 
   412 
   413         /// @warning The default constructor sets the iterator
   413         /// @warning The default constructor sets the iterator
   422 
   422 
   423         /// Initialize the iterator to be invalid.
   423         /// Initialize the iterator to be invalid.
   424         ///
   424         ///
   425         OutArcIt(Invalid) { }
   425         OutArcIt(Invalid) { }
   426         /// This constructor sets the iterator to the first outgoing arc.
   426         /// This constructor sets the iterator to the first outgoing arc.
   427     
   427 
   428         /// This constructor sets the iterator to the first outgoing arc of
   428         /// This constructor sets the iterator to the first outgoing arc of
   429         /// the node.
   429         /// the node.
   430         ///@param n the node
   430         ///@param n the node
   431         ///@param g the graph
   431         ///@param g the graph
   432         OutArcIt(const Graph& n, const Node& g) {
   432         OutArcIt(const Graph& n, const Node& g) {
   433 	  ignore_unused_variable_warning(n);
   433           ignore_unused_variable_warning(n);
   434 	  ignore_unused_variable_warning(g);
   434           ignore_unused_variable_warning(g);
   435 	}
   435         }
   436         /// Arc -> OutArcIt conversion
   436         /// Arc -> OutArcIt conversion
   437 
   437 
   438         /// Sets the iterator to the value of the trivial iterator.
   438         /// Sets the iterator to the value of the trivial iterator.
   439 	/// This feature necessitates that each time we 
   439         /// This feature necessitates that each time we
   440         /// iterate the arc-set, the iteration order is the same.
   440         /// iterate the arc-set, the iteration order is the same.
   441         OutArcIt(const Graph&, const Arc&) { }
   441         OutArcIt(const Graph&, const Arc&) { }
   442         ///Next outgoing arc
   442         ///Next outgoing arc
   443         
   443 
   444         /// Assign the iterator to the next 
   444         /// Assign the iterator to the next
   445         /// outgoing arc of the corresponding node.
   445         /// outgoing arc of the corresponding node.
   446         OutArcIt& operator++() { return *this; }
   446         OutArcIt& operator++() { return *this; }
   447       };
   447       };
   448 
   448 
   449       /// This iterator goes trough the incoming directed arcs of a node.
   449       /// This iterator goes trough the incoming directed arcs of a node.
   474 
   474 
   475         /// Initialize the iterator to be invalid.
   475         /// Initialize the iterator to be invalid.
   476         ///
   476         ///
   477         InArcIt(Invalid) { }
   477         InArcIt(Invalid) { }
   478         /// This constructor sets the iterator to first incoming arc.
   478         /// This constructor sets the iterator to first incoming arc.
   479     
   479 
   480         /// This constructor set the iterator to the first incoming arc of
   480         /// This constructor set the iterator to the first incoming arc of
   481         /// the node.
   481         /// the node.
   482         ///@param n the node
   482         ///@param n the node
   483         ///@param g the graph
   483         ///@param g the graph
   484         InArcIt(const Graph& g, const Node& n) { 
   484         InArcIt(const Graph& g, const Node& n) {
   485 	  ignore_unused_variable_warning(n);
   485           ignore_unused_variable_warning(n);
   486 	  ignore_unused_variable_warning(g);
   486           ignore_unused_variable_warning(g);
   487 	}
   487         }
   488         /// Arc -> InArcIt conversion
   488         /// Arc -> InArcIt conversion
   489 
   489 
   490         /// Sets the iterator to the value of the trivial iterator \c e.
   490         /// Sets the iterator to the value of the trivial iterator \c e.
   491         /// This feature necessitates that each time we 
   491         /// This feature necessitates that each time we
   492         /// iterate the arc-set, the iteration order is the same.
   492         /// iterate the arc-set, the iteration order is the same.
   493         InArcIt(const Graph&, const Arc&) { }
   493         InArcIt(const Graph&, const Arc&) { }
   494         /// Next incoming arc
   494         /// Next incoming arc
   495 
   495 
   496         /// Assign the iterator to the next inarc of the corresponding node.
   496         /// Assign the iterator to the next inarc of the corresponding node.
   497         ///
   497         ///
   498         InArcIt& operator++() { return *this; }
   498         InArcIt& operator++() { return *this; }
   499       };
   499       };
   500 
   500 
   501       /// \brief Read write map of the nodes to type \c T.
   501       /// \brief Read write map of the nodes to type \c T.
   502       /// 
   502       ///
   503       /// ReadWrite map of the nodes to type \c T.
   503       /// ReadWrite map of the nodes to type \c T.
   504       /// \sa Reference
   504       /// \sa Reference
   505       template<class T> 
   505       template<class T>
   506       class NodeMap : public ReadWriteMap< Node, T >
   506       class NodeMap : public ReadWriteMap< Node, T >
   507       {
   507       {
   508       public:
   508       public:
   509 
   509 
   510         ///\e
   510         ///\e
   514 
   514 
   515         ///Copy constructor
   515         ///Copy constructor
   516         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   516         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   517         ///Assignment operator
   517         ///Assignment operator
   518         template <typename CMap>
   518         template <typename CMap>
   519         NodeMap& operator=(const CMap&) { 
   519         NodeMap& operator=(const CMap&) {
   520           checkConcept<ReadMap<Node, T>, CMap>();
   520           checkConcept<ReadMap<Node, T>, CMap>();
   521           return *this; 
   521           return *this;
   522         }
   522         }
   523       };
   523       };
   524 
   524 
   525       /// \brief Read write map of the directed arcs to type \c T.
   525       /// \brief Read write map of the directed arcs to type \c T.
   526       ///
   526       ///
   527       /// Reference map of the directed arcs to type \c T.
   527       /// Reference map of the directed arcs to type \c T.
   528       /// \sa Reference
   528       /// \sa Reference
   529       template<class T> 
   529       template<class T>
   530       class ArcMap : public ReadWriteMap<Arc,T>
   530       class ArcMap : public ReadWriteMap<Arc,T>
   531       {
   531       {
   532       public:
   532       public:
   533 
   533 
   534         ///\e
   534         ///\e
   537         ArcMap(const Graph&, T) { }
   537         ArcMap(const Graph&, T) { }
   538         ///Copy constructor
   538         ///Copy constructor
   539         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   539         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   540         ///Assignment operator
   540         ///Assignment operator
   541         template <typename CMap>
   541         template <typename CMap>
   542         ArcMap& operator=(const CMap&) { 
   542         ArcMap& operator=(const CMap&) {
   543           checkConcept<ReadMap<Arc, T>, CMap>();
   543           checkConcept<ReadMap<Arc, T>, CMap>();
   544           return *this; 
   544           return *this;
   545         }
   545         }
   546       };
   546       };
   547 
   547 
   548       /// Read write map of the edges to type \c T.
   548       /// Read write map of the edges to type \c T.
   549 
   549 
   550       /// Reference map of the arcs to type \c T.
   550       /// Reference map of the arcs to type \c T.
   551       /// \sa Reference
   551       /// \sa Reference
   552       template<class T> 
   552       template<class T>
   553       class EdgeMap : public ReadWriteMap<Edge,T>
   553       class EdgeMap : public ReadWriteMap<Edge,T>
   554       {
   554       {
   555       public:
   555       public:
   556 
   556 
   557         ///\e
   557         ///\e
   560         EdgeMap(const Graph&, T) { }
   560         EdgeMap(const Graph&, T) { }
   561         ///Copy constructor
   561         ///Copy constructor
   562         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
   562         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
   563         ///Assignment operator
   563         ///Assignment operator
   564         template <typename CMap>
   564         template <typename CMap>
   565         EdgeMap& operator=(const CMap&) { 
   565         EdgeMap& operator=(const CMap&) {
   566           checkConcept<ReadMap<Edge, T>, CMap>();
   566           checkConcept<ReadMap<Edge, T>, CMap>();
   567           return *this; 
   567           return *this;
   568         }
   568         }
   569       };
   569       };
   570 
   570 
   571       /// \brief Direct the given edge.
   571       /// \brief Direct the given edge.
   572       ///
   572       ///
   573       /// Direct the given edge. The returned arc source
   573       /// Direct the given edge. The returned arc source
   574       /// will be the given node.
   574       /// will be the given node.
   575       Arc direct(const Edge&, const Node&) const {
   575       Arc direct(const Edge&, const Node&) const {
   576 	return INVALID;
   576         return INVALID;
   577       }
   577       }
   578 
   578 
   579       /// \brief Direct the given edge.
   579       /// \brief Direct the given edge.
   580       ///
   580       ///
   581       /// Direct the given edge. The returned arc
   581       /// Direct the given edge. The returned arc
   582       /// represents the given edge and the direction comes
   582       /// represents the given edge and the direction comes
   583       /// from the bool parameter. The source of the edge and
   583       /// from the bool parameter. The source of the edge and
   584       /// the directed arc is the same when the given bool is true.
   584       /// the directed arc is the same when the given bool is true.
   585       Arc direct(const Edge&, bool) const {
   585       Arc direct(const Edge&, bool) const {
   586 	return INVALID;
   586         return INVALID;
   587       }
   587       }
   588 
   588 
   589       /// \brief Returns true if the arc has default orientation.
   589       /// \brief Returns true if the arc has default orientation.
   590       ///
   590       ///
   591       /// Returns whether the given directed arc is same orientation as
   591       /// Returns whether the given directed arc is same orientation as
   623 
   623 
   624       /// \brief Target node of the directed arc.
   624       /// \brief Target node of the directed arc.
   625       Node target(Arc) const { return INVALID; }
   625       Node target(Arc) const { return INVALID; }
   626 
   626 
   627       /// \brief Returns the id of the node.
   627       /// \brief Returns the id of the node.
   628       int id(Node) const { return -1; } 
   628       int id(Node) const { return -1; }
   629 
   629 
   630       /// \brief Returns the id of the edge.
   630       /// \brief Returns the id of the edge.
   631       int id(Edge) const { return -1; } 
   631       int id(Edge) const { return -1; }
   632 
   632 
   633       /// \brief Returns the id of the arc.
   633       /// \brief Returns the id of the arc.
   634       int id(Arc) const { return -1; } 
   634       int id(Arc) const { return -1; }
   635 
   635 
   636       /// \brief Returns the node with the given id.
   636       /// \brief Returns the node with the given id.
   637       ///
   637       ///
   638       /// \pre The argument should be a valid node id in the graph.
   638       /// \pre The argument should be a valid node id in the graph.
   639       Node nodeFromId(int) const { return INVALID; } 
   639       Node nodeFromId(int) const { return INVALID; }
   640 
   640 
   641       /// \brief Returns the edge with the given id.
   641       /// \brief Returns the edge with the given id.
   642       ///
   642       ///
   643       /// \pre The argument should be a valid edge id in the graph.
   643       /// \pre The argument should be a valid edge id in the graph.
   644       Edge edgeFromId(int) const { return INVALID; } 
   644       Edge edgeFromId(int) const { return INVALID; }
   645 
   645 
   646       /// \brief Returns the arc with the given id.
   646       /// \brief Returns the arc with the given id.
   647       ///
   647       ///
   648       /// \pre The argument should be a valid arc id in the graph.
   648       /// \pre The argument should be a valid arc id in the graph.
   649       Arc arcFromId(int) const { return INVALID; } 
   649       Arc arcFromId(int) const { return INVALID; }
   650 
   650 
   651       /// \brief Returns an upper bound on the node IDs.
   651       /// \brief Returns an upper bound on the node IDs.
   652       int maxNodeId() const { return -1; } 
   652       int maxNodeId() const { return -1; }
   653 
   653 
   654       /// \brief Returns an upper bound on the edge IDs.
   654       /// \brief Returns an upper bound on the edge IDs.
   655       int maxEdgeId() const { return -1; } 
   655       int maxEdgeId() const { return -1; }
   656 
   656 
   657       /// \brief Returns an upper bound on the arc IDs.
   657       /// \brief Returns an upper bound on the arc IDs.
   658       int maxArcId() const { return -1; } 
   658       int maxArcId() const { return -1; }
   659 
   659 
   660       void first(Node&) const {}
   660       void first(Node&) const {}
   661       void next(Node&) const {}
   661       void next(Node&) const {}
   662 
   662 
   663       void first(Edge&) const {}
   663       void first(Edge&) const {}
   681       Edge fromId(int, Edge) const { return INVALID; }
   681       Edge fromId(int, Edge) const { return INVALID; }
   682       // The second parameter is dummy.
   682       // The second parameter is dummy.
   683       Arc fromId(int, Arc) const { return INVALID; }
   683       Arc fromId(int, Arc) const { return INVALID; }
   684 
   684 
   685       // Dummy parameter.
   685       // Dummy parameter.
   686       int maxId(Node) const { return -1; } 
   686       int maxId(Node) const { return -1; }
   687       // Dummy parameter.
   687       // Dummy parameter.
   688       int maxId(Edge) const { return -1; } 
   688       int maxId(Edge) const { return -1; }
   689       // Dummy parameter.
   689       // Dummy parameter.
   690       int maxId(Arc) const { return -1; } 
   690       int maxId(Arc) const { return -1; }
   691 
   691 
   692       /// \brief Base node of the iterator
   692       /// \brief Base node of the iterator
   693       ///
   693       ///
   694       /// Returns the base node (the source in this case) of the iterator
   694       /// Returns the base node (the source in this case) of the iterator
   695       Node baseNode(OutArcIt e) const {
   695       Node baseNode(OutArcIt e) const {
   696 	return source(e);
   696         return source(e);
   697       }
   697       }
   698       /// \brief Running node of the iterator
   698       /// \brief Running node of the iterator
   699       ///
   699       ///
   700       /// Returns the running node (the target in this case) of the
   700       /// Returns the running node (the target in this case) of the
   701       /// iterator
   701       /// iterator
   702       Node runningNode(OutArcIt e) const {
   702       Node runningNode(OutArcIt e) const {
   703 	return target(e);
   703         return target(e);
   704       }
   704       }
   705 
   705 
   706       /// \brief Base node of the iterator
   706       /// \brief Base node of the iterator
   707       ///
   707       ///
   708       /// Returns the base node (the target in this case) of the iterator
   708       /// Returns the base node (the target in this case) of the iterator
   709       Node baseNode(InArcIt e) const {
   709       Node baseNode(InArcIt e) const {
   710 	return target(e);
   710         return target(e);
   711       }
   711       }
   712       /// \brief Running node of the iterator
   712       /// \brief Running node of the iterator
   713       ///
   713       ///
   714       /// Returns the running node (the source in this case) of the
   714       /// Returns the running node (the source in this case) of the
   715       /// iterator
   715       /// iterator
   716       Node runningNode(InArcIt e) const {
   716       Node runningNode(InArcIt e) const {
   717 	return source(e);
   717         return source(e);
   718       }
   718       }
   719 
   719 
   720       /// \brief Base node of the iterator
   720       /// \brief Base node of the iterator
   721       ///
   721       ///
   722       /// Returns the base node of the iterator
   722       /// Returns the base node of the iterator
   723       Node baseNode(IncEdgeIt) const {
   723       Node baseNode(IncEdgeIt) const {
   724 	return INVALID;
   724         return INVALID;
   725       }
   725       }
   726       
   726 
   727       /// \brief Running node of the iterator
   727       /// \brief Running node of the iterator
   728       ///
   728       ///
   729       /// Returns the running node of the iterator
   729       /// Returns the running node of the iterator
   730       Node runningNode(IncEdgeIt) const {
   730       Node runningNode(IncEdgeIt) const {
   731 	return INVALID;
   731         return INVALID;
   732       }
   732       }
   733 
   733 
   734       template <typename _Graph>
   734       template <typename _Graph>
   735       struct Constraints {
   735       struct Constraints {
   736 	void constraints() {
   736         void constraints() {
   737 	  checkConcept<IterableGraphComponent<>, _Graph>();
   737           checkConcept<IterableGraphComponent<>, _Graph>();
   738 	  checkConcept<IDableGraphComponent<>, _Graph>();
   738           checkConcept<IDableGraphComponent<>, _Graph>();
   739 	  checkConcept<MappableGraphComponent<>, _Graph>();
   739           checkConcept<MappableGraphComponent<>, _Graph>();
   740 	}
   740         }
   741       };
   741       };
   742 
   742 
   743     };
   743     };
   744 
   744 
   745   }
   745   }