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:

Status badges

Description (last modified by tscrim)

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.


Apply: trac_10896-fix_strong_reg_graph-ts.patch

Attachments (3)

srg.py (3.1 KB) - added by pgdx 10 years ago.
Source code containing function testing whether a graph is a Strongly Regular Graph (srg)
trac_10896_strongly_regular_graph.patch (4.1 KB) - added by pgdx 10 years ago.
Patch
trac_10896-fix_strong_reg_graph-ts.patch (1.5 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (12)

Changed 10 years ago by pgdx

Source code containing function testing whether a graph is a Strongly Regular Graph (srg)

Changed 10 years ago by pgdx

Patch

comment:1 Changed 10 years ago by pgdx

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 pgdx

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 chapoton

  • Milestone set to sage-duplicate/invalid/wontfix

comment:4 Changed 8 years ago by chapoton

  • Status changed from new to needs_review

comment:5 Changed 8 years ago by tscrim

  • Authors changed from pgdx to Travis Scrimshaw
  • 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 tscrim

comment:6 Changed 8 years ago by tscrim

  • Description modified (diff)

For patchbot:

Apply: trac_10896-fix_strong_reg_graph-ts.patch

comment:7 Changed 8 years ago by ncohen

  • 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 jdemeyer

  • Authors Travis Scrimshaw deleted
  • Reviewers set to Travis Scrimshaw

comment:9 Changed 8 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.