rust_igraph/algorithms/operators/
induced_subgraph_edges.rs

1//! Induced subgraph edges query (ALGO-OP-026).
2//!
3//! Counterpart of `igraph_induced_subgraph_edges()` from
4//! `references/igraph/src/operators/subgraph.c`.
5//!
6//! Returns the edge IDs connecting vertices in a specified set, without
7//! building the full subgraph.
8
9use crate::core::{Graph, IgraphError, IgraphResult};
10
11/// Returns the IDs of edges whose both endpoints lie in `vids`.
12///
13/// This is a lightweight alternative to [`crate::induced_subgraph`] when
14/// you only need the edge list, not the full subgraph structure. It's
15/// useful for counting or iterating over edges within a vertex subset.
16///
17/// The returned edge IDs are sorted in ascending order. Duplicate vertex
18/// IDs in `vids` are silently ignored.
19///
20/// # Errors
21///
22/// Returns `InvalidArgument` if any vertex ID in `vids` is out of range.
23///
24/// # Examples
25///
26/// ```
27/// use rust_igraph::{Graph, induced_subgraph_edges};
28///
29/// let mut g = Graph::with_vertices(5);
30/// g.add_edge(0, 1).unwrap(); // eid 0
31/// g.add_edge(1, 2).unwrap(); // eid 1
32/// g.add_edge(2, 3).unwrap(); // eid 2
33/// g.add_edge(3, 4).unwrap(); // eid 3
34/// g.add_edge(0, 4).unwrap(); // eid 4
35///
36/// // Edges within {0, 1, 2}: only 0-1 and 1-2
37/// let edges = induced_subgraph_edges(&g, &[0, 1, 2]).unwrap();
38/// assert_eq!(edges, vec![0, 1]);
39/// ```
40pub fn induced_subgraph_edges(graph: &Graph, vids: &[u32]) -> IgraphResult<Vec<u32>> {
41    let n = graph.vcount();
42    let m = graph.ecount();
43
44    // Validate and build a membership set.
45    let mut in_set: Vec<bool> = vec![false; n as usize];
46    for &vid in vids {
47        if vid >= n {
48            return Err(IgraphError::InvalidArgument(format!(
49                "induced_subgraph_edges: vertex ID {vid} out of range (graph has {n} vertices)"
50            )));
51        }
52        in_set[vid as usize] = true;
53    }
54
55    // Scan all edges and collect those with both endpoints in the set.
56    let mut result: Vec<u32> = Vec::new();
57    for eid_usize in 0..m {
58        #[allow(clippy::cast_possible_truncation)]
59        let eid = eid_usize as u32;
60        let (from, to) = graph.edge(eid)?;
61        if in_set[from as usize] && in_set[to as usize] {
62            result.push(eid);
63        }
64    }
65
66    Ok(result)
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn basic_undirected() {
75        let mut g = Graph::with_vertices(5);
76        g.add_edge(0, 1).unwrap(); // 0
77        g.add_edge(1, 2).unwrap(); // 1
78        g.add_edge(2, 3).unwrap(); // 2
79        g.add_edge(3, 4).unwrap(); // 3
80        g.add_edge(0, 4).unwrap(); // 4
81
82        let edges = induced_subgraph_edges(&g, &[0, 1, 2]).unwrap();
83        assert_eq!(edges, vec![0, 1]);
84    }
85
86    #[test]
87    fn all_vertices() {
88        let mut g = Graph::with_vertices(4);
89        g.add_edge(0, 1).unwrap();
90        g.add_edge(1, 2).unwrap();
91        g.add_edge(2, 3).unwrap();
92
93        let edges = induced_subgraph_edges(&g, &[0, 1, 2, 3]).unwrap();
94        assert_eq!(edges, vec![0, 1, 2]);
95    }
96
97    #[test]
98    fn single_vertex() {
99        let mut g = Graph::with_vertices(3);
100        g.add_edge(0, 1).unwrap();
101        g.add_edge(1, 2).unwrap();
102
103        let edges = induced_subgraph_edges(&g, &[1]).unwrap();
104        assert!(edges.is_empty());
105    }
106
107    #[test]
108    fn self_loop_included() {
109        let mut g = Graph::with_vertices(3);
110        g.add_edge(0, 0).unwrap(); // 0: self-loop
111        g.add_edge(0, 1).unwrap(); // 1
112        g.add_edge(1, 2).unwrap(); // 2
113
114        let edges = induced_subgraph_edges(&g, &[0]).unwrap();
115        assert_eq!(edges, vec![0]); // self-loop counts
116    }
117
118    #[test]
119    fn directed_graph() {
120        let mut g = Graph::new(4, true).unwrap();
121        g.add_edge(0, 1).unwrap(); // 0
122        g.add_edge(1, 2).unwrap(); // 1
123        g.add_edge(2, 0).unwrap(); // 2
124        g.add_edge(2, 3).unwrap(); // 3
125
126        let edges = induced_subgraph_edges(&g, &[0, 1, 2]).unwrap();
127        assert_eq!(edges, vec![0, 1, 2]);
128    }
129
130    #[test]
131    fn empty_vertex_set() {
132        let mut g = Graph::with_vertices(3);
133        g.add_edge(0, 1).unwrap();
134
135        let edges = induced_subgraph_edges(&g, &[]).unwrap();
136        assert!(edges.is_empty());
137    }
138
139    #[test]
140    fn no_matching_edges() {
141        let mut g = Graph::with_vertices(4);
142        g.add_edge(0, 1).unwrap();
143        g.add_edge(2, 3).unwrap();
144
145        // Vertices 0 and 2 have no edge between them
146        let edges = induced_subgraph_edges(&g, &[0, 2]).unwrap();
147        assert!(edges.is_empty());
148    }
149
150    #[test]
151    fn duplicate_vertex_ids() {
152        let mut g = Graph::with_vertices(3);
153        g.add_edge(0, 1).unwrap(); // 0
154        g.add_edge(1, 2).unwrap(); // 1
155
156        let edges = induced_subgraph_edges(&g, &[0, 1, 0, 1]).unwrap();
157        assert_eq!(edges, vec![0]);
158    }
159
160    #[test]
161    fn vertex_out_of_range() {
162        let g = Graph::with_vertices(3);
163        let err = induced_subgraph_edges(&g, &[5]).unwrap_err();
164        assert!(matches!(err, IgraphError::InvalidArgument(_)));
165    }
166
167    #[test]
168    fn graph_with_no_edges() {
169        let g = Graph::with_vertices(5);
170        let edges = induced_subgraph_edges(&g, &[0, 1, 2]).unwrap();
171        assert!(edges.is_empty());
172    }
173}
rust_igraph/algorithms/operators/induced_subgraph_edges.rs

rust_igraph/algorithms/operators/
induced_subgraph_edges.rs
