rustworkx_core/
token_swapper.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use rand::prelude::*;
14use rand::rngs::SysRng;
15use rand_distr::{StandardUniform, Uniform};
16use rand_pcg::Pcg64;
17use std::error::Error;
18use std::fmt;
19use std::hash::Hash;
20
21use hashbrown::HashMap;
22use petgraph::Directed;
23use petgraph::Direction::{Incoming, Outgoing};
24use petgraph::stable_graph::{NodeIndex, StableGraph};
25use petgraph::visit::{
26    EdgeCount, GraphBase, IntoEdges, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount,
27    NodeIndexable, Visitable,
28};
29use rayon::prelude::*;
30use rayon_cond::CondIterator;
31
32use crate::connectivity::find_cycle;
33use crate::dictmap::*;
34use crate::shortest_path::dijkstra;
35use crate::traversal::dfs_edges;
36
37type Swap = (NodeIndex, NodeIndex);
38type Edge = (NodeIndex, NodeIndex);
39
40/// Error returned by token swapper if the request mapping
41/// is impossible
42#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Copy, Clone)]
43pub struct MapNotPossible;
44
45impl Error for MapNotPossible {}
46impl fmt::Display for MapNotPossible {
47    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
48        write!(f, "No mapping possible.")
49    }
50}
51
52struct TokenSwapper<G: GraphBase>
53where
54    G::NodeId: Eq + Hash,
55{
56    // The input graph
57    graph: G,
58    // The user-supplied mapping to use for swapping tokens
59    mapping: HashMap<G::NodeId, G::NodeId>,
60    // Number of trials
61    trials: usize,
62    // Seed for random selection of a node for a trial
63    seed: Option<u64>,
64    // Threshold for how many nodes will trigger parallel iterator
65    parallel_threshold: usize,
66    // Map of NodeId to NodeIndex
67    node_map: HashMap<G::NodeId, NodeIndex>,
68    // Map of NodeIndex to NodeId
69    rev_node_map: HashMap<NodeIndex, G::NodeId>,
70}
71
72impl<G> TokenSwapper<G>
73where
74    G: NodeCount
75        + EdgeCount
76        + IntoEdges
77        + Visitable
78        + NodeIndexable
79        + IntoNeighborsDirected
80        + IntoNodeIdentifiers
81        + Send
82        + Sync,
83    G::NodeId: Hash + Eq + Send + Sync,
84{
85    fn new(
86        graph: G,
87        mapping: HashMap<G::NodeId, G::NodeId>,
88        trials: Option<usize>,
89        seed: Option<u64>,
90        parallel_threshold: Option<usize>,
91    ) -> Self {
92        TokenSwapper {
93            graph,
94            mapping,
95            trials: trials.unwrap_or(4),
96            seed,
97            parallel_threshold: parallel_threshold.unwrap_or(50),
98            node_map: HashMap::with_capacity(graph.node_count()),
99            rev_node_map: HashMap::with_capacity(graph.node_count()),
100        }
101    }
102
103    fn map(&mut self) -> Result<Vec<Swap>, MapNotPossible> {
104        let num_nodes = self.graph.node_bound();
105        let num_edges = self.graph.edge_count();
106
107        // Directed graph with nodes matching ``graph`` and
108        // edges for neighbors closer than nodes
109        let mut digraph = StableGraph::with_capacity(num_nodes, num_edges);
110
111        // First fill the digraph with nodes. Then since it's a stable graph,
112        // must go through and remove nodes that were removed in original graph
113        for _ in 0..self.graph.node_bound() {
114            digraph.add_node(());
115        }
116        let mut count: usize = 0;
117        for gnode in self.graph.node_identifiers() {
118            let gidx = self.graph.to_index(gnode);
119            if gidx != count {
120                for idx in count..gidx {
121                    digraph.remove_node(NodeIndex::new(idx));
122                }
123                count = gidx;
124            }
125            count += 1;
126        }
127
128        // Create maps between NodeId and NodeIndex
129        for node in self.graph.node_identifiers() {
130            self.node_map
131                .insert(node, NodeIndex::new(self.graph.to_index(node)));
132            self.rev_node_map
133                .insert(NodeIndex::new(self.graph.to_index(node)), node);
134        }
135        // sub will become same as digraph but with no self edges in add_token_edges
136        let mut sub_digraph = digraph.clone();
137
138        // The mapping in HashMap form using NodeIndex
139        let mut tokens: HashMap<NodeIndex, NodeIndex> = self
140            .mapping
141            .iter()
142            .map(|(k, v)| (self.node_map[k], self.node_map[v]))
143            .collect();
144
145        // todo_nodes are all the mapping entries where left != right
146        let mut todo_nodes: Vec<NodeIndex> = tokens
147            .iter()
148            .filter_map(|(node, dest)| if node != dest { Some(*node) } else { None })
149            .collect();
150        todo_nodes.par_sort();
151
152        // Add initial edges to the digraph/sub_digraph
153        for node in self.graph.node_identifiers() {
154            self.add_token_edges(
155                self.node_map[&node],
156                &mut digraph,
157                &mut sub_digraph,
158                &mut tokens,
159            )?;
160        }
161        // First collect the self.trial number of random numbers
162        // into a Vec based on the given seed
163        let outer_rng: Pcg64 = match self.seed {
164            Some(rng_seed) => Pcg64::seed_from_u64(rng_seed),
165            None => Pcg64::try_from_rng(&mut SysRng).unwrap(),
166        };
167        let trial_seeds_vec: Vec<u64> = outer_rng
168            .sample_iter(&StandardUniform)
169            .take(self.trials)
170            .collect();
171
172        CondIterator::new(
173            trial_seeds_vec,
174            self.graph.node_count() >= self.parallel_threshold,
175        )
176        .map(|trial_seed| {
177            self.trial_map(
178                digraph.clone(),
179                sub_digraph.clone(),
180                tokens.clone(),
181                todo_nodes.clone(),
182                trial_seed,
183            )
184        })
185        .min_by_key(|result| match result {
186            Ok(res) => Ok(res.len()),
187            Err(e) => Err(*e),
188        })
189        .unwrap()
190    }
191
192    fn add_token_edges(
193        &self,
194        node: NodeIndex,
195        digraph: &mut StableGraph<(), (), Directed>,
196        sub_digraph: &mut StableGraph<(), (), Directed>,
197        tokens: &mut HashMap<NodeIndex, NodeIndex>,
198    ) -> Result<(), MapNotPossible> {
199        // Adds an edge to digraph if distance from the token to a neighbor is
200        // less than distance from token to node. sub_digraph is same except
201        // for self-edges.
202        if !tokens.contains_key(&node) {
203            return Ok(());
204        }
205        if tokens[&node] == node {
206            digraph.update_edge(node, node, ());
207            return Ok(());
208        }
209        let id_node = self.rev_node_map[&node];
210        let id_token = self.rev_node_map[&tokens[&node]];
211
212        if self.graph.neighbors(id_node).next().is_none() {
213            return Err(MapNotPossible {});
214        }
215
216        for id_neighbor in self.graph.neighbors(id_node) {
217            let neighbor = self.node_map[&id_neighbor];
218            let dist_neighbor: DictMap<G::NodeId, usize> = dijkstra(
219                &self.graph,
220                id_neighbor,
221                Some(id_token),
222                |_| Ok::<usize, &str>(1),
223                None,
224            )
225            .unwrap();
226
227            let dist_node: DictMap<G::NodeId, usize> = dijkstra(
228                &self.graph,
229                id_node,
230                Some(id_token),
231                |_| Ok::<usize, &str>(1),
232                None,
233            )
234            .unwrap();
235            let neigh_dist = dist_neighbor.get(&id_token);
236            let node_dist = dist_node.get(&id_token);
237            if neigh_dist.is_none() {
238                return Err(MapNotPossible {});
239            }
240            if node_dist.is_none() {
241                return Err(MapNotPossible {});
242            }
243
244            if neigh_dist < node_dist {
245                digraph.update_edge(node, neighbor, ());
246                sub_digraph.update_edge(node, neighbor, ());
247            }
248        }
249        Ok(())
250    }
251
252    fn trial_map(
253        &self,
254        mut digraph: StableGraph<(), (), Directed>,
255        mut sub_digraph: StableGraph<(), (), Directed>,
256        mut tokens: HashMap<NodeIndex, NodeIndex>,
257        mut todo_nodes: Vec<NodeIndex>,
258        trial_seed: u64,
259    ) -> Result<Vec<Swap>, MapNotPossible> {
260        // Create a random trial list of swaps to move tokens to optimal positions
261        let mut steps = 0;
262        let mut swap_edges: Vec<Swap> = vec![];
263        let mut rng_seed: Pcg64 = Pcg64::seed_from_u64(trial_seed);
264        while !todo_nodes.is_empty() && steps <= 4 * digraph.node_count().pow(2) {
265            // Choose a random todo_node
266            let between = Uniform::new(0, todo_nodes.len()).map_err(|_| MapNotPossible {})?;
267            let random: usize = between.sample(&mut rng_seed);
268            let todo_node = todo_nodes[random];
269
270            // If there's a cycle in sub_digraph, add it to swap_edges and do swap
271            let cycle = find_cycle(&sub_digraph, Some(todo_node));
272            if !cycle.is_empty() {
273                for edge in cycle[1..].iter().rev() {
274                    swap_edges.push(*edge);
275                    self.swap(
276                        edge.0,
277                        edge.1,
278                        &mut digraph,
279                        &mut sub_digraph,
280                        &mut tokens,
281                        &mut todo_nodes,
282                    )?;
283                }
284                steps += cycle.len() - 1;
285            // If there's no cycle, see if there's an edge target that matches a token key.
286            // If so, add to swap_edges and do swap
287            } else {
288                let mut found = false;
289                let sub2 = &sub_digraph.clone();
290                for edge in dfs_edges(sub2, Some(todo_node)) {
291                    let new_edge = (NodeIndex::new(edge.0), NodeIndex::new(edge.1));
292                    if !tokens.contains_key(&new_edge.1) {
293                        swap_edges.push(new_edge);
294                        self.swap(
295                            new_edge.0,
296                            new_edge.1,
297                            &mut digraph,
298                            &mut sub_digraph,
299                            &mut tokens,
300                            &mut todo_nodes,
301                        )?;
302                        steps += 1;
303                        found = true;
304                        break;
305                    }
306                }
307                // If none found, look for cycle in digraph which will result in
308                // an unhappy node. Look for a predecessor and add node and pred
309                // to swap_edges and do swap
310                if !found {
311                    let cycle: Vec<Edge> = find_cycle(&digraph, Some(todo_node));
312                    let unhappy_node = cycle[0].0;
313                    let mut found = false;
314                    let di2 = &mut digraph.clone();
315                    for predecessor in di2.neighbors_directed(unhappy_node, Incoming) {
316                        if predecessor != unhappy_node {
317                            swap_edges.push((unhappy_node, predecessor));
318                            self.swap(
319                                unhappy_node,
320                                predecessor,
321                                &mut digraph,
322                                &mut sub_digraph,
323                                &mut tokens,
324                                &mut todo_nodes,
325                            )?;
326                            steps += 1;
327                            found = true;
328                            break;
329                        }
330                    }
331                    assert!(
332                        found,
333                        "The token swap process has ended unexpectedly, this points to a bug in rustworkx, please open an issue."
334                    );
335                }
336            }
337        }
338        assert!(
339            todo_nodes.is_empty(),
340            "The output final swap map is incomplete, this points to a bug in rustworkx, please open an issue."
341        );
342        Ok(swap_edges)
343    }
344
345    fn swap(
346        &self,
347        node1: NodeIndex,
348        node2: NodeIndex,
349        digraph: &mut StableGraph<(), (), Directed>,
350        sub_digraph: &mut StableGraph<(), (), Directed>,
351        tokens: &mut HashMap<NodeIndex, NodeIndex>,
352        todo_nodes: &mut Vec<NodeIndex>,
353    ) -> Result<(), MapNotPossible> {
354        // Get token values for the 2 nodes and remove them
355        let token1 = tokens.remove(&node1);
356        let token2 = tokens.remove(&node2);
357
358        // Swap the token edge values
359        if let Some(t2) = token2 {
360            tokens.insert(node1, t2);
361        }
362        if let Some(t1) = token1 {
363            tokens.insert(node2, t1);
364        }
365        // For each node, remove the (node, successor) from digraph and
366        // sub_digraph. Then add new token edges back in.
367        for node in [node1, node2] {
368            let edge_nodes: Vec<(NodeIndex, NodeIndex)> = digraph
369                .neighbors_directed(node, Outgoing)
370                .map(|successor| (node, successor))
371                .collect();
372            for (edge_node1, edge_node2) in edge_nodes {
373                let edge = digraph.find_edge(edge_node1, edge_node2).unwrap();
374                digraph.remove_edge(edge);
375            }
376            let edge_nodes: Vec<(NodeIndex, NodeIndex)> = sub_digraph
377                .neighbors_directed(node, Outgoing)
378                .map(|successor| (node, successor))
379                .collect();
380            for (edge_node1, edge_node2) in edge_nodes {
381                let edge = sub_digraph.find_edge(edge_node1, edge_node2).unwrap();
382                sub_digraph.remove_edge(edge);
383            }
384            self.add_token_edges(node, digraph, sub_digraph, tokens)?;
385
386            // If a node is a token key and not equal to the value, add it to todo_nodes
387            if tokens.contains_key(&node) && tokens[&node] != node {
388                if !todo_nodes.contains(&node) {
389                    todo_nodes.push(node);
390                }
391            // Otherwise if node is in todo_nodes, remove it
392            } else if todo_nodes.contains(&node) {
393                todo_nodes.swap_remove(todo_nodes.iter().position(|x| *x == node).unwrap());
394            }
395        }
396        Ok(())
397    }
398}
399
400/// Module to perform an approximately optimal Token Swapping algorithm. Supports partial
401/// mappings (i.e. not-permutations) for graphs with missing tokens.
402///
403/// Based on the paper: Approximation and Hardness for Token Swapping by Miltzow et al. (2016)
404/// ArXiV: <https://arxiv.org/abs/1602.05150>
405///
406/// Arguments:
407///
408/// * `graph` - The graph on which to perform the token swapping.
409/// * `mapping` - A partial mapping to be implemented in swaps.
410/// * `trials` - Optional number of trials. If None, defaults to 4.
411/// * `seed` - Optional integer seed. If None, the internal rng will be initialized from system entropy.
412/// * `parallel_threshold` - Optional integer for the number of nodes in the graph that will
413///   trigger the use of parallel threads. If the number of nodes in the graph is less than this value
414///   it will run in a single thread. The default value is 50.
415///
416/// It returns a list of tuples representing the swaps to perform. The result will be an
417/// `Err(MapNotPossible)` if the `token_swapper()` function can't find a mapping.
418///
419/// This function is multithreaded and will launch a thread pool with threads equal to
420/// the number of CPUs by default. You can tune the number of threads with
421/// the ``RAYON_NUM_THREADS`` environment variable. For example, setting ``RAYON_NUM_THREADS=4``
422/// would limit the thread pool to 4 threads.
423///
424/// # Example
425/// ```rust
426/// use hashbrown::HashMap;
427/// use rustworkx_core::petgraph;
428/// use rustworkx_core::token_swapper::token_swapper;
429/// use rustworkx_core::petgraph::graph::NodeIndex;
430///
431///  let g = petgraph::graph::UnGraph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 3)]);
432///  let mapping = HashMap::from([
433///   (NodeIndex::new(0), NodeIndex::new(0)),
434///   (NodeIndex::new(1), NodeIndex::new(3)),
435///   (NodeIndex::new(3), NodeIndex::new(1)),
436///   (NodeIndex::new(2), NodeIndex::new(2)),
437///  ]);
438///  // Do the token swap
439///  let output = token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("Swap mapping failed.");
440///  assert_eq!(3, output.len());
441///
442/// ```
443pub fn token_swapper<G>(
444    graph: G,
445    mapping: HashMap<G::NodeId, G::NodeId>,
446    trials: Option<usize>,
447    seed: Option<u64>,
448    parallel_threshold: Option<usize>,
449) -> Result<Vec<Swap>, MapNotPossible>
450where
451    G: NodeCount
452        + EdgeCount
453        + IntoEdges
454        + Visitable
455        + NodeIndexable
456        + IntoNeighborsDirected
457        + IntoNodeIdentifiers
458        + Send
459        + Sync,
460    G::NodeId: Hash + Eq + Send + Sync,
461{
462    let mut swapper = TokenSwapper::new(graph, mapping, trials, seed, parallel_threshold);
463    swapper.map()
464}
465
466#[cfg(test)]
467mod test_token_swapper {
468
469    use crate::petgraph;
470    use crate::token_swapper::token_swapper;
471    use hashbrown::HashMap;
472    use petgraph::graph::NodeIndex;
473
474    fn do_swap(mapping: &mut HashMap<NodeIndex, NodeIndex>, swaps: &Vec<(NodeIndex, NodeIndex)>) {
475        // Apply the swaps to the mapping to get final result
476        for (swap1, swap2) in swaps {
477            //Need to create temp nodes in case of partial mapping
478            let mut temp_node1: Option<NodeIndex> = None;
479            let mut temp_node2: Option<NodeIndex> = None;
480            if mapping.contains_key(swap1) {
481                temp_node1 = Some(mapping[swap1]);
482                mapping.remove(swap1);
483            }
484            if mapping.contains_key(swap2) {
485                temp_node2 = Some(mapping[swap2]);
486                mapping.remove(swap2);
487            }
488            if let Some(t1) = temp_node1 {
489                mapping.insert(*swap2, t1);
490            }
491            if let Some(t2) = temp_node2 {
492                mapping.insert(*swap1, t2);
493            }
494        }
495    }
496
497    #[test]
498    fn test_simple_swap() {
499        // Simple arbitrary swap
500        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
501        let mapping = HashMap::from([
502            (NodeIndex::new(0), NodeIndex::new(0)),
503            (NodeIndex::new(1), NodeIndex::new(3)),
504            (NodeIndex::new(3), NodeIndex::new(1)),
505            (NodeIndex::new(2), NodeIndex::new(2)),
506        ]);
507        let swaps = token_swapper(&g, mapping, Some(4), Some(4), Some(50));
508        assert_eq!(3, swaps.expect("swap mapping errored").len());
509    }
510
511    #[test]
512    fn test_small_swap() {
513        // Reverse all small swap
514        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([
515            (0, 1),
516            (1, 2),
517            (2, 3),
518            (3, 4),
519            (4, 5),
520            (5, 6),
521            (6, 7),
522        ]);
523        let mut mapping = HashMap::with_capacity(8);
524        for i in 0..8 {
525            mapping.insert(NodeIndex::new(i), NodeIndex::new(7 - i));
526        }
527        // Do the token swap
528        let mut new_map = mapping.clone();
529        let swaps =
530            token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("swap mapping errored");
531        do_swap(&mut new_map, &swaps);
532        let mut expected = HashMap::with_capacity(8);
533        for i in 0..8 {
534            expected.insert(NodeIndex::new(i), NodeIndex::new(i));
535        }
536        assert_eq!(expected, new_map);
537    }
538
539    #[test]
540    fn test_happy_swap_chain() {
541        // Reverse all happy swap chain > 2
542        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([
543            (0, 1),
544            (0, 2),
545            (0, 3),
546            (0, 4),
547            (1, 2),
548            (1, 3),
549            (1, 4),
550            (2, 3),
551            (2, 4),
552            (3, 4),
553            (3, 6),
554        ]);
555        let mapping = HashMap::from([
556            (NodeIndex::new(0), NodeIndex::new(4)),
557            (NodeIndex::new(1), NodeIndex::new(0)),
558            (NodeIndex::new(2), NodeIndex::new(3)),
559            (NodeIndex::new(3), NodeIndex::new(6)),
560            (NodeIndex::new(4), NodeIndex::new(2)),
561            (NodeIndex::new(6), NodeIndex::new(1)),
562        ]);
563        // Do the token swap
564        let mut new_map = mapping.clone();
565        let swaps =
566            token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("swap mapping errored");
567        do_swap(&mut new_map, &swaps);
568        let mut expected = HashMap::with_capacity(6);
569        for i in (0..5).chain(6..7) {
570            expected.insert(NodeIndex::new(i), NodeIndex::new(i));
571        }
572        assert_eq!(expected, new_map);
573    }
574
575    #[test]
576    fn test_partial_simple() {
577        // Simple partial swap
578        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
579        let mapping = HashMap::from([(NodeIndex::new(0), NodeIndex::new(3))]);
580        let mut new_map = mapping.clone();
581        let swaps =
582            token_swapper(&g, mapping, Some(4), Some(4), Some(1)).expect("swap mapping errored");
583        do_swap(&mut new_map, &swaps);
584        let mut expected = HashMap::with_capacity(4);
585        expected.insert(NodeIndex::new(3), NodeIndex::new(3));
586        assert_eq!(expected, new_map);
587    }
588
589    #[test]
590    fn test_partial_simple_remove_node() {
591        // Simple partial swap
592        let mut g =
593            petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3), (3, 4)]);
594        let mapping = HashMap::from([(NodeIndex::new(0), NodeIndex::new(3))]);
595        g.remove_node(NodeIndex::new(2));
596        g.add_edge(NodeIndex::new(1), NodeIndex::new(3), ());
597        let mut new_map = mapping.clone();
598        let swaps =
599            token_swapper(&g, mapping, Some(4), Some(4), Some(1)).expect("swap mapping errored");
600        do_swap(&mut new_map, &swaps);
601        let mut expected = HashMap::with_capacity(4);
602        expected.insert(NodeIndex::new(3), NodeIndex::new(3));
603        assert_eq!(expected, new_map);
604    }
605
606    #[test]
607    fn test_partial_small() {
608        // Partial inverting on small path graph
609        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
610        let mapping = HashMap::from([
611            (NodeIndex::new(0), NodeIndex::new(3)),
612            (NodeIndex::new(1), NodeIndex::new(2)),
613        ]);
614        let mut new_map = mapping.clone();
615        let swaps =
616            token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("swap mapping errored");
617        do_swap(&mut new_map, &swaps);
618        let expected = HashMap::from([
619            (NodeIndex::new(2), NodeIndex::new(2)),
620            (NodeIndex::new(3), NodeIndex::new(3)),
621        ]);
622        assert_eq!(5, swaps.len());
623        assert_eq!(expected, new_map);
624    }
625
626    #[test]
627    fn test_large_partial_random() {
628        // Test a random (partial) mapping on a large randomly generated graph
629        use crate::generators::gnm_random_graph;
630        use rand::prelude::*;
631        use rand_pcg::Pcg64;
632        use std::iter::zip;
633
634        let mut rng: Pcg64 = Pcg64::seed_from_u64(4);
635
636        // Note that graph may have "gaps" in the node counts, i.e. the numbering is noncontiguous.
637        let size = 100;
638        let mut g: petgraph::stable_graph::StableGraph<(), ()> =
639            gnm_random_graph(size, size.pow(2) / 10, Some(4), || (), || ()).unwrap();
640
641        // Remove self-loops
642        let nodes: Vec<_> = g.node_indices().collect();
643        for node in nodes {
644            if let Some(edge) = g.find_edge(node, node) {
645                g.remove_edge(edge);
646            }
647        }
648        // Make sure the graph is connected by adding C_n
649        for i in 0..(g.node_count() - 1) {
650            g.add_edge(NodeIndex::new(i), NodeIndex::new(i + 1), ());
651        }
652
653        // Get node indices and randomly shuffle
654        let mut mapped_nodes: Vec<usize> = g.node_indices().map(|node| node.index()).collect();
655        let nodes = mapped_nodes.clone();
656        mapped_nodes.shuffle(&mut rng);
657
658        // Zip nodes and shuffled nodes and remove every other one
659        let mut mapping: Vec<(usize, usize)> = zip(nodes, mapped_nodes).collect();
660        mapping.retain(|(a, _)| a % 2 == 0);
661
662        // Convert mapping to HashMap of NodeIndex's
663        let mapping: HashMap<NodeIndex, NodeIndex> = mapping
664            .into_iter()
665            .map(|(a, b)| (NodeIndex::new(a), NodeIndex::new(b)))
666            .collect();
667        let mut new_map = mapping.clone();
668        let expected: HashMap<NodeIndex, NodeIndex> =
669            mapping.values().map(|val| (*val, *val)).collect();
670
671        let swaps =
672            token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("swap mapping errored");
673        do_swap(&mut new_map, &swaps);
674        assert_eq!(expected, new_map)
675    }
676
677    #[test]
678    fn test_disjoint_graph_works() {
679        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (2, 3)]);
680        let mapping = HashMap::from([
681            (NodeIndex::new(1), NodeIndex::new(0)),
682            (NodeIndex::new(0), NodeIndex::new(1)),
683            (NodeIndex::new(2), NodeIndex::new(3)),
684            (NodeIndex::new(3), NodeIndex::new(2)),
685        ]);
686        let mut new_map = mapping.clone();
687        let swaps =
688            token_swapper(&g, mapping, Some(10), Some(4), Some(50)).expect("swap mapping errored");
689        do_swap(&mut new_map, &swaps);
690        let expected = HashMap::from([
691            (NodeIndex::new(2), NodeIndex::new(2)),
692            (NodeIndex::new(3), NodeIndex::new(3)),
693            (NodeIndex::new(1), NodeIndex::new(1)),
694            (NodeIndex::new(0), NodeIndex::new(0)),
695        ]);
696        assert_eq!(2, swaps.len());
697        assert_eq!(expected, new_map);
698    }
699
700    #[test]
701    fn test_disjoint_graph_fails() {
702        let g = petgraph::graph::UnGraph::<(), ()>::from_edges([(0, 1), (2, 3)]);
703        let mapping = HashMap::from([
704            (NodeIndex::new(2), NodeIndex::new(0)),
705            (NodeIndex::new(1), NodeIndex::new(1)),
706            (NodeIndex::new(0), NodeIndex::new(2)),
707            (NodeIndex::new(3), NodeIndex::new(3)),
708        ]);
709        assert!(
710            token_swapper(&g, mapping, Some(10), Some(4), Some(50)).is_err(),
711            "This should error"
712        );
713    }
714
715    #[test]
716    fn test_edgeless_graph_fails() {
717        let mut g = petgraph::graph::UnGraph::<(), ()>::new_undirected();
718        let a = g.add_node(());
719        let b = g.add_node(());
720        let c = g.add_node(());
721        let d = g.add_node(());
722        g.add_edge(c, d, ());
723        let mapping = HashMap::from([(a, b), (b, a)]);
724        assert!(
725            token_swapper(&g, mapping, Some(10), Some(4), Some(50)).is_err(),
726            "This should error"
727        );
728    }
729}
rustworkx_core/token_swapper.rs

rustworkx_core/
token_swapper.rs
