Hello, I try to dig up an old idea that we've discussed previously (the thread is here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Shortest-distance-complexity-when-used-with-max-dist-td4026018.html> ).
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 <https://git.skewed.de/count0/graph-tool/blob/master/src/graph/topology/graph_distance.cc#L326> ] The proposed approach (as per this boost thread <https://groups.google.com/forum/#!topic/boost-list/7nCzvkkEXCk>) 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 <https://git.skewed.de/count0/graph-tool/blob/master/src/graph_tool/topology/__init__.py#L1568> ). 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 <https://www.jetbrains.com/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.
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
