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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

// Compressed Sparse Bit Vectors
pub struct CSBV{
    pub bit_blocks: Vec<usize>,
    pub block_ids: Vec<usize>,
    pub ptrs: Vec<usize>
}

impl CSBV{

    pub fn n_nodes(&self) -> usize{
        return self.ptrs.len() - 1;
    }


    pub fn block_iter(&self, u: usize) -> NeighborBlockIterator{
        return NeighborBlockIterator{
            csbv: self,
            end: self.ptrs[u+1],
            ptr: self.ptrs[u]
        }
    }

    pub fn neighbor_iter(&self, u: usize) -> NeighborIterator{
        let ptr = self.ptrs[u];
        
        return NeighborIterator{
            csbv: self,
            end: self.ptrs[u+1],
            ptr,
            bits: match self.bit_blocks.get(ptr) { Some(x) => *x, None => 0}
        };
    }

    // edges are sorted, and has no duplicate. Nodes in each edge is ordered.
    pub fn from_sorted_edges(edges: &[(usize, usize)], n_nodes: usize) -> CSBV{
        let mut u_prev = usize::MAX;
        let mut bl_prev = usize::MAX;
        let block_size = 64usize;

        let mut n_blocks = 0usize;
        for (u, v) in edges {
            let bl = *v / block_size;
            
            if *u != u_prev {
                u_prev = *u;
                bl_prev = bl;
                n_blocks += 1;
            }
            else if bl != bl_prev {
                bl_prev = bl;
                n_blocks += 1;
            }
        }

        let mut csbv = CSBV{
            bit_blocks: vec![0usize; n_blocks],
            block_ids: vec![0usize; n_blocks],
            ptrs: vec![0usize; n_nodes+1],
        };

        u_prev = usize::MAX;
        bl_prev = usize::MAX;
        
        let mut bi = 0usize;
        for (u, v) in edges {
            let bl = *v / block_size;

            if *u != u_prev {
                u_prev = *u;
                bl_prev = bl;
                csbv.bit_blocks[bi] = 1usize << (*v % block_size);
                csbv.block_ids[bi] = bl;
                bi += 1;
                csbv.ptrs[*u + 1] += 1; // compute degrees
            }
            else if bl != bl_prev {
                bl_prev = bl;
                csbv.bit_blocks[bi] = 1usize << (*v % block_size);
                csbv.block_ids[bi] = bl;
                bi += 1;
                csbv.ptrs[*u + 1] += 1;
            }
            else{
                csbv.bit_blocks[bi-1] |= 1usize << (*v % block_size);
            }
            
        }

        for i in 1..n_nodes {
            csbv.ptrs[i+1] += csbv.ptrs[i];
        }
        // for i in (0..n_nodes).rev() {
        //     csbv.ptrs[i+1] = csbv.ptrs[i];
        // }
        csbv.ptrs[0] = 0;

        return csbv;
    }
}


pub struct NeighborIterator<'a>{
    csbv: &'a CSBV,
    end: usize,
    ptr: usize,
    bits: usize
}

impl<'a> Iterator for NeighborIterator<'a> {
    type Item = usize;
    
    fn next(&mut self) -> Option<Self::Item> {

        const BLOCK_SIZE: usize = 64usize;
        
        if self.bits == 0 {
            if self.ptr + 1 >= self.end { return None; }

            self.ptr += 1;
            self.bits = self.csbv.bit_blocks[self.ptr];
        }

        let offset: usize = self.bits.trailing_zeros() as usize;
        self.bits -= 1 << offset;
        
        return Some(self.csbv.block_ids[self.ptr] * BLOCK_SIZE + offset);
    }
}


pub struct NeighborBlockIterator<'a>{
    csbv: &'a CSBV,
    end: usize,
    ptr: usize
}

impl<'a> Iterator for NeighborBlockIterator<'a>{
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {

        if self.ptr < self.end {
            self.ptr += 1;
            return Some( (self.csbv.block_ids[self.ptr-1], self.csbv.bit_blocks[self.ptr-1]) );
        }
        
        return None;
    }
}