Group layout performance new

transformationsperformancelayoutgroupingvisual-grouping

This example shows how to use node grouping to group nodes and handle the global layout of the graph. Click on Add Nodes and see how Ogma automatically group nodes, computes the layout and animates the changes. Grow button will load more and more nodes into one group, and you will see how it can be done without disturbing the global layout.

index.ts

import Ogma, { ForceLayoutOptions, Item, RawGraph } from '@linkurious/ogma';
import { labelPropagation } from './labelPropagation';
import { cleanup, getPadding, hexToRgba, printInfo, resetTimer } from './utils';
import { NodeData, EdgeData } from './types';
import { colors, duration, easing } from './constants';

import { addGroup } from './addGroup';
import { growGroup } from './growGroup';
import { addNodesToGroups } from './addNodesToGroups';

import './styles.css';
import { state } from './state';

const ogma = new Ogma<NodeData, EdgeData>({
  container: 'graph-container'
});

ogma.styles.addNodeRule({
  color: node => colors[+node.getData('group') % colors.length],
  innerStroke: { width: 0 }
});

ogma.styles.addNodeRule(node => node.isVirtual(), {
  color: (node: Item) => hexToRgba(node.getAttribute('color'), 0.5),
  outline: false
});

ogma.styles.addEdgeRule(e => e.isVirtual(), {
  width: e => e.getSubEdges()!.size,
  stroke: {
    width: 1,
    color: 'rgba(0, 0, 0, 0.2)'
  },
  color: 'white'
});

ogma.styles.setSelectedNodeAttributes({
  outerStroke: {
    color: '#E74C3C'
  },
  outline: false
});

let groupCount = 0;
const grouping = ogma.transformations.addNodeGrouping({
  groupIdFunction: node => node.getData('group'),
  nodeGenerator: (nodes, group) => {
    if (nodes.size === 1) return null;
    return {
      id: `group-${group}`,
      data: {
        group
      }
    };
  },
  showContents: group => {
    if (state.closedGroups.has(group.getId())) return false;
    return true;
  },
  padding: 20,
  duration,
  enabled: false,
  onGroupUpdate: (group, nodes) => {
    return {
      layout: 'force',
      params: { gpu: true }
    };
  }
});

ogma.events.on(['transformationRefresh', 'transformationEnabled'], () => {
  printInfo(ogma);
});

function toggleInputs(on: boolean) {
  [
    ...document.querySelectorAll<HTMLInputElement>('sl-switch,[role="button"]')
  ].forEach(input => (input.disabled = !on));
}

let groups = 0;
ogma.transformations.onGroupsUpdated(topLevel => {
  if (!state.skipNextRelayout) {
    state.skipNextRelayout = false;
    return {
      layout: 'force',
      params: {} as ForceLayoutOptions<NodeData, EdgeData>
    };
  }
  state.skipNextRelayout = false;
});

document
  .getElementById('grouping')!
  .addEventListener('sl-change', async evt => {
    toggleInputs(false);
    await grouping.toggle();
    if (grouping.isEnabled()) return toggleInputs(true);
    resetTimer();
    await ogma.layouts.force({ gpu: true, duration: 200 });
    printInfo(ogma);
    toggleInputs(true);
  });

document.getElementById('add')!.addEventListener('click', async () => {
  toggleInputs(false);
  resetTimer();
  await addGroup(ogma, grouping);
  printInfo(ogma);
  toggleInputs(true);
});

document
  .getElementById('add-nodes-to-group')!
  .addEventListener('click', async evt => {
    toggleInputs(false);
    ogma.clearSelection();
    resetTimer();
    await growGroup(ogma, grouping);
    printInfo(ogma);

    toggleInputs(true);
  });

document.getElementById('add-nodes')!.addEventListener('click', async () => {
  toggleInputs(false);
  resetTimer();
  await addNodesToGroups(ogma, grouping);
  printInfo(ogma);
  toggleInputs(true);
});

document.getElementById('relayout')!.addEventListener('click', async () => {
  toggleInputs(false);
  resetTimer();
  ogma.clearSelection();
  await ogma.layouts.force({ cx: 0, cy: 0 });
  printInfo(ogma);
  toggleInputs(true);
});

document.getElementById('center')?.addEventListener('click', async () => {
  await ogma.view.locateGraph({
    padding: getPadding(),
    duration,
    easing
  });
});

const graph = cleanup(
  await Ogma.parse.jsonFromUrl('files/mathematicians.json')
);

await ogma.setGraph(graph as RawGraph<NodeData, EdgeData>);
// zoom out to prepare for the grouping
await ogma.view.set({ zoom: 0.25 }, { ignoreZoomLimits: true });

