{"id":"8677131d6d27c4a7","slug":"data-driven-projections-darwins-world","trashed":false,"description":"","likes":40,"publish_level":"public","forks":0,"fork_of":null,"has_importers":false,"update_time":"2018-10-07T23:37:41.373Z","first_public_version":null,"paused_version":null,"publish_time":"2018-10-07T17:43:39.034Z","publish_version":1920,"latest_version":1920,"thumbnail":"8d1749aa104458d8e2e253eb562706951056e5c429013963c5f557d8c900dd28","default_thumbnail":"8d1749aa104458d8e2e253eb562706951056e5c429013963c5f557d8c900dd28","roles":[],"sharing":null,"owner":{"id":"18bbeceb36c8f564","avatar_url":"https://avatars.observableusercontent.com/avatar/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","login":"bmschmidt","name":"Benjamin Schmidt","bio":"Digital Humanist. Manhattan-based.","home_url":"http://benschmidt.org","type":"team","tier":"starter_2024"},"creator":{"id":"33354ca265b21f01","avatar_url":"https://avatars.observableusercontent.com/avatar/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","login":"bmschmidt","name":"Benjamin Schmidt","bio":"Digital Humanist. Manhattan-based.","home_url":"http://benschmidt.org","tier":"pro"},"authors":[{"id":"33354ca265b21f01","avatar_url":"https://avatars.observableusercontent.com/avatar/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","name":"Benjamin Schmidt","login":"bmschmidt","bio":"Digital Humanist. Manhattan-based.","home_url":"http://benschmidt.org","tier":"pro","approved":true,"description":""}],"collections":[{"id":"9cbebc0d45eec1ae","type":"public","slug":"maps","title":"Maps","description":"Embrace your inner shapefile. Or GeoJSON or TopoJSON. 🌍","update_time":"2018-11-13T23:08:46.395Z","pinned":true,"ordered":false,"custom_thumbnail":"731383d6e26988b24804bbe587cfde54620becf89d421a1d23c51903a8cf5e17","default_thumbnail":"970f477c509f8ebe4677acf5d708b9bf4b0c53f3d222e553ac7b3bdc063b1bc7","thumbnail":"731383d6e26988b24804bbe587cfde54620becf89d421a1d23c51903a8cf5e17","listing_count":67,"parent_collection_count":1,"owner":{"id":"f35c755083683fe5","avatar_url":"https://avatars.observableusercontent.com/avatar/5a51c3b908225a581d20577e488e2aba8cbc9541c52982c638638c370c3e5e8e","login":"observablehq","name":"Observable","bio":"The end-to-end solution for building and hosting better data apps, dashboards, and reports.","home_url":"https://observablehq.com","type":"team","tier":"enterprise_2024"}}],"files":[],"comments":[],"commenting_lock":null,"suggestion_from":null,"suggestions_to":[],"version":1920,"title":"Data-driven projections: Darwin's world","license":null,"copyright":"","nodes":[{"id":0,"value":"md`# Data-driven projections: Darwin's world\n\nOrdinarily you have to choose a map projection appropriate for your data. Philippe Riviere's [Voronoi projection](https://beta.observablehq.com/@fil/voronoi-projection), on the other hand, makes it possible to dynamically create a bespoke map projection that minimizes distortion for a *particular dataset*. \n\nHere I've taken the track of the voyage of the Beagle (1831-1836), on which Charles Darwin began to develop the theory of evolution through natural selection, and defined a cost function that preserves continuity near the areas that the ship sailed. The result is a projection that does a good job at preserving the shape of the world that Charles Darwin saw, and radically fractures areas like North America and Eurasia that are unimportant for looking at Darwin's voyage. (The ship's voyage is in dark blue: the Galapagos islands, appropriately enough, end up right at the center of the map).\n\n![Darwin](https://raw.githubusercontent.com/bmschmidt/voronoi-projection/master/Darwin.png)\n\nThe 100,000 face projection of the Beagle's voyage was done on a desktop. Below is an dynamic notebook for a few hundred faces. (Forked from a notebook by [@fil](https://beta.observablehq.com/@fil/voronoi-projection). You could replace Darwin's path, below with anything you like. Put in the coordinates of every place you've been, and generate a map projection unique to you!\n`","pinned":false,"mode":"js","data":null,"name":null},{"id":15,"value":"VORONOI = map(projection, { tree: false, path:path })","pinned":false,"mode":"js","data":null,"name":null},{"id":1910,"value":"md`An array of coordinates sampled from the full path of the Beagle.`","pinned":false,"mode":"js","data":null,"name":null},{"id":970,"value":"path = [ [-4.17,50.37]\n,[-7.01,47.88]\n,[-8.75,46.24]\n,[-9.69,45.34]\n,[-10.75,44.27]\n,[-11.6,43.42]\n,[-15.05,38.4]\n,[-15.53,37.48]\n,[-16.54,34.36]\n,[-21.27,20.48]\n,[-23.4,15.05]\n,[-23.5,14.9]\n,[-24.29,14.22]\n,[-25.08,13.55]\n,[-25.32,13.28]\n,[-26.57,11.87]\n,[-38.42,-13.48]\n,[-36.32,-17.2]\n,[-38.67,-17.96]\n,[-43.13,-22.9]\n,[-38.75,-16.92]\n,[-38.52,-20.17]\n,[-40.52,-23.07]\n,[-42.68,-23.08]\n,[-43.13,-22.9]\n,[-43.13,-22.9]\n,[-45.73,-27.13]\n,[-48.09,-30.17]\n,[-50.3,-33.35]\n,[-53.32,-34.98]\n,[-58.36,-34.59]\n,[-56.6,-36.38]\n,[-56.64,-36.51]\n,[-57.96,-38.6]\n,[-58.79,-38.77]\n,[-61.06,-39.23]\n,[-60.91,-39.27]\n,[-60.81,-39.29]\n,[-60.67,-39.32]\n,[-60.6,-39.34]\n,[-60.43,-39.38]\n,[-60.39,-39.39]\n,[-60.29,-39.41]\n,[-60.28,-39.41]\n,[-60.21,-39.43]\n,[-60.07,-39.46]\n,[-59.94,-39.5]\n,[-59.87,-39.51]\n,[-59.52,-39.53]\n,[-58.92,-39.41]\n,[-57.17,-38.85]\n,[-57.75,-34.68]\n,[-56.58,-35.13]\n,[-56.18,-34.87]\n,[-58.01,-39.19]\n,[-58.17,-39.33]\n,[-59.72,-40.05]\n,[-62.1,-40.8]\n,[-61.49,-42.15]\n,[-61.37,-43.57]\n,[-63.37,-46.28]\n,[-68.16,-56.48]\n,[-69.31,-57.01]\n,[-69.4,-56.26]\n,[-69.38,-56.25]\n,[-71.15,-56.73]\n,[-69.4,-56.12]\n,[-69.21,-56.29]\n,[-68.74,-55.98]\n,[-63.33,-53.3]\n,[-62.88,-53.3]\n,[-59.36,-50.12]\n,[-59.92,-49.07]\n,[-61.6,-47.2]\n,[-62.33,-43.02]\n,[-62.62,-41.13]\n,[-62.66,-41.15]\n,[-60.17,-40.48]\n,[-55.54,-37.01]\n,[-55.5,-37.06]\n,[-54.95,-34.9]\n,[-55.78,-34.9]\n,[-54.87,-34.9]\n,[-53.28,-35.23]\n,[-58.07,-38.15]\n,[-59.29,-40.13]\n,[-59.14,-38.31]\n,[-58.88,-38.09]\n,[-61.97,-41.67]\n,[-56.2,-34.9]\n,[-54.95,-34.9]\n,[-56.24,-35.18]\n,[-56.97,-37.77]\n,[-55.81,-34.9]\n,[-56.45,-37.18]\n,[-57.02,-37.82]\n,[-58.4,-41.25]\n,[-58.82,-42.53]\n,[-60.19,-43.53]\n,[-60.77,-44.2]\n,[-64.43,-46.79]\n,[-65.48,-47.63]\n,[-66.37,-48.77]\n,[-67.4,-49.0]\n,[-66.01,-49.31]\n,[-70.55,-53.11]\n,[-70.71,-53.34]\n,[-70.79,-53.43]\n,[-70.91,-53.63]\n,[-70.53,-53.59]\n,[-70.51,-53.58]\n,[-70.11,-53.54]\n,[-68.93,-53.41]\n,[-68.36,-53.34]\n,[-68.23,-53.33]\n,[-69.78,-52.81]\n,[-70.11,-54.02]\n,[-72.78,-52.38]\n,[-72.6,-52.51]\n,[-67.01,-55.24]\n,[-66.64,-55.15]\n,[-65.81,-54.83]\n,[-60.8,-49.44]\n,[-64.15,-50.17]\n,[-65.08,-49.77]\n,[-66.63,-50.95]\n,[-66.76,-52.47]\n,[-66.71,-52.28]\n,[-66.71,-52.46]\n,[-70.69,-53.3]\n,[-70.93,-53.63]\n,[-72.06,-54.13]\n,[-72.91,-54.5]\n,[-74.99,-54.78]\n,[-76.23,-44.45]\n,[-74.14,-43.29]\n,[-73.87,-43.18]\n,[-75.08,-42.69]\n,[-74.96,-42.23]\n,[-75.01,-42.19]\n,[-75.44,-41.83]\n,[-73.75,-35.95]\n,[-73.18,-34.6]\n,[-72.89,-34.17]\n,[-71.95,-33.27]\n,[-71.85,-33.19]\n,[-78.03,-39.85]\n,[-76.35,-41.48]\n,[-76.28,-41.53]\n,[-77.34,-43.72]\n,[-76.75,-44.3]\n,[-76.3,-44.44]\n,[-74.54,-44.44]\n,[-73.9,-43.54]\n,[-74.09,-44.0]\n,[-74.34,-45.03]\n,[-74.6,-45.3]\n,[-75.05,-45.9]\n,[-75.56,-46.58]\n,[-74.33,-44.57]\n,[-74.05,-43.81]\n,[-73.5,-39.83]\n,[-73.53,-39.72]\n,[-73.6,-38.95]\n,[-73.77,-38.95]\n,[-73.91,-38.3]\n,[-73.08,-36.83]\n,[-72.86,-35.55]\n,[-72.82,-35.28]\n,[-72.43,-33.75]\n,[-72.27,-33.61]\n,[-79.05,-34.18]\n,[-81.16,-35.03]\n,[-76.25,-35.63]\n,[-73.04,-36.64]\n,[-71.6,-33.0]\n,[-71.59,-32.69]\n,[-71.54,-32.39]\n,[-71.28,-31.58]\n,[-71.68,-30.22]\n,[-71.43,-29.97]\n,[-74.41,-31.44]\n,[-71.65,-27.68]\n,[-71.48,-25.53]\n,[-70.32,-20.29]\n,[-72.32,-18.78]\n,[-72.78,-18.47]\n,[-83.32,-6.87]\n,[-89.95,-0.84]\n,[-91.2,-1.09]\n,[-91.33,-0.55]\n,[-91.24,-0.36]\n,[-90.66,0.52]\n,[-90.67,0.26]\n,[-91.29,-0.57]\n,[-90.85,0.16]\n,[-90.84,0.22]\n,[-92.41,1.38]\n,[-99.48,-0.92]\n,[-104.57,-4.9]\n,[-105.44,-5.48]\n,[-107.0,-6.53]\n,[-126.11,-11.71]\n,[-142.07,-15.39]\n,[-146.09,-16.09]\n,[-147.83,-16.79]\n,[-148.52,-17.08]\n,[-148.67,-17.15]\n,[-149.26,-17.4]\n,[-152.63,-17.33]\n,[-153.93,-17.58]\n,[-155.0,-17.9]\n,[-160.64,-19.3]\n,[-165.21,-21.14]\n,[-167.0,-22.03]\n,[-169.98,-23.1]\n,[-172.81,-24.23]\n,[-179.87,-28.13]\n,[179.93,-28.36]\n,[179.67,-28.66]\n,[174.28,-35.28]\n,[174.0,-35.98]\n,[164.88,-34.33]\n,[163.97,-34.35]\n,[159.9,-35.1]\n,[150.44,-39.11]\n,[149.93,-42.8]\n,[148.24,-42.86]\n,[147.96,-42.87]\n,[145.23,-44.12]\n,[133.38,-41.66]\n,[132.35,-41.43]\n,[129.02,-40.57]\n,[125.48,-39.63]\n,[123.3,-38.02]\n,[123.2,-37.92]\n,[122.76,-37.58]\n,[117.29,-35.03]\n,[113.89,-34.87]\n,[112.97,-32.72]\n,[109.52,-28.13]\n,[105.73,-22.96]\n,[104.26,-20.76]\n,[97.54,-12.42]\n,[97.38,-12.34]\n,[97.36,-12.33]\n,[97.07,-12.17]\n,[44.99,-26.58]\n,[42.67,-27.52]\n,[42.55,-27.52]\n,[42.13,-27.51]\n,[37.87,-27.83]\n,[36.97,-27.97]\n,[22.76,-34.79]\n,[21.92,-35.46]\n,[21.05,-35.2]\n,[20.37,-35.08]\n,[19.97,-34.87]\n,[20.03,-35.18]\n,[19.85,-35.19]\n,[17.13,-34.95]\n,[17.06,-34.95]\n,[16.92,-34.95]\n,[16.91,-31.68]\n,[15.48,-30.48]\n,[5.22,-23.07]\n,[3.27,-21.0]\n,[-0.53,-18.87]\n,[-3.72,-17.88]\n,[-6.49,-15.29]\n,[-8.21,-13.94]\n,[-22.72,-11.28]\n,[-23.87,-11.44]\n,[-38.51,-12.98]\n,[-38.25,-13.03]\n,[-36.28,-11.5]\n,[-35.31,-9.68]\n,[-35.1,-7.97]\n,[-34.86,-8.06]\n,[-34.83,-7.96]\n,[-34.42,-6.67]\n,[-29.5,2.3]\n,[-24.3,9.95]\n,[-23.42,12.86]\n,[-23.27,13.9]\n,[-25.35,14.4]\n,[-30.61,19.05]\n,[-32.42,23.12]\n,[-32.6,23.33]\n,[-34.57,25.68]\n,[-35.78,27.87]\n,[-34.5,32.68]\n,[-32.37,35.25]\n,[-28.86,37.25]\n,[-27.55,38.18]\n,[-27.09,38.76]\n,[-26.14,38.07]\n,[-24.5,39.33]\n,[-23.7,39.92]\n,[-13.93,45.63]\n,[-8.97,48.25]\n,[-5.05,50.14]\n,[-4.17,50.37]\n]","pinned":false,"mode":"js","data":null,"name":null},{"id":1890,"value":"N_FACETS = 100","pinned":false,"mode":"js","data":null,"name":null},{"id":752,"value":"projection = d3\n  .geoPolyhedralVoronoi()\n  .parents(parents)\n  .polygons(polygons)\n  .angle(0)\n  .fitExtent([[0, 0], [950, 500]], { type: \"Sphere\" })","pinned":true,"mode":"js","data":null,"name":null},{"id":1393,"value":"function map(projection, opts) {\n  const height = width * (2 / 3),\n    scale = 1;\n  const context = DOM.context2d(width * scale, height * scale);\n\n  context.scale(scale, scale);\n\n  opts = Object.assign({}, opts);\n\n  const projectionmap = opts.view || projection;\n  projectionmap.fitExtent([[2, 2], [width - 2, height - 2]], {\n    type: \"Sphere\"\n  });\n\n  var path = d3.geoPath(projectionmap, context);\n  context.clearRect(0, 0, width, height);\n\n  context.beginPath(),\n    path({ type: \"Sphere\" }),\n    (context.fillStyle = \"#fefef6\"),\n    context.fill();\n\n  context.beginPath(),\n    path(d3.geoGraticule()()),\n    (context.strokeStyle = \"#ccc\"),\n    context.stroke();\n\n  context.beginPath(),\n    path(land),\n    (context.fillStyle = \"black\"),\n    context.fill();\n\n  // Polyhedral projections expose their structure as projection.tree()\n  // To draw them we need to cancel the rotate\n  if (true) {\n    var rotate = projection.rotate();\n    projection.rotate([0, 0, 0]);\n\n    // run the tree of faces to get all sites and folds\n    var sites = [],\n      folds = [],\n      i = 0;\n    function recurse(face) {\n      var site = d3.geoCentroid({ type: \"MultiPoint\", coordinates: face.face });\n      site.id = face.id || i++;\n      sites[site.id] = site;\n      if (face.children) {\n        face.children.forEach(function(child) {\n          folds.push({\n            type: \"LineString\",\n            coordinates: child.shared.map(e =>\n              d3.geoInterpolate(e, face.centroid)(1e-5)\n            )\n          });\n          recurse(child);\n        });\n      }\n    }\n    recurse(projection.tree());\n\n    const circles = points;\n\n    // links\n    if (opts.tree) {\n      context.beginPath(),\n        path({\n          type: \"MultiLineString\",\n          coordinates: parents\n            .map((from, to) => [circles[from], circles[to]])\n            .filter(d => !!d[0])\n        }),\n        (context.strokeStyle = \"green\"),\n        context.stroke();\n    }\n\n    if (opts.path) {\n      context.beginPath(),\n        path({\n          type: \"LineString\",\n          coordinates: opts.path\n        }),\n        (context.strokeStyle = \"red\"),\n        context.stroke()\n    }\n    \n    // folding lines\n    context.beginPath(),\n      (context.lineWidth = 0.5),\n      context.setLineDash([3, 4]),\n      (context.strokeStyle = \"#666\");\n    if (opts.view) path(voro.cellMesh());\n    else folds.forEach(path);\n    context.stroke(), context.setLineDash([]);\n\n    if (opts.cut) {\n      (context.lineWidth = 1),\n        (context.strokeStyle = \"brown\"),\n        context.beginPath(),\n        path(projection.preclip().polygon()),\n        context.stroke();\n    }\n\n    (context.lineWidth = 1),\n      (context.strokeStyle = \"#000\"),\n      context.beginPath(),\n      path({ type: \"Sphere\" });\n    context.stroke();\n\n    // restore the projection’s rotate\n    projection.rotate(rotate);\n  }\n\n  return context.canvas;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":797,"value":"md`The Voronoi projection requires faces. I define them here as 264 random points, plus 300 points sampled from the track of the Beagle.`","pinned":false,"mode":"js","data":null,"name":null},{"id":1830,"value":"// From @fil's Voronoi code\n\nfunction randompoints(n) {\n  return [[0, 0]].concat(\n    d3\n      .range(n - 1)\n      .map(i => [\n        360 * Math.random() - 180,\n        90 * (Math.random() - Math.random())\n      ])\n  );\n}\n","pinned":false,"mode":"js","data":null,"name":null},{"id":1829,"value":"points = { \n  var p = randompoints(N_FACETS)\n  //p.concat(path.filter(d => return Math.random() ))   .sort( () => Math.random() - 0.5) )\n  return p\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":771,"value":"voro = d3.geoVoronoi()(points.map((p, i) => [...p, i]))","pinned":false,"mode":"js","data":null,"name":null},{"id":779,"value":"polygons = voro.polygons()","pinned":false,"mode":"js","data":null,"name":null},{"id":1844,"value":"function pathDist(p) {\n  // Brute force along the entire defining path.\n  return d3.min(path.map( (pathPoint) => d3.geoDistance(p, pathPoint)))\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":1072,"value":"cost = {\n  return function(a, b) {\n    const d = pathDist(a)*pathDist(b);\n    return d\n  };\n}","pinned":true,"mode":"js","data":null,"name":null},{"id":1479,"value":"clipPolygon = d3.geoProject(\n  {\n    type: \"MultiPolygon\",\n    coordinates: voro.polygons().features.map((d, i) => {\n      const c = voro.points[i];\n      return d.geometry.coordinates;\n    })\n  },\n  d3\n    .geoEquirectangular()\n    .scale(degrees)\n    .translate([0, 0])\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":1197,"value":"inland = {\n  // hack d.geoContains\n  const contains = geoContainsCache(land),\n    d3_geoContains = d3.geoContains;\n\n  d3.geoContains = function(_, d) {\n    if (_ === land) return contains(d);\n    return d3_geoContains(_, d);\n  };\n\n  const inland = points.map(d => +d3.geoContains(land, d));\n\n  return inland;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":1757,"value":"import {geoContainsCache} from \"@fil/another-hex-map\"","pinned":false,"mode":"js","data":null,"name":null},{"id":774,"value":"parents = {\n  var n = points.length;\n\n  var links = voro.links().features.map(d => d.properties);\n\n  var k = kruskal(\n    links.map(\n      d => ((d.source.index = d.source[2]), (d.target.index = d.target[2]), d)\n    ),\n    cost\n  ).map(l => ({\n    type: \"LineString\",\n    coordinates: [l.source, l.target],\n    properties: l\n  }));\n\n  // Build a tree of the faces\n  var parents = [-1];\n  var search = n - 1;\n  do {\n    k.forEach(l => {\n      var s = l.properties.source[2],\n        t = l.properties.target[2];\n      if (parents[s] !== undefined && parents[t] === undefined) {\n        parents[t] = s;\n        search--;\n      } else if (parents[t] !== undefined && parents[s] === undefined) {\n        parents[s] = t;\n        search--;\n      }\n    });\n  } while (search > 0);\n\n  return parents;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":513,"value":"md`-----------\n_Play zone_`","pinned":false,"mode":"js","data":null,"name":null},{"id":9,"value":"land = d3.json(\n  \"https://unpkg.com/visionscarto-world-atlas@0.0.4/world/110m_land.geojson\"\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":1161,"value":"countries = d3.json(\n  \"https://unpkg.com/visionscarto-world-atlas@0.0.3/world/110m_countries.geojson\"\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":2,"value":"d3 = require(\"d3-array\", \"d3-fetch\", \"d3-geo\", \"d3-geo-projection\", \"d3-geo-polygon\", \"d3-geo-voronoi\")","pinned":false,"mode":"js","data":null,"name":null},{"id":756,"value":"kruskal = {\n  // https://github.com/mikolalysenko/union-find\n  const UnionFind = (function() {\n    \"use strict\";\n    \"use restrict\";\n\n    function UnionFind(count) {\n      this.roots = new Array(count);\n      this.ranks = new Array(count);\n\n      for (var i = 0; i < count; ++i) {\n        this.roots[i] = i;\n        this.ranks[i] = 0;\n      }\n    }\n\n    var proto = UnionFind.prototype;\n\n    Object.defineProperty(proto, \"length\", {\n      get: function() {\n        return this.roots.length;\n      }\n    });\n\n    proto.makeSet = function() {\n      var n = this.roots.length;\n      this.roots.push(n);\n      this.ranks.push(0);\n      return n;\n    };\n\n    proto.find = function(x) {\n      var x0 = x;\n      var roots = this.roots;\n      while (roots[x] !== x) {\n        x = roots[x];\n      }\n      while (roots[x0] !== x) {\n        var y = roots[x0];\n        roots[x0] = x;\n        x0 = y;\n      }\n      return x;\n    };\n\n    proto.link = function(x, y) {\n      var xr = this.find(x),\n        yr = this.find(y);\n      if (xr === yr) {\n        return;\n      }\n      var ranks = this.ranks,\n        roots = this.roots,\n        xd = ranks[xr],\n        yd = ranks[yr];\n      if (xd < yd) {\n        roots[xr] = yr;\n      } else if (yd < xd) {\n        roots[yr] = xr;\n      } else {\n        roots[yr] = xr;\n        ++ranks[xr];\n      }\n    };\n\n    return UnionFind;\n  })();\n\n  function kruskal(graph, dist) {\n    // 1   A := ø\n    const A = [];\n    // 2   for each vertex v of G :\n    // 3      create set(v)\n    let n = -Infinity;\n    graph.forEach(l => {\n      if (l.source.index > n) n = l.source.index;\n      if (l.target.index > n) n = l.target.index;\n    });\n    const uf = new UnionFind(n);\n    // 4   sort the edges of G by increasing weight\n\n    graph = graph.map(l => {\n      l.w = dist ? dist(l.source, l.target) : l.length;\n      return l;\n    });\n    graph\n      .sort((a, b) => d3.ascending(a.w, b.w))\n      // 5   for each edge (u, v) of G (sorted by weigth):\n      .forEach(l => {\n        // 6      if find(u) ≠ find(v) :\n        if (uf.find(l.source.index) != uf.find(l.target.index)) {\n          // 7         add (u, v) to the set A\n          A.push(l);\n          // 8         union(u, v)\n          uf.link(l.source.index, l.target.index);\n        }\n      });\n    // 9   solution = A\n    return A;\n  }\n\n  return kruskal;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":1709,"value":"import { degrees } from \"@fil/math\"","pinned":false,"mode":"js","data":null,"name":null}],"resolutions":[],"schedule":null,"last_view_time":null}