Function token_swapper

pub fn token_swapper<G>(
    graph: G,
    mapping: HashMap<G::NodeId, G::NodeId>,
    trials: Option<usize>,
    seed: Option<u64>,
    parallel_threshold: Option<usize>,
) -> Result<Vec<(NodeIndex, NodeIndex)>, MapNotPossible>
where
    G: NodeCount + EdgeCount + IntoEdges + Visitable + NodeIndexable + IntoNeighborsDirected + IntoNodeIdentifiers + Send + Sync,
    G::NodeId: Hash + Eq + Send + Sync,

Module to perform 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

Arguments:

• graph - The graph on which to perform the token swapping.
• mapping - A partial mapping to be implemented in swaps.
• trials - Optional number of trials. If None, defaults to 4.
• seed - Optional integer seed. If None, the internal rng will be initialized from system entropy.
• parallel_threshold - Optional integer for 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.

It returns a list of tuples representing the swaps to perform. The result will be an Err(MapNotPossible) if the token_swapper() function can’t find a mapping.

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.

Example

use hashbrown::HashMap;
use rustworkx_core::petgraph;
use rustworkx_core::token_swapper::token_swapper;
use rustworkx_core::petgraph::graph::NodeIndex;

 let g = petgraph::graph::UnGraph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 3)]);
 let mapping = HashMap::from([
  (NodeIndex::new(0), NodeIndex::new(0)),
  (NodeIndex::new(1), NodeIndex::new(3)),
  (NodeIndex::new(3), NodeIndex::new(1)),
  (NodeIndex::new(2), NodeIndex::new(2)),
 ]);
 // Do the token swap
 let output = token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("Swap mapping failed.");
 assert_eq!(3, output.len());