Force-Directed Graph Layout

FEATURED

In this example below you will see how to do a Force-Directed Graph Layout with some HTML / CSS and Javascript

Thumbnail
This awesome code was written by Tom, you can see more from this user in the personal repository.
You can find the original code on Codepen.io
Copyright Tom ©
  • HTML
  • CSS
  • JavaScript
    canvas
div.controls
  button.graph.red New

/*Downloaded from https://www.codeseek.co/MisterKeefe/force-directed-graph-layout-gKLdrO */
    body, html {
  width: 100%;
  height: 100%;
  padding: 0;
  margin: 0;
  overflow:hidden;
  background: rgba(255, 255, 250, 1.0);
}

.controls {
  position: absolute;
  bottom: 0;
  left: 0;
  display: grid;
  grid-template-rows: 100px;
  grid-gap: 2px;
}

button {
  font-family: sans-serif;
  font-weight: bold;
  font-size: 16px;
  text-transform: uppercase;
  width: 100px;
  height: 100px;
  border: none;
  background: rgba(192, 192, 192, 1.0);
  color: #fff;
  top: 0;
  left: 0;
  cursor:pointer;
  outline: none!important;
  
  &:hover {
    background: rgba(160, 160, 160, 1.0);
  }
  &:active {
    background: rgba(128, 128, 128, 1.0);
  }
 
  &.red {
     background: rgba(255, 160, 160, 1.0);
    &:hover {
      background: rgba(255, 128, 128, 1.0);
    }
    &:active {
      background: rgba(255, 64, 64, 1.0);
    }
  }
  
  &.blue {
    background: rgba(160, 160, 255, 1.0);
    &:hover {
      background: rgba(128, 128, 255, 1.0);
    }
    &:active {
      background: rgba(64, 64, 255, 1.0);
    }
  }
}


/*Downloaded from https://www.codeseek.co/MisterKeefe/force-directed-graph-layout-gKLdrO */
    let canvas = document.querySelector('canvas');
let ctx = canvas.getContext('2d');

let mousePos;
let dragNode;

canvas.width = document.body.clientWidth;
canvas.height = document.body.clientHeight;

const TIMESTEP = 0.1;
const NODESIZE = 12;
const REPULSION = 10000;
const ATTRACTION = 2/REPULSION;
const DRAG = 2;
const REPULSION_HORIZON = 2;
const ATTRACTION_HORIZON = 2;
const MAX_SPEED = 1;


const distance = (a, b) => {
  return Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));
}

const length = (a) => {
  return distance(a, {x: 0, y: 0});
}

const normalize = (a) => {
  let k = length(a);
  if(k === 0){
    return {
      x: 0,
      y: 0
    }
  }
  return {
    x: a.x / k,
    y: a.y / k
  }
}

