diff options
authorRelease Manager <>2015-08-05 12:52:22 +0200
committerVolker Braun <>2015-08-05 12:52:22 +0200
commit1b01a852c389bf9959e552e0e90efbf3153a30a9 (patch)
parentTrac #18989: Incorrect input_alphabet in FiniteStateMachine.disjoint_union (diff)
parenttrac #18948: Broken doctest (diff)
Trac #18948: Strongly Regular Graphs database
This ticket implements a new module names `strongly_regular_db` that lets us build one example of strongly regular graph, given four integer parametes (v,k,lambda,mu). It uses Andries Brouwer's database to return more meaningful non- existence results, and help us find which constructions are missing from the database. With a bit of luck (and time, and work) it would be great if we could reproduce all SRG that are known to exist! The module has a simple structure: has a simple structure: - A `seems_feasible(v,k,l,mu)` function that performs the basic artihmetic checks to figure out if `(v,k,l,mu)` is realizable. The 'apparently_feasible_parameters(n)` returns the lists of all parameters that pass these tests for v<n. When n=1301, the set of parameters it returns is precisely those that appear on your database (this is checked in the code). - Several functions (is_paley, is_johnson, ...) test if a given set of parameters (v,k,l,mu) can be realized with a graph of the corresponding family (a Paley graph, a Johnson graph, ...). If they can, they return the parameters of that graph so that it can be built easily. - The main function `strongly_regular_graph` can be called in two ways: - `strongly_regular_graph(v,k,l,mu,existence=True)` answers True if such a graph is known to exists, False if it is known to be infeasible, and Unknown otherwise. - `strongly_regular_graph(v,k,l,mu)` attempts to build and return the requested graph, and returns a meaningful exception if it cannot. This branch also updates the package 'graphs', which now ships the database in json format. Nathann URL: Reported by: ncohen Ticket author(s): Nathann Cohen Reviewer(s): Dima Pasechnik