How can I double check a non-isomorphism between graphs?

[Paul Leopardi]

Since asking the question "How should I determine if two strongly regular graphs are isomorphic?" I have made great progress in classifying Bent functions by their Cayley graphs.
That is, up until now. I have found two graphs which I was (emprically) expecting to be isomorphic have different canonical labels.

To reproduce:
1. Clone the python-refactor branch of penguian/Boolean-Cayley-graphs
2. Copy the attached Sage file test_isomorphism.sage to your cloned Boolean-Cayley-graphs directory.
3. In your cloned Boolean-Cayley-graphs directory, run sage and enter
load("test_isomorphism.sage")

You should see:

sage: load("test_isomorphism.sage")
Defining bent function f...
f.algebraic_normal_form() == x0*x1*x6 + x0*x3 + x1*x4 + x2*x3*x6 + x2*x5 + x3*x4 + x4*x5*x6 + x6*x7
Determining strongly regular graphs SG1 and SG2...
Finding canonical labels CG1 and GG2...
CG1 == CG2: False
G1.is_isomorphic(G2): False
SageCG1 == SageCG2: False
SG1.stored_clique_polynomial == SG2.stored_clique_polynomial: True
SG1.stored_clique_polynomial == 45056*t^9 + 780288*t^8 + 2998272*t^7 + 5505024*t^6 + 4816896*t^5 + 1892352*t^4 + 286720*t^3 + 15360*t^2 + 256*t + 1
SG1.rank == SG2.rank: True
SG1.rank == 16
SG1.group_order == SG2.group_order: True
SG1.group_order == 229376
G1.automorphism_group().is_isomorphic(G2.automorphism_group()): True
sage:

This is saying that G1, the Cayley graph of f, and G2, the strongly regular graph obtained from the two-weight code derived from f, are not isomorphic, *but*
G1 and G2 have the same clique polynomial, *and*
G1 and G2 have isomorphic automorphism groups.

Do you have any hints on how I can further diagnose what is really going on here? I suspect a bug in my own code rather than a bug in Sage or a true non-isomorphism, but at this stage I can't be sure.
For example, I have not yet found nor devised a proof that G1 and G2 should be isomorphic, beyond observing that it is true for all the other cases I have examined so far.

The code for cayley_graph() and for strongly_regular_graph() is in bent_function.py.
The method strongly_regular_graph() depends on linear_code(), which is defined in boolean_function_improved.py, and is based on a simplified version of Ding III a) https://arxiv.org/abs/1503.06511
Sorry I haven't yet fully documented my code. It is a work in progress.

[David Joyner]

I haven't looked at your code but are you comparing the SRG associated
to the Boolean bent function and the graph associated to the incidence
matrix of that graph?

> Sorry I haven't yet fully documented my code. It is a work in progress.
>

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Paul Leopardi]

On Monday, 24 October 2016 01:45:10 UTC+11, David Joyner wrote:

I haven't looked at your code but are you comparing the SRG associated
to the Boolean bent function and the graph associated to the incidence
matrix of that graph?

I don't understand your precise meaning here, so I will spell out exactly what I have done.

Briefly, if f is a Boolean bent function f: Z_2^{dim} -> Z_2, with f(0)=0, then, if Z_2^{dim} is given lexicographical ordering from 0 to 2^{dim}-1, define the matrix M[i,j]=f(i \xor j).
The matrix M is the *adjacency* matrix of the Cayley graph of f, and is simple because f(0) != 1. The following function takes the equivalent f : Z -> Z_2 and produces the Cayley graph for a given dim.

def boolean_cayley_graph(dim, f):
    v = 2 ** dim
    result = Graph(v)
    result.add_edges([(i,j) for i in xsrange(v) for j in xsrange(i) if f(i ^ j)])
    return result

This is the graph that I am using for G1 in test_isomorphism.sage

A Boolean bent function can also generate a projective, two-weight linear code. Again, we take lexicographic ordering of Z_2^{dim} and produce a matrix M, but here the number of columns is the weight of f, i.e. the size of the support of f,
the number of rows is 2^{dim}, and each entry M[x,j] = <x, {support}_j> where support is a list corresponding to the support of f. This matrix M generates the linear code. In fact, the elements of the code are the rows of M.

    def linear_code(self):
        dim = self.nvariables()
        v = 2 ** dim
        f = self.extended_translate()
        support = [y
                   for y in xsrange(n)
                   if f(y)==1]
        M = matrix(GF(2), [[inner(x, y)
                            for y in support]
                            for x in xsrange(v)])
        return LinearCode(M)

