Handling closures and FnMut

[RaoulLuque]

Hi there,

I thought that it'd be neat if one could combine some functionalities from petgraph with the flexibility of the API in the pathfinding crate.

That is, I am trying to create a Dijkstra struct (to run and store the results of the Dijkstra algorithm), but provide the functionality to run the algorithm using closures or graphs from petgraph as desired. That is, have the flexibility to only provide closures when creating a new dijkstra struct (similar to the Pathfinding APIs) or to provide an entire petgraph graph.

However, I am having problems with getting the types to be "instantiated" correctly, in particular working with the FnMut traits and closures.

This is the basic and easy part of the code / struct:

pub struct Dijkstra<N, C, FN, IN, FG>
where
    N: Eq + Hash,
    C: Measure + Copy,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FG: FnMut(&N) -> bool,
{
    start: N,
    neighbors: FN,
    goal: FG,
    pub distances: HashMap<N, C>,
}

impl<N, C, FN, IN, FG> Dijkstra<N, C, FN, IN, FG>
where
    N: Eq + Hash + Copy,
    C: Measure + Copy,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FG: FnMut(&N) -> bool,
{
    pub fn new_from_closures(
        start: N,
        neighbors: FN,
        goal: FG,
    ) -> Self {
        Self {
            start,
            neighbors,
            goal,
            distances: HashMap::new(),
        }
    }
}

However, now I would want to add another associated function, i.e. a method / factory, to construct a Dijkstra instance from a petgraph graph. That is, something like the following:

pub fn new_from_graph<G, FC, C>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_cost: FC,
) -> Dijkstra<
    G::NodeId,
    C,
    impl FnMut(&G::NodeId) -> impl IntoIterator<Item = (G::NodeId, C)>,
    impl IntoIterator<Item = (G::NodeId, C)>,
    impl FnMut(&G::NodeId) -> bool,
>
where
    G: IntoEdges + Visitable,
    G::NodeId: Eq + Hash,
    FC: FnMut(G::EdgeRef) -> C,
    C: Measure + Copy,
{
    let neighbors = move |node: &G::NodeId| {
        graph
            .edges(*node)
            .map(|edge: G::EdgeRef| (edge.target(), edge_cost(edge)))
    };
    let goal_fn = move |node: &G::NodeId| *node == goal;
    Dijkstra::new_from_closures(start, neighbors, goal_fn)
}

Technically, the above is not a method, because I wanted to try implementing it as a function first as that seemed easier with all the generics and trait bounds.
However, this fails since impl Trait is not allowed in the return type of Fn trait bounds. More specifically the compiler error message is the following:

error[E0562]: `impl Trait` is not allowed in the return type of `Fn` trait bounds
   --> src/algo/dijkstra.rs:106:31
    |
106 |     impl FnMut(&G::NodeId) -> impl IntoIterator<Item = (G::NodeId, C)>,
    |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `impl Trait` is only allowed in arguments and return types of functions and methods
    = note: see issue #99697 <https://github.com/rust-lang/rust/issues/99697> for more information
    = help: add `#![feature(impl_trait_in_fn_trait_return)]` to the crate attributes to enable
    = note: this compiler was built on 2025-07-26; consider upgrading it if it is out of date

How could I address this without using the feature flag? Could I somehow specify the return type of the FnMut for the instances created from graphs? That is, replace the impl IntoIterator<_> with a specific type and fix the issue that way?

Thanks in advance

[kpreid]

Some possibilities:

• Implement your iterator as a custom struct without using .map() or any other closures. (This is usually the best choice for a library.)
• Specify the concrete type of the iterator. (You will have to specify fn(G::EdgeRef) -> (G::NodeId, C) as the type of the function in the iter::Map adapter. This may result in some dynamic dispatch overhead that could otherwise be avoided.)
• Add to your library a trait Pathfind that Dijkstra implements. This way, new_from_closures() can return impl Pathfind and hide all the generics.
• Return Box<dyn Iterator> instead of impl IntoIterator from the neighbors function.

Someday, when we have type alias impl Trait (TAIT) in stable Rust, we will be able to give names to the anonymous types here, and then there will no longer be a tradeoff that has be made just to allow the use of .map().

[RaoulLuque]

Thanks for the quick response Just for completeness and anyone wondering, here is the solution I went for (implementing an own iterator type):

pub struct Dijkstra<N, FG, FN, IN, FC, C>
where
    N: Eq + Hash,
    FG: FnMut(&N) -> bool,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>,
    FC: FnMut(&N, &N) -> C,
    C: Measure + Copy,
{
    start: N,
    goal: FG,
    neighbors: FN,
    edge_cost: FC,
    distances: HashMap<N, C>,
}

