### Install Valgrind for Deterministic Benchmarks

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Install Valgrind, a prerequisite for running iai-callgrind deterministic benchmarks.

```bash
sudo apt-get install valgrind  # On Ubuntu/Debian
```

--------------------------------

### Install pre-commit Hook

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Install the pre-commit hook for the repository to enforce commit message conventions and code quality checks.

```bash
$ pre-commit install --hook-type commit-msg
```

--------------------------------

### Knight Moves Pathfinding Example

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Searches for the shortest path on a chessboard from (1, 1) to (4, 6) using knight moves with BFS. Requires the Pos struct to implement Clone, Debug, Eq, Hash, Ord, PartialEq, and PartialOrd.

```rust
use pathfinding::prelude::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
  fn successors(&self) -> Vec<Pos> {
    let &Pos(x, y) = self;
    vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2),
         Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)]
  }
}

static GOAL: Pos = Pos(4, 6);
let result = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
assert_eq!(result.expect("no path found").len(), 5);
```

--------------------------------

### Find All Shortest Paths with Dijkstra

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

This snippet demonstrates how to find all shortest paths from a starting node to all reachable nodes in a graph. The `dijkstra_all` function returns a map of reachable nodes and their associated costs.

```rust
use pathfinding::prelude::dijkstra_all;

let result = dijkstra_all(&start, successors);
// result contains all reachable nodes and their costs from start
```

--------------------------------

### Depth-First Search (DFS) Reachability

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Collects all reachable nodes from a starting point using DFS. Useful for exploring connected components or all possible states.

```rust
use pathfinding::prelude::dfs_reach;

fn main() {
    let nodes: Vec<_> = dfs_reach(1, |&n| {
        vec![n*2, n*3].into_iter().filter(|&x| x < 15)
    }).collect();

    println!("DFS order: {:?}", nodes);
    // [1, 2, 4, 8, 12, 6, 3, 9]
}
```

--------------------------------

### Bidirectional BFS: Faster pathfinding by searching from both ends

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Bidirectional BFS (`bfs_bidirectional`) simultaneously searches from the start and end nodes, meeting in the middle. This approach can be significantly faster than unidirectional BFS on large graphs. Requires successor functions for both forward and backward searches.

```rust
use pathfinding::prelude::bfs_bidirectional;

fn main() {
    // Successor function for forward search
    let successors = |&(x, y): &(i32, i32)| vec![
        (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2),
        (x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1)
    ];

    // For undirected graphs, predecessors = successors
    let result = bfs_bidirectional(&(1, 1), &(4, 6), successors, successors);

    match result {
        Some(path) => println!("Path found: {:?}", path),
        None => println!("No path found"),
    }
}
```

--------------------------------

### Count Paths in an Acyclic Graph

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Counts the number of possible paths from a starting node to a goal node in an acyclic graph. Requires a successor function and a goal predicate.

```rust
use pathfinding::prelude::count_paths;

fn main() {
    // Count paths in a grid from top-left to bottom-right
    fn successors(&(x, y): &(u32, u32)) -> Vec<(u32, u32)> {
        let mut next = vec![];
        if x < 3 { next.push((x + 1, y)); }
        if y < 3 { next.push((x, y + 1)); }
        next
    }

    let count = count_paths((0, 0), successors, |&pos| pos == (3, 3));
    println!("Number of paths: {}", count);  // 20 paths in a 4x4 grid
}
```

--------------------------------

### Cycle Detection - Floyd's and Brent's Algorithms

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Detects cycles in infinite sequences using Floyd's tortoise and hare algorithm or Brent's algorithm. Returns the cycle length, the first element in the cycle, and the index where the cycle starts.

```rust
use pathfinding::prelude::{floyd, brent};

fn main() {
    // Detect cycle in sequence: x -> (x * 2) % 7
    let (cycle_length, first_elem, start_index) = floyd(1, |x| (x * 2) % 7);

    println!("Cycle length: {}", cycle_length);      // 3
    println!("First element in cycle: {}", first_elem);
    println!("Cycle starts at index: {}", start_index);

    // Brent's algorithm is often faster
    let (lam, elem, mu) = brent(1, |x| (x * 2) % 7);
    println!("Brent: length={}, element={}, start={}", lam, elem, mu);
}
```

--------------------------------

### Check if a Path Exists with Dijkstra

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Use this pattern to quickly determine if a path exists between a start and goal node using the Dijkstra algorithm. It returns a boolean indicating existence.

```rust
let path_exists = dijkstra(&start, successors, |&n| n == goal).is_some();
```

--------------------------------

