An emscripten/WebAssembly version of the UFPC implementation of the Hsu-McConnell algorithm for producing PQ-/PC-trees for the (circular) consecutive ones problem. See the paper "Experimental Comparison of PC-Trees and PQ-Trees" by Fink et al. for more details on this implementation. This project was initiated by Dominik Peters, with some updates by Simon D. Fink.
Graphical Online Version available at n-coder.github.io/pqtree.js
The online version is also automatically built by CI.
To build the emscripten version, assuming emscripten is installed so emcc is callable:
./build.shUse it as follows in HTML:
<script src="libPCTree.js"></script>
<script>
var Module = {
onRuntimeInitialized: function () {
const is_circular = false; // use linear orders and PQ-trees
// (instead of cyclic orders and PC-trees)
Module.setRestrictions("001010\n011010\n011101", is_circular); // returns true
Module.setRestrictions("11000\n00110\n11110\n10101", is_circular); // returns false
}
};
</script>Function setRestrictions returns true if an order exists and the corresponding tree has been stored in internal
state,
or false if no such order exists and the internal state has been cleared.
See the further methods in glue.cpp for methods for querying the tree stored in internal state.