rust_igraph/algorithms/properties/
local_scan.rs

1//! Local scan statistics (ALGO-PR-051 + ALGO-PR-042).
2//!
3//! Counterparts of `igraph_local_scan_*` from
4//! `references/igraph/src/misc/scan.c`.
5//!
6//! Scan statistics summarise local neighbourhood structure. For each
7//! vertex the k-neighbourhood is identified and the edges (or total
8//! weight) within that neighbourhood are counted.
9//!
10//! ## Functions
11//!
12//! - [`local_scan_1`] — undirected-only 1-neighbourhood edge count
13//!   (original ALGO-PR-051, kept for backward compatibility).
14//! - [`local_scan_0`] — k=0 (degree / strength).
15//! - [`local_scan_1_ecount`] — k=1 with directed-mode support.
16//! - [`local_scan_0_them`] — two-graph k=0 scan.
17//! - [`local_scan_1_ecount_them`] — two-graph k=1 scan.
18//! - [`local_scan_subset_ecount`] — edge count in given vertex subsets.
19
20use crate::algorithms::properties::degree::DegreeMode;
21use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
22
23/// Collect incident edge IDs for a vertex respecting mode.
24fn incident_with_mode(graph: &Graph, v: VertexId, mode: DegreeMode) -> IgraphResult<Vec<u32>> {
25    if !graph.is_directed() {
26        return graph.incident(v);
27    }
28    match mode {
29        DegreeMode::Out => graph.incident(v),
30        DegreeMode::In => graph.incident_in(v),
31        DegreeMode::All => {
32            let mut out = graph.incident(v)?;
33            let in_edges = graph.incident_in(v)?;
34            out.extend(in_edges);
35            Ok(out)
36        }
37    }
38}
39
40/// Collect vertex neighbours respecting mode.
41fn neighbors_with_mode(graph: &Graph, v: VertexId, mode: DegreeMode) -> IgraphResult<Vec<u32>> {
42    if !graph.is_directed() {
43        return graph.neighbors(v);
44    }
45    match mode {
46        DegreeMode::Out => {
47            let edges = graph.incident(v)?;
48            edges.iter().map(|&e| graph.edge_other(e, v)).collect()
49        }
50        DegreeMode::In => {
51            let edges = graph.incident_in(v)?;
52            edges.iter().map(|&e| graph.edge_other(e, v)).collect()
53        }
54        DegreeMode::All => {
55            let out_edges = graph.incident(v)?;
56            let in_edges = graph.incident_in(v)?;
57            let mut neis = Vec::with_capacity(out_edges.len() + in_edges.len());
58            for &e in &out_edges {
59                neis.push(graph.edge_other(e, v)?);
60            }
61            for &e in &in_edges {
62                neis.push(graph.edge_other(e, v)?);
63            }
64            Ok(neis)
65        }
66    }
67}
68
69// ────────────────── local_scan_1 (legacy, backward-compat) ──────────────────
70
71/// For each vertex, count edges within its closed 1-neighborhood.
72///
73/// The closed 1-neighborhood of vertex `v` is `{v} ∪ neighbors(v)`.
74/// This function counts all edges that have both endpoints in that set.
75///
76/// For undirected graphs, each such edge is counted once per vertex whose
77/// neighborhood contains it.
78///
79/// `weights`: optional edge weights (length must equal `ecount()`).
80/// When provided, sums edge weights instead of counting edges.
81///
82/// Returns a vector of length `vcount()`.
83///
84/// # Examples
85///
86/// ```
87/// use rust_igraph::{Graph, local_scan_1};
88///
89/// // Triangle: each vertex's 1-neighborhood is the whole graph.
90/// // 3 edges in the neighborhood of each vertex.
91/// let mut g = Graph::with_vertices(3);
92/// g.add_edge(0, 1).unwrap();
93/// g.add_edge(1, 2).unwrap();
94/// g.add_edge(2, 0).unwrap();
95/// let s = local_scan_1(&g, None).unwrap();
96/// assert!((s[0] - 3.0).abs() < 1e-10);
97/// assert!((s[1] - 3.0).abs() < 1e-10);
98/// assert!((s[2] - 3.0).abs() < 1e-10);
99/// ```
100pub fn local_scan_1(graph: &Graph, weights: Option<&[f64]>) -> IgraphResult<Vec<f64>> {
101    local_scan_1_ecount(graph, weights, DegreeMode::All)
102}
103
104// ──────────────────────── local_scan_0 ──────────────────────────────────────
105
106/// Local scan-0: vertex degree (unweighted) or strength (weighted).
107///
108/// For `k = 0` the scan statistic is defined as the degree (or
109/// weighted strength) of each vertex.
110///
111/// # Examples
112///
113/// ```
114/// use rust_igraph::{Graph, local_scan_0, DegreeMode};
115///
116/// let mut g = Graph::with_vertices(4);
117/// g.add_edge(0, 1).unwrap();
118/// g.add_edge(0, 2).unwrap();
119/// g.add_edge(0, 3).unwrap();
120/// let res = local_scan_0(&g, None, DegreeMode::All).unwrap();
121/// assert!((res[0] - 3.0).abs() < 1e-12);
122/// assert!((res[1] - 1.0).abs() < 1e-12);
123/// ```
124pub fn local_scan_0(
125    graph: &Graph,
126    weights: Option<&[f64]>,
127    mode: DegreeMode,
128) -> IgraphResult<Vec<f64>> {
129    if let Some(w) = weights {
130        if w.len() != graph.ecount() {
131            return Err(IgraphError::InvalidArgument(format!(
132                "weight vector length {} != edge count {}",
133                w.len(),
134                graph.ecount()
135            )));
136        }
137    }
138
139    let n = graph.vcount() as usize;
140    let mut res = vec![0.0_f64; n];
141    let directed = graph.is_directed();
142    let ecount = graph.ecount();
143
144    for eid in 0..ecount {
145        let eid_u32 =
146            u32::try_from(eid).map_err(|_| IgraphError::Internal("ecount exceeds u32::MAX"))?;
147        let from = graph.edge_source(eid_u32)? as usize;
148        let to = graph.edge_target(eid_u32)? as usize;
149        let w = weights.map_or(1.0, |ws| ws[eid]);
150
151        if directed {
152            match mode {
153                DegreeMode::Out => res[from] += w,
154                DegreeMode::In => res[to] += w,
155                DegreeMode::All => {
156                    res[from] += w;
157                    res[to] += w;
158                }
159            }
160        } else {
161            res[from] += w;
162            res[to] += w;
163        }
164    }
165
166    Ok(res)
167}
168
169// ──────────────────────── local_scan_1_ecount ───────────────────────────────
170
171/// Local scan-1 for directed graphs (mode != All): mark+crawl approach.
172fn local_scan_1_directed(
173    graph: &Graph,
174    weights: Option<&[f64]>,
175    mode: DegreeMode,
176) -> IgraphResult<Vec<f64>> {
177    let n = graph.vcount();
178    let n_usize = n as usize;
179    let mut res = vec![0.0_f64; n_usize];
180    let mut marker: Vec<i64> = vec![-1; n_usize];
181
182    for node in 0..n {
183        let node_i = i64::from(node);
184        let edges1 = incident_with_mode(graph, node, mode)?;
185
186        marker[node as usize] = node_i;
187        for &e in &edges1 {
188            let nei = graph.edge_other(e, node)?;
189            let w = weights.map_or(1.0, |ws| ws[e as usize]);
190            marker[nei as usize] = node_i;
191            res[node as usize] += w;
192        }
193
194        for &e in &edges1 {
195            let nei = graph.edge_other(e, node)?;
196            if nei == node {
197                break;
198            }
199            let edges2 = incident_with_mode(graph, nei, mode)?;
200            for &e2 in &edges2 {
201                let nei2 = graph.edge_other(e2, nei)?;
202                if marker[nei2 as usize] == node_i {
203                    let w2 = weights.map_or(1.0, |ws| ws[e2 as usize]);
204                    res[node as usize] += w2;
205                }
206            }
207        }
208    }
209
210    Ok(res)
211}
212
213/// Local scan-1 for directed graphs with mode = All: unmark-after-visit.
214fn local_scan_1_directed_all(graph: &Graph, weights: Option<&[f64]>) -> IgraphResult<Vec<f64>> {
215    let n = graph.vcount();
216    let n_usize = n as usize;
217    let mut res = vec![0.0_f64; n_usize];
218    let mut marker: Vec<i64> = vec![-1; n_usize];
219
220    for node in 0..n {
221        let node_i = i64::from(node);
222        let edges1 = incident_with_mode(graph, node, DegreeMode::All)?;
223
224        for &e in &edges1 {
225            let nei = graph.edge_other(e, node)?;
226            let w = weights.map_or(1.0, |ws| ws[e as usize]);
227            marker[nei as usize] = node_i;
228            res[node as usize] += w;
229        }
230
231        marker[node as usize] = -1;
232
233        for &e in &edges1 {
234            let nei = graph.edge_other(e, node)?;
235            if marker[nei as usize] != node_i {
236                continue;
237            }
238            let edges2 = incident_with_mode(graph, nei, DegreeMode::All)?;
239            for &e2 in &edges2 {
240                let nei2 = graph.edge_other(e2, nei)?;
241                if marker[nei2 as usize] == node_i {
242                    let w2 = weights.map_or(1.0, |ws| ws[e2 as usize]);
243                    res[node as usize] += w2;
244                }
245            }
246            marker[nei as usize] = -1;
247        }
248    }
249
250    Ok(res)
251}
252
253/// Local scan-1 edge count / weight sum in the 1-neighbourhood of
254/// every vertex, with directed-mode support.
255///
256/// # Examples
257///
258/// ```
259/// use rust_igraph::{Graph, local_scan_1_ecount, DegreeMode};
260///
261/// // Triangle 0-1-2 plus pendant 3-0
262/// let mut g = Graph::with_vertices(4);
263/// g.add_edge(0, 1).unwrap();
264/// g.add_edge(1, 2).unwrap();
265/// g.add_edge(2, 0).unwrap();
266/// g.add_edge(3, 0).unwrap();
267/// let res = local_scan_1_ecount(&g, None, DegreeMode::All).unwrap();
268/// assert!((res[0] - 4.0).abs() < 1e-12);
269/// assert!((res[3] - 1.0).abs() < 1e-12);
270/// ```
271pub fn local_scan_1_ecount(
272    graph: &Graph,
273    weights: Option<&[f64]>,
274    mode: DegreeMode,
275) -> IgraphResult<Vec<f64>> {
276    if let Some(w) = weights {
277        if w.len() != graph.ecount() {
278            return Err(IgraphError::InvalidArgument(format!(
279                "weight vector length {} != edge count {}",
280                w.len(),
281                graph.ecount()
282            )));
283        }
284    }
285
286    if graph.is_directed() {
287        if mode == DegreeMode::All {
288            local_scan_1_directed_all(graph, weights)
289        } else {
290            local_scan_1_directed(graph, weights, mode)
291        }
292    } else {
293        // For undirected graphs, use k-general BFS approach
294        crate::algorithms::properties::local_scan_k::local_scan_k_ecount(graph, 1, weights, mode)
295    }
296}
297
298// ────────────────────── local_scan_0_them ────────────────────────────────────
299
300/// Local scan-0 on two graphs: degree/strength from `them` restricted
301/// to edges that also exist in `us`.
302///
303/// Both graphs must have the same vertex count and directedness.
304///
305/// # Examples
306///
307/// ```
308/// use rust_igraph::{Graph, local_scan_0_them, DegreeMode};
309///
310/// let mut us = Graph::with_vertices(3);
311/// us.add_edge(0, 1).unwrap();
312/// us.add_edge(0, 2).unwrap();
313/// let mut them = Graph::with_vertices(3);
314/// them.add_edge(0, 1).unwrap();
315/// them.add_edge(1, 2).unwrap();
316/// let res = local_scan_0_them(&us, &them, None, DegreeMode::All).unwrap();
317/// assert!((res[0] - 1.0).abs() < 1e-12);
318/// assert!((res[1] - 1.0).abs() < 1e-12);
319/// assert!((res[2] - 0.0).abs() < 1e-12);
320/// ```
321pub fn local_scan_0_them(
322    us: &Graph,
323    them: &Graph,
324    weights_them: Option<&[f64]>,
325    mode: DegreeMode,
326) -> IgraphResult<Vec<f64>> {
327    check_them_compat(us, them, weights_them, "local_scan_0_them")?;
328
329    let is_graph = crate::algorithms::operators::intersection::intersection(us, them)?;
330
331    // For unweighted, just compute scan_0 on the intersection
332    if weights_them.is_none() {
333        return local_scan_0(&is_graph, None, mode);
334    }
335
336    // For weighted, we need to map weights from `them` to the intersection.
337    // The intersection result has edge_map2 which maps intersection edges
338    // back to `them` edges. But our intersection returns IntersectionResult
339    // which only has .graph. We'll do the unweighted path for now and
340    // handle weighted via a different approach.
341    //
342    // Weighted scan-0-them: for each edge in `us`, check if the same edge
343    // exists in `them` and if so add its weight.
344    let Some(ws) = weights_them else {
345        return Err(IgraphError::Internal(
346            "weights_them should be Some after guard",
347        ));
348    };
349    let n = us.vcount() as usize;
350    let mut res = vec![0.0_f64; n];
351    let directed = us.is_directed();
352    let us_ecount = us.ecount();
353
354    for eid in 0..us_ecount {
355        let eid_u32 =
356            u32::try_from(eid).map_err(|_| IgraphError::Internal("ecount exceeds u32::MAX"))?;
357        let from = us.edge_source(eid_u32)?;
358        let to = us.edge_target(eid_u32)?;
359
360        // Check if this edge exists in `them`
361        if let Some(them_eid) = them.find_eid(from, to)? {
362            let w = ws[them_eid as usize];
363            if directed {
364                match mode {
365                    DegreeMode::Out => res[from as usize] += w,
366                    DegreeMode::In => res[to as usize] += w,
367                    DegreeMode::All => {
368                        res[from as usize] += w;
369                        res[to as usize] += w;
370                    }
371                }
372            } else {
373                res[from as usize] += w;
374                res[to as usize] += w;
375            }
376        }
377    }
378
379    Ok(res)
380}
381
382// ────────────────── local_scan_1_ecount_them ─────────────────────────────────
383
384/// Local scan-1 edge count on two graphs: count edges from `them` in
385/// the 1-neighbourhood defined by `us`.
386///
387/// Both graphs must have the same vertex count and directedness.
388///
389/// # Examples
390///
391/// ```
392/// use rust_igraph::{Graph, local_scan_1_ecount_them, DegreeMode};
393///
394/// let mut us = Graph::with_vertices(3);
395/// us.add_edge(0, 1).unwrap();
396/// us.add_edge(1, 2).unwrap();
397/// let mut them = Graph::with_vertices(3);
398/// them.add_edge(0, 1).unwrap();
399/// them.add_edge(0, 2).unwrap();
400/// them.add_edge(1, 2).unwrap();
401/// let res = local_scan_1_ecount_them(&us, &them, None, DegreeMode::All).unwrap();
402/// assert!((res[1] - 3.0).abs() < 1e-12);
403/// ```
404pub fn local_scan_1_ecount_them(
405    us: &Graph,
406    them: &Graph,
407    weights_them: Option<&[f64]>,
408    mode: DegreeMode,
409) -> IgraphResult<Vec<f64>> {
410    check_them_compat(us, them, weights_them, "local_scan_1_ecount_them")?;
411
412    let n = us.vcount();
413    let n_usize = n as usize;
414    let mut res = vec![0.0_f64; n_usize];
415    let mut marker: Vec<i64> = vec![-1; n_usize];
416    let undirected_or_all = mode == DegreeMode::All || !us.is_directed();
417
418    for node in 0..n {
419        let node_i = i64::from(node);
420
421        marker[node as usize] = node_i;
422        let us_neis = neighbors_with_mode(us, node, mode)?;
423        for &nei in &us_neis {
424            marker[nei as usize] = node_i;
425        }
426
427        let them_edges_ego = incident_with_mode(them, node, mode)?;
428        for &e in &them_edges_ego {
429            let nei = them.edge_other(e, node)?;
430            if marker[nei as usize] == node_i {
431                let w = weights_them.map_or(1.0, |ws| ws[e as usize]);
432                res[node as usize] += w;
433            }
434        }
435
436        for &us_nei in &us_neis {
437            let them_edges = incident_with_mode(them, us_nei, mode)?;
438            for &e2 in &them_edges {
439                let nei2 = them.edge_other(e2, us_nei)?;
440                if marker[nei2 as usize] == node_i {
441                    let w = weights_them.map_or(1.0, |ws| ws[e2 as usize]);
442                    res[node as usize] += w;
443                }
444            }
445        }
446
447        if undirected_or_all {
448            res[node as usize] /= 2.0;
449        }
450    }
451
452    Ok(res)
453}
454
455// ────────────────── local_scan_subset_ecount ─────────────────────────────────
456
457/// Local scan on given vertex subsets: count edges (or sum weights)
458/// in the induced subgraph of each subset.
459///
460/// # Examples
461///
462/// ```
463/// use rust_igraph::{Graph, local_scan_subset_ecount};
464///
465/// let mut g = Graph::with_vertices(4);
466/// g.add_edge(0, 1).unwrap();
467/// g.add_edge(1, 2).unwrap();
468/// g.add_edge(2, 0).unwrap();
469/// g.add_edge(2, 3).unwrap();
470/// let subsets = vec![vec![0, 1, 2], vec![2, 3]];
471/// let res = local_scan_subset_ecount(&g, &subsets, None).unwrap();
472/// assert!((res[0] - 3.0).abs() < 1e-12);
473/// assert!((res[1] - 1.0).abs() < 1e-12);
474/// ```
475pub fn local_scan_subset_ecount(
476    graph: &Graph,
477    subsets: &[Vec<VertexId>],
478    weights: Option<&[f64]>,
479) -> IgraphResult<Vec<f64>> {
480    if let Some(w) = weights {
481        if w.len() != graph.ecount() {
482            return Err(IgraphError::InvalidArgument(format!(
483                "weight vector length {} != edge count {}",
484                w.len(),
485                graph.ecount()
486            )));
487        }
488    }
489
490    let n = graph.vcount();
491    let n_usize = n as usize;
492    let directed = graph.is_directed();
493    let num_subsets = subsets.len();
494    let mut res = vec![0.0_f64; num_subsets];
495    let mut marker: Vec<i64> = vec![-1; n_usize];
496
497    for (subset_idx, subset) in subsets.iter().enumerate() {
498        let subset_i = i64::try_from(subset_idx)
499            .map_err(|_| IgraphError::Internal("subset index overflow"))?;
500
501        for &v in subset {
502            if v >= n {
503                return Err(IgraphError::InvalidArgument(format!(
504                    "vertex {v} out of range for graph with {n} vertices"
505                )));
506            }
507            marker[v as usize] = subset_i;
508        }
509
510        // Use out-edges (IGRAPH_OUT mode with IGRAPH_LOOPS_TWICE) to
511        // count each undirected edge once from each endpoint, then halve.
512        for &v in subset {
513            let edges = graph.incident(v)?;
514            for &e in &edges {
515                let nei = graph.edge_other(e, v)?;
516                if marker[nei as usize] == subset_i {
517                    let w = weights.map_or(1.0, |ws| ws[e as usize]);
518                    res[subset_idx] += w;
519                }
520            }
521
522            if directed {
523                let in_edges = graph.incident_in(v)?;
524                for &e in &in_edges {
525                    let nei = graph.edge_other(e, v)?;
526                    if marker[nei as usize] == subset_i {
527                        let w = weights.map_or(1.0, |ws| ws[e as usize]);
528                        res[subset_idx] += w;
529                    }
530                }
531            }
532        }
533
534        res[subset_idx] /= 2.0;
535    }
536
537    Ok(res)
538}
539
540/// Validate compatibility for two-graph ("them") scan functions.
541fn check_them_compat(
542    us: &Graph,
543    them: &Graph,
544    weights_them: Option<&[f64]>,
545    name: &str,
546) -> IgraphResult<()> {
547    if us.vcount() != them.vcount() {
548        return Err(IgraphError::InvalidArgument(format!(
549            "{name}: vertex count mismatch ({} vs {})",
550            us.vcount(),
551            them.vcount()
552        )));
553    }
554    if us.is_directed() != them.is_directed() {
555        return Err(IgraphError::InvalidArgument(format!(
556            "{name}: directedness mismatch"
557        )));
558    }
559    if let Some(w) = weights_them {
560        if w.len() != them.ecount() {
561            return Err(IgraphError::InvalidArgument(format!(
562                "{name}: weight vector length {} != them edge count {}",
563                w.len(),
564                them.ecount()
565            )));
566        }
567    }
568    Ok(())
569}
570
571#[cfg(test)]
572mod tests {
573    use super::*;
574
575    fn close(a: f64, b: f64) -> bool {
576        (a - b).abs() < 1e-10
577    }
578
579    // --- local_scan_1 (legacy) tests ---
580
581    #[test]
582    fn empty_graph() {
583        let g = Graph::with_vertices(0);
584        let s = local_scan_1(&g, None).unwrap();
585        assert!(s.is_empty());
586    }
587
588    #[test]
589    fn no_edges() {
590        let g = Graph::with_vertices(5);
591        let s = local_scan_1(&g, None).unwrap();
592        assert!(s.iter().all(|&v| close(v, 0.0)));
593    }
594
595    #[test]
596    fn triangle() {
597        let mut g = Graph::with_vertices(3);
598        g.add_edge(0, 1).unwrap();
599        g.add_edge(1, 2).unwrap();
600        g.add_edge(2, 0).unwrap();
601        let s = local_scan_1(&g, None).unwrap();
602        assert!(close(s[0], 3.0));
603        assert!(close(s[1], 3.0));
604        assert!(close(s[2], 3.0));
605    }
606
607    #[test]
608    fn path_5() {
609        let mut g = Graph::with_vertices(5);
610        for i in 0..4u32 {
611            g.add_edge(i, i + 1).unwrap();
612        }
613        let s = local_scan_1(&g, None).unwrap();
614        assert!(close(s[0], 1.0));
615        assert!(close(s[1], 2.0));
616        assert!(close(s[2], 2.0));
617        assert!(close(s[3], 2.0));
618        assert!(close(s[4], 1.0));
619    }
620
621    #[test]
622    fn star() {
623        let mut g = Graph::with_vertices(4);
624        g.add_edge(0, 1).unwrap();
625        g.add_edge(0, 2).unwrap();
626        g.add_edge(0, 3).unwrap();
627        let s = local_scan_1(&g, None).unwrap();
628        assert!(close(s[0], 3.0));
629        assert!(close(s[1], 1.0));
630        assert!(close(s[2], 1.0));
631        assert!(close(s[3], 1.0));
632    }
633
634    #[test]
635    fn k4() {
636        let mut g = Graph::with_vertices(4);
637        for u in 0..4u32 {
638            for v in (u + 1)..4 {
639                g.add_edge(u, v).unwrap();
640            }
641        }
642        let s = local_scan_1(&g, None).unwrap();
643        for &val in &s {
644            assert!(close(val, 6.0));
645        }
646    }
647
648    #[test]
649    fn two_triangles_with_bridge() {
650        let mut g = Graph::with_vertices(6);
651        g.add_edge(0, 1).unwrap();
652        g.add_edge(0, 2).unwrap();
653        g.add_edge(1, 2).unwrap();
654        g.add_edge(3, 4).unwrap();
655        g.add_edge(3, 5).unwrap();
656        g.add_edge(4, 5).unwrap();
657        g.add_edge(2, 3).unwrap();
658        let s = local_scan_1(&g, None).unwrap();
659        assert!(close(s[0], 3.0));
660        assert!(close(s[1], 3.0));
661        assert!(close(s[2], 4.0));
662        assert!(close(s[3], 4.0));
663        assert!(close(s[4], 3.0));
664        assert!(close(s[5], 3.0));
665    }
666
667    #[test]
668    fn weighted() {
669        let mut g = Graph::with_vertices(3);
670        g.add_edge(0, 1).unwrap();
671        g.add_edge(1, 2).unwrap();
672        g.add_edge(2, 0).unwrap();
673        let w = vec![2.0, 3.0, 5.0];
674        let s = local_scan_1(&g, Some(&w)).unwrap();
675        assert!(close(s[0], 10.0));
676        assert!(close(s[1], 10.0));
677        assert!(close(s[2], 10.0));
678    }
679
680    #[test]
681    fn self_loop() {
682        let mut g = Graph::with_vertices(2);
683        g.add_edge(0, 0).unwrap();
684        g.add_edge(0, 1).unwrap();
685        let s = local_scan_1(&g, None).unwrap();
686        assert!(close(s[0], 2.0));
687        assert!(close(s[1], 2.0));
688    }
689
690    #[test]
691    fn weights_mismatch_errors() {
692        let mut g = Graph::with_vertices(2);
693        g.add_edge(0, 1).unwrap();
694        assert!(local_scan_1(&g, Some(&[1.0, 2.0])).is_err());
695    }
696
697    // --- local_scan_0 tests ---
698
699    #[test]
700    fn scan0_empty() {
701        let g = Graph::with_vertices(0);
702        let res = local_scan_0(&g, None, DegreeMode::All).unwrap();
703        assert!(res.is_empty());
704    }
705
706    #[test]
707    fn scan0_no_edges() {
708        let g = Graph::with_vertices(5);
709        let res = local_scan_0(&g, None, DegreeMode::All).unwrap();
710        assert_eq!(res, vec![0.0; 5]);
711    }
712
713    #[test]
714    fn scan0_triangle() {
715        let mut g = Graph::with_vertices(3);
716        g.add_edge(0, 1).unwrap();
717        g.add_edge(1, 2).unwrap();
718        g.add_edge(2, 0).unwrap();
719        let res = local_scan_0(&g, None, DegreeMode::All).unwrap();
720        for &d in &res {
721            assert!(close(d, 2.0));
722        }
723    }
724
725    #[test]
726    fn scan0_weighted() {
727        let mut g = Graph::with_vertices(3);
728        g.add_edge(0, 1).unwrap();
729        g.add_edge(1, 2).unwrap();
730        let w = vec![3.0, 5.0];
731        let res = local_scan_0(&g, Some(&w), DegreeMode::All).unwrap();
732        assert!(close(res[0], 3.0));
733        assert!(close(res[1], 8.0));
734        assert!(close(res[2], 5.0));
735    }
736
737    #[test]
738    fn scan0_directed_out() {
739        let mut g = Graph::new(3, true).unwrap();
740        g.add_edge(0, 1).unwrap();
741        g.add_edge(0, 2).unwrap();
742        g.add_edge(1, 2).unwrap();
743        let res = local_scan_0(&g, None, DegreeMode::Out).unwrap();
744        assert!(close(res[0], 2.0));
745        assert!(close(res[1], 1.0));
746        assert!(close(res[2], 0.0));
747    }
748
749    #[test]
750    fn scan0_directed_in() {
751        let mut g = Graph::new(3, true).unwrap();
752        g.add_edge(0, 1).unwrap();
753        g.add_edge(0, 2).unwrap();
754        g.add_edge(1, 2).unwrap();
755        let res = local_scan_0(&g, None, DegreeMode::In).unwrap();
756        assert!(close(res[0], 0.0));
757        assert!(close(res[1], 1.0));
758        assert!(close(res[2], 2.0));
759    }
760
761    // --- local_scan_1_ecount tests ---
762
763    #[test]
764    fn scan1e_triangle() {
765        let mut g = Graph::with_vertices(3);
766        g.add_edge(0, 1).unwrap();
767        g.add_edge(1, 2).unwrap();
768        g.add_edge(2, 0).unwrap();
769        let res = local_scan_1_ecount(&g, None, DegreeMode::All).unwrap();
770        for &v in &res {
771            assert!(close(v, 3.0));
772        }
773    }
774
775    #[test]
776    fn scan1e_path4() {
777        let mut g = Graph::with_vertices(4);
778        g.add_edge(0, 1).unwrap();
779        g.add_edge(1, 2).unwrap();
780        g.add_edge(2, 3).unwrap();
781        let res = local_scan_1_ecount(&g, None, DegreeMode::All).unwrap();
782        assert!(close(res[0], 1.0));
783        assert!(close(res[1], 2.0));
784        assert!(close(res[2], 2.0));
785        assert!(close(res[3], 1.0));
786    }
787
788    #[test]
789    fn scan1e_directed_out() {
790        let mut g = Graph::new(3, true).unwrap();
791        g.add_edge(0, 1).unwrap();
792        g.add_edge(1, 2).unwrap();
793        let res = local_scan_1_ecount(&g, None, DegreeMode::Out).unwrap();
794        assert!(close(res[0], 1.0));
795        assert!(close(res[1], 1.0));
796        assert!(close(res[2], 0.0));
797    }
798
799    #[test]
800    fn scan1e_directed_all_cycle() {
801        let mut g = Graph::new(3, true).unwrap();
802        g.add_edge(0, 1).unwrap();
803        g.add_edge(1, 2).unwrap();
804        g.add_edge(2, 0).unwrap();
805        let res = local_scan_1_ecount(&g, None, DegreeMode::All).unwrap();
806        for &v in &res {
807            assert!(close(v, 3.0));
808        }
809    }
810
811    // --- local_scan_0_them tests ---
812
813    #[test]
814    fn scan0t_basic() {
815        let mut us = Graph::with_vertices(3);
816        us.add_edge(0, 1).unwrap();
817        us.add_edge(0, 2).unwrap();
818        let mut them = Graph::with_vertices(3);
819        them.add_edge(0, 1).unwrap();
820        them.add_edge(1, 2).unwrap();
821        let res = local_scan_0_them(&us, &them, None, DegreeMode::All).unwrap();
822        assert!(close(res[0], 1.0));
823        assert!(close(res[1], 1.0));
824        assert!(close(res[2], 0.0));
825    }
826
827    #[test]
828    fn scan0t_identical() {
829        let mut g = Graph::with_vertices(3);
830        g.add_edge(0, 1).unwrap();
831        g.add_edge(1, 2).unwrap();
832        g.add_edge(2, 0).unwrap();
833        let res = local_scan_0_them(&g, &g, None, DegreeMode::All).unwrap();
834        let self_scan = local_scan_0(&g, None, DegreeMode::All).unwrap();
835        for (a, b) in res.iter().zip(self_scan.iter()) {
836            assert!(close(*a, *b));
837        }
838    }
839
840    #[test]
841    fn scan0t_vcount_mismatch() {
842        let us = Graph::with_vertices(3);
843        let them = Graph::with_vertices(4);
844        assert!(local_scan_0_them(&us, &them, None, DegreeMode::All).is_err());
845    }
846
847    // --- local_scan_1_ecount_them tests ---
848
849    #[test]
850    fn scan1t_basic() {
851        let mut us = Graph::with_vertices(3);
852        us.add_edge(0, 1).unwrap();
853        us.add_edge(1, 2).unwrap();
854        let mut them = Graph::with_vertices(3);
855        them.add_edge(0, 1).unwrap();
856        them.add_edge(0, 2).unwrap();
857        them.add_edge(1, 2).unwrap();
858        let res = local_scan_1_ecount_them(&us, &them, None, DegreeMode::All).unwrap();
859        // v1: nbd in us = {0,1,2}, edges in them within: 0-1,0-2,1-2 = 3
860        assert!(close(res[1], 3.0));
861    }
862
863    #[test]
864    fn scan1t_vcount_mismatch() {
865        let us = Graph::with_vertices(3);
866        let them = Graph::with_vertices(4);
867        assert!(local_scan_1_ecount_them(&us, &them, None, DegreeMode::All).is_err());
868    }
869
870    // --- local_scan_subset_ecount tests ---
871
872    #[test]
873    fn subset_triangle() {
874        let mut g = Graph::with_vertices(4);
875        g.add_edge(0, 1).unwrap();
876        g.add_edge(1, 2).unwrap();
877        g.add_edge(2, 0).unwrap();
878        g.add_edge(2, 3).unwrap();
879        let subsets = vec![vec![0, 1, 2], vec![2, 3], vec![0, 3]];
880        let res = local_scan_subset_ecount(&g, &subsets, None).unwrap();
881        assert!(close(res[0], 3.0));
882        assert!(close(res[1], 1.0));
883        assert!(close(res[2], 0.0));
884    }
885
886    #[test]
887    fn subset_weighted() {
888        let mut g = Graph::with_vertices(3);
889        g.add_edge(0, 1).unwrap();
890        g.add_edge(1, 2).unwrap();
891        let w = vec![3.0, 7.0];
892        let subsets = vec![vec![0, 1, 2]];
893        let res = local_scan_subset_ecount(&g, &subsets, Some(&w)).unwrap();
894        assert!(close(res[0], 10.0));
895    }
896
897    #[test]
898    fn subset_empty_subset() {
899        let mut g = Graph::with_vertices(3);
900        g.add_edge(0, 1).unwrap();
901        let subsets: Vec<Vec<VertexId>> = vec![vec![]];
902        let res = local_scan_subset_ecount(&g, &subsets, None).unwrap();
903        assert!(close(res[0], 0.0));
904    }
905
906    #[test]
907    fn subset_invalid_vertex() {
908        let g = Graph::with_vertices(3);
909        let subsets = vec![vec![0, 5]];
910        assert!(local_scan_subset_ecount(&g, &subsets, None).is_err());
911    }
912
913    #[test]
914    fn subset_directed() {
915        let mut g = Graph::new(3, true).unwrap();
916        g.add_edge(0, 1).unwrap();
917        g.add_edge(1, 2).unwrap();
918        g.add_edge(2, 0).unwrap();
919        let subsets = vec![vec![0, 1, 2]];
920        let res = local_scan_subset_ecount(&g, &subsets, None).unwrap();
921        assert!(close(res[0], 3.0));
922    }
923}
rust_igraph/algorithms/properties/local_scan.rs

rust_igraph/algorithms/properties/
local_scan.rs
