On 28.06.2017 15:00, François Kawala wrote:
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 don't see the drawback of always using the no_init version, with a single visitor that always does implicit initialization. The init=True version would be redundant, but at almost no extra cost. If the extra cost is important, the user should be using init=False anyways...
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.
There is no such thing... I just use a text editor (emacs).
* how do you debug during development ?
GDB, valgrind, etc. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>