python - 无向图重新排序顶点

Question

给定一个邻接矩阵和一个新的顶点排序，我们如何在 python 中置换图？这个任务有图书馆吗？

Answer 1

您可以手动构建新的邻接矩阵。old是旧的邻接矩阵，并且perm是一个向量，用于存储每个新顶点的旧名称，即如果顶点j移动到顶点，i则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

（请注意，我假设您将邻接矩阵作为密集矩阵存储在n× nnumpy 数组中。另外，对于 Python 3.x，xrange应该是range.）