lemon/hypercube_graph.h
changeset 789 8ddb7deabab9
parent 778 a143f19f465b
parent 737 9d6c3e8b2421
child 787 c2230649a493
equal deleted inserted replaced
9:a7996e653bdb 10:7cf92a7cfe88
   280 
   280 
   281   /// \ingroup graphs
   281   /// \ingroup graphs
   282   ///
   282   ///
   283   /// \brief Hypercube graph class
   283   /// \brief Hypercube graph class
   284   ///
   284   ///
   285   /// This class implements a special graph type. The nodes of the graph
   285   /// HypercubeGraph implements a special graph type. The nodes of the
   286   /// are indiced with integers with at most \c dim binary digits.
   286   /// graph are indexed with integers having at most \c dim binary digits.
   287   /// Two nodes are connected in the graph if and only if their indices
   287   /// Two nodes are connected in the graph if and only if their indices
   288   /// differ only on one position in the binary form.
   288   /// differ only on one position in the binary form.
       
   289   /// This class is completely static and it needs constant memory space.
       
   290   /// Thus you can neither add nor delete nodes or edges, however 
       
   291   /// the structure can be resized using resize().
       
   292   ///
       
   293   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
       
   294   /// Most of its member functions and nested classes are documented
       
   295   /// only in the concept class.
   289   ///
   296   ///
   290   /// \note The type of the indices is chosen to \c int for efficiency
   297   /// \note The type of the indices is chosen to \c int for efficiency
   291   /// reasons. Thus the maximum dimension of this implementation is 26
   298   /// reasons. Thus the maximum dimension of this implementation is 26
   292   /// (assuming that the size of \c int is 32 bit).
   299   /// (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".
       
   296   class HypercubeGraph : public ExtendedHypercubeGraphBase {
   300   class HypercubeGraph : public ExtendedHypercubeGraphBase {
   297     typedef ExtendedHypercubeGraphBase Parent;
   301     typedef ExtendedHypercubeGraphBase Parent;
   298 
   302 
   299   public:
   303   public:
   300 
   304 
   301     /// \brief Constructs a hypercube graph with \c dim dimensions.
   305     /// \brief Constructs a hypercube graph with \c dim dimensions.
   302     ///
   306     ///
   303     /// Constructs a hypercube graph with \c dim dimensions.
   307     /// Constructs a hypercube graph with \c dim dimensions.
   304     HypercubeGraph(int dim) { construct(dim); }
   308     HypercubeGraph(int dim) { construct(dim); }
       
   309 
       
   310     /// \brief Resizes the graph
       
   311     ///
       
   312     /// This function resizes the graph. It fully destroys and
       
   313     /// rebuilds the structure, therefore the maps of the graph will be
       
   314     /// reallocated automatically and the previous values will be lost.
       
   315     void resize(int dim) {
       
   316       Parent::notifier(Arc()).clear();
       
   317       Parent::notifier(Edge()).clear();
       
   318       Parent::notifier(Node()).clear();
       
   319       construct(dim);
       
   320       Parent::notifier(Node()).build();
       
   321       Parent::notifier(Edge()).build();
       
   322       Parent::notifier(Arc()).build();
       
   323     }
   305 
   324 
   306     /// \brief The number of dimensions.
   325     /// \brief The number of dimensions.
   307     ///
   326     ///
   308     /// Gives back the number of dimensions.
   327     /// Gives back the number of dimensions.
   309     int dimension() const {
   328     int dimension() const {
   318     }
   337     }
   319 
   338 
   320     /// \brief The dimension id of an edge.
   339     /// \brief The dimension id of an edge.
   321     ///
   340     ///
   322     /// Gives back the dimension id of the given edge.
   341     /// Gives back the dimension id of the given edge.
   323     /// It is in the [0..dim-1] range.
   342     /// It is in the range <tt>[0..dim-1]</tt>.
   324     int dimension(Edge edge) const {
   343     int dimension(Edge edge) const {
   325       return Parent::dimension(edge);
   344       return Parent::dimension(edge);
   326     }
   345     }
   327 
   346 
   328     /// \brief The dimension id of an arc.
   347     /// \brief The dimension id of an arc.
   329     ///
   348     ///
   330     /// Gives back the dimension id of the given arc.
   349     /// Gives back the dimension id of the given arc.
   331     /// It is in the [0..dim-1] range.
   350     /// It is in the range <tt>[0..dim-1]</tt>.
   332     int dimension(Arc arc) const {
   351     int dimension(Arc arc) const {
   333       return Parent::dimension(arc);
   352       return Parent::dimension(arc);
   334     }
   353     }
   335 
   354 
   336     /// \brief The index of a node.
   355     /// \brief The index of a node.