search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

Usainboltz package: fast Boltzmann random generation of tree-like structures #27526

Open Kerl13 opened 5 years ago

Kerl13 commented 5 years ago

Usain Boltz is a !Python/Cython/C++ library that automates the random generation of tree-like structures. It allows to describe a combinatorial structure using a specification in the style of “Analytic Combinatorics” and, using the Boltzmann sampling framework, it produces a fast, uniform, and approximate size sampler of objects described by this specification.

https://gitlab.com/ParComb/usain-boltz

Depends on #34251

CC: @sagetrac-tmonteil @MatthieuDien @Kerl13 @mantepse

Component: packages: optional

Author: Martin Pépin, Matthieu Dien

Branch/Commit: u/MartinPepin/usainboltz @ d8e42b9

Reviewer: Thierry Monteil

Issue created by migration from https://trac.sagemath.org/ticket/27526

Kerl13 commented 5 years ago

Branch: u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Commit: 693df81

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

693df81Boltzmann sampling: module-wide documentation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

75ec37cUse sage's randstate API for random number generation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 693df81 to 75ec37c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 75ec37c to 8b40cc1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

8b40cc1Boltzmann: document the generator module
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

b798133Boltzmann(Grammar): `labelled` optional argument
1c7b6b0Integrate Boltzmann's doc into the reference manual
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 8b40cc1 to 1c7b6b0

MatthieuDien commented 5 years ago

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

Kerl13 commented 5 years ago

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

MatthieuDien commented 5 years ago

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

Kerl13 commented 5 years ago

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

1da6bd2Boltzmann(Oracle): pep8 + fix doctests
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 1c7b6b0 to 1da6bd2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 1da6bd2 to 5303f2a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

5303f2aBoltzmann: fix import statements in doctests
MatthieuDien commented 5 years ago

Description changed:

--- 
+++ 
@@ -1 +1,13 @@
+The Boltzmann method is a framework whose describe how to build a uniform random generator for a family of discrete structures from a grammar describing  that family.

