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