igraph/selector.rs
1//! Vertex and edge selectors.
2//!
3//! Many igraph functions operate on a *set* of vertices or edges, described
4//! by an `igraph_vs_t` / `igraph_es_t` selector. In Rust these are the enums
5//! [`VertexSelector`] and [`EdgeSelector`], which convert from convenient
6//! values thanks to [`From`]:
7//!
8//! | Rust value | Selected vertices | C constructor |
9//! |-------------------------|----------------------------|---------------|
10//! | `..` or `VertexSelector::All` | all vertices | `igraph_vs_all` |
11//! | `VertexSelector::None` | no vertex | `igraph_vs_none` |
12//! | `3` (an `i64`) | the single vertex 3 | `igraph_vs_1` |
13//! | `&[0, 2, 5]`, `vec![..]`, `&VectorInt` | the listed vertices, in order | `igraph_vss_vector` |
14//! | `2..6` | vertices 2, 3, 4, 5 | `igraph_vs_range` |
15//! | `2..=5` | vertices 2, 3, 4, 5 | `igraph_vs_range` |
16//! | `VertexSelector::adjacent(v, mode)` | the neighbors of `v` | `igraph_vs_adj` |
17//! | `VertexSelector::non_adjacent(v, mode)` | the vertices not adjacent to `v` (including `v` itself unless it has a loop) | `igraph_vs_nonadj` |
18//!
19//! | Rust value | Selected edges | C constructor |
20//! |-------------------------|----------------------------|---------------|
21//! | `..` or `EdgeSelector::All`, `EdgeSelector::AllOrdered(order)` | all edges, by id or by endpoint | `igraph_es_all` |
22//! | `EdgeSelector::None` | no edge | `igraph_es_none` |
23//! | `3`, `&[0, 2]`, `vec![..]`, `1..4`, `1..=3` | as for vertices | `igraph_es_1`, `igraph_ess_vector`, `igraph_es_range` |
24//! | [`EdgeSelector::incident(v, mode)`](EdgeSelector::incident) | the edges incident to `v` | `igraph_es_incident` |
25//! | [`EdgeSelector::pairs(&[(a, b), ..], directed)`](EdgeSelector::pairs) | one edge between each pair | `igraph_es_pairs` |
26//! | [`EdgeSelector::path(&[a, b, c, ..], directed)`](EdgeSelector::path) | the edges along a path | `igraph_es_path` |
27//! | [`EdgeSelector::all_between(a, b, directed)`](EdgeSelector::all_between) | all the (multi-)edges between two vertices | `igraph_es_all_between` |
28//!
29//! The immediate constructors (`igraph_vss_none`, `igraph_vss_1`,
30//! `igraph_vss_range`, `igraph_ess_all`, `igraph_ess_none`, `igraph_ess_1`,
31//! `igraph_ess_range`), the copying ones (`igraph_vs_vector_copy`,
32//! `igraph_es_vector_copy`, `igraph_vs_copy`, `igraph_es_copy`), the
33//! non-immediate vector ones (`igraph_vs_vector`, `igraph_es_vector`), the
34//! variadic `*_small` ones (`igraph_vs_vector_small`, `igraph_es_pairs_small`,
35//! `igraph_es_path_small`) and the iterators (`igraph_vit_create`,
36//! `igraph_vit_destroy`, `igraph_vit_as_vector`, `igraph_eit_create`,
37//! `igraph_eit_destroy`, `igraph_eit_as_vector`) are not wrapped: the
38//! constructors in the tables above cover the same selections (a Rust
39//! selector is rebuilt, not copied, for every call), and
40//! [`Graph::select_vertices`](crate::Graph::select_vertices) /
41//! [`Graph::select_edges`](crate::Graph::select_edges) resolve a selector
42//! to a [`Vec`] where C code would iterate.
43//!
44//! The C constructors are documented in the
45//! [Iterators](https://igraph.org/c/html/latest/igraph-Iterators.html)
46//! chapter of the igraph manual. Selectors are resolved against a graph with
47//! [`Graph::select_vertices`](crate::Graph::select_vertices) /
48//! [`Graph::select_edges`](crate::Graph::select_edges) and counted with
49//! [`Graph::vs_size`](crate::Graph::vs_size) /
50//! [`Graph::es_size`](crate::Graph::es_size) (`igraph_iterators.h`).
51//!
52//! Functions accept `impl Into<VertexSelector<'_>>`, e.g.
53//! `graph.degree(.., NeighborMode::All, Loops::Twice)` or
54//! `graph.degree(&[0, 1][..], ...)`.
55//!
56//! ```
57//! use igraph::prelude::*;
58//!
59//! let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3)], 4, false).unwrap();
60//! assert_eq!(g.degree(.., NeighborMode::All, Loops::Twice).unwrap(), vec![2, 2, 3, 1]);
61//! assert_eq!(g.degree(vec![2, 3], NeighborMode::All, Loops::Twice).unwrap(), vec![3, 1]);
62//! let adjacent_to_2 = VertexSelector::Adjacent { vertex: 2, mode: NeighborMode::All };
63//! assert_eq!(g.select_vertices(adjacent_to_2).unwrap(), vec![0, 1, 3]);
64//!
65//! // Edge selectors: remove the triangle's edges along the path 0 - 1 - 2.
66//! let mut h = g.clone();
67//! h.delete_edges(EdgeSelector::path(&[0, 1, 2], false)).unwrap();
68//! assert_eq!(h.edge_list(), vec![(0, 2), (2, 3)]);
69//! ```
70//!
71//! Selectors are accepted all over the crate, e.g. by
72//! [`Graph::induced_subgraph`](crate::Graph::induced_subgraph),
73//! [`Graph::closeness`](crate::Graph::closeness) or
74//! [`Graph::subgraph_from_edges`](crate::Graph::subgraph_from_edges).
75
76use crate::{constants::*, error::Result, ffi::*, vector::VectorInt};
77use std::{borrow::Cow, mem::MaybeUninit, ops::Range};
78
79/// A set of vertices, see the [module docs](self).
80#[derive(Debug, Clone, PartialEq, Eq)]
81pub enum VertexSelector<'a> {
82 /// All vertices, in increasing id order.
83 All,
84 /// No vertex.
85 None,
86 /// A single vertex.
87 Single(igraph_int_t),
88 /// The listed vertices, in the given order (duplicates allowed).
89 List(Cow<'a, [igraph_int_t]>),
90 /// Vertices with id in `start..end`; like a Rust range it is empty
91 /// (and selects nothing, whatever the graph) when `start >= end`.
92 Range(igraph_int_t, igraph_int_t),
93 /// Neighbors of a vertex, each listed once, in increasing order (loops
94 /// and multi-edges are ignored; see
95 /// [`Graph::adjacent_vertices`](crate::Graph::adjacent_vertices) for
96 /// other conventions).
97 Adjacent {
98 /// The center vertex.
99 vertex: igraph_int_t,
100 /// Which neighbors, for directed graphs.
101 mode: NeighborMode,
102 },
103 /// Vertices *not* adjacent to a vertex.
104 NonAdjacent {
105 /// The center vertex.
106 vertex: igraph_int_t,
107 /// Which neighbors, for directed graphs.
108 mode: NeighborMode,
109 },
110}
111
112impl From<std::ops::RangeFull> for VertexSelector<'_> {
113 fn from(_: std::ops::RangeFull) -> Self {
114 Self::All
115 }
116}
117
118impl From<igraph_int_t> for VertexSelector<'_> {
119 fn from(v: igraph_int_t) -> Self {
120 Self::Single(v)
121 }
122}
123
124impl<'a> From<&'a [igraph_int_t]> for VertexSelector<'a> {
125 fn from(v: &'a [igraph_int_t]) -> Self {
126 Self::List(Cow::Borrowed(v))
127 }
128}
129
130impl<'a, const N: usize> From<&'a [igraph_int_t; N]> for VertexSelector<'a> {
131 fn from(v: &'a [igraph_int_t; N]) -> Self {
132 Self::List(Cow::Borrowed(v))
133 }
134}
135
136impl<'a> From<&'a Vec<igraph_int_t>> for VertexSelector<'a> {
137 fn from(v: &'a Vec<igraph_int_t>) -> Self {
138 Self::List(Cow::Borrowed(v))
139 }
140}
141
142impl<'a> From<&'a VectorInt> for VertexSelector<'a> {
143 fn from(v: &'a VectorInt) -> Self {
144 Self::List(Cow::Borrowed(v.as_slice()))
145 }
146}
147
148impl From<Vec<igraph_int_t>> for VertexSelector<'_> {
149 fn from(v: Vec<igraph_int_t>) -> Self {
150 Self::List(Cow::Owned(v))
151 }
152}
153
154impl From<Range<igraph_int_t>> for VertexSelector<'_> {
155 fn from(r: Range<igraph_int_t>) -> Self {
156 Self::Range(r.start, r.end)
157 }
158}
159
160impl From<std::ops::RangeInclusive<igraph_int_t>> for VertexSelector<'_> {
161 /// `a..=b` selects the vertices `a, a + 1, ..., b` (none if `a > b`).
162 fn from(r: std::ops::RangeInclusive<igraph_int_t>) -> Self {
163 if r.is_empty() {
164 Self::None
165 } else {
166 // `b + 1` cannot overflow for a valid id; `i64::MAX` is invalid
167 // anyway and still makes igraph report an error.
168 Self::Range(*r.start(), r.end().saturating_add(1))
169 }
170 }
171}
172
173impl<'a> VertexSelector<'a> {
174 /// The neighbors of `vertex` (shorthand for [`VertexSelector::Adjacent`]).
175 pub fn adjacent(vertex: igraph_int_t, mode: NeighborMode) -> Self {
176 Self::Adjacent { vertex, mode }
177 }
178
179 /// The vertices not adjacent to `vertex` (shorthand for
180 /// [`VertexSelector::NonAdjacent`]).
181 pub fn non_adjacent(vertex: igraph_int_t, mode: NeighborMode) -> Self {
182 Self::NonAdjacent { vertex, mode }
183 }
184
185 /// An owned copy of the selector, not borrowing anything.
186 pub fn into_owned(self) -> VertexSelector<'static> {
187 match self {
188 Self::All => VertexSelector::All,
189 Self::None => VertexSelector::None,
190 Self::Single(v) => VertexSelector::Single(v),
191 Self::List(l) => VertexSelector::List(Cow::Owned(l.into_owned())),
192 Self::Range(a, b) => VertexSelector::Range(a, b),
193 Self::Adjacent { vertex, mode } => VertexSelector::Adjacent { vertex, mode },
194 Self::NonAdjacent { vertex, mode } => VertexSelector::NonAdjacent { vertex, mode },
195 }
196 }
197}
198
199/// A raw `igraph_vs_t` together with the storage it points to.
200///
201/// Created by [`VertexSelector::to_raw`]; call [`RawVs::get`] to obtain the
202/// `igraph_vs_t` to pass *by value* to igraph functions. The storage stays
203/// alive as long as this value does.
204pub struct RawVs {
205 vs: igraph_vs_t,
206 // Boxed: `vs` may point to this vector, whose address must therefore not
207 // change when `RawVs` is moved.
208 _storage: Option<Box<VectorInt>>,
209}
210
211impl RawVs {
212 /// A bitwise copy of the selector, to be passed by value to igraph.
213 ///
214 /// Selectors built here never own heap memory, so copies are harmless.
215 pub fn get(&self) -> igraph_vs_t {
216 unsafe { std::ptr::read(&self.vs) }
217 }
218
219 /// Pointer to the selector, for functions taking `const igraph_vs_t *`.
220 pub fn as_ptr(&self) -> *const igraph_vs_t {
221 &self.vs
222 }
223
224 /// Whether the selector denotes all vertices
225 /// ([`igraph_vs_is_all`](https://igraph.org/c/html/latest/igraph-Iterators.html#igraph_vs_is_all)).
226 pub fn is_all(&self) -> bool {
227 unsafe { igraph_vs_is_all(&self.vs) }
228 }
229
230 /// The raw selector type (`igraph_vs_type`), e.g. `IGRAPH_VS_ALL`.
231 pub fn raw_type(&self) -> igraph_vs_type_t {
232 unsafe { igraph_vs_type(&self.vs) }
233 }
234}
235
236impl VertexSelector<'_> {
237 /// Builds the raw igraph selector (`igraph_vs_t`), for calling raw FFI
238 /// functions; the safe wrappers of the crate do it for you.
239 ///
240 /// Empty ranges (`start >= end`) become `igraph_vs_none`: igraph 1.0.0
241 /// and 1.0.1 would reject an empty range starting at `vcount` and accept
242 /// a decreasing one with a negative size.
243 ///
244 /// # Errors
245 /// Only if igraph fails to build the selector (e.g. out of memory);
246 /// vertex ids are validated when the selector is used.
247 pub fn to_raw(&self) -> Result<RawVs> {
248 crate::error::ensure_init();
249 let mut vs = MaybeUninit::<igraph_vs_t>::uninit();
250 let mut storage = None;
251 unsafe {
252 match self {
253 Self::All => crate::igraph_call!(igraph_vs_all(vs.as_mut_ptr()))?,
254 Self::None => crate::igraph_call!(igraph_vs_none(vs.as_mut_ptr()))?,
255 Self::Single(v) => crate::igraph_call!(igraph_vs_1(vs.as_mut_ptr(), *v))?,
256 Self::List(list) => {
257 // The selector stores a *pointer* to the vector: box it so
258 // that it never moves (a moved-from stack slot would dangle).
259 let v = Box::new(VectorInt::from_slice(list));
260 vs.write(igraph_vss_vector(&*v));
261 storage = Some(v);
262 }
263 // igraph 1.0.0 and 1.0.1 reject an empty range starting at
264 // `vcount` and accept a *decreasing* one, whose size
265 // (`end - start`) is then negative: map every empty range to
266 // "no vertex".
267 Self::Range(start, end) if start >= end => {
268 crate::igraph_call!(igraph_vs_none(vs.as_mut_ptr()))?
269 }
270 Self::Range(start, end) => {
271 crate::igraph_call!(igraph_vs_range(vs.as_mut_ptr(), *start, *end))?
272 }
273 Self::Adjacent { vertex, mode } => crate::igraph_call!(igraph_vs_adj(
274 vs.as_mut_ptr(),
275 *vertex,
276 (*mode).into(),
277 Loops::None.into(),
278 false
279 ))?,
280 Self::NonAdjacent { vertex, mode } => {
281 crate::igraph_call!(igraph_vs_nonadj(vs.as_mut_ptr(), *vertex, (*mode).into()))?
282 }
283 }
284 Ok(RawVs {
285 vs: vs.assume_init(),
286 _storage: storage,
287 })
288 }
289 }
290}
291
292/// A set of edges, see the [module docs](self).
293#[derive(Debug, Clone, PartialEq, Eq)]
294pub enum EdgeSelector<'a> {
295 /// All edges, ordered by id.
296 All,
297 /// All edges, in the given order.
298 AllOrdered(EdgeOrder),
299 /// No edge.
300 None,
301 /// A single edge.
302 Single(igraph_int_t),
303 /// The listed edges, in the given order.
304 List(Cow<'a, [igraph_int_t]>),
305 /// Edges with id in `start..end`; like a Rust range it is empty
306 /// (and selects nothing, whatever the graph) when `start >= end`.
307 Range(igraph_int_t, igraph_int_t),
308 /// Edges incident to a vertex, each loop edge listed once (use
309 /// [`Graph::incident_edges`](crate::Graph::incident_edges) to choose how
310 /// loops are counted).
311 Incident {
312 /// The vertex.
313 vertex: igraph_int_t,
314 /// Which incident edges, for directed graphs.
315 mode: NeighborMode,
316 },
317 /// The edges connecting the given `(from, to)` vertex pairs (one per pair).
318 Pairs {
319 /// Endpoint pairs.
320 pairs: Cow<'a, [(igraph_int_t, igraph_int_t)]>,
321 /// Whether to respect edge directions.
322 directed: bool,
323 },
324 /// The edges along a path given as a vertex sequence.
325 Path {
326 /// The vertices of the path.
327 vertices: Cow<'a, [igraph_int_t]>,
328 /// Whether to respect edge directions.
329 directed: bool,
330 },
331 /// All the (possibly multiple) edges between two vertices.
332 AllBetween {
333 /// Source vertex.
334 from: igraph_int_t,
335 /// Target vertex.
336 to: igraph_int_t,
337 /// Whether to respect edge directions.
338 directed: bool,
339 },
340}
341
342impl From<std::ops::RangeFull> for EdgeSelector<'_> {
343 fn from(_: std::ops::RangeFull) -> Self {
344 Self::All
345 }
346}
347
348impl From<igraph_int_t> for EdgeSelector<'_> {
349 fn from(e: igraph_int_t) -> Self {
350 Self::Single(e)
351 }
352}
353
354impl<'a> From<&'a [igraph_int_t]> for EdgeSelector<'a> {
355 fn from(e: &'a [igraph_int_t]) -> Self {
356 Self::List(Cow::Borrowed(e))
357 }
358}
359
360impl<'a, const N: usize> From<&'a [igraph_int_t; N]> for EdgeSelector<'a> {
361 fn from(e: &'a [igraph_int_t; N]) -> Self {
362 Self::List(Cow::Borrowed(e))
363 }
364}
365
366impl<'a> From<&'a Vec<igraph_int_t>> for EdgeSelector<'a> {
367 fn from(e: &'a Vec<igraph_int_t>) -> Self {
368 Self::List(Cow::Borrowed(e))
369 }
370}
371
372impl<'a> From<&'a VectorInt> for EdgeSelector<'a> {
373 fn from(e: &'a VectorInt) -> Self {
374 Self::List(Cow::Borrowed(e.as_slice()))
375 }
376}
377
378impl From<Vec<igraph_int_t>> for EdgeSelector<'_> {
379 fn from(e: Vec<igraph_int_t>) -> Self {
380 Self::List(Cow::Owned(e))
381 }
382}
383
384impl From<Range<igraph_int_t>> for EdgeSelector<'_> {
385 fn from(r: Range<igraph_int_t>) -> Self {
386 Self::Range(r.start, r.end)
387 }
388}
389
390impl From<std::ops::RangeInclusive<igraph_int_t>> for EdgeSelector<'_> {
391 /// `a..=b` selects the edges `a, a + 1, ..., b` (none if `a > b`).
392 fn from(r: std::ops::RangeInclusive<igraph_int_t>) -> Self {
393 if r.is_empty() {
394 Self::None
395 } else {
396 Self::Range(*r.start(), r.end().saturating_add(1))
397 }
398 }
399}
400
401impl<'a> EdgeSelector<'a> {
402 /// The edges incident to `vertex` (shorthand for [`EdgeSelector::Incident`]).
403 pub fn incident(vertex: igraph_int_t, mode: NeighborMode) -> Self {
404 Self::Incident { vertex, mode }
405 }
406
407 /// One edge between each `(from, to)` pair (shorthand for
408 /// [`EdgeSelector::Pairs`]).
409 pub fn pairs(pairs: &'a [(igraph_int_t, igraph_int_t)], directed: bool) -> Self {
410 Self::Pairs {
411 pairs: Cow::Borrowed(pairs),
412 directed,
413 }
414 }
415
416 /// The edges along a vertex path (shorthand for [`EdgeSelector::Path`]).
417 pub fn path(vertices: &'a [igraph_int_t], directed: bool) -> Self {
418 Self::Path {
419 vertices: Cow::Borrowed(vertices),
420 directed,
421 }
422 }
423
424 /// All edges between two vertices (shorthand for [`EdgeSelector::AllBetween`]).
425 pub fn all_between(from: igraph_int_t, to: igraph_int_t, directed: bool) -> Self {
426 Self::AllBetween { from, to, directed }
427 }
428}
429
430/// A raw `igraph_es_t` together with the storage it points to; it is
431/// destroyed (with `igraph_es_destroy`) on drop.
432pub struct RawEs {
433 es: igraph_es_t,
434 // Boxed: `es` may point to this vector, whose address must therefore not
435 // change when `RawEs` is moved.
436 _storage: Option<Box<VectorInt>>,
437}
438
439impl RawEs {
440 /// A bitwise copy of the selector, to be passed by value to igraph.
441 /// The copy must not outlive `self` nor be destroyed.
442 pub fn get(&self) -> igraph_es_t {
443 unsafe { std::ptr::read(&self.es) }
444 }
445
446 /// Pointer to the selector, for functions taking `const igraph_es_t *`.
447 pub fn as_ptr(&self) -> *const igraph_es_t {
448 &self.es
449 }
450
451 /// Whether the selector denotes all edges
452 /// ([`igraph_es_is_all`](https://igraph.org/c/html/latest/igraph-Iterators.html#igraph_es_is_all)).
453 pub fn is_all(&self) -> bool {
454 unsafe { igraph_es_is_all(&self.es) }
455 }
456
457 /// The raw selector type (`igraph_es_type`), e.g. `IGRAPH_ES_PAIRS`.
458 pub fn raw_type(&self) -> igraph_es_type_t {
459 unsafe { igraph_es_type(&self.es) }
460 }
461}
462
463impl Drop for RawEs {
464 fn drop(&mut self) {
465 unsafe { igraph_es_destroy(&mut self.es) };
466 }
467}
468
469impl EdgeSelector<'_> {
470 /// Builds the raw igraph selector (`igraph_es_t`), for calling raw FFI
471 /// functions; the safe wrappers of the crate do it for you. Empty ranges
472 /// select nothing, as for [`VertexSelector::to_raw`].
473 ///
474 /// # Errors
475 /// Only if igraph fails to build the selector (e.g. out of memory); ids
476 /// are validated when the selector is used.
477 pub fn to_raw(&self) -> Result<RawEs> {
478 crate::error::ensure_init();
479 let mut es = MaybeUninit::<igraph_es_t>::uninit();
480 let mut storage = None;
481 unsafe {
482 match self {
483 Self::All => {
484 crate::igraph_call!(igraph_es_all(es.as_mut_ptr(), EdgeOrder::Id.into()))?
485 }
486 Self::AllOrdered(order) => {
487 crate::igraph_call!(igraph_es_all(es.as_mut_ptr(), (*order).into()))?
488 }
489 Self::None => crate::igraph_call!(igraph_es_none(es.as_mut_ptr()))?,
490 Self::Single(e) => crate::igraph_call!(igraph_es_1(es.as_mut_ptr(), *e))?,
491 Self::List(list) => {
492 // The selector stores a *pointer* to the vector: box it so
493 // that it never moves (a moved-from stack slot would dangle).
494 let v = Box::new(VectorInt::from_slice(list));
495 es.write(igraph_ess_vector(&*v));
496 storage = Some(v);
497 }
498 // See `VertexSelector::to_raw`: empty ranges select nothing.
499 Self::Range(start, end) if start >= end => {
500 crate::igraph_call!(igraph_es_none(es.as_mut_ptr()))?
501 }
502 Self::Range(start, end) => {
503 crate::igraph_call!(igraph_es_range(es.as_mut_ptr(), *start, *end))?
504 }
505 Self::Incident { vertex, mode } => crate::igraph_call!(igraph_es_incident(
506 es.as_mut_ptr(),
507 *vertex,
508 (*mode).into(),
509 // A selector denotes a *set* of edges: list loops once
510 // (with `Twice`, deleting them would name them twice).
511 Loops::Once.into()
512 ))?,
513 Self::Pairs { pairs, directed } => {
514 let flat: VectorInt = pairs.iter().flat_map(|&(a, b)| [a, b]).collect();
515 crate::igraph_call!(igraph_es_pairs(es.as_mut_ptr(), &flat, *directed))?
516 }
517 Self::Path { vertices, directed } => {
518 let v = VectorInt::from_slice(vertices);
519 crate::igraph_call!(igraph_es_path(es.as_mut_ptr(), &v, *directed))?
520 }
521 Self::AllBetween { from, to, directed } => crate::igraph_call!(
522 igraph_es_all_between(es.as_mut_ptr(), *from, *to, *directed)
523 )?,
524 }
525 Ok(RawEs {
526 es: es.assume_init(),
527 _storage: storage,
528 })
529 }
530 }
531}