neuralqx.utils.symmetries.graph_symmetries module

class GraphSymmetries(edges, *, max_permutation_edges=10, allow_key_permutations=True, max_total_key_permutations=16384)

Bases: object

Compute permutations, cycles, and automorphisms of an oriented multigraph with parallel edges.

The input edges are oriented and may include parallel edges distinguished by an integer key. For structural computations (permutations / cycles / automorphisms), edge orientation is ignored by converting edges to a canonical, orientation-agnostic form (via _canon_edge). However, the original oriented domain is preserved for indexing and for the concrete permutation objects returned.

Key permutations:

If allow_key_permutations is enabled, automorphisms may additionally permute the keys within each unordered vertex pair, i.e. within each multiedge bucket connecting the same two vertices. This can greatly increase the number of automorphisms, so a cap max_total_key_permutations is used to avoid combinatorial blow-up.

The class lazily computes and caches:

  • permutations: edge permutations (up to a size cap)

  • cycles: cyclic shifts of the canonical edge ordering

  • automorphisms: structure-preserving vertex maps (plus optional within-pair key permutations)

  • graph_symmetries: concatenation of the above

Parameters:

  • edges (Iterable[Tuple[int, int, int]]) – Iterable of oriented keyed edges. Orientation is ignored for structure but preserved in the returned symmetry objects’ domain.

  • max_permutation_edges (int) – If the number of unique canonical edges exceeds this value, permutations returns only the identity (avoids factorial growth).

  • allow_key_permutations (bool) – If True, automorphisms include permutations of keys within each unordered vertex pair when there are multiple parallel edges.

  • max_total_key_permutations (int) – Upper bound on the total number of combinations of per-pair key permutations for a given vertex automorphism. If this cap is exceeded, key permutations fall back to identity per pair.

Raises:

ValueError – If no edges are provided, or if duplicate keys occur within an unordered vertex pair.

property permutations: List[Permutation]

Lazily compute and return edge permutations on the canonical edge set.

The returned list always includes the identity permutation. If the number of canonical edges n is at most max_permutation_edges, all n! permutations are generated (excluding the identity which is already included). If n exceeds the cap, only the identity permutation is returned to avoid combinatorial blow-up.

Returns:

List of Permutation objects acting on the stored domain.

property cycles: List[Cycle]

Lazily compute and return cyclic shifts of the canonical edge ordering.

For n canonical edges, this produces n cycles, where the k-th cycle maps edge position i to position (i + k) mod n in the canonical ordering.

Returns:

List of Cycle objects.

property automorphisms: List[Automorphism]

Lazily compute and return automorphisms of the multigraph.

Automorphisms are computed by enumerating candidate vertex permutations subject to pruning:

  • Vertices are bucketed by a permutation-invariant signature derived from incident multiedge structure (see _compute_vertex_invariants()).

  • Only within-bucket vertex permutations are combined (cartesian product across buckets).

  • Each candidate vertex map is checked for structure preservation (including key multisets per unordered pair).

If allow_key_permutations is True, then for each vertex automorphism, all admissible permutations of parallel-edge keys within each mapped unordered vertex pair are also enumerated. The total number of key-permutation combinations is capped by max_total_key_permutations, if exceeded, key permutations fall back to the identity per pair.

The identity automorphism is guaranteed to be included.

Returns:

List of Automorphism objects.

property graph_symmetries: List[object]

Return all computed graph symmetries as a single list.

This is the concatenation of permutations, cycles, and automorphisms in that order. The result is cached after first construction.

Returns:

List containing permutations, cycles, and automorphisms.

property edges: List[Tuple[int, int, int]]

Return canonical, orientation-agnostic unique edges in deterministic order.

These edges represent the structural edge set used for symmetry computations. To iterate edges in a way that respects the original oriented input, iterate over the emitted Permutation/Cycle/Automorphism objects (which carry domain built from the oriented input).

Returns:

List of canonical edges.

property vertices: List[int]

Return the sorted list of vertices present in the canonical edge set.

Returns:

List of vertex ids in deterministic order.

make_permutation_from_order(new_order, name='custom')

Build a Permutation from a provided ordering of the canonical edge set.

The provided new_order must be a permutation of edges up to canonicalization. Oriented versions are allowed, only their canonical forms are used for validity and mapping.

Parameters:

  • new_order (Sequence[Tuple[int, int, int]]) – Sequence of edges representing the desired order, must match the current canonical edge set up to permutation.

  • name (str) – Name assigned to the resulting permutation. Defaults to "custom".

Return type:

Permutation

Returns:

A Permutation mapping the current canonical ordering to new_order.

Raises:

ValueError – If new_order is not a permutation of the canonical edge set.