Adjacency Matrix and std:mdspan, C++23
2 days ago
- #C++23
- #Graph Theory
- #Data Structures
- An adjacency matrix is a square matrix used to represent dense graphs, indicating vertex adjacency and storing edge weights in weighted graphs.
- Traditional implementations use vector of vectors, which is inefficient due to multiple memory allocations.
- C++23 introduces std::mdspan for efficient handling of multidimensional data without nested containers.
- Initial implementation uses a vector of vectors, initializing with INF (no connection) and 0 on the diagonal (self-connection).
- Improvement: Using a single contiguous vector for better cache locality and reduced memory fragmentation.
- C++23's std::mdspan provides a lightweight non-owning view for multidimensional data, simplifying indexing.
- Implementation with std::mdspan allows direct multidimensional indexing without explicit functions.
- Const correctness is important; getters should return const views to prevent unintended modifications.
- Rule of Five must be considered when using view types as class members to ensure proper copy/move operations.
- Additional improvements include type constraints (std::is_arithmetic_v<T>), explicit constructors, noexcept, and nodiscard attributes.
- Error handling via exceptions for out-of-bounds and invalid operations.
- Final implementation demonstrates efficient adjacency matrix handling with C++23 features.