graph_tools/
tricnt.rs

1use std::cmp::Ordering;
2
3pub mod csr {
4
5    use crate::csr::CSR;
6
7    pub fn count(graph: &CSR) -> usize{
8        let mut cnt = 0usize;
9        for u in 0..graph.n_nodes() {
10            for v in graph.neighbors(u){
11                cnt += count_intersect(u, *v, graph);
12            }
13        }
14        return cnt;
15    }
16
17    pub fn count_intersect(u: usize, v: usize, graph: &CSR) -> usize {
18        let mut cnt = 0usize;
19        
20        let mut uiter = graph.neighbors(u).iter();
21        let mut viter = graph.neighbors(v).iter();
22    
23        let mut un = match uiter.next() {
24            Some(x) => x,
25            None => return cnt
26        };
27    
28        let mut vn = match viter.next() {
29            Some(x) => x,
30            None => return cnt
31        };
32    
33        loop{
34            if un < vn {
35                un = match uiter.next() {
36                    Some(x) => x,
37                    None => return cnt
38                }
39            }
40            else if un > vn {
41                vn = match viter.next() {
42                    Some(x) => x,
43                    None => return cnt
44                }
45            }
46            else {
47                cnt += 1;
48    
49                un = match uiter.next() {
50                    Some(x) => x,
51                    None => return cnt
52                };
53                vn = match viter.next() {
54                    Some(x) => x,
55                    None => return cnt
56                };
57            }
58        }
59    }
60}
61
62pub mod csbv {
63    
64    use crate::csbv::CSBV;
65
66    pub fn count(graph: &CSBV) -> usize{
67
68        let mut cnt = 0usize;
69    
70        for u in 0..graph.n_nodes() {
71            for v in graph.neighbor_iter(u) {
72                cnt += count_intersect(u, v, &graph);
73            }
74        }
75        return cnt;
76    }
77
78    pub fn count_intersect(u: usize, v: usize, graph: &CSBV) -> usize{
79        let mut cnt = 0usize;
80        
81        let mut uiter = graph.block_iter(u);
82        let mut viter = graph.block_iter(v);
83    
84        let (mut un, mut un_bits) = match uiter.next() {
85            Some(x) => x,
86            None => return cnt
87        };
88    
89        let (mut vn, mut vn_bits) = match viter.next() {
90            Some(x) => x,
91            None => return cnt
92        };
93    
94        loop{
95            if un < vn {
96                (un, un_bits) = match uiter.next() {
97                    Some(x) => x,
98                    None => return cnt
99                }
100            }
101            else if un > vn {
102                (vn, vn_bits) = match viter.next() {
103                    Some(x) => x,
104                    None => return cnt
105                }
106            }
107            else {
108                cnt += (un_bits & vn_bits).count_ones() as usize;
109    
110                    (un, un_bits) = match uiter.next() {
111                        Some(x) => x,
112                        None => return cnt
113                    };
114                    (vn, vn_bits) = match viter.next() {
115                        Some(x) => x,
116                        None => return cnt
117                    };
118            }
119        }
120    
121    }
122
123}
124
125
126pub fn count_total(adj: Vec<Vec<usize>>) -> usize{
127    let mut cnt = 0usize;
128    for adj_u in adj.iter(){
129        for v in adj_u{
130            cnt += count_intersect_btw_sorted(adj_u, &adj[*v]);
131        }
132    }
133    return cnt;
134}
135
136fn count_intersect_btw_sorted(adj_u: &Vec<usize>, adj_v: &Vec<usize>) -> usize{
137    let mut iter_u = adj_u.iter();
138    let mut iter_v = adj_v.iter();
139    let mut un = match iter_u.next() { Some(un) => un, None => return 0 };
140    let mut vn = match iter_v.next() { Some(vn) => vn, None => return 0 };
141    
142    let mut cnt = 0usize;
143
144    loop {
145        match un.cmp(vn){
146            Ordering::Less => {
147                un = match iter_u.next() { Some(un) => un, None => return cnt };
148            }
149            Ordering::Greater => {
150                vn = match iter_v.next() { Some(vn) => vn, None => return cnt };
151            }
152            Ordering::Equal => {
153                cnt += 1;
154                un = match iter_u.next() { Some(un) => un, None => return cnt };
155                vn = match iter_v.next() { Some(vn) => vn, None => return cnt };
156            }
157        };
158    }
159}
graph_tools/tricnt.rs

graph_tools/
tricnt.rs
