MuPADCombinatWiki

The BitSet Dynamic Module.

For my own Research, I need to deals with two differents but closely related objects

subsets of {1..N};
undirected graphs;

For dealing with graphs there exists a program called nauty http://cs.anu.edu.au/bdm/nauty that is designed for computing the automorphism group of a graph, and that also allows to compute an canonical labelling. Note that nauty store graphs as array of bitfield, that encode the subsets of ajacencies. For example, the graph

              *---*---*---*
              0   1   2   3

Is stored as an array of four 32 bits C/C++ unsigned int whose binary expansion is

   0000 0000  0000 0000   0000 0000  0000 0010
   0000 0000  0000 0000   0000 0000  0000 0101
   0000 0000  0000 0000   0000 0000  0000 1010
   0000 0000  0000 0000   0000 0000  0000 0100

Which corresponds to the adjacency lists

          [{1},{0,2},{1,3},{2}]

The question is how to wrap sur C/C++ arrays of long integers into a MuPAD objects. Of course, I need this to be as efficient as possible with respect to time and memory. I hope to deal with the full set of graphs over 10 vertices...

To resume what is needed is a way to wrap a C long int array of variable lenght into a MuPAD object such that the object is correctly handled by the memory management system (alloc, copy and free). All the manipulation on the object are done by the dynamic module.

!!Two possibilities

Stephan suggest that :

According to my experience, bit arrays are best stored as integers in MuPAD. However, this means that you have to call PARI functions (like bitttest) directly without using the standard interface of dynamic modules, and consequently, your module will not work under Windows.

It seems that there is another hack which is demosntrated on the MuPAD server

http://www.mupad.de/BIB/ONLINE/SORGATZ98/demo/MFP/index.shtml The hack in mfp.C never ``really'' worked. When comparing objects of user-defined type, the kernel ignores those parts where this code stores its data, so it is impossible to store data of such type in a set, say.

OK so I used the other methods.

The bitSetSize Module

After some difficulties to start, I manage to build some working

dynamic module. The first one may be of general interest, so I would like to advertise a little bit, hopping to have some comment.

In combinatorics but not only, we often need to deals with subset

of {$0..sz} for a given number sz of also with subset of N. The MuPAD structure DOM_SET as the advantage to be sparse, but is relatively slow (at least for my intended usage). A more speed efficient approach is to store such sets as dense bitfields. So the aim of this first module is to build a new domain bitSetSize of such subset. At the creation the size is fixed, and you only can add or remove element within this size. Here is an example of usage:

>> bla := bitSetSize(3, [2]);
                           bitSetSize(3, {2})
>> bli := bitSetSize(3);
                            bitSetSize(3, {})
>> bli := bitSetSize::addElement(bli, 2);
                           bitSetSize(3, {2})
>> bool(bla=bli);
                                  TRUE
>> bitSetSize(3, {1,2}) intersect bitSetSize(3, {2});
                           bitSetSize(3, {2})
>> bitSetSize::addElement(bli, 1);
                          bitSetSize(3, {1, 2})
>> bitSetSize::addElement(bli, 4);
Error: Invalid argument [bitSetSize_mod::addElement]

I think this can be useful in many places. Though the module

fulfill my need, it probably has to be extended. Thus, I've many

design questions

Is this module needed elsewhere, should I rewrite the needed part of nauty ?
Is the restriction of fixed size a good idea. Should I remove it or add a resize function. I plan to build an other module can bitSet with auto resizing. Any comment ?
Here is the current interface anything else is needed ?

doc, new, op, nops, size, toSet, expr, print, full, isEmpty, addElement, delElement, nextElement, flipElement, _union, _minus, _intersect, complement
All the data are stored into a PARI number which is encapsulated into a mupad domain element, adding one more level of indirection. Is it a problem ?
What is the good way of integrating external software such as nauty into MuPAD-Combinat ?

Finally here is the first try of the help page ==========================================

MODULE
  bitSetSize -- MuPAD dynamic module for bitSet of fixed size

INTRODUCTION

  This dynamic module deals with set of integers of fixed size, that
  is given a nonnegative integer sz, it deal with subset of the set
  {$0..zs-1}. The bitSet are stored in a dense bit-field structure.

  This dynamic module is a part of the MuPAD-Combinat project.
  see http://mupad-combinat.sourceforge.net/

AUTHOR
  Florent Hivert <Florent.Hivert@univ-mlv.fr>

INTERFACE

   doc, new, op, nops, size, toSet, expr, print,
   full, isEmpty, addElement, delElement, nextElement, flipElement,
   _union, _minus, _intersect, complement


<!-- BEGIN-FUNC new -->
NAME
  bitSetSize::new - create a new bitSet of fixed size

SYNOPSIS
  bitSetSize(sz)       : create a new empty bitSet of size sz
  bitSetSize(sz, set)  : create a new bitSet of size sz, whose
                         elements are given in set.
  bitSetSize(sz, list) : create a new bitSet of size sz, whose
                         elements are given in list.

PARAMETERS
  sz: non-negative integers
  set: a MuPAD subset of {$0..sz-1}
  list: a MuPAD list of with element from the set{$0..sz-1}

DESCRIPTION
  Returns a bitSet of fixed size sz. If set or list is given the
  bitSet contains the elements given set or list. Otherwise the bitSet
  is empty. If list is given, it has not to be sorted, and it may also
  have repetitions.

EXAMPLE
  Create the empty set of size 10

  >> bitSetSize(10);

                          bitSetSize(10, {})

  Create the empty set of size 10, with element 2,4,7

  >> bitSetSize(10, [2, 4, 7]);

                       bitSetSize(10, {2, 4, 7})

SEE ALSO

<!-- END-FUNC -->

Bit Set

The BitSet Dynamic Module.

The bitSetSize Module