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.]]

Required Files¶

• 3-cayley permutation 1 adjacency matrix
• 3-cayley permutation 2 adjacency matrix
• 3-cayley variant adjacency matrix

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

#!/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