const shuffle = (a) => {
    var j, x, i;
    for (i = a.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

class AttractionConstraint {
   constructor (p1, p2, strength) {
     this.p1 = p1;
     this.p2 = p2;
     this.strength = strength || 1.0;
   }
  
  apply (dt) {
     let evec = {
      x: this.p2.position.x - this.p1.position.x,
      y: this.p2.position.y - this.p1.position.y
    }
    
    let distance_without_radii = length(evec) - (ATTRACTION_HORIZON * NODESIZE);
    
    let normalized_evec = normalize(evec);
    
    let scale_factor = this.strength * ATTRACTION * (distance_without_radii * distance_without_radii);
    
    let acceleration_vec = {
      x: normalized_evec.x * scale_factor * dt,
      y: normalized_evec.y * scale_factor * dt
    }

    this.p1.applyForce({
      x: acceleration_vec.x,
      y: acceleration_vec.y
    });
    
    this.p2.applyForce({
      x: -acceleration_vec.x,
      y: -acceleration_vec.y
    });
  }
}

class RepulsionConstraint {
  constructor (p1, p2) {
    this.p1 = p1;
    this.p2 = p2;
  }
  
  apply (dt) {
    let evec = {
      x: this.p1.position.x - this.p2.position.x,
      y: this.p1.position.y - this.p2.position.y
    }

    if (length(evec) < (2 * NODESIZE)){
      // oh no they are overlapping
      // separate without triggering movement
 
      let k = ((2 * NODESIZE) - length(evec)) + 0.01;
      let p = normalize(evec);
      
      let correction = {
        x: p.x * k,
        y: p.y * k
      }    
      
      this.p1.position = {
        x: this.p1.position.x + 0.5 * correction.x,
        y: this.p1.position.y + 0.5 * correction.y
      }
      
      this.p1.oldPosition = {
        x: this.p1.oldPosition.x + 0.5 * correction.x,
        y: this.p1.oldPosition.y + 0.5 * correction.y
      }
      
      this.p2.position = {
        x: this.p2.position.x - 0.5 * correction.x,
        y: this.p2.position.y - 0.5 * correction.y
      }
      
      this.p2.oldPosition = {
        x: this.p2.oldPosition.x - 0.5 * correction.x,
        y: this.p2.oldPosition.y - 0.5 * correction.y
      }
    } else {
      
      let distance_without_radii = length(evec) - (REPULSION_HORIZON * NODESIZE);
            

      let scale_factor = REPULSION / (distance_without_radii * distance_without_radii);
      
      let normalized_evec = normalize(evec);

      let acceleration_vec = {
        x: normalized_evec.x * scale_factor * dt,
        y: normalized_evec.y * scale_factor * dt
      }
      

      this.p1.applyForce({
        x: acceleration_vec.x,
        y: acceleration_vec.y
      });

      this.p2.applyForce({
        x: -acceleration_vec.x,
        y: -acceleration_vec.y
      });
    }
  }
}

/* Fix distance between 2 points */
class DistanceConstraint {
  constructor (p1, p2, stiffness){
    this.p1 = p1;
    this.p2 = p2;
    this.stiffness = stiffness || 0.8;
    this.distance = distance(p1.position, p2.position);
  }

  apply (dt) {
    let evec = {
      x: this.p1.position.x - this.p2.position.x,
      y: this.p1.position.y - this.p2.position.y
    }
    
    let scale_factor = ((this.distance * this.distance) - (length(evec) * length(evec))) / (length(evec) * length(evec));
    let normalized_evec = normalize(evec);
    
    let restitution_vec = {
      x: normalized_evec.x * scale_factor * this.stiffness * dt,
      y: normalized_evec.y * scale_factor * this.stiffness * dt
    }
    
    this.p1.position = {
      x: this.p1.position.x + restitution_vec.x,
      y: this.p1.position.y + restitution_vec.y
    }
    
    this.p2.position = {
      x: this.p2.position.x - restitution_vec.x,
      y: this.p2.position.y - restitution_vec.y
    }  
  }
}

class Node {
  constructor (v, label){
    this.position = v;
    this.oldPosition = {
      x: v.x,
      y: v.y
    }
    this.acceleration = {
      x: 0,
      y: 0
    }
    this.label = label;
  }
    
  update (dt) {
    let temp = { x: this.position.x, y: this.position.y };
      
    let diff = {
      x: (this.position.x - this.oldPosition.x) + (this.acceleration.x * (dt * dt)),
      y: (this.position.y - this.oldPosition.y) + (this.acceleration.y * dt * dt)
    }  
    
    
    let magnitude = length(diff);
    let d = normalize(diff);
    
    let p = {
      x: d.x * Math.min(magnitude, MAX_SPEED),
      y: d.y * Math.min(magnitude, MAX_SPEED)
    }
    
    this.position = { 
      x: this.position.x + p.x,
      y: this.position.y + p.y
    }
      
    this.oldPosition = temp;
    
    let drag = {
      x: DRAG * p.x * -1,
      y: DRAG * p.y * -1
    }

    this.acceleration = drag;
  }

  applyForce (f) {
    this.acceleration = { 
      x: this.acceleration.x + f.x,
      y: this.acceleration.y + f.y
    }
  }
  
  draw (ctx){
    ctx.save();
    ctx.fillStyle = 'rgba(255, 255, 240, 1.0)';
    ctx.beginPath();
    ctx.arc(this.position.x, this.position.y, NODESIZE, 0, 2 * Math.PI);
    ctx.fill();
    ctx.closePath();
    ctx.fillStyle = 'rgba(255, 128, 128, 1.0)';
    ctx.beginPath();
    ctx.arc(this.position.x, this.position.y, NODESIZE - 5, 0, 2 * Math.PI);
    ctx.fill();
    ctx.closePath();
    ctx.restore();
  }
}

class Edge {
  constructor (p1, p2, strength){
    this.p1 = p1;
    this.p2 = p2;
    this.strength = strength || 1.0;
  }
  draw (ctx) {
    ctx.save();    
    ctx.strokeStyle = "rgba(64, 0, 0," + (0.3 + (this.strength/12)) + ")";
    ctx.lineWidth = this.strength;
    ctx.beginPath();
    ctx.moveTo(this.p1.position.x, this.p1.position.y);
    ctx.lineTo(this.p2.position.x, this.p2.position.y);
    ctx.stroke();
    ctx.closePath();
    ctx.restore();
  }
}

let h = canvas.width / 2;
let v = canvas.height / 2;

let nodes, forces, edges;

function makeGraph() {
  nodes = [];
  edges = [];
  forces = [];
  let threshold = 0.8;
  let nodeCount = 5 + Math.floor(15 * Math.random());
  
  for(let i = 0; i < nodeCount; i++){
    let heading = 2 * Math.PI * Math.random();
    let magnitude = (15 + Math.floor(5 * Math.random())) * NODESIZE;
    nodes.push(new Node({x: h + magnitude * Math.cos(heading), y:  v + magnitude * Math.sin(heading)}, "m"));

    for(let j = 0; j < i; j++){
      if(Math.random() > threshold) {
        let s = 0.1 + (3 * Math.random());
        edges.push(new Edge(nodes[j], nodes[i], s));
        forces.push(new AttractionConstraint(nodes[i], nodes[j], s));
      }
    }    
  }  
  
  for(let i = 0; i < nodeCount; i++){
    for(let j = i + 1; j < nodeCount; j++){
      forces.push(new RepulsionConstraint(nodes[i], nodes[j]));
    }
  }
  
}

makeGraph();

document.querySelector('.graph').addEventListener("click", () => {
  makeGraph();
});

  
let render = (dt) => {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  
  // update
  ctx.fillStyle = "rgba(255, 0, 0, 1.0)";
  
  for(let i = 0; i < 16; i++){ 
    shuffle(nodes).map(n => n.update(TIMESTEP));
    shuffle(forces).map(r => r.apply(TIMESTEP));
    // f.apply(TIMESTEP);
  }
  
  if(dragNode){
    dragNode.position = mousePos;
    dragNode.oldPosition = mousePos;
  }
  
  edges.map(e => e.draw(ctx));
  nodes.map(n => n.draw(ctx));
  // f.draw(ctx);
}

/* You can usually ignore stuff below this line*/

// rAF

let start = null;
let loop = (timestamp) => {
  if (!start) start = timestamp;
  let dt = timestamp - start;
  start = timestamp;
  render(dt);
  
  requestAnimationFrame(loop);
}

requestAnimationFrame(loop);

// taken from MDN - canvas resize

(function() {
    var throttle = function(type, name, obj) {
        obj = obj || window;
        var running = false;
        var func = function() {
            if (running) { return; }
            running = true;
             requestAnimationFrame(function() {
                obj.dispatchEvent(new CustomEvent(name));
                running = false;
            });
        };
        obj.addEventListener(type, func);
    };

    /* init - you can init any event */
    throttle("resize", "optimizedResize");
})();

// handle event
window.addEventListener("optimizedResize", () => {
  canvas.width = document.body.clientWidth;
  canvas.height = document.body.clientHeight;
});

window.addEventListener("mousedown", (e) => {
  dragNode = nodes.filter(n => distance(n.position, mousePos) < NODESIZE)[0];
});

window.addEventListener("touchstart", (e) => {
  dragNode = nodes.filter(n => distance(n.position, mousePos) < NODESIZE)[0];
});

window.addEventListener("mouseup", (e) => {
  dragNode = null;
});

window.addEventListener("touchmove", (e) => {
  mousePos = {
    x: e.touches[0].clientX,
    y: e.touches[0].clientY
  }  
});

window.addEventListener("mousemove", (e) => {
  mousePos = {
    x: e.clientX,
    y: e.clientY
  }
});

Comments