3e:null 3f:["$","title",null,{"children":"Christofides Algorithm | Andrew's Workspace | Observable"}] 45:T4c0,M = { // Minimize the sum of edge weights const objective = { direction: glpk.GLP_MIN, vars: [] }; for (let i = 0; i < O.verts.length; i++) for (let j = 0; j < i; j++) { if (i != j) objective.vars.push({ name: "x"+i+"_"+j, coef: dist[O.verts[i]][O.verts[j]] }); } // Only one edge may touch a vertex const subjectTo = []; for (let i = 0; i < O.verts.length; i++) { const constraint = { vars: [], bnds: { type: glpk.GLP_FX, lb: 1, ub: 1 } }; for (let j = 0; j < O.verts.length; j++) { if (i != j) { constraint.vars.push({ name: "x"+Math.max(i,j)+"_"+Math.min(i,j), coef: 1 }); } } subjectTo.push(constraint); } const binaries = []; for (let i = 0; i < O.verts.length; i++) for (let j = 0; j < i; j++) if (i != j) binaries.push("x"+i+"_"+j); const soln = await glpk.solve({ name: 'LP', objective: objective, subjectTo: subjectTo, binaries: binaries, }); const edges = []; for (let i = 0; i < O.verts.length; i++) for (let j = 0; j < i; j++) { if (soln.result.vars["x"+i+"_"+j] == 1 || soln.result.vars["x"+j+"_"+i] == 1) edges.push([O.verts[i], O.verts[j]]); }; return edges; }46:T4e7,E = { let MuT = T.edges.concat(M); // If we remove an edge k do we disconnect the graph? function isbridge(k) { const edges = MuT.slice(); const queue = []; queue.push(MuT[k][0]); edges.splice(k,1); while (queue.length > 0) { const j = queue[0]; queue.splice(0,1); if (j == MuT[k][1]) { // Reached our goal. return false; } // Add each of the verts we are adjacent to, and burn their bridges. for (let i = 0; i < edges.length; i++) { if (j == edges[i][0]) { queue.push(edges[i][1]); edges.splice(i,1); } else if (j == edges[i][1]) { queue.push(edges[i][0]); edges.splice(i,1); } } } return true; } let tour = [MuT[0][0]]; for (;;) { let i = tour[tour.length-1]; // Current vertex let K = -1; for (let k = 0; k < MuT.length; k++) { if (MuT[k][0] == i || MuT[k][1] == i) { K = k; // If we found a non-bridge, take it, otherwise keep looking if (!isbridge(k)) { break; } } } if (K == -1) break; tour.push((MuT[K][0] == i)? MuT[K][1] : MuT[K][0]); MuT.splice(K,1); } return tour; }47:[] 43:{"id":"dd8364c0dec3a912","slug":null,"title":"Christofides Algorithm","thumbnail":"e261d8e68c93b3dee322abde208877fed0b2f25aae3e3b0626f3f0737d1ef03b","access_level":"public","create_time":"$D2023-11-30T03:58:05.844Z","update_time":"$D2023-12-14T03:30:16.012Z","view_time":null,"first_public_time":"$D2023-12-14T03:24:47.478Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","bio":"","following":false},"version":454,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","role":"editor"},{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"f4aee92b58c0361a","slug":"travelling-salesperson-problem","title":"Travelling Salesperson Problem","owner":{"id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace"}},"type":"notebook","body":{"titling":"auto","title":"Christofides Algorithm","cells":[{"id":0,"value":"# Christofides Algorithm\n\nFirst we generate the problem.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":55,"value":"viewof n = Inputs.range([1, 20], {step: 1, label: \"Number of Cities\"}); ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"R = d3.randomLcg(1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"x = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"y = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"// Now we compute distances between them (symmetric)\ndist = Array.from(Array(n), (_, i) => Array.from(Array(n), (_, j) => \n Math.hypot(x[i]-x[j], y[i]-y[j])\n));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":421,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"## Minimum Spanning Tree\n\nNow we will compute a Minimum Spanning Tree `T` using Prim's Algorithm. While computing the tree we will also keep track of each vertex's degree, which we will need for the next step.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"T = {\n const verts = [];\n const edges = [];\n const degree = Array.from(Array(n), () => 0);\n \n verts.push(0);\n \n for (let k = 0; k < n; k++) {\n // Small optimisation: As we are searching we use degree to determine\n // which vertices haven't been included yet. The degree will be needed\n // in next step.\n \n let edge = null;\n for (const i of verts)\n for (let j = 0; j < n; j++) {\n // If j hasn't been chosen yet, and we either haven't picked an edge or its a cheaper edge\n if (!degree[j] && (!edge || dist[i][j] < dist[edge[0]][edge[1]])) {\n edge = [i, j];\n }\n }\n let [i,j] = edge;\n edges.push(edge);\n verts.push(j); degree[i]++; degree[j]++;\n }\n return {edges, verts, degree};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":426,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (const [i,j] of T.edges) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[i])\n .attr(\"y1\", y[i])\n .attr(\"x2\", x[j])\n .attr(\"y2\", y[j]);\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":397,"value":"## Mark Odd-Degree Vertices\n\nFind the subset `O` of vertices in `T` which have odd degree. There will be an even number of them (due to the Handshake Lemma). Here they have been marked in red.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":48,"value":"O = {\n const verts = [];\n for (let i = 0; i < n; i++)\n if ((T.degree[i] % 2) == 1)\n verts.push(i);\n return {verts};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"stroke\", d => (O.verts.indexOf(d) != -1) ? \"red\" : \"none\")\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (const [i,j] of T.edges) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[i])\n .attr(\"y1\", y[i])\n .attr(\"x2\", x[j])\n .attr(\"y2\", y[j]);\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":399,"value":"## Minimal Perfect Matching\n\nCompute a (perfect) matching with the lowest weight. Since there are an even number of vertices we know this will be a perfect matching. This is the most expensive step of the algorithm, and there are many different choices here, but we will use an Integer Program.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":67,"value":"glpk = {\n const module = await import('https://cdn.skypack.dev/glpk.js@4.0.1?min')\n return module.default()\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"$45","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":260,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n \n for (const [i,j] of T.edges) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#aaa\")\n .append(\"line\")\n .attr(\"x1\", x[i])\n .attr(\"y1\", y[i])\n .attr(\"x2\", x[j])\n .attr(\"y2\", y[j]);\n }\n for (const [i,j] of M) {\n svg.append(\"g\")\n .attr(\"stroke\", \"red\")\n .append(\"line\")\n .attr(\"x1\", x[i])\n .attr(\"y1\", y[i])\n .attr(\"x2\", x[j])\n .attr(\"y2\", y[j]);\n }\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"stroke\", d => (O.verts.indexOf(d) != -1) ? \"red\" : \"none\")\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"## Euler Cycle\n\nNow we find a Euler Cycle of the union `T U M` as a multigraph. Here we will use Fleury's algorithm, though more efficient algorithms exist. We pick a vertex arbitrarily to begin our cycle, and then continue travelling along connected edges, removing them as we go. At every step we favor edges that are not bridges when possible (edges which would disconnect the graph).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":97,"value":"$46","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (let i = 0; i < E.length-1; i++) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[E[i]])\n .attr(\"y1\", y[E[i]])\n .attr(\"x2\", x[E[i+1]])\n .attr(\"y2\", y[E[i+1]]);\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"## Shortcutting the Multigraph\n\nNow we remove duplicates from the Euler Cycle so that only the first appearance of a vertex remains. This completes the construction of our approximate solution to the TSP.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"tour = {\n // Shortcutting\n const result = [];\n for (let i = 0; i < E.length; i++)\n if (result.indexOf(E[i]) == -1)\n result.push(E[i]);\n result.push(result[0]); // Close circuit\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (let i = 0; i < tour.length-1; i++) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[tour[i]])\n .attr(\"y1\", y[tour[i]])\n .attr(\"x2\", x[tour[i+1]])\n .attr(\"y2\", y[tour[i+1]]);\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":446,"value":"length = {\n let total = 0.0;\n for (let i = 0; i+1 < tour.length; i++)\n total += dist[tour[i]][tour[i+1]];\n return total;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W47","stdlib":"1"}} 44:"$43:body"