python - 頂点の無向グラフの並べ替え

Question

隣接行列と頂点の新しい順序が与えられた場合、Pythonでグラフをどのように並べ替えることができますか？このタスク用のライブラリはありますか？

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.)