One of the tools in our research on the expressive power of (fragments of) Tarski's relation algebra is a bruteforce tool. This tool can compute every possible query result one can obtain via queries expressed in a given query language and evaluated on a given graph. Using these computations, we can determine results on the expressive power for Boolean queries and path queries.
The first such tool was developed by Jan Van den Bussche, and was used to help with obtaining the results in
The version I used for my PhD thesis and for several papers started as a clean reimplementation from scratch with the aim of making a high-performance bruteforce tool while, at the same time, playing around with the new features in C++11 (and later C++14).
I have developed two versions of the bruteforce tool, which are available for public use under the BSD-license (license details included in the source files):
There is a set of notes. This note should give a clear idea of the basic working of the bruteforce technique to prove results on the expressive power. The note also describes some of the implementation details in the above two bruteforce programs These notes where originally planned to be part of another new version of the bruteforce program that improved on the programs above. Consequently, not all details in the note match the implementations above, but especially the part on Boolean matrix multiplication techniques can prove to be useful.
The bruteforce results in my thesis can be obtained by feedinf the clean bruteforce program the following script.