A C++17 graph library with BFS, DFS, Dijkstra's shortest path, and Floyd-Warshall all-pairs shortest paths. Includes a CLI menu interface and exports graphs to .dot format.
C++17, Google Test, lcov, custom Stack/Queue containers, Matrix<T> template
Custom stack and queue used for traversal. BFS uses containers::Queue<T> (doubly-linked list), DFS uses containers::Stack<T> (singly-linked list) - both hand-rolled, no STL std::stack/std::queue. The DFS iterates the adjacency row in reverse (i = size-1; i > 0; --i) to preserve natural left-to-right visit order when popping from the stack.
ExportGraphToDot auto-detects directed vs undirected. Before writing edges it scans the matrix for asymmetry (adjacencyMatrix_(i,j) != adjacencyMatrix_(j,i)) and switches the edge token between " -- " and " -> " accordingly - no flag required from the caller.
Floyd-Warshall initializes 0 off-diagonal entries to UINT_MAX in-place on a copy of the adjacency matrix, then runs the standard triple loop. This avoids a separate distance matrix allocation while correctly handling absent edges.
Dijkstra's uses linear scan for minimum instead of a priority queue - O(V²). Simple and correct for the graph sizes targeted here.
Build system produces two separate static libs - graph.a (graph only) and graph_algorithms.a (graph + algorithms) - built from the same sources via different ar invocations, so consumers can link only what they need.
cd src
# Build and run CLI
make interface
# Run tests
make test
# Run tests + coverage report
make gcov_report
# Build static libraries
make libsPlain text adjacency matrix with size on the first line:
4
0 1 0 0
0 0 1 1
0 0 0 0
0 0 0 0