Adjacency Matrix and std:mdspan, C++23

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 #include #include #include 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:

" ); 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 weighted graph.

The adjacency matrix is initialized with INF (representing no direct connection between nodes).

(representing no direct connection between nodes). The diagonal elements are set to 0 since a node is always connected to itself.

... continue reading