Skip to content

Instantly share code, notes, and snippets.

@sdjacobs
Last active August 29, 2015 14:13
Show Gist options
  • Save sdjacobs/c2ee01307cdeceb19f9d to your computer and use it in GitHub Desktop.
Save sdjacobs/c2ee01307cdeceb19f9d to your computer and use it in GitHub Desktop.
Putting Dijkstra's algorithm on the map

In this example, a directed graph of selected cities in the US is superimposed on a map of the US. Click a city to run Dijkstra's algorithm from that city.

The data comes from Infoplease, although I manually picked which cities had direct connections, for the purposes of showing the algorithm. Map imagery is (c) Open Street Map and Mapbox.

This builds on my d3-mapzoom plugin, as well as my Dijkstra implementation.

d3.mapzoom = function() {
var center = [0,0]
var scale = 10000
var projection = undefined,
zoom = undefined,
tile = undefined
var layers = []
function map(svg) {
projection = d3.geo.mercator()
.center(center)
.scale(scale)
zoom = d3.behavior.zoom()
.translate(projection([0,0]))
.scale(projection.scale() * 2 * Math.PI)
.on("zoom", redraw)
zoom(svg)
}
function redraw() {
projection.scale(zoom.scale() / (2 * Math.PI));
var c = projection.center(), t = projection.invert(zoom.translate())
var i = c[0] - t[0]
var j = c[1] - t[1]
projection.center([i, j])
layers.forEach(function(layer) {
layer();
});
}
map.center = function(_) {
if (!arguments.length)
return center;
else {
center = _;
}
return map;
}
map.scale = function(_) {
if (!arguments.length)
return scale;
else {
scale = _;
}
return map;
}
map.projection = function(_) {
if (!arguments.length)
return projection;
else
projection = _;
return map;
}
map.zoom = function(_) {
if (!arguments.length)
return zoom;
else
zoom = _;
return map;
}
map.tile = function(_) {
if (!arguments.length)
return tile;
else
tile = _;
return map;
}
map.layers = function(_) {
if (!arguments.length)
return layers;
else
laters = _;
return map;
}
map.addLayer = function(_) {
layers.push(_)
redraw()
}
map.addTileLayer = function(frame, url, prefixes) {
var tile = d3.geo.tile()
.zoomDelta((window.devicePixelRatio || 1) - .5)
function draw() {
var tiles = tile
.scale(zoom.scale())
.translate(zoom.translate())()
frame.selectAll('*').remove()
frame
.selectAll("image")
.data(tiles)
.enter().append("image")
.attr("xlink:href", function(d) { return "http://" + prefixes[Math.random() * prefixes.length | 0] + "." + url + d[2] + "/" + d[0] + "/" + d[1] + ".png"; })
.attr("width", Math.round(tiles.scale))
.attr("height", Math.round(tiles.scale))
.attr("x", function(d) { return Math.round((d[0] + tiles.translate[0]) * tiles.scale); })
.attr("y", function(d) { return Math.round((d[1] + tiles.translate[1]) * tiles.scale); })
}
layers.push(draw)
redraw()
}
map.addEraseCanvas = function(canvas) {
var ctx = canvas.getContext('2d')
var erase = function() {
ctx.clearRect(0, 0, canvas.width, canvas.height)
}
layers.unshift(erase) // add at beginning
}
map.addCanvasTileLayer = function(canvas, url, prefixes) {
var tile = d3.geo.tile()
.zoomDelta((window.devicePixelRatio || 1) - .5)
var ctx = canvas.getContext('2d')
function draw() {
var tiles = tile
.scale(zoom.scale())
.translate(zoom.translate())()
tiles.forEach(function(d, i) {
if (! d.img) {
d.img = new Image()
d.img.onload = function() {
var x = Math.round((d[0] + tiles.translate[0]) * tiles.scale);
var y = Math.round((d[1] + tiles.translate[1]) * tiles.scale);
var length = Math.round(tiles.scale)
ctx.drawImage(d.img, x, y, length, length);
}
}
d.img.src = "http://" + prefixes[Math.random() * prefixes.length | 0] + "." + url + d[2] + "/" + d[0] + "/" + d[1] + ".png";
});
}
layers.push(draw);
}
return map
}
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");
};
source target value
Seattle San Francisco 817
Seattle Salt Lake City 883
Seattle Minneapolis 1641
Seattle Omaha 1705
San Francisco Seattle 817
San Francisco Los Angeles 403
San Francisco Salt Lake City 754
Los Angeles San Francisco 403
Los Angeles Salt Lake City 728
Los Angeles Phoenix 398
Phoenix Los Angeles 398
Phoenix Salt Lake City 651
Phoenix El Paso 402
Phoenix Denver 836
Salt Lake City Seattle 883
Salt Lake City Denver 512
Salt Lake City San Francisco 754
Salt Lake City Los Angeles 728
Salt Lake City Phoenix 651
Denver Salt Lake City 512
Denver El Paso 652
Denver Omaha 559
Denver Kansas City 616
Denver Dallas 801
Denver Phoenix 836
El Paso Phoenix 402
El Paso Denver 652
El Paso Dallas 625
El Paso Houston 756
Dallas Houston 242
Dallas El Paso 625
Dallas Memphis 470
Dallas Kansas City 508
Kansas City Denver 616
Kansas City Omaha 204
Kansas City Dallas 508
Kansas City Memphis 454
Kansas City St. Louis 255
Omaha Denver 559
Omaha Kansas City 204
Omaha Minneapolis 373
Omaha Chicago 493
Houston New Orleans 365
Houston Dallas 242
Houston El Paso 756
Minneapolis Omaha 373
Minneapolis Chicago 411
Minneapolis St. Louis 559
Minneapolis Seattle 1641
St. Louis Minneapolis 559
St. Louis Kansas City 255
St. Louis Memphis 295
St. Louis Chicago 293
St. Louis Indianapolis 239
St. Louis Chicago 293
St. Louis Louisville 264
Memphis St. Louis 295
Memphis Kansas City 454
Memphis Dallas 470
Memphis New Orleans 401
Memphis Birmingham 249
Memphis Louisville 396
New Orleans Houston 365
New Orleans Birmingham 347
New Orleans Miami 892
New Orleans Memphis 401
Chicago Minneapolis 411
Chicago Detroit 279
Chicago Cleveland 344
Chicago St. Louis 293
Chicago Indianapolis 189
Chicago Omaha 493
Indianapolis Chicago 189
Indianapolis St. Louis 239
Indianapolis Louisville 114
Indianapolis Cleveland 318
Indianapolis Detroit 290
Birmingham Memphis 249
Birmingham New Orleans 347
Birmingham Miami 777
Birmingham Louisville 378
Birmingham Washington 751
Louisville Indianapolis 114
Louisville St. Louis 264
Louisville Memphis 396
Louisville Birmingham 378
Louisville Pittsburgh 416
Louisville Washington 601
Detroit Chicago 279
Detroit Cleveland 175
Detroit Buffalo 252
Detroit Indianapolis 290
Cleveland Detroit 175
Cleveland Chicago 344
Cleveland Pittsburgh 131
Cleveland Indianapolis 318
Cleveland Buffalo 192
Pittsburgh Cleveland 131
Pittsburgh Indianapolis 360
Pittsburgh Buffalo 219
Pittsburgh Philadelphia 304
Pittsburgh Washington 241
Pittsburgh Louisville 416
Buffalo Cleveland 192
Buffalo Pittsburgh 219
Buffalo New York 436
Buffalo Boston 457
Buffalo Detroit 252
Buffalo Washington 386
Buffalo Philadelphia 383
Washington Buffalo 386
Washington Pittsburgh 241
Washington Philadelphia 140
Washington Miami 1101
Washington Louisville 601
Washington Birmingham 751
Miami Washington 1101
Miami New Orleans 892
Miami Birmingham 777
Philadelphia Washington 140
Philadelphia New York 93
Philadelphia Pittsburgh 304
Philadelphia Buffalo 383
New York Philadelphia 93
New York Boston 213
New York Buffalo 436
Boston New York 213
Boston Buffalo 457
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.stroke {
fill: none;
stroke: #000;
stroke-width: .5;
}
.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
stroke: #999;
stroke-opacity: .6;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://d3js.org/d3.geo.tile.v0.min.js"></script>
<script src="d3.mapzoom.js"></script>
<script src="dijkstra.js"></script>
<script>
var width = 900,
height = 600;
var center = [-92.4, 36.8], scale = 816;
var mapzoom = d3.mapzoom()
.center(center)
.scale(scale)
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.call(mapzoom);
var frame = svg.append("g")
mapzoom.addTileLayer(frame, "tiles.mapbox.com/v3/examples.map-zr0njcqy/", "abcd");
d3.tsv("places.tsv", function(cities) {
d3.csv("distance.csv", function(edges) {
main(cities, edges);
});
});
function main(nodes, links) {
var projection = mapzoom.projection(),
nodesByName = {}
nodes.forEach(function(d) {
d.coord = [+d.lon, +d.lat]
nodesByName[d.name] = d;
d.links = [];
});
links.forEach(function(d) {
d.source = nodesByName[d.source]
d.target = nodesByName[d.target]
d.value = +d.value;
});
var link = svg.append("g").selectAll(".link")
.data(links)
.enter().append("path")
.attr("class", "link")
.style("stroke-width", 1);
var node = svg.append("g").selectAll(".node")
.data(nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", 5)
.attr("fill", "grey")
node
.append("title")
.text(function(d) { return d.name })
mapzoom.addLayer(function() {
node
.each(function(d) { d.proj = projection(d.coord); })
.attr("transform", function(d) { return "translate(" + d.proj + ")" })
link
.attr("d", function(d) { return "M " + d.source.proj + " L " + d.target.proj });
});
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" });
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(d) {
d3.select(this)
.style("stroke-width", 10);
d.source.selection
.attr("r", 10);
d.target.selection
.attr("r", 10);
});
link.on("mouseout", function() {
d3.select(this)
.style("stroke-width", 1);
node.attr("r", 5);
});
var dijkstra = d3.dijkstra()
.nodes(nodes)
.edges(links);
var color = d3.scale.linear()
.domain([0, 1000, 2500])
.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 + " miles from " + name + ")" });
});
node.on("click", dijkstra.start);
}
</script>
name lat lon
Chicago 41.8781136 -87.6297982
Boston 42.3600825 -71.0588801
Buffalo 42.88644679999999 -78.8783689
Birmingham 33.5206608 -86.80248999999999
Cleveland 41.49932 -81.6943605
Dallas 32.7766642 -96.79698789999999
Detroit 42.331427 -83.0457538
Denver 39.7392358 -104.990251
El Paso 31.7775757 -106.4424559
Houston 29.7604267 -95.3698028
Indianapolis 39.768403 -86.158068
Kansas City 39.0997265 -94.5785667
Memphis 35.1495343 -90.0489801
Louisville 38.2526647 -85.7584557
Los Angeles 34.0522342 -118.2436849
Miami 25.7616798 -80.1917902
Minneapolis 44.977753 -93.2650108
Omaha 41.2523634 -95.99798829999999
New York 40.7127837 -74.0059413
New Orleans 29.95106579999999 -90.0715323
Philadelphia 39.9525839 -75.1652215
Salt Lake City 40.7607793 -111.8910474
St. Louis 38.6270025 -90.19940419999999
Phoenix 33.4483771 -112.0740373
Pittsburgh 40.44062479999999 -79.9958864
San Francisco 37.7749295 -122.4194155
Seattle 47.6062095 -122.3320708
Washington 38.9071923 -77.0368707
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment