lemon/full_graph.h
changeset 750 b7e3662faf02
parent 617 4137ef9aacc6
child 780 580af8cf2f6a
equal deleted inserted replaced
6:2043d91a056f 7:d062c9a90155
    22 #include <lemon/core.h>
    22 #include <lemon/core.h>
    23 #include <lemon/bits/graph_extender.h>
    23 #include <lemon/bits/graph_extender.h>
    24 
    24 
    25 ///\ingroup graphs
    25 ///\ingroup graphs
    26 ///\file
    26 ///\file
    27 ///\brief FullGraph and FullDigraph classes.
    27 ///\brief FullDigraph and FullGraph classes.
    28 
    28 
    29 namespace lemon {
    29 namespace lemon {
    30 
    30 
    31   class FullDigraphBase {
    31   class FullDigraphBase {
    32   public:
    32   public:
   146 
   146 
   147   typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
   147   typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
   148 
   148 
   149   /// \ingroup graphs
   149   /// \ingroup graphs
   150   ///
   150   ///
   151   /// \brief A full digraph class.
   151   /// \brief A directed full graph class.
   152   ///
   152   ///
   153   /// This is a simple and fast directed full graph implementation.
   153   /// FullDigraph is a simple and fast implmenetation of directed full
   154   /// From each node go arcs to each node (including the source node),
   154   /// (complete) graphs. It contains an arc from each node to each node
   155   /// therefore the number of the arcs in the digraph is the square of
   155   /// (including a loop for each node), therefore the number of arcs
   156   /// the node number. This digraph type is completely static, so you
   156   /// is the square of the number of nodes.
   157   /// can neither add nor delete either arcs or nodes, and it needs
   157   /// This class is completely static and it needs constant memory space.
   158   /// constant space in memory.
   158   /// Thus you can neither add nor delete nodes or arcs, however
   159   ///
   159   /// the structure can be resized using resize().
   160   /// This class fully conforms to the \ref concepts::Digraph
   160   ///
   161   /// "Digraph concept".
   161   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
   162   ///
   162   /// Most of its member functions and nested classes are documented
   163   /// The \c FullDigraph and \c FullGraph classes are very similar,
   163   /// only in the concept class.
       
   164   ///
       
   165   /// \note FullDigraph and FullGraph classes are very similar,
   164   /// but there are two differences. While this class conforms only
   166   /// but there are two differences. While this class conforms only
   165   /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
   167   /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
   166   /// class conforms to the \ref concepts::Graph "Graph" concept,
   168   /// conforms to the \ref concepts::Graph "Graph" concept,
   167   /// moreover \c FullGraph does not contain a loop arc for each
   169   /// moreover FullGraph does not contain a loop for each
   168   /// node as \c FullDigraph does.
   170   /// node as this class does.
   169   ///
   171   ///
   170   /// \sa FullGraph
   172   /// \sa FullGraph
   171   class FullDigraph : public ExtendedFullDigraphBase {
   173   class FullDigraph : public ExtendedFullDigraphBase {
   172     typedef ExtendedFullDigraphBase Parent;
   174     typedef ExtendedFullDigraphBase Parent;
   173 
   175 
   174   public:
   176   public:
   175 
   177 
   176     /// \brief Constructor
   178     /// \brief Default constructor.
       
   179     ///
       
   180     /// Default constructor. The number of nodes and arcs will be zero.
   177     FullDigraph() { construct(0); }
   181     FullDigraph() { construct(0); }
   178 
   182 
   179     /// \brief Constructor
   183     /// \brief Constructor
   180     ///
   184     ///
   181     /// Constructor.
   185     /// Constructor.
   182     /// \param n The number of the nodes.
   186     /// \param n The number of the nodes.
   183     FullDigraph(int n) { construct(n); }
   187     FullDigraph(int n) { construct(n); }
   184 
   188 
   185     /// \brief Resizes the digraph
   189     /// \brief Resizes the digraph
   186     ///
   190     ///
   187     /// Resizes the digraph. The function will fully destroy and
   191     /// This function resizes the digraph. It fully destroys and
   188     /// rebuild the digraph. This cause that the maps of the digraph will
   192     /// rebuilds the structure, therefore the maps of the digraph will be
   189     /// reallocated automatically and the previous values will be lost.
   193     /// reallocated automatically and the previous values will be lost.
   190     void resize(int n) {
   194     void resize(int n) {
   191       Parent::notifier(Arc()).clear();
   195       Parent::notifier(Arc()).clear();
   192       Parent::notifier(Node()).clear();
   196       Parent::notifier(Node()).clear();
   193       construct(n);
   197       construct(n);
   195       Parent::notifier(Arc()).build();
   199       Parent::notifier(Arc()).build();
   196     }
   200     }
   197 
   201 
   198     /// \brief Returns the node with the given index.
   202     /// \brief Returns the node with the given index.
   199     ///
   203     ///
   200     /// Returns the node with the given index. Since it is a static
   204     /// Returns the node with the given index. Since this structure is 
   201     /// digraph its nodes can be indexed with integers from the range
   205     /// completely static, the nodes can be indexed with integers from
   202     /// <tt>[0..nodeNum()-1]</tt>.
   206     /// the range <tt>[0..nodeNum()-1]</tt>.
   203     /// \sa index()
   207     /// \sa index()
   204     Node operator()(int ix) const { return Parent::operator()(ix); }
   208     Node operator()(int ix) const { return Parent::operator()(ix); }
   205 
   209 
   206     /// \brief Returns the index of the given node.
   210     /// \brief Returns the index of the given node.
   207     ///
   211     ///
   208     /// Returns the index of the given node. Since it is a static
   212     /// Returns the index of the given node. Since this structure is 
   209     /// digraph its nodes can be indexed with integers from the range
   213     /// completely static, the nodes can be indexed with integers from
   210     /// <tt>[0..nodeNum()-1]</tt>.
   214     /// the range <tt>[0..nodeNum()-1]</tt>.
   211     /// \sa operator()
   215     /// \sa operator()()
   212     int index(const Node& node) const { return Parent::index(node); }
   216     int index(Node node) const { return Parent::index(node); }
   213 
   217 
   214     /// \brief Returns the arc connecting the given nodes.
   218     /// \brief Returns the arc connecting the given nodes.
   215     ///
   219     ///
   216     /// Returns the arc connecting the given nodes.
   220     /// 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 {
   218       return Parent::arc(u, v);
   222       return Parent::arc(u, v);
   219     }
   223     }
   220 
   224 
   221     /// \brief Number of nodes.
   225     /// \brief Number of nodes.
   222     int nodeNum() const { return Parent::nodeNum(); }
   226     int nodeNum() const { return Parent::nodeNum(); }
   518 
   522 
   519   /// \ingroup graphs
   523   /// \ingroup graphs
   520   ///
   524   ///
   521   /// \brief An undirected full graph class.
   525   /// \brief An undirected full graph class.
   522   ///
   526   ///
   523   /// This is a simple and fast undirected full graph
   527   /// FullGraph is a simple and fast implmenetation of undirected full
   524   /// implementation. From each node go edge to each other node,
   528   /// (complete) graphs. It contains an edge between every distinct pair
   525   /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
   529   /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
   526   /// This graph type is completely static, so you can neither
   530   /// This class is completely static and it needs constant memory space.
   527   /// add nor delete either edges or nodes, and it needs constant
   531   /// Thus you can neither add nor delete nodes or edges, however
   528   /// space in memory.
   532   /// the structure can be resized using resize().
   529   ///
   533   ///
   530   /// This class fully conforms to the \ref concepts::Graph "Graph concept".
   534   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   531   ///
   535   /// Most of its member functions and nested classes are documented
   532   /// The \c FullGraph and \c FullDigraph classes are very similar,
   536   /// only in the concept class.
   533   /// but there are two differences. While the \c FullDigraph class
   537   ///
       
   538   /// \note FullDigraph and FullGraph classes are very similar,
       
   539   /// but there are two differences. While FullDigraph
   534   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   540   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   535   /// this class conforms to the \ref concepts::Graph "Graph" concept,
   541   /// this class conforms to the \ref concepts::Graph "Graph" concept,
   536   /// moreover \c FullGraph does not contain a loop arc for each
   542   /// moreover this class does not contain a loop for each
   537   /// node as \c FullDigraph does.
   543   /// node as FullDigraph does.
   538   ///
   544   ///
   539   /// \sa FullDigraph
   545   /// \sa FullDigraph
   540   class FullGraph : public ExtendedFullGraphBase {
   546   class FullGraph : public ExtendedFullGraphBase {
   541     typedef ExtendedFullGraphBase Parent;
   547     typedef ExtendedFullGraphBase Parent;
   542 
   548 
   543   public:
   549   public:
   544 
   550 
   545     /// \brief Constructor
   551     /// \brief Default constructor.
       
   552     ///
       
   553     /// Default constructor. The number of nodes and edges will be zero.
   546     FullGraph() { construct(0); }
   554     FullGraph() { construct(0); }
   547 
   555 
   548     /// \brief Constructor
   556     /// \brief Constructor
   549     ///
   557     ///
   550     /// Constructor.
   558     /// Constructor.
   551     /// \param n The number of the nodes.
   559     /// \param n The number of the nodes.
   552     FullGraph(int n) { construct(n); }
   560     FullGraph(int n) { construct(n); }
   553 
   561 
   554     /// \brief Resizes the graph
   562     /// \brief Resizes the graph
   555     ///
   563     ///
   556     /// Resizes the graph. The function will fully destroy and
   564     /// This function resizes the graph. It fully destroys and
   557     /// rebuild the graph. This cause that the maps of the graph will
   565     /// rebuilds the structure, therefore the maps of the graph will be
   558     /// reallocated automatically and the previous values will be lost.
   566     /// reallocated automatically and the previous values will be lost.
   559     void resize(int n) {
   567     void resize(int n) {
   560       Parent::notifier(Arc()).clear();
   568       Parent::notifier(Arc()).clear();
   561       Parent::notifier(Edge()).clear();
   569       Parent::notifier(Edge()).clear();
   562       Parent::notifier(Node()).clear();
   570       Parent::notifier(Node()).clear();
   566       Parent::notifier(Arc()).build();
   574       Parent::notifier(Arc()).build();
   567     }
   575     }
   568 
   576 
   569     /// \brief Returns the node with the given index.
   577     /// \brief Returns the node with the given index.
   570     ///
   578     ///
   571     /// Returns the node with the given index. Since it is a static
   579     /// Returns the node with the given index. Since this structure is 
   572     /// graph its nodes can be indexed with integers from the range
   580     /// completely static, the nodes can be indexed with integers from
   573     /// <tt>[0..nodeNum()-1]</tt>.
   581     /// the range <tt>[0..nodeNum()-1]</tt>.
   574     /// \sa index()
   582     /// \sa index()
   575     Node operator()(int ix) const { return Parent::operator()(ix); }
   583     Node operator()(int ix) const { return Parent::operator()(ix); }
   576 
   584 
   577     /// \brief Returns the index of the given node.
   585     /// \brief Returns the index of the given node.
   578     ///
   586     ///
   579     /// Returns the index of the given node. Since it is a static
   587     /// Returns the index of the given node. Since this structure is 
   580     /// graph its nodes can be indexed with integers from the range
   588     /// completely static, the nodes can be indexed with integers from
   581     /// <tt>[0..nodeNum()-1]</tt>.
   589     /// the range <tt>[0..nodeNum()-1]</tt>.
   582     /// \sa operator()
   590     /// \sa operator()()
   583     int index(const Node& node) const { return Parent::index(node); }
   591     int index(Node node) const { return Parent::index(node); }
   584 
   592 
   585     /// \brief Returns the arc connecting the given nodes.
   593     /// \brief Returns the arc connecting the given nodes.
   586     ///
   594     ///
   587     /// Returns the arc connecting the given nodes.
   595     /// 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 {
   589       return Parent::arc(s, t);
   597       return Parent::arc(s, t);
   590     }
   598     }
   591 
   599 
   592     /// \brief Returns the edge connects the given nodes.
   600     /// \brief Returns the edge connecting the given nodes.
   593     ///
   601     ///
   594     /// Returns the edge connects the given nodes.
   602     /// Returns the edge connecting the given nodes.
   595     Edge edge(const Node& u, const Node& v) const {
   603     Edge edge(Node u, Node v) const {
   596       return Parent::edge(u, v);
   604       return Parent::edge(u, v);
   597     }
   605     }
   598 
   606 
   599     /// \brief Number of nodes.
   607     /// \brief Number of nodes.
   600     int nodeNum() const { return Parent::nodeNum(); }
   608     int nodeNum() const { return Parent::nodeNum(); }