fn from_prufer_sequence(n: usize, prufer: &[usize]) -> Vec<(usize, usize)>Examples found in repository?
crates/competitive/src/tree/generator.rs (lines 9-14)
7 fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8 let n = rng.random(&self.0);
9 let edges = from_prufer_sequence(
10 n,
11 &rng.random_iter(0..n)
12 .take(n.saturating_sub(2))
13 .collect::<Vec<usize>>(),
14 );
15 UndirectedSparseGraph::from_edges(n, edges)
16 }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22 fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23 let n = rng.random(&self.0);
24 let edges = (1..n).map(|u| (u - 1, u)).collect();
25 UndirectedSparseGraph::from_edges(n, edges)
26 }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32 fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33 let n = rng.random(&self.0);
34 let edges = (1..n).map(|u| (0, u)).collect();
35 UndirectedSparseGraph::from_edges(n, edges)
36 }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42 fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43 fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44 let mut edges = Vec::with_capacity(n.saturating_sub(1));
45 if n >= 2 {
46 let k = rng.random(1..n);
47 for n in [k, n - k].iter().cloned() {
48 let ty = rng.rand(6);
49 edges.extend(match ty {
50 0 => from_prufer_sequence(
51 n,
52 &rng.random_iter(0..n)
53 .take(n.saturating_sub(2))
54 .collect::<Vec<usize>>(),
55 ),
56 1 => (1..n).map(|u| (u - 1, u)).collect(),
57 2 => (1..n).map(|u| (0, u)).collect(),
58 _ => rand_inner(n, rng),
59 });
60 }
61 for (u, v) in edges[k - 1..].iter_mut() {
62 *u += k;
63 *v += k;
64 }
65 edges.push((rng.random(0..k), rng.random(k..n)));
66 }
67 edges
68 }