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. |