Opened 7 years ago

Closed 7 years ago

#14514 closed enhancement (fixed)

A constructor for the Brouwer-Haemers graph

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: azi Merged in: sage-5.10.beta2
Authors: Nathann Cohen Reviewers: Jernej Azarija
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14283 Stopgaps:

Description

Attachments (1)

trac_14514.patch (3.4 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

With a Sexyyyyyyyyyyyyyyyy embedding :-P

Nathann

comment:2 follow-up: Changed 7 years ago by azi

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 ??

comment:3 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by ncohen

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

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by azi

Replying to ncohen:

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

comment:5 Changed 7 years ago by azi

  • Reviewers set to Jernej Azarija
  • Status changed from needs_review to positive_review

comment:6 in reply to: ↑ 4 Changed 7 years ago by ncohen

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

comment:7 Changed 7 years ago by jdemeyer

  • Dependencies set to #14283
  • Status changed from positive_review to needs_work

There is a conflict with #14283.

comment:8 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:9 Changed 7 years ago by ncohen

Done !

comment:10 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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
**********************************************************************

Changed 7 years ago by ncohen

comment:11 Changed 7 years ago by ncohen

Fixed.......

Nathann

comment:12 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:13 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.