GraphSTL

Values on the outside, integer IDs on the inside

Callers write g.addEdge('A', 'B', 4) with their own values; a value → ID hash map turns that into an O(1) average lookup, and every algorithm works on plain size_t IDs.

Trade-offEach value is stored twice, and T must be hashable (std::hash<T> and ==).

Directedness is a template parameter

graph<T, W, true> and graph<T, W, false> are different types. addEdge adds the reverse edge for undirected graphs, if constexpr picks the right cycle-detection strategy, and Kahn's sort and Kosaraju static_assert that the graph is directed, so misuse is a compile error.

Trade-offDirectedness can't change at runtime, and the two kinds can't be mixed in one container.

Algorithms are free functions in their own header

Like std::sort over iterators, the algorithms sit outside the container, so adding one never touches the graph class. They read the graph through getAdjList() and getData().

Trade-offThose accessors return the internal maps (as const references), so the representation is effectively part of the public API.

Results as values, unpacked with structured bindings

auto [cost, path] = dijkstra(g, 'A', 'F'); returns everything in one value. Unreachable targets come back as {numeric_limits<Weight>::max(), {}}, a negative cycle in Bellman-Ford as {min(), {}}, and Kahn's sort on a cyclic graph as an empty vector.

Trade-offThe sentinels are conventions the caller has to know; std::optional or a status field would make them impossible to miss.

Two Dijkstras, kept on purpose

The main version uses a binary-heap priority queue with lazy deletion (stale entries are skipped) and stops at the target. dijkstra_naive scans every node, O(V²), and exists so the benchmark can compare the two and check they agree.

Trade-offA second implementation to keep correct.

A node that doesn't exist

Lookups by value throw std::runtime_error("Node not found") rather than inventing a node. Adding an existing value returns its existing ID instead of creating a duplicate.

No path to the target

Dijkstra, A* and Bellman-Ford return the sentinel cost with an empty path; Floyd-Warshall's path() returns an empty vector. Each case is tested.

Negative weights and negative cycles

Bellman-Ford handles negative weights and reports a reachable negative cycle; Floyd-Warshall sets hasNegativeCycle. Both are tested.

A cycle where a DAG is required

Kahn's sort returns an empty vector when it can't order every node, tested together with cyclePresent().

The wrong kind of graph

Kahn's sort and Kosaraju's SCC on an undirected graph fail at compile time with a readable static_assert message.

Removing nodes and edges

removeNode also deletes every incoming edge from every other adjacency list; removeEdge on an undirected graph removes both directions. Both are tested, as is a self-loop counting as a cycle.

Runaway path reconstruction

Floyd-Warshall's path() walks the next-hop table at most |V| + 1 steps, so a corrupt table can't loop forever. Bellman-Ford stops as soon as a pass changes nothing.

Iterate instead of recursing

Tarjan, Kosaraju and cycle detection recurse through std::function lambdas, so a long chain of nodes can overflow the stack. Explicit stacks, as dfs() already uses, would remove the limit and the indirect call per visit.

Guard every precondition the way Kahn does

Dijkstra and A* silently return wrong answers on negative weights, and Kruskal accepts a directed graph and treats its edges as undirected. A static_assert(!IsDirected) on Kruskal and a negative-weight check would match the static_assert already on Kahn and Kosaraju.

Benchmark with repetitions and full runs

Each case is timed once with no warm-up, and both Dijkstras stop early at node n − 1. That measures early exit on a dense random graph more than the O((V+E) log V) versus O(V²) gap. Repeated runs, or Google Benchmark, over full single-source searches would show the real curve.

Store adjacency in vectors

NodeIDs are dense counters, yet adjacency and every algorithm's dist and parent use hash maps. Vectors indexed by ID would be faster and simpler; removed nodes would need a free list.

Property tests for every algorithm

A* and Kruskal have one test each. This site's TypeScript port cross-checks 200 random graphs (the shortest-path algorithms agree, Kruskal equals a brute-force Prim, Tarjan equals Kosaraju), and the same idea would fit the C++ suite.