bug in discovery of SRG' complements - related to twograph_descendant #26513

dimpase · 2018-10-20T08:05:31Z

as reported by Ferdinand Ihringer:

The following two graphs do not work, but their complement does:

graphs.strongly_regular_graph(539, 250, 105, 125)
graphs.strongly_regular_graph(779, 378, 177, 189)

Here the complement does not work:

graphs.strongly_regular_graph(819, 400, 190, 200)
graphs.strongly_regular_graph(819, 418, 217, 209)

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-1-5ba69562e41c> in <module>()
----> 1 graphs.strongly_regular_graph(Integer(539), Integer(250), Integer(105), Integer(125))

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.strongly_regular_graph (build/cythonized/sage/graphs/strongly_regular_db.c:44406)()
   2982                 return True
   2983             ans = f(*params)
-> 2984             return check_srg(ans[0](*ans[1:]))
   2985         if f(*params_complement):
   2986             if existence:

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.is_twograph_descendant_of_srg.la (build/cythonized/sage/graphs/strongly_regular_db.c:23106)()
   1500                 def la(vv):
   1501                     from sage.combinat.designs.twographs import twograph_descendant
-> 1502                     g = strongly_regular_graph(vv, k, l - 2*mu + k)
   1503                     return twograph_descendant(g, next(g.vertex_iterator()),
   1504                                                name=True)

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.strongly_regular_graph (build/cythonized/sage/graphs/strongly_regular_db.c:45159)()
   3015             if existence:
   3016                 return True
