How to generate every possible Adjacency Matrix for graphs with N nodes?

Question

I'm currently working on a small project for a course related to Graph Theory. The current task I've ran into trouble with is generating every non-isomorphic graph with N nodes (where N <= 4).

More specifically, I'm not sure how to achieve a certain 'step' of my algorithm. The idea is to generate every possible graph with N nodes or in other words, to generate every possible adjacency matrix of the order N, send each of them over to a function to check for isomorphism, and print them out if they are isomorphic.

The whole task involves a few functions and steps, though in this question, I will focus on the one which is giving me problems - generating every possible combination of adjacency matrices.

What I was able to do so far is generating all matrices with one edge, or in other words, with only one "1". Here is my function (in C++):

void generateAdjacencyMatrices(int N) {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                adjacencyMatrix[i][j] = 1;
                //logic for isomorphism
                //logic for printing the graph
            }
            adjacencyMatrix[i][j] = 0;
        }        
    }
}

What this generates are matrices like these (on the example of N = 3):

0 1 0      0 0 1     0 0 0     0 0 0
0 0 0      0 0 0     1 0 0     0 0 1
0 0 0      0 0 0     0 0 0     0 0 0

and so on.

What I need to do is generate every single matrix with an arbitrary number of edges (arbitrary number of "1"s in the matrix) which I'm not sure how to do in a normal amount of time. Any tips would be much appreciated.

Answer 1

This code will generate all 2^(N*N) adjacency matrices for size N:

#include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N);
    for (unsigned int counter = 0; counter < max; ++counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N && c != 0; i++) {
            for (int j = 0; j < N && c != 0; j++) {
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto &row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << '\n';
        }
        std::cout << '\n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}

It iterates over the numbers from 0 to N-1 and uses the binary representation of each number to fill the values of the matrix.

With a simple change you can keep the zero diagonal and generate 2^(N*N - N) adjacency matrices:

#include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N - N);
    for (unsigned int counter = 0; counter < max; ++counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N && c != 0; i++) {
            for (int j = 0; j < N && c != 0; j++) {
                if (i == j) continue;
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto &row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << '\n';
        }
        std::cout << '\n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}

You can start with counter = 1 to skip the zero matrix:

#include <iostream>
#include <vector>

unsigned int pow(unsigned int b, unsigned int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) {
        return pow(b, e/2) * pow(b, e/2);
    }
    return b * pow(b, e - 1);
}

void generateAdjacencyMatrices(int N) {
    const auto max = pow(2, N*N - N);
    for (unsigned int counter = 1; counter < max; ++counter) {
        auto c = counter;
        std::vector<std::vector<int>> adjacencyMatrix(N, std::vector<int>(N));
        for (int i = 0; i < N && c != 0; i++) {
            for (int j = 0; j < N && c != 0; j++) {
                if (i == j) continue;
                adjacencyMatrix[i][j] = c % 2;
                c /= 2; 
            }        
        }
        for (const auto &row : adjacencyMatrix) {
            for (const auto value : row) {
                std::cout << value << ' ';
            }
            std::cout << '\n';
        }
        std::cout << '\n';
    }
}

int main() {
    generateAdjacencyMatrices(3);
}