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
use rayon::prelude::*;
use crate::{
HyperedgeIndex,
HyperedgeKey,
HyperedgeTrait,
Hypergraph,
VertexIndex,
VertexTrait,
core::utils::are_slices_equal,
errors::HypergraphError,
};
impl<V, HE> Hypergraph<V, HE>
where
V: VertexTrait,
HE: HyperedgeTrait,
{
/// Updates the vertices of a hyperedge by index.
pub fn update_hyperedge_vertices(
&mut self,
hyperedge_index: HyperedgeIndex,
vertices: Vec<VertexIndex>,
) -> Result<(), HypergraphError<V, HE>> {
// If the provided vertices are empty, skip the update.
if vertices.is_empty() {
return Err(HypergraphError::HyperedgeUpdateNoVertices(hyperedge_index));
}
let internal_index = self.get_internal_hyperedge(hyperedge_index)?;
let internal_vertices = self.get_internal_vertices(vertices)?;
let HyperedgeKey {
vertices: previous_vertices,
weight,
} = self.hyperedges.get_index(internal_index).cloned().ok_or(
HypergraphError::InternalHyperedgeIndexNotFound(internal_index),
)?;
// If the new vertices are the same as the old ones, skip the update.
if are_slices_equal(&internal_vertices, &previous_vertices) {
return Err(HypergraphError::HyperedgeVerticesUnchanged(hyperedge_index));
}
// Find the vertices which have been added.
let mut added = internal_vertices
.par_iter()
.fold_with(vec![], |mut acc: Vec<usize>, index| {
if !previous_vertices
.par_iter()
.any(|current_index| current_index == index)
{
acc.push(*index);
}
acc
})
.flatten()
.collect::<Vec<usize>>();
added.par_sort_unstable();
added.dedup();
// Find the vertices which have been removed.
let mut removed = previous_vertices
.into_par_iter()
.filter_map(|index| {
if internal_vertices
.par_iter()
.any(|current_index| index == *current_index)
{
None
} else {
Some(index)
}
})
.collect::<Vec<usize>>();
removed.par_sort_unstable();
removed.dedup();
// Update the added vertices.
for index in added {
match self.vertices.get_index_mut(index) {
Some((_, index_set)) => {
index_set.insert(internal_index);
}
None => return Err(HypergraphError::InternalVertexIndexNotFound(index)),
}
}
// Update the removed vertices.
for index in removed {
match self.vertices.get_index_mut(index) {
Some((_, index_set)) => {
// This has an impact on the internal indexing for the set.
// However since this is not exposed to the user - i.e. no
// mapping is involved - we can safely perform the operation.
index_set.swap_remove_index(internal_index);
}
None => return Err(HypergraphError::InternalVertexIndexNotFound(index)),
}
}
// Insert the new entry.
// Since we are not altering the weight, we can safely perform the
// operation without checking its output.
self.hyperedges.insert(HyperedgeKey {
vertices: internal_vertices,
weight,
});
// Swap and remove by index.
// Since we know that the internal index is correct, we can safely
// perform the operation without checking its output.
self.hyperedges.swap_remove_index(internal_index);
// Return a unit.
Ok(())
}
}