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
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 If |
True
|
Returns:
| Type | Description |
|---|---|
tuple of numpy.uint64
|
If Otherwise, return \[
\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
where \(d\) and \(p\) are orientation and parity bitmasks.
The encoded state is
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
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
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
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 |
False
|
Returns:
| Type | Description |
|---|---|
int or tuple of (int, numpy.ndarray)
|
Numerically smallest combined bitmask under the supplied group action. If |
Notes
The combined bitmask is
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 |
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 |
False
|
Returns:
| Type | Description |
|---|---|
int or tuple of (int, numpy.ndarray)
|
Numerically smallest orientation bitmask under the supplied group action. If |
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 |
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 |
False
|
Returns:
| Type | Description |
|---|---|
int or tuple of (int, numpy.ndarray)
|
Numerically smallest parity bitmask under the supplied group action. If |
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 |
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
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
and
The result is the combined bitmask
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
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
where \(j\) is the image edge index and \(s_i = \pm 1\).
The orientation bits \(d_i\) transform according to
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
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
where \(j\) is the image edge index and \(s_i = \pm 1\).
The parity bits \(p_i\) transform according to
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
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
|
sym_grp
|
ndarray
|
Non-empty array of signed edge permutations of shape \((N_{\mathrm{sym}}, |E|)\). Required when |
None
|
Returns:
| Type | Description |
|---|---|
int
|
Encoded state with reversed orientation bits, optionally canonicalized. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |
Notes
Global orientation reversal acts on the bitmask \(d\) as
The encoded graph ID is preserved.
If canonical=True, the returned orientation bitmask is
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
the components are recovered using
No graph ID is extracted.
This function is the inverse of combine_bits()
for bitmasks within the permitted ranges.