Opened 2 years ago

Closed 2 years ago

#30303 closed enhancement (fixed)

Graphs: two families of distance-regular graphs

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

Status badges

Description

We introduce two families of distance-regular graphs related to dual polar spaces.

Change History (13)

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

  • Branch set to public/graphs/30303
  • Commit set to 33bb6a5e15d8aefc19049d0f3fad4885444571bb
  • Status changed from new to needs_review

Last 10 new commits:

ecde7cafix wrong rebase merge conflict resolution
e897a6bMerge branch 'drg_sporadic2' into drg_sporadic3
9b11d8dadded the last sporadic drg
68da709added references; added name to graph catalog
59299e6fix some docstrings
574960dadded gap_packages flag to atlasrep
9db5fd3Merge branch 'drg_sporadic1' into drg_sporadic2
a87fad1added gap_packages flag to atlasrep
73c4fedMerge ticket 30260 into ticket 30286
33bb6a5added dual polar orthogonal and Ustimenko

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

  • Cc dimpase added

comment:3 follow-up: Changed 2 years ago by dcoudert

Why are you using const int m ? any particular reason ?

you must add tests to check the validity of input parameters.

Instead of for v in G.vertices(sort=False), you can simply do for v in G which iterates over the unsorted vertices., And instead of G.neighbors(v), you can use G.neighbor_iterator(v)`.

a few pep8 issues like

  • (2*m-2,q) -> (2 * m - 2, q)
  • ({m},{q}) -> ({m}, {q})
  • (%d,%d,%d)"%(e,m,q) -> (%d, %d, %d)"%(e, m, q)

comment:4 Changed 2 years ago by git

  • Commit changed from 33bb6a5e15d8aefc19049d0f3fad4885444571bb to efa934018e31d3af05aec092310a1e51c6ca7d1d

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

e410f11remove comment from doctest
efa9340some code formatting

comment:5 in reply to: ↑ 3 ; follow-up: Changed 2 years ago by gh-Ivo-Maffei

Replying to dcoudert:

Why are you using const int m ? any particular reason ?

The idea is that Cython is faster when static typing is used. Not sure how much of a gain is in these python-full functions. However, I believe that types are great as they give the reader useful info.

you must add tests to check the validity of input parameters.

Do you mean doctests or checks inside the functions? For the latter there shouldn't be any need as errors will get raised from the functions used inside.

Instead of for v in G.vertices(sort=False), you can simply do for v in G which iterates over the unsorted vertices., And instead of G.neighbors(v), you can use G.neighbor_iterator(v)`.

These are good things to know and I updated the code. Is there any benefit in using them?

a few pep8 issues

I think I got them all fixed now.

comment:6 Changed 2 years ago by git

  • Commit changed from efa934018e31d3af05aec092310a1e51c6ca7d1d to be1896327f9ef6bf4c14e5404d3e019f377e49ef

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

be18963added some sig_checks

comment:7 in reply to: ↑ 5 Changed 2 years ago by dcoudert

Replying to gh-Ivo-Maffei:

Replying to dcoudert:

Why are you using const int m ? any particular reason ?

The idea is that Cython is faster when static typing is used. Not sure how much of a gain is in these python-full functions. However, I believe that types are great as they give the reader useful info.

I agree that this way the type of input is checked, but I don't think you can expect any speed up here.

you must add tests to check the validity of input parameters.

Do you mean doctests or checks inside the functions? For the latter there shouldn't be any need as errors will get raised from the functions used inside.

I mean in the function, but if your are sure that functions called inside this method will raise errors in all cases, then it should be ok.

Instead of for v in G.vertices(sort=False), you can simply do for v in G which iterates over the unsorted vertices., And instead of G.neighbors(v), you can use G.neighbor_iterator(v)`.

These are good things to know and I updated the code. Is there any benefit in using them?

for v in G is equivalent to for v in G.vertex_iterator(). So it iterates over the vertices without assumption on the order of the vertices. So far, G.vertices() returns a (sorted) list of vertices. So when you call for v in G.vertices(sort=False):, you first build the list of vertices and then iterate over it. It's equivalent to for v in list(G) or for v in list(G.vertex_iterator()). Building this list is a waste of space and time here.

This is different for edges as now G.edges() returns an object of type EdgesView enabling to iterate over the edges without building the list. So for e in G.edges(sort=False) and for e in G.edge_iterator() are now similar. In the future, G.edge_iterator() will certainly also return a EdgesView.

I don't have gap installed on my laptop yet, so I let Dima check that every think is ok :P

comment:8 Changed 2 years ago by dimpase

Can we have naming scheme and location of DualPolarOrthogonalGraph (to be renamed OrthogonalDualPolarGraph) consistent with UnitaryDualPolarGraph and SymplecticDualPolarGraph, which are in sage/graphs/generators/classical_geometries.py ?

comment:9 follow-up: Changed 2 years ago by gh-Ivo-Maffei

Should I move also the UstimenkoGraph since is the distance 1-or-2 graph of the SymplecticDualPolarGraph?

comment:10 Changed 2 years ago by git

  • Commit changed from be1896327f9ef6bf4c14e5404d3e019f377e49ef to d7453fa0517deeeb16511216f5a91b08b04409d4

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

19b859emoved and renamed orthogonal dual polar
d6a403bMerge branch 9.2.beta8 into 30303
d7453faremoved cython code; added imports

comment:11 in reply to: ↑ 9 Changed 2 years ago by dimpase

Replying to gh-Ivo-Maffei:

Should I move also the UstimenkoGraph since is the distance 1-or-2 graph of the SymplecticDualPolarGraph?

No, I think it's OK with UstimenkoGraph as it is now.

comment:12 Changed 2 years ago by dimpase

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

looks good, thanks.

comment:13 Changed 2 years ago by vbraun

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