Mostly just notebooks about transportation and maps!
Published
Edited
Jun 19, 2021
Importers
class Network {
constructor(networkData, ODData, firstThroughNode = 0) {
this.numNodes = 0;
this.numLinks = 0;
this.firstThroughNode = firstThroughNode;
this.node = {};
this.link = {};
this.ODpair = {};
this.path = {};
this.readNodes(networkData.nodes);
this.readLinks(networkData.edges);
this.readODs(ODData);
}
ODPlot() {
var thisNet = this;
var ODnodes = Object.entries(thisNet.node).filter(n =>
this.ODData.hasOwnProperty(n[0])
);
for (let n of ODnodes) {
n[1]['total_outdemand'] = Object.entries(thisNet.ODData[n[0]]).reduce(
(a, c) => a + c[1],
0
);
}
ODnodes = Object.fromEntries(ODnodes);
const ODedges = Object.keys(thisNet.ODData)
.map(origin => {
return Object.keys(thisNet.ODData[origin]).map(dest => {
return {
source: origin,
target: dest,
demand: thisNet.ODData[origin][dest]
};
});
})
.flat();
const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]);
var streets = svg
.append('g')
.selectAll('line')
.data(Object.entries(thisNet.link))
.join('line')
.style('stroke-width', '0.5')
.style('stroke', 'lightgray')
.attr('x1', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[0];
})
.attr('y1', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[1];
})
.attr('x2', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[0];
})
.attr('y2', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[1];
});
var link = svg
.append('g')
.selectAll('path')
.data(ODedges)
.join('path')
.style('stroke-width', d => d.demand * 0.2)
.style('stroke', '#8E4848')
.style('stroke-opacity', 0.1)
.style('fill', 'transparent')
.attr('d', d => {
const sourceProj = projection(ODnodes[d.source].geometry.coordinates);
const targetProj = projection(ODnodes[d.target].geometry.coordinates);
const midpoint_x = (sourceProj[0] + targetProj[0]) / 2;
const midpoint_y = (sourceProj[1] + targetProj[1]) / 2;
const dx = targetProj[0] - sourceProj[0];
const dy = targetProj[1] - sourceProj[1];
var normalise = Math.sqrt(dx * dx + dy * dy);
const offset = 0.2 * normalise;
var offSetX = midpoint_x + offset * (dy / normalise);
var offSetY = midpoint_y - offset * (dx / normalise);
return (
`M ${sourceProj[0]},${sourceProj[1]}` +
`S ${offSetX},${offSetY} ${targetProj[0]},${targetProj[1]}`
);
});
// .attr('x1', d => {
// return projection(ODnodes[d.source].geometry.coordinates)[0];
// })
// .attr('y1', d => {
// return projection(ODnodes[d.source].geometry.coordinates)[1];
// })
// .attr('x2', d => {
// return projection(ODnodes[d.target].geometry.coordinates)[0];
// })
// .attr('y2', d => {
// return projection(ODnodes[d.target].geometry.coordinates)[1];
// });
var node = svg
.append('g')
.selectAll('circle')
.data(Object.keys(ODnodes))
.join('circle')
.attr('r', d => Math.sqrt(ODnodes[d]['total_outdemand'] * 0.1))
.attr('fill', 'firebrick')
.attr('transform', d => {
const projCoords = projection(ODnodes[d].geometry.coordinates);
return `translate(${projCoords[0]}, ${projCoords[1]}) `;
})
.on('mouseover', (event, nodeID) => {
link.style('stroke-opacity', d => {
if (d.source === nodeID) {
return 0.7;
} else {
return 0.05;
}
});
})
.on('mouseout', (event, nodeID) => {
link.style('stroke-opacity', 0.1);
});
return svg.node();
}
timePlot() {
const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]);
var thisNet = this;
var link = svg
.append('g')
.selectAll('line')
.data(Object.entries(thisNet.link))
.join('line')
.style('stroke-width', '1')
.style('stroke', d => {
return timeColor(d[1].cost);
})
.attr('x1', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[0];
})
.attr('y1', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[1];
})
.attr('x2', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[0];
})
.attr('y2', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[1];
});
svg
.append("g")
.attr("transform", `translate(${width - 220},10)`)
.append(() =>
legend({
color: timeColor,
title: 'Estimated Travel Time [s]',
width: 200
})
);
return svg.node();
}
flowPlot() {
const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]);
var thisNet = this;
var link = svg
.append('g')
.selectAll('line')
.data(Object.entries(thisNet.link))
.join('line')
.style('stroke-width', '1')
.style('stroke', d => {
return flowColor(d[1].flow);
})
.attr('x1', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[0];
})
.attr('y1', d => {
return projection(thisNet.node[d[1].head].geometry.coordinates)[1];
})
.attr('x2', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[0];
})
.attr('y2', d => {
return projection(thisNet.node[d[1].tail].geometry.coordinates)[1];
});
svg
.append("g")
.attr("transform", `translate(${width - 220},10)`)
.append(() =>
legend({
color: flowColor,
title: 'Estimated Flow [veh/peak hour]',
width: 200
})
);
return svg.node();
}
relativeGap() {
const numerator = Object.keys(this.link)
.map(ij => this.link[ij].cost * this.link[ij].flow)
.reduce((a, c) => a + c);
var denominator = 0;
for (let origin of Object.keys(this.node)) {
const matchingODpairs = Object.keys(this.ODpair).filter(
od => this.ODpair[od].origin == origin
);
if (matchingODpairs.length == 0) continue;
const [backlink, cost] = this.shortestPath(origin);
for (let od of matchingODpairs) {
let curnode = this.ODpair[od].destination;
while (curnode != this.ODpair[od].origin) {
denominator +=
this.link[backlink[curnode]].cost * this.ODpair[od].demand;
curnode = this.link[backlink[curnode]].tail;
}
}
}
return numerator / denominator - 1;
}
shiftFlows(targetFlows, stepSize) {
for (let ij of Object.keys(this.link)) {
this.link[ij].flow =
stepSize * targetFlows[ij] + (1 - stepSize) * this.link[ij].flow;
this.link[ij].updateCost();
}
}
frankWolfeStepSize(targetFlows, precision = 1e-4) {
let low = 0;
let high = 1;
let mid = 0.5;
while (high - low > precision) {
let mid = (high + low) / 2;
let zetaPrime = 0;
for (let ij of Object.keys(this.link)) {
let oldFlow = this.link[ij].flow;
this.link[ij].flow = mid * targetFlows[ij] + (1 - mid) * oldFlow;
zetaPrime +=
this.link[ij].calculateCost() * (targetFlows[ij] - oldFlow);
this.link[ij].flow = oldFlow;
}
if (zetaPrime > 0) {
high = mid;
} else {
low = mid;
}
}
return mid;
}
userEquilibrium(maxIterations = 10, targetGap = 1e-6, stepSizeRule = 'MSA') {
const initialFlows = this.allOrNothing();
for (let ij of Object.keys(this.link)) {
this.link[ij].flow = initialFlows[ij];
this.link[ij].updateCost();
}
let iteration = 0;
while (iteration < maxIterations) {
iteration += 1;
const gap = this.relativeGap();
if (gap < targetGap) {
break;
}
const targetFlows = this.allOrNothing();
let stepSize = 0;
if (stepSizeRule === 'FW') {
stepSize = this.frankWolfeStepSize(targetFlows);
} else if (stepSizeRule === 'MSA') {
stepSize = 1 / (iteration + 1);
} else {
throw Error('Bad Network Operation');
}
this.shiftFlows(targetFlows, stepSize);
}
}
allOrNothing() {
var aON = {};
for (let ij of Object.keys(this.link)) {
aON[ij] = 0;
}
for (let origin of Object.keys(this.node)) {
const matchingODpairs = Object.keys(this.ODpair).filter(
od => this.ODpair[od].origin == origin
);
if (matchingODpairs.length == 0) continue;
const [backlink, cost] = this.shortestPath(origin);
for (let od of matchingODpairs) {
let curnode = this.ODpair[od].destination;
if (backlink[curnode] === NO_PATH_EXISTS) {
continue;
}
while (curnode != this.ODpair[od].origin) {
aON[backlink[curnode]] += this.ODpair[od].demand;
curnode = this.link[backlink[curnode]].tail;
}
}
}
return aON;
}
beckmannFunction() {
var beckmann = 0;
for (let ij of Object.keys(this.link)) {
beckmann += this.link[ij].calculateBeckmannComponent();
}
return beckmann;
}
acyclicShortestPath(origin) {
var backlink = {};
var cost = {};
for (let i of Object.keys(this.node)) {
backlink[i] = NO_PATH_EXISTS;
cost[i] = INFINITY;
}
cost[origin] = 0;
for (
let topoNode = this.node[origin].order + 1;
topoNode < this.numNodes + 1;
topoNode++
) {
const i = this.topologicalList[topoNode];
for (let hi of this.node[i].reverseStar) {
const h = this.link[hi].tail;
if (h < this.firstThroughNode && h != origin) {
continue;
}
const tempCost = cost[h] + this.link[hi].cost;
if (tempCost < cost[i]) {
cost[i] = tempCost;
backlink[i] = hi;
}
}
}
return [backlink, cost];
}
shortestPath(origin) {
var backlink = {};
var cost = {};
for (let i of Object.keys(this.node)) {
backlink[i] = NO_PATH_EXISTS;
cost[i] = INFINITY;
}
cost[origin] = 0;
var scanList = this.node[origin].forwardStar.map(ij => this.link[ij].head);
while (scanList.length > 0) {
const i = scanList[0];
scanList.shift();
let labelChanged = false;
for (let hi of this.node[i].reverseStar) {
const h = this.link[hi].tail;
if (h < this.firstThroughNode && h != origin) {
continue;
}
let tempCost = cost[h] + this.link[hi].cost;
if (tempCost < cost[i]) {
cost[i] = tempCost;
backlink[i] = hi;
labelChanged = true;
}
}
if (labelChanged) {
scanList.push(
...this.node[i].forwardStar
.map(ij => this.link[ij].head)
.filter(n => !scanList.includes(n))
);
}
}
return [backlink, cost];
}
findLeastEnteringLinks() {
var leastEnteringLinks = this.numLinks + 1;
var leastEnteringNode = null;
for (let i of Object.keys(this.node)) {
if (this.node[i].reverseStar.length < leastEnteringLinks) {
leastEnteringLinks = this.node[i].reverseStar.length;
leastEnteringNode = i;
}
}
return leastEnteringNode;
}
findTopologicalOrder() {
let numOrderedNodes = 0;
while (numOrderedNodes < this.numNodes) {
let nextNode = this.findLeastEnteringLinks();
if (!this.node.hasOwnProperty(nextNode)) {
return numOrderedNodes;
}
if (this.node[nextNode].reverseStar.length > 0) {
throw Error('Bad Network Operation');
}
numOrderedNodes += 1;
this.node[nextNode].order = numOrderedNodes;
this.node[nextNode].reverseStar = Array(this.numLinks);
for (let i = 0; i < this.numLinks; i++) {
this.node[nextNode].reverseStar[i] = 0;
}
for (let ij of this.node[nextNode].forwardStar) {
const headNode = this.link[ij].head;
this.node[headNode].reverseStar = this.node[
headNode
].reverseStar.filter(
l => this.link[l].tail.toString() !== nextNode.toString()
);
}
}
//fix the reverse stars
for (let i of Object.keys(this.node)) {
this.node[i].reverseStar = [];
}
for (let ij of Object.keys(this.link)) {
this.node[this.link[ij].head].reverseStar.push(ij);
}
}
createTopologicalList() {
let sortedList = Object.keys(this.node)
.map(n => [n, this.node[n]])
.sort((nPair, mPair) => {
return nPair[1].order - mPair[1].order;
})
.map(nPair => nPair[0]);
sortedList.unshift(NO_PATH_EXISTS);
this.topologicalList = sortedList;
}
loadPaths() {
/*
This method should take given values of path flows (stored in the
self.path[].flow attributes), and do the following:
1. Set link flows to correspond to these values (self.link[].flow)
2. Set link costs based on new flows (self.link[].cost), see link.py
3. Set path costs based on new link costs (self.path[].cost), see path.py
*/
for (let ij of Object.keys(this.link)) {
this.link[ij].flow = 0;
}
for (let p of Object.keys(this.path)) {
for (let ij of Object.keys(this.path[p].links)) {
this.link[ij].flow += this.path[p].flow;
}
}
for (let ij of Object.keys(this.link)) {
this.link[ij].updateCost();
}
for (let p of Object.keys(this.path)) {
this.path[p].updateCost();
}
}
readODs(ODData) {
this.ODData = ODData;
for (let origin of Object.keys(ODData)) {
for (let dest of Object.keys(ODData[origin])) {
this.ODpair[`${origin}->${dest}`] = new OD(
origin,
dest,
ODData[origin][dest]
);
}
}
}
readNodes(nodeData) {
nodeData.forEach(n => {
this.node[n.id] = new Node(n.geometry, n.is_zone ? true : false);
this.numNodes += 1;
});
}
readLinks(linkData) {
// length is in units of feet, so we have to do some dimensional analysis to get travel time in seconds
// I am going to very loosely go for flows per hour, but I am a scrub so for right now
// it is gonna be proportional to the speed limit
linkData.forEach(e => {
if (
!this.node.hasOwnProperty(e.source) ||
!this.node.hasOwnProperty(e.target)
) {
return;
}
const linkID = `(${e.source},${e.target})`;
if (this.link.hasOwnProperty(linkID)) {
return;
}
this.link[linkID] = new Link(
e.target,
e.source,
300,
(e.len_div_splim * 3600) / 5280
);
this.node[e.source].forwardStar.push(linkID);
this.node[e.target].reverseStar.push(linkID);
if (this.link[linkID] !== undefined) {
this.numLinks += 1;
}
});
}
}
import { Button } from '@observablehq/inputs'
import { legend, swatches } from "@d3/color-legend"
d3 = require('d3', 'd3-geo')
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
