graph_tools/
slashburn.rs

1use super::union_find::UnionFind;
2use super::heap;
3use std::collections::{HashSet, HashMap};
4
5pub fn slashburn(edges: &[(usize, usize)], n_nodes: usize, k: usize) -> Vec<usize>{
6
7    let mut remain_edges : Vec<(usize, usize)> = edges.iter().copied().collect();
8    let mut remain_nodes : HashSet<usize> = (0..n_nodes).collect();
9    let mut new_node_order = vec![0usize; n_nodes];
10    let mut cur_hubs = 0;
11    let mut cur_spokes = n_nodes;
12
13    let mut degrees = vec![0; n_nodes].into_boxed_slice();
14
15    let mut uf = UnionFind::new(n_nodes);
16
17    for (u, v) in edges{
18        degrees[*u] += 1;
19        degrees[*v] += 1;
20    }
21
22    loop{
23        eprintln!("remain edges: {}, remain_nodes: {}", remain_edges.len(), remain_nodes.len());
24
25        let hubs_remain = topk(k, &remain_nodes, &degrees);
26        let hubset_remain : HashSet<usize> = hubs_remain.iter().copied().collect();
27
28        remain_nodes.retain(|u| !hubset_remain.contains(u));
29        
30        remain_edges.retain(|(u, v)| {
31            if remain_nodes.contains(u) && remain_nodes.contains(v) {
32                return true;
33            }
34            else{
35                degrees[*u] -= 1;
36                degrees[*v] -= 1;
37                return false;
38            }
39        });
40
41        new_node_order[cur_hubs..cur_hubs + hubs_remain.len()].clone_from_slice(&hubs_remain);
42        cur_hubs += hubs_remain.len();
43        // hubs.extend(hubs_remain.iter());
44
45        if remain_nodes.is_empty() {
46            break;
47        }
48        
49        let spokes_remain = find_and_remove_spokes(&remain_edges, &mut remain_nodes, &mut uf);
50        
51        
52        new_node_order[cur_spokes-spokes_remain.len()..cur_spokes].clone_from_slice(&spokes_remain);
53        cur_spokes -= spokes_remain.len();
54        // spokes.extend(spokes_remain.iter().rev());
55
56        if remain_nodes.is_empty() {
57            break;
58        }
59    }
60
61    assert_eq!(cur_spokes, cur_hubs);
62
63    return new_node_order;
64
65}
66
67fn find_and_remove_spokes(edges: &[(usize, usize)], nodes: &mut HashSet<usize>, uf: &mut UnionFind) -> Vec<usize>{
68    
69    uf.reset(nodes.iter());
70
71    for (u, v) in edges.iter() {
72        uf.union(*u, *v);
73    }
74
75    let cc : Vec<usize> = nodes.iter().map(|u| uf.find(*u)).collect();
76    
77    let mut cc_sizes : HashMap<usize, usize> = HashMap::new();
78    for c in &cc{
79        *cc_sizes.entry(*c).or_insert(0) += 1;
80    }
81
82    let (gccid, gcccnt) = cc_sizes.into_iter().max_by(|(_, x), (_, y)| x.cmp(y)).expect("What the hell?");
83
84    let mut spokes = Vec::with_capacity(nodes.len() - gcccnt);
85    
86    
87    nodes.retain(|u| {
88        if gccid == uf.find(*u) {
89            true
90        }
91        else{
92            spokes.push(*u);
93            false
94        }
95    });
96
97    spokes.sort_by(|a,b| uf.find(*a).cmp(&uf.find(*b)));
98    
99    return spokes;
100}
101
102fn topk(k: usize, keys: &HashSet<usize>, values: &[usize]) -> Vec<usize> {
103    
104    let k = if k < keys.len() { k } else { keys.len() }; 
105
106    let mut key_iter = keys.iter();
107
108    let mut heap : Vec<usize> = vec![0;k];
109    for i in heap.iter_mut(){
110        *i = *key_iter.next().unwrap();
111    }
112
113    heap::heapify_indices(&mut heap, &values);
114
115    for x in key_iter{
116        heap::heap_push_indices(*x, &mut heap, &values);
117    }
118
119    heap::sort_heap_indices(&mut heap, &values);
120
121    return heap;
122}
graph_tools/slashburn.rs

graph_tools/
slashburn.rs
