Graph algorithms for traversal, search, and transformation.
More...
|
| template<Internal::valid_graph_type G> |
| std::vector< typename G::id_type > | GraphLib::breadth_first_search (const G &graph, typename G::id_type root, typename G::id_type target) |
| | Performs a breadth-first search (BFS) to find a path from root to target node in a graph.
|
| template<Internal::valid_graph_type G> |
| G | GraphLib::breadth_first_search (const G &graph, typename G::id_type root) |
| | Performs a breadth-first search (BFS) to construct a spanning tree rooted at the given node.
|
| template<Internal::valid_graph_type G> |
| std::vector< typename G::id_type > | GraphLib::depth_first_search (const G &graph, typename G::id_type root, typename G::id_type target) |
| | Performs a depth-first search (DFS) to find a path from root to target node in a graph.
|
| template<Internal::valid_graph_type G> |
| G | GraphLib::depth_first_search (const G &graph, typename G::id_type root) |
| | Performs a depth-first search (DFS) to construct a spanning tree rooted at the given node.
|
| template<Internal::valid_weighted_graph_type G> |
| G | GraphLib::dijkstra (const G &graph, const typename G::id_type start) |
| | Computes the shortest-path spanning tree from a start node using Dijkstra's algorithm.
|
| template<Internal::valid_weighted_graph_type G> |
| std::optional< std::list< typename G::id_type > > | GraphLib::uniform_cost_search (const G &graph, const typename G::id_type start, const typename G::id_type target) |
| | Finds the lowest-cost path from start to target using Dijkstra's algorithm.
|
| template<Internal::valid_weighted_undirected_graph_type G> |
| G | GraphLib::kruskal (const G &graph) |
| | Computes the Minimum Spanning Tree of a weighted undirected graph using Kruskal's algorithm.
|
| template<Internal::valid_weighted_undirected_graph_type G> |
| G | GraphLib::prim (const G &graph, typename G::id_type root) |
| | Computes the Minimum Spanning Tree of a weighted undirected graph using Prim's algorithm.
|
| template<Internal::valid_directed_graph_type G> |
| std::vector< std::vector< typename G::id_type > > | GraphLib::tarjan (const G &graph) |
| | Finds all strongly connected components (SCCs) in a directed graph using Tarjan's algorithm.
|
Graph algorithms for traversal, search, and transformation.
This group contains generic algorithm implementations (like BFS, DFS, etc.) applicable to graphs that satisfy GraphLib's graph concepts.
◆ breadth_first_search() [1/2]
template<Internal::valid_graph_type G>
| G GraphLib::breadth_first_search |
( |
const G & | graph, |
|
|
typename G::id_type | root ) |
Performs a breadth-first search (BFS) to construct a spanning tree rooted at the given node.
This function generates a spanning tree of the input graph starting from the root node, traversing the graph breadth-first. For weighted graphs, the edge weights are preserved.
- Template Parameters
-
| G | Type of the graph. Must satisfy the valid_graph_type concept. |
- Parameters
-
| graph | The graph instance to build the spanning tree from. |
| root | The ID of the starting node for the BFS traversal. |
- Returns
- G A new graph instance representing the spanning tree rooted at root.
- Exceptions
-
| std::runtime_error | If the root node ID does not exist in the graph. |
Definition at line 98 of file bfs.h.
◆ breadth_first_search() [2/2]
template<Internal::valid_graph_type G>
| std::vector< typename G::id_type > GraphLib::breadth_first_search |
( |
const G & | graph, |
|
|
typename G::id_type | root, |
|
|
typename G::id_type | target ) |
Performs a breadth-first search (BFS) to find a path from root to target node in a graph.
This function searches for the shortest path (in terms of edges) between the specified root node and target node using BFS.
- Template Parameters
-
| G | Type of the graph. Must satisfy the valid_graph_type concept. |
- Parameters
-
| graph | The graph instance to search on. |
| root | The ID of the starting node. |
| target | The ID of the destination node. |
- Returns
- std::vector<typename G::id_type> A vector of node IDs representing the path from root to target. If no path is found, returns an empty vector.
- Exceptions
-
| std::runtime_error | If either the root or target node ID does not exist in the graph. |
Definition at line 48 of file bfs.h.
◆ depth_first_search() [1/2]
template<Internal::valid_graph_type G>
| G GraphLib::depth_first_search |
( |
const G & | graph, |
|
|
typename G::id_type | root ) |
Performs a depth-first search (DFS) to construct a spanning tree rooted at the given node.
This function generates a spanning tree of the input graph starting from the root node, traversing the graph depth-first. The returned graph contains the same nodes as the original, with edges connecting nodes in the DFS traversal order.
- Template Parameters
-
| G | Type of the graph. Must satisfy the valid_graph_type concept. |
- Parameters
-
| graph | The graph instance to build the spanning tree from. |
| root | The ID of the starting node for the DFS traversal. |
- Returns
- G A new graph instance representing the spanning tree rooted at root.
- Exceptions
-
| std::runtime_error | If the root node ID does not exist in the graph. |
Definition at line 101 of file dfs.h.
◆ depth_first_search() [2/2]
template<Internal::valid_graph_type G>
| std::vector< typename G::id_type > GraphLib::depth_first_search |
( |
const G & | graph, |
|
|
typename G::id_type | root, |
|
|
typename G::id_type | target ) |
Performs a depth-first search (DFS) to find a path from root to target node in a graph.
This function searches for a path (not necessarily shortest) between the specified root node and target node using DFS.
- Template Parameters
-
| G | Type of the graph. Must satisfy the valid_graph_type concept. |
- Parameters
-
| graph | The graph instance to search on. |
| root | The ID of the starting node. |
| target | The ID of the destination node. |
- Returns
- std::vector<typename G::id_type> A vector of node IDs representing the path from root to target. If no path is found, returns an empty vector.
- Exceptions
-
| std::runtime_error | If either the root or target node ID does not exist in the graph. |
Definition at line 44 of file dfs.h.
◆ dijkstra()
template<Internal::valid_weighted_graph_type G>
| G GraphLib::dijkstra |
( |
const G & | graph, |
|
|
const typename G::id_type | start ) |
Computes the shortest-path spanning tree from a start node using Dijkstra's algorithm.
- Template Parameters
-
| G | A graph type that satisfies the valid_weighted_graph_type concept. |
- Parameters
-
| graph | The input graph. |
| start | The node from which to compute shortest paths. |
- Returns
- A new graph representing the shortest-path tree.
Definition at line 209 of file dijkstra.h.
◆ kruskal()
template<Internal::valid_weighted_undirected_graph_type G>
| G GraphLib::kruskal |
( |
const G & | graph | ) |
|
Computes the Minimum Spanning Tree of a weighted undirected graph using Kruskal's algorithm.
Constructs an MST by sorting edges by weight and greedily adding edges that do not form cycles. Uses a union-find (disjoint set) data structure to track connected components efficiently.
- Template Parameters
-
| G | The graph type. Must satisfy the valid_weighted_undirected_graph_type concept. |
- Parameters
-
| graph | The input weighted undirected graph. |
- Returns
- G A new graph instance representing the MST of the input graph.
- Note
- Assumes the graph is connected or will return an MST forest if disconnected.
Definition at line 37 of file kruskal.h.
◆ prim()
template<Internal::valid_weighted_undirected_graph_type G>
| G GraphLib::prim |
( |
const G & | graph, |
|
|
typename G::id_type | root ) |
Computes the Minimum Spanning Tree of a weighted undirected graph using Prim's algorithm.
Starts from a root node and iteratively adds the smallest edge connecting the visited nodes to unvisited nodes. Throws an exception if the graph is disconnected and a spanning tree cannot be completed.
- Template Parameters
-
| G | The graph type. Must satisfy the valid_weighted_undirected_graph_type concept. |
- Parameters
-
| graph | The input weighted undirected graph. |
| root | The node ID from which to start building the MST. |
- Returns
- G A new graph instance representing the MST of the input graph.
- Exceptions
-
| std::runtime_error | if the root node does not exist or the graph is disconnected. |
Definition at line 37 of file prim.h.
◆ tarjan()
template<Internal::valid_directed_graph_type G>
| std::vector< std::vector< typename G::id_type > > GraphLib::tarjan |
( |
const G & | graph | ) |
|
Finds all strongly connected components (SCCs) in a directed graph using Tarjan's algorithm.
Uses DFS traversal to assign discovery and low-link values to nodes, detecting SCCs when a node's discovery value equals its low-link value.
- Template Parameters
-
| G | The graph type. Must satisfy the valid_directed_graph_type concept. |
- Parameters
-
| graph | The input directed graph. |
- Returns
- std::vector<std::vector<typename G::id_type>> A vector of SCCs, each SCC is a vector of node IDs.
Definition at line 36 of file tarjan.h.
◆ uniform_cost_search()
template<Internal::valid_weighted_graph_type G>
| std::optional< std::list< typename G::id_type > > GraphLib::uniform_cost_search |
( |
const G & | graph, |
|
|
const typename G::id_type | start, |
|
|
const typename G::id_type | target ) |
Finds the lowest-cost path from start to target using Dijkstra's algorithm.
- Template Parameters
-
| G | A graph type that satisfies the valid_weighted_graph_type concept. |
- Parameters
-
| graph | The input graph. |
| start | The start node. |
| target | The target node. |
- Returns
- An optional list of node IDs representing the path, or std::nullopt if unreachable.
Definition at line 238 of file dijkstra.h.
1.14.0