Gecol aims at providing
CFFI
bindings to allow for constraint programming in Lisp using
Gecode.
The intended API will be quite low-level, on which other layers can be built.
Currently, we are targeting Gecode 1.3.1.
07.12.2006: A very preliminary version of the codebase has been uploaded.
Suggestions are very welcome.
For the time being, you can only work with finite domain integers -
although limited, this should already allow to solve a range of problems.
Be careful however, the API might still change....
This project has not released any files.
Source code is held in a Darcs repository at:
http://common-lisp.net/project/gecol/darcs/gecol.
You can find more information on how to use darcs at the DarcsWiki.
You can browse the code through its DarcsWeb interface.
For most up-to-date and further examples see examples.lisp
First, we load it:
? (oos 'load-op :gecol) [...]
Please note: The following examples are currently out-of-date,
but they should give a general idea.
Let's start with the cartesian product of three integer variables
that each have a domain of (1 2 3):
? (defun cartesian-product () ;; create a search space of 3 integer variables ;; in the range [1,3] and 0 boolean variables (let ((s (gecol:create-space 3 1 3 0 0))) ;; determines the order, how values are chosen, ;; when distributing a variable (gecol:gec-branch-vars-min s) ;; create a search-engine that can be queried ;; for the next solution (let ((e (gecol:create-search-engine s))) (loop for sol = (gecol:search-next e) ;; a null-pointer means there is no more solution until (cffi:null-pointer-p sol) ;; access the current solution do (format t "~a, ~a, ~a~%" (gecol:space-read-int sol 0) (gecol:space-read-int sol 1) (gecol:space-read-int sol 2)) do (gecol:dispose-space sol)) (gecol:dispose-search-engine e) (gecol:dispose-space s)))) CARTESIAN-PRODUCT ? (cartesian-product) 1, 1, 1 1, 1, 2 1, 1, 3 1, 2, 1 1, 2, 2 1, 2, 3 1, 3, 1 1, 3, 2 1, 3, 3 2, 1, 1 2, 1, 2 2, 1, 3 2, 2, 1 2, 2, 2 2, 2, 3 2, 3, 1 2, 3, 2 2, 3, 3 3, 1, 1 3, 1, 2 3, 1, 3 3, 2, 1 3, 2, 2 3, 2, 3 3, 3, 1 3, 3, 2 3, 3, 3 NIL
Same as above, but with an additional distinct constraint:
? (defun distinct () (let ((s (gecol:create-space 3 1 3 0 0))) ;; distinct - we pass the indices of the integer variables (gecol:gec-distinct s (list 0 1 2) :icl-def) (gecol:gec-branch-vars-min s) (let ((e (gecol:create-search-engine s))) (loop for sol = (gecol:search-next e) until (cffi:null-pointer-p sol) do (format t "~a, ~a, ~a~%" (gecol:space-read-int sol 0) (gecol:space-read-int sol 1) (gecol:space-read-int sol 2)) do (gecol:dispose-space sol)) (gecol:dispose-search-engine e) (gecol:dispose-space s)))) DISTINCT ? (distinct) 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 NIL ?
Force the three variables to be sorted:
? (defun sorted () (let ((s (gecol:create-space 3 1 3 0 0))) ;; v0 < v1 (gecol:gec-rel-var s 0 :irt-< 1 :icl-def) ;; v1 < v2 (gecol:gec-rel-var s 1 :irt-< 2 :icl-def) (gecol:gec-branch-vars-min s) (let ((e (gecol:create-search-engine s))) (loop for sol = (gecol:search-next e) until (cffi:null-pointer-p sol) do (format t "~a, ~a, ~a~%" (gecol:space-read-int sol 0) (gecol:space-read-int sol 1) (gecol:space-read-int sol 2)) do (gecol:dispose-space sol)) (gecol:dispose-search-engine e) (gecol:dispose-space s)))) SORTED ? (sorted) 1, 2, 3 NIL
Again unconstrained cartesian product, but with another
value ordering:
? (defun cartesian-product-distr-max () (let ((s (gecol:create-space 3 1 3 0 0))) ;; !! (gecol:gec-branch-vars-max s) (let ((e (gecol:create-search-engine s))) (loop for sol = (gecol:search-next e) until (cffi:null-pointer-p sol) do (format t "~a, ~a, ~a~%" (gecol:space-read-int sol 0) (gecol:space-read-int sol 1) (gecol:space-read-int sol 2)) do (gecol:dispose-space sol)) (gecol:dispose-search-engine e) (gecol:dispose-space s)))) CARTESIAN-PRODUCT-DISTR-MAX ? (cartesian-product-distr-max) 3, 3, 3 3, 3, 2 3, 3, 1 3, 2, 3 3, 2, 2 3, 2, 1 3, 1, 3 3, 1, 2 3, 1, 1 2, 3, 3 2, 3, 2 2, 3, 1 2, 2, 3 2, 2, 2 2, 2, 1 2, 1, 3 2, 1, 2 2, 1, 1 1, 3, 3 1, 3, 2 1, 3, 1 1, 2, 3 1, 2, 2 1, 2, 1 1, 1, 3 1, 1, 2 1, 1, 1 NIL
Back to Common-lisp.net.