I cProfiled old versus your last commit. The graph has 7 953 158 vertices, I sample 100 vertices and do shortest_distance from each one. I specify no target, and set the max_dist parameter. After each call to shortest_distance, I use the reached array to reset the predecessor map. In average each search reaches 120177 vertices.
- 2.22 : 9.101 seconds - commit 26404ef4 : 4.536 seconds - commit 26404ef4 + no dist map init : 4.141 seconds That more than twice faster, great news ! About the third configuration (no dist map init), I removed the distance map initialization (graph_tool/topology/__init__.py L1779 <https://git.skewed.de/count0/graph-tool/blob/master/src/graph_tool/topology/__init__.py#L1779>) and used the reached array to reset dist_map to infinity. We could have a do_initialization parameter, I think it would be more explicit, see my proposal <https://git.skewed.de/francois/graph-tool/commit/946826546a80f1f080681a4eaaa5fb2590b5abd4> . François. Le ven. 30 juin 2017 à 21:59, Tiago de Paula Peixoto <[email protected]> a écrit : > On 30.06.2017 18:44, François Kawala wrote: > > I realize that I'm not familiar enough with boost to do this change. > > > > From what I get, I'll add three private members : _distance and > _predecessor > > they would be initialized as follows : > > > > _distance(get(vertex_distance, *_mg)), > > _predecessor(get(predecessor, *_mg)), > > > > I don't know if the _distance member should be filled with zeros ? > > > > The last private member would be _reach a std::vector<size_t> > > > > From that I'll declare two functions : > > > > set_reached to update the reached vertices > > reset_distance to reset the _distance, _predecessor and _reach to > their > > default values. > > > > Does that sounds right ? If so, I'll guess that I'll have to make > > the do_djk_search function to call the set_reached and reset_distance > functions. > > > > Am I missing something ? > > > > Sorry for this stuttering approach. > > I've just pushed a commit that implements what you want; you can look > inside > for the details. > > In short, you can now do multiple searches as follows: > > dist_map = g.new_vp("double", numpy.inf) # must be infinity > pred_map = g.vertex_index.copy() # must be identity > > for source in sources: > > # the following does not initialize dist_map and pred_map, and > # returns an array of reached vertices > > dist_map, pred_map, reached = \ > shortest_distance(g, source, weights=w, pred_map=pred_map, > dist_map=dist_map, return_reached=True) > > # reset property maps for next search; this is O(len(reached)) > > dist_map.a[reached] = numpy.inf > pred_map.a[reached] = reached > > Please tell me if this brings the improvements you were seeking. > > Best, > Tiago > > > > > _______________________________________________ > graph-tool mailing list > [email protected] > https://lists.skewed.de/mailman/listinfo/graph-tool >
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
