greuler is graph theory visualization tool powered by d3 and on top of WebCola which allows the creation and manipulation of graphs with a simple api
greuler works on top of d3.js and WebCola so include those first
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.js"></script>
<script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
Install greuler with bower
bower install greuler
And then include it in your webpage
<script src="bower_components/greuler/dist/greuler.js"></script>
The hello world program requires calling greuler with an object having the following properties
target A selector to the container to hold the graphdata An object describing the properties of the graphdata.nodes The nodes of the graph, they need to have an iddata.edges The edges of the graph, they join two nodes by idA full description of the properties can be found in the README
After the instance is created it's needed to call instance.update() to create the initial
layout
'use strict';
greuler({
target: '#hello-world',
width: 480,
data: {
nodes: [
{id: 0},
{id: 1},
{id: 2},
{id: 3},
{id: 4}
],
links: [
{source: 0, target: 1},
{source: 1, target: 2},
{source: 2, target: 0},
{source: 3, target: 4}
]
}
}).update();
You can also generate a graph by calling greuler.Graph.random(options)
'use strict';
greuler({
target: '#random',
width: 480,
height: 200,
data: greuler.Graph.random({
order: 5,
size: 5,
connected: true
})
}).update();
Assuming that instance = greuler(options).update() is called there are two ways to interact
with the graph
instance.graph holds utility methods to manipulate the graph like adding/removing
nodes and edges and other utility methods like querying the adjacent nodes of some node, etc.
The convention I used for the project is to always use objects as the first parameter to
describe a node or edge (an array/function is needed in some cases of some methods of
instance.graph but they describe multiple nodes/edges),
also all the methods of instance.graph (but the ones who add nodes and edges) receive a
single parameter
Please take a look at all the methods of instance.graph which can be found
here
instance.selector holds utility methods to animate existing nodes/edges of the graph,
under the hood it uses instance.graph and wraps the returning values inside d3 selections
Just like instance.graph the first method will always be an object describing a node / edge,
the second parameter is an override of the styles predefined to be used during the animation
'use strict';
(function () {
var greuler = window.greuler;
var instance = greuler({
target: '#dfs',
height: 500,
animationTime: 500,
data: greuler.Graph.random({ connected: true })
}).update();
window.examples.dfs = function () {
var player = new greuler.player.Generator(instance);
player.run(function *algorithm(instance) {
var visited = [];
function *dfs(u, p) {
yield function () {
instance.selector.highlightNode({ id: u });
};
visited[u] = true;
var adjacent = instance.graph.getAdjacentNodes({ id: u });
for (var i = 0; i < adjacent.length; i += 1) {
var v = adjacent[i].id;
if (v === p) { continue; }
if (!visited[v]) {
yield function () {
instance.selector.traverseAllEdgesBetween({ source: u, target: v });
};
yield *dfs(v, u);
} else {
yield function () {
instance.selector.traverseAllEdgesBetween(
{ source: u, target: v },
{ keepStroke: false }
)
.transition()
.attr('opacity', 0.3);
};
}
}
yield function () {
instance.selector.getNode({ id: u })
.transition()
.attr('fill', 'black');
};
}
yield *dfs(0, -1);
});
};
})();
'use strict';
(function () {
var greuler = window.greuler;
var instance = greuler({
target: '#bfs',
width: 600,
height: 600,
animationTime: 500,
data: greuler.Graph.random({ connected: true })
}).update();
window.examples.bfs = function () {
var player = new greuler.player.Generator(instance);
player.run(function *algorithm(instance) {
function *bfs(source) {
// queue
var distance = [];
var q = [];
var parent = [];
function highlight(id, visit) {
return function () {
var node = instance.graph.getNode({ id: id });
node.topRightLabel = distance[id];
instance.selector.highlightNode({ id: id });
if (visit) {
instance.selector.getNode({ id: id })
.transition()
.attr('fill', 'black');
}
instance.update({skipLayout: true});
};
}
distance[source] = 0;
q.push(source);
while (q.length) {
var top = q.shift();
var adjacent = instance.graph.getAdjacentNodes({ id: top });
yield highlight(top, true);
for (var i = 0; i < adjacent.length; i += 1) {
var next = adjacent[i].id;
if (next === parent[top]) { continue; }
if (typeof distance[next] === 'undefined') {
distance[next] = distance[top] + 1;
parent[next] = top;
q.push(next);
yield function () {
instance.selector.traverseAllEdgesBetween(
{ source: top, target: next }
);
};
yield highlight(next);
} else {
yield function () {
instance.selector.traverseAllEdgesBetween(
{ source: top, target: next },
{ keepStroke: false }
)
.transition()
.attr('opacity', 0.3);
};
}
}
}
}
yield *bfs(0);
});
};
})();
'use strict';
window.d3.json('scripts/examples/data/eulerian-graph.json', function (error, data) {
var instance = greuler({
target: '#eulerian-trail',
width: 600,
height: 600,
animationTime: 500,
data: data
}).update();
window.examples['eulerian-trail'] = function () {
var greuler = window.greuler;
var player = new greuler.player.Generator(instance);
player.run(function *algorithm(instance) {
var stack = [];
var trail = [];
function eulerianTrail(u) {
stack.push(u);
var edges = instance.graph.getIncidentEdges({ id: u });
for (var i = 0; i < edges.length; i += 1) {
var e = edges[i];
var next = e.target.id === u ? e.source.id : e.target.id;
if (e.used) { continue; }
e.used = true;
eulerianTrail(next);
}
trail.push(stack.pop());
}
eulerianTrail(0);
// node traversal is given by trail
for (var i = 0; i < trail.length; i += 1) {
yield function () {
instance.selector.traverseAllEdgesBetween(
{ source: trail[i], target: trail[i + 1] }
);
};
}
});
};
});