Opened 4 years ago

Closed 2 years ago

#26513 closed defect (fixed)

bug in discovery of SRG' complements - related to twograph_descendant

Reported by: Dima Pasechnik Owned by:
Priority: major Milestone: sage-9.1
Component: graph theory Keywords:
Cc: gh-Ivo-Maffei, gh-ferihr, Volker Braun Merged in:
Authors: Dima Pasechnik Reviewers: Ivo Maffei, Ferdinand Ihringer
Report Upstream: N/A Work issues:
Branch: b267320 (Commits, GitHub, GitLab) Commit: b2673206665f09f15ba3ebc6b5b176d7825dd42a
Dependencies: Stopgaps:

Status badges

Description (last modified by Dima Pasechnik)

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).

Change History (21)

comment:1 Changed 4 years ago by Dima Pasechnik

Description: modified (diff)

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.

comment:2 Changed 4 years ago by Dima Pasechnik

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

  • src/sage/graphs/strongly_regular_db.pyx

    diff --git a/src/sage/graphs/strongly_regular_db.pyx b/src/sage/graphs/strongly_regular_db.pyx
    index e8ece2dca0..e4e3fd0189 100644
    a b def strongly_regular_graph(int v,int k,int l,int mu=-1,bint existence=False,bint 
    29812981            if existence:
    29822982                return True
    29832983            ans = f(*params)
    2984             return check_srg(ans[0](*ans[1:]))
     2984            try:
     2985                return check_srg(ans[0](*ans[1:]))
     2986            except RuntimeError: # try the complement
     2987                pass
    29852988        if f(*params_complement):
    29862989            if existence:
    29872990                return True
    29882991            ans = f(*params_complement)
    2989             return check_srg(ans[0](*ans[1:]).complement())
     2992            try:
     2993                return check_srg(ans[0](*ans[1:]).complement())
     2994            except RuntimeError: # try more functions
     2995                pass
    29902996
    29912997    # From now on, we have no idea how to build the graph.
    29922998    #

comment:3 Changed 2 years ago by Dima Pasechnik

here is a quick fix for all the issues here

  • src/sage/graphs/strongly_regular_db.pyx

    a b def is_twograph_descendant_of_srg(int v, int k0, int l, int mu): 
    14841484            k = int(kf)
    14851485            if k == kf and \
    14861486                strongly_regular_graph(v+1, k, l - 2*mu + k , k - mu,  existence=True) is True:
    1487                 def la(vv):
    1488                     from sage.combinat.designs.twographs import twograph_descendant
    1489                     g = strongly_regular_graph(vv, k, l - 2*mu + k)
    1490                     return twograph_descendant(g, next(g.vertex_iterator()),
    1491                                                name=True)
    1492                 return la, v + 1
     1487                try:
     1488                    g = strongly_regular_graph(v+1, k, l - 2*mu + k) # Sage might not know how to build g
     1489                    def la(gg):
     1490                        from sage.combinat.designs.twographs import twograph_descendant
     1491                        return twograph_descendant(gg, next(gg.vertex_iterator()),
     1492                                                   name=True)
     1493                    return la, g
     1494                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.

comment:4 Changed 2 years ago by Dima Pasechnik

Authors: Dima Pasechnik
Branch: u/dimpase/graphs/srgcomplfix
Commit: 0caf90ec95464c6b505b3c94cbecb5a01a531880
Milestone: sage-8.5sage-9.1
Status: newneeds_review

New commits:

0caf90efix for the problem reported on trac #26513

comment:5 Changed 2 years ago by Dima Pasechnik

Cc: gh-Ivo-Maffei gh-ferihr added

comment:6 Changed 2 years ago by git

Commit: 0caf90ec95464c6b505b3c94cbecb5a01a531880e64452cf794aa5838e85f798b5ea87d488912913

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

e64452cremove forgotten address in a test

comment:7 Changed 2 years ago by gh-Ivo-Maffei

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!

comment:8 Changed 2 years ago by gh-ferihr

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)

comment:9 Changed 2 years ago by gh-ferihr

Status: needs_reviewneeds_work

comment:10 Changed 2 years ago by Dima Pasechnik

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

comment:11 Changed 2 years ago by gh-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)

comment:12 in reply to:  11 Changed 2 years ago by Dima Pasechnik

Replying to gh-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.

comment:13 Changed 2 years ago by git

Commit: e64452cf794aa5838e85f798b5ea87d488912913238d7b66ac4b438db2e099e5f68ac9aa5ad98e96

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

238d7b6missing * in lambda, more tests, removed prints

comment:14 Changed 2 years ago by Dima Pasechnik

Reviewers: Ivo Maffei, Ferdinand Ihringer
Status: needs_workneeds_review

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

comment:15 Changed 2 years ago by gh-Ivo-Maffei

Status: needs_reviewpositive_review

comment:16 Changed 2 years ago by Dima Pasechnik

Cc: Volker Braun added

Thanks!

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

comment:17 Changed 2 years ago by Volker Braun

Branch: u/dimpase/graphs/srgcomplfix238d7b66ac4b438db2e099e5f68ac9aa5ad98e96
Resolution: fixed
Status: positive_reviewclosed

comment:18 Changed 2 years ago by Volker Braun

Commit: 238d7b66ac4b438db2e099e5f68ac9aa5ad98e96
Resolution: fixed
Status: closednew

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

comment:19 Changed 2 years ago by Dima Pasechnik

Branch: 238d7b66ac4b438db2e099e5f68ac9aa5ad98e96u/dimpase/graphs/srgcomplfix
Commit: b2673206665f09f15ba3ebc6b5b176d7825dd42a
Status: newneeds_review

New commits:

bc2d07ffix for the problem reported on trac #26513
8b330c3remove forgotten address in a test
d08181bmissing * in lambda, more tests, removed prints
b267320do not depend on vertex numbering in some tests

comment:20 Changed 2 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

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

comment:21 Changed 2 years ago by Volker Braun

Branch: u/dimpase/graphs/srgcomplfixb2673206665f09f15ba3ebc6b5b176d7825dd42a
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.