#30337 closed enhancement (fixed)

Graphs: obtain distance-regular graphs from generalised quadrangles

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords:
Cc: dimpase Merged in:
Authors: Ivo Maffei Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 3449361 (Commits, GitHub, GitLab) Commit: 344936159a22dcfe08d64c516496bf688cba49e1
Dependencies: #30223, #30509 Stopgaps:

Status badges

Description

Added code that constructs distance-regular graphs from generalised quadrangles with spread. Also added a function that checks whether an distance-regular graph can be built using the method above.

Change History (35)

comment:1 Changed 16 months ago by gh-Ivo-Maffei

  • Branch set to public/graphs/30337
  • Cc dimpase added
  • Commit set to b98b5e0161582c1a0ebe5593bf00258dceebd7bb
  • Status changed from new to needs_review

This is where #30223 gets used.


Last 10 new commits:

51d73b4Merge 30312 into 30329
06b8d25code for symmetric matrices
9991f4fadded file
931859badded code
7555255cleaned up code; added docstring; added tests
0e82896removed gap int; fixed some docstrings
ee0e18fadded references
51517feMerge 30223 into drg_fam2
190dd4badded code to generate drg from GQs
b98b5e0fix doctests; added references

comment:2 Changed 16 months ago by git

  • Commit changed from b98b5e0161582c1a0ebe5593bf00258dceebd7bb to 7753054764ee230c3dd584e31c2e195408733701

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

9a3e609reverted changes to matrix_space.py
e78c2d0removed dependecies from symmetric generator
38577a8fixed bug with matrix generation; added meataxe flag to tests
d2ff33fMerge branch 30312 into 30329 (removed 29886)
7753054Merge branch 30329 into 30337

comment:3 Changed 15 months ago by dimpase

it seems that the latest changes should be merged in.

comment:4 Changed 15 months ago by git

  • Commit changed from 7753054764ee230c3dd584e31c2e195408733701 to 0d92ec49345b05ab42118406755808d60a06d79a

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

48395a1use integer vectors in bilinear form to represents matrices
339b4f5fix docstrings
c081ddeMerge branch '30312' into 30329
ac45a62some code formatting and docstrings
e96c7c7Merge branch '30329' into 30337
a0463d5fix docsrtings; renamed module
5d16394renamed in design_catalog
e6ff3faMerge branch 't/30223' into t/30337
3e1df8cadded const to half cube
0d92ec4Merge branch 't/30329' into t/30337

comment:5 Changed 15 months ago by dimpase

