pq-trees

pq-trees copied to clipboard

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.

IMPORTANT NOTE: This code currently is known to be buggy on some rare inputs. A believed to be correct, but harder to use version of this code 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 two binaries: fuzztest and pqtest.

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.

fuzztest generates a large random set of possible reductions and runs them against the library making sure that it never returns false or segfaults.

Usage: Primarily, this is intended to be used as a library, not a binary. But you can still compile and run the binaries |pqtest| and |fuzztest|. My personal recommendation would be to compile with scons, http://scons.org/. To do so, run:

$ scons $ ./fuzztest $ ./pqtest

Alternatively, I also handily include the tried and true MakeFile, so if you don't have scons on your system and don't feel like installing it, instead just run:

$ make $ ./fuzztest $ ./pqtest