Graph API
trivalent.trivalent.Graph
Represent a trivalent graph with a specified cyclic ordering of edges.
A Graph object represents a 3-regular graph together with the counterclockwise cyclic ordering of incident edges at each vertex. These cyclic orders determine a combinatorial embedding of the graph in an orientable surface.
The graph is constructed from an implicitly ordered edge list: the order in which edges appear determines their cyclic ordering at each vertex.
Notes
- Vertex and edge indices are zero-based.
- The endpoints of each edge determine its reference direction, used when constructing signed edge permutations.
- The graph may be modified in place by Pachner moves.
- Face information is calculated when needed.
- Construction does not establish planarity or 3-connectivity.
- Isomorphism and automorphism computations assume connected graphs. The constructor does not verify this precondition.
Examples:
Create a triangular prism:
>>> G = Graph.create_prism(3)
>>> G.num_vert
6
>>> G.num_edges
9
>>> G.num_faces
5
Attributes
edge_list
property
ndarray of shape \((|E|, 2)\): Edges \((u, v)\) of the graph.
Each row contains the two zero-based vertex indices of an edge. The order of the endpoints defines the reference direction of the edge, used when constructing signed edge permutations.
Edges are indexed by their row positions, starting at zero.
A copy of the active edge list is returned, so modifying the returned array does not affect the Graph object.
face_adj_matrix
property
Return the symmetric adjacency matrix of the graph's faces.
Returns:
| Type | Description |
|---|---|
ndarray
|
Symmetric array of shape \((|F|, |F|)\). The entry \(A_{ij}\) counts the number of graph edges shared by faces \(i\) and \(j\). |
Notes
The matrix is the adjacency matrix of the dual graph, with edge multiplicities retained.
If an edge has the same face on both sides, it contributes two to the diagonal entry \(A_{ii}\).
Face information is calculated on first access if necessary. A copy of the matrix is returned.
face_bndy_list
property
Return the ordered boundary edges of each face.
Returns:
| Type | Description |
|---|---|
list of list of int
|
Entry i contains the signed edge labels forming the boundary of face i, traversed counterclockwise. |
Notes
The signed label of edge \(e\) is \(+(e+1)\) when traversed in its reference direction, and \(-(e+1)\) when traversed in the opposite direction.
The reference direction is determined by the order of the edge endpoints in edge_list, not by any orientation decoration.
Face information is calculated on first access if necessary. A copy of each face boundary list is returned.
face_idx_list
property
Return the face indices on either side of each edge.
Returns:
| Type | Description |
|---|---|
ndarray of shape (E, 2)
|
For each edge e:
|
Notes
Left and right are defined relative to the reference direction of each edge, as specified by its ordered endpoints.
Face indices are zero-based and determined by find_faces(). They are not intrinsic labels preserved under graph isomorphisms or Pachner moves.
Face information is calculated on first access if necessary. A copy of the array is returned.
face_size_list
property
Return the number of boundary edges of each face.
Returns:
| Type | Description |
|---|---|
ndarray
|
One-dimensional array of shape \((|F|,)\), where \(|F|\) is the number of faces. Entry \(i\) gives the length of the boundary walk of face \(i\), counting edge traversals. |
Notes
Face information is calculated on first access if necessary. A copy of the array is returned.
num_edges
property
int: Number of edges \(|E|\) in the graph.
num_faces
property
int: Number of faces \(|F|\) in the graph's combinatorial embedding.
Face information is calculated on first access if it has not already been determined.
num_vert
property
int: Number of vertices \(|V|\) in the graph.
vert_cyc_order
property
ndarray of shape \((|V|, 3)\): Cyclic ordering of incident edges.
Each row contains the zero-based indices of the three edges incident to a vertex, in counterclockwise cyclic order.
Row i corresponds to vertex i.
A copy of the active vertex cyclic orders is returned, so modifying the returned array does not affect the Graph object.
Methods:
__eq__(other)
Test equality of two embedded trivalent graphs.
Two Graph objects are equal if there exists an isomorphism
preserving the counterclockwise cyclic order of incident
edges at every vertex.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
other
|
Graph
|
Graph to compare with the current graph. |
required |
Returns:
| Type | Description |
|---|---|
bool
|
|
Notes
Implements the == operator by calling
is_isomorphic(other, return_perm = False).
For objects that are not instances of Graph, the method
returns NotImplemented, allowing Python's normal
comparison machinery to handle the result.
__init__(ordered_edge_list=None, max_num_vert=None, validate=True)
Initialize a graph from an implicitly ordered edge list.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
ordered_edge_list
|
array_like of int
|
Array of shape \((|E|, 2)\), containing pairs of vertex indices \((u,v)\) specifying the graph edges. Vertex indices run from \(0\) to \(|V|-1\). The order in which edges occur in the list determines the counterclockwise cyclic order of incident edges at each vertex. If |
None
|
max_num_vert
|
int
|
Maximum number of vertices accommodated by the graph's internal storage, including subsequent Pachner moves. Defaults to Graph.DEFAULT_MAX_VERT (currently 50). The permitted range is 1 to 84. |
None
|
validate
|
bool
|
If True, check that the edge count is compatible with a trivalent graph, that vertex labels are consecutive starting at zero, and that each vertex occurs exactly three times in the edge list. This does not test graph connectivity, planarity, or 3-connectivity. |
True
|
Raises:
| Type | Description |
|---|---|
ValueError
|
If max_num_vert is invalid or the edge list fails the implemented validation checks. |
Notes
The graph's vertex and edge counts are determined from the edge list. Face information is computed separately when first requested.
create_prism(N)
classmethod
Construct an \(N\)-gonal prism as an embedded trivalent graph.
The prism consists of two \(N\)-cycles connected by \(N\) edges joining corresponding vertices.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
N
|
int
|
Number of vertices in each of the two polygonal faces. Must satisfy \(N \geq 3\). |
required |
Returns:
| Type | Description |
|---|---|
Graph
|
A new |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |
Notes
The resulting graph is planar, 3-regular, and 3-connected, with
The vertex cyclic orders are determined by the implicitly ordered edge list.
The graph is created using the default vertex
storage capacity. Thus, \(N \leq 25\) with
DEFAULT_MAX_VERT = 50
Examples:
Construct the square prism (cube graph):
>>> G = Graph.create_prism(4)
>>> G.num_vert, G.num_edges, G.num_faces
(8, 12, 6)
find_faces()
Find the faces of the combinatorially embedded graph.
The faces are determined by the counterclockwise cyclic ordering of incident edges at each vertex. They are enumerated by tracing the directed boundary walks.
The resulting face information is stored in the graph.
Returns:
| Type | Description |
|---|---|
None
|
The method updates the internally stored face data. |
Notes
The following face information is calculated:
num_faces: number of faces \(|F|\).face_bndy_list: signed edge labels for each face boundary.face_idx_list: left- and right-hand face indices for each edge.face_size_list: number of edge traversals around each face.
Face indices are zero-based and assigned in traversal order.
The boundary of each face is traversed counterclockwise, with the face on the left. Boundary edges use one-based signed labels, with positive sign when traversed in the edge's reference direction.
For a zero-based edge index \(e\), face_idx_list[e, 0]
and face_idx_list[e, 1] give the faces on the left
and right of its reference direction, respectively.
Face labels depend on the edge ordering and are not invariant under graph isomorphisms.
For a non-planar combinatorial embedding, the faces correspond to the boundary walks of the associated orientable surface embedding, not necessarily the sphere.
Face information is also calculated automatically when first requested through the corresponding properties.
find_min_combined_state(combined_state, sym_grp)
Find the canonical representative of a combined state.
The state contains both orientation and parity decorations. Both bitmasks are transformed simultaneously under the same signed edge permutation.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
combined_state
|
int
|
Encoded combined state containing a graph ID, \(|E|\) orientation bits, and \(|E|\) parity bits. |
required |
sym_grp
|
ndarray
|
Array of shape \((N_{\mathrm{sym}}, |E|)\) containing
signed edge permutations, usually obtained from
|
required |
Returns:
| Type | Description |
|---|---|
int
|
Numerically smallest encoded combined state under the supplied group action. |
Notes
The graph ID is preserved.
The encoding places the orientation bits above the parity bits. Consequently, numerical minimization first minimizes the orientation bitmask and then, among equivalent minimum orientations, minimizes the parity bitmask.
The same permutation must act on both decorations; they are not minimized independently.
find_min_orient_state(orient_state, sym_grp)
Find the canonical representative of an orientation state.
The state is minimized over its orbit under the 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 |
sym_grp
|
ndarray
|
Array of shape \((N_{\mathrm{sym}}, |E|)\) containing
signed edge permutations, usually obtained from
|
required |
Returns:
| Type | Description |
|---|---|
int
|
Numerically smallest encoded orientation state under the supplied group action. |
Notes
The graph ID is preserved. Only the orientation bitmask is transformed.
A negative entry in a signed permutation accounts for reversal of the reference direction of an edge when transforming its orientation bit.
Global reversal of all edge orientations is not included as an additional equivalence operation.
find_min_parity_state(parity_state, sym_grp)
Find the canonical representative of a parity state.
The state is minimized over its orbit under the supplied group of signed edge permutations.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
parity_state
|
int
|
Encoded parity state containing a graph ID and \(|E|\) parity bits. |
required |
sym_grp
|
ndarray
|
Array of shape \((N_{\mathrm{sym}}, |E|)\) containing
signed edge permutations, usually obtained from
|
required |
Returns:
| Type | Description |
|---|---|
int
|
Numerically smallest encoded parity state under the supplied group action. |
Notes
The graph ID is preserved. Only the parity bitmask is transformed.
If sym_grp is the full positive automorphism group,
the result is a canonical representative of the
parity state under \(\operatorname{Aut}^{+}(G)\).
find_noniso_edges(mask_type=None, bitmask=None, sym_grp=None)
Find representatives of edge orbits under graph automorphisms.
The edges are partitioned into orbits under the action of the positive automorphism group \(\operatorname{Aut}^{+}(G)\), or the subgroup preserving a specified edge decoration.
One representative is returned from each orbit.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
mask_type
|
(None, orient, parity, combined)
|
Type of edge decoration to preserve.
|
None
|
bitmask
|
int
|
Integer encoding the edge decorations specified by
Required when |
None
|
sym_grp
|
ndarray
|
Array of shape \((N_{\mathrm{sym}}, |E|)\) containing signed edge permutations. If Otherwise, the supplied group is used. |
None
|
Returns:
| Type | Description |
|---|---|
ndarray
|
One-dimensional integer array containing one zero-based edge index from each orbit. The number of entries equals the number of edge orbits under the selected group action. |
Notes
For an undecorated graph, the relevant group is \(\operatorname{Aut}^{+}(G)\).
For an oriented graph state \((G, d)\), the relevant group is the stabilizer
with the analogous definitions for parity and combined decorations.
The orbit of an edge \(e\) under a group \(H\) is
Two edges are equivalent if they belong to the same orbit.
The returned indices are representatives of these orbits; they are not necessarily the smallest indices in their respective orbits.
Only the absolute values of the signed edge permutations are used when determining edge equivalence.
The supplied sym_grp is assumed to contain valid graph
automorphisms. Its group properties are not verified.
Examples:
Find representatives of the edge orbits of a triangular prism:
>>> G = Graph.create_prism(3)
>>> edges = G.find_noniso_edges()
>>> len(edges)
2
find_sym()
Find the positive automorphism group \(\operatorname{Aut}^{+}(G)\) of the embedded graph \(G\).
A positive automorphism is an isomorphism from the graph to itself that preserves the counterclockwise cyclic ordering of incident edges at every vertex.
These automorphisms are represented by signed permutations of the graph edges.
Returns:
| Type | Description |
|---|---|
ndarray
|
Integer array of shape \((N_{\mathrm{sym}}, |E|)\), where \(N_{\mathrm{sym}}\) is the number of automorphisms found. Each row represents one automorphism as a signed permutation of the edges. |
Notes
The returned permutations use one-based signed edge labels.
For a permutation p, the entry p[e] specifies the
image of the zero-based edge index \(e\):
abs(p[e]) - 1is the corresponding edge index.- A positive sign means the reference direction is preserved.
- A negative sign means the reference direction is reversed.
The signs refer to the ordering of edge endpoints, not to independently assigned orientation decorations.
Only automorphisms preserving the vertex cyclic orders are included. Automorphisms reversing the embedding orientation are excluded.
The identity automorphism is included. The ordering of group elements is not guaranteed.
The implementation currently limits the number of
returned automorphisms to DEFAULT_MAX_SYM (60).
Graphs with larger automorphism groups may therefore
have incomplete results.
Examples:
Find the automorphism group of a triangular prism:
>>> G = Graph.create_prism(3)
>>> sym_grp = G.find_sym()
>>> sym_grp.shape[1] == G.num_edges
True
The order of the returned group is:
>>> len(sym_grp)
6
is_isomorphic(other, return_perm=True)
Determine whether two embedded trivalent graphs are isomorphic.
An isomorphism is required to preserve the counterclockwise cyclic ordering of incident edges at every vertex. Thus, the test is for isomorphism of combinatorially embedded graphs, rather than abstract graph isomorphism.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
other
|
Graph
|
Graph to compare with the current graph. |
required |
return_perm
|
bool
|
If If |
= True
|
Returns:
| Type | Description |
|---|---|
ndarray or bool or None
|
If Otherwise, return If |
Notes
The returned signed permutation uses one-based edge labels. For each zero-based source edge index \(e\),
where \(j\) is the corresponding zero-based edge index in
other, and \(s_e = \pm 1\).
The sign records whether the isomorphism preserves (\(+1\)) or reverses (\(-1\)) the reference direction of that edge, as specified by its ordered endpoints.
The sign does not indicate an independently assigned orientation decoration.
Mirror embeddings are distinguished because the isomorphism must preserve the vertex cyclic orders.
If multiple isomorphisms exist, only one is returned.
Examples:
Test isomorphism without constructing an edge permutation:
>>> G = Graph.create_prism(3)
>>> G.is_isomorphic(G, return_perm = False)
True
Obtain a signed edge permutation:
>>> perm = G.is_isomorphic(G)
>>> len(perm) == G.num_edges
True
map_combined_state(combined_state, other)
Map a combined state to a positively isomorphic graph.
Find a positive isomorphism from the current graph self
to other, then transform both orientation and parity
decorations to match the edge ordering of other.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
combined_state
|
int
|
Encoded combined state whose edge indices correspond to the current graph. |
required |
other
|
Graph
|
Target graph, positively isomorphic to the current graph. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded combined state with both decorations expressed
in the edge ordering of |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the two embedded graphs are not positively isomorphic. |
Notes
Both decorations are transformed using the same signed
edge permutation obtained from is_isomorphic().
Negative permutation entries reverse orientation bits, but do not affect parity values.
The encoded graph ID is preserved. Neither graph is modified.
map_orient_state(orient_state, other)
Map an orientation state to a positively isomorphic graph.
Find a positive isomorphism from the current graph self
to other, then transform the orientation state to match
the edge ordering and reference directions of other.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
orient_state
|
int
|
Encoded orientation state whose edge indices correspond to the current graph. |
required |
other
|
Graph
|
Target graph, positively isomorphic to the current graph. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded orientation state with edge decorations
expressed in the edge ordering of |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the two embedded graphs are not positively isomorphic. |
Notes
The signed edge permutation is obtained automatically
using is_isomorphic().
A negative permutation entry reverses the corresponding orientation bit to account for the change in edge reference direction.
The encoded graph ID is preserved. Neither graph is modified.
map_parity_state(parity_state, other)
Map a parity state to a positively isomorphic graph.
Find a positive isomorphism from the current graph self
to other, then transform the parity state to match the
edge ordering of other.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
parity_state
|
int
|
Encoded parity state whose edge indices correspond to the current graph. |
required |
other
|
Graph
|
Target graph, positively isomorphic to the current graph. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded parity state with edge decorations expressed
in the edge ordering of |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the two embedded graphs are not positively isomorphic. |
Notes
The signed edge permutation is obtained automatically
using is_isomorphic().
Only edge positions are permuted; signs in the permutation do not change parity values.
The encoded graph ID is preserved. Neither graph is modified.
pachner13(vert_idx)
Perform a Pachner 1-3 move at a specified vertex.
Replace the vertex by a triangular face, reconnecting its three incident edges to the vertices of the triangle.
The graph is modified in place.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
vert_idx
|
int
|
Zero-based index of the vertex to expand. |
required |
Returns:
| Type | Description |
|---|---|
tuple of int
|
Zero-based indices of the three newly created edges, in their order in the updated edge list. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the move would exceed the graph's |
Notes
The move changes the graph sizes according to
The original vertex is retained, and two new vertices are appended to the vertex list.
The indices of all existing edges are preserved. The three new edges are appended at indices \(|E|\), \(|E|+1\), and \(|E|+2\), where \(|E|\) is the original edge count.
Face information is invalidated and recalculated when subsequently requested.
The method does not assign orientation or parity decorations to the new edges.
Consequently, existing edge decorations retain their edge indices, while the new edges require additional decoration values.
Existing edge indices are preserved, but changes in reference direction may require updating their orientation bits.
Examples:
Expand vertex 0 of a triangular prism:
>>> G = Graph.create_prism(3)
>>> new_edges = G.pachner13(0)
>>> new_edges
(9, 10, 11)
>>> G.num_vert
8
pachner22(edge_idx)
Perform a Pachner 2-2 move on a specified edge.
Replace the local connection between the two vertices incident to the edge, preserving the trivalent structure and cyclic ordering of incident edges.
The graph is modified in place if the move succeeds.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
edge_idx
|
int
|
Zero-based index of the edge on which to perform the move. |
required |
Returns:
| Type | Description |
|---|---|
tuple of (int, numpy.ndarray)
|
A pair
If the move is prohibited, return |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |
Notes
The move preserves the numbers of vertices, edges, and faces.
The implementation rejects a move when the two opposite faces involved already share an edge, as this would violate the intended 3-connectivity restriction.
The signed edge mapping uses one-based labels. For an original edge index \(e\),
where \(j\) is its index after the move and \(s_e = \pm 1\) records any reversal of its reference direction.
The edge list may be reordered to preserve the implicit cyclic-order convention.
Face information is invalidated after a successful move and recalculated when subsequently requested.
The method does not assign new edge decorations or determine admissible decorated Pachner moves.
pachner31(cycle_list)
Perform a Pachner 3-1 move on a triangular cycle.
Contract a 3-cycle to a single vertex, reconnecting the three external edges incident to the cycle.
The graph is modified in place.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
cycle_list
|
array_like of int
|
Three zero-based edge indices forming a 3-cycle in the graph. The indices may be supplied in any order. |
required |
Returns:
| Type | Description |
|---|---|
ndarray
|
Signed integer array of shape \((|E|-3,)\), where \(|E|\) denotes the original edge count. Entry |
Raises:
| Type | Description |
|---|---|
ValueError
|
If the number of supplied edges is not three, an edge index is out of range, or the given edges do not form a 3-cycle. |
Notes
The move changes the graph sizes according to
The vertex with the smallest index in the 3-cycle is retained. The other two vertices and the three cycle edges are removed.
Remaining vertices and edges are relabeled to maintain consecutive indices and the implicit cyclic-order convention.
The returned mapping is from NEW edges to OLD edges:
where \(i\) is the original index of the surviving edge corresponding to new edge \(j\), and \(s_j = \pm 1\) records any reversal of the reference direction.
Face information is invalidated and recalculated when subsequently requested.
The method does not update edge decorations or verify that the resulting graph is 3-connected.
permute_combined_state(combo_state, signed_edge_perm)
Apply a signed edge permutation to an encoded combined state.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
combo_state
|
int
|
Encoded state containing orientation and parity bits. |
required |
signed_edge_perm
|
array_like of int
|
Signed permutation of shape \((|E|,)\) using one-based edge labels. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded state with both decorations permuted. |
Notes
The same signed permutation acts on both decorations.
Negative entries reverse the corresponding orientation bits but do not change parity values.
The graph ID is preserved.
The permutation is checked for validity as a signed permutation, but is not verified to be a positive automorphism of the graph.
permute_orient_state(orient_state, signed_edge_perm)
Apply a signed edge permutation to an encoded orientation state.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
orient_state
|
int
|
Encoded orientation state to transform. |
required |
signed_edge_perm
|
array_like of int
|
Signed permutation of shape \((|E|,)\) using one-based edge labels. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded state with permuted orientation bits. |
Notes
A negative permutation entry reverses the corresponding orientation bit when assigning it to its target edge.
The graph ID is preserved.
The permutation is checked for validity as a signed permutation, but is not verified to be a positive automorphism of the graph.
permute_parity_state(parity_state, signed_edge_perm)
Apply a signed edge permutation to an encoded parity state.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
parity_state
|
int
|
Encoded parity state to transform. |
required |
signed_edge_perm
|
array_like of int
|
Signed permutation of shape \((|E|,)\) using one-based edge labels. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Encoded state with permuted parity bits. |
Notes
Only the absolute values of the permutation entries affect the parity bitmask.
The graph ID is preserved.
The permutation is checked for validity as a signed permutation, but is not verified to be a positive automorphism of the graph.