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