LightGraphs users (and other interested parties): please opine below

Specific Domains Graphs
, , , ,
21

consider when you want to do Dijkstra with the same parameters across multiple graphs, and different shortest paths algorithms on the same graph:

d_alg = ShortestPaths.Dijkstra(track_vertices=true)
dsp1 = shortest_paths(g1, 1, d_alg)
dsp11 = shortest_paths(g1, 1, distance_matrix, d_alg)
for sp_alg in [Dijkstra(), BellmanFord()]
    shortest_paths(g, 1, distance_matrix, sp_alg)
end
2 Likes
22

What do you think of Zach’s trait-like idea?

d_alg = ShortestPaths.Dijkstra(track_vertices=true)

becomes

d_alg = ShortestPaths.algorithm(Dijkstra(), track_vertices=true)

and you only have one Dijkstra struct (or something).

23

Hm. That could work. The only disadvantage I see right now – and it’s not a huge one – is that the “track_vertices” is a parameter of the ShortestPaths.algorithm and not Dijkstra. From an abstraction perspective, this doesn’t make sense, as track_vertices is specific to Dijkstra and not, say, FloydWarshall. We would have to throw errors in that case, and it would be really complex to handle defaults.

It’s a really interesting approach though. I need to give it more thought.

24

Sure, but why would you need to handle default arguments for other algorithms. When you call algorithm with a Dijkstra argument, it will dispatch on that particular method that can have different kwargs than other methods (unless I’m confused… again :sweat_smile:).

25

Right now you have:

function Dijkstra(;all_paths=false, track_vertices=false, maxdist=typemax(Float64))
    ...
end

What I’m suggesting would probably be implemented like:

function PathParams(algo::Dijkstra; all_paths=false, track_vertices=false, maxsdist=typemax(Float64))
    PathParams( algo, (all_paths=all_paths, track_vertices=track_vertices, maxsdist=maxsdist))
end

function PathParams(algo::FloydWarshal)
    PathParams(algo, NamedTuple((),Tuple{})())
end

I could come up with some combination of multiple dispatch and kwargs... to throw more specific error messages. If you feel like it’s the right approach I’d be happy to iron out more specifics of implementation.

26

I need to think about this a bit more, so please hold off on doing any work :slight_smile: At first blush it looks overly complicated.

I’m also rethinking my initial bias to not export the structs. It turns out there are some real advantages to exporting them (discoverability, for one), and we might be able to reduce the mane conflicts another way. So many choices!

4 Likes