search

pnevyk / gryf

Graph data structure library aspiring to be convenient, versatile, correct and performant.
MIT License
69 stars 1 forks source link

Desired behavior of shortest paths algorithms when the goal is not reached #29

Closed pnevyk closed 1 year ago

pnevyk commented 1 year ago

The shortest paths API allows to specify a goal vertex:

let result = ShortestPaths::on(&graph).goal(target).run(start).unwrap();

What should be the behavior when the target vertex is not reachable from the start vertex?

  1. Silently ignore that. Then getting distance to the target returns None.
  2. Return an error from run.
pnevyk commented 1 year ago

I am in favor of (2), returning an error from run. Because when the goal is specified, the user desires to find the shortest path and its distance to that target vertex and has right to expect their availability after getting a successful result. In that case, returning None from dist could be confusing. Returning error early should prevent such confusion.

In general case, when no goal is specified, it is fine to return None for unreachable vertices, because the user should keep in mind that a graph in general can contain unreachable vertices.