Skip to content

Instantly share code, notes, and snippets.

@fabiovalse

fabiovalse/README.md

Last active January 26, 2023 14:28
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fabiovalse/03d07b071257987add9a7ba28a4befb5 to your computer and use it in GitHub Desktop.
Save fabiovalse/03d07b071257987add9a7ba28a4befb5 to your computer and use it in GitHub Desktop.
Download ZIP
Dijkstra on node-link diagram
Raw
README.md

A node-link diagram running a javascript implementation of the Dijkstra algorithm. Every time the visualization is refreshed two nodes are selected as start (in red) and end point (in blue). Then the shortest path is computed and shown on the diagram by highlighting the edges.

Raw
dijkstra.js
var Graph = (function (undefined) {
var extractKeys = function (obj) {
var keys = [], key;
for (key in obj) {
Object.prototype.hasOwnProperty.call(obj,key) && keys.push(key);
}
return keys;
}
var sorter = function (a, b) {
return parseFloat (a) - parseFloat (b);
}
var findPaths = function (map, start, end, infinity) {
infinity = infinity || Infinity;
var costs = {},
open = {'0': [start]},
predecessors = {},
keys;
var addToOpen = function (cost, vertex) {
var key = "" + cost;
if (!open[key]) open[key] = [];
open[key].push(vertex);
}
costs[start] = 0;
while (open) {
if(!(keys = extractKeys(open)).length) break;
keys.sort(sorter);
var key = keys[0],
bucket = open[key],
node = bucket.shift(),
currentCost = parseFloat(key),
adjacentNodes = map[node] || {};
if (!bucket.length) delete open[key];
for (var vertex in adjacentNodes) {
if (Object.prototype.hasOwnProperty.call(adjacentNodes, vertex)) {
var cost = adjacentNodes[vertex],
totalCost = cost + currentCost,
vertexCost = costs[vertex];
if ((vertexCost === undefined) || (vertexCost > totalCost)) {
costs[vertex] = totalCost;
addToOpen(totalCost, vertex);
predecessors[vertex] = node;
}
}
}
}
if (costs[end] === undefined) {
return null;
} else {
return predecessors;
}
}
var extractShortest = function (predecessors, end) {
var nodes = [],
u = end;
while (u) {
nodes.push(u);
u = predecessors[u];
}
nodes.reverse();
return nodes;
}
var findShortestPath = function (map, nodes) {
var start = nodes.shift(),
end,
predecessors,
path = [],
shortest;
while (nodes.length) {
end = nodes.shift();
predecessors = findPaths(map, start, end);
if (predecessors) {
shortest = extractShortest(predecessors, end);
if (nodes.length) {
path.push.apply(path, shortest.slice(0, -1));
} else {
return path.concat(shortest);
}
} else {
return null;
}
start = end;
}
}
var toArray = function (list, offset) {
try {
return Array.prototype.slice.call(list, offset);
} catch (e) {
var a = [];
for (var i = offset || 0, l = list.length; i < l; ++i) {
a.push(list[i]);
}
return a;
}
}
var Graph = function (map) {
this.map = map;
}
Graph.prototype.findShortestPath = function (start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(this.map, start);
} else if (arguments.length === 2) {
return findShortestPath(this.map, [start, end]);
} else {
return findShortestPath(this.map, toArray(arguments));
}
}
Graph.findShortestPath = function (map, start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(map, start);
} else if (arguments.length === 3) {
return findShortestPath(map, [start, end]);
} else {
return findShortestPath(map, toArray(arguments, 1));
}
}
return Graph;
})();
Raw
index.coffee
circle_radius = 12
nodes = [{id: 'a'},{id: 'b'},{id: 'c'},{id: 'd'},{id: 'e'},{id: 'f'},{id: 'g'},{id: 'h'},{id: 'i'},{id: 'j'},{id: 'k'},{id: 'l'},{id: 'm'},{id: 'n'},{id: 'o'},{id: 'p'},{id: 'q'},{id: 'r'},{id: 's'},{id: 't'},{id: 'u'},{id: 'v'},{id: 'w'},{id: 'x'},{id: 'y'},{id: 'z'}]
a = nodes[Math.floor Math.random()*nodes.length]
a.start = true
a = a.id
b = nodes[Math.floor Math.random()*nodes.length]
b.end = true
b = b.id
links = [
{source: 'a', target: 'b', value: Math.floor(Math.random()*10+1)}
{source: 'a', target: 'c', value: Math.floor(Math.random()*10+1)}
{source: 'd', target: 'n', value: Math.floor(Math.random()*10+1)}
{source: 'c', target: 'b', value: Math.floor(Math.random()*10+1)}
{source: 'c', target: 'e', value: Math.floor(Math.random()*10+1)}
{source: 'e', target: 'g', value: Math.floor(Math.random()*10+1)}
{source: 'f', target: 'h', value: Math.floor(Math.random()*10+1)}
{source: 'h', target: 'm', value: Math.floor(Math.random()*10+1)}
{source: 'i', target: 'z', value: Math.floor(Math.random()*10+1)}
{source: 'z', target: 'l', value: Math.floor(Math.random()*10+1)}
{source: 'r', target: 'b', value: Math.floor(Math.random()*10+1)}
{source: 's', target: 'r', value: Math.floor(Math.random()*10+1)}
{source: 'a', target: 's', value: Math.floor(Math.random()*10+1)}
{source: 'c', target: 'o', value: Math.floor(Math.random()*10+1)}
{source: 'o', target: 'b', value: Math.floor(Math.random()*10+1)}
{source: 'x', target: 't', value: Math.floor(Math.random()*10+1)}
{source: 't', target: 'm', value: Math.floor(Math.random()*10+1)}
{source: 'w', target: 'd', value: Math.floor(Math.random()*10+1)}
{source: 'y', target: 'k', value: Math.floor(Math.random()*10+1)}
{source: 'i', target: 'k', value: Math.floor(Math.random()*10+1)}
{source: 'x', target: 'z', value: Math.floor(Math.random()*10+1)}
{source: 'm', target: 'e', value: Math.floor(Math.random()*10+1)}
{source: 'j', target: 'h', value: Math.floor(Math.random()*10+1)}
{source: 'i', target: 'j', value: Math.floor(Math.random()*10+1)}
{source: 'u', target: 'e', value: Math.floor(Math.random()*10+1)}
{source: 'm', target: 'a', value: Math.floor(Math.random()*10+1)}
{source: 'x', target: 'l', value: Math.floor(Math.random()*10+1)}
{source: 'l', target: 'n', value: Math.floor(Math.random()*10+1)}
{source: 'n', target: 'a', value: Math.floor(Math.random()*10+1)}
{source: 'v', target: 'm', value: Math.floor(Math.random()*10+1)}
{source: 'q', target: 'a', value: Math.floor(Math.random()*10+1)}
{source: 'p', target: 'l', value: Math.floor(Math.random()*10+1)}
{source: 'q', target: 'n', value: Math.floor(Math.random()*10+1)}
{source: 'y', target: 'f', value: Math.floor(Math.random()*10+1)}
]
graph = {nodes: nodes, links: links}
### Shortest Path
###
convert_graph = (graph) ->
map = {}
for n in graph.nodes
for l in links
if n.id is l.source
if !(n.id of map)
map[n.id] = {}
map[n.id][l.target] = l.value
return map
map = convert_graph graph
lib_graph = new Graph map
shortest_path = lib_graph.findShortestPath(a, b)
if shortest_path?
for n,i in shortest_path
if i < shortest_path.length-1
link = {source: n, target: shortest_path[i+1]}
for l in links
if l.source is link.source and l.target is link.target
l.covered = true
### Visualization
###
width = d3.select('body').node().getBoundingClientRect().width
height = d3.select('body').node().getBoundingClientRect().height
svg = d3.select 'svg'
.attrs
width: width
height: height
defs = svg.append 'defs'
zoomable_layer = svg.append 'g'
zoom = d3.zoom()
.scaleExtent([-Infinity,Infinity])
.on 'zoom', () ->
zoomable_layer
.attrs
transform: d3.event.transform
svg.call zoom
arrowheads = defs.append 'marker'
.attrs
class: 'arrowhead'
id: 'arrow'
viewBox: '0 0 10 10'
refX: 6.5+circle_radius
refY: 5
orient: 'auto'
arrowheads.append 'path'
.attrs
d: 'M0,0 L0,10 L10,5 z'
fill: '#dddddd'
sp_arrowheads = defs.append 'marker'
.attrs
class: 'arrowhead'
id: 'sp_arrow'
viewBox: '0 0 10 10'
refX: 6.5+circle_radius
refY: 5
orient: 'auto'
sp_arrowheads.append 'path'
.attrs
d: 'M0,0 L0,10 L10,5 z'
fill: '#ff9999'
### Force simulation
###
ticked = () ->
zoomable_layer.selectAll '.node'
.attrs
transform: (d) -> "translate(#{d.x},#{d.y})"
zoomable_layer.selectAll '.link'
.attrs
x1: (d) -> d.source.x
y1: (d) -> d.source.y
x2: (d) -> d.target.x
y2: (d) -> d.target.y
zoomable_layer.selectAll '.label'
.attrs
transform: (d) -> "translate(#{(d.source.x+d.target.x)/2},#{(d.source.y+d.target.y)/2})"
charge = d3.forceManyBody()
.strength -300
simulation = d3.forceSimulation()
.force 'link', d3.forceLink().id((d) -> d.id)
.force 'charge', charge
.force 'center', d3.forceCenter(width / 2, height / 2)
simulation
.nodes graph.nodes
.on 'tick', ticked
simulation.force 'link'
.links graph.links
### Links
###
links = zoomable_layer.selectAll '.link'
.data(graph.links, (d) -> d.id)
links.enter().append 'line'
.attrs
class: 'link'
'marker-end': (d) -> if d.covered? and d.covered is true then 'url(#sp_arrow)' else 'url(#arrow)'
stroke: (d) -> if d.covered? and d.covered is true then '#ff9999' else '#dddddd'
links.exit().remove()
# label links
labels = zoomable_layer.selectAll '.label'
.data(graph.links, (d) -> d.id)
labels.enter().append 'text'
.attrs
class: 'label'
'text-anchor': 'middle'
.text (d) -> d.value
### Nodes
###
nodes = zoomable_layer.selectAll '.node'
.data(graph.nodes, (d) -> d.id)
new_nodes = nodes.enter().append 'g'
.attrs
class: 'node'
new_nodes.append 'circle'
.attrs
r: circle_radius
fill: (d) ->
if d.start?
'#ff9999'
else if d.end?
'#9999ff'
else if d.id
'#404040'
new_nodes.append 'text'
.text (d) -> d.id
.attr 'dy', '0.35em'
nodes.exit().remove()
Raw
index.css
html, body {
padding: 0;
margin: 0;
width: 100%;
height: 100%;
}
.node > text {
font-family: sans-serif;
text-anchor: middle;
pointer-events: none;
fill: #fff;
}
.link {
stroke-width: 4px;
}
.label {
font-size: 13px
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Dijkstra on node-link diagram</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="dijkstra.js"></script>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-selection-multi.v0.4.min.js"></script>
</head>
<body>
<svg></svg>
<script src="index.js"></script>
</body>
</html>
Raw
index.js
// Generated by CoffeeScript 1.10.0
(function() {
var a, arrowheads, b, charge, circle_radius, convert_graph, defs, graph, height, i, j, k, l, labels, len, len1, lib_graph, link, links, map, n, new_nodes, nodes, shortest_path, simulation, sp_arrowheads, svg, ticked, width, zoom, zoomable_layer;
circle_radius = 12;
nodes = [
{
id: 'a'
}, {
id: 'b'
}, {
id: 'c'
}, {
id: 'd'
}, {
id: 'e'
}, {
id: 'f'
}, {
id: 'g'
}, {
id: 'h'
}, {
id: 'i'
}, {
id: 'j'
}, {
id: 'k'
}, {
id: 'l'
}, {
id: 'm'
}, {
id: 'n'
}, {
id: 'o'
}, {
id: 'p'
}, {
id: 'q'
}, {
id: 'r'
}, {
id: 's'
}, {
id: 't'
}, {
id: 'u'
}, {
id: 'v'
}, {
id: 'w'
}, {
id: 'x'
}, {
id: 'y'
}, {
id: 'z'
}
];
a = nodes[Math.floor(Math.random() * nodes.length)];
a.start = true;
a = a.id;
b = nodes[Math.floor(Math.random() * nodes.length)];
b.end = true;
b = b.id;
links = [
{
source: 'a',
target: 'b',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'a',
target: 'c',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'd',
target: 'n',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'c',
target: 'b',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'c',
target: 'e',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'e',
target: 'g',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'f',
target: 'h',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'h',
target: 'm',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'i',
target: 'z',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'z',
target: 'l',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'r',
target: 'b',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 's',
target: 'r',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'a',
target: 's',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'c',
target: 'o',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'o',
target: 'b',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'x',
target: 't',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 't',
target: 'm',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'w',
target: 'd',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'y',
target: 'k',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'i',
target: 'k',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'x',
target: 'z',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'm',
target: 'e',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'j',
target: 'h',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'i',
target: 'j',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'u',
target: 'e',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'm',
target: 'a',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'x',
target: 'l',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'l',
target: 'n',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'n',
target: 'a',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'v',
target: 'm',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'q',
target: 'a',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'p',
target: 'l',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'q',
target: 'n',
value: Math.floor(Math.random() * 10 + 1)
}, {
source: 'y',
target: 'f',
value: Math.floor(Math.random() * 10 + 1)
}
];
graph = {
nodes: nodes,
links: links
};
/* Shortest Path
*/
convert_graph = function(graph) {
var j, k, l, len, len1, map, n, ref;
map = {};
ref = graph.nodes;
for (j = 0, len = ref.length; j < len; j++) {
n = ref[j];
for (k = 0, len1 = links.length; k < len1; k++) {
l = links[k];
if (n.id === l.source) {
if (!(n.id in map)) {
map[n.id] = {};
}
map[n.id][l.target] = l.value;
}
}
}
return map;
};
map = convert_graph(graph);
lib_graph = new Graph(map);
shortest_path = lib_graph.findShortestPath(a, b);
if (shortest_path != null) {
for (i = j = 0, len = shortest_path.length; j < len; i = ++j) {
n = shortest_path[i];
if (i < shortest_path.length - 1) {
link = {
source: n,
target: shortest_path[i + 1]
};
for (k = 0, len1 = links.length; k < len1; k++) {
l = links[k];
if (l.source === link.source && l.target === link.target) {
l.covered = true;
}
}
}
}
}
/* Visualization
*/
width = d3.select('body').node().getBoundingClientRect().width;
height = d3.select('body').node().getBoundingClientRect().height;
svg = d3.select('svg').attrs({
width: width,
height: height
});
defs = svg.append('defs');
zoomable_layer = svg.append('g');
zoom = d3.zoom().scaleExtent([-Infinity, Infinity]).on('zoom', function() {
return zoomable_layer.attrs({
transform: d3.event.transform
});
});
svg.call(zoom);
arrowheads = defs.append('marker').attrs({
"class": 'arrowhead',
id: 'arrow',
viewBox: '0 0 10 10',
refX: 6.5 + circle_radius,
refY: 5,
orient: 'auto'
});
arrowheads.append('path').attrs({
d: 'M0,0 L0,10 L10,5 z',
fill: '#dddddd'
});
sp_arrowheads = defs.append('marker').attrs({
"class": 'arrowhead',
id: 'sp_arrow',
viewBox: '0 0 10 10',
refX: 6.5 + circle_radius,
refY: 5,
orient: 'auto'
});
sp_arrowheads.append('path').attrs({
d: 'M0,0 L0,10 L10,5 z',
fill: '#ff9999'
});
/* Force simulation
*/
ticked = function() {
zoomable_layer.selectAll('.node').attrs({
transform: function(d) {
return "translate(" + d.x + "," + d.y + ")";
}
});
zoomable_layer.selectAll('.link').attrs({
x1: function(d) {
return d.source.x;
},
y1: function(d) {
return d.source.y;
},
x2: function(d) {
return d.target.x;
},
y2: function(d) {
return d.target.y;
}
});
return zoomable_layer.selectAll('.label').attrs({
transform: function(d) {
return "translate(" + ((d.source.x + d.target.x) / 2) + "," + ((d.source.y + d.target.y) / 2) + ")";
}
});
};
charge = d3.forceManyBody().strength(-300);
simulation = d3.forceSimulation().force('link', d3.forceLink().id(function(d) {
return d.id;
})).force('charge', charge).force('center', d3.forceCenter(width / 2, height / 2));
simulation.nodes(graph.nodes).on('tick', ticked);
simulation.force('link').links(graph.links);
/* Links
*/
links = zoomable_layer.selectAll('.link').data(graph.links, function(d) {
return d.id;
});
links.enter().append('line').attrs({
"class": 'link',
'marker-end': function(d) {
if ((d.covered != null) && d.covered === true) {
return 'url(#sp_arrow)';
} else {
return 'url(#arrow)';
}
},
stroke: function(d) {
if ((d.covered != null) && d.covered === true) {
return '#ff9999';
} else {
return '#dddddd';
}
}
});
links.exit().remove();
labels = zoomable_layer.selectAll('.label').data(graph.links, function(d) {
return d.id;
});
labels.enter().append('text').attrs({
"class": 'label',
'text-anchor': 'middle'
}).text(function(d) {
return d.value;
});
/* Nodes
*/
nodes = zoomable_layer.selectAll('.node').data(graph.nodes, function(d) {
return d.id;
});
new_nodes = nodes.enter().append('g').attrs({
"class": 'node'
});
new_nodes.append('circle').attrs({
r: circle_radius,
fill: function(d) {
if (d.start != null) {
return '#ff9999';
} else if (d.end != null) {
return '#9999ff';
} else if (d.id) {
return '#404040';
}
}
});
new_nodes.append('text').text(function(d) {
return d.id;
}).attr('dy', '0.35em');
nodes.exit().remove();
}).call(this);
@iosonosempreio
Copy link

Hi,
very interesting example. Is there a way for use it with undirected graphs?
Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment