Background
The island detection algorithm identifies small weakly connected components (WCCs) and flags their edges for removal. The downstream cleanup in compute_vertex_remapping and clean_omf_edge_list then removes the vertices those edges touch.
This works correctly only because we use weak connectivity. In a WCC, every vertex belonging to a flagged component is exclusively reachable from other flagged edges, there is no vertex that is simultaneously part of an island component and a non-island component. That invariant is what allows vertices to be unconditionally removed when all their incident edges in any one component are flagged.
The constraint
If the algorithm were changed to use strong connectivity (SCCs) or when we implement component per-edge-list (#116), this invariant breaks. An SCC can share boundary vertices with the rest of the graph (a vertex may be the source or destination of both a flagged SCC edge and a non-flagged edge in the main graph). Removing that vertex would corrupt surviving edges.
In strong connectivity mode, vertex removal would need to be conditional: a vertex should only be removed if all of its incident edges (across all edge lists, in both directions) are flagged for removal.
What needs to change if we move to strong connectivity
compute_vertex_remapping currently marks a vertex as removed if it appears as src or dst of any island edge. It would need to change to: mark a vertex for removal only if every edge touching it is also flagged.
clean_omf_edge_list and the vertex_lookup update in omf_graph.rs are correct as-is, since they already respect the remapping vector, they just depend on the remapping being computed correctly.
Background
The island detection algorithm identifies small weakly connected components (WCCs) and flags their edges for removal. The downstream cleanup in
compute_vertex_remappingandclean_omf_edge_listthen removes the vertices those edges touch.This works correctly only because we use weak connectivity. In a WCC, every vertex belonging to a flagged component is exclusively reachable from other flagged edges, there is no vertex that is simultaneously part of an island component and a non-island component. That invariant is what allows vertices to be unconditionally removed when all their incident edges in any one component are flagged.
The constraint
If the algorithm were changed to use strong connectivity (SCCs) or when we implement component per-edge-list (#116), this invariant breaks. An SCC can share boundary vertices with the rest of the graph (a vertex may be the source or destination of both a flagged SCC edge and a non-flagged edge in the main graph). Removing that vertex would corrupt surviving edges.
In strong connectivity mode, vertex removal would need to be conditional: a vertex should only be removed if all of its incident edges (across all edge lists, in both directions) are flagged for removal.
What needs to change if we move to strong connectivity
compute_vertex_remappingcurrently marks a vertex as removed if it appears as src or dst of any island edge. It would need to change to: mark a vertex for removal only if every edge touching it is also flagged.clean_omf_edge_listand thevertex_lookupupdate inomf_graph.rsare correct as-is, since they already respect the remapping vector, they just depend on the remapping being computed correctly.