### BFS Loop: Find the shortest cycle in a graph

Source: https://context7.com/evenfurther/pathfinding/llms.txt

The `bfs_loop` function is designed to find the shortest cycle starting and ending at a given node. It explores paths until it encounters a node already visited in the current traversal, returning the cycle if found.

```rust
use pathfinding::prelude::bfs_loop;

fn main() {
    fn successors(&n: &u32) -> Vec<u32> {
        match n {
            1 => vec![2, 3],
            2 => vec![4],
            3 => vec![4],
            4 => vec![1],  // Creates a cycle back to 1
            _ => vec![],
        }
    }

    let cycle = bfs_loop(&1, successors);
    println!("Cycle found: {:?}", cycle);  // Some([1, 2, 4, 1]) or [1, 3, 4, 1]
}
```

--------------------------------

### Dijkstra Reach: Iterate over reachable nodes in cost order

Source: https://context7.com/evenfurther/pathfinding/llms.txt

The `dijkstra_reach` function provides an iterator that yields nodes in increasing order of cost from the start node. This is useful for exploring graphs incrementally or when early termination is desired.

```rust
use pathfinding::prelude::dijkstra_reach;

fn main() {
    fn successors(&n: &u32) -> Vec<(u32, u32)> {
        if n < 10 { vec![(n*2, n), (n+1, 1)] } else { vec![] }
    }

    // Iterate over reachable nodes in cost order
    for item in dijkstra_reach(&1, successors).take(5) {
        println!(
            "Node: {}, Total cost: {}, Parent: ?",
            item.node, item.total_cost, item.parent
        );
    }
    // Node: 1, Total cost: 0, Parent: None
    // Node: 2, Total cost: 1, Parent: Some(1)
    // Node: 3, Total cost: 2, Parent: Some(2)
    // ...
}
```

--------------------------------

### BFS Reach: Iterate over all reachable nodes in BFS order

Source: https://context7.com/evenfurther/pathfinding/llms.txt

The `bfs_reach` function returns an iterator that visits all nodes reachable from a starting point in Breadth-First Search order. This is useful for exploring all accessible nodes without needing to specify a goal.

```rust
use pathfinding::prelude::bfs_reach;

fn main() {
    // Generate multiples of 2 and 3
    let mut iter = bfs_reach(1, |&n| vec![n*2, n*3].into_iter().filter(|&x| x <= 20));

    let all_nodes: Vec<_> = iter.collect();
    println!("Reachable nodes: {:?}", all_nodes);
    // [1, 2, 3, 4, 6, 9, 8, 12, 18, 16]
}
```

--------------------------------

### Import BFS Algorithm in Rust

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Import the Breadth-First Search (BFS) algorithm from the pathfinding crate's prelude.

```rust
use pathfinding::prelude::bfs;
```

--------------------------------

### Pathfinding with Adjacency Matrix (A*)

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Illustrates finding a path in a graph using an adjacency matrix and the A* algorithm. Nodes are represented by indices, and the successor function is derived from the matrix. A heuristic function is also required for A*.

```rust
use pathfinding::prelude::astar;

fn main() {
    // Represent nodes as indices (0, 1, 2, 3, 4)
    // None means no edge, Some(weight) means edge with weight
    let adjacency_matrix: Vec<Vec<Option<u32>>> = vec![
        vec![None,    Some(4), Some(2), None,    None],    // Node 0 (A)
        vec![None,    None,    Some(1), Some(5), None],    // Node 1 (B)
        vec![None,    None,    None,    Some(8), Some(10)], // Node 2 (C)
        vec![None,    None,    None,    None,    Some(2)],  // Node 3 (D)
        vec![None,    None,    None,    None,    None],     // Node 4 (E)
    ];

    let num_nodes = adjacency_matrix.len();

    // Successor function using the matrix
    let successors = |&node: &usize| -> Vec<(usize, u32)> {
        (0..num_nodes)
            .filter_map(|neighbor| {
                adjacency_matrix[node][neighbor].map(|weight| (neighbor, weight))
            })
            .collect()
    };

    // Simple heuristic (for demonstration - in real use, make it admissible)
    let heuristic = |&node: &usize| -> u32 {
        if node == 4 { 0 } else { 1 }
    };

    // Find path from node 0 to node 4 using A*
    let result = astar(
        &0,
        successors,
        heuristic,
        |&node| node == 4,
    );

    match result {
        Some((path, cost)) => {
            println!("Path: {:?}", path);
            println!("Total cost: {}", cost);
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Run Wall-time Benchmarks

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Execute wall-time benchmarks using Criterion and CodSpeed compatibility. Ensure you have the necessary benchmark targets specified.

```bash
cargo bench --bench algos --bench edmondskarp --bench kuhn_munkres --bench separate_components
```

--------------------------------

### A* Shortest Path on a Spatial Graph

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Demonstrates finding the shortest path on a spatial graph using the A* algorithm. Requires defining custom Location and SpatialGraph structs with appropriate methods for distance calculation and edge traversal.

```Rust
use pathfinding::prelude::astar;
use std::collections::HashMap;

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct Location {
    id: u32,
    x: f64,
    y: f64,
}

