3e:null 3f:["$","title",null,{"children":"Routing dollars | Ruzgar Imski | Observable"}] 45:T526,allFlows = { const context = DOM.context2d(width, height); context.fillStyle = "white"; context.fillRect(0, 0, width, height); const path = d3.geoPath(projection, context).pointRadius(15); context.beginPath(); for (const o of data.polygones) d3.geoPath(projection).context(context)(o.geom); context.strokeStyle = "black"; context.lineWidth = 0.2; context.stroke(); for (let i = 0; i < regions.length; i++) { for (let j = 0; j < regions.length; j++) { if (i !== j && data.OD[i][j] > 0) { context.beginPath(); context.lineWidth = data.OD[i][j] / 100; path({ type: "LineString", coordinates: [points[j], points[i]] }); context.stroke(); } } } for (let i = 0; i < points.length; i++) { context.beginPath(); const r = 14; const A = projection(points[i]); context.moveTo(A[0] + r, A[1]); context.arc(...A, r, 0, 2 * Math.PI); context.fillStyle = "#333"; context.fill(); context.lineJoin = "round"; context.textAlign = "center"; context.strokeStyle = "white"; context.lineWidth = 4; context.strokeText(regions[i], ...projection(points[i])); context.fillStyle = "black"; context.fillText(regions[i], ...projection(points[i])); } return context.canvas; }46:T547,{ const context = DOM.context2d(width, height); context.fillStyle = "white"; context.fillRect(0, 0, width, height); const path = d3.geoPath(projection, context); context.beginPath(); for (const o of data.polygones) d3.geoPath(projection).context(context)(o.geom); context.strokeStyle = "black"; context.lineWidth = 0.2; context.stroke(); for (let i = 0; i < regions.length; i++) { for (let j = 0; j < regions.length; j++) { if (i !== j && data.OD[i][j] > 0) { context.beginPath(); context.lineWidth = data.OD[i][j] / 100; path({ type: "LineString", coordinates: [points[j], points[i]] }); context.stroke(); } } } for (let i = 0; i < points.length; i++) { context.beginPath(); const r = radius(Math.abs(balance[i])); const A = projection(points[i]); context.moveTo(A[0] + r, A[1]); context.arc(...A, r, 0, 2 * Math.PI); context.fillStyle = balance[i] < 0 ? "orange" : "steelblue"; context.fill(); context.lineJoin = "round"; context.textAlign = "center"; context.strokeStyle = "white"; context.lineWidth = 4; context.strokeText(regions[i], ...projection(points[i])); context.fillStyle = "black"; context.fillText(regions[i], ...projection(points[i])); } return context.canvas; }47:T424,Let’s focus on the Boston region for a moment. It was the source of 1,300 notes that ended up to be counted in the Dallas region. But instead of shipping these notes directly (say, by plane), we can suppose that they travelled through some other regions. They might have been taken from Boston to San Francisco, then Cleveland, then Dallas. We don’t know their exact routes, but we can make a guess: that “most” of the trafic passed by a kind of shortest route. So, Boston → New York → Philadelphia → Cleveland → St. Louis → Dallas seems like a good bet for these 1,300 notes, or at least, it makes more sense than another, wiggly path. The list of the shortest paths from Boston to any of the other regions is an optimal tree 🎄. And we can distribute all the notes originating from Boston along the branches of that tree. Next, we can compute an optimal tree from each of the 12 regions (that is, an optimal forest 🌲 🌳 🎄), and add all the flows. This results in a the much simpler (summary) matrix and distribution system:48:T62c,{ const smin = 0; // use e.g. 80 to discard small flows const context = DOM.context2d(width, height); context.fillStyle = "white"; context.fillRect(0, 0, width, height); context.beginPath(); for (const o of data.polygones) d3.geoPath(projection).context(context)(o.geom); context.strokeStyle = "black"; context.lineWidth = 0.2; context.stroke(); for (const [i, j] of links) { const s = flows.get(`${i}-${j}`) - flows.get(`${j}-${i}`); if (i === j || s <= smin) continue; context.beginPath(); // draw a triangle from i to j with width s const A = projection(points[i]); const B = projection(points[j]); const N = [B[1] - A[1], A[0] - B[0]]; const n = Math.hypot(...N); const C = N.map((d) => ((d / n) * s) / 50); context.moveTo(...A); context.lineTo(B[0] + C[0], B[1] + C[1]); context.lineTo(B[0] - C[0], B[1] - C[1]); context.fillStyle = "#333"; context.fill(); } for (let i = 0; i < points.length; i++) { context.beginPath(); const r = radius(Math.abs(balance[i])); const A = projection(points[i]); context.moveTo(A[0] + r, A[1]); context.arc(...A, r, 0, 2 * Math.PI); context.fillStyle = balance[i] < 0 ? "orange" : "steelblue"; context.fill(); context.lineJoin = "round"; context.textAlign = "center"; context.strokeStyle = "white"; context.lineWidth = 4; context.strokeText(regions[i], ...projection(points[i])); context.fillStyle = "black"; context.fillText(regions[i], ...projection(points[i])); } return context.canvas; }49:[{"id":"2457d244bae60bbd756fb26bbc782c7cf46cc97a77996f71f5e9b583c0544a74f68ecf587e64714b5f3dae37c508464671cbacadaeb5037c2ce0bfd418c84e4a","href":"https://static.observableusercontent.com/files/2457d244bae60bbd756fb26bbc782c7cf46cc97a77996f71f5e9b583c0544a74f68ecf587e64714b5f3dae37c508464671cbacadaeb5037c2ce0bfd418c84e4a","name":"dollars.json","type":"application/json","lastModified":1705130301847.099,"size":3092}] 43:{"id":"c8076efa91a04b89","slug":null,"title":"Routing dollars","thumbnail":"c170590e529bc62a67767d71610f536635fadb684cfd24431bcec9e4a8364546","access_level":"public","create_time":"$D2024-01-13T07:18:21.847Z","update_time":"$D2024-01-13T07:18:21.847Z","view_time":null,"first_public_time":"$D2024-01-13T07:18:21.847Z","has_unpublished_edits":null,"fork":{"id":"825e5d5362e01b27","slug":"routing-dollars","title":"Routing dollars","owner":{"id":"166c5a16a7264bea","login":"visionscarto","name":"Visionscarto"}},"stars":0,"starred":false,"owner":{"type":"team","id":"62eaf79b101c4021","login":"mondano","name":"Ruzgar Imski","avatar_url":"https://avatars-next.observableusercontent.com/77349a6cb8957792df3c6651144ca808d40794c15df75040d13e6d6387841d04","tier":"starter_2024","bio":"","following":false},"version":763,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"97ed911fd2a1208e","login":"mondano","name":"Ruzgar Imski","avatar_url":"https://avatars-next.observableusercontent.com/77349a6cb8957792df3c6651144ca808d40794c15df75040d13e6d6387841d04","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"97ed911fd2a1208e","login":"mondano","name":"Ruzgar Imski","avatar_url":"https://avatars-next.observableusercontent.com/77349a6cb8957792df3c6651144ca808d40794c15df75040d13e6d6387841d04","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Routing dollars","cells":[{"id":585,"value":"# Routing dollars\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"*#30DayMapChallenge — Day 20. Movement.*\n\nThe inspiration for this map comes from Waldo Tobler, “A Model of Geographical Movement,” *Geographical Analysis,* 13: 1-20 (1981) [[PDF](https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1538-4632.1981.tb00711.x)]. My friends from the “[tribute to Tobler](https://neocarto.hypotheses.org/ttt-tobler)” project shared the data —which was collected by S. Pignatello in 1976— on their [github page](https://github.com/tributetotobler).\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"The story is the following: the United States has 12 Federal Reserve Bank (FRB) regions that issue $1 notes. [A specific mark on each note](https://www.uscurrency.gov/denominations/bank-note-identifiers) indicates its provenance. As customers travel around, they carry money and spend it, and the notes diffuse in the country. By *counting* the notes observed in stores in each of the 12 regions, one can establish an origin/destination matrix, indicating how many notes issued in Boston end up in Chicago, etc. The matrix looks like this:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":299,"value":"Inputs.table(\n regions.map((from, i) =>\n Object.assign(\n { \"↓from / to→\": from },\n Object.fromEntries(regions.map((to, j) => [to, data.OD[i][j]]))\n )\n ),\n {\n rows: 13,\n layout: \"fixed\",\n width: { \"↓from / to→\": 90 }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"*Note: numbers in hundreds.*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":341,"value":"We can map all the flows (remark: the points describe the FRB regions, not the cities!). Of course, it’s hard to make sense of what’s happening. In particular we have no idea in which directions the money flows.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":326,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":295,"value":"In the referenced article, Tobler offers several solutions to that problem. The first insight is that we can simplify this map quite a bit by identify “sources” (that print more money than they use) and “sinks” (that use more notes than they print). For this, we compute the balances:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"// compute the balance of dollar notes as the difference between\n// the sum of the rows and the sum of the columns of the OD matrix\nbalance = {\n const outs = data.OD.map((l) => d3.sum(l));\n const ins = d3.transpose(data.OD).map((l) => d3.sum(l));\n return d3.zip(ins, outs).map(([in_, out_]) => in_ - out_);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":348,"value":"Inputs.table(\n regions.map((region, i) => ({ region, balance: balance[i] })),\n { rows: 13, width: 230 }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":749,"value":"*Note: numbers in hundreds.*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":367,"value":"This balance table shows that Boston is “attracting” dollar notes (using more than it issues), and New York is “exporting” them. We can represent the balance on the map, with orange dots for sources, and blue dots for sinks.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"$47","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":369,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"viewof exponent = Inputs.range([1, 5], {\n label: \"exponent\",\n value: 2,\n step: 0.1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":570,"value":"*…and that’s my map for today!*\n\nThe simplified matrix is very sparse:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":604,"value":"Inputs.table(\n regions.map((from, i) =>\n Object.assign(\n { \"↓from / to→\": from },\n Object.fromEntries(\n regions.map((to, j) => {\n const diff = flows.get(`${i}-${j}`) - flows.get(`${j}-${i}`);\n return [to, i === j ? 0 : diff > 0 ? diff : -1];\n })\n )\n )\n ),\n {\n rows: 13,\n layout: \"fixed\",\n width: { \"↓from / to→\": 90 },\n format: Object.fromEntries(\n regions.map((d) => [\n d,\n (v) => (v > 0 ? d3.format(\",\")(v) : v === 0 ? \"•\" : \"\")\n ])\n )\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":752,"value":"*Note: numbers in hundreds.*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":398,"value":"## Routing algorithm\n\nWe’re going to create a graph connecting all the regions, and will use [Dijkstra](https://observablehq.com/@fil/dijkstra)’s algorithm to find the cheapest route. To make this work, we need the actual cost of going from one region to increase non-linearly with the distance, so that using an intermediate stop is easier than taking the straight line. Hence the exponent in the following cost factor, which can be anything starting from 1 (which uses all the direct routes, *i.e.* no simplification).\n\n(A variant, that would be easier to scale if we had more points, would be to start with a [Delaunay](https://github.com/d3/d3-delaunay), [Urquhart](https://observablehq.com/@fil/the-urquhart-graph) or [Gabriel](https://observablehq.com/@visionscarto/world-cities-gabriel) graph; but we don't need to complicate things here, since we only have 12 regions.)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":402,"value":"factor = (i, j) => {\n const distance = Math.hypot(\n points[i][0] - points[j][0],\n points[i][1] - points[j][1]\n );\n return Math.pow(distance, exponent);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":468,"value":"The graph is symmetric, from any point to any other point, using that cost factor:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":279,"value":"links = d3\n .cross(d3.range(points.length), d3.range(points.length))\n .filter(([i, j]) => i !== j)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"graph = ({\n sources: Uint16Array.from(links, ([i]) => i),\n targets: Uint16Array.from(links, ([, j]) => j),\n costs: links.map(([i, j]) => factor(i, j))\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":480,"value":"We solve it for each of the regions, and add all the flows on each step of the way: ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"flows = {\n const A = new Map();\n\n // compute the best tree from each starting point\n for (let i = 0; i < regions.length; i++) {\n const tree = [...shortest_tree({ graph, origins: [i] })].pop();\n\n for (let j = 0; j < regions.length; j++) {\n const p = data.OD[i][j];\n let l;\n let k = j;\n while ((l = tree.predecessor[k]) > -1) {\n A.set(`${l}-${k}`, (A.get(`${l}-${k}`) || 0) + p);\n k = l;\n }\n }\n }\n\n return A;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":757,"value":"Last remark: this algorithm does take a few cues from Tobler’s original article, but should not be considered as an implementation of the paper. It is just my way of reading it and experimenting with the proposed concepts. Thank you for reading! Send suggestions!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":490,"value":"---\n*data and tooling*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"// https://raw.githubusercontent.com/tributetotobler/ttt/main/data/dollars.json\ndata = FileAttachment(\"dollars.json\").json()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"points = data.coords.map(({ V2, V4 }) => [V2, V4])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"regions = data.polygones.map((d) => d.name)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"projection = d3\n .geoIdentity()\n .reflectY(true)\n .fitExtent(\n [\n [0, 0],\n [width, height]\n ],\n {\n type: \"LineString\",\n coordinates: [\n [5, 4],\n [68, 45]\n ]\n }\n )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"radius = d3.scaleSqrt([0, 1500], [2, 30])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"height = 500","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"import { shortest_tree } from \"@fil/dijkstra\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 44:"$43:body"