Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
967 stars 140 forks source link

Add stochastic block model generator #1200

Closed SILIZ4 closed 1 month ago

SILIZ4 commented 1 month ago

This naive O(n^2) algorithm might not be the fastest possible algorithm since there exists a O(m) algorithm for G(n, p), but I didn't see how to generalize it for non square "sub-matrices". I'm not convinced that networkx's implementation with iterators is actually more efficient.

I was unable to add hyperlinks to the G(n, p) generator in rustworkx and rustworkx-core. Is there a way to do so?

coveralls commented 1 month ago

Pull Request Test Coverage Report for Build 9238376817

Details


Changes Missing Coverage Covered Lines Changed/Added Lines %
rustworkx-core/src/generators/random_graph.rs 72 73 98.63%
<!-- Total: 132 133 99.25% -->
Totals Coverage Status
Change from base Build 9192798441: 0.02%
Covered Lines: 17105
Relevant Lines: 17813

💛 - Coveralls
IvanIsCoding commented 1 month ago

This naive O(n^2) algorithm might not be the fastest possible algorithm since there exists a O(m) algorithm for G(n, p), but I didn't see how to generalize it for non square "sub-matrices". I'm not convinced that networkx's implementation with iterators is actually more efficient.

I was unable to add hyperlinks to the G(n, p) generator in rustworkx and rustworkx-core. Is there a way to do so?

By the way, for links you want:

SILIZ4 commented 1 month ago

I wasn't sure how dependencies versions should be handled so I added ndarray directly with cargo. Docs hyperlinks are fixed. I also changed the first argument for the community sizes instead of membership. It makes more sense and is what networkx uses.

IvanIsCoding commented 1 month ago

I wasn't sure how dependencies versions should be handled so I added ndarray directly with cargo. Docs hyperlinks are fixed. I also changed the first argument for the community sizes instead of membership. It makes more sense and is what networkx uses.

I will tweak ndarray to use Cargo workspaces