Remove The Hashmap from Shorted Path for Centrality Computation

Paulo-21 commented 2 weeks ago

Hello, I removed the hashmap for the shorted path for centrality.

This may improve performance.

Tell me what do u think about :)

coveralls commented 2 weeks ago

Pull Request Test Coverage Report for Build 11846697683

Details

20 of 20 (100.0%) changed or added relevant lines in 1 file are covered.
No unchanged relevant lines lost coverage.
Overall coverage remained the same at 95.809%

Totals
Change from base Build 11840985523:	0.0%
Covered Lines:	18013
Relevant Lines:	18801

💛 - Coveralls

Paulo-21 commented 2 weeks ago

I think minimizing the number of hashing operations that happen during the shortest path is a good idea in general. But I am not convinced this works, we need to benchmark this more carefully.

I have a feeling this method will be slower for directed graphs, where some nodes are not able to reach all other nodes in the graph. In those cases, having a small hashmap with the nodes that can be reached is much faster than having a large vector with mostly non-visited entries.

I heard your argument and i agree that we should benchmark to be sure that it will be faster when the hashmap was not full filled But in this particular case the hashmap was full filled before the algorithm started so i don't think it will cause any different. I think we can replace every hashmap indexed by NodeId type and that is full filled before algorithm start.

Qiskit / rustworkx