There is Sage function strongly_regular_from_two_

weight_code(), described at http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/strongly_regular_db.html
"A strongly regular graph can be built from a two-weight projective code with weights w1,w2 (assuming w1 < w2) by adding an edge between any two codewords whose difference has weight w1."

The graph G2 that I am using in test_isomorphism.sage is thus strongly_regular_from_two_weight_code(f.linear_code()).

The bent function f can have one of two weights. If m=dim/2, the weight of f is either 2^{2m-1} - 2^{m-1} (weight class 0) or 2^{2m-1}+2^{m-1} (weight class 1).
In all cases where m<4, it turns out that if f has weight class 0 then f.cayley_graph() is isomorphic to f.strongly_regular_graph(), and if f has weight class 0 then f.cayley_graph() is isomorphic to f.strongly_regular_graph().complement().
For m=4, these isomorphisms are true for the bent functions in the extended affine equivalence class of the bent function corresponding to each of the first 8 polynomials listed below. For polynomials 9 and 10, there are exceptions,
according to the canonical label algorithms as implemented in Sage.

def bent_function_extended_affine_representative_polynomials_dimension_8():
    r"""
    The Boolean polynomials p8[i] for from 1 to 10 are the representatives of
    the extended affine equivalence classes of bent functions in 8 variables,
    with degree up to 3, as listed at 7.3 of Tokareva 2015,
    with citation [167] to Hou 1998.
    """
    R8.<x1,x2,x3,x4,x5,x6,x7,x8> = BooleanPolynomialRing(8)
    p8 = [None]*11
    p8[1] = x1*x2 + x3*x4 + x5*x6 + x7*x8
    p8[2] = x1*x2*x3 + x1*x4 + x2*x5 + x3*x6 + x7*x8
    p8[3] = x1*x2*x3 + x2*x4*x5 + x3*x4 + x2*x6 + x1*x7 + x5*x8
    p8[4] = x1*x2*x3 + x2*x4*x5 + x1*x3 + x1*x5 + x2*x6 + x3*x4 + x7*x8
    p8[5] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x2*x6 + x2*x5 + x1*x7 + x4*x8
    p8[6] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x1*x3 + x1*x4 + x2*x7 + x6*x8
    p8[7] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x2*x6 + x2*x5 + x1*x2 + x1*x3 + x1*x4 + x7*x8
    p8[8] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x1*x6 + x2*x7 + x4*x8
    p8[9] = x1*x2*x7 + x3*x4*x7 + x5*x6*x7 + x1*x4 + x3*x6 + x2*x5 + x4*x5 + x7*x8
    p8[10] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x1*x4*x7 + x3*x5 + x2*x7 + x1*x5 + x1*x6 + x4*x8
    return p8

 

[Dima Pasechnik]

I'd start by checking that the parameters of these strongly regular graphs are the same, i.e. comparing

G2.is_strongly_regular(parameters=True)

G1.is_strongly_regular(parameters=True)

it could be that you'd need to take the complement, or, even worse, a graph coming from the dual (in the S-ring, etc sense)

association scheme.

In particular, I recall stumbling upon this while working on these graphs, and finding out that the formulae here:

http://moodle.tec.hkr.se/~chen/research/2-weight-codes/index.htm

are not always correct.

Dima

[Paul Leopardi]

On 25 October 2016 12:12:44 AM AEDT, Dima Pasechnik <dim...@gmail.com> wrote:
>I'd start by checking that the parameters of these strongly regular
>graphs
>are the same, i.e. comparing
>
>G2.is_strongly_regular(parameters=True)
>G1.is_strongly_regular(parameters=True)
>
>it could be that you'd need to take the complement, or, even worse, a
>graph
>coming from the dual (in the S-ring, etc sense)
>association scheme.
>
>In particular, I recall stumbling upon this while working on these
>graphs,
>and finding out that the formulae here:
>http://moodle.tec.hkr.se/~chen/research/2-weight-codes/index.htm
>are not always correct.

Thanks, Dima.
The strongly regular graph parameters are always the same. The graphs themselves are in some cases not isomorphic. In my next message I will post the relevant output from my code.
--
Paul Leopardi https://sites.google.com/site/paulleopardi/

[Dima Pasechnik]

I am trying to run your script, but am getting

IOError: did not find file 'boolean_dimension_cayley_graph_classifications.sage' to load or attach

and indeed, there is no file so named in your github repo.

