HypercubeGraph

Declared in lemon/hypercube_graph.h, in the group Graph Structures; the same class on the Doxygen site.

class HypercubeGraph : public GraphExtender< HypercubeGraphBase >

Hypercube graph class.

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

Public Functions

inline HypercubeGraph( int dim )

Constructs a hypercube graph with dim dimensions.

inline void resize( int dim )

Resizes the graph.

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.

inline int dimension() const

The number of dimensions.

Gives back the number of dimensions.

inline bool projection( Node node , int n ) const

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

inline int dimension( Edge edge ) const

The dimension id of an edge.

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

inline int dimension( Arc arc ) const

The dimension id of an arc.

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

inline Node operator()( int ix ) const

Gives back a node by its index.

inline int nodeNum() const

Number of nodes.

inline int edgeNum() const

Number of edges.

inline int arcNum() const

Number of arcs.

Public Static Functions

static inline int index( Node node )

The index of a node.

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

template< typename T , typename BF = std::plus< T > >
class HyperMap

Linear combination map.

This map makes possible to give back a linear combination for each node. It works like the std::accumulate function, so it accumulates the bf binary function with the fv first value. The map accumulates only on that positions (dimensions) where the index of the node is one. The values that have to be accumulated should be given by the begin and end iterators and the length of this range should be equal to the dimension number of the graph.

const int DIM = 3;
HypercubeGraph graph( DIM );
dim2::Point< double > base[ DIM ];
for( int k = 0 ; k < DIM ; ++k )
{
 base[ k ].x = rnd();
 base[ k ].y = rnd();
 }
HypercubeGraph::HyperMap< dim2::Point< double > >
  pos( graph , base , base + DIM , dim2::Point< double >( 0.0 , 0.0 ) );

See also

HypercubeGraph

Public Types

typedef Node Key

The key type of the map.

typedef T Value

The value type of the map.

Public Functions

template< typename It >
inline HyperMap(
const Graph & graph,
It begin,
It end,
T fv = 0,
const BF & bf = BF()
)

Constructor for HyperMap.

Construct a HyperMap for the given graph. The values that have to be accumulated should be given by the begin and end iterators and the length of this range should be equal to the dimension number of the graph.

This map accumulates the bf binary function with the fv first value on that positions (dimensions) where the index of the node is one.

inline Value operator[]( const Key & k ) const

The partial accumulated value.

Gives back the partial accumulated value.