Skip to content
  1. Examples
  2. Analysis

BFS and DFS graph traversals

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

ts
import Ogma, { Node, NodeList, RawGraph } from '@linkurious/ogma';
import { GUI } from '@linkurious/ogma-ui-kit/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 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" />
    <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 }
  ]
}