# GraphISO_sr.py¶

## Description¶

This example script returns the GI certificates, and also checks isomorphism of various graphs in the strongly regular $$(25,12,5,6)$$ family.

1. Firstly, two permutations of graph 1 in the SR family are formed by reordering the rows and columns in such a way as to preserve the symmetry of the graph. For example,

\begin{align} &\text{i)}\text{ swap rows }2\text{ & }3: \left[\begin{matrix} a & b & c\\ b & d & e\\ c & e & f \end{matrix}\right] \Rightarrow \left[\begin{matrix} b & d & e\\ a & b & c\\ c & e & f \end{matrix}\right]\\[12pt] &\text{ii)} \text{ swap columns }2\text{ & }3: \left[\begin{matrix} b & d & e\\ a & b & c\\ c & e & f \end{matrix}\right] \Rightarrow \left[\begin{matrix} d & b & e\\ b & a & c\\ e & c & f \end{matrix}\right] \end{align}

– for adjacency matrices, this is process is equivalent to ‘swapping’ the label of nodes 1 and 2, and thus is isomorphic to the original adjacency matrix.

The GI certificates of both permutations of graph 1 are then calculated and displayed side by side. For each graph, these consist of a column of probabilities resulting from performing an interacting two particle quantum walk over all possible initial bosonic edge states; i.e.

$|\psi(0)\rangle = \frac{1}{\sqrt{2}}\left(|j\rangle\otimes|j\rangle + |k\rangle\otimes|k\rangle \right)~~~~\forall j,k\in\{0,1,\dots,N-1\},$

coupled with the frequency with which they appear. The quantum walk is performed for time $$t=2N$$, allowing the walk time to propagate to all nodes. Therefore, as the graphs are isomorphic, the GI certificates should be identical.

Finally, pyCTQW.MPI.GraphISO.isomorphicQ() is used to verify that the two graphs are in fact isomorphic.

2. The second section of the program uses pyCTQW.MPI.GraphISO.isomorphicQ() to check whether graphs 1 and 11 of the SR family are isomorphic. They are not, and this is correctly returned by the program.

## Output¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 \$ mpirun -np 2 GraphISO_sr.py The GI certificates of two permutations of SR(25,12,5,6) graph 1: [ 1.14200170e-01 1.88140000e+04] [ 1.14200170e-01 1.88140000e+04] [ 1.53741042e-01 1.54380000e+04] [ 1.53741042e-01 1.54380000e+04] [ 1.76558859e-01 1.02600000e+04] [ 1.76558859e-01 1.02600000e+04] [ 1.28264401e-01 9.89800000e+03] [ 1.28264401e-01 9.89800000e+03] [ 1.02738389e-01 9.75000000e+03] [ 1.02738389e-01 9.75000000e+03] [ 2.22889534e-01 5.45200000e+03] [ 2.22889534e-01 5.45200000e+03] [ 1.43460570e-01 5.32600000e+03] [ 1.43460570e-01 5.32600000e+03] [ 2.08976427e-01 4.86000000e+03] [ 2.08976427e-01 4.86000000e+03] [ 1.88334629e-01 4.25600000e+03] [ 1.88334629e-01 4.25600000e+03] [ 9.23774555e-02 2.46800000e+03] [ 9.23774555e-02 2.46800000e+03] [ 1.98534713e-01 1.96000000e+03] [ 1.98534713e-01 1.96000000e+03] [ 1.64488997e-01 1.79000000e+03] [ 1.64488997e-01 1.79000000e+03] [ 2.38430321e-01 1.76200000e+03] [ 2.38430321e-01 1.76200000e+03] [ 2.52977006e-01 5.34000000e+02] [ 2.52977006e-01 5.34000000e+02] [ 2.65853983e-01 4.04000000e+02] [ 2.65853983e-01 4.04000000e+02] [ 7.43487849e-02 3.01000000e+02] [ 7.43487849e-02 3.01000000e+02] [ 0.27720404 178. ] [ 0.27720404 178. ] Testing isomorphism of the two permutations of SR(25,12,5,6) graph 1: True Testing isomorphism of graphs 1 and 11 of the SR(25,12,5,6) family: False 

## Source Code¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #!/usr/bin/env python2.7 # initialize PETSc import sys import petsc4py petsc4py.init(sys.argv) from petsc4py import PETSc import numpy as np # import pyCTQW as qw import pyCTQW.MPI as qw # get the MPI rank rank = PETSc.Comm.Get_rank(PETSc.COMM_WORLD) # create a graph isomorphism object gi = qw.GraphISO() #========================= # Two Isomorphic Graphs #========================= # import two adjacency matrices; these are permutations # of the first graph in the SR-25-12-5-6, and thus are isomorphic adj1 = np.genfromtxt('../graphs/strong-regular-25-12-5-6/1-permutations/SR1_perm_1.txt') adj1p = np.genfromtxt('../graphs/strong-regular-25-12-5-6/1-permutations/SR1_perm_3.txt') # generate certificates for these two graphs cert1 = gi.GIcert(adj1) cert1p = gi.GIcert(adj1p) # print the certificates side by side; # they should be identical if rank == 0: print 'The GI certificates of two permutations of SR(25,12,5,6) graph 1:' for i in range(len(cert1)): print cert1[i], cert1p[i] if rank == 0: print '\nTesting isomorphism of the two permutations of SR(25,12,5,6) graph 1:' # verify using the inbuilt checking method cert1, cert1p, checkISO = gi.isomorphicQ(cert1, cert1p) if rank == 0: print checkISO #========================= #Two Non-Isomorphic Graphs #========================= if rank == 0: print '\nTesting isomorphism of graphs 1 and 11 of the SR(25,12,5,6) family:' adj2 = np.genfromtxt('../graphs/strong-regular-25-12-5-6/11.txt') cert1, cert2, checkISO = gi.isomorphicQ(cert1, adj2) if rank == 0: print checkISO