- Notifications
You must be signed in to change notification settings - Fork12
The collection of Context-Free Path Querying algorithms
License
FormalLanguageConstrainedPathQuerying/CFPQ_PyAlgo
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
The CFPQ_PyAlgo is a repository for developing, testing and benchmarking algorithms that solve Formal-Language-Constrained Path Problems, such as Context-Free Path Queries and Regular Path Queries. All algorithms are based on theGraphBLAS framework that allows you to represent graphs as matrices and work with them in terms of linear algebra. For convenience, all the code is written in Python usingpygraphblas or in C/C++ using purelySuiteSparse with a Python wrapper.
First of all you need to clone repository with its submodules:
git clone --recurse-submodules https://github.com/JetBrains-Research/CFPQ_PyAlgo.gitcd CFPQ_PyAlgo/ git submodule initgit submodule updateThen the easiest way to get started is to use Docker. An alternative, which is more correct, is to install everything directly.
The first way to start is to use Docker:
# build docker imagedocker build --tag<some_tag>.# run docker containerdocker run --rm -it -v${PWD}:/CFPQ_PyAlgo<some_tag> bash
After it you can develop everything locally and run tests and benchmarks inside the container. Also you can use PyCharm andconfigure an interpreter using Docker.
The correct way is to install everything into your local python interpreter or virtual environment.
First of all you need to installpygraphblas package.
pip3 install pygraphblas
Secondly you need to install cfpq_data_devtools package and other requirements:
cd deps/CFPQ_Datapip3 install -r requirements.txtpython3 setup.py install --usercd ../../pip3 install -r requirements.txt
To check if the installation was successful you can run simple tests
python3 -m pytesttest -v -m"CI"
Look pleaseReadme inbenchmark
Let's describe an example of using the implementation outside this environment.
For example, you want to solve a basic problem CFPQ using the matrix algorithm. To do this, you need a context-free grammar (Gr), as well as a graph (G) in the format of "triplets".
Then the matrix algorithm can be run as follows, wherePATH_TO_GRAMMAR --- path to file withGr,PATH_TO_GRAPH --- path to file withG
from src.problems.Base.algo.matrix_base.matrix_baseimport MatrixBaseAlgofrom cfpq_dataimport cfg_from_txtfrom src.graph.graphimport Graphfrom pathlibimport Pathalgo= MatrixBaseAlgo()algo.prepare(Graph.from_txt(Path(PATH_TO_GRAPH)), cfg_from_txt(Path(PATH_TO_GRAMMAR)))res= algo.solve()print(res.matrix_S.nvals)
The given fragment displays the number of pairs of vertices between which the desired path exists.
More examples can be found intest
The global project structure is the following:
.├── deps│ └── CFPQ_Data - repository with graphs and grammars suites├───benchmark - directory for performance measurements of implementations├── src│ ├── problems - directory where all the problems CFPQ that we know how to solve│ │ ├───AllPaths│ │ ├───Base│ │ ├───MultipleSource│ │ └───SinglePath│ ├── grammar - directory for all grammar formats representation and its loading │ ├── graph - directory for all graph formats representation and its loading│ └── utils - directory for other useful classes and methods└── test ├───AllPaths - tests for implementations in src.problems.AllPaths ├───Base - tests for implementations in src.problems.Base ├───data - dataset for tests ├───MultipleSource - tests for implementations in src.problems.MultipleSource ├───SinglePath - tests for implementations in src.problems.SinglePath └───suitesAbout
The collection of Context-Free Path Querying algorithms
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Uh oh!
There was an error while loading.Please reload this page.
Contributors7
Uh oh!
There was an error while loading.Please reload this page.