ForceAtlas2 Rust

Very fast implementation of ForceAtlas2 – force-directed Continuous Graph Layout Algorithm for Handy Network Visualization (i.e. position the nodes of a n-dimension graph for drawing it more human-readably)

Optimization

The implementations used depend on the type and the parameters. The most optimized is a Copy type with prevent_overlapping and barnes_hut disabled, in 2D or 3D. Some specializations are not implemented yet. x86 and x86_64 processors with support to avx2 use SIMD to compute faster on the f64 or f32, 2D, prevent_overlapping disabled and barnes_hut disabled case.

TL;DR If you want best performance, use the following:

• CPU: x86 or x86_64 with avx2
• Layout<f32> (Layout<f64> should be ~2 times slower)
• Settings::prevent_overlapping: None
• Settings::barnes_hut: false (or just don't use this feature)
• RUSTFLAGS='-C target-feature=+avx2'

Use the barnes_hut feature to turn repulsion from O(n^2) to O(n×log(n)) (only for 2D/3D and f64/f32). However, some optimizations like SIMD are not available with Barnes-Hut.

Parallelization is implemented for all the cases without other barnes_hut and prevent_overlapping. The bigger is your graph, the more interesting is the parallel mode. Tune it with Settings::chunk_size. You can control the number of threads with rayon::ThreadPoolBuilder. Parallel SIMD is still a bit unstable, turn it off if it causes trouble.

Examples

Install Rustup and switch to nightly:

rustup toolchain install nightly && rustup default nightly

Clone repository:

git clone https://framagit.org/ZettaScript/forceatlas2-rs && cd forceatlas2-rs

The file examples/wot.csv lists the edges of a directed graph, in two columns.

GTK viewer

You need GTK installed.

RUSTFLAGS='-C target-feature=+avx2' cargo run --release -p viz -- examples/wot.csv

SDL viewer

A packet may be needed to draw graph:

sudo apt install libfreetype6-dev

Build example:

RUSTFLAGS='-C target-feature=+avx2' cargo build --release --example csv_import
./target/release/examples/csv_import examples/wot.csv

Output images are in target directory.

Comparison

Python (forceatlas2, fa2) and JS (sigma.js) implementations are slow.

Java implementation (Gephi) does not use SIMD.

Julia implementation (Anim-Wotmap) beats them all and uses SIMD, but is still slower than this one.

If you know any faster comparable force-directed layout implementation, please let me know.

Bindings

There is a binding for use in Python, fa2rs.

License

GNU AGPL v3, CopyLeft 2020-2021 Pascal Engélibert

Implementation details inspired by:

• python-forceatlas2 (GNU GPL v3, CopyLeft 2016 Max Shinn)
• python-fa2 (GNU GPL v3, CopyLeft 2017 Bhargav Chippada)
• Gephi (GNU GPL v3 / CDDL 1.0, CopyLeft 2011 Gephi Consortium)
• sigma.js, Graphology (MIT, Guillaume Plique)
• Anim-Wotmap (Hugo Trentesaux)

The ForceAtlas2 paper was released under CC BY, Copyright 2014 Jacomy et al.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, version 3 of the License.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License along with this program. If not, see https://www.gnu.org/licenses/.