Opened 10 years ago
Closed 8 years ago
#10896 closed enhancement (duplicate)
Strongly Regular Graph
Reported by: | pgdx | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | srg strongly regular graph |
Cc: | ncohen | Merged in: | |
Authors: | Reviewers: | Travis Scrimshaw | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
I have been missing a function/method in the Graph class that allows you to test whether or not a graph is strongly regular.
A graph is strongly regular, or srg(n,k,l,m) if it is a regular graph on n vertices with degree k, and every two adjacent vertices have l common neighbours and every two non-adjacent vertices have m common neighbours. Examples are PetersenGraph? (10,3,0,1), the 5-Cycle (5,2,0,1), the Shrikhande graph (16,6,2,2) with more. For information on strongly regular graphs read on Wikipedia.
I have written a function, with documentation, that tests if a graph is strongly regular. The functions have optional arguments: n,k,l,m,certificate. More on this is to be found in the attached file.
The only thing that needs to be done is testing it and making it into a method of Graph, instead of a function, i.e. remove "g" from its argument list and rename all function calls g.* to this.*
Hope to see this path upstream as soon as possible.
I hereby give Sage community full copyright and other possible ownerships.
Attachments (3)
Change History (12)
Changed 10 years ago by
comment:1 Changed 10 years ago by
I don't know if I should add a new patch, so I for now, just add a note here that we should use the parameter for is_regular, i.e.
if k is None: if not this.is_regular(): return False else: if not this.is_regular(k): return False
Also, this patch is maybe a bit slower then necessary; We fetch the neighbourhood of a vertex O(n²) times. This is simply because I don't know how to get the neighbourhood of a vertex, i.e. the vertices in its neighbourhood, not the edges it is adjacent to. The neighbourhood could be fetched in the beginning of the function, but I don't know how we deal with this kind of allocating a lot of memory.
comment:2 Changed 10 years ago by
Furthermore, if the degree_iterator is somewhat slow, we could, since we are iterating through all vertices' neighbourhood anyway, skip that test in the beginning, and do it as we go.
comment:3 Changed 8 years ago by
- Milestone set to sage-duplicate/invalid/wontfix
comment:4 Changed 8 years ago by
- Status changed from new to needs_review
comment:5 Changed 8 years ago by
- Milestone changed from sage-duplicate/invalid/wontfix to sage-5.9
There's a small bug in is_strongly_regular()
which I'm recycling this ticket for: the output block had one extra level of indentation so things like cliques would return None
instead of True
(or the parameters).
Changed 8 years ago by
comment:6 Changed 8 years ago by
- Description modified (diff)
For patchbot:
Apply: trac_10896-fix_strong_reg_graph-ts.patch
comment:7 Changed 8 years ago by
- Milestone changed from sage-5.9 to sage-duplicate/invalid/wontfix
- Status changed from needs_review to positive_review
This is a duplicate of #14297 then.
Nathann
comment:8 Changed 8 years ago by
- Reviewers set to Travis Scrimshaw
comment:9 Changed 8 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Source code containing function testing whether a graph is a Strongly Regular Graph (srg)