In grad school I ran across an cool problem and an interesting algorithm to solve it. Your input is a grid of elements, lets say rows 1, 2, 3, 4, 5 and columns A, B, C, D, E. In addition, you are given a set of "rectangles" which each consist of a subset of the grid's rows and a subset of the grid's columns. Is there a way to arrange the grid by permuting it's rows and columns such that all the rectangles are present contiguously?

Imagine a rectangle consisting of rows 2 and 5 and columns A, C, and D. The grid must be arranged such that row (2, 5) are contiguous and columns (A, C, D) are contiguous. One rectangle is trivial, multiple rectangles is a challenge. Take a look at the figure which visualizes one of these grids with embedded rectangles.

I realized the 2D problem decomposes into two separate 1D problems. The rows can be arranged without caring about the columns and vice versa. Once you reduce the problem to 1D, it turns out that it is a problem known as the Consecutive Ones Problem. If all you want to do is find an valid ordering, there is even an algorithm to solve the problem. In my case, there was rarely a perfect ordering, so I had to extend the problem to find the best ordering for some definition of best (see this paper on the subject).

That would be the end of the boring story, except I mentioned that there was a algorithm that solved the perfect ordering problem and it was well-studied. It turned out that despite it being well studied, it is poorly known and virtually unreferenced on the internet.

The paper that explained it, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, came out in 1976. The paper doesn't exist anywhere on the internet, not even for purchase. No full description or implementation of the algorithm exists on the internet either. None of this has changed in the 5 years since I looked into this algorithm - still barely any references on the web. I intend to change that today.

The algorithm is called the "PQ-Tree Algorithm". I picked up a copy of the paper in book-form from my local library. Surprisingly, the problem can be solved in linear time. It is quite an intricate algorithm. I think I recall spending 2 weeks doing nothing but implementing this algorithm.

Lets make sure that you know what the problem is first. I'll state it simpler than my above 2D problem:

Furthermore, there may be many of these types of constraints, so perhaps you have (Sue, Fred, Bob) as one constraint and another might be (Sue, Bob, Tom). One possible solution would be given as:

This is the crux of consecutive ones problem, although the consecutive ones problem is formulated a little differently: Given a binary matrix containing only ones and zeros, reorder the columns such that the ones in every row are consecutive. The image below illustrates the point:

The matrix (a) can be transformed to the matrix (b) be rearranging only the columns in (a). The matrix (b) has the consecutive ones property (COP) in that the 1 values in each row are consecutive when read in order. The consecutive ones problem is: Given a matrix (a), determine if it can be converted into a matrix (b) by rearranging columns such that (b) has the consecutive ones property, and if so represent all valid orderings of the columns.

To see that this is the same as the guest seating problem, assign each guest to a column in matrix A. Each row represents one of the constraints we want to apply to our seating - the columns in that row containing 1's are the guests that we want to seat together.

Not all matrices can be transformed into a COP matrix. Similarly, some matrices can have many possible orderings.

I've created a project up at github which tracks the code: PQ Tree Algorithm Implementation.The code (just a library) should be decent, bug-free, and GPL. The first internet implementation out there.

A full description of the PQ Tree algorithm can be found on knol: PQ Trees and the Consecutive Ones Property. I'd recommend checking out the algorithm knol even if just to get a high-level flavor of this interesting algorithm.

If you stumble across this page while trying desperately to do some research for your graduate program, I hope this is useful to you. I ask one small thing of you though. I spent a good bit of time putting all of this together. Drop me a comment or email letting me know how you are using it. That way I'll know it was worth the effort.

Imagine a rectangle consisting of rows 2 and 5 and columns A, C, and D. The grid must be arranged such that row (2, 5) are contiguous and columns (A, C, D) are contiguous. One rectangle is trivial, multiple rectangles is a challenge. Take a look at the figure which visualizes one of these grids with embedded rectangles.

I realized the 2D problem decomposes into two separate 1D problems. The rows can be arranged without caring about the columns and vice versa. Once you reduce the problem to 1D, it turns out that it is a problem known as the Consecutive Ones Problem. If all you want to do is find an valid ordering, there is even an algorithm to solve the problem. In my case, there was rarely a perfect ordering, so I had to extend the problem to find the best ordering for some definition of best (see this paper on the subject).

### The PQ Tree Algorithm

That would be the end of the boring story, except I mentioned that there was a algorithm that solved the perfect ordering problem and it was well-studied. It turned out that despite it being well studied, it is poorly known and virtually unreferenced on the internet.

The paper that explained it, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, came out in 1976. The paper doesn't exist anywhere on the internet, not even for purchase. No full description or implementation of the algorithm exists on the internet either. None of this has changed in the 5 years since I looked into this algorithm - still barely any references on the web. I intend to change that today.

The algorithm is called the "PQ-Tree Algorithm". I picked up a copy of the paper in book-form from my local library. Surprisingly, the problem can be solved in linear time. It is quite an intricate algorithm. I think I recall spending 2 weeks doing nothing but implementing this algorithm.

Lets make sure that you know what the problem is first. I'll state it simpler than my above 2D problem:

### Consecutive Ones Problem

