VanderWaerden.hpp File Reference

Plans regarding generators for vdW-hypergraphs. More...

Go to the source code of this file.

Detailed Description

Plans regarding generators for vdW-hypergraphs.

  • See OKlib::Combinatorics::Hypergraphs::Generators::Pd_arithprog_ohg for the C++ implementation.
  • DONE Order of hyperedges:
    1. Currently the order is directly derived from the colexicographical ordering on the original hyperedges.
    2. For example palindromise_vdw_ohg(arithprog_ohg(3,7)) = [[1,2,3,4],[{1,2,3},{2,3,4},{1,3},{3,4},{2,4},{1,4}]].
    3. Perhaps colexicographical ordering would be better, which would be here [{1,3},{1,2,3},{1,4},{2,4},{3,4},{2,3,4}].
    4. In ComputerAlgebra/Combinatorics/Lisp/Enumeration/Order.mac we have colex_lessp_l, however this functions needs to be generalised to handle lists of different lengths.
  • DONE Perhaps subsumption-elimination should be performed. For the above example we would get [{1,3},{1,4},{2,4},{3,4}].
  • Counting the number of hyperedges: a formula for the number of hyperedges should be developed.
DONE (now the implementation is non-recursive, and in case more memory is needed, use default_memory_ecl()) Hypergraphs of arithmetic progressions
  • The current implementation of arithprog_ohg/arithprog_hg can only handle small values of n --- otherwise we get a stack-size error!
    C-STACK overflow at size 139456. Stack can probably be resized.
    (this on a 32-bit machine with 2GB memory).
  • Perhaps this is due to Ecl --- can we grow the stack size?!
    1. ulimit reports that there are no restrictions from the bash-side.
    2. There are various Ecl memory limits which are discussed in the manual - http://ecls.sourceforge.net/new-manual/re34.html#table.memory.limits .
    3. In this case the C-STACK is overflowing with a current limit of 128KB. This can be adjusted to say 1MB in the following way:
      :lisp (ext:set-limit 'ext:c-stack 1048576)
    4. MG: Please make the documentation of Ecl available (locally), document all the memory option (apparently there are five: "frame-stack, binding-stack, c-stack, heap-size, lisp-stack"; they can also be set on the command line), together with appropriate values, and move this important documentation into its right (general) place. Likely the OKlibrary should provide meta-commands, which work for all Lisps supported; perhaps just asking for one argument, the amount of memory available for Maxima, and then calculating the approriate values. One also needs to find out how to pass command-line arguments to ecl (for example "--frame-stack 4096").
    5. Compare "Reasonable memory and stack limits" in Buildsystem/MasterScript/SpecialProcessing/plans/Maxima_Init.hpp.
  • On the other hand, a non-recursive solution is also very easy to produce.
  • However, such little problems shouldn't pose a problem!

Definition in file VanderWaerden.hpp.