astar_bag does not terminate on graphs with a zero-cost cycle

[tachsin]

astar_bag never returns its first solution when the graph contains a cycle whose edges all cost zero. It is not slow, it does not terminate: the first next() on the returned iterator allocates until the process dies. I hit it as a 103 GB allocation failure during a randomised comparison against a brute-force reference.

Costs are only required to be non-negative, and astar handles the same graphs correctly, so this is astar_bag alone.

Reproducing

use pathfinding::prelude::{astar, astar_bag};

let succ = |&n: &u32| match n {
    0 => vec![(1, 1u32)],
    1 => vec![(1, 0), (2, 1)],   // zero-cost self loop on node 1
    _ => vec![],
};

// Fine: returns a 3-node path costing 2.
assert!(astar(&0, succ, |_| 0, |&n| n == 2).is_some());

// Returns cost 2, then this hangs forever.
let (solutions, _cost) = astar_bag(&0, succ, |_| 0, |&n| n == 2).unwrap();
let _first = solutions.take(1).collect::<Vec<_>>();

A self loop is the smallest case, but any zero-cost cycle does it:

graph	astar	astar_bag
zero-cost self loop on 1	cost 2	never returns
zero-cost 2-cycle, 1 -> 3 -> 1 both 0	cost 2	never returns
same shape, cycle edges cost 1	cost 2	[0, 1, 2], then exhausted

The third row is the control: same topology, only the cost differs, and everything works. So it is the zero cost rather than the shape.

Cause

Two pieces meet badly.

When a successor is reached again at exactly the cost already recorded, the node it came from is added as an additional optimal parent:

if e.get().1 == new_cost {
    // New parent with an identical cost, this is not
    // considered as an insertion.
    let s = e.get_mut();
    if !s.0.contains(&index) {
        s.0.push(index);
    }
}

Across a zero-cost edge that is reachable, so with a self loop on 1, arriving at 1 from 1 costs exactly what arriving at 1 already cost, and 1 ends up recorded as its own parent. With the two-node cycle, 1 and 3 end up as each other's parents.

AstarSolution::complete then walks backwards through parents until it finds a node that has none, taking that to mean it has reached the start:

loop {
    let ps = match self.current.last() {
        None => self.sinks.clone(),
        Some(last) => self.parents(*last.last().unwrap()).clone(),
    };
    if ps.is_empty() {
        break;
    }
    self.current.push(ps);
}

Given 1 -> 1 -> 1 -> ... that walk never reaches a parentless node, and self.current grows until memory runs out.

Note on what the right answer is

With a zero-cost cycle there are infinitely many equally cheap walks, so "all shortest paths" is not a finite set unless paths are required to be simple. The rest of the crate already takes that position: astar documents that "a node will never be included twice in the path". Restricting astar_bag to simple paths would make the answer finite and consistent with astar, and would leave graphs without zero-cost cycles completely unaffected, since a shortest path through positive edges cannot repeat a node anyway.

Happy to put up a PR along those lines. The part that needs care is that complete currently reads "no parents" as "reached the start", so skipping a parent for being already on the path must trigger backtracking rather than emit a path that stops short of the start.