BFS and DFS graph traversals

This example shows how to traverse the graph using the Depth first and Breadth first algorithms.

import Ogma, { Node, NodeList, RawGraph } from '@linkurious/ogma';
import DAT from 'dat.gui';
// data
import tree from './tree.json';
import goggles from './goggles.json';

type GraphType = 'tree' | 'goggles';
const graphs: Record<GraphType, RawGraph> = {
  tree,
  goggles
};
let traversalType: 'dfs' | 'bfs' = 'dfs';

let animation: Promise<void | NodeList | Node> = Promise.resolve();
const settings = {
  graph: 'tree' as GraphType,
  traversal: 'Depth First',
  onTraverse() {
    animation = animation.then(() => ogma.getNodes().removeClass('visited'));
    animation.then(() => traverse());
  }
};
const gui = new DAT.GUI();
gui
  .add(settings, 'graph', ['tree', 'goggles'])
  .name('Graph')
  .onChange((value: GraphType) => {
    animation = animation
      .then(() => ogma.setGraph(graphs[value]))
      .then(() => layout(value));
    animation.then(() => traverse());
  });
gui
  .add(settings, 'traversal', ['Depth First', 'Breadth First'])
  .name('Traversal')
  .onChange(value => {
    traversalType = value === 'Depth First' ? 'dfs' : 'bfs';
    animation = animation.then(() => ogma.getNodes().removeClass('visited'));
    animation.then(() => traverse());
  });
gui.add(settings, 'onTraverse').name('Traverse');

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

ogma.styles.addRule({
  edgeAttributes: {
    shape: 'arrow',
    width: 3
  },
  nodeAttributes: {
    text: {
      content: n => n.getId(),
      minVisibleSize: 0,
      backgroundColor: '#222',
      color: '#fff',
      tip: false,
      position: 'center'
    }
  }
});

ogma.styles.createClass({
  name: 'visited',
  nodeAttributes: {
    color: '#ff0000',
    radius: 8
  }
});

function layout(type: GraphType) {
  const options = { locate: true };
  const l =
    type === 'tree'
      ? ogma.layouts.hierarchical(options)
      : ogma.layouts.force(options);
  return l.then(() => ogma.view.locateGraph());
}

function traverse() {
  const order: Node[] = [];
  const traversal =
    traversalType === 'dfs' ? ogma.algorithms.dfs : ogma.algorithms.bfs;

  traversal({
    root: ogma.getNode(0)!,
    onNode: node => {
      order.push(node);
    }
  });

  // animate nodes one by one
  animation = animation.then(() =>
    order.reduce(
      (acc, node) =>
        acc
          .then(() => node.addClass('visited', 800))
          .then(() => Promise.resolve(undefined)),
      Promise.resolve()
    )
  );
  return animation;
}

layout('tree').then(traverse);

html

<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script src="https://cdn.jsdelivr.net/npm/tweakpane@3.0.5/dist/tweakpane.min.js"></script>
    <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;
}

json

{
  "nodes": [
    { "id": 0 },
    { "id": 1 },
    { "id": 2 },
    { "id": 3 },
    { "id": 4 },
    { "id": 5 }
  ],
  "edges": [
    { "source": 0, "target": 1 },
    { "source": 1, "target": 2 },
    { "source": 2, "target": 0 },
    { "source": 2, "target": 3 },
    { "source": 3, "target": 4 },
    { "source": 4, "target": 5 },
    { "source": 5, "target": 3 }
  ]
}

json

{
  "nodes": [
    { "id": 0 },
    { "id": 1 },
    { "id": 2 },
    { "id": 3 },
    { "id": 4 },
    { "id": 5 }
  ],
  "edges": [
    { "source": 0, "target": 1 },
    { "source": 0, "target": 2 },
    { "source": 1, "target": 3 },
    { "source": 1, "target": 4 },
    { "source": 4, "target": 5 }
  ]
}

BFS and DFS graph traversals ​

BFS and DFS graph traversals