交换邻接矩阵的行列，标准化邻接矩阵

背景

肝了几天终于把这个算法肝出来了，其实不太高明，而且算法时间复杂度高，但是目前想不到其他办法了，最后出来的代码很简单，但是之前尝试了很多种可能时间复杂度底的方法都行不通，不能将邻接矩阵标准化，最后只得放弃，用这个简单但是算起来很慢的算法。主要是之前做的那些失败的尝试花费了很多时间。

正文

需求

做一个图的项目，想要从邻接矩阵这里获得位置信息，但是可能相同的图结构会给不同的位置编码，因此了解到同构图的概念，去学习了一下，但是主要的提出的计算同构图的方法都是不是基于邻接矩阵的，如果我要直接用他们的算法的话还需要处理我的邻接矩阵，鉴于本人水平有限，所以还是打算从邻接矩阵入手。参考的文献在文件夹：E:\桌面大包\计算机\Graphormer学习 中。

算法讲解

很简单，就是先按度从小到大排列好，然后穷举所有的度相同的排列，这些得到的矩阵做一个排序，选第一个就认为是原邻接矩阵的标准化。
这里需要提到的是有学者发论文，提出过一种标准化邻接矩阵的方法，但是我复现了他的思路并不能标准化邻接矩阵。

代码实现

import torch
import random
import copy
import math

import torch
import numpy as np
import scipy.sparse as sp

from collections import defaultdict
from ast import literal_eval

from itertools import combinations, permutations
import itertools

from functools import reduce

def norm(a):
    #     print('a:\n',a)
    order = a.sum(-1).sort().indices
    b = a[order]
    c = b[:,order]

    #     print('c:\n',c)

    list1 = list(c.sum(-1).numpy())
    set1 = list(set(list1))

    degree_id_dict = {i: [] for i in set1}

    for target in set1:
        for index, nums in enumerate(list1):
            if nums == target:
                degree_id_dict[target].append(index)
    #         degree_id_dict[target] = torch.tensor(degree_id_dict[target])
    degree_id_dict_ = copy.deepcopy(degree_id_dict)

    iterings = [list(permutations(degree_id_dict[i], len(degree_id_dict[i]))) for i in degree_id_dict]  # 打乱index的顺序，所有排列组合做成迭代器

    all_order_lists = fn(iterings)

    c2_list = []
    for all_order_list in all_order_lists:
    #     print(all_order_list)
        c1 = c[list(all_order_list)]
        c2 = c1[:,list(all_order_list)]
    #     print(c)
        c2_list.append(c2.numpy().tolist())


    c2_list_sorted = sorted(c2_list)
    c_min = torch.tensor(c2_list_sorted[0])
    
    return c_min
    
fn = lambda x, code=',': reduce(lambda x, y: [i+j for i in x for j in y], x)
# 直接调用fn(lists, code)

text:

# 创建邻接矩阵
def make_AM(size = 12, numof1 = 30):
    a = torch.zeros(size,size).int()

    for m in range(numof1):
        i,j = random.sample(range(size),2)
    #     x = random.randint(0,9)
        a[i,j] = a[j,i]=1
    return a

# 交换行列，制作同构图
def make_homo_G(a):
    assert a.shape[0] == a.shape[1]
    
    size = a.shape[0]
    order = random.sample(range(size),size)
    b = a[order]
    c = b[:,order]
    return c

for i in range(128):
    homo1 = make_AM(size = 9, numof1 = 20)
    homo2 = make_homo_G(homo1)
#     print(homo1.numpy().tolist())
#     print(homo2.numpy().tolist())
#    print(homo1.sum(-1))
#    print(homo2.sum(-1))
    o1 = (norm(homo1))
    o2 = (norm(homo2))
#     print(o1)
#     print(o2)
    print((o1 != o2).sum())
#     print('=====================================')