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