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 |
