fera_graph/algs/
degrees.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! Test if a graph is regular, find minimum and maximum degrees, etc.
6
7use params::IntoOwned;
8use prelude::*;
9
10pub trait Degrees: Adjacency {
11    fn degree_spanning_subgraph<I>(&self, edges: I) -> DefaultVertexPropMut<Self, u32>
12    where
13        Self: WithEdge + WithVertexProp<u32>,
14        I: IntoIterator,
15        I::Item: IntoOwned<Edge<Self>>,
16    {
17        let mut degree = self.default_vertex_prop(0);
18        self.degree_add(&mut degree, edges);
19        degree
20    }
21
22    fn degree_add<P, I>(&self, degree: &mut P, edges: I)
23    where
24        Self: WithEdge,
25        P: VertexPropMut<Self, u32>,
26        I: IntoIterator,
27        I::Item: IntoOwned<Edge<Self>>,
28    {
29        for e in edges {
30            let (u, v) = self.end_vertices(e.into_owned());
31            degree[u] += 1;
32            degree[v] += 1;
33        }
34    }
35
36    fn is_k_regular(&self, k: usize) -> bool
37    where
38        Self: WithEdge<Kind = Undirected> + VertexList,
39    {
40        self.vertices().all(|v| self.out_degree(v) == k)
41    }
42
43    fn is_regular(&self) -> bool
44    where
45        Self: WithEdge<Kind = Undirected> + VertexList,
46    {
47        let mut vertices = self.vertices();
48
49        if let Some(v) = vertices.next() {
50            let deg = self.out_degree(v);
51            vertices.all(|v| self.out_degree(v) == deg)
52        } else {
53            true
54        }
55    }
56
57    fn maximum_out_degree(&self) -> Option<usize>
58    where
59        Self: VertexList,
60    {
61        self.vertices().map(|v| self.out_degree(v)).max()
62    }
63
64    fn minimum_out_degree(&self) -> Option<usize>
65    where
66        Self: VertexList,
67    {
68        self.vertices().map(|v| self.out_degree(v)).min()
69    }
70
71    fn is_isolated(&self, v: Vertex<Self>) -> bool
72    where
73        Self: WithEdge<Kind = Undirected>,
74    {
75        self.out_degree(v) == 0
76    }
77
78    fn is_pendant(&self, v: Vertex<Self>) -> bool
79    where
80        Self: WithEdge<Kind = Undirected>,
81    {
82        self.out_degree(v) == 1
83    }
84}
85
86impl<G: Adjacency> Degrees for G {}
fera_graph/algs/degrees.rs

fera_graph/algs/
degrees.rs
