hypergraph/core/
mod.rs

1pub(crate) mod bi_hash_map;
2#[doc(hidden)]
3pub mod errors;
4#[doc(hidden)]
5pub mod hyperedges;
6mod indexes;
7#[doc(hidden)]
8pub mod iterator;
9mod shared;
10#[doc(hidden)]
11mod types;
12mod utils;
13#[doc(hidden)]
14pub mod vertices;
15
16use std::{
17    fmt::{
18        Debug,
19        Display,
20        Formatter,
21        Result,
22    },
23    hash::Hash,
24    ops::Deref,
25};
26
27use bi_hash_map::BiHashMap;
28use types::{
29    AIndexMap,
30    AIndexSet,
31    ARandomState,
32};
33
34// Reexport indexes at this level.
35pub use crate::core::indexes::{
36    HyperedgeIndex,
37    VertexIndex,
38};
39
40/// Shared Trait for the vertices.
41/// Must be implemented to use the library.
42pub trait VertexTrait: Copy + Debug + Display + Eq + Hash + Send + Sync {}
43
44impl<T> VertexTrait for T where T: Copy + Debug + Display + Eq + Hash + Send + Sync {}
45
46/// Shared Trait for the hyperedges.
47/// Must be implemented to use the library.
48pub trait HyperedgeTrait: VertexTrait + Into<usize> {}
49
50impl<T> HyperedgeTrait for T where T: VertexTrait + Into<usize> {}
51
52/// A `HyperedgeKey` is a representation of both the vertices and the weight
53/// of a hyperedge, used as a key in the hyperedges set.
54/// In a non-simple hypergraph, since the same vertices can be shared by
55/// different hyperedges, the weight is also included in the key to keep
56/// it unique.
57#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
58pub(crate) struct HyperedgeKey<HE> {
59    vertices: Vec<usize>,
60    weight: HE,
61}
62
63impl<HE> HyperedgeKey<HE> {
64    /// Creates a new `HyperedgeKey` from the given vertices and weight.
65    pub(crate) fn new(vertices: Vec<usize>, weight: HE) -> HyperedgeKey<HE> {
66        Self { vertices, weight }
67    }
68}
69
70impl<HE> Deref for HyperedgeKey<HE> {
71    type Target = HE;
72
73    fn deref(&self) -> &HE {
74        &self.weight
75    }
76}
77
78/// A directed hypergraph composed of generic vertices and hyperedges.
79pub struct Hypergraph<V, HE> {
80    /// Vertices are stored as a map whose unique keys are the weights
81    /// and the values are a set of the hyperedges indexes which include
82    /// the current vertex.
83    vertices: AIndexMap<V, AIndexSet<usize>>,
84
85    /// Hyperedges are stored as a set whose unique keys are a combination of
86    /// vertices indexes and a weight. Two or more hyperedges can contain
87    /// the exact same vertices (non-simple hypergraph).
88    hyperedges: AIndexSet<HyperedgeKey<HE>>,
89
90    /// Bi-directional map for hyperedges.
91    hyperedges_mapping: BiHashMap<HyperedgeIndex>,
92
93    /// Bi-directional map for vertices.
94    vertices_mapping: BiHashMap<VertexIndex>,
95
96    /// Stable index generation counter for hyperedges.
97    hyperedges_count: usize,
98
99    /// Stable index generation counter for vertices.
100    vertices_count: usize,
101}
102
103impl<V, HE> Debug for Hypergraph<V, HE>
104where
105    V: Eq + Hash + Debug,
106    HE: Debug,
107{
108    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
109        f.debug_struct("Hypergraph")
110            .field("vertices", &self.vertices)
111            .field("hyperedges", &self.hyperedges)
112            .finish_non_exhaustive()
113    }
114}
115
116impl<V, HE> Default for Hypergraph<V, HE>
117where
118    V: VertexTrait,
119    HE: HyperedgeTrait,
120{
121    fn default() -> Self {
122        Hypergraph::new()
123    }
124}
125
126/// Hypergraph implementations.
127impl<V, HE> Hypergraph<V, HE>
128where
129    V: VertexTrait,
130    HE: HyperedgeTrait,
131{
132    /// Clears the hypergraph.
133    pub fn clear(&mut self) {
134        // Clear the hyperedges and vertices sets while keeping their capacities.
135        self.hyperedges.clear();
136        self.vertices.clear();
137
138        // Reset the mappings.
139        self.hyperedges_mapping = BiHashMap::default();
140        self.vertices_mapping = BiHashMap::default();
141
142        // Reset the counters.
143        self.hyperedges_count = 0;
144        self.vertices_count = 0;
145    }
146
147    /// Creates a new hypergraph with no allocation.
148    pub fn new() -> Self {
149        Hypergraph::with_capacity(0, 0)
150    }
151
152    /// Creates a new hypergraph with the specified capacity.
153    pub fn with_capacity(vertices: usize, hyperedges: usize) -> Self {
154        Hypergraph {
155            hyperedges_count: 0,
156            hyperedges_mapping: BiHashMap::default(),
157            hyperedges: AIndexSet::with_capacity_and_hasher(hyperedges, ARandomState::default()),
158            vertices_count: 0,
159            vertices_mapping: BiHashMap::default(),
160            vertices: AIndexMap::with_capacity_and_hasher(vertices, ARandomState::default()),
161        }
162    }
163}
hypergraph/core/mod.rs

hypergraph/core/
mod.rs
