Ctrl+K

MS_Reachability#

Info#

Full Name

Multiple-Source_Reachability_Benchmark

Version

4.0.0

Direct download

.tar.gz

Description#

This benchmark contains graphs, queries, sets of source vertices, and results for the multiple-source formal-language-constrained reachability problem. For each graph we provide the following benchmark information:

  • graph -- contains a graph and its statistics (.csv + .md)

  • queries -- contains different regular queries in the form of regular expressions

  • results -- contains files with pairs of vertices <src, dest> where 'src' is a source vertex and 'dest' is a vertex reachable from the 'src' vertex with respect to a particular query and a set of source vertices

  • src_vertices -- contains different sets of source vertices

More information about multiple-source formal-language-constrained reachability problem can be found in "Multiple-Source Context-Free Path Querying in Terms of Linear Algebra"

Graphs Used#

Graph

Num Nodes

Num Edges

Download

core

1323

2752

.tar.gz 📥

enzyme

48815

86543

.tar.gz 📥

eclass

239111

360248

.tar.gz 📥

go

582929

1437437

.tar.gz 📥

Query Examples#

\[\begin{split}\textit{type} \, \textit{isDefinedBy}^{*} \, \textit{type}\\\end{split}\]

Pyformlang Regex:

type isDefinedBy* type
\[\begin{split}(\textit{rest} \, | \, \textit{label} \, | \, \textit{range} \, | \, \textit{type} \, | \, \textit{comment}) \, \textit{seeAlso}^{*}\\\end{split}\]

Pyformlang Regex:

(rest | label | range | type | comment) seeAlso*

Useful utilities#

For this benchmark we provide some useful functions from Graph utilities. For example, the set of source vertices can be saved to the TXT file or it can be loaded from benchmark by using functions multiple_source_from_txt and multiple_source_to_txt.

import cfpq_data

s = {1, 2, 5, 10}
path = cfpq_data.multiple_source_to_txt(s, "test.txt")
source_vertices = cfpq_data.multiple_source_from_txt(path)
On this page