Skip to content
  1. Examples

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();