Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rename DigraphDijkstra #570

Open
mtorpey opened this issue Jan 18, 2023 · 0 comments
Open

Rename DigraphDijkstra #570

mtorpey opened this issue Jan 18, 2023 · 0 comments
Assignees
Labels
not-backwards-compatible A label for PRs that break backwards compatibility

Comments

@mtorpey
Copy link
Collaborator

mtorpey commented Jan 18, 2023

DigraphShortestPath and DigraphDijkstra are two closely related functions that both find the shortest path between two vertices, where "shortest" means "fewest edges".

The algorithm they're using appears to be basically the same: it's a breadth-first search starting at the source vertex and proceeding until the destination vertex is found. Dijkstra's algorithm in general is smarter than this, since it uses edge lengths to decide where to explore next; but we don't have edge lengths, so this isn't relevant here.

The reason both operations are valuable is that they have different outputs. They both return two lists, but don't be fooled! DigraphShortestPath returns

a pair of lists [v,a] as follows:
• v is the list [v_1, v_2, ..., v_n].
• a is the list of positive integers [a_1, a_2, ..., a_n-1] where for each each i < n, a_i is the position of v_i+1 in OutNeighboursOfVertex(digraph,v_i) corresponding to the edge e_i.

whereas DigraphDijkstra returns

two lists. Each element of the first list is the distance of the corresponding element from source. If a vertex was not visited in the process of calculating the shortest distance to target or if there is no path connecting that vertex with source, then the corresponding distance is infinity. Each element of the second list gives the previous vertex in the shortest path from source to the corresponding vertex. For source and for any vertices that remained unvisited this will be -1.

The issue here is that "DigraphDijkstra" isn't a helpful name. We usually name our operations after the thing they return rather than the author of the core algorithm we're using. The output of DigraphShortestPath is consistent with other "paths" in the package, so this is reasonable. Hence we need a name to replace "Dijkstra".

The main thing that distinguishes Dijkstra from ShortestPath is that it gives information on how to reach multiple vertices in the shortest distance: all vertices in the connected component, or else all the ones it can find while searching for destination. Hence, a good option might be DigraphShortestPaths, which I don't think would be too confusing.

We could make this change easily, although we should make sure to preserve DigraphDijkstra as a synonym for backwards compatibility, till 2.0

Any thoughts?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
not-backwards-compatible A label for PRs that break backwards compatibility
Development

No branches or pull requests

2 participants