hiperwalk.Hypercube#

hiperwalk.Hypercube(dim, multiedges=None, weights=None)[source]#

Hypercube graph constructor.

The hypercube graph consists of 2**dim vertices. The numerical labels of these vertices are 0, 1, …, 2**dim - 1. Two vertices are adjacent if and only if the corresponding binary tuples differ by only one bit, indicating a Hamming distance of 1.

Parameters:

dimint: The dimension of the hypercube.
multiedges, weights: scipy.sparse.csr_array, default=None: See Graph Constructors.

Returns:

hiperwalk.Graph: See Graph Constructors for details.

See also

Graph Constructors

Notes

A vertex \(v\) in the hypercube is adjacent to all other vertices that have a Hamming distance of 1. To put it differently, \(v\) is adjacent to \(v \oplus 2^0\), \(v \oplus 2^1\), \(\ldots\), \(v \oplus 2^{n - 2}\), and \(v \oplus 2^{n - 1}\). Here, \(\oplus\) represents the bitwise XOR operation, and \(n\) signifies the dimension of the hypercube.

The order of neighbors is determined by the XOR operation. The neighbors of vertex \(u\) are given in the following order: \(u \oplus 2^0\), \(u \oplus 2^1, \ldots,\) \(u \oplus 2^{n - 1}\). For example,

>>> g = hpw.Hypercube(4)
>>> u = 10
>>> bin(u)
'0b1010'
>>> neigh = g.neighbors(u)
>>> neigh
array([11,  8, 14,  2])
>>> [bin(v) for v in neigh]
['0b1011', '0b1000', '0b1110', '0b10']
>>> [u^v for v in neigh]
[1, 2, 4, 8]

Methods#

Besides all methods inherited from hiperwalk.Graph, hiperwalk.Multigraph, or hiperwalk.WeightedGraph, a hypercube instance also has the following method.

dimension(self)

The dimension of the Hypercube.