1 /* 2 --------------------------------------------------------------------------- 3 BOUND.H 4 Declarations of public routines found in bound.c 5 Macros dealing with weave boundaries 6 Public Domain 7 --------------------------------------------------------------------------- 8 */ 9 10 #ifndef BOUND 11 #define BOUND 12 13 #include "standard.h" 14 #include "poly.h" 15 16 #define MAXSTRING 12 17 #define BIGWEAVE (2*MAXSTRING+2) 18 19 /* 20 --------------------------------------------------------------------------- 21 This algorithm models the solved region of a link by a set of simple 22 weaves and their associated polynomials, which are called tags. Due to a 23 nice result, any simple weave is uniquely defined by how its inputs are 24 matched to its outputs. A list of the outputs the inputs are matched to, 25 in the order of the inputs, is enough to define a simple weave. 26 Unfortunatly, there is no similar result about the associated tags. Since 27 I've never seen a workstation capable of storing 9! polynomials, it 28 is reasonable to assume no weave of more than 8 inputs ever needs to be 29 dealt with. Weaves of 8 inputs have 16 boundary crossings, so any reduced 30 weave with 8 inputs or less can be stored in (8 copies of 4 bits =32 bits). 31 The size of an integer nowadays is, you guessed it, 32 bits. Something of 32 type WEAVE is just a simple weave and its tag. BODY is a compressed 33 representation of the simple weave itself. TAG is the polynomial 34 associated with that simple weave. 35 --------------------------------------------------------------------------- 36 */ 37 38 struct weave 39 { 40 ub4 boundary[2]; /* Representation of the weave, heavily encoded. */ 41 Poly tag; /* Polynomial associated with link represented by weave */ 42 }; 43 typedef struct weave weave; 44 45 /* 46 --------------------------------------------------------------------------- 47 Global Variables -- located in bound.c 48 --------------------------------------------------------------------------- 49 */ 50 extern word list[]; /* description of first new weave */ 51 extern word list2[]; /* description of second, if needed */ 52 extern word old_going_in[]; /* Was *i* an input? *old_going_in[i]*. */ 53 extern word going_in[]; /* Will *i* be an input? *going_in[i]*. */ 54 extern word map[]; /* i of old weave becomes map[i] of new weave */ 55 extern word first; /* first boundary crossing to remove */ 56 extern word second; /* second boundary crossing to remove */ 57 extern word right; /* Is the crossing being added righthanded? */ 58 extern word oldcross; /* number of boundary crossings in the old weave */ 59 extern word newcross; /* number of boundary crossings in each new weave */ 60 extern word oldin; /* number of inputs to the old weave */ 61 extern word newin; /* number of inputs to the new weave */ 62 63 /* 64 --------------------------------------------------------------------------- 65 Procedures defined in bound.c 66 --------------------------------------------------------------------------- 67 */ 68 69 /* Manipulate those variables whose values are universal to all weaves at a 70 given step. (These are the global variables declared above). */ 71 void b_manip(weave *oldweaves); 72 73 /* Add a crossing to a single weave without removing any pair of boundary 74 crossings. Compute list, and perhaps list2, describing the new simple 75 weaves. */ 76 void b_no_pairs(word *list, word *list2, word *one, word *two); 77 78 /* Add a crossing to a simple weave and remove one pair of boundary crossings. 79 If the result is one or two simple weaves, well and good. If the result 80 is more complicated than that, b_one_pair is essentially a no-op. */ 81 void b_one_pair(word *list, word *list2, word *one, word *two); 82 83 84 /* 85 --------------------------------------------------------------------------- 86 There are three representations of weave boundaries. 87 1) *list* is an array of words of size oldcross saying which crossing 88 is attached to which other crossing. If list[i]==j, list[j]==i. 89 2) The medium-size representation (two ub4's) stores the values of 90 *list* for only the inputs (the output can be deduced). Further, each 91 value is stored in 5 bits, with 6 values per ub4. 92 3) The tiny representation recognizes that the medium-size representation 93 is a permutation of the outputs, and permutations can be enumerated. 94 The tiny representation is the number for that permutation. 95 --------------------------------------------------------------------------- 96 */ 97 98 /* 99 --------------------------------------------------------------------------- 100 The macro b_cross determines if two strings cross in a simple weave in 101 standard form. This formula has been proven to be correct 102 (via a large truth table). 103 --------------------------------------------------------------------------- 104 */ 105 #define b_cross( inp1, inp2, outp1, outp2) \ 106 (((inp1)<(inp2))==((inp2)<(outp1))==((outp1)<(outp2))==((inp1)<(outp2))) 107 108 109 /* 110 --------------------------------------------------------------------------- 111 Switch the positions of *first* and *second* in the boundary *list*. 112 --------------------------------------------------------------------------- 113 */ 114 #define b_switch( list, first, second, temp ) \ 115 if (1) \ 116 { \ 117 list[list[first]] = second; \ 118 list[list[second]] = first; \ 119 temp = list[first]; \ 120 list[first] = list[second]; \ 121 list[second] = temp; \ 122 } else 123 124 125 /* 126 --------------------------------------------------------------------------- 127 Should the crossing of *first* and *second* in *list* be righthanded? *i*. 128 Boundary crossings are numbered counterclockwise. Inside a simple weave, 129 the string with the lowest input should be an overpass. 130 --------------------------------------------------------------------------- 131 */ 132 #define b_right( list, going_in, first, second, i ) \ 133 if (1) \ 134 { \ 135 word x = first < list[first] ? first : list[first]; \ 136 word y = second < list[second] ? second : list[second]; \ 137 if (x > y) {i = x; x = y; y = i;} \ 138 i = !(going_in[x] && !going_in[y]); \ 139 } else 140 141 #endif /* BOUND */ 142