/*
File closure.c
Initially published by Mark Bowron on Math Transit.com: 13 Nov 2012.
Last updated: 16 Nov 2012.
This file is freeware, with one request:
*************************************************************************************************************
* *
* If you upgrade this program, please let me know at mathematrucker@gmail.com. *
* *
*************************************************************************************************************
File history:
*************************************************************************************************************
* *
* The original code for this program was spun together in under an hour by professional C programmer *
* and mathematician Stanley Rabinowitz in March 1996. Stan's coding pace amazed me. I would describe a *
* step in the algorithm, then, almost before I could think of the next one, after a flurry of keystrokes *
* I'd hear him saying "Okay, done. What's next?" *
* *
* Rabinowitz's original file can be found here: http://www.mathtransit.com/closure_3-96.c *
* *
* As of November 2012 all additional code is mine. The original file had 376 lines of code. This one *
* contains another 2000 or so. There are still many more features that could be added. *
* *
*************************************************************************************************************
File overview:
*************************************************************************************************************
* *
* This program takes as input a "subbase" of sets and generates from it an underlying mathematical space *
* (two types are currently available: topological, and closure space). A manually-entered seed set is *
* also needed. *
* *
* The program then generates, under certain set operations chosen from among several available, a family *
* of sets that is either closed under the operations, or so large that it halts the program. One way *
* the latter can happen is if the string length of a set's label exceeds the constant LABEL_MAX. *
* *
* Points and subsets are represented as follows. *
* *
* We assume that the points in the generated space are the numbers 1,2,3,...,SPACE_SIZE. *
* *
* Each point is represented by a bit position in an unsigned long int (in right-to-left order). *
* *
* Since the program assumes sizeof(unsigned long) = 8 bytes, every unsigned long int represents a *
* particular subset of {1,2,3,...,64} (a bit value of "1" means the point represented by that bit *
* is in the subset, whereas a value of "0" means it is not). *
* *
* Depending on the operations chosen, the program currently works for space sizes up to about 30 points. *
* *
* The program has two different "modes" of operation: manual and automatic. *
* *
* In manual mode, one seed set in one space generates a family of sets under a fixed set of operations. *
* *
* In automatic mode, various seed sets in various spaces have a fixed set of operations applied to them. *
* *
* To get a topological space, we close a given subbase under unions and intersections. In this case the *
* system of sets generated is the system of open sets in the topological space. *
* *
* To get a closure space we just close the subbase under intersections. In this case the system of sets *
* generated is the system of closed sets in the closure space. Note: when the empty set is included in *
* the subbase for a closure space, the resulting space is called a "Fréchet V-space". *
* *
* For an alternative method of computing finite topological spaces, see: *
* *
* "Computing Topologies" by L. W. Brinn, Math. Mag., 58(1985), pp. 67-77. *
* *
*************************************************************************************************************
Usage:
Strings of operator symbols determine which operators are to be applied in what order. For example, the
string "kbx" first closes the family under closure (k), then under boundary (b), then under intersection (x).
These strings are manually assigned to the global string variables close_first_fam[], close_second_fam[], and
close_third_fam[]. Note: the symbols in these strings must match precisely those assigned to the respective
operations by the constants TAKE_CLOSURES, etc.
The three global string variables above each represent one "operator batch". Each such batch continues to
repeat until the generated family of sets has received no new set after a full repetition. Once this
happens, the next batch in line (when defined) then kicks in.
At a further level out, these operator batches themselves, taken as a whole, continue to repeat until
the generated family has added no new sets through an entire repetition - assuming that the number of
repetitions has not exceeded the constant MAX_CYCLES_ZERO (the process halts otherwise).
When the operations are capable of generating an infinite family, MAX_CYCLES_ZERO is best set at a
low number like 1 or 2 to avoid letting the program write thousands of sets to the output file. Otherwise
it can be set at a higher number (like 20) to keep it from getting in the way.
But even if MAX_CYCLES_ZERO is set to too high a number and thousands of sets get generated, the program still
has another safety valve: the constant LABEL_MAX. I usually always leave its value set to 100. When the
string length of a set label exceeds LABEL_MAX, program execution halts with an error message.
The global string variables close_first_b_one[], close_second_b_one[], etc., located in the same section of
the program as the string variables mentioned above, serve a less important purpose but they are still useful.
What they do is label, in terms of operations applied to the seed set, sets in the system generated by the
subbase. Note: from here onward we shall always refer to the system of sets generated by the subbase simply
as "the system", whereas "the family" shall always mean the family of sets generated by the seed set.
This labeling process includes one extra (outer) looping level. The constant TOPOLOGY_LABELS sets the extra
number of times the outer level gets repeated. It must be a number from 0 to 4. This allows sets in the
system to be labeled in terms of operator sets different from the one used to generate the family (which
always automatically gets applied, to label sets in the system).
I added this extra labeling ability when I was trying to minimize the cardinality of the system in closure
spaces that are capable of generating a maximal family. Labeling the sets in multiple ways greatly
simplified the task of finding identity candidates.
Note: the constants MAX_CYCLES_ONE, MAX_CYCLES_TWO, etc. serve essentially the same purpose that
MAX_CYCLES_ZERO does for generating the family, except they are only used for labeling the system (they
have nothing to do with generating the family).
The constant SPACE_SIZE determines the cardinality of the underlying space. It is extremely important!
The constant SEED_SET is entered as a decimal integer. Its binary form represents the seed set. Note: in
automatic mode, no generality is lost if this constant is always set equal to a power of 2 minus 1.
The (Boolean) constant MULTIPLE_SEED_SETS determines whether various seed sets are to be used (only applies
in automatic mode).
The (Boolean) constant CHECK_HASSE can safely be set to 0 and ignored. When it is set to 1, the program
identifies what type of Kuratowski monoid the underlying topological space generates. See reference
[GJ 2008 A] of Kuratowski's Closure-Complement Cornucopia for details.
When the (Boolean) constant CLOSURE_SPACE is set to 1, the program assumes the subbase is supposed to
generate a closure space instead of a topological space. Make sure this constant is set to 0 anytime
you want to work in a topological space.
The (Boolean) constant CLOSURE_ALGEBRAIC can safely be set to 0 and ignored. Setting it to 1 allows the
program to generate the system of closed sets (which determines the algebraic closure) of an abstract
algebra, given a set of "fundamental operations". See reference [AS 1971 A] of Kuratowski's
Closure-Complement Cornucopia for details. (The only reason I added this "feature" is because I was
verifying a result in Anusiak and Shum, that seemed easier to automate than check manually.)
The (Boolean) constant IDENTITIES is yet another one that should almost always be set to 0 and ignored.
When it is set to 1, every time a candidate set fails to be new while the family is being generated,
an equation is printed in the output file that shows which set in the family it was equal to.
(This feature pretty much always produces an overly long list of equations in the output file.)
For automatic mode only, the constant MIN_TOPOLOGY sets a minimum cardinality on the system for the
program to proceed to generating the family from the seed set. When the system fails this test,
the program skips to the next randomly-generated subbase. This speeds up automatic mode a little.
Similarly, the constant MIN_SETS sets a minimum cardinality on the family for it to be written to the
output file (applies to both modes). Its main purpose is to limit the size of the output file.
The constant MIN_FIRST_FAM sets a minimum cardinality on the family generated by the first repetition
of the first operator batch (for the program to continue generating the family). For example if the
first operator batch takes closures and interiors only, setting this constant to 7 will make the program
stop generating the family immediately upon discovering that the seed set is not a 14-set.
(This constant applies to both modes, but it only becomes useful in automatic mode.) Similarly, the
constant MIN_SECOND_FAM sets a minimum cardinality on the family after the first repetition of the second
operator batch has been completed.
The (Boolean) constant AUTORUN determines the operating mode. Setting it to 1 puts the program in
automatic mode.
In automatic mode, setting the (Boolean) constant FIXED_SUBBASE_SIZES to 1 allows the distribution
of the subbase set cardinalities to be specified precisely. This is done using the subbase_count[]
array: setting subbase_count[i] = j makes the program produce exactly j subbase sets of cardinality i.
Among the most recent features added to the program, it greatly improved automatic mode.
The constant NUMTRIALS sets the number of trials in automatic mode. Depending on the space size and
whether or not FIXED_SUBBASE_SIZES and other timesavers are set to 1, this can be set to a fairly large
number without causing the program to run forever. For example, for space sizes up to about 14,
running 100,000 trials usually only takes a few minutes.
The constants SB_MIN, SB_RANGE, and SB_CARD_RANGE only apply when FIXED_SUBBASE_SIZES is set to 0.
When I first introduced automatic mode, both the number, as well as the cardinalities of the subbase
sets, were generated randomly subject to these constraints. I omit the details here, since after much
experimentation I have found the FIXED_SUBBASE_SIZES method to be superior to this earlier one.
As mentioned above, the constant LABEL_MAX sets the maximum string length for the label of a set.
In manual mode, the subbase sets must be entered into an input file named "inputs.txt".
These sets can all be entered as binary strings following the word "digits". For example, the line
digits 011001 110011 000010
represents the subbase {{1,4,5}, {1,2,5,6}, {2}}. This same subbase can alternatively be entered as
a (space-delimited, as before) list beginning with the identifier-string "sets":
sets 1,4,5 1,2,5,6 2
or entered using carriage returns for the delimiters:
sets
1,4,5
1,2,5,6
2
The only other way to input a subbase in manual mode is to set CLOSURE_ALGEBRAIC to 1 and define
some fundamental operations in an abstract algebra. Since the code I wrote for this feature
was put together in a haste without regard to any future use, it currently isn't very workable.
The input variables for automatic mode have already been described above.
The program's output is written to a file named "results.txt". This file contains several useful
results. First, it shows the system ordered by cardinality. Next it gives a minimal base for the
system. Next it shows the family. Lastly it indicates whether the family distinguishes every point
in the space. When it doesn't, two and only two undistinguished points are given (others may exist).
Put another way, the program determines whether essentially the same family could have been generated
by essentially the same space, except with one point removed. This feature comes in handy when trying
to minimize the cardinality of the underlying space.
Note: the output file currently only represents sets in binary string format.
An early functions reference appears in a comment below, at the end of the file. Note: many functions
were added later to the program but not added to this reference.
Note: I am mostly self-taught in C. Almost all of my programming experience involves hobby projects
like this one, so please cut me some slack if my coding style irritates you.
Collaborators are welcome. If anyone would like to improve this - maybe add a GUI, etc. - I will be
happy to post their work on Math Transit.com (or a link to it).
The program is not overly complicated, but if anything confuses you to the point where you need help,
free support is available by contacting me at mathematrucker@gmail.com or by phone at +1 702-420-6684.
Note: the current version has only been tested with Xcode on a Macbook Pro running Lion (OS 10.7.5).
In the past I have ported the program back and forth between Windows and Mac with no major issues.
It should still be fairly portable.
Mark Bowron
16 Nov 2012
*/
#include
#include
#include
#include
#include
#include
#define UNION |
#define INTERSECT &
#define COMPLEMENT ~
#define TRUE 1
#define FALSE 0
#define TAKE_CLOSURES 'k' // closure symbol
#define TAKE_INTERIORS 'i' // interior symbol
#define TAKE_COMPLEMENTS 'c' // complement symbol
#define TAKE_BOUNDARIES 'b' // boundary symbol
#define TAKE_UNIONS 'u' // union symbol
#define TAKE_INTERSECTIONS 'x' // intersection symbol
#define SEED_LABEL 'A' // seed set symbol
#define TOPOLOGY_LABELS 2 // extra label-batches to run for topology (useful for equalities)
#define MAX_CYCLES_ZERO 10 // for initial fam, max three-batch cycles
#define MAX_CYCLES_ONE 10 // for extra label-batch 1, max three-batch cycles
#define MAX_CYCLES_TWO 2 // for extra label-batch 2, max three-batch cycles
#define MAX_CYCLES_THREE 0 // for extra label-batch 3, max three-batch cycles
#define MAX_CYCLES_FOUR 0 // for extra label-batch 4, max three-batch cycles
#define SPACE_SIZE 10 // cardinality of underlying space
#define SEED_SET 63 // manually-entered seed set (WLOG can be 2^k-1 for some k)
#define MULTIPLE_SEED_SETS 0 // generate multiple seed sets automatically
#define CHECK_HASSE 0 // find the Kuratowski monoid
#define CLOSURE_SPACE 0 // create closure space instead of topological space
#define CLOSURE_ALGEBRAIC 0 // use "fundamental functions" to define closure
#define IDENTITIES 0 // display identities?
#define MIN_TOPOLOGY 0 // min cardinality of topology required to continue (autorun only)
#define MIN_SETS 0 // min distinct sets in initial fam required to print anything
#define MIN_FIRST_FAM 0 // min number of 1st elements required to go on to 2nd batch
#define MIN_SECOND_FAM 0 // min number of 2nd elements required to go on to 3rd batch
#define AUTORUN 0 // 0 = enter subbase manually in "inputs.txt"
#define FIXED_SUBBASE_SIZES 1 // fix the subbase set cardinalities?
#define NUMTRIALS 80000 // number of randomly generated topologies attempted
#define SB_MIN 4 // min cardinality of subbase
#define SB_RANGE 3 // max additional subbase sets
#define SB_CARD_RANGE 0 // max diff between subbase set cardinality and seed cardinality
#define LABEL_MAX 100 // max length of expressions like k * k(kcE * ckE)
typedef struct
{
unsigned long numberOfElements; // cardinality of topology
unsigned long numberOfBaseElements; // cardinality of base
unsigned long *list; // list of sets in topology, indexed by 0,1,2,...
unsigned long *clist; // list of closed sets, indexed by 0,1,2,...
unsigned long *base; // list of base sets, indexed by 0,1,2,...
unsigned long *signature; // signature[i] = TRUE iff i is in list
unsigned long *insubbase; // insubbase[i] = TRUE iff i is in subbase
unsigned long *inbase; // inbase[i] = TRUE iff i is in base
char **binaryRep; // indexed by 0,1,2,...
char **binaryRepb; // indexed by 0,1,2,...
char **binaryRepc; // indexed by 0,1,2,...
} Topology;
typedef struct
{
unsigned long numberOfElements;
unsigned long subsetcount;
unsigned long lastcl; // last closure attempted
unsigned long lastint; // last interior attempted
unsigned long lastcomp; // last complement attempted
unsigned long lastbdy; // last boundary attempted
unsigned long lastu; // last upper set attempted in union
unsigned long lastx; // last upper set attempted in intersection
unsigned long *list; // list of sets in family, indexed by 0,1,2,...
unsigned long *signature; // signature[i]=TRUE iff i is in list
char **binaryRep; // indexed by 0,1,2,...
char **label; // indexed by ->list
unsigned long itergroup; // index of ->itercount
unsigned long *itercount; // number of sets generated per iteration
} Family;
typedef struct
{
unsigned long *i;
unsigned long *k;
unsigned long *ik;
unsigned long *ki;
unsigned long *iki;
unsigned long *kik;
} Hasse;
static void BinaryRep(unsigned long n, char *binaryRep);
static unsigned long DecimalRep(char *binaryRep);
static unsigned long OneCounts(unsigned long n);
static int comparRtn(const void *a, const void *b);
void prepend(char* s, const char* t);
static void InsertTopology(Topology *topology, unsigned long element);
static void InsertClosureSpace(Topology *topology, unsigned long element);
static void InsertFamily(Family *family, unsigned long element, char *elementLabel);
void PrintTopology(Topology *topology, Family *family, Family *fam_one, Family *fam_two, Family *fam_three, Family *fam_four);
void PrintFamily(Family *family);
static unsigned long Closure(Topology *topology, unsigned long B);
static unsigned long Complement(unsigned long k);
static unsigned long Interior(Topology *topology, unsigned long B);
static unsigned long Boundary(Topology *topology, unsigned long C);
static void TakeClosures(Topology *topology, Family *family);
static void TakeComplements(Family *family);
static void TakeInteriors(Topology *topology, Family *family);
static void TakeBoundaries(Topology *topology, Family *family);
static void TakeUnions(Family *family);
static void TakeIntersections(Family *family);
static void ApplyOperations(Topology *topology, Family *family, char *first_b, char *second_b, char *third_b, unsigned long maxcycles);
void ComputeBase(Topology *topology);
void ComputeTopology(Topology *topology);
void ComputeClosureSpace(Topology *topology);
static void ComputeFamily();
static void GenerateFamily(Topology *topology, Family *family, Family *fam_one, Family *fam_two, Family *fam_three, Family *fam_four);
static void ComputeHasse(Topology *topology, Hasse *hasse);
void CheckHasse(Hasse *hasse);
Topology *CreateTopology();
static void EraseTopology(Topology *topology);
static void FreeTopology(Topology *topology);
Family *CreateFamily();
static void EraseFamily(Family *family);
static void FreeFamily(Family *family);
Hasse *CreateHasse();
static void EraseHasse(Hasse *hasse);
static void FreeHasse(Hasse *hasse);
/*
* We close the family under a first batch of operations,
* then (optionally) under a second, then (optionally) under a third,
* then repeat this process until no new sets get generated.
*/
static char close_first_fam[] = "kc"; // close family under these operations first
static char close_second_fam[] = ""; // close under these second
static char close_third_fam[] = ""; // close under these third
static unsigned long maxcycles_fam = MAX_CYCLES_ZERO; // max three-batch cycles for initial fam
static unsigned long minfirstfam = MIN_FIRST_FAM; // min number of 1st-batch elements required
static unsigned long minsecondfam = MIN_SECOND_FAM; // min number of 2nd-batch elements required
static unsigned long mintop = MIN_TOPOLOGY; // min cardinality of topology required
static char close_first_b_one[] = "kc"; // for label-batch 1, close under these first
static char close_second_b_one[] = ""; // for label-batch 1, close under these second
static char close_third_b_one[] = ""; // for label-batch 1, close under these third
static unsigned long maxcycles_b_one = MAX_CYCLES_ONE; // for label-batch 1, max three-batch cycles
static char close_first_b_two[] = "kc"; // for label-batch 2, close under these first
static char close_second_b_two[] = "x"; // for label-batch 2, close under these second
static char close_third_b_two[] = ""; // for label-batch 2, close under these third
static unsigned long maxcycles_b_two = MAX_CYCLES_TWO; // for label-batch 2, max three-batch cycles
static char close_first_b_three[] = ""; // for label-batch 3, close under these first
static char close_second_b_three[] = ""; // for label-batch 3, close under these second
static char close_third_b_three[] = ""; // for label-batch 3, close under these third
static unsigned long maxcycles_b_three = MAX_CYCLES_THREE; // for label-batch 3, max three-batch cycles
static char close_first_b_four[] = ""; // for label-batch 4, close under these first
static char close_second_b_four[] = ""; // for label-batch 4, close under these second
static char close_third_b_four[] = ""; // for label-batch 4, close under these third
static unsigned long maxcycles_b_four = MAX_CYCLES_FOUR; // for label-batch 4, max three-batch cycles
/*
* This next array is for autorun only.
* We fix the distribution of cardinalities of the subbase sets.
*/
static char subbase_set[64]; // stores the digits of the randomly generated subbase set
/*
* The subbase_count array stores the number of subbase sets per cardinality.
*/
static unsigned long subbase_count[32];
static unsigned long *oneCounts;
static unsigned long *twopower;
static unsigned long spacesize = SPACE_SIZE; // cardinality of topological space
static unsigned long pairs[SPACE_SIZE][SPACE_SIZE]; // shorthand for 2-point subsets (with repetition)
static unsigned long seed = SEED_SET; // the seed set A
static unsigned long seedsize; // cardinality of the seed set A
static unsigned long wholespace; // decimal rep of whole space
static unsigned long maxfam; // upper bound on families of sets
static unsigned long closuresp = CLOSURE_SPACE; // do closure space instead
static unsigned long algebraic = CLOSURE_ALGEBRAIC; // define closed sets with fundamental functions
static unsigned long clchar = TAKE_CLOSURES; // define closure label/unsigned longacter
static unsigned long compchar = TAKE_COMPLEMENTS; // define complement label/character
static unsigned long intchar = TAKE_INTERIORS; // define interior label/character
static unsigned long bdychar = TAKE_BOUNDARIES; // define boundary label/character
static unsigned long uchar = TAKE_UNIONS; // define union character
static unsigned long xchar = TAKE_INTERSECTIONS; // define intersection character
static char seedchar = SEED_LABEL; // define seed label
static unsigned long printidentities = IDENTITIES; // switch to display identities
static unsigned long fixsubsizes = FIXED_SUBBASE_SIZES; // switch to fix subbase set cardinalities
static char *clstr; // store closure label in string
static char *compstr; // store complement label in string
static char *intstr; // store interior label in string
static char *bdystr; // store boundary label in string
static char *ustr; // store union character in string
static char *xstr; // store intersection character in string
static char *seedstr; // store seed label in string
static FILE *results;
int main(int argc, const char * argv[])
{
unsigned long k, x;
subbase_count[0] = 0; // puts empty set in subbase if checked (doing so would be redundant though)
subbase_count[1] = 0; // number of singletons in subbase
subbase_count[2] = 0; // number of 2-point sets in subbase
subbase_count[3] = 0; // number of 3-point sets in subbase
subbase_count[4] = 0; // ...
subbase_count[5] = 0;
subbase_count[6] = 2;
subbase_count[7] = 0;
subbase_count[8] = 0;
subbase_count[9] = 0;
subbase_count[10] = 2;
subbase_count[11] = 3;
subbase_count[12] = 2;
subbase_count[13] = 0;
subbase_count[14] = 0;
subbase_count[15] = 0;
subbase_count[16] = 0;
subbase_count[17] = 0;
subbase_count[18] = 0;
subbase_count[19] = 0;
subbase_count[20] = 0;
subbase_count[21] = 0;
subbase_count[22] = 0;
subbase_count[23] = 0;
subbase_count[24] = 0;
subbase_count[25] = 0;
subbase_count[26] = 0;
subbase_count[27] = 0;
subbase_count[28] = 0;
subbase_count[29] = 0;
subbase_count[30] = 0;
subbase_count[31] = 0;
results = fopen("results.txt", "w");
twopower = (unsigned long *)malloc(62 * sizeof(unsigned long));
if (twopower==0)
{
fprintf(results, "Could not allocate space for twopower array.\n");
exit(0);
}
/*
* Load twopower array.
*/
twopower[0] = 1;
twopower[1] = 2;
twopower[2] = 4;
twopower[3] = 8;
twopower[4] = 16;
twopower[5] = 32;
twopower[6] = 64;
twopower[7] = 128;
twopower[8] = 256;
twopower[9] = 512;
twopower[10] = 1024;
twopower[11] = 2048;
twopower[12] = 4096;
twopower[13] = 8192;
twopower[14] = 16384;
twopower[15] = 32768;
twopower[16] = 65536;
twopower[17] = 131072;
twopower[18] = 262144;
twopower[19] = 524288;
twopower[20] = 1048576;
twopower[21] = 2097152;
twopower[22] = 4194304;
twopower[23] = 8388608;
twopower[24] = 16777216;
twopower[25] = 33554432;
twopower[26] = 67108864;
twopower[27] = 134217728;
twopower[28] = 268435456;
twopower[29] = 536870912;
twopower[30] = 1073741824;
twopower[31] = 2147483648; // RAND_MAX = twopower[31]-1
twopower[32] = 4294967296;
twopower[33] = 8589934592;
twopower[34] = 17179869184;
twopower[35] = 34359738368;
twopower[36] = 68719476736;
twopower[37] = 137438953472;
twopower[38] = 274877906944;
twopower[39] = 549755813888;
twopower[40] = 1099511627776;
twopower[41] = 2199023255552;
twopower[42] = 4398046511104;
twopower[43] = 8796093022208;
twopower[44] = 17592186044416;
twopower[45] = 35184372088832;
twopower[46] = 70368744177664;
twopower[47] = 140737488355328;
twopower[48] = 281474976710656;
twopower[49] = 562949953421312;
twopower[50] = 1125899906842624;
twopower[51] = 2251799813685248;
twopower[52] = 4503599627370496;
twopower[53] = 9007199254740992;
twopower[54] = 18014398509481984;
twopower[55] = 36028797018963968;
twopower[56] = 72057594037927936;
twopower[57] = 144115188075855872;
twopower[58] = 288230376151711744;
twopower[59] = 576460752303423488;
twopower[60] = 1152921504606846976;
twopower[61] = 2305843009213693952;
// twopower[62] = 4611686018427387904;
// twopower[63] = 9223372036854775808;
// twopower[64] = 18446744073709551616;
wholespace = twopower[spacesize]-1;
maxfam = twopower[spacesize];
for (x=spacesize; x<64; x++) subbase_set[x] = '\0'; // initialize unused digits of subbase_set to null
/*
* Load label strings.
*/
clstr = (char *)calloc(3, sizeof(char));
compstr = (char *)calloc(3, sizeof(char));
intstr = (char *)calloc(3, sizeof(char));
bdystr = (char *)calloc(3, sizeof(char));
ustr = (char *)calloc(3, sizeof(char));
xstr = (char *)calloc(3, sizeof(char));
seedstr = (char *)calloc(3, sizeof(char));
clstr[0] = clchar;
compstr[0] = compchar;
intstr[0] = intchar;
bdystr[0] = bdychar;
ustr[0] = uchar;
xstr[0] = xchar;
seedstr[0] = seedchar;
clstr[1] = '\0';
compstr[1] = '\0';
intstr[1] = '\0';
bdystr[1] = '\0';
ustr[1] = '\0';
xstr[1] = '\0';
seedstr[1] = '\0';
oneCounts = (unsigned long *)malloc(maxfam * sizeof(unsigned long));
if (oneCounts==0)
{
fprintf(results, "Could not allocate space for one counts.\n");
exit(0);
}
for (k=0; kXb || (Xa==Xb && Ya>Yb)) ? -1 : ((Xa==Xb && Ya==Yb) ? 0 : 1);
}
void prepend(char* s, const char* t)
{
size_t lent = strlen(t);
size_t lens = strlen(s)+1;
size_t i;
/*
* Prepend t into s. Assumes s has enough space allocated for the combined string.
*/
memmove(s + lent, s, lens);
for (i = 0; i < lent; ++i)
{
s[i] = t[i];
}
}
static void InsertTopology(Topology *topology, unsigned long element)
{
if (topology->signature[element]) return;
topology->signature[element] = TRUE;
topology->list[topology->numberOfElements] = element;
topology->clist[topology->numberOfElements] = Complement(element);
assert(topology->numberOfElements < maxfam);
topology->numberOfElements++;
}
static void InsertClosureSpace(Topology *topology, unsigned long element)
{
if (topology->signature[element]) return;
topology->signature[element] = TRUE;
topology->clist[topology->numberOfElements] = element;
topology->list[topology->numberOfElements] = Complement(element);
assert(topology->numberOfElements < maxfam);
topology->numberOfElements++;
}
static void InsertFamily(Family *family, unsigned long element, char *elementLabel)
{
unsigned long i;
if (family->signature[element])
{
if (printidentities == 1)
{
for (i=0; inumberOfElements; i++)
if (element == family->list[i])
{
fprintf(results, "%s = %s\n", elementLabel, family->label[family->list[i]]);
break;
}
}
return;
}
family->signature[element] = TRUE;
strcpy(family->label[element], elementLabel);
family->list[family->numberOfElements] = element;
assert(family->numberOfElements < maxfam);
family->numberOfElements++;
}
void PrintTopology(Topology *topology, Family *family, Family *fam_one, Family *fam_two, Family *fam_three, Family *fam_four)
{
unsigned long i, j;
unsigned long s, setsize;
setsize = spacesize;
j = TOPOLOGY_LABELS;
i = 0;
while (i < j)
{
switch (i)
{
case 0:
strcpy(fam_one->label[seed], seedstr);
InsertFamily(fam_one, seed, fam_one->label[seed]);
BinaryRep(fam_one->list[0], fam_one->binaryRep[0]);
ApplyOperations(topology, fam_one, close_first_b_one, close_second_b_one, close_third_b_one, maxcycles_b_one);
break;
case 1:
strcpy(fam_two->label[seed], seedstr);
InsertFamily(fam_two, seed, fam_two->label[seed]);
BinaryRep(fam_two->list[0], fam_two->binaryRep[0]);
ApplyOperations(topology, fam_two, close_first_b_two, close_second_b_two, close_third_b_two, maxcycles_b_two);
break;
case 2:
strcpy(fam_three->label[seed], seedstr);
InsertFamily(fam_three, seed, fam_three->label[seed]);
BinaryRep(fam_three->list[0], fam_three->binaryRep[0]);
ApplyOperations(topology, fam_three, close_first_b_three, close_second_b_three, close_third_b_three, maxcycles_b_three);
break;
case 3:
strcpy(fam_four->label[seed], seedstr);
InsertFamily(fam_four, seed, fam_four->label[seed]);
BinaryRep(fam_four->list[0], fam_four->binaryRep[0]);
ApplyOperations(topology, fam_four, close_first_b_four, close_second_b_four, close_third_b_four, maxcycles_b_four);
break;
}
i++;
}
if (!closuresp)
{
fprintf(results, "\nTopology contains %lu sets:\n\n", topology->numberOfElements);
for (i=0; inumberOfElements; i++)
{
BinaryRep(topology->list[i], topology->binaryRep[i]);
if (setsize > oneCounts[topology->list[i]])
{
fprintf(results, "\n");
setsize = oneCounts[topology->list[i]];
}
switch (j)
{
case 0:
if (topology->insubbase[topology->list[i]])
fprintf(results, "%s %2lu %s\t\t(subbase set)\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]]);
else fprintf(results, "%s %2lu %s\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]]);
break;
case 1:
if (topology->insubbase[topology->list[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t(subbase set)\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]]);
break;
case 2:
if (topology->insubbase[topology->list[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]]);
break;
case 3:
if (topology->insubbase[topology->list[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]], fam_three->label[topology->list[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]], fam_three->label[topology->list[i]]);
break;
case 4:
if (topology->insubbase[topology->list[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]], fam_three->label[topology->list[i]], fam_four->label[topology->list[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t%s\n", &(topology->binaryRep[i][64-spacesize]), oneCounts[topology->list[i]], family->label[topology->list[i]], fam_one->label[topology->list[i]], fam_two->label[topology->list[i]], fam_three->label[topology->list[i]], fam_four->label[topology->list[i]]);
break;
} // end switch
} // end for (i=0; inumberOfElements; i++)
ComputeBase(topology);
setsize = spacesize;
fprintf(results, "\n**********************************************\n\n");
fprintf(results, "Minimal base contains %2lu sets:\n", topology->numberOfBaseElements);
for (s=0; snumberOfBaseElements; s++)
{
BinaryRep(topology->base[s], topology->binaryRepb[s]);
if (oneCounts[topology->base[s]] == spacesize) fprintf(results, "\n");
else if (setsize > oneCounts[topology->base[s]])
{
fprintf(results, "\n");
setsize = oneCounts[topology->base[s]];
}
fprintf(results, "%s %2lu\n", &(topology->binaryRepb[s][64-spacesize]), oneCounts[topology->base[s]]);
}
}
else // print closure space
{
fprintf(results, "\nSystem of closed sets contains %lu sets:\n\n", topology->numberOfElements);
for (i=0; inumberOfElements; i++)
{
BinaryRep(topology->clist[i], topology->binaryRepc[i]);
if (setsize > oneCounts[topology->clist[i]])
{
fprintf(results, "\n");
setsize = oneCounts[topology->clist[i]];
}
switch (j)
{
case 0:
if (topology->insubbase[topology->clist[i]])
fprintf(results, "%s %2lu %s\t\t(subbase set)\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]]);
else fprintf(results, "%s %2lu %s\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]]);
break;
case 1:
if (topology->insubbase[topology->clist[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t(subbase set)\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]]);
break;
case 2:
if (topology->insubbase[topology->clist[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]]);
break;
case 3:
if (topology->insubbase[topology->clist[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]], fam_three->label[topology->clist[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]], fam_three->label[topology->clist[i]]);
break;
case 4:
if (topology->insubbase[topology->clist[i]])
fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t%s\t\t(subbase set)\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]], fam_three->label[topology->clist[i]], fam_four->label[topology->clist[i]]);
else fprintf(results, "%s %2lu %s\t\t%s\t\t%s\t\t%s\t\t%s\n", &(topology->binaryRepc[i][64-spacesize]), oneCounts[topology->clist[i]], family->label[topology->clist[i]], fam_one->label[topology->clist[i]], fam_two->label[topology->clist[i]], fam_three->label[topology->clist[i]], fam_four->label[topology->clist[i]]);
break;
} // end switch
} // end for (i=0; inumberOfElements; i++)
} // end if (!closuresp)
switch (j)
{
case 0:
break;
case 1:
EraseFamily(fam_one);
break;
case 2:
EraseFamily(fam_one);
EraseFamily(fam_two);
break;
case 3:
EraseFamily(fam_one);
EraseFamily(fam_two);
EraseFamily(fam_three);
break;
case 4:
EraseFamily(fam_one);
EraseFamily(fam_two);
EraseFamily(fam_three);
EraseFamily(fam_four);
break;
} // end switch
}
void PrintFamily(Family *family)
{
unsigned long i;
unsigned long setsize;
family->itergroup++;
family->itercount[family->itergroup] = family->numberOfElements - family->itercount[family->itergroup-1];
qsort(family->list+family->itercount[family->itergroup-1], (size_t)(family->itercount[family->itergroup]), sizeof(unsigned long), comparRtn);
setsize = spacesize;
fprintf(results, "\n**********************************************\n\n");
fprintf(results, "Generated family contains %lu sets:\n", family->itercount[family->itergroup]);
for (i=family->itercount[family->itergroup-1]; inumberOfElements; i++)
{
BinaryRep(family->list[i], family->binaryRep[i]);
if (oneCounts[family->list[i]] == spacesize) fprintf(results, "\n");
else if (setsize > oneCounts[family->list[i]])
{
fprintf(results, "\n");
setsize = oneCounts[family->list[i]];
}
fprintf(results, "%s %2lu %s\n", &(family->binaryRep[i][64-spacesize]), oneCounts[family->list[i]], family->label[family->list[i]]);
}
}
static unsigned long Closure(Topology *topology, unsigned long B)
{
unsigned long i, C;
/*
* Scan up the closed sets from smallest to largest
* until you find the first one that contains B.
*/
for (i=topology->numberOfElements-1; i>0; i--)
{
C = topology->clist[i];
if ((B&C)==B) return C;
if (i==1)
{
C = topology->clist[0];
return C;
}
}
/*
* If we get to here, something's wrong.
*/
fprintf(results, "Error - closure not found.\n");
exit(0);
}
static unsigned long Complement(unsigned long k)
{
unsigned long C;
char *binaryRep;
unsigned long i;
binaryRep = (char *)malloc(65 * sizeof(char));
if (binaryRep==0)
{
fprintf(results, "Could not allocate space for complement binaryRep.\n");
exit(0);
}
C = COMPLEMENT k;
BinaryRep(C, binaryRep);
for (i=0; i<(64-spacesize); i++) binaryRep[i] = '0';
C = DecimalRep(binaryRep);
free(binaryRep);
return C;
}
static unsigned long Interior(Topology *topology, unsigned long B)
{
B = Complement(B);
B = Closure(topology, B);
B = Complement(B);
return B;
}
static unsigned long Boundary(Topology *topology, unsigned long C)
{
unsigned long A, B;
A = Closure(topology, C);
B = Complement(C);
B = Closure(topology, B);
B = A INTERSECT B;
return B;
}
static void TakeClosures(Topology *topology, Family *family)
{
unsigned long j;
unsigned long B, C, D;
unsigned long num;
char elementLabel[LABEL_MAX];
char *firstk;
size_t length;
num = family->numberOfElements;
for (j=family->lastcl; jlist[j];
D = B;
/*
* Don't take closures of closures.
*/
firstk = strchr(family->label[D], clchar);
if (firstk != NULL)
if (strcmp(firstk, family->label[D]) == 0) // goes to next j if clchar begins family->label[D]
continue;
length = strlen(family->label[D]);
if (length > LABEL_MAX - 2)
{
fprintf(results, "Label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, family->label[D]);
prepend(elementLabel, clstr);
C = Closure(topology, B);
InsertFamily(family, C, elementLabel);
}
family->lastcl = j;
}
static void TakeComplements(Family *family)
{
unsigned long j;
unsigned long B, D;
unsigned long num;
char elementLabel[LABEL_MAX];
char *firstc;
size_t length;
num = family->numberOfElements;
elementLabel[0] = '\0';
for (j=family->lastcomp; jlist[j];
/*
* Don't take complements of complements.
*/
firstc = strchr(family->label[D], compchar);
if (firstc != NULL)
if (strcmp(firstc, family->label[D]) == 0) // goes to next j if compchar begins family->label[D]
continue;
length = strlen(family->label[D]);
if (length > LABEL_MAX - 2)
{
fprintf(results, "Complement label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, family->label[D]);
prepend(elementLabel, compstr);
B = Complement(family->list[j]);
InsertFamily(family, B, elementLabel);
}
family->lastcomp = j;
}
static void TakeInteriors(Topology *topology, Family *family)
{
unsigned long j;
unsigned long B, C, D;
unsigned long num;
char elementLabel[LABEL_MAX];
char *firsti;
size_t length;
num = family->numberOfElements;
for (j=family->lastint; jlist[j];
D = B;
/*
* Don't take interiors of interiors.
*/
firsti = strchr(family->label[D], intchar);
if (firsti != NULL)
if (strcmp(firsti, family->label[D]) == 0) // goes to next j if intchar begins family->label[D]
continue;
length = strlen(family->label[D]);
if (length > LABEL_MAX - 2)
{
fprintf(results, "Label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, family->label[D]);
prepend(elementLabel, intstr);
C = Interior(topology, B);
InsertFamily(family, C, elementLabel);
}
family->lastint = j;
}
static void TakeBoundaries(Topology *topology, Family *family)
{
unsigned long j;
unsigned long B, D;
unsigned long num;
char elementLabel[LABEL_MAX];
char *firstc;
size_t length;
num = family->numberOfElements;
elementLabel[0] = '\0';
for (j=family->lastbdy; jlist[j];
/*
* Don't take boundaries of complements.
*/
firstc = strchr(family->label[D], compchar);
if (firstc != NULL)
if (strcmp(firstc, family->label[D]) == 0) // goes to next j if compchar begins family->label[D]
continue;
length = strlen(family->label[D]);
if (length > LABEL_MAX - 2)
{
fprintf(results, "Boundary label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, family->label[D]);
prepend(elementLabel, bdystr);
B = Boundary(topology, family->list[j]);
InsertFamily(family, B, elementLabel);
}
family->lastbdy = j;
}
static void TakeUnions(Family *family)
{
unsigned long i, j;
unsigned long B, C, D;
char elementLabel[LABEL_MAX];
size_t length;
for (i=family->lastu; inumberOfElements; i++) // upper limit varies dynamically
{
B = family->list[i];
for (j=0; j*list[j];
length = strlen(family->label[B]) + strlen(family->label[C]);
if (length > LABEL_MAX - 6)
{
fprintf(results, "Label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, "(");
strcat(elementLabel, family->label[B]);
strcat(elementLabel, " + ");
strcat(elementLabel, family->label[C]);
strcat(elementLabel, ")");
D = family->list[i] UNION family->list[j];
InsertFamily(family, D, elementLabel);
}
}
family->lastu = i;
}
static void TakeIntersections(Family *family)
{
unsigned long i, j;
unsigned long B, C, D;
char elementLabel[LABEL_MAX];
size_t length;
for (i=family->lastx; inumberOfElements; i++) // upper limit varies dynamically
{
B = family->list[i];
for (j=0; j**list[j];
length = strlen(family->label[B]) + strlen(family->label[C]);
if (length > LABEL_MAX - 6)
{
fprintf(results, "Label too long. Increase LABEL_MAX then retry.\n");
exit(0);
}
strcpy(elementLabel, "(");
strcat(elementLabel, family->label[B]);
strcat(elementLabel, " * ");
strcat(elementLabel, family->label[C]);
strcat(elementLabel, ")");
D = family->list[i] INTERSECT family->list[j];
InsertFamily(family, D, elementLabel);
}
}
family->lastx = i;
}
static void ApplyOperations(Topology *topology, Family *family, char *first_b, char *second_b, char *third_b, unsigned long maxcycles)
{
unsigned long u, num_outer, num_first, num_second, num_third;
size_t j, len_first, len_second, len_third;
len_first = strlen(first_b);
len_second = strlen(second_b);
len_third = strlen(third_b);
/*
* Repeat the three batches a specified number (maxcycles_fam) of times, or until
* no new sets get generated, whichever comes first.
*/
for (u=0; unumberOfElements;
while (TRUE) // close under first batch of operators
{
num_first = family->numberOfElements;
for (j=0; jnumberOfElements) break;
}
if (family->numberOfElements < minfirstfam) break;
if (len_second>0)
while (TRUE) // close under second batch of operators
{
num_second = family->numberOfElements;
for (j=0; jnumberOfElements) break;
}
if (family->numberOfElements < minsecondfam) break;
if (len_third>0)
while (TRUE) // close under third batch of operators
{
num_third = family->numberOfElements;
for (j=0; jnumberOfElements) break;
}
if (num_outer == family->numberOfElements) break;
} // end for (u=0; unumberOfElements; i++)
if (topology->binaryRep[i][63-k] == '1') j = j INTERSECT topology->list[i];
if (topology->inbase[j]) continue;
topology->inbase[j] = TRUE;
topology->base[topology->numberOfBaseElements] = j;
topology->numberOfBaseElements++;
}
qsort(topology->base, (size_t)(topology->numberOfBaseElements), sizeof(unsigned long), comparRtn);
}
void ComputeTopology(Topology *topology)
{
unsigned long i, j, newbie;
i = 1;
while(inumberOfElements) // compute union and intersection of list[i] with all previous elements
{
for (j=0; j**list[i] UNION topology->list[j];
InsertTopology(topology, newbie);
newbie = topology->list[i] INTERSECT topology->list[j];
InsertTopology(topology, newbie);
}
i++;
}
/*
* Sort the systems of open and closed sets in descending order.
*/
qsort(topology->list, (size_t)(topology->numberOfElements), sizeof(unsigned long), comparRtn);
qsort(topology->clist, (size_t)(topology->numberOfElements), sizeof(unsigned long), comparRtn);
}
void ComputeClosureSpace(Topology *topology)
{
unsigned long i, j, n, newbie, temp;
if (!algebraic) // just close the "subbase" under intersection
{
i = 1;
while(inumberOfElements) // compute intersection of list[i] with all previous elements
{
for (j=0; j**clist[i] INTERSECT topology->clist[j];
InsertClosureSpace(topology, newbie);
}
i++;
}
}
else // apply closure to every nonempty proper subset n using fundamental functions
{
for(i=1; iclist, (size_t)(topology->numberOfElements), sizeof(unsigned long), comparRtn);
qsort(topology->list, (size_t)(topology->numberOfElements), sizeof(unsigned long), comparRtn);
}
static void ComputeFamily()
{
Topology *topology;
Hasse *hasse;
Family *family, *fam_one, *fam_two, *fam_three, *fam_four;
unsigned long autorun = AUTORUN;
unsigned long checkhasse = CHECK_HASSE;
unsigned long autoseed = MULTIPLE_SEED_SETS;
// these are for manual only
FILE *sb;
unsigned long cnt;
char *b, *c, *str;
char delim[] = ",";
// these are for autorun only
unsigned long subsize, subrange, x, y;
unsigned long n;
unsigned long p, s;
unsigned long numtrials = NUMTRIALS; // number of different topologies attempted
// these are for both manual and autorun
unsigned long g, h;
unsigned long j, m;
unsigned int sbCount;
for (g=0; glist[0] = wholespace;
topology->clist[0] = 0;
topology->insubbase[wholespace] = TRUE;
topology->signature[wholespace] = TRUE;
topology->list[1] = 0;
topology->clist[1] = wholespace;
topology->insubbase[0] = TRUE;
topology->signature[0] = TRUE;
}
else // empty set not necessarily closed in a closure space
{
topology->list[0] = 0;
topology->clist[0] = wholespace;
topology->insubbase[wholespace] = TRUE;
topology->signature[wholespace] = TRUE;
}
if (!closuresp) sbCount = 2;
else sbCount = 1;
if (!algebraic) // (algebraic closure is computed entirely within ComputeClosureSpace function)
{
sb = fopen("inputs.txt", "r");
if (sb == 0)
{
fprintf(results, "Could not open file inputs.txt.\n");
exit(0);
}
b = (char *)malloc(65);
c = (char *)malloc(65);
char sets[] = "sets";
char digits[] = "digits";
/*
* First string in inputs.txt specifies input format.
* Use "sets" for tab-separated lists of comma-separated decimal numbers: 1 7 1,2 6,7 3,5
* Use "digits" for space-separated boolean strings: 0000001 1000000 0000011 1100000 0010100
*/
fscanf(sb, "%s", b);
if (!strcmp(b, sets))
{
while(TRUE) // read in the subbase in integer format
{
cnt = fscanf(sb, "%s", c);
if (cnt != 1) break;
m = 0;
str = strtok(c, delim);
while (str != NULL)
{
j = atoi(str)-1;
m = m + twopower[j];
str = strtok(NULL, delim);
}
if (topology->signature[m]) continue;
if (!closuresp)
{
topology->list[sbCount] = m;
topology->clist[sbCount] = Complement(m);
}
else // the "subbase" generates the system of closed sets
{
topology->clist[sbCount] = m;
topology->list[sbCount] = Complement(m);
}
topology->insubbase[m] = TRUE;
topology->signature[m] = TRUE;
sbCount++;
}
}
if (!strcmp(b, digits))
{
while(TRUE) // read in the subbase in digit-string format
{
cnt = fscanf(sb, "%s", c);
if (cnt != 1) break;
m = DecimalRep(c);
if (topology->signature[m]) continue;
if (!closuresp)
{
topology->list[sbCount] = m;
topology->clist[sbCount] = Complement(m);
}
else // the "subbase" generates the system of closed sets
{
topology->clist[sbCount] = m;
topology->list[sbCount] = Complement(m);
}
topology->insubbase[m] = TRUE;
topology->signature[m] = TRUE;
sbCount++;
}
}
fclose(sb);
free(b);
free(c);
} // end if (!algebraic)
topology->numberOfElements = sbCount; // initially |topology| = |subbase|
/*
* Compute topology.
*/
if (!closuresp) ComputeTopology(topology);
else ComputeClosureSpace(topology);
if (!autoseed)
{
if (!checkhasse)
{
GenerateFamily(topology, family, fam_one, fam_two, fam_three, fam_four); // generate family
EraseFamily(family); // erase the generated family
}
else
{
ComputeHasse(topology, hasse); // compute Hasse diagram for all subsets
CheckHasse(hasse); // check for key identities in Hasse diagram
EraseHasse(hasse); // erase the Hasse
}
}
else // autoseed
{
for (seed=twopower[spacesize-3]; seedlist[0] = wholespace;
topology->clist[0] = 0;
topology->insubbase[wholespace] = TRUE;
topology->signature[wholespace] = TRUE;
topology->list[1] = 0;
topology->clist[1] = wholespace;
topology->insubbase[0] = TRUE;
topology->signature[0] = TRUE;
p = 2; // both whole space and empty set are in subbase
}
else // empty set not necessarily closed in a closure space
{
topology->list[0] = 0;
topology->clist[0] = wholespace;
topology->insubbase[wholespace] = TRUE;
topology->signature[wholespace] = TRUE;
p = 1; // just whole space is in subbase
}
topology->numberOfElements = p;
/*
* Compute the subbase, one cardinality at a time, or randomly.
*/
if (!fixsubsizes)
{
subrange = SB_CARD_RANGE;
sbCount = rand() % SB_RANGE + SB_MIN; // sets SB_MIN <= sbCount <= SB_MIN + SB_RANGE
while (p < sbCount) // generate subbase sets randomly
{
m = rand() % wholespace;
if (topology->signature[m]) continue;
/*
* Only allow subbase sets of medium cardinality (helps maximize family).
*/
subsize = oneCounts[m];
if (subsize-seedsize<0-subrange) continue;
if (!closuresp)
{
if (subsize-seedsize>subrange) continue; // big subbase sets are okay if closuresp
topology->list[p] = m;
topology->clist[p] = Complement(m);
}
else // the "subbase" generates the system of closed sets
{
topology->clist[p] = m;
topology->list[p] = Complement(m);
}
topology->insubbase[m] = TRUE;
topology->signature[m] = TRUE;
p++;
}
topology->numberOfElements = sbCount; // initially |topology| = |subbase|
}
else // fixedsubsizes
{
for (subsize=0; subsizespacesize/2)
{
for (x=0; xspacesize/2)
s = DecimalRep(subbase_set);
if (topology->signature[s]) continue;
topology->signature[s] = TRUE; // add subbase set manually (without "Insert...")
topology->insubbase[s] = TRUE;
if (!closuresp)
{
topology->list[topology->numberOfElements] = s;
topology->clist[topology->numberOfElements] = Complement(s);
}
else
{
topology->clist[topology->numberOfElements] = s;
topology->list[topology->numberOfElements] = Complement(s);
}
assert(topology->numberOfElements < maxfam);
topology->numberOfElements++;
p++;
} // end while (pnumberOfElements < mintop)
{
EraseTopology(topology);
continue;
}
/*
* The section below (for seeking counterexamples) is usually commented out.
*/
/*
unsigned long kempty, kixkic;
kempty = Closure(0);
j = Interior(seed);
j = Closure(j);
k = Complement(seed);
k = Interior(k);
k = Closure(k);
kixkic = j INTERSECT k;
if(kempty != kixkic)
{
ComputeFamily(topology);
EraseTopology(topology);
EraseFamily(family);
break;
}
else continue;
*/
/*
* Compute family of subsets.
*/
if (!autoseed)
{
GenerateFamily(topology, family, fam_one, fam_two, fam_three, fam_four); // generate family
EraseFamily(family); // erase the generated family
}
else // autoseed
{
for (seed=twopower[spacesize-3]; seedlabel[seed], seedstr);
InsertFamily(family, seed, family->label[seed]);
BinaryRep(family->list[0], family->binaryRep[0]);
/*
* Make sure the seed set doesn't contain anything outside the space.
*/
for (i=0; i<64; i++)
if(family->binaryRep[0][i]=='1')
{
sizereq = 64-i;
break;
}
if (sizereq > spacesize)
{
fprintf(results, "\n**********************************************\n\n");
fprintf(results, "Error: seed set = %s exceeds size of space. Execution aborted.\n", &(family->binaryRep[0][64-sizereq]));
exit(0);
}
ApplyOperations(topology, family, close_first_fam, close_second_fam, close_third_fam, maxcycles_fam);
if (family->numberOfElements < MIN_SETS) return;
/*
* Print the topology.
*/
PrintTopology(topology, family, fam_one, fam_two, fam_three, fam_four);
/*
* Print the family.
*/
PrintFamily(family);
/*
* Check that the family distinguishes all points.
*/
fprintf(results, "\n**********************************************\n\n");
for (s=64-spacesize; s<63; s++)
{
for (t=s+1; t<64; t++)
{
i=0;
while (inumberOfElements)
{
if (family->binaryRep[i][s] == family->binaryRep[i][t]) i++;
else break;
}
if (i == family->numberOfElements) break;
}
if (i == family->numberOfElements)
{
fprintf(results, "Points %2lu and %2lu are not distinguished by family.\n\n", 64-t, 64-s);
break;
}
}
if (i < family->numberOfElements)
fprintf(results, "All points are distinguished by family.\n\n");
fprintf(results, "**********************************************\n\n");
}
static void ComputeHasse(Topology *topology, Hasse *hasse)
{
unsigned long j;
/*
* Calculate each set in the Hasse diagram for every possible seed.
*/
for (j=0; ji[j] = Interior(topology, j);
hasse->k[j] = Closure(topology, j);
hasse->ik[j] = Interior(topology, hasse->k[j]);
hasse->ki[j] = Closure(topology, hasse->i[j]);
hasse->iki[j] = Interior(topology, hasse->ki[j]);
hasse->kik[j] = Closure(topology, hasse->ik[j]);
}
}
void CheckHasse(Hasse *hasse)
{
unsigned long j;
/*
* Check for key identities among the Kuratowski operators.
*/
j=0;
while (jiki[j] == hasse->ki[j]) j++;
else break;
}
if (j == maxfam) fprintf(results, "We have iki = ki for this space.\n");
else fprintf(results, "iki(%lu) = %lu and ki(%lu) = %lu.\n", j, hasse->iki[j], j, hasse->ki[j]);
j=0;
while (jiki[j] == hasse->ik[j]) j++;
else break;
}
if (j == maxfam) fprintf(results, "We have iki = ik for this space.\n");
else fprintf(results, "iki(%lu) = %lu and ik(%lu) = %lu.\n", j, hasse->iki[j], j, hasse->ik[j]);
j=0;
while (jiki[j] == hasse->i[j]) j++;
else break;
}
if (j == maxfam) fprintf(results, "We have iki = i for this space.\n");
else fprintf(results, "iki(%lu) = %lu and i(%lu) = %lu.\n", j, hasse->iki[j], j, hasse->i[j]);
}
Topology *CreateTopology()
{
Topology *topology;
unsigned long i, j;
unsigned long s;
topology = (Topology *)malloc(sizeof(Topology));
if (topology==0)
{
fprintf(results, "Could not allocate space for topology.\n");
exit(0);
}
topology->list = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (topology->list==0)
{
fprintf(results, "Could not allocate space for topology list.\n");
exit(0);
}
topology->clist = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (topology->clist==0)
{
fprintf(results, "Could not allocate space for topology clist.\n");
exit(0);
}
topology->base = (unsigned long *)calloc(spacesize, sizeof(unsigned long));
if (topology->base==0)
{
fprintf(results, "Could not allocate space for topology base.\n");
exit(0);
}
topology->binaryRep = (char **)malloc(maxfam * sizeof(char *));
if (topology->binaryRep==0)
{
fprintf(results, "Could not allocate space for topology binary rep.\n");
exit(0);
}
topology->binaryRepb = (char **)malloc(spacesize * sizeof(char *));
if (topology->binaryRep==0)
{
fprintf(results, "Could not allocate space for topology binary reps.\n");
exit(0);
}
topology->binaryRepc = (char **)malloc(maxfam * sizeof(char *));
if (topology->binaryRep==0)
{
fprintf(results, "Could not allocate space for topology binary reps.\n");
exit(0);
}
for (i=0; ibinaryRep[i] = (char *)malloc(65 * sizeof(char));
if (topology->binaryRep[i]==0)
{
fprintf(results, "Could not allocate space for topology binary rep.\n");
exit(0);
}
topology->binaryRepc[i] = (char *)malloc(65 * sizeof(char));
if (topology->binaryRepc[i]==0)
{
fprintf(results, "Could not allocate space for topology binary rep for closure.\n");
exit(0);
}
}
for (s=0; sbinaryRepb[s] = (char *)malloc(65 * sizeof(char));
if (topology->binaryRepb[s]==0)
{
fprintf(results, "Could not allocate space for topology binary rep for base.\n");
exit(0);
}
}
topology->signature = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (topology->signature==0)
{
fprintf(results, "Could not allocate space for topology signature.\n");
exit(0);
}
topology->insubbase = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (topology->insubbase==0)
{
fprintf(results, "Could not allocate space for subbase identifier.\n");
exit(0);
}
topology->inbase = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (topology->inbase==0)
{
fprintf(results, "Could not allocate space for base identifier.\n");
exit(0);
}
for (i=0; ibinaryRep[i][j] = '\0';
topology->binaryRepc[i][j] = '\0';
}
}
topology->numberOfElements = 0;
topology->numberOfBaseElements = 0;
return topology;
}
static void EraseTopology(Topology *topology)
{
unsigned long i, j;
for (i=0; ilist[i] = 0;
for (i=0; iclist[i] = 0;
for (i=0; isignature[i] = 0;
for (i=0; iinsubbase[i] = 0;
for (i=0; iinbase[i] = 0;
for (i=0; ibase[i] = 0;
for (i=0; ibinaryRep[i][j] = '\0';
topology->binaryRepc[i][j] = '\0';
}
}
for (i=0; ibinaryRepb[i][j] = '\0';
topology->numberOfElements = 0;
topology->numberOfBaseElements = 0;
}
static void FreeTopology(Topology *topology)
{
unsigned long i;
unsigned long s;
free(topology->list);
free(topology->clist);
free(topology->base);
for (i=0; ibinaryRep[i]);
free(topology->binaryRepc[i]);
}
for (s=0; sbinaryRepb[s]);
free(topology->binaryRep);
free(topology->binaryRepc);
free(topology->binaryRepb);
free(topology->signature);
free(topology->insubbase);
free(topology->inbase);
free(topology);
}
Family *CreateFamily()
{
Family *family;
unsigned long i, j;
family = (Family *)malloc(sizeof(Family));
if (family==0)
{
fprintf(results, "Could not allocate space for family.\n");
exit(0);
}
family->numberOfElements = 0;
family->subsetcount = 0;
family->lastcl = 0;
family->lastint = 0;
family->lastcomp = 0;
family->lastbdy = 0;
family->lastu = 0;
family->lastx = 0;
family->itergroup = 0;
family->itercount = (unsigned long *)malloc(maxfam * sizeof(unsigned long));
if (family->itercount==0)
{
fprintf(results, "Could not allocate space for family itercount.\n");
exit(0);
}
family->list = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (family->list==0)
{
fprintf(results, "Could not allocate space for family list.\n");
exit(0);
}
family->signature = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (family->signature==0)
{
fprintf(results, "Could not allocate space for family signature.\n");
exit(0);
}
family->binaryRep = (char **)malloc(maxfam * sizeof(char *));
if (family->binaryRep==0)
{
fprintf(results, "Could not allocate space for family binary rep.\n");
exit(0);
}
family->label = (char **)malloc(maxfam * sizeof(char *));
if (family->label==0)
{
fprintf(results, "Could not allocate space for family label.\n");
exit(0);
}
for (j=0; jbinaryRep[j] = (char *)malloc(65 * sizeof(char));
if (family->binaryRep[j]==0)
{
fprintf(results, "Could not allocate space for family binary rep.\n");
exit(0);
}
family->label[j] = (char *)malloc(LABEL_MAX * sizeof(char));
if (family->label[j]==0)
{
fprintf(results, "Could not allocate space for family label.\n");
exit(0);
}
}
for (i=0; ibinaryRep[i][j] = '\0';
for (j=0; jlabel[i][j] = '\0';
family->itercount[i] = 0;
}
return family;
}
static void EraseFamily(Family *family)
{
unsigned long i, j;
family->numberOfElements = 0;
family->subsetcount = 0;
family->lastcl = 0;
family->lastint = 0;
family->lastcomp = 0;
family->lastbdy = 0;
family->lastu = 0;
family->lastx = 0;
family->itergroup = 0;
for (i=0; ibinaryRep[i][j] = '\0';
for (j=0; jlabel[i][j] = '\0';
family->itercount[i] = 0;
family->list[i] = 0;
family->signature[i] = 0;
}
}
static void FreeFamily(Family *family)
{
unsigned long i;
free(family->list);
free(family->signature);
for (i=0; ibinaryRep[i]);
free(family->label[i]);
}
free(family->binaryRep);
free(family->label);
free(family->itercount);
free(family);
}
Hasse *CreateHasse()
{
Hasse *hasse;
hasse = (Hasse *)malloc(sizeof(Hasse));
if (hasse==0)
{
fprintf(results, "Could not allocate space for Hasse diagram.\n");
exit(0);
}
hasse->i = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->i==0)
{
fprintf(results, "Could not allocate space for Hasse-i.\n");
exit(0);
}
hasse->k = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->k==0)
{
fprintf(results, "Could not allocate space for Hasse-k.\n");
exit(0);
}
hasse->ik = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->ik==0)
{
fprintf(results, "Could not allocate space for Hasse-ik.\n");
exit(0);
}
hasse->ki = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->ki==0)
{
fprintf(results, "Could not allocate space for Hasse-ki.\n");
exit(0);
}
hasse->iki = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->iki==0)
{
fprintf(results, "Could not allocate space for Hasse-iki.\n");
exit(0);
}
hasse->kik = (unsigned long *)calloc(maxfam, sizeof(unsigned long));
if (hasse->kik==0)
{
fprintf(results, "Could not allocate space for Hasse-kik.\n");
exit(0);
}
return hasse;
}
static void EraseHasse(Hasse *hasse)
{
unsigned long j;
for (j=0; ji[j] = 0;
hasse->k[j] = 0;
hasse->ik[j] = 0;
hasse->ki[j] = 0;
hasse->iki[j] = 0;
hasse->kik[j] = 0;
}
}
static void FreeHasse(Hasse *hasse)
{
free(hasse->i);
free(hasse->k);
free(hasse->ik);
free(hasse->ki);
free(hasse->iki);
free(hasse->kik);
free(hasse);
}
/*
-------------------------------
Functions Reference
-------------------------------
static void BinaryRep(unsigned long n, char *binaryRep):
loads binaryRep[j] with the coefficient of 2^j in the binary representation of n
for example if n = 6 then binaryRep[0] = binaryRep[1] = 1 and binaryRep[j] = 0 for j > 1
static unsigned long DecimalRep(char *binaryRep):
inverse of BinaryRep
static void InsertTopology(unsigned long element, Topology *top):
checks if element is already in the topology
if not then adds it to the topology and its complement (which requires spacesize to evaluate)
to the list of closed sets
static void InsertFamily(unsigned long element, Family *fam, char *elementLabel):
checks if element is already in family, if not then add to family
firstiter = 0 during Kuratowski 14, = 1 after Kuratowski 14
static char OneCounts(unsigned long n):
returns cardinality of subset that n represents (count of 1's in its binary representation)
static int comparRtn(const void *a, const void *b):
a "<" b iff cardinality(a) > cardinality(b)
a "=" b iff cardinality(a) = cardinality(b) AND a > b
a ">" b iff cardinality(a) < cardinality(b) OR {cardinality(a) = cardinality(b) AND a <= b}
void ComputeTopology(Topology *top):
loads the sorted topology into *top, sorted by comparRtn
void PrintTopology(Topology *top):
prints the topology sorted by cardinality and (optionally) the closed sets (also sorted)
static void TakeInteriors(Family *fam, Topology *topology)
static void TakeClosures(Family *fam, Topology *topology)
static void TakeComplements(Family *fam)
static void TakeUnions(Family *fam)
static void TakeIntersections(Family *fam):
each of the above closes the family under the operation specified
static unsigned long Complement(unsigned long k):
returns the (set-theoretic) complement of the set represented by k
Topology *CreateTopology():
creates/initializes the Topology structure
Family *CreateFamily():
creates/initializes the Family structure
static void FreeTopology(Topology *top);
static void FreeFamily(Family *fam);
the above free memory created by calls to malloc and calloc
Family *ComputeFamily(Topology *topology):
prints/returns the generated family
-------------------------------
*/*