gecol

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.

News

Mailing Lists

Download

This project has not released any files.

Darcs

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.

Examples

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.

Valid XHTML 1.0 Strict