search

Qiskit / rustworkx

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

Implement Layout Algorithms targeting Very Large Graphs #1151

Open zachcp opened 8 months ago

zachcp commented 8 months ago

What is the expected enhancement?

I've been using the Rustwork library and its fantastic. However, large spring layouts still take a lot of time. I am wondering if this is a care where adding some amount of parallelization can get a speed boost.

IvanIsCoding commented 7 months ago

I think the limitation here is that Spring Layout is computationally expensive which is not what you need.

I think there are other families of layout algorithms that could fit this use case. https://osf.io/ms27r is a survey that lists a few. We should narrow it down to a specific algorithm that is not too slow and that has OK aesthetics.

jamestwebber commented 7 months ago

I find that SFDP is fast and works well for large graphs (10k to 100k nodes, for me), which is why I opened #917 way back in the day. A re-implementation of that without the dependency on graphviz would be slick.

IvanIsCoding commented 7 months ago

I find that SFDP is fast and works well for large graphs (10k to 100k nodes, for me), which is why I opened #917 way back in the day. A re-implementation of that without the dependency on graphviz would be slick.

That is a good idea. I found https://github.com/t-mw/force-graph-rs/ and https://github.com/grantshandy/fdg to be related, maybe we can depend on another crate or fork their work to get started on this.