Appearance

  2. Examples

GPU layout new ​

performancebig-graphsforce-layoutgpulayout

This example shows the differences between the GPU and CPU mode of the force layout. The GPU mode is much faster and provides better final layout quality.

ts
import Ogma, { Options, ForceLayoutOptions, RawGraph } from '@linkurious/ogma';
import { filterParallelEdges, loadZip, startTimer, stopTimer } from './utils';
import { applyStyles } from './colors';
import { optionsForDataset } from './options';

// Prepare two Ogma instances, one for the CPU and one for the GPU
const ogmaLeft = new Ogma({
  container: 'container-cpu',
  options: {
    backgroundColor: '#e6f1ff',
    interactions: { drag: { enabled: false } }
  }
});
const ogmaRight = new Ogma({
  container: 'container-gpu',
  options: {
    backgroundColor: '#fefefe',
    interactions: { drag: { enabled: false } }
  }
});
applyStyles(ogmaLeft);
applyStyles(ogmaRight);

const stopButton =
  document.querySelector<HTMLSpanElement>('.left .stop-layout')!;
stopButton.addEventListener('click', () => {
  ogmaLeft.layouts.stop();
  stopTimer('cpu');
});

// Disable text hover, and text overlap detection for this example
const options: Options = { texts: { preventOverlap: false } };
ogmaLeft.setOptions(options);
ogmaRight.setOptions(options);

const spinner = document.querySelector<HTMLDivElement>('#spinner')!;
const setSpinner = (on: boolean) => {
  spinner.style.display = on ? 'block' : 'none';
};

function loadFile(dataset: string) {
  let parse = dataset.endsWith('.mtx')
    ? Ogma.parse.mtxFromUrl
    : Ogma.parse.jsonFromUrl;
  if (dataset.endsWith('.gz')) {
    parse = (zip: string) =>
      loadZip(zip).then((str: string) =>
        dataset.replace('.gz', '').endsWith('.mtx')
          ? Ogma.parse.mtx(str)
          : Ogma.parse.json(str)
      );
  }
  return parse(dataset);
}

function addNewGraph(ogma: Ogma, graph: RawGraph) {
  graph.edges = filterParallelEdges(graph.edges);
  graph.nodes.forEach(
    node => (node.attributes = { x: Math.random(), y: Math.random() })
  );
  // this is an important trick to reduce the memory pressure
  // which can lead to fatal crashes on older hardware
  const batchSize = graph.nodes.length < 1e4 ? 1e3 : 5e3;
  return ogma.setGraph(graph, { batchSize });
}

// Actual function comparing the CPU and GPU force layout algorithms
async function comparison(dataset: string) {
  setSpinner(true);
  const graph = await loadFile(dataset);
  graph.edges = filterParallelEdges(graph.edges);
  graph.nodes.forEach(node => (node.attributes = {}));
  await Promise.all([
    addNewGraph(ogmaLeft, graph),
    addNewGraph(ogmaRight, graph)
  ]);
  startTimer('gpu');
  await ogmaRight.layouts.force({ ...optionsForDataset[dataset], gpu: true });
  stopTimer('gpu');
  startTimer('cpu');
  await ogmaLeft.layouts.force(optionsForDataset[dataset]);
  stopTimer('cpu');
  stopTimer();
  setSpinner(false);
}

const datasetSelect =
  document.querySelector<HTMLSelectElement>('#dataset-select')!;
const onChange = async () => {
  datasetSelect.setAttribute('disabled', 'disabled');
  await comparison(datasetSelect.value);
  datasetSelect.removeAttribute('disabled');
};
datasetSelect.addEventListener('change', onChange);
onChange();
html
<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script src="https://cdn.jsdelivr.net/npm/fflate@0.8.0/umd/index.min.js"></script>
    <script src="https://cdn.jsdelivr.net/npm/alea"></script>
    <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="container-cpu" class="graph-container left">
      <span class="controls">
        <span class="stop-layout" title="Stop">
          <svg
            xmlns="http://www.w3.org/2000/svg"
            width="1.5em"
            height="1.5em"
            style="color: currentColor"
            viewBox="0 0 24 24"
          >
            <path
              fill="currentColor"
              d="M12 21a9 9 0 1 1 0-18 9 9 0 0 1 0 18Zm0-16.5a7.5 7.5 0 1 0 0 15 7.5 7.5 0 0 0 0-15Z"
            />
            <path
              fill="currentColor"
              d="M14.5 8h-5C8.67 8 8 8.67 8 9.5v5c0 .83.67 1.5 1.5 1.5h5c.83 0 1.5-.67 1.5-1.5v-5c0-.83-.67-1.5-1.5-1.5Z"
            /></svg
        ></span>
        <span class="stats">CPU</span>
      </span>
    </div>
    <div id="container-gpu" class="graph-container right">
      <span class="controls">
        <span class="stats">GPU</span>
      </span>
    </div>
    <div class="spinner" id="spinner"></div>
    <div id="dataset">
      <select id="dataset-select">
        <option value="files/paris-software.json">
          3689 nodes, 3762 edges
        </option>
        <option value="files/relativity.json">5242 nodes, 14496 edges</option>
        <option value="files/oregon.json">10981 nodes, 30855 edges</option>
        <option value="files/silk-road.json">26112 nodes, 90514 edges</option>
        <option value="files/small-clusters.mtx.gz">
          32460 nodes, 147788 edges
        </option>
        <option value="files/circuit_4.mtx.gz">
          80209 nodes, 307604 edges
        </option>
        <option value="files/hcircuit.mtx.gz">
          105767 nodes, 309362 edges
        </option>
      </select>
    </div>

    <div>
      <input type="radio" id="gpu" name="gpu" value="gpu" checked />
      <label for="gpu">GPU</label>
    </div>
    <script type="module" src="index.ts"></script>
  </body>