// group nodes using label propagation algorithm
const nodeToLabel = await labelPropagation(ogma);

groupCount = new Set(Array.from(nodeToLabel.values())).size; // count unique labels
ogma.getNodes().forEach(node => {
  const label = nodeToLabel.get(node.getId());
  if (label) node.setData('group', label);
  else console.warn(`No label found for node ${node.getId()}`);
});
await grouping.enable();

index.html

<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script src="https://cdn.jsdelivr.net/npm/@linkurious/ogma-ui-kit@0.0.9/dist/ogma-ui-kit.min.js"></script>
  </head>

  <body>
    <div id="info" class="panel">
      <table>
        <thead>
          <tr>
            <td><span class="icon-circle-small"></span>Nodes</td>
            <td><span class="icon-minus"></span>Edges</td>
            <td><span class="icon-bubbles"></span>Groups</td>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td id="nodes-count">0</td>
            <td id="edges-count">0</td>
            <td id="groups-count">0</td>
          </tr>
        </tbody>
      </table>
    </div>
    <div id="graph-container"></div>
    <div class="panel" id="actions">
      <div class="title"><span class="icon-timer"></span> Time</div>
      <div class="row" id="time">0ms</div>
      <sl-divider></sl-divider>
      <div class="title">GROUPING</div>
      <span class="row">
        Grouping
        <sl-switch checked id="grouping"></sl-switch>
      </span>
      <sl-divider></sl-divider>
      <div class="title">LAYOUT</div>
      <sl-button variant="secondary" id="add" role="button">
        <sl-icon library="lucide" slot="prefix" name="circle-plus"></sl-icon>
        Add Group</sl-button
      >

      <sl-button variant="secondary" id="add-nodes" role="button">
        <sl-icon library="lucide" slot="prefix" name="circle-plus"></sl-icon>
        Add nodes to groups</sl-button
      >

      <sl-button variant="secondary" id="add-nodes-to-group" role="button">
        <sl-icon library="lucide" slot="prefix" name="circle-plus"></sl-icon>
        Grow one group</sl-button
      >

      <sl-button variant="primary" id="relayout" role="button">
        <sl-icon library="lucide" slot="prefix" name="rotate-ccw"></sl-icon>
        Relayout</sl-button
      >

      <div class="size"></div>
    </div>
    <button id="center">
      <span class="icon-scan"></span>
    </button>
    <script type="module" src="index.ts"></script>
  </body>
</html>

styles.css

:root {
  --info-icon-size: 16px;
}
html,
body {
  overflow: hidden;
}
#graph-container {
  position: absolute;
  top: 0;
  left: 0;
  bottom: 0;
  right: 0;
}

#info {
  position: absolute;
  top: 30px;
  left: 50%;
  transform: translateX(-50%);
  z-index: 10;
  display: flex;
  flex-direction: column;
  align-items: center;
  width: unset;
}

#info thead td {
  font-weight: 600;
  color: #606060;
  font-size: var(--info-icon-size);
  min-width: 80px;
  line-height: 1em;
  text-align: left;
  margin-right: 40px;
}

#info td:not(:last-child),
#info th:not(:last-child) {
  padding-right: 40px;
}

#info thead td [class^='icon-'] {
  vertical-align: bottom;
  margin-right: 4px;
}

#center {
  position: absolute;
  bottom: 40px;
  right: 40px;
  outline: none;
  border: none;
  z-index: 10;
  background: #fff;
  padding: 8px 8px 6px 8px;
  line-height: 16px;
  border-radius: 8px;
  font-size: 16px;
  box-shadow: 0 1px 4px #00000146;
  cursor: pointer;
}

#center:hover {
  box-shadow: 0 1px 6px #00000146;
}

.title {
  font-weight: 500;
}

#time {
  font-size: 24px;
}

addGroup.ts

import Ogma, { NodeGrouping } from '@linkurious/ogma';
import { NodeData } from './types';
import { easing, duration } from './constants';
import { getPadding, offsetIds } from './utils';
import { state } from './state';

