[GAP Forum] Partition backtrack

[Christopher Jefferson]

I am working on such a library, which can be found here:

https://github.com/gap-system/ferret


This code is currently a GAP library, but it is designed so it can be used without GAP (I also use it for Graph Isomorphism testing). The library is in the YAPB++ directory, the code in src links this to GAP.

There are a small number of calls in the YAPB++ code back into GAP -- the main one is to generate a base + strong generating set for a group (there are obviously other implementations of this available).

The code is (I believe) tested and complete, although I continue to add new extensions which improve the performance beyond that of existing implementations.

I have not yet tried building this code multi-threaded, but I believe it should not cause any great problems (it is a long term plan, but I was waiting while HPC-GAP before further stable, as the main current use of this library is to replace the partition backtrack code in GAP).

This code implements currently the actions OnSets, OnSetsSets, OnSetsTuples and OnTuplesSets. Implementing others is easy.

The code does not yet implement RepresentativeAction, but I aim to implement it shortly -- the code is missing coset search and I have no yet bothered to add it.

An alternative to RepresentativeAction worth considering is CanonicalImagePerm, from my and Steve Linton's images package:



https://github.com/gap-system/images


This function returns a permutation and guarantees, given a group G, and sets S and T such that there exists g in G such that S^g = T that:

S^CanonicalImagePerm(G, S) = T^CanonicalImagePerm(G,T)

This can be used to find a mapping from S to T, and in particular can be more efficient if you have a list of sets S1, S2, ... , Sn, and want to place them into equivalence classes.

This code is however currently just GAP code. It would be easy to turn into C++ give an implementation of strong+base generating set, and change of basis, and that is where the majority of the time is spent in the algorithm.

Please let me know if you have any questions, or feedback if you look at the code -- in particular it is not really documented, and I would be happy to add some internal documentation if that would be useful.

Chris

On 26/08/2015, 09:19, "forum-bounces at gap-system.org on behalf of Mathieu Dutour" <forum-bounces at gap-system.org on behalf of mathieu.dutour at gmail.com> wrote:

>I would like to have a C/C++ library code which implements partition
>backtrack for computing Stabilizer/RepresentativeAction for the actions
>OnSets.
>
>This work seems to have its origin in the work of Jeffrey S. Leon as
>described in his paper "Permutation group algorithms based on partitions".
>and all source code originates from it. There is another code in permlib
>but it has performance problems.
>
>What are the variants of the code right now? I can think of several right
>now:
>---The code of guava3.12 which contains the original code of leon.
>---The C-code of GAP.
>---The code in sage. But it is written in Cython and so available only
>    via Python.
>As a side remark, the guava code provides partition backtrack for
>the action OnSetsSets, which is not in GAP as far as I know.
>
>The code of guava is the nearer to my needs but it has a number of problems:
>---It is a standalone binary and not a library, Adapting it to a library is
>a non-trivial work since there are many global variables.
>---It uses static variables which prevents it being included in a parallel
>program
>---It has performance problems in some small cases (48 points) for testing
>equivalence (GAP has no problem at all).
>---There are some segmentation faults in the program.
>
>What would be your recommendation for having a good C++ library
>for partition backtrack, that is: fast, clean and usable in parallel
>programs?
>
>  Mathieu
>_______________________________________________
>Forum mailing list
>Forum at mail.gap-system.org
>http://mail.gap-system.org/mailman/listinfo/forum