Verify that the SCCs form an exact partition of the graph's alive vertices. After [`compute_order`], every non-DUMMY vertex (`VertexId(1)..VertexId(vertex_count)`) must appear in exactly one SCC exactly once. A violation means the ordering stage has lost or duplicated a vertex, which downstream corrupts the emitted file (duplicated tail, relocated line) while reporting success. This is the struct
(&self, vertex_count: usize)
| 340 | /// release builds can call it explicitly; [`compute_order`] runs it under |
| 341 | /// `debug_assert!`. |
| 342 | pub fn validate_partition(&self, vertex_count: usize) -> Result<(), OrderInvariantError> { |
| 343 | // Index 0 is the DUMMY sentinel and must never appear in an SCC. |
| 344 | // Alive vertices are 1..vertex_count. |
| 345 | let mut seen = vec![false; vertex_count]; |
| 346 | for scc in &self.sccs { |
| 347 | for &vid in scc { |
| 348 | let idx = vid.index(); |
| 349 | if idx == 0 { |
| 350 | return Err(OrderInvariantError::DummyInScc); |
| 351 | } |
| 352 | if idx >= vertex_count { |
| 353 | return Err(OrderInvariantError::OutOfRange { |
| 354 | vertex: vid, |
| 355 | vertex_count, |
| 356 | }); |
| 357 | } |
| 358 | if seen[idx] { |
| 359 | return Err(OrderInvariantError::Duplicate { vertex: vid }); |
| 360 | } |
| 361 | seen[idx] = true; |
| 362 | } |
| 363 | } |
| 364 | // Every alive vertex must have been covered. |
| 365 | for (idx, covered) in seen.iter().enumerate().skip(1) { |
| 366 | if !*covered { |
| 367 | return Err(OrderInvariantError::Missing { |
| 368 | vertex: VertexId::new(idx), |
| 369 | }); |
| 370 | } |
| 371 | } |
| 372 | Ok(()) |
| 373 | } |
| 374 | } |
| 375 | |
| 376 | /// A violation of the SCC-partition invariant detected by |