cayleypy.CayleyGraph

class cayleypy.CayleyGraph

Represents a Schreier coset graph for some group.

In this graph:

• Vertices (aka “states”) are integer vectors or matrices.

• There is an outgoing edge for every vertex A and every generator G.

• On the other end of this edge, there is a vertex G(A).

When definition.generator_type is PERMUTATION:

• The group is the group of permutations S_n.

• Generators are permutations of n elements.

• States are vectors of integers of size n.

When definition.generator_type is MATRIX:

• The group is the group of n*n integer matrices under multiplication (usual or modular)

• Technically, it’s a group only when all generators are invertible, but we don’t require this.

• Generators are n*n integer matrices.

• States are n*m integers matrices.

In general case, this graph is directed. However, in the case when set of generators is closed under inversion, every edge has and edge in other direction, so the graph can be viewed as undirected.

The graph is fully defined by list of generators and one selected state called “central state”. The graph contains all vertices reachable from the central state. This definition is encapsulated in cayleypy.CayleyGraphDef.

In the case when the central state is a permutation itself, and generators fully generate S_n, this is a Cayley graph, hence the name. In more general case, elements can have less than n distinct values, and we call the set of vertices “coset”.

__init__(definition: CayleyGraphDef, *, device: str = 'auto', random_seed: int | None = None, bit_encoding_width: int | None | str = 'auto', verbose: int = 0, batch_size: int = 1048576, hash_chunk_size: int = 33554432, memory_limit_gb: float = 16, _hasher: StateHasher | None = None, **unused_kwargs)

Initializes CayleyGraph.

Parameters:

• definition – definition of the graph (as CayleyPyDef).

• device – one of [‘auto’,’cpu’,’cuda’] - PyTorch device to store all tensors.

• random_seed – random seed for deterministic hashing.

• bit_encoding_width – how many bits (between 1 and 63) to use to encode one element in a state. If ‘auto’, optimal width will be picked. If None, elements will be encoded by int64 numbers.

• verbose – Level of logging. 0 means no logging.

• batch_size – Size of batch for batch processing.

• hash_chunk_size – Size of chunk for hashing.

• memory_limit_gb – Approximate available memory, in GB. It is safe to set this to less than available on your machine, it will just cause more frequent calls to the “free memory” function.

Methods

__init__(definition, *[, device, ...])	Initializes CayleyGraph.
apply_generator_batched(i, src, dst)	Applies i-th generator to encoded states in src, writes output to dst.
apply_path(states, generator_ids)	Applies multiple generators to given state(s) in order.
beam_search(**kwargs)	Tries to find a path from start_state to central state using Beam Search algorithm.
bfs(*[, start_states, ...])	Runs bread-first search (BFS) algorithm from given start_states.
decode_states(states)	Converts states from internal to human-readable representation.
encode_states(states)	Converts states from human-readable to internal representation.
find_path_from(start_state, bfs_result)	Finds path from start_state to central_state using pre-computed BfsResult.
find_path_to(end_state, bfs_result)	Finds path from central_state to end_state using pre-computed BfsResult.
free_memory()
get_neighbors(states)	Calculates all neighbors of states (in internal representation).
get_neighbors_decoded(states)	Calculates neighbors in decoded (external) representation.
get_unique_states(states[, hashes])	Removes duplicates from states and sorts them by hash.
modified_copy(new_def)	Makes a copy of this graph with different definition but other parameters unchanged.
random_walks(**kwargs)	Generates random walks on this graph.
restore_path(hashes, to_state)	Restores path from layers hashes.
to_networkx_graph()
validate_path(start_state, path)	Checks that path indeed is path from start_state to central state.

Attributes

generators	Generators of this Cayley graph.
with_inverted_generators	Returns copy of this graph with inverted generators.

apply_generator_batched(i: int, src: Tensor, dst: Tensor)

Applies i-th generator to encoded states in src, writes output to dst.

apply_path(states: Tensor | ndarray | list, generator_ids: list[int]) → Tensor

Applies multiple generators to given state(s) in order.

Parameters:

• states – one or more states (as torch.Tensor) to which to apply the states.

• generator_ids – Indexes of generators to apply.

Returns:

States after applying specified generators in order.

