cayleypy.algo.BfsAlgorithm

class cayleypy.algo.BfsAlgorithm[source]

Basic version of the bread-first search (BFS) algorithm.

__init__()

Methods

__init__()

bfs(graph, *[, start_states, ...])

Runs bread-first search (BFS) algorithm from given start_states.
static bfs(graph: CayleyGraph, *, 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[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:

  • graph – CayleyGraph object on which to run BFS.

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