</html>
css
html,
body {
  font-family: 'IBM Plex Sans', Arial, sans-serif;
}
.graph-container {
  top: 0;
  bottom: 0;
  left: 0;
  right: 0;
  width: 50%;
  position: absolute;
  margin: 0;
  overflow: hidden;
  display: flex;
  justify-content: center;
}
.graph-container .controls {
  position: absolute;
  font-size: 2em;
  background-color: white;
  padding: 0.1em;
}
.graph-container .stop-layout {
  padding: 0.1em;
  left: 2em;
  cursor: pointer;
  color: #042b53;
  vertical-align: middle;
  display: none;
}

.info {
  position: absolute;
  color: #fff;
  background: #141229;
  font-size: 12px;
  font-family: monospace;
  padding: 5px;
}
.left {
  left: 0;
}
.right {
  left: 50%;
}

.ratio {
  margin-left: 0.5em;
  background: #1098f7;
  border-radius: 0.25em;
  padding: 0.25em;
  color: #fff;
}

#dataset {
  bottom: 30px;
  left: 50%;
  position: absolute;
}

#dataset > select {
  margin-left: -50%;
  font-size: 1.25em;
}

.loading,
.spinner {
  pointer-events: none;
  background-position: 50% 50%;
  background-repeat: no-repeat;
  background-image: url('data:image/gif;base64,R0lGODlhIAAgAPMLAAQEBMbGxoSEhLa2tpqamjY2NlZWVtjY2OTk5Ly8vB4eHv///wAAAAAAAAAAAAAAACH/C05FVFNDQVBFMi4wAwEAAAAh+QQFCgALACwAAAAAIAAgAEAE5nDJSSkBpOo6SsmToSiChgwTkgzsIQlwDG/0wt5Dgkjn4E6Blo0lue1qlZECJQE4JysfckLwMKeLH/YgxEZzx1o0fKMEr9NBieIEmInYSWG0bhdZYZrB4zFokTg6cYNDgXmEFX8aZywJU1wpX4oVUT9lEpWECIorjohTCgAKiYc1CCMGbE88jYQCIwUTdlmtiANKO3ZcAwEUu2FVfUwBCiA1jLwaA3t8cbuTJmufFQEEMjOEODcJ1dfS04+Dz6ZfnljIvRO7YBMDpbvpEgcrpRQ9TJe75s61hSmXcVjE8+erniZBcSIAACH5BAUKAAsALAAAAAAYABcAAARycMlJqxo161lUqQKxiZRiUgUAaMVXnhKhKmybTCYtKaqgES0DDiaYbRaGFim3OKgApE3LxTSoXE2B4IbCUmSBSUKrPUgOBcyRMiCHEOvNwe2Lb8aCsP2o3vvjCAkDg4R/C4KEhX+BiYOGj5CRkpNHensRACH5BAUKAAsALAEAAAAdAA4AAARycMlJ5yg1671MMdnATUdSFShlKMooCYI4oZg0sPUIC8ecSgWWS5LY+XK4oYQAMy1oCwRLIZsgNgfjMyVggSYCAICAGCR6E2ZM01oqxADeYJ64RgWBUaAAB9QCc3N5Sn1UFAgJgU4uYXFYc2hDBpFYShwRACH5BAUKAAsALAcAAAAZABEAAARpcMm5ggg0600Eyd+2IEcmnFlRiMOATadAqeLSDgiMSoYaaodWQidbEFSG2iLRKi1iEtVKibhJoAtaRqEYUAJNzaDgHHMVYmfNcFYklZv2lOKFG7l2uCCX7/s1AIGCCj99gocAfwuIAIQRACH5BAUKAAsALA4AAAASABgAAARl8JCzqr14ELwS5QshXoQggOFYHeYJilvVJihcJS2axu33jgNTrEIoFFABAcJiMBaGIIrzqKtMDbSq9anter8VhXhM1Y3PiipaURiAvQJfVwAAuLr1ugKKLOQBZVUECnl3WnQAbhEAIfkEBQoACwAsDgAAABIAHgAABIAQJbSqvTiNhAO+QwgSxFeFw0WmJmoNpNeKS0CW5uIud36KNgKrkhAIDqbD8GA0cnwIQlOA802PPkvAmcUMu+BsYUw2fD/kdEGsNoTfFsqboFDA6/XCOWnAK9wmAgAyAwV4JgYAAGsXhiYIigBVXYIAdm8KigJvA5FwBYpyYVQmEQAh+QQFCgALACwPAAEAEQAfAAAEe3DJuQ6iGIcxskdc4mUJd4zUEaIUN1xsxQUpB1P3gpQmu7k0lGuQyHlUg1NMolw6PYKolBCESq+oa5T67DoHhQLBGQ4bnuXCiKCgGMpjikChOE/G6gVgL6ErOh57ABN0eRmCEwV0I4iEi4d8EwaPGI0tHgoAbU4EAHFLEQAh+QQFCgALACwIAA4AGAASAAAEbHDJSesaOCdk+8xg4nkgto1oig4qGgiC2FpwfcwUQtQCMQ+F2+LAky0CAEGnUKgkYMJFAQAwLBRYCbM5IlABHKxCQmBaPQqq8pqVGJg+GnUsEVO2nTQgzqZPmB1UXHVtE3wVOxUFCoM4H34qEQAh+QQFCgALACwCABIAHQAOAAAEeHDJSatd59JjtD3DkF0CAAgelYRDglCDYpopFbBDIBUzUOiegOC1QKxCh5JJQZAcmJaBQNCcHFYIggk1MSgUqIJYMhWMLMRJ7LsbLxLl2qTAbhcmhGlCvvje7VZxNXQKA3NuEnlcKV8dh38TCWcehhUGBY58cpA1EQAh+QQFCgALACwAAA8AGQARAAAEZ5AoQOu6OOtbO9hgJnlfaJ7oiQgpqihECxbvK2dGrRjoMWy1wu8i3PgGgczApikULoLoZUBFoJzPRZS1OCZOBmdMK70kqIcQwcmDlhcI6nCWdXMvAWrIqdlqDlZqGgQCYzcaAQJJGxEAIfkEBQoACwAsAQAIABEAGAAABFxwACCWvfiKCRTJ4FJwQBGEGKGQaLZRbXZUcW3feK7vKFEUtoTh96sRgYeW72e4IAQn0O9zIQgEg8Vgi5pdLdts6CpIgLmgBPkSHl+TZ7ELi2mDDnJLYmC+IRIIEQAh+QQFCgALACwAAAIADgAdAAAEcnDJuYigeAJQMt7A4E3CpoyTsl0oAR5pRxWbkSpKIS4BwEoGHM4A8wwKwhNqgSMsF4jncmAoWK+Zq1ZGoW650vAOlRAIAqODee2xrAlRTNlMQEsG8YVakKAEBgNFHgiAYx4JgIIZB4B9ZIB5RgN2KAiKEQA7');
}

