图的同构问题

引用知网论文[1]张海龙. 图的同构问题算法研究[D].华中科技大学,2007.中基于矩阵变换的同构算法的步骤。用python编写代码实现。这里只是简单判断图是否同构，不涉及映射关系。代码涉及的行间异或矩阵、行间同或矩阵、同型矩阵等自己去参考这个论文。代码由于只是简单翻译算法步骤，相信读起来很困难，如果先去看看这个论文再来看代码就非常容易看懂了。本人是python初学者，有一些代码写的也是很弱智，请见谅。

'''
    图的同构
    A  B  是否同构
    步骤：
        结点数目相同？ 没意义
        度数相同？
        对B全排列 A与全排列的子集逐一匹配
        匹配则同构 若均不满足 则不同构
        时间复杂度 全排列 n! 吓死人的
        根据百度 从 图的同构问题算法研究_张海龙这一论文中找到一种解法
        时间复杂度O(n^3)空间复杂度O(n^2)
        无向图G=（V,E),G1=(V1,E1)设邻接矩阵为A 同型矩阵为AA，行间同或矩阵为RA，行间异或矩阵为RX
        步骤：
        求出同型矩阵AA
        根据同或异或距离计算方法求出RA，RX
        以G的RX为参照，对RX的每一行，搜索G1的RX的所有行，找到一个匹配，若无匹配则不同构，若匹配则下一步骤
        判断在A,RX中是否存在同样匹配，若存在则调整相应行列，转上一步骤，若不成立则不同构
        所所有行存在行行交换，则继续寻找顶点之间的一一关系。
        以下根据论文中的以此算法做实例3.3图同构的实例应用分析 写出对应的代码
'''
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
def getAA(A): #获取同型矩阵
    RES=np.full((len(A), len(A)), 0)
    for i in range(len(A)):
        for j in range(len(A)):
            if(A[i][j]>0):
                RES[i][j]=1
    return RES
def getRA(A,AA):#获取行间同或矩阵为RA
    RX = np.full((len(A), len(A)), 0)
    for i in range(len(A)):
        for j in range(len(A)):
            if(i==j):
                RX[i][j]=AA[i][j]
            else:
                res=0
                for k in range(len(A)):
                    res += (A[i][k] + A[j][k])*((AA[i][k]^AA[j][k])^1)
                RX[i][j] = res
    return RX
def getRX(A,AA):#获取行间异或矩阵为RA
    RX=np.full((len(A),len(A)),0)
    for i in range(len(A)):
        for j in range(len(A)):
            if (i == j):
                RX[i][j] = AA[i][j]
            else:
                res = 0
                for k in range(len(A)):
                    res += (A[i][k] + A[j][k])*(AA[i][k]^AA[j][k])
                RX[i][j] = res
    return RX
if __name__ == '__main__':
    A=np.array([
        [1,2,1,1,1],
        [2,0,3,1,1],
        [1,3,0,2,2],
        [1,1,2,0,1],
        [1,1,2,1,0]
    ])#测试邻接矩阵01
    AA=getAA(A)#获取同型矩阵
    RA=getRA(A,AA)#获取行间同或矩阵为RA
    RX=getRX(A,AA)#获取行间异或矩阵为RA
    A1=np.array([
        [0,2,1,1,1],
        [2,0,1,2,3],
        [1,1,1,1,2],
        [1,2,1,0,1],
        [1,3,2,1,0]
    ])#测试邻接矩阵02
    AA1=getAA(A1)#获取同型矩阵
    RA1=getRA(A1,AA1)#获取行间同或矩阵为RA
    RX1=getRX(A1,AA1)#获取行间异或矩阵为RA
    flag=0#判断同不同构
    aid=np.full((len(A),len(A)),0)#复制A邻接矩阵 这个只是用来与结果比对 没什么其他作用了
    for i in range(len(A)):
        for j in range(len(A)):
            aid[i][j]=A[i][j]
    for i in range(len(RX1)):
        # print("RX1:",RX1[i])
        # temp=[]#测试用的
        index=-1
        for j in range(len(RX)):
            if(set(RX[j]) == set(RX1[i])):
                # temp=RX[j]#测试用的
                index=j #找到匹配的行了 记录用于下一步骤
                break#找到了就没必要找接下去了 
        if(index!=-1):#也就是找到匹配行
            # print("temp:",temp)#测试用的
            if(set(RA[index]) != set(RA1[i]) or set(A[index]) != set(A1[i])): #还要判断相对应的行间同或矩阵、行间异或矩阵是否也存在同样的匹配
                flag=1
                print("非同构！")
                break
            #若成立才交换 否则直接退出
            print("交换行{1} {0}".format(index + 1, i + 1))
            #以下都是同样的操作 交换对应矩阵的行和列 先交换行 再交换列
            for k in range(len(RX)):
                RX[index][k], RX[i][k] = RX[i][k], RX[index][k]
            for k in range(len(RX)):
                RX[k][index], RX[k][i] = RX[k][i], RX[k][index]
            for k in range(len(RX)):
                RA[index][k],RA[i][k]=RA[i][k],RA[index][k]
            for k in range(len(RX)):
                RA[k][index],RA[k][i]=RA[k][i],RA[k][index]
            for k in range(len(RX)):
                A[index][k],A[i][k]=A[i][k],A[index][k]
            for k in range(len(RX)):
                A[k][index],A[k][i]=A[k][i],A[k][index]
        else:
            print("非同构！")
            break
    if(flag==0):
        print("同构！")
        print("起始矩阵:\n",aid)
        print("变换后的矩阵:\n",A)
        print("与另外一个矩阵A1:\n{0}一致".format(A1))

复杂度就不详细计算了。
时间复杂度:O(n^3),n表示结点个数。
空间复杂度：O(n^2),涉及邻接矩阵。

改算法设计是本人的算法课实验作业，本人实在想不出好的方法，才从知网上找相关思路，翻译成代码完成作业的，别学。