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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
