Constant weights

[pnevyk]

For graphs without edge weights, shortest path algorithms use some constant value (e.g., 1), which is represented by Unit type. However, the implementation of Dijkstra still accesses the edge to the next neighbor to be able to get the weight, even when the weight getter does not actually need that edge (as in Unit case). This is unfortunate for two reasons:

1. It does unnecessary work (retrieving the edge data) which is never zero-cost in standard storages.
2. It requires implicit graphs to implement EdgesWeak::edge_weak that returns Some, even if otherwise unnecessary.

Instead, the GetWeight trait can be extended such that it can communicate an availability of a constant weight, i.e., allow to skip retrieving the edges.

pub trait GetWeight<E, W>
where
    W: Weight,
{
    fn get(&self, edge: &E) -> W;
    fn get_const(&self) -> Option<W> { None }
}

Having a default implementation means that it is opt-in, and can be really overridden only by our Unit type. Taking &self (i.e., not using fn get_const() -> Option<W> signature, is to allow types that return a constant value determined at runtime (e.g., passed to the constructor of a hypothetical Constant weight getter).

The implementation of an algorithm can then first ask for get_const and use the edge to compute the weight only if the constant value is not available. I strongly believe that the compiler should even be able to eliminate the check and choose the appropriate code path when the concrete types are known.