rustworkx.graph_token_swapper#

graph_token_swapper(graph, mapping, /, trials=None, seed=None, parallel_threshold=50)#

This module performs an approximately optimal Token Swapping algorithm Supports partial mappings (i.e. not-permutations) for graphs with missing tokens.

Based on the paper: Approximation and Hardness for Token Swapping by Miltzow et al. (2016) ArXiV: https://arxiv.org/abs/1602.05150

The inputs are a partial mapping to be implemented in swaps, and the number of trials to perform the mapping. It’s minimized over the trials.

It returns a list of tuples representing the swaps to perform.

Parameters:

  • graph (PyGraph) – The input graph

  • dict[int – int] mapping: Map of (node, token)

  • trials (int) – The number of trials to run

  • seed (int) – The random seed to be used in producing random ints for selecting which nodes to process next

  • parallel_threshold (int) – The number of nodes in the graph that will trigger the use of parallel threads. If the number of nodes in the graph is less than this value it will run in a single thread. The default value is 50.

This function is multithreaded and will launch a thread pool with threads equal to the number of CPUs by default. You can tune the number of threads with the RAYON_NUM_THREADS environment variable. For example, setting RAYON_NUM_THREADS=4 would limit the thread pool to 4 threads.

Returns:

A list of tuples which are the swaps to be applied to the mapping to rearrange the tokens.

Return type:

EdgeList