vcsgraph/analytics/
sortsindicators.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2//
3// This software may be used and distributed according to the terms of the
4// GNU General Public License version 2 or any later version.
5//
6// Copyright 2020  Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>
7
8use crate::analytics::sorts::{index_map, NodeSort};
9use crate::graph::{Graph, GraphReadError, Parents, Revision, NULL_REVISION};
10use std::cmp::max;
11use std::collections::{HashMap, HashSet};
12use std::result::Result;
13use std::result::Result::Ok;
14
15#[derive(Debug)]
16pub struct SortIndicators {
17    pub xc: usize,
18    pub xp: usize,
19    pub xa: usize,
20    pub xf: usize,
21}
22
23pub fn sort_indicators(
24    graph: &impl Graph,
25    node_sort: &NodeSort,
26) -> Result<SortIndicators, GraphReadError> {
27    Ok(SortIndicators {
28        xc: xc(graph, node_sort)?,
29        xp: xp(graph, node_sort)?,
30        xa: xa(graph, node_sort)?,
31        xf: xf(graph, node_sort)?,
32    })
33}
34
35///// CUT-BASED INDICATORS
36
37/// X_c(s) := max_i #{ j | j<i \exists k>i s_j->s_k }
38/// where a->b := a \in parents(b)
39///
40/// The X_c indicator corresponds to the maximum number of revisions having one
41/// or more child in the other part of the cut during the iteration.
42pub fn xc(
43    graph: &impl Graph,
44    node_sort: &NodeSort,
45) -> Result<usize, GraphReadError> {
46    let mut pending_parents: HashSet<Revision> = HashSet::new();
47    pending_parents.insert(NULL_REVISION);
48    let mut max_card = pending_parents.len();
49
50    for rev in node_sort.iter().rev() {
51        pending_parents.remove(&rev);
52        max_card = max(pending_parents.len(), max_card);
53        let Parents([p1, p2]) = graph.parents(*rev)?;
54        pending_parents.insert(p1);
55        pending_parents.insert(p2);
56    }
57
58    Ok(max_card - 1) // -1 to exclude NULL_REVISION
59}
60
61/// X_p(s) := max_i #{ k | k>i \exists j<i s_j->s_k }
62/// where a->b := a \in parents(b)
63///
64/// The X_p indicator corresponds to the maximum number of revisions
65/// simultaneously having one or more parent in the other part of the cut
66/// during the iteration.
67pub fn xp(
68    graph: &impl Graph,
69    node_sort: &NodeSort,
70) -> Result<usize, GraphReadError> {
71    let sort_indices = index_map(node_sort);
72    let mut max_card = 0;
73    let mut referenced_child_count = 0;
74    let mut child_count_by_rev = HashMap::with_capacity(node_sort.len());
75
76    for i in (1..node_sort.len()).rev() {
77        let rev = node_sort[i];
78        let next_rev = node_sort[i - 1];
79
80        referenced_child_count -= child_count_by_rev.get(&rev).unwrap_or(&0);
81        max_card = max(referenced_child_count, max_card);
82
83        match graph.parents(rev)? {
84            Parents([NULL_REVISION, NULL_REVISION]) => {}
85            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => {
86                if p != next_rev {
87                    referenced_child_count += 1;
88                    *child_count_by_rev.entry(p).or_insert(0) += 1;
89                }
90            }
91            Parents([p1, p2]) => {
92                if p1 != next_rev || p2 != next_rev {
93                    referenced_child_count += 1;
94                    if sort_indices[&p1] < sort_indices[&p2] {
95                        *child_count_by_rev.entry(p1).or_insert(0) += 1;
96                    } else {
97                        *child_count_by_rev.entry(p2).or_insert(0) += 1;
98                    }
99                }
100            }
101        }
102    }
103
104    Ok(max_card)
105}
106
107/// X_a(s) := max_i #{ (j,k) | j<i<k s_j->s_k }
108/// where a->b := a \in parents(b)
109///
110/// The X_a indicator corresponds to the maximum number of arcs linking parents
111/// and children crossed by the cut during the iteration.
112pub fn xa(
113    graph: &impl Graph,
114    node_sort: &NodeSort,
115) -> Result<usize, GraphReadError> {
116    let mut max_card = 0;
117    let mut referenced_child_count = 0;
118    let mut child_count_by_rev = HashMap::with_capacity(node_sort.len());
119
120    for i in (1..node_sort.len()).rev() {
121        let rev = node_sort[i];
122        let next_rev = node_sort[i - 1];
123
124        referenced_child_count -= child_count_by_rev.get(&rev).unwrap_or(&0);
125        max_card = max(referenced_child_count, max_card);
126
127        let Parents([p1, p2]) = graph.parents(rev)?;
128
129        if p1 != NULL_REVISION && p1 != next_rev {
130            *child_count_by_rev.entry(p1).or_insert(0) += 1;
131            referenced_child_count += 1;
132        }
133
134        if p2 != NULL_REVISION && p2 != next_rev && p2 != p1 {
135            *child_count_by_rev.entry(p2).or_insert(0) += 1;
136            referenced_child_count += 1;
137        }
138    }
139
140    Ok(max_card)
141}
142
143/// X_f(s) := max_i #{ k | i<k \forall j s_j->s_k => j<i }
144/// where a->b := a \in parents(b)
145///
146/// The X_f indicator corresponds to the maximum number of revisions for which
147/// all parents are on the other side of the cut during the iteration.
148/// It is similar to the X_p indicator but for nodes that have all parents on
149/// the other side.
150pub fn xf(
151    graph: &impl Graph,
152    node_sort: &NodeSort,
153) -> Result<usize, GraphReadError> {
154    let mut pending_children: HashSet<Revision> = HashSet::new();
155    let mut max_card = 0;
156
157    for rev in node_sort.iter().rev() {
158        pending_children
159            .retain(|child| !graph.parents(*child).unwrap().contains(*rev));
160        max_card = max(pending_children.len(), max_card);
161        pending_children.insert(*rev);
162    }
163
164    Ok(max_card)
165}
166
167#[cfg(test)]
168mod tests {
169    use crate::analytics::sorts::{stable_sort, NodeSort};
170    use crate::analytics::sortsindicators::{xa, xc, xf, xp};
171    use crate::graph::{Graph, Revision, SizedGraph, StableOrderGraph};
172    use crate::testing::graph_io::read_graph;
173    use crate::testing::ordering::NodeIDComparator;
174    use std::io::{BufRead, Cursor};
175
176    fn make_dummy_graph() -> impl Graph + SizedGraph + StableOrderGraph {
177        // rnd2.graph
178        let def = "
1790000000000000000000000000000000000000100 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000
1800000000000000000000000000000000000000101 0000000000000000000000000000000000000100 0000000000000000000000000000000000000000
1810000000000000000000000000000000000000102 0000000000000000000000000000000000000100 0000000000000000000000000000000000000101
1820000000000000000000000000000000000000103 0000000000000000000000000000000000000102 0000000000000000000000000000000000000100
1830000000000000000000000000000000000000104 0000000000000000000000000000000000000103 0000000000000000000000000000000000000000
1840000000000000000000000000000000000000105 0000000000000000000000000000000000000101 0000000000000000000000000000000000000100
1850000000000000000000000000000000000000106 0000000000000000000000000000000000000100 0000000000000000000000000000000000000000
1860000000000000000000000000000000000000107 0000000000000000000000000000000000000101 0000000000000000000000000000000000000100
1870000000000000000000000000000000000000108 0000000000000000000000000000000000000105 0000000000000000000000000000000000000103
1880000000000000000000000000000000000000109 0000000000000000000000000000000000000107 0000000000000000000000000000000000000000
1890000000000000000000000000000000000000110 0000000000000000000000000000000000000108 0000000000000000000000000000000000000109
1900000000000000000000000000000000000000111 0000000000000000000000000000000000000108 0000000000000000000000000000000000000110
1910000000000000000000000000000000000000112 0000000000000000000000000000000000000104 0000000000000000000000000000000000000000
1920000000000000000000000000000000000000113 0000000000000000000000000000000000000102 0000000000000000000000000000000000000000
1930000000000000000000000000000000000000114 0000000000000000000000000000000000000109 0000000000000000000000000000000000000106
1940000000000000000000000000000000000000115 0000000000000000000000000000000000000102 0000000000000000000000000000000000000000
1950000000000000000000000000000000000000116 0000000000000000000000000000000000000105 0000000000000000000000000000000000000000
1960000000000000000000000000000000000000117 0000000000000000000000000000000000000105 0000000000000000000000000000000000000000
1970000000000000000000000000000000000000118 0000000000000000000000000000000000000101 0000000000000000000000000000000000000101
1980000000000000000000000000000000000000119 0000000000000000000000000000000000000101 0000000000000000000000000000000000000000
1990000000000000000000000000000000000000120 0000000000000000000000000000000000000119 0000000000000000000000000000000000000105
2000000000000000000000000000000000000000121 0000000000000000000000000000000000000109 0000000000000000000000000000000000000108
2010000000000000000000000000000000000000122 0000000000000000000000000000000000000103 0000000000000000000000000000000000000000
2020000000000000000000000000000000000000123 0000000000000000000000000000000000000106 0000000000000000000000000000000000000000
2030000000000000000000000000000000000000124 0000000000000000000000000000000000000112 0000000000000000000000000000000000000115
2040000000000000000000000000000000000000125 0000000000000000000000000000000000000118 0000000000000000000000000000000000000124
2050000000000000000000000000000000000000126 0000000000000000000000000000000000000120 0000000000000000000000000000000000000000
2060000000000000000000000000000000000000127 0000000000000000000000000000000000000100 0000000000000000000000000000000000000103
2070000000000000000000000000000000000000128 0000000000000000000000000000000000000123 0000000000000000000000000000000000000120
2080000000000000000000000000000000000000129 0000000000000000000000000000000000000103 0000000000000000000000000000000000000105
2090000000000000000000000000000000000000130 0000000000000000000000000000000000000101 0000000000000000000000000000000000000000
2100000000000000000000000000000000000000131 0000000000000000000000000000000000000100 0000000000000000000000000000000000000000
2110000000000000000000000000000000000000132 0000000000000000000000000000000000000106 0000000000000000000000000000000000000100
2120000000000000000000000000000000000000133 0000000000000000000000000000000000000107 0000000000000000000000000000000000000000
2130000000000000000000000000000000000000134 0000000000000000000000000000000000000114 0000000000000000000000000000000000000000
2140000000000000000000000000000000000000135 0000000000000000000000000000000000000107 0000000000000000000000000000000000000130
2150000000000000000000000000000000000000136 0000000000000000000000000000000000000104 0000000000000000000000000000000000000000
2160000000000000000000000000000000000000137 0000000000000000000000000000000000000121 0000000000000000000000000000000000000000
2170000000000000000000000000000000000000138 0000000000000000000000000000000000000135 0000000000000000000000000000000000000000
2180000000000000000000000000000000000000139 0000000000000000000000000000000000000131 0000000000000000000000000000000000000114
2190000000000000000000000000000000000000140 0000000000000000000000000000000000000135 0000000000000000000000000000000000000135
2200000000000000000000000000000000000000141 0000000000000000000000000000000000000140 0000000000000000000000000000000000000101
2210000000000000000000000000000000000000142 0000000000000000000000000000000000000141 0000000000000000000000000000000000000102
2220000000000000000000000000000000000000143 0000000000000000000000000000000000000142 0000000000000000000000000000000000000103
2230000000000000000000000000000000000000144 0000000000000000000000000000000000000143 0000000000000000000000000000000000000104
2240000000000000000000000000000000000000145 0000000000000000000000000000000000000144 0000000000000000000000000000000000000105
2250000000000000000000000000000000000000146 0000000000000000000000000000000000000145 0000000000000000000000000000000000000106
2260000000000000000000000000000000000000147 0000000000000000000000000000000000000146 0000000000000000000000000000000000000107
2270000000000000000000000000000000000000148 0000000000000000000000000000000000000147 0000000000000000000000000000000000000108
2280000000000000000000000000000000000000149 0000000000000000000000000000000000000148 0000000000000000000000000000000000000109
2290000000000000000000000000000000000000150 0000000000000000000000000000000000000149 0000000000000000000000000000000000000110
2300000000000000000000000000000000000000151 0000000000000000000000000000000000000150 0000000000000000000000000000000000000111
2310000000000000000000000000000000000000152 0000000000000000000000000000000000000151 0000000000000000000000000000000000000112
2320000000000000000000000000000000000000153 0000000000000000000000000000000000000152 0000000000000000000000000000000000000113
2330000000000000000000000000000000000000154 0000000000000000000000000000000000000153 0000000000000000000000000000000000000114
2340000000000000000000000000000000000000155 0000000000000000000000000000000000000154 0000000000000000000000000000000000000115
2350000000000000000000000000000000000000156 0000000000000000000000000000000000000155 0000000000000000000000000000000000000116
2360000000000000000000000000000000000000157 0000000000000000000000000000000000000156 0000000000000000000000000000000000000117
2370000000000000000000000000000000000000158 0000000000000000000000000000000000000157 0000000000000000000000000000000000000118
2380000000000000000000000000000000000000159 0000000000000000000000000000000000000158 0000000000000000000000000000000000000119
2390000000000000000000000000000000000000160 0000000000000000000000000000000000000159 0000000000000000000000000000000000000120
2400000000000000000000000000000000000000161 0000000000000000000000000000000000000160 0000000000000000000000000000000000000121
2410000000000000000000000000000000000000162 0000000000000000000000000000000000000161 0000000000000000000000000000000000000122
2420000000000000000000000000000000000000163 0000000000000000000000000000000000000162 0000000000000000000000000000000000000123
2430000000000000000000000000000000000000164 0000000000000000000000000000000000000163 0000000000000000000000000000000000000124
2440000000000000000000000000000000000000165 0000000000000000000000000000000000000164 0000000000000000000000000000000000000125
2450000000000000000000000000000000000000166 0000000000000000000000000000000000000165 0000000000000000000000000000000000000126
2460000000000000000000000000000000000000167 0000000000000000000000000000000000000166 0000000000000000000000000000000000000127
2470000000000000000000000000000000000000168 0000000000000000000000000000000000000167 0000000000000000000000000000000000000128
2480000000000000000000000000000000000000169 0000000000000000000000000000000000000168 0000000000000000000000000000000000000129
2490000000000000000000000000000000000000170 0000000000000000000000000000000000000169 0000000000000000000000000000000000000130
2500000000000000000000000000000000000000171 0000000000000000000000000000000000000170 0000000000000000000000000000000000000131
2510000000000000000000000000000000000000172 0000000000000000000000000000000000000171 0000000000000000000000000000000000000132
2520000000000000000000000000000000000000173 0000000000000000000000000000000000000172 0000000000000000000000000000000000000133
2530000000000000000000000000000000000000174 0000000000000000000000000000000000000173 0000000000000000000000000000000000000134
2540000000000000000000000000000000000000175 0000000000000000000000000000000000000174 0000000000000000000000000000000000000135
2550000000000000000000000000000000000000176 0000000000000000000000000000000000000175 0000000000000000000000000000000000000136
2560000000000000000000000000000000000000177 0000000000000000000000000000000000000176 0000000000000000000000000000000000000137
2570000000000000000000000000000000000000178 0000000000000000000000000000000000000177 0000000000000000000000000000000000000138
2580000000000000000000000000000000000000179 0000000000000000000000000000000000000178 0000000000000000000000000000000000000139
259";
260        let lines = Cursor::new(def).lines();
261        read_graph::<_, NodeIDComparator>(lines).unwrap()
262    }
263
264    fn make_dummy_sort(
265        graph: &(impl Graph + SizedGraph + StableOrderGraph),
266    ) -> NodeSort {
267        stable_sort(graph, (graph.nb_nodes() - 1) as Revision).unwrap()
268    }
269
270    #[test]
271    fn test_xc() {
272        /// X_c(s) := max_i #{ j | j<i \exists k>i s_j->s_k }
273        fn naive(graph: &impl Graph, node_sort: &NodeSort) -> usize {
274            let mut max_card = 0;
275            for i in 0..node_sort.len() {
276                let mut q_e_card = 0;
277                for rev_j in node_sort[..i].iter() {
278                    for rev_k in node_sort[i + 1..].iter() {
279                        if graph.parents(*rev_k).unwrap().contains(*rev_j) {
280                            q_e_card += 1;
281                            break;
282                        }
283                    }
284                }
285                if q_e_card > max_card {
286                    max_card = q_e_card;
287                }
288            }
289            max_card
290        }
291
292        let graph = make_dummy_graph();
293        let sort = make_dummy_sort(&graph);
294        assert_eq!(xc(&graph, &sort).unwrap(), naive(&graph, &sort));
295    }
296
297    #[test]
298    fn test_xp() {
299        /// X_p(s) := max_i #{ k | k>i \exists j<i s_j->s_k }
300        pub fn naive(graph: &impl Graph, node_sort: &NodeSort) -> usize {
301            let mut max_card = 0;
302            for i in 0..node_sort.len() {
303                let mut q_p_card = 0;
304                for rev_k in node_sort[i + 1..].iter() {
305                    for rev_j in node_sort[0..i].iter() {
306                        if graph.parents(*rev_k).unwrap().contains(*rev_j) {
307                            q_p_card += 1;
308                            break;
309                        }
310                    }
311                }
312                println!("{}", q_p_card);
313                if q_p_card > max_card {
314                    max_card = q_p_card;
315                }
316            }
317            max_card
318        }
319
320        let graph = make_dummy_graph();
321        let sort = make_dummy_sort(&graph);
322        println!("node_sort: {:#?}", sort);
323        assert_eq!(xp(&graph, &sort).unwrap(), naive(&graph, &sort));
324    }
325
326    #[test]
327    fn test_xa() {
328        /// X_a(s) := max_i #{ (j,k) | j<i<k s_j->s_k }
329        pub fn naive(graph: &impl Graph, node_sort: &NodeSort) -> usize {
330            let mut max_card = 0;
331            for i in 0..node_sort.len() {
332                let mut q_a_card = 0;
333                for rev_j in node_sort[..i].iter() {
334                    for rev_k in node_sort[i + 1..].iter() {
335                        if graph.parents(*rev_k).unwrap().contains(*rev_j) {
336                            q_a_card += 1;
337                        }
338                    }
339                }
340                if q_a_card > max_card {
341                    max_card = q_a_card;
342                }
343            }
344            max_card
345        }
346
347        let graph = make_dummy_graph();
348        let sort = make_dummy_sort(&graph);
349        assert_eq!(xa(&graph, &sort).unwrap(), naive(&graph, &sort));
350    }
351
352    #[test]
353    fn test_xf() {
354        /// X_f(s) := max_i #{ k | i<k \forall j s_j->s_k => j<i }
355        pub fn naive(graph: &impl Graph, node_sort: &NodeSort) -> usize {
356            let mut max_card = 0;
357            for i in 0..node_sort.len() {
358                let mut q_h_card = 0;
359                'for_all: for rev_k in node_sort[i + 1..].iter() {
360                    for (j, rev_j) in node_sort.iter().enumerate() {
361                        if graph.parents(*rev_k).unwrap().contains(*rev_j) {
362                            if j >= i {
363                                continue 'for_all;
364                            }
365                        }
366                    }
367                    q_h_card += 1;
368                }
369                if q_h_card > max_card {
370                    max_card = q_h_card;
371                }
372            }
373            max_card
374        }
375
376        let graph = make_dummy_graph();
377        let sort = make_dummy_sort(&graph);
378        assert_eq!(xf(&graph, &sort).unwrap(), naive(&graph, &sort));
379    }
380}
vcsgraph/analytics/sortsindicators.rs

vcsgraph/analytics/
sortsindicators.rs
