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.
> 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 ?