1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
use crate::{
core::utils::are_arrays_equal, HyperedgeIndex, HyperedgeVertices, Hypergraph, SharedTrait,
VertexIndex, WeightedHyperedgeIndex,
};
use indexmap::IndexSet;
use itertools::{max, Itertools};
impl<V, HE> Hypergraph<V, HE>
where
V: SharedTrait,
HE: SharedTrait,
{
/// Adds a hyperedge as an array of vertices indexes and a custom weight in the hypergraph.
/// Returns the weighted index of the hyperedge.
pub fn add_hyperedge(
&mut self,
vertices: &[usize],
weight: HE,
) -> Option<WeightedHyperedgeIndex> {
// Safe check to avoid out of bound index!
if *max(vertices).unwrap() + 1 > self.vertices.len() {
return None;
}
// Update the vertices so that we keep directly track of the hyperedge.
for vertex in vertices.iter() {
let mut index_set = self.vertices[*vertex].clone();
index_set.insert(vertices.to_vec());
self.vertices.insert(
self.vertices.get_index(*vertex).unwrap().0.to_owned(),
index_set,
);
}
// Insert the new hyperedge with the corresponding weight, get back the indexes.
Some(match self.hyperedges.get(vertices) {
Some(weights) => {
let mut new_weights = weights.clone();
let (weight_index, _) = new_weights.insert_full(weight);
let (hyperedge_index, _) = self
.hyperedges
.insert_full(vertices.to_owned(), new_weights);
[hyperedge_index, weight_index]
}
None => {
let mut weights = IndexSet::new();
let (weight_index, _) = weights.insert_full(weight);
let (hyperedge_index, _) =
self.hyperedges.insert_full(vertices.to_owned(), weights);
[hyperedge_index, weight_index]
}
})
}
/// Returns the number of hyperedges in the hypergraph.
pub fn count_hyperedges(&self) -> usize {
self.hyperedges
.iter()
.fold(0, |count, (_, weights)| count + weights.len())
}
/// Gets the list of all hyperedges containing a matching connection from
/// one vertex to another.
pub fn get_hyperedges_connections(
&self,
from: VertexIndex,
to: VertexIndex,
) -> Vec<VertexIndex> {
self.get_connections(from, Some(to))
}
/// Gets the hyperedge's vertices.
pub fn get_hyperedge_vertices(&self, index: HyperedgeIndex) -> Option<HyperedgeVertices> {
self.hyperedges
.get_index(index)
.map(|(vertices, _)| vertices.to_owned())
}
/// Gets the weight of a hyperedge from its weighted index.
pub fn get_hyperedge_weight(
&self,
[hyperedge_index, weight_index]: WeightedHyperedgeIndex,
) -> Option<&HE> {
match self.hyperedges.get_index(hyperedge_index) {
Some((_, weights)) => weights.get_index(weight_index),
None => None,
}
}
/// Gets the intersections of a set of hyperedges as a vector of vertices.
pub fn get_hyperedges_intersections(&self, hyperedges: &[HyperedgeIndex]) -> HyperedgeVertices {
hyperedges
.iter()
.filter_map(|index| {
self.hyperedges
.get_index(*index)
.map(|(vertices, _)| vertices.iter().unique().collect_vec())
})
.flatten()
.sorted()
// Map the result to tuples where the second term is an arbitrary value.
// The goal is to group them by indexes.
.map(|index| (*index, 0))
.into_group_map()
.iter()
// Filter the groups having the same size as the hyperedge.
.filter_map(|(index, occurences)| {
if occurences.len() == hyperedges.len() {
Some(*index)
} else {
None
}
})
.sorted()
.collect::<Vec<usize>>()
}
/// Removes a hyperedge based on its index.
/// IndexMap doesn't allow holes by design, see:
/// https://github.com/bluss/indexmap/issues/90#issuecomment-455381877
/// As a consequence, we have two options. Either we use shift_remove
/// and it will result in an expensive regeneration of all the indexes
/// in the map or we use swap_remove and deal with the fact that the last
/// element will be swapped in place of the removed one and will thus get
/// a new index. We use the latter solution for performance reasons.
pub fn remove_hyperedge(
&mut self,
[hyperedge_index, weight_index]: WeightedHyperedgeIndex,
) -> bool {
match self.hyperedges.clone().get_index(hyperedge_index) {
Some((vertices, weights)) => {
// Either we have multiple weights for the index or only one.
// In the first case, we only want to drop the weight.
if weights.len() > 1 {
let mut new_weights = weights.clone();
match self.get_hyperedge_weight([hyperedge_index, weight_index]) {
Some(weight) => {
// Use swap and remove.
// This can potentially alter the indexes but
// only at the hyperedge level.
new_weights.swap_remove(weight);
// Update with the new weights.
self.hyperedges
.insert(vertices.to_owned(), new_weights)
.is_some()
}
None => false,
}
} else {
// In the second case, we need to remove the hyperedge completely.
// First update the vertices accordingly.
for index in vertices.iter() {
if let Some((weight, vertex)) = self.vertices.clone().get_index(*index) {
self.vertices.insert(
*weight,
vertex.iter().fold(
IndexSet::new(),
|mut new_index_set, hyperedge| {
if !are_arrays_equal(hyperedge, &vertices) {
new_index_set.insert(hyperedge.clone());
}
new_index_set
},
),
);
}
}
// Finally remove it.
self.hyperedges.swap_remove(vertices).is_some()
}
}
None => false,
}
}
/// Updates the weight of a hyperedge based on its weighted index.
pub fn update_hyperedge_weight(
&mut self,
[hyperedge_index, weight_index]: WeightedHyperedgeIndex,
weight: HE,
) -> bool {
match self.hyperedges.get_index_mut(hyperedge_index) {
Some((_, weights)) => {
// We can't directly replace the value in the set.
// First, we need to insert the new weight, it will end up
// being at the last position.
if !weights.insert(weight) {
return false;
};
// Then get the value by index of the original weight.
match weights.clone().get_index(weight_index) {
Some(weight) => {
// Last, use swap and remove. It will remove the old weight
// and insert the new one at the index position of the former.
weights.swap_remove(weight)
}
None => false,
}
}
None => false,
}
}
/// Updates the vertices of a hyperedge based on its index.
pub fn update_hyperedge_vertices(
&mut self,
hyperedge_index: usize,
vertices: &[usize],
) -> bool {
match self.hyperedges.clone().get_index(hyperedge_index) {
Some((key, value)) => {
// Keep track of the initial indexes.
let previous_vertices = self.get_hyperedge_vertices(hyperedge_index).unwrap();
// Find the indexes which have been added.
let added = vertices.iter().fold(vec![], |mut acc: Vec<usize>, index| {
if !previous_vertices.iter().any(|x| x == index) {
acc.push(*index)
}
acc
});
// Find the indexes which have been removed.
let removed = previous_vertices
.iter()
.filter_map(|x| {
if !vertices.iter().any(|y| x == y) {
Some(*x)
} else {
None
}
})
.collect::<Vec<usize>>();
// Finally get the unchanged ones.
let unchanged = previous_vertices
.iter()
.filter_map(|x| {
if !removed.iter().any(|y| x == y) {
Some(*x)
} else {
None
}
})
.collect::<Vec<usize>>();
// Process the updated ones.
for index in unchanged.iter() {
if let Some((weight, vertex)) = self.vertices.clone().get_index(*index) {
self.vertices.insert(
*weight,
vertex
.iter()
.fold(IndexSet::new(), |mut new_index_set, hyperedge| {
new_index_set.insert(
// Insert the new ones if it's a match.
if are_arrays_equal(hyperedge, &previous_vertices) {
vertices.to_vec()
} else {
hyperedge.clone()
},
);
new_index_set
}),
);
};
}
// Process the removed ones.
for index in removed.iter() {
if let Some((weight, vertex)) = self.vertices.clone().get_index(*index) {
self.vertices.insert(
*weight,
vertex
.iter()
.fold(IndexSet::new(), |mut new_index_set, hyperedge| {
// Skip the removed ones, i.e. if there's no match.
if !are_arrays_equal(hyperedge, &previous_vertices) {
new_index_set.insert(hyperedge.clone());
}
new_index_set
}),
);
};
}
// Process the added ones.
for index in added.iter() {
if let Some((weight, vertex)) = self.vertices.clone().get_index_mut(*index) {
// Insert the new vertices.
vertex.insert(vertices.to_vec());
self.vertices.insert(*weight, vertex.clone());
};
}
// We need to use the insert and swap_remove trick here too,
// see e.g. the update_vertex_weight method.
self.hyperedges.insert(vertices.to_vec(), value.to_owned());
self.hyperedges.swap_remove(key).is_some()
}
None => false,
}
}
}