2b:null 2c:["$","title",null,{"children":"Kruskal Maze | Fil | Observable"}] 31:T4e9,// A voronoi maze needs removal of sub paths shared by connected sites /* pseudocode * links.each( cell(a) + cell(b) => remove common edge; it is written in opposite directions ) */ show_maze = function(sel, voronoi, id) { var poly = voronoi.polygons(); var links = kruskal(delaunay); var commons = [], walls = []; links = d3.merge([ links.map(l => [l.source.index, l.target.index]), links.map(l => [l.target.index, l.source.index]) ]); links.forEach(l => { var p0 = poly[l[0]], p1 = poly[l[1]]; for (var i = 0; i < p0.length; i++) { var common = false; var segment0 = [p0[i], p0[(i+1) % (p0.length)]]; for (var j = p1.length; j > 0; j--) { var segment1 = [p1[j % (p1.length)], p1[(j-1)]]; if (almost(segment0,segment1)) common = true; } var p = 'M' + segment0[0] + 'L' + segment0[1]; if (common) { commons.push(p); //commons.push('M' + segment0[1] + 'L' + segment0[0]); } walls.push(p); } }); walls = walls.filter(d => commons.indexOf(d) === -1) if (sel) { var update = sel.select(`svg #${id}`).selectAll('path') .data([walls]); var enter = update.enter() .append('path') .classed('polygons', true); update.merge(enter).attr('d', d => d.join(' ')); } return commons.join(' '); }32:T579,function diameter(graph) { var neighbours = sites.map((d,i) => ({n: [], live: true, index: i})); graph .forEach(link => { neighbours[link.target.index].n.push(link.source.index); neighbours[link.source.index].n.push(link.target.index); }) var order = [[]]; var max = 1000; var k = 0; var center = null; var live = neighbours.length; while(max-->0) { k++; let o = []; neighbours .map(d => { d.mark = d.n.length <= 1 && d.live; return d; }) .forEach((d,i) => { if (d.mark) { o.push(i); center = i; if (live>2) { neighbours[d.n[0]].n = neighbours[d.n[0]].n.filter(d => d !== i); neighbours[d.n[0]].tag = i; } neighbours[i].n = []; neighbours[i].live = false; live--; } }); if (o.length === 0) break; order.push(o); } var diameter = []; let o = order[order.length - 1]; if (o.length === 2) { diameter.push({ source: sites[o[0]], target: sites[o[1]] }); } else { o = order[order.length - 2]; diameter.push({ source: sites[center], target: sites[o[0]] }); diameter.push({ source: sites[center], target: sites[o[1]] }); } max = 10000 while (max-->0) { o = o.map(i => { const a = neighbours[i].tag; if (a !== undefined) { diameter.push({ source: sites[i], target: sites[a]}); } return a; }).filter(d => d !== undefined); if (o.length === 0) break; } return [diameter, center, order]; }33:[] 2f:{"id":"5cd260bce3683bb4","slug":"kruskal-maze","title":"Kruskal Maze","thumbnail":"df32f4916f64b794203063b75bd387c29873df682f4ddc289f322996706eaf5a","access_level":"public","create_time":"$D2018-02-10T13:38:48.304Z","update_time":"$D2021-11-01T21:21:11.751Z","view_time":null,"first_public_time":"$D2018-02-10T13:39:46.550Z","fork":true,"stars":9,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":1504,"publish_version":1504,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":{"id":"1b93c3deba41e333","slug":"voronoi","title":"Voronoi","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"type":"notebook","body":{"title":"Kruskal Maze","cells":[{"id":1452,"value":"md`# Kruskal Maze`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1093,"value":"d3\n .select(this || create_svg())\n .call(show_maze, voronoi, \"network1\")\n //.call(show_sites, sites, 'sites')\n //.call(show_sites, _centers, 'centers')\n .call(show_sites, extremes, \"centers\")\n //.call(show_links, delaunay, 'network3')\n //.call(show_links, urquhart(voronoi), 'network1')\n //.call(show_links, urquhart(voronoi), 'network3')\n //.call(show_links, kruskal(voronoi.links()), 'network2')\n //.call(show_forest, mst_clustering(voronoi.links(), dist2, 450, 10), 'network4')\n //.call(show_forest, mst_clustering(urquhart(voronoi), dist2, 120, 10), 'network4')\n .call(show_links, _diameter[0], \"network4\")\n .node()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":579,"value":"interval_t = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1420,"value":"/*\n\nhttps://meyavuz.wordpress.com/2017/03/11/how-does-kruskals-algorithm-progress/\n\nhttps://fr.wikipedia.org/wiki/Algorithme_de_Kruskal\n\nhttp://people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/union_find/\n\nhttps://fr.wikipedia.org/wiki/Union-find\n\nhttps://www.researchgate.net/publication/221612693_A_Voronoi_Diagram_Approach_to_Autonomous_Clustering\n\nhttps://www.youtube.com/watch?v=KFnZS-UgNqs\n\nhttps://www.youtube.com/watch?v=86twBpK1YIs (totally amazing)\n\nhttps://daniel.lawrence.lu/blog/y2013m05d13/ (adds visibility)\n\nhttp://ofb.net/~uranium/voronoi/\n\nhttp://nbviewer.jupyter.org/github/jakevdp/mst_clustering/blob/master/MSTClustering.ipynb\n\nhttp://slideplayer.com/slide/4799175/\n\nhttp://proceedings.mlr.press/v9/telgarsky10a/telgarsky10a.pdf\n\nhttps://link.springer.com/chapter/10.1007/978-3-642-29280-4_21\n\n*/","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1,"value":"width = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":577,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":23,"value":"n = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":779,"value":"sites.length","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":25,"value":"d3 = require(\"d3@5\", \"d3-voronoi@1\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":881,"value":"_centers = {\n\tvar C = _diameter[2];\n\treturn C[C.length - 1].map(i => sites[i]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1397,"value":"extremes = {\n\tvar k = _diameter[0].slice(-2);\n\treturn [k[0].target, k[1].target];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1261,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1318,"value":"function almost(a,b) {\n\treturn dist2(a[0], b[0]) + dist2(a[1], b[1]) < 1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1166,"value":"// https://github.com/jakevdp/mst_clustering\n// independent implementation (indeed I found out about jakevdp after I coded it)\nfunction mst_clustering(graph, distance /* distance function */, maxdist /* cutoff_scale */, min_nodes = 1) {\n\tconst links = kruskal(graph.filter(l => distance(l.source, l.target) < maxdist));\n\tconst uf = new UnionFind(links.length * 2);\n\tlinks.forEach(l => {\n\t\tuf.link(l.source.index, l.target.index);\n\t});\n\tconst forest = d3.nest()\n\t\t.key(d => uf.find(d.source.index)) // same as d.target.index as they've been linked :-)\n\t\t.entries(links);\n\n\treturn forest.filter(d => d.values.length >= min_nodes).map(d => d.values);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1173,"value":"mst_clustering(voronoi.links(), dist2, 40)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":825,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":827,"value":"_diameter = diameter(kruskal(delaunay))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":715,"value":"import {UnionFind} from \"@fil/union-find\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":710,"value":"function kruskal(graph) {\n // 1 A := ø\n const A = [];\n // 2 pour chaque sommet v de G :\n // 3 créerEnsemble(v)\n \n \n \n const uf = new UnionFind(sites.length);\n let groups = sites.length;\n // 4 trier les arêtes de G par poids croissant\n graph = graph.map(l => {\n l.w = dist2(l.source, l.target);\n return l;\n });\n graph\n .sort((a, b) => d3.ascending(a.w, b.w))\n // 5 pour chaque arête (u, v) de G prise par poids croissant :\n .forEach(l => {\n if (groups > 0)\n if (uf.find(l.source.index) != uf.find(l.target.index)) {\n // 6 si find(u) ≠ find(v) :\n // 7 ajouter l'arête (u, v) à l'ensemble A\n A.push(l);\n // 8 union(u, v)\n uf.link(l.source.index, l.target.index);\n groups--;\n }\n });\n // 9 retourner A\n return A;\n //\tyield uf;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":439,"value":"orderbylength = function(graph) {\n\tfunction len2(link) {\n\t\treturn Math.pow(link.source[0] - link.target[0], 2) + Math.pow(link.source[1] - link.target[1], 2);\n\t}\n return graph.slice().sort((a,b) => d3.descending(len2(a), len2(b)));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":442,"value":"remove_long_edges = function(graph) {\n\tgraph = orderbylength(graph);\n\tfor (var i = 0; i< graph.length; i++) {\n\t\tvar graph2 = graph.slice();\n\t\tdelete graph2[i];\n\t\tvar link = graph[i];\n\t\tif (graph_connects(graph2, link.source.index, link.target.index)) delete graph[i];\n\t}\n\treturn(graph);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":639,"value":"function dist2(a,b) {\n\tvar dx = a[0] - b[0],\n\t\t\tdy = a[1] - b[1];\n\treturn dx * dx + dy * dy;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":504,"value":"function graph_connects(graph, i, j) {\n\tvar neighbours = d3.map();\n\tvar visited = d3.map();\n\tgraph.filter(link => link)\n\t\t.forEach(link => {\n\t\t\tneighbours.set(link.target.index, (neighbours.get(link.target.index) || []).concat([link.source.index])); \n\t\t\tneighbours.set(link.source.index, (neighbours.get(link.source.index) || []).concat([link.target.index])); \n\t\t})\n\tvisited.set(i, true);\n\tvar front = [i];\n\twhile (front.length > 0) {\n\t\tvar init = [];\n\t\tfront.forEach(k => (neighbours.get(k) || [] ).forEach(n => {\n\t\t\tif (!visited.get(n)) {\n\t\t\t\tinit.push(n);\n\t\t\t\tvisited.set(n, true);\n\t\t\t}\n\t\t}));\n\t\tif (init.indexOf(j) >= 0) return true;\n\t\tfront = init;\n\t};\n\treturn false;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":372,"value":"nodangling = function(graph) {\n\tvar nodes = [];\n var active = graph.map((link, i) => {\n\t\tlink.index = i;\n\t\tnodes[link.source.index] = (nodes[link.source.index] || []).concat([link.index]); \n\t\tnodes[link.target.index] = (nodes[link.target.index] || []).concat([link.index]); \n\t\treturn link;\n\t});\n\n\tvar a, b = nodes.length, n = [];\n\tdo {\n\t\ta = nodes.length;\n\t\tn.push(a);\n\t\n\t\tnodes\n\t\t.filter(node => node.length == 1)\n\t\t.forEach(node => node.forEach(i => delete active[i]));\n\n\t\tnodes = sites.map(d => {\n\t\t\tvar a = [];\n\t\t\ta.index = d.index;\n\t\t\treturn a;\n\t\t});\n\t\tactive.forEach(link => {\n\t\t\tnodes[link.source.index].push(link.index);\n\t\t\tnodes[link.target.index].push(link.index);\n\t\t});\n\n\t\tnodes = nodes.filter(d => d.length);\n\n\t} while(nodes.length < a);\n\n return active;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":97,"value":"create_svg = function() {\nreturn d3.select(DOM.element('div'))\n.html(`\n\n\n`).node()\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":37,"value":"create_sites = function(n) {\n return d3.range(n)\n .map(function(d) { return [ 5 + Math.random() * (width - 2 * 5), 5 + Math.random() * (height - 2 * 5)]; })\n .map(function(d,i) { d.index = i; return d; });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"function show_sites(sel, sites, id) {\n var update = sel.select(`svg #${id}`)\n .selectAll('circle')\n .data(sites, d => d.index);\n\n var enter = update.enter()\n\t\t.append('circle')\n \t\t.attr('cx', d => d[0])\n \t\t.attr('cy', d => d[1])\n\t\t.attr('stroke', 'green');\n\n\tupdate.exit()\n\t\t.attr('stroke', 'red')\n\t\t//.transition()\n\t\t//.duration(800)\n\t\t//.attr('opacity', 0)\n\t\t.remove();\n\n\tupdate\n\t\t.attr('stroke', '#666')\n .merge(enter)\n\t\t//.transition()\n\t\t//.duration(800)\n \t\t.attr('cx', d => d[0])\n \t\t.attr('cy', d => d[1]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":122,"value":"function show_links(sel, links, id) {\n var update = sel.select(`svg #${id}`)\n .selectAll('path')\n .data([1]);\n\n var enter = update.enter()\n\t\t.append('path');\n\n\tupdate.exit()\n\t\t.remove();\n\n\tupdate\n .merge(enter)\n\t\t.attr('opacity', 0)\n \t\t.attr('d',\n\t\t\tlinks.filter(d => d)\n\t\t\t.map(d => `M${d.source}L${d.target}`)\n\t\t\t.join('')\n\t\t)\n\t\t//.transition()\n\t\t//.delay(700)\n\t\t//.duration(300)\n\t\t.attr('opacity', 1);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1185,"value":"function show_forest(sel, forest, id) {\n var update = sel.select(`svg #${id}`)\n .selectAll('path')\n .data(forest);\n\n var enter = update.enter()\n\t\t.append('path');\n\n\tupdate.exit()\n\t\t.remove();\n\n\tupdate\n .merge(enter)\n\t\t.attr('opacity', 0)\n \t\t.attr('d',\n\t\t\td => d.filter(d => d)\n\t\t\t.map(d => `M${d.source}L${d.target}`)\n\t\t\t.join('')\n\t\t)\n\t\t//.transition()\n\t\t//.delay(700)\n\t\t//.duration(300)\n\t\t.style('stroke', (d,i) => color(i))\n\t\t.attr('opacity', 1);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1189,"value":"color = d3.scaleOrdinal(d3.schemeCategory10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":993,"value":"roots = create_sites(n * (3 + Math.random()))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":72,"value":"sites = Generators.observe(notify => {\n\tnotify(roots);\n if (interval_t) {\n\t var interval = setInterval(() => {\n\t\t\troots.map(d => {\n\t\t\t\td[0] += Math.random()- Math.random() + (d[0] < 0) - (d[0] > width);\n\t\t\t\td[1] += Math.random()- Math.random() + (d[1] < 0) - (d[1] > height);\n\t\t\t\treturn d;\n\t\t\t});\n\t\t\tnotify(roots)\n\t\t}, interval_t || 100000);\n\t return () => clearInterval(interval);\n\t}\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":142,"value":"voronoi = d3.voronoi().extent([[0,0],[width-1, height-1]])(sites)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":104,"value":"delaunay = voronoi.links()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":139,"value":"urquhart = function(diagram) {\n var urquhart = d3.map();\n \n diagram.links().forEach(function(link) {\n var v = d3.extent([link.source.index, link.target.index]);\n urquhart.set(v, link);\n });\n urquhart._remove = [];\n diagram.triangles()\n .forEach(function(t) {\n var l = 0, length = 0, i, v;\n for (var j=0; j<3; j++) {\n var a = t[j], b = t[(j+1)%3];\n v = d3.extent([a.index, b.index]);\n length = (a[0]-b[0]) * (a[0]-b[0]) + (a[1]-b[1]) * (a[1]-b[1]);\n if (length > l) {\n l = length;\n i = v;\n }\n }\n urquhart._remove.push(i);\n });\n urquhart._remove.forEach(function(i) {\n if (urquhart.has(i)) urquhart.remove(i);\n });\n return urquhart.values();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1474,"value":"md`\n----------------\nIf you enjoyed this notebook please contact me fil@rezo.net or https://twitter.com/@recifs\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"