rust_igraph/algorithms/properties/
unfold_tree.rs

1//! Unfold a graph into a tree (ALGO-PR-036).
2//!
3//! Performs BFS from given roots and replicates vertices visited more
4//! than once. The result is a tree (or forest) with the same local
5//! neighbourhood structure as the original graph.
6//!
7//! Counterpart of `igraph_unfold_tree`.
8
9use std::collections::VecDeque;
10
11use crate::core::graph::EdgeId;
12use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
13
14/// Result of unfolding a graph into a tree.
15#[derive(Debug, Clone)]
16pub struct UnfoldTreeResult {
17    /// The unfolded tree (or forest).
18    pub tree: Graph,
19    /// Mapping from tree vertices to original graph vertices.
20    /// `vertex_index[v_tree]` gives the original vertex ID.
21    pub vertex_index: Vec<VertexId>,
22}
23
24/// Unfold a graph into a tree by BFS, replicating multiply-visited
25/// vertices.
26///
27/// Starting from each root, BFS explores the graph. The first time a
28/// vertex is reached, it keeps its original ID. Subsequent visits via
29/// different edges create replica vertices with new IDs. The result
30/// is always a tree (or forest if multiple roots cover disjoint
31/// components).
32///
33/// For directed graphs, `mode` controls traversal: `Out` follows
34/// outgoing edges, `In` follows incoming edges, `All` ignores
35/// direction.
36///
37/// # Errors
38///
39/// Returns an error if any root is out of range.
40///
41/// # Examples
42///
43/// ```
44/// use rust_igraph::{Graph, unfold_tree, DegreeMode};
45///
46/// // Triangle: unfolding from vertex 0 creates a tree with 4 vertices.
47/// let mut g = Graph::with_vertices(3);
48/// g.add_edge(0, 1).unwrap();
49/// g.add_edge(1, 2).unwrap();
50/// g.add_edge(2, 0).unwrap();
51/// let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
52/// // BFS from 0: sees 1,2 directly. Edge 1-2 creates a replica.
53/// assert_eq!(result.tree.vcount(), 4);
54/// assert_eq!(result.tree.ecount(), 3);
55/// ```
56pub fn unfold_tree(
57    graph: &Graph,
58    roots: &[VertexId],
59    mode: crate::algorithms::properties::degree::DegreeMode,
60) -> IgraphResult<UnfoldTreeResult> {
61    let n = graph.vcount();
62    let ecount = graph.ecount();
63
64    for &r in roots {
65        if r >= n {
66            return Err(IgraphError::InvalidArgument(format!(
67                "unfold_tree: root {r} out of range (vcount = {n})"
68            )));
69        }
70    }
71
72    let mut edges: Vec<(VertexId, VertexId)> = Vec::with_capacity(ecount);
73    let mut vertex_index: Vec<VertexId> = (0..n).collect();
74    let mut seen_vertices = vec![false; n as usize];
75    let mut seen_edges = vec![false; ecount];
76    let mut queue: VecDeque<VertexId> = VecDeque::new();
77    let mut tree_vcount = n;
78
79    for &root in roots {
80        if seen_vertices[root as usize] {
81            continue;
82        }
83        seen_vertices[root as usize] = true;
84        queue.push_back(root);
85
86        while let Some(actnode) = queue.pop_front() {
87            let incident_edges = get_incident(graph, actnode, mode)?;
88
89            for eid in incident_edges {
90                if seen_edges[eid as usize] {
91                    continue;
92                }
93                seen_edges[eid as usize] = true;
94
95                let (from, to) = graph.edge(eid)?;
96                let nei = if from == actnode { to } else { from };
97
98                if seen_vertices[nei as usize] {
99                    let new_vid = tree_vcount;
100                    tree_vcount += 1;
101                    vertex_index.push(nei);
102
103                    if from == nei {
104                        edges.push((new_vid, to));
105                    } else {
106                        edges.push((from, new_vid));
107                    }
108                } else {
109                    edges.push((from, to));
110                    seen_vertices[nei as usize] = true;
111                    queue.push_back(nei);
112                }
113            }
114        }
115    }
116
117    let mut tree = Graph::new(tree_vcount, graph.is_directed())?;
118    tree.add_edges(edges)?;
119
120    Ok(UnfoldTreeResult { tree, vertex_index })
121}
122
123fn get_incident(
124    graph: &Graph,
125    v: VertexId,
126    mode: crate::algorithms::properties::degree::DegreeMode,
127) -> IgraphResult<Vec<EdgeId>> {
128    use crate::algorithms::properties::degree::DegreeMode;
129
130    match mode {
131        DegreeMode::Out => graph.incident(v),
132        DegreeMode::In => graph.incident_in(v),
133        DegreeMode::All => {
134            let mut out = graph.incident(v)?;
135            if graph.is_directed() {
136                let in_edges = graph.incident_in(v)?;
137                for eid in in_edges {
138                    if !out.contains(&eid) {
139                        out.push(eid);
140                    }
141                }
142            }
143            Ok(out)
144        }
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151    use crate::algorithms::properties::degree::DegreeMode;
152
153    #[test]
154    fn empty_graph() {
155        let g = Graph::with_vertices(0);
156        let result = unfold_tree(&g, &[], DegreeMode::All).unwrap();
157        assert_eq!(result.tree.vcount(), 0);
158        assert_eq!(result.tree.ecount(), 0);
159    }
160
161    #[test]
162    fn single_vertex() {
163        let g = Graph::with_vertices(1);
164        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
165        assert_eq!(result.tree.vcount(), 1);
166        assert_eq!(result.tree.ecount(), 0);
167    }
168
169    #[test]
170    fn tree_stays_tree() {
171        let mut g = Graph::with_vertices(4);
172        g.add_edge(0, 1).unwrap();
173        g.add_edge(0, 2).unwrap();
174        g.add_edge(0, 3).unwrap();
175        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
176        assert_eq!(result.tree.vcount(), 4);
177        assert_eq!(result.tree.ecount(), 3);
178        assert_eq!(result.vertex_index, vec![0, 1, 2, 3]);
179    }
180
181    #[test]
182    fn triangle_unfolds() {
183        let mut g = Graph::with_vertices(3);
184        g.add_edge(0, 1).unwrap();
185        g.add_edge(1, 2).unwrap();
186        g.add_edge(2, 0).unwrap();
187        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
188        // Triangle has one extra edge beyond a tree; one vertex gets replicated
189        assert_eq!(result.tree.vcount(), 4);
190        assert_eq!(result.tree.ecount(), 3);
191        // The first 3 entries in vertex_index are identity
192        assert_eq!(result.vertex_index[0], 0);
193        assert_eq!(result.vertex_index[1], 1);
194        assert_eq!(result.vertex_index[2], 2);
195    }
196
197    #[test]
198    fn k4_unfolds() {
199        let mut g = Graph::with_vertices(4);
200        g.add_edge(0, 1).unwrap();
201        g.add_edge(0, 2).unwrap();
202        g.add_edge(0, 3).unwrap();
203        g.add_edge(1, 2).unwrap();
204        g.add_edge(1, 3).unwrap();
205        g.add_edge(2, 3).unwrap();
206        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
207        // K4: 6 edges, spanning tree has 3 → 3 extra edges → 3 replicas
208        assert_eq!(result.tree.ecount(), 6);
209        assert_eq!(result.tree.vcount(), 7);
210    }
211
212    #[test]
213    fn two_components() {
214        let mut g = Graph::with_vertices(4);
215        g.add_edge(0, 1).unwrap();
216        g.add_edge(2, 3).unwrap();
217        let result = unfold_tree(&g, &[0, 2], DegreeMode::All).unwrap();
218        // Already a forest, no replication
219        assert_eq!(result.tree.vcount(), 4);
220        assert_eq!(result.tree.ecount(), 2);
221    }
222
223    #[test]
224    fn directed_out_mode() {
225        let mut g = Graph::new(3, true).unwrap();
226        g.add_edge(0, 1).unwrap();
227        g.add_edge(0, 2).unwrap();
228        g.add_edge(1, 2).unwrap();
229        let result = unfold_tree(&g, &[0], DegreeMode::Out).unwrap();
230        // From 0: out-edges to 1, 2. From 1: out-edge to 2 (replica).
231        assert_eq!(result.tree.vcount(), 4);
232        assert_eq!(result.tree.ecount(), 3);
233    }
234
235    #[test]
236    fn root_out_of_range() {
237        let g = Graph::with_vertices(3);
238        assert!(unfold_tree(&g, &[5], DegreeMode::All).is_err());
239    }
240
241    #[test]
242    fn vertex_index_correctness() {
243        let mut g = Graph::with_vertices(3);
244        g.add_edge(0, 1).unwrap();
245        g.add_edge(1, 2).unwrap();
246        g.add_edge(2, 0).unwrap();
247        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
248        // All vertex_index entries should be valid original vertices
249        for &orig in &result.vertex_index {
250            assert!(orig < 3);
251        }
252    }
253
254    #[test]
255    fn cycle_5() {
256        let mut g = Graph::with_vertices(5);
257        g.add_edge(0, 1).unwrap();
258        g.add_edge(1, 2).unwrap();
259        g.add_edge(2, 3).unwrap();
260        g.add_edge(3, 4).unwrap();
261        g.add_edge(4, 0).unwrap();
262        let result = unfold_tree(&g, &[0], DegreeMode::All).unwrap();
263        // C5: 5 edges, spanning tree 4 → 1 replica
264        assert_eq!(result.tree.vcount(), 6);
265        assert_eq!(result.tree.ecount(), 5);
266    }
267}
rust_igraph/algorithms/properties/unfold_tree.rs

rust_igraph/algorithms/properties/
unfold_tree.rs