export async function addGroup(
  ogma: Ogma<NodeData>,
  grouping: NodeGrouping<NodeData, unknown>
) {
  const graph = await ogma.generate.random({ nodes: 20, edges: 10 });
  const groupCount = ogma.getNodes().filter(node => !node.isVirtual()).size + 1; // count existing groups

  const nodeIdOffset = ogma.getNodes().size + 1;
  offsetIds(graph, nodeIdOffset);
  const groupId = Math.floor(Math.random() * groupCount);
  graph.nodes.forEach(node => {
    node.data = { group: `${groupId}` };
    node.attributes = ogma.getNodes().getBoundingBox().center();
  });
  const t = 3 + Math.floor(Math.random() * 10);
  for (let i = 0; i < t; i++) {
    const randomNode = ogma
      .getNodes()
      .get(Math.floor(Math.random() * ogma.getNodes().size))!;
    graph.edges.push({
      source: graph.nodes[Math.floor(Math.random() * graph.nodes.length)].id!,
      target: randomNode.getId()
    });
  }

  graph.edges.forEach(edge => delete edge.id);
  await ogma.addGraph(graph);

  if (grouping.isEnabled()) {
    await ogma.transformations.afterNextUpdate();
    await ogma.view.afterNextFrame();
    ogma.clearSelection();
    const toSelect = ogma
      .getNodes()
      .filter(node => node.isVirtual() && +node.getData('group') === groupId);
    await toSelect.setSelected(true);
    ogma.view.moveToBounds(toSelect.getBoundingBox(), {
      easing,
      duration
    });
  } else {
    ogma.view.moveToBounds(
      ogma
        .getNodes(graph.nodes.map(n => n.id!))
        .getBoundingBox()
        .pad(100),
      { easing, duration }
    );
  }
}

addNodesToGroups.ts

import Ogma, { NodeGrouping } from '@linkurious/ogma';
import { duration, easing } from './constants';
import { offsetIds, resetTimer } from './utils';
import { EdgeData, NodeData } from './types';

export async function addNodesToGroups(
  ogma: Ogma<NodeData, EdgeData>,
  grouping: NodeGrouping<NodeData, EdgeData>
) {
  ogma.clearSelection();
  const graph = await ogma.generate.random({ nodes: 120, edges: 110 });
  const nodeIdOffset = ogma.getNodes().size + 1;
  offsetIds(graph, nodeIdOffset);
  const affectedGroups = new Set<string>();

  // assign nodes to random groups
  graph.nodes.forEach(node => {
    const groupId = +node.id! % 3;
    node.data = { group: `${groupId}` };
    affectedGroups.add(`${groupId}`);
  });
  resetTimer();
  await ogma.addGraph(graph);

  if (grouping.isEnabled()) {
    await ogma.transformations.afterNextUpdate();

    const toSelect = ogma.getNodes(
      Array.from(affectedGroups).map(g => `group-${g}`)
    );
    ogma.clearSelection();
    await toSelect.setSelected(true);

    ogma.view.moveToBounds(toSelect.getBoundingBox(), { easing, duration });
  } else {
    const toSelect = ogma.getNodes(graph.nodes.map(n => n.id!));
    toSelect.setSelected(true);

    ogma.view.moveToBounds(toSelect.getBoundingBox().pad(100), {
      easing,
      duration
    });
  }
  //toSelect.locate({ duration, easing, padding: getPadding() });
}

constants.ts

export const duration = 300; // Duration for animations in milliseconds
export const easing = 'quadraticOut'; // Easing function for animations
export const colors = [
  '#FF5733',
  '#33FF57',
  '#3357FF',
  '#F1C40F',
  '#8E44AD',
  '#E74C3C',
  '#2ECC71',
  '#3498DB',
  '#9B59B6',
  '#F39C12'
];

growGroup.ts

import Ogma, { NodeGrouping } from '@linkurious/ogma';
import { NodeData } from './types';
import { offsetIds } from './utils';
import { easing, duration } from './constants';
import { state } from './state';

export async function growGroup(
  ogma: Ogma<NodeData>,
  grouping: NodeGrouping<NodeData, unknown>
) {
  const biggestGroup = getRandomGroup(ogma);
  const subgraph = offsetIds(
    await ogma.generate.random({
      nodes: 50,
      edges: 50
    }),
    ogma.getNodes().size + 1
  );

  const position = grouping.isEnabled()
    ? ogma.getNode(`group-${biggestGroup}`)!.getPosition()
    : { x: 0, y: 0 };

  subgraph.nodes.forEach(node => {
    node.data = { group: biggestGroup };
    node.attributes = position;
  });

  let radiusBefore = 0;
  if (grouping.isEnabled()) {
    const focusNode = ogma.getNode(`group-${biggestGroup}`)!;
    radiusBefore = +focusNode.getAttribute('radius');
  }

  await ogma.addGraph(subgraph);
  state.skipNextRelayout = true; // skip relayout to avoid flickering

  if (grouping.isEnabled()) {
    const focusNode = ogma.getNode(`group-${biggestGroup}`)!;
    await ogma.transformations.afterNextUpdate();
    await ogma.algorithms.fishEyeExpand({
      focusNode,
      nodes: ogma.getNodes().filter(n => n.isVirtual() || !n.getMetaNode()),
      deltaRadius: Number(focusNode.getAttribute('radius')) - radiusBefore + 20,
      duration
    });
  }

  if (
    !ogma
      .getNodes(subgraph.nodes.map(n => n.id!))
      .every(node => node.isInView({ margin: 150 }))
  )
    ogma.view.moveToBounds(
      ogma
        .getNodes(subgraph.nodes.map(n => n.id!))
        .getBoundingBox()
        .pad(150),
      { duration, easing }
    );
}

