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 <tiago@skewed.de> 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 graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool