blob: 9137dced841db3247054b388a4b46cd9d13f00fe [file] [log] [blame]
 //! # Shortest Path Module //! //! This module contains traits and implementations for shortest path and shortest distance //! algorithms. //! These algorithms are used to find the shortest path or distance between two nodes in a graph. //! //! ## Traits //! //! - [`ShortestPath`]: Any implementation of this trait can be used to find the shortest path, //! depending on algorithm some restrictions may apply. //! - [`ShortestDistance`]: Any implementation of this trait can be used to find the shortest //! distance, depending on algorithm some restrictions may apply. //! //! ## Implementations //! //! These are the algorithms implemented in `petgraph` itself, companion crates may implement other //! algorithms. //! //! - [`AStar`]: An implementation of the A* shortest path algorithm. //! - [`BellmanFord`]: An implementation of the Bellman-Ford shortest path algorithm. //! - [`Dijkstra`]: An implementation of the Dijkstra's shortest path algorithm. //! - [`FloydWarshall`]: An implementation of the Floyd-Warshall shortest path algorithm. //! //! ## Usage //! //! Each algorithm provides methods to find the shortest path or distance from a source node to a //! target node, from a source node to all other nodes, and between all pairs of nodes. //! //! The [`ShortestPath`] trait provides methods to find paths, while the [`ShortestDistance`] trait //! provides methods to find distances. //! The difference between a path and a distance is that a path includes the sequence of nodes and //! edges, while a distance is just the sum of the weights of the edges. //! //! ## Example //! //! ```rust //! use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath}; //! use petgraph_dino::DiDinoGraph; //! //! let mut graph = DiDinoGraph::new(); //! let a = graph.insert_node("A").id(); //! let b = graph.insert_node("B").id(); //! graph.insert_edge(7, a, b); //! //! let dijkstra = Dijkstra::directed(); //! let path = dijkstra.path_between(&graph, a, b); //! assert!(path.is_some()); //! //! let path = dijkstra.path_between(&graph, b, a); //! assert!(path.is_none()); //! ``` pub mod astar; pub mod bellman_ford; mod common; pub mod dijkstra; pub mod floyd_warshall; use error_stack::{Context, Result}; use petgraph_core::{node::NodeId, Graph, GraphStorage}; pub use self::{ astar::AStar, bellman_ford::BellmanFord, common::{ cost::{Cost, GraphCost}, path::Path, route::{DirectRoute, Route}, }, dijkstra::Dijkstra, floyd_warshall::FloydWarshall, }; pub mod utilities { //! # Utilities //! //! This module contains utilities that can be used with shortest path algorithms. //! //! Currently this module only contains the [`cost`] and [`heuristic`] functions, which resolve //! common lifetime problems whenever closures are used for the cost and heuristic functions. pub use super::common::closures::{cost, heuristic}; } // TODO: should algorithms take `Node` instead?! /// # Shortest Path /// /// A shortest path algorithm is an algorithm that finds a path between two nodes in a graph such /// that the sum of the weights of its constituent edges is minimized. /// /// Different algorithms exist to solve this problem, each with its own trade-offs, refer to the /// different algorithms for more information. /// /// ## Shortest Path vs Shortest Distance /// /// The shortest path is the path between two nodes that has the lowest cost. /// The shortest distance is the cost of the shortest path. /// You should prefer shortest distance algorithms over shortest path algorithms if you are only /// interested in the cost of the shortest path. /// /// # Example /// /// ```rust /// use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath}; /// use petgraph_dino::DiDinoGraph; /// /// let mut graph = DiDinoGraph::new(); /// let a = graph.insert_node("A").id(); /// let b = graph.insert_node("B").id(); /// let c = graph.insert_node("C").id(); /// /// graph.insert_edge(7, a, b); /// graph.insert_edge(5, b, c); /// graph.insert_edge(3, a, c); /// /// let dijkstra = Dijkstra::directed(); /// let path = dijkstra.path_between(&graph, a, c).expect("path exists"); /// /// assert_eq!(path.cost().into_value(), 3); /// /// assert_eq!(path.path().source().id(), a); /// assert_eq!(path.path().target().id(), c); /// /// assert!(path.path().transit().is_empty()); /// ``` pub trait ShortestPath where S: GraphStorage, { /// The cost of the shortest path. type Cost; /// The error that can occur when computing the shortest path. type Error: Context; /// Returns the shortest path from the source to the target. /// /// Returns an iterator over all routes in the graph that end at the given target node. // TODO: example? fn path_to<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, target: NodeId, ) -> Result> + 'this, Self::Error> { let iter = self.every_path(graph)?; Ok(iter.filter(move |route| route.path().target().id() == target)) } /// Returns the shortest path from the source to the target. /// /// This is also known as `SSSP` (Single Source Shortest Path) problem. /// /// Returns an iterator over all routes in the graph that start at the given source node. fn path_from<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, source: NodeId, ) -> Result> + 'this, Self::Error> { let iter = self.every_path(graph)?; Ok(iter.filter(move |route| route.path().source().id() == source)) } /// Returns the shortest path from the source to the target. /// /// This will return [`None`] if no path exists between the source and the target. fn path_between<'graph>( &self, graph: &'graph Graph, source: NodeId, target: NodeId, ) -> Option> { self.path_from(graph, source) .ok()? .find(|route| route.path().target().id() == target) } /// Returns an iterator over all shortest paths in the graph. /// /// This is also known as `APSP` (All Pairs Shortest Path) problem. /// /// Returns an iterator over all routes in the graph. fn every_path<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, ) -> Result> + 'this, Self::Error>; } /// # Shortest Distance /// /// A shortest distance algorithm is an algorithm that finds the distance between two nodes in a /// graph such that the sum of the weights of its constituent edges is minimized. /// /// Different algorithms exist to solve this problem, each with its own trade-offs, refer to the /// different algorithms for more information. /// /// ## Shortest Path vs Shortest Distance /// /// The shortest path is the path between two nodes that has the lowest cost. /// The shortest distance is the cost of the shortest path. /// You should prefer shortest distance algorithms over shortest path algorithms if you are only /// interested in the cost of the shortest path. // TODO: example? pub trait ShortestDistance where S: GraphStorage, { /// The cost of the shortest path. type Cost; /// The error that can occur when computing the shortest path. type Error: Context; /// Returns the shortest distance from the source to the target. /// /// Returns an iterator over all direct routes in the graph that end at the given target node. /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes. fn distance_to<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, target: NodeId, ) -> Result> + 'this, Self::Error> { let iter = self.every_distance(graph)?; Ok(iter.filter(move |route| route.target().id() == target)) } /// Returns the shortest distance from the source to the target. /// /// This is also known as `SSSP` (Single Source Shortest Path) problem. /// /// Returns an iterator over all direct routes in the graph that start at the given source node. /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes. fn distance_from<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, source: NodeId, ) -> Result> + 'this, Self::Error> { let iter = self.every_distance(graph)?; Ok(iter.filter(move |route| route.source().id() == source)) } /// Returns the shortest distance from the source to the target. /// /// This will return [`None`] if no path exists between the source and the target. fn distance_between( &self, graph: &Graph, source: NodeId, target: NodeId, ) -> Option> { self.every_distance(graph) .ok()? .find(move |route| route.source().id() == source && route.target().id() == target) .map(DirectRoute::into_cost) } /// Returns an iterator over all shortest distances in the graph. /// /// This is also known as `APSP` (All Pairs Shortest Path) problem. /// /// Returns an iterator over all direct routes in the graph. /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes. fn every_distance<'graph: 'this, 'this>( &'this self, graph: &'graph Graph, ) -> Result> + 'this, Self::Error>; }