2a:null 2b:["$","title",null,{"children":"Hypercube graphs | Torben Jansen | Observable"}] 30:T50d,md`In graph theory, [graphs](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)) are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). ${tex.block`G = (V, E)`} A [hypercube](https://en.wikipedia.org/wiki/Hypercube) is an ${tex`n`}-dimensional analogue of a square (${tex`n`} = 2) and a cube (${tex`n`} = 3). It has ${tex`2^n`} vertices and ${tex`2^{n-1}n`} edges. The [hypercube graph](https://en.wikipedia.org/wiki/Hypercube_graph) ${tex`Q_n`} is the graph formed from the vertices and edges of an ${tex`n`}-dimensional hypercube with ${tex`n`} edges touching each vertex. For instance, the hypercube graph ${tex`Q_4`} is the graph formed by the 16 vertices and 32 edges of a [4-dimensional hypercube](https://observablehq.com/@toja/4d-hypercube). It can be constructed using the ${tex`2^n`} vertices labeled with ${tex`n`}-bit binary numbers and connecting two vertices by an edge whenever the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) of their labels is one (their labels differ in a single bit). Let's start by creating a set of vertices for an ${dimensions}-dimensional hypercube.`31:T7dd,{ const size = Math.min(600, width); const margin = ({top: 20, right: 20, bottom: 40, left: 40}); const x = d3.scaleLinear() .domain([0, dimensions || 1]) .range([margin.left, size - margin.right]) const y = d3.scaleLinear() .domain([0, V.size - 1 || 1]) .range([size - margin.bottom, margin.top]) .nice(); const svg = d3.create("svg") .attr("width", size) .attr("height", size); const xAxis = g => g .attr("transform", `translate(0, ${size - margin.bottom})`) .call(d3.axisBottom(x).ticks(dimensions || 1)) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("y", -14) .attr("text-anchor", "end") .attr("font-weight", "bold") .text("Hamming distance from coordinate origin")); const yAxis = g => g .attr("transform", `translate(${margin.left}, 0)`) .call(d3.axisLeft(y) .tickValues(y.ticks().filter(tick => Number.isInteger(tick))) .tickFormat(d3.format(".0f")) ) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .text("vertex label")); const positions = []; for (let v of V) positions.push([hammingDistance(0, v), v]) svg.append("g") .call(xAxis); svg.append("g") .call(yAxis); svg.append("g") .selectAll("links") .data([...edges(V)]) .join("line") .attr("stroke", "#ccc") .attr("x1", d => x(positions[d[0]][0])) .attr("y1", d => y(positions[d[0]][1])) .attr("x2", d => x(positions[d[1]][0])) .attr("y2", d => y(positions[d[1]][1])); svg.append("g") .selectAll("nodes") .data(positions) .join("circle") .attr("r", 4) .attr("stroke", "white") .attr("fill", d => color(d[0])) .attr("cx", d => x(d[0])) .attr("cy", d => y(d[1])); return svg.node(); }32:T4d3,md`The visualization above shows the described pattern by mapping the ${tex`n`}-bit binary label of a vertex against the Hamming distance of a vertex to the coordinate orign. Furthermore we get an insight on how to create the data for an [isometric projection](https://en.wikipedia.org/wiki/Isometric_projection) of an ${tex`n`}-dimensional hypercube. The term *isometric* comes from the Greek for *equal measure*, reflecting that the *scale along* and the *angles between* each axis of the projection is the same (unlike some other forms of graphical projection). Since every edge in a hypercube has the same length, every edge of a hypercube in an isometric projection will have the same length. The projected direction ${tex`\theta_{e'}`} of an edge ${tex`e'`} from one vertex to another can be computed with the help of the slope ${tex`m_e`} of an edge ${tex`e`} between two vertices when mapped as in the visualization above: ${tex.block` \theta_{e'} = \frac{\pi}{n}\log_2(m_e) `} Here the slope ${tex`m_e`} is simply the difference between the binary representations of two connected vertices (${tex`\delta y`}), since we already know that the Hamming distance between two connected vertices (${tex`\delta x`}) is always 1. `33:T54b,{ const angleOffset = Math.PI / dimensions; const angle = (m) => angleOffset * Math.log2(m); const positions = [[0, 0]]; const length = 100; for (let edge of edges(V)) { if (positions[edge[1]]) continue; const rad = angle(edge[1] - edge[0]) positions[edge[1]] = [ Math.cos(rad) * length + positions[edge[0]][0], Math.sin(rad) * length + positions[edge[0]][1] ] } const extentX = d3.extent(positions, d => d[0]); const extentY = d3.extent(positions, d => d[1]); const padding = 20; const size = Math.min(600, width); const context = DOM.context2d(size, size); context.translate(size / 2 - (extentX[0] + extentX[1]) / 2, size / 2 + extentY[1] / 2); context.scale(1, -1); const dot = new Path2D(); dot.arc(0, 0, 4, 0, 2 * Math.PI); context.strokeStyle = "#ccc"; for (let edge of edges(V)) { context.beginPath(); context.moveTo(...positions[edge[0]]); context.lineTo(...positions[edge[1]]); context.stroke(); } context.strokeStyle = "#fff"; positions.forEach((d, i) => { context.save(); context.translate(d[0], d[1]); context.fillStyle = coloring === "hamming" ? color(hammingDistance(0, i)) : color(bitcount(i) & 1); context.fill(dot); context.stroke(dot); context.restore(); }) return context.canvas; }34:T4cc,{ const angleOffset = Math.PI / dimensions; const angle = (m) => angleOffset * Math.log2(m); const positions = [[0, 0]]; const length = 100; for (let edge of edges(V)) { if (positions[edge[1]]) continue; const rad = angle(edge[1] - edge[0]) positions[edge[1]] = [ Math.cos(rad) * length + positions[edge[0]][0], Math.sin(rad) * length + positions[edge[0]][1] ] } const extentX = d3.extent(positions, d => d[0]); const extentY = d3.extent(positions, d => d[1]); const padding = 20; const size = Math.min(600, width); const context = DOM.context2d(size, size); context.translate(size / 2 - (extentX[0] + extentX[1]) / 2, size / 2 + extentY[1] / 2); context.scale(1, -1); const dot = new Path2D(); dot.arc(0, 0, 4, 0, 2 * Math.PI); context.strokeStyle = "#ccc"; positions.forEach((d, i) => { context.beginPath(); context.arc(d[0], d[1], length, 0, 2 * Math.PI); context.stroke(); }); context.strokeStyle = "#fff"; //context.fillStyle = "#ccc" positions.forEach((d, i) => { context.beginPath(); context.arc(d[0], d[1], 3, 0, 2 * Math.PI); context.fill(); context.stroke(); }); return context.canvas; }35:T506,{ const angleOffset = Math.PI / dimensions; const angle = (m) => angleOffset * Math.log2(m); const positions = [[0, 0]]; const length = 100; const e = []; for (let i of V) { for (let j of V) { if (hammingDistance(i, j) === k) e.push([i, j]) } } for (let edge of edges(V)) { if (positions[edge[1]]) continue; const rad = angle(edge[1] - edge[0]) positions[edge[1]] = [ Math.cos(rad) * length + positions[edge[0]][0], Math.sin(rad) * length + positions[edge[0]][1] ] } const extentX = d3.extent(positions, d => d[0]); const extentY = d3.extent(positions, d => d[1]); const padding = 20; const size = Math.min(600, width); const context = DOM.context2d(size, size); context.translate(size / 2 - (extentX[0] + extentX[1]) / 2, size / 2 + extentY[1] / 2); context.scale(1, -1); context.strokeStyle = "#ccc"; e.forEach(edge => { context.beginPath(); context.moveTo(...positions[edge[0]]); context.lineTo(...positions[edge[1]]); context.stroke(); }); context.strokeStyle = "#fff"; positions.forEach((d, i) => { context.beginPath(); context.arc(d[0], d[1], 3, 0, 2 * Math.PI); context.fill(); context.stroke(); }); return context.canvas; }36:[] 2e:{"id":"837b7754c1c4a9b4","slug":"hypercube-graphs","title":"Hypercube graphs","thumbnail":"b0339e15d0735aea23591bff5eefa8ad884357ada9190343927616a24c442956","access_level":"public","create_time":"$D2019-11-15T16:51:40.135Z","update_time":"$D2020-09-11T14:49:17.237Z","view_time":null,"first_public_time":"$D2019-11-23T15:28:02.895Z","has_unpublished_edits":null,"fork":false,"stars":28,"starred":false,"owner":{"type":"team","id":"03836a98946da550","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":"starter_2024"},"version":1460,"publish_version":1460,"role":null,"authored":false,"authors":[{"type":"individual","id":"9334261743951ef0","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":null}],"members":[{"type":"individual","id":"9334261743951ef0","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":12,"collection":{"id":"48442ce39f9dad7b","slug":"geometry","title":"Geometry","owner":{"id":"03836a98946da550","login":"toja","name":"Torben Jansen"}},"type":"notebook","body":{"titling":"auto","title":"Hypercube graphs","cells":[{"id":0,"value":"md`# Hypercube graphs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":821,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"V = new Set(Array.from({ length: 2 ** dimensions }, (_, i) => i))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":957,"value":"md`There are several ways to represent graphs, each with its advantages and disadvantages. In an [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix) the elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph: For a simple graph with vertex set ${tex`V`}, the adjacency matrix is a |${tex`V`}| × |${tex`V`}| matrix ${tex`A`} such that its element ${tex`A_{ij}`} is *one* when there is an edge from vertex ${tex`i`} to vertex ${tex`j`}, and *zero* when there is no edge.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"viewof adjacencyMatrix = {\n const size = Math.min(512, width);\n const context = DOM.context2d(size, size);\n \n const scale = d3.scaleBand()\n .domain(Array.from(V))\n .range([0, size])\n .paddingInner(0.1);\n \n const cellSize = scale.bandwidth();\n \n const adjacencyMatrix = [];\n \n for (let i of V) {\n const y = scale(i);\n adjacencyMatrix.push([]);\n for (let j of V) {\n const x = scale(j);\n adjacencyMatrix[i][j] = hammingDistance(i, j) === 1;\n context.fillStyle = adjacencyMatrix[i][j] ? j < i ? color(0) : \"#aaa\": \"#eee\";\n context.fillRect(x, y, cellSize, cellSize);\n }\n }\n \n context.canvas.value = adjacencyMatrix;\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1017,"value":"bind(html`\n` , viewof dimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1091,"value":"md`The adjacency matrix of an ${tex`n`}-dimensional hypercube graph ${tex`Q_n`} is symmetrical with diagonal elements equal to 0. Therefore the graph is undirected and has no loops, and we only need to consider the elements of the lower triangular submatrix, i.e. for 0 ≤ ${tex`i`} ≤ ${tex`n`} and 0 ≤ ${tex`j`} < ${tex`i`}.\n\nWhen looking closer at the adjacency matrix we can see a recursive pattern emerging and we can define it as:\n\n${tex.block`\nA_{n+1} =\n \\begin{pmatrix}\n A_n & I \\\\\n I & A_n\n \\end{pmatrix}\n,\nn > 0,\nA_0 = (0)\n`}\n\nWhy is this the case? If we take two 2-dimensional hypercubes (or squares) and connect each vertex in the first hypercube with another vertex (in the corresponding position) in the second hypercube, we'll obtain a 3-dimensional hypercube (well, a cube).\n\nAnd this is the case for any dimension: For any ${tex`n \\in \\mathbb{N}`}, the hypercube ${tex`Q_n`} is a simple graph consisting of two copies of ${tex`Q_{n-1}`} connected together at corresponding nodes. ${tex`Q_0`} has 1 node.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1213,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1245,"value":"bind(html`\n` , viewof dimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1301,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1387,"value":"viewof coloring = radio({\n description: 'Coloring',\n options: [\n { label: 'Hamming distance', value: 'hamming' },\n { label: 'Bipartite', value: 'bipartite' }\n ],\n value: 'hamming'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1084,"value":"bind(html`\n` , viewof dimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1426,"value":"md`---\n## Playground`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1410,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1431,"value":"bind(html`\n` , viewof dimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1436,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1451,"value":"bind(html`\n` , viewof dimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1447,"value":"viewof k = {\n const k = html`\n`\n \n k.oninput = () => k.value = k[0].valueAsNumber;\n k.oninput();\n return k;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1379,"value":"md`---\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"edges = function* (vertices) {\n for (let i of vertices) {\n for (let j of vertices) {\n if (j <= i) continue; // use only one half of the matrix\n if (adjacencyMatrix[i][j]) {\n yield [i, j];\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"hammingDistance = (x, y) => bitcount(x ^ y);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":595,"value":"bitcount = (i) => {\n let d = 0;\n while (i) d += i & 1, i >>= 1;\n return d;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"color = d3.scaleOrdinal(d3.schemeTableau10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":990,"value":"viewof dimensions = new View(5)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1009,"value":"function bind(input, view) {\n function update({value}) {\n if (!isNaN(value) && input[0].valueAsNumber !== value) {\n input[0].value = value;\n }\n }\n input[0].value = view.value;\n input.oninput = () => view.value = input[0].valueAsNumber;\n view.addEventListener(\"input\", update);\n return Generators.disposable(input, () => {\n view.removeEventListener(\"input\", update);\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":986,"value":"import { View } from \"@mbostock/synchronized-views\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1383,"value":"import {radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 2f:"$2e:body"