LifeLine — disaster response and evacuation simulator

The actual problem

A DSA course teaches ten algorithms in isolation and then asks for a project. The interesting version of that assignment is not implementing them again — it is putting them in one system where each one has a job that the others depend on, and where a wrong answer is visible rather than hidden behind a test case.

So: Indrapur, a fictional city of 40 locations and 83 roads, held as a weighted graph. A flood spreads across it, and the engine has to keep the city working.

What it does

Routing. Dijkstra and A* over the road network, with a haversine heuristic. On Riverside Colony → Sunrise Hospital both return the same optimal 4.78 km path, but Dijkstra settles 24 nodes to A*’s 8 — the point of the comparison view is that the heuristic changes the search, not the answer. The heuristic is admissible by construction: tools/generate_city.py guarantees every road is at least as long as the straight line it spans.

Disaster and evacuation. A level-order BFS from the epicentre blocks roads ring by ring. The same route reroutes to 5.42 km over the north bridge; at two rings both southern approaches are cut and the west→east trip becomes impossible. Evacuation capacity is Edmonds–Karp max-flow from a super-source over danger nodes to a super-sink over shelters, and the min-cut names the exact bottleneck roads — the tests assert the duality on the real graph.

Dispatch. Incidents enter a custom max-heap for triage, with a monotonic sequence number breaking ties so equal severities stay FIFO. Each incident runs one dijkstraAll() — not one Dijkstra per vehicle — because the road graph is undirected and distances are symmetric. Supply loading is 0/1 knapsack DP with backtracking, which beats the greedy value-per-weight order it is compared against.

Resilience. One Tarjan DFS finds bridges and articulation points from the same disc/low arrays. On the healthy city both sets are empty — it was generated 2-edge-connected with minimum degree 3, so there is no single point of failure to find. Under flood, 5 critical roads and 7 critical junctions appear. Prim and Kruskal both run and their totals are asserted equal, which is a proof line rather than a feature: distinct edge weights mean the MST is unique.

Engineering notes

No STL containers in the algorithm paths. The binary min-heap and max-heap, the separate-chaining hash map (djb2, load factor 0.75), the trie behind prefix search and the Union–Find with path halving are all in backend/src/ds/. That was the point of the exercise — std::priority_queue would have hidden the part worth learning, including the decision to use lazy deletion instead of decrease-key.

The backend is a single static binary with no external dependencies: cpp-httplib and nlohmann/json are header-only, and the built React frontend is served by the same binary at /. SQLite is a compile-time #ifdef with a JSONL fallback, so the default build needs nothing installed.

Testing is the part I would defend hardest. tools/verify_city.py is an independent pure-Python re-implementation, and the 96 checks compare against it on the real graph: shortest paths across all 1,600 node pairs, max-flow/min-cut duality, the bridge and articulation sets, MST totals, diameter and centrality. Cross-verification against a second implementation catches the class of bug that a hand-written expected value never does.

What I would change

Dispatch is greedy, so it is locally optimal per incident rather than globally optimal — min-cost matching via the Hungarian algorithm at O(n³) would be the correct offline answer. Greedy is defensible here because dispatch is an online problem and incidents arrive over time, but that is a justification, not a proof, and I would like to measure the gap.