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.

Quick start

If you want to get a quick start, load the package into your lisp and evaluate 
CL-USER> (in-package #:DE.UUHAUS.CL-JOINTGEN)
#<The DE.UUHAUS.CL-JOINTGEN package>
CL-JOINTGEN> (with-open-file (s "instances/perms66.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.

Exported Symbol Index

check-duality, function
clause, class
clause->bitlist/lsb, function
clause->bitlist/msb, function
clause->bitvec/lsb, function
clause->bitvec/msb, function
clause-ref, function
clutter, class
hypergraph-edge-oracle, class
hypergraph-edge-oracle, type
joint-generation, function
make-sperner-hypergraph-oracle, function
mbf-oracle, class
mbf-oracle, type
query-oracle, function