Title of Package

Denys Duchier - Kurt Mehlhorn

provides

x-ozlib://duchier/cp/mehlhorn/Mehlhorn.ozf

requires

LEDA Library

Purpose

This module provides a satisfiability test for a class of dominance constraints.

{Mehlhorn.satisfiable +N +Nodes +Edges ?Answer}

N is the number of nodes. Each node is denoted by an integer between 0 inclusive and N exclusive. Nodes is a list of pairs I#K where I denotes a node and K is the `kind' of the node represented as the integer 0, 1, or 2 according to whether the kind is root, leaf, or interior respectively. Edges is a list of triples I#J#B where I denotes the source node, J the target node, and B is a boolean which is true iff the edge is solid. Answer is either true if the dominance constraints are satisfiable, or else it is the representation of a falsifying cycle in the form of a list of pairs I#J representing the edges involved in the cycle.

{Mehlhorn.satisfiableNative +N +Nodes +Edges ?Answer}

This is the same as the above, but without any type checking or synchronization. Use at your own risk.

Installation

Assuming LEDA support has been installed (see below), this package can be installed by following the usual configure, build, install procedure, i.e. by executing a the shell: ./configure make install By default, all files of the package are installed in the user's ~/.oz directory tree. In particular, all modules are installed in the user's private cache.

in order for this package to be compilable and runnable, LEDA support for mozart must be installed. This can be accomplished as follows:

1. download the LEDA binary tarball for your platform and unpack in some directory. Let's call this directory LEDA_UNPACKED

2. configure this present package using the --with-leda option argument: ./configure --with-leda=LEDA_UNPACKED
3. install leda support: make install.leda