[vtk-developers] perf improvements to vtkDijkstra* classes

[Dean Inglis]

Is there any interest in (or objections to) PIMPL'ing some (or all) of

the storage containers in vtkDijkstraGraphGeodesicPath?

In a test class, I have reimplemented vtkDijkstraGraphGeodesicPath

using the following substitutions and noticed substantial (qualitative) 

speed gains in interactivity:

 

1) - change containers f and s to vector<bool>

2) - change containers pre, Heap, and p to vector<int>

3) - change container for cost; d, to vector<float>

4) - change container for Adjacency from an array of vtkIdList*  to

  vector<map<int,float>> for unique insertion of vertex id's and

  associated edge costs

 

Probably most of the improvement comes from item 4) since

you can pre-calculate all edge costs at the time of constructing

the adjacency array, which only needs to be done when the input

changes (not when start and end vertices change).

 

Dean

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20080826/385e2074/attachment.html>