# msakai/toysolver architecture

> Architecture diagram of the GitHub repository msakai/toysolver, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-03-29). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/msakai/toysolver
- Repository: https://github.com/msakai/toysolver

## Overview

##### Main Components
- Command-Line Front-Ends: These include the entry points found in the “app” directory such as toysolver (arithmetic-based), toysat (SAT-based), toysmt (SMT solver built on toysat), toyfmf (finite model finder), and toyconvert (file format converter). Each provides a unique interface for various problem types.
- Solver Library Modules: The “src/ToySolver” directory encapsulates the core solver functionalities. For example:
– Arithmetic and optimization modules (found under “src/ToySolver/Arith”) for MILP, linear programming (Simplex, FourierMotzkin, etc.), OmegaTest, and others.
– SAT solving modules (under “src/ToySolver/SAT”) that implement different encoding strategies (Tseitin, cardinality encoders, PB encoding) and solver strategies such as CDCL and SLS.
– SMT and Boolean modules (e.g., “src/ToySolver/SMT”, “src/ToySolver/BitVector”) that extend SAT capabilities.
– Data and conversion libraries (under “src/ToySolver/Data” and “src/ToySolver/Converter”) that handle input problem formats, algebraic numbers, boolean expressions, and file format conversions.
- Support and Utility Components: This includes internal utility functions (found in “src/ToySolver/Internal”), file format parsing (“src/ToySolver/FileFormat”), and graph/combinatorial logic for problems like Max Cut and Knapsack.
- Testing & Benchmarks: The “test” directory and “benchmarks” folder both serve to validate and evaluate the various algorithms across a range of input formats.

##### Relationships and Interactions
- The CLI front-ends (toysolver, toysat, etc.) are the user interfaces that accept input files (in formats such as .cnf, .lp, .mps, etc.) and then route these inputs to appropriate solver libraries.
- The input files are parsed by FileFormat modules. If conversions are needed (e.g., between CNF and OPB or LP formats), the Converter modules are used.
- The parsed input is then processed by the appropriate solver engine (arithmetic, SAT, SMT, etc.) that is implemented in the corresponding submodules (Arith, SAT, etc.).
- The solvers use several common utility modules (Data, Internal, Graph) and leverage shared algorithms for different problem constructs.
- Results are then output back to the user through the command-line, and can also be used by other tools (such as the ersatz-toysat and satchmo-toysat bindings).

##### Architectural Patterns and Design Principles
- Modularity: There is a clear separation between the CLI layer (in “app”) and the core libraries (in “src/ToySolver”). Each solver category (SAT, SMT, arithmetic) is implemented in its own set of modules.
- Reusability and Functional Purity: Being written in Haskell, much of the code is composed of pure functions and modular components that can be reused across multiple solver tools.
- Layered Architecture: At the top, the front-ends handle user interactions; the middle layers handle parsing, data mapping, and conversion; and the bottom layer contains the core algorithms that perform the actual computation.
- Extensibility: The project is structured so that additional solver paradigms or conversion routines can be easily integrated.

##### Relevant Technologies and Frameworks
- Haskell and its package management (Stack) are central to the project.
- Integration with C components is visible in the “app/toysat-ipasir” directory (notably ipasir.h, ipasir.c, etc.) for performance-critical SAT solving – indicating a foreign function interface (FFI).

