PQ-tree

PQ-tree is a data structure for representing permutations. It's useful for solving the consecutive ones problem.

This is an implementation of PQ-tree as described by Booth and Lueker. The tree consists of three types of nodes, P, Q and leaf. Leaves are single elements. The frontier of the tree is the left to right order of leaves in the tree. A P-node is equivalent to another with its children permuted in any order. A Q-node is equivalent to one with its children reversed. The permutations represented by a tree are the frontiers of all equivalent trees.

The various reduction templates described in Booth and Lueker's paper are used, but the construction algorithm is not. This implementation is purely functional, hence it uses a simpler top-down approach instead that runs in O(n) time (plus set member check overheads) rather than in O(update size). This implementation is specialized to Ints, but can be modified to work with other types.

Sources:

• https://en.wikipedia.org/wiki/PQ_tree
• Kellogg S. Booth and George S. Lueker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", 1976 https://www.sciencedirect.com/science/article/pii/S0022000076800451