block by emeeks b8da1d56fd9c21244fdd

Simple Network Flooding

Full Screen

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.

index.html

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

d3map.css

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

dijkstra.js

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;

})();