impl Location {
    fn distance_to(&self, other: &Location) -> u32 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        ((dx * dx + dy * dy).sqrt() * 100.0) as u32 // Scale for integer costs
    }
}

struct SpatialGraph {
    locations: HashMap<u32, Location>,
    edges: HashMap<u32, Vec<(u32, u32)>>,
}

impl SpatialGraph {
    fn new() -> Self {
        Self {
            locations: HashMap::new(),
            edges: HashMap::new(),
        }
    }

    fn add_location(&mut self, id: u32, x: f64, y: f64) {
        self.locations.insert(id, Location { id, x, y });
    }

    fn add_edge(&mut self, from: u32, to: u32, cost: u32) {
        self.edges.entry(from).or_default().push((to, cost));
    }

    fn find_shortest_path(&self, start_id: u32, goal_id: u32) -> Option<(Vec<u32>, u32)> {
        let goal_location = self.locations.get(&goal_id)?;

        astar(
            &start_id,
            |&node_id| {
                self.edges
                    .get(&node_id)
                    .cloned()
                    .unwrap_or_default()
            },
            |&node_id| {
                // Heuristic: straight-line distance to goal
                self.locations
                    .get(&node_id)
                    .map(|loc| loc.distance_to(goal_location))
                    .unwrap_or(u32::MAX)
            },
            |&node_id| node_id == goal_id,
        )
    }
}

fn main() {
    let mut graph = SpatialGraph::new();

    // Add locations (nodes)
    graph.add_location(1, 0.0, 0.0);
    graph.add_location(2, 10.0, 0.0);
    graph.add_location(3, 10.0, 10.0);
    graph.add_location(4, 0.0, 10.0);
    graph.add_location(5, 5.0, 5.0);

    // Add edges with costs
    graph.add_edge(1, 2, 1000);
    graph.add_edge(1, 5, 707);
    graph.add_edge(2, 3, 1000);
    graph.add_edge(2, 5, 707);
    graph.add_edge(3, 4, 1000);
    graph.add_edge(3, 5, 707);
    graph.add_edge(4, 1, 1000);
    graph.add_edge(4, 5, 707);

    // Find shortest path from location 1 to location 3
    if let Some((path, cost)) = graph.find_shortest_path(1, 3) {
        println!("Shortest path: {:?}", path);
        println!("Total cost: {}", cost);
    } else {
        println!("No path found");
    }
}

```

--------------------------------

### Pathfinding with Adjacency List (Dijkstra)

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Demonstrates finding the shortest path in a weighted graph represented by an adjacency list using the Dijkstra algorithm. Requires a HashMap to store graph connections and a closure for the successor function.

```rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

// Define our graph as an adjacency list: Node -> Vec<(Neighbor, Weight)>
type Graph = HashMap<&'static str, Vec<(&'static str, u32)>>;

