pnevyk / gryf

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

Use BFS for shortest paths if unit weight is used #22

Closed pnevyk closed 1 year ago

pnevyk commented 1 year ago

In shortest paths algorithm, detect if unit weight (i.e., all edges have weight equal to 1) is used and use simple BFS algorithm if so. Unit edge weights are represented by Unit type. For unit weights the overhead of Dijkstra's algorithm is unnecessary and thus using a straightforward BFS implementation will be more efficient.

Somewhat tricky part is how to deduce that the edge weight getter represents unit weight. We can't use std::any API, because we don't want to constrain the edge weight getter to be 'static. One possible way that I can think of now is to add a new static method to GetEdgeWeight trait called is_unit() -> bool with the default implementation returning false. The Unit type would then be the only type that would return true. This is not perfect as it can't recognize user functions that also represent a unit weight, but using such functions should be discouraged.

Do not expose BFS as a new algorithm option in Algo enum, as this should be solely an implementation detail, which covers only a niche use case.

pnevyk commented 1 year ago

Deducing that the weight getter represents a constant weight can be done with getter.get_const().is_some(), where get_const is an extension of GetWeight trait mentioned in #31.

pnevyk commented 1 year ago

Having a bfs() method on the algorithm builder that would force the BFS algorithm should be probably allowed, because using a specific algorithm is needed in cases where the type constraints of the common entrypoint are too strict. In shortest paths example, it is completely valid to run the algorithm on an implicit graph, and dijkstra() already allows that. BFS should be possible too. Calling this bfs() would only be allowed if the edge weight type is Unit.