COIN-OR::LEMON - Graph Library

Changeset 735:853fcddcf282 in lemon-main


Ignore:
Timestamp:
08/23/09 11:09:22 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Doc improvements, fixes and unifications for graphs (#311)

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

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

    r617 r735  
    2525///\ingroup graphs
    2626///\file
    27 ///\brief FullGraph and FullDigraph classes.
     27///\brief FullDigraph and FullGraph classes.
    2828
    2929namespace lemon {
     
    149149  /// \ingroup graphs
    150150  ///
    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,
     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,
    164166  /// but there are two differences. While this class conforms only
    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.
     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.
    169171  ///
    170172  /// \sa FullGraph
     
    174176  public:
    175177
    176     /// \brief Constructor
     178    /// \brief Default constructor.
     179    ///
     180    /// Default constructor. The number of nodes and arcs will be zero.
    177181    FullDigraph() { construct(0); }
    178182
     
    185189    /// \brief Resizes the digraph
    186190    ///
    187     /// Resizes the digraph. The function will fully destroy and
    188     /// rebuild the digraph. This cause that the maps of the digraph will
     191    /// This function resizes the digraph. It fully destroys and
     192    /// rebuilds the structure, therefore the maps of the digraph will be
    189193    /// reallocated automatically and the previous values will be lost.
    190194    void resize(int n) {
     
    198202    /// \brief Returns the node with the given index.
    199203    ///
    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>.
     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>.
    203207    /// \sa index()
    204208    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    206210    /// \brief Returns the index of the given node.
    207211    ///
    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); }
     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); }
    213217
    214218    /// \brief Returns the arc connecting the given nodes.
    215219    ///
    216220    /// Returns the arc connecting the given nodes.
    217     Arc arc(const Node& u, const Node& v) const {
     221    Arc arc(Node u, Node v) const {
    218222      return Parent::arc(u, v);
    219223    }
     
    521525  /// \brief An undirected full graph class.
    522526  ///
    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
     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
    534540  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    535541  /// this class conforms to the \ref concepts::Graph "Graph" concept,
    536   /// moreover \c FullGraph does not contain a loop arc for each
    537   /// node as \c FullDigraph does.
     542  /// moreover this class does not contain a loop for each
     543  /// node as FullDigraph does.
    538544  ///
    539545  /// \sa FullDigraph
     
    543549  public:
    544550
    545     /// \brief Constructor
     551    /// \brief Default constructor.
     552    ///
     553    /// Default constructor. The number of nodes and edges will be zero.
    546554    FullGraph() { construct(0); }
    547555
     
    554562    /// \brief Resizes the graph
    555563    ///
    556     /// Resizes the graph. The function will fully destroy and
    557     /// rebuild the graph. This cause that the maps of the graph will
     564    /// This function resizes the graph. It fully destroys and
     565    /// rebuilds the structure, therefore the maps of the graph will be
    558566    /// reallocated automatically and the previous values will be lost.
    559567    void resize(int n) {
     
    569577    /// \brief Returns the node with the given index.
    570578    ///
    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>.
     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>.
    574582    /// \sa index()
    575583    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    577585    /// \brief Returns the index of the given node.
    578586    ///
    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); }
     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); }
    584592
    585593    /// \brief Returns the arc connecting the given nodes.
    586594    ///
    587595    /// Returns the arc connecting the given nodes.
    588     Arc arc(const Node& s, const Node& t) const {
     596    Arc arc(Node s, Node t) const {
    589597      return Parent::arc(s, t);
    590598    }
    591599
    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 {
     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 {
    596604      return Parent::edge(u, v);
    597605    }
  • lemon/grid_graph.h

    r617 r735  
    471471  /// \brief Grid graph class
    472472  ///
    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
     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
    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().
    484488  ///
    485489  /// \image html grid_graph.png
     
    497501  ///\endcode
    498502  ///
    499   /// This graph type fully conforms to the \ref concepts::Graph
    500   /// "Graph concept".
     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.
    501506  class GridGraph : public ExtendedGridGraphBase {
    502507    typedef ExtendedGridGraphBase Parent;
     
    504509  public:
    505510
    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>.
     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>".
    509516    class IndexMap {
    510517    public:
     
    515522
    516523      /// \brief Constructor
    517       ///
    518       /// Constructor
    519524      IndexMap(const GridGraph& graph) : _graph(graph) {}
    520525
    521526      /// \brief The subscript operator
    522       ///
    523       /// The subscript operator.
    524527      Value operator[](Key key) const {
    525528        return _graph.pos(key);
     
    541544
    542545      /// \brief Constructor
    543       ///
    544       /// Constructor
    545546      ColMap(const GridGraph& graph) : _graph(graph) {}
    546547
    547548      /// \brief The subscript operator
    548       ///
    549       /// The subscript operator.
    550549      Value operator[](Key key) const {
    551550        return _graph.col(key);
     
    567566
    568567      /// \brief Constructor
    569       ///
    570       /// Constructor
    571568      RowMap(const GridGraph& graph) : _graph(graph) {}
    572569
    573570      /// \brief The subscript operator
    574       ///
    575       /// The subscript operator.
    576571      Value operator[](Key key) const {
    577572        return _graph.row(key);
     
    584579    /// \brief Constructor
    585580    ///
    586     /// Construct a grid graph with given size.
     581    /// Construct a grid graph with the given size.
    587582    GridGraph(int width, int height) { construct(width, height); }
    588583
    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.
     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.
    595589    void resize(int width, int height) {
    596590      Parent::notifier(Arc()).clear();
     
    610604    }
    611605
    612     /// \brief Gives back the column index of the node.
     606    /// \brief The column index of the node.
    613607    ///
    614608    /// Gives back the column index of the node.
     
    617611    }
    618612
    619     /// \brief Gives back the row index of the node.
     613    /// \brief The row index of the node.
    620614    ///
    621615    /// Gives back the row index of the node.
     
    624618    }
    625619
    626     /// \brief Gives back the position of the node.
     620    /// \brief The position of the node.
    627621    ///
    628622    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
     
    631625    }
    632626
    633     /// \brief Gives back the number of the columns.
     627    /// \brief The number of the columns.
    634628    ///
    635629    /// Gives back the number of the columns.
     
    638632    }
    639633
    640     /// \brief Gives back the number of the rows.
     634    /// \brief The number of the rows.
    641635    ///
    642636    /// Gives back the number of the rows.
     
    645639    }
    646640
    647     /// \brief Gives back the arc goes right from the node.
     641    /// \brief The arc goes right from the node.
    648642    ///
    649643    /// Gives back the arc goes right from the node. If there is not
     
    653647    }
    654648
    655     /// \brief Gives back the arc goes left from the node.
     649    /// \brief The arc goes left from the node.
    656650    ///
    657651    /// Gives back the arc goes left from the node. If there is not
     
    661655    }
    662656
    663     /// \brief Gives back the arc goes up from the node.
     657    /// \brief The arc goes up from the node.
    664658    ///
    665659    /// Gives back the arc goes up from the node. If there is not
     
    669663    }
    670664
    671     /// \brief Gives back the arc goes down from the node.
     665    /// \brief The arc goes down from the node.
    672666    ///
    673667    /// Gives back the arc goes down from the node. If there is not
  • lemon/hypercube_graph.h

    r617 r735  
    283283  /// \brief Hypercube graph class
    284284  ///
    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.
     285  /// HypercubeGraph implements a special graph type. The nodes of the
     286  /// graph are indexed with integers having 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.
     291  ///
     292  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
     293  /// Most of its member functions and nested classes are documented
     294  /// only in the concept class.
    289295  ///
    290296  /// \note The type of the indices is chosen to \c int for efficiency
    291297  /// reasons. Thus the maximum dimension of this implementation is 26
    292298  /// (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".
    296299  class HypercubeGraph : public ExtendedHypercubeGraphBase {
    297300    typedef ExtendedHypercubeGraphBase Parent;
     
    321324    ///
    322325    /// Gives back the dimension id of the given edge.
    323     /// It is in the [0..dim-1] range.
     326    /// It is in the range <tt>[0..dim-1]</tt>.
    324327    int dimension(Edge edge) const {
    325328      return Parent::dimension(edge);
     
    329332    ///
    330333    /// Gives back the dimension id of the given arc.
    331     /// It is in the [0..dim-1] range.
     334    /// It is in the range <tt>[0..dim-1]</tt>.
    332335    int dimension(Arc arc) const {
    333336      return Parent::dimension(arc);
  • lemon/list_graph.h

    r617 r735  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListDigraph, ListGraph classes.
     24///\brief ListDigraph and ListGraph classes.
    2525
    2626#include <lemon/core.h>
     
    312312  ///A general directed graph structure.
    313313
    314   ///\ref ListDigraph is a simple and fast <em>directed graph</em>
    315   ///implementation based on static linked lists that are stored in
     314  ///\ref ListDigraph is a versatile and fast directed graph
     315  ///implementation based on linked lists that are stored in
    316316  ///\c std::vector structures.
    317317  ///
    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
     318  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
     319  ///and it also provides several useful additional functionalities.
     320  ///Most of its member functions and nested classes are documented
    321321  ///only in the concept class.
    322322  ///
    323323  ///\sa concepts::Digraph
    324 
     324  ///\sa ListGraph
    325325  class ListDigraph : public ExtendedListDigraphBase {
    326326    typedef ExtendedListDigraphBase Parent;
    327327
    328328  private:
    329     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    330 
    331     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    332     ///
     329    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
    333330    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    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.
     331    /// \brief Assignment of a digraph to another one is \e not allowed.
     332    /// Use DigraphCopy instead.
    339333    void operator=(const ListDigraph &) {}
    340334  public:
     
    348342    ///Add a new node to the digraph.
    349343
    350     ///Add a new node to the digraph.
     344    ///This function adds a new node to the digraph.
    351345    ///\return The new node.
    352346    Node addNode() { return Parent::addNode(); }
     
    354348    ///Add a new arc to the digraph.
    355349
    356     ///Add a new arc to the digraph with source node \c s
     350    ///This function adds a new arc to the digraph with source node \c s
    357351    ///and target node \c t.
    358352    ///\return The new arc.
    359     Arc addArc(const Node& s, const Node& t) {
     353    Arc addArc(Node s, Node t) {
    360354      return Parent::addArc(s, t);
    361355    }
     
    363357    ///\brief Erase a node from the digraph.
    364358    ///
    365     ///Erase a node from the digraph.
    366     ///
    367     void erase(const Node& n) { Parent::erase(n); }
     359    ///This function erases the given node from the digraph.
     360    void erase(Node n) { Parent::erase(n); }
    368361
    369362    ///\brief Erase an arc from the digraph.
    370363    ///
    371     ///Erase an arc from the digraph.
    372     ///
    373     void erase(const Arc& a) { Parent::erase(a); }
     364    ///This function erases the given arc from the digraph.
     365    void erase(Arc a) { Parent::erase(a); }
    374366
    375367    /// Node validity check
    376368
    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.
     369    /// This function gives back \c true if the given node is valid,
     370    /// i.e. it is a real node of the digraph.
     371    ///
     372    /// \warning A removed node could become valid again if new nodes are
     373    /// added to the digraph.
    383374    bool valid(Node n) const { return Parent::valid(n); }
    384375
    385376    /// Arc validity check
    386377
    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.
     378    /// This function gives back \c true if the given arc is valid,
     379    /// i.e. it is a real arc of the digraph.
     380    ///
     381    /// \warning A removed arc could become valid again if new arcs are
     382    /// added to the digraph.
    393383    bool valid(Arc a) const { return Parent::valid(a); }
    394384
    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.
     385    /// Change the target node of an arc
     386
     387    /// This function changes the target node of the given arc \c a to \c n.
     388    ///
     389    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
     390    ///arc remain valid, however \c InArcIt iterators are invalidated.
    402391    ///
    403392    ///\warning This functionality cannot be used together with the Snapshot
     
    406395      Parent::changeTarget(a,n);
    407396    }
    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.
     397    /// Change the source node of an arc
     398
     399    /// This function changes the source node of the given arc \c a to \c n.
     400    ///
     401    ///\note \c InArcIt iterators referencing the changed arc remain
     402    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
    415403    ///
    416404    ///\warning This functionality cannot be used together with the Snapshot
     
    420408    }
    421409
    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.
     410    /// Reverse the direction of an arc.
     411
     412    /// This function reverses the direction of the given arc.
     413    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
     414    ///the changed arc are invalidated.
    427415    ///
    428416    ///\warning This functionality cannot be used together with the Snapshot
    429417    ///feature.
    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); };
     418    void reverseArc(Arc a) {
     419      Node t=target(a);
     420      changeTarget(a,source(a));
     421      changeSource(a,t);
     422    }
    455423
    456424    ///Contract two nodes.
    457425
    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.
     426    ///This function contracts the given two nodes.
     427    ///Node \c v is removed, but instead of deleting its
     428    ///incident arcs, they are joined to node \c u.
     429    ///If the last parameter \c r is \c true (this is the default value),
     430    ///then the newly created loops are removed.
     431    ///
     432    ///\note The moved arcs are joined to node \c u using changeSource()
     433    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
     434    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
     435    ///iterators are invalidated for the incomming arcs of \c v.
     436    ///Moreover all iterators referencing node \c v or the removed
     437    ///loops are also invalidated. Other iterators remain valid.
    467438    ///
    468439    ///\warning This functionality cannot be used together with the Snapshot
    469440    ///feature.
    470     void contract(Node a, Node b, bool r = true)
     441    void contract(Node u, Node v, bool r = true)
    471442    {
    472       for(OutArcIt e(*this,b);e!=INVALID;) {
     443      for(OutArcIt e(*this,v);e!=INVALID;) {
    473444        OutArcIt f=e;
    474445        ++f;
    475         if(r && target(e)==a) erase(e);
    476         else changeSource(e,a);
     446        if(r && target(e)==u) erase(e);
     447        else changeSource(e,u);
    477448        e=f;
    478449      }
    479       for(InArcIt e(*this,b);e!=INVALID;) {
     450      for(InArcIt e(*this,v);e!=INVALID;) {
    480451        InArcIt f=e;
    481452        ++f;
    482         if(r && source(e)==a) erase(e);
    483         else changeTarget(e,a);
     453        if(r && source(e)==u) erase(e);
     454        else changeTarget(e,u);
    484455        e=f;
    485456      }
    486       erase(b);
     457      erase(v);
    487458    }
    488459
    489460    ///Split a node.
    490461
    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.
     462    ///This function splits the given node. First, a new node is added
     463    ///to the digraph, then the source of each outgoing arc of node \c n
     464    ///is moved to this new node.
     465    ///If the second parameter \c connect is \c true (this is the default
     466    ///value), then a new arc from node \c n to the newly created node
     467    ///is also added.
    495468    ///\return The newly created node.
    496469    ///
    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
     470    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
     471    ///arcs of node \c n are invalidated. Other iterators remain valid.
     472    ///
     473    ///\warning This functionality cannot be used together with the
    502474    ///Snapshot feature.
    503475    Node split(Node n, bool connect = true) {
     
    515487    ///Split an arc.
    516488
    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     ///
     489    ///This function splits the given arc. First, a new node \c v is
     490    ///added to the digraph, then the target node of the original arc
     491    ///is set to \c v. Finally, an arc from \c v to the original target
     492    ///is added.
    521493    ///\return The newly created node.
     494    ///
     495    ///\note \c InArcIt iterators referencing the original arc are
     496    ///invalidated. Other iterators remain valid.
    522497    ///
    523498    ///\warning This functionality cannot be used together with the
    524499    ///Snapshot feature.
    525     Node split(Arc e) {
    526       Node b = addNode();
    527       addArc(b,target(e));
    528       changeTarget(e,b);
    529       return b;
    530     }
     500    Node split(Arc a) {
     501      Node v = addNode();
     502      addArc(v,target(a));
     503      changeTarget(a,v);
     504      return v;
     505    }
     506
     507    ///Clear the digraph.
     508
     509    ///This function erases all nodes and arcs from the digraph.
     510    ///
     511    void clear() {
     512      Parent::clear();
     513    }
     514
     515    /// Reserve memory for nodes.
     516
     517    /// Using this function, it is possible to avoid superfluous memory
     518    /// allocation: if you know that the digraph you want to build will
     519    /// be large (e.g. it will contain millions of nodes and/or arcs),
     520    /// then it is worth reserving space for this amount before starting
     521    /// to build the digraph.
     522    /// \sa reserveArc()
     523    void reserveNode(int n) { nodes.reserve(n); };
     524
     525    /// Reserve memory for arcs.
     526
     527    /// Using this function, it is possible to avoid superfluous memory
     528    /// allocation: if you know that the digraph you want to build will
     529    /// be large (e.g. it will contain millions of nodes and/or arcs),
     530    /// then it is worth reserving space for this amount before starting
     531    /// to build the digraph.
     532    /// \sa reserveNode()
     533    void reserveArc(int m) { arcs.reserve(m); };
    531534
    532535    /// \brief Class to make a snapshot of the digraph and restore
     
    538541    /// restore() function.
    539542    ///
    540     /// \warning Arc and node deletions and other modifications (e.g.
    541     /// contracting, splitting, reversing arcs or nodes) cannot be
     543    /// \note After a state is restored, you cannot restore a later state,
     544    /// i.e. you cannot add the removed nodes and arcs again using
     545    /// another Snapshot instance.
     546    ///
     547    /// \warning Node and arc deletions and other modifications (e.g.
     548    /// reversing, contracting, splitting arcs or nodes) cannot be
    542549    /// restored. These events invalidate the snapshot.
     550    /// However the arcs and nodes that were added to the digraph after
     551    /// making the current snapshot can be removed without invalidating it.
    543552    class Snapshot {
    544553    protected:
     
    710719      ///
    711720      /// Default constructor.
    712       /// To actually make a snapshot you must call save().
     721      /// You have to call save() to actually make a snapshot.
    713722      Snapshot()
    714723        : digraph(0), node_observer_proxy(*this),
     
    717726      /// \brief Constructor that immediately makes a snapshot.
    718727      ///
    719       /// This constructor immediately makes a snapshot of the digraph.
    720       /// \param _digraph The digraph we make a snapshot of.
    721       Snapshot(ListDigraph &_digraph)
     728      /// This constructor immediately makes a snapshot of the given digraph.
     729      Snapshot(ListDigraph &gr)
    722730        : node_observer_proxy(*this),
    723731          arc_observer_proxy(*this) {
    724         attach(_digraph);
     732        attach(gr);
    725733      }
    726734
    727735      /// \brief Make a snapshot.
    728736      ///
    729       /// Make a snapshot of the digraph.
    730       ///
    731       /// This function can be called more than once. In case of a repeated
     737      /// This function makes a snapshot of the given digraph.
     738      /// It can be called more than once. In case of a repeated
    732739      /// call, the previous snapshot gets lost.
    733       /// \param _digraph The digraph we make the snapshot of.
    734       void save(ListDigraph &_digraph) {
     740      void save(ListDigraph &gr) {
    735741        if (attached()) {
    736742          detach();
    737743          clear();
    738744        }
    739         attach(_digraph);
     745        attach(gr);
    740746      }
    741747
    742748      /// \brief Undo the changes until the last snapshot.
    743       //
    744       /// Undo the changes until the last snapshot created by save().
     749      ///
     750      /// This function undos the changes until the last snapshot
     751      /// created by save() or Snapshot(ListDigraph&).
    745752      void restore() {
    746753        detach();
     
    756763      }
    757764
    758       /// \brief Gives back true when the snapshot is valid.
     765      /// \brief Returns \c true if the snapshot is valid.
    759766      ///
    760       /// Gives back true when the snapshot is valid.
     767      /// This function returns \c true if the snapshot is valid.
    761768      bool valid() const {
    762769        return attached();
     
    795802
    796803    typedef ListGraphBase Graph;
    797 
    798     class Node;
    799     class Arc;
    800     class Edge;
    801804
    802805    class Node {
     
    848851      bool operator<(const Arc& arc) const {return id < arc.id;}
    849852    };
    850 
    851 
    852853
    853854    ListGraphBase()
     
    11651166  ///A general undirected graph structure.
    11661167
    1167   ///\ref ListGraph is a simple and fast <em>undirected graph</em>
    1168   ///implementation based on static linked lists that are stored in
     1168  ///\ref ListGraph is a versatile and fast undirected graph
     1169  ///implementation based on linked lists that are stored in
    11691170  ///\c std::vector structures.
    11701171  ///
    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
     1172  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
     1173  ///and it also provides several useful additional functionalities.
     1174  ///Most of its member functions and nested classes are documented
    11741175  ///only in the concept class.
    11751176  ///
    11761177  ///\sa concepts::Graph
    1177 
     1178  ///\sa ListDigraph
    11781179  class ListGraph : public ExtendedListGraphBase {
    11791180    typedef ExtendedListGraphBase Parent;
    11801181
    11811182  private:
    1182     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1183 
    1184     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1185     ///
     1183    /// Graphs are \e not copy constructible. Use GraphCopy instead.
    11861184    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    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.
     1185    /// \brief Assignment of a graph to another one is \e not allowed.
     1186    /// Use GraphCopy instead.
    11921187    void operator=(const ListGraph &) {}
    11931188  public:
     
    12021197    /// \brief Add a new node to the graph.
    12031198    ///
    1204     /// Add a new node to the graph.
     1199    /// This function adds a new node to the graph.
    12051200    /// \return The new node.
    12061201    Node addNode() { return Parent::addNode(); }
     
    12081203    /// \brief Add a new edge to the graph.
    12091204    ///
    1210     /// Add a new edge to the graph with source node \c s
    1211     /// and target node \c t.
     1205    /// This function adds a new edge to the graph between nodes
     1206    /// \c u and \c v with inherent orientation from node \c u to
     1207    /// node \c v.
    12121208    /// \return The new edge.
    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); }
     1209    Edge addEdge(Node u, Node v) {
     1210      return Parent::addEdge(u, v);
     1211    }
     1212
     1213    ///\brief Erase a node from the graph.
     1214    ///
     1215    /// This function erases the given node from the graph.
     1216    void erase(Node n) { Parent::erase(n); }
     1217
     1218    ///\brief Erase an edge from the graph.
     1219    ///
     1220    /// This function erases the given edge from the graph.
     1221    void erase(Edge e) { Parent::erase(e); }
    12281222    /// Node validity check
    12291223
    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
     1224    /// This function gives back \c true if the given node is valid,
     1225    /// i.e. it is a real node of the graph.
     1226    ///
     1227    /// \warning A removed node could become valid again if new nodes are
    12351228    /// added to the graph.
    12361229    bool valid(Node n) const { return Parent::valid(n); }
     1230    /// Edge validity check
     1231
     1232    /// This function gives back \c true if the given edge is valid,
     1233    /// i.e. it is a real edge of the graph.
     1234    ///
     1235    /// \warning A removed edge could become valid again if new edges are
     1236    /// added to the graph.
     1237    bool valid(Edge e) const { return Parent::valid(e); }
    12371238    /// Arc validity check
    12381239
    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
     1240    /// This function gives back \c true if the given arc is valid,
     1241    /// i.e. it is a real arc of the graph.
     1242    ///
     1243    /// \warning A removed arc could become valid again if new edges are
    12441244    /// added to the graph.
    12451245    bool valid(Arc a) const { return Parent::valid(a); }
    1246     /// Edge validity check
    1247 
    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
    1253     /// added to the graph.
    1254     bool valid(Edge e) const { return Parent::valid(e); }
    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.
     1246
     1247    /// \brief Change the first node of an edge.
     1248    ///
     1249    /// This function changes the first node of the given edge \c e to \c n.
     1250    ///
     1251    ///\note \c EdgeIt and \c ArcIt iterators referencing the
     1252    ///changed edge are invalidated and all other iterators whose
     1253    ///base node is the changed node are also invalidated.
    12631254    ///
    12641255    ///\warning This functionality cannot be used together with the
     
    12671258      Parent::changeU(e,n);
    12681259    }
    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.
     1260    /// \brief Change the second node of an edge.
     1261    ///
     1262    /// This function changes the second node of the given edge \c e to \c n.
     1263    ///
     1264    ///\note \c EdgeIt iterators referencing the changed edge remain
     1265    ///valid, however \c ArcIt iterators referencing the changed edge and
     1266    ///all other iterators whose base node is the changed node are also
     1267    ///invalidated.
    12761268    ///
    12771269    ///\warning This functionality cannot be used together with the
     
    12801272      Parent::changeV(e,n);
    12811273    }
     1274
    12821275    /// \brief Contract two nodes.
    12831276    ///
    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.
     1277    /// This function contracts the given two nodes.
     1278    /// Node \c b is removed, but instead of deleting
     1279    /// its incident edges, they are joined to node \c a.
     1280    /// If the last parameter \c r is \c true (this is the default value),
     1281    /// then the newly created loops are removed.
     1282    ///
     1283    /// \note The moved edges are joined to node \c a using changeU()
     1284    /// or changeV(), thus all edge and arc iterators whose base node is
     1285    /// \c b are invalidated.
     1286    /// Moreover all iterators referencing node \c b or the removed
     1287    /// loops are also invalidated. Other iterators remain valid.
    12921288    ///
    12931289    ///\warning This functionality cannot be used together with the
     
    13081304    }
    13091305
     1306    ///Clear the graph.
     1307
     1308    ///This function erases all nodes and arcs from the graph.
     1309    ///
     1310    void clear() {
     1311      Parent::clear();
     1312    }
    13101313
    13111314    /// \brief Class to make a snapshot of the graph and restore
     
    13171320    /// using the restore() function.
    13181321    ///
    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.
     1322    /// \note After a state is restored, you cannot restore a later state,
     1323    /// i.e. you cannot add the removed nodes and edges again using
     1324    /// another Snapshot instance.
     1325    ///
     1326    /// \warning Node and edge deletions and other modifications
     1327    /// (e.g. changing the end-nodes of edges or contracting nodes)
     1328    /// cannot be restored. These events invalidate the snapshot.
     1329    /// However the edges and nodes that were added to the graph after
     1330    /// making the current snapshot can be removed without invalidating it.
    13221331    class Snapshot {
    13231332    protected:
     
    14891498      ///
    14901499      /// Default constructor.
    1491       /// To actually make a snapshot you must call save().
     1500      /// You have to call save() to actually make a snapshot.
    14921501      Snapshot()
    14931502        : graph(0), node_observer_proxy(*this),
     
    14961505      /// \brief Constructor that immediately makes a snapshot.
    14971506      ///
    1498       /// This constructor immediately makes a snapshot of the graph.
    1499       /// \param _graph The graph we make a snapshot of.
    1500       Snapshot(ListGraph &_graph)
     1507      /// This constructor immediately makes a snapshot of the given graph.
     1508      Snapshot(ListGraph &gr)
    15011509        : node_observer_proxy(*this),
    15021510          edge_observer_proxy(*this) {
    1503         attach(_graph);
     1511        attach(gr);
    15041512      }
    15051513
    15061514      /// \brief Make a snapshot.
    15071515      ///
    1508       /// Make a snapshot of the graph.
    1509       ///
    1510       /// This function can be called more than once. In case of a repeated
     1516      /// This function makes a snapshot of the given graph.
     1517      /// It can be called more than once. In case of a repeated
    15111518      /// call, the previous snapshot gets lost.
    1512       /// \param _graph The graph we make the snapshot of.
    1513       void save(ListGraph &_graph) {
     1519      void save(ListGraph &gr) {
    15141520        if (attached()) {
    15151521          detach();
    15161522          clear();
    15171523        }
    1518         attach(_graph);
     1524        attach(gr);
    15191525      }
    15201526
    15211527      /// \brief Undo the changes until the last snapshot.
    1522       //
    1523       /// Undo the changes until the last snapshot created by save().
     1528      ///
     1529      /// This function undos the changes until the last snapshot
     1530      /// created by save() or Snapshot(ListGraph&).
    15241531      void restore() {
    15251532        detach();
     
    15351542      }
    15361543
    1537       /// \brief Gives back true when the snapshot is valid.
     1544      /// \brief Returns \c true if the snapshot is valid.
    15381545      ///
    1539       /// Gives back true when the snapshot is valid.
     1546      /// This function returns \c true if the snapshot is valid.
    15401547      bool valid() const {
    15411548        return attached();
  • lemon/smart_graph.h

    r617 r735  
    3333
    3434  class SmartDigraph;
    35   ///Base of SmartDigraph
    36 
    37   ///Base of SmartDigraph
    38   ///
     35
    3936  class SmartDigraphBase {
    4037  protected:
     
    188185  ///\brief A smart directed graph class.
    189186  ///
    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".
     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).
    195191  ///
    196   ///\sa concepts::Digraph.
     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
    197199  class SmartDigraph : public ExtendedSmartDigraphBase {
    198200    typedef ExtendedSmartDigraphBase Parent;
    199201
    200202  private:
    201 
    202     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
    203 
    204     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
    205     ///
     203    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
    206204    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
    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.
     205    /// \brief Assignment of a digraph to another one is \e not allowed.
     206    /// Use DigraphCopy instead.
    212207    void operator=(const SmartDigraph &) {}
    213208
     
    222217    ///Add a new node to the digraph.
    223218
    224     /// Add a new node to the digraph.
    225     /// \return The new node.
     219    ///This function adds a new node to the digraph.
     220    ///\return The new node.
    226221    Node addNode() { return Parent::addNode(); }
    227222
    228223    ///Add a new arc to the digraph.
    229224
    230     ///Add a new arc to the digraph with source node \c s
     225    ///This function adds a new arc to the digraph with source node \c s
    231226    ///and target node \c t.
    232227    ///\return The new arc.
    233     Arc addArc(const Node& s, const Node& t) {
     228    Arc addArc(Node s, Node t) {
    234229      return Parent::addArc(s, t);
    235230    }
    236231
    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 
    259232    /// \brief Node validity check
    260233    ///
    261     /// This function gives back true if the given node is valid,
    262     /// ie. it is a real node of the graph.
     234    /// This function gives back \c true if the given node is valid,
     235    /// i.e. it is a real node of the digraph.
    263236    ///
    264237    /// \warning A removed node (using Snapshot) could become valid again
    265     /// when new nodes are added to the graph.
     238    /// if new nodes are added to the digraph.
    266239    bool valid(Node n) const { return Parent::valid(n); }
    267240
    268241    /// \brief Arc validity check
    269242    ///
    270     /// This function gives back true if the given arc is valid,
    271     /// ie. it is a real arc of the graph.
     243    /// This function gives back \c true if the given arc is valid,
     244    /// i.e. it is a real arc of the digraph.
    272245    ///
    273246    /// \warning A removed arc (using Snapshot) could become valid again
    274     /// when new arcs are added to the graph.
     247    /// if new arcs are added to the graph.
    275248    bool valid(Arc a) const { return Parent::valid(a); }
    276249
    277     ///Clear the digraph.
    278 
    279     ///Erase all the nodes and arcs from the digraph.
    280     ///
    281     void clear() {
    282       Parent::clear();
    283     }
    284 
    285250    ///Split a node.
    286251
    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.
     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.
    291258    ///\return The newly created node.
    292259    ///
    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.
     260    ///\note All iterators remain valid.
     261    ///
    297262    ///\warning This functionality cannot be used together with the Snapshot
    298263    ///feature.
     
    309274    }
    310275
     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
    311304  public:
    312305
     
    333326  public:
    334327
    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.
     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.
    338331    ///
    339332    ///The newly added nodes and arcs can be removed using the
    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.
     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.
    349345    class Snapshot
    350346    {
     
    358354
    359355      ///Default constructor.
    360       ///To actually make a snapshot you must call save().
    361       ///
     356      ///You have to call save() to actually make a snapshot.
    362357      Snapshot() : _graph(0) {}
    363358      ///Constructor that immediately makes a snapshot
    364359
    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) {
     360      ///This constructor immediately makes a snapshot of the given digraph.
     361      ///
     362      Snapshot(SmartDigraph &gr) : _graph(&gr) {
    368363        node_num=_graph->nodes.size();
    369364        arc_num=_graph->arcs.size();
     
    372367      ///Make a snapshot.
    373368
    374       ///Make a snapshot of the digraph.
    375       ///
    376       ///This function can be called more than once. In case of a repeated
     369      ///This function makes a snapshot of the given digraph.
     370      ///It can be called more than once. In case of a repeated
    377371      ///call, the previous snapshot gets lost.
    378       ///\param graph The digraph we make the snapshot of.
    379       void save(SmartDigraph &graph)
    380       {
    381         _graph=&graph;
     372      void save(SmartDigraph &gr) {
     373        _graph=&gr;
    382374        node_num=_graph->nodes.size();
    383375        arc_num=_graph->arcs.size();
     
    386378      ///Undo the changes until a snapshot.
    387379
    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().
     380      ///This function undos the changes until the last snapshot
     381      ///created by save() or Snapshot(SmartDigraph&).
    393382      void restore()
    394383      {
     
    622611  /// \brief A smart undirected graph class.
    623612  ///
    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".
     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).
    629617  ///
    630   /// \sa concepts::Graph.
     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
    631625  class SmartGraph : public ExtendedSmartGraphBase {
    632626    typedef ExtendedSmartGraphBase Parent;
    633627
    634628  private:
    635 
    636     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
    637 
    638     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
    639     ///
     629    /// Graphs are \e not copy constructible. Use GraphCopy instead.
    640630    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
    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.
     631    /// \brief Assignment of a graph to another one is \e not allowed.
     632    /// Use GraphCopy instead.
    647633    void operator=(const SmartGraph &) {}
    648634
     
    655641    SmartGraph() {}
    656642
    657     ///Add a new node to the graph.
    658 
    659     /// Add a new node to the graph.
     643    /// \brief Add a new node to the graph.
     644    ///
     645    /// This function adds a new node to the graph.
    660646    /// \return The new node.
    661647    Node addNode() { return Parent::addNode(); }
    662648
    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);
     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);
    670657    }
    671658
    672659    /// \brief Node validity check
    673660    ///
    674     /// This function gives back true if the given node is valid,
    675     /// ie. it is a real node of the graph.
     661    /// This function gives back \c true if the given node is valid,
     662    /// i.e. it is a real node of the graph.
    676663    ///
    677664    /// \warning A removed node (using Snapshot) could become valid again
    678     /// when new nodes are added to the graph.
     665    /// if new nodes are added to the graph.
    679666    bool valid(Node n) const { return Parent::valid(n); }
    680667
     668    /// \brief Edge validity check
     669    ///
     670    /// This function gives back \c true if the given edge is valid,
     671    /// i.e. it is a real edge of the graph.
     672    ///
     673    /// \warning A removed edge (using Snapshot) could become valid again
     674    /// if new edges are added to the graph.
     675    bool valid(Edge e) const { return Parent::valid(e); }
     676
    681677    /// \brief Arc validity check
    682678    ///
    683     /// This function gives back true if the given arc is valid,
    684     /// ie. it is a real arc of the graph.
     679    /// This function gives back \c true if the given arc is valid,
     680    /// i.e. it is a real arc of the graph.
    685681    ///
    686682    /// \warning A removed arc (using Snapshot) could become valid again
    687     /// when new edges are added to the graph.
     683    /// if new edges are added to the graph.
    688684    bool valid(Arc a) const { return Parent::valid(a); }
    689685
    690     /// \brief Edge validity check
    691     ///
    692     /// This function gives back true if the given edge is valid,
    693     /// ie. it is a real edge of the graph.
    694     ///
    695     /// \warning A removed edge (using Snapshot) could become valid again
    696     /// when new edges are added to the graph.
    697     bool valid(Edge e) const { return Parent::valid(e); }
    698 
    699686    ///Clear the graph.
    700687
    701     ///Erase all the nodes and edges from the graph.
     688    ///This function erases all nodes and arcs from the graph.
    702689    ///
    703690    void clear() {
     
    743730  public:
    744731
    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.
     732    ///Class to make a snapshot of the graph and to restore it later.
     733
     734    ///Class to make a snapshot of the graph and to restore it later.
     735    ///
     736    ///The newly added nodes and edges can be removed using the
     737    ///restore() function. This is the only way for deleting nodes and/or
     738    ///edges from a SmartGraph structure.
     739    ///
     740    ///\note After a state is restored, you cannot restore a later state,
     741    ///i.e. you cannot add the removed nodes and edges again using
     742    ///another Snapshot instance.
     743    ///
     744    ///\warning The validity of the snapshot is not stored due to
     745    ///performance reasons. If you do not use the snapshot correctly,
     746    ///it can cause broken program, invalid or not restored state of
     747    ///the graph or no change.
    760748    class Snapshot
    761749    {
     
    769757
    770758      ///Default constructor.
    771       ///To actually make a snapshot you must call save().
    772       ///
     759      ///You have to call save() to actually make a snapshot.
    773760      Snapshot() : _graph(0) {}
    774761      ///Constructor that immediately makes a snapshot
    775762
    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);
     763      /// This constructor immediately makes a snapshot of the given graph.
     764      ///
     765      Snapshot(SmartGraph &gr) {
     766        gr.saveSnapshot(*this);
    780767      }
    781768
    782769      ///Make a snapshot.
    783770
    784       ///Make a snapshot of the graph.
    785       ///
    786       ///This function can be called more than once. In case of a repeated
     771      ///This function makes a snapshot of the given graph.
     772      ///It can be called more than once. In case of a repeated
    787773      ///call, the previous snapshot gets lost.
    788       ///\param graph The digraph we make the snapshot of.
    789       void save(SmartGraph &graph)
     774      void save(SmartGraph &gr)
    790775      {
    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().
     776        gr.saveSnapshot(*this);
     777      }
     778
     779      ///Undo the changes until the last snapshot.
     780
     781      ///This function undos the changes until the last snapshot
     782      ///created by save() or Snapshot(SmartGraph&).
    801783      void restore()
    802784      {
Note: See TracChangeset for help on using the changeset viewer.