igraph/cocitation.rs
1//! Cocitation, bibliographic coupling and vertex similarity
2//! (`igraph_cocitation.h`).
3//!
4//! This module binds the functions of igraph's `igraph_cocitation.h` header
5//! (documented in the
6//! [Similarity measures](https://igraph.org/c/html/latest/igraph-Structural.html#similarity-measures)
7//! section of the Structural chapter of the C manual) as methods of [`Graph`]. They all measure how
8//! *similar* two vertices are by looking at the neighbors they share:
9//!
10//! - **cocitation**: how many vertices cite (point to) *both* of them;
11//! - **bibliographic coupling**: how many vertices *both* of them cite;
12//! - **Jaccard** similarity: `|N(u) ∩ N(v)| / |N(u) ∪ N(v)|`;
13//! - **Dice** similarity: `2 |N(u) ∩ N(v)| / (|N(u)| + |N(v)|)`, a monotone
14//! function of the Jaccard one (`D = 2J / (1 + J)`);
15//! - **inverse log-weighted** similarity (Adamic–Adar): common neighbors,
16//! each weighted by `1 / ln(degree)`, so that sharing a rare neighbor
17//! counts more than sharing a hub.
18//!
19//! Such scores are the classic baseline for *link prediction*: two
20//! non-adjacent vertices with many common neighbors are likely to become
21//! connected.
22//!
23//! # Example
24//!
25//! ```
26//! use igraph::prelude::*;
27//!
28//! // The citation network of igraph's own example: 0 -> 1, 2 -> 1, 2 -> 0, 3 -> 0.
29//! let g = Graph::from_edges(&[(0, 1), (2, 1), (2, 0), (3, 0)], 4, true)?;
30//!
31//! // 0 and 1 are both cited by 2.
32//! let cocit = g.cocitation(..)?;
33//! assert_eq!(cocit[(0, 1)], 1.0);
34//! // 2 and 3 both cite 0; 0 and 2 both cite 1.
35//! let bib = g.bibcoupling(..)?;
36//! assert_eq!((bib[(2, 3)], bib[(0, 2)]), (1.0, 1.0));
37//!
38//! // Ignoring directions, 1 and 2 share the neighbor 0 out of {0, 1, 2}.
39//! let jac = g.similarity_jaccard(1..3, 1..3, NeighborMode::All, false)?;
40//! assert!((jac[(0, 1)] - 1.0 / 3.0).abs() < 1e-12);
41//! let dice = g.similarity_dice_pairs(&[(1, 2)], NeighborMode::All, false)?;
42//! assert!((dice[0] - 0.5).abs() < 1e-12);
43//! # Ok::<(), igraph::Error>(())
44//! ```
45//!
46//! # Provided functionality
47//!
48//! | C function | Method of [`Graph`] | Result |
49//! |------------|---------------------|--------|
50//! | `igraph_cocitation` | [`cocitation`](Graph::cocitation) | [`Matrix`], one row per selected vertex |
51//! | `igraph_bibcoupling` | [`bibcoupling`](Graph::bibcoupling) | [`Matrix`], one row per selected vertex |
52//! | `igraph_similarity_inverse_log_weighted` | [`similarity_inverse_log_weighted`](Graph::similarity_inverse_log_weighted) | [`Matrix`], one row per selected vertex |
53//! | `igraph_similarity_jaccard` | [`similarity_jaccard`](Graph::similarity_jaccard) | [`Matrix`] `from × to` |
54//! | `igraph_similarity_jaccard_pairs` | [`similarity_jaccard_pairs`](Graph::similarity_jaccard_pairs) | `Vec<f64>`, one value per pair |
55//! | `igraph_similarity_jaccard_es` | [`similarity_jaccard_es`](Graph::similarity_jaccard_es) | `Vec<f64>`, one value per edge |
56//! | `igraph_similarity_dice` | [`similarity_dice`](Graph::similarity_dice) | [`Matrix`] `from × to` |
57//! | `igraph_similarity_dice_pairs` | [`similarity_dice_pairs`](Graph::similarity_dice_pairs) | `Vec<f64>`, one value per pair |
58//! | `igraph_similarity_dice_es` | [`similarity_dice_es`](Graph::similarity_dice_es) | `Vec<f64>`, one value per edge |
59//!
60//! All the functions of the header are covered.
61//!
62//! # Differences from the C functions
63//!
64//! These wrappers are safer than the C functions they bind, and give the
65//! results the C documentation promises in cases where igraph 1.0.1 does not:
66//!
67//! - `igraph_similarity_jaccard` and `igraph_similarity_dice` fill the
68//! matrix as if `from` and `to` were the same vertex list. If they differ,
69//! the results are wrong, and when `from` is longer than `to` the C code
70//! writes past the end of the matrix. [`similarity_jaccard`](Graph::similarity_jaccard)
71//! and [`similarity_dice`](Graph::similarity_dice) call them only when the
72//! two lists are identical and have no repeated vertex. Otherwise they
73//! compute every `from × to` pair with the `*_pairs` function.
74//! - When a vertex appears several times in `vids`, `igraph_cocitation`,
75//! `igraph_bibcoupling` and `igraph_similarity_inverse_log_weighted` fill
76//! only its last row and leave the other rows at zero. The wrappers fill
77//! every row.
78//! - On a directed graph, the Jaccard and Dice functions clear igraph's
79//! property cache around the C call. Otherwise a cached "no multi-edges"
80//! flag would count each mutual pair `u -> v`, `v -> u` twice with
81//! [`NeighborMode::All`] (see [`crate::structural`]).
82//!
83//! # See also
84//!
85//! - Common neighbors of two vertices: [`Graph::neighbors`] (core).
86//! - Other similarity-like structures: [`Graph::get_adjacency`]
87//! ([`conversion`](crate::conversion)) and the transitivity functions in
88//! [`centrality`](crate::centrality).
89
90use crate::{
91 constants::NeighborMode,
92 error::Result,
93 ffi::*,
94 graph::{Graph, VertexId},
95 igraph_call,
96 matrix::Matrix,
97 selector::{EdgeSelector, VertexSelector},
98 structural::with_multi_cache_guard,
99 vector::{Vector, VectorInt},
100};
101use std::{borrow::Cow, collections::HashMap};
102
103type RowFn =
104 unsafe extern "C" fn(*const igraph_t, *mut igraph_matrix_t, igraph_vs_t) -> igraph_error_t;
105
106impl igraph_t {
107 /// Runs one of the "one row per vertex of `vids`, one column per vertex
108 /// of the graph" functions. If `vids` repeats a vertex, the function runs
109 /// on the distinct vertices and the rows are then copied into place,
110 /// because the C code fills only the last row of a repeated vertex.
111 fn per_vertex_rows<'a>(
112 &self,
113 vids: impl Into<VertexSelector<'a>>,
114 f: impl Fn(&Graph, &mut Matrix, igraph_vs_t) -> Result<()>,
115 ) -> Result<Matrix> {
116 let list = self.select_vertices(vids)?;
117 let mut distinct: Vec<VertexId> = Vec::with_capacity(list.len());
118 let mut row_of: HashMap<VertexId, i64> = HashMap::with_capacity(list.len());
119 for &v in &list {
120 row_of.entry(v).or_insert_with(|| {
121 distinct.push(v);
122 distinct.len() as i64 - 1
123 });
124 }
125 let vs = VertexSelector::List(Cow::Borrowed(&distinct)).to_raw()?;
126 let mut res = Matrix::new();
127 f(self, &mut res, vs.get())?;
128 if distinct.len() == list.len() {
129 return Ok(res);
130 }
131 let rows: Vec<i64> = list.iter().map(|v| row_of[v]).collect();
132 res.select_rows(&rows)
133 }
134
135 fn per_vertex_rows_c<'a>(
136 &self,
137 vids: impl Into<VertexSelector<'a>>,
138 cfn: RowFn,
139 ) -> Result<Matrix> {
140 self.per_vertex_rows(vids, |g, res, vs| igraph_call!(cfn(g, res, vs)))
141 }
142
143 /// Cocitation counts: `res[(i, j)]` is the number of vertices that cite
144 /// (have an edge pointing to) both the `i`-th vertex of `vids` and vertex
145 /// `j`.
146 ///
147 /// The result has one row per vertex of `vids`, in the order given, and
148 /// one column per vertex of the graph. In a simple graph the diagonal is
149 /// zero: a vertex is not cocited with itself. Multi-edges count with
150 /// multiplicity. For example, `k -> a` twice and `k -> b` once add 2 to
151 /// `(a, b)`. They also add 2 to the diagonal entry `(a, a)`, because the
152 /// two parallel edges form a pair. A self-loop of an undirected graph
153 /// lists its vertex twice among its own neighbors, so it has the same
154 /// effect as a double edge (a loop of a directed graph counts once).
155 /// In an undirected graph every edge
156 /// counts as a citation both ways, so the score is the number of common
157 /// neighbors. Cocitation is symmetric, and it equals bibliographic
158 /// coupling on the transposed graph. Off the diagonal, it is `AᵀA`, with
159 /// `A` the adjacency matrix.
160 ///
161 /// Binds [`igraph_cocitation`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_cocitation).
162 /// Time complexity: `O(|V| d²)`, with `d` the maximum degree.
163 ///
164 /// # Errors
165 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) (or
166 /// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) for a range)
167 /// if `vids` names a missing vertex.
168 ///
169 /// # Examples
170 /// ```
171 /// use igraph::prelude::*;
172 /// // Papers 3 and 4 both cite papers 0 and 1; paper 4 also cites 2.
173 /// let g = Graph::from_edges(&[(3, 0), (3, 1), (4, 0), (4, 1), (4, 2)], 5, true)?;
174 /// let m = g.cocitation(&[0, 2])?;
175 /// assert_eq!(m.row(0), vec![0.0, 2.0, 1.0, 0.0, 0.0]);
176 /// assert_eq!(m.row(1), vec![1.0, 1.0, 0.0, 0.0, 0.0]);
177 /// # Ok::<(), igraph::Error>(())
178 /// ```
179 pub fn cocitation<'a>(&self, vids: impl Into<VertexSelector<'a>>) -> Result<Matrix> {
180 self.per_vertex_rows_c(vids, igraph_cocitation)
181 }
182
183 /// Bibliographic coupling: `res[(i, j)]` is the number of vertices cited
184 /// by both the `i`-th vertex of `vids` and vertex `j`.
185 ///
186 /// The result has one row per vertex of `vids`, in the order given, and
187 /// one column per vertex of the graph. The diagonal is zero in a simple
188 /// graph; multi-edges (and undirected self-loops) count with multiplicity
189 /// as in [`cocitation`](Self::cocitation). In an undirected graph this is the
190 /// same as the cocitation (the number of common neighbors). Off the
191 /// diagonal, the matrix is `AAᵀ`.
192 ///
193 /// Binds [`igraph_bibcoupling`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_bibcoupling).
194 /// Time complexity: `O(|V| d²)`, with `d` the maximum degree.
195 ///
196 /// # Errors
197 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) (or
198 /// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) for a range)
199 /// if `vids` names a missing vertex.
200 ///
201 /// # Examples
202 /// ```
203 /// use igraph::prelude::*;
204 /// // Papers 3 and 4 share two references (0 and 1).
205 /// let g = Graph::from_edges(&[(3, 0), (3, 1), (4, 0), (4, 1), (4, 2)], 5, true)?;
206 /// let m = g.bibcoupling(4)?;
207 /// assert_eq!(m.row(0), vec![0.0, 0.0, 0.0, 2.0, 0.0]);
208 /// # Ok::<(), igraph::Error>(())
209 /// ```
210 pub fn bibcoupling<'a>(&self, vids: impl Into<VertexSelector<'a>>) -> Result<Matrix> {
211 self.per_vertex_rows_c(vids, igraph_bibcoupling)
212 }
213
214 /// Inverse log-weighted similarity (Adamic and Adar, 2003): the common
215 /// neighbors of two vertices, each weighted by `1 / ln(degree)`.
216 ///
217 /// The idea is that sharing a low-degree neighbor says more about two
218 /// vertices than sharing a hub, which many vertices share by chance.
219 /// `mode` chooses which neighbors are compared in a directed graph:
220 ///
221 /// - [`NeighborMode::Out`]: out-neighbors (the vertices both cite); each
222 /// common neighbor is weighted by its **in**-degree;
223 /// - [`NeighborMode::In`]: in-neighbors; weighted by the **out**-degree;
224 /// - [`NeighborMode::All`]: the graph is treated as undirected.
225 ///
226 /// The result has one row per vertex of `vids`, in the order given, and
227 /// one column per vertex of the graph. In a simple graph the
228 /// self-similarities (the diagonal) are zero, and isolated vertices have
229 /// zero similarity to all others. Multi-edges count with multiplicity,
230 /// and an undirected loop makes a vertex its own neighbor twice (which
231 /// also makes the diagonal nonzero). This can raise *or* lower a
232 /// similarity, since it also raises the degrees used as weights, so consider
233 /// [`simplify`](Graph::simplify)ing the graph first.
234 ///
235 /// Binds [`igraph_similarity_inverse_log_weighted`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_inverse_log_weighted).
236 /// Time complexity: `O(|V| d²)`, with `d` the maximum degree.
237 ///
238 /// # Errors
239 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) (or
240 /// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) for a range)
241 /// if `vids` names a missing vertex.
242 ///
243 /// # Examples
244 /// ```
245 /// use igraph::prelude::*;
246 /// // 0 and 1 share the neighbor 2, which has degree 3.
247 /// let g = Graph::from_edges(&[(0, 2), (1, 2), (2, 3)], 4, false)?;
248 /// let m = g.similarity_inverse_log_weighted(0, NeighborMode::All)?;
249 /// assert!((m[(0, 1)] - 1.0 / 3f64.ln()).abs() < 1e-12);
250 /// # Ok::<(), igraph::Error>(())
251 /// ```
252 pub fn similarity_inverse_log_weighted<'a>(
253 &self,
254 vids: impl Into<VertexSelector<'a>>,
255 mode: NeighborMode,
256 ) -> Result<Matrix> {
257 self.per_vertex_rows(vids, |g, res, vs| {
258 igraph_call!(igraph_similarity_inverse_log_weighted(
259 g,
260 res,
261 vs,
262 mode.into()
263 ))
264 })
265 }
266
267 /// Jaccard similarity of every pair in `from × to`: the number of common
268 /// neighbors divided by the number of vertices adjacent to at least one of
269 /// the two.
270 ///
271 /// `res[(i, j)]` is the similarity of the `i`-th vertex of `from` and the
272 /// `j`-th vertex of `to`. `mode` selects out-, in- or all neighbors in
273 /// directed graphs (ignored for undirected ones). Neighbor *sets* are
274 /// compared, so loops and multi-edges are ignored. With `loops = true`,
275 /// each vertex is added to its own neighbor set, which is the usual choice
276 /// for link prediction ("closed neighborhoods"). A vertex has similarity
277 /// 1 with itself. Two vertices with no neighbors at all have similarity 0.
278 ///
279 /// Binds [`igraph_similarity_jaccard`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_jaccard).
280 /// When `from` and `to` are the same list with no repeated vertex, this
281 /// calls that function. Otherwise it computes the pairs with
282 /// `igraph_similarity_jaccard_pairs`, because the C function is wrong
283 /// (and can write out of bounds) in that case (see the
284 /// [module docs](self#differences-from-the-c-functions)).
285 /// Time complexity: `O(|from| |to| d)`, with `d` the maximum degree.
286 ///
287 /// # Errors
288 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) (or
289 /// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) for a range)
290 /// if a selector names a missing vertex.
291 ///
292 /// # Examples
293 /// ```
294 /// use igraph::prelude::*;
295 /// // A 4-cycle 0-1-2-3: opposite vertices have the same neighbors.
296 /// let g = Graph::ring(4, false, false, true)?;
297 /// let m = g.similarity_jaccard(.., .., NeighborMode::All, false)?;
298 /// assert_eq!(m[(0, 2)], 1.0);
299 /// assert_eq!(m[(0, 1)], 0.0);
300 /// // Rectangular: the rows are {0}, the columns {1, 2}.
301 /// let r = g.similarity_jaccard(0, &[1, 2], NeighborMode::All, true)?;
302 /// assert_eq!(r.shape(), (1, 2));
303 /// assert_eq!(r[(0, 1)], 0.5); // {0,1,3} vs {1,2,3}
304 /// # Ok::<(), igraph::Error>(())
305 /// ```
306 pub fn similarity_jaccard<'a, 'b>(
307 &self,
308 from: impl Into<VertexSelector<'a>>,
309 to: impl Into<VertexSelector<'b>>,
310 mode: NeighborMode,
311 loops: bool,
312 ) -> Result<Matrix> {
313 self.similarity_matrix(from.into(), to.into(), mode, loops, false)
314 }
315
316 /// Jaccard similarity of each vertex pair in `pairs`, in the same order.
317 ///
318 /// See [`similarity_jaccard`](Self::similarity_jaccard) for the meaning
319 /// of `mode` and `loops`. A pair `(v, v)` has similarity 1.
320 ///
321 /// Binds [`igraph_similarity_jaccard_pairs`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_jaccard_pairs).
322 /// Time complexity: `O(n d)` for `n` pairs, with `d` the maximum degree.
323 ///
324 /// # Errors
325 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) if a
326 /// pair names a missing vertex.
327 ///
328 /// # Examples
329 /// ```
330 /// use igraph::prelude::*;
331 /// // A star with center 0: all leaves have the same neighbor set {0}.
332 /// let g = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], 4, false)?;
333 /// let s = g.similarity_jaccard_pairs(&[(1, 2), (0, 1), (3, 3)], NeighborMode::All, false)?;
334 /// assert_eq!(s, vec![1.0, 0.0, 1.0]);
335 /// # Ok::<(), igraph::Error>(())
336 /// ```
337 pub fn similarity_jaccard_pairs(
338 &self,
339 pairs: &[(VertexId, VertexId)],
340 mode: NeighborMode,
341 loops: bool,
342 ) -> Result<Vec<f64>> {
343 let flat: Vec<i64> = pairs.iter().flat_map(|&(a, b)| [a, b]).collect();
344 self.jaccard_pairs_flat(&flat, mode, loops, false)
345 }
346
347 /// Jaccard similarity of the two endpoints of each edge of `es`, in the
348 /// order of the selector.
349 ///
350 /// See [`similarity_jaccard`](Self::similarity_jaccard) for the meaning
351 /// of `mode` and `loops`. A low value marks an edge between vertices with
352 /// different neighborhoods, such as a "bridge" between communities.
353 ///
354 /// Binds [`igraph_similarity_jaccard_es`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_jaccard_es).
355 /// Time complexity: `O(n d)` for `n` edges, with `d` the maximum degree.
356 ///
357 /// # Errors
358 /// [`ErrorKind::InvalidEdgeId`](crate::ErrorKind::InvalidEdgeId) (or another
359 /// kind, depending on the selector) if `es` names missing edges.
360 ///
361 /// # Examples
362 /// ```
363 /// use igraph::prelude::*;
364 /// // Two triangles joined by the edge 2-3.
365 /// let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)], 6, false)?;
366 /// let s = g.similarity_jaccard_es(.., NeighborMode::All, true)?;
367 /// // Inside a triangle: {0,1,2} vs {0,1,2,3} = 3/4; across: {0,1,2,3} vs {2,3,4,5} = 2/6.
368 /// assert_eq!(s[1], 0.75);
369 /// assert!((s[3] - 1.0 / 3.0).abs() < 1e-12);
370 /// # Ok::<(), igraph::Error>(())
371 /// ```
372 pub fn similarity_jaccard_es<'a>(
373 &self,
374 es: impl Into<EdgeSelector<'a>>,
375 mode: NeighborMode,
376 loops: bool,
377 ) -> Result<Vec<f64>> {
378 self.similarity_es(es.into(), mode, loops, false)
379 }
380
381 /// Dice similarity of every pair in `from × to`: twice the number of
382 /// common neighbors divided by the sum of the two neighbor-set sizes.
383 ///
384 /// Dice and Jaccard similarities are related by `D = 2J / (1 + J)`, so
385 /// they rank pairs the same way. Everything else (shape, `mode`, `loops`,
386 /// self-similarity 1, and the fallback to the pairs function when `from`
387 /// and `to` differ) is as for [`similarity_jaccard`](Self::similarity_jaccard).
388 ///
389 /// Binds [`igraph_similarity_dice`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_dice).
390 /// Time complexity: `O(|from| |to| d)`, with `d` the maximum degree.
391 ///
392 /// # Errors
393 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) (or
394 /// [`ErrorKind::InvalidValue`](crate::ErrorKind::InvalidValue) for a range)
395 /// if a selector names a missing vertex.
396 ///
397 /// # Examples
398 /// ```
399 /// use igraph::prelude::*;
400 /// let g = Graph::ring(4, false, false, true)?;
401 /// let m = g.similarity_dice(.., .., NeighborMode::All, true)?;
402 /// // {0,1,3} vs {0,1,2}: 2 * 2 / (3 + 3).
403 /// assert!((m[(0, 1)] - 2.0 / 3.0).abs() < 1e-12);
404 /// # Ok::<(), igraph::Error>(())
405 /// ```
406 pub fn similarity_dice<'a, 'b>(
407 &self,
408 from: impl Into<VertexSelector<'a>>,
409 to: impl Into<VertexSelector<'b>>,
410 mode: NeighborMode,
411 loops: bool,
412 ) -> Result<Matrix> {
413 self.similarity_matrix(from.into(), to.into(), mode, loops, true)
414 }
415
416 /// Dice similarity of each vertex pair in `pairs`, in the same order.
417 ///
418 /// See [`similarity_dice`](Self::similarity_dice).
419 ///
420 /// Binds [`igraph_similarity_dice_pairs`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_dice_pairs).
421 /// Time complexity: `O(n d)` for `n` pairs, with `d` the maximum degree.
422 ///
423 /// # Errors
424 /// [`ErrorKind::InvalidVertexId`](crate::ErrorKind::InvalidVertexId) if a
425 /// pair names a missing vertex.
426 ///
427 /// # Examples
428 /// ```
429 /// use igraph::prelude::*;
430 /// let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 3)], 4, false)?;
431 /// // N(0) = {1, 2}, N(3) = {1}: 2 * 1 / (2 + 1).
432 /// let s = g.similarity_dice_pairs(&[(0, 3)], NeighborMode::All, false)?;
433 /// assert!((s[0] - 2.0 / 3.0).abs() < 1e-12);
434 /// # Ok::<(), igraph::Error>(())
435 /// ```
436 pub fn similarity_dice_pairs(
437 &self,
438 pairs: &[(VertexId, VertexId)],
439 mode: NeighborMode,
440 loops: bool,
441 ) -> Result<Vec<f64>> {
442 let flat: Vec<i64> = pairs.iter().flat_map(|&(a, b)| [a, b]).collect();
443 self.jaccard_pairs_flat(&flat, mode, loops, true)
444 }
445
446 /// Dice similarity of the two endpoints of each edge of `es`, in the
447 /// order of the selector.
448 ///
449 /// See [`similarity_dice`](Self::similarity_dice) and
450 /// [`similarity_jaccard_es`](Self::similarity_jaccard_es).
451 ///
452 /// Binds [`igraph_similarity_dice_es`](https://igraph.org/c/html/latest/igraph-Structural.html#igraph_similarity_dice_es).
453 /// Time complexity: `O(n d)` for `n` edges, with `d` the maximum degree.
454 ///
455 /// # Errors
456 /// [`ErrorKind::InvalidEdgeId`](crate::ErrorKind::InvalidEdgeId) (or another
457 /// kind, depending on the selector) if `es` names missing edges.
458 ///
459 /// # Examples
460 /// ```
461 /// use igraph::prelude::*;
462 /// let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], 3, false)?;
463 /// // In a triangle, closed neighborhoods are all {0, 1, 2}.
464 /// assert_eq!(g.similarity_dice_es(.., NeighborMode::All, true)?, vec![1.0; 3]);
465 /// # Ok::<(), igraph::Error>(())
466 /// ```
467 pub fn similarity_dice_es<'a>(
468 &self,
469 es: impl Into<EdgeSelector<'a>>,
470 mode: NeighborMode,
471 loops: bool,
472 ) -> Result<Vec<f64>> {
473 self.similarity_es(es.into(), mode, loops, true)
474 }
475
476 fn similarity_matrix(
477 &self,
478 from: VertexSelector<'_>,
479 to: VertexSelector<'_>,
480 mode: NeighborMode,
481 loops: bool,
482 dice: bool,
483 ) -> Result<Matrix> {
484 let from = self.select_vertices(from)?;
485 let to = self.select_vertices(to)?;
486 let mut sorted = from.clone();
487 sorted.sort_unstable();
488 let distinct = sorted.windows(2).all(|w| w[0] != w[1]);
489 if from == to && distinct {
490 // The only case the C matrix functions handle correctly.
491 let vs = VertexSelector::List(Cow::Borrowed(&from)).to_raw()?;
492 let cfn = if dice {
493 igraph_similarity_dice
494 } else {
495 igraph_similarity_jaccard
496 };
497 let mut res = Matrix::new();
498 with_multi_cache_guard(self, || {
499 igraph_call!(cfn(self, &mut res, vs.get(), vs.get(), mode.into(), loops))
500 })?;
501 return Ok(res);
502 }
503 let mut flat = Vec::with_capacity(2 * from.len() * to.len());
504 for &u in &from {
505 for &v in &to {
506 flat.extend([u, v]);
507 }
508 }
509 let values = self.jaccard_pairs_flat(&flat, mode, loops, dice)?;
510 if values.is_empty() {
511 let mut m = Matrix::new();
512 m.resize(from.len(), to.len());
513 return Ok(m);
514 }
515 Matrix::from_row_major(from.len(), to.len(), &values)
516 }
517
518 fn jaccard_pairs_flat(
519 &self,
520 flat: &[i64],
521 mode: NeighborMode,
522 loops: bool,
523 dice: bool,
524 ) -> Result<Vec<f64>> {
525 debug_assert!(flat.len().is_multiple_of(2));
526 let pairs = VectorInt::view(flat);
527 let mut res = Vector::new();
528 let cfn = if dice {
529 igraph_similarity_dice_pairs
530 } else {
531 igraph_similarity_jaccard_pairs
532 };
533 with_multi_cache_guard(self, || {
534 igraph_call!(cfn(self, &mut res, pairs.as_ptr(), mode.into(), loops))
535 })?;
536 Ok(res.into())
537 }
538
539 fn similarity_es(
540 &self,
541 es: EdgeSelector<'_>,
542 mode: NeighborMode,
543 loops: bool,
544 dice: bool,
545 ) -> Result<Vec<f64>> {
546 let es = es.to_raw()?;
547 let mut res = Vector::new();
548 let cfn = if dice {
549 igraph_similarity_dice_es
550 } else {
551 igraph_similarity_jaccard_es
552 };
553 with_multi_cache_guard(self, || {
554 igraph_call!(cfn(self, &mut res, es.get(), mode.into(), loops))
555 })?;
556 Ok(res.into())
557 }
558}