# GraphISO_3cayley.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 the 3-Cayley tree 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 script then uses pyCTQW.MPI.GraphISO.AllIsomorphicQ() to test the isomorphism of all combinations of these two matrices (i.e. 1 with 2, 1 with 1, 2 with 2, and 2 with 1), and constructs a matrix containing $$1$$ for isomorphic graphs, and $$0$$ otherwise.

As these graph are isomorphic, the result should be a matrix where all elements are $$1$$.

2. The second section of the program uses pyCTQW.MPI.GraphISO.AllIsomorphicQ() to test the isomorphism of all combinations of a 3-Cayley graph and a variant of the 3-Cayley graph, where an additional edge is placed between nodes 1 and 9.

As these graph are not isomorphic, the result should be a $$2\times 2$$: identity matrix.

## Output¶

 1 2 3 4 5 6 7 8 \$ mpirun -np 2 GraphISO_3cayley.py 1) Testing isomorphism of all permutations: [[ 1. 1.] [ 1. 1.]] 2) Testing isomorphism of all permutations: [[ 1. 0.] [ 0. 1.]] 

## 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 #!/usr/bin/env python2.7 # initialize PETSc import sys, 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() # generate certificate adj1 = np.genfromtxt('../graphs/cayley/3-cayley.txt') cert1 = gi.GIcert(adj1) # print the certificate if rank == 0: print 'The GI certificate of 3-cayley.txt:' np.savetxt('out/3cayley-cert.txt',cert1) # create a comparison table of two 3-cayley permutations # present in the '../graphs/cayley/3-cayley-permutations' # folder. As they are permutations, they are isomorphic, # so the result should be a 2x2 matrix composed of 1. comparisonTable = gi.AllIsomorphicQ('../graphs/cayley/3-cayley-permutations',info=False) if rank==0: print '1) Testing isomorphism of all pairings:' print comparisonTable # create a comparison table of a 3-cayley graph, and a # a 3-cayley graph with an additional edge added. # These are *not* isomorphic, # so the result should be a 2x2 matrix identity matrix. comparisonTable = gi.AllIsomorphicQ('../graphs/cayley/3-cayley-variant',info=False) if rank==0: print '\n2) Testing isomorphism of all pairings:' print comparisonTable