How liloheinrich/mst-tsp works
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