.spinner {
  z-index: 1000;
  top: 50%;
  left: 50%;
  position: absolute;
  width: 40px;
  height: 40px;
  background-color: #fff;
  border-radius: 10px;
  margin-left: -20px;
  margin-top: -20px;
  display: none;
}

.controls svg {
  width: 1em;
  height: 1em;
  margin: 0 0.25em;
  cursor: pointer;
  display: inline-block;
  text-align: right;
}
ts
import Ogma from '@linkurious/ogma';

// Missing types for `alea` package
declare class Alea {
  constructor(seed: number);
  next(): number;
}

const seed = new Date().getFullYear();
const colors = ['#FFBE0B', '#FB5607', '#FF006E', '#8338EC', '#3A86FF'];

// We need to use a seeded PRNG to get the same colors for both visualizations
export const generator =
  (prng = new Alea(seed)) =>
  () =>
    colors[Math.floor(prng.next() * colors.length)];

export const applyStyles = (ogma: Ogma) =>
  ogma.styles.addRule({
    nodeAttributes: {
      color: '#042B53',
      innerStroke: {
        width: 0
      },
      radius: 12.5
    },
    edgeAttributes: {
      color: '#ccc'
    }
  });
ts
import { ForceLayoutOptions } from '@linkurious/ogma';

export const defaultOptions: ForceLayoutOptions = {
  steps: 200,
  charge: 10,
  edgeStrength: 0.5,
  gravity: 0.01,
  elasticity: 0.9,
  margin: 1,
  duration: 0,
  locate: true
};
export const optionsForDataset: Record<string, ForceLayoutOptions> = {
  'files/eurosys.json': { ...defaultOptions, gravity: 0.005 },
  'files/arctic-cleaned-up.json': {
    ...defaultOptions,
    edgeStrength: 1,
    edgeLength: 0,
    gravity: 0.002
  },
  'files/yeast.json': { ...defaultOptions, gravity: 0.005 },
  'files/paris-software.json': {
    ...defaultOptions,
    charge: 20,
    gravity: 0.002
  },
  'files/relativity.json': { ...defaultOptions, gravity: 0.005 },
  'files/oregon.json': defaultOptions,
  'files/silk-road.json': defaultOptions,
  'files/small-clusters.mtx.gz': defaultOptions,
  'files/circuit_4.mtx.gz': defaultOptions,
  'files/ruwikt20160210_2017-01-08_noun.json.gz': defaultOptions,
  'files/hcircuit.mtx.gz': {
    ...defaultOptions,
    charge: 15,
    edgeStrength: 5,
    gravity: 0.005
  },
  'files/notre-dame.mtx.gz': defaultOptions
};
ts
import { RawEdge } from '@linkurious/ogma';

