umons-dept-comp-sci / PhoegRustGraph

Graph library specialized for small graphs.
3 stars 2 forks source link

`algorithm::isolate` should suffer from invalidated iterator, `GraphIter::neighbors` type seems wrong. #9

Closed antegallya closed 2 years ago

antegallya commented 2 years ago

Function algorithm::isolate removes edges while iterating over the neighbors of u. The neighbors iterator should, in theory, be invalidated since removing an edge with u would modify the neighbors of u. It seems to work though because the underlying Nauty set doesn't change its size and pointers are not invalidated after DELELEMENT.

We should not even be allowed to write this code because Rust should see it. However, since GraphIter::neighbors doesn't take a lifetime specification, and the GraphNauty::neighbors implementation uses unsafe, this bug slipped through the cracks.

This code is allowed and is actually completely wrong:

for v in g.neighbors(1) {
    g.remove_vertex(v);
}