Appearance
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 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 }
]
}