Strongly Regular Graphs database #18948

nathanncohen · 2015-07-24T16:42:31Z

This ticket implements a new module names strongly_regular_db that lets us build one example of strongly regular graph, given four integer parametes (v,k,lambda,mu).

It uses Andries Brouwer's database to return more meaningful non-existence results, and help us find which constructions are missing from the database.

With a bit of luck (and time, and work) it would be great if we could reproduce all SRG that are known to exist!

The module has a simple structure:

has a simple structure:

A seems_feasible(v,k,l,mu) function that performs the basic artihmetic
checks to figure out if (v,k,l,mu) is realizable. The
'apparently_feasible_parameters(n)` returns the lists of all parameters that
pass these tests for v<n. When n=1301, the set of parameters it returns is
precisely those that appear on your database (this is checked in the code).
Several functions (is_paley, is_johnson, ...) test if a given set of
parameters (v,k,l,mu) can be realized with a graph of the corresponding family
(a Paley graph, a Johnson graph, ...). If they can, they return the parameters
of that graph so that it can be built easily.
The main function strongly_regular_graph can be called in two ways:
- strongly_regular_graph(v,k,l,mu,existence=True) answers True if such a
  graph is known to exists, False if it is known to be infeasible, and Unknown
  otherwise.
- strongly_regular_graph(v,k,l,mu) attempts to build and return the
  requested graph, and returns a meaningful exception if it cannot.

This branch also updates the package 'graphs', which now ships the database in json format.

http://www.steinertriples.fr/ncohen/tmp/graphs-20150724.tar.bz2

Nathann

Depends on #18934

CC: @dimpase

Component: graph theory

Author: Nathann Cohen

Branch/Commit: d1d25a0

Reviewer: Dima Pasechnik

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

The text was updated successfully, but these errors were encountered:

nathanncohen · 2015-07-24T16:44:00Z

Branch: u/ncohen/18948

nathanncohen · 2015-07-24T16:44:00Z

New commits:

`f599ffe`	`trac XXX: Strongly Regular Graphs database`

nathanncohen · 2015-07-24T16:44:00Z

Commit: f599ffe

sagetrac-git · 2015-07-24T16:45:15Z

Changed commit from f599ffe to a0173e2

sagetrac-git · 2015-07-24T16:45:15Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`a0173e2`	`trac #18948: Strongly Regular Graphs database`

sagetrac-git · 2015-07-26T10:57:08Z

Branch pushed to git repo; I updated commit sha1. New commits:

`4adcf95`	`trac #18948: Two missing graphs`

sagetrac-git · 2015-07-26T10:57:08Z

Changed commit from a0173e2 to 4adcf95

seblabbe · 2015-07-26T11:28:49Z

comment:5

I think you do not need to edit module_list.py file anymore when there is no dependencies. See #15410.

nathanncohen · 2015-07-26T13:15:40Z

comment:6

I think you do not need to edit module_list.py file anymore when there is no dependencies. See #15410.

I removed it and all doctests break because of an import problem. As I do not mind much either way personally, I leave it like that.

Nathann

dimpase · 2015-07-30T13:20:33Z

comment:7

