Undirected Graph Reordering the Vertices

Question

Given an adjacency matrix and a new ordering of vertices how can we permute the graph in python? Is there any library for this task?

Answer 1

You can just construct the new adjacency matrix by hand. old is the old adjacency matrix, and perm is a vector that stores the old name for each new vertex, that is, if vertex j is moved to vertex i then perm[i] == j.

import numpy as np

def rearrange(old, perm):
    n = old.shape[0]
    new = np.zeros_like(old)

    for x in xrange(n):
        for y in xrange(x+1): # only need to traverse half the matrix
            # the matrix is symmetric (because of undirectedness)
            new[y, x] = new[x, y] = old[perm[x], perm[y]]
    return new

(Note that I'm assuming you're are storing your adjacency matrix as a dense matrix in an n×n numpy array. Also, for Python 3.x, xrange should be range.)