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. François. Le jeu. 29 juin 2017 à 18:22, François Kawala <francois@karos.fr> a écrit :
we could have only ***one*** initialization for the whole lifespan of the program. If
I get it right, their proposal would, prior to a search, to "re-set" the values from distances vector and predecessors vector only for the reached vertices of the last search. I think it worth a try because, from what I timed the python side of initialization could cost around 18ms (5ms for distance map, 13ms for predecessor map) see timeit snipet below.
In order for this to work, the function would need to keep and return a list of reached vertices. This is is not difficult to do, but I wonder how much it would actually improve...
To elaborate on this, a quick an dirty profiling (with the timeit module) gives 0.27 ms to reset 10e5 random items to np.inf in a numpy array with 7e6 items.
I'm confident that this improvement worth to be done and I can try to do it.
Once initialized, the distance map, the predecessor map, and the "last reached index" would be internal property maps, correct ? Would it be relevant to do the "re-set" in the CPP part ?
François