[Dima Pasechnik]

I would do a check using GAP's Grape package, which allows for checking isomorphisms

(it uses nauty as the backend)

While there is no ready function to call Grape from Sage, this should be easy to write using e.g.

libgap.function_factory()

[Paul Leopardi]

On Tuesday, 25 October 2016 05:55:42 UTC+11, Dima Pasechnik wrote:

I am trying to run your script, but am getting

IOError: did not find file 'boolean_dimension_cayley_graph_classifications.sage' to load or attach

and indeed, there is no file so named in your github repo.

It is here: https://github.com/penguian/Boolean-Cayley-graphs/blob/python-refactor/boolean_dimension_cayley_graph_classifications.sage
You need to use the python-refactor branch.
Sorry, this is all work in progress, and I have been sick over the last few days, with not enough energy to tidy things up.

[Paul Leopardi]

Hi,
I have attached the output file here. I am sorry that I have not put more time into cleaning up the code and the output.

Once you figure out what the output is trying to tell you, you will see that the relevant pairs of strongly regular graphs are isomorphic for dim=4 and dim=6, and also for the first 8 of 10 polynomials for dim=8.
All the best, Paul

[Paul Leopardi]

On Tuesday, 25 October 2016 06:02:06 UTC+11, Dima Pasechnik wrote:

I would do a check using GAP's Grape package, which allows for checking isomorphisms

(it uses nauty as the backend)

While there is no ready function to call Grape from Sage, this should be easy to write using e.g.

libgap.function_factory()

Thanks for the tip!
 

[Paul Leopardi]

On Tuesday, 25 October 2016 06:02:06 UTC+11, Dima Pasechnik wrote:

I would do a check using GAP's Grape package, which allows for checking isomorphisms

(it uses nauty as the backend)

While there is no ready function to call Grape from Sage, this should be easy to write using e.g.

libgap.function_factory()

Is there a simple guide on how to copy Sage graphs and matrices into and out of Gap? What I have seen so far is not encouraging. In fact I have not yet seen any documentation on how to copy a GF(2) matrix from Sage to Gap. Similarly for graphs. Presumably someone has done it by now. Is there a FAQ for this?
 

[David Joyner]

On Tue, Oct 25, 2016 at 7:37 AM, Paul Leopardi <paul.l...@gmail.com> wrote:
> On Tuesday, 25 October 2016 06:02:06 UTC+11, Dima Pasechnik wrote:
>>
>> I would do a check using GAP's Grape package, which allows for checking
>> isomorphisms
>> (it uses nauty as the backend)
>> While there is no ready function to call Grape from Sage, this should be
>> easy to write using e.g.
>> libgap.function_factory()
>>
>
> Is there a simple guide on how to copy Sage graphs and matrices into and out
> of Gap? What I have seen so far is not encouraging. In fact I have not yet
> seen any documentation on how to copy a GF(2) matrix from Sage to Gap.

sage: A = matrix(GF(2), [[1,1,0],[1,0,1]])
sage: gap(A)
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, 0*Z(2), Z(2)^0 ] ]
sage: A
[1 1 0]
[1 0 1]

> Similarly for graphs. Presumably someone has done it by now. Is there a FAQ
> for this?
>
>

[Paul Leopardi]

On Tuesday, 25 October 2016 06:02:06 UTC+11, Dima Pasechnik wrote:

I would do a check using GAP's Grape package, which allows for checking isomorphisms

(it uses nauty as the backend)

While there is no ready function to call Grape from Sage, this should be easy to write using e.g.

libgap.function_factory()

I finally managed to figure out how to get graphs from Sage to Grape, but now Grape can't find nauty. What do I need to do to configure Grape properly?

