HypercubeGraph Class Reference

Detailed Description

HypercubeGraph implements a special graph type. The nodes of the graph are indexed with integers having at most dim binary digits. Two nodes are connected in the graph if and only if their indices differ only on one position in the binary form. This class is completely static and it needs constant memory space. Thus you can neither add nor delete nodes or edges, however, the structure can be resized using resize().

This type fully conforms to the Graph concept. Most of its member functions and nested classes are documented only in the concept class.

This class provides constant time counting for nodes, edges and arcs.

Note

The type of the indices is chosen to int for efficiency reasons. Thus the maximum dimension of this implementation is 26 (assuming that the size of int is 32 bit).

#include <lemon/hypercube_graph.h>

Inherits GraphExtender< Base >.

Classes
class	HyperMap
	Linear combination map. More...

Public Member Functions
	HypercubeGraph (int dim)
	Constructs a hypercube graph with dim dimensions. More...
void	resize (int dim)
	Resizes the graph. More...
int	dimension () const
	The number of dimensions. More...
bool	projection (Node node, int n) const
	Returns true if the n'th bit of the node is one. More...
int	dimension (Edge edge) const
	The dimension id of an edge. More...
int	dimension (Arc arc) const
	The dimension id of an arc. More...
Node	operator() (int ix) const
	Gives back a node by its index. More...
int	nodeNum () const
	Number of nodes.
int	edgeNum () const
	Number of edges.
int	arcNum () const
	Number of arcs.

Static Public Member Functions
static int	index (Node node)
	The index of a node. More...

Constructor & Destructor Documentation

HypercubeGraph ( int  dim )

inline

Constructs a hypercube graph with dim dimensions.

Member Function Documentation

void resize ( int  dim )

inline

This function resizes the graph. It fully destroys and rebuilds the structure, therefore the maps of the graph will be reallocated automatically and the previous values will be lost.

int dimension ( ) const

inline

Gives back the number of dimensions.

bool projection ( Node  node, int  n  ) const

inline

Returns true if the n'th bit of the node is one.

int dimension ( Edge  edge ) const

inline

Gives back the dimension id of the given edge. It is in the range [0..dim-1].

int dimension ( Arc  arc ) const

inline

Gives back the dimension id of the given arc. It is in the range [0..dim-1].

static int index ( Node  node )

inlinestatic

Gives back the index of the given node. The lower bits of the integer describes the node.

Node operator() ( int  ix ) const

inline

Gives back a node by its index.