Railway Cargo Propagation Solver

A high-performance analysis engine designed to determine cargo reachability within a directed railway network. This project implements an optimized Data-Flow Analysis solver using Bit-Vectors, demonstrating techniques commonly used in modern compiler optimization passes.

Architecture & Theory

Determining which cargo types arrive at a station is functionally analogous to Reaching Definitions or Liveness Analysis in compiler theory. This solver models the railway system as a Monotone Framework:

• Lattice: The power set of all possible cargo types.
• Direction: Forward-flow (originating from the start station $s_0$).
• Meet Operator: Union ($\cup$), implemented via hardware-efficient bitwise OR.
• Transfer Function: For each station $v$, the departing cargo $D_v$ is derived from the arriving cargo $A_v$ as: $$D_v = (A_v \setminus {unload_v}) \cup {load_v}$$

By representing cargo sets as bit-vectors, we process all cargo types concurrently, minimizing memory overhead and maximizing CPU throughput.

---

Algorithms

1. Naive BFS (Baseline)

My initial approach used a multi-pass strategy that isolated each cargo type and ran independent Breadth-First Searches to track propagation. Verdict: This was discarded during testing as highly inefficient.

• Complexity: $O(C \cdot (V + E))$, where $C$ is the number of cargo types.
• Characteristics: While intuitive, it scales poorly due to redundant graph traversals. In stress tests (1000 nodes, 8000 edges), it performed ~100x slower than the bit-vector approach.

2. Bit-Vector Data-Flow (Optimized)

After researching fixed-point iteration, I implemented a solver that processes all cargo types concurrently using bitwise operations and a worklist.

• Complexity: $O((V + E) \cdot (C / W))$, where $W$ is the machine word size (typically 64).
• Coordinate Compression: Arbitrary cargo IDs (e.g., 1,000,000) are mapped to a dense integer range ($0 \dots N$) to optimize bit-vector density.

---

Project Structure

• main.py: The entry point for manual testing and browser-based visual debugging.
• tests.py: A comprehensive test suite covering edge cases: cycles, isolated nodes, and hub-and-spoke redistribution.
• algorithm.py: The core implementation of the optimized bitmask solver and coordinate compression logic.

---

🖥️ Usage

Standard Execution Pipe the topology data via standard input:

python3 main.py

Example input:

5 7
1 0 10
2 20 5
3 30 15
4 40 25
5 50 40
2 1
2 3
3 4
4 3
3 2
5 4
1 2
1

Example output:

========================================
STATION      | ARRIVING CARGO
----------------------------------------
1            | [5, 10, 15, 25]
2            | [5, 10, 15, 25]
3            | [5, 10, 15, 25]
4            | [5, 10, 15, 25]
5            | []