[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