This package implements high dimensional graph layout with O(m*(|V| + |E|)) time complexity.
While the layout doesn't necessary look appealing for all possible graphs, this package
provides amazing initial configuration for nodes for subsequent refinement by ngraph.forcelayout
or d3-force.
Since force based layout convergence speed depends on initial configuration, this library can provide significant boost for large graphs layout.
See the demo here: https://anvaka.github.io/ngraph.hde/
Demo's source code is here
The package follows Graph Drawing by High-Dimensional Embedding paper by David Harel and Yehuda Koren.
First, the graph is projected into M-dimensional space. In this space adjacent nodes are
close to each other. By default M has 50 dimensions.
Then from this M dimensional space we crash graph back into 2D or 3D, or any other D < M where you want
to visualize the graph. The "crash" is done by PCA. In this D-dimensional space we can visualize the graph,
or use it as starting position for a force based layout.
npm install ngraph.hde
Then, using your favorite bundler:
let createLayout = require('ngraph.hde');
let createGraph = require('ngraph.graph');
let graph = createGraph(); // your graph.
graph.addLink(1, 2);
graph.addLink(2, 3);
graph.addLink(1, 3);
// set up nodes/vertices and then:
let layout = createLayout(graph);
layout.getNodePosition(1); // returns [0.39, -0.72]Current version of the library doesn't support graphs with multiple disconnected components. You'd have to first find the connected components and then use layout on connected parts.
Layout supports a few options:
let layout = createLayout(graph, {
// Defines number of dimensions in `M` space. If value is larger than number
// of nodes, then number of nodes is used by default.
pivotCount: 50,
// Defines number of components for `getNodePosition()` method. This is number of
// principal component in the PCA.
dimensions: 2
});You can always reach out to me on twitter if you have any questions. If you love this library, please consider sponsoring it https://github.com/sponsors/anvaka .
MIT