type LayoutType = 'cpu' | 'gpu';
const state = {
  labels: {
    cpu: document.querySelector<HTMLSpanElement>('#container-cpu .stats')!,
    gpu: document.querySelector<HTMLSpanElement>('#container-gpu .stats')!
  },
  duration: {
    cpu: 0,
    gpu: 0
  },
  start: {
    cpu: 0,
    gpu: 0
  },
  // timer is running
  timers: {
    cpu: 0,
    gpu: 0
  },
  running: {
    cpu: false,
    gpu: false
  }
};

export const updateTimeLabel = (
  side: LayoutType,
  title: string,
  time: number
) => (state.labels[side].innerText = `${title} ${(time / 1000).toFixed(2)}s`);

export const startTimer = (id: LayoutType) => {
  state.running[id] = true;
  state.start[id] = performance.now();

  // CPU side needs a button to stop the layout because it can get too long
  if (id === 'cpu') {
    const stopButton =
      document.querySelector<HTMLSpanElement>('.left .stop-layout')!;
    stopButton.style.display = 'inline-block';
  }

  const update = () => {
    state.timers[id] = requestAnimationFrame(update);
    const t = performance.now() - state.start[id];
    if (state.running.cpu) updateTimeLabel('cpu', 'CPU', t);
    if (state.running.gpu) updateTimeLabel('gpu', 'GPU', t);
  };
  update();
};

export const stopTimer = (id?: LayoutType) => {
  if (id) {
    cancelAnimationFrame(state.timers[id]);
    state.running[id] = false;
    state.duration[id] = performance.now() - state.start[id];
    if (id === 'cpu') {
      const stopButton =
        document.querySelector<HTMLSpanElement>('.left .stop-layout')!;
      stopButton.style.display = '';
    }
  } else {
    // update the performace comparison label
    const { cpu, gpu } = state.duration;
    const ratio = (cpu / gpu).toFixed(2);
    state.labels.gpu.innerHTML += `<span class="ratio">&nbsp;${ratio}&times; faster</span>`;
  }
};

export function filterParallelEdges(edges: RawEdge[]) {
  const edgeset = new Set();
  return edges.filter(edge => {
    const st = `${edge.source}-${edge.target}`;
    const ts = `${edge.target}-${edge.source}`;
    if (edgeset.has(st) || edgeset.has(ts)) return false;
    edgeset.add(st);
    edgeset.add(ts);
    return true;
  });
}

export function loadZip(zip: string): Promise<string> {
  return new Promise((resolve, reject) => {
    fetch(zip)
      .then(res => res.arrayBuffer())
      .then(buffer => {
        // @ts-expect-error missing types for fflate
        fflate.gunzip(
          new Uint8Array(buffer),
          (err: unknown, unzipped: Uint8Array) => {
            if (err) return reject(err);
            // @ts-expect-error missing types for fflate
            const str = fflate.strFromU8(unzipped) as string;
            resolve(str);
          }
        );
      });
  });
}