'predecessors' argument to igraph_get_shortest_paths[_dijkstra]
Bug #920681 reported by
Tamás Nepusz
This bug affects 1 person
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
igraph |
In Progress
|
Medium
|
Unassigned |
Bug Description
When running the single-source shortest path (SSSP) algorithm from Python on a large graph, most of the time is actually spent not by finding the paths but by converting the path vectors to Python lists. A lot of time could be saved by allowing the user to query the "predecessor vector" instead of the actual paths. The i-th element of the predecessor vector would simply be the index of the vertex that is the predecessor of vertex i in the SSSP tree or -1 if the vertex was not reached. (The predecessor of i is of course i itself).
We could simply add this feature by adding a third argument called "predecessors" besides the existing "vertices" and "edges" arguments in the C layer.
Changed in igraph: | |
status: | New → Confirmed |
importance: | Undecided → Medium |
assignee: | nobody → Tamás Nepusz (ntamas) |
Changed in igraph: | |
status: | Confirmed → In Progress |
milestone: | none → 0.7 |
Changed in igraph: | |
assignee: | Tamás Nepusz (ntamas) → nobody |
To post a comment you must log in.
Fine with me.