# foo/online-knapsack architecture

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

- Interactive diagram: https://gitdiagram.com/foo/online-knapsack
- Repository: https://github.com/foo/online-knapsack

## Overview

##### Project type and purpose
- This is an academic research‐code repository accompanying the ICALP 2020 paper “An optimal algorithm for online multiple knapsack.”
- It contains:
- Three LaTeX targets (ICALP submission, Arxiv version, journal version) under top‐level folders “0-ICALP”, “1-Arxiv”, “2-journal”.
- A “code” folder with multiple experiment modules (C++ implementations, Python scripts, plotting pipelines).
- Utilities, data files, and Makefiles to drive builds, runs, data‐generation, and plot generation.

##### File structure
- Top level:
- Makefile & README.md – orchestrate full build (PDF + experiments + plots)
- 0-ICALP, 1-Arxiv, 2-journal – LaTeX sources and assets for each paper variant
- code/ – all experiment source code submodules
- utilities.py & code/utilities/ – shared helper functions
- code/ submodules (each with its own Makefile or script pipeline):
- case-check, fighting-two-arg, eval, estimations – C++ executables to run algorithms and collect raw results
- knapsack-plot – Python + gnuplot scripts to transform data.dat → .eps/.pdf
- plots – C++ + gnuplot templates to generate the “final” set of 09 figures
- szysio – various Python helper scripts (data processing, bounds calculators)
- trash – legacy or exploratory code (safe to ignore or annotate as “archived experiments”)
- Data flow: C++/Python code → raw data (.dat) → gnuplot/python → plot files (.eps/.pdf) → LaTeX inclusion → final paper PDFs.

##### Key insights from README
- Describes the core algorithmic contribution (online multiple knapsack).

##### Detail
- Shared utilities as a dependency across multiple experiment modules.

## Diagram (Mermaid)

```mermaid
flowchart TD
    direction TB

    %% Toolchain & Environment
    subgraph "Toolchain & Environment"
        Make["Makefile & README"]:::toolchain
        Make -->|"orchestrates"| CaseCheck
        Make -->|"orchestrates"| FightingTwoArg
        Make -->|"orchestrates"| EvalExec
        Make -->|"orchestrates"| EstimationsExec
        Make -->|"orchestrates"| KnapsackPlot
        Make -->|"orchestrates"| PlotsPipeline
        Make -->|"orchestrates"| Szysio
        Make -->|"orchestrates"| LaTeXICALP
        Make -->|"orchestrates"| LaTeXArxiv
        Make -->|"orchestrates"| LaTeXJournal
    end

    click Make "https://github.com/foo/online-knapsack/tree/master/Makefile"

    %% Shared Utilities
    UtilitiesRoot["utilities.py"]:::utility
    UtilitiesCPP["code/utilities/"]:::utility
    click UtilitiesRoot "https://github.com/foo/online-knapsack/blob/master/code/utilities.py"
    click UtilitiesCPP "https://github.com/foo/online-knapsack/tree/master/code/utilities/"

    %% Experiment Stage
    subgraph "Experiment Stage"
        CaseCheck["case-check exec"]:::experiment
        FightingTwoArg["fighting-two-arg exec"]:::experiment
        EvalExec["eval exec"]:::experiment
        EstimationsExec["estimations exec"]:::experiment

        CaseCheck -->|uses| UtilitiesCPP
        FightingTwoArg -->|uses| UtilitiesCPP
        EvalExec -->|uses| UtilitiesCPP
        EstimationsExec -->|uses| UtilitiesCPP

        CaseCheck -->|"produces"| RawData
        FightingTwoArg -->|"produces"| RawData
        EvalExec -->|"produces"| RawData
        EstimationsExec -->|"produces"| RawData
    end

    click CaseCheck "https://github.com/foo/online-knapsack/tree/master/code/case-check/"
    click FightingTwoArg "https://github.com/foo/online-knapsack/tree/master/code/fighting-two-arg/"
    click EvalExec "https://github.com/foo/online-knapsack/blob/master/code/eval/eval.cpp"
    click EstimationsExec "https://github.com/foo/online-knapsack/blob/master/code/estimations/estimate4.cpp"

    %% Raw Data
    RawData["raw data (.dat)"]:::data

    %% Visualization Stage
    subgraph "Visualization Stage"
        KnapsackPlot["knapsack-plot pipeline"]:::plotting
        PlotsPipeline["plots final figures"]:::plotting
        Szysio["szysio scripts"]:::plotting

        RawData -->|input| KnapsackPlot
        KnapsackPlot -->|"generates"| PlotFiles
        RawData -->|input| PlotsPipeline
        Szysio -->|helps| PlotsPipeline
    end

    click KnapsackPlot "https://github.com/foo/online-knapsack/tree/master/code/knapsack-plot/"
    click PlotsPipeline "https://github.com/foo/online-knapsack/tree/master/code/plots/"
    click Szysio "https://github.com/foo/online-knapsack/tree/master/code/szysio/"

    %% Plot Files
    PlotFiles[".eps/.pdf files"]:::data

    %% Publication Stage
    subgraph "Publication Stage"
        LaTeXICALP["0-ICALP LaTeX build"]:::latex
        LaTeXArxiv["1-Arxiv LaTeX build"]:::latex
        LaTeXJournal["2-journal LaTeX build"]:::latex

        PlotFiles -->|included in| LaTeXICALP
        PlotFiles -->|included in| LaTeXArxiv
        PlotFiles -->|included in| LaTeXJournal
    end

    click LaTeXICALP "https://github.com/foo/online-knapsack/tree/master/0-ICALP/"
    click LaTeXArxiv "https://github.com/foo/online-knapsack/tree/master/1-Arxiv/"
    click LaTeXJournal "https://github.com/foo/online-knapsack/tree/master/2-journal/"

    %% Utilities link to Python helpers
    UtilitiesRoot -->|imported by| KnapsackPlot
    UtilitiesRoot -->|imported by| Szysio

    %% Styles
    classDef toolchain fill:#D3D3D3,stroke:#000,stroke-width:1px;
    classDef experiment fill:#ADD8E6,stroke:#000,stroke-width:1px;
    classDef data fill:#90EE90,stroke:#000,stroke-width:1px;
    classDef plotting fill:#FFA500,stroke:#000,stroke-width:1px;
    classDef latex fill:#FFD700,stroke:#000,stroke-width:1px;
    classDef utility fill:#E6E6FA,stroke:#000,stroke-width:1px;
```
