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

[Download 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