hypergraphx/traits/
mod.rs

1//! Most of the functionality of this library is encapsulated in these traits. A quick overview:
2//!
3//! GraphBasics: Provides iterators over nodes and edges.
4//! 
5//! Weights: Provides shared and mutable access to node and edge weight.
6//! 
7//! MatrixRepresentation: Adjacency and incidence matrices.
8//! 
9//! GraphProperties: Basic properties of graphs, such as degree, connected components, etc.
10//! 
11//! DiGraphProperties: The directed analogue of GraphProperties.
12//! 
13//! CommonProperties: Trait for functions that apply to both directed and undirected graphs, but with
14//!     different implementations.
15//! 
16//! HypergraphProperties: Properties specific to hypergraphs, such as edge order.
17//! 
18//! DirectedHypergraphProperties: Directed analogue of HypergraphProperties.
19//! 
20//! GraphType: A trait over which other traits are generic - when the same set of functions
21//!     applies to multiple kinds of graphs and I didn't want to write the same code multiple times.
22//!     In general, unless you're implementing a new graph type, you do not need to worry about this 
23//!     trait.
24//! 
25//! ParallelWeights: Provides parallel iterators over graph weights with rayon.
26//!     
27//!
28//! In principle, none of these traits borrow the graph (or atleast the incidence structure) mutably. 
29//! All mutation is done though struct methods, because the function signatures vary too much 
30//! between different graph types. Also, cleaner?
31
32use crate::prelude::*;
33use hashbrown::{HashMap, HashSet};
34use itertools::Itertools;
35use std::{
36    hash::Hash,
37    ops::{Deref, DerefMut},
38};
39
40pub mod undirected;
41pub use undirected::*;
42pub mod directed;
43pub use directed::*;
44pub mod linalg;
45pub use linalg::*;
46pub mod common;
47pub use common::*;
48#[cfg(feature = "rayon")]
49pub mod parallel;
50#[cfg(feature = "rayon")]
51pub use parallel::*;
52
53/// The root trait for all graphs and hypergraphs.
54/// Provides functions to iterate over nodes and edges, and count them.
55///
56/// Note: We have the associated types `NodeRef` and `EdgeRef`, which are references to
57/// nodes and edges respectively. This allows complex graph types, like `Multiplex`, to use
58/// enums with variants holding references to different types of edges or nodes.
59///
60/// Typical graphs and hypergraphs use `usize` for node and edge indices. However,
61/// the associated types `NodeIndex` and `EdgeIndex` allow for more complex graph types to use
62/// different of indices.
63/// For example, `Multiplex` uses `MultiplexIndex(Option<usize>, usize)`. This allows trait methods to
64/// return sets of/iterators over edges from a specific layer (`Some` variant) or over all layers (`None` variant).
65///
66/// However, the `NodeIndex` and `EdgeIndex` types must implement `From<usize>` and `Into<usize>`, so that the methods
67/// accepting indices as arguments can be used while iterating over the nodes and/or edges.
68///
69pub trait GraphBasics<'a> {
70    type NodeRef: Eq + Hash + Copy;
71    type EdgeRef: Eq + Hash + Copy;
72
73    type NodeIndex: Copy + Eq + Hash + From<usize> + Into<usize>;
74    type EdgeIndex: Copy + Eq + Hash + From<usize> + Into<usize>;
75
76    fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef>;
77    fn node_count(&'a self) -> usize;
78
79    fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef>;
80    fn edge_count(&'a self) -> usize;
81
82    fn is_directed(&self) -> bool;
83    fn node(&'a self, node_index: Self::NodeIndex) -> Option<Self::NodeRef>;
84    fn edge(&'a self, edge_index: Self::EdgeIndex) -> Option<Self::EdgeRef>;
85    fn node_iter(
86        &'a self,
87        node_index: impl Iterator<Item = Self::NodeIndex>,
88    ) -> impl Iterator<Item = Option<Self::NodeRef>>;
89    fn edge_iter(
90        &'a self,
91        edge_index: impl Iterator<Item = Self::EdgeIndex>,
92    ) -> impl Iterator<Item = Option<Self::EdgeRef>>;
93}
94
95#[macro_export]
96macro_rules! impl_graph_basics {
97    ($graph:ty, $node:ty, $edge:ty, $dir:literal $(, <$($gens:tt),*>)? $(, |$(const $cgens:ident: $ity:ty),*|)? ) => {
98        // use rayon::prelude::*;
99        impl<'a, N, E$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
100            for $graph
101            where N: 'a + Clone + Eq + Hash,
102                  E: 'a + Clone + Eq + Hash,
103        {
104            type NodeRef = $node;
105            type EdgeRef = $edge;
106            type EdgeIndex = usize;
107            type NodeIndex = usize;
108
109            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
110                self.nodes.iter()
111            }
112
113            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
114                self.edges.iter()
115            }
116            fn node_count(&'a self) -> usize {
117                self.nodes.len()
118            }
119
120            fn edge_count(&'a self) -> usize {
121                self.edges.len()
122            }
123            fn is_directed(&self) -> bool {
124                $dir
125            }
126            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
127                self.nodes.get(node_index)
128            }
129            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
130                self.edges.get(edge_index)
131            }
132            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
133                node_index.map(|i| self.node(i))
134            }
135            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
136                edge_index.map(|i| self.edge(i))
137            }
138        }
139    };
140}
141
142impl<'a, T, U> GraphBasics<'a> for U
143where
144    T: GraphBasics<'a> + 'a,
145    U: Deref<Target = T>,
146{
147    type NodeRef = T::NodeRef;
148
149    type EdgeRef = T::EdgeRef;
150
151    type NodeIndex = T::NodeIndex;
152
153    type EdgeIndex = T::EdgeIndex;
154
155    fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
156        (**self).nodes()
157    }
158
159    fn node_count(&'a self) -> usize {
160        (**self).node_count()
161    }
162
163    fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
164        (**self).edges()
165    }
166
167    fn edge_count(&'a self) -> usize {
168        (**self).edge_count()
169    }
170
171    fn is_directed(&self) -> bool {
172        (**self).is_directed()
173    }
174
175    fn node(&'a self, node_index: Self::NodeIndex) -> Option<Self::NodeRef> {
176        (**self).node(node_index)
177    }
178
179    fn edge(&'a self, edge_index: Self::EdgeIndex) -> Option<Self::EdgeRef> {
180        (**self).edge(edge_index)
181    }
182
183    fn node_iter(
184        &'a self,
185        node_index: impl Iterator<Item = Self::NodeIndex>,
186    ) -> impl Iterator<Item = Option<Self::NodeRef>> {
187        node_index.map(|i| (**self).node(i))
188    }
189
190    fn edge_iter(
191        &'a self,
192        edge_index: impl Iterator<Item = Self::EdgeIndex>,
193    ) -> impl Iterator<Item = Option<Self::EdgeRef>> {
194        edge_index.map(|i| (**self).edge(i))
195    }
196}
197
198/// This trait allows mutable access to the node and edge *weights* of a graph.
199/// It's generally a bad idea to mess with the graph incidence data - that's why there's no
200/// mutable access to `Node`s or `Edge`s. You can, however, go crazy with the weights.
201///
202/// As for shared access to the weights, just iterate over the nodes (edges) and access the weights directly.
203pub trait Weights<'a, N: 'a, E: 'a>: GraphBasics<'a> {
204    fn node_weights(&'a self) -> impl Iterator<Item = &'a N> + 'a;
205    fn edge_weights(&'a self) -> impl Iterator<Item = &'a E> + 'a;
206    fn node_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut N> + 'a;
207    fn edge_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut E> + 'a;
208    fn node_weight_mut(
209        &'a mut self,
210        node_index: <Self as GraphBasics<'a>>::NodeIndex,
211    ) -> Option<&'a mut N>;
212    fn edge_weight_mut(
213        &'a mut self,
214        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
215    ) -> Option<&'a mut E>;
216    fn node_weight(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<&'a N>;
217    fn edge_weight(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<&'a E>;
218    // Be nice to have these, I figured.
219    unsafe fn node_weight_unchecked(
220        &'a self,
221        node_index: <Self as GraphBasics<'a>>::NodeIndex,
222    ) -> &'a N;
223    unsafe fn edge_weight_unchecked(
224        &'a self,
225        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
226    ) -> &'a E;
227    unsafe fn node_weight_unchecked_mut(
228        &'a mut self,
229        node_index: <Self as GraphBasics<'a>>::NodeIndex,
230    ) -> &'a mut N;
231    unsafe fn edge_weight_unchecked_mut(
232        &'a mut self,
233        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
234    ) -> &'a mut E;
235    fn edge_weight_copied(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<E>
236    where
237        E: Copy;
238    fn node_weight_copied(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<N>
239    where
240        N: Copy;
241    unsafe fn edge_weight_copied_unchecked(
242        &'a self,
243        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
244    ) -> E
245    where
246        E: Copy;
247    unsafe fn node_weight_copied_unchecked(
248        &'a self,
249        node_index: <Self as GraphBasics<'a>>::NodeIndex,
250    ) -> N
251    where
252        N: Copy;
253}
254
255#[macro_export]
256macro_rules! impl_weights {
257    ($graph:ty$(, <$($gens:tt),*>)? $(, |$(const $cgens:ident: $ity:ty),*|)?) => {
258        impl<'a, N: 'a, E: 'a$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> Weights<'a, N, E> for $graph
259        where
260            N: Clone + Eq + Hash,
261            E: Clone + Eq + Hash,
262        {
263            fn node_weights(&'a self) -> impl Iterator<Item = &'a N> + 'a {
264                self.nodes.iter().map(|node| &node.weight)
265            }
266
267            fn edge_weights(&'a self) -> impl Iterator<Item = &'a E> + 'a {
268                self.edges.iter().map(|edge| &edge.weight)
269            }
270
271            fn node_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut N> + 'a {
272                self.nodes.iter_mut().map(|node| &mut node.weight)
273            }
274
275            fn edge_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut E> + 'a {
276                self.edges.iter_mut().map(|edge| &mut edge.weight)
277            }
278
279            fn node_weight_mut(&'a mut self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<&'a mut N> {
280                self.nodes.get_mut(node_index).map(|node| &mut node.weight)
281            }
282
283            fn edge_weight_mut(&'a mut self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<&'a mut E> {
284                self.edges.get_mut(edge_index).map(|edge| &mut edge.weight)
285            }
286
287            fn node_weight(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<&'a N> {
288                self.nodes.get(node_index).map(|node| &node.weight)
289            }
290
291            fn edge_weight(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<&'a E> {
292                self.edges.get(edge_index).map(|edge| &edge.weight)
293            }
294
295            unsafe fn node_weight_unchecked(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> &'a N {
296                unsafe {&self.nodes.get_unchecked(node_index).weight}
297            }
298
299            unsafe fn edge_weight_unchecked(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> &'a E {
300                unsafe {&self.edges.get_unchecked(edge_index).weight}
301            }
302
303            unsafe fn node_weight_unchecked_mut(&'a mut self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> &'a mut N {
304                unsafe {&mut self.nodes.get_unchecked_mut(node_index).weight}
305            }
306
307            unsafe fn edge_weight_unchecked_mut(&'a mut self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> &'a mut E {
308                unsafe {&mut self.edges.get_unchecked_mut(edge_index).weight}
309            }
310
311            fn edge_weight_copied(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<E> where E: Copy {
312                Some(self.edges[edge_index].weight)
313            }
314
315            fn node_weight_copied(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<N> where N: Copy {
316                Some(self.nodes[node_index].weight)
317            }
318
319            unsafe fn edge_weight_copied_unchecked(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> E where E: Copy {
320                unsafe{self.edges.get_unchecked(edge_index).weight}
321            }
322
323            unsafe fn node_weight_copied_unchecked(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> N where N: Copy {
324                unsafe{self.nodes.get_unchecked(node_index).weight}
325            }
326        }
327
328    }
329}
330
331impl<'a, T: 'a, U, N: 'a, E: 'a> Weights<'a, N, E> for U
332where
333    T: Weights<'a, N, E>,
334    U: DerefMut<Target = T>,
335{
336    fn node_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut N> + 'a {
337        (**self).node_weights_mut()
338    }
339
340    fn edge_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut E> + 'a {
341        (**self).edge_weights_mut()
342    }
343
344    fn node_weight_mut(
345        &'a mut self,
346        node_index: <Self as GraphBasics<'a>>::NodeIndex,
347    ) -> Option<&'a mut N> {
348        (**self).node_weight_mut(node_index)
349    }
350
351    fn edge_weight_mut(
352        &'a mut self,
353        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
354    ) -> Option<&'a mut E> {
355        (**self).edge_weight_mut(edge_index)
356    }
357
358    fn node_weight(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<&'a N> {
359        (**self).node_weight(node_index)
360    }
361
362    fn edge_weight(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<&'a E> {
363        (**self).edge_weight(edge_index)
364    }
365
366    unsafe fn node_weight_unchecked(
367        &'a self,
368        node_index: <Self as GraphBasics<'a>>::NodeIndex,
369    ) -> &'a N {
370        unsafe { (**self).node_weight_unchecked(node_index) }
371    }
372
373    unsafe fn edge_weight_unchecked(
374        &'a self,
375        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
376    ) -> &'a E {
377        unsafe { (**self).edge_weight_unchecked(edge_index) }
378    }
379
380    unsafe fn node_weight_unchecked_mut(
381        &'a mut self,
382        node_index: <Self as GraphBasics<'a>>::NodeIndex,
383    ) -> &'a mut N {
384        unsafe { (**self).node_weight_unchecked_mut(node_index) }
385    }
386
387    unsafe fn edge_weight_unchecked_mut(
388        &'a mut self,
389        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
390    ) -> &'a mut E {
391        unsafe { (**self).edge_weight_unchecked_mut(edge_index) }
392    }
393
394    fn edge_weight_copied(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<E>
395    where
396        E: Copy,
397    {
398        (**self).edge_weight_copied(edge_index)
399    }
400
401    fn node_weight_copied(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<N>
402    where
403        N: Copy,
404    {
405        (**self).node_weight_copied(node_index)
406    }
407
408    unsafe fn edge_weight_copied_unchecked(
409        &'a self,
410        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
411    ) -> E
412    where
413        E: Copy,
414    {
415        unsafe { (**self).edge_weight_copied_unchecked(edge_index) }
416    }
417
418    unsafe fn node_weight_copied_unchecked(
419        &'a self,
420        node_index: <Self as GraphBasics<'a>>::NodeIndex,
421    ) -> N
422    where
423        N: Copy,
424    {
425        unsafe { (**self).node_weight_copied_unchecked(node_index) }
426    }
427
428    fn node_weights(&'a self) -> impl Iterator<Item = &'a N> + 'a {
429        (**self).node_weights()
430    }
431
432    fn edge_weights(&'a self) -> impl Iterator<Item = &'a E> + 'a {
433        (**self).edge_weights()
434    }
435}
436
437#[cfg(feature = "temporal")]
438pub trait TemporalProperties<'a>: GraphBasics<'a> {
439    type Inner: GraphBasics<'a>;
440    fn step(&mut self) {
441        *self.get_time_mut() += 1;
442    }
443    fn get_time(&self) -> usize;
444    /// Use this method to jump forward and backward, maybe for snapshots, 
445    /// maybe to test whether stuff behaves the way you want it to.
446    fn get_time_mut(&mut self) -> &mut usize;
447
448    fn snapshot(&'a self) -> &'a Self::Inner;
449
450    fn temporal_behaviour(&self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<TemporalBehaviour>;
451}
452
453pub trait HypergraphBasics<'a>: GraphBasics<'a> {
454    /// Returns none if the hypergraph is not uniform, or the size of the hyperedges if it is.
455    /// A hypergraph is uniform if all hyperedges have the same number of nodes.
456    /// For example, a hypergraph with hyperedges of size 3 is 3-uniform.
457    fn uniform(&self) -> bool;
458
459    /// Much like subgraphs, the dual of a hypergraph is not necessarily the same type as the original
460    /// hypergraph. For example, the dual of a uniform hypergraph is not necessarily uniform.
461    type DualType;
462    fn dual(&self) -> Self::DualType;
463}
464
465pub trait StatisticalFilters {}
466
467pub trait Dynamics {}
468
469pub trait Generate<N, E, T: GraphType> {
470    /// Make your own parser inside this function.
471    fn from_file<P: AsRef<std::path::Path>>(path: P) -> Self;
472    /// Unweighted Hypergraphs only.
473    fn random_hypergraph(node_count: usize, edges_by_size: HashMap<usize, usize>) -> Self;
474    fn random_weighted_hypergraph(
475        node_count: usize,
476        edges_by_size: HashMap<usize, usize>,
477        node_weight_sampler: impl Fn() -> N,
478        edge_weight_sampler: impl Fn() -> E,
479    ) -> Self;
480}
481
hypergraphx/traits/mod.rs

hypergraphx/traits/
mod.rs
