#30329 closed enhancement (fixed)

Graphs: last unbounded diameter distance-regular graphs

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

Status badges

Description (last modified by gh-Ivo-Maffei)

Added constructions for a few distance-regular graphs:

  • bipartite double of Odd graph
  • halved graph of Cube graph
  • Grassmann graph
  • Double Grassmann graph

Change History (25)

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

  • Branch set to public/graphs/30329
  • Cc dimpase added
  • Commit set to 7985a1aae587058bd1428b9123822d16bdc97af6
  • Description modified (diff)
  • Status changed from new to needs_review

Last 10 new commits:

be18963added some sig_checks
7f4d042code for symmetric matrices
e4957c2added examples and tests
10f063ffixed formatting
c4f1e6fremoved trailing whitespaces
7528f25fixed more code formatting; allow f=None for nomal symmetric matrices
e171598added bilinear, alternating and hermitian form graphs
7fcf73eremoved sporadic g; fixed doctests
b921ccfremoved random s
7985a1adouble odd, half cube, (double) grassmann

comment:2 Changed 13 months ago by gh-Ivo-Maffei

  • Status changed from needs_review to needs_work

Remainder to update once #30312 is sorted

comment:3 Changed 13 months ago by git

  • Commit changed from 7985a1aae587058bd1428b9123822d16bdc97af6 to d2ff33fa76a2875c2b7d21af3b9dda5ad90b49f9

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

19b859emoved and renamed orthogonal dual polar
d6a403bMerge branch 9.2.beta8 into 30303
d7453faremoved cython code; added imports
562283fMerge branch 30303 (and sage 9.2.beta8) into 30312
503bc12renamed functions; added meataxe flag to doctests
51d73b4Merge 30312 into 30329
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)

comment:4 Changed 13 months ago by git

  • Commit changed from d2ff33fa76a2875c2b7d21af3b9dda5ad90b49f9 to ac45a626b9cd7cc9df8223f6e774243bc76cb238

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

582b480normilised vector in alternating forms graph
dd05147normalised v and multiply all matrices by all non-zero scalars; unordered pairs
1b8db43fix typos
e9cdce9generate rank 1 bilienear forms without computing ranks
91bc5bcremoved testing code
383397dexpanded outer_product into cython; now as fast as initial implementation
48395a1use integer vectors in bilinear form to represents matrices
339b4f5fix docstrings
c081ddeMerge branch '30312' into 30329
ac45a62some code formatting and docstrings

comment:5 Changed 13 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

#30312 should be sorted out now, so this is ready

comment:6 Changed 13 months ago by dimpase

there is a bit of inconsistency with type hints - sometimes const is missing where it can well be added.

comment:7 Changed 13 months ago by dimpase

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

feel free to fix these and turn back to positive review

comment:8 Changed 13 months ago by git

  • Commit changed from ac45a626b9cd7cc9df8223f6e774243bc76cb238 to 3e1df8ce0340a76e7648bde15e4fc81d03b34626
  • 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:

3e1df8cadded const to half cube

comment:9 Changed 13 months ago by gh-Ivo-Maffei

  • Status changed from needs_review to positive_review

comment:10 Changed 13 months ago by gh-Ivo-Maffei

If you find another, please let me know

comment:11 Changed 13 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
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute
        exec(compiled, globs)
      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 679, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11665)
        m3 = tuple([m1[i] + m2[i] for i in range(d*e)])
    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
**********************************************************************
Last edited 13 months ago by vbraun (previous) (diff)

comment:12 Changed 13 months ago by git

  • Commit changed from 3e1df8ce0340a76e7648bde15e4fc81d03b34626 to d5555b4d8c11a2bf3f47056d4172a5bb7442250c

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

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

comment:13 Changed 13 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

Merged the fix on branch #30312

