Linear Code's covering_radius method forces the use of optional package Guava

[dlucas]

The method covering_radius for linear codes (in linear_code.py), uses optional package Guava for Gap by default.

If this package is not installed, the method crashes without a proper error message.

This ticket proposes a reimplementation of covering_radius, with a generic algorithm written in Python. If Guava is not installed on the user's system, it uses the generic algorithm, else it uses the Guava one.

[dlucas]

I pushed the patch, this is now open for review.

---

New commits:

​ce9b19c

Rewrote covering_radius method to have a non-guava implementation

[git]

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

​c13dc05

covering_radius is now a cached method

[dlucas]

As computing the covering radius is quite slow, I made this method a cached method. This is still open for review.

[ncohen]

Could you only nest inside of the try/except what needs to be, i.e. the 'load_package' command?

As it is, any 'RuntimError?' raised by another line would be interpreted as a missing package, though it may well have another cause.

Thanks,

Nathann

[ncohen]

Alternatively, there is this trick that Dima used somewhere else:

if not bool(libgap.LoadPackage("grape")):
    <code>

[git]

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

​37dad1a

Better test to check if Guava is installed

[dlucas]

Hello,

Thanks for your remark! I picked Dima's trick and fixed my code.

David

[git]

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

​88f0d6f	Update to 7.0
​654b4e2	Fixed bug with check on Guava

[dlucas]

It actually seems that

if not bool(libgap.LoadPackage("Guava")):
    <code>

calls an error message which invites the user to install Guava if it's not installed.

Anyway, I went back to a (proper) try-except block.

[git]

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

​15a108c

Merged with latest beta and fixed conflict

[dlucas]

I updated this ticket to the latest beta and fixed merge conflict. This is still open for review.

[danielaugot]

Hi

this is incredibly slow, up to the point of being not usable. Yet the code is correct, works on very small instances, and tests are passed.

I send the status to positive review.

Daniel

[vbraun]

Reviewer name is missing

[dlucas]

Before setting to positive_review again, please read comment 13 on #21339.

[ylchapuy]

You might also look at this implementation: ​u/ylchapuy/coset_leaders

[ylchapuy]

We don't really need Guava, there's all we need in gap.

I provide a sample implementation but it's buggy (try it with the code codes.ExtendedQuadraticResidueCode(17, GF(4)))

The branch up there could also be used in #21339 , and in the method _build_lookup_table from linear_code.py

This branch is quite efficient and computes the 177147 coset_leaders of a random linear code [30, 19] over GF(3) in less than 4 seconds, and the covering radius (5 in my example) in 3 seconds.