Something that I've not frequently needed to do, but have needed to do enough that I feel I should ask others for suggestions is the following: I need to perform operations on a contiguous set of indices, however I only have a set of disjoint unordered indices. Let's take the example of a graph, which is the specific example I'm facing at the moment. I need to perform unionfind on the edges of a graph, but not the entire graph. Therefore I can't simply create a disjoint group from every vertex, as I am only performing union on a limited set of edges within the graph. Therefore I need to get the count of unique vertex indices, and put them in their own collection, using the new index in the new type.
fn example() {
let edges = [(1, 8), (200, 10), (5, 34), (8, 10), (1, 8)];
// We don't know how many unique vertices we have.
let mut vec = Vec::with_capacity(edges.len() * 2);
for e in edges {
vec.push(e.0);
vec.push(e.1);
}
vec.sort_unstable();
vec = vec.into_iter().dedup().collect();
// Optional:
vec.shrink_to_fit();
// Now I can use the length of `vec` as my vertex count, and the vector indices (not the
// elements) in my unionfind. Afterwards I map the element indices back into their original
// vertex index.
}
Another example is, once again a graph, where lets say I want to construct an adjacency matrix for that same set of edges. Let's take the first edge, (1, 8), and insert it into a lower triangle matrix. I have now defined vertex index 1 as as the row/column 1, and vertex index 8 as row/column 0. In this example I can simply push 8 then 1 to a vector, and for the following vertex indices, iterate to see if a row/column is already made for a vertex to get the i, j indices. Which I could have done in the unionfind example also.
I'm not as much asking for suggestions for the approaches above, but asking if there are any crates, datastructures, abstractions or suggestions for simplifying the packing of sets of (lets say random) indices into a dense set where needed. Does anyone have any advice?