Prufer Code

E
```use std::collections::{BTreeMap, BTreeSet, BinaryHeap};

type Graph<V> = BTreeMap<V, Vec<V>>;

pub fn prufer_encode<V: Ord + Copy>(tree: &Graph<V>) -> Vec<V> {
if tree.len() <= 2 {
return vec![];
}
let mut result: Vec<V> = Vec::new();
result.reserve(tree.len() - 2);
let mut queue = BinaryHeap::new();
let mut in_tree = BTreeSet::new();
let mut degree = BTreeMap::new();
for (vertex, adj) in tree {
in_tree.insert(*vertex);
queue.push(*vertex);
}
}
for _ in 2..tree.len() {
let v = queue.pop().unwrap();
in_tree.remove(&v);
let u = tree[&v].iter().find(|u| in_tree.contains(u)).unwrap();
result.push(*u);
*degree.get_mut(u).unwrap() -= 1;
if degree[u] == 1 {
queue.push(*u);
}
}
result
}

#[inline]
fn add_directed_edge<V: Ord + Copy>(tree: &mut Graph<V>, a: V, b: V) {
tree.entry(a).or_default().push(b);
}

#[inline]
fn add_edge<V: Ord + Copy>(tree: &mut Graph<V>, a: V, b: V) {
}

pub fn prufer_decode<V: Ord + Copy>(code: &[V], vertex_list: &[V]) -> Graph<V> {
// For many cases, this function won't fail even if given unsuitable code
// array. As such, returning really unlikely errors doesn't make much sense.
let mut result = BTreeMap::new();
let mut list_count: BTreeMap<V, usize> = BTreeMap::new();
for vertex in code {
*list_count.entry(*vertex).or_insert(0) += 1;
}
let mut queue = BinaryHeap::from(
vertex_list
.iter()
.filter(|v| !list_count.contains_key(v))
.cloned()
.collect::<Vec<V>>(),
);
for vertex in code {
let child = queue.pop().unwrap();
let cnt = list_count.get_mut(vertex).unwrap();
*cnt -= 1;
if *cnt == 0 {
queue.push(*vertex);
}
}
let u = queue.pop().unwrap();
let v = queue.pop().unwrap();
result
}

#[cfg(test)]
mod tests {

fn equal_graphs<V: Ord + Copy>(g1: &mut Graph<V>, g2: &mut Graph<V>) -> bool {
}
}
return g1 == g2;
}

#[test]
fn small_trees() {
let mut g: Graph<u32> = Graph::new();
// Binary tree with 7 vertices
let edges = vec![(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)];
for (u, v) in edges {
}
let code = prufer_encode(&g);
let vertices = g.keys().cloned().collect::<Vec<u32>>();
let mut decoded = prufer_decode(&code, &vertices);
assert_eq!(code, vec![3, 3, 2, 2, 1]);
assert!(equal_graphs(&mut g, &mut decoded));

g.clear();
// A path of length 10
for v in 2..=9 {
g.insert(v, vec![v - 1, v + 1]);
}
g.insert(1, vec![2]);
g.insert(10, vec![9]);
let code = prufer_encode(&g);
let vertices = g.keys().cloned().collect::<Vec<u32>>();
let mut decoded = prufer_decode(&code, &vertices);
assert_eq!(code, vec![9, 8, 7, 6, 5, 4, 3, 2]);
assert!(equal_graphs(&mut g, &mut decoded));

g.clear();
// 7-5-3-1-2-4-6
let edges = vec![(1, 2), (2, 4), (4, 6), (1, 3), (3, 5), (5, 7)];
for (u, v) in edges {