# liloheinrich/mst-tsp architecture

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

- Interactive diagram: https://gitdiagram.com/liloheinrich/mst-tsp
- Repository: https://github.com/liloheinrich/mst-tsp

## Overview

##### Project type and purpose
- This is a small, single-language (Python) algorithmic tool for computing a 2-approximation of the metric TSP via MST plus a brute-force TSP solver.
- It is not a full-stack or microservice project but rather a command‐line algorithm implementation with built-in tests.

##### File structure
- Top-level:
- AAHW3.pdf (assignment spec)
- LICENSE (open-source terms)
- README.md (project description & instructions)
- tsp-approx.py (all source code + tests in one file)
- No separate “src,” “tests,” or “config” folders – everything is contained in tsp-approx.py.

##### README for additional insights
- Goals: implement MST, brute-force TSP, demonstrate 2-approximation.
- Starter code already includes MST routines; tests appended at the bottom.

a. Main components
1. Input Parser & Data Loader
– Reads number of vertices and distance matrix from stdin or file.
2. MST Generator (Prim’s or Kruskal’s algorithm)
3. Approximate TSP Path Builder
– Performs a preorder tree walk on the MST to get 2-approx tour.
4. Brute-Force TSP Solver
– Enumerates all permutations of vertices, computes exact optimal tour length.
5. Comparator & Reporter
– Compares lengths, verifies approximation ratio ≤2, outputs results.
6. Test Harness
– Invokes all algorithms on predefined test graphs, asserts expected outputs.
b. Relationships & Interactions
- User → (Input Parser) → Graph Data
- Graph Data → MST Generator → MST Structure
- MST Structure → Approximate TSP Builder → Approx Tour & Length
- Graph Data → Brute-Force Solver → Exact Tour & Length
- Both Tour Results → Comparator → Console Output
- Test Harness calls all above components with known datasets and checks results.
c. Architectural patterns or design principles
- Single-process, modular code organized by function
- Data flow is purely in-memory, functional pipelines
- Separation of concerns: input, MST, TSP approximation, brute force, testing
d. Key technologies & libraries
- Python 3 standard library: itertools (permutations), sys (I/O), time (optional benchmarks)
- No external dependencies

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% User and CLI
    User["User"]:::external
    User -->|stdin/file| InputParser["Input Parser & Data Loader"]:::process

    %% Main Data Entity
    GraphData["Graph Data"]:::data
    InputParser -->|"Adjacency Matrix"| GraphData

    %% MST Flow
    MSTGen["MST Generator"]:::process
    GraphData -->|"Adjacency Matrix"| MSTGen
    MST["MST Structure"]:::data
    MSTGen -->|"Tree Edges"| MST

    %% Approximate TSP Flow
    ApproxBuilder["Approximate TSP Path Builder"]:::process
    MST -->|"Preorder Walk"| ApproxBuilder
    ApproxTour["Approx Tour + Length"]:::data
    ApproxBuilder -->|"Tour Sequence"| ApproxTour

    %% Brute-Force TSP Flow
    BruteSolver["Brute-Force TSP Solver"]:::process
    GraphData -->|"Adjacency Matrix"| BruteSolver
    ExactTour["Exact Tour + Length"]:::data
    BruteSolver -->|"Permuted Tours"| ExactTour

    %% Comparison and Reporting
    Comparator["Comparator & Reporter"]:::process
    ApproxTour -->|"Approx Length"| Comparator
    ExactTour -->|"Exact Length"| Comparator
    ConsoleOutput["Console Output"]:::external
    Comparator -->|"Results"| ConsoleOutput

    %% Test Harness
    TestHarness["Test Harness"]:::test
    TestHarness -.-> InputParser
    TestHarness -.-> MSTGen
    TestHarness -.-> ApproxBuilder
    TestHarness -.-> BruteSolver
    TestHarness -.-> Comparator

    %% Documentation
    README["README.md"]:::docs
    Spec["AAHW3.pdf"]:::docs
    License["LICENSE"]:::docs

    %% Click Events
    click InputParser "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click MSTGen "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click ApproxBuilder "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click BruteSolver "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click Comparator "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click TestHarness "https://github.com/liloheinrich/mst-tsp/blob/main/tsp-approx.py"
    click README "https://github.com/liloheinrich/mst-tsp/blob/main/README.md"
    click Spec "https://github.com/liloheinrich/mst-tsp/blob/main/AAHW3.pdf"
    click License "https://github.com/liloheinrich/mst-tsp/tree/main/LICENSE"

    %% Styles
    classDef data fill:#D0EFFF,stroke:#333,stroke-width:1px
    classDef process fill:#D0F0D0,stroke:#333,stroke-width:1px
    classDef test fill:#FFE5B4,stroke:#333,stroke-width:1px,stroke-dasharray: 5 5
    classDef docs fill:#F0D0FF,stroke:#333,stroke-width:1px
    classDef external fill:#EEEEEE,stroke:#333,stroke-width:1px,stroke-dasharray: 2 2
```
