cayleypy.algo.MeetInTheMiddle

class cayleypy.algo.MeetInTheMiddle[source]

Meet-in-the middle (MITM) algorithm for path finding.

__init__()

Methods

__init__()

find_path_between(graph, start_states, ...)

Finds shortest path between two sets of states using MITM algorithm.

find_path_from(graph, start_state, bfs_result)

Finds path from start_state to central state using MITM algorithm and precomputed BFS result.

find_path_to(graph, dest_state, bfs_result)

Finds path from central state to dest_state using MITM algorithm and precomputed BFS result.
static find_path_between(graph: CayleyGraph, start_states: Tensor | ndarray | list, dest_states: Tensor | ndarray | list, max_diameter: int = 1000000000) → CayleyPath | None[source]

Finds shortest path between two sets of states using MITM algorithm.

Finds such x in start_states and y in dest_states that the shortest path from x to y is the shortest among all such paths and returns that path.

If the shortest path exists and has length <= 2*max_diameter, this algorithm is guaranteed to find the shortest path. Otherwise, it returns None.

The difference from find_path_from and find_path_to is that this version of algorithm computes BFS layers from both sides synchronously. Also, it supports finding paths between sets of states.

Note that this algorithm can also be used to find the shortest path between 2 states, you just need to pass two single states instead of sets of states

Parameters:

  • graph – Graph in which path needs to be found.

  • start_states – Set of initial states (as list or 2D tensor).

  • dest_states – Set of destination states (as list or 2D tensor).

  • max_diameter – depth of BFS.

Returns:

The found path, or None if path was not found.

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

Finds path from start_state to central state using MITM algorithm and precomputed BFS result.

This is a wrapper around find_path_to and it works only for inverse-closed generators.

static find_path_to(graph: CayleyGraph, dest_state: Tensor | ndarray | list, bfs_result: BfsResult) → list[int] | None[source]

Finds path from central state to dest_state using MITM algorithm and precomputed BFS result.

This algorithm will start BFS from dest_state and for each layer check whether it intersects with already found states in bfs_result. This BFS is done in inverted graph (graph where generators are inverses of generators in the original graph).

If shortest path has length <= 2*bfs_result.diameter(), this algorithm is guaranteed to find the shortest path. Otherwise, it returns None.

Parameters:

  • graph – Graph in which path needs to be found.

  • dest_state – Last state of the path.

  • bfs_result – precomputed partial BFS result.

Returns:

The found path (list of generator ids), or None if path was not found.