Struct IndexedGraph 

pub struct IndexedGraph<C> { /* private fields */ }

A directed graph stored as dense usize indices with weighted adjacency lists.

Implementations

impl<C> IndexedGraph<C>

pub const fn from_adjacency(adjacency: Vec<Vec<(usize, C)>>) -> Self

Build a directed indexed graph from an adjacency list.

pub const fn node_count(&self) -> usize

Return the number of nodes in the graph.

pub const fn len(&self) -> usize

Return the number of nodes in the graph.

pub const fn is_empty(&self) -> bool

Return true if the graph contains no nodes.

pub fn successors(&self, node: usize) -> &[(usize, C)]

Return the adjacency list for node.

pub fn adjacency(&self) -> &[Vec<(usize, C)>]

Return all adjacency lists.

pub fn astar<FH, FS>( &self, start: usize, heuristic: FH, success: FS, ) -> Option<(Vec<usize>, C)>

where C: Zero + Ord + Copy, FH: FnMut(usize) -> C, FS: FnMut(usize) -> bool,

Run A* from start to a node satisfying success.

pub fn astar_bag<FH, FS>( &self, start: usize, heuristic: FH, success: FS, ) -> Option<(impl Iterator<Item = Vec<usize>>, C)>

where C: Zero + Ord + Copy, FH: FnMut(usize) -> C, FS: FnMut(usize) -> bool,

Run A* and return all shortest paths as an iterator.

pub fn astar_bag_collect<FH, FS>( &self, start: usize, heuristic: FH, success: FS, ) -> Option<(Vec<Vec<usize>>, C)>

where C: Zero + Ord + Copy, FH: FnMut(usize) -> C, FS: FnMut(usize) -> bool,

Run A* and collect all shortest paths into a vector.

pub fn bfs<FS>(&self, start: usize, success: FS) -> Option<Vec<usize>>

where FS: FnMut(usize) -> bool,

Run BFS from start to a node satisfying success.

pub fn bfs_loop(&self, start: usize) -> Option<Vec<usize>>

Run BFS and return the shortest loop starting and ending at start.

pub fn bfs_bidirectional(&self, start: usize, end: usize) -> Option<Vec<usize>>

Run bidirectional BFS from start to end.

pub fn bfs_reach(&self, start: usize) -> impl Iterator<Item = usize> + '_

Iterate over nodes reachable from start using BFS order.

pub fn dfs<FS>(&self, start: usize, success: FS) -> Option<Vec<usize>>

where FS: FnMut(usize) -> bool,

Run DFS from start to a node satisfying success.

pub fn dfs_reach(&self, start: usize) -> impl Iterator<Item = usize> + '_

Iterate over nodes reachable from start using DFS order.

pub fn iddfs<FS>(&self, start: usize, success: FS) -> Option<Vec<usize>>

where FS: FnMut(usize) -> bool,

Run IDDFS from start to a node satisfying success.

pub fn idastar<FH, FS>( &self, start: usize, heuristic: FH, success: FS, ) -> Option<(Vec<usize>, C)>

where C: Zero + Ord + Copy, FH: FnMut(usize) -> C, FS: FnMut(usize) -> bool,

Run IDA* from start to a node satisfying success.

pub fn dijkstra<FS>(&self, start: usize, success: FS) -> Option<(Vec<usize>, C)>

where C: Zero + Ord + Copy, FS: FnMut(usize) -> bool,

Run Dijkstra from start to a node satisfying success.

pub fn dijkstra_all(&self, start: usize) -> Vec<Option<(usize, C)>>

where C: Zero + Ord + Copy,

Compute shortest paths to all reachable nodes from start.

pub fn dijkstra_partial<FS>( &self, start: usize, stop: FS, ) -> (Vec<Option<(usize, C)>>, Option<usize>)

where C: Zero + Ord + Copy, FS: FnMut(usize) -> bool,

Compute shortest paths until stop returns true.

pub fn dijkstra_reach( &self, start: usize, ) -> impl Iterator<Item = (usize, Option<usize>, C)> + '_

where C: Zero + Ord + Copy + Hash,

Iterate over nodes reached by Dijkstra, yielding the node, parent, and total cost.

pub fn bmssp<FS>(&self, start: usize, success: FS) -> Option<(Vec<usize>, C)>

where C: Zero + Ord + Copy, FS: FnMut(usize) -> bool,

Run the BMSSP-based SSSP algorithm from start.

pub fn bmssp_all(&self, start: usize) -> Vec<Option<(usize, C)>>

where C: Zero + Ord + Copy,

Compute BMSSP parents and costs for all reachable nodes from start.

pub fn fringe<FH, FS>( &self, start: usize, heuristic: FH, success: FS, ) -> Option<(Vec<usize>, C)>

where C: Bounded + Zero + Ord + Copy, FH: FnMut(usize) -> C, FS: FnMut(usize) -> bool,

Run Fringe search from start to a node satisfying success.

pub fn topological_sort(&self) -> Result<Vec<usize>, usize>

Compute a topological ordering of all nodes.

Errors

Returns Err(node) when a cycle is detected.

pub fn strongly_connected_components(&self) -> Vec<Vec<usize>>

Compute strongly connected components for all nodes.

pub fn strongly_connected_components_from( &self, start: usize, ) -> Vec<Vec<usize>>

Compute strongly connected components reachable from start.

pub fn strongly_connected_component(&self, node: usize) -> Vec<usize>

Compute the strongly connected component containing node.

pub fn count_paths<FS>(&self, start: usize, success: FS) -> usize

where FS: FnMut(usize) -> bool,

Count the number of paths from start to nodes satisfying success.

pub fn yen<FS>( &self, start: usize, success: FS, k: usize, ) -> Vec<(Vec<usize>, C)>

where C: Zero + Ord + Copy, FS: FnMut(usize) -> bool,

Compute k-shortest paths using Yen’s algorithm.

pub fn edmonds_karp( &self, source: usize, sink: usize, ) -> (Vec<((usize, usize), C)>, C, Vec<((usize, usize), C)>)

where C: Copy + Zero + Signed + Ord + Bounded,

Compute the maximum flow and minimum cut using Edmonds-Karp.

Panics

Panics if source or sink are out of bounds.

impl<C: Copy> IndexedGraph<C>

pub fn from_adjacency_matrix( matrix: &[Vec<Option<C>>], ) -> Result<Self, IndexedInputError>

Build a directed indexed graph from a square adjacency matrix.

Every Some(weight) cell becomes a directed edge from the row index to the column index. None cells produce no edge.

Errors

Returns IndexedInputError::RaggedMatrix if rows have different lengths and IndexedInputError::NonSquareAdjacencyMatrix if the matrix is not square.

Example

use pathfinding_indexed::IndexedGraph;

let graph = IndexedGraph::from_adjacency_matrix(&[
    vec![None, Some(3), None],
    vec![None, None, Some(2)],
    vec![Some(1), None, None],
])
.unwrap();

assert_eq!(graph.successors(0), &[(1, 3)]);
assert_eq!(graph.successors(1), &[(2, 2)]);
assert_eq!(graph.successors(2), &[(0, 1)]);

Trait Implementations

impl<C: Clone> Clone for IndexedGraph<C>

fn clone(&self) -> IndexedGraph<C>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<C: Debug> Debug for IndexedGraph<C>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.