beam_search(**kwargs)

Tries to find a path from start_state to central state using Beam Search algorithm.

See cayleypy.algo.BeamSearchAlgorithm for more details.

bfs(*, start_states: None | Tensor | ndarray | list = None, max_layer_size_to_store: int | None = 1000, max_layer_size_to_explore: int = 1000000000000, max_diameter: int = 1000000, return_all_edges: bool = False, return_all_hashes: bool = False, stop_condition: Callable[[Tensor, Tensor], bool] | None = None, disable_batching: bool = False) → BfsResult

Runs bread-first search (BFS) algorithm from given start_states.

BFS visits all vertices of the graph in layers, where next layer contains vertices adjacent to previous layer that were not visited before. As a result, we get all vertices grouped by their distance from the set of initial states.

Depending on parameters below, it can be used to:

• Get growth function (number of vertices at each BFS layer).

• Get vertices at some first and last layers.

• Get all vertices.

• Get all vertices and edges (i.e. get the whole graph explicitly).

Parameters:

• start_states – states on 0-th layer of BFS. Defaults to destination state of the graph.

• max_layer_size_to_store – maximal size of layer to store. If None, all layers will be stored (use this if you need full graph). Defaults to 1000. First and last layers are always stored.

• max_layer_size_to_explore – if reaches layer of larger size, will stop the BFS.

• max_diameter – maximal number of BFS iterations.

• return_all_edges – whether to return list of all edges (uses more memory).

• return_all_hashes – whether to return hashes for all vertices (uses more memory).

• stop_condition – function to be called after each iteration. It takes 2 tensors: latest computed layer and its hashes, and returns whether BFS must immediately terminate. If it returns True, the layer that was passed to the function will be the last returned layer in the result. This function can also be used as a “hook” to do some computations after BFS iteration (in which case it must always return False).

• disable_batching – Disable batching. Use if you need states and hashes to be in the same order.

Returns:

BfsResult object with requested BFS results.

decode_states(states: Tensor) → Tensor

Converts states from internal to human-readable representation.

encode_states(states: Tensor | ndarray | list) → Tensor

Converts states from human-readable to internal representation.

find_path_from(start_state: Tensor | ndarray | list, bfs_result: BfsResult) → list[int] | None

Finds path from start_state to central_state using pre-computed BfsResult.

This is possible only for inverse-closed generators.

Parameters:

• start_state – First state of the path.

• bfs_result – Pre-computed BFS result (call bfs(return_all_hashes=True) to get this).

Returns:

The found path (list of generator ids), or None if central_state is not reachable from start_state.

find_path_to(end_state: Tensor | ndarray | list, bfs_result: BfsResult) → list[int] | None

Finds path from central_state to end_state using pre-computed BfsResult.

Parameters:

• end_state – Final state of the path.

• bfs_result – Pre-computed BFS result (call bfs(return_all_hashes=True) to get this).

Returns:

The found path (list of generator ids), or None if end_state is not reachable from start_state.

property generators

Generators of this Cayley graph.

get_neighbors(states: Tensor) → Tensor

Calculates all neighbors of states (in internal representation).

get_neighbors_decoded(states: Tensor) → Tensor

Calculates neighbors in decoded (external) representation.

get_unique_states(states: Tensor, hashes: Tensor | None = None) → tuple[Tensor, Tensor]

Removes duplicates from states and sorts them by hash.

modified_copy(new_def: CayleyGraphDef) → CayleyGraph

Makes a copy of this graph with different definition but other parameters unchanged.

The new graph will use the same encoding and hashing for states as the original.

random_walks(**kwargs)

Generates random walks on this graph.

See cayleypy.algo.RandomWalksGenerator for more details.

restore_path(hashes: list[Tensor], to_state: Tensor | ndarray | list) → list[int]

Restores path from layers hashes.

Layers must be such that there is edge from state on previous layer to state on next layer. The end of the path is to_state. Last layer in hashes must contain a state from which there is a transition to to_state. to_state must be in “decoded” format. Length of returned path is equal to number of layers.

validate_path(start_state: Tensor | ndarray | list, path: list[int])

Checks that path indeed is path from start_state to central state.

property with_inverted_generators

Returns copy of this graph with inverted generators.