Graphology Noverlap

JavaScript implementation of the Noverlap anti-collision layout algorithm for graphology.

Note that this algorithm is iterative and might not converge easily in some cases.

Installation

npm install graphology-layout-noverlap

Usage

• Pre-requisite
• Settings
• Synchronous layout
• Webworker

Pre-requisites

Each node’s starting position must be set before running the Noverlap anti-collision layout. Two attributes called x and y must therefore be defined for all the graph nodes.

Settings

• gridSize ?number 20: number of grid cells horizontally and vertically subdivising the graph’s space. This is used as an optimization scheme. Set it to 1 and you will have O(n²) time complexity, which can sometimes perform better with very few nodes.
• margin ?number 5: margin to keep between nodes.
• expansion ?number 1.1: percentage of current space that nodes could attempt to move outside of.
• ratio ?number 1.0: ratio scaling node sizes.
• speed ?number 3: dampening factor that will slow down node movements to ease the overall process.

Synchronous layout

import noverlap from 'graphology-layout-noverlap';

const positions = noverlap(graph, {maxIterations: 50});

// With settings:
const positions = noverlap(graph, {
  maxIterations: 50,
  settings: {
    ratio: 2
  }
});

// With a custom input reducer
const positions = noverlap(graph, {
  inputReducer: (key, attr) => ({
    x: store[key].x,
    y: store[key].y,
    size: attr.size
  }),
  outputReducer: (key, pos) => ({x: pos.x * 10, y: pos.y * 10})
});

// To directly assign the positions to the nodes:
noverlap.assign(graph);

Arguments

• graph Graph: target graph.
• options object: options:
  • maxIterations ?number 500: maximum number of iterations to perform before stopping. Note that the algorithm will also stop as soon as converged.
  • inputReducer ?function: a function reducing each node attributes. This can be useful if the rendered positions/sizes of your graph are stored outside of the graph’s data. This is the case when using sigma.js for instance.
  • outputReducer ?function: a function reducing node positions as computed by the layout algorithm. This can be useful to map back to a previous coordinates system. This is the case when using sigma.js for instance.
  • settings ?object: the layout’s settings (see #settings).

Webworker

If you need to run the layout’s computation in a web worker, the library comes with a utility to do so:

Example

import NoverlapLayout from 'graphology-layout-noverlap/worker';

const layout = new NoverlapLayout(graph, params);

// To start the layout. It will automatically stop when converged
layout.start();

// To stop the layout
layout.stop();

// To kill the layout and release attached memory
layout.kill();

// Assess whether the layout is currently running
layout.isRunning();