##### Elements
– CLI Applications: toysolver, toysat, toysmt, toyfmf, toyconvert.
– Core Solver Modules: Arith, SAT, SMT, Combinatorial, Data, Converter.
– Support/Utility Modules: Internal, FileFormat, Graph.
– External Dependencies: Haskell’s runtime, potential C libraries (as seen in toysat-ipasir), and any third-party bindings like ersatz-toysat.
– From input files flowing into the CLI.
– From the CLI to file format parsing and conversion layers.
– From converter modules to the specific solver engines.
– From solver engines back to the CLI output.

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Input Layer
    InputFiles["Input Files"]:::input

    %% CLI Applications Subgraph
    subgraph "CLI Applications"
        toysolver["toysolver"]:::cli
        toysat["toysat"]:::cli
        toysmt["toysmt"]:::cli
        toyfmf["toyfmf"]:::cli
        toyconvert["toyconvert"]:::cli
        IPASIR_FFI["IPASIR FFI"]:::cli
    end

    %% Parsing & Conversion Subgraph
    subgraph "Parsing & Conversion"
        FileFormat["FileFormat Parsing"]:::utility
        Converter["Converter"]:::utility
    end

    %% Core Solver Modules Subgraph
    subgraph "Core Solver Modules"
        subgraph "Solver Engines"
            Arith["Arithmetic & Optimization"]:::solver
            SAT["SAT Solving Modules"]:::solver
            SMT["SMT Modules"]:::solver
            BitVector["BitVector Module"]:::solver
        end
    end

    %% Support/Utility Modules Subgraph
    subgraph "Support / Utility Modules"
        Internal["Internal Functions"]:::utility
        Graph["Graph/Combinatorial"]:::utility
        DataLib["Data Library"]:::utility
    end

    %% Testing & Benchmark Subgraph
    subgraph "Testing & Benchmarks"
        Tests["Tests"]:::test
        Benchmarks["Benchmarks"]:::test
    end

    %% Connections
    InputFiles -->|"provides input"| toysolver
    InputFiles -->|"provides input"| toysat
    InputFiles -->|"provides input"| toysmt
    InputFiles -->|"provides input"| toyfmf
    InputFiles -->|"provides input"| toyconvert

    %% CLI to Parsing & Conversion flow
    toysolver -->|"reads"| FileFormat
    toysat -->|"reads"| FileFormat
    toysmt -->|"reads"| FileFormat
    toyfmf -->|"reads"| FileFormat
    toyconvert -->|"reads"| FileFormat

    FileFormat -->|"parses into"| Converter

    %% Parsing to Core Solver Modules
    Converter -->|"routes"| Arith
    Converter -->|"routes"| SAT
    Converter -->|"routes"| SMT
    Converter -->|"routes"| BitVector

    %% FFI Integration for SAT
    SAT -->|"integrates"| IPASIR_FFI

    %% Solver Engines output results back to CLI layer
    Arith -->|"outputs result"| toysolver
    SAT -->|"outputs result"| toysat
    SMT -->|"outputs result"| toysmt
    BitVector -->|"outputs result"| toysmt

    %% Cross dependencies among CLI applications 
    toysmt -->|"depends_on"| toysat

    %% Solver Engines use utility functions
    Arith ---|"uses"| Internal
    SAT ---|"uses"| Internal
    SMT ---|"uses"| Internal
    BitVector ---|"uses"| Internal

    Arith ---|"uses"| Graph
    SAT ---|"uses"| Graph
    SMT ---|"uses"| Graph
    BitVector ---|"uses"| Graph

    Arith ---|"uses"| DataLib
    SAT ---|"uses"| DataLib
    SMT ---|"uses"| DataLib
    BitVector ---|"uses"| DataLib

    %% Testing & Benchmarks connections
    Tests ---|"validate"| Arith
    Tests ---|"validate"| SAT
    Tests ---|"validate"| SMT
    Tests ---|"validate"| BitVector
    Benchmarks ---|"evaluate"| Arith
    Benchmarks ---|"evaluate"| SAT
    Benchmarks ---|"evaluate"| SMT
    Benchmarks ---|"evaluate"| BitVector

    %% Classes
    classDef cli fill:#FCE38A,stroke:#333,stroke-width:2px;
    classDef solver fill:#F38181,stroke:#333,stroke-width:2px;
    classDef utility fill:#95E1D3,stroke:#333,stroke-width:2px;
    classDef test fill:#A8DADC,stroke:#333,stroke-width:2px;
    classDef input fill:#C5E1A5,stroke:#333,stroke-width:2px;

    %% Click Events
    click toysolver "https://github.com/msakai/toysolver/blob/master/app/toysolver.hs"
    click toysat "https://github.com/msakai/toysolver/blob/master/app/toysat/toysat.hs"
    click toysmt "https://github.com/msakai/toysolver/blob/master/app/toysmt/toysmt.hs"
    click toyfmf "https://github.com/msakai/toysolver/blob/master/app/toyfmf.hs"
    click toyconvert "https://github.com/msakai/toysolver/blob/master/app/toyconvert.hs"
    click IPASIR_FFI "https://github.com/msakai/toysolver/tree/master/app/toysat-ipasir"
    click Arith "https://github.com/msakai/toysolver/tree/master/src/ToySolver/Arith"
    click SAT "https://github.com/msakai/toysolver/tree/master/src/ToySolver/SAT"
    click SMT "https://github.com/msakai/toysolver/tree/master/src/ToySolver/SMT"
    click BitVector "https://github.com/msakai/toysolver/tree/master/src/ToySolver/BitVector"
    click Converter "https://github.com/msakai/toysolver/tree/master/src/ToySolver/Converter"
    click FileFormat "https://github.com/msakai/toysolver/tree/master/src/ToySolver/FileFormat"
    click Internal "https://github.com/msakai/toysolver/tree/master/src/ToySolver/Internal"
    click Graph "https://github.com/msakai/toysolver/tree/master/src/ToySolver/Graph"
    click DataLib "https://github.com/msakai/toysolver/tree/master/src/ToySolver/Data"
    click Tests "https://github.com/msakai/toysolver/tree/master/test"
    click Benchmarks "https://github.com/msakai/toysolver/tree/master/benchmarks"
```
