Improvements related to full graphs (#57)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 01 Nov 2008 19:22:18 +0100
changeset 35480a4d0742e98
parent 353 37557a46e298
child 355 aa75d24ba7d0
Improvements related to full graphs (#57)
lemon/full_graph.h
test/digraph_test.cc
     1.1 --- a/lemon/full_graph.h	Thu Aug 14 21:49:39 2008 +0200
     1.2 +++ b/lemon/full_graph.h	Sat Nov 01 19:22:18 2008 +0100
     1.3 @@ -19,14 +19,13 @@
     1.4  #ifndef LEMON_FULL_GRAPH_H
     1.5  #define LEMON_FULL_GRAPH_H
     1.6  
     1.7 -#include <lemon/math.h>
     1.8 -
     1.9  #include <lemon/core.h>
    1.10  #include <lemon/bits/graph_extender.h>
    1.11  
    1.12  ///\ingroup graphs
    1.13  ///\file
    1.14 -///\brief FullDigraph and FullGraph classes.
    1.15 +///\brief FullGraph and FullDigraph classes.
    1.16 +
    1.17  namespace lemon {
    1.18  
    1.19    class FullDigraphBase {
    1.20 @@ -67,12 +66,10 @@
    1.21      Node source(Arc arc) const { return arc._id / _node_num; }
    1.22      Node target(Arc arc) const { return arc._id % _node_num; }
    1.23  
    1.24 -
    1.25      static int id(Node node) { return node._id; }
    1.26      static int id(Arc arc) { return arc._id; }
    1.27  
    1.28      static Node nodeFromId(int id) { return Node(id);}
    1.29 -
    1.30      static Arc arcFromId(int id) { return Arc(id);}
    1.31  
    1.32      typedef True FindArcTag;
    1.33 @@ -81,7 +78,6 @@
    1.34        return prev != INVALID ? arc(s, t) : INVALID;
    1.35      }
    1.36  
    1.37 -
    1.38      class Node {
    1.39        friend class FullDigraphBase;
    1.40  
    1.41 @@ -157,14 +153,20 @@
    1.42    /// This is a simple and fast directed full graph implementation.
    1.43    /// From each node go arcs to each node (including the source node),
    1.44    /// therefore the number of the arcs in the digraph is the square of
    1.45 -  /// the node number. The digraph is completely static, so you can
    1.46 -  /// neither add nor delete either arcs or nodes, and it needs just
    1.47 +  /// the node number. This digraph type is completely static, so you
    1.48 +  /// can neither add nor delete either arcs or nodes, and it needs
    1.49    /// constant space in memory.
    1.50    ///
    1.51 -  /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
    1.52 +  /// This class conforms to the \ref concepts::Digraph "Digraph" concept
    1.53    /// and it also has an important extra feature that its maps are
    1.54    /// real \ref concepts::ReferenceMap "reference map"s.
    1.55 -  /// \sa concepts::Digraph.
    1.56 +  ///
    1.57 +  /// The \c FullDigraph and \c FullGraph classes are very similar,
    1.58 +  /// but there are two differences. While this class conforms only
    1.59 +  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
    1.60 +  /// class conforms to the \ref concepts::Graph "Graph" concept,
    1.61 +  /// moreover \c FullGraph does not contain a loop arc for each
    1.62 +  /// node as \c FullDigraph does.
    1.63    ///
    1.64    /// \sa FullGraph
    1.65    class FullDigraph : public ExtendedFullDigraphBase {
    1.66 @@ -177,15 +179,15 @@
    1.67  
    1.68      /// \brief Constructor
    1.69      ///
    1.70 +    /// Constructor.
    1.71      /// \param n The number of the nodes.
    1.72      FullDigraph(int n) { construct(n); }
    1.73  
    1.74 -    /// \brief Resize the digraph
    1.75 +    /// \brief Resizes the digraph
    1.76      ///
    1.77 -    /// Resize the digraph. The function will fully destroy and
    1.78 -    /// rebuild the digraph.  This cause that the maps of the digraph
    1.79 -    /// will reallocated automatically and the previous values will be
    1.80 -    /// lost.
    1.81 +    /// Resizes the digraph. The function will fully destroy and
    1.82 +    /// rebuild the digraph. This cause that the maps of the digraph will
    1.83 +    /// reallocated automatically and the previous values will be lost.
    1.84      void resize(int n) {
    1.85        Parent::notifier(Arc()).clear();
    1.86        Parent::notifier(Node()).clear();
    1.87 @@ -196,23 +198,23 @@
    1.88  
    1.89      /// \brief Returns the node with the given index.
    1.90      ///
    1.91 -    /// Returns the node with the given index. Because it is a
    1.92 -    /// static size digraph the node's of the digraph can be indexed
    1.93 -    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
    1.94 -    /// the node can accessed by the \e index() member.
    1.95 +    /// Returns the node with the given index. Since it is a static
    1.96 +    /// digraph its nodes can be indexed with integers from the range
    1.97 +    /// <tt>[0..nodeNum()-1]</tt>.
    1.98 +    /// \sa index()
    1.99      Node operator()(int ix) const { return Parent::operator()(ix); }
   1.100  
   1.101 -    /// \brief Returns the index of the node.
   1.102 +    /// \brief Returns the index of the given node.
   1.103      ///
   1.104 -    /// Returns the index of the node. Because it is a
   1.105 -    /// static size digraph the node's of the digraph can be indexed
   1.106 -    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
   1.107 -    /// the node can accessed by the \e index() member.
   1.108 +    /// Returns the index of the given node. Since it is a static
   1.109 +    /// digraph its nodes can be indexed with integers from the range
   1.110 +    /// <tt>[0..nodeNum()-1]</tt>.
   1.111 +    /// \sa operator()
   1.112      int index(const Node& node) const { return Parent::index(node); }
   1.113  
   1.114 -    /// \brief Returns the arc connects the given nodes.
   1.115 +    /// \brief Returns the arc connecting the given nodes.
   1.116      ///
   1.117 -    /// Returns the arc connects the given nodes.
   1.118 +    /// Returns the arc connecting the given nodes.
   1.119      Arc arc(const Node& u, const Node& v) const {
   1.120        return Parent::arc(u, v);
   1.121      }
   1.122 @@ -280,7 +282,6 @@
   1.123  
   1.124    public:
   1.125  
   1.126 -
   1.127      Node operator()(int ix) const { return Node(ix); }
   1.128      int index(const Node& node) const { return node._id; }
   1.129  
   1.130 @@ -367,6 +368,7 @@
   1.131  
   1.132      class Edge {
   1.133        friend class FullGraphBase;
   1.134 +      friend class Arc;
   1.135  
   1.136      protected:
   1.137        int _id;
   1.138 @@ -518,20 +520,21 @@
   1.139    ///
   1.140    /// This is a simple and fast undirected full graph
   1.141    /// implementation. From each node go edge to each other node,
   1.142 -  /// therefore the number of edges in the graph is
   1.143 -  /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
   1.144 -  /// add nor delete either edges or nodes, and it needs just constant
   1.145 +  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
   1.146 +  /// This graph type is completely static, so you can neither
   1.147 +  /// add nor delete either edges or nodes, and it needs constant
   1.148    /// space in memory.
   1.149    ///
   1.150 -  /// The \e FullDigraph and \e FullGraph classes are very similar,
   1.151 -  /// but there are two differences. While the \e FullDigraph class is
   1.152 -  /// conform just to the \ref concepts::Digraph "Digraph" concept,
   1.153 -  /// this class is conform to the \ref concepts::Graph "Graph"
   1.154 -  /// concept. In addition, the \e FullGraph class does not contain a
   1.155 -  /// loop arc from each node as the \e FullDigraph does.
   1.156 +  /// This class conforms to the \ref concepts::Graph "Graph" concept
   1.157 +  /// and it also has an important extra feature that its maps are
   1.158 +  /// real \ref concepts::ReferenceMap "reference map"s.
   1.159    ///
   1.160 -  /// It also has an important extra feature that its maps are real
   1.161 -  /// \ref concepts::ReferenceMap "reference map"s.
   1.162 +  /// The \c FullGraph and \c FullDigraph classes are very similar,
   1.163 +  /// but there are two differences. While the \c FullDigraph class
   1.164 +  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   1.165 +  /// this class conforms to the \ref concepts::Graph "Graph" concept,
   1.166 +  /// moreover \c FullGraph does not contain a loop arc for each
   1.167 +  /// node as \c FullDigraph does.
   1.168    ///
   1.169    /// \sa FullDigraph
   1.170    class FullGraph : public ExtendedFullGraphBase {
   1.171 @@ -544,15 +547,15 @@
   1.172  
   1.173      /// \brief Constructor
   1.174      ///
   1.175 +    /// Constructor.
   1.176      /// \param n The number of the nodes.
   1.177      FullGraph(int n) { construct(n); }
   1.178  
   1.179 -    /// \brief Resize the graph
   1.180 +    /// \brief Resizes the graph
   1.181      ///
   1.182 -    /// Resize the graph. The function will fully destroy and rebuild
   1.183 -    /// the graph.  This cause that the maps of the graph will
   1.184 -    /// reallocated automatically and the previous values will be
   1.185 -    /// lost.
   1.186 +    /// Resizes the graph. The function will fully destroy and
   1.187 +    /// rebuild the graph. This cause that the maps of the graph will
   1.188 +    /// reallocated automatically and the previous values will be lost.
   1.189      void resize(int n) {
   1.190        Parent::notifier(Arc()).clear();
   1.191        Parent::notifier(Edge()).clear();
   1.192 @@ -565,30 +568,23 @@
   1.193  
   1.194      /// \brief Returns the node with the given index.
   1.195      ///
   1.196 -    /// Returns the node with the given index. Because it is a static
   1.197 -    /// size graph the node's of the graph can be indexed in the range
   1.198 -    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
   1.199 -    /// accessed by the \e index() member.
   1.200 +    /// Returns the node with the given index. Since it is a static
   1.201 +    /// graph its nodes can be indexed with integers from the range
   1.202 +    /// <tt>[0..nodeNum()-1]</tt>.
   1.203 +    /// \sa index()
   1.204      Node operator()(int ix) const { return Parent::operator()(ix); }
   1.205  
   1.206 -    /// \brief Returns the index of the node.
   1.207 +    /// \brief Returns the index of the given node.
   1.208      ///
   1.209 -    /// Returns the index of the node. Because it is a static size
   1.210 -    /// graph the node's of the graph can be indexed in the range
   1.211 -    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
   1.212 -    /// accessed by the \e index() member.
   1.213 +    /// Returns the index of the given node. Since it is a static
   1.214 +    /// graph its nodes can be indexed with integers from the range
   1.215 +    /// <tt>[0..nodeNum()-1]</tt>.
   1.216 +    /// \sa operator()
   1.217      int index(const Node& node) const { return Parent::index(node); }
   1.218  
   1.219 -    /// \brief Number of nodes.
   1.220 -    int nodeNum() const { return Parent::nodeNum(); }
   1.221 -    /// \brief Number of arcs.
   1.222 -    int arcNum() const { return Parent::arcNum(); }
   1.223 -    /// \brief Number of edges.
   1.224 -    int edgeNum() const { return Parent::edgeNum(); }
   1.225 -
   1.226 -    /// \brief Returns the arc connects the given nodes.
   1.227 +    /// \brief Returns the arc connecting the given nodes.
   1.228      ///
   1.229 -    /// Returns the arc connects the given nodes.
   1.230 +    /// Returns the arc connecting the given nodes.
   1.231      Arc arc(const Node& s, const Node& t) const {
   1.232        return Parent::arc(s, t);
   1.233      }
   1.234 @@ -599,6 +595,14 @@
   1.235      Edge edge(const Node& u, const Node& v) const {
   1.236        return Parent::edge(u, v);
   1.237      }
   1.238 +
   1.239 +    /// \brief Number of nodes.
   1.240 +    int nodeNum() const { return Parent::nodeNum(); }
   1.241 +    /// \brief Number of arcs.
   1.242 +    int arcNum() const { return Parent::arcNum(); }
   1.243 +    /// \brief Number of edges.
   1.244 +    int edgeNum() const { return Parent::edgeNum(); }
   1.245 +
   1.246    };
   1.247  
   1.248  
     2.1 --- a/test/digraph_test.cc	Thu Aug 14 21:49:39 2008 +0200
     2.2 +++ b/test/digraph_test.cc	Sat Nov 01 19:22:18 2008 +0100
     2.3 @@ -142,9 +142,9 @@
     2.4      checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
     2.5      checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
     2.6    }
     2.7 -//  { // Checking FullDigraph
     2.8 -//    checkConcept<Digraph, FullDigraph>();
     2.9 -//  }
    2.10 +  { // Checking FullDigraph
    2.11 +    checkConcept<Digraph, FullDigraph>();
    2.12 +  }
    2.13  //  { // Checking HyperCubeDigraph
    2.14  //    checkConcept<Digraph, HyperCubeDigraph>();
    2.15  //  }