Skip to content

Instantly share code, notes, and snippets.

@jalapic
Last active April 11, 2017 03:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jalapic/0eba1241acdf67c62f5b87357864d662 to your computer and use it in GitHub Desktop.
Save jalapic/0eba1241acdf67c62f5b87357864d662 to your computer and use it in GitHub Desktop.
Find geodesic distances
license: mit

This example shows an implementation of Dijkstra's algorithm for finding distances in a graph, implemented as a D3 plugin.

Click an individual to start Dijkstra's algorithm with that node as the source. You can view individual names by hovering over nodes in the graph. When Dijkstra's algorithm completes, hover over a node to see its geodesic distance from the source individual.

Data from German School network example 1900.(see Heidler et al 2014 Social Networks)

All code adapted from sdjacobs's excellent block: Dijkstra's algorithm in Javascript/D3

d3.dijkstra = function () {
var dijkstra = {}, nodes, edges, source, dispatch = d3.dispatch("start", "tick", "step", "end");
dijkstra.run = function (src) {
source = src;
var unvisited = [];
nodes.forEach(function (d) {
if (d != src) {
d.distance = Infinity;
unvisited.push(d);
d.visited = false;
}
});
var current = src;
current.distance = 0;
function tick() {
current.visited = true;
current.links.forEach(function(link) {
var tar = link.target;
if (!tar.visited) {
var dist = current.distance + link.value;
tar.distance = Math.min(dist, tar.distance);
}
});
if (unvisited.length == 0 || current.distance == Infinity) {
dispatch.end()
return true;
}
unvisited.sort(function(a, b) {
return b.distance - a.distance
});
current = unvisited.pop()
dispatch.tick();
return false;
}
d3.timer(tick);
};
dijkstra.nodes = function (_) {
if (!arguments.length)
return nodes;
else {
nodes = _;
return dijkstra;
}
};
dijkstra.edges = function (_) {
if (!arguments.length)
return edges;
else {
edges = _;
return dijkstra;
}
};
dijkstra.source = function(_) {
if (!arguments.length)
return source;
else {
source = _;
return dijkstra;
}
};
dispatch.on("start.code", dijkstra.run);
return d3.rebind(dijkstra, dispatch, "on", "end", "start", "tick");
};
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
stroke: #999;
stroke-opacity: .6;
}
</style>
<body>
<br>
<h2>Click a node to find the geodesic distances</h2>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="dijkstra.js"></script>
<script>
var width = 960,
height = 500;
var color = d3.scale.category20();
var force = d3.layout.force()
.charge(-120)
.linkDistance(30)
.size([width, height]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
d3.csv("mat.csv", function(error, data) {
var nodes = [], nodesByName = {}, links = [];
function addNodeByName(fullname) {
var name = fullname.split(',')[0];
if (!nodesByName[name]) {
var node = {"name":name, "links":[]}
nodesByName[name] = node;
nodes.push(node);
return node;
}
else
return nodesByName[name];
}
data.forEach(function(d) {
for (k in d) {
if (d.hasOwnProperty(k) && k != "Cities1" && d[k] > 0) {
links.push({"source": addNodeByName(d["Cities1"]), "target": addNodeByName(k), "value": parseInt(d[k])})
}
}
});
force
.nodes(nodes)
.links(links)
.start();
var link = svg.selectAll(".link")
.data(links)
.enter().append("line")
.attr("class", "link")
.style("stroke-width", 1);
var node = svg.selectAll(".node")
.data(nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", 5)
.style("fill", "grey")
.call(force.drag);
link.each(function(d) {
d.source.links.push(d);
d.selection = d3.select(this);
});
node.each(function(d) {
d.selection = d3.select(this);
});
node.append("title")
.text(function(d) { return d.name; });
link.append("title")
.text(function(d) { return d.source.name + " → " + d.target.name + "\n" + d.value + " mi" });
force.on("tick", function() {
link.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
});
node.on("mouseover", function(d) {
d3.select(this)
.attr("r", 10)
d.links.forEach(function(l) {
l.selection
.style("stroke-width", 10)
l.target.selection
.attr("r", 7);
});
});
node.on("mouseout", function(d) {
node.attr("r", 5)
link.style("stroke-width", 1);
});
link.on("mouseover", function() {
d3.select(this)
.style("stroke-width", 10);
});
link.on("mouseout", function() {
d3.select(this)
.style("stroke-width", 1);
});
var dijkstra = d3.dijkstra()
.nodes(nodes)
.edges(links);
var color = d3.scale.linear()
.domain([1, 3, 5])
.range(["green", "yellow", "red"]);
dijkstra.on("tick", function() {
node.style("fill", function(d) { return color(d.distance); });
});
dijkstra.on("end", function() {
var name = dijkstra.source().name;
node.select("title")
.text(function(d) { return d.name + "\n(" + d.distance + " geodesic distance from " + name + ")" });
});
node.on("click", dijkstra.start);
});
</script>
Cities1 Albert Hager Albin Hager Bager Bernhardt Ebersbach Eisenreich Ernst Fahrmann Flach Fritzsche Golla Gross Haas Herold Hofmann Holzmuller Kachel Kiessling Kneisel Lasch Meier Meinhold O. Muller Pfeil Pippig Prahl Prase Prase2 R. Muller R. Schubert Rahling Raubert Rausch Rettig Rich. Zimmermann Rudolf Schaller Schlegel Schmidt Schnabel Schneider Seifert Stolze Thrum Trampler Vetter Wilhelm Wolf
Albert Hager 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
Albin Hager 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Bager 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0
Bernhardt 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Ebersbach 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
Eisenreich 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1
Ernst 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Fahrmann 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1
Flach 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Fritzsche 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
Golla 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
Gross 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1
Haas 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
Herold 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
Hofmann 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Holzmuller 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
Kachel 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Kiessling 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
Kneisel 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1
Lasch 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0
Meier 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0
Meinhold 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0
O. Muller 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
Pfeil 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1
Pippig 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
Prahl 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Prase 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Prase2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0
R. Muller 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
R. Schubert 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0
Rahling 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
Raubert 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
Rausch 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0
Rettig 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Rich. Zimmermann 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
Rudolf 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Schaller 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
Schlegel 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0
Schmidt 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Schnabel 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0
Schneider 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Seifert 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1
Stolze 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1
Thrum 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0
Trampler 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Vetter 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1
Wilhelm 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Wolf 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment