rustworkx_core/
transitivity.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 hashbrown::HashSet;
14
15use petgraph::visit::{IntoEdges, IntoNeighborsDirected, IntoNodeIdentifiers, NodeIndexable};
16use rayon::prelude::*;
17
18use std::hash::Hash;
19
20/// Counts triangles and connected triples containing `node` of the given undirected graph.
21fn graph_node_triangles<G>(graph: G, node: G::NodeId) -> (usize, usize)
22where
23    G: IntoEdges,
24    G::NodeId: Hash + Eq,
25{
26    let node_neighbors: HashSet<G::NodeId> = graph.neighbors(node).filter(|v| *v != node).collect();
27
28    let triangles: usize = node_neighbors
29        .iter()
30        .map(|&v| {
31            graph
32                .neighbors(v)
33                .filter(|&x| (x != v) && node_neighbors.contains(&x))
34                .count()
35        })
36        .sum();
37
38    let triples = match node_neighbors.len() {
39        0 => 0,
40        d => (d * (d - 1)) / 2,
41    };
42
43    (triangles / 2, triples)
44}
45
46/// Compute the transitivity of an undirected graph.
47///
48/// The transitivity of a graph is 3*number of triangles / number of connected triples, where
49/// “connected triple” means a single vertex with edges running to an unordered pair of others.
50///
51/// This function is multithreaded and will launch a thread pool with threads equal to the number
52/// of CPUs by default. You can tune the number of threads with the ``RAYON_NUM_THREADS``
53/// environment variable. For example, setting ``RAYON_NUM_THREADS=4`` would limit the thread pool
54/// to 4 threads.
55///
56/// The function implicitly assumes that there are no parallel edges or self loops. It may produce
57/// incorrect/unexpected results if the input graph has self loops or parallel edges.
58pub fn graph_transitivity<G>(graph: G) -> f64
59where
60    G: NodeIndexable + IntoEdges + IntoNodeIdentifiers + Send + Sync,
61    G::NodeId: Hash + Eq + Send + Sync,
62{
63    let nodes: Vec<_> = graph.node_identifiers().collect();
64    let (triangles, triples) = nodes
65        .par_iter()
66        .map(|node| graph_node_triangles(graph, *node))
67        .reduce(
68            || (0, 0),
69            |(sumx, sumy), (resx, resy)| (sumx + resx, sumy + resy),
70        );
71
72    match triangles {
73        0 => 0.0,
74        _ => triangles as f64 / triples as f64,
75    }
76}
77
78/// Counts triangles and triples containing `node` of the given directed graph.
79fn digraph_node_triangles<G>(graph: G, node: G::NodeId) -> (usize, usize)
80where
81    G: IntoNeighborsDirected,
82    G::NodeId: Hash + Eq,
83{
84    let out_neighbors: HashSet<G::NodeId> = graph
85        .neighbors_directed(node, petgraph::Direction::Outgoing)
86        .filter(|v| *v != node)
87        .collect();
88
89    let in_neighbors: HashSet<G::NodeId> = graph
90        .neighbors_directed(node, petgraph::Direction::Incoming)
91        .filter(|v| *v != node)
92        .collect();
93
94    let triangles: usize = out_neighbors
95        .iter()
96        .chain(in_neighbors.iter())
97        .map(|v| {
98            graph
99                .neighbors_directed(*v, petgraph::Direction::Outgoing)
100                .chain(graph.neighbors_directed(*v, petgraph::Direction::Incoming))
101                .map(|x| {
102                    ((x != *v) && out_neighbors.contains(&x)) as usize
103                        + ((x != *v) && in_neighbors.contains(&x)) as usize
104                })
105                .sum::<usize>()
106        })
107        .sum();
108
109    let d_tot = in_neighbors.len() + out_neighbors.len();
110    let d_bil = out_neighbors.intersection(&in_neighbors).count();
111    let triples = match d_tot {
112        0 => 0,
113        _ => d_tot * (d_tot - 1) - 2 * d_bil,
114    };
115
116    (triangles / 2, triples)
117}
118
119/// Compute the transitivity of a directed graph.
120///
121/// The transitivity of a directed graph is 3*number of triangles/number of all possible triangles.
122/// A triangle is a connected triple of nodes. Different edge orientations counts as different
123/// triangles.
124///
125/// This function is multithreaded and will launch a thread pool with threads equal to the number
126/// of CPUs by default. You can tune the number of threads with the ``RAYON_NUM_THREADS``
127/// environment variable. For example, setting ``RAYON_NUM_THREADS=4`` would limit the thread pool
128/// to 4 threads.
129///
130/// The function implicitly assumes that there are no parallel edges or self loops. It may produce
131/// incorrect/unexpected results if the input graph has self loops or parallel edges.
132pub fn digraph_transitivity<G>(graph: G) -> f64
133where
134    G: NodeIndexable + IntoNodeIdentifiers + IntoNeighborsDirected + Send + Sync,
135    G::NodeId: Hash + Eq + Send + Sync,
136{
137    let nodes: Vec<_> = graph.node_identifiers().collect();
138    let (triangles, triples) = nodes
139        .par_iter()
140        .map(|node| digraph_node_triangles(graph, *node))
141        .reduce(
142            || (0, 0),
143            |(sumx, sumy), (resx, resy)| (sumx + resx, sumy + resy),
144        );
145
146    match triangles {
147        0 => 0.0,
148        _ => triangles as f64 / triples as f64,
149    }
150}
151
152#[cfg(test)]
153mod test_transitivity {
154    use petgraph::{
155        graph::{DiGraph, UnGraph},
156        Graph,
157    };
158
159    use super::{
160        digraph_node_triangles, digraph_transitivity, graph_node_triangles, graph_transitivity,
161    };
162
163    #[test]
164    fn test_node_triangles() {
165        let mut graph: UnGraph<(), ()> = Graph::with_capacity(5, 6);
166        let a = graph.add_node(());
167        let b = graph.add_node(());
168        let c = graph.add_node(());
169        let d = graph.add_node(());
170        let e = graph.add_node(());
171        graph.extend_with_edges([(a, b), (b, c), (a, c), (a, d), (c, d), (d, e)]);
172        assert_eq!(graph_node_triangles(&graph, a), (2, 3));
173    }
174
175    #[test]
176    fn test_node_triangles_disconnected() {
177        let mut graph: UnGraph<(), ()> = Graph::with_capacity(1, 0);
178        let a = graph.add_node(());
179        assert_eq!(graph_node_triangles(&graph, a), (0, 0));
180    }
181
182    #[test]
183    fn test_transitivity() {
184        let mut graph: UnGraph<(), ()> = Graph::with_capacity(5, 5);
185        let a = graph.add_node(());
186        let b = graph.add_node(());
187        let c = graph.add_node(());
188        let d = graph.add_node(());
189        let e = graph.add_node(());
190        graph.extend_with_edges([(a, b), (a, c), (a, d), (a, e), (b, c)]);
191
192        assert_eq!(graph_transitivity(&graph), 3. / 8.);
193    }
194
195    #[test]
196    fn test_transitivity_triangle() {
197        let mut graph: UnGraph<(), ()> = Graph::with_capacity(3, 3);
198        let a = graph.add_node(());
199        let b = graph.add_node(());
200        let c = graph.add_node(());
201        graph.extend_with_edges([(a, b), (a, c), (b, c)]);
202        assert_eq!(graph_transitivity(&graph), 1.0)
203    }
204
205    #[test]
206    fn test_transitivity_star() {
207        let mut graph: UnGraph<(), ()> = Graph::with_capacity(5, 4);
208        let a = graph.add_node(());
209        let b = graph.add_node(());
210        let c = graph.add_node(());
211        let d = graph.add_node(());
212        let e = graph.add_node(());
213        graph.extend_with_edges([(a, b), (a, c), (a, d), (a, e)]);
214        assert_eq!(graph_transitivity(&graph), 0.0)
215    }
216
217    #[test]
218    fn test_transitivity_empty() {
219        let graph: UnGraph<(), ()> = Graph::with_capacity(0, 0);
220        assert_eq!(graph_transitivity(&graph), 0.0)
221    }
222
223    #[test]
224    fn test_transitivity_disconnected() {
225        let mut graph: UnGraph<(), ()> = Graph::with_capacity(2, 1);
226        let a = graph.add_node(());
227        let b = graph.add_node(());
228        graph.add_node(());
229        graph.add_edge(a, b, ());
230        assert_eq!(graph_transitivity(&graph), 0.0)
231    }
232
233    #[test]
234    fn test_two_directed_node_triangles() {
235        let mut graph: DiGraph<(), ()> = Graph::with_capacity(5, 7);
236        let a = graph.add_node(());
237        let b = graph.add_node(());
238        let c = graph.add_node(());
239        let d = graph.add_node(());
240        let e = graph.add_node(());
241        // The reciprocal edge (a, c) (c, a) double the number of triangles
242        graph.extend_with_edges([(a, b), (b, c), (c, a), (a, c), (c, d), (d, a), (d, e)]);
243        assert_eq!(digraph_node_triangles(&graph, a), (4, 10));
244    }
245
246    #[test]
247    fn test_directed_node_triangles_disconnected() {
248        let mut graph: DiGraph<(), ()> = Graph::with_capacity(1, 0);
249        let a = graph.add_node(());
250        assert_eq!(graph_node_triangles(&graph, a), (0, 0));
251    }
252
253    #[test]
254    fn test_transitivity_directed() {
255        let mut graph: DiGraph<(), ()> = Graph::with_capacity(5, 4);
256        let a = graph.add_node(());
257        let b = graph.add_node(());
258        let c = graph.add_node(());
259        let d = graph.add_node(());
260        graph.add_node(());
261        graph.extend_with_edges([(a, b), (a, c), (a, d), (b, c)]);
262        assert_eq!(digraph_transitivity(&graph), 3. / 10.);
263    }
264
265    #[test]
266    fn test_transitivity_triangle_directed() {
267        let mut graph: DiGraph<(), ()> = Graph::with_capacity(3, 3);
268        let a = graph.add_node(());
269        let b = graph.add_node(());
270        let c = graph.add_node(());
271        graph.extend_with_edges([(a, b), (a, c), (b, c)]);
272        assert_eq!(digraph_transitivity(&graph), 0.5);
273    }
274
275    #[test]
276    fn test_transitivity_fulltriangle_directed() {
277        let mut graph: DiGraph<(), ()> = Graph::with_capacity(3, 6);
278        let a = graph.add_node(());
279        let b = graph.add_node(());
280        let c = graph.add_node(());
281        graph.extend_with_edges([(a, b), (b, a), (a, c), (c, a), (b, c), (c, b)]);
282        assert_eq!(digraph_transitivity(&graph), 1.0);
283    }
284
285    #[test]
286    fn test_transitivity_empty_directed() {
287        let graph: DiGraph<(), ()> = Graph::with_capacity(0, 0);
288        assert_eq!(digraph_transitivity(&graph), 0.0);
289    }
290}
rustworkx_core/transitivity.rs

rustworkx_core/
transitivity.rs
