How rocq-community/graph-theory works
This project is a formal Coq library for graph theory, aimed at formalizing standard and recent graph theory results—including proofs of Menger’s theorem, variants of Wagner’s theorem, and various graph isomorphism properties. The focus is on highly structured formal proof developments using Coq, with a clear separation between core graph theory results and specialized planarity results.
Main Components
• Core Graph Theory Library – Represented by the theories/core directory. This component contains the essential graph theory development: proofs, definitions (e.g., for digraphs, trees, partitions, minors), and supporting files (e.g., Makefiles for building).
• Planar Graph Theory Extension – Represented by the theories/planar directory. This is an extension of the core library providing planarity-specific results (for example, a Coq formalization of Wagner’s theorem and related results). Indicate that this builds on and interacts with the core library.
• Build and Dependency Management – Represented by the top-level Makefile files, the dune-project information, and opam package files (e.g., coq-graph-theory.opam, coq-graph-theory-planar.opam). This shows how the project is built, tested, and installed using standardized tools (Make, dune, opam).
• Continuous Integration and Release Systems – Include the .github directory that contains CI/CD workflows (docker-action.yml) for automated testing and building.
Relationships and Interactions
• The core and planar components are connected: the planar module extends the core with additional theories while relying on the common definitions.
• The build system (Makefile and dune configurations) orchestrates compiling these Coq files and integrating them into the final library.
• Opam packaging ensures that users (and continuous integration systems) can install the libraries separately or together, reflecting their dependency relationships.
• CI pipelines from GitHub (via docker-action.yml) trigger automated builds and tests upon changes, ensuring the correctness of proofs during development.
Architectural Patterns and Design Principles
• Layered Architecture – Separate the core graph theory proofs from the planarity extensions.
• Modular Design – Each theory is developed as a module (or in separate files) that can be independently compiled and then integrated into the larger library.
• Dependency Management – Clear use of external dependencies (MathComp libraries, hierarchy-builder) and organized build scripts (Makefiles, dune files) facilitate robust development and integration.
• Formal Verification Workflow – The project reflects a disciplined approach to formal proof development using Coq, where each file corresponds to logical components of the overall theory.
Relevant Technologies and Tools
• Coq – The primary proof assistant used for formal development.
• Make, dune – Used for building and managing the Coq projects.
• opam – The package manager for installing the Coq packages.
• GitHub and Docker – For CI/CD and automated testing.
• External libraries – MathComp (SSReflect, Algebra, finmap, etc.) and Hierarchy Builder.