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
use crate::{HyperedgeVertices, Hypergraph, SharedTrait, VertexIndex};
use indexmap::IndexSet;
use std::{cmp::Ordering, collections::BinaryHeap, fmt::Debug};
impl<V, HE> Hypergraph<V, HE>
where
V: SharedTrait,
HE: SharedTrait,
{
/// Adds a vertex as a custom weight in the hypergraph.
/// Returns the index of the vertex.
pub fn add_vertex(&mut self, weight: V) -> VertexIndex {
self.vertices
.entry(weight)
.or_insert(IndexSet::with_capacity(0));
// Assume that unwrapping the index can't be none due to previous insertion.
self.vertices.get_index_of(&weight).unwrap()
}
/// Returns the number of vertices in the hypergraph.
pub fn count_vertices(&self) -> usize {
self.vertices.len()
}
/// Gets a list of the shortest path of vertices between two vertices.
/// The implementation of the algorithm is based on
/// <https://doc.rust-lang.org/std/collections/binary_heap/#examples>
pub fn get_dijkstra_connections(
&self,
from: VertexIndex,
to: VertexIndex,
) -> Option<Vec<VertexIndex>> {
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Cursor {
distance: usize,
index: usize,
}
// Use a custom implementation of Ord as we want a min-heap BinaryHeap.
impl Ord for Cursor {
fn cmp(&self, other: &Cursor) -> Ordering {
other
.distance
.cmp(&self.distance)
.then_with(|| self.distance.cmp(&other.distance))
}
}
impl PartialOrd for Cursor {
fn partial_cmp(&self, other: &Cursor) -> Option<Ordering> {
Some(self.cmp(other))
}
}
// We need to initialize a vector of length equal to the number of vertices.
// The default value, as per Dijkstra, must be set to infinity.
// A value of usize::MAX is used.
let mut distances = (0..self.vertices.len())
.map(|_| usize::MAX)
.collect::<Vec<usize>>();
// Create an empty binary heap.
let mut heap = BinaryHeap::new();
// Initialize the first vertex to zero.
distances[from] = 0;
// Push the first cursor to the heap.
heap.push(Cursor {
distance: 0,
index: from,
});
// Keep track of the traversal path.
let mut path = Vec::<usize>::new();
while let Some(Cursor { distance, index }) = heap.pop() {
// End of the traversal.
if index == to {
// We need to inject the index of the target vertex.
path.push(to);
// Remove duplicates generated during the iteration of the algorithm.
path.dedup();
return Some(path);
}
// Skip if a better path has already been found.
if distance > distances[index] {
continue;
}
// For every connected vertex, try to find the lowest distance.
for vertex_index in self.get_vertex_connections(index) {
let next = Cursor {
// We assume a distance of one by default.
distance: distance + 1,
index: vertex_index,
};
// If so, add it to the frontier and continue.
if next.distance < distances[next.index] {
// Update the traversal accordingly.
path.push(index);
// Push it to the heap.
heap.push(next);
// Relaxation, we have now found a better way
distances[vertex_index] = next.distance;
}
}
}
None
}
/// Gets the list of all vertices connected to a given vertex.
pub fn get_vertex_connections(&self, from: VertexIndex) -> Vec<VertexIndex> {
self.get_connections(from, None)
}
/// Gets the hyperedges as vectors of vertices of a vertex from its index.
pub fn get_vertex_hyperedges(&self, index: VertexIndex) -> Option<Vec<HyperedgeVertices>> {
self.vertices
.get_index(index)
.map(|(_, hyperedges)| hyperedges)
.map(|index_set| index_set.iter().cloned().collect())
}
/// Gets the weight of a vertex from its index.
pub fn get_vertex_weight(&self, index: VertexIndex) -> Option<&V> {
self.vertices.get_index(index).map(|(weight, _)| weight)
}
/// Removes a vertex 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_vertex(&mut self, index: VertexIndex) -> bool {
match self.vertices.clone().get_index(index) {
Some((key, hyperedges)) => {
// First, we need to get all the hyperedges' indexes of the
// vertex in order to update them accordingly.
// We preemptively store the eventual index of the swapped
// vertex to avoid extra loops.
let last_index = self.count_vertices() - 1;
let maybe_swapped_index = if last_index == index {
None
} else {
Some(last_index)
};
for hyperedge in hyperedges.iter() {
if let Some(hyperedge_index) = self.hyperedges.get_index_of(hyperedge) {
self.update_hyperedge_vertices(
hyperedge_index,
&hyperedge
.iter()
.filter_map(|current_index| {
if current_index != &index {
// Inject the current index or the swapped one.
match maybe_swapped_index {
Some(swapped_index) => {
Some(if swapped_index == *current_index {
index
} else {
*current_index
})
}
None => Some(*current_index),
}
} else {
None
}
})
.collect::<Vec<usize>>(),
);
}
}
// We also need to update the other hyperedges which are impacted by this change.
if let Some(swapped_index) = maybe_swapped_index {
if let Some(hyperedge_weights) = self.get_vertex_hyperedges(swapped_index) {
for weight in hyperedge_weights.iter() {
if let Some(hyperedge_index) = self.hyperedges.get_index_of(weight) {
self.update_hyperedge_vertices(
hyperedge_index,
&weight
.iter()
.map(|current_index| {
if *current_index == swapped_index {
index
} else {
*current_index
}
})
.collect::<Vec<usize>>(),
);
}
}
}
}
// Now we can safely remove the vertex.
self.vertices.swap_remove(key).is_some()
}
None => false,
}
}
/// Updates the weight of a vertex based on its index.
pub fn update_vertex_weight(&mut self, index: VertexIndex, weight: V) -> bool {
match self.vertices.clone().get_index(index) {
Some((key, value)) => {
// We can't directly replace the value in the map.
// First, we need to insert the new weight, it will end up
// being at the last position.
self.vertices.insert(weight, value.to_owned());
// Then we use swap and remove. It will remove the old weight
// and insert the new one at the index position of the former.
self.vertices.swap_remove(key).is_some()
}
None => false,
}
}
}