COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [741:10c9c3a35b83:739:32baeb8e5c8f] in lemon-1.2


Ignore:
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r735 r663  
    637637\brief Skeleton and concept checking classes for graph structures
    638638
    639 This group contains the skeletons and concept checking classes of
    640 graph structures.
     639This group contains the skeletons and concept checking classes of LEMON's
     640graph structures and helper classes used to implement these.
    641641*/
    642642

  • lemon/concepts/digraph.h

    r734 r580  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the common interface of all directed
    39     /// graphs (digraphs).
     38    /// This class describes the \ref concept "concept" of the
     39    /// immutable directed digraphs.
    4040    ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// directed graphs should compile with this class, but it will not
    44     /// run properly, of course.
    45     /// An actual digraph implementation like \ref ListDigraph or
    46     /// \ref SmartDigraph may have additional functionality.
     41    /// Note that actual digraph implementation like @ref ListDigraph or
     42    /// @ref SmartDigraph may have several additional functionality.
    4743    ///
    48     /// \sa Graph
     44    /// \sa concept
    4945    class Digraph {
    5046    private:
    51       /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
    52       Digraph(const Digraph &) {}
    53       /// \brief Assignment of a digraph to another one is \e not allowed.
    54       /// Use DigraphCopy instead.
     47      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
     48
     49      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
     50      ///
     51      Digraph(const Digraph &) {};
     52      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
     53      ///\e not allowed. Use DigraphCopy() instead.
     54
     55      ///Assignment of \ref Digraph "Digraph"s to another ones are
     56      ///\e not allowed.  Use DigraphCopy() instead.
     57
    5558      void operator=(const Digraph &) {}
    56 
    5759    public:
    58       /// Default constructor.
     60      ///\e
     61
     62      /// Defalult constructor.
     63
     64      /// Defalult constructor.
     65      ///
    5966      Digraph() { }
    60 
    61       /// The node type of the digraph
     67      /// Class for identifying a node of the digraph
    6268
    6369      /// This class identifies a node of the digraph. It also serves
    6470      /// as a base class of the node iterators,
    65       /// thus they convert to this type.
     71      /// thus they will convert to this type.
    6672      class Node {
    6773      public:
    6874        /// Default constructor
    6975
    70         /// Default constructor.
    71         /// \warning It sets the object to an undefined value.
     76        /// @warning The default constructor sets the iterator
     77        /// to an undefined value.
    7278        Node() { }
    7379        /// Copy constructor.
    … …  
    7783        Node(const Node&) { }
    7884
    79         /// %Invalid constructor \& conversion.
    80 
    81         /// Initializes the object to be invalid.
     85        /// Invalid constructor \& conversion.
     86
     87        /// This constructor initializes the iterator to be invalid.
    8288        /// \sa Invalid for more details.
    8389        Node(Invalid) { }
    8490        /// Equality operator
    8591
    86         /// Equality operator.
    87         ///
    8892        /// Two iterators are equal if and only if they point to the
    89         /// same object or both are \c INVALID.
     93        /// same object or both are invalid.
    9094        bool operator==(Node) const { return true; }
    9195
    9296        /// Inequality operator
    9397
    94         /// Inequality operator.
     98        /// \sa operator==(Node n)
     99        ///
    95100        bool operator!=(Node) const { return true; }
    96101
    97102        /// Artificial ordering operator.
    98103
    99         /// Artificial ordering operator.
    100         ///
    101         /// \note This operator only has to define some strict ordering of
    102         /// the nodes; this order has nothing to do with the iteration
    103         /// ordering of the nodes.
     104        /// To allow the use of digraph descriptors as key type in std::map or
     105        /// similar associative container we require this.
     106        ///
     107        /// \note This operator only have to define some strict ordering of
     108        /// the items; this order has nothing to do with the iteration
     109        /// ordering of the items.
    104110        bool operator<(Node) const { return false; }
    105       };
    106 
    107       /// Iterator class for the nodes.
    108 
    109       /// This iterator goes through each node of the digraph.
     111
     112      };
     113
     114      /// This iterator goes through each node.
     115
     116      /// This iterator goes through each node.
    110117      /// Its usage is quite simple, for example you can count the number
    111       /// of nodes in a digraph \c g of type \c %Digraph like this:
     118      /// of nodes in digraph \c g of type \c Digraph like this:
    112119      ///\code
    113120      /// int count=0;
    … …  
    118125        /// Default constructor
    119126
    120         /// Default constructor.
    121         /// \warning It sets the iterator to an undefined value.
     127        /// @warning The default constructor sets the iterator
     128        /// to an undefined value.
    122129        NodeIt() { }
    123130        /// Copy constructor.
    … …  
    126133        ///
    127134        NodeIt(const NodeIt& n) : Node(n) { }
    128         /// %Invalid constructor \& conversion.
    129 
    130         /// Initializes the iterator to be invalid.
     135        /// Invalid constructor \& conversion.
     136
     137        /// Initialize the iterator to be invalid.
    131138        /// \sa Invalid for more details.
    132139        NodeIt(Invalid) { }
    133140        /// Sets the iterator to the first node.
    134141
    135         /// Sets the iterator to the first node of the given digraph.
    136         ///
    137         explicit NodeIt(const Digraph&) { }
    138         /// Sets the iterator to the given node.
    139 
    140         /// Sets the iterator to the given node of the given digraph.
    141         ///
     142        /// Sets the iterator to the first node of \c g.
     143        ///
     144        NodeIt(const Digraph&) { }
     145        /// Node -> NodeIt conversion.
     146
     147        /// Sets the iterator to the node of \c the digraph pointed by
     148        /// the trivial iterator.
     149        /// This feature necessitates that each time we
     150        /// iterate the arc-set, the iteration order is the same.
    142151        NodeIt(const Digraph&, const Node&) { }
    143152        /// Next node.
    … …  
    149158
    150159
    151       /// The arc type of the digraph
     160      /// Class for identifying an arc of the digraph
    152161
    153162      /// This class identifies an arc of the digraph. It also serves
    … …  
    158167        /// Default constructor
    159168
    160         /// Default constructor.
    161         /// \warning It sets the object to an undefined value.
     169        /// @warning The default constructor sets the iterator
     170        /// to an undefined value.
    162171        Arc() { }
    163172        /// Copy constructor.
    … …  
    166175        ///
    167176        Arc(const Arc&) { }
    168         /// %Invalid constructor \& conversion.
    169 
    170         /// Initializes the object to be invalid.
    171         /// \sa Invalid for more details.
     177        /// Initialize the iterator to be invalid.
     178
     179        /// Initialize the iterator to be invalid.
     180        ///
    172181        Arc(Invalid) { }
    173182        /// Equality operator
    174183
    175         /// Equality operator.
    176         ///
    177184        /// Two iterators are equal if and only if they point to the
    178         /// same object or both are \c INVALID.
     185        /// same object or both are invalid.
    179186        bool operator==(Arc) const { return true; }
    180187        /// Inequality operator
    181188
    182         /// Inequality operator.
     189        /// \sa operator==(Arc n)
     190        ///
    183191        bool operator!=(Arc) const { return true; }
    184192
    185193        /// Artificial ordering operator.
    186194
    187         /// Artificial ordering operator.
    188         ///
    189         /// \note This operator only has to define some strict ordering of
    190         /// the arcs; this order has nothing to do with the iteration
    191         /// ordering of the arcs.
     195        /// To allow the use of digraph descriptors as key type in std::map or
     196        /// similar associative container we require this.
     197        ///
     198        /// \note This operator only have to define some strict ordering of
     199        /// the items; this order has nothing to do with the iteration
     200        /// ordering of the items.
    192201        bool operator<(Arc) const { return false; }
    193202      };
    194203
    195       /// Iterator class for the outgoing arcs of a node.
     204      /// This iterator goes trough the outgoing arcs of a node.
    196205
    197206      /// This iterator goes trough the \e outgoing arcs of a certain node
    … …  
    199208      /// Its usage is quite simple, for example you can count the number
    200209      /// of outgoing arcs of a node \c n
    201       /// in a digraph \c g of type \c %Digraph as follows.
     210      /// in digraph \c g of type \c Digraph as follows.
    202211      ///\code
    203212      /// int count=0;
    204       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     213      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    205214      ///\endcode
     215
    206216      class OutArcIt : public Arc {
    207217      public:
    208218        /// Default constructor
    209219
    210         /// Default constructor.
    211         /// \warning It sets the iterator to an undefined value.
     220        /// @warning The default constructor sets the iterator
     221        /// to an undefined value.
    212222        OutArcIt() { }
    213223        /// Copy constructor.
    … …  
    216226        ///
    217227        OutArcIt(const OutArcIt& e) : Arc(e) { }
    218         /// %Invalid constructor \& conversion.
    219 
    220         /// Initializes the iterator to be invalid.
    221         /// \sa Invalid for more details.
     228        /// Initialize the iterator to be invalid.
     229
     230        /// Initialize the iterator to be invalid.
     231        ///
    222232        OutArcIt(Invalid) { }
    223         /// Sets the iterator to the first outgoing arc.
    224 
    225         /// Sets the iterator to the first outgoing arc of the given node.
    226         ///
     233        /// This constructor sets the iterator to the first outgoing arc.
     234
     235        /// This constructor sets the iterator to the first outgoing arc of
     236        /// the node.
    227237        OutArcIt(const Digraph&, const Node&) { }
    228         /// Sets the iterator to the given arc.
    229 
    230         /// Sets the iterator to the given arc of the given digraph.
    231         ///
     238        /// Arc -> OutArcIt conversion
     239
     240        /// Sets the iterator to the value of the trivial iterator.
     241        /// This feature necessitates that each time we
     242        /// iterate the arc-set, the iteration order is the same.
    232243        OutArcIt(const Digraph&, const Arc&) { }
    233         /// Next outgoing arc
     244        ///Next outgoing arc
    234245
    235246        /// Assign the iterator to the next
    … …  
    238249      };
    239250
    240       /// Iterator class for the incoming arcs of a node.
     251      /// This iterator goes trough the incoming arcs of a node.
    241252
    242253      /// This iterator goes trough the \e incoming arcs of a certain node
    243254      /// of a digraph.
    244255      /// Its usage is quite simple, for example you can count the number
    245       /// of incoming arcs of a node \c n
    246       /// in a digraph \c g of type \c %Digraph as follows.
     256      /// of outgoing arcs of a node \c n
     257      /// in digraph \c g of type \c Digraph as follows.
    247258      ///\code
    248259      /// int count=0;
    249       /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     260      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    250261      ///\endcode
     262
    251263      class InArcIt : public Arc {
    252264      public:
    253265        /// Default constructor
    254266
    255         /// Default constructor.
    256         /// \warning It sets the iterator to an undefined value.
     267        /// @warning The default constructor sets the iterator
     268        /// to an undefined value.
    257269        InArcIt() { }
    258270        /// Copy constructor.
    … …  
    261273        ///
    262274        InArcIt(const InArcIt& e) : Arc(e) { }
    263         /// %Invalid constructor \& conversion.
    264 
    265         /// Initializes the iterator to be invalid.
    266         /// \sa Invalid for more details.
     275        /// Initialize the iterator to be invalid.
     276
     277        /// Initialize the iterator to be invalid.
     278        ///
    267279        InArcIt(Invalid) { }
    268         /// Sets the iterator to the first incoming arc.
    269 
    270         /// Sets the iterator to the first incoming arc of the given node.
    271         ///
     280        /// This constructor sets the iterator to first incoming arc.
     281
     282        /// This constructor set the iterator to the first incoming arc of
     283        /// the node.
    272284        InArcIt(const Digraph&, const Node&) { }
    273         /// Sets the iterator to the given arc.
    274 
    275         /// Sets the iterator to the given arc of the given digraph.
    276         ///
     285        /// Arc -> InArcIt conversion
     286
     287        /// Sets the iterator to the value of the trivial iterator \c e.
     288        /// This feature necessitates that each time we
     289        /// iterate the arc-set, the iteration order is the same.
    277290        InArcIt(const Digraph&, const Arc&) { }
    278291        /// Next incoming arc
    279292
    280         /// Assign the iterator to the next
    281         /// incoming arc of the corresponding node.
     293        /// Assign the iterator to the next inarc of the corresponding node.
     294        ///
    282295        InArcIt& operator++() { return *this; }
    283296      };
    284 
    285       /// Iterator class for the arcs.
    286 
    287       /// This iterator goes through each arc of the digraph.
     297      /// This iterator goes through each arc.
     298
     299      /// This iterator goes through each arc of a digraph.
    288300      /// Its usage is quite simple, for example you can count the number
    289       /// of arcs in a digraph \c g of type \c %Digraph as follows:
     301      /// of arcs in a digraph \c g of type \c Digraph as follows:
    290302      ///\code
    291303      /// int count=0;
    292       /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
     304      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
    293305      ///\endcode
    294306      class ArcIt : public Arc {
    … …  
    296308        /// Default constructor
    297309
    298         /// Default constructor.
    299         /// \warning It sets the iterator to an undefined value.
     310        /// @warning The default constructor sets the iterator
     311        /// to an undefined value.
    300312        ArcIt() { }
    301313        /// Copy constructor.
    … …  
    304316        ///
    305317        ArcIt(const ArcIt& e) : Arc(e) { }
    306         /// %Invalid constructor \& conversion.
    307 
    308         /// Initializes the iterator to be invalid.
    309         /// \sa Invalid for more details.
     318        /// Initialize the iterator to be invalid.
     319
     320        /// Initialize the iterator to be invalid.
     321        ///
    310322        ArcIt(Invalid) { }
    311         /// Sets the iterator to the first arc.
    312 
    313         /// Sets the iterator to the first arc of the given digraph.
    314         ///
    315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
    316         /// Sets the iterator to the given arc.
    317 
    318         /// Sets the iterator to the given arc of the given digraph.
    319         ///
     323        /// This constructor sets the iterator to the first arc.
     324
     325        /// This constructor sets the iterator to the first arc of \c g.
     326        ///@param g the digraph
     327        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     328        /// Arc -> ArcIt conversion
     329
     330        /// Sets the iterator to the value of the trivial iterator \c e.
     331        /// This feature necessitates that each time we
     332        /// iterate the arc-set, the iteration order is the same.
    320333        ArcIt(const Digraph&, const Arc&) { }
    321         /// Next arc
     334        ///Next arc
    322335
    323336        /// Assign the iterator to the next arc.
    324         ///
    325337        ArcIt& operator++() { return *this; }
    326338      };
    327 
    328       /// \brief The source node of the arc.
    329       ///
    330       /// Returns the source node of the given arc.
     339      ///Gives back the target node of an arc.
     340
     341      ///Gives back the target node of an arc.
     342      ///
     343      Node target(Arc) const { return INVALID; }
     344      ///Gives back the source node of an arc.
     345
     346      ///Gives back the source node of an arc.
     347      ///
    331348      Node source(Arc) const { return INVALID; }
    332349
    333       /// \brief The target node of the arc.
    334       ///
    335       /// Returns the target node of the given arc.
    336       Node target(Arc) const { return INVALID; }
    337 
    338       /// \brief The ID of the node.
    339       ///
    340       /// Returns the ID of the given node.
     350      /// \brief Returns the ID of the node.
    341351      int id(Node) const { return -1; }
    342352
    343       /// \brief The ID of the arc.
    344       ///
    345       /// Returns the ID of the given arc.
     353      /// \brief Returns the ID of the arc.
    346354      int id(Arc) const { return -1; }
    347355
    348       /// \brief The node with the given ID.
    349       ///
    350       /// Returns the node with the given ID.
    351       /// \pre The argument should be a valid node ID in the digraph.
     356      /// \brief Returns the node with the given ID.
     357      ///
     358      /// \pre The argument should be a valid node ID in the graph.
    352359      Node nodeFromId(int) const { return INVALID; }
    353360
    354       /// \brief The arc with the given ID.
    355       ///
    356       /// Returns the arc with the given ID.
    357       /// \pre The argument should be a valid arc ID in the digraph.
     361      /// \brief Returns the arc with the given ID.
     362      ///
     363      /// \pre The argument should be a valid arc ID in the graph.
    358364      Arc arcFromId(int) const { return INVALID; }
    359365
    360       /// \brief An upper bound on the node IDs.
    361       ///
    362       /// Returns an upper bound on the node IDs.
     366      /// \brief Returns an upper bound on the node IDs.
    363367      int maxNodeId() const { return -1; }
    364368
    365       /// \brief An upper bound on the arc IDs.
    366       ///
    367       /// Returns an upper bound on the arc IDs.
     369      /// \brief Returns an upper bound on the arc IDs.
    368370      int maxArcId() const { return -1; }
    369371
    … …  
    391393      int maxId(Arc) const { return -1; }
    392394
    393       /// \brief The opposite node on the arc.
    394       ///
    395       /// Returns the opposite node on the given arc.
    396       Node oppositeNode(Node, Arc) const { return INVALID; }
    397 
    398395      /// \brief The base node of the iterator.
    399396      ///
    400       /// Returns the base node of the given outgoing arc iterator
    401       /// (i.e. the source node of the corresponding arc).
    402       Node baseNode(OutArcIt) const { return INVALID; }
     397      /// Gives back the base node of the iterator.
     398      /// It is always the target of the pointed arc.
     399      Node baseNode(const InArcIt&) const { return INVALID; }
    403400
    404401      /// \brief The running node of the iterator.
    405402      ///
    406       /// Returns the running node of the given outgoing arc iterator
    407       /// (i.e. the target node of the corresponding arc).
    408       Node runningNode(OutArcIt) const { return INVALID; }
     403      /// Gives back the running node of the iterator.
     404      /// It is always the source of the pointed arc.
     405      Node runningNode(const InArcIt&) const { return INVALID; }
    409406
    410407      /// \brief The base node of the iterator.
    411408      ///
    412       /// Returns the base node of the given incomming arc iterator
    413       /// (i.e. the target node of the corresponding arc).
    414       Node baseNode(InArcIt) const { return INVALID; }
     409      /// Gives back the base node of the iterator.
     410      /// It is always the source of the pointed arc.
     411      Node baseNode(const OutArcIt&) const { return INVALID; }
    415412
    416413      /// \brief The running node of the iterator.
    417414      ///
    418       /// Returns the running node of the given incomming arc iterator
    419       /// (i.e. the source node of the corresponding arc).
    420       Node runningNode(InArcIt) const { return INVALID; }
    421 
    422       /// \brief Standard graph map type for the nodes.
    423       ///
    424       /// Standard graph map type for the nodes.
    425       /// It conforms to the ReferenceMap concept.
     415      /// Gives back the running node of the iterator.
     416      /// It is always the target of the pointed arc.
     417      Node runningNode(const OutArcIt&) const { return INVALID; }
     418
     419      /// \brief The opposite node on the given arc.
     420      ///
     421      /// Gives back the opposite node on the given arc.
     422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
     423
     424      /// \brief Reference map of the nodes to type \c T.
     425      ///
     426      /// Reference map of the nodes to type \c T.
    426427      template<class T>
    427428      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    428429      public:
    429430
    430         /// Constructor
    431         explicit NodeMap(const Digraph&) { }
    432         /// Constructor with given initial value
     431        ///\e
     432        NodeMap(const Digraph&) { }
     433        ///\e
    433434        NodeMap(const Digraph&, T) { }
    434435
    … …  
    445446      };
    446447
    447       /// \brief Standard graph map type for the arcs.
    448       ///
    449       /// Standard graph map type for the arcs.
    450       /// It conforms to the ReferenceMap concept.
     448      /// \brief Reference map of the arcs to type \c T.
     449      ///
     450      /// Reference map of the arcs to type \c T.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         /// Constructor
    456         explicit ArcMap(const Digraph&) { }
    457         /// Constructor with given initial value
     455        ///\e
     456        ArcMap(const Digraph&) { }
     457        ///\e
    458458        ArcMap(const Digraph&, T) { }
    459 
    460459      private:
    461460        ///Copy constructor

  • lemon/concepts/graph.h

    r734 r657  
    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>
    2927#include <lemon/core.h>
    3028
    … …  
    3432    /// \ingroup graph_concepts
    3533    ///
    36     /// \brief Class describing the concept of undirected graphs.
     34    /// \brief Class describing the concept of Undirected Graphs.
    3735    ///
    38     /// This class describes the common interface of all undirected
    39     /// graphs.
     36    /// This class describes the common interface of all Undirected
     37    /// Graphs.
    4038    ///
    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
     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
    4442    /// run properly, of course.
    45     /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.   
    4743    ///
    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.
     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.
    6153    ///
    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.
     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.
    6861    ///
    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
     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.
    7368    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 
    8169    public:
    82       /// Default constructor.
    83       Graph() {}
    84 
    85       /// \brief Undirected graphs should be tagged with \c UndirectedTag.
    86       ///
    87       /// Undirected graphs should be tagged with \c UndirectedTag.
    88       ///
    89       /// This tag helps the \c enable_if technics to make compile time
     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
    9075      /// specializations for undirected graphs.
    9176      typedef True UndirectedTag;
    9277
    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.
     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.
    9885      class Node {
    9986      public:
    10087        /// Default constructor
    10188
    102         /// Default constructor.
    103         /// \warning It sets the object to an undefined value.
     89        /// @warning The default constructor sets the iterator
     90        /// to an undefined value.
    10491        Node() { }
    10592        /// Copy constructor.
    … …  
    10996        Node(const Node&) { }
    11097
    111         /// %Invalid constructor \& conversion.
    112 
    113         /// Initializes the object to be invalid.
     98        /// Invalid constructor \& conversion.
     99
     100        /// This constructor initializes the iterator to be invalid.
    114101        /// \sa Invalid for more details.
    115102        Node(Invalid) { }
    116103        /// Equality operator
    117104
    118         /// Equality operator.
    119         ///
    120105        /// Two iterators are equal if and only if they point to the
    121         /// same object or both are \c INVALID.
     106        /// same object or both are invalid.
    122107        bool operator==(Node) const { return true; }
    123108
    124109        /// Inequality operator
    125110
    126         /// Inequality operator.
     111        /// \sa operator==(Node n)
     112        ///
    127113        bool operator!=(Node) const { return true; }
    128114
    129115        /// Artificial ordering operator.
    130116
    131         /// Artificial ordering operator.
    132         ///
    133         /// \note This operator only has to define some strict ordering of
     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
    134121        /// the items; this order has nothing to do with the iteration
    135122        /// ordering of the items.
    … …  
    138125      };
    139126
    140       /// Iterator class for the nodes.
    141 
    142       /// This iterator goes through each node of the graph.
     127      /// This iterator goes through each node.
     128
     129      /// This iterator goes through each node.
    143130      /// 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:
     131      /// of nodes in graph \c g of type \c Graph like this:
    145132      ///\code
    146133      /// int count=0;
    … …  
    151138        /// Default constructor
    152139
    153         /// Default constructor.
    154         /// \warning It sets the iterator to an undefined value.
     140        /// @warning The default constructor sets the iterator
     141        /// to an undefined value.
    155142        NodeIt() { }
    156143        /// Copy constructor.
    … …  
    159146        ///
    160147        NodeIt(const NodeIt& n) : Node(n) { }
    161         /// %Invalid constructor \& conversion.
    162 
    163         /// Initializes the iterator to be invalid.
     148        /// Invalid constructor \& conversion.
     149
     150        /// Initialize the iterator to be invalid.
    164151        /// \sa Invalid for more details.
    165152        NodeIt(Invalid) { }
    166153        /// Sets the iterator to the first node.
    167154
    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         ///
     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.
    175164        NodeIt(const Graph&, const Node&) { }
    176165        /// Next node.
    … …  
    182171
    183172
    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.
     173      /// The base type of the edge iterators.
     174
     175      /// The base type of the edge iterators.
     176      ///
    189177      class Edge {
    190178      public:
    191179        /// Default constructor
    192180
    193         /// Default constructor.
    194         /// \warning It sets the object to an undefined value.
     181        /// @warning The default constructor sets the iterator
     182        /// to an undefined value.
    195183        Edge() { }
    196184        /// Copy constructor.
    … …  
    199187        ///
    200188        Edge(const Edge&) { }
    201         /// %Invalid constructor \& conversion.
    202 
    203         /// Initializes the object to be invalid.
    204         /// \sa Invalid for more details.
     189        /// Initialize the iterator to be invalid.
     190
     191        /// Initialize the iterator to be invalid.
     192        ///
    205193        Edge(Invalid) { }
    206194        /// Equality operator
    207195
    208         /// Equality operator.
    209         ///
    210196        /// Two iterators are equal if and only if they point to the
    211         /// same object or both are \c INVALID.
     197        /// same object or both are invalid.
    212198        bool operator==(Edge) const { return true; }
    213199        /// Inequality operator
    214200
    215         /// Inequality operator.
     201        /// \sa operator==(Edge n)
     202        ///
    216203        bool operator!=(Edge) const { return true; }
    217204
    218205        /// Artificial ordering operator.
    219206
    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.
     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.
    225213        bool operator<(Edge) const { return false; }
    226214      };
    227215
    228       /// Iterator class for the edges.
    229 
    230       /// This iterator goes through each edge of the graph.
     216      /// This iterator goes through each edge.
     217
     218      /// This iterator goes through each edge of a graph.
    231219      /// 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:
     220      /// of edges in a graph \c g of type \c Graph as follows:
    233221      ///\code
    234222      /// int count=0;
    … …  
    239227        /// Default constructor
    240228
    241         /// Default constructor.
    242         /// \warning It sets the iterator to an undefined value.
     229        /// @warning The default constructor sets the iterator
     230        /// to an undefined value.
    243231        EdgeIt() { }
    244232        /// Copy constructor.
    … …  
    247235        ///
    248236        EdgeIt(const EdgeIt& e) : Edge(e) { }
    249         /// %Invalid constructor \& conversion.
    250 
    251         /// Initializes the iterator to be invalid.
    252         /// \sa Invalid for more details.
     237        /// Initialize the iterator to be invalid.
     238
     239        /// Initialize the iterator to be invalid.
     240        ///
    253241        EdgeIt(Invalid) { }
    254         /// Sets the iterator to the first edge.
    255 
    256         /// Sets the iterator to the first edge of the given graph.
    257         ///
    258         explicit EdgeIt(const Graph&) { }
    259         /// Sets the iterator to the given edge.
    260 
    261         /// Sets the iterator to the given edge of the given graph.
    262         ///
     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.
    263252        EdgeIt(const Graph&, const Edge&) { }
    264253        /// Next edge
    265254
    266255        /// Assign the iterator to the next edge.
    267         ///
    268256        EdgeIt& operator++() { return *this; }
    269257      };
    270258
    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.
     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      ///
    275266      /// 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.
     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.
    278269      ///
    279270      ///\code
    … …  
    281272      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    282273      ///\endcode
    283       ///
    284       /// \warning Loop edges will be iterated twice.
    285274      class IncEdgeIt : public Edge {
    286275      public:
    287276        /// Default constructor
    288277
    289         /// Default constructor.
    290         /// \warning It sets the iterator to an undefined value.
     278        /// @warning The default constructor sets the iterator
     279        /// to an undefined value.
    291280        IncEdgeIt() { }
    292281        /// Copy constructor.
    … …  
    295284        ///
    296285        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    297         /// %Invalid constructor \& conversion.
    298 
    299         /// Initializes the iterator to be invalid.
    300         /// \sa Invalid for more details.
     286        /// Initialize the iterator to be invalid.
     287
     288        /// Initialize the iterator to be invalid.
     289        ///
    301290        IncEdgeIt(Invalid) { }
    302         /// Sets the iterator to the first incident edge.
    303 
    304         /// Sets the iterator to the first incident edge of the given node.
    305         ///
     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.
    306295        IncEdgeIt(const Graph&, const Node&) { }
    307         /// Sets the iterator to the given edge.
    308 
    309         /// Sets the iterator to the given edge of the given graph.
    310         ///
     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.
    311301        IncEdgeIt(const Graph&, const Edge&) { }
    312         /// Next incident edge
    313 
    314         /// Assign the iterator to the next incident edge
     302        /// Next incident arc
     303
     304        /// Assign the iterator to the next incident arc
    315305        /// of the corresponding node.
    316306        IncEdgeIt& operator++() { return *this; }
    317307      };
    318308
    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.
     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.
    324314      class Arc {
    325315      public:
    326316        /// Default constructor
    327317
    328         /// Default constructor.
    329         /// \warning It sets the object to an undefined value.
     318        /// @warning The default constructor sets the iterator
     319        /// to an undefined value.
    330320        Arc() { }
    331321        /// Copy constructor.
    … …  
    334324        ///
    335325        Arc(const Arc&) { }
    336         /// %Invalid constructor \& conversion.
    337 
    338         /// Initializes the object to be invalid.
    339         /// \sa Invalid for more details.
     326        /// Initialize the iterator to be invalid.
     327
     328        /// Initialize the iterator to be invalid.
     329        ///
    340330        Arc(Invalid) { }
    341331        /// Equality operator
    342332
    343         /// Equality operator.
    344         ///
    345333        /// Two iterators are equal if and only if they point to the
    346         /// same object or both are \c INVALID.
     334        /// same object or both are invalid.
    347335        bool operator==(Arc) const { return true; }
    348336        /// Inequality operator
    349337
    350         /// Inequality operator.
     338        /// \sa operator==(Arc n)
     339        ///
    351340        bool operator!=(Arc) const { return true; }
    352341
    353342        /// Artificial ordering operator.
    354343
    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.
     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.
    360350        bool operator<(Arc) const { return false; }
    361351
    362         /// Converison to \c Edge
    363        
    364         /// Converison to \c Edge.
    365         ///
     352        /// Converison to Edge
    366353        operator Edge() const { return Edge(); }
    367354      };
    368 
    369       /// Iterator class for the arcs.
    370 
    371       /// This iterator goes through each directed arc of the graph.
     355      /// This iterator goes through each directed arc.
     356
     357      /// This iterator goes through each arc of a graph.
    372358      /// 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:
     359      /// of arcs in a graph \c g of type \c Graph as follows:
    374360      ///\code
    375361      /// int count=0;
    376       /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
     362      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
    377363      ///\endcode
    378364      class ArcIt : public Arc {
    … …  
    380366        /// Default constructor
    381367
    382         /// Default constructor.
    383         /// \warning It sets the iterator to an undefined value.
     368        /// @warning The default constructor sets the iterator
     369        /// to an undefined value.
    384370        ArcIt() { }
    385371        /// Copy constructor.
    … …  
    388374        ///
    389375        ArcIt(const ArcIt& e) : Arc(e) { }
    390         /// %Invalid constructor \& conversion.
    391 
    392         /// Initializes the iterator to be invalid.
    393         /// \sa Invalid for more details.
     376        /// Initialize the iterator to be invalid.
     377
     378        /// Initialize the iterator to be invalid.
     379        ///
    394380        ArcIt(Invalid) { }
    395         /// Sets the iterator to the first arc.
    396 
    397         /// Sets the iterator to the first arc of the given graph.
    398         ///
    399         explicit ArcIt(const Graph &g) { 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         ///
     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.
    404391        ArcIt(const Graph&, const Arc&) { }
    405         /// Next arc
     392        ///Next arc
    406393
    407394        /// Assign the iterator to the next arc.
    408         ///
    409395        ArcIt& operator++() { return *this; }
    410396      };
    411397
    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.
     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.
    416402      /// Its usage is quite simple, for example you can count the number
    417403      /// of outgoing arcs of a node \c n
    418       /// in a graph \c g of type \c %Graph as follows.
     404      /// in graph \c g of type \c Graph as follows.
    419405      ///\code
    420406      /// int count=0;
    421       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     407      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    422408      ///\endcode
     409
    423410      class OutArcIt : public Arc {
    424411      public:
    425412        /// Default constructor
    426413
    427         /// Default constructor.
    428         /// \warning It sets the iterator to an undefined value.
     414        /// @warning The default constructor sets the iterator
     415        /// to an undefined value.
    429416        OutArcIt() { }
    430417        /// Copy constructor.
    … …  
    433420        ///
    434421        OutArcIt(const OutArcIt& e) : Arc(e) { }
    435         /// %Invalid constructor \& conversion.
    436 
    437         /// Initializes the iterator to be invalid.
    438         /// \sa Invalid for more details.
     422        /// Initialize the iterator to be invalid.
     423
     424        /// Initialize the iterator to be invalid.
     425        ///
    439426        OutArcIt(Invalid) { }
    440         /// Sets the iterator to the first outgoing arc.
    441 
    442         /// Sets the iterator to the first outgoing arc of the given node.
    443         ///
     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
    444433        OutArcIt(const Graph& n, const Node& g) {
    445434          ignore_unused_variable_warning(n);
    446435          ignore_unused_variable_warning(g);
    447436        }
    448         /// Sets the iterator to the given arc.
    449 
    450         /// Sets the iterator to the given arc of the given graph.
    451         ///
     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.
    452442        OutArcIt(const Graph&, const Arc&) { }
    453         /// Next outgoing arc
     443        ///Next outgoing arc
    454444
    455445        /// Assign the iterator to the next
    … …  
    458448      };
    459449
    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.
     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.
    464454      /// 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.
     455      /// of outgoing arcs of a node \c n
     456      /// in graph \c g of type \c Graph as follows.
    467457      ///\code
    468458      /// int count=0;
    469       /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     459      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    470460      ///\endcode
     461
    471462      class InArcIt : public Arc {
    472463      public:
    473464        /// Default constructor
    474465
    475         /// Default constructor.
    476         /// \warning It sets the iterator to an undefined value.
     466        /// @warning The default constructor sets the iterator
     467        /// to an undefined value.
    477468        InArcIt() { }
    478469        /// Copy constructor.
    … …  
    481472        ///
    482473        InArcIt(const InArcIt& e) : Arc(e) { }
    483         /// %Invalid constructor \& conversion.
    484 
    485         /// Initializes the iterator to be invalid.
    486         /// \sa Invalid for more details.
     474        /// Initialize the iterator to be invalid.
     475
     476        /// Initialize the iterator to be invalid.
     477        ///
    487478        InArcIt(Invalid) { }
    488         /// Sets the iterator to the first incoming arc.
    489 
    490         /// Sets the iterator to the first incoming arc of the given node.
    491         ///
     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
    492485        InArcIt(const Graph& g, const Node& n) {
    493486          ignore_unused_variable_warning(n);
    494487          ignore_unused_variable_warning(g);
    495488        }
    496         /// Sets the iterator to the given arc.
    497 
    498         /// Sets the iterator to the given arc of the given graph.
    499         ///
     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.
    500494        InArcIt(const Graph&, const Arc&) { }
    501495        /// Next incoming arc
    502496
    503         /// Assign the iterator to the next
    504         /// incoming arc of the corresponding node.
     497        /// Assign the iterator to the next inarc of the corresponding node.
     498        ///
    505499        InArcIt& operator++() { return *this; }
    506500      };
    507501
    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.
     502      /// \brief Reference map of the nodes to type \c T.
     503      ///
     504      /// Reference map of the nodes to type \c T.
    512505      template<class T>
    513506      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    … …  
    515508      public:
    516509
    517         /// Constructor
    518         explicit NodeMap(const Graph&) { }
    519         /// Constructor with given initial value
     510        ///\e
     511        NodeMap(const Graph&) { }
     512        ///\e
    520513        NodeMap(const Graph&, T) { }
    521514
    … …  
    532525      };
    533526
    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.
     527      /// \brief Reference map of the arcs to type \c T.
     528      ///
     529      /// Reference map of the arcs to type \c T.
    538530      template<class T>
    539531      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    … …  
    541533      public:
    542534
    543         /// Constructor
    544         explicit ArcMap(const Graph&) { }
    545         /// Constructor with given initial value
     535        ///\e
     536        ArcMap(const Graph&) { }
     537        ///\e
    546538        ArcMap(const Graph&, T) { }
    547 
    548539      private:
    549540        ///Copy constructor
    … …  
    558549      };
    559550
    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.
     551      /// Reference map of the edges to type \c T.
     552
     553      /// Reference map of the edges to type \c T.
    564554      template<class T>
    565555      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    … …  
    567557      public:
    568558
    569         /// Constructor
    570         explicit EdgeMap(const Graph&) { }
    571         /// Constructor with given initial value
     559        ///\e
     560        EdgeMap(const Graph&) { }
     561        ///\e
    572562        EdgeMap(const Graph&, T) { }
    573 
    574563      private:
    575564        ///Copy constructor
    … …  
    584573      };
    585574
    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.
     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.
    595619      /// \sa v()
    596620      /// \sa direction()
    597621      Node u(Edge) const { return INVALID; }
    598622
    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.
     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.
    608633      /// \sa u()
    609634      /// \sa direction()
    610635      Node v(Edge) const { return INVALID; }
    611636
    612       /// \brief The source node of the arc.
    613       ///
    614       /// Returns the source node of the given arc.
     637      /// \brief Source node of the directed arc.
    615638      Node source(Arc) const { return INVALID; }
    616639
    617       /// \brief The target node of the arc.
    618       ///
    619       /// Returns the target node of the given arc.
     640      /// \brief Target node of the directed arc.
    620641      Node target(Arc) const { return INVALID; }
    621642
    622       /// \brief The ID of the node.
    623       ///
    624       /// Returns the ID of the given node.
     643      /// \brief Returns the id of the node.
    625644      int id(Node) const { return -1; }
    626645
    627       /// \brief The ID of the edge.
    628       ///
    629       /// Returns the ID of the given edge.
     646      /// \brief Returns the id of the edge.
    630647      int id(Edge) const { return -1; }
    631648
    632       /// \brief The ID of the arc.
    633       ///
    634       /// Returns the ID of the given arc.
     649      /// \brief Returns the id of the arc.
    635650      int id(Arc) const { return -1; }
    636651
    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.
     652      /// \brief Returns the node with the given id.
     653      ///
     654      /// \pre The argument should be a valid node id in the graph.
    641655      Node nodeFromId(int) const { return INVALID; }
    642656
    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.
     657      /// \brief Returns the edge with the given id.
     658      ///
     659      /// \pre The argument should be a valid edge id in the graph.
    647660      Edge edgeFromId(int) const { return INVALID; }
    648661
    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.
     662      /// \brief Returns the arc with the given id.
     663      ///
     664      /// \pre The argument should be a valid arc id in the graph.
    653665      Arc arcFromId(int) const { return INVALID; }
    654666
    655       /// \brief An upper bound on the node IDs.
    656       ///
    657       /// Returns an upper bound on the node IDs.
     667      /// \brief Returns an upper bound on the node IDs.
    658668      int maxNodeId() const { return -1; }
    659669
    660       /// \brief An upper bound on the edge IDs.
    661       ///
    662       /// Returns an upper bound on the edge IDs.
     670      /// \brief Returns an upper bound on the edge IDs.
    663671      int maxEdgeId() const { return -1; }
    664672
    665       /// \brief An upper bound on the arc IDs.
    666       ///
    667       /// Returns an upper bound on the arc IDs.
     673      /// \brief Returns an upper bound on the arc IDs.
    668674      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; }
    703675
    704676      void first(Node&) const {}
    … …  
    734706      int maxId(Arc) const { return -1; }
    735707
    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; }
     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      }
    769749
    770750      template <typename _Graph>

  • lemon/concepts/graph_components.h

    r734 r666  
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only has to define some strict ordering of
     95      /// \note This operator only have to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.

  • lemon/full_graph.h

    r735 r617  
    2525///\ingroup graphs
    2626///\file
    27 ///\brief FullDigraph and FullGraph classes.
     27///\brief FullGraph and FullDigraph classes.
    2828
    2929namespace lemon {
    … …  
    149149  /// \ingroup graphs
    150150  ///
    151   /// \brief A directed full graph class.
    152   ///
    153   /// FullDigraph is a simple and fast implmenetation of directed full
    154   /// (complete) graphs. It contains an arc from each node to each node
    155   /// (including a loop for each node), therefore the number of arcs
    156   /// is the square of the number of nodes.
    157   /// This class is completely static and it needs constant memory space.
    158   /// Thus you can neither add nor delete nodes or arcs, however
    159   /// the structure can be resized using resize().
    160   ///
    161   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
    162   /// Most of its member functions and nested classes are documented
    163   /// only in the concept class.
    164   ///
    165   /// \note FullDigraph and FullGraph classes are very similar,
     151  /// \brief A full digraph class.
     152  ///
     153  /// This is a simple and fast directed full graph implementation.
     154  /// From each node go arcs to each node (including the source node),
     155  /// therefore the number of the arcs in the digraph is the square of
     156  /// the node number. This digraph type is completely static, so you
     157  /// can neither add nor delete either arcs or nodes, and it needs
     158  /// constant space in memory.
     159  ///
     160  /// This class fully conforms to the \ref concepts::Digraph
     161  /// "Digraph concept".
     162  ///
     163  /// The \c FullDigraph and \c FullGraph classes are very similar,
    166164  /// but there are two differences. While this class conforms only
    167   /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
    168   /// conforms to the \ref concepts::Graph "Graph" concept,
    169   /// moreover FullGraph does not contain a loop for each
    170   /// node as this class does.
     165  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
     166  /// class conforms to the \ref concepts::Graph "Graph" concept,
     167  /// moreover \c FullGraph does not contain a loop arc for each
     168  /// node as \c FullDigraph does.
    171169  ///
    172170  /// \sa FullGraph
    … …  
    176174  public:
    177175
    178     /// \brief Default constructor.
    179     ///
    180     /// Default constructor. The number of nodes and arcs will be zero.
     176    /// \brief Constructor
    181177    FullDigraph() { construct(0); }
    182178
    … …  
    189185    /// \brief Resizes the digraph
    190186    ///
    191     /// This function resizes the digraph. It fully destroys and
    192     /// rebuilds the structure, therefore the maps of the digraph will be
     187    /// Resizes the digraph. The function will fully destroy and
     188    /// rebuild the digraph. This cause that the maps of the digraph will
    193189    /// reallocated automatically and the previous values will be lost.
    194190    void resize(int n) {
    … …  
    202198    /// \brief Returns the node with the given index.
    203199    ///
    204     /// Returns the node with the given index. Since this structure is
    205     /// completely static, the nodes can be indexed with integers from
    206     /// the range <tt>[0..nodeNum()-1]</tt>.
     200    /// Returns the node with the given index. Since it is a static
     201    /// digraph its nodes can be indexed with integers from the range
     202    /// <tt>[0..nodeNum()-1]</tt>.
    207203    /// \sa index()
    208204    Node operator()(int ix) const { return Parent::operator()(ix); }
    … …  
    210206    /// \brief Returns the index of the given node.
    211207    ///
    212     /// Returns the index of the given node. Since this structure is
    213     /// completely static, the nodes can be indexed with integers from
    214     /// the range <tt>[0..nodeNum()-1]</tt>.
    215     /// \sa operator()()
    216     int index(Node node) const { return Parent::index(node); }
     208    /// Returns the index of the given node. Since it is a static
     209    /// digraph its nodes can be indexed with integers from the range
     210    /// <tt>[0..nodeNum()-1]</tt>.
     211    /// \sa operator()
     212    int index(const Node& node) const { return Parent::index(node); }
    217213
    218214    /// \brief Returns the arc connecting the given nodes.
    219215    ///
    220216    /// Returns the arc connecting the given nodes.
    221     Arc arc(Node u, Node v) const {
     217    Arc arc(const Node& u, const Node& v) const {
    222218      return Parent::arc(u, v);
    223219    }
    … …  
    525521  /// \brief An undirected full graph class.
    526522  ///
    527   /// FullGraph is a simple and fast implmenetation of undirected full
    528   /// (complete) graphs. It contains an edge between every distinct pair
    529   /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
    530   /// This class is completely static and it needs constant memory space.
    531   /// Thus you can neither add nor delete nodes or edges, however
    532   /// the structure can be resized using resize().
    533   ///
    534   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
    535   /// Most of its member functions and nested classes are documented
    536   /// only in the concept class.
    537   ///
    538   /// \note FullDigraph and FullGraph classes are very similar,
    539   /// but there are two differences. While FullDigraph
     523  /// This is a simple and fast undirected full graph
     524  /// implementation. From each node go edge to each other node,
     525  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
     526  /// This graph type is completely static, so you can neither
     527  /// add nor delete either edges or nodes, and it needs constant
     528  /// space in memory.
     529  ///
     530  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
     531  ///
     532  /// The \c FullGraph and \c FullDigraph classes are very similar,
     533  /// but there are two differences. While the \c FullDigraph class
    540534  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    541535  /// this class conforms to the \ref concepts::Graph "Graph" concept,
    542   /// moreover this class does not contain a loop for each
    543   /// node as FullDigraph does.
     536  /// moreover \c FullGraph does not contain a loop arc for each
     537  /// node as \c FullDigraph does.
    544538  ///
    545539  /// \sa FullDigraph
    … …  
    549543  public:
    550544
    551     /// \brief Default constructor.
    552     ///
    553     /// Default constructor. The number of nodes and edges will be zero.
     545    /// \brief Constructor
    554546    FullGraph() { construct(0); }
    555547
    … …  
    562554    /// \brief Resizes the graph
    563555    ///
    564     /// This function resizes the graph. It fully destroys and
    565     /// rebuilds the structure, therefore the maps of the graph will be
     556    /// Resizes the graph. The function will fully destroy and
     557    /// rebuild the graph. This cause that the maps of the graph will
    566558    /// reallocated automatically and the previous values will be lost.
    567559    void resize(int n) {
    … …  
    577569    /// \brief Returns the node with the given index.
    578570    ///
    579     /// Returns the node with the given index. Since this structure is
    580     /// completely static, the nodes can be indexed with integers from
    581     /// the range <tt>[0..nodeNum()-1]</tt>.
     571    /// Returns the node with the given index. Since it is a static
     572    /// graph its nodes can be indexed with integers from the range
     573    /// <tt>[0..nodeNum()-1]</tt>.
    582574    /// \sa index()
    583575    Node operator()(int ix) const { return Parent::operator()(ix); }
    … …  
    585577    /// \brief Returns the index of the given node.
    586578    ///
    587     /// Returns the index of the given node. Since this structure is
    588     /// completely static, the nodes can be indexed with integers from
    589     /// the range <tt>[0..nodeNum()-1]</tt>.
    590     /// \sa operator()()
    591     int index(Node node) const { return Parent::index(node); }
     579    /// Returns the index of the given node. Since it is a static
     580    /// graph its nodes can be indexed with integers from the range
     581    /// <tt>[0..nodeNum()-1]</tt>.
     582    /// \sa operator()
     583    int index(const Node& node) const { return Parent::index(node); }
    592584
    593585    /// \brief Returns the arc connecting the given nodes.
    594586    ///
    595587    /// Returns the arc connecting the given nodes.
    596     Arc arc(Node s, Node t) const {
     588    Arc arc(const Node& s, const Node& t) const {
    597589      return Parent::arc(s, t);
    598590    }
    599591
    600     /// \brief Returns the edge connecting the given nodes.
    601     ///
    602     /// Returns the edge connecting the given nodes.
    603     Edge edge(Node u, Node v) const {
     592    /// \brief Returns the edge connects the given nodes.
     593    ///
     594    /// Returns the edge connects the given nodes.
     595    Edge edge(const Node& u, const Node& v) const {
    604596      return Parent::edge(u, v);
    605597    }

  • lemon/grid_graph.h

    r735 r617  
    471471  /// \brief Grid graph class
    472472  ///
    473   /// GridGraph implements a special graph type. The nodes of the
    474   /// graph can be indexed by two integer values \c (i,j) where \c i is
    475   /// in the range <tt>[0..width()-1]</tt> and j is in the range
    476   /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
    477   /// the indices differ exactly on one position and the difference is
    478   /// also exactly one. The nodes of the graph can be obtained by position
    479   /// using the \c operator()() function and the indices of the nodes can
    480   /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
     473  /// This class implements a special graph type. The nodes of the
     474  /// graph can be indexed by two integer \c (i,j) value where \c i is
     475  /// in the \c [0..width()-1] range and j is in the \c
     476  /// [0..height()-1] range. Two nodes are connected in the graph if
     477  /// the indexes differ exactly on one position and exactly one is
     478  /// the difference. The nodes of the graph can be indexed by position
     479  /// with the \c operator()() function. The positions of the nodes can be
     480  /// get with \c pos(), \c col() and \c row() members. The outgoing
    481481  /// arcs can be retrieved with the \c right(), \c up(), \c left()
    482482  /// and \c down() functions, where the bottom-left corner is the
    483483  /// origin.
    484   ///
    485   /// This class is completely static and it needs constant memory space.
    486   /// Thus you can neither add nor delete nodes or edges, however
    487   /// the structure can be resized using resize().
    488484  ///
    489485  /// \image html grid_graph.png
    … …  
    501497  ///\endcode
    502498  ///
    503   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
    504   /// Most of its member functions and nested classes are documented
    505   /// only in the concept class.
     499  /// This graph type fully conforms to the \ref concepts::Graph
     500  /// "Graph concept".
    506501  class GridGraph : public ExtendedGridGraphBase {
    507502    typedef ExtendedGridGraphBase Parent;
    … …  
    509504  public:
    510505
    511     /// \brief Map to get the indices of the nodes as \ref dim2::Point
    512     /// "dim2::Point<int>".
    513     ///
    514     /// Map to get the indices of the nodes as \ref dim2::Point
    515     /// "dim2::Point<int>".
     506    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
     507    ///
     508    /// Map to get the indices of the nodes as dim2::Point<int>.
    516509    class IndexMap {
    517510    public:
    … …  
    522515
    523516      /// \brief Constructor
     517      ///
     518      /// Constructor
    524519      IndexMap(const GridGraph& graph) : _graph(graph) {}
    525520
    526521      /// \brief The subscript operator
     522      ///
     523      /// The subscript operator.
    527524      Value operator[](Key key) const {
    528525        return _graph.pos(key);
    … …  
    544541
    545542      /// \brief Constructor
     543      ///
     544      /// Constructor
    546545      ColMap(const GridGraph& graph) : _graph(graph) {}
    547546
    548547      /// \brief The subscript operator
     548      ///
     549      /// The subscript operator.
    549550      Value operator[](Key key) const {
    550551        return _graph.col(key);
    … …  
    566567
    567568      /// \brief Constructor
     569      ///
     570      /// Constructor
    568571      RowMap(const GridGraph& graph) : _graph(graph) {}
    569572
    570573      /// \brief The subscript operator
     574      ///
     575      /// The subscript operator.
    571576      Value operator[](Key key) const {
    572577        return _graph.row(key);
    … …  
    579584    /// \brief Constructor
    580585    ///
    581     /// Construct a grid graph with the given size.
     586    /// Construct a grid graph with given size.
    582587    GridGraph(int width, int height) { construct(width, height); }
    583588
    584     /// \brief Resizes the graph
    585     ///
    586     /// This function resizes the graph. It fully destroys and
    587     /// rebuilds the structure, therefore the maps of the graph will be
    588     /// reallocated automatically and the previous values will be lost.
     589    /// \brief Resize the graph
     590    ///
     591    /// Resize the graph. The function will fully destroy and rebuild
     592    /// the graph.  This cause that the maps of the graph will
     593    /// reallocated automatically and the previous values will be
     594    /// lost.
    589595    void resize(int width, int height) {
    590596      Parent::notifier(Arc()).clear();
    … …  
    604610    }
    605611
    606     /// \brief The column index of the node.
     612    /// \brief Gives back the column index of the node.
    607613    ///
    608614    /// Gives back the column index of the node.
    … …  
    611617    }
    612618
    613     /// \brief The row index of the node.
     619    /// \brief Gives back the row index of the node.
    614620    ///
    615621    /// Gives back the row index of the node.
    … …  
    618624    }
    619625
    620     /// \brief The position of the node.
     626    /// \brief Gives back the position of the node.
    621627    ///
    622628    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
    … …  
    625631    }
    626632
    627     /// \brief The number of the columns.
     633    /// \brief Gives back the number of the columns.
    628634    ///
    629635    /// Gives back the number of the columns.
    … …  
    632638    }
    633639
    634     /// \brief The number of the rows.
     640    /// \brief Gives back the number of the rows.
    635641    ///
    636642    /// Gives back the number of the rows.
    … …  
    639645    }
    640646
    641     /// \brief The arc goes right from the node.
     647    /// \brief Gives back the arc goes right from the node.
    642648    ///
    643649    /// Gives back the arc goes right from the node. If there is not
    … …  
    647653    }
    648654
    649     /// \brief The arc goes left from the node.
     655    /// \brief Gives back the arc goes left from the node.
    650656    ///
    651657    /// Gives back the arc goes left from the node. If there is not
    … …  
    655661    }
    656662
    657     /// \brief The arc goes up from the node.
     663    /// \brief Gives back the arc goes up from the node.
    658664    ///
    659665    /// Gives back the arc goes up from the node. If there is not
    … …  
    663669    }
    664670
    665     /// \brief The arc goes down from the node.
     671    /// \brief Gives back the arc goes down from the node.
    666672    ///
    667673    /// Gives back the arc goes down from the node. If there is not

  • lemon/hypercube_graph.h

    r737 r617  
    283283  /// \brief Hypercube graph class
    284284  ///
    285   /// HypercubeGraph implements a special graph type. The nodes of the
    286   /// graph are indexed with integers having at most \c dim binary digits.
     285  /// This class implements a special graph type. The nodes of the graph
     286  /// are indiced with integers with at most \c dim binary digits.
    287287  /// Two nodes are connected in the graph if and only if their indices
    288288  /// differ only on one position in the binary form.
    289   /// This class is completely static and it needs constant memory space.
    290   /// Thus you can neither add nor delete nodes or edges, however
    291   /// the structure can be resized using resize().
    292   ///
    293   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
    294   /// Most of its member functions and nested classes are documented
    295   /// only in the concept class.
    296289  ///
    297290  /// \note The type of the indices is chosen to \c int for efficiency
    298291  /// reasons. Thus the maximum dimension of this implementation is 26
    299292  /// (assuming that the size of \c int is 32 bit).
     293  ///
     294  /// This graph type fully conforms to the \ref concepts::Graph
     295  /// "Graph concept".
    300296  class HypercubeGraph : public ExtendedHypercubeGraphBase {
    301297    typedef ExtendedHypercubeGraphBase Parent;
    … …  
    307303    /// Constructs a hypercube graph with \c dim dimensions.
    308304    HypercubeGraph(int dim) { construct(dim); }
    309 
    310     /// \brief Resizes the graph
    311     ///
    312     /// This function resizes the graph. It fully destroys and
    313     /// rebuilds the structure, therefore the maps of the graph will be
    314     /// reallocated automatically and the previous values will be lost.
    315     void resize(int dim) {
    316       Parent::notifier(Arc()).clear();
    317       Parent::notifier(Edge()).clear();
    318       Parent::notifier(Node()).clear();
    319       construct(dim);
    320       Parent::notifier(Node()).build();
    321       Parent::notifier(Edge()).build();
    322       Parent::notifier(Arc()).build();
    323     }
    324305
    325306    /// \brief The number of dimensions.
    … …  
    340321    ///
    341322    /// Gives back the dimension id of the given edge.
    342     /// It is in the range <tt>[0..dim-1]</tt>.
     323    /// It is in the [0..dim-1] range.
    343324    int dimension(Edge edge) const {
    344325      return Parent::dimension(edge);
    … …  
    348329    ///
    349330    /// Gives back the dimension id of the given arc.
    350     /// It is in the range <tt>[0..dim-1]</tt>.
     331    /// It is in the [0..dim-1] range.
    351332    int dimension(Arc arc) const {
    352333      return Parent::dimension(arc);

  • lemon/list_graph.h

    r741 r739  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListDigraph and ListGraph classes.
     24///\brief ListDigraph, ListGraph classes.
    2525
    2626#include <lemon/core.h>
    … …  
    3232
    3333namespace lemon {
    34 
    35   class ListDigraph;
    3634
    3735  class ListDigraphBase {
    … …  
    6563    class Node {
    6664      friend class ListDigraphBase;
    67       friend class ListDigraph;
    6865    protected:
    6966
    … …  
    8178    class Arc {
    8279      friend class ListDigraphBase;
    83       friend class ListDigraph;
    8480    protected:
    8581
    … …  
    316312  ///A general directed graph structure.
    317313
    318   ///\ref ListDigraph is a versatile and fast directed graph
    319   ///implementation based on linked lists that are stored in
     314  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
     315  ///implementation based on static linked lists that are stored in
    320316  ///\c std::vector structures.
    321317  ///
    322   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
    323   ///and it also provides several useful additional functionalities.
    324   ///Most of its member functions and nested classes are documented
     318  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
     319  ///also provides several useful additional functionalities.
     320  ///Most of the member functions and nested classes are documented
    325321  ///only in the concept class.
    326322  ///
    327323  ///\sa concepts::Digraph
    328   ///\sa ListGraph
     324
    329325  class ListDigraph : public ExtendedListDigraphBase {
    330326    typedef ExtendedListDigraphBase Parent;
    331327
    332328  private:
    333     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
     329    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     330
     331    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     332    ///
    334333    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    335     /// \brief Assignment of a digraph to another one is \e not allowed.
    336     /// Use DigraphCopy instead.
     334    ///\brief Assignment of ListDigraph to another one is \e not allowed.
     335    ///Use copyDigraph() instead.
     336
     337    ///Assignment of ListDigraph to another one is \e not allowed.
     338    ///Use copyDigraph() instead.
    337339    void operator=(const ListDigraph &) {}
    338340  public:
    … …  
    346348    ///Add a new node to the digraph.
    347349
    348     ///This function adds a new node to the digraph.
     350    ///Add a new node to the digraph.
    349351    ///\return The new node.
    350352    Node addNode() { return Parent::addNode(); }
    … …  
    352354    ///Add a new arc to the digraph.
    353355
    354     ///This function adds a new arc to the digraph with source node \c s
     356    ///Add a new arc to the digraph with source node \c s
    355357    ///and target node \c t.
    356358    ///\return The new arc.
    357     Arc addArc(Node s, Node t) {
     359    Arc addArc(const Node& s, const Node& t) {
    358360      return Parent::addArc(s, t);
    359361    }
    … …  
    361363    ///\brief Erase a node from the digraph.
    362364    ///
    363     ///This function erases the given node from the digraph.
    364     void erase(Node n) { Parent::erase(n); }
     365    ///Erase a node from the digraph.
     366    ///
     367    void erase(const Node& n) { Parent::erase(n); }
    365368
    366369    ///\brief Erase an arc from the digraph.
    367370    ///
    368     ///This function erases the given arc from the digraph.
    369     void erase(Arc a) { Parent::erase(a); }
     371    ///Erase an arc from the digraph.
     372    ///
     373    void erase(const Arc& a) { Parent::erase(a); }
    370374
    371375    /// Node validity check
    372376
    373     /// This function gives back \c true if the given node is valid,
    374     /// i.e. it is a real node of the digraph.
    375     ///
    376     /// \warning A removed node could become valid again if new nodes are
    377     /// added to the digraph.
     377    /// This function gives back true if the given node is valid,
     378    /// ie. it is a real node of the graph.
     379    ///
     380    /// \warning A Node pointing to a removed item
     381    /// could become valid again later if new nodes are
     382    /// added to the graph.
    378383    bool valid(Node n) const { return Parent::valid(n); }
    379384
    380385    /// Arc validity check
    381386
    382     /// This function gives back \c true if the given arc is valid,
    383     /// i.e. it is a real arc of the digraph.
    384     ///
    385     /// \warning A removed arc could become valid again if new arcs are
    386     /// added to the digraph.
     387    /// This function gives back true if the given arc is valid,
     388    /// ie. it is a real arc of the graph.
     389    ///
     390    /// \warning An Arc pointing to a removed item
     391    /// could become valid again later if new nodes are
     392    /// added to the graph.
    387393    bool valid(Arc a) const { return Parent::valid(a); }
    388394
    389     /// Change the target node of an arc
    390 
    391     /// This function changes the target node of the given arc \c a to \c n.
    392     ///
    393     ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
    394     ///arc remain valid, however \c InArcIt iterators are invalidated.
     395    /// Change the target of \c a to \c n
     396
     397    /// Change the target of \c a to \c n
     398    ///
     399    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
     400    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
     401    ///invalidated.
    395402    ///
    396403    ///\warning This functionality cannot be used together with the Snapshot
    … …  
    399406      Parent::changeTarget(a,n);
    400407    }
    401     /// Change the source node of an arc
    402 
    403     /// This function changes the source node of the given arc \c a to \c n.
    404     ///
    405     ///\note \c InArcIt iterators referencing the changed arc remain
    406     ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
     408    /// Change the source of \c a to \c n
     409
     410    /// Change the source of \c a to \c n
     411    ///
     412    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
     413    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
     414    ///invalidated.
    407415    ///
    408416    ///\warning This functionality cannot be used together with the Snapshot
    … …  
    412420    }
    413421
    414     /// Reverse the direction of an arc.
    415 
    416     /// This function reverses the direction of the given arc.
    417     ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
    418     ///the changed arc are invalidated.
     422    /// Invert the direction of an arc.
     423
     424    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
     425    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
     426    ///invalidated.
    419427    ///
    420428    ///\warning This functionality cannot be used together with the Snapshot
    421429    ///feature.
    422     void reverseArc(Arc a) {
    423       Node t=target(a);
    424       changeTarget(a,source(a));
    425       changeSource(a,t);
    426     }
     430    void reverseArc(Arc e) {
     431      Node t=target(e);
     432      changeTarget(e,source(e));
     433      changeSource(e,t);
     434    }
     435
     436    /// Reserve memory for nodes.
     437
     438    /// Using this function it is possible to avoid the superfluous memory
     439    /// allocation: if you know that the digraph you want to build will
     440    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     441    /// then it is worth reserving space for this amount before starting
     442    /// to build the digraph.
     443    /// \sa reserveArc
     444    void reserveNode(int n) { nodes.reserve(n); };
     445
     446    /// Reserve memory for arcs.
     447
     448    /// Using this function it is possible to avoid the superfluous memory
     449    /// allocation: if you know that the digraph you want to build will
     450    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     451    /// then it is worth reserving space for this amount before starting
     452    /// to build the digraph.
     453    /// \sa reserveNode
     454    void reserveArc(int m) { arcs.reserve(m); };
    427455
    428456    ///Contract two nodes.
    429457
    430     ///This function contracts the given two nodes.
    431     ///Node \c v is removed, but instead of deleting its
    432     ///incident arcs, they are joined to node \c u.
    433     ///If the last parameter \c r is \c true (this is the default value),
    434     ///then the newly created loops are removed.
    435     ///
    436     ///\note The moved arcs are joined to node \c u using changeSource()
    437     ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
    438     ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    439     ///iterators are invalidated for the incomming arcs of \c v.
    440     ///Moreover all iterators referencing node \c v or the removed
    441     ///loops are also invalidated. Other iterators remain valid.
     458    ///This function contracts two nodes.
     459    ///Node \p b will be removed but instead of deleting
     460    ///incident arcs, they will be joined to \p a.
     461    ///The last parameter \p r controls whether to remove loops. \c true
     462    ///means that loops will be removed.
     463    ///
     464    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
     465    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
     466    ///may be invalidated.
    442467    ///
    443468    ///\warning This functionality cannot be used together with the Snapshot
    444469    ///feature.
    445     void contract(Node u, Node v, bool r = true)
     470    void contract(Node a, Node b, bool r = true)
    446471    {
    447       for(OutArcIt e(*this,v);e!=INVALID;) {
     472      for(OutArcIt e(*this,b);e!=INVALID;) {
    448473        OutArcIt f=e;
    449474        ++f;
    450         if(r && target(e)==u) erase(e);
    451         else changeSource(e,u);
     475        if(r && target(e)==a) erase(e);
     476        else changeSource(e,a);
    452477        e=f;
    453478      }
    454       for(InArcIt e(*this,v);e!=INVALID;) {
     479      for(InArcIt e(*this,b);e!=INVALID;) {
    455480        InArcIt f=e;
    456481        ++f;
    457         if(r && source(e)==u) erase(e);
    458         else changeTarget(e,u);
     482        if(r && source(e)==a) erase(e);
     483        else changeTarget(e,a);
    459484        e=f;
    460485      }
    461       erase(v);
     486      erase(b);
    462487    }
    463488
    464489    ///Split a node.
    465490
    466     ///This function splits the given node. First, a new node is added
    467     ///to the digraph, then the source of each outgoing arc of node \c n
    468     ///is moved to this new node.
    469     ///If the second parameter \c connect is \c true (this is the default
    470     ///value), then a new arc from node \c n to the newly created node
    471     ///is also added.
     491    ///This function splits a node. First a new node is added to the digraph,
     492    ///then the source of each outgoing arc of \c n is moved to this new node.
     493    ///If \c connect is \c true (this is the default value), then a new arc
     494    ///from \c n to the newly created node is also added.
    472495    ///\return The newly created node.
    473496    ///
    474     ///\note All iterators remain valid.
    475     ///
    476     ///\warning This functionality cannot be used together with the
     497    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
     498    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
     499    ///be invalidated.
     500    ///
     501    ///\warning This functionality cannot be used in conjunction with the
    477502    ///Snapshot feature.
    478503    Node split(Node n, bool connect = true) {
    479504      Node b = addNode();
    480       nodes[b.id].first_out=nodes[n.id].first_out;
    481       nodes[n.id].first_out=-1;
    482       for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
    483         arcs[i].source=b.id;
     505      for(OutArcIt e(*this,n);e!=INVALID;) {
     506        OutArcIt f=e;
     507        ++f;
     508        changeSource(e,b);
     509        e=f;
    484510      }
    485511      if (connect) addArc(n,b);
    … …  
    489515    ///Split an arc.
    490516
    491     ///This function splits the given arc. First, a new node \c v is
    492     ///added to the digraph, then the target node of the original arc
    493     ///is set to \c v. Finally, an arc from \c v to the original target
    494     ///is added.
     517    ///This function splits an arc. First a new node \c b is added to
     518    ///the digraph, then the original arc is re-targeted to \c
     519    ///b. Finally an arc from \c b to the original target is added.
     520    ///
    495521    ///\return The newly created node.
    496     ///
    497     ///\note \c InArcIt iterators referencing the original arc are
    498     ///invalidated. Other iterators remain valid.
    499522    ///
    500523    ///\warning This functionality cannot be used together with the
    501524    ///Snapshot feature.
    502     Node split(Arc a) {
    503       Node v = addNode();
    504       addArc(v,target(a));
    505       changeTarget(a,v);
    506       return v;
    507     }
    508 
    509     ///Clear the digraph.
    510 
    511     ///This function erases all nodes and arcs from the digraph.
    512     ///
    513     void clear() {
    514       Parent::clear();
    515     }
    516 
    517     /// Reserve memory for nodes.
    518 
    519     /// Using this function, it is possible to avoid superfluous memory
    520     /// allocation: if you know that the digraph you want to build will
    521     /// be large (e.g. it will contain millions of nodes and/or arcs),
    522     /// then it is worth reserving space for this amount before starting
    523     /// to build the digraph.
    524     /// \sa reserveArc()
    525     void reserveNode(int n) { nodes.reserve(n); };
    526 
    527     /// Reserve memory for arcs.
    528 
    529     /// Using this function, it is possible to avoid superfluous memory
    530     /// allocation: if you know that the digraph you want to build will
    531     /// be large (e.g. it will contain millions of nodes and/or arcs),
    532     /// then it is worth reserving space for this amount before starting
    533     /// to build the digraph.
    534     /// \sa reserveNode()
    535     void reserveArc(int m) { arcs.reserve(m); };
     525    Node split(Arc e) {
     526      Node b = addNode();
     527      addArc(b,target(e));
     528      changeTarget(e,b);
     529      return b;
     530    }
    536531
    537532    /// \brief Class to make a snapshot of the digraph and restore
    … …  
    543538    /// restore() function.
    544539    ///
    545     /// \note After a state is restored, you cannot restore a later state,
    546     /// i.e. you cannot add the removed nodes and arcs again using
    547     /// another Snapshot instance.
    548     ///
    549     /// \warning Node and arc deletions and other modifications (e.g.
    550     /// reversing, contracting, splitting arcs or nodes) cannot be
     540    /// \warning Arc and node deletions and other modifications (e.g.
     541    /// contracting, splitting, reversing arcs or nodes) cannot be
    551542    /// restored. These events invalidate the snapshot.
    552     /// However the arcs and nodes that were added to the digraph after
    553     /// making the current snapshot can be removed without invalidating it.
    554543    class Snapshot {
    555544    protected:
    … …  
    721710      ///
    722711      /// Default constructor.
    723       /// You have to call save() to actually make a snapshot.
     712      /// To actually make a snapshot you must call save().
    724713      Snapshot()
    725714        : digraph(0), node_observer_proxy(*this),
    … …  
    728717      /// \brief Constructor that immediately makes a snapshot.
    729718      ///
    730       /// This constructor immediately makes a snapshot of the given digraph.
    731       Snapshot(ListDigraph &gr)
     719      /// This constructor immediately makes a snapshot of the digraph.
     720      /// \param _digraph The digraph we make a snapshot of.
     721      Snapshot(ListDigraph &_digraph)
    732722        : node_observer_proxy(*this),
    733723          arc_observer_proxy(*this) {
    734         attach(gr);
     724        attach(_digraph);
    735725      }
    736726
    737727      /// \brief Make a snapshot.
    738728      ///
    739       /// This function makes a snapshot of the given digraph.
    740       /// It can be called more than once. In case of a repeated
     729      /// Make a snapshot of the digraph.
     730      ///
     731      /// This function can be called more than once. In case of a repeated
    741732      /// call, the previous snapshot gets lost.
    742       void save(ListDigraph &gr) {
     733      /// \param _digraph The digraph we make the snapshot of.
     734      void save(ListDigraph &_digraph) {
    743735        if (attached()) {
    744736          detach();
    745737          clear();
    746738        }
    747         attach(gr);
     739        attach(_digraph);
    748740      }
    749741
    750742      /// \brief Undo the changes until the last snapshot.
    751       ///
    752       /// This function undos the changes until the last snapshot
    753       /// created by save() or Snapshot(ListDigraph&).
    754       ///
    755       /// \warning This method invalidates the snapshot, i.e. repeated
    756       /// restoring is not supported unless you call save() again.
     743      //
     744      /// Undo the changes until the last snapshot created by save().
    757745      void restore() {
    758746        detach();
    … …  
    768756      }
    769757
    770       /// \brief Returns \c true if the snapshot is valid.
     758      /// \brief Gives back true when the snapshot is valid.
    771759      ///
    772       /// This function returns \c true if the snapshot is valid.
     760      /// Gives back true when the snapshot is valid.
    773761      bool valid() const {
    774762        return attached();
    … …  
    807795
    808796    typedef ListGraphBase Graph;
     797
     798    class Node;
     799    class Arc;
     800    class Edge;
    809801
    810802    class Node {
    … …  
    856848      bool operator<(const Arc& arc) const {return id < arc.id;}
    857849    };
     850
     851
    858852
    859853    ListGraphBase()
    … …  
    11711165  ///A general undirected graph structure.
    11721166
    1173   ///\ref ListGraph is a versatile and fast undirected graph
    1174   ///implementation based on linked lists that are stored in
     1167  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
     1168  ///implementation based on static linked lists that are stored in
    11751169  ///\c std::vector structures.
    11761170  ///
    1177   ///This type fully conforms to the \ref concepts::Graph "Graph concept"
    1178   ///and it also provides several useful additional functionalities.
    1179   ///Most of its member functions and nested classes are documented
     1171  ///It conforms to the \ref concepts::Graph "Graph concept" and it
     1172  ///also provides several useful additional functionalities.
     1173  ///Most of the member functions and nested classes are documented
    11801174  ///only in the concept class.
    11811175  ///
    11821176  ///\sa concepts::Graph
    1183   ///\sa ListDigraph
     1177
    11841178  class ListGraph : public ExtendedListGraphBase {
    11851179    typedef ExtendedListGraphBase Parent;
    11861180
    11871181  private:
    1188     /// Graphs are \e not copy constructible. Use GraphCopy instead.
     1182    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     1183
     1184    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     1185    ///
    11891186    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    1190     /// \brief Assignment of a graph to another one is \e not allowed.
    1191     /// Use GraphCopy instead.
     1187    ///\brief Assignment of ListGraph to another one is \e not allowed.
     1188    ///Use copyGraph() instead.
     1189
     1190    ///Assignment of ListGraph to another one is \e not allowed.
     1191    ///Use copyGraph() instead.
    11921192    void operator=(const ListGraph &) {}
    11931193  public:
    … …  
    12021202    /// \brief Add a new node to the graph.
    12031203    ///
    1204     /// This function adds a new node to the graph.
     1204    /// Add a new node to the graph.
    12051205    /// \return The new node.
    12061206    Node addNode() { return Parent::addNode(); }
    … …  
    12081208    /// \brief Add a new edge to the graph.
    12091209    ///
    1210     /// This function adds a new edge to the graph between nodes
    1211     /// \c u and \c v with inherent orientation from node \c u to
    1212     /// node \c v.
     1210    /// Add a new edge to the graph with source node \c s
     1211    /// and target node \c t.
    12131212    /// \return The new edge.
    1214     Edge addEdge(Node u, Node v) {
    1215       return Parent::addEdge(u, v);
    1216     }
    1217 
    1218     ///\brief Erase a node from the graph.
    1219     ///
    1220     /// This function erases the given node from the graph.
    1221     void erase(Node n) { Parent::erase(n); }
    1222 
    1223     ///\brief Erase an edge from the graph.
    1224     ///
    1225     /// This function erases the given edge from the graph.
    1226     void erase(Edge e) { Parent::erase(e); }
     1213    Edge addEdge(const Node& s, const Node& t) {
     1214      return Parent::addEdge(s, t);
     1215    }
     1216
     1217    /// \brief Erase a node from the graph.
     1218    ///
     1219    /// Erase a node from the graph.
     1220    ///
     1221    void erase(const Node& n) { Parent::erase(n); }
     1222
     1223    /// \brief Erase an edge from the graph.
     1224    ///
     1225    /// Erase an edge from the graph.
     1226    ///
     1227    void erase(const Edge& e) { Parent::erase(e); }
    12271228    /// Node validity check
    12281229
    1229     /// This function gives back \c true if the given node is valid,
    1230     /// i.e. it is a real node of the graph.
    1231     ///
    1232     /// \warning A removed node could become valid again if new nodes are
     1230    /// This function gives back true if the given node is valid,
     1231    /// ie. it is a real node of the graph.
     1232    ///
     1233    /// \warning A Node pointing to a removed item
     1234    /// could become valid again later if new nodes are
    12331235    /// added to the graph.
    12341236    bool valid(Node n) const { return Parent::valid(n); }
     1237    /// Arc validity check
     1238
     1239    /// This function gives back true if the given arc is valid,
     1240    /// ie. it is a real arc of the graph.
     1241    ///
     1242    /// \warning An Arc pointing to a removed item
     1243    /// could become valid again later if new edges are
     1244    /// added to the graph.
     1245    bool valid(Arc a) const { return Parent::valid(a); }
    12351246    /// Edge validity check
    12361247
    1237     /// This function gives back \c true if the given edge is valid,
    1238     /// i.e. it is a real edge of the graph.
    1239     ///
    1240     /// \warning A removed edge could become valid again if new edges are
     1248    /// This function gives back true if the given edge is valid,
     1249    /// ie. it is a real arc of the graph.
     1250    ///
     1251    /// \warning A Edge pointing to a removed item
     1252    /// could become valid again later if new edges are
    12411253    /// added to the graph.
    12421254    bool valid(Edge e) const { return Parent::valid(e); }
    1243     /// Arc validity check
    1244 
    1245     /// This function gives back \c true if the given arc is valid,
    1246     /// i.e. it is a real arc of the graph.
    1247     ///
    1248     /// \warning A removed arc could become valid again if new edges are
    1249     /// added to the graph.
    1250     bool valid(Arc a) const { return Parent::valid(a); }
    1251 
    1252     /// \brief Change the first node of an edge.
    1253     ///
    1254     /// This function changes the first node of the given edge \c e to \c n.
    1255     ///
    1256     ///\note \c EdgeIt and \c ArcIt iterators referencing the
    1257     ///changed edge are invalidated and all other iterators whose
    1258     ///base node is the changed node are also invalidated.
     1255    /// \brief Change the end \c u of \c e to \c n
     1256    ///
     1257    /// This function changes the end \c u of \c e to node \c n.
     1258    ///
     1259    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
     1260    ///changed edge are invalidated and if the changed node is the
     1261    ///base node of an iterator then this iterator is also
     1262    ///invalidated.
    12591263    ///
    12601264    ///\warning This functionality cannot be used together with the
    … …  
    12631267      Parent::changeU(e,n);
    12641268    }
    1265     /// \brief Change the second node of an edge.
    1266     ///
    1267     /// This function changes the second node of the given edge \c e to \c n.
    1268     ///
    1269     ///\note \c EdgeIt iterators referencing the changed edge remain
    1270     ///valid, however \c ArcIt iterators referencing the changed edge and
    1271     ///all other iterators whose base node is the changed node are also
    1272     ///invalidated.
     1269    /// \brief Change the end \c v of \c e to \c n
     1270    ///
     1271    /// This function changes the end \c v of \c e to \c n.
     1272    ///
     1273    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
     1274    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
     1275    ///base node of an iterator then this iterator is invalidated.
    12731276    ///
    12741277    ///\warning This functionality cannot be used together with the
    … …  
    12771280      Parent::changeV(e,n);
    12781281    }
    1279 
    12801282    /// \brief Contract two nodes.
    12811283    ///
    1282     /// This function contracts the given two nodes.
    1283     /// Node \c b is removed, but instead of deleting
    1284     /// its incident edges, they are joined to node \c a.
    1285     /// If the last parameter \c r is \c true (this is the default value),
    1286     /// then the newly created loops are removed.
    1287     ///
    1288     /// \note The moved edges are joined to node \c a using changeU()
    1289     /// or changeV(), thus all edge and arc iterators whose base node is
    1290     /// \c b are invalidated.
    1291     /// Moreover all iterators referencing node \c b or the removed
    1292     /// loops are also invalidated. Other iterators remain valid.
     1284    /// This function contracts two nodes.
     1285    /// Node \p b will be removed but instead of deleting
     1286    /// its neighboring arcs, they will be joined to \p a.
     1287    /// The last parameter \p r controls whether to remove loops. \c true
     1288    /// means that loops will be removed.
     1289    ///
     1290    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
     1291    /// valid.
    12931292    ///
    12941293    ///\warning This functionality cannot be used together with the
    … …  
    13091308    }
    13101309
    1311     ///Clear the graph.
    1312 
    1313     ///This function erases all nodes and arcs from the graph.
    1314     ///
    1315     void clear() {
    1316       Parent::clear();
    1317     }
    1318 
    1319     /// Reserve memory for nodes.
    1320 
    1321     /// Using this function, it is possible to avoid superfluous memory
    1322     /// allocation: if you know that the graph you want to build will
    1323     /// be large (e.g. it will contain millions of nodes and/or edges),
    1324     /// then it is worth reserving space for this amount before starting
    1325     /// to build the graph.
    1326     /// \sa reserveEdge()
    1327     void reserveNode(int n) { nodes.reserve(n); };
    1328 
    1329     /// Reserve memory for edges.
    1330 
    1331     /// Using this function, it is possible to avoid superfluous memory
    1332     /// allocation: if you know that the graph you want to build will
    1333     /// be large (e.g. it will contain millions of nodes and/or edges),
    1334     /// then it is worth reserving space for this amount before starting
    1335     /// to build the graph.
    1336     /// \sa reserveNode()
    1337     void reserveEdge(int m) { arcs.reserve(2 * m); };
    13381310
    13391311    /// \brief Class to make a snapshot of the graph and restore
    … …  
    13451317    /// using the restore() function.
    13461318    ///
    1347     /// \note After a state is restored, you cannot restore a later state,
    1348     /// i.e. you cannot add the removed nodes and edges again using
    1349     /// another Snapshot instance.
    1350     ///
    1351     /// \warning Node and edge deletions and other modifications
    1352     /// (e.g. changing the end-nodes of edges or contracting nodes)
    1353     /// cannot be restored. These events invalidate the snapshot.
    1354     /// However the edges and nodes that were added to the graph after
    1355     /// making the current snapshot can be removed without invalidating it.
     1319    /// \warning Edge and node deletions and other modifications
     1320    /// (e.g. changing nodes of edges, contracting nodes) cannot be
     1321    /// restored. These events invalidate the snapshot.
    13561322    class Snapshot {
    13571323    protected:
    … …  
    15231489      ///
    15241490      /// Default constructor.
    1525       /// You have to call save() to actually make a snapshot.
     1491      /// To actually make a snapshot you must call save().
    15261492      Snapshot()
    15271493        : graph(0), node_observer_proxy(*this),
    … …  
    15301496      /// \brief Constructor that immediately makes a snapshot.
    15311497      ///
    1532       /// This constructor immediately makes a snapshot of the given graph.
    1533       Snapshot(ListGraph &gr)
     1498      /// This constructor immediately makes a snapshot of the graph.
     1499      /// \param _graph The graph we make a snapshot of.
     1500      Snapshot(ListGraph &_graph)
    15341501        : node_observer_proxy(*this),
    15351502          edge_observer_proxy(*this) {
    1536         attach(gr);
     1503        attach(_graph);
    15371504      }
    15381505
    15391506      /// \brief Make a snapshot.
    15401507      ///
    1541       /// This function makes a snapshot of the given graph.
    1542       /// It can be called more than once. In case of a repeated
     1508      /// Make a snapshot of the graph.
     1509      ///
     1510      /// This function can be called more than once. In case of a repeated
    15431511      /// call, the previous snapshot gets lost.
    1544       void save(ListGraph &gr) {
     1512      /// \param _graph The graph we make the snapshot of.
     1513      void save(ListGraph &_graph) {
    15451514        if (attached()) {
    15461515          detach();
    15471516          clear();
    15481517        }
    1549         attach(gr);
     1518        attach(_graph);
    15501519      }
    15511520
    15521521      /// \brief Undo the changes until the last snapshot.
    1553       ///
    1554       /// This function undos the changes until the last snapshot
    1555       /// created by save() or Snapshot(ListGraph&).
    1556       ///
    1557       /// \warning This method invalidates the snapshot, i.e. repeated
    1558       /// restoring is not supported unless you call save() again.
     1522      //
     1523      /// Undo the changes until the last snapshot created by save().
    15591524      void restore() {
    15601525        detach();
    … …  
    15701535      }
    15711536
    1572       /// \brief Returns \c true if the snapshot is valid.
     1537      /// \brief Gives back true when the snapshot is valid.
    15731538      ///
    1574       /// This function returns \c true if the snapshot is valid.
     1539      /// Gives back true when the snapshot is valid.
    15751540      bool valid() const {
    15761541        return attached();

  • lemon/smart_graph.h

    r736 r617  
    3333
    3434  class SmartDigraph;
    35 
     35  ///Base of SmartDigraph
     36
     37  ///Base of SmartDigraph
     38  ///
    3639  class SmartDigraphBase {
    3740  protected:
    … …  
    185188  ///\brief A smart directed graph class.
    186189  ///
    187   ///\ref SmartDigraph is a simple and fast digraph implementation.
    188   ///It is also quite memory efficient but at the price
    189   ///that it does not support node and arc deletion
    190   ///(except for the Snapshot feature).
     190  ///This is a simple and fast digraph implementation.
     191  ///It is also quite memory efficient, but at the price
     192  ///that <b> it does support only limited (only stack-like)
     193  ///node and arc deletions</b>.
     194  ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
    191195  ///
    192   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
    193   ///and it also provides some additional functionalities.
    194   ///Most of its member functions and nested classes are documented
    195   ///only in the concept class.
    196   ///
    197   ///\sa concepts::Digraph
    198   ///\sa SmartGraph
     196  ///\sa concepts::Digraph.
    199197  class SmartDigraph : public ExtendedSmartDigraphBase {
    200198    typedef ExtendedSmartDigraphBase Parent;
    201199
    202200  private:
    203     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
     201
     202    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
     203
     204    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
     205    ///
    204206    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
    205     /// \brief Assignment of a digraph to another one is \e not allowed.
    206     /// Use DigraphCopy instead.
     207    ///\brief Assignment of SmartDigraph to another one is \e not allowed.
     208    ///Use DigraphCopy() instead.
     209
     210    ///Assignment of SmartDigraph to another one is \e not allowed.
     211    ///Use DigraphCopy() instead.
    207212    void operator=(const SmartDigraph &) {}
    208213
    … …  
    217222    ///Add a new node to the digraph.
    218223
    219     ///This function adds a new node to the digraph.
    220     ///\return The new node.
     224    /// Add a new node to the digraph.
     225    /// \return The new node.
    221226    Node addNode() { return Parent::addNode(); }
    222227
    223228    ///Add a new arc to the digraph.
    224229
    225     ///This function adds a new arc to the digraph with source node \c s
     230    ///Add a new arc to the digraph with source node \c s
    226231    ///and target node \c t.
    227232    ///\return The new arc.
    228     Arc addArc(Node s, Node t) {
     233    Arc addArc(const Node& s, const Node& t) {
    229234      return Parent::addArc(s, t);
    230235    }
    231236
     237    /// \brief Using this it is possible to avoid the superfluous memory
     238    /// allocation.
     239
     240    /// Using this it is possible to avoid the superfluous memory
     241    /// allocation: if you know that the digraph you want to build will
     242    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     243    /// then it is worth reserving space for this amount before starting
     244    /// to build the digraph.
     245    /// \sa reserveArc
     246    void reserveNode(int n) { nodes.reserve(n); };
     247
     248    /// \brief Using this it is possible to avoid the superfluous memory
     249    /// allocation.
     250
     251    /// Using this it is possible to avoid the superfluous memory
     252    /// allocation: if you know that the digraph you want to build will
     253    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     254    /// then it is worth reserving space for this amount before starting
     255    /// to build the digraph.
     256    /// \sa reserveNode
     257    void reserveArc(int m) { arcs.reserve(m); };
     258
    232259    /// \brief Node validity check
    233260    ///
    234     /// This function gives back \c true if the given node is valid,
    235     /// i.e. it is a real node of the digraph.
     261    /// This function gives back true if the given node is valid,
     262    /// ie. it is a real node of the graph.
    236263    ///
    237264    /// \warning A removed node (using Snapshot) could become valid again
    238     /// if new nodes are added to the digraph.
     265    /// when new nodes are added to the graph.
    239266    bool valid(Node n) const { return Parent::valid(n); }
    240267
    241268    /// \brief Arc validity check
    242269    ///
    243     /// This function gives back \c true if the given arc is valid,
    244     /// i.e. it is a real arc of the digraph.
     270    /// This function gives back true if the given arc is valid,
     271    /// ie. it is a real arc of the graph.
    245272    ///
    246273    /// \warning A removed arc (using Snapshot) could become valid again
    247     /// if new arcs are added to the graph.
     274    /// when new arcs are added to the graph.
    248275    bool valid(Arc a) const { return Parent::valid(a); }
    249276
     277    ///Clear the digraph.
     278
     279    ///Erase all the nodes and arcs from the digraph.
     280    ///
     281    void clear() {
     282      Parent::clear();
     283    }
     284
    250285    ///Split a node.
    251286
    252     ///This function splits the given node. First, a new node is added
    253     ///to the digraph, then the source of each outgoing arc of node \c n
    254     ///is moved to this new node.
    255     ///If the second parameter \c connect is \c true (this is the default
    256     ///value), then a new arc from node \c n to the newly created node
    257     ///is also added.
     287    ///This function splits a node. First a new node is added to the digraph,
     288    ///then the source of each outgoing arc of \c n is moved to this new node.
     289    ///If \c connect is \c true (this is the default value), then a new arc
     290    ///from \c n to the newly created node is also added.
    258291    ///\return The newly created node.
    259292    ///
    260     ///\note All iterators remain valid.
    261     ///
     293    ///\note The <tt>Arc</tt>s
     294    ///referencing a moved arc remain
     295    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
     296    ///may be invalidated.
    262297    ///\warning This functionality cannot be used together with the Snapshot
    263298    ///feature.
    … …  
    274309    }
    275310
    276     ///Clear the digraph.
    277 
    278     ///This function erases all nodes and arcs from the digraph.
    279     ///
    280     void clear() {
    281       Parent::clear();
    282     }
    283 
    284     /// Reserve memory for nodes.
    285 
    286     /// Using this function, it is possible to avoid superfluous memory
    287     /// allocation: if you know that the digraph you want to build will
    288     /// be large (e.g. it will contain millions of nodes and/or arcs),
    289     /// then it is worth reserving space for this amount before starting
    290     /// to build the digraph.
    291     /// \sa reserveArc()
    292     void reserveNode(int n) { nodes.reserve(n); };
    293 
    294     /// Reserve memory for arcs.
    295 
    296     /// Using this function, it is possible to avoid superfluous memory
    297     /// allocation: if you know that the digraph you want to build will
    298     /// be large (e.g. it will contain millions of nodes and/or arcs),
    299     /// then it is worth reserving space for this amount before starting
    300     /// to build the digraph.
    301     /// \sa reserveNode()
    302     void reserveArc(int m) { arcs.reserve(m); };
    303 
    304311  public:
    305312
    … …  
    326333  public:
    327334
    328     ///Class to make a snapshot of the digraph and to restore it later.
    329 
    330     ///Class to make a snapshot of the digraph and to restore it later.
     335    ///Class to make a snapshot of the digraph and to restrore to it later.
     336
     337    ///Class to make a snapshot of the digraph and to restrore to it later.
    331338    ///
    332339    ///The newly added nodes and arcs can be removed using the
    333     ///restore() function. This is the only way for deleting nodes and/or
    334     ///arcs from a SmartDigraph structure.
    335     ///
    336     ///\note After a state is restored, you cannot restore a later state,
    337     ///i.e. you cannot add the removed nodes and arcs again using
    338     ///another Snapshot instance.
    339     ///
    340     ///\warning Node splitting cannot be restored.
    341     ///\warning The validity of the snapshot is not stored due to
    342     ///performance reasons. If you do not use the snapshot correctly,
    343     ///it can cause broken program, invalid or not restored state of
    344     ///the digraph or no change.
     340    ///restore() function.
     341    ///\note After you restore a state, you cannot restore
     342    ///a later state, in other word you cannot add again the arcs deleted
     343    ///by restore() using another one Snapshot instance.
     344    ///
     345    ///\warning If you do not use correctly the snapshot that can cause
     346    ///either broken program, invalid state of the digraph, valid but
     347    ///not the restored digraph or no change. Because the runtime performance
     348    ///the validity of the snapshot is not stored.
    345349    class Snapshot
    346350    {
    … …  
    354358
    355359      ///Default constructor.
    356       ///You have to call save() to actually make a snapshot.
     360      ///To actually make a snapshot you must call save().
     361      ///
    357362      Snapshot() : _graph(0) {}
    358363      ///Constructor that immediately makes a snapshot
    359364
    360       ///This constructor immediately makes a snapshot of the given digraph.
    361       ///
    362       Snapshot(SmartDigraph &gr) : _graph(&gr) {
     365      ///This constructor immediately makes a snapshot of the digraph.
     366      ///\param graph The digraph we make a snapshot of.
     367      Snapshot(SmartDigraph &graph) : _graph(&graph) {
    363368        node_num=_graph->nodes.size();
    364369        arc_num=_graph->arcs.size();
    … …  
    367372      ///Make a snapshot.
    368373
    369       ///This function makes a snapshot of the given digraph.
    370       ///It can be called more than once. In case of a repeated
     374      ///Make a snapshot of the digraph.
     375      ///
     376      ///This function can be called more than once. In case of a repeated
    371377      ///call, the previous snapshot gets lost.
    372       void save(SmartDigraph &gr) {
    373         _graph=&gr;
     378      ///\param graph The digraph we make the snapshot of.
     379      void save(SmartDigraph &graph)
     380      {
     381        _graph=&graph;
    374382        node_num=_graph->nodes.size();
    375383        arc_num=_graph->arcs.size();
    … …  
    378386      ///Undo the changes until a snapshot.
    379387
    380       ///This function undos the changes until the last snapshot
    381       ///created by save() or Snapshot(SmartDigraph&).
     388      ///Undo the changes until a snapshot created by save().
     389      ///
     390      ///\note After you restored a state, you cannot restore
     391      ///a later state, in other word you cannot add again the arcs deleted
     392      ///by restore().
    382393      void restore()
    383394      {
    … …  
    611622  /// \brief A smart undirected graph class.
    612623  ///
    613   /// \ref SmartGraph is a simple and fast graph implementation.
    614   /// It is also quite memory efficient but at the price
    615   /// that it does not support node and edge deletion
    616   /// (except for the Snapshot feature).
     624  /// This is a simple and fast graph implementation.
     625  /// It is also quite memory efficient, but at the price
     626  /// that <b> it does support only limited (only stack-like)
     627  /// node and arc deletions</b>.
     628  /// It fully conforms to the \ref concepts::Graph "Graph concept".
    617629  ///
    618   /// This type fully conforms to the \ref concepts::Graph "Graph concept"
    619   /// and it also provides some additional functionalities.
    620   /// Most of its member functions and nested classes are documented
    621   /// only in the concept class.
    622   ///
    623   /// \sa concepts::Graph
    624   /// \sa SmartDigraph
     630  /// \sa concepts::Graph.
    625631  class SmartGraph : public ExtendedSmartGraphBase {
    626632    typedef ExtendedSmartGraphBase Parent;
    627633
    628634  private:
    629     /// Graphs are \e not copy constructible. Use GraphCopy instead.
     635
     636    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
     637
     638    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
     639    ///
    630640    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
    631     /// \brief Assignment of a graph to another one is \e not allowed.
    632     /// Use GraphCopy instead.
     641
     642    ///\brief Assignment of SmartGraph to another one is \e not allowed.
     643    ///Use GraphCopy() instead.
     644
     645    ///Assignment of SmartGraph to another one is \e not allowed.
     646    ///Use GraphCopy() instead.
    633647    void operator=(const SmartGraph &) {}
    634648
    … …  
    641655    SmartGraph() {}
    642656
    643     /// \brief Add a new node to the graph.
    644     ///
    645     /// This function adds a new node to the graph.
     657    ///Add a new node to the graph.
     658
     659    /// Add a new node to the graph.
    646660    /// \return The new node.
    647661    Node addNode() { return Parent::addNode(); }
    648662
    649     /// \brief Add a new edge to the graph.
    650     ///
    651     /// This function adds a new edge to the graph between nodes
    652     /// \c u and \c v with inherent orientation from node \c u to
    653     /// node \c v.
    654     /// \return The new edge.
    655     Edge addEdge(Node u, Node v) {
    656       return Parent::addEdge(u, v);
     663    ///Add a new edge to the graph.
     664
     665    ///Add a new edge to the graph with node \c s
     666    ///and \c t.
     667    ///\return The new edge.
     668    Edge addEdge(const Node& s, const Node& t) {
     669      return Parent::addEdge(s, t);
    657670    }
    658671
    659672    /// \brief Node validity check
    660673    ///
    661     /// This function gives back \c true if the given node is valid,
    662     /// i.e. it is a real node of the graph.
     674    /// This function gives back true if the given node is valid,
     675    /// ie. it is a real node of the graph.
    663676    ///
    664677    /// \warning A removed node (using Snapshot) could become valid again
    665     /// if new nodes are added to the graph.
     678    /// when new nodes are added to the graph.
    666679    bool valid(Node n) const { return Parent::valid(n); }
    667680
     681    /// \brief Arc validity check
     682    ///
     683    /// This function gives back true if the given arc is valid,
     684    /// ie. it is a real arc of the graph.
     685    ///
     686    /// \warning A removed arc (using Snapshot) could become valid again
     687    /// when new edges are added to the graph.
     688    bool valid(Arc a) const { return Parent::valid(a); }
     689
    668690    /// \brief Edge validity check
    669691    ///
    670     /// This function gives back \c true if the given edge is valid,
    671     /// i.e. it is a real edge of the graph.
     692    /// This function gives back true if the given edge is valid,
     693    /// ie. it is a real edge of the graph.
    672694    ///
    673695    /// \warning A removed edge (using Snapshot) could become valid again
    674     /// if new edges are added to the graph.
     696    /// when new edges are added to the graph.
    675697    bool valid(Edge e) const { return Parent::valid(e); }
    676698
    677     /// \brief Arc validity check
    678     ///
    679     /// This function gives back \c true if the given arc is valid,
    680     /// i.e. it is a real arc of the graph.
    681     ///
    682     /// \warning A removed arc (using Snapshot) could become valid again
    683     /// if new edges are added to the graph.
    684     bool valid(Arc a) const { return Parent::valid(a); }
    685 
    686699    ///Clear the graph.
    687700
    688     ///This function erases all nodes and arcs from the graph.
     701    ///Erase all the nodes and edges from the graph.
    689702    ///
    690703    void clear() {
    691704      Parent::clear();
    692705    }
    693 
    694     /// Reserve memory for nodes.
    695 
    696     /// Using this function, it is possible to avoid superfluous memory
    697     /// allocation: if you know that the graph you want to build will
    698     /// be large (e.g. it will contain millions of nodes and/or edges),
    699     /// then it is worth reserving space for this amount before starting
    700     /// to build the graph.
    701     /// \sa reserveEdge()
    702     void reserveNode(int n) { nodes.reserve(n); };
    703 
    704     /// Reserve memory for edges.
    705 
    706     /// Using this function, it is possible to avoid superfluous memory
    707     /// allocation: if you know that the graph you want to build will
    708     /// be large (e.g. it will contain millions of nodes and/or edges),
    709     /// then it is worth reserving space for this amount before starting
    710     /// to build the graph.
    711     /// \sa reserveNode()
    712     void reserveEdge(int m) { arcs.reserve(2 * m); };
    713706
    714707  public:
    … …  
    750743  public:
    751744
    752     ///Class to make a snapshot of the graph and to restore it later.
    753 
    754     ///Class to make a snapshot of the graph and to restore it later.
    755     ///
    756     ///The newly added nodes and edges can be removed using the
    757     ///restore() function. This is the only way for deleting nodes and/or
    758     ///edges from a SmartGraph structure.
    759     ///
    760     ///\note After a state is restored, you cannot restore a later state,
    761     ///i.e. you cannot add the removed nodes and edges again using
    762     ///another Snapshot instance.
    763     ///
    764     ///\warning The validity of the snapshot is not stored due to
    765     ///performance reasons. If you do not use the snapshot correctly,
    766     ///it can cause broken program, invalid or not restored state of
    767     ///the graph or no change.
     745    ///Class to make a snapshot of the digraph and to restrore to it later.
     746
     747    ///Class to make a snapshot of the digraph and to restrore to it later.
     748    ///
     749    ///The newly added nodes and arcs can be removed using the
     750    ///restore() function.
     751    ///
     752    ///\note After you restore a state, you cannot restore
     753    ///a later state, in other word you cannot add again the arcs deleted
     754    ///by restore() using another one Snapshot instance.
     755    ///
     756    ///\warning If you do not use correctly the snapshot that can cause
     757    ///either broken program, invalid state of the digraph, valid but
     758    ///not the restored digraph or no change. Because the runtime performance
     759    ///the validity of the snapshot is not stored.
    768760    class Snapshot
    769761    {
    … …  
    777769
    778770      ///Default constructor.
    779       ///You have to call save() to actually make a snapshot.
     771      ///To actually make a snapshot you must call save().
     772      ///
    780773      Snapshot() : _graph(0) {}
    781774      ///Constructor that immediately makes a snapshot
    782775
    783       /// This constructor immediately makes a snapshot of the given graph.
     776      ///This constructor immediately makes a snapshot of the digraph.
     777      ///\param graph The digraph we make a snapshot of.
     778      Snapshot(SmartGraph &graph) {
     779        graph.saveSnapshot(*this);
     780      }
     781
     782      ///Make a snapshot.
     783
     784      ///Make a snapshot of the graph.
    784785      ///
    785       Snapshot(SmartGraph &gr) {
    786         gr.saveSnapshot(*this);
    787       }
    788 
    789       ///Make a snapshot.
    790 
    791       ///This function makes a snapshot of the given graph.
    792       ///It can be called more than once. In case of a repeated
     786      ///This function can be called more than once. In case of a repeated
    793787      ///call, the previous snapshot gets lost.
    794       void save(SmartGraph &gr)
     788      ///\param graph The digraph we make the snapshot of.
     789      void save(SmartGraph &graph)
    795790      {
    796         gr.saveSnapshot(*this);
    797       }
    798 
    799       ///Undo the changes until the last snapshot.
    800 
    801       ///This function undos the changes until the last snapshot
    802       ///created by save() or Snapshot(SmartGraph&).
     791        graph.saveSnapshot(*this);
     792      }
     793
     794      ///Undo the changes until a snapshot.
     795
     796      ///Undo the changes until a snapshot created by save().
     797      ///
     798      ///\note After you restored a state, you cannot restore
     799      ///a later state, in other word you cannot add again the arcs deleted
     800      ///by restore().
    803801      void restore()
    804802      {

  • test/digraph_test.cc

    r740 r440  
    3636  checkGraphArcList(G, 0);
    3737
    38   G.reserveNode(3);
    39   G.reserveArc(4);
    40 
    4138  Node
    4239    n1 = G.addNode(),
    … …  
    287284
    288285  snapshot.restore();
    289   snapshot.save(G);
    290 
    291   checkGraphNodeList(G, 4);
    292   checkGraphArcList(G, 4);
    293 
    294   G.addArc(G.addNode(), G.addNode());
    295 
    296   snapshot.restore();
    297286
    298287  checkGraphNodeList(G, 4);
    … …  
    387376  typedef FullDigraph Digraph;
    388377  DIGRAPH_TYPEDEFS(Digraph);
    389 
    390378  Digraph G(num);
    391   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
    392 
    393   G.resize(num);
    394   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
    395379
    396380  checkGraphNodeList(G, num);

  • test/graph_test.cc

    r740 r440  
    3939  checkGraphArcList(G, 0);
    4040
    41   G.reserveNode(3);
    42   G.reserveEdge(3);
    43 
    4441  Node
    4542    n1 = G.addNode(),
    … …  
    260257
    261258  snapshot.restore();
    262   snapshot.save(G);
    263259
    264260  checkGraphNodeList(G, 4);
    265261  checkGraphEdgeList(G, 3);
    266262  checkGraphArcList(G, 6);
    267  
    268   G.addEdge(G.addNode(), G.addNode());
    269 
    270   snapshot.restore();
    271 
    272   checkGraphNodeList(G, 4);
    273   checkGraphEdgeList(G, 3);
    274   checkGraphArcList(G, 6);
    275263}
    276264
    … …  
    280268
    281269  Graph G(num);
    282   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
    283         "Wrong size");
    284 
    285   G.resize(num);
    286   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
    287         "Wrong size");
    288 
    289270  checkGraphNodeList(G, num);
    290271  checkGraphEdgeList(G, num * (num - 1) / 2);
    … …  
    431412  check(G.height() == height, "Wrong row number");
    432413
    433   G.resize(width, height);
    434   check(G.width() == width, "Wrong column number");
    435   check(G.height() == height, "Wrong row number");
    436 
    437414  for (int i = 0; i < width; ++i) {
    438415    for (int j = 0; j < height; ++j) {
    … …  
    510487
    511488  HypercubeGraph G(dim);
    512   check(G.dimension() == dim, "Wrong dimension");
    513 
    514   G.resize(dim);
    515   check(G.dimension() == dim, "Wrong dimension");
    516  
    517489  checkGraphNodeList(G, 1 << dim);
    518490  checkGraphEdgeList(G, dim * (1 << (dim-1)));
Note: See TracChangeset for help on using the changeset viewer.