Simple network flooding. Click on a circle to find the network distance to the other nodes on the network. Nodes that can’t be reached will be colored gray.
This example implements a simple weighted breadth-first search to calculate distance and should work with any topojson file that has linestrings. This kind of thing is very useful for identifying areas of a network dataset that need more correcting or additional data.
<html xmlns="//www.w3.org/1999/xhtml">
<head>
<title>Simple Topojson Network Flooding</title>
<meta charset="utf-8" />
<link type="text/css" rel="stylesheet" href="d3map.css" />
<link type="text/css" rel="stylesheet" href="https://raw.githubusercontent.com/emeeks/d3-carto-map/master/examples/example.css" />
</head>
<style>
html,body {
height: 100%;
width: 100%;
margin: 0;
}
#map {
height: 100%;
width: 100%;
position: absolute;
}
.reproject {
position: absolute;
z-index: 99;
left: 50px;
top: 250px;
}
.node {
fill: blue;
stroke: black;
stroke-width: 1
}
.roads {
stroke: brown;
stroke-width: 1px;
fill: none;
}
</style>
<script>
function makeSomeMaps() {
pathSource = 0;
map = d3.carto.map();
d3.select("#map").call(map);
map.centerOn([-88,39],"latlong");
map.setScale(4);
map.refresh();
wcLayer = d3.carto.layer.tile();
wcLayer
.tileType("stamen")
.path("watercolor")
.label("Watercolor")
.visibility(true)
postLayer = d3.carto.layer.topojson();
postLayer
.path("uspost.topojson")
.label("Postal Routes")
.cssClass("roads")
.renderMode("svg")
.on("load", createMatrix);
map.addCartoLayer(wcLayer).addCartoLayer(postLayer);
function createMatrix() {
postdata = postLayer.features()
edgeList = [];
edgeMap = {};
nodes = [];
nodeHash = {};
for (x in postdata) {
var line = postdata[x].geometry.coordinates;
var lS = line[0];
var lE = line[line.length - 1];
var nA = [lS,lE];
for (y in nA) {
if (!nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)]) {
var newNode = {label: "Node " + nodes.length, id: nodes.length.toString(), coordinates: [nA[y]], x: nA[y][0], y: nA[y][1]}
nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)] = newNode;
nodes.push(newNode)
}
}
postdata[x].properties.source = nodeHash["node" + Math.ceil(lS[0] * 1000) + (lS[1] * 1000)];
postdata[x].properties.target = nodeHash["node" + Math.ceil(lE[0] * 1000) + (lE[1] * 1000)];
postdata[x].properties.cost = d3.geo.length(postdata[x]) * 6371;
}
nodeLayer = d3.carto.layer.xyArray();
nodeLayer
.features(nodes)
.label("Vertices")
.cssClass("node")
.renderMode("svg")
.x("x")
.y("y")
.markerSize(5)
.clickableFeatures(true)
.on("load", function() {d3.selectAll("circle.node").on("click", function(d) {flood(d.id)})});
map.addCartoLayer(nodeLayer);
for (x in postdata) {
if (edgeMap[postdata[x].properties.source.id]) {
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.source.id] = {};
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
if (edgeMap[postdata[x].properties.target.id]) {
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.target.id] = {};
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
}
graph = new Graph(edgeMap);
}
function flood(siteID) {
siteDistance = d3.keys(graph.map).map(function(d) {return Infinity});
siteDistance[siteID] = 0;
var map = graph.map;
var calculatedSites = [siteID];
var connectedSites = d3.keys(graph.map[siteID]);
var visitedSites = [siteID];
var sitesToVisit = [siteID];
var currentNode = siteID;
var currentCost = 0;
while (sitesToVisit.length > 0) {
sitesToVisit.splice(0,1);
for (x in connectedSites) {
if (calculatedSites.indexOf(connectedSites[x]) == -1) {
calculatedSites.push(connectedSites[x]);
siteDistance[connectedSites[x]] = currentCost + map[currentNode][connectedSites[x]];
}
else {
siteDistance[connectedSites[x]] = Math.min(currentCost + map[currentNode][connectedSites[x]], siteDistance[connectedSites[x]]);
}
if (visitedSites.indexOf(connectedSites[x]) == -1 && sitesToVisit.indexOf(connectedSites[x]) == -1) {
sitesToVisit.push(connectedSites[x]);
console.log("push")
}
}
visitedSites.push(currentNode)
//sort sitesToVisit
sitesToVisit = sitesToVisit.sort(function(a,b) {
if (siteDistance[a] < siteDistance[b])
return -1;
if (siteDistance[a] > siteDistance[b])
return 1;
return 0;
})
currentNode = sitesToVisit[0];
currentCost = siteDistance[currentNode];
connectedSites = d3.keys(graph.map[currentNode]);
}
color = d3.scale.linear().domain([0,500,3500]).range(["green","yellow","red"])
d3.selectAll("circle.node").style("fill", "lightgray")
.transition()
.delay(function(d) {return siteDistance[d.id] == Infinity ? 5000 : siteDistance[d.id] * 2})
.duration(1000)
.style("fill", function(d) {return siteDistance[d.id] == Infinity ? "gray" : color(siteDistance[d.id])})
}
}
</script>
<body onload="makeSomeMaps()">
<div id="map"></div>
<footer>
<script src="//d3js.org/d3.v3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="//d3js.org/topojson.v1.min.js" type="text/javascript">
</script>
<script src="//d3js.org/d3.geo.projection.v0.min.js" type="text/javascript">
</script>
<script src="//bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/tile.js" type="text/javascript">
</script>
<script src="//bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.quadtiles.js" type="text/javascript">
</script>
<script src="//bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.geo.raster.js" type="text/javascript">
</script>
<script src="https://rawgit.com/emeeks/d3-carto-map/master/d3.carto.map.js" type="text/javascript">
</script>
<script src="dijkstra.js" type="text/javascript">
</script>
</footer>
</body>
</html>
path,circle,rect,polygon,ellipse,line {
vector-effect: non-scaling-stroke;
}
svg, canvas {
top: 0;
}
#d3MapZoomBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 10px;
right: 50px;
}
#d3MapZoomBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
.d3MapControlsBox > button {
font-size:22px;
font-weight:900;
border: none;
height:25px;
width:25px;
background: rgba(35,31,32,.85);
color: white;
padding: 0;
cursor: pointer;
}
.d3MapControlsBox > button:hover {
background: black;
}
#d3MapPanBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 60px;
right: 50px;
}
#d3MapPanBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
#d3MapPanBox > button#left {
position: absolute;
left: -25px;
top: 10px;
}
#d3MapPanBox > button#right {
position: absolute;
right: -25px;
top: 10px;
}
#d3MapLayerBox {
position: relative;
z-index: 10;
height: 100px;
width: 120px;
top: 10px;
left: 10px;
overflow: auto;
color: white;
background: rgba(35,31,32,.85);
}
#d3MapLayerBox > div {
margin: 5px;
border: none;
}
#d3MapLayerBox ul {
list-style: none;
padding: 0;
margin: 0;
cursor: pointer;
}
#d3MapLayerBox li {
list-style: none;
padding: 0;
}
#d3MapLayerBox li:hover {
font-weight:700;
}
#d3MapLayerBox li input {
cursor: pointer;
}
div.d3MapModal {
position: absolute;
z-index: 11;
background: rgba(35,31,32,.90);
top: 50px;
left: 50px;
color: white;
max-width: 400px;
}
div.d3MapModalContent {
width:100%;
height: 100%;
overflow: auto;
}
div.d3MapModalContent > p {
padding: 0px 20px;
margin: 5px 0;
}
div.d3MapModalContent > h1 {
padding: 0px 20px;
font-size: 20px;
}
div.d3MapModalArrow {
content: "";
width: 0;
height: 0;
border-left: 20px solid transparent;
border-right: 20px solid transparent;
border-top: 20px solid rgba(35,31,32,.90);
position: absolute;
bottom: -20px;
left: 33px;
}
#d3MapSVG {
}
rect.minimap-extent {
fill: rgba(200,255,255,0.35);
stroke: black;
stroke-width: 2px;
stroke-dasharray: 5 5;
}
circle.newpoints {
fill: black;
stroke: red;
stroke-width: 2px;
}
path.newfeatures {
fill: steelblue;
fill-opacity: .5;
stroke: pink;
stroke-width: 2px;
}
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);
predecessor = predecessors[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;
})();