This week I have been working on a way to implement my Dancing Links parallelization idea. I found out that my DLX library implementation was too monolithic so I had to devise a plan to split it up into smaller pieces. Currently it has been divided into the following parts:
- dlx – The Dancing Links algorithm library is where the exact cover problem is actually solved. It depends on the sbmatrix library to provide the matrix data structure.
- sbmatrix – The Sparse Boolean Matrix library takes care of the exact cover matrix data structure. It is entirely self contained and can easily be used independently of the DECS project.
- fileio – File Input/Output library which deals with the DECS file format. It can read/write matrices from/to file by using the data structure provided by sbmatrix . It should also be the only place where byte ordering problems are “take care of”.
Work is currently in under way to complete the migration to the new modular approach. The benefits will be much looser coupling between the components which will allow better extensibility, better integration of existing components and less code duplication.
I finally undestood how Donald Knuth’s own Dancing Links implementation in C (CWEB) works. The GOTO statements did a good job in obscuring the actual flow of control. Using plain loops, like the pseudo code in his paper, would have made a big difference in readability. The implementation didn’t provide any additional insight so it was probably a waste of time to study it, except as an exercise to better learn C.
The DLX library has been improved by adding some cleanup functions which should eliminate most of the previous memory leaks. The it’s learning ePortfolio host also looks like it has stabilized. yey…
NOTE: This post has been imported from my old it’s learning ePortfolio DECS blog.