Python First-Order Graph Property Library
Project description
Python First-Order Graph Property Library
Pygplib (Python First-Order Graph Property Library) is a Python module for constructing, manipulating, and encoding graph properties expressible with first-order logic of graphs. It serves as a prototyping tool to tackle with various graph related applications. It provides access to state-of-the-art satisfiability technologies without advanced knowledge. Basic steps to follow are :
Express a graph property of interest as a first-order formula.
Set a graph structure, and encode a first-order formula into CNF, a canonical normal form for propositional formulas.
Apply satisfiability tools to the CNF to compute satisfying assignments.
Decode the result into an assignment of first-order variables.
Documentation
For installation, examples, tutorials, and so on, please see online documentation .
Citation
Please cite the following paper if you use pygplib:
@INPROCEEDINGS {10356599, author = {T. Toda and T. Ito and J. Kawahara and T. Soh and A. Suzuki and J. Teruyama}, booktitle = {2023 IEEE 35th International Conference on Tools with Artificial Intelligence (ICTAI)}, title = {Solving Reconfiguration Problems of First-Order Expressible Properties of Graph Vertices with Boolean Satisfiability}, year = {2023}, volume = {}, issn = {}, pages = {294-302}, abstract = {This paper presents a unified framework for capturing a variety of graph reconfiguration problems in terms of firstorder expressible properties and proposes a Boolean encoding for formulas in the first-order logic of graphs based on the exploitation of fundamental properties of graphs. We show that a variety of graph reconfiguration problems captured in our framework can be computed in a unified way by combining our encoding and Boolean satisfiability solver in a bounded model checking approach but allowing us to use quantifiers and predicates on vertices to express reconfiguration properties.}, keywords = {automata;model checking;encoding;artificial intelligence}, doi = {10.1109/ICTAI59109.2023.00050}, url = {https://doi.ieeecomputersociety.org/10.1109/ICTAI59109.2023.00050}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, month = {nov} }
Bugs/Requests/Discussions
Please report bugs and requests from GitHub Issues , and ask questions from GitHub Discussions .
History
Please see CHANGES .
License
Please see LICENSE .
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.