Single-path results for context-free path queries

To evaluate path queries, one typically resorts to the relational semantics in which node pairs (m, n) are returned that are connected by a path of interest. A popular way to specify paths of interest is by the labeling of the edges of the path, e.g., by specifying languages of allowed labeling. Unfortunately, this relational semantics provides little insight in how node pairs (m, n) are obtained. To improve on this, we propose the single-path semantics, in which path queries are answered by minimal-length paths between such node-pairs.

Our implementation of query evaluation using the single-path semantics allows one to evaluate context-free path queries. Furthermore, the underlying algorithms can also be used to efficiently determine the shortest strings in a context-free grammar. Our implementation is in C++14 and is tested using two modern C++ compiler, namely the Microsoft Visual C++ compiler and the GNU g++ compiler. We have one external dependency, namely the Fibonacci Heap implementation of the Boost library. The implementation is available for public use under the BSD-license (license details included in the source files):

The implementation of single-path semantics
for the evaluation of context-free path queries using single-path semantics. Also included are dataset generators in accordance with the experiments and the raw experimental results.