Appearance
Group layout performance new
This example shows how you can match the patterns in the groups and optimize the overall layout time by skipping unnecessary work: star-shaped subgraphs or the disconnected nodes.
ts
import Ogma, { RawGraph, NodeList } from '@linkurious/ogma';
import chroma from 'chroma-js';
import { layout } from './layout';
import { GUI } from 'dat.gui';
import { generate } from './generate';
import { random } from './randomize';
const ogma = new Ogma({
container: 'graph-container'
});
const settings = {
optimize: true
};
const colorScale = chroma
.scale('RdBu' /*['#0fa3b1', '#f7a072']*/)
.domain([0, 100]);
ogma.styles.addRule({
nodeAttributes: {
color: node => {
const group = node.getData('group');
if (node.isVirtual()) {
const [r, g, b] = colorScale(group).rgb();
return `rgb(${r},${g},${b}, 0.3)`;
}
return colorScale(group);
},
opacity: node => (node.isVirtual() ? 0.3 : 1),
innerStroke: {
width: 0
}
}
});
let layoutTime = 0;
let start = Date.now();
await ogma.addGraph(generate());
async function groupNodes() {
start = Date.now();
let groupCounter = 0;
const transformation = ogma.transformations.addNodeGrouping({
groupIdFunction(node) {
return node.getData('group');
},
nodeGenerator(nodes, groupId) {
groupCounter++;
return { data: { group: groupId } };
},
onGroupUpdate: (group, nodes) => {
return (
settings.optimize ? layout(ogma, nodes) : ogma.layouts.force({ nodes })
).then(g => {
if (--groupCounter === 0) layoutTime = Date.now() - start;
return g;
});
},
showContents: true,
padding: 10
});
await transformation.whenApplied();
await layoutMetaGraph();
logTime(layoutTime);
}
function logTime(time: number) {
const container = document.getElementById('output')!;
container.innerHTML = `Global sublayouts time: ${time}ms`;
}
async function layoutMetaGraph() {
await ogma.layouts.force({
locate: true,
nodeMass: n => {
if (n.isVirtual()) {
return Math.max(
1,
n.getSubNodes()!.getAdjacentEdges({ bothExtremities: true }).size
);
}
return 1;
},
gravity: 0.01
});
}
await groupNodes();
const gui = new GUI();
gui
.add(settings, 'optimize')
.name('Optimize layout')
.onChange(async () => {
const groups = ogma.getNodes().filter(n => n.isVirtual());
ogma.transformations.triggerGroupUpdated(groups);
start = Date.now();
ogma.transformations.getList().forEach(t => t.refresh());
await ogma.transformations.afterNextUpdate();
await layoutMetaGraph();
logTime(layoutTime);
});
html
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<link rel="preconnect" href="https://fonts.googleapis.com" />
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin />
<link
href="https://fonts.googleapis.com/css2?family=IBM+Plex+Sans:ital,wght@0,100;0,200;0,300;0,400;0,500;0,600;0,700;1,100;1,200;1,300;1,400;1,500;1,600;1,700&display=swap"
rel="stylesheet"
/>
<link type="text/css" rel="stylesheet" href="styles.css" />
</head>
<body>
<div id="graph-container"></div>
<div id="output"></div>
<script src="index.ts"></script>
</body>
</html>
css
:root {
--base-font-family: 'IBM Plex Sans', Arial, Helvetica, sans-serif;
font-family: var(--base-font-family);
}
#graph-container {
top: 0;
bottom: 0;
left: 0;
right: 0;
position: absolute;
margin: 0;
overflow: hidden;
}
#output {
z-index: 9999;
top: 0;
left: 50%;
position: absolute;
padding: 1em;
margin-left: -5em;
font-size: 1.2em;
text-shadow:
-1px -1px 0 white,
1px -1px 0 white,
-1px 1px 0 white,
1px 1px 0 white;
}
ts
import { RawEdge, RawGraph, RawNode } from '@linkurious/ogma';
import { random } from './randomize';
function generateStar(n: number, group: number, startId: number): RawGraph {
const nodes = Array.from({ length: n }, (_, i) => ({
id: startId + i,
data: { group }
}));
const edges = nodes.slice(1).map(node => ({
source: startId,
target: node.id
}));
return { nodes, edges };
}
export function generate(): RawGraph<{ group: number }> {
let groupCounter = 0;
const nodes: RawNode[] = [];
const edges: RawEdge[] = [];
// add singleton groups
for (let i = 0; i < 50; i++) {
const idOffset = nodes.length;
const group = groupCounter++;
nodes.push(
...Array.from({ length: group }, (_, i) => ({
id: idOffset + i,
data: { group }
}))
);
}
// add stars
for (let i = 0; i < 130; i++) {
let group = groupCounter++;
const star = generateStar(5 * Math.log(group * i), group, nodes.length);
nodes.push(...star.nodes);
edges.push(...star.edges);
}
// random subgraphs
for (let i = 0; i < 25; i++) {
groupCounter++;
const N = Math.floor(Math.max(10, random() * 50));
const E = Math.floor(Math.max(10, random() * 100));
const idOffset = nodes.length;
for (let j = 0; j < N; j++) {
nodes.push({
id: idOffset + j,
data: { group: groupCounter }
});
}
for (let j = 0; j < E; j++) {
edges.push({
source: idOffset + Math.floor(random() * N),
target: idOffset + Math.floor(random() * N)
});
}
}
console.log('Generated', 'nodes and', edges.length, 'edges');
return { nodes, edges };
}
ts
import Ogma, { NodeList, PixelSize, Point } from '@linkurious/ogma';
function isStar(ogma: Ogma, nodes: NodeList) {
let i = 0;
for (const node of nodes) {
const adjacent = node.getAdjacentNodes();
const isStar =
node.getDegree() > 2 && adjacent.getDegree().every(d => d === 1);
if (isStar && adjacent.size + 1 === nodes.size) return i;
i++;
}
return -1;
}
interface CircularLayoutOptions {
radii: PixelSize[] | number[];
cx?: number;
cy?: number;
startAngle?: number;
clockwise?: boolean;
getRadius?: (radius: PixelSize) => number;
distanceRatio?: number;
}
function runCircularLayout({
radii,
clockwise = true,
cx = 0,
cy = 0,
startAngle = (3 / 2) * Math.PI,
getRadius = (radius: PixelSize) => Number(radius),
distanceRatio = 0.0
}: CircularLayoutOptions): Point[] {
const N = radii.length;
// dummy checks
if (N === 0) return [];
if (N === 1) return [{ x: cx, y: cy }];
// minDistance
const minDistance =
radii.map(getRadius).reduce((acc, r) => Math.max(acc, r), 0) *
(2 + distanceRatio);
const sweep = 2 * Math.PI - (2 * Math.PI) / N;
const deltaAngle = sweep / Math.max(1, N - 1);
const dcos = Math.cos(deltaAngle) - Math.cos(0);
const dsin = Math.sin(deltaAngle) - Math.sin(0);
const rMin = Math.sqrt(
(minDistance * minDistance) / (dcos * dcos + dsin * dsin)
);
const r = Math.max(rMin, 0);
return radii.map((_, i) => {
const angle = startAngle + i * deltaAngle * (clockwise ? 1 : -1);
const rx = r * Math.cos(angle);
const ry = r * Math.sin(angle);
return {
x: cx + rx,
y: cy + ry
};
});
}
export async function layout(ogma: Ogma, nodes: NodeList) {
if (nodes.size === 0) return;
if (nodes.size === 2) {
const [r1, r2] = nodes.getAttribute('radius') as number[];
return Promise.resolve([
{ x: 0, y: 0 },
{ x: r1 + r2 + 5, y: 0 }
]);
}
const edges = nodes.getAdjacentEdges({ bothExtremities: true });
if (edges.size === 0)
return ogma.algorithms.circlePack({
nodes,
margin: Math.min(...(nodes.getAttribute('radius') as number[]))
});
const centerIndex = isStar(ogma, nodes);
if (centerIndex !== -1) {
const satellites = nodes.filter((n, i) => i !== centerIndex);
const center = nodes.get(centerIndex);
const pos = center.getPosition();
const positions = runCircularLayout({
radii: satellites.getAttribute('radius'),
cx: pos.x,
cy: pos.y,
clockwise: false,
distanceRatio: 1.5
});
positions.splice(centerIndex, 0, pos);
return positions;
} else return ogma.layouts.force({ nodes });
}
ts
import Alea from 'alea';
const prng = new Alea(42);
export const random = () => prng.next();