graph_tools/
csbv.rs

1// Compressed Sparse Bit Vectors
2pub struct CSBV{
3    pub bit_blocks: Vec<usize>,
4    pub block_ids: Vec<usize>,
5    pub ptrs: Vec<usize>
6}
7
8impl CSBV{
9
10    pub fn n_nodes(&self) -> usize{
11        return self.ptrs.len() - 1;
12    }
13
14
15    pub fn block_iter(&self, u: usize) -> NeighborBlockIterator{
16        return NeighborBlockIterator{
17            csbv: self,
18            end: self.ptrs[u+1],
19            ptr: self.ptrs[u]
20        }
21    }
22
23    pub fn neighbor_iter(&self, u: usize) -> NeighborIterator{
24        let ptr = self.ptrs[u];
25        
26        return NeighborIterator{
27            csbv: self,
28            end: self.ptrs[u+1],
29            ptr,
30            bits: match self.bit_blocks.get(ptr) { Some(x) => *x, None => 0}
31        };
32    }
33
34    // edges are sorted, and has no duplicate. Nodes in each edge is ordered.
35    pub fn from_sorted_edges(edges: &[(usize, usize)], n_nodes: usize) -> CSBV{
36        let mut u_prev = usize::MAX;
37        let mut bl_prev = usize::MAX;
38        let block_size = 64usize;
39
40        let mut n_blocks = 0usize;
41        for (u, v) in edges {
42            let bl = *v / block_size;
43            
44            if *u != u_prev {
45                u_prev = *u;
46                bl_prev = bl;
47                n_blocks += 1;
48            }
49            else if bl != bl_prev {
50                bl_prev = bl;
51                n_blocks += 1;
52            }
53        }
54
55        let mut csbv = CSBV{
56            bit_blocks: vec![0usize; n_blocks],
57            block_ids: vec![0usize; n_blocks],
58            ptrs: vec![0usize; n_nodes+1],
59        };
60
61        u_prev = usize::MAX;
62        bl_prev = usize::MAX;
63        
64        let mut bi = 0usize;
65        for (u, v) in edges {
66            let bl = *v / block_size;
67
68            if *u != u_prev {
69                u_prev = *u;
70                bl_prev = bl;
71                csbv.bit_blocks[bi] = 1usize << (*v % block_size);
72                csbv.block_ids[bi] = bl;
73                bi += 1;
74                csbv.ptrs[*u + 1] += 1; // compute degrees
75            }
76            else if bl != bl_prev {
77                bl_prev = bl;
78                csbv.bit_blocks[bi] = 1usize << (*v % block_size);
79                csbv.block_ids[bi] = bl;
80                bi += 1;
81                csbv.ptrs[*u + 1] += 1;
82            }
83            else{
84                csbv.bit_blocks[bi-1] |= 1usize << (*v % block_size);
85            }
86            
87        }
88
89        for i in 1..n_nodes {
90            csbv.ptrs[i+1] += csbv.ptrs[i];
91        }
92        // for i in (0..n_nodes).rev() {
93        //     csbv.ptrs[i+1] = csbv.ptrs[i];
94        // }
95        csbv.ptrs[0] = 0;
96
97        return csbv;
98    }
99}
100
101
102pub struct NeighborIterator<'a>{
103    csbv: &'a CSBV,
104    end: usize,
105    ptr: usize,
106    bits: usize
107}
108
109impl<'a> Iterator for NeighborIterator<'a> {
110    type Item = usize;
111    
112    fn next(&mut self) -> Option<Self::Item> {
113
114        const BLOCK_SIZE: usize = 64usize;
115        
116        if self.bits == 0 {
117            if self.ptr + 1 >= self.end { return None; }
118
119            self.ptr += 1;
120            self.bits = self.csbv.bit_blocks[self.ptr];
121        }
122
123        let offset: usize = self.bits.trailing_zeros() as usize;
124        self.bits -= 1 << offset;
125        
126        return Some(self.csbv.block_ids[self.ptr] * BLOCK_SIZE + offset);
127    }
128}
129
130
131pub struct NeighborBlockIterator<'a>{
132    csbv: &'a CSBV,
133    end: usize,
134    ptr: usize
135}
136
137impl<'a> Iterator for NeighborBlockIterator<'a>{
138    type Item = (usize, usize);
139
140    fn next(&mut self) -> Option<Self::Item> {
141
142        if self.ptr < self.end {
143            self.ptr += 1;
144            return Some( (self.csbv.block_ids[self.ptr-1], self.csbv.bit_blocks[self.ptr-1]) );
145        }
146        
147        return None;
148    }
149}
graph_tools/csbv.rs

graph_tools/
csbv.rs