+Our goal is to design a high-level and user-friendly API with :
+* handling of grammars for monovariate/multivariate and unlabeled/labeled/increasingly labeled structures.
+* use of the state of the art oracles (newton iteration, multiparametric tuning, etc)
+* fast sampling of large structures (size 1e6 and more)
+ 
+In this ticket we provide a implementation of the Boltzmann method introduced by Duchon, Flajolet, Louchard and Schaeffer (see [DuFlLoSc04](http://algo.inria.fr/flajolet/Publications/DuFlLoSc04.pdf)) with the following features :
+* labeled and unlabeled classes defined with +, *, Seq and recursive definition
+* an oracle dealing with explicit generating function
+* an oracle based on the work of Darasse (see [his thesis](http://www.ortsa.com/lip6_these/docs/these.pdf)) : less accurate but more generic
+* a fast Cython implementation of a generic generator
+
MatthieuDien commented 5 years ago

Changed author from Martin Pépin to Martin Pépin, Matthieu Dien

MatthieuDien commented 5 years ago

New commits:

5303f2aBoltzmann: fix import statements in doctests
Kerl13 commented 5 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-The Boltzmann method is a framework whose describe how to build a uniform random generator for a family of discrete structures from a grammar describing  that family.
+The Boltzmann method is a framework that describes how to build a uniform random generator for a family of discrete structures from a grammar describing  that family.

 Our goal is to design a high-level and user-friendly API with :
 * handling of grammars for monovariate/multivariate and unlabeled/labeled/increasingly labeled structures.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 5303f2a to 04ca7e6

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

b648771Fix various generator bugs
04ca7e6Boltzmann(Generator): towards labellings
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 04ca7e6 to a25d00c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

71271d4Boltzmann: first implementation of labellings
a25d00cBoltzmann: clean the generator, labelling works
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

b94b94aBoltzmann: default builders show the labels
70e9b92Boltzmann: shuffle the labels of an atom of size >1
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from a25d00c to 70e9b92

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

0a058e1Boltzmann: more tests
db4b2a9Boltzmann: various oracle fixes
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 70e9b92 to db4b2a9

MatthieuDien commented 5 years ago

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

Kerl13 commented 5 years ago

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

2b13bfcBoltzmann: move the labelling information to the atoms
b453c34Boltzmann: Grammar.atoms()
d20b9dcBoltzmann: implement multi-labellings
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from db4b2a9 to d20b9dc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from d20b9dc to a92c66b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

a92c66bBoltzmann: more docs + doc fixes
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

f42a856Boltzmann: TODO list
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from a92c66b to f42a856

MatthieuDien commented 5 years ago

Changed branch from u/gh-Kerl13/boltzmann_samplers_for_combinatorial_grammars to u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars

fchapoton commented 5 years ago

Changed commit from f42a856 to b55d493

fchapoton commented 5 years ago
comment:24

Please have a look at the patchbot warnings (click on the color round icon on top of the page) and in particular the plugins results.

New commits:

b55d493moving the todo list in "our" directory
mantepse commented 2 years ago
comment:27

Hi Martin!

the species implementation is currently undergoing the long awaited overhaul. Travis and I have just finished a lazy series implementation, which is much more robust than what we had previously. Ticket #32367 replaces the old (and somewhat unreliable) LazyPowerSeries with our new one.

Do you think we should try to see whether a uniform user interface for defining a grammar is possible?

edd8e884-f507-429a-b577-5d554626c0fe commented 2 years ago
comment:28

Replying to Martin Rubey:

Hi Martin!

the species implementation is currently undergoing the long awaited overhaul. Travis and I have just finished a lazy series implementation, which is much more robust than what we had previously. Ticket #32367 replaces the old (and somewhat unreliable) LazyPowerSeries with our new one.

Do you think we should try to see whether a uniform user interface for defining a grammar is possible?

Hi all ! To be transparent, we had an informal discussion this afternoon with Martin Pépin about that same issue !

If you remember, a long time ago (before covid), i proposed to have a general meeting of all people interested in making a plan for the whole analytic combinatorics stuff in Sage (species, ore algebras, (multi-variate, lazy, etc) power series, Bolzmann samplers, singularity analysis, asymptotic expansions, etc). Most people answered positively but wanted to postpone the date, unfortunately the delays were too short as the grant was ending. Maybe, we could revive the idea. What do you think ?

mantepse commented 2 years ago
comment:29

I am all for it! I have no teaching in February. Until then, zoom and email is fine for me!

Kerl13 commented 2 years ago
comment:30

Hi!

First an important note: Matthieu and I (temporarily) moved away from this ticket about 3 years ago as we decided to implement a standalone python library available here (usainboltz). This means that the branch tied to this ticket is obsolete and should not be used.

That being said:

  1. It doesn't prevent us from adding usainboltz to sage! Adding it as an optional package seems right to me (is it?)

  2. I agree with you that having a uniform user interface for defining grammars would be great. And the species, if they work, seem to be a very good candidate to me. I'd love to see some nice integration with usainboltz (and other existing tools) so that sampling objects described by a species becomes as simple as:

>>> sampler = my_specy.get_boltzmann_sampler()
>>> sampler(size_in=[1000, 2000])
<some big object>

I'm all in to work on this as well!

Kerl13 commented 2 years ago

Changed branch from u/MatthieuDien/boltzmann_samplers_for_combinatorial_grammars to u/MartinPepin/usainboltz

Kerl13 commented 2 years ago

Changed commit from b55d493 to 08202bc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

e72b3a7Add usainboltz as an optional package
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 08202bc to e72b3a7

Kerl13 commented 2 years ago
comment:33

I added usainboltz as a pip package following https://doc.sagemath.org/html/en/developer/packaging.html#python-based-packages.

But something must be wrong with what I did, I can't install usainboltz using sage -i:

$ ./sage -i usainboltz
[ a log of log about sage checking if it needs to rebuild stuff ]
Error: package 'usainboltz' not found
Note: if it is an old-style package, installing these is no longer supported

Note that ./sage --optional and ./sage --info usainboltz both see usainboltz. I might need a bit of help to understand what is happening.

edd8e884-f507-429a-b577-5d554626c0fe commented 2 years ago
comment:34

It worked well for me, i could successfully execute binarytrees.ipynb.