Remove The Hashmap from Shorted Path for Centrality Computation

[Paulo-21]

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

This may improve performance.

Tell me what do u think about :)

[coveralls]

Pull Request Test Coverage Report for Build 15007738295

Details

• 51 of 51 (100.0%) changed or added relevant lines in 1 file are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage decreased (-0.001%) to 95.235%

---

Totals
Change from base Build 14954677437:	-0.001%
Covered Lines:	18727
Relevant Lines:	19664

---

💛 - Coveralls

[Paulo-21]

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.

[Paulo-21]

Hello, i have finaly run some benchmark This is a screenshot from the perf tool on linux with the version with hashmap. We can see that there a non -negligable time spend with the hashmap.

I have run some benchmark in single thread :

For a small graph with hashmap 1789 micro seconds without hasmap 1050 micro seconds .

For a very big graph : with hashmap : 949950855 micro seconds -> 950 secondes without hashmap : 455474771 micro seconds -> 455 secondes

Do you want more benchmark ?

[IvanIsCoding]

Also, last but not least add a test to test edge betweness centrality with a deleted node: https://github.com/Qiskit/rustworkx/blob/30897c5bc46efcb17bc81c33946a0a4260e2d652/tests/graph/test_centrality.py#L62

[Paulo-21]

Hello, come back from benchmark

I have run some benchmark with the graphs you mentionned before. The supposed worse case and best case senarios.

For the Directed graph of 10000 nodes :

With hashmap : 2.5117154121398926 secondes without : 0.8792691230773926 secondes

For Complete graph of 1000 nodes :

With hashmap : 4.231908559799194 secondes Without : 2.379117965698242 secondes

if you want to test by your self pip install --force-reinstall git+https://github.com/Paulo-21/rustworkx

from rustworkx import betweenness_centrality
import rustworkx.generators
from time import time
#graph = rustworkx.generators.directed_path_graph(100000)
graph = rustworkx.generators.complete_graph(1000)
t = time()
betweenness_centrality(graph)
print(time() - t)

[Paulo-21]

Also, last but not least add a test to test edge betweness centrality with a deleted node:

https://github.com/Qiskit/rustworkx/blob/30897c5bc46efcb17bc81c33946a0a4260e2d652/tests/graph/test_centrality.py#L62

Okay i will do it later

[IvanIsCoding]

There are some Clippy failures, but they are from the update to Rust 1.89. They are not your fault.

you can leave the PR as is, I’ll tweak it and merge it during 0.18. Right now, reviews for 0.17 are a bit stuck

[Paulo-21]

I ran "cargo test -all" with the code up to date and i get this error

Test error trace

failures:

---- centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_improved_digraph stdout ----

thread 'centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_improved_digraph' panicked at rustworkx-core/src/centrality.rs:1394:13:
assertion `left == right` failed
  left: [Some(inf), Some(6.0), Some(2.0), Some(1.0), Some(0.6), Some(0.4000000000000001), Some(0.2857142857142857)]
 right: [Some(0.0), Some(0.16666666666666666), Some(0.2222222222222222), Some(0.25), Some(0.26666666666666666), Some(0.27777777777777773), Some(0.2857142857142857)]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_not_improved_digraph stdout ----

thread 'centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_not_improved_digraph' panicked at rustworkx-core/src/centrality.rs:1373:13:
assertion `left == right` failed
  left: [Some(inf), Some(6.0), Some(2.0), Some(1.0), Some(0.6), Some(0.4), Some(0.2857142857142857)]
 right: [Some(0.0), Some(1.0), Some(0.6666666666666666), Some(0.5), Some(0.4), Some(0.3333333333333333), Some(0.2857142857142857)]

---- centrality::test_newman_weighted_closeness_centrality::test_weighted_closeness_graph stdout ----

thread 'centrality::test_newman_weighted_closeness_centrality::test_weighted_closeness_graph' panicked at rustworkx-core/src/centrality.rs:1348:13:
assertion `left == right` failed
  left: [Some(0.2608695652173913), Some(0.3333333333333333), Some(0.4), Some(0.42857142857142855), Some(0.4), Some(0.3333333333333333), Some(0.2608695652173913)]
 right: [Some(0.2857142857142857), Some(0.375), Some(0.46153846153846156), Some(0.5), Some(0.46153846153846156), Some(0.375), Some(0.2857142857142857)]


failures:
    centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_improved_digraph
    centrality::test_newman_weighted_closeness_centrality::test_the_same_as_closeness_centrality_when_weights_are_1_not_improved_digraph
    centrality::test_newman_weighted_closeness_centrality::test_weighted_closeness_graph

test result: FAILED. 308 passed; 3 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.70s

error: test failed, to rerun pass `-p rustworkx-core --lib`