A C++ implementation of Booth & Lueker's PQ-Tree algorithm.

Kellog S. Booth, George S. Lueker, Testing for the consecutive ones property,
interval graphs, and graph planarity using PQ-tree algorithms, Journal of
Computer and Systems Sciences, 13(3) (1976) 335-379.

Testing:
The library is checked by a randomized fuzz test against two independent
oracles (brute-force permutation search on small trees, and a hidden
permutation on large ones), by a structural invariant walk after every
reduction (PQTree::CheckInvariants), and by a deterministic API test. All
tests pass under AddressSanitizer, UndefinedBehaviorSanitizer and
LeakSanitizer. See the Building section below for how to run them.

An independent implementation can be found as a library within BiVoC:
https://bioinformatics.cs.vt.edu/~murali/papers/bivoc/

Description of files:
The main file for this library is pqtree.h.  It contains an API that can be
used by client code for dealing with PQ-Trees.  There are three binaries:
pqtest, apitest and fuzztest.

pqtest runs the pqtree code for one example set of reductions on a single tree,
printing the state of the tree at every step.  This illustrates how the pqtree
is built.

apitest is a deterministic test of the rest of the API: copying, assignment,
SafeReduce, ReduceAll, SafeReduceAll and the accessors.

fuzztest generates random reduction sequences and checks the library against
two independent oracles.  See the comment at the top of fuzztest.cc.

Building:
The build uses CMake (3.20 or newer) and produces a static library, pqtree,
plus the two test binaries:

$ cmake -B build
$ cmake --build build
$ ctest --test-dir build

To build with AddressSanitizer and UndefinedBehaviorSanitizer enabled:

$ cmake -B build-asan -DPQTREES_SANITIZE=ON
$ cmake --build build-asan
$ ctest --test-dir build-asan