Algorithm configuration builders

[pnevyk]

Instead of using several run methods with many arguments, the algorithms can use the builder pattern with reasonable defaults instead. Example with ShortestPaths:

Current way

ShortestPaths::run(&graph, start, Some(goal), edge_weight);
ShortestPaths::run_algo(&graph, start, Some(goal), edge_weight, Some(shortest_paths::Algo::Dijkstra));
ShortestPaths::run_dijkstra(&graph, start, Some(goal), edge_weight);
ShortestPaths::run_bellman_ford(&graph, start, edge_weight);

Builder pattern

The API is just a quick, first draft and is subject to change.

ShortestPaths::run(&graph, start); // with goal = None, edge_weight = identity, algo = any
ShortestPaths::with(&graph, start).goal(goal).edge_weight(edge_weight).dijkstra().run();

An interesting challenge will be to allow to choose a specific algorithm which should also result in more specific constraints on the graph (for which there are now separate functions such as run_dijkstra). But this should be quite doable with type parameters and zero-sized new types.

The main advantages are:

• The API should be more convenient to use, especially when the default values are appropriate.
• More options can be added in a backwards-compatible way.
• It enables to use optional arguments (Option) with a generic type without any hassle (for a function fn foo<T>(x: Option<T>) the compiler cannot infer the type for T in foo(None)).

[pnevyk]

Alternative builder API:

ShortestPaths::on(&graph).run(start); // with goal = None, edge_weight = identity, algo = any
ShortestPaths::on(&graph).goal(goal).edge_weight(edge_weight).dijkstra().run(start);

The difference between on and run methods is:

• on would always take the graph, which would determine the graph concrete type, which would often be necessary or helpful with restricting the builder API available (e.g., bellman_ford() could not be used if the graph does no implement required traits).
• run would take required arguments of the algorithm where no default value makes sense (in the shortest paths example, it is the start of the search).

The advantage is that the appearance of the usage is consistent whether or not any builder method is used. Although there could still be a shortcut:

ShortestPaths::run(&graph, start); // with goal = None, edge_weight = identity, algo = any

[pnevyk]

When implementing the run method on the builder, specify the graph constraints on the method level rather than impl level, because it arguably gives slightly better error messages when violated (playground).

// Method level - GOOD
impl<G> Builder<G, Dijkstra> {
    pub fn run(self, ...)
    where
        G: ...,
    {
        // ...
    }
}

// Impl level - WORSE
impl<G> Builder<G, BellmanFord>
where
    G: ...,
{
    pub fn run(self, ...) {
        // ...
    }
}