Index stability

[glyn]

/// 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 {

@yamafaktory Did you consider managing your own indices internally and mapping these to indices in the IndexMap? Then the indices exposed to users could be kept invariant across remove_vertex. Also, in terms of usability, having hypergraph allocate indices might be more usable than requiring the user to keep track of which indices are in use.

[yamafaktory]

@glyn thanks for the feedback! That's a very good call. When I implemented that part I was bothered by this behavior (https://docs.rs/indexmap/1.7.0/src/indexmap/map/core.rs.html#577). At some point, I thought about returning a mapping of the mutated indexes. This is definitely not optimal - as you've rightfully highlighted it - since it's just shifting the problem. I'm wondering if the exposed invariants should be kept as simple indices or perhaps as UUIDs.

[glyn]

UUIDs may be overkill and could impact performance (the overhead of generating a random number). A numeric index could eventually wrap, but you could use a u64 to make wrapping unlikely/infeasible.

Is there a natural choice of pointer which could act as an O(1) index? (I haven't looked at the code enough to know.) Perhaps the ownership complexity of this wouldn't be worth it.

Another option would be to use a custom type which could be implemented in terms of a numeric index, a UUID, etc., but I guess it would have to have a known size at compile time so it could be returned.

[yamafaktory]

@glyn for the record, I've created a PR (#17) which ended up being a huge refactoring. This will tackle the current index stability issue.

[yamafaktory]

A new version has been released https://crates.io/crates/hypergraph/1.0.0.