Skip to content

State and bitmask functions

trivalent.states

Functions:

combine_bits(orient_bits, parity_bits, num_edges)

Combine orientation and parity bitmasks into a single integer.

Parameters:

Name Type Description Default
orient_bits int

Orientation bitmask containing \(|E|\) bits.

required
parity_bits int

Parity bitmask containing \(|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Type Description
uint64

Combined decoration bitmask.

Notes

The combined bitmask is

\[ c = 2^{|E|}d + p, \]

where \(d\) and \(p\) are the orientation and parity bitmasks, respectively.

The parity bits occupy the lowest \(|E|\) positions, followed by the orientation bits.

No graph ID is included in the result.

The input bitmasks are assumed to be non-negative and to fit within \(|E|\) bits.

decode_combined_state(combined_state, num_edges, separate=True)

Decode a combined state into its graph ID and decorations.

Parameters:

Name Type Description Default
combined_state int

Encoded combined state.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required
separate bool

If True, return the orientation and parity bitmasks separately.

If False, return a single combined decoration bitmask.

True

Returns:

Type Description
tuple of numpy.uint64

If separate=True, return (graph_num, orient_bits, parity_bits).

Otherwise, return (graph_num, combined_bits), where

\[ \mathrm{combined\_bits} = 2^{|E|}d + p. \]
Notes

This is the inverse of encode_combined_state() for valid encoded states.

When \(|E|=32\), the graph ID is zero.

decode_orient_state(orient_state, num_edges)

Decode an orientation state into its graph ID and bitmask.

Parameters:

Name Type Description Default
orient_state int

Encoded orientation state.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Name Type Description
graph_num uint64

Graph ID extracted from the encoded state.

orient_bits uint64

Orientation bitmask occupying the lowest \(|E|\) bits.

Notes

This is the inverse of encode_orient_state() for valid encoded states.

When \(|E|=64\), the graph ID is zero.

decode_parity_state(parity_state, num_edges)

Decode a parity state into its graph ID and parity bitmask.

Parameters:

Name Type Description Default
parity_state int

Encoded parity state.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Name Type Description
graph_num uint64

Graph ID extracted from the encoded state.

parity_bits uint64

Parity bitmask occupying the lowest \(|E|\) bits.

Notes

This is the inverse of encode_parity_state() for valid encoded states.

When \(|E|=64\), the graph ID is zero.

encode_combined_bits_state(graph_num, combined_bits, num_edges)

Encode a graph ID and combined decoration bitmask.

Parameters:

Name Type Description Default
graph_num int

Non-negative graph ID supplied by the caller.

required
combined_bits int

Combined orientation and parity bitmask containing \(2|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Type Description
int

Encoded combined state.

Notes

The combined decoration bitmask has the form

\[ c = 2^{|E|}d + p, \]

where \(d\) and \(p\) are orientation and parity bitmasks.

The encoded state is

\[ s_c = 2^{2|E|}g + c. \]

This function is equivalent to separating the decoration bitmasks and calling encode_combined_state().

encode_combined_state(graph_num, orient_bits, parity_bits, num_edges)

Encode a graph ID, orientation bitmask, and parity bitmask.

Parameters:

Name Type Description Default
graph_num int

Non-negative graph ID supplied by the caller.

required
orient_bits int

Orientation bitmask containing \(|E|\) bits.

required
parity_bits int

Parity bitmask containing \(|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Type Description
int

Encoded combined state.

Raises:

Type Description
ValueError

If any input is negative, or the encoded state would exceed 64 bits.

Notes

The encoding is

\[ s_c = 2^{2|E|}g + 2^{|E|}d + p, \]

where \(g\) is the graph ID, \(d\) is the orientation bitmask, and \(p\) is the parity bitmask.

The parity bits occupy the lowest \(|E|\) positions, followed by the orientation bits, then the graph ID.

No decoration admissibility conditions are checked.

encode_orient_state(graph_num, orient_bits, num_edges)

Encode a graph ID and orientation bitmask as a single integer.

Parameters:

Name Type Description Default
graph_num int

Non-negative graph ID supplied by the caller.

required
orient_bits int

Orientation bitmask containing \(|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Encoded orientation state.

Raises:

Type Description
ValueError

If either input is negative, or the encoded state would exceed 64 bits.

Notes

The encoding is

\[ s_d = 2^{|E|}g + d, \]

where \(g\) is the graph ID and \(d\) is the orientation bitmask.

Bit \(e\) of \(d\) represents the orientation of edge index \(e\) relative to its reference direction.

No orientation admissibility conditions are checked.

encode_parity_state(graph_num, parity_bits, num_edges)

Encode a graph ID and parity bitmask as a single integer.

Parameters:

Name Type Description Default
graph_num int

Non-negative graph ID supplied by the caller.

required
parity_bits int

Parity bitmask containing \(|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Encoded parity state.

Raises:

Type Description
ValueError

If either input is negative, or the encoded state would exceed 64 bits.

Notes

The encoding is

\[ s_p = 2^{|E|}g + p, \]

where \(g\) is the graph ID and \(p\) is the parity bitmask.

Bit \(e\) of \(p\) represents edge index \(e\).

No parity admissibility conditions are checked.

find_min_combined_bits(combined_bits, sym_grp, num_edges, return_perm=False)

Find the minimum combined bitmask under a symmetry group.

Both orientation and parity decorations are transformed using the same signed edge permutation.

Parameters:

Name Type Description Default
combined_bits int

Combined decoration bitmask containing \(2|E|\) bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Numerically smallest combined bitmask under the supplied group action.

If return_perm=True, also return a signed edge permutation attaining this minimum.

Notes

The combined bitmask is

\[ c = 2^{|E|}d + p, \]

where \(d\) and \(p\) are the orientation and parity bitmasks.

Numerical minimization is equivalent to lexicographic minimization of \((d,p)\), with orientation taking precedence over parity.

The two decorations are not minimized independently.

If no strictly smaller bitmask is found, the identity permutation is returned when requested.

find_min_combined_state(combined_state, sym_grp, num_edges, return_perm=False)

Find the minimum encoded combined state under a symmetry group.

Parameters:

Name Type Description Default
combined_state int

Encoded state containing a graph ID, orientation bits, and parity bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Minimum encoded combined state, optionally accompanied by a minimizing signed edge permutation.

Notes

The graph ID is preserved.

Both decorations are transformed using the same signed edge permutation.

Numerical minimization gives priority to the orientation bitmask, followed by the parity bitmask among equivalent minimum orientations.

The decorations are not minimized independently.

find_min_orient_bits(orient_bits, sym_grp, num_edges, return_perm=False)

Find the minimum orientation bitmask under a symmetry group.

Parameters:

Name Type Description Default
orient_bits int

Orientation bitmask containing \(|E|\) bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Numerically smallest orientation bitmask under the supplied group action.

If return_perm=True, also return a signed edge permutation attaining this minimum.

Notes

The signs of the permutations are used to account for reversals of edge reference directions.

If no strictly smaller bitmask is found, the identity permutation is returned when requested.

Global reversal of all edge orientations is not included as an additional equivalence operation.

find_min_orient_state(orient_state, sym_grp, num_edges, return_perm=False)

Find the minimum encoded orientation state under a symmetry group.

Parameters:

Name Type Description Default
orient_state int

Encoded orientation state containing a graph ID and \(|E|\) orientation bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Minimum encoded orientation state, optionally accompanied by a minimizing signed edge permutation.

Notes

Only the orientation bitmask is minimized. The encoded graph ID is preserved.

Signed permutation entries account for changes in edge reference directions.

Global orientation reversal is not included as an additional equivalence operation.

find_min_parity_bits(parity_bits, sym_grp, num_edges, return_perm=False)

Find the minimum parity bitmask under a symmetry group.

Parameters:

Name Type Description Default
parity_bits int

Parity bitmask containing \(|E|\) bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Numerically smallest parity bitmask under the supplied group action.

If return_perm=True, also return a signed edge permutation attaining this minimum.

Notes

The minimum is calculated over the orbit of the original parity bitmask.

If no strictly smaller bitmask is found, the identity permutation is returned when requested.

No graph ID is included.

find_min_parity_state(parity_state, sym_grp, num_edges, return_perm=False)

Find the minimum encoded parity state under a symmetry group.

Parameters:

Name Type Description Default
parity_state int

Encoded parity state containing a graph ID and \(|E|\) parity bits.

required
sym_grp ndarray

Non-empty array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required
return_perm bool

If True, also return a permutation attaining the minimum.

False

Returns:

Type Description
int or tuple of (int, numpy.ndarray)

Minimum encoded parity state, optionally accompanied by a minimizing signed edge permutation.

Notes

Only the parity bitmask is minimized. The encoded graph ID is preserved.

If no strictly smaller state is found, the identity permutation is returned when requested.

permute_combined_bits(combined_bits, signed_perm, num_edges)

Apply a signed edge permutation to combined decorations.

The same permutation acts simultaneously on the orientation and parity bitmasks.

Parameters:

Name Type Description Default
combined_bits int

Combined decoration bitmask containing \(2|E|\) bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Type Description
int

Permuted combined decoration bitmask.

Notes

The combined bitmask is represented as

\[ c = 2^{|E|}d+p, \]

where \(d\) and \(p\) are the orientation and parity bitmasks, respectively.

For a signed permutation \(q[i]=s_i(j+1)\), the decorations transform according to

\[ p'_j=p_i, \]

and

\[ d'_j = \begin{cases} d_i, & s_i=+1,\\ 1-d_i, & s_i=-1. \end{cases} \]

The result is the combined bitmask

\[ c'=2^{|E|}d'+p'. \]

The signed permutation is validated, but is not required to be a graph automorphism.

The combined bitmask is assumed to be non-negative and to fit within \(2|E|\) bits.

No graph ID is included in the result.

permute_combined_state(combined_state, signed_perm, num_edges)

Apply a signed edge permutation to an encoded combined state.

The same permutation acts simultaneously on both orientation and parity decorations.

Parameters:

Name Type Description Default
combined_state int

Encoded combined state containing a graph ID, \(|E|\) orientation bits, and \(|E|\) parity bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Type Description
int

Encoded state with both decorations permuted.

Notes

The combined state is encoded as

\[ s_c = 2^{2|E|}g + 2^{|E|}d + p, \]

where \(g\) is the graph ID, \(d\) is the orientation bitmask, and \(p\) is the parity bitmask.

Both decorations undergo the same edge permutation. Negative permutation entries complement orientation bits but do not change parity values.

The graph ID is preserved.

The supplied permutation is validated, but is not required to be a positive graph automorphism.

permute_orient_bits(orient_bits, signed_perm, num_edges)

Apply a signed edge permutation to an orientation bitmask.

Parameters:

Name Type Description Default
orient_bits int

Orientation bitmask containing \(|E|\) bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Permuted orientation bitmask.

Notes

For each original edge index \(i\), let \(q\) be a signed edge permutation, with

\[ q[i] = s_i(j+1), \]

where \(j\) is the image edge index and \(s_i = \pm 1\).

The orientation bits \(d_i\) transform according to

\[ d'_j = \begin{cases} d_i, & s_i = +1,\\ 1-d_i, & s_i = -1. \end{cases} \]

Thus, a negative permutation entry complements the orientation bit when moving it to its new position.

The input bitmask and signed permutation are validated. The permutation is not required to be a graph automorphism.

No graph ID is included in the result.

permute_orient_state(orient_state, signed_perm, num_edges)

Apply a signed edge permutation to an encoded orientation state.

Parameters:

Name Type Description Default
orient_state int

Encoded orientation state containing a graph ID and \(|E|\) orientation bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Encoded state with permuted orientation bits.

Notes

For a signed permutation \(q[i]=s_i(j+1)\), the orientation bits transform as

\[ d'_j = \begin{cases} d_i, & s_i=+1,\\ 1-d_i, & s_i=-1. \end{cases} \]

Thus, a negative permutation entry complements the corresponding orientation bit.

The graph ID is preserved, and only the edge decoration is transformed.

The supplied permutation is validated, but is not required to be a positive graph automorphism.

permute_parity_bits(parity_bits, signed_perm, num_edges)

Apply a signed edge permutation to a parity bitmask.

Parameters:

Name Type Description Default
parity_bits int

Parity bitmask containing \(|E|\) bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Permuted parity bitmask.

Notes

For each original edge index \(i\), let \(q\) be a signed edge permutation, with

\[ q[i] = s_i(j+1), \]

where \(j\) is the image edge index and \(s_i = \pm 1\).

The parity bits \(p_i\) transform according to

\[ p'_j = p_i. \]

The signs of the permutation entries do not affect the parity values.

The input bitmask and signed permutation are validated. The permutation is not required to be a graph automorphism.

No graph ID is included in the result.

permute_parity_state(parity_state, signed_perm, num_edges)

Apply a signed edge permutation to an encoded parity state.

Parameters:

Name Type Description Default
parity_state int

Encoded parity state containing a graph ID and \(|E|\) parity bits.

required
signed_perm array_like of int

Signed edge permutation of length \(|E|\), using one-based edge labels.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required

Returns:

Type Description
int

Encoded state with permuted parity bits.

Notes

For an original edge index \(i\) mapped to edge \(j\), the parity bits transform as

\[ p'_j = p_i. \]

The signs of the permutation entries are ignored.

The graph ID is preserved, and only the edge decoration is transformed.

The supplied permutation is validated, but is not required to be a positive graph automorphism.

reverse_orientation(orient_state, num_edges, canonical=True, sym_grp=None)

Reverse all edge orientations in an encoded orientation state.

The operation complements every orientation bit while preserving the encoded graph ID.

Optionally, the reversed state is canonicalized under a supplied group of signed edge permutations.

Parameters:

Name Type Description Default
orient_state int

Encoded orientation state containing a graph ID and \(|E|\) orientation bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 64.

required
canonical bool

If True, find the minimum orientation bitmask after reversing all edge orientations.

True
sym_grp ndarray

Non-empty array of signed edge permutations of shape \((N_{\mathrm{sym}}, |E|)\).

Required when canonical=True.

None

Returns:

Type Description
int

Encoded state with reversed orientation bits, optionally canonicalized.

Raises:

Type Description
ValueError

If canonical=True and sym_grp is not supplied, or if the state or symmetry group is invalid.

Notes

Global orientation reversal acts on the bitmask \(d\) as

\[ R(d) = d \oplus (2^{|E|}-1). \]

The encoded graph ID is preserved.

If canonical=True, the returned orientation bitmask is

\[ d' = \min_{h\in H} h\cdot R(d), \]

where \(H\) is the supplied symmetry group.

Global orientation reversal is an involution before canonicalization.

separate_bits(combined_bits, num_edges)

Separate a combined decoration bitmask into its components.

Parameters:

Name Type Description Default
combined_bits int

Combined orientation and parity bitmask containing \(2|E|\) bits.

required
num_edges int

Number of graph edges \(|E|\), between 1 and 32.

required

Returns:

Name Type Description
orient_bits uint64

Orientation bitmask extracted from the upper \(|E|\) decoration bits.

parity_bits uint64

Parity bitmask extracted from the lower \(|E|\) decoration bits.

Notes

For a valid combined bitmask

\[ c = 2^{|E|}d + p, \]

the components are recovered using

\[ d = \left\lfloor \frac{c}{2^{|E|}} \right\rfloor, \qquad p = c \bmod 2^{|E|}. \]

No graph ID is extracted.

This function is the inverse of combine_bits() for bitmasks within the permitted ranges.