- 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.

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 -->

Page Execution took real: 2.009, user: 0.580, sys: 0.100 seconds |