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)
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.
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.
You need GTK installed.
RUSTFLAGS='-C target-feature=+avx2' cargo run --release -p viz -- examples/wot.csv
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.
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.
There is a binding for use in Python, fa2rs.
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/.