sage: GG=libgap.eval('GG := Graph( G, [1..16], OnPoints, function(x,y) return MCG[x][y] = 1; end,true );')
sage: GG
rec( adjacencies := [ [ 2, 3, 5, 7, 10, 11 ], [ 1, 4, 6, 7, 10, 12 ], [ 1, 4, 5, 8, 11, 13 ], [ 2, 3, 6, 8, 12, 13 ], [ 1, 3, 6, 9, 11, 14 ], [ 2, 4, 5, 9, 12, 14 ], [ 1, 2, 8, 9, 10, 15 ], [ 3, 4, 7, 9, 13, 15 ], [ 5, 6, 7, 8, 14, 15 ], [ 1, 2, 7, 13, 14, 16 ], [ 1, 3, 5, 12, 15, 16 ], [ 2, 4, 6, 11, 15, 16 ], [ 3, 4, 8, 10, 14, 16 ], [ 5, 6, 9, 10, 13, 16 ], [ 7, 8, 9, 11, 12, 16 ], [ 10, 11, 12, 13, 14, 15 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], order := 16, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16 ] )
sage: HH=libgap.eval('HH := Graph( G, [1..16], OnPoints, function(x,y) return MLG[x][y] = 1; end,true );')
sage: HH
rec( adjacencies := [ [ 2, 3, 5, 7, 10, 11 ], [ 1, 4, 6, 7, 10, 12 ], [ 1, 4, 5, 8, 11, 13 ], [ 2, 3, 6, 8, 12, 13 ], [ 1, 3, 6, 9, 11, 14 ], [ 2, 4, 5, 9, 12, 14 ], [ 1, 2, 8, 9, 10, 15 ], [ 3, 4, 7, 9, 13, 15 ], [ 5, 6, 7, 8, 14, 15 ], [ 1, 2, 7, 13, 14, 16 ], [ 1, 3, 5, 12, 15, 16 ], [ 2, 4, 6, 11, 15, 16 ], [ 3, 4, 8, 10, 14, 16 ], [ 5, 6, 9, 10, 13, 16 ], [ 7, 8, 9, 11, 12, 16 ], [ 10, 11, 12, 13, 14, 15 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], order := 16, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16 ] )
sage: libgap.eval('GraphIsomorphism(GG,HH)')                                                              
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-80-325cd83b9cf4> in <module>()
----> 1 libgap.eval('GraphIsomorphism(GG,HH)')

/home/leopardi/opt/sage/sage-7.2/src/sage/libs/gap/libgap.pyx in sage.libs.gap.libgap.Gap.eval (/home/leopardi/opt/sage/sage-7.2/src/build/cythonized/sage/libs/gap/libgap.c:4183)()
    429         if not isinstance(gap_command, basestring):
    430             gap_command = str(gap_command._gap_init_())
--> 431         return make_any_gap_element(self, gap_eval(gap_command))
    432
    433     @cached_method

/home/leopardi/opt/sage/sage-7.2/src/sage/libs/gap/util.pyx in sage.libs.gap.util.gap_eval (/home/leopardi/opt/sage/sage-7.2/src/build/cythonized/sage/libs/gap/util.c:4947)()
    286             sig_off()
    287         except RuntimeError as msg:
--> 288             raise ValueError('libGAP: '+str(msg).strip())
    289
    290         if libGAP_Symbol != libGAP_S_SEMICOLON:

