Package de.uuhaus.cl-jointgen

This package provides a free and extensible implementation of Joint Generation Algorithms.

We chose Common Lisp as the implementation language to facilitate easy experimentation with the ad-hoc decisions in the implementation, and to make implementation of your favourite monotone boolean function oracle easy.

The canonical project home page is here, the SVN repository, file releases and bug tracking are hosted on SourceForge.

About This Package

Installation
Quick start
Literature
Authors

Installation

To make use of this package you will need

A Common Lisp Environment. SBCL is a good free candidate. See the ALU Wiki for a list of choices.
(Optionally) Emacs with SLIME installed.
The ASDF System definition package. If you chose SBCL above then you already have it.
This package, either as .zip file release, or from the SVN repository.

If you are using Debian GNU/Linux you can fetch the prerequistites by

apt-get install emacs slime sbcl

A one-step solution may be Lispbox.

If any of the above does not make sense to you, you may want to start learning more about Common Lisp by reading Peter Seibel's Practical Common Lisp, a great Lisp book suitable as online <a href="http://www.gigamonkeys.com/book/">Common Lisp tutorial</a> but also available in printed form with ISBN 978-1590592397.

Quick start

If you want to get a quick start, load the package into your lisp and evaluate

CL-USER> (asdf:operate 'asdf:load-op 'cl-jointgen)
; registering #<SYSTEM CL-JOINTGEN> as CL-JOINTGEN
NIL
CL-USER> (in-package #:DE.UUHAUS.CL-JOINTGEN)
#<The DE.UUHAUS.CL-JOINTGEN package>
CL-JOINTGEN> (with-open-file (s "instances/acet.lisp"
                              :direction :input)
               (joint-generation
                 (make-jg-problem/hg-oracle (read s))))
[lots of output scrolling by]

Literature

Applications are discussed in

Haus, Klamt, Stephen: Computing Knock-Out Strategies in Metabolic Networks.

If you are serious about the mathematical background read one or more of the following papers:

Fredman, Khachiyan: On the Complexity of Dualization of Monotone Disjunctive Normal Forms DOI link
Khachiyan, Boros, Elbassioni, Gurvich: An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation DOI link

Authors

This code is released under the GNU Public License with Lisp clarfications and copyrighted by Utz-Uwe Haus and Tamon Stephen. Please see the files LICENSE.GPL and LICENSE.Lisp-GPL-Preface in the distribution for details.