A constructor for the Brouwer-Haemers graph

[nathanncohen]

As the title says !

http://www.win.tue.nl/~aeb/graphs/Brouwer-Haemers.html

Nathann

Depends on #14283

CC: @sagetrac-azi

Component: graph theory

Author: Nathann Cohen

Reviewer: Jernej Azarija

Merged: sage-5.10.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14514

[nathanncohen]

comment:1

With a Sexyyyyyyyyyyyyyyyy embedding :-P

Nathann

[sagetrac-azi]

comment:2

Hello!!

The patch is fine! I would only add the following test.

The graph has eigenvalues 20,2,-7

sage: set(G.spectrum()) == set([20,2,-7])
True

So that we have as much new tests as possible! Otherwise the whole testing of the graph theory module finishes too quickly !!!

BTW. I was wondering if its time to redesign this graph database thing. If we keep adding "specific" graphs the codebase will explode with code that basically just constructs new objects.

One thing that I would suggest for all fixed graphs, compute their sparse6/graph6 string (whichever is shorter) and simply have Graph(thestring) in the given method?

Or perhaps have a data file with graphs/sparse6 strings/layouts and load that at runtime or something?

What do you think ??

[nathanncohen]

comment:3

Yoooooooooo !!

The patch is fine! I would only add the following test.

Done !

So that we have as much new tests as possible! Otherwise the whole testing of the graph theory module finishes too quickly !!!

Ahem. Yeah, good point :-P

BTW. I was wondering if its time to redesign this graph database thing. If we keep adding "specific" graphs the codebase will explode with code that basically just constructs new objects.

Yep. I don't like it either.

One thing that I would suggest for all fixed graphs, compute their sparse6/graph6 string (whichever is shorter) and simply have Graph(thestring) in the given method?

Once again : I don't like the way we do things now either. But replacing the methods with sparse6 string means that our graphs are "proprietary" graphs how they are built is also a nice information to have around. Plus we lose layouts, the vertices' names (which may contain some information too). And it would only shorten the smallgraphs file, not the constructors that actually build families of graphs.
And we lose the doctests and documentation too, perhaps ?

Or perhaps have a data file with graphs/sparse6 strings/layouts and load that at runtime or something?

What do you think ??

I think that we will need to have an index of all sparse6 string of the graphs we have in Sage at some point. When we will want Sage to answer questions like "Have you ever seen this graph ?". But if we do have such an index, I think that we will still have the methods around at the same time. They don't have the same purpose.

But still, I don't like it either :-P

What do you think ?

Patch updated, by the way !

Nathann

[sagetrac-azi]

comment:4

Replying to @nathanncohen:

Yoooooooooo !!

The patch is fine! I would only add the following test.

Done !

So that we have as much new tests as possible! Otherwise the whole testing of the graph theory module finishes too quickly !!!

Ahem. Yeah, good point :-P

BTW. I was wondering if its time to redesign this graph database thing. If we keep adding "specific" graphs the codebase will explode with code that basically just constructs new objects.

Yep. I don't like it either.

One thing that I would suggest for all fixed graphs, compute their sparse6/graph6 string (whichever is shorter) and simply have Graph(thestring) in the given method?

Once again : I don't like the way we do things now either. But replacing the methods with sparse6 string means that our graphs are "proprietary" graphs how they are built is also a nice information to have around. Plus we lose layouts, the vertices' names (which may contain some information too). And it would only shorten the smallgraphs file, not the constructors that actually build families of graphs.
And we lose the doctests and documentation too, perhaps ?

Or perhaps have a data file with graphs/sparse6 strings/layouts and load that at runtime or something?

What do you think ??

I agree. Somehow we want to balance usability and performance without making a bloated module. I don't see a solution for that though :-)

I think that we will need to have an index of all sparse6 string of the graphs we have in Sage at some point. When we will want Sage to answer questions like "Have you ever seen this graph ?". But if we do have such an index, I think that we will still have the methods around at the same time. They don't have the same purpose.

Yes. I was also thinking about that. To have some method of the form "nameGraph()" returning the name of a given graph (if known) or perhaps a construction of it in the sense "cartesian product of petersen and 5-cycle"

But this again sounds like a messy thing to implement :-)

But still, I don't like it either :-P

What do you think ?

Patch updated, by the way !

Patch is fine I'm gonna change the status to reflect that.

Nathann

[sagetrac-azi]

Reviewer: Jernej Azarija

[nathanncohen]

comment:6

Yes. I was also thinking about that. To have some method of the form "nameGraph()" returning the name of a given graph (if known) or perhaps a construction of it in the sense "cartesian product of petersen and 5-cycle"

Well... For sure we will need a db at some point... For sure the function will answer "I've never seen this graph in my life" most of the time. But it is not necessarily complicated to implement..

Oh, and by the way we already have a small database of graphs from ISGCI #14396.

It's a good thing to have around, though it also looks like there will be a lot of duplicated information if we ever do that ;-)

Patch is fine I'm gonna change the status to reflect that.

Thanks ! :-)

Nathann

[jdemeyer]

Dependencies: #14283

[jdemeyer]

comment:7

There is a conflict with #14283.

[nathanncohen]

comment:9

Done !

[jdemeyer]

comment:10

PLEASE RUN DOCTESTS BEFORE SETTING A PATCH TO NEEDS_REVIEW OR POSITIVE_REVIEW

sage -t devel/sage/sage/graphs/generators/smallgraphs.py
**********************************************************************
File "devel/sage/sage/graphs/generators/smallgraphs.py", line 1067, in sage.graphs.generators.smallgraphs.BrouwerHaemersGraph
Failed example:
    set(G.spectrum()) == {20,2,-7}
Exception raised:
    Traceback (most recent call last):
      File "/mazur/release/merger/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 466, in _run
        self.execute(example, compiled, test.globs)
      File "/mazur/release/merger/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 825, in execute
        exec compiled in globs
      File "<doctest sage.graphs.generators.smallgraphs.BrouwerHaemersGraph[2]>", line 1, in <module>
        set(G.spectrum()) == {Integer(20),Integer(2),-Integer(7)}
    NameError: name 'G' is not defined
**********************************************************************

[nathanncohen]

Attachment: trac_14514.patch.gz

[nathanncohen]

comment:11

Fixed.......

Nathann

[jdemeyer]

Merged: sage-5.10.beta2