Graphs from Context-Free Grammars.
Project description
NeoGrammarGraph
Creating graphs from context-free grammars for fun and profit.
This project is a re-implementation of GrammarGraph based on the efficient graph-tool library. As of now, it does not support the full set of features supported by GrammarGraph; however, all implemented features should work significantly more efficiently thanks to graph-tool.
Supported Features
- Reachability of grammar symbols.
- Computing shortest paths between grammar symbols.
- Export to GraphViz DOT files.
Planned Features
- Creating sub graphs
- Filter abstraction
- Checking whether a (sub) graph represents a tree
- Computing k-paths (paths of exactly length k) in grammars and derivation trees, and a k-path coverage measure (see this paper) of derivation trees based on that.
Install
NeoGrammarGraph requires at least Python 3.10 and a working installation of graph-tool.
We refer to the graph-tool homepage (https://graph-tool.skewed.de/) for instructions
on how to obtain graph-tool. On a MacOS system, we recommend the installation using
homebrew
; on Debian/Ubuntu, there's a custom APT repository to be used with apt-get
.
We recommend installing NeoGrammarGraph in a virtual environment. Example usage (inside project directory):
python3.10 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
# Run tests
python3 -m pytest
On MacOS (maybe also on other systems), it might be required to link the graph-tool
library into the virtual environment. If you used homebrew
to install graph-tool,
an example command-line invocation could look as follows (you might have to update
some paths depending on the Python/graph-tool versions on your system):
ln -s \
/usr/local/Cellar/graph-tool/2.51/lib/python3.11/site-packages/graph_tool \
venv/lib/python3.10/site-packages
For the GitHub workflow, the following line was required:
sudo ln -s \
/usr/lib/python3/dist-packages/graph_tool \
/opt/hostedtoolcache/Python/3.10.11/x64/lib/python3.10/site-packages
Author: Dominic Steinhöfel.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for neo_grammar_graph-0.0.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 422339b5ff21da519993cc2c25fe1a489b0898b95bd836b9a949cd334e678527 |
|
MD5 | d5f691dd097343ab66f22ddaa45bc946 |
|
BLAKE2b-256 | 21e7b162b7d4d056fb2a30855112f477a90b52f6d4b43f4e8ed975b128595dd2 |