Skip to main content

​
Graph

#include <graph.hpp>
Generic directed weighted graph. Implements an adjacency list graph with support for:
  • Breadth-first search (unweighted shortest path)
  • Dijkstra’s algorithm (weighted shortest path)
  • A* search (heuristic-guided pathfinding)

​
Parameters

  • Id Vertex identifier type (must be hashable)
  • IdHash Hash function for Id type (default: std::hash<Id>)
:::note Edge weights must be non-negative for Dijkstra and A* ::: :::note Self-loops and duplicate edges are supported :::

​
Public Methods

ReturnNameDescription
voidadd_edgeAdd a directed edge to the graph.
std::vector< Id >bfs constBreadth-first search from a start vertex.
std::optional< PathResult >dijkstra constDijkstra’s algorithm for shortest path.
std::optional< PathResult >astar constA* pathfinding algorithm.

​
add_edge

inline 
inline void add_edge(const Id & from, const Id & to, double w)
Add a directed edge to the graph.

​
Parameters

  • from Source vertex
  • to Destination vertex
  • w Edge weight (default: 1.0)
Edge from->to exists with weight w :::note If edge already exists, adds additional parallel edge :::

​
Example:

Graph<int> g;
g.add_edge(1, 2, 5.0);   // Weighted edge
g.add_edge(2, 3);        // Unweighted edge (weight=1)

​
bfs

const 
inline std::vector< Id > bfs(const Id & start) const
Breadth-first search from a start vertex. Returns all vertices reachable from start in BFS order. Uses O(V + E) time where V = vertices, E = edges.

​
Parameters

  • start Starting vertex

​
Returns

Vector of visited vertices in BFS order Returns empty vector if start not in graph :::note Does not consider edge weights (treats all as weight 1) :::

​
dijkstra

const 
inline std::optional< PathResult > dijkstra(const Id & start, const Id & end) const
Dijkstra’s algorithm for shortest path. Finds the shortest path between two vertices using Dijkstra’s algorithm with a binary heap priority queue.

​
Parameters

  • start Starting vertex
  • end Destination vertex

​
Returns

PathResult if path exists, std::nullopt otherwise On success, path contains vertices from start to end cost equals sum of edge weights along path :::note Time complexity: O((V + E) log V) ::: :::note Edge weights must be non-negative :::

​
Example:

Graph<std::string> g;
g.add_edge("home", "store", 5.0);
g.add_edge("store", "work", 3.0);

auto result = g.dijkstra("home", "work");
if (result) {
    // result->path = ["home", "store", "work"]
    // result->cost = 8.0
}

​
astar

const 
inline std::optional< PathResult > astar(const Id & start, const Id & end, std::function< double(const Id &, const Id &)> h) const
A* pathfinding algorithm. Finds shortest path using heuristic-guided search. More efficient than Dijkstra when a good heuristic is available.

​
Parameters

  • start Starting vertex
  • end Destination vertex
  • h Heuristic function: estimated cost from node to goal Must be admissible (never overestimate)

​
Returns

PathResult if path exists, std::nullopt otherwise On success, path contains vertices from start to end cost equals g-score (actual cost, not f-score) :::note Time complexity: O(E log V) in best case with good heuristic ::: :::note Heuristic must be admissible for optimal results ::: :::note Edge weights must be non-negative :::

​
Example:

Graph<int> g;
// Add edges representing a grid...

// Manhattan distance heuristic for grid
auto h = [&](int from, int to) {
    return std::abs(from - to);  // Simplified
};

auto result = g.astar(0, 100, h);

​
Private Attributes

ReturnNameDescription
std::unordered_map< Id, std::vector< std::pair< Id, double > >, IdHash >adj_Adjacency list: vertex -> list of (neighbor, weight) pairs.

​
adj_

std::unordered_map< Id, std::vector< std::pair< Id, double > >, IdHash > adj_
Adjacency list: vertex -> list of (neighbor, weight) pairs.