Hello,

I try to dig up an old idea that we've discussed previously (the thread is here).

summary: when one runs shortest distance on a graph with several million vertices the distance initialization cost is high with respect to the actual Dijsktra cost. We want to circumvent the initialization [see L326 of src/graph/topology/graph_distance.cc]

The proposed approach (as per this boost thread) is to use the `dijkstra_shortest_paths_no_color_map_no_init`. The distance initialization is done "on the fly" by the `examine_edge` function. More precisely, the Dijkstra visitor maintains a set of discovered vertices. This set is read in the `examine_edge` function to set the distance to infinity when a the target vertex does not belong to the set of discovered vertices. The `examine_edge` function is also responsible to update the set of discovered vertices.

As proposed in the initial thread, we would like to add a init-or-not switch to the shortest_distance parameters (see L1568 of /src/graph_tool/topology/__init__.py).

I plan to :

define a new Dijkstra visitor named `djk_max_visitor_no_init` (and maybe a second one to handle multiple targets scenario)
update the `do_djk_search` function to use `dijkstra_shortest_paths_no_color_map_no_init`
update the python shortest_distance (add the init-or-not switch)

How does it sounds ? Am I missing something ?

I have two side questions :

what is the "standard" development environment ? I tried to use CLION but I cannot figure out how to configure it properly so that all the boost dependencies are correctly resolved.
how do you debug during development ?

Best regards,

François.