Putting Dijkstra's algorithm on the map

readme.md

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.js

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
}
    

dijkstra.js

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");
};

distance.csv

index.html

<!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>

places.tsv

thumbnail.png