Resolve undefined behavior for unreachable targets in `ShortestPath`

[dominikbraun]

The behavior of the current ShortestPath implementation is not clearly defined when the target vertex isn't reachable from the source vertex. The documentation says that an error is returned when the target isn't reachable, but I'm not so sure whether this is true at all... At the moment, this scenario isn't covered by too many test cases either.

The behavior should be clearly defined, documented, and tested. Further checks in the implementation to determine whether the target is reachable are needed in any case.

[alexloebel]

Hi,

I encountered the same issue and found one example where it does not seem to terminate:

g := graph.New(graph.StringHash)

g.AddVertex("hello")
g.AddVertex("world")

g.AddEdge("hello", "world")
g.AddEdge("world", "bye")

path, err := graph.ShortestPath(g, "hello", "bye")

log.Println(path)

I.e. if one only adds the edge (to node "bye") without ever adding the node beforehand. Even if this is usage that is not supported, I'd say this should return an error rather than running forever.

As far as I can tell, it seems to be stuck in this backtracking loop: https://github.com/dominikbraun/graph/blob/21fcddafc8008532b8932dd616bda0fbb0e0493d/paths.go#L130

Hope this helps!

[dominikbraun]

@alexloebel Thanks!

Even if this is usage that is not supported, I'd say this should return an error rather than running forever.

An error is already returned by g.AddEdge("world", "bye") because both nodes need to exist beforehand. But yes, ShortestPath should return an error here as well.

[alexloebel]

I think, I have another example on a well-defined (directed) graph this time. This again does not terminate while it should find that there is no shortest path.

func graph_example() {
    g := graph.New(graph.IntHash, graph.Directed())
    g.AddVertex(0)
    g.AddVertex(1)
    g.AddVertex(2)

    g.AddEdge(0, 1)
    g.AddEdge(0, 2)

    p, err := graph.ShortestPath(g, 1, 2)
    if err != nil {
        log.Fatal(err)
    }
    log.Println(len(p))
}

Obviously, there is no path from 1 to 2 since the edges are directed and thus it should report that.

[dominikbraun]

I'm going to close this issue as this should be fixed with release 0.15.1.