function getRandomGroup(ogma: Ogma<NodeData>) {
  const groupNodes = ogma.getNodes().filter(n => n.isVirtual());
  if (groupNodes.size === 0) return '0'; // no groups available, return default group
  return groupNodes.get(0).getData('group');
}

labelPropagation.ts

import Ogma, { NodeId } from '@linkurious/ogma';

export async function labelPropagation(ogma: Ogma, maxIterations = 20) {
  const nodes = ogma.getNodes().filter(node => !node.isVirtual());
  const labels = new Map();

  // Step 1: Initialize each node's label with its own ID
  nodes.forEach(node => labels.set(node.getId(), node.getId().toString()));

  // Step 2: Iterate label updates
  for (let i = 0; i < maxIterations; i++) {
    let changed = false;

    for (const node of nodes) {
      const neighbors = node.getAdjacentNodes();
      const neighborLabels = neighbors.map(n => labels.get(n.getId()));

      if (neighborLabels.length === 0) continue;

      // Count label frequencies
      const counts: Record<NodeId, number> = {};
      for (const label of neighborLabels) {
        counts[label] = (counts[label] || 0) + 1;
      }

      // Choose most frequent label
      const mostCommonLabel = Object.entries(counts).sort(
        (a, b) => b[1] - a[1]
      )[0][0];

      // Update label if it changed
      const nodeId = node.getId();
      if (labels.get(nodeId) !== mostCommonLabel) {
        labels.set(nodeId, mostCommonLabel);
        changed = true;
      }
    }

    if (!changed) break; // Stop if no label changed this round
  }

  return labels;
}

state.ts

import { NodeId } from '@linkurious/ogma';

export const state = {
  closedGroups: new Set<NodeId>(),
  skipNextRelayout: false
};

types.ts

export interface NodeData {
  group: string;
}

utils.ts

import Ogma, { Item, NodeId, RawGraph } from '@linkurious/ogma';
import chroma from 'chroma-js';
import { EdgeData, NodeData } from './types';

export function offsetIds(
  graph: RawGraph<NodeData>,
  offset: number
): RawGraph<NodeData> {
  graph.nodes.forEach(node => {
    //node.data = { group: `${Math.ceil(Math.random() * groupCount)}` };
    (node.id as number) += offset;
  });
  graph.edges.forEach(edge => {
    delete edge.id; // remove id to avoid conflicts
    (edge.source as number) += offset;
    (edge.target as number) += offset;
  });
  return graph;
}

export function cleanup(graph: RawGraph<NodeData>) {
  const idTable = new Map<NodeId, NodeId>();
  graph.nodes.forEach((n, i) => {
    idTable.set(n.id!, i);
    n.id = i; // reset id to avoid conflicts
    delete n.attributes?.color;
  });
  graph.edges.forEach(e => {
    e.source = idTable.get(e.source)!;
    e.target = idTable.get(e.target)!;
    delete e.id; // remove id to avoid conflicts
    delete e.attributes;
  });
  return graph;
}

export const formatRGBA = (color: [number, number, number, number]) =>
  `rgba(${color.join(', ')})`;

export const hexToRgba = (hex: string, tint: number) =>
  formatRGBA(chroma(hex).tint(tint).rgba());

export const nonVirtual = (item: Item) => !item.isVirtual();

let start = Date.now();

export function resetTimer() {
  start = Date.now();
}

export function printInfo(ogma: Ogma<NodeData, EdgeData>) {
  const nodes = ogma.getNodes().filter(nonVirtual);
  const edges = ogma.getEdges().filter(nonVirtual);
  const groups = ogma.getNodes().filter(n => n.isVirtual());
  let elapsed = Date.now() - start;

  document.getElementById('nodes-count')!.innerText = `${nodes.size}`;
  document.getElementById('edges-count')!.innerText = `${edges.size}`;
  document.getElementById('groups-count')!.innerText = `${groups.size}`;
  document.getElementById('time')!.innerText = `${elapsed}ms`;
}

function getLeftOffset() {
  const container = document.getElementById('actions')!;
  const rect = container.getBoundingClientRect();
  return rect.left + rect.width + 20; // 20px padding
}

export function getPadding() {
  return { top: 120, left: getLeftOffset(), right: 120, bottom: 120 };
}