rust_igraph/algorithms/paths/
edge_path_to_vertex_path.rs

1//! Edge path to vertex path conversion (ALGO-SP-030).
2//!
3//! Counterpart of `igraph_vertex_path_from_edge_path()` from
4//! `references/igraph/src/misc/other.c`.
5//!
6//! Converts a walk described by edge IDs into the corresponding sequence
7//! of vertex IDs.
8
9use crate::core::{Graph, IgraphError, IgraphResult};
10
11/// Direction mode for edge-path traversal.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum WalkMode {
14    /// Follow outgoing edges (from → to).
15    Out,
16    /// Follow incoming edges (to → from).
17    In,
18    /// Ignore edge direction.
19    All,
20}
21
22/// Convert an edge path to a vertex path.
23///
24/// Given a sequence of edge IDs forming a continuous walk starting at
25/// `start`, returns the sequence of vertex IDs traversed. The result
26/// always has `edge_path.len() + 1` elements.
27///
28/// If `start` is `None`, the start vertex is inferred from the first
29/// edge (requires at least one edge). For directed graphs with `WalkMode::Out`,
30/// the source of the first edge is used; for `In`, the target is used.
31/// For undirected graphs or `All` mode with multiple edges, the vertex
32/// connecting the first two edges is determined.
33///
34/// The `mode` parameter is ignored for undirected graphs (treated as `All`).
35///
36/// # Errors
37///
38/// - `InvalidArgument` if `start` is out of range.
39/// - `InvalidArgument` if `start` is `None` and `edge_path` is empty.
40/// - `InvalidArgument` if the edge IDs do not form a continuous path.
41///
42/// # Examples
43///
44/// ```
45/// use rust_igraph::{Graph, vertex_path_from_edge_path, WalkMode};
46///
47/// let mut g = Graph::with_vertices(4);
48/// g.add_edge(0, 1).unwrap(); // eid 0
49/// g.add_edge(1, 2).unwrap(); // eid 1
50/// g.add_edge(2, 3).unwrap(); // eid 2
51///
52/// let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 1, 2], WalkMode::All).unwrap();
53/// assert_eq!(vpath, vec![0, 1, 2, 3]);
54/// ```
55pub fn vertex_path_from_edge_path(
56    graph: &Graph,
57    start: Option<u32>,
58    edge_path: &[u32],
59    mode: WalkMode,
60) -> IgraphResult<Vec<u32>> {
61    let effective_mode = if graph.is_directed() {
62        mode
63    } else {
64        WalkMode::All
65    };
66
67    let mut current = if let Some(v) = start {
68        if v >= graph.vcount() {
69            return Err(IgraphError::InvalidArgument(format!(
70                "vertex_path_from_edge_path: start vertex {v} out of range"
71            )));
72        }
73        v
74    } else {
75        if edge_path.is_empty() {
76            return Err(IgraphError::InvalidArgument(
77                "vertex_path_from_edge_path: cannot infer start vertex from empty edge path".into(),
78            ));
79        }
80        infer_start(graph, edge_path, effective_mode)?
81    };
82
83    let mut vertex_path: Vec<u32> = Vec::with_capacity(edge_path.len().saturating_add(1));
84
85    for (i, &eid) in edge_path.iter().enumerate() {
86        let (from, to) = graph.edge(eid)?;
87        vertex_path.push(current);
88
89        let (ok, next) = match effective_mode {
90            WalkMode::Out => (from == current, to),
91            WalkMode::In => (to == current, from),
92            WalkMode::All => {
93                if from == current {
94                    (true, to)
95                } else if to == current {
96                    (true, from)
97                } else {
98                    (false, 0)
99                }
100            }
101        };
102
103        if !ok {
104            return Err(IgraphError::InvalidArgument(format!(
105                "vertex_path_from_edge_path: edge {eid} at position {i} does not connect to \
106                 current vertex {current}"
107            )));
108        }
109
110        current = next;
111    }
112
113    vertex_path.push(current);
114    Ok(vertex_path)
115}
116
117fn infer_start(graph: &Graph, edge_path: &[u32], mode: WalkMode) -> IgraphResult<u32> {
118    let (from, to) = graph.edge(edge_path[0])?;
119    match mode {
120        WalkMode::Out => Ok(from),
121        WalkMode::In => Ok(to),
122        WalkMode::All => {
123            if edge_path.len() > 1 {
124                let (from2, to2) = graph.edge(edge_path[1])?;
125                if to == from2 || to == to2 {
126                    Ok(from)
127                } else {
128                    Ok(to)
129                }
130            } else {
131                Ok(from)
132            }
133        }
134    }
135}
136
137#[cfg(test)]
138mod tests {
139    use super::*;
140
141    fn make_undirected(n: u32, edges: &[(u32, u32)]) -> Graph {
142        let mut g = Graph::with_vertices(n);
143        for &(u, v) in edges {
144            g.add_edge(u, v).unwrap();
145        }
146        g
147    }
148
149    #[test]
150    fn empty_edge_path_with_start() {
151        let g = make_undirected(3, &[(0, 1), (1, 2)]);
152        let vpath = vertex_path_from_edge_path(&g, Some(1), &[], WalkMode::All).unwrap();
153        assert_eq!(vpath, vec![1]);
154    }
155
156    #[test]
157    fn empty_edge_path_no_start_error() {
158        let g = make_undirected(3, &[(0, 1), (1, 2)]);
159        let err = vertex_path_from_edge_path(&g, None, &[], WalkMode::All).unwrap_err();
160        assert!(matches!(err, IgraphError::InvalidArgument(_)));
161    }
162
163    #[test]
164    fn simple_path_undirected() {
165        let g = make_undirected(4, &[(0, 1), (1, 2), (2, 3)]);
166        let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 1, 2], WalkMode::All).unwrap();
167        assert_eq!(vpath, vec![0, 1, 2, 3]);
168    }
169
170    #[test]
171    fn reverse_path_undirected() {
172        let g = make_undirected(4, &[(0, 1), (1, 2), (2, 3)]);
173        let vpath = vertex_path_from_edge_path(&g, Some(3), &[2, 1, 0], WalkMode::All).unwrap();
174        assert_eq!(vpath, vec![3, 2, 1, 0]);
175    }
176
177    #[test]
178    fn directed_out_mode() {
179        let mut g = Graph::new(4, true).unwrap();
180        g.add_edge(0, 1).unwrap(); // eid 0
181        g.add_edge(1, 2).unwrap(); // eid 1
182        g.add_edge(2, 3).unwrap(); // eid 2
183        let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 1, 2], WalkMode::Out).unwrap();
184        assert_eq!(vpath, vec![0, 1, 2, 3]);
185    }
186
187    #[test]
188    fn directed_in_mode() {
189        let mut g = Graph::new(4, true).unwrap();
190        g.add_edge(0, 1).unwrap(); // eid 0
191        g.add_edge(1, 2).unwrap(); // eid 1
192        g.add_edge(2, 3).unwrap(); // eid 2
193        let vpath = vertex_path_from_edge_path(&g, Some(3), &[2, 1, 0], WalkMode::In).unwrap();
194        assert_eq!(vpath, vec![3, 2, 1, 0]);
195    }
196
197    #[test]
198    fn directed_discontinuous_error() {
199        let mut g = Graph::new(4, true).unwrap();
200        g.add_edge(0, 1).unwrap(); // eid 0
201        g.add_edge(2, 3).unwrap(); // eid 1
202        let err = vertex_path_from_edge_path(&g, Some(0), &[0, 1], WalkMode::Out).unwrap_err();
203        assert!(matches!(err, IgraphError::InvalidArgument(_)));
204    }
205
206    #[test]
207    fn infer_start_out() {
208        let mut g = Graph::new(3, true).unwrap();
209        g.add_edge(0, 1).unwrap();
210        g.add_edge(1, 2).unwrap();
211        let vpath = vertex_path_from_edge_path(&g, None, &[0, 1], WalkMode::Out).unwrap();
212        assert_eq!(vpath, vec![0, 1, 2]);
213    }
214
215    #[test]
216    fn infer_start_in() {
217        let mut g = Graph::new(3, true).unwrap();
218        g.add_edge(0, 1).unwrap();
219        g.add_edge(1, 2).unwrap();
220        let vpath = vertex_path_from_edge_path(&g, None, &[1, 0], WalkMode::In).unwrap();
221        assert_eq!(vpath, vec![2, 1, 0]);
222    }
223
224    #[test]
225    fn infer_start_all_multiple_edges() {
226        let g = make_undirected(4, &[(0, 1), (1, 2), (2, 3)]);
227        let vpath = vertex_path_from_edge_path(&g, None, &[0, 1, 2], WalkMode::All).unwrap();
228        assert_eq!(vpath, vec![0, 1, 2, 3]);
229    }
230
231    #[test]
232    fn infer_start_all_single_edge() {
233        let g = make_undirected(2, &[(0, 1)]);
234        let vpath = vertex_path_from_edge_path(&g, None, &[0], WalkMode::All).unwrap();
235        // Should pick from (0) as start
236        assert_eq!(vpath.len(), 2);
237        assert!(vpath == vec![0, 1] || vpath == vec![1, 0]);
238    }
239
240    #[test]
241    fn cycle_walk() {
242        let g = make_undirected(3, &[(0, 1), (1, 2), (2, 0)]);
243        let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 1, 2], WalkMode::All).unwrap();
244        assert_eq!(vpath, vec![0, 1, 2, 0]);
245    }
246
247    #[test]
248    fn start_vertex_out_of_range() {
249        let g = make_undirected(3, &[(0, 1)]);
250        let err = vertex_path_from_edge_path(&g, Some(10), &[0], WalkMode::All).unwrap_err();
251        assert!(matches!(err, IgraphError::InvalidArgument(_)));
252    }
253
254    #[test]
255    fn walk_with_repeated_vertex() {
256        // Walk: 0→1→0→1 via edges 0, 0, 0
257        let g = make_undirected(2, &[(0, 1)]);
258        let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 0, 0], WalkMode::All).unwrap();
259        assert_eq!(vpath, vec![0, 1, 0, 1]);
260    }
261
262    #[test]
263    fn directed_all_mode_ignores_direction() {
264        let mut g = Graph::new(3, true).unwrap();
265        g.add_edge(0, 1).unwrap(); // eid 0
266        g.add_edge(2, 1).unwrap(); // eid 1: 2→1, so traversing 1→2 in ALL mode
267        let vpath = vertex_path_from_edge_path(&g, Some(0), &[0, 1], WalkMode::All).unwrap();
268        assert_eq!(vpath, vec![0, 1, 2]);
269    }
270}
rust_igraph/algorithms/paths/edge_path_to_vertex_path.rs

rust_igraph/algorithms/paths/
edge_path_to_vertex_path.rs
