Shortest path function that returns a "shortest path tree" object usable for quick path retreival

[szhorvat]

What is the feature or improvement you would like to see?

The current shortest path functions will return a list of paths from a source s to all other vertices.

This is a proposal for an additional, different function which also takes a source s as input, and will return a special object which can be used for the efficient computation of paths from s to any t on demand. The object would contain a shortest path tree rooted at s, in a suitable representation. The C layer also produces this information, e.g. in

int igraph_get_shortest_paths_dijkstra(const igraph_t *graph,
                                       igraph_vector_ptr_t *vertices,
                                       igraph_vector_ptr_t *edges,
                                       igraph_integer_t from,
                                       igraph_vs_t to,
                                       const igraph_vector_t *weights,
                                       igraph_neimode_t mode,
                                       igraph_vector_long_t *predecessors,
                                       igraph_vector_long_t *inbound_edges)

the predecessors and inbound_edges output arguments encode this tree.

The object will have methods to:

• Get the shortest path to any t vertex
• Extract the tree in various formats (edge ID list or an actual graph)

Use cases for the feature

The proposed object is a concise representation of the shortest path structure from a given source. It takes O(|V|) storage only. The full lists of paths takes O(|V| d) storage where d is the average distance from s.

This object may be used repeatedly to get the shortest paths to arbitrary other nodes, very efficiently. If a user need to compute shortest path from s to other nodes, but does not know which other nodes to take yet, they are likely to run a full single-source shortest path algorithm separate for each target node. This is inefficient—why don't we make it possible to store the gist of the result from a single run and re-use it?

This function will be especially useful when working with large graphs, where both computation time and storage requirements are a concern.

In some applications, the shortest path tree itself may be of use. It is useful to have a function to provide this in igraph. The proposed function would achieve this with a concise API and added functionality.

This is in the spirit of the Flexibility design principle I recently proposed: don't just return the result in the most naïve/simple form; instead enable users to do as many different things as possible with the result of the computation.