I still got Memory Error in the longest bilinear forms graphs test, so here is an optimisation that reduces memory consumption by packing matrices into int, with it all tests pass.

  • src/sage/graphs/generators/distance_regular.pyx

    diff --git a/src/sage/graphs/generators/distance_regular.pyx b/src/sage/graphs/generators/distance_regular.pyx
    index 094f9bdc6a..7f8df1250d 100644
    a b def BilinearFormsGraph(const int d, const int e, const int q): 
    648648        sage: K.is_isomorphic(G)
    649649        True
    650650    """
    651     from sage.combinat.integer_vector import IntegerVectors
     651    from itertools import product as cartprod
    652652
    653653    Fq = GF(q)
    654654    Fqelems = list(Fq)
    655     matricesOverq = IntegerVectors(k=d*e, max_part=q-1)
    656 
     655    dim = d*e
     656    matricesOverq = cartprod(*([range(q)]*dim))
     657    qv = [int(q**jj) for jj in range(dim)]
    657658    rank1Matrices = []
     659    vsp = VectorSpace(Fq, e)
    658660    for u in VectorSpace(Fq, d):
    659661        if u.is_zero() or not u[u.support()[0]].is_one():
    660662            continue
    661663
    662         for v in VectorSpace(Fq, e):
     664        for v in vsp:
    663665            if v.is_zero():
    664666                continue
    665667
    666668            sig_check()
    667             M = [0] * (d*e)
     669            M = [0] * dim
    668670            for row in range(d):
    669671                for col in range(e):
    670672                    M[e*row + col] = u[row] * v[col]
    def BilinearFormsGraph(const int d, const int e, const int q): 
    673675
    674676    edges = []
    675677    for m1 in matricesOverq:
    676         m1 = tuple(map(lambda x: Fqelems[x], m1))
     678        im1 = 0
     679        for jj in range(dim):
     680            im1 += m1[jj] * qv[jj]
    677681        for m2 in rank1Matrices:
    678682            sig_check()
    679             m3 = tuple([m1[i] + m2[i] for i in range(d*e)])
    680             edges.append((m1, m3))
     683            im3 = 0
     684            for jj in range(dim):
     685                im3 += Fqelems.index(Fqelems[m1[jj]] + m2[jj]) * qv[jj]
     686            edges.append((im1, im3))
    681687
    682688    G = Graph(edges, format='list_of_edges')
    683689    G.name("Bilinear forms graphs over F_%d with parameters (%d, %d)"%(q, d, e))

comment:6 follow-up: Changed 15 months ago by gh-Ivo-Maffei

Is this conversion to integers needed for the other forms graphs?

comment:7 Changed 15 months ago by git

  • Commit changed from 0d92ec49345b05ab42118406755808d60a06d79a to 376d459639fd29d6d73487d4d4271a88fdebcbd8

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

376d459convert matrices in bilinearFormsGraph to integers to lower memory requirements

comment:8 in reply to: ↑ 6 Changed 15 months ago by dimpase

Replying to gh-Ivo-Maffei:

Is this conversion to integers needed for the other forms graphs?

it certainly lowers memory consumption, but I would not worry too much about it. There are much better ways to handle this, as implemented in GAP package GRAPE.

comment:9 Changed 15 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

comment:10 Changed 15 months ago by git

  • Commit changed from 376d459639fd29d6d73487d4d4271a88fdebcbd8 to ec4456053d07fb45a78270c9dc2d66756b0f2659
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

ec44560a python style fix

comment:11 Changed 15 months ago by dimpase

  • Status changed from needs_review to positive_review

comment:12 Changed 15 months ago by vbraun

  • Status changed from positive_review to needs_work
**********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 629, in sage.graphs.generators.distance_regular.BilinearFormsGraph
Failed example:
    G = graphs.BilinearFormsGraph(3,3,3)  # long time (20 s)
Exception raised:
    Traceback (most recent call last):
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 715, in _run
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute
      File "<doctest sage.graphs.generators.distance_regular.BilinearFormsGraph[2]>", line 1, in <module>
        G = graphs.BilinearFormsGraph(Integer(3),Integer(3),Integer(3))  # long time (20 s)
      File "sage/graphs/generators/distance_regular.pyx", line 691, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11929)
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/graphs/graph.py", line 1261, in __init__
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 10935, in add_edges
      File "sage/graphs/base/sparse_graph.pyx", line 1645, in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17623)
      File "sage/graphs/base/sparse_graph.pyx", line 1096, in sage.graphs.base.sparse_graph.SparseGraph.add_arc_label (build/cythonized/sage/graphs/base/sparse_graph.c:13067)
    MemoryError
**********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 630, in sage.graphs.generators.distance_regular.BilinearFormsGraph
Failed example:
    G.order()  # long time (due to above)
Expected:
    19683
Got:
    512
**********************************************************************

comment:13 Changed 15 months ago by vbraun

Does that really test a code path that cannot be tested in <1s?

comment:14 Changed 15 months ago by gh-Ivo-Maffei

I cannot reproduce the error.

All my code do is calling Graph(edges, format='list_of_edges'). The edges list is long (6652854) but I believe the code path (i.e. the full stack of function calls) should not differ from Graph([(0,1)], format='list_of_edges').

I can change the doctest to importing BilinearFormsGraph directly from sage.graphs.generators.distance_regular if this solves the issue, but I don't know how to test it myself.

comment:15 Changed 15 months ago by dimpase

I agree with Volker (vbraun) that this doctest takes way too long. Mark it not tested and add graphs.BilinearFormsGraph(3,4,2) instead - this takes <3 sec.

comment:16 Changed 15 months ago by git

  • Commit changed from ec4456053d07fb45a78270c9dc2d66756b0f2659 to 59776810db8b3352985cc688c82b9ea6e48a70dc

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

5977681removed long doctests

comment:17 Changed 15 months ago by dimpase

Please run

./sage -tp --long --verbose src/sage/graphs/generators/distance_regular.pyx

to see what tests are the longest. This file is still by far the slowest to test in sage/graphs/, 3 times as long as anything else there. GrassmannGraph(2, 6, 3) and DoubleGrassmannGraph(3, 2) are the two slowest ones (>30 sec each on my oldish X1 Carbon Lenovo, and they aren't even tagged long time!), but there are more.

comment:18 Changed 15 months ago by git

  • Commit changed from 59776810db8b3352985cc688c82b9ea6e48a70dc to 3c3b4b5648d28b7224dee103da30bcf1732f601f

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

3c3b4b5added long time flags

comment:19 Changed 15 months ago by gh-Ivo-Maffei

I marked everything that took more than 1s as long.

I think one should change the default value for --warn-long (it is usually 2 min) if 30s are long.

Last edited 15 months ago by gh-Ivo-Maffei (previous) (diff)

comment:20 Changed 15 months ago by vbraun

The buildbot limits the available memory to encourage writing efficient unit tests, hence the MemoryError?

comment:21 Changed 15 months ago by git

  • Commit changed from 3c3b4b5648d28b7224dee103da30bcf1732f601f to f8803529b1b0007f7a0be54d75b8b6ad4705a78d

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

4675366replaced long doctest
d5555b4Merge branch 't/30312' into t/30329
f880352Merge branch 't/30329' into t/30337

comment:22 follow-up: Changed 15 months ago by dimpase

let's wait for the next beta/rc, to lessen the rebase work.

comment:23 in reply to: ↑ 22 Changed 15 months ago by gh-Ivo-Maffei

Replying to dimpase:

let's wait for the next beta/rc, to lessen the rebase work.

I'm having issues with beta11 not starting for an import error on libgsl.23.dylib Has this issue been brought up yet or am I the only one?

comment:24 Changed 15 months ago by dimpase

How do you get gsl in your installation? Does it come from the system/Homebrew/conda, or do you build it?

comment:25 Changed 15 months ago by gh-Ivo-Maffei

It is in sage/local/lib/. I can send you the crash report, if you wish

comment:26 Changed 15 months ago by dimpase

gsl has been updated in just merged #29483. Perhaps you need to run ./sage -f gsl && make build

comment:27 Changed 15 months ago by git

  • Commit changed from f8803529b1b0007f7a0be54d75b8b6ad4705a78d to 8c12a8f333132858ec3b9e39cd21523786b41dc1

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

05c9593Merge branch 'develop' of git://trac.sagemath.org/sage into t/30337
97f0450Merge branch 'develop' into t/30312
2a1861dMerge branch 't/30312' into t/30329
5344f35added long time flags and fixed van Lint name
9e69f0dmissing # long time
49cdcc1Merge branch 't/30312' into t/30329
ea30040added long time flags
4bcdb3ctypos and TeX fixes
feabf4fbetter index section, uniform naming
8c12a8fMerge branch 't/30329' into t/30337

comment:28 Changed 15 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

comment:29 Changed 15 months ago by git

  • Commit changed from 8c12a8f333132858ec3b9e39cd21523786b41dc1 to c97bda5c59adcfa6f5822587e0d0adaf57d1c38b

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

1fdcad9fixed typo
c97bda5Merge branch 't/30329' into t/30337

comment:30 Changed 15 months ago by git

  • Commit changed from c97bda5c59adcfa6f5822587e0d0adaf57d1c38b to d9c9149b5e5a60850b15cd90849e63c57898bea2

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

3024980faster implementation of HalfCube
898fbeeadded positions to HalfCube
d9c9149Merge branch 't/30509' into t/30337

comment:31 Changed 15 months ago by gh-Ivo-Maffei

  • Dependencies changed from #30223, #30329 to #30223, #30509

comment:32 Changed 15 months ago by dimpase

please also merge in the latest develop beta, beta12.

comment:33 Changed 15 months ago by git

  • Commit changed from d9c9149b5e5a60850b15cd90849e63c57898bea2 to 344936159a22dcfe08d64c516496bf688cba49e1

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

3449361Merge branch 9.2.beta12 into t/30337

comment:34 Changed 15 months ago by dimpase

  • Status changed from needs_review to positive_review

OK, good!

comment:35 Changed 14 months ago by vbraun

  • Branch changed from public/graphs/30337 to 344936159a22dcfe08d64c516496bf688cba49e1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.