Adjacency Matrix and std::mdspan, C++23

2025-09-08 08:14:00
www.cppstories.com

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_limitsT>::max();
private:
    std::vectorstd::vectorT>> adjacencyMatrix;
    size_t numVertices;

public:
    Graph(size_t vertices) 
        : numVertices(vertices)
        , adjacencyMatrix(vertices, std::vectorT>(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::vectorstd::vectorT>>& getAdjacencyMatrix() const {
        return adjacencyMatrix;
    }
};

template typename T>
void printGraph(const GraphT>& g) {
    std::print("Adjacency Matrix:\n");
    for (const auto& row : g.getAdjacencyMatrix()) {
        for (T weight : row) {
            if (weight == GraphT>::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).
The diagonal elements are set to 0 since a node is always connected to itself.
addEdge ensures bidirectional connections by setting both adjacencyMatrix[u][v] and adjacencyMatrix[v][u].
isConnected checks if a direct edge exists between two vertices.

And here’s the main function:

int main() {
    Graphint> g(5);

    g.addEdge(0, 1, 4);
    g.addEdge(0, 2, 8);
    g.addEdge(1, 2, 2);
    g.addEdge(1, 3, 6);
    g.addEdge(2, 3, 3);
    g.addEdge(3, 4, 5);
    g.addEdge(4, 0, 7);

    printGraph(g);

    std::print("\nIs node 1 connected to node 3? {}\n", g.isConnected(1, 3));
    std::print("Is node 0 connected to node 4? {}\n", g.isConnected(0, 4));
}

Run @Compiler Explorer

Here’s a visual representation of this demo graph:

Improving Efficiency with a Single Vector

Using a vector of vectors is simple but inefficient due to separate memory allocations for each row. Instead, we can use a single contiguous vector to store the matrix elements, which improves cache locality and reduces memory fragmentation.

See the following code:

template typename T>
class Graph {
public:
    static constexpr T INF = std::numeric_limitsT>::max();
private:
    std::vectorT> adjacencyMatrix;
    size_t numVertices;

    size_t index(size_t row, size_t col) const {
        return row * numVertices + col;
    }

public:
    Graph(size_t vertices)
        : numVertices(vertices)
        , adjacencyMatrix(vertices * vertices, INF)
    {
        for (size_t i = 0; i  numVertices; i++)
            adjacencyMatrix[index(i, i)] = 0;
    }
    
    // ...

Above, we have the function index(row, col) that does the proper indexing.

Run @Compiler Explorer

C++23 MD span

C++23 introduces std::mdspan, a lightweight non-owning view over multidimensional data. It allows indexing into a contiguous 1D array as if it were a multidimensional array without needing explicit indexing functions.

Here’s a basic example of how to use this view type:

#include 
#include  // 
#include 

bool isSymmetric(std::mdspanint, std::dextentssize_t, 2>> matrix) {
    const auto rows = matrix.extent(0);
    const auto cols = matrix.extent(1);

    if (rows != cols) return false;

    for (size_t i = 0uz; i  rows; ++i) {
        for (size_t j = i + 1; j  cols; ++j) {
            if (matrix[i, j] != matrix[j, i]) 
                return false;
        }
    }
    return true;
}

int main() {
    std::vectorint> matrix_data = {1, 2, 3, 2, 4, 5, 3, 5, 6};
    auto matrix = std::mdspan(matrix_data.data(), 3, 3);

    std::cout  isSymmetric(matrix);
}

See @Compiler Explorer

The key thing is that mdspan is just one object that you pass to a function, and it has all the information and also features to access multidimensional data. Notice the operator [] with two arguments: matrix[i, j].

I must say that the type std::mdspan> matrix is probably not the nicest to write and spell out, but it wraps all the information in a pretty flexible way.

(In C++26, have std::dims helper type that can even make things shorter for dynamic mdspan extents).

Adjacency Matrix with mdspan

Thanks to std::mdspan, we can simplify the code to calculate the index. The operator [] can now handle multiple arguments, so it’s easy to index into a multidimensional array:

#include 
#include 
#include 
#include 

template typename T>
class Graph {
public:
    static constexpr T INF = std::numeric_limitsT>::max();

private:
    std::vectorT> adjacencyMatrix;
    std::mdspanT, std::dextentssize_t, 2>> matrixView;
    size_t numVertices;

public:
    Graph(size_t vertices) 
        : numVertices(vertices)
        , adjacencyMatrix(vertices * vertices, INF)
        , matrixView(adjacencyMatrix.data(), vertices, vertices) 
    {
        for (size_t i = 0; i  numVertices; i++)
            matrixView[i, i] = 0;
    }
	
	// copy ctor / move op / assignment...

    void addEdge(size_t u, size_t v, T weight) {
        if (u  numVertices && v  numVertices && u != v) {
            matrixView[u, v] = weight;
            matrixView[v, u] = weight;
        }
    }

    bool isConnected(size_t u, size_t v) const {
        return (u  numVertices 
		     && v  numVertices 
			 && matrixView[u, v] != INF);
    }

    auto getAdjacencyMatrix() const {
        return matrixView;
    }

    size_t getNumVertices() const {
        return numVertices;
    }
};

template typename T>
void printGraph(const GraphT>& g) {
    size_t n = g.getNumVertices();
    auto matrix = g.getAdjacencyMatrix();

    std::print("Adjacency Matrix:\n");
    for (size_t i = 0; i  n; i++) {
        for (size_t j = 0; j  n; j++) {
            T weight = matrix[i, j];
            if (weight == GraphT>::INF)
                std::print("   ∞ ");
            else
                std::print(" {:3} ", weight);
        }
        std::println();
    }
}

Run @Compiler Explorer

Const Correctness

In the previous example, I made a mistake with the member function/getter

auto getAdjacencyMatrix() const {
    return matrixView;
}

While the auto as the return type is handy and shortened the code, the issue is that now we can write

auto matrix = g.getAdjacencyMatrix();
matrix[0, 1] = 1234;

In other words, we return a non-const view of the data, allowing modification of its elements.

It’s usually not the best approach for getters, and to preserve cost correctness, we should manually specify the return type.

std::mdspanconst T, std::dims2>> getAdjacencyMatrix() const {
    return matrixView;
}

Now, you can access elements, but you cannot modify them.

Rule of Five

Thanks to a valuable comment at Reddit, I’ve noticed also another issue:

Rule of Five…

Since we introduced a view type as the member of the class, we have to support it through copy/move/assignment operations. Otherwise when you copy a graph object the span will point to a wrong data! See the updated version of the code in the next section.

Improvements

The code works, but it’s definitely not perfect. Here are some updates we should make:

requires std::is_arithmetic_v – the graph class is a template, but we should at least narrow down the “weight” type that we support.
Rule of Zero – checked; see above.
explicit ctor – to prevent unwanted conversions
noexcept – at least in some basic functions
nodiscard – to indicate that a return value should be used, not just thrown away
error handling through exceptions

Here’s the updated version:

#include 
#include 
#include 
#include 

template typename T>
requires std::is_arithmetic_vT>
class Graph {
public:
    static constexpr T INF = std::numeric_limitsT>::max();

private:
    std::vectorT> adjacencyMatrix;
    std::mdspanT, std::dims2>> matrixView;
    size_t numVertices;

public:
    explicit Graph(size_t vertices) 
        : numVertices(vertices)
        , adjacencyMatrix(vertices * vertices, INF)
        , matrixView(adjacencyMatrix.data(), vertices, vertices) 
    {
        for (size_t i = 0; i  numVertices; i++)
            matrixView[i, i] = 0;
    }

	// copy ctor, move ctor, assignment...

    void addEdge(size_t u, size_t v, T weight) {
        if (u >= numVertices || v >= numVertices)  
            throw std::out_of_range("Vertex index out of bounds");  
        if (u == v)  
            throw std::invalid_argument("Self-loops are not allowed");

        matrixView[u, v] = weight;
        matrixView[v, u] = weight;
    }

    [[nodiscard]] bool isConnected(size_t u, size_t v) const{
        if (u >= numVertices || v >= numVertices)  
            throw std::out_of_range("Vertex index out of bounds"); 
        return matrixView[u, v] != INF;
    }

    [[nodiscard]] std::mdspanconst T, std::dims2>> getAdjacencyMatrix() const {
        return matrixView;
    }

    [[nodiscard]] size_t getNumVertices() const noexcept {
        return numVertices;
    }
};

template typename T>
void printGraph(const GraphT>& g) {
    size_t n = g.getNumVertices();
    auto matrix = g.getAdjacencyMatrix();

    std::print("Adjacency Matrix:\n");
    for (size_t i = 0; i  n; i++) {
        for (size_t j = 0; j  n; j++) {
            T weight = matrix[i, j];
            if (weight == GraphT>::INF)
                std::print("   ∞ ");
            else
                std::print(" {:3} ", weight);
        }
        std::println();
    }
}

Run @Compiler Explorer

Implementation notes

The code shown in examples works just great in Clang 18.+! In Compiler Explorer use -stdlib=libc++ so that it uses the proper Standard Library implementation.

Summary

In this article, we discuss a simple and naive implementation of an adjacency graph and enhance it with the latest features from C++23. The use of mdspan facilitates the creation of a proper 2D view over a contiguous sequence of data.

The final code is a bit better, but of course, I’m happy to see your suggestions and improvements we can make here.

Back to you

Have you played with mdspan?
What do you use to work with multidimensional data?

Share your comments below

Source Link

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!

Unlock unlimited streaming with a free Amazon Prime trial!
Sign up today!

Help Power Techcratic’s Future – Scan To Support

If Techcratic’s content and insights have helped you, consider giving back by supporting the platform with crypto. Every contribution makes a difference, whether it’s for high-quality content, server maintenance, or future updates. Techcratic is constantly evolving, and your support helps drive that progress.

As a solo operator who wears all the hats, creating content, managing the tech, and running the site, your support allows me to stay focused on delivering valuable resources. Your support keeps everything running smoothly and enables me to continue creating the content you love. I’m deeply grateful for your support, it truly means the world to me! Thank you!

BITCOIN

Bitcoin Logo