fn main() {
    // Create a weighted graph
    let graph: Graph = [
        ("A", vec![("B", 4), ("C", 2)]),
        ("B", vec![("C", 1), ("D", 5)]),
        ("C", vec![("D", 8), ("E", 10)]),
        ("D", vec![("E", 2)]),
        ("E", vec![]),
    ]
    .iter()
    .cloned()
    .collect();

    // Define the successor function
    let successors = |node: &&str| -> Vec<(&str, u32)> {
        graph.get(node).cloned().unwrap_or_default()
    };

    // Find shortest path from A to E
    let result = dijkstra(&"A", successors, |&node| node == "E");

    match result {
        Some((path, cost)) => {
            println!("Path: {:?}", path);
            println!("Total cost: {}", cost);
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Grid Data Structure Operations

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Shows how to create and manipulate a Grid, including adding vertices, enabling diagonal movement, and performing BFS reachability searches.

```rust
use pathfinding::prelude::Grid;

fn main() {
    // Create an empty 5x5 grid
    let mut grid = Grid::new(5, 5);

    // Add vertices
    grid.add_vertex((0, 0));
    grid.add_vertex((1, 0));
    grid.add_vertex((1, 1));
    grid.add_vertex((2, 1));

    // Enable diagonal movement
    grid.enable_diagonal_mode();

    // Get neighbors of a vertex
    let neighbors = grid.neighbours((1, 1));
    println!("Neighbors of (1,1): {:?}", neighbors);

    // Check edge existence
    println!("Edge (0,0)-(1,1): {}", grid.has_edge((0, 0), (1, 1)));

    // Iterate over vertices
    for vertex in grid.iter() {
        println!("Vertex: {:?}", vertex);
    }

    // Debug display
    println!("{:?}", grid);
    // #....
    // ##...
    // .#...
    // .....
    // .....

    // Create from coordinates
    let grid2 = Grid::from_coordinates(&[(2, 2), (3, 4), (3, 5)]).unwrap();
    println!("{:?}", grid2);

    // BFS reachability on grid
    grid.fill();  // Fill all vertices
    let reachable = grid.bfs_reachable((0, 0), |_| true);
    println!("Reachable from (0,0): {} vertices", reachable.len());
}
```

--------------------------------

### Yen's K-Shortest Paths Algorithm

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Finds the k shortest loopless paths between two nodes using Yen's algorithm. Useful for identifying alternative routes.

```rust
use pathfinding::prelude::yen;

fn main() {
    // Find 3 shortest paths from 'c' to 'h'
    let paths = yen(
        &'c',
        |c| match c {
            'c' => vec![('d', 3), ('e', 2)],
            'd' => vec![('f', 4)],
            'e' => vec![('d', 1), ('f', 2), ('g', 3)],
            'f' => vec![('g', 2), ('h', 1)],
            'g' => vec![('h', 2)],
            'h' => vec![],
            _ => vec![],
        },
        |c| *c == 'h',
        3  // Find 3 shortest paths
    );

    for (i, (path, cost)) in paths.iter().enumerate() {
        println!("Path {}: {:?} with cost {}", i + 1, path, cost);
    }
    // Path 1: ['c', 'e', 'f', 'h'] with cost 5
    // Path 2: ['c', 'e', 'g', 'h'] with cost 7
    // Path 3: ['c', 'd', 'f', 'h'] with cost 8
}
```

--------------------------------

### Dijkstra Pathfinding: Python to Rust Conversion

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Shows how to adapt graph data from Python's `networkx` library to a Rust `HashMap` for the `dijkstra` function. Assumes edges are provided as a list of (from, to, weight) tuples.

```Python
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from(edges)
path = nx.shortest_path(G, source, target, weight='weight')
```

```Rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

let mut graph: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
for (from, to, weight) in edges {
    graph.entry(from).or_default().push((to, weight));
}

let result = dijkstra(
    &source,
    |node| graph.get(node).cloned().unwrap_or_default(),
    |node| *node == target,
);
```

--------------------------------

### Add pathfinding Crate to Cargo.toml

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Add this to your Cargo.toml file to include the pathfinding crate in your project.

```ini
[dependencies]
pathfinding = "4.15.0"
```

--------------------------------

### A* Algorithm for Weighted Graphs with Heuristics

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Utilize the A* algorithm for efficient shortest path finding in weighted graphs when a good admissible heuristic is available. The heuristic function should underestimate the true cost to the goal.

```Rust
use pathfinding::prelude::astar;

let result = astar(
    &start_node,
    |node| get_neighbors(node),      // Returns Vec<(Neighbor, Cost)>
    |node| estimate_cost_to_goal(node), // Heuristic function
    |node| node == goal_node,
);
```

--------------------------------

### Matrix Data Structure Operations

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Demonstrates creating, accessing, and transforming a Matrix, including neighbor finding and directional iteration. Supports reachability searches.

```rust
use pathfinding::prelude::{Matrix, directions};

fn main() {
    // Create a matrix from rows
    let matrix = Matrix::from_rows(vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ]).unwrap();

    println!("Element at (1, 2): {}", matrix[(1, 2)]);  // 6

    // Get neighbors (with diagonals)
    let neighbors: Vec<_> = matrix.neighbours((1, 1), true).collect();
    println!("Neighbors of (1,1): {:?}", neighbors);
    // [(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)]

    // Iterate in a direction
    let cells: Vec<_> = matrix.in_direction((0, 0), directions::SE).collect();
    println!("SE from (0,0): {:?}", cells);  // [(1, 1), (2, 2)]

    // Create and transform matrices
    let rotated = matrix.rotated_cw(1);  // Rotate 90 degrees clockwise
    let transposed = matrix.transposed();

    // Flood fill with BFS reachability
    let reachable = matrix.bfs_reachable((0, 0), false, |pos| {
        matrix.get(pos).map_or(false, |&v| v < 5)
    });
    println!("Cells reachable with value < 5: {:?}", reachable);
}
```

--------------------------------

### A* Search Algorithm Implementation

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Finds the shortest path in a weighted graph using a heuristic. Requires a successor function, an admissible heuristic, and a success predicate. The heuristic must not overestimate the cost for optimal results.

```rust
use pathfinding::prelude::astar;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
    fn distance(&self, other: &Pos) -> u32 {
        (self.0.abs_diff(other.0) + self.1.abs_diff(other.1)) as u32
    }

    fn successors(&self) -> Vec<(Pos, u32)> {
        let &Pos(x, y) = self;
        vec![
            Pos(x+1, y+2), Pos(x+1, y-2), Pos(x-1, y+2), Pos(x-1, y-2),
            Pos(x+2, y+1), Pos(x+2, y-1), Pos(x-2, y+1), Pos(x-2, y-1)
        ].into_iter().map(|p| (p, 1)).collect()
    }
}

fn main() {
    let goal = Pos(4, 6);
    let result = astar(
        &Pos(1, 1),
        |p| p.successors(),
        |p| p.distance(&goal) / 3,  // Heuristic
        |p| *p == goal              // Success condition
    );

    match result {
        Some((path, cost)) => {
            println!("Path found with cost {}: {:?}", cost, path);
            // Output: Path found with cost 4: [Pos(1, 1), Pos(3, 2), Pos(4, 4), Pos(2, 5), Pos(4, 6)]
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Run Deterministic Benchmarks with iai-callgrind

Source: https://github.com/evenfurther/pathfinding/blob/main/README.md

Execute deterministic benchmarks using iai-callgrind with the 'iai' feature flag enabled. This provides precise performance measurements.

```bash
cargo bench --features iai --bench iai_algos --bench iai_edmondskarp --bench iai_kuhn_munkres --bench iai_separate_components
```

--------------------------------

### A* Bag - Finding All Shortest Paths

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Returns an iterator over all shortest paths, not just one. Useful when multiple optimal solutions exist. Requires a successor function, a heuristic, and a success predicate.

```rust
use pathfinding::prelude::astar_bag;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
    fn successors(&self) -> Vec<(Pos, u32)> {
        let &Pos(x, y) = self;
        vec![
            Pos(x+1, y), Pos(x-1, y), Pos(x, y+1), Pos(x, y-1)
        ].into_iter()
         .filter(|&Pos(nx, ny)| nx >= 0 && ny >= 0 && nx <= 3 && ny <= 3)
         .map(|p| (p, 1))
         .collect()
    }
}

fn main() {
    let goal = Pos(2, 2);
    let result = astar_bag(
        &Pos(0, 0),
        |p| p.successors(),
        |p| ((p.0 - goal.0).abs() + (p.1 - goal.1).abs()) as u32,
        |p| *p == goal
    );

    if let Some((solutions, cost)) = result {
        println!("Found {} shortest paths with cost {}:", solutions.clone().count(), cost);
        for path in solutions {
            println!("  {:?}", path);
        }
    }
}
```

--------------------------------

### BFS: Find shortest path in unweighted graphs

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Breadth-First Search (`bfs`) finds the shortest path in terms of hops for unweighted graphs. It explores nodes level by level, making it suitable for minimum step calculations. Requires a successor function and a goal predicate.

```rust
use pathfinding::prelude::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
    fn successors(&self) -> Vec<Pos> {
        let &Pos(x, y) = self;
        // Knight moves on a chess board
        vec![
            Pos(x+1, y+2), Pos(x+1, y-2), Pos(x-1, y+2), Pos(x-1, y-2),
            Pos(x+2, y+1), Pos(x+2, y-1), Pos(x-2, y+1), Pos(x-2, y-1)
        ]
    }
}

fn main() {
    let goal = Pos(4, 6);
    let result = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == goal);

    match result {
        Some(path) => {
            println!("Path length: {} moves", path.len() - 1);
            println!("Path: {:?}", path);
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Dijkstra Pathfinding: R to Rust Conversion

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Illustrates converting graph data from an R `igraph` structure to a Rust `HashMap` for use with the `dijkstra` function. Assumes edges are provided as a list of (from, to, weight) tuples.

```R
library(igraph)
g <- graph_from_data_frame(edges_df)
shortest_paths(g, from, to)
```

```Rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

// Convert your R edge list to adjacency list
let mut graph: HashMap<String, Vec<(String, u32)>> = HashMap::new();
for (from, to, weight) in edges {
    graph.entry(from).or_default().push((to, weight));
}

// Use dijkstra
let result = dijkstra(
    &start_node,
    |node| graph.get(node).cloned().unwrap_or_default(),
    |node| node == &goal_node,
);
```

--------------------------------

### Dijkstra's Algorithm for Weighted Graphs

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Implement Dijkstra's algorithm for finding the shortest path in a weighted graph with non-negative edge weights. The neighbor function must return tuples of (Neighbor, Cost).

```Rust
use pathfinding::prelude::dijkstra;

let result = dijkstra(
    &start_node,
    |node| get_neighbors(node),  // Returns Vec<(Neighbor, Cost)>
    |node| node == goal_node,
);
```

--------------------------------

### Depth-First Search (DFS) Pathfinding

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Finds a path between two nodes using DFS. It explores as far as possible along each branch before backtracking. Does not guarantee the shortest path.

```rust
use pathfinding::prelude::dfs;

fn main() {
    // Find a path from 1 to 17, where successors are n+1 and n*n
    let result = dfs(
        1,
        |&n| vec![n*n, n+1].into_iter().filter(|&x| x <= 17),
        |&n| n == 17
    );

    match result {
        Some(path) => println!("Path found: {:?}", path),  // [1, 2, 4, 16, 17]
        None => println!("No path found"),
    }
}
```

--------------------------------

### Handle Multiple Goals with Dijkstra

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Adapt the Dijkstra algorithm to find a path to any node within a specified set of goals. The provided closure checks if the current node is present in the goals vector.

```rust
let goals = vec![goal1, goal2, goal3];
let result = dijkstra(&start, successors, |node| goals.contains(node));
```

--------------------------------

### Adding Bidirectional Edges in Rust

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Demonstrates how to represent undirected edges in a graph by adding edges in both directions. This is crucial for algorithms that assume or require bidirectional connectivity.

```Rust
graph.entry(a).or_default().push((b, cost));
graph.entry(b).or_default().push((a, cost));
```

--------------------------------

### BFS for Shortest Path by Hops

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Use BFS when all edges have the same cost (unweighted graph) and the goal is to find the path with the minimum number of hops. The neighbor function returns only the neighbors, without associated costs.

```Rust
use pathfinding::prelude::bfs;

let result = bfs(
    &start_node,
    |node| get_neighbors(node),  // Returns Vec<Neighbor> (no costs)
    |node| node == goal_node,
);
```

--------------------------------

### Dijkstra with Edge List and Lookup

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Converts an edge list to an adjacency list for efficient pathfinding using Dijkstra's algorithm. Requires defining nodes and edges, then building a HashMap for graph representation.

```rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct Node {
    id: u32,
}

struct Edge {
    from: u32,
    to: u32,
    weight: u32,
}

fn main() {
    // Define edges
    let edges = vec![
        Edge { from: 1, to: 2, weight: 7 },
        Edge { from: 1, to: 3, weight: 9 },
        Edge { from: 1, to: 6, weight: 14 },
        Edge { from: 2, to: 3, weight: 10 },
        Edge { from: 2, to: 4, weight: 15 },
        Edge { from: 3, to: 4, weight: 11 },
        Edge { from: 3, to: 6, weight: 2 },
        Edge { from: 4, to: 5, weight: 6 },
        Edge { from: 5, to: 6, weight: 9 },
    ];

    // Build adjacency list from edge list
    let mut graph: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
    for edge in edges {
        graph.entry(edge.from).or_default().push((edge.to, edge.weight));
    }

    // Successor function
    let successors = |node_id: &u32| -> Vec<(u32, u32)> {
        graph.get(node_id).cloned().unwrap_or_default()
    };

    // Find shortest path
    let result = dijkstra(&1, successors, |&node| node == 5);

    match result {
        Some((path, cost)) => {
            println!("Path: {:?}", path);
            println!("Total cost: {}", cost);
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Kuhn-Munkres (Hungarian Algorithm) for Max/Min Assignment

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Solves the assignment problem to find maximum or minimum weight matching in a bipartite graph. Requires a Matrix input.

```rust
use pathfinding::prelude::{kuhn_munkres, kuhn_munkres_min, Matrix};

fn main() {
    // Three people bidding on three items
    // Rows = people, Columns = items
    let weights = Matrix::from_rows(vec![
        //   Cloth, Statue, Painting
        vec![100,   110,    90],    // Ann
        vec![95,    130,    75],    // Bernard
        vec![95,    140,    65],    // Claude
    ]).unwrap();

    // Find maximum weight matching
    let (max_value, assignments) = kuhn_munkres(&weights);

    println!("Maximum total value: {}", max_value);  // 325
    println!("Assignments: {:?}", assignments);       // [2, 0, 1]
    // Ann gets Painting (90), Bernard gets Cloth (95), Claude gets Statue (140)

    // For minimization problems, use kuhn_munkres_min
    let (min_value, min_assignments) = kuhn_munkres_min(&weights);
    println!("Minimum total value: {}", min_value);
}
```

--------------------------------

### Fringe Search Pathfinding

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Implements Fringe Search, an alternative to A* that uses less memory. Suitable for grid-based pathfinding with consistent heuristics.

```rust
use pathfinding::prelude::fringe;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
    fn distance(&self, other: &Pos) -> u32 {
        (self.0.abs_diff(other.0) + self.1.abs_diff(other.1)) as u32
    }

    fn successors(&self) -> Vec<(Pos, u32)> {
        let &Pos(x, y) = self;
        vec![
            Pos(x+1, y+2), Pos(x+1, y-2), Pos(x-1, y+2), Pos(x-1, y-2),
            Pos(x+2, y+1), Pos(x+2, y-1), Pos(x-2, y+1), Pos(x-2, y-1)
        ].into_iter().map(|p| (p, 1)).collect()
    }
}

fn main() {
    let goal = Pos(4, 6);
    let result = fringe(
        &Pos(1, 1),
        |p| p.successors(),
        |p| p.distance(&goal) / 3,
        |p| *p == goal
    );

    if let Some((path, cost)) = result {
        println!("Path cost: {}", cost);  // 4
    }
}
```

--------------------------------

### Struct-Based Graph for Dijkstra and A*

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Encapsulates graph logic within a struct, providing methods for adding roads, coordinates, and finding paths using both Dijkstra and A* algorithms. The A* algorithm utilizes a heuristic based on Euclidean distance.

```rust
use pathfinding::prelude::{astar, dijkstra};
use std::collections::HashMap;

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct City {
    name: String,
}

struct RoadNetwork {
    // adjacency list: city name -> list of (neighbor, distance)
    connections: HashMap<String, Vec<(String, u32)>>,
    // coordinates for heuristic (optional)
    coordinates: HashMap<String, (f64, f64)>,
}

impl RoadNetwork {
    fn new() -> Self {
        Self {
            connections: HashMap::new(),
            coordinates: HashMap::new(),
        }
    }

    fn add_road(&mut self, from: &str, to: &str, distance: u32) {
        self.connections
            .entry(from.to_string())
            .or_default()
            .push((to.to_string(), distance));
    }

    fn add_coordinates(&mut self, city: &str, x: f64, y: f64) {
        self.coordinates.insert(city.to_string(), (x, y));
    }

    fn successors(&self, city: &str) -> Vec<(String, u32)> {
        self.connections.get(city).cloned().unwrap_or_default()
    }

    fn heuristic(&self, from: &str, to: &str) -> u32 {
        // Euclidean distance as heuristic
        if let (Some(&(x1, y1)), Some(&(x2, y2))) =
            (self.coordinates.get(from), self.coordinates.get(to))
        {
            let dx = x2 - x1;
            let dy = y2 - y1;
            // Note: In production code, consider using proper rounding
            // and handling potential truncation explicitly
            #[expect(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
            let distance = (dx * dx + dy * dy).sqrt() as u32;
            distance
        } else {
            0
        }
    }

    fn find_path_dijkstra(&self, start: &str, goal: &str) -> Option<(Vec<String>, u32)> {
        dijkstra(
            &start.to_string(),
            |city| self.successors(city),
            |city| city == goal,
        )
    }

    fn find_path_astar(&self, start: &str, goal: &str) -> Option<(Vec<String>, u32)> {
        let goal_str = goal.to_string();
        astar(
            &start.to_string(),
            |city| self.successors(city),
            |city| self.heuristic(city, &goal_str),
            |city| city == &goal_str,
        )
    }
}

fn main() {
    let mut network = RoadNetwork::new();

    // Add roads (bidirectional)
    network.add_road("CityA", "CityB", 10);
    network.add_road("CityB", "CityA", 10);
    network.add_road("CityA", "CityC", 15);
    network.add_road("CityC", "CityA", 15);
    network.add_road("CityB", "CityD", 12);
    network.add_road("CityD", "CityB", 12);
    network.add_road("CityC", "CityD", 10);
    network.add_road("CityD", "CityC", 10);

    // Add coordinates for A* heuristic
    network.add_coordinates("CityA", 0.0, 0.0);
    network.add_coordinates("CityB", 10.0, 0.0);
    network.add_coordinates("CityC", 0.0, 15.0);
    network.add_coordinates("CityD", 10.0, 12.0);

    // Find path using Dijkstra
    if let Some((path, cost)) = network.find_path_dijkstra("CityA", "CityD") {
        println!("Dijkstra - Path: {:?}, Cost: {}", path, cost);
    }

    // Find path using A*
    if let Some((path, cost)) = network.find_path_astar("CityA", "CityD") {
        println!("A* - Path: {:?}, Cost: {}", path, cost);
    }
}
```

--------------------------------

### BFS for Unweighted Graphs

Source: https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md

Use BFS for unweighted graphs to find the shortest path in terms of hops. The successor function should return only neighboring nodes without costs. This is useful for maze solving or social network analysis.

```Rust
use pathfinding::prelude::bfs;
use std::collections::HashMap;

fn main() {
    // Define an unweighted graph as an adjacency list
    // Each node maps to a list of neighbors (no weights)
    let graph: HashMap<&str, Vec<&str>> = [
        ("A", vec!["B", "C"]),
        ("B", vec!["A", "D", "E"]),
        ("C", vec!["A", "F"]),
        ("D", vec!["B"]),
        ("E", vec!["B", "F"]),
        ("F", vec!["C", "E"]),
    ]
    .iter()
    .cloned()
    .collect();

    // Successor function returns just neighbors (no costs)
    let successors = |node: &&str| -> Vec<&str> {
        graph.get(node).cloned().unwrap_or_default()
    };

    // Find shortest path from A to F using BFS
    let result = bfs(&"A", successors, |&node| node == "F");

    match result {
        Some(path) => {
            println!("Shortest path from A to F: {:?}", path);
            println!("Number of hops: {}", path.len() - 1);
            // Expected: ["A", "C", "F"] with 2 hops
        }
        None => println!("No path found"),
    }
}
```

--------------------------------

### Find Shortest Path with Dijkstra's Algorithm

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Finds the shortest path between two nodes in a weighted graph using Dijkstra's algorithm. The graph is represented using an adjacency list. Requires a successor function that returns neighbors and their associated costs.

```rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct Node { id: u32 }

struct Graph {
    edges: HashMap<u32, Vec<(u32, u32)>>,
}

impl Graph {
    fn new() -> Self {
        Graph { edges: HashMap::new() }
    }

    fn add_edge(&mut self, from: u32, to: u32, weight: u32) {
        self.edges.entry(from).or_default().push((to, weight));
    }

    fn successors(&self, node: &u32) -> Vec<(u32, u32)> {
        self.edges.get(node).cloned().unwrap_or_default()
    }

    fn shortest_path(&self, start: u32, goal: u32) -> Option<(Vec<u32>, u32)> {
        dijkstra(&start, |n| self.successors(n), |&n| n == goal)
    }
}

fn main() {
    let mut graph = Graph::new();
    graph.add_edge(1, 2, 7);
    graph.add_edge(1, 3, 9);
    graph.add_edge(2, 3, 10);
    graph.add_edge(2, 4, 15);
    graph.add_edge(3, 4, 11);

    if let Some((path, cost)) = graph.shortest_path(1, 4) {
        println!("Path: {:?}, Cost: {}", path, cost);
    }
}
```

--------------------------------

### Dijkstra's Algorithm Implementation

Source: https://context7.com/evenfurther/pathfinding/llms.txt

Finds the shortest path in a weighted graph without a heuristic. Requires non-negative edge costs. Suitable when a heuristic is unavailable or unreliable.

```rust
use pathfinding::prelude::dijkstra;
use std::collections::HashMap;

fn main() {
    // Define a weighted graph as an adjacency list
    let graph: HashMap<&str, Vec<(&str, u32)>> = [
        ("A", vec![("B", 4), ("C", 2)]),
        ("B", vec![("C", 1), ("D", 5)]),
        ("C", vec![("D", 8), ("E", 10)]),
        ("D", vec![("E", 2)]),
        ("E", vec![]),
    ].iter().cloned().collect();

    let result = dijkstra(
        &"A",
        |node| graph.get(node).cloned().unwrap_or_default(),
        |&node| node == "E"
    );

    match result {
        Some((path, cost)) => {
            println!("Shortest path: {:?}", path);      // ["A", "B", "C", "D", "E"]
            println!("Total cost: {}", cost);           // 12
        }
        None => println!("No path found"),
    }
}
```