rustworkx_core/connectivity/
isolates.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use petgraph::visit::{IntoNeighborsDirected, IntoNodeIdentifiers, NodeIndexable};
14use petgraph::Direction::{Incoming, Outgoing};
15
16/// Return the isolates in a graph object
17///
18/// An isolate is a node without any neighbors meaning it has a degree of 0. For
19/// directed graphs this means the in-degree and out-degree are both 0.
20///
21/// Arguments:
22///
23/// * `graph` - The graph in which to find the isolates.
24///
25/// # Example
26/// ```rust
27/// use petgraph::prelude::*;
28/// use rustworkx_core::connectivity::isolates;
29///
30/// let edge_list = vec![
31///     (0, 1),
32///     (3, 0),
33///     (0, 5),
34///     (8, 0),
35///     (1, 2),
36///     (1, 6),
37///     (2, 3),
38///     (3, 4),
39///     (4, 5),
40///     (6, 7),
41///     (7, 8),
42///     (8, 9),
43/// ];
44/// let mut graph = DiGraph::<i32, i32>::from_edges(&edge_list);
45/// graph.add_node(10);
46/// graph.add_node(11);
47/// let res: Vec<usize> = isolates(&graph).into_iter().map(|x| x.index()).collect();
48/// assert_eq!(res, [10, 11])
49/// ```
50pub fn isolates<G>(graph: G) -> Vec<G::NodeId>
51where
52    G: NodeIndexable + IntoNodeIdentifiers + IntoNeighborsDirected,
53{
54    graph
55        .node_identifiers()
56        .filter(|x| {
57            graph
58                .neighbors_directed(*x, Incoming)
59                .chain(graph.neighbors_directed(*x, Outgoing))
60                .next()
61                .is_none()
62        })
63        .collect()
64}
65
66#[cfg(test)]
67mod tests {
68    use crate::connectivity::isolates;
69    use petgraph::prelude::*;
70
71    #[test]
72    fn test_isolates_directed_empty() {
73        let graph = DiGraph::<i32, i32>::new();
74        let res: Vec<NodeIndex> = isolates(&graph);
75        assert_eq!(res, []);
76    }
77
78    #[test]
79    fn test_isolates_undirected_empty() {
80        let graph = UnGraph::<i32, i32>::default();
81        let res: Vec<NodeIndex> = isolates(&graph);
82        assert_eq!(res, []);
83    }
84
85    #[test]
86    fn test_isolates_directed_no_isolates() {
87        let graph = DiGraph::<i32, i32>::from_edges([(0, 1), (1, 2)]);
88        let res: Vec<NodeIndex> = isolates(&graph);
89        assert_eq!(res, []);
90    }
91
92    #[test]
93    fn test_isolates_undirected_no_isolates() {
94        let graph = UnGraph::<i32, i32>::from_edges([(0, 1), (1, 2)]);
95        let res: Vec<NodeIndex> = isolates(&graph);
96        assert_eq!(res, []);
97    }
98
99    #[test]
100    fn test_isolates_directed() {
101        let edge_list = vec![
102            (0, 1),
103            (3, 0),
104            (0, 5),
105            (8, 0),
106            (1, 2),
107            (1, 6),
108            (2, 3),
109            (3, 4),
110            (4, 5),
111            (6, 7),
112            (7, 8),
113            (8, 9),
114        ];
115        let mut graph = DiGraph::<i32, i32>::from_edges(edge_list);
116        graph.add_node(10);
117        graph.add_node(11);
118        let res: Vec<usize> = isolates(&graph).into_iter().map(|x| x.index()).collect();
119        assert_eq!(res, [10, 11])
120    }
121
122    #[test]
123    fn test_isolates_undirected() {
124        let edge_list = vec![
125            (0, 1),
126            (3, 0),
127            (0, 5),
128            (8, 0),
129            (1, 2),
130            (1, 6),
131            (2, 3),
132            (3, 4),
133            (4, 5),
134            (6, 7),
135            (7, 8),
136            (8, 9),
137        ];
138        let mut graph = UnGraph::<i32, i32>::from_edges(edge_list);
139        graph.add_node(10);
140        graph.add_node(11);
141        let res: Vec<usize> = isolates(&graph).into_iter().map(|x| x.index()).collect();
142        assert_eq!(res, [10, 11])
143    }
144}
rustworkx_core/connectivity/isolates.rs

rustworkx_core/connectivity/
isolates.rs
