The KURE for your relational problems

KURE is an abbreviation for ``Kiel University Relation package''

Kure is a C library which provides manipulation of relations and operations of relation algebra using a fast implementation using binary decision diagram. It provides a Lua based domain-specific embedded programming language to conveniently manipulate and work with relations. For instance, given relations R, S, the tupling of them can be computed using [R,S] and they can be composed using R*S.

Historically, the Kure library originates from the RelView tool. Today, Kure is a standalone static library, that does not depend on any part of the RelView tool.

Features

• Representation and manipulation of arbitrary large relations, e.g. 2¹⁰⁰ x 2¹⁰⁰.
• Relational constants: All, null, identity.
• Special relations: Membership, partial and total functions, successors, domain.
• Basic functions: Join, meet, composition, complement, transpose.
• Bit level access.
• Comparison of relations and comparison of relations by cardinality.
• Manipulation and special functions of vectors (line complete relations).
• Reflexive, symmetric and transitive closures.
• Random relations, random relations without cycles and random bijections.
• Left and right residue (resp.) and symmetric quotient.
• Direct sum, tupling, product order and sum order.
• Domains for binary direct products and direct sums including projection functions.
• Fully scriptable and extensible using Lua (very fast).
• Domain-specific embedded programming language for high level scripting.

• Written in C using POSIX.
• pkg-config support.
• GNU autotools support, i.e. can be built using a configure script and GNU Make.

Download

The development of the the package takes place at http://sourceforge.net/projects/kure/. Please check out the SVN repository for the latest version of the library. The current version of the library is 2.2 which has been released in September 2012. Please consult the CHANGES file in the distribution's root directory for details on new features and bug fixes.

Help on how to compile the library can be found in doc/INSTRUCTIONS. Kure depends on the following third-party libraries:

• CUDD >=2.3.1 (FTP)
• LUA >=5.1
• GNU MP library >=4.0
• GLib 2.0

Documentation

The library comes with a Doxygen documentation which can be found in the doc/ directory. The documentation is also available online here.

Some examples as well as details on the domain-specific language can be found on Relview's project page. A list of available base functions is available there are well, e.g. syq(R,S) for the symmetric quotient of two relations R and S. Some examples are also included in the distribution: Approximation algorithms, Algorithms for orders and lattices, Graph-theoretic algorithms, Algorithms for C/E Petri nets, Recursive programs, Miscellaneous and some more.

How it looks like

#include "Kure.h"
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char ** argv)
{
  int rows, cols;
  int i, j;
  KureContext * context = NULL;
  KureRel * rel = NULL;

  printf ("Please enter the dimension of your relation, e.g. '5 9' "
          "(without quotes) for a relation with 5 rows and 9 columns:\n");

  if ( 2 != fscanf(stdin, "%d %d", &rows, &cols)) {
    printf ("First two numbers have to be the numbers of rows and cols"
        "respectively.\n");
    return EXIT_FAILURE;
  }

  /* Create a new kure2 context. Contexts are background objects which 
   * are used to manage relations internally. You should use a single
   * context for all your relations since relations in different contexts
   * cannot, for instance, be compared or used in binary operations.
   * The context has a reference count of one and has to be references,
   * for instance, if passed to LUA routines. */
  context = kure_context_new ();
  kure_context_ref (context);

  /* Create a new relation with the given size. As you will very often
   * a bunch of functions is provided to do something with as few 
   * conversions as possible. Here, we create a relation of a given size
   * (_with_size) and we use signed integers (_si). In comparison, the
   * default type to store integers is GMP's mpz_t type. */
  rel = kure_rel_new_with_size_si (context, rows, cols);
  if (rel) {

      printf ("Now, enter some pairs of numbers, for instance, '1 2' "
              "(without quotes again) to set some bits in your "
              "relation. The pair '1 2' sets the second bit in "
              "the first row. You can stop with CTRL-D at any time."
              "The relation is written to the screen afterwards:\n");

    /* Read some pairs of numbers. May separated by newlines. */
    while (!feof (stdin) && 2 == fscanf(stdin, "%d %d", &i, &j)) {

      /* Set the given bit. Again, we use signed integers here (_si). 
       * Most function in kure provide error checking. To this end, 
       * Kure_success (TRUE/FALSE) is returned. Either as the return value
       * or as an argument as in kure_get_bit_si. */
      if ( !kure_set_bit_si (rel, 1/*true*/, i,j)) {
    KureError * err = kure_context_get_error (context);
    printf ("Unable to set bit %d:%d (row,col) relation. Reason: %s.\n", 
        i,j,err?err->message:"Unknown");

    /* The error object is managed internally, so we don't have
     * to care about memory management here. */
      }
    }

    /* NULL for psuccess means that we ignore the error. This is
     * dangerous if the number of entries can exceed INT_MAX */
    printf ("The relation has %d entries.\n",
        kure_get_entries_si (rel, NULL));

    /* Print the relation to the screen. */
    for (i = 0 ; i < rows ; ++i) {
      for (j = 0 ; j < cols ; ++j) {
    if (kure_get_bit_si (rel, i,j, NULL))
      putchar('X');
    else putchar('.');
      }
      putchar ('\n');
    }
  }
  else {
    KureError * err = kure_context_get_error (context);
    printf ("Unable to create relation. Reason: %s.\n", 
        err?err->message:"Unknown");
  }

  /* Destroy the context. This also destroys all relations in this 
   * context. */
  kure_context_deref (context);

  return EXIT_SUCCESS;
}

Backward compatibility

License

Maintainer

Please send any comments, questions and bug reports to Prof. Dr. Rudolf Berghammer.