Flexbox is a C++ Program which implements common graph algorithms to determine critical failure points in a city, made for Los Altos Hacks (my first hackathon!) testCases.txt contains sample test cases which I used to debug the main program. flexbox.cpp contains the program. I debugged and compiled it in gcc 7.5.0, using the bits.stdc header.
Flexbox receives basic information about a given area and returns unique insights on its design. It uses the Union Find data structure, as well as Dijkstra's and Kruskal's algorithms to compute connectivity, shortest paths and the minimum spanning tree. The program contains 4 main functions:
- Determine whether all intersections are connected to eachother via directed or undirected roads
- Determine whether a given node can reach all other nodes through some transitive path
- Determine intersections and roads which were "at risk" (the intersections and roads which, when removed, would split the city into two disjoint components)
- Determine the minimum spanning tree (the minimum amount of road which would need to be laid so that all nodes can be accessed somehow)