Skip to content

Instantly share code, notes, and snippets.

@alexhornbake

alexhornbake/chapter7.js

Last active December 19, 2015 15:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alexhornbake/5980804 to your computer and use it in GitHub Desktop.
Save alexhornbake/5980804 to your computer and use it in GitHub Desktop.
Download ZIP
Shortest Route Hiva 'Oa Map
Raw
chapter7.js
// Visualization of the Hiva 'Oa map in chapter 7 of
// 'Eloquent Javascript' by Marijn Haverbeke
// see original example at http://eloquentjavascript.net/
// for more detail on everything below noted as "Original example from text" in chapter7.js
//BEGIN ORIGINAL EXAMPLE FROM TEXT
var roads = {};
function makeRoad(from, to, length)
{
function addRoad(from, to)
{
if(!(from in roads))
roads[from] = [];
roads[from].push({to: to, distance: length});
}
addRoad(from, to);
addRoad(to, from);
}
function makeRoads(start)
{
for ( var i = 1; i < arguments.length; i+=2)
makeRoad(start,arguments[i],arguments[i+1]);
}
function roadsFrom(place) {
var found = roads[place];
if (found == undefined)
throw new error("No place named '"+place+"' found.");
else
return found;
}
function printRoads(start)
{
var temp = roadsFrom(start);
for( var x in temp)
console.log(temp[x]);
}
function member(array, value) {
for(var x in array){
if(array[x] === value) return true;
}
return false;
}
function possibleRoutes(from, to) {
function findRoutes(route) {
function notVisited(road) {
return !member(route.places, road.to);
}
function continueRoute(road) {
return findRoutes({places: route.places.concat([road.to]), length: route.length + road.distance});
}
var end = route.places[route.places.length - 1];
if (end == to)
return [route];
else
return flatten(map(continueRoute, filter(notVisited,roadsFrom(end)) ) );
}
return findRoutes({places: [from], length: 0});
}
function shortestRoute(from,to) {
var currentShortest = null;
forEach(possibleRoutes(from,to), function(route){
if(!currentShortest || currentShortest.length > route.length)
currentShortest = route;
});
return currentShortest;
}
//Load data in to our map
makeRoads("Point Kiukiu", "Hanaiapa", 19, "Mt Feani", 15, "Taaoa", 15);
makeRoads("Airport", "Hanaiapa", 6, "Mt Feani", 5, "Atuona", 4, "Mt Ootua", 11);
makeRoads("Mt Temetiu", "Mt Feani", 8, "Taaoa", 4);
makeRoads("Atuona", "Taaoa", 3, "Hanakee Pearl Lodge", 1);
makeRoads("Cemetery", "Hanakee Pearl Lodge", 6, "Mt Ootua", 5);
makeRoads("Hanapaoa", "Mt Ootua", 3);
makeRoads("Puamua", "Mt Ootua", 13, "Point Teohotepapapa", 14);
//END ORIGINAL EXAMPLE FROM TEXT
Raw
chapter7Viz.js
//Setup Some Parameters
var mapWidth = 640;
var mapHeight = 260;
var nodeSize = 7;
var mapRoads = [];
var placeKeys = [];
var shortRoute = {};
var to = "",
from = "";
//Note: these data points were generated by tracing the map example by hand in illustrator, and exporting an SVG.
var mapLocations = [{x:11.062, y:118.5, id:"Point Kiukiu" },
{x:230.062, y:35.5, id:"Hanaiapa" },
{x:150.062, y:111.5, id:"Mt Feani" },
{x:150.062, y:224.5, id:"Taaoa" },
{x:206.062, y:104.5, id:"Airport" },
{x:177.062, y:173.5, id:"Atuona" },
{x:311.062, y:114.5, id:"Mt Ootua" },
{x:131.062, y:173.5, id:"Mt Temetiu" },
{x:213.062, y:166.5, id:"Hanakee Pearl Lodge" },
{x:297.062, y:163.5, id:"Cemetery" },
{x:319.062, y:74.5, id:"Hanapaoa" },
{x:425.062, y:97.5, id:"Puamua" },
{x:549.062, y:101.5, id:"Point Teohotepapapa"}];
var mapOutline = "387.562,173.5 393.062,165 407.562,173.5 414.062,165 432.062,165 466.062,140 476.062,140 512.062,117.5 530.562,120.5 560.812,108.5 556.562,98.75 574.062,71.5 547.562,66.5 547.562,84.5 535.062,98.75 512.062,100.669 501.062,114 491.562,113.5 491.562,113.5 491.562,102.5 492.062,102.588 455.062,98.75 440.062,108.5 432.062,104.5 438.729,86.168 419.062,66 373.562,61 311.562,66.5 302.062,15.75 277.562,0 253.562,3 236.062,12 232.062,28 195.062,9 175.562,22.5 175.562,28.5 175.562,28 138.062,56 124.063,55.5 125.562,66.5 125.562,66.5 113.062,66 99.062,84.5 92.062,74.5 55.062,85 44.562,84.5 44.562,84.5 39.812,105 22.938,92.5 0,117.5 16.562,139.5 16.562,162.5 60.062,213.5 99.062,235 140.562,243 164.688,258.5 189.062,245.5 187.188,235 161.562,225.5 156.812,216 172.562,183.5 185.312,181 189.062,175 210.062,175 210.062,175 236.062,181 244.812,174.5 253.062,181 265.062,181 265.562,181 280.562,168 316.562,174 332.062,162.5 352.062,173.5 370.062,169.25 377.062,174 387.062,174";
//Get all possible places, we need this to lookup roads, and to load in to our selection form
for(var temp in roads) placeKeys.push(temp);
// Get our Links between Nodes/Places
// Nodes, and PlaceKeys are in the same order, so we can lookup via the index and for our purposes assume they are 1:1
forEach(mapLocations, function(place){
forEach(roads[place.id], function(road) {
mapRoads.push({source: place, target: mapLocations[placeKeys.indexOf(road.to)], dist: road.distance});
});
});
//Translate the results of the Shortest path finder in to a friendlier format for D3 to visualize
//lookup all of the places in our roads object, and calculate distances from last place, and from start
function convertRoute(route)
{
var newRoute = [];
var lastPlace = "";
map(function(place){
newRoute.push({place: place, distanceFromLast: 0, distanceFromStart: 0});
if(roads[lastPlace]) {
forEach(roads[lastPlace],function(element){
if(element.to == place) {
newRoute[newRoute.length-1].distanceFromLast = element.distance;
newRoute[newRoute.length-1].distanceFromStart = newRoute[newRoute.length-2].distanceFromStart + element.distance;
}
});
}
lastPlace = place;
},route.places);
return newRoute;
}
//Visualize the Shortest Path on a subway style Route Map
function drawStraightRoute(){
var shortPath = convertRoute(shortRoute);
//Clear out the old SVG if one exists.
d3.select("#routeContainer").selectAll("svg").remove();
//Setup our chart size, radius of nodes, padding, and textSize
var w = 640,
h = 150,
r = 6,
lp = 20, //padding for left side of chart range
//padding for right, HACK way to make sure text labels aren't clipped.
//the "correct" solution might be to draw the entire chart off screen check for clipping, then redraw on-screen.
rp = 100,
xAx = h/3 + .5, // axis height
textSize = 12;
var x = d3.scale.linear()
.domain([0, shortRoute.length])
.range([r+lp, w-rp]);
//Quantize scale to avoid overlaps
function fit(val){
var scaled = x(val);
return scaled-scaled%((r*2));
}
//Create the SVG needed to display the route
var chart = d3.select("#routeContainer").append("svg")
.attr("width", w)
.attr("height", h);
//Create the circles that will represent our map points
var node = d3.select("#routeContainer").select("svg").selectAll("circle")
.data(shortPath);
//Create the text labels for the node names
var placeLabel = d3.select("#routeContainer").select("svg").selectAll("text")
.data(shortPath);
var distanceLabel = d3.select("#routeContainer").select("svg").selectAll("distanceLabel")
.data(shortPath);
var distancePath = d3.select("#routeContainer").select("svg").selectAll("distancePath")
.attr("class","distancePath")
.data(shortPath);
// Enter…
node.enter().append("circle")
.attr("class","routeNode")
.attr("cx",function(d) {
return fit(d.distanceFromStart);})
.attr("cy",xAx)
.attr("r",r);
placeLabel.enter().append("text")
.attr("class","placeLabel")
.style("text-anchor","start")
.style("font-size",textSize + "px")
.text(function(d) {return d.place})
.attr("transform",function(d) { return "translate(" + (fit(d.distanceFromStart) + r/2 ) + ", " + (xAx + r + (textSize/2)) + ") rotate(45)"; });
distanceLabel.enter().append("text")
.attr("class","distanceLabel")
.style("text-anchor","middle")
.style("font-size", textSize*.8 + "px")
.text(function(d) {return d.distanceFromLast})
.attr("transform",function(d) {
if(d.distanceFromLast != 0)
return "translate(" + ((fit(d.distanceFromStart - d.distanceFromLast) + fit(d.distanceFromStart))/2.0) + ", " + (xAx - 4*r - 5) + ")";
// return "translate(" + (fit(d.distanceFromStart - d.distanceFromLast) + (fit(d.distanceFromStart) - fit(d.distanceFromStart - d.distanceFromLast))/2.0) + ", " + (xAx - 4*r - 5) + ")";
else return ""});
distancePath.enter().append("path")
.attr("class","distancePath")
.attr("d",function(d){
if(d.distanceFromLast != 0) {
var a = d.distanceFromStart;
var b = d.distanceFromLast;
//Path definition for curly brackets
return ("M " + fit(a) + " " + (xAx-r) +
" Q " + fit(a) + " " + (xAx-2*r) + " " + (fit(a) - .25*(fit(a)-fit(a-b))) + " " + (xAx -2*r) +
" T " + ((fit(a - b) + fit(a))*.5) + " " + (xAx-4*r) +
" M " + (fit(a - b)) + " " + (xAx-r) +
" Q " + (fit(a - b)) + " " + (xAx-2*r) + " " + (fit(a) - .75*(fit(a)-fit(a-b))) + " " + (xAx - 2*r) +
" T " + ((fit(a - b) + fit(a))*.5) + " " + (xAx-4*r));
}
else return });
// Exit…
node.exit().remove();
placeLabel.exit().remove();
distanceLabel.exit().remove();
distancePath.exit().remove();
}
function nodeClicked(place)
{
d3.select("#" + removeWhiteSpace(place)).attr("class","mapNodeActive");
from = to;
to = place;
if (from != "") {
shortRoute = shortestRoute(from,to);
updateMap();
drawStraightRoute();
}
}
function updateMap()
{
//reset our highlighted styles
d3.selectAll(".mapLinkActive").attr("class","mapLink");
d3.selectAll(".mapNodeActive").attr("class","mapNode");
var lastPlace = "";
forEach(shortRoute.places, function(place){
d3.select("#" + removeWhiteSpace(place)).attr("class","mapNodeActive");
//Try both directions to find link
d3.select("#" + removeWhiteSpace(place) + "-" + removeWhiteSpace(lastPlace)).attr("class","mapLinkActive");
d3.select("#" + removeWhiteSpace(lastPlace) + "-" + removeWhiteSpace(place)).attr("class","mapLinkActive");
lastPlace = place;
});
}
function drawMap()
{
var svg = d3.select("#mapContainer").append("svg")
.attr("width", mapWidth)
.attr("height", mapHeight);
var outline = d3.select("#mapContainer").select("svg")
.append("polyline")
.attr("points",mapOutline)
.attr("class","mapOutline");
var nodes = d3.select("#mapContainer").select("svg").selectAll("mapNode")
.attr("class", "mapNode").data(mapLocations);
var links = d3.select("#mapContainer").select("svg").selectAll("mapLinks")
.attr("class", "mapLinks").data(mapRoads);
var labels = d3.select("#mapContainer").select("svg").selectAll("mapLabels")
.attr("class", "mapLabels").data(mapLocations);
links.enter().append("line")
.attr("class","mapLink")
.attr("id",function(d){ return removeWhiteSpace(d.source.id) + "-" + removeWhiteSpace(d.target.id);})
.attr("x1",function(d){ return d.source.x;})
.attr("y1",function(d){ return d.source.y;})
.attr("x2",function(d){ return d.target.x;})
.attr("y2",function(d){ return d.target.y;});
nodes.enter().append("circle")
.attr("class","mapNode")
.attr("id",function(d){ return removeWhiteSpace(d.id);})
.attr("cx",function(d){ return d.x;})
.attr("cy",function(d){ return d.y;})
.attr("r", nodeSize)
.on("click", function(d) { nodeClicked(d.id); });
labels.enter().append("text")
.attr("class","mapLabels")
.text(function(d){ return d.id;})
.style("text-anchor", function(d){
if(d.x < 100) return "start"; // Hack to prevent label clipping
if(d.x > 400) return "end"; // Hack to prevent label clipping
else return "middle";
})
.attr("transform", function(d){
if(d.id == "Hanakee Pearl Lodge") return "translate(" + d.x + ", " + (d.y - 10) + ")"; // Hack to prevent label overlap
return "translate(" + d.x + ", " + (d.y + 14) + ")";});
outline.exit().remove();
links.exit().remove();
nodes.exit().remove();
}
function removeWhiteSpace(str)
{
return str.replace(/\s/g, '');
}
drawMap();
Raw
eloquentUtils.js
//Utility Functions to make JS more Functional
var op = {
"+": function(a, b){return a + b;},
"==": function(a, b){return a == b;},
"===": function(a, b){return a === b;},
"!": function(a){return !a;}
/* and so on */
};
function asArray(quasiArray, start) {
var result = [];
for (var i = (start || 0); i < quasiArray.length; i++)
result.push(quasiArray[i]);
return result;
}
function partial(func) {
var fixedArgs = asArray(arguments, 1);
return function(){
return func.apply(null, fixedArgs.concat(asArray(arguments)));
};
}
var Break = {toString: function() {return "Break";}};
function forEach(array, action) {
try {
for (var i = 0; i < array.length; i++)
action(array[i]);
}
catch (exception) {
if (exception != Break)
throw exception;
}
}
function reduce(combine, base, array) {
forEach(array, function (element) {
base = combine(base, element);
});
return base;
}
function map(func, array) {
var result = [];
forEach(array, function (element) {
result.push(func(element));
});
return result;
}
function any(test, array) {
for (var i = 0; i < array.length; i++) {
var found = test(array[i]);
if (found)
return found;
}
return false;
}
function every(test, array) {
for (var i = 0; i < array.length; i++) {
var found = test(array[i]);
if (!found)
return found;
}
return true;
}
function member(array, value) {
return any(partial(op["==="], value), array);
}
function flatten(arrays) {
var result = [];
forEach(arrays, function (array) {
forEach(array, function (element){result.push(element);});
});
return result;
}
function filter(test, array) {
var result = [];
forEach(array, function (element) {
if (test(element))
result.push(element);
});
return result;
}
function minimise(func, array) {
var minScore = null;
var found = null;
forEach(array, function(element) {
var score = func(element);
if (minScore == null || score < minScore) {
minScore = score;
found = element;
}
});
return found;
}
function getProperty(propName) {
return function(object) {
return object[propName];
};
}
Raw
index.html
<!-- Visualization of the Hiva 'Oa map in chapter 7 of
'Eloquent Javascript' by Marijn Haverbeke
see original example at http://eloquentjavascript.net/
for more detail on everything below noted as "Original example from text" in chapter7.js -->
<html>
<title>Eloquent JS, Chapter 7 Visualization</title>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script type="text/javascript" src="eloquentUtils.js"></script>
<script type="text/javascript" src="chapter7.js"></script>
<style>
body {
background: #f4f4f4;
font-family: Arial, Helvetica, sans-serif;
}
#routeContainer {
text-align: center;
}
#mapContainer {
text-align: center;
}
.routeNode {
fill: #4682B4;
stroke: #4A4A4A;
}
.distancePath {
stroke: #666666;
stroke-width: 1px;
fill: none;
}
.mapOutline {
fill: #ADC980;
stroke: #E6E690;
stroke-width: 3px;
}
.mapLink {
stroke:#999999;
stroke-width: .5px;
}
.mapNode {
fill: #666666;
stroke-width: .5px;
}
.mapLinkActive {
fill:#4682B4;
stroke:#000000;
stroke-width:.5px;
}
.mapNodeActive {
fill:#4682B4;
stroke:#000000;
stroke-width:.5px;
}
.mapLabels {
font-size: 10px;
}
p {
text-align: center;
font-size: .8em;
}
</style>
<body>
<p>Click on two points to find the shortest path (cost, not distance) between. See original example at <a target="_top" href="http://eloquentjavascript.net/chapter7.html">eloquentjavascript.net</a></p>
<div id="mapContainer"></div>
<div id="routeContainer"></div>
<script type="text/javascript" src="chapter7Viz.js"></script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment