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.

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;
}

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 };
}

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

import Alea from 'alea';
const prng = new Alea(42);

export const random = () => prng.next();

Group layout performance new ​

Group layout performance new