ValueError: libGAP: d
$1n16g
2
3
5
7
10
11;
1
4
6
7
10
12;
1
4
5
8
11
13;
2
3
6
8
12
13;
1
3
6
9
11
14;
2
4
5
9
12
14;
1
2
8
9
10
15;
3
4
7
9
13
15;
5
6
7
8
14
15;
1
2
7
13
14
16;
1
3
5
12
15
16;
2
4
6
11
15
16;
3
4
8
10
14
16;
5
6
9
10
13
16;
7
8
9
11
12
16;
10
11
12
13
14
15.
> /tmp/tmd2qUpq/ftmp1 p,cx
>> /tmp/tmd2qUpq/ftmp2 bq
16
Error, cannot find output produced by `dreadnaut'

[Dima Pasechnik]

Right, this looks like a recent regression. AFAIR, it used to work.

If you use gap.* rather than libgap.*, things seem to work for me, e.g.

sage: gap.load_package('grape')

sage: gap.eval('GG:=JohnsonGraph(5,2);')

'rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4)\n  (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, \n  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], \n      [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, \n  representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 \n     ] )'

sage: gap.eval('AutGroupGraph(GG);')

'Group([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7), (1,2)(6,8)(7,9) ])'

sage: 

(whereas if I use libgap.* I end up with the same error as you)

This is now

https://trac.sagemath.org/ticket/21794

[Paul Leopardi]

Hi Dima,
Thanks. By the way, should gap.set_global and gap.get_global do the same sort of things as libgap.set_global and libgap.get_global? If not, why not?

[Dima Pasechnik]

On Wednesday, November 2, 2016 at 6:53:41 AM UTC, Paul Leopardi wrote:

Hi Dima,
Thanks. By the way, should gap.set_global and gap.get_global do the same sort of things as libgap.set_global and libgap.get_global? If not, why not?

I must say I don't know why these libgap.set_global and get_global are needed.

But there are more differences; in general libgap is designed so that potentially every GAP command Blah is callable as

libgap.Blah, but in gap-interface  (which is much older) you need to do more to achieve this.

Dima

[Paul Leopardi]

On Wednesday, 2 November 2016 20:08:20 UTC+11, Dima Pasechnik wrote:

I must say I don't know why these libgap.set_global and get_global are needed.

I used them to get my large matrices into libgap as globals. Trying to pass them through a text based interface does not work.


Following is a toy example, starting with a graph lg on 16 vertices.
sage: lg=c[1].linear_graph_class_list[0]
sage: mlg=lg.adjacency_matrix()
sage: libgap.set_global('MLG',mlg)
sage: MLG=libgap.get_global('MLG')
sage: type(MLG)
<type 'sage.libs.gap.element.GapElement_List'>
sage: libgap.eval('MLG')
[ [ 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0 ], [ 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0 ], [ 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0 ], [ 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0 ], [ 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0 ], [ 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 ], [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1 ], [ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1 ], [ 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 ], [ 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1 ], [ 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0 ] ]

The actual adjacency matrices that I want to use in my test are 256x256.

sage: c, reclassification, cayley_graph_classes = load_boolean_dimension_graph_classifications(8,9)
sage: lg=c[9].linear_graph_class_list[0]
sage: mlg=lg.adjacency_matrix()
sage: mlg.dimensions()
(256, 256)
sage: libgap.set_global('MLG',mlg)
sage: MLG=libgap.get_global('MLG')

sage: HH=libgap.eval('HH := Graph( G, [1..16], OnPoints, function(x,y) return MLG[x][y] = 1; end,true );')

sage: cg=c[9].cayley_graph_class_list[0]
sage: mcg=cg.adjacency_matrix()
sage: mcg.dimensions()
(256, 256)
sage: libgap.set_global('MCG',mcg)

[Dima Pasechnik]

On Wednesday, November 2, 2016 at 11:57:20 AM UTC, Paul Leopardi wrote:

On Wednesday, 2 November 2016 20:08:20 UTC+11, Dima Pasechnik wrote:

I must say I don't know why these libgap.set_global and get_global are needed.

I used them to get my large matrices into libgap as globals. Trying to pass them through a text based interface does not work.

could you show an example of this? 

IMHO you might indeed have a problem if you use libgap.eval(). But you should not...

The other thought is that you appear to work with Cayley graphs, and for them you only need to pass one row of the adjacency matrix,

and the group; passing the whole matrix is an overkill.

[Paul Leopardi]

On Thursday, 3 November 2016 04:58:11 UTC+11, Dima Pasechnik wrote:

On Wednesday, November 2, 2016 at 11:57:20 AM UTC, Paul Leopardi wrote:

On Wednesday, 2 November 2016 20:08:20 UTC+11, Dima Pasechnik wrote:

I must say I don't know why these libgap.set_global and get_global are needed.

I used them to get my large matrices into libgap as globals. Trying to pass them through a text based interface does not work.

ld you show an example of this? 

IMHO you might indeed have a problem if you use libgap.eval(). But you should not...

The other thought is that you appear to work with Cayley graphs, and for them you only need to pass one row of the adjacency matrix,

and the group; passing the whole matrix is an overkill.

Hi Dima,
Thanks for your patience and for all your help. I finally got the following to work:


gap.load_package('grape')


def check_graphs_using_gap(g_0, g_1):
    m_0 = g_0.adjacency_matrix()
    m_1 = g_1.adjacency_matrix()
    dim = str(m_0.dimensions()[0])
    gap.eval('M_0 := '+gap(m_0).str())
    gap.eval('M_1 := '+gap(m_1).str())
    gap.eval('GR := Group( () )')
    gap.eval('G_0 := Graph( GR, [1..'+dim+'], OnPoints, function(x,y) return M_0[x][y] = 1; end,true );')
    gap.eval('G_1 := Graph( GR, [1..'+dim+'], OnPoints, function(x,y) return M_1[x][y] = 1; end,true );')
    return gap.eval('IsIsomorphicGraph(G_0, G_1);')

Assuming that the algorithm used is Nauty rather than Bliss, running this code against my graphs confirms the cases of non-isomorphism that I previously identified.

[Dima Pasechnik]

you might try to find a combinatorial invariant distinguishing graphs here, e.g. the 4-vertex condition

(introduced in http://www.ams.org/mathscinet-getitem?mr=340088

more references here: http://link.springer.com/article/10.1007/s10801-014-0554-1)