lemon/concepts/digraph.h
changeset 771 8452ca46e29a
parent 580 2313edd0db0b
child 786 e20173729589
equal deleted inserted replaced
9:bdced82c75af 10:528c5e757510
    33 
    33 
    34     /// \ingroup graph_concepts
    34     /// \ingroup graph_concepts
    35     ///
    35     ///
    36     /// \brief Class describing the concept of directed graphs.
    36     /// \brief Class describing the concept of directed graphs.
    37     ///
    37     ///
    38     /// This class describes the \ref concept "concept" of the
    38     /// This class describes the common interface of all directed
    39     /// immutable directed digraphs.
    39     /// graphs (digraphs).
    40     ///
    40     ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    41     /// Like all concept classes, it only provides an interface
    42     /// @ref SmartDigraph may have several additional functionality.
    42     /// without any sensible implementation. So any general algorithm for
       
    43     /// directed graphs should compile with this class, but it will not
       
    44     /// run properly, of course.
       
    45     /// An actual digraph implementation like \ref ListDigraph or
       
    46     /// \ref SmartDigraph may have additional functionality.
    43     ///
    47     ///
    44     /// \sa concept
    48     /// \sa Graph
    45     class Digraph {
    49     class Digraph {
    46     private:
    50     private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    51       /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
    48 
    52       Digraph(const Digraph &) {}
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    53       /// \brief Assignment of a digraph to another one is \e not allowed.
    50       ///
    54       /// Use DigraphCopy instead.
    51       Digraph(const Digraph &) {};
       
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
       
    53       ///\e not allowed. Use DigraphCopy() instead.
       
    54 
       
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
       
    56       ///\e not allowed.  Use DigraphCopy() instead.
       
    57 
       
    58       void operator=(const Digraph &) {}
    55       void operator=(const Digraph &) {}
       
    56 
    59     public:
    57     public:
    60       ///\e
    58       /// Default constructor.
    61 
       
    62       /// Defalult constructor.
       
    63 
       
    64       /// Defalult constructor.
       
    65       ///
       
    66       Digraph() { }
    59       Digraph() { }
    67       /// Class for identifying a node of the digraph
    60 
       
    61       /// The node type of the digraph
    68 
    62 
    69       /// This class identifies a node of the digraph. It also serves
    63       /// This class identifies a node of the digraph. It also serves
    70       /// as a base class of the node iterators,
    64       /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
    65       /// thus they convert to this type.
    72       class Node {
    66       class Node {
    73       public:
    67       public:
    74         /// Default constructor
    68         /// Default constructor
    75 
    69 
    76         /// @warning The default constructor sets the iterator
    70         /// Default constructor.
    77         /// to an undefined value.
    71         /// \warning It sets the object to an undefined value.
    78         Node() { }
    72         Node() { }
    79         /// Copy constructor.
    73         /// Copy constructor.
    80 
    74 
    81         /// Copy constructor.
    75         /// Copy constructor.
    82         ///
    76         ///
    83         Node(const Node&) { }
    77         Node(const Node&) { }
    84 
    78 
    85         /// Invalid constructor \& conversion.
    79         /// %Invalid constructor \& conversion.
    86 
    80 
    87         /// This constructor initializes the iterator to be invalid.
    81         /// Initializes the object to be invalid.
    88         /// \sa Invalid for more details.
    82         /// \sa Invalid for more details.
    89         Node(Invalid) { }
    83         Node(Invalid) { }
    90         /// Equality operator
    84         /// Equality operator
    91 
    85 
       
    86         /// Equality operator.
       
    87         ///
    92         /// Two iterators are equal if and only if they point to the
    88         /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
    89         /// same object or both are \c INVALID.
    94         bool operator==(Node) const { return true; }
    90         bool operator==(Node) const { return true; }
    95 
    91 
    96         /// Inequality operator
    92         /// Inequality operator
    97 
    93 
    98         /// \sa operator==(Node n)
    94         /// Inequality operator.
    99         ///
       
   100         bool operator!=(Node) const { return true; }
    95         bool operator!=(Node) const { return true; }
   101 
    96 
   102         /// Artificial ordering operator.
    97         /// Artificial ordering operator.
   103 
    98 
   104         /// To allow the use of digraph descriptors as key type in std::map or
    99         /// Artificial ordering operator.
   105         /// similar associative container we require this.
   100         ///
   106         ///
   101         /// \note This operator only has to define some strict ordering of
   107         /// \note This operator only have to define some strict ordering of
   102         /// the nodes; this order has nothing to do with the iteration
   108         /// the items; this order has nothing to do with the iteration
   103         /// ordering of the nodes.
   109         /// ordering of the items.
       
   110         bool operator<(Node) const { return false; }
   104         bool operator<(Node) const { return false; }
   111 
   105       };
   112       };
   106 
   113 
   107       /// Iterator class for the nodes.
   114       /// This iterator goes through each node.
   108 
   115 
   109       /// This iterator goes through each node of the digraph.
   116       /// This iterator goes through each node.
       
   117       /// Its usage is quite simple, for example you can count the number
   110       /// Its usage is quite simple, for example you can count the number
   118       /// of nodes in digraph \c g of type \c Digraph like this:
   111       /// of nodes in a digraph \c g of type \c %Digraph like this:
   119       ///\code
   112       ///\code
   120       /// int count=0;
   113       /// int count=0;
   121       /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
   114       /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
   122       ///\endcode
   115       ///\endcode
   123       class NodeIt : public Node {
   116       class NodeIt : public Node {
   124       public:
   117       public:
   125         /// Default constructor
   118         /// Default constructor
   126 
   119 
   127         /// @warning The default constructor sets the iterator
   120         /// Default constructor.
   128         /// to an undefined value.
   121         /// \warning It sets the iterator to an undefined value.
   129         NodeIt() { }
   122         NodeIt() { }
   130         /// Copy constructor.
   123         /// Copy constructor.
   131 
   124 
   132         /// Copy constructor.
   125         /// Copy constructor.
   133         ///
   126         ///
   134         NodeIt(const NodeIt& n) : Node(n) { }
   127         NodeIt(const NodeIt& n) : Node(n) { }
   135         /// Invalid constructor \& conversion.
   128         /// %Invalid constructor \& conversion.
   136 
   129 
   137         /// Initialize the iterator to be invalid.
   130         /// Initializes the iterator to be invalid.
   138         /// \sa Invalid for more details.
   131         /// \sa Invalid for more details.
   139         NodeIt(Invalid) { }
   132         NodeIt(Invalid) { }
   140         /// Sets the iterator to the first node.
   133         /// Sets the iterator to the first node.
   141 
   134 
   142         /// Sets the iterator to the first node of \c g.
   135         /// Sets the iterator to the first node of the given digraph.
   143         ///
   136         ///
   144         NodeIt(const Digraph&) { }
   137         explicit NodeIt(const Digraph&) { }
   145         /// Node -> NodeIt conversion.
   138         /// Sets the iterator to the given node.
   146 
   139 
   147         /// Sets the iterator to the node of \c the digraph pointed by
   140         /// Sets the iterator to the given node of the given digraph.
   148         /// the trivial iterator.
   141         ///
   149         /// This feature necessitates that each time we
       
   150         /// iterate the arc-set, the iteration order is the same.
       
   151         NodeIt(const Digraph&, const Node&) { }
   142         NodeIt(const Digraph&, const Node&) { }
   152         /// Next node.
   143         /// Next node.
   153 
   144 
   154         /// Assign the iterator to the next node.
   145         /// Assign the iterator to the next node.
   155         ///
   146         ///
   156         NodeIt& operator++() { return *this; }
   147         NodeIt& operator++() { return *this; }
   157       };
   148       };
   158 
   149 
   159 
   150 
   160       /// Class for identifying an arc of the digraph
   151       /// The arc type of the digraph
   161 
   152 
   162       /// This class identifies an arc of the digraph. It also serves
   153       /// This class identifies an arc of the digraph. It also serves
   163       /// as a base class of the arc iterators,
   154       /// as a base class of the arc iterators,
   164       /// thus they will convert to this type.
   155       /// thus they will convert to this type.
   165       class Arc {
   156       class Arc {
   166       public:
   157       public:
   167         /// Default constructor
   158         /// Default constructor
   168 
   159 
   169         /// @warning The default constructor sets the iterator
   160         /// Default constructor.
   170         /// to an undefined value.
   161         /// \warning It sets the object to an undefined value.
   171         Arc() { }
   162         Arc() { }
   172         /// Copy constructor.
   163         /// Copy constructor.
   173 
   164 
   174         /// Copy constructor.
   165         /// Copy constructor.
   175         ///
   166         ///
   176         Arc(const Arc&) { }
   167         Arc(const Arc&) { }
   177         /// Initialize the iterator to be invalid.
   168         /// %Invalid constructor \& conversion.
   178 
   169 
   179         /// Initialize the iterator to be invalid.
   170         /// Initializes the object to be invalid.
   180         ///
   171         /// \sa Invalid for more details.
   181         Arc(Invalid) { }
   172         Arc(Invalid) { }
   182         /// Equality operator
   173         /// Equality operator
   183 
   174 
       
   175         /// Equality operator.
       
   176         ///
   184         /// Two iterators are equal if and only if they point to the
   177         /// Two iterators are equal if and only if they point to the
   185         /// same object or both are invalid.
   178         /// same object or both are \c INVALID.
   186         bool operator==(Arc) const { return true; }
   179         bool operator==(Arc) const { return true; }
   187         /// Inequality operator
   180         /// Inequality operator
   188 
   181 
   189         /// \sa operator==(Arc n)
   182         /// Inequality operator.
   190         ///
       
   191         bool operator!=(Arc) const { return true; }
   183         bool operator!=(Arc) const { return true; }
   192 
   184 
   193         /// Artificial ordering operator.
   185         /// Artificial ordering operator.
   194 
   186 
   195         /// To allow the use of digraph descriptors as key type in std::map or
   187         /// Artificial ordering operator.
   196         /// similar associative container we require this.
   188         ///
   197         ///
   189         /// \note This operator only has to define some strict ordering of
   198         /// \note This operator only have to define some strict ordering of
   190         /// the arcs; this order has nothing to do with the iteration
   199         /// the items; this order has nothing to do with the iteration
   191         /// ordering of the arcs.
   200         /// ordering of the items.
       
   201         bool operator<(Arc) const { return false; }
   192         bool operator<(Arc) const { return false; }
   202       };
   193       };
   203 
   194 
   204       /// This iterator goes trough the outgoing arcs of a node.
   195       /// Iterator class for the outgoing arcs of a node.
   205 
   196 
   206       /// This iterator goes trough the \e outgoing arcs of a certain node
   197       /// This iterator goes trough the \e outgoing arcs of a certain node
   207       /// of a digraph.
   198       /// of a digraph.
   208       /// Its usage is quite simple, for example you can count the number
   199       /// Its usage is quite simple, for example you can count the number
   209       /// of outgoing arcs of a node \c n
   200       /// of outgoing arcs of a node \c n
   210       /// in digraph \c g of type \c Digraph as follows.
   201       /// in a digraph \c g of type \c %Digraph as follows.
   211       ///\code
   202       ///\code
   212       /// int count=0;
   203       /// int count=0;
   213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   204       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
   214       ///\endcode
   205       ///\endcode
   215 
       
   216       class OutArcIt : public Arc {
   206       class OutArcIt : public Arc {
   217       public:
   207       public:
   218         /// Default constructor
   208         /// Default constructor
   219 
   209 
   220         /// @warning The default constructor sets the iterator
   210         /// Default constructor.
   221         /// to an undefined value.
   211         /// \warning It sets the iterator to an undefined value.
   222         OutArcIt() { }
   212         OutArcIt() { }
   223         /// Copy constructor.
   213         /// Copy constructor.
   224 
   214 
   225         /// Copy constructor.
   215         /// Copy constructor.
   226         ///
   216         ///
   227         OutArcIt(const OutArcIt& e) : Arc(e) { }
   217         OutArcIt(const OutArcIt& e) : Arc(e) { }
   228         /// Initialize the iterator to be invalid.
   218         /// %Invalid constructor \& conversion.
   229 
   219 
   230         /// Initialize the iterator to be invalid.
   220         /// Initializes the iterator to be invalid.
   231         ///
   221         /// \sa Invalid for more details.
   232         OutArcIt(Invalid) { }
   222         OutArcIt(Invalid) { }
   233         /// This constructor sets the iterator to the first outgoing arc.
   223         /// Sets the iterator to the first outgoing arc.
   234 
   224 
   235         /// This constructor sets the iterator to the first outgoing arc of
   225         /// Sets the iterator to the first outgoing arc of the given node.
   236         /// the node.
   226         ///
   237         OutArcIt(const Digraph&, const Node&) { }
   227         OutArcIt(const Digraph&, const Node&) { }
   238         /// Arc -> OutArcIt conversion
   228         /// Sets the iterator to the given arc.
   239 
   229 
   240         /// Sets the iterator to the value of the trivial iterator.
   230         /// Sets the iterator to the given arc of the given digraph.
   241         /// This feature necessitates that each time we
   231         ///
   242         /// iterate the arc-set, the iteration order is the same.
       
   243         OutArcIt(const Digraph&, const Arc&) { }
   232         OutArcIt(const Digraph&, const Arc&) { }
   244         ///Next outgoing arc
   233         /// Next outgoing arc
   245 
   234 
   246         /// Assign the iterator to the next
   235         /// Assign the iterator to the next
   247         /// outgoing arc of the corresponding node.
   236         /// outgoing arc of the corresponding node.
   248         OutArcIt& operator++() { return *this; }
   237         OutArcIt& operator++() { return *this; }
   249       };
   238       };
   250 
   239 
   251       /// This iterator goes trough the incoming arcs of a node.
   240       /// Iterator class for the incoming arcs of a node.
   252 
   241 
   253       /// This iterator goes trough the \e incoming arcs of a certain node
   242       /// This iterator goes trough the \e incoming arcs of a certain node
   254       /// of a digraph.
   243       /// of a digraph.
   255       /// Its usage is quite simple, for example you can count the number
   244       /// Its usage is quite simple, for example you can count the number
   256       /// of outgoing arcs of a node \c n
   245       /// of incoming arcs of a node \c n
   257       /// in digraph \c g of type \c Digraph as follows.
   246       /// in a digraph \c g of type \c %Digraph as follows.
   258       ///\code
   247       ///\code
   259       /// int count=0;
   248       /// int count=0;
   260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
   249       /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
   261       ///\endcode
   250       ///\endcode
   262 
       
   263       class InArcIt : public Arc {
   251       class InArcIt : public Arc {
   264       public:
   252       public:
   265         /// Default constructor
   253         /// Default constructor
   266 
   254 
   267         /// @warning The default constructor sets the iterator
   255         /// Default constructor.
   268         /// to an undefined value.
   256         /// \warning It sets the iterator to an undefined value.
   269         InArcIt() { }
   257         InArcIt() { }
   270         /// Copy constructor.
   258         /// Copy constructor.
   271 
   259 
   272         /// Copy constructor.
   260         /// Copy constructor.
   273         ///
   261         ///
   274         InArcIt(const InArcIt& e) : Arc(e) { }
   262         InArcIt(const InArcIt& e) : Arc(e) { }
   275         /// Initialize the iterator to be invalid.
   263         /// %Invalid constructor \& conversion.
   276 
   264 
   277         /// Initialize the iterator to be invalid.
   265         /// Initializes the iterator to be invalid.
   278         ///
   266         /// \sa Invalid for more details.
   279         InArcIt(Invalid) { }
   267         InArcIt(Invalid) { }
   280         /// This constructor sets the iterator to first incoming arc.
   268         /// Sets the iterator to the first incoming arc.
   281 
   269 
   282         /// This constructor set the iterator to the first incoming arc of
   270         /// Sets the iterator to the first incoming arc of the given node.
   283         /// the node.
   271         ///
   284         InArcIt(const Digraph&, const Node&) { }
   272         InArcIt(const Digraph&, const Node&) { }
   285         /// Arc -> InArcIt conversion
   273         /// Sets the iterator to the given arc.
   286 
   274 
   287         /// Sets the iterator to the value of the trivial iterator \c e.
   275         /// Sets the iterator to the given arc of the given digraph.
   288         /// This feature necessitates that each time we
   276         ///
   289         /// iterate the arc-set, the iteration order is the same.
       
   290         InArcIt(const Digraph&, const Arc&) { }
   277         InArcIt(const Digraph&, const Arc&) { }
   291         /// Next incoming arc
   278         /// Next incoming arc
   292 
   279 
   293         /// Assign the iterator to the next inarc of the corresponding node.
   280         /// Assign the iterator to the next
   294         ///
   281         /// incoming arc of the corresponding node.
   295         InArcIt& operator++() { return *this; }
   282         InArcIt& operator++() { return *this; }
   296       };
   283       };
   297       /// This iterator goes through each arc.
   284 
   298 
   285       /// Iterator class for the arcs.
   299       /// This iterator goes through each arc of a digraph.
   286 
       
   287       /// This iterator goes through each arc of the digraph.
   300       /// Its usage is quite simple, for example you can count the number
   288       /// Its usage is quite simple, for example you can count the number
   301       /// of arcs in a digraph \c g of type \c Digraph as follows:
   289       /// of arcs in a digraph \c g of type \c %Digraph as follows:
   302       ///\code
   290       ///\code
   303       /// int count=0;
   291       /// int count=0;
   304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
   292       /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
   305       ///\endcode
   293       ///\endcode
   306       class ArcIt : public Arc {
   294       class ArcIt : public Arc {
   307       public:
   295       public:
   308         /// Default constructor
   296         /// Default constructor
   309 
   297 
   310         /// @warning The default constructor sets the iterator
   298         /// Default constructor.
   311         /// to an undefined value.
   299         /// \warning It sets the iterator to an undefined value.
   312         ArcIt() { }
   300         ArcIt() { }
   313         /// Copy constructor.
   301         /// Copy constructor.
   314 
   302 
   315         /// Copy constructor.
   303         /// Copy constructor.
   316         ///
   304         ///
   317         ArcIt(const ArcIt& e) : Arc(e) { }
   305         ArcIt(const ArcIt& e) : Arc(e) { }
   318         /// Initialize the iterator to be invalid.
   306         /// %Invalid constructor \& conversion.
   319 
   307 
   320         /// Initialize the iterator to be invalid.
   308         /// Initializes the iterator to be invalid.
   321         ///
   309         /// \sa Invalid for more details.
   322         ArcIt(Invalid) { }
   310         ArcIt(Invalid) { }
   323         /// This constructor sets the iterator to the first arc.
   311         /// Sets the iterator to the first arc.
   324 
   312 
   325         /// This constructor sets the iterator to the first arc of \c g.
   313         /// Sets the iterator to the first arc of the given digraph.
   326         ///@param g the digraph
   314         ///
   327         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
   315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
   328         /// Arc -> ArcIt conversion
   316         /// Sets the iterator to the given arc.
   329 
   317 
   330         /// Sets the iterator to the value of the trivial iterator \c e.
   318         /// Sets the iterator to the given arc of the given digraph.
   331         /// This feature necessitates that each time we
   319         ///
   332         /// iterate the arc-set, the iteration order is the same.
       
   333         ArcIt(const Digraph&, const Arc&) { }
   320         ArcIt(const Digraph&, const Arc&) { }
   334         ///Next arc
   321         /// Next arc
   335 
   322 
   336         /// Assign the iterator to the next arc.
   323         /// Assign the iterator to the next arc.
       
   324         ///
   337         ArcIt& operator++() { return *this; }
   325         ArcIt& operator++() { return *this; }
   338       };
   326       };
   339       ///Gives back the target node of an arc.
   327 
   340 
   328       /// \brief The source node of the arc.
   341       ///Gives back the target node of an arc.
   329       ///
   342       ///
   330       /// Returns the source node of the given arc.
       
   331       Node source(Arc) const { return INVALID; }
       
   332 
       
   333       /// \brief The target node of the arc.
       
   334       ///
       
   335       /// Returns the target node of the given arc.
   343       Node target(Arc) const { return INVALID; }
   336       Node target(Arc) const { return INVALID; }
   344       ///Gives back the source node of an arc.
   337 
   345 
   338       /// \brief The ID of the node.
   346       ///Gives back the source node of an arc.
   339       ///
   347       ///
   340       /// Returns the ID of the given node.
   348       Node source(Arc) const { return INVALID; }
       
   349 
       
   350       /// \brief Returns the ID of the node.
       
   351       int id(Node) const { return -1; }
   341       int id(Node) const { return -1; }
   352 
   342 
   353       /// \brief Returns the ID of the arc.
   343       /// \brief The ID of the arc.
       
   344       ///
       
   345       /// Returns the ID of the given arc.
   354       int id(Arc) const { return -1; }
   346       int id(Arc) const { return -1; }
   355 
   347 
   356       /// \brief Returns the node with the given ID.
   348       /// \brief The node with the given ID.
   357       ///
   349       ///
   358       /// \pre The argument should be a valid node ID in the graph.
   350       /// Returns the node with the given ID.
       
   351       /// \pre The argument should be a valid node ID in the digraph.
   359       Node nodeFromId(int) const { return INVALID; }
   352       Node nodeFromId(int) const { return INVALID; }
   360 
   353 
   361       /// \brief Returns the arc with the given ID.
   354       /// \brief The arc with the given ID.
   362       ///
   355       ///
   363       /// \pre The argument should be a valid arc ID in the graph.
   356       /// Returns the arc with the given ID.
       
   357       /// \pre The argument should be a valid arc ID in the digraph.
   364       Arc arcFromId(int) const { return INVALID; }
   358       Arc arcFromId(int) const { return INVALID; }
   365 
   359 
   366       /// \brief Returns an upper bound on the node IDs.
   360       /// \brief An upper bound on the node IDs.
       
   361       ///
       
   362       /// Returns an upper bound on the node IDs.
   367       int maxNodeId() const { return -1; }
   363       int maxNodeId() const { return -1; }
   368 
   364 
   369       /// \brief Returns an upper bound on the arc IDs.
   365       /// \brief An upper bound on the arc IDs.
       
   366       ///
       
   367       /// Returns an upper bound on the arc IDs.
   370       int maxArcId() const { return -1; }
   368       int maxArcId() const { return -1; }
   371 
   369 
   372       void first(Node&) const {}
   370       void first(Node&) const {}
   373       void next(Node&) const {}
   371       void next(Node&) const {}
   374 
   372 
   390       // Dummy parameter.
   388       // Dummy parameter.
   391       int maxId(Node) const { return -1; }
   389       int maxId(Node) const { return -1; }
   392       // Dummy parameter.
   390       // Dummy parameter.
   393       int maxId(Arc) const { return -1; }
   391       int maxId(Arc) const { return -1; }
   394 
   392 
       
   393       /// \brief The opposite node on the arc.
       
   394       ///
       
   395       /// Returns the opposite node on the given arc.
       
   396       Node oppositeNode(Node, Arc) const { return INVALID; }
       
   397 
   395       /// \brief The base node of the iterator.
   398       /// \brief The base node of the iterator.
   396       ///
   399       ///
   397       /// Gives back the base node of the iterator.
   400       /// Returns the base node of the given outgoing arc iterator
   398       /// It is always the target of the pointed arc.
   401       /// (i.e. the source node of the corresponding arc).
   399       Node baseNode(const InArcIt&) const { return INVALID; }
   402       Node baseNode(OutArcIt) const { return INVALID; }
   400 
   403 
   401       /// \brief The running node of the iterator.
   404       /// \brief The running node of the iterator.
   402       ///
   405       ///
   403       /// Gives back the running node of the iterator.
   406       /// Returns the running node of the given outgoing arc iterator
   404       /// It is always the source of the pointed arc.
   407       /// (i.e. the target node of the corresponding arc).
   405       Node runningNode(const InArcIt&) const { return INVALID; }
   408       Node runningNode(OutArcIt) const { return INVALID; }
   406 
   409 
   407       /// \brief The base node of the iterator.
   410       /// \brief The base node of the iterator.
   408       ///
   411       ///
   409       /// Gives back the base node of the iterator.
   412       /// Returns the base node of the given incomming arc iterator
   410       /// It is always the source of the pointed arc.
   413       /// (i.e. the target node of the corresponding arc).
   411       Node baseNode(const OutArcIt&) const { return INVALID; }
   414       Node baseNode(InArcIt) const { return INVALID; }
   412 
   415 
   413       /// \brief The running node of the iterator.
   416       /// \brief The running node of the iterator.
   414       ///
   417       ///
   415       /// Gives back the running node of the iterator.
   418       /// Returns the running node of the given incomming arc iterator
   416       /// It is always the target of the pointed arc.
   419       /// (i.e. the source node of the corresponding arc).
   417       Node runningNode(const OutArcIt&) const { return INVALID; }
   420       Node runningNode(InArcIt) const { return INVALID; }
   418 
   421 
   419       /// \brief The opposite node on the given arc.
   422       /// \brief Standard graph map type for the nodes.
   420       ///
   423       ///
   421       /// Gives back the opposite node on the given arc.
   424       /// Standard graph map type for the nodes.
   422       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
   425       /// It conforms to the ReferenceMap concept.
   423 
       
   424       /// \brief Reference map of the nodes to type \c T.
       
   425       ///
       
   426       /// Reference map of the nodes to type \c T.
       
   427       template<class T>
   426       template<class T>
   428       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
   427       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
   429       public:
   428       public:
   430 
   429 
   431         ///\e
   430         /// Constructor
   432         NodeMap(const Digraph&) { }
   431         explicit NodeMap(const Digraph&) { }
   433         ///\e
   432         /// Constructor with given initial value
   434         NodeMap(const Digraph&, T) { }
   433         NodeMap(const Digraph&, T) { }
   435 
   434 
   436       private:
   435       private:
   437         ///Copy constructor
   436         ///Copy constructor
   438         NodeMap(const NodeMap& nm) : 
   437         NodeMap(const NodeMap& nm) : 
   443           checkConcept<ReadMap<Node, T>, CMap>();
   442           checkConcept<ReadMap<Node, T>, CMap>();
   444           return *this;
   443           return *this;
   445         }
   444         }
   446       };
   445       };
   447 
   446 
   448       /// \brief Reference map of the arcs to type \c T.
   447       /// \brief Standard graph map type for the arcs.
   449       ///
   448       ///
   450       /// Reference map of the arcs to type \c T.
   449       /// Standard graph map type for the arcs.
       
   450       /// It conforms to the ReferenceMap concept.
   451       template<class T>
   451       template<class T>
   452       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
   452       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
   453       public:
   453       public:
   454 
   454 
   455         ///\e
   455         /// Constructor
   456         ArcMap(const Digraph&) { }
   456         explicit ArcMap(const Digraph&) { }
   457         ///\e
   457         /// Constructor with given initial value
   458         ArcMap(const Digraph&, T) { }
   458         ArcMap(const Digraph&, T) { }
       
   459 
   459       private:
   460       private:
   460         ///Copy constructor
   461         ///Copy constructor
   461         ArcMap(const ArcMap& em) :
   462         ArcMap(const ArcMap& em) :
   462           ReferenceMap<Arc, T, T&, const T&>(em) { }
   463           ReferenceMap<Arc, T, T&, const T&>(em) { }
   463         ///Assignment operator
   464         ///Assignment operator