cayleypy.CayleyGraph

class cayleypy.CayleyGraph[source]

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)[source]

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_path(states, generator_ids)

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

beam_search(*, start_state[, predictor, ...])

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.

free_memory()

get_neighbors(states)

Calculates all neighbors of states (in internal representation).

get_neighbors_decoded(states)

Calculates neighbors in decoded (external) representation.

random_walks(*[, width, length, mode, ...])

Generates random walks on this graph.

to_networkx_graph()

Attributes

generators

Generators of this Cayley graph.
apply_path(states: Tensor, generator_ids: list[int]) → Tensor[source]

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.

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

Parameters:

  • start_state – State from which to star search.

  • predictor – A heuristic that estimates scores for states (lower score = closer to center). Defaults to Hamming distance heuristic.

  • beam_width – Width of the beam (how many “best” states we consider at each step”.

  • max_iterations – Maximum number of iterations before giving up.

  • return_path – Whether to return parth (consumes much more memory if True).

Returns:

BeamSearchResult containing found path length and 9optionally) the path itself.

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

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).

Returns:

BfsResult object with requested BFS results.

decode_states(states: Tensor) → Tensor[source]

Converts states from internal to human-readable representation.

encode_states(states: Tensor | ndarray | list) → Tensor[source]

Converts states from human-readable to internal representation.

property generators

Generators of this Cayley graph.

get_neighbors(states: Tensor) → Tensor[source]

Calculates all neighbors of states (in internal representation).

get_neighbors_decoded(states: Tensor) → Tensor[source]

Calculates neighbors in decoded (external) representation.

random_walks(*, width=5, length=10, mode='classic', start_state: None | Tensor | ndarray | list = None) → tuple[Tensor, Tensor][source]

Generates random walks on this graph.

The following modes of random walk generation are supported:

  • “classic” - random walk is a path in this graph starting from start_state, where on each step the next edge is chosen randomly with equal probability. We generate width such random walks independently. The output will have exactly width*length states. i-th random walk can be extracted as: [x[i+j*width] for j in range(length)]. y[i] is equal to number of random steps it took to get to state x[i]. Note that in this mode a lot of states will have overestimated distance (meaning y[i] may be larger than the length of the shortest path from x[i] to start_state). The same state may appear multiple times with different distance in y.

  • “bfs” - we perform Breadth First Search starting from start_state with one modification: if size of next layer is larger than width, only width states (chosen randomly) will be kept. We also remove states from current layer if they appeared on some previous layer (so this also can be called “non-backtracking random walk”). All states in the output are unique. y still can be overestimated, but it will be closer to the true distance than in “classic” mode. Size of output is <= width*length. If width and length are large enough (width at least as large as largest BFS layer, and length >= diameter), this will return all states and true distances to the start state.

Parameters:

  • width – Number of random walks to generate.

  • length – Length of each random walk.

  • start_state – State from which to start random walk. Defaults to the central state.

  • mode – Type of random walk (see above). Defaults to “classic”.

Returns:

Pair of tensors x, y. x contains states. y[i] is the estimated distance from start state to state x[i].