this comment landed on the wrong ticket (#18960), sorry:

Test if a Paley graph is `(v,k,\lambda,\mu)`-strongly regular.

Huh? Do you mean

Test whether a  `(v,k,\lambda,\mu)`-strongly regular graph is Paley.

All the similar docstrings have the same problem. Namely, one tests that a (v,k,l,m)-srg is BlahBlah, not the other way around...

nathanncohen · 2015-07-30T15:31:55Z

comment:8

this comment landed on the wrong ticket (#18960), sorry:
Test if a Paley graph is `(v,k,\lambda,\mu)`-strongly regular.
Huh? Do you mean
Test whether a  `(v,k,\lambda,\mu)`-strongly regular graph is Paley.

To me your phrasing also sounds incorrect, as it seems to test whether "every (v,k,l,mu)-strongly regular graph is a Paley graph".

What about replacing 'a' by 'some'?

Test if some Paley graph is (v,k,l,mu)-strongly regular

Nathann

sagetrac-git · 2015-07-30T16:45:16Z

Changed commit from 4adcf95 to a9280c9

sagetrac-git · 2015-07-30T16:45:16Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8f25493`	`trac #18948: Merged with 6.9.beta0`
`a9280c9`	`trac #18948: Rephrasing the doc`

dimpase · 2015-08-01T08:34:36Z

comment:10

Do you really want to keep mu as a required by functions parameter? I would rather get rid of it, for it is a simple computation to find mu given the 1st three parameters.

nathanncohen · 2015-08-01T08:36:13Z

comment:11

Do you really want to keep mu as a required by functions parameter? I would rather get rid of it, for it is a simple computation to find mu given the 1st three parameters.

I prefer to keep it, for it belongs to the definition of strongly regular graphs. I don't see anything wrong it making it optional: we can replace 'None' by the computed value if necessary.

Nathann

sagetrac-git · 2015-08-01T17:04:37Z

Branch pushed to git repo; I updated commit sha1. New commits:

`0ed8441`	`trac #18948: guess mu`

sagetrac-git · 2015-08-01T17:04:37Z

Changed commit from a9280c9 to 0ed8441

sagetrac-git · 2015-08-01T17:05:25Z

Changed commit from 0ed8441 to cf8f2da

sagetrac-git · 2015-08-01T17:05:25Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`cf8f2da`	`trac #18948: guess mu`

dimpase · 2015-08-01T19:50:48Z

comment:14

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`cf8f2da`	`trac #18948: guess mu`

How about functions like is_paley()? They also do not need mu...

By the way, what is the point of doing return (lambda q : PaleyGraph(q),v) instead of
return PaleyGraph(v) ?

nathanncohen · 2015-08-01T22:33:23Z

comment:15

How about functions like is_paley()? They also do not need mu...

If you think that this feature would be useful, I have nothing against your adding it in another ticket. I do not see the point, as those functions are not even meant to be called directly by users, who can do so with 'strongly_regular_graph' (which can automatically guess 'mu' if needed).

By the way, what is the point of doing return (lambda q : PaleyGraph(q),v) instead of
return PaleyGraph(v) ?

That's in order to be able to tell if the construction can be done without doing it (which can take quite some time). Very useful to know which entries Sage can build to compare it to the list of those that are known to exist. I used a design similar to the one used in sage.combinat.designs.orthogonal_arrays_find_construction, where many functions exist to guess the parameters of some constructions (exactly like it is done here). With these design, knowing if something can be built and getting the data to build it is done in the same operation. There are two advantages:

No need of a 'exists=True' optional keyword when you call the function
No 'if exists' everywhere in the code's function, to return 'True' instead of returning the graph
If you want to test the existence, THEN build the graph, you do not call the function twice with different parameters (which would not use the function's cache, and so you compute the decomposition twice).

Admittedly, the functions of the design code are computationally much more expensive than those.

Nathann

dimpase · 2015-08-03T07:56:37Z

comment:16

it seems that

cdef eigenvalues(int v,int k,int l,int mu)

only returns correct results for the non-Paley (non-conference) case (i.e. the case where the eigenvalues are not integer).

This should be documented, at least.

sagetrac-git · 2015-08-03T08:04:45Z

Changed commit from cf8f2da to aed4022

sagetrac-git · 2015-08-03T08:04:45Z

Branch pushed to git repo; I updated commit sha1. New commits:

`aed4022`	`trac #18948: DOcstring`

nathanncohen · 2015-08-05T08:30:11Z

comment:54

These commits should not affect the outcome, or at least I don't see how they can.

Easy: you add constructions of strongly regular graphs. The only thing this doctest does is check the COUNT of them (note that the individual lines naming each graph are not check, except the first, because of '...'). Given that you add constructions, the final number changes, and the doctest breaks.

Or, if you like, I have weird test failures on my branch due to something in your already reviewed tickets...

Just load ONLY the branch, and you will not have any problem. If you add other commits, now, I can do no magic.

Nathann

nathanncohen · 2015-08-05T08:32:03Z

comment:55

Yes, comment:33

If you read his 'history' file you will see that he tested more commits than that. He also had some commits of hiw own patch (#18972) in his history. If you load only the branch on my tickets things work, but you can't expect me to fix in my branches the errors introduced on non-reviewed tickets. The only thing that it proves is that #18972 needs to be rebased on #18988. And that's clearly not my job.

Nathann

vbraun · 2015-08-05T08:35:11Z

comment:56

comment:33 is from the buildbot and does not include any non-reviewed tickets:

http://build.sagemath.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2032%20bit%29%20incremental/builds/37

dimpase · 2015-08-05T08:35:27Z

comment:57

Replying to @nathanncohen:

These commits should not affect the outcome, or at least I don't see how they can.

Easy: you add constructions of strongly regular graphs. The only thing this doctest does is check the COUNT of them (note that the individual lines naming each graph are not check, except the first, because of '...'). Given that you add constructions, the final number changes, and the doctest breaks.

Oh hell... How about we add a special tag (say, countexamples) to these counting test(s), so that they don't normally run.

Or, if you like, I have weird test failures on my branch due to something in your already reviewed tickets...

Just load ONLY the branch, and you will not have any problem. If you add other commits, now, I can do no magic.

The problem is that nobody expects the Spanish Inquisition hitting on your tests this way. Doctesting such counts is akin to doctesting number of Sage tests that pass...

nathanncohen · 2015-08-05T08:38:22Z

comment:58

The problem is that nobody expects the Spanish Inquisition hitting on your tests this way. Doctesting such counts is akin to doctesting number of Sage tests that pass...

Regardless of that, the doctests pass, in this ticket and in those above.

Nathann

nathanncohen · 2015-08-05T08:40:05Z

comment:59

comment:33 is from the buildbot and does not include any non-reviewed tickets:

Is this buildbot running beta0 (which does not include #18934) or is it running your own more-updated relase (which includes #18934)?

vbraun · 2015-08-05T08:40:50Z

comment:60

The buildbot always merges dependencies first; Currently I'm at

d3a0be9 Trac #18989: Incorrect input_alphabet in FiniteStateMachine.disjoint_union
00f8736 Trac #18938: Refactor shortest paths
387fe06 Trac #17462: Remove the (deprecated) _boundary parameter
d868995 Trac #18608: Arc method in BalancedIncompleteBlockDesign class
649bf59 Trac #18585: Comparison of sparse polynomials
d9bb5de Trac #18978: gf2x fails to build with GCC 5.2
3c97405 Trac #18775: polytopes.icosidodecahedron and graphs.TruncatedIcosidodecahedralGraph
af59a3f Trac #18977: ncurses fails to build with GCC 5.2
4f379dc Trac #18860: Faster Poyhedron.graph()
47f6780 Trac #18975: make searches case-insensitive by default
50f503f Trac #18976: Update to IPython 3.2.1
8063cb3 Trac #18961: upgrade  ECL to 15.3.7
d6a3379 Trac #18934: New (v,6,1)-BIBD with v<=201
82513eb Trac #18089: Automaton.shannon_parry_markov_chain: New method
01a74d6 Trac #10194: Set factories
3b7932c Trac #18963: Remove 5 occurrences of FSMOldProcessOutput (Followup to #16133)
9559da6 Trac #18967: Silence the messages about deleting empty directories
0247d96 Trac #18742: interactive_simplex_method: Support several styles corresponding to major textbooks
571ad54 Trac #18910: Boost minimum spanning tree
c33a40b Trac #18876: Boost Cuthill-McKee, King Ordering
02125c0 Trac #18557: Implement FiniteStateMachine.disjoint_union (and .__or__)
f4a0ac6 Trac #18556: FiniteStateMachine.is_deterministic: machines with >1 initial states are non-deterministic
c0d4e06 Trac #18282: Fixes, cleanup and improvements to the default evaluation method for univariate polynomials
b74bb0b Trac #12607: ChainComplex reports zero homology groups (depending on ChomP)
d401fff Trac #18831: Hyperelliptic point counting various methods disagree
edb1b08 Updated Sage version to 6.9.beta0

nathanncohen · 2015-08-05T08:43:17Z

comment:61

The buildbot always merges dependencies first; Currently I'm at

So that is your explanation. Yesterday, or that night, you ran the doctests on a version of Sage which included #18934. This branch, at that time, did not have #18934 as a dependency. This morning, I rebased this ticket (and those above) over #18934, and I fixed it. So now it should work, because of this rebasing. So unless you find something wrong with this branch, please set it back to its original status.

Nathann

vbraun · 2015-08-05T08:47:06Z

comment:62

And this is why it shouldn't be possible to change positively reviewed branches... we can implement a cool-off period just for you if you prefer ;-)

dimpase · 2015-08-05T08:47:41Z

comment:63

As the reviewer, I hereby humbly beg for the _check_database() test to be amended; either
suppress checking the actual numbers by ..., or give it an extra optional tag so that it does not stand in the way.

nathanncohen · 2015-08-05T08:48:25Z

comment:64

And this is why it shouldn't be possible to change positively reviewed branches... we can implement a cool-off period just for you if you prefer ;-)

Create a poll on sage-devel.

nathanncohen · 2015-08-05T08:49:36Z

comment:65

As the reviewer, I hereby humbly beg for the _check_database() test to be amended; either
suppress checking the actual numbers by ..., or give it an extra optional tag so that it does not stand in the way.

If we do it now, I will have to re-merge 3 linearly ordered patches again. So let's do that later.

Nathann

dimpase · 2015-08-05T08:54:30Z

comment:66

Replying to @nathanncohen:

As the reviewer, I hereby humbly beg for the _check_database() test to be amended; either
suppress checking the actual numbers by ..., or give it an extra optional tag so that it does not stand in the way.

If we do it now, I will have to re-merge 3 linearly ordered patches again. So let's do that later.

Can you do this on #18988, or whatever ticket that has the latest commits in this chain?

nathanncohen · 2015-08-05T08:56:55Z

comment:67

Yeah yeah. I'm against it, but after having been complaining pointlessly for 30 minutes on a ticket because you were all testing something different from the branch stored on this ticket, I won't even bother trying to explain.

Nathann

nathanncohen · 2015-08-05T08:57:28Z

comment:68

Easier to blame the doctest, of course.

nathanncohen · 2015-08-05T08:58:34Z

comment:69

Let's create another ticket for that. It's unrelated to the topic of #18988..

nathanncohen · 2015-08-05T09:00:25Z

comment:70

So? Are you now convinced that there is no broken doctest in this ticket, and that it can be set back to its original status ?

vbraun · 2015-08-05T09:10:00Z

comment:71

I'm not necessarily convinced but I can try again... hopefully I'll get through a testing cycle before the branch changes again ;-)

nathanncohen · 2015-08-05T09:11:00Z

comment:72

I'm not necessarily convinced but I can try again... hopefully I'll get through a testing cycle before the branch changes again ;-)

Yeah, sorry for that. I should have remembered to keep such tickets in a linear order at all times.

dimpase · 2015-08-05T09:13:13Z

comment:73

Replying to @nathanncohen:

Let's create another ticket for that. It's unrelated to the topic of #18988..

As you like. Please do.

vbraun · 2015-08-05T16:58:56Z

Changed branch from u/ncohen/18948 to d1d25a0

nathanncohen mannequin added this to the sage-6.8 milestone Jul 24, 2015

nathanncohen mannequin added c: graph theory labels Jul 24, 2015

This comment has been minimized.

Sign in to view

nathanncohen mannequin added the s: needs review label Jul 24, 2015

vbraun added s: positive review and removed s: needs work labels Aug 5, 2015

vbraun removed the s: positive review label Aug 5, 2015

vbraun closed this as completed in 1b01a85 Aug 5, 2015

This was referenced Aug 1, 2015

New (v,6,1)-BIBD with v<=201 #18934

Closed

Strongly Regular Graphs from two-weight codes #18960

Closed

dimpase mentioned this issue Aug 28, 2015

twographs and Seidel switching #18972

Closed

This was referenced Aug 5, 2015

Orthogonal Polar graphs in strongly_regular_graph #18988

Closed

Remove useful doctest #18991

Closed

Strongly Regular Graphs database #18948

Strongly Regular Graphs database #18948

Comments

nathanncohen mannequin commented Jul 24, 2015

This comment has been minimized.

nathanncohen mannequin commented Jul 24, 2015

nathanncohen mannequin commented Jul 24, 2015

nathanncohen mannequin commented Jul 24, 2015

sagetrac-git mannequin commented Jul 24, 2015

sagetrac-git mannequin commented Jul 24, 2015

sagetrac-git mannequin commented Jul 26, 2015

sagetrac-git mannequin commented Jul 26, 2015

seblabbe commented Jul 26, 2015

nathanncohen mannequin commented Jul 26, 2015

dimpase commented Jul 30, 2015

nathanncohen mannequin commented Jul 30, 2015

sagetrac-git mannequin commented Jul 30, 2015

sagetrac-git mannequin commented Jul 30, 2015

dimpase commented Aug 1, 2015

nathanncohen mannequin commented Aug 1, 2015

sagetrac-git mannequin commented Aug 1, 2015

sagetrac-git mannequin commented Aug 1, 2015

sagetrac-git mannequin commented Aug 1, 2015

sagetrac-git mannequin commented Aug 1, 2015

dimpase commented Aug 1, 2015

nathanncohen mannequin commented Aug 1, 2015

dimpase commented Aug 3, 2015

sagetrac-git mannequin commented Aug 3, 2015

sagetrac-git mannequin commented Aug 3, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

vbraun commented Aug 5, 2015

dimpase commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

vbraun commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

vbraun commented Aug 5, 2015

dimpase commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

dimpase commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

vbraun commented Aug 5, 2015

nathanncohen mannequin commented Aug 5, 2015

dimpase commented Aug 5, 2015

vbraun commented Aug 5, 2015