impl<N, C, FN, IN, FC, FG> Dijkstra<N, FG, FN, IN, FC, C>
where
    N: Eq + Hash + Copy,
    FG: FnMut(&N) -> bool,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>,
    FC: FnMut(&N, &N) -> C,
    C: Measure + Copy,
{
    pub fn new_from_closures(start: N, goal: FG, neighbors: FN, edge_cost: FC) -> Self {
        Self {
            start,
            neighbors,
            edge_cost,
            goal,
            distances: HashMap::new(),
        }
    }

    pub fn run(&mut self) -> DijkstraResult<N, C> {
        let mut visited = HashSet::new();
        let mut visit_next = BinaryHeap::new();
        let zero_score = C::default();
        self.distances.insert(self.start, zero_score);
        visit_next.push(MinScored(zero_score, self.start));
        let mut goal_node = None;
        while let Some(MinScored(node_score, node)) = visit_next.pop() {
            if visited.contains(&node) {
                continue;
            }
            if (self.goal)(&node) {
                goal_node = Some(node);
                break;
            }
            for next in (self.neighbors)(&node) {
                if visited.contains(&next) {
                    continue;
                }
                let next_cost = (self.edge_cost)(&node, &next);
                let next_score = node_score + next_cost;
                match self.distances.entry(next) {
                    Occupied(ent) => {
                        if next_score < *ent.get() {
                            *ent.into_mut() = next_score;
                            visit_next.push(MinScored(next_score, next));
                            //predecessor.insert(next.clone(), node.clone());
                        }
                    }
                    Vacant(ent) => {
                        ent.insert(next_score);
                        visit_next.push(MinScored(next_score, next));
                        //predecessor.insert(next.clone(), node.clone());
                    }
                }
            }
            visited.insert(node);
        }
        DijkstraResult {
            paths: HashMap::new(),
            distances: self.distances.clone(),
        }
    }
}

#[doc(hidden)]
/// A marker type used for `Dijkstra::new_from_graph` to provide for the `neighbors` type parameter.
pub struct DijkstraMarkerType<N> {
    _marker: core::marker::PhantomData<N>,
}

#[doc(hidden)]
impl<N> IntoIterator for DijkstraMarkerType<N> {
    type Item = N;
    type IntoIter = core::iter::Empty<N>;

    fn into_iter(self) -> Self::IntoIter {
        core::iter::empty()
    }
}

pub struct DijkstraNeighborIterator<G>
where
    G: IntoEdges,
{
    edges: G::Edges,
}

impl<G> Iterator for DijkstraNeighborIterator<G>
where
    G: IntoEdges,
{
    type Item = G::NodeId;

    fn next(&mut self) -> Option<Self::Item> {
        match self.edges.next() {
            Some(edge_red) => Some(edge_red.target()),
            None => None,
        }
    }
}

impl<N, C, FG>
    Dijkstra<N, FG, fn(&N) -> DijkstraMarkerType<N>, DijkstraMarkerType<N>, fn(&N, &N) -> C, C>
where
    N: Eq + Hash + Copy,
    FG: FnMut(&N) -> bool,

    C: Measure + Copy,
{
    pub fn new_from_graph<G, FCG>(
        graph: G,
        start: G::NodeId,
        goal: FG,
        mut edge_cost: FCG,
    ) -> Dijkstra<
        G::NodeId,
        FG,
        impl FnMut(&G::NodeId) -> DijkstraNeighborIterator<G>,
        DijkstraNeighborIterator<G>,
        impl FnMut(&G::NodeId, &G::NodeId) -> C,
        C,
    >
    where
        G: IntoEdges + Visitable,
        G::NodeId: Eq + Hash,
        FG: FnMut(&G::NodeId) -> bool,
        FCG: FnMut(G::EdgeRef) -> C,
        C: Measure + Copy,
    {
        let neighbors = move |node: &G::NodeId| DijkstraNeighborIterator {
            edges: graph.edges(*node),
        };
        let edge_cost = move |start: &G::NodeId, end: &G::NodeId| {
            let mut cost = None;
            for edge in graph.edges(*start) {
                if edge.target() == *end {
                    cost = Some(edge_cost(edge));
                    break;
                }
            }
            cost.expect("Edge not found")
        };
        Dijkstra::new_from_closures(start, goal, neighbors, edge_cost)
    }
}

See, here.