A small function for rendering a connectivity matrix into a normal form.

normalize_cm.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import numpy as np
from itertools import permutations


def normalize_cm(connectivity_matrix):
    """Render a square connectivity matrix into a normal form.

    Two connectivity matrices will have the same normal form if they are
    equivalent up to a permutation of the ordering of their nodes.
    """
    # Cast to a numpy array
    connectivity_matrix = np.array(connectivity_matrix)
    # Get the number of nodes (length of one side of the square matrix)
    num_nodes = connectivity_matrix.shape[0]
    # Get the permutations of the node indices
    perms = tuple(permutations(range(num_nodes)))

    # This will hold all the permuted connectivity matrices
    cm_perms = []
    for perm in perms:
        # Initialize a connectivity matrix of the proper shape
        cm = np.zeros((num_nodes, num_nodes)).astype(int)
        # The i,jth element of the permuted connectivity matrix is the
        # p(i),p(j)th element, where p(i) and p(j) are the images of i and j
        # under the permutation
        for i in range(num_nodes):
            for j in range(num_nodes):
                cm[i][j] = connectivity_matrix[perm[i]][perm[j]]
        cm_perms.append(cm.tolist())
    # In-place lexicographical sort of all the permuted connectivity matrices
    cm_perms.sort()
    # Return the lexicographically least one (the normal form)
    return cm_perms[0]