COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/concepts/graph.h

    r704 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of Undirected Graphs.
     21///\brief The concept of undirected graphs.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_H
    … …  
    2525
    2626#include <lemon/concepts/graph_components.h>
     27#include <lemon/concepts/maps.h>
     28#include <lemon/concept_check.h>
    2729#include <lemon/core.h>
    2830
    … …  
    3234    /// \ingroup graph_concepts
    3335    ///
    34     /// \brief Class describing the concept of Undirected Graphs.
     36    /// \brief Class describing the concept of undirected graphs.
    3537    ///
    36     /// This class describes the common interface of all Undirected
    37     /// Graphs.
     38    /// This class describes the common interface of all undirected
     39    /// graphs.
    3840    ///
    39     /// As all concept describing classes it provides only interface
    40     /// without any sensible implementation. So any algorithm for
    41     /// undirected graph should compile with this class, but it will not
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// undirected graphs should compile with this class, but it will not
    4244    /// run properly, of course.
     45    /// An actual graph implementation like \ref ListGraph or
     46    /// \ref SmartGraph may have additional functionality.
    4347    ///
    44     /// The LEMON undirected graphs also fulfill the concept of
    45     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
    46     /// Concept"). Each edges can be seen as two opposite
    47     /// directed arc and consequently the undirected graph can be
    48     /// seen as the direceted graph of these directed arcs. The
    49     /// Graph has the Edge inner class for the edges and
    50     /// the Arc type for the directed arcs. The Arc type is
    51     /// convertible to Edge or inherited from it so from a directed
    52     /// arc we can get the represented edge.
     48    /// The undirected graphs also fulfill the concept of \ref Digraph
     49    /// "directed graphs", since each edge can also be regarded as two
     50    /// oppositely directed arcs.
     51    /// Undirected graphs provide an Edge type for the undirected edges and
     52    /// an Arc type for the directed arcs. The Arc type is convertible to
     53    /// Edge or inherited from it, i.e. the corresponding edge can be
     54    /// obtained from an arc.
     55    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
     56    /// and ArcMap classes can be used for the arcs (just like in digraphs).
     57    /// Both InArcIt and OutArcIt iterates on the same edges but with
     58    /// opposite direction. IncEdgeIt also iterates on the same edges
     59    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
     60    /// only to Edge.
    5361    ///
    54     /// In the sense of the LEMON each edge has a default
    55     /// direction (it should be in every computer implementation,
    56     /// because the order of edge's nodes defines an
    57     /// orientation). With the default orientation we can define that
    58     /// the directed arc is forward or backward directed. With the \c
    59     /// direction() and \c direct() function we can get the direction
    60     /// of the directed arc and we can direct an edge.
     62    /// In LEMON, each undirected edge has an inherent orientation.
     63    /// Thus it can defined if an arc is forward or backward oriented in
     64    /// an undirected graph with respect to this default oriantation of
     65    /// the represented edge.
     66    /// With the direction() and direct() functions the direction
     67    /// of an arc can be obtained and set, respectively.
    6168    ///
    62     /// The EdgeIt is an iterator for the edges. We can use
    63     /// the EdgeMap to map values for the edges. The InArcIt and
    64     /// OutArcIt iterates on the same edges but with opposite
    65     /// direction. The IncEdgeIt iterates also on the same edges
    66     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    67     /// to Edge.
     69    /// Only nodes and edges can be added to or removed from an undirected
     70    /// graph and the corresponding arcs are added or removed automatically.
     71    ///
     72    /// \sa Digraph
    6873    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
    6981    public:
    70       /// \brief The undirected graph should be tagged by the
    71       /// UndirectedTag.
    72       ///
    73       /// The undirected graph should be tagged by the UndirectedTag. This
    74       /// tag helps the enable_if technics to make compile time
     82      /// Default constructor.
     83      Graph() {}
     84
     85      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
     86      ///
     87      /// Undirected graphs should be tagged with \c UndirectedTag.
     88      ///
     89      /// This tag helps the \c enable_if technics to make compile time
    7590      /// specializations for undirected graphs.
    7691      typedef True UndirectedTag;
    7792
    78       /// \brief The base type of node iterators,
    79       /// or in other words, the trivial node iterator.
    80       ///
    81       /// This is the base type of each node iterator,
    82       /// thus each kind of node iterator converts to this.
    83       /// More precisely each kind of node iterator should be inherited
    84       /// from the trivial node iterator.
     93      /// The node type of the graph
     94
     95      /// This class identifies a node of the graph. It also serves
     96      /// as a base class of the node iterators,
     97      /// thus they convert to this type.
    8598      class Node {
    8699      public:
    87100        /// Default constructor
    88101
    89         /// @warning The default constructor sets the iterator
    90         /// to an undefined value.
     102        /// Default constructor.
     103        /// \warning It sets the object to an undefined value.
    91104        Node() { }
    92105        /// Copy constructor.
    … …  
    96109        Node(const Node&) { }
    97110
    98         /// Invalid constructor \& conversion.
    99 
    100         /// This constructor initializes the iterator to be invalid.
     111        /// %Invalid constructor \& conversion.
     112
     113        /// Initializes the object to be invalid.
    101114        /// \sa Invalid for more details.
    102115        Node(Invalid) { }
    103116        /// Equality operator
    104117
     118        /// Equality operator.
     119        ///
    105120        /// 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.
    107122        bool operator==(Node) const { return true; }
    108123
    109124        /// Inequality operator
    110125
    111         /// \sa operator==(Node n)
    112         ///
     126        /// Inequality operator.
    113127        bool operator!=(Node) const { return true; }
    114128
    115129        /// Artificial ordering operator.
    116130
    117         /// To allow the use of graph descriptors as key type in std::map or
    118         /// similar associative container we require this.
    119         ///
    120         /// \note This operator only have to define some strict ordering of
     131        /// Artificial ordering operator.
     132        ///
     133        /// \note This operator only has to define some strict ordering of
    121134        /// the items; this order has nothing to do with the iteration
    122135        /// ordering of the items.
    … …  
    125138      };
    126139
    127       /// This iterator goes through each node.
    128 
    129       /// This iterator goes through each node.
    130       /// Its usage is quite simple, for example you can count the number
    131       /// of nodes in graph \c g of type \c Graph like this:
     140      /// Iterator class for the nodes.
     141
     142      /// This iterator goes through each node of the graph.
     143      /// Its usage is quite simple, for example, you can count the number
     144      /// of nodes in a graph \c g of type \c %Graph like this:
    132145      ///\code
    133146      /// int count=0;
    … …  
    138151        /// Default constructor
    139152
    140         /// @warning The default constructor sets the iterator
    141         /// to an undefined value.
     153        /// Default constructor.
     154        /// \warning It sets the iterator to an undefined value.
    142155        NodeIt() { }
    143156        /// Copy constructor.
    … …  
    146159        ///
    147160        NodeIt(const NodeIt& n) : Node(n) { }
    148         /// Invalid constructor \& conversion.
    149 
    150         /// Initialize the iterator to be invalid.
     161        /// %Invalid constructor \& conversion.
     162
     163        /// Initializes the iterator to be invalid.
    151164        /// \sa Invalid for more details.
    152165        NodeIt(Invalid) { }
    153166        /// Sets the iterator to the first node.
    154167
    155         /// Sets the iterator to the first node of \c g.
    156         ///
    157         NodeIt(const Graph&) { }
    158         /// Node -> NodeIt conversion.
    159 
    160         /// Sets the iterator to the node of \c the graph pointed by
    161         /// the trivial iterator.
    162         /// This feature necessitates that each time we
    163         /// iterate the arc-set, the iteration order is the same.
     168        /// Sets the iterator to the first node of the given digraph.
     169        ///
     170        explicit NodeIt(const Graph&) { }
     171        /// Sets the iterator to the given node.
     172
     173        /// Sets the iterator to the given node of the given digraph.
     174        ///
    164175        NodeIt(const Graph&, const Node&) { }
    165176        /// Next node.
    … …  
    171182
    172183
    173       /// The base type of the edge iterators.
    174 
    175       /// The base type of the edge iterators.
    176       ///
     184      /// The edge type of the graph
     185
     186      /// This class identifies an edge of the graph. It also serves
     187      /// as a base class of the edge iterators,
     188      /// thus they will convert to this type.
    177189      class Edge {
    178190      public:
    179191        /// Default constructor
    180192
    181         /// @warning The default constructor sets the iterator
    182         /// to an undefined value.
     193        /// Default constructor.
     194        /// \warning It sets the object to an undefined value.
    183195        Edge() { }
    184196        /// Copy constructor.
    … …  
    187199        ///
    188200        Edge(const Edge&) { }
    189         /// Initialize the iterator to be invalid.
    190 
    191         /// Initialize the iterator to be invalid.
    192         ///
     201        /// %Invalid constructor \& conversion.
     202
     203        /// Initializes the object to be invalid.
     204        /// \sa Invalid for more details.
    193205        Edge(Invalid) { }
    194206        /// Equality operator
    195207
     208        /// Equality operator.
     209        ///
    196210        /// 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.
    198212        bool operator==(Edge) const { return true; }
    199213        /// Inequality operator
    200214
    201         /// \sa operator==(Edge n)
    202         ///
     215        /// Inequality operator.
    203216        bool operator!=(Edge) const { return true; }
    204217
    205218        /// Artificial ordering operator.
    206219
    207         /// To allow the use of graph descriptors as key type in std::map or
    208         /// similar associative container we require this.
    209         ///
    210         /// \note This operator only have to define some strict ordering of
    211         /// the items; this order has nothing to do with the iteration
    212         /// ordering of the items.
     220        /// Artificial ordering operator.
     221        ///
     222        /// \note This operator only has to define some strict ordering of
     223        /// the edges; this order has nothing to do with the iteration
     224        /// ordering of the edges.
    213225        bool operator<(Edge) const { return false; }
    214226      };
    215227
    216       /// This iterator goes through each edge.
    217 
    218       /// This iterator goes through each edge of a graph.
    219       /// Its usage is quite simple, for example you can count the number
    220       /// of edges in a graph \c g of type \c Graph as follows:
     228      /// Iterator class for the edges.
     229
     230      /// This iterator goes through each edge of the graph.
     231      /// Its usage is quite simple, for example, you can count the number
     232      /// of edges in a graph \c g of type \c %Graph as follows:
    221233      ///\code
    222234      /// int count=0;
    … …  
    227239        /// Default constructor
    228240
    229         /// @warning The default constructor sets the iterator
    230         /// to an undefined value.
     241        /// Default constructor.
     242        /// \warning It sets the iterator to an undefined value.
    231243        EdgeIt() { }
    232244        /// Copy constructor.
    … …  
    235247        ///
    236248        EdgeIt(const EdgeIt& e) : Edge(e) { }
    237         /// Initialize the iterator to be invalid.
    238 
    239         /// Initialize the iterator to be invalid.
    240         ///
     249        /// %Invalid constructor \& conversion.
     250
     251        /// Initializes the iterator to be invalid.
     252        /// \sa Invalid for more details.
    241253        EdgeIt(Invalid) { }
    242         /// This constructor sets the iterator to the first edge.
    243 
    244         /// This constructor sets the iterator to the first edge.
    245         EdgeIt(const Graph&) { }
    246         /// Edge -> EdgeIt conversion
    247 
    248         /// Sets the iterator to the value of the trivial iterator.
    249         /// This feature necessitates that each time we
    250         /// iterate the edge-set, the iteration order is the
    251         /// same.
     254        /// Sets the iterator to the first edge.
     255
     256        /// Sets the iterator to the first edge of the given graph.
     257        ///
     258        explicit EdgeIt(const Graph&) { }
     259        /// Sets the iterator to the given edge.
     260
     261        /// Sets the iterator to the given edge of the given graph.
     262        ///
    252263        EdgeIt(const Graph&, const Edge&) { }
    253264        /// Next edge
    254265
    255266        /// Assign the iterator to the next edge.
     267        ///
    256268        EdgeIt& operator++() { return *this; }
    257269      };
    258270
    259       /// \brief This iterator goes trough the incident undirected
    260       /// arcs of a node.
    261       ///
    262       /// This iterator goes trough the incident edges
    263       /// of a certain node of a graph. You should assume that the
    264       /// loop arcs will be iterated twice.
    265       ///
    266       /// Its usage is quite simple, for example you can compute the
    267       /// degree (i.e. count the number of incident arcs of a node \c n
    268       /// in graph \c g of type \c Graph as follows.
     271      /// Iterator class for the incident edges of a node.
     272
     273      /// This iterator goes trough the incident undirected edges
     274      /// of a certain node of a graph.
     275      /// Its usage is quite simple, for example, you can compute the
     276      /// degree (i.e. the number of incident edges) of a node \c n
     277      /// in a graph \c g of type \c %Graph as follows.
    269278      ///
    270279      ///\code
    … …  
    272281      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    273282      ///\endcode
     283      ///
     284      /// \warning Loop edges will be iterated twice.
    274285      class IncEdgeIt : public Edge {
    275286      public:
    276287        /// Default constructor
    277288
    278         /// @warning The default constructor sets the iterator
    279         /// to an undefined value.
     289        /// Default constructor.
     290        /// \warning It sets the iterator to an undefined value.
    280291        IncEdgeIt() { }
    281292        /// Copy constructor.
    … …  
    284295        ///
    285296        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    286         /// Initialize the iterator to be invalid.
    287 
    288         /// Initialize the iterator to be invalid.
    289         ///
     297        /// %Invalid constructor \& conversion.
     298
     299        /// Initializes the iterator to be invalid.
     300        /// \sa Invalid for more details.
    290301        IncEdgeIt(Invalid) { }
    291         /// This constructor sets the iterator to first incident arc.
    292 
    293         /// This constructor set the iterator to the first incident arc of
    294         /// the node.
     302        /// Sets the iterator to the first incident edge.
     303
     304        /// Sets the iterator to the first incident edge of the given node.
     305        ///
    295306        IncEdgeIt(const Graph&, const Node&) { }
    296         /// Edge -> IncEdgeIt conversion
    297 
    298         /// Sets the iterator to the value of the trivial iterator \c e.
    299         /// This feature necessitates that each time we
    300         /// iterate the arc-set, the iteration order is the same.
     307        /// Sets the iterator to the given edge.
     308
     309        /// Sets the iterator to the given edge of the given graph.
     310        ///
    301311        IncEdgeIt(const Graph&, const Edge&) { }
    302         /// Next incident arc
    303 
    304         /// Assign the iterator to the next incident arc
     312        /// Next incident edge
     313
     314        /// Assign the iterator to the next incident edge
    305315        /// of the corresponding node.
    306316        IncEdgeIt& operator++() { return *this; }
    307317      };
    308318
    309       /// The directed arc type.
    310 
    311       /// The directed arc type. It can be converted to the
    312       /// edge or it should be inherited from the undirected
    313       /// edge.
     319      /// The arc type of the graph
     320
     321      /// This class identifies a directed arc of the graph. It also serves
     322      /// as a base class of the arc iterators,
     323      /// thus they will convert to this type.
    314324      class Arc {
    315325      public:
    316326        /// Default constructor
    317327
    318         /// @warning The default constructor sets the iterator
    319         /// to an undefined value.
     328        /// Default constructor.
     329        /// \warning It sets the object to an undefined value.
    320330        Arc() { }
    321331        /// Copy constructor.
    … …  
    324334        ///
    325335        Arc(const Arc&) { }
    326         /// Initialize the iterator to be invalid.
    327 
    328         /// Initialize the iterator to be invalid.
    329         ///
     336        /// %Invalid constructor \& conversion.
     337
     338        /// Initializes the object to be invalid.
     339        /// \sa Invalid for more details.
    330340        Arc(Invalid) { }
    331341        /// Equality operator
    332342
     343        /// Equality operator.
     344        ///
    333345        /// 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.
    335347        bool operator==(Arc) const { return true; }
    336348        /// Inequality operator
    337349
    338         /// \sa operator==(Arc n)
    339         ///
     350        /// Inequality operator.
    340351        bool operator!=(Arc) const { return true; }
    341352
    342353        /// Artificial ordering operator.
    343354
    344         /// To allow the use of graph descriptors as key type in std::map or
    345         /// similar associative container we require this.
    346         ///
    347         /// \note This operator only have to define some strict ordering of
    348         /// the items; this order has nothing to do with the iteration
    349         /// ordering of the items.
     355        /// Artificial ordering operator.
     356        ///
     357        /// \note This operator only has to define some strict ordering of
     358        /// the arcs; this order has nothing to do with the iteration
     359        /// ordering of the arcs.
    350360        bool operator<(Arc) const { return false; }
    351361
    352         /// Converison to Edge
     362        /// Converison to \c Edge
     363
     364        /// Converison to \c Edge.
     365        ///
    353366        operator Edge() const { return Edge(); }
    354367      };
    355       /// This iterator goes through each directed arc.
    356 
    357       /// This iterator goes through each arc of a graph.
    358       /// Its usage is quite simple, for example you can count the number
    359       /// of arcs in a graph \c g of type \c Graph as follows:
     368
     369      /// Iterator class for the arcs.
     370
     371      /// This iterator goes through each directed arc of the graph.
     372      /// Its usage is quite simple, for example, you can count the number
     373      /// of arcs in a graph \c g of type \c %Graph as follows:
    360374      ///\code
    361375      /// int count=0;
    362       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
     376      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
    363377      ///\endcode
    364378      class ArcIt : public Arc {
    … …  
    366380        /// Default constructor
    367381
    368         /// @warning The default constructor sets the iterator
    369         /// to an undefined value.
     382        /// Default constructor.
     383        /// \warning It sets the iterator to an undefined value.
    370384        ArcIt() { }
    371385        /// Copy constructor.
    … …  
    374388        ///
    375389        ArcIt(const ArcIt& e) : Arc(e) { }
    376         /// Initialize the iterator to be invalid.
    377 
    378         /// Initialize the iterator to be invalid.
    379         ///
     390        /// %Invalid constructor \& conversion.
     391
     392        /// Initializes the iterator to be invalid.
     393        /// \sa Invalid for more details.
    380394        ArcIt(Invalid) { }
    381         /// This constructor sets the iterator to the first arc.
    382 
    383         /// This constructor sets the iterator to the first arc of \c g.
    384         ///@param g the graph
    385         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
    386         /// Arc -> ArcIt conversion
    387 
    388         /// Sets the iterator to the value of the trivial iterator \c e.
    389         /// This feature necessitates that each time we
    390         /// iterate the arc-set, the iteration order is the same.
     395        /// Sets the iterator to the first arc.
     396
     397        /// Sets the iterator to the first arc of the given graph.
     398        ///
     399        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     400        /// Sets the iterator to the given arc.
     401
     402        /// Sets the iterator to the given arc of the given graph.
     403        ///
    391404        ArcIt(const Graph&, const Arc&) { }
    392         ///Next arc
     405        /// Next arc
    393406
    394407        /// Assign the iterator to the next arc.
     408        ///
    395409        ArcIt& operator++() { return *this; }
    396410      };
    397411
    398       /// This iterator goes trough the outgoing directed arcs of a node.
    399 
    400       /// This iterator goes trough the \e outgoing arcs of a certain node
    401       /// of a graph.
    402       /// Its usage is quite simple, for example you can count the number
     412      /// Iterator class for the outgoing arcs of a node.
     413
     414      /// This iterator goes trough the \e outgoing directed arcs of a
     415      /// certain node of a graph.
     416      /// Its usage is quite simple, for example, you can count the number
    403417      /// 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.
    405419      ///\code
    406420      /// 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;
    408422      ///\endcode
    409 
    410423      class OutArcIt : public Arc {
    411424      public:
    412425        /// Default constructor
    413426
    414         /// @warning The default constructor sets the iterator
    415         /// to an undefined value.
     427        /// Default constructor.
     428        /// \warning It sets the iterator to an undefined value.
    416429        OutArcIt() { }
    417430        /// Copy constructor.
    … …  
    420433        ///
    421434        OutArcIt(const OutArcIt& e) : Arc(e) { }
    422         /// Initialize the iterator to be invalid.
    423 
    424         /// Initialize the iterator to be invalid.
    425         ///
     435        /// %Invalid constructor \& conversion.
     436
     437        /// Initializes the iterator to be invalid.
     438        /// \sa Invalid for more details.
    426439        OutArcIt(Invalid) { }
    427         /// This constructor sets the iterator to the first outgoing arc.
    428 
    429         /// This constructor sets the iterator to the first outgoing arc of
    430         /// the node.
    431         ///@param n the node
    432         ///@param g the graph
     440        /// Sets the iterator to the first outgoing arc.
     441
     442        /// Sets the iterator to the first outgoing arc of the given node.
     443        ///
    433444        OutArcIt(const Graph& n, const Node& g) {
    434445          ignore_unused_variable_warning(n);
    435446          ignore_unused_variable_warning(g);
    436447        }
    437         /// Arc -> OutArcIt conversion
    438 
    439         /// Sets the iterator to the value of the trivial iterator.
    440         /// This feature necessitates that each time we
    441         /// iterate the arc-set, the iteration order is the same.
     448        /// Sets the iterator to the given arc.
     449
     450        /// Sets the iterator to the given arc of the given graph.
     451        ///
    442452        OutArcIt(const Graph&, const Arc&) { }
    443         ///Next outgoing arc
     453        /// Next outgoing arc
    444454
    445455        /// Assign the iterator to the next
    … …  
    448458      };
    449459
    450       /// This iterator goes trough the incoming directed arcs of a node.
    451 
    452       /// This iterator goes trough the \e incoming arcs of a certain node
    453       /// of a graph.
    454       /// Its usage is quite simple, for example you can count the number
    455       /// of outgoing arcs of a node \c n
    456       /// in graph \c g of type \c Graph as follows.
     460      /// Iterator class for the incoming arcs of a node.
     461
     462      /// This iterator goes trough the \e incoming directed arcs of a
     463      /// certain node of a graph.
     464      /// Its usage is quite simple, for example, you can count the number
     465      /// of incoming arcs of a node \c n
     466      /// in a graph \c g of type \c %Graph as follows.
    457467      ///\code
    458468      /// 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;
    460470      ///\endcode
    461 
    462471      class InArcIt : public Arc {
    463472      public:
    464473        /// Default constructor
    465474
    466         /// @warning The default constructor sets the iterator
    467         /// to an undefined value.
     475        /// Default constructor.
     476        /// \warning It sets the iterator to an undefined value.
    468477        InArcIt() { }
    469478        /// Copy constructor.
    … …  
    472481        ///
    473482        InArcIt(const InArcIt& e) : Arc(e) { }
    474         /// Initialize the iterator to be invalid.
    475 
    476         /// Initialize the iterator to be invalid.
    477         ///
     483        /// %Invalid constructor \& conversion.
     484
     485        /// Initializes the iterator to be invalid.
     486        /// \sa Invalid for more details.
    478487        InArcIt(Invalid) { }
    479         /// This constructor sets the iterator to first incoming arc.
    480 
    481         /// This constructor set the iterator to the first incoming arc of
    482         /// the node.
    483         ///@param n the node
    484         ///@param g the graph
     488        /// Sets the iterator to the first incoming arc.
     489
     490        /// Sets the iterator to the first incoming arc of the given node.
     491        ///
    485492        InArcIt(const Graph& g, const Node& n) {
    486493          ignore_unused_variable_warning(n);
    487494          ignore_unused_variable_warning(g);
    488495        }
    489         /// Arc -> InArcIt conversion
    490 
    491         /// Sets the iterator to the value of the trivial iterator \c e.
    492         /// This feature necessitates that each time we
    493         /// iterate the arc-set, the iteration order is the same.
     496        /// Sets the iterator to the given arc.
     497
     498        /// Sets the iterator to the given arc of the given graph.
     499        ///
    494500        InArcIt(const Graph&, const Arc&) { }
    495501        /// Next incoming arc
    496502
    497         /// Assign the iterator to the next inarc of the corresponding node.
    498         ///
     503        /// Assign the iterator to the next
     504        /// incoming arc of the corresponding node.
    499505        InArcIt& operator++() { return *this; }
    500506      };
    501507
    502       /// \brief Reference map of the nodes to type \c T.
    503       ///
    504       /// Reference map of the nodes to type \c T.
     508      /// \brief Standard graph map type for the nodes.
     509      ///
     510      /// Standard graph map type for the nodes.
     511      /// It conforms to the ReferenceMap concept.
    505512      template<class T>
    506513      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    … …  
    508515      public:
    509516
    510         ///\e
    511         NodeMap(const Graph&) { }
    512         ///\e
     517        /// Constructor
     518        explicit NodeMap(const Graph&) { }
     519        /// Constructor with given initial value
    513520        NodeMap(const Graph&, T) { }
    514521
    … …  
    525532      };
    526533
    527       /// \brief Reference map of the arcs to type \c T.
    528       ///
    529       /// Reference map of the arcs to type \c T.
     534      /// \brief Standard graph map type for the arcs.
     535      ///
     536      /// Standard graph map type for the arcs.
     537      /// It conforms to the ReferenceMap concept.
    530538      template<class T>
    531539      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    … …  
    533541      public:
    534542
    535         ///\e
    536         ArcMap(const Graph&) { }
    537         ///\e
     543        /// Constructor
     544        explicit ArcMap(const Graph&) { }
     545        /// Constructor with given initial value
    538546        ArcMap(const Graph&, T) { }
     547
    539548      private:
    540549        ///Copy constructor
    … …  
    549558      };
    550559
    551       /// Reference map of the edges to type \c T.
    552 
    553       /// Reference map of the edges to type \c T.
     560      /// \brief Standard graph map type for the edges.
     561      ///
     562      /// Standard graph map type for the edges.
     563      /// It conforms to the ReferenceMap concept.
    554564      template<class T>
    555565      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    … …  
    557567      public:
    558568
    559         ///\e
    560         EdgeMap(const Graph&) { }
    561         ///\e
     569        /// Constructor
     570        explicit EdgeMap(const Graph&) { }
     571        /// Constructor with given initial value
    562572        EdgeMap(const Graph&, T) { }
     573
    563574      private:
    564575        ///Copy constructor
    … …  
    573584      };
    574585
    575       /// \brief Direct the given edge.
    576       ///
    577       /// Direct the given edge. The returned arc source
    578       /// will be the given node.
    579       Arc direct(const Edge&, const Node&) const {
    580         return INVALID;
    581       }
    582 
    583       /// \brief Direct the given edge.
    584       ///
    585       /// Direct the given edge. The returned arc
    586       /// represents the given edge and the direction comes
    587       /// from the bool parameter. The source of the edge and
    588       /// the directed arc is the same when the given bool is true.
    589       Arc direct(const Edge&, bool) const {
    590         return INVALID;
    591       }
    592 
    593       /// \brief Returns true if the arc has default orientation.
    594       ///
    595       /// Returns whether the given directed arc is same orientation as
    596       /// the corresponding edge's default orientation.
    597       bool direction(Arc) const { return true; }
    598 
    599       /// \brief Returns the opposite directed arc.
    600       ///
    601       /// Returns the opposite directed arc.
    602       Arc oppositeArc(Arc) const { return INVALID; }
    603 
    604       /// \brief Opposite node on an arc
    605       ///
    606       /// \return The opposite of the given node on the given edge.
    607       Node oppositeNode(Node, Edge) const { return INVALID; }
    608 
    609       /// \brief First node of the edge.
    610       ///
    611       /// \return The first node of the given edge.
    612       ///
    613       /// Naturally edges don't have direction and thus
    614       /// don't have source and target node. However we use \c u() and \c v()
    615       /// methods to query the two nodes of the arc. The direction of the
    616       /// arc which arises this way is called the inherent direction of the
    617       /// edge, and is used to define the "default" direction
    618       /// of the directed versions of the arcs.
     586      /// \brief The first node of the edge.
     587      ///
     588      /// Returns the first node of the given edge.
     589      ///
     590      /// Edges don't have source and target nodes, however, methods
     591      /// u() and v() are used to query the two end-nodes of an edge.
     592      /// The orientation of an edge that arises this way is called
     593      /// the inherent direction, it is used to define the default
     594      /// direction for the corresponding arcs.
    619595      /// \sa v()
    620596      /// \sa direction()
    621597      Node u(Edge) const { return INVALID; }
    622598
    623       /// \brief Second node of the edge.
    624       ///
    625       /// \return The second node of the given edge.
    626       ///
    627       /// Naturally edges don't have direction and thus
    628       /// don't have source and target node. However we use \c u() and \c v()
    629       /// methods to query the two nodes of the arc. The direction of the
    630       /// arc which arises this way is called the inherent direction of the
    631       /// edge, and is used to define the "default" direction
    632       /// of the directed versions of the arcs.
     599      /// \brief The second node of the edge.
     600      ///
     601      /// Returns the second node of the given edge.
     602      ///
     603      /// Edges don't have source and target nodes, however, methods
     604      /// u() and v() are used to query the two end-nodes of an edge.
     605      /// The orientation of an edge that arises this way is called
     606      /// the inherent direction, it is used to define the default
     607      /// direction for the corresponding arcs.
    633608      /// \sa u()
    634609      /// \sa direction()
    635610      Node v(Edge) const { return INVALID; }
    636611
    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.
    638615      Node source(Arc) const { return INVALID; }
    639616
    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.
    641620      Node target(Arc) const { return INVALID; }
    642621
    643       /// \brief Returns the id of the node.
     622      /// \brief The ID of the node.
     623      ///
     624      /// Returns the ID of the given node.
    644625      int id(Node) const { return -1; }
    645626
    646       /// \brief Returns the id of the edge.
     627      /// \brief The ID of the edge.
     628      ///
     629      /// Returns the ID of the given edge.
    647630      int id(Edge) const { return -1; }
    648631
    649       /// \brief Returns the id of the arc.
     632      /// \brief The ID of the arc.
     633      ///
     634      /// Returns the ID of the given arc.
    650635      int id(Arc) const { return -1; }
    651636
    652       /// \brief Returns the node with the given id.
    653       ///
    654       /// \pre The argument should be a valid node id in the graph.
     637      /// \brief The node with the given ID.
     638      ///
     639      /// Returns the node with the given ID.
     640      /// \pre The argument should be a valid node ID in the graph.
    655641      Node nodeFromId(int) const { return INVALID; }
    656642
    657       /// \brief Returns the edge with the given id.
    658       ///
    659       /// \pre The argument should be a valid edge id in the graph.
     643      /// \brief The edge with the given ID.
     644      ///
     645      /// Returns the edge with the given ID.
     646      /// \pre The argument should be a valid edge ID in the graph.
    660647      Edge edgeFromId(int) const { return INVALID; }
    661648
    662       /// \brief Returns the arc with the given id.
    663       ///
    664       /// \pre The argument should be a valid arc id in the graph.
     649      /// \brief The arc with the given ID.
     650      ///
     651      /// Returns the arc with the given ID.
     652      /// \pre The argument should be a valid arc ID in the graph.
    665653      Arc arcFromId(int) const { return INVALID; }
    666654
    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.
    668658      int maxNodeId() const { return -1; }
    669659
    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.
    671663      int maxEdgeId() const { return -1; }
    672664
    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.
    674668      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; }
    675703
    676704      void first(Node&) const {}
    … …  
    706734      int maxId(Arc) const { return -1; }
    707735
    708       /// \brief Base node of the iterator
    709       ///
    710       /// Returns the base node (the source in this case) of the iterator
    711       Node baseNode(OutArcIt e) const {
    712         return source(e);
    713       }
    714       /// \brief Running node of the iterator
    715       ///
    716       /// Returns the running node (the target in this case) of the
    717       /// iterator
    718       Node runningNode(OutArcIt e) const {
    719         return target(e);
    720       }
    721 
    722       /// \brief Base node of the iterator
    723       ///
    724       /// Returns the base node (the target in this case) of the iterator
    725       Node baseNode(InArcIt e) const {
    726         return target(e);
    727       }
    728       /// \brief Running node of the iterator
    729       ///
    730       /// Returns the running node (the source in this case) of the
    731       /// iterator
    732       Node runningNode(InArcIt e) const {
    733         return source(e);
    734       }
    735 
    736       /// \brief Base node of the iterator
    737       ///
    738       /// Returns the base node of the iterator
    739       Node baseNode(IncEdgeIt) const {
    740         return INVALID;
    741       }
    742 
    743       /// \brief Running node of the iterator
    744       ///
    745       /// Returns the running node of the iterator
    746       Node runningNode(IncEdgeIt) const {
    747         return INVALID;
    748       }
     736      /// \brief The base node of the iterator.
     737      ///
     738      /// Returns the base node of the given incident edge iterator.
     739      Node baseNode(IncEdgeIt) const { return INVALID; }
     740
     741      /// \brief The running node of the iterator.
     742      ///
     743      /// Returns the running node of the given incident edge iterator.
     744      Node runningNode(IncEdgeIt) const { return INVALID; }
     745
     746      /// \brief The base node of the iterator.
     747      ///
     748      /// Returns the base node of the given outgoing arc iterator
     749      /// (i.e. the source node of the corresponding arc).
     750      Node baseNode(OutArcIt) const { return INVALID; }
     751
     752      /// \brief The running node of the iterator.
     753      ///
     754      /// Returns the running node of the given outgoing arc iterator
     755      /// (i.e. the target node of the corresponding arc).
     756      Node runningNode(OutArcIt) const { return INVALID; }
     757
     758      /// \brief The base node of the iterator.
     759      ///
     760      /// Returns the base node of the given incomming arc iterator
     761      /// (i.e. the target node of the corresponding arc).
     762      Node baseNode(InArcIt) const { return INVALID; }
     763
     764      /// \brief The running node of the iterator.
     765      ///
     766      /// Returns the running node of the given incomming arc iterator
     767      /// (i.e. the source node of the corresponding arc).
     768      Node runningNode(InArcIt) const { return INVALID; }
    749769
    750770      template <typename _Graph>
Note: See TracChangeset for help on using the changeset viewer.