Adjacency Matrix and std:mdspan, C++23

Summary

In graph theory, an adjacency matrix is a square matrix used to represent a finite (and usually dense) graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not, and in weighted graphs, they store the edge weights. In many beginner-level tutorials, adjacency matrices are implemented using vector of vectors (nested dynamic arrays), but this approach has inefficiencies due to multiple memory allocations. C++23 introduces std::mdspan, which provides a more efficient way to handle multidimensional data structures without the overhead of nested containers. In this blog post, we’ll explore various implementations of an adjacency matrix, starting with a basic approach and progressively improving it using std::mdspan. Starting slow Let’s start with a straightforward implementation using a vector of vectors to represent the adjacency matrix. #include <iostream> #include <vector> #include <limits> #include <print> template <typename T> class Graph { public: static constexpr T INF = std::numeric_limits<T>::max(); private: std::vector<std::vector<T>> adjacencyMatrix; size_t numVertices; public: Graph(size_t vertices) : numVertices(vertices) , adjacencyMatrix(vertices, std::vector<T>(vertices, INF)) { for (size_t i = 0; i < numVertices; i++) adjacencyMatrix[i][i] = 0; } void addEdge(size_t u, size_t v, T weight) { if (u < numVertices && v < numVertices && u != v) { adjacencyMatrix[u][v] = weight; adjacencyMatrix[v][u] = weight; } } bool isConnected(size_t u, size_t v) const { return (u < numVertices && v < numVertices && adjacencyMatrix[u][v] != INF); } const std::vector<std::vector<T>>& getAdjacencyMatrix() const { return adjacencyMatrix; } }; template <typename T> void printGraph(const Graph<T>& g) { std::print("Adjacency Matrix:\n"); for (const auto& row : g.getAdjacencyMatrix()) { for (T weight : row) { if (weight == Graph<T>::INF) std::print(" ∞ "); else std::print(" {:3} ", weight); } std::println(); } } The class represents an undirected wei...