comment:14 Changed 13 months ago by dimpase

  • Branch changed from public/graphs/30329 to public/graphs/30329rebased
  • Commit changed from d5555b4d8c11a2bf3f47056d4172a5bb7442250c to 845c3b444fc7f4c920bc68144e9c03714a5cc861

rebased over latest #30312


New commits:

97f0450Merge branch 'develop' into t/30312
5344f35added long time flags and fixed van Lint name
9e69f0dmissing # long time
6b6aceadouble odd, half cube, (double) grassmann
9c14650some code formatting and docstrings
845c3b4added const to half cube

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

I've actually merged it 30s ago and I'm now running the tests

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

  • Branch changed from public/graphs/30329rebased to public/graphs/30329
  • Commit changed from 845c3b444fc7f4c920bc68144e9c03714a5cc861 to ea30040d9d0726b18435cb94793d61bf525c5b5e

Last 10 new commits:

17cd79cMerge branch 'develop' into drg_fam1
51d73b4Merge 30312 into 30329
d2ff33fMerge branch 30312 into 30329 (removed 29886)
c081ddeMerge branch '30312' into 30329
ac45a62some code formatting and docstrings
3e1df8cadded const to half cube
d5555b4Merge branch 't/30312' into t/30329
2a1861dMerge branch 't/30312' into t/30329
49cdcc1Merge branch 't/30312' into t/30329
ea30040added long time flags

comment:17 Changed 13 months ago by git

  • Commit changed from ea30040d9d0726b18435cb94793d61bf525c5b5e to 4bcdb3ce885b32356fcf66fa7a14a1c9f940d572

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

4bcdb3ctypos and TeX fixes

comment:18 Changed 13 months ago by git

  • Commit changed from 4bcdb3ce885b32356fcf66fa7a14a1c9f940d572 to feabf4fd56996341180d1eacf0dbf859e8d426c8

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

feabf4fbetter index section, uniform naming

comment:19 Changed 13 months ago by dimpase

  • Status changed from needs_review to positive_review

OK, done

comment:20 Changed 13 months ago by dcoudert

  • Status changed from positive_review to needs_work

in HalfCube:

  • typo: calssical
  • the hamming distance function could be rewritten like sum(1 for a, b in zip(v, w) if a != b)
  • The following construction is way faster when n is large (e.g., 12), but for small dimensions the running time is similar. Indeed, the time complexity is in O(2 ^ (n-1) * (n - 1) ^ 2) while your version is in O(2 ^ (2 * (n - 1))).
    def HalfCubeBest(const int n):
        """
        """
        if n < 2:
            raise ValueError("the dimension must be n > 1")
    
        from sage.graphs.graph_generators import graphs
        G = graphs.CubeGraph(n - 1)
        G.relabel()
    
        cdef int u, uu, v, i, j
        cdef list E = []
        for u in G:
            # flip 2 bits to get vertices at distance 2
            for i in range(n - 1):
                uu = u ^ (1 << i)
                for j in range(i + 1, n - 1):
                    v = uu ^ (1 << j)
                    if u < v:
                        E.append((u, v))
        G.add_edges(E)
        G.name("Half %d Cube"%n)
        return G
    

comment:21 Changed 13 months ago by dimpase

the code in comment:20 depends upon the ordering produced by G.relabel() ? How do we know that number of a vertex u corresponds naturally to the binary representation of the number u, this is more of a luck that it does.

I propose to do optimisation on a followup ticket, and just fix the typo here.

comment:22 Changed 13 months ago by dcoudert

Right, I have to improve the mapping from binary representation to int, and the optimization can be done later.

comment:23 Changed 13 months ago by git

  • Commit changed from feabf4fd56996341180d1eacf0dbf859e8d426c8 to 1fdcad9f649697e6a6e5fa168518df6a2152b21c

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

1fdcad9fixed typo

comment:24 Changed 13 months ago by dimpase

  • Status changed from needs_work to positive_review

comment:25 Changed 12 months ago by vbraun

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