Skip to content
  1. Examples

Shortest path

This example shows how to use the shortest path algorithm to find the shortest path between two nodes in the graph.

Click on any two nodes to see the shortest path between them

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

const ogma = new Ogma({ container: 'graph-container' });

const fadeClass = ogma.styles.createClass({
  name: 'fade',
  nodeAttributes: { opacity: 0.3 },
  edgeAttributes: { opacity: 0.3 }
});

const pathClass = ogma.styles.createClass({
  name: 'path',
  nodeAttributes: { radius: 60, opacity: 1, layer: 10 },
  edgeAttributes: { width: 24, opacity: 1, layer: 10 }
});

function clear() {
  fadeClass.clearEdges();
  fadeClass.clearNodes();
  pathClass.clearEdges();
  pathClass.clearNodes();
}

const selected: NodeId[] = [];
ogma.events.on('click', ({ target }) => {
  if (target && target.isNode) {
    selected.push(target.getId());
    if (selected.length === 2) {
      ogma.getNodes(selected).setSelected(true);
      findShortestPath(selected[0], selected[1]);
      selected.length = 0;
    } else clear();
  } else {
    clear();
    selected.length = 0;
  }
});

function findShortestPath(start: NodeId, target: NodeId) {
  clear();
  ogma.algorithms
    .shortestPath({
      source: start,
      target: target
    })
    .then(path => {
      path?.nodes.inverse().addClass('fade');
      path?.edges.inverse().addClass('fade');
      path?.nodes.addClass('path');
      path?.edges.addClass('path');
    });
}

const graph = await Ogma.parse.jsonFromUrl('files/paris-metro.json');
await ogma.setGraph(graph);
const [source, target] = [
  'Père LachaisePARIS-11EME',
  'La Motte-Picquet - GrenellePARIS-15EME'
];
ogma.getNodes([source, target]).setSelected(true);
findShortestPath(source, target);
html
<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />

    <link type="text/css" rel="stylesheet" href="styles.css" />
  </head>

  <body>
    <div id="graph-container"></div>
    <script type="module" src="index.ts"></script>
  </body>
</html>
css
#graph-container {
  top: 0;
  bottom: 0;
  left: 0;
  right: 0;
  position: absolute;
  margin: 0;
  overflow: hidden;
}