# rocq-community/graph-theory architecture

> Architecture diagram of the GitHub repository rocq-community/graph-theory, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-04-01). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/rocq-community/graph-theory
- Repository: https://github.com/rocq-community/graph-theory

## Overview

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.

## Diagram (Mermaid)

```mermaid
flowchart TD
    CI["CI/CD Pipeline"]:::ci
    ED["External Dependencies & Documentation"]:::ext
    Build["Build & Packaging"]:::build
    Core["Core Graph Theory Module"]:::core
    Planar["Planar Graph Extensions"]:::planar

    CI -->|"triggers"| Build
    ED -->|"provides"| Build
    Build -->|"compiles"| Core
    Build -->|"compiles"| Planar
    Core -->|"extended by"| Planar

    click CI "https://github.com/rocq-community/graph-theory/blob/master/.github/workflows/docker-action.yml"
    click ED "https://github.com/rocq-community/graph-theory/blob/master/README.md"
    click Build "https://github.com/rocq-community/graph-theory/tree/master/Makefile"
    click Core "https://github.com/rocq-community/graph-theory/tree/master/theories/core"
    click Planar "https://github.com/rocq-community/graph-theory/tree/master/theories/planar"

    classDef core fill:#AED6F1,stroke:#1B4F72,stroke-width:2px;
    classDef planar fill:#F9E79F,stroke:#B7950B,stroke-width:2px;
    classDef build fill:#A9DFBF,stroke:#196F3D,stroke-width:2px;
    classDef ci fill:#F5CBA7,stroke:#943126,stroke-width:2px;
    classDef ext fill:#FADBD8,stroke:#922B21,stroke-width:2px;
```
