graphrs/graph/degree.rs
1use super::Graph;
2use crate::{Error, ErrorKind};
3use std::collections::HashMap;
4use std::fmt::Display;
5use std::hash::Hash;
6
7impl<T, A> Graph<T, A>
8where
9 T: Eq + Clone + PartialOrd + Ord + Hash + Send + Sync + Display,
10 A: Clone,
11{
12 /**
13 Compute the degree for all nodes in the graph.
14
15 # Examples
16
17 ```
18 use graphrs::{Edge, Graph, GraphSpecs};
19 let edges = vec![
20 Edge::new("n1", "n2"),
21 Edge::new("n1", "n3"),
22 Edge::new("n1", "n4"),
23 Edge::new("n4", "n5"),
24 ];
25 let graph: Graph<&str, ()> =
26 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
27 .unwrap();
28 let result = graph.get_degree_for_all_nodes();
29 assert_eq!(result.get("n1").unwrap(), &3);
30 ```
31 */
32 pub fn get_degree_for_all_nodes(&self) -> HashMap<T, usize> {
33 self.get_all_nodes()
34 .iter()
35 .map(|n| {
36 (
37 n.name.clone(),
38 self.get_node_degree(n.name.clone()).unwrap(),
39 )
40 })
41 .collect()
42 }
43
44 pub(crate) fn get_degree_for_all_node_indexes(&self) -> Vec<usize> {
45 self.successors_vec.iter().map(|s| s.len()).collect()
46 }
47
48 /**
49 Compute the in-degree for all nodes in the graph.
50
51 # Examples
52
53 ```
54 use graphrs::{Edge, Graph, GraphSpecs};
55 let edges = vec![
56 Edge::new("n1", "n2"),
57 Edge::new("n1", "n3"),
58 Edge::new("n1", "n5"),
59 Edge::new("n4", "n5"),
60 ];
61 let graph: Graph<&str, ()> =
62 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
63 .unwrap();
64 let result = graph.get_in_degree_for_all_nodes().unwrap();
65 assert_eq!(result.get("n5").unwrap(), &2);
66 ```
67 */
68 pub fn get_in_degree_for_all_nodes(&self) -> Result<HashMap<T, usize>, Error> {
69 if !self.specs.directed {
70 return Err(Error {
71 kind: ErrorKind::WrongMethod,
72 message: "Use the `get_degree_for_all_nodes` method when `directed` is `false`"
73 .to_string(),
74 });
75 }
76 Ok(self
77 .get_all_nodes()
78 .iter()
79 .map(|n| {
80 (
81 n.name.clone(),
82 self.get_node_in_degree(n.name.clone()).unwrap(),
83 )
84 })
85 .collect())
86 }
87
88 /**
89 Compute the out-degree for all nodes in the graph.
90
91 # Examples
92
93 ```
94 use graphrs::{Edge, Graph, GraphSpecs};
95 let edges = vec![
96 Edge::new("n1", "n2"),
97 Edge::new("n1", "n3"),
98 Edge::new("n1", "n5"),
99 Edge::new("n4", "n5"),
100 ];
101 let graph: Graph<&str, ()> =
102 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
103 .unwrap();
104 let result = graph.get_out_degree_for_all_nodes().unwrap();
105 assert_eq!(result.get("n1").unwrap(), &3);
106 ```
107 */
108 pub fn get_out_degree_for_all_nodes(&self) -> Result<HashMap<T, usize>, Error> {
109 if !self.specs.directed {
110 return Err(Error {
111 kind: ErrorKind::WrongMethod,
112 message: "Use the `get_degree_for_all_nodes` method when `directed` is `false`"
113 .to_string(),
114 });
115 }
116 Ok(self
117 .get_all_nodes()
118 .iter()
119 .map(|n| {
120 (
121 n.name.clone(),
122 self.get_node_out_degree(n.name.clone()).unwrap(),
123 )
124 })
125 .collect())
126 }
127
128 /**
129 Computes the degree of a given node.
130 The node degree is the number of edges adjacent to the node.
131
132 # Arguments
133
134 * `node_name`: the name of the node to get the degree of
135
136 # Examples
137
138 ```
139 use graphrs::{generators};
140 let graph = generators::social::karate_club_graph();
141 assert_eq!(graph.get_node_degree(25).unwrap(), 3);
142 ```
143 */
144 pub fn get_node_degree(&self, node_name: T) -> Option<usize> {
145 match self.get_edges_for_node(node_name.clone()) {
146 Err(_) => None,
147 Ok(edges) => {
148 let total_count = edges.len();
149 // self-loops are double-counted: https://en.wikipedia.org/wiki/Loop_(graph_theory)
150 let self_loops_count = edges
151 .iter()
152 .filter(|e| e.u == node_name && e.v == node_name)
153 .count();
154 Some(total_count + self_loops_count)
155 }
156 }
157 }
158
159 pub(crate) fn get_node_degree_by_index(&self, node_index: usize) -> usize {
160 let adjacent = self.get_adjacent_nodes_by_index(node_index);
161 adjacent
162 .iter()
163 .map(|adj| {
164 if adj.node_index == node_index {
165 return 2;
166 }
167 1
168 })
169 .sum()
170 }
171
172 /**
173 Computes the in-degree of a given node.
174 The node in-degree is the number of edges (u, v) where v is the node.
175
176 # Arguments
177
178 * `node_name`: the name of the node to get the in-degree of
179
180 # Examples
181
182 ```
183 use graphrs::{Edge, Graph, GraphSpecs};
184 let edges = vec![
185 Edge::new("n2", "n1"),
186 Edge::new("n3", "n1"),
187 Edge::new("n4", "n1"),
188 Edge::new("n1", "n4"),
189 ];
190 let graph: Graph<&str, ()> =
191 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
192 .unwrap();
193 assert_eq!(graph.get_node_in_degree("n1").unwrap(), 3);
194 ```
195 */
196 pub fn get_node_in_degree(&self, node_name: T) -> Option<usize> {
197 match self.get_in_edges_for_node(node_name) {
198 Err(_) => None,
199 Ok(edges) => Some(edges.len()),
200 }
201 }
202
203 /**
204 Computes the out-degree of a given node.
205 The node out-degree is the number of edges (u, v) where u is the node.
206
207 # Arguments
208
209 * `node_name`: the name of the node to get the out-degree of
210
211 # Examples
212
213 ```
214 use graphrs::{Edge, Graph, GraphSpecs};
215 let edges = vec![
216 Edge::new("n1", "n2"),
217 Edge::new("n3", "n1"),
218 Edge::new("n4", "n1"),
219 Edge::new("n1", "n4"),
220 ];
221 let graph: Graph<&str, ()> =
222 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
223 .unwrap();
224 assert_eq!(graph.get_node_out_degree("n1").unwrap(), 2);
225 ```
226 */
227 pub fn get_node_out_degree(&self, node_name: T) -> Option<usize> {
228 match self.get_out_edges_for_node(node_name) {
229 Err(_) => None,
230 Ok(edges) => Some(edges.len()),
231 }
232 }
233
234 /**
235 Computes the weighted degree of a given node.
236 The weighted degree is sum of the weights of edges adjacent to the node.
237
238 # Arguments
239
240 * `node_name`: the name of the node to get the weighted degree of
241
242 # Examples
243
244 ```
245 use graphrs::{Edge, Graph, GraphSpecs};
246 let edges = vec![
247 Edge::with_weight("n2", "n1", 1.0),
248 Edge::with_weight("n3", "n1", 2.0),
249 Edge::with_weight("n4", "n1", 3.0),
250 Edge::with_weight("n1", "n4", 4.0),
251 ];
252 let graph: Graph<&str, ()> =
253 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
254 .unwrap();
255 assert_eq!(graph.get_node_weighted_degree("n1").unwrap(), 10.0);
256 ```
257 */
258 pub fn get_node_weighted_degree(&self, node_name: T) -> Option<f64> {
259 match self.get_edges_for_node(node_name.clone()) {
260 Err(_) => None,
261 Ok(edges) => {
262 let total_weight: f64 = edges.iter().map(|e| e.weight).sum();
263 // self-loops are double-counted: https://en.wikipedia.org/wiki/Loop_(graph_theory)
264 let self_loops_weight: f64 = edges
265 .iter()
266 .filter(|e| e.u == node_name && e.v == node_name)
267 .map(|e| e.weight)
268 .sum();
269 Some(total_weight + self_loops_weight)
270 }
271 }
272 }
273
274 pub(crate) fn get_node_weighted_degree_by_index(&self, node_index: usize) -> f64 {
275 let adjacent = self.get_adjacent_nodes_by_index(node_index);
276 adjacent
277 .iter()
278 .map(|adj| {
279 if adj.node_index == node_index {
280 return adj.weight * 2.0;
281 }
282 adj.weight
283 })
284 .sum()
285 }
286
287 /**
288 Computes the weighted in-degree of a given node.
289 The weighted in-degree is sum of the weights of edges into to the node.
290
291 # Arguments
292
293 * `node_name`: the name of the node to get the weighted in-degree of
294
295 # Examples
296
297 ```
298 use graphrs::{Edge, Graph, GraphSpecs};
299 let edges = vec![
300 Edge::with_weight("n2", "n1", 1.0),
301 Edge::with_weight("n3", "n1", 2.0),
302 Edge::with_weight("n4", "n1", 3.0),
303 Edge::with_weight("n1", "n4", 4.0),
304 ];
305 let graph: Graph<&str, ()> =
306 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
307 .unwrap();
308 assert_eq!(graph.get_node_weighted_in_degree("n1").unwrap(), 6.0);
309 ```
310 */
311 pub fn get_node_weighted_in_degree(&self, node_name: T) -> Option<f64> {
312 match self.get_in_edges_for_node(node_name) {
313 Err(_) => None,
314 Ok(edges) => Some(edges.iter().map(|e| e.weight).sum()),
315 }
316 }
317
318 /**
319 Computes the weighted out-degree of a given node.
320 The weighted out-degree is sum of the weights of edges coming from the node.
321
322 # Arguments
323
324 * `node_name`: the name of the node to get the weighted out-degree of
325
326 # Examples
327
328 ```
329 use graphrs::{Edge, Graph, GraphSpecs};
330 let edges = vec![
331 Edge::with_weight("n1", "n2", 1.0),
332 Edge::with_weight("n3", "n1", 2.0),
333 Edge::with_weight("n4", "n1", 3.0),
334 Edge::with_weight("n1", "n4", 4.0),
335 ];
336 let graph: Graph<&str, ()> =
337 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
338 .unwrap();
339 assert_eq!(graph.get_node_weighted_out_degree("n1").unwrap(), 5.0);
340 ```
341 */
342 pub fn get_node_weighted_out_degree(&self, node_name: T) -> Option<f64> {
343 match self.get_out_edges_for_node(node_name) {
344 Err(_) => None,
345 Ok(edges) => Some(edges.iter().map(|e| e.weight).sum()),
346 }
347 }
348
349 /**
350 Compute the weighted degree for all nodes in the graph.
351
352 # Examples
353
354 ```
355 use graphrs::{Edge, Graph, GraphSpecs};
356 let edges = vec![
357 Edge::with_weight("n1", "n2", 1.0),
358 Edge::with_weight("n1", "n3", 2.0),
359 Edge::with_weight("n1", "n4", 3.0),
360 Edge::with_weight("n4", "n5", 4.0),
361 ];
362 let graph: Graph<&str, ()> =
363 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
364 .unwrap();
365 let result = graph.get_weighted_degree_for_all_nodes();
366 assert_eq!(result.get("n1").unwrap(), &6.0);
367 ```
368 */
369 pub fn get_weighted_degree_for_all_nodes(&self) -> HashMap<T, f64> {
370 self.get_all_nodes()
371 .iter()
372 .map(|n| {
373 (
374 n.name.clone(),
375 self.get_node_weighted_degree(n.name.clone()).unwrap(),
376 )
377 })
378 .collect()
379 }
380
381 pub(crate) fn get_weighted_degree_for_all_node_indexes(&self) -> Vec<f64> {
382 self.successors_vec
383 .iter()
384 .enumerate()
385 .map(|(i, s)| {
386 s.iter()
387 .map(|adj| {
388 if adj.node_index == i {
389 return adj.weight * 2.0;
390 }
391 adj.weight
392 })
393 .sum()
394 })
395 .collect()
396 }
397
398 /**
399 Compute the weighted in-degree for all nodes in the graph.
400
401 # Examples
402
403 ```
404 use graphrs::{Edge, Graph, GraphSpecs};
405 let edges = vec![
406 Edge::with_weight("n1", "n2", 1.0),
407 Edge::with_weight("n1", "n3", 2.0),
408 Edge::with_weight("n1", "n5", 3.0),
409 Edge::with_weight("n4", "n5", 4.0),
410 ];
411 let graph: Graph<&str, ()> =
412 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
413 .unwrap();
414 let result = graph.get_weighted_in_degree_for_all_nodes().unwrap();
415 assert_eq!(result.get("n5").unwrap(), &7.0);
416 ```
417 */
418 pub fn get_weighted_in_degree_for_all_nodes(&self) -> Result<HashMap<T, f64>, Error> {
419 if !self.specs.directed {
420 return Err(Error {
421 kind: ErrorKind::WrongMethod,
422 message:
423 "Use the `get_weighted_degree_for_all_nodes` method when `directed` is `false`"
424 .to_string(),
425 });
426 }
427 Ok(self
428 .get_all_nodes()
429 .iter()
430 .map(|n| {
431 (
432 n.name.clone(),
433 self.get_node_weighted_in_degree(n.name.clone()).unwrap(),
434 )
435 })
436 .collect())
437 }
438
439 /**
440 Compute the weighted out-degree for all nodes in the graph.
441
442 # Examples
443
444 ```
445 use graphrs::{Edge, Graph, GraphSpecs};
446 let edges = vec![
447 Edge::with_weight("n1", "n2", 1.0),
448 Edge::with_weight("n1", "n3", 2.0),
449 Edge::with_weight("n1", "n5", 3.0),
450 Edge::with_weight("n4", "n5", 4.0),
451 ];
452 let graph: Graph<&str, ()> =
453 Graph::new_from_nodes_and_edges(vec![], edges, GraphSpecs::directed_create_missing())
454 .unwrap();
455 let result = graph.get_weighted_out_degree_for_all_nodes().unwrap();
456 assert_eq!(result.get("n1").unwrap(), &6.0);
457 ```
458 */
459 pub fn get_weighted_out_degree_for_all_nodes(&self) -> Result<HashMap<T, f64>, Error> {
460 if !self.specs.directed {
461 return Err(Error {
462 kind: ErrorKind::WrongMethod,
463 message:
464 "Use the `get_weighted_degree_for_all_nodes` method when `directed` is `false`"
465 .to_string(),
466 });
467 }
468 Ok(self
469 .get_all_nodes()
470 .iter()
471 .map(|n| {
472 (
473 n.name.clone(),
474 self.get_node_weighted_out_degree(n.name.clone()).unwrap(),
475 )
476 })
477 .collect())
478 }
479}
480
481#[cfg(test)]
482mod tests {
483
484 use crate::{Edge, Graph, GraphSpecs};
485
486 #[test]
487 fn test_get_node_degree_by_index() {
488 let edges = vec![Edge::new(0, 1), Edge::new(1, 2), Edge::new(2, 2)];
489 let specs = GraphSpecs {
490 self_loops: true,
491 ..GraphSpecs::directed_create_missing()
492 };
493 let graph: Graph<usize, ()> =
494 Graph::new_from_nodes_and_edges(vec![], edges, specs).unwrap();
495 assert_eq!(graph.get_node_degree_by_index(0), 1);
496 assert_eq!(graph.get_node_degree_by_index(1), 2);
497 assert_eq!(graph.get_node_degree_by_index(2), 3);
498 }
499
500 #[test]
501 fn test_get_weighted_node_degree_by_index() {
502 let edges = vec![
503 Edge::with_weight(0, 1, 0.5),
504 Edge::with_weight(1, 2, 6.3),
505 Edge::with_weight(2, 2, 10.0),
506 ];
507 let specs = GraphSpecs {
508 self_loops: true,
509 ..GraphSpecs::directed_create_missing()
510 };
511 let graph: Graph<usize, ()> =
512 Graph::new_from_nodes_and_edges(vec![], edges, specs).unwrap();
513 assert_eq!(graph.get_node_weighted_degree_by_index(0), 0.5);
514 assert_eq!(graph.get_node_weighted_degree_by_index(1), 6.8);
515 assert_eq!(graph.get_node_weighted_degree_by_index(2), 26.3);
516 }
517}