A potential optimization for #1103.
Currently, symmetric edge pairs are identified using a hash-based approach.
Alternatively, we could sort the edges so that symmetric pairs become adjacent in the array, then detect pairs with a single linear scan. This would avoid the memory overhead of a hash table and may be faster in practice due to improved memory locality and cache-friendly access patterns.
This trades O(n) expected time for O(n log n) worst-case time, but simplifies the implementation and reduces auxiliary data structures. For large inputs, the constant factors may be favorable.
A first implementation might use qsort or a custom comparison sort (to avoid function pointer overhead). For very large edge sets, we might also try a radix sort.
A potential optimization for #1103.
Currently, symmetric edge pairs are identified using a hash-based approach.
Alternatively, we could sort the edges so that symmetric pairs become adjacent in the array, then detect pairs with a single linear scan. This would avoid the memory overhead of a hash table and may be faster in practice due to improved memory locality and cache-friendly access patterns.
This trades O(n) expected time for O(n log n) worst-case time, but simplifies the implementation and reduces auxiliary data structures. For large inputs, the constant factors may be favorable.
A first implementation might use
qsortor a custom comparison sort (to avoid function pointer overhead). For very large edge sets, we might also try a radix sort.