Table of Contents

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 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() {
    Graph<int> 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_limits<T>::max();
private:
    std::vector<T> 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 <vector>
#include <mdspan> // << new header!
#include <iostream>

bool isSymmetric(std::mdspan<int, std::dextents<size_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::vector<int> 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<int, std::dextents<size_t, 2>> 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 <vector>
#include <limits>
#include <print>
#include <mdspan>

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

private:
    std::vector<T> adjacencyMatrix;
    std::mdspan<T, std::dextents<size_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 Graph<T>& 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 == Graph<T>::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::mdspan<const T, std::dims<2>> 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<T> - 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 <vector>
#include <limits>
#include <print>
#include <mdspan>

template <typename T>
requires std::is_arithmetic_v<T>
class Graph {
public:
    static constexpr T INF = std::numeric_limits<T>::max();

private:
    std::vector<T> adjacencyMatrix;
    std::mdspan<T, std::dims<2>> 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::mdspan<const T, std::dims<2>> getAdjacencyMatrix() const {
        return matrixView;
    }

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

template <typename T>
void printGraph(const Graph<T>& 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 == Graph<T>::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