Simple Force-directed Graph Algorithm

README.md

A simple force-directed graph algorithm ported to Rust, copied from here:

• https://stackoverflow.com/a/62393274/26829651
• https://editor.p5js.org/JeromePaddick/sketches/bjA_UOPip

fdg.rs

use nannou::glam::*;
use nannou::rand::random_range;

#[derive(Debug, Clone)]
pub struct Node {
    pub pos: Vec2,
    pub size: f32,
    pub force: Vec2,
    pub mass: f32,
}

impl Node {
    pub fn new(pos: Vec2, size: f32) -> Self {
        Node {
            pos,
            size,
            force: Vec2::ZERO,
            mass: (2.0 * std::f32::consts::PI * size) / 1.5,
        }
    }

    pub fn update(&mut self) {
        let vel = self.force / self.mass;
        self.pos += vel;
    }
}

#[derive(Debug)]
pub struct Conn {
    pub a: usize,
    pub b: usize,
}

pub struct Graph {
    pub nodes: Vec<Node>,
    pub connections: Vec<Conn>,
    pub gravity_constant: f32,
    pub force_constant: f32,
}

impl Default for Graph {
    fn default() -> Self {
        Self {
            nodes: Default::default(),
            connections: Default::default(),
            gravity_constant: 1.1,
            force_constant: 1000.0,
        }
    }
}

impl Graph {
    pub fn gen_random(nodes: usize, connections: usize, size: Vec2) -> Self {
        let mut graph = Graph::default();

        let start_dist_multiplier = 10.0;
        for i in 0..nodes {
            let x = random_range(
                -start_dist_multiplier * size.x,
                start_dist_multiplier * size.x,
            );
            let y = random_range(
                -start_dist_multiplier * size.y,
                start_dist_multiplier * size.y,
            );
            graph.nodes.push(Node::new(vec2(x, y), 10.0));
        }

        for i in 0..connections {
            graph.connections.push(Conn {
                a: random_range(0, nodes - 1),
                b: random_range(0, nodes - 1),
            });
        }

        graph
    }

    pub fn update(&mut self) {
        for node in &mut self.nodes {
            let gravity = node.pos * -1.0 * self.gravity_constant;
            node.force = gravity;
        }

        for i in 0..self.nodes.len() {
            for j in 0..self.nodes.len() {
                let pos = self.nodes[i].pos;
                let dir = self.nodes[j].pos - pos;
                let force = dir / dir.length().max(0.001).powf(2.0);
                let force = force * self.force_constant;
                self.nodes[i].force += force * -1.0;
                self.nodes[j].force += force;
            }
        }

        for conn in &mut self.connections {
            let mut a = self.nodes[conn.a].pos;
            let mut b = self.nodes[conn.b].pos;
            let dist = a - b;
            self.nodes[conn.a].force -= dist;
            self.nodes[conn.b].force += dist;
        }

        for node in &mut self.nodes {
            node.update();
        }
    }
}

main.rs

use nannou::prelude::*;

mod fdg;

fn main() {
    nannou::app(model).update(update).run();
}

struct Model {
    window: window::Id,
    graph: fdg::Graph,
}

fn model(app: &App) -> Model {
    let window = app.new_window().view(view).build().unwrap();
    let mut graph = fdg::Graph::gen_random(100, 75, app.window_rect().wh());
    graph.force_constant = 3000.0;
    graph.gravity_constant *= 1.5;
    Model {
        window,
        graph,
    }
}

fn update(_app: &App, model: &mut Model, _update: Update) {
    model.graph.update();
}

fn view(app: &App, model: &Model, frame: Frame) {
    let draw = app.draw();
    draw.background().color(BLACK);

    for conn in &model.graph.connections {
        let a = &model.graph.nodes[conn.a];
        let b = &model.graph.nodes[conn.b];
        draw.line().start(a.pos).end(b.pos).color(WHITE).finish();
    }
    for node in &model.graph.nodes {
        draw.ellipse()
            .color(WHITE)
            .radius(node.size / 2.0)
            .xy(node.pos);
    }

    draw.to_frame(app, &frame).unwrap();
}