Re: [sage-support] How should I determine if two strongly regular graphs are isomorphic?

[Jori Mäntysalo]

On Tue, 23 Aug 2016, Paul Leopardi wrote:


Do you have the package bliss or nauty installed?


sage: is_package_installed('bliss')
True


That explains it. canonical_label() uses Bliss by default if it is 
installed. Setting algorithm='sage' will override this (and slow down 
computation). So we should just expose more Bliss and Nauty features to 
Sage.


--
Jori Mäntysalo

Re: [sage-support] How should I determine if two strongly regular graphs are isomorphic?

[Paul Leopardi]

On Wednesday, 24 August 2016 00:14:10 UTC+10, vdelecroix wrote:
>
> Do you have the package bliss or nauty installed? 
>


sage: is_package_installed('bliss')
True
sage: is_package_installed('nauty')
True
 

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] How should I determine if two strongly regular graphs are isomorphic?

[Dima Pasechnik]

In this case your graphs give rise to Hadamard matrices (take Seidel adjacency 
matrix), so if you get nonisomorphic Hadamard matrices then you get 
nonisomorphic graphs, but not the other way around, generally speaking.
Although isomorphism of Hadamard matrices is probably harder...

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] How should I determine if two strongly regular graphs are isomorphic?

[Vincent Delecroix]

Do you have the package bliss or nauty installed?

On 23/08/16 10:53, Paul Leopardi wrote:

Hi all,
I am currently trying to use Sage to classify bent functions by their
Cayley graphs.

I have attached an example where I have two (256, 120, 56, 56) strongly
regular graphs, g and h, which are also canonical labels, such that g does
not equal h, and so g and h are not isomorphic.
It takes a relatively short time to produce the canonical labels, 38.8s to
run h.is_isomorphic(g), and g.is_isomorphic(h) is still running.

The example includes the Sage code that I used to generate the graphs, as
well as a transcript of my Sage session, including the graph6_string() of
each of the two graphs.

I would like some advice on how I should proceed with the classification,
given that I want to compare about 2^(16) such graphs to a small number of
representative graphs (about 6).

I have done other tests with graphs of this size that show that usually
g.is_isomorphic(h) is faster than comparing g.automorphism_group().order()
with h.automorphism_group().order(), which is faster than comparing
g.canonical_label() with h.canonical_label().
It's just that occasionally I have found cases where g.is_isomorphic(h) is
extremely slow.

I'm thinking of using threading and a timeout of (e.g.) 5 seconds, so that
my search first tries to use g.is_isomorphic(h), and if this times out, it
then compares the automorphism group orders, and only if they are equal,
does it then compute the canonical label.

What are other people doing?
All the best, Paul



--
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] How should I determine if two strongly regular graphs are isomorphic?

[Paul Leopardi]

Hi all,
I am currently trying to use Sage to classify bent functions by their 
Cayley graphs.

I have attached an example where I have two (256, 120, 56, 56) strongly 
regular graphs, g and h, which are also canonical labels, such that g does 
not equal h, and so g and h are not isomorphic.
It takes a relatively short time to produce the canonical labels, 38.8s to 
run h.is_isomorphic(g), and g.is_isomorphic(h) is still running.

The example includes the Sage code that I used to generate the graphs, as 
well as a transcript of my Sage session, including the graph6_string() of 
each of the two graphs.

I would like some advice on how I should proceed with the classification, 
given that I want to compare about 2^(16) such graphs to a small number of 
representative graphs (about 6).

I have done other tests with graphs of this size that show that usually 
g.is_isomorphic(h) is faster than comparing g.automorphism_group().order() 
with h.automorphism_group().order(), which is faster than comparing 
g.canonical_label() with h.canonical_label().
It's just that occasionally I have found cases where g.is_isomorphic(h) is 
extremely slow.

I'm thinking of using threading and a timeout of (e.g.) 5 seconds, so that 
my search first tries to use g.is_isomorphic(h), and if this times out, it 
then compares the automorphism group orders, and only if they are equal, 
does it then compute the canonical label.

What are other people doing?
All the best, Paul

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
┌┐
│ SageMath version 7.2, Release Date: 2016-05-15 │
│ Type "notebook()" for the browser-based notebook interface.│
│ Type "help()" for help.│
└┘
sage: from sage.crypto.boolean_function import BooleanFunction
sage: R. = BooleanPolynomialRing(8)
sage: fg=BooleanFunction(x1*x2*x3 + x1*x4 + x2*x5 + x3*x6 + x7*x8 + x1 + x2 + 
x3)
sage: fh=BooleanFunction(x1*x2*x3 + x1*x4 + x2*x5 + x3*x6 + x7*x8 + x4)
sage: load("boolean_cayley_graph.sage")
sage: bg=boolean_function_cayley_graph(fg)
sage: bh=boolean_function_cayley_graph(fh)
sage: %time g=bg.canonical_label()
CPU times: user 80 ms, sys: 4 ms, total: 84 ms
Wall time: 78.1 ms
sage: %time h=bh.canonical_label()
CPU times: user 188 ms, sys: 4 ms, total: 192 ms
Wall time: 189 ms
sage: print g.is_strongly_regular(parameters=True)
(256, 120, 56, 56)
sage: print h.is_strongly_regular(parameters=True)
(256, 120, 56, 56)
sage: %time g == h
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 913 µs
False
sage: gs=g.graph6_string()
sage: hs=h.graph6_string()
sage: len(gs)
5444
sage: len(hs)
5444
sage: print gs