-> 3017             raise RuntimeError(("Andries Brouwer's database claims that such a "+
   3018                                 "({},{},{},{})-strongly regular graph exists, but "+
   3019                                 "Sage does not know how to build it. If *you* do, "+

RuntimeError: Andries Brouwer's database claims that such a (540,245,100,120)-strongly regular graph exists, but Sage does not know how to build it. If *you* do, please get in touch with us on sage-devel!
Comments: 2-graph
sage:
sage: graphs.strongly_regular_graph(539, 288, 162, 144)
descendant of  at 0: Graph on 539 vertices

This is related to the missing in Sage constructions.

In the first two cases graphs can be constructed using 2-graph descendant from Fickus et al SRGs (cf Brouwer's tables, not yet implemented in Sage), while their complements are
constructed using 2-graph descendant from known to Sage SRGs.

This illustrates a bug in discovery of SRGs via taking complements.

In the last case graphs can be constructed using 2-graph descendant from Fickus et al SRGs (cf Brouwer's tables, not yet implemented in Sage) or their complements.

There is also a discrepancy: the database gets broken after trying to build graphs.strongly_regular_graph(819, 400, 190, 200)
graphs.strongly_regular_graph(819, 418, 217, 209).

CC: @Ivo-Maffei @ferihr @vbraun

Component: graph theory

Author: Dima Pasechnik

Branch/Commit: b267320

Reviewer: Ivo Maffei, Ferdinand Ihringer

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

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

dimpase · 2018-10-20T08:43:53Z

comment:1

There is also a bug with the database getting corrupt by an attempt to build an SRG:

│ SageMath version 8.4, Release Date: 2018-10-17
sage: graphs.strongly_regular_graph(819,418,217,209)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-1-b80bcfe45035> in <module>()
----> 1 graphs.strongly_regular_graph(Integer(819),Integer(418),Integer(217),Integer(209))

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.strongly_regular_graph (build/cythonized/sage/graphs/strongly_regular_db.c:44406)()
   2982                 return True
   2983             ans = f(*params)
-> 2984             return check_srg(ans[0](*ans[1:]))
   2985         if f(*params_complement):
   2986             if existence:

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.is_twograph_descendant_of_srg.la (build/cythonized/sage/graphs/strongly_regular_db.c:23106)()
   1500                 def la(vv):
   1501                     from sage.combinat.designs.twographs import twograph_descendant
-> 1502                     g = strongly_regular_graph(vv, k, l - 2*mu + k)
   1503                     return twograph_descendant(g, next(g.vertex_iterator()),
   1504                                                name=True)

/home/dimpase/Sage/sagetrac-mirror/local/lib/python2.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.strongly_regular_graph (build/cythonized/sage/graphs/strongly_regular_db.c:45159)()
   3015             if existence:
   3016                 return True
-> 3017             raise RuntimeError(("Andries Brouwer's database claims that such a "+
   3018                                 "({},{},{},{})-strongly regular graph exists, but "+
   3019                                 "Sage does not know how to build it. If *you* do, "+

RuntimeError: Andries Brouwer's database claims that such a (820,429,228,220)-strongly regular graph exists, but Sage does not know how to build it. If *you* do, please get in touch with us on sage-devel!
Comments: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph
sage: from sage.graphs.strongly_regular_db import _check_database
sage: _check_database()
Sage cannot build a (512  133  24   38  ) that exists. Comment from Brouwer's database: <a href="srgtabrefs.html#Godsil92">Godsil</a>(q=8,r=3); pg(7,18,2)?
Sage cannot build a (512  378  282  270 ) that exists. Comment from Brouwer's database: 
Sage cannot build a (540  245  100  120 ) that exists. Comment from Brouwer's database: 2-graph
Sage cannot build a (540  294  168  150 ) that exists. Comment from Brouwer's database: from 2-(45,5,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
Sage cannot build a (780  369  168  180 ) that exists. Comment from Brouwer's database: 2-graph
Sage cannot build a (780  410  220  210 ) that exists. Comment from Brouwer's database: from 2-(39,3,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
Sage cannot build a (820  390  180  190 ) that exists. Comment from Brouwer's database: 2-graph
Sage cannot build a (820  429  228  220 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph

In Andries Brouwer's database:
- 462 impossible entries
- 2916 undecided entries
- 1160 realizable entries (Sage misses 8 of them)

whereas if the 1st call is not run then as expected one gets two more missing entries:

Sage cannot build a (819  400  190  200 ) that exists. Comment from Brouwer's database: pg(20,19,10)?; 2-graph*
Sage cannot build a (819  418  217  209 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph*

and the final count of missing graphs is 10.

dimpase · 2018-12-03T19:16:58Z

comment:2

The following patch fixes the discovery (but not the database inconsistency, which is a different story):

diff --git a/src/sage/graphs/strongly_regular_db.pyx b/src/sage/graphs/strongly_regular_db.pyx
index e8ece2dca0..e4e3fd0189 100644
--- a/src/sage/graphs/strongly_regular_db.pyx
+++ b/src/sage/graphs/strongly_regular_db.pyx
@@ -2981,12 +2981,18 @@ def strongly_regular_graph(int v,int k,int l,int mu=-1,bint existence=False,bint
             if existence:
                 return True
             ans = f(*params)
-            return check_srg(ans[0](*ans[1:]))
+            try:
+                return check_srg(ans[0](*ans[1:]))
+            except RuntimeError: # try the complement
+                pass
         if f(*params_complement):
             if existence:
                 return True
             ans = f(*params_complement)
-            return check_srg(ans[0](*ans[1:]).complement())
+            try:
+                return check_srg(ans[0](*ans[1:]).complement())
+            except RuntimeError: # try more functions
+                pass
 
     # From now on, we have no idea how to build the graph.
     #

dimpase · 2020-04-03T17:29:27Z

comment:3

here is a quick fix for all the issues here

--- a/src/sage/graphs/strongly_regular_db.pyx
+++ b/src/sage/graphs/strongly_regular_db.pyx
@@ -1484,12 +1484,15 @@ def is_twograph_descendant_of_srg(int v, int k0, int l, int mu):
             k = int(kf)
             if k == kf and \
                 strongly_regular_graph(v+1, k, l - 2*mu + k , k - mu,  existence=True) is True:
-                def la(vv):
-                    from sage.combinat.designs.twographs import twograph_descendant
-                    g = strongly_regular_graph(vv, k, l - 2*mu + k)
-                    return twograph_descendant(g, next(g.vertex_iterator()),
-                                               name=True)
-                return la, v + 1
+                try:
+                    g = strongly_regular_graph(v+1, k, l - 2*mu + k) # Sage might not know how to build g
+                    def la(gg):
+                        from sage.combinat.designs.twographs import twograph_descendant
+                        return twograph_descendant(gg, next(gg.vertex_iterator()),
+                                                   name=True)
+                    return la, g 
+                except RuntimeError:

basically, la() must keep its promise to return a graph if called, but currently it does not if g can't be built, due to an absent implementation.
A naive way (in the patch) is just to try to actually build g first.

dimpase · 2020-04-06T03:53:01Z

Commit: 0caf90e

dimpase · 2020-04-06T03:53:01Z

Author: Dima Pasechnik

dimpase · 2020-04-06T03:53:01Z

New commits:

`0caf90e`	`fix for the problem reported on trac #26513`

dimpase · 2020-04-06T03:53:01Z

Branch: u/dimpase/graphs/srgcomplfix

sagetrac-git · 2020-04-07T18:12:13Z

Changed commit from 0caf90e to e64452c

sagetrac-git · 2020-04-07T18:12:13Z

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

`e64452c`	`remove forgotten address in a test`

Ivo-Maffei · 2020-04-08T23:27:17Z

comment:7

I don't fully understand how the srg database works, but I looked at the new code and I see its point.

The la function contains a reference to g[0], but g is defined in in the scope of is_twograph_descendant_of_srg and not returned. This seems weird (does not g[0] get destroyed?), but, after some tests, it looks like Cython makes it work, so I just want to
bring it to your attention since you definitely know more than me how Cython works.
Apart from the above, the la function still contains some debugging code (lines 1489 and 1492).
In strongly_regular_graph the code that handles mu == -1 (line 2838, 2839) is pointless as the same code is executed inside strongly_regular_graph_lazy.

Everything else looks good!

ferihr · 2020-04-09T17:09:30Z

comment:8

The following works in the develop branch or 9.0, but no longer works with your version. It is the only set of parameters where I entcountered this issue, but I failed at automating my testing process.

sage: graphs.strongly_regular_graph(209, 100, 45, 50)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-3438f70cd243> in <module>()
----> 1 graphs.strongly_regular_graph(Integer(209), Integer(100), Integer(45), Integer(50))

/home/ferihr/git/sage/local/lib/python3.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.strongly_regular_graph (build/cythonized/sage/graphs/strongly_regular_db.c:41956)()
   2841     if existence is True:
   2842         return g
-> 2843     G = g[0](*g[1:])
   2844     if check and (v,k,l,mu) != G.is_strongly_regular(parameters=True):
   2845         params = (v,k,l,mu)

/home/ferihr/git/sage/local/lib/python3.7/site-packages/sage/graphs/strongly_regular_db.pyx in sage.graphs.strongly_regular_db.is_twograph_descendant_of_srg.la (build/cythonized/sage/graphs/strongly_regular_db.c:22420)()
   1491                         from sage.combinat.designs.twographs import twograph_descendant
   1492                     #    print("in la:", g[0], gr)
-> 1493                         gg = g[0](*gr)
   1494                         if (gg.name() is None) or (gg.name() == ''):
   1495                             gg = Graph(gg, name=str((v+1, k, l - 2*mu + k , k - mu))+"-strongly regular graph")

TypeError: lambda27() takes exactly one argument (0 given)

dimpase · 2020-04-11T14:30:22Z

comment:10

Thanks, I noticed your helpful reviews only now, as somehow I stopped receiving email notifications. I'll work on this soon.

Ivo-Maffei · 2020-04-11T16:02:21Z

comment:11

I had a look at the bug yesterday evening, and I believe the issues is the lambda function at line 2903. I think inserting * before t will fix it, but I have not done much testing. (another lambda function that probably needs the same fix can be found at line 2937)

dimpase · 2020-04-12T08:08:04Z

comment:12

Replying to @Ivo-Maffei:

I had a look at the bug yesterday evening, and I believe the issues is the lambda function at line 2903. I think inserting * before t will fix it, but I have not done much testing. (another lambda function that probably needs the same fix can be found at line 2937)

Yes, good catch, you are right about line 2903, it should be lambda *t to accommodate functions
without arguments. On the line 2937 all the functions are with at least one argument,
so it should be OK.

sagetrac-git · 2020-04-12T08:13:23Z

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

`238d7b6`	`missing * in lambda, more tests, removed prints`

sagetrac-git · 2020-04-12T08:13:23Z

Changed commit from e64452c to 238d7b6

dimpase · 2020-04-12T08:24:14Z

comment:14

OK, this appears to fix everything. To test every graph, one can run mentioned in the manual loop (you'll need gap_packages spkg installed):

        sage: from sage.graphs.strongly_regular_db import apparently_feasible_parameters
        sage: for p in sorted(apparently_feasible_parameters(1300)):   # not tested
        ....:     if graphs.strongly_regular_graph(*p,existence=True) is True: # not tested
        ....:         try:                                             # not tested
        ....:             _ = graphs.strongly_regular_graph(*p)        # not tested
        ....:             print(p, "built successfully")               # not tested
        ....:         except RuntimeError as e:                        # not tested
        ....:             if 'Brouwer' not in str(e):                  # not tested
        ....:                 raise                                    # not tested

dimpase · 2020-04-12T08:24:14Z

Reviewer: Ivo Maffei, Ferdinand Ihringer

dimpase · 2020-04-21T15:24:26Z

comment:16

Thanks!

Volker, could this make it into 9.1? Just one file is touched, long-standing bug fixed.

vbraun · 2020-04-23T22:33:13Z

Changed branch from u/dimpase/graphs/srgcomplfix to 238d7b6

vbraun · 2020-04-25T08:56:03Z

comment:18

On Python 2:

**********************************************************************
File "src/sage/graphs/strongly_regular_db.pyx", line 2812, in sage.graphs.strongly_regular_db.strongly_regular_graph
Failed example:
    graphs.strongly_regular_graph(209, 100, 45, 50)
Expected:
    descendant of complement(merging of S_7 on Circulant(6,[1,4])s) at 11: Graph on 209 vertices
Got:
    descendant of complement(merging of S_7 on Circulant(6,[1,4])s) at 1: Graph on 209 vertices
**********************************************************************
1 item had failures:
   1 of  20 in sage.graphs.strongly_regular_db.strongly_regular_graph
    [330 tests, 1 failure, 24.69 s]
**********************************************************************

vbraun · 2020-04-25T08:56:03Z

Changed commit from 238d7b6 to none

dimpase · 2020-04-26T06:01:41Z

Commit: b267320

dimpase · 2020-04-26T06:01:41Z

New commits:

`bc2d07f`	`fix for the problem reported on trac #26513`
`8b330c3`	`remove forgotten address in a test`
`d08181b`	`missing * in lambda, more tests, removed prints`
`b267320`	`do not depend on vertex numbering in some tests`

dimpase · 2020-04-26T06:01:41Z

Changed branch from 238d7b6 to u/dimpase/graphs/srgcomplfix

dimpase · 2020-04-26T06:02:50Z

comment:20

OK, the trivial fix by replacing unstable indices by ...

vbraun · 2020-05-02T21:58:28Z

Changed branch from u/dimpase/graphs/srgcomplfix to b267320

dimpase added this to the sage-8.5 milestone Oct 20, 2018

dimpase added c: graph theory labels Oct 20, 2018

This comment has been minimized.

Sign in to view

dimpase added the s: needs review label Apr 6, 2020

dimpase modified the milestones: sage-8.5, sage-9.1 Apr 6, 2020

ferihr mannequin added s: needs work and removed s: needs review labels Apr 9, 2020

dimpase added s: needs review and removed s: needs work labels Apr 12, 2020

Ivo-Maffei mannequin added s: positive review and removed s: needs review labels Apr 21, 2020

vbraun removed the s: positive review label Apr 23, 2020

vbraun closed this as completed Apr 23, 2020

vbraun reopened this Apr 25, 2020

dimpase added the s: needs review label Apr 26, 2020

dimpase added s: positive review and removed s: needs review labels Apr 26, 2020

vbraun removed the s: positive review label May 2, 2020

vbraun closed this as completed in f6d1907 May 2, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

bug in discovery of SRG' complements - related to twograph_descendant #26513

bug in discovery of SRG' complements - related to twograph_descendant #26513

dimpase commented Oct 20, 2018

This comment has been minimized.

dimpase commented Oct 20, 2018

dimpase commented Dec 3, 2018

dimpase commented Apr 3, 2020

dimpase commented Apr 6, 2020

dimpase commented Apr 6, 2020

dimpase commented Apr 6, 2020

dimpase commented Apr 6, 2020

sagetrac-git mannequin commented Apr 7, 2020

sagetrac-git mannequin commented Apr 7, 2020

Ivo-Maffei mannequin commented Apr 8, 2020

ferihr mannequin commented Apr 9, 2020

dimpase commented Apr 11, 2020

Ivo-Maffei mannequin commented Apr 11, 2020

dimpase commented Apr 12, 2020

sagetrac-git mannequin commented Apr 12, 2020

sagetrac-git mannequin commented Apr 12, 2020

dimpase commented Apr 12, 2020

dimpase commented Apr 12, 2020

dimpase commented Apr 21, 2020

vbraun commented Apr 23, 2020

vbraun commented Apr 25, 2020

vbraun commented Apr 25, 2020

dimpase commented Apr 26, 2020

dimpase commented Apr 26, 2020

dimpase commented Apr 26, 2020

dimpase commented Apr 26, 2020

vbraun commented May 2, 2020