rust_igraph/algorithms/paths/
spanner.rs

1//! Graph spanner (ALGO-PA-030) — Baswana-Sen algorithm.
2//!
3//! Counterpart of `igraph_spanner` in
4//! `references/igraph/src/paths/sparsifier.c:152`.
5//!
6//! A t-spanner of G is a subgraph H with the same vertex set such
7//! that for every pair (u, v), `dist_H(u, v)` ≤ t · `dist_G(u, v)`.
8//! The algorithm returns edge IDs of a sparse subgraph achieving
9//! this stretch guarantee.
10//!
11//! ## Algorithm
12//!
13//! Baswana and Sen, "A Simple and Linear Time Randomized Algorithm
14//! for Computing Sparse Spanners in Weighted Graphs", Random
15//! Structures & Algorithms 30(4), 2007.
16//!
17//! Randomized Las Vegas: the result is always correct (verified
18//! stretch), but expected edge count is O(k·n^(1+1/k)) for
19//! unweighted and O(n^(1+1/k)) for weighted, where k = (t+1)/2.
20
21use crate::core::VertexId;
22use crate::core::{Graph, IgraphError, IgraphResult};
23
24type IncList = Vec<Vec<(VertexId, u32, f64)>>;
25
26/// Compute a t-spanner of the graph.
27///
28/// Returns a sorted list of edge IDs whose induced subgraph is a
29/// t-spanner of the input graph. Edge directions are ignored.
30///
31/// # Arguments
32///
33/// * `graph` — input graph (undirected or directed; directions ignored).
34/// * `stretch` — the stretch factor t (must be ≥ 1.0).
35/// * `weights` — optional edge weight vector (all positive). `None`
36///   means unit weights.
37///
38/// # Errors
39///
40/// Returns an error if `stretch < 1.0`, weight vector length doesn't
41/// match edge count, or weights contain non-positive/NaN values.
42///
43/// # Examples
44///
45/// ```
46/// use rust_igraph::{Graph, spanner};
47///
48/// // Path graph: 0-1-2-3. A 1-spanner must include all edges.
49/// let mut g = Graph::new(4, false).unwrap();
50/// g.add_edge(0, 1).unwrap();
51/// g.add_edge(1, 2).unwrap();
52/// g.add_edge(2, 3).unwrap();
53/// let sp = spanner(&g, 1.0, None).unwrap();
54/// assert_eq!(sp.len(), 3); // must keep all edges for stretch=1
55/// ```
56#[allow(clippy::cast_precision_loss)]
57pub fn spanner(graph: &Graph, stretch: f64, weights: Option<&[f64]>) -> IgraphResult<Vec<u32>> {
58    let n = graph.vcount() as usize;
59    let m = graph.ecount();
60
61    validate_inputs(stretch, weights, m)?;
62
63    if n == 0 || m == 0 {
64        return Ok(Vec::new());
65    }
66
67    let k = stretch / 2.0 + 0.5;
68    let sample_prob = (n as f64).powf(-1.0 / k);
69
70    let mut inc = build_incidence(graph, n, m, weights)?;
71    let mut in_spanner = vec![false; m];
72    let mut clustering: Vec<u32> = (0..n)
73        .map(|v| u32::try_from(v).unwrap_or(u32::MAX))
74        .collect();
75
76    let mut rng_state: u64 =
77        0x1234_5678_9abc_def0_u64 ^ (n as u64).wrapping_mul(0x517c_c1b7_2722_0a95);
78
79    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
80    let k_iters = (k - 1.0).max(0.0).ceil() as usize;
81
82    for _iter in 0..k_iters {
83        phase1_iteration(
84            n,
85            &mut inc,
86            &mut in_spanner,
87            &mut clustering,
88            &mut rng_state,
89            sample_prob,
90        );
91    }
92
93    phase2_finalize(n, &inc, &mut in_spanner, &clustering);
94
95    let mut result: Vec<u32> = (0..m)
96        .filter(|&e| in_spanner[e])
97        .filter_map(|e| u32::try_from(e).ok())
98        .collect();
99    result.sort_unstable();
100    Ok(result)
101}
102
103fn validate_inputs(stretch: f64, weights: Option<&[f64]>, m: usize) -> IgraphResult<()> {
104    if stretch < 1.0 {
105        return Err(IgraphError::InvalidArgument(
106            "spanner: stretch factor must be at least 1.0".into(),
107        ));
108    }
109
110    if let Some(w) = weights {
111        if w.len() != m {
112            return Err(IgraphError::InvalidArgument(format!(
113                "spanner: weight vector length {} != edge count {m}",
114                w.len()
115            )));
116        }
117        for (i, &v) in w.iter().enumerate() {
118            if v.is_nan() {
119                return Err(IgraphError::InvalidArgument(format!(
120                    "spanner: weights[{i}] is NaN"
121                )));
122            }
123            if v < 0.0 {
124                return Err(IgraphError::InvalidArgument(format!(
125                    "spanner: weights[{i}] = {v} is negative"
126                )));
127            }
128        }
129    }
130    Ok(())
131}
132
133fn build_incidence(
134    graph: &Graph,
135    n: usize,
136    m: usize,
137    weights: Option<&[f64]>,
138) -> IgraphResult<IncList> {
139    let mut inc: IncList = vec![Vec::new(); n];
140    for eid in 0..m {
141        let eid32 = u32::try_from(eid)
142            .map_err(|_| IgraphError::InvalidArgument("spanner: edge id overflow".into()))?;
143        let (from, to) = graph.edge(eid32)?;
144        let w = weights.map_or(1.0, |ws| ws[eid]);
145        inc[from as usize].push((to, eid32, w));
146        if from != to {
147            inc[to as usize].push((from, eid32, w));
148        }
149    }
150    Ok(inc)
151}
152
153fn xorshift64(state: &mut u64) -> f64 {
154    *state ^= *state << 13;
155    *state ^= *state >> 7;
156    *state ^= *state << 17;
157    // Divide by a constant to get [0, 1) — precision loss is acceptable for PRNG
158    #[allow(clippy::cast_precision_loss)]
159    let val = (*state >> 11) as f64 / ((1_u64 << 53) as f64);
160    val
161}
162
163fn update_lightest(lightest: &mut Vec<(u32, u32, f64)>, cluster: u32, eid: u32, w: f64) {
164    for entry in &mut *lightest {
165        if entry.0 == cluster {
166            if w < entry.2 {
167                entry.1 = eid;
168                entry.2 = w;
169            }
170            return;
171        }
172    }
173    lightest.push((cluster, eid, w));
174}
175
176fn phase1_iteration(
177    n: usize,
178    inc: &mut IncList,
179    in_spanner: &mut [bool],
180    clustering: &mut Vec<u32>,
181    rng_state: &mut u64,
182    sample_prob: f64,
183) {
184    let mut new_clustering: Vec<u32> = vec![u32::MAX; n];
185    let mut is_sampled = vec![false; n];
186
187    for v in 0..n {
188        let cv = clustering[v] as usize;
189        if cv == v && xorshift64(rng_state) < sample_prob {
190            is_sampled[v] = true;
191        }
192    }
193
194    for v in 0..n {
195        let cluster_v = clustering[v];
196        if cluster_v != u32::MAX && is_sampled[cluster_v as usize] {
197            new_clustering[v] = cluster_v;
198            continue;
199        }
200
201        let mut lightest_to_cluster: Vec<(u32, u32, f64)> = Vec::new();
202        let mut nearest_sampled: Option<(u32, u32, f64)> = None;
203
204        for &(nb, eid, w) in &inc[v] {
205            let cluster_nb = clustering[nb as usize];
206            if cluster_nb == u32::MAX {
207                continue;
208            }
209
210            update_lightest(&mut lightest_to_cluster, cluster_nb, eid, w);
211
212            if is_sampled[cluster_nb as usize] {
213                let better = nearest_sampled
214                    .as_ref()
215                    .is_none_or(|(_, _, best_w)| w < *best_w);
216                if better {
217                    nearest_sampled = Some((cluster_nb, eid, w));
218                }
219            }
220        }
221
222        if let Some((sampled_cluster, sampled_eid, sampled_w)) = nearest_sampled {
223            in_spanner[sampled_eid as usize] = true;
224            new_clustering[v] = sampled_cluster;
225
226            for &(_, eid, w) in &lightest_to_cluster {
227                if w < sampled_w {
228                    in_spanner[eid as usize] = true;
229                }
230            }
231
232            inc[v].retain(|&(nb, _, _)| {
233                let cluster_nb = clustering[nb as usize];
234                if cluster_nb == u32::MAX {
235                    return true;
236                }
237                if cluster_nb == sampled_cluster {
238                    return false;
239                }
240                let cluster_lightest = lightest_to_cluster
241                    .iter()
242                    .find(|e| e.0 == cluster_nb)
243                    .map_or(f64::INFINITY, |e| e.2);
244                cluster_lightest >= sampled_w
245            });
246        } else {
247            for &(_, eid, _) in &lightest_to_cluster {
248                in_spanner[eid as usize] = true;
249            }
250            inc[v].clear();
251        }
252    }
253
254    *clustering = new_clustering;
255
256    for v in 0..n {
257        let cv = clustering[v];
258        if cv == u32::MAX {
259            continue;
260        }
261        inc[v].retain(|&(nb, _, _)| clustering[nb as usize] != cv);
262    }
263}
264
265fn phase2_finalize(n: usize, inc: &IncList, in_spanner: &mut [bool], clustering: &[u32]) {
266    for v in 0..n {
267        if clustering[v] == u32::MAX {
268            continue;
269        }
270
271        let mut lightest_to_cluster: Vec<(u32, u32, f64)> = Vec::new();
272        for &(nb, eid, w) in &inc[v] {
273            let cluster_nb = clustering[nb as usize];
274            if cluster_nb == u32::MAX {
275                continue;
276            }
277            update_lightest(&mut lightest_to_cluster, cluster_nb, eid, w);
278        }
279
280        for &(_, eid, _) in &lightest_to_cluster {
281            in_spanner[eid as usize] = true;
282        }
283    }
284}
285
286#[cfg(test)]
287mod tests {
288    use super::*;
289
290    #[test]
291    fn spanner_empty() {
292        let g = Graph::new(0, false).unwrap();
293        let sp = spanner(&g, 3.0, None).unwrap();
294        assert!(sp.is_empty());
295    }
296
297    #[test]
298    fn spanner_no_edges() {
299        let g = Graph::new(5, false).unwrap();
300        let sp = spanner(&g, 3.0, None).unwrap();
301        assert!(sp.is_empty());
302    }
303
304    #[test]
305    fn spanner_single_edge() {
306        let mut g = Graph::new(2, false).unwrap();
307        g.add_edge(0, 1).unwrap();
308        let sp = spanner(&g, 3.0, None).unwrap();
309        assert_eq!(sp, vec![0]);
310    }
311
312    #[test]
313    fn spanner_stretch_1_keeps_all() {
314        let mut g = Graph::new(4, false).unwrap();
315        g.add_edge(0, 1).unwrap();
316        g.add_edge(1, 2).unwrap();
317        g.add_edge(2, 3).unwrap();
318        let sp = spanner(&g, 1.0, None).unwrap();
319        assert_eq!(sp.len(), 3);
320    }
321
322    #[test]
323    fn spanner_triangle() {
324        let mut g = Graph::new(3, false).unwrap();
325        g.add_edge(0, 1).unwrap();
326        g.add_edge(1, 2).unwrap();
327        g.add_edge(0, 2).unwrap();
328        let sp = spanner(&g, 3.0, None).unwrap();
329        assert!(sp.len() >= 2);
330        assert!(sp.len() <= 3);
331    }
332
333    #[test]
334    fn spanner_complete_4() {
335        let mut g = Graph::new(4, false).unwrap();
336        g.add_edge(0, 1).unwrap();
337        g.add_edge(0, 2).unwrap();
338        g.add_edge(0, 3).unwrap();
339        g.add_edge(1, 2).unwrap();
340        g.add_edge(1, 3).unwrap();
341        g.add_edge(2, 3).unwrap();
342        let sp = spanner(&g, 3.0, None).unwrap();
343        assert!(sp.len() >= 3);
344        assert!(sp.len() <= 6);
345    }
346
347    #[test]
348    fn spanner_weighted() {
349        let mut g = Graph::new(3, false).unwrap();
350        g.add_edge(0, 1).unwrap();
351        g.add_edge(1, 2).unwrap();
352        g.add_edge(0, 2).unwrap();
353        let weights = vec![1.0, 1.0, 3.0];
354        let sp = spanner(&g, 3.0, Some(&weights)).unwrap();
355        assert!(sp.len() >= 2);
356    }
357
358    #[test]
359    fn spanner_invalid_stretch() {
360        let g = Graph::new(2, false).unwrap();
361        assert!(spanner(&g, 0.5, None).is_err());
362    }
363
364    #[test]
365    fn spanner_invalid_weights_len() {
366        let mut g = Graph::new(2, false).unwrap();
367        g.add_edge(0, 1).unwrap();
368        assert!(spanner(&g, 3.0, Some(&[1.0, 2.0])).is_err());
369    }
370
371    #[test]
372    fn spanner_negative_weight() {
373        let mut g = Graph::new(2, false).unwrap();
374        g.add_edge(0, 1).unwrap();
375        assert!(spanner(&g, 3.0, Some(&[-1.0])).is_err());
376    }
377
378    #[test]
379    fn spanner_result_sorted() {
380        let mut g = Graph::new(5, false).unwrap();
381        g.add_edge(0, 1).unwrap();
382        g.add_edge(1, 2).unwrap();
383        g.add_edge(2, 3).unwrap();
384        g.add_edge(3, 4).unwrap();
385        g.add_edge(4, 0).unwrap();
386        let sp = spanner(&g, 3.0, None).unwrap();
387        let mut sorted = sp.clone();
388        sorted.sort_unstable();
389        assert_eq!(sp, sorted);
390    }
391
392    #[test]
393    fn spanner_directed_ignores_direction() {
394        let mut g = Graph::new(3, true).unwrap();
395        g.add_edge(0, 1).unwrap();
396        g.add_edge(1, 2).unwrap();
397        g.add_edge(2, 0).unwrap();
398        let sp = spanner(&g, 3.0, None).unwrap();
399        assert!(sp.len() >= 2);
400    }
401}
rust_igraph/algorithms/paths/spanner.rs

rust_igraph/algorithms/paths/
spanner.rs