Imagine that you are having a dinner party and are planning the seating arrangement. To simplify the problem, imagine your seating as a one-dimensional ordering of your guests: Sue > Fred > Tom > Rudy > Bob > ... You are trying to choose a seating arrangement that makes the most sense for your guests, and you have a number of constraints that apply to the problem. Each constraint is represented by a subset of your guests which you want to seat together (consecutively). So, if one constraint is that Sue, Fred, and Bob sit together, then there are certain permutations that are invalid and certain permutations that are valid:**Valid**: Rudy >**Sue > Fred > Bob**> Tom**Valid**: Tom > Rudy >**Bob > Sue > Fred****Invalid**: Tom >**Bob**> Rudy >**Fred > Sue**

Furthermore, there may be many of these types of constraints, so perhaps you have (Sue, Fred, Bob) as one constraint and another might be (Sue, Bob, Tom). One possible solution would be given as:

__Tom >__**Sue > Bob****> Fred**> RudyThis is the crux of consecutive ones problem, although the consecutive ones problem is formulated a little differently: Given a binary matrix containing only ones and zeros, reorder the columns such that the ones in every row are consecutive. The image below illustrates the point:

The matrix (a) can be transformed to the matrix (b) be rearranging only the columns in (a). The matrix (b) has the consecutive ones property (COP) in that the 1 values in each row are consecutive when read in order. The consecutive ones problem is: Given a matrix (a), determine if it can be converted into a matrix (b) by rearranging columns such that (b) has the consecutive ones property, and if so represent all valid orderings of the columns.

To see that this is the same as the guest seating problem, assign each guest to a column in matrix A. Each row represents one of the constraints we want to apply to our seating - the columns in that row containing 1's are the guests that we want to seat together.

Not all matrices can be transformed into a COP matrix. Similarly, some matrices can have many possible orderings.

### My Contributions

I implemented this algorithm in grad school. My implementation then was functional but not high quality, and it was embedded in a larger library. I've spent considerable spare time here and there over the last couple months rewriting a large part of that code.I've created a project up at github which tracks the code: PQ Tree Algorithm Implementation.The code (just a library) should be decent, bug-free, and GPL. The first internet implementation out there.

A full description of the PQ Tree algorithm can be found on knol: PQ Trees and the Consecutive Ones Property. I'd recommend checking out the algorithm knol even if just to get a high-level flavor of this interesting algorithm.

If you stumble across this page while trying desperately to do some research for your graduate program, I hope this is useful to you. I ask one small thing of you though. I spent a good bit of time putting all of this together. Drop me a comment or email letting me know how you are using it. That way I'll know it was worth the effort.

### Birds of a Feather

If you are one of the handful of people interested in PQ-Trees and advanced software algorithms like this, you are the type of person I'd like to see working with me at Google. If you send me your resume (ggrothau@gmail.com), I can make sure it gets in front of the right recruiters and watch to make sure that it doesn't get lost in the pile that we get every day.

**Update**: Despite the fact that this post was published in 2008, this offer still stands today.
## 7 comments:

Hi Greg,

very nice article. I'm actually studying a problem very close to this topic. I've downloaded the code of PQ-Tree implementation from your Gregable page on github.com

http://github.com/Gregable/pq-trees/tree/master

But there are relatively few examples. I didn't understand the way to insert a problem. For instance, how can I use the program on the matrix in the blog?

Thank you in advance for the answer!

The API needs a bit more documentation and in fact there is no good way to access more than one possible frontier within the current API. I intend to improve upon this in the future.

For now, take a look at the pqtest.cc file, which should give you a good idea of how to do reductions. The interface you want to interact with is in pqtree.h. Sorry that I don't have a better answer yet, but the code especially is still a little bit of a work in progress.

I added some API improvements so that you can recursively explore the tree if desired. Also the github wiki has a tiny bit of documentation in it. The API is very simple - you can create trees, apply reductions, and then explore or print the tree/frontier.

All of these methods are demonstrated in pqtest.cc and documented pretty well in pqtree.h.

Mate i donno who you are and what you do, But this piece of info you've blogged won here has made my day,

I have my project an 8-credit course on this topic. "COP & CROP" and this info youve written down here has helped me so so much,

Im just grateful to you. I would have never got this useful info without google. so thanks to google too...

And as i said i'll be working on it for the nex 2-3 months and i'll hopefully ask you more Q's and doubts.

Cheers, hope you'll be there to clear my doubts.

I gen'ly dont blog so mail me.

There is another data structure PC-tree for consecutive ones problem.

It is simpler than PQ-Tree.

You can google it.

http://www.google.com.tw/search?q=PC-Tree+consecutive+One+problem&sourceid=navclient-ff&ie=UTF-8&rlz=1B3GGGL_enES303ES303

FYI

There's another implementation in C++, together with a report describing it. The report is available here:

http://www.zaik.uni-koeln.de/~paper/preprints.html?show=zpr97-259

I don't know about the source code/license, but I guess it's free for "academic use".

Very interesting. The paper can be downloaded here

http://www.sciencedirect.com/science/article/pii/S0022000076800451

Thanks!

Post a Comment