Progress report for week 41

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.


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: