Opened 14 months ago
Closed 12 months ago
#30329 closed enhancement (fixed)
Graphs: last unbounded diameter distanceregular graphs
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description (last modified by )
Added constructions for a few distanceregular 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
 Branch set to public/graphs/30329
 Cc dimpase added
 Commit set to 7985a1aae587058bd1428b9123822d16bdc97af6
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 13 months ago by
 Status changed from needs_review to needs_work
Remainder to update once #30312 is sorted
comment:3 Changed 13 months ago by
 Commit changed from 7985a1aae587058bd1428b9123822d16bdc97af6 to d2ff33fa76a2875c2b7d21af3b9dda5ad90b49f9
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
19b859e  moved and renamed orthogonal dual polar

d6a403b  Merge branch 9.2.beta8 into 30303

d7453fa  removed cython code; added imports

562283f  Merge branch 30303 (and sage 9.2.beta8) into 30312

503bc12  renamed functions; added meataxe flag to doctests

51d73b4  Merge 30312 into 30329

9a3e609  reverted changes to matrix_space.py

e78c2d0  removed dependecies from symmetric generator

38577a8  fixed bug with matrix generation; added meataxe flag to tests

d2ff33f  Merge branch 30312 into 30329 (removed 29886)

comment:4 Changed 13 months ago by
 Commit changed from d2ff33fa76a2875c2b7d21af3b9dda5ad90b49f9 to ac45a626b9cd7cc9df8223f6e774243bc76cb238
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
582b480  normilised vector in alternating forms graph

dd05147  normalised v and multiply all matrices by all nonzero scalars; unordered pairs

1b8db43  fix typos

e9cdce9  generate rank 1 bilienear forms without computing ranks

91bc5bc  removed testing code

383397d  expanded outer_product into cython; now as fast as initial implementation

48395a1  use integer vectors in bilinear form to represents matrices

339b4f5  fix docstrings

c081dde  Merge branch '30312' into 30329

ac45a62  some code formatting and docstrings

comment:5 Changed 13 months ago by
 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
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
 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
 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:
3e1df8c  added const to half cube

comment:9 Changed 13 months ago by
 Status changed from needs_review to positive_review
comment:10 Changed 13 months ago by
If you find another, please let me know
comment:11 Changed 13 months ago by
 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/sitepackages/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/sitepackages/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 **********************************************************************
comment:12 Changed 13 months ago by
 Commit changed from 3e1df8ce0340a76e7648bde15e4fc81d03b34626 to d5555b4d8c11a2bf3f47056d4172a5bb7442250c
comment:13 Changed 13 months ago by
 Status changed from needs_work to needs_review
Merged the fix on branch #30312
comment:14 Changed 13 months ago by
 Branch changed from public/graphs/30329 to public/graphs/30329rebased
 Commit changed from d5555b4d8c11a2bf3f47056d4172a5bb7442250c to 845c3b444fc7f4c920bc68144e9c03714a5cc861
comment:15 Changed 13 months ago by
I've actually merged it 30s ago and I'm now running the tests
comment:16 Changed 13 months ago by
 Branch changed from public/graphs/30329rebased to public/graphs/30329
 Commit changed from 845c3b444fc7f4c920bc68144e9c03714a5cc861 to ea30040d9d0726b18435cb94793d61bf525c5b5e
Last 10 new commits:
17cd79c  Merge branch 'develop' into drg_fam1

51d73b4  Merge 30312 into 30329

d2ff33f  Merge branch 30312 into 30329 (removed 29886)

c081dde  Merge branch '30312' into 30329

ac45a62  some code formatting and docstrings

3e1df8c  added const to half cube

d5555b4  Merge branch 't/30312' into t/30329

2a1861d  Merge branch 't/30312' into t/30329

49cdcc1  Merge branch 't/30312' into t/30329

ea30040  added long time flags

comment:17 Changed 13 months ago by
 Commit changed from ea30040d9d0726b18435cb94793d61bf525c5b5e to 4bcdb3ce885b32356fcf66fa7a14a1c9f940d572
Branch pushed to git repo; I updated commit sha1. New commits:
4bcdb3c  typos and TeX fixes

comment:18 Changed 13 months ago by
 Commit changed from 4bcdb3ce885b32356fcf66fa7a14a1c9f940d572 to feabf4fd56996341180d1eacf0dbf859e8d426c8
Branch pushed to git repo; I updated commit sha1. New commits:
feabf4f  better index section, uniform naming

comment:20 Changed 13 months ago by
 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 inO(2 ^ (n1) * (n  1) ^ 2)
while your version is inO(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
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
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
 Commit changed from feabf4fd56996341180d1eacf0dbf859e8d426c8 to 1fdcad9f649697e6a6e5fa168518df6a2152b21c
Branch pushed to git repo; I updated commit sha1. New commits:
1fdcad9  fixed typo

comment:24 Changed 13 months ago by
 Status changed from needs_work to positive_review
comment:25 Changed 12 months ago by
 Branch changed from public/graphs/30329 to 1fdcad9f649697e6a6e5fa168518df6a2152b21c
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
added some sig_checks
code for symmetric matrices
added examples and tests
fixed formatting
removed trailing whitespaces
fixed more code formatting; allow f=None for nomal symmetric matrices
added bilinear, alternating and hermitian form graphs
removed sporadic g; fixed doctests
removed random s
double odd, half cube, (double) grassmann