Symmetry Detection

Automorphism based symmetry detection.

class asunder.base.branch_and_price.symmetry_detection.OrbitsResult(rep, orbits, generators)

Bases: object

Symmetry-orbit data for the original graph vertices.

Parameters:

  • rep (ndarray)

  • orbits (List[List[int]])

  • generators (List[List[int]])

rep

Array where rep[i] is the representative vertex for the orbit containing vertex i.

Type:

numpy.ndarray

orbits

Orbit partition of the original vertices.

Type:

list of list of int

generators

Automorphism generators of the transformed graph.

Type:

list of list of int

asunder.base.branch_and_price.symmetry_detection._iter_upper_weighted_edges(A)

Yield nonzero weighted edges from the upper triangle of a matrix.

Parameters:

A (array-like or scipy.sparse matrix) – Square weighted adjacency matrix.

Yields:

tuple of int, int, float – Edge triplets (i, j, w) with i < j and A[i, j] != 0.

Raises:

ValueError – If A is dense and not square.

Return type:

Iterable[Tuple[int, int, float]]

asunder.base.branch_and_price.symmetry_detection.weighted_constraint_orbits(A, *, vertex_colors=None, weight_to_key=None, weight_round_tol=1e-09, sh='fl')

Compute exact vertex orbits of a weighted graph under color-preserving automorphisms.

Parameters:

  • A (array-like or scipy.sparse matrix) – Square weighted adjacency matrix. Nonzeros in the upper triangle define undirected edges.

  • vertex_colors (sequence of int, optional) – Vertex color classes to preserve during the automorphism computation.

  • weight_to_key (callable, optional) – Function mapping each edge weight to a hashable key used to distinguish weight classes. If omitted, near-integer weights are bucketed by integer value.

  • weight_round_tol (float, optional) – Tolerance used when deciding whether a weight should be treated as an integer-valued key.

  • sh (str, optional) – BLISS splitting heuristic passed to igraph.Graph.automorphism_group.

Returns:

Orbit representatives, orbit lists, and automorphism generators.

Return type:

OrbitsResult

Notes

Edge weights are preserved up to the chosen weight bucketing rule.

Raises:

ImportError – If python-igraph is not available.

Parameters:

  • vertex_colors (Sequence[int] | None)

  • weight_to_key (Callable[[float], Hashable] | None)

  • weight_round_tol (float)

  • sh (str)

Return type:

OrbitsResult