# [binset.h] Type: Binary Set

## contents

#include "standard.h"

## Types and macros

The elements in a binary set M with card(M) = N are represented by the numbers 0 .. N-1.

BS_Set | Abstract binary set type

Element, row and column index

    #define BS_RELEL(l,r,maxC)      ( ( ( ( l ) - 1 ) * ( maxC ) ) + ( r ) )
                                    /* r = SetElement 1 .. maxC */
                                    /* l = SetElement 1 ..      */
    #define BS_RIDX(v,maxC)         ( ( ( v ) - 1 ) / ( maxC ) + 1 )
    #define BS_CIDX(v,maxC)         ( ( ( v ) - 1 ) % ( maxC ) + 1 )

## Basics

    BS_Set BS_init(BS_Set set)

initializes set

    BS_Set BS_create(INT card)

creates a binary set

    INT BS_card(BS_Set set)

cardinality of set

    void BS_delS(BS_Set set)

deletes set

## Operations and predicates on one set

    INT BS_setE(INT element, BS_Set set)

adds element to set

    void BS_delE(INT element, BS_Set set)

deletes element from set

    c_bool BS_member(INT element, BS_Set set)

element in set ?

    c_bool BS_empty(BS_Set set)

empty set ?

    INT BS_cnt(BS_Set set)

number of elements in set

## Operations and predicates on two sets

    c_bool BS_equal(BS_Set left, BS_Set right)

left = right ?

    c_bool BS_subset(BS_Set left, BS_Set right)

left <= right ?

    BS_Set BS_copy(BS_Set dst, BS_Set src)

copies src to dst

    BS_Set BS_union(BS_Set dst, BS_Set left, BS_Set right)

dst = left U right

    BS_Set BS_minus(BS_Set dst, BS_Set left, BS_Set right)

dst = left - right

    BS_Set BS_inter(BS_Set dst, BS_Set left, BS_Set right)

dst = left & right

## Binary graph

    INT BS_setGE(BS_Set rel, INT SetCard, INT from, INT to)

adds a vertice, requires initialized rel

    BS_Set BS_setG(BS_Set rel, INT SetCard, c_bool (*isRel)(INT from, INT to))

adds vertices, requires initialized rel

    BS_Set BS_copyR(BS_Set rel, BS_Set set, INT row, c_bool toGraph)

copies set to rel[row] (toGraph = True), rel[row] to set (toGraph = False)

    INT BS_findR(BS_Set rel, BS_Set set)

searches row with rel[row] = set, returns
row = 1 .. ( BS__CARD(rel) / BS__CARD(set) ) oder 0

The following functions require binary relations over a single domain.

    BS_Set BS_trans(BS_Set rel, INT SetCard)

reverse relation / transponent matrix rel'

    BS_Set BS_rclosure(BS_Set dst, BS_Set rel, INT SetCard)

reflexive closure dst = rel U id

    BS_Set BS_sclosure(BS_Set dst, BS_Set rel, INT SetCard)

symmetric closure dst = rel U rel'

    BS_Set BS_iclosure(BS_Set dst, BS_Set rel, INT SetCard)

(Warshall in N*N-Platz, vgl. Mehlhorn) transitive closure dst = rel+

    BS_Set BS_closure(BS_Set dst, BS_Set rel, INT SetCard)

(Warshall) transitive, reflexive closure dst = rel*

    BS_Set BS_eclosure(BS_Set dst, BS_Set rel, INT SetCard)

equivalence relation dst = (rel U rel')*

    BS_Set BS_kern(BS_Set dst, BS_Set rel, INT SetCard)

kernel dst = rel\square(rel), requires rel = strict order