graph-tools 0.1.2

Graph tools and algorithms written in Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use super::union_find::UnionFind;
use super::heap;
use std::collections::{HashSet, HashMap};

pub fn slashburn(edges: &[(usize, usize)], n_nodes: usize, k: usize) -> Vec<usize>{

    let mut remain_edges : Vec<(usize, usize)> = edges.iter().copied().collect();
    let mut remain_nodes : HashSet<usize> = (0..n_nodes).collect();
    let mut new_node_order = vec![0usize; n_nodes];
    let mut cur_hubs = 0;
    let mut cur_spokes = n_nodes;

    let mut degrees = vec![0; n_nodes].into_boxed_slice();

    let mut uf = UnionFind::new(n_nodes);

    for (u, v) in edges{
        degrees[*u] += 1;
        degrees[*v] += 1;
    }

    loop{
        eprintln!("remain edges: {}, remain_nodes: {}", remain_edges.len(), remain_nodes.len());

        let hubs_remain = topk(k, &remain_nodes, &degrees);
        let hubset_remain : HashSet<usize> = hubs_remain.iter().copied().collect();

        remain_nodes.retain(|u| !hubset_remain.contains(u));
        
        remain_edges.retain(|(u, v)| {
            if remain_nodes.contains(u) && remain_nodes.contains(v) {
                return true;
            }
            else{
                degrees[*u] -= 1;
                degrees[*v] -= 1;
                return false;
            }
        });

        new_node_order[cur_hubs..cur_hubs + hubs_remain.len()].clone_from_slice(&hubs_remain);
        cur_hubs += hubs_remain.len();
        // hubs.extend(hubs_remain.iter());

        if remain_nodes.is_empty() {
            break;
        }
        
        let spokes_remain = find_and_remove_spokes(&remain_edges, &mut remain_nodes, &mut uf);
        
        
        new_node_order[cur_spokes-spokes_remain.len()..cur_spokes].clone_from_slice(&spokes_remain);
        cur_spokes -= spokes_remain.len();
        // spokes.extend(spokes_remain.iter().rev());

        if remain_nodes.is_empty() {
            break;
        }
    }

    assert_eq!(cur_spokes, cur_hubs);

    return new_node_order;

}

fn find_and_remove_spokes(edges: &[(usize, usize)], nodes: &mut HashSet<usize>, uf: &mut UnionFind) -> Vec<usize>{
    
    uf.reset(nodes.iter());

    for (u, v) in edges.iter() {
        uf.union(*u, *v);
    }

    let cc : Vec<usize> = nodes.iter().map(|u| uf.find(*u)).collect();
    
    let mut cc_sizes : HashMap<usize, usize> = HashMap::new();
    for c in &cc{
        *cc_sizes.entry(*c).or_insert(0) += 1;
    }

    let (gccid, gcccnt) = cc_sizes.into_iter().max_by(|(_, x), (_, y)| x.cmp(y)).expect("What the hell?");

    let mut spokes = Vec::with_capacity(nodes.len() - gcccnt);
    
    
    nodes.retain(|u| {
        if gccid == uf.find(*u) {
            true
        }
        else{
            spokes.push(*u);
            false
        }
    });

    spokes.sort_by(|a,b| uf.find(*a).cmp(&uf.find(*b)));
    
    return spokes;
}

fn topk(k: usize, keys: &HashSet<usize>, values: &[usize]) -> Vec<usize> {
    
    let k = if k < keys.len() { k } else { keys.len() }; 

    let mut key_iter = keys.iter();

    let mut heap : Vec<usize> = vec![0;k];
    for i in heap.iter_mut(){
        *i = *key_iter.next().unwrap();
    }

    heap::heapify_indices(&mut heap, &values);

    for x in key_iter{
        heap::heap_push_indices(*x, &mut heap, &values);
    }

    heap::sort_heap_indices(&mut heap, &values);

    return heap;
}