This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.
- 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
mappingto be implemented in swaps, and the number of
trialsto perform the mapping. It’s minimized over the trials.
It returns a list of tuples representing the swaps to perform.
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_THREADSenvironment variable. For example, setting
RAYON_NUM_THREADS=4would limit the thread pool to 4 threads.
A list of tuples which are the swaps to be applied to the mapping to rearrange the tokens.
- Return type: