This tie-up is written for a loom with 6 shafts and 6 treadles; but suppose that because of an accident, my loom is broken and only has 5 working treadles. I want to weave the pattern on my 5-treadle loom. LoadPattern()The first thing weavereduce.cgi does is to verify that the number of shafts and treadles I gave it make sense. It then calls LoadPattern(InputString), which constructs a collection of sets, one for each treadle in the original tie-up. I call these sets targets, so they end up in an array of sets called TargetArray.In keeping with C convention, let's number the rows in our example tie-up with numbers 0-5, starting in the top row. The leftmost treadle corresponds to the set {1,3}, since that treadle is tied to shafts 1 and 3. (Remember that we are numbering from the top, and that the top row is row 0.) The next treadle corresponds to the set {0,2,3,5}, and so on. At the end of LoadPattern(), the array TargetArray contains the following 6 target sets: Targets:
The goal is to find a collection of 5 sets, one for each working treadle of my loom, such that each target set is either one of these 5 sets, or a union of 2 of them. The trouble with this goal is that even in this simple example, there are 63 non-empty subsets of {1, 2, 3, 4, 5, 6}; and there are 7,028,847 collections of 5 subsets. If we were trying to reduce a 14-treadle tie-up so we could weave it on a 10-treadle loom, then the number of collections we'd have to consider would be 382,805,484,029,414,797,963,859,411,093,325,825, which is too many to examine. We therefore need to do something to reduce our search space. The nice thing turns out to be that if we're a bit clever, we can reduce the search space dramatically without throwing away any possible solutions. How we do this is what makes the subsequent code interesting. DeChaff()Next, there are two bits of bookkeeping. A timer is started which will terminate processing after the interval specified by the user. Then the original tie-up is printed, and the function DeChaff() is run. DeChaff() removes from the TargetArray any target sets corresponding to treadles tied to no shafts or to treadles that repeat the same set of shafts as another treadle. These shouldn't ever appear in a tie-up anyway, but it takes little time to remove them if they do. If DeChaff() removes any targets, then it prints a message and prints the tie-up minus the targets removed.BricksAs we just said, we're looking in our example for a collection of 5 sets such that each of our 6 targets is either one of the 5 sets or a union of 2 of them. Where should we look for these sets?My colleague Tekla Lewin was able to prove that the only sets we need to consider as candidates for our 5 sets are intersections of 1 or more targets. That is, if we can find a collection of 5 sets that does the job, then Tekla proved we can also find a collection of 5 sets all of which are intersections of 1 or more targets that also does the job. I call these intersections bricks, since they are the pieces that will be put together to build the target sets. The next job is therefore to find all the possible bricks - all the sets that are intersections of 1 or more target sets. The functions InitializeBrickList() and MakeBricks() produce all the bricks, and store them in the list BrickList. This is done by first listing all the targets (since every target is a brick), and then starting down the list and intersecting each brick with all the bricks that follow it on the list. Any new set so produced is added to the end of BrickList. In our example, there are 19 bricks, listed here: Bricks:
We can now refine our goal. We want to find a set of 5 bricks such that every target is either a brick or an intersection of 2 bricks. There are only 11,628 collections of 5 bricks; so directly examining all the collections via some sort of depth-first search seems eminently possible. Unfortunately, for larger problems, life is not so nice. When reducing a 14-treadle tie-up to 10 treadles, there often seem to be about 30 bricks; which means that there are 30,045,015 collections to consider. This is probably at the border of possibility in reasonable time, but a slightly larger problem with 50 bricks where we were reducing from 16 to 14 treadles would mean examining 937,845,656,300 collections, which is currently out of the question. So we still need to refine our search technique. MakeTargetOptions()What we'll do is to conduct a depth-first search through the collections of bricks to find a solution; but we want to make the search as efficient as possible. We'll do this by pre-computing as much information as we can, and by sorting the bricks into an order that makes the top of the search tree as narrow as possible, so that we prune as many nodes as possible each time we are forced to backtrack.The first step of this is in the function MakeTargetOptions(), which builds an array called TargetOptionsArray. Each entry in this array is a record consisting of a target set together with a list of pairs of bricks, where each pair consists of two bricks, neither of which is the target, but whose union is the target. That is, each record shows a target set along with every way to build that target set as a union of 1 or 2 bricks. Producing these records isn't hard, since we only need to look at all the pairs of bricks, of which there aren't many. (Even with 50 bricks, we'd only have to examine 1225 pairs.) In our example, the records in TargetOptionsArray are the rows in the following table.
Preparing for the Depth-First SearchNow the structure of our search is starting to become clear. We know from the table above that one of our 5 bricks has to be {0,2,3,5}, since there is no way to get this target as a union of 2 smaller bricks. We also know that we have to choose either {1,3} or both the bricks {1} and {3}; since these are the only 2 ways to get the target {1,3}. It also seems clear that the next thing we ought to do is to examine each of the 7 possible options to get the target {1,2,3}, rather than looking at the other targets, which can be obtained in 8 or in 12 possible ways. In particular, we ought to put off considering the target {2,3,4,5} as long as possible, in hopes either that we will get down to that target and find that it can already be obtained as a union of two selected bricks, or that the search will be forced to backtrack before we get down to {2,3,4,5}.The first thing we do to get ready for the search is therefore to call SortTargetOptions, which rearranges the records in TargetOptionsArray so that those with the fewest possible options come first in the array. So far, we have been dealing with the bricks as sets (i.e., as BigSet structs). We want now to start dealing with collections of bricks, and asking whether or not given bricks live in given collections. If we're not careful we'll end up wasting a lot of time comparing BigSets. It therefore makes more sense to number the BigSets, and to replace each of the sets in the pairs in the table above (i.e., in TargetOptionsArray) with the corresponding number. Then each pair will be a pair of ints, not a pair of BigSets, which will speed up comparisons a lot. For technical convenience, we start by looking again at our list of 19 bricks. Not all these bricks actually turn up in the table above: the brick {5} was never used in building any target. The function RemoveUnusedBricks() removes from our list of bricks these extraneous bricks, and adjusts BrickCount accordingly. The function OptionsToSets() carries out the last piece of preprocessing before we start the depth-first search. It builds a global array, BrickArray, containing the remaining bricks. (We can use an array instead of a list since we now know the exact number of bricks we have to deal with, and since we would like to be able to access random bricks quickly.) It also builds a global OptionsArray holding the pairs of ints corresponding to the pairs of bricks in the table above. When OptionsToSets is finished, we have 3 important global arrays: TargetArray holds the target sets, which in our example are numbered like this: Targets:
BrickArray holds the remaining bricks. In our example, only the brick {5} was unused; so there are 18 remaining bricks, numbered like this: Bricks:
OptionsArray holds lists of pairs of bricks. Each list corresponds to 1 of the target sets. The list corresponding to a target contains every pair of bricks that can be used to form that target. In our case, OptionsArray looks like this: Representations of targets in terms of bricks:
The next list, OptionsArray[1], says that our set of 5 bricks needs to include either brick 0, or both bricks 6 and 7. This means we either have the brick {1,3} or both the brick {3} and the brick {1}; so this list is telling us how to get the target {1,3}. The list in OptionsArray[2] starts with {5,5}, which means it must correspond to brick 5, which is target 5, the set {1,2,3}. This row says we can get the target {1,2,3} either by using brick 5, or by using both bricks 11 and 16, or by using both bricks 7 and 11, and so on. The remaining rows correspond to targets 3, 4, and 2, resp. The Depth-First SearchDFS() is the function that now carries out the depth-first search. It's a bit messy to read, but it just starts with and empty set and adds the first entry in each list in OptionsArray, looking for a set of 5 bricks that can form all the targets. So it will initially add bricks 1, 0, 5, 3, and 4 in order, then find that target 5 still isn't included. At this point, it backtracks, removing brick 4 and trying to add bricks 15 and 16, the next options in OptionsArray[4]. Neither this nor any of the other choices in OptionsArray[4] work, so it backtracks further, removing brick 3 as well. The set now contains only bricks 1, 0, and 5. We try adding in bricks 12 and 14, the next option in OptionsArray[3], but this fails to give us target 4, so we remove these and try adding 9 and 14, and so on.In the example, success is finally attained with the bricks 0, 1, 11, 15, and 16, which are gotten by picking {1,1} from OptionsArray[0], Printing the ResultsNow all that's left to do is to print the solution, which is done, logically enough, by PrintSolution(). In our example, we get toldHere's one solution: Tie up your loom like this:
The treadles of the original tie-up correspond to treadles or pairs of treadles in the reduced tie-up according to the following table:
On the set-theoretic level, our solution consisted of bricks
The bottom table of the output tells how to obtain each of the original 6 treadles (targets) using intersections of 1 or 2 of the 5 working treadles on our loom (bricks). That's the whole story. To anyone still reading at this point, congratulations! Questions of EfficiencyDuring the 2 years people have been using the Treadle Reducer, I haven't had complaints about its speed; so it would seem as though the design outlined here works fast enough for the problems most people are throwing at it.When I profile the weavereduce.cgi under typical inputs, I find that over 99% of the CPU time is used by the single function DFS that does the depth-first search. Since the whole design of the program has been aimed at making the depth-first search as efficient as possible, and since I've worked to make DFS as efficient as I can (at major cost to its readability), there are probably no simple modifications that will yield order of magnitude improvements in efficiency. Of course, it is always possible that a clever new algorithm might be found to replace what is at bottom a rather unrefined brute-force search. Closing CommentsI hope that this summary helps to clarify the design and function of the Treadle Reducer's source code. Again, it's all available to anyone who wants it under the terms of the GPL. Should you wish to make use of it, though, I would appreciate very much hearing from you. This project was a fun one for me, but it's also lovely to hear from people who find the Treadle Reducer useful.Finally, comments on the source code from either an algorithmic or a software engineering perspective are more than welcome. Be nice, though; I don't claim to be more than an enthusiastic amateur.
Tim McLarnan,
|
Page last updated: August 28, 2008