2f:T41a,### Encoding The Graph6 format, as well as some related formats, is [described roughly here](https://users.cecs.anu.edu.au/~bdm/data/formats.html). The general idea is to write down the zeros and ones above the diagonal of the adjacency matrix representation of the graph as a bit string. That bit string is then partitioned into groups of length 6, which can be recorded as bytes and easily mapped to ASCII characters. The format is described in [painful detail here](https://users.cecs.anu.edu.au/~bdm/data/formats.txt). The encoding and decoding functions defined in this notebook are based on that description. The `encode_graph` function accepts a graph as described in the Javascript format section above and returns the Graph6 string representation of that graph. These functions work well enough for graphs with up to 400 vertices and 10000 edges but get intolerably slow much past that. This is not a serious drawback here, since the main objective here is visualization. A better implementation could be written with bitwise operators.30:[{"id":"350de668766caa33301484c17d7739982bd2c70bd111583aae8825351813e973af9d3c126336f49b3e7a94fe480bbc9a7444af2451cbf1eaa1bdab77e1f7dbb3","href":"https://static.observableusercontent.com/files/350de668766caa33301484c17d7739982bd2c70bd111583aae8825351813e973af9d3c126336f49b3e7a94fe480bbc9a7444af2451cbf1eaa1bdab77e1f7dbb3","name":"graphs.g6","type":"application/octet-stream","lastModified":1667907769869.231,"size":5855}] 2d:{"title":"Graph6","cells":[{"id":0,"value":"# Graph6\n\nGraph6 is a compact, ASCII format for storing small, dense, simple graphs. Here, for example, is a graph with ${G.n} vertices and ${G.edges.length} edges:","pinned":false,"hidden":false,"mode":"md"},{"id":1132,"value":"{\n let container = d3.create(\"div\");\n let graph_div = container.append(\"div\");\n d3\n .graphviz(graph_div.node())\n .engine(\"neato\")\n .width(width)\n .fit(true) // Doesn't quite work; see transform in penultimate line.\n .zoom(false) // Re-transform for fit breaks the zoom.\n .renderDot(`graph{\n node[shape=point] \n ${d3.range(G.n).join(\";\")}\n ${G.edges.map(([i, j]) => `${i}--${j}`).join(\";\")}\n }`);\n\n return container.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1139,"value":"

\n The Graph6 representation of that graph is: \n

${encode_graph(G)}

","pinned":false,"hidden":false,"mode":"html"},{"id":1149,"value":"## A lot of graphs\n\nThis notebook implements functions for encoding and decoding Graph6. This allows us to explore certain graph databases. For example, Brendan McKay (the creator of Graph6) has over a billion small graphs stored in Graph6 format [on his web page](http://users.cecs.anu.edu.au/~bdm/data/graphs.html). Using his data, the interactive tool below allows you to explore all ${graphs.length} connected graphs with at least two vertices and at most seven vertices.","pinned":false,"hidden":false,"mode":"md"},{"id":1058,"value":"viewof graph_num = step_slider(0, graphs.length - 1, d3.randomInt(100, 1000)())","pinned":false,"hidden":false,"mode":"ojs"},{"id":1025,"value":"{\n let G = decode_graph(graphs[graph_num]);\n let container = d3.create(\"div\").style(\"height\", \"340px\");\n container.append(\"div\").text(`${G.n} vertices and ${G.edges.length} edges`);\n let graph_div = container.append(\"div\");\n d3\n .graphviz(graph_div.node())\n .engine(\"neato\")\n .width(width)\n .fit(true) // Doesn't quite work; see transform in penultimate line.\n .zoom(false) // Re-transform for fit breaks the zoom.\n .renderDot(`graph{\n node[shape=point] \n ${d3.range(G.n).join(\";\")}\n ${G.edges.map(([i, j]) => `${i}--${j}`).join(\";\")}\n }`);\n\n return container.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1183,"value":"## Code","pinned":false,"hidden":false,"mode":"md"},{"id":653,"value":"### Javascript format \n\nGraphs on this page are represented as objects of the form:\n\n {\n n, // Number of vertices taken to be 0,1,...,n-1\n edges // A list of pairs of the form [i,j] where 0 <= i < j < n\n }\n\nHere's a simple example:","pinned":false,"hidden":false,"mode":"md"},{"id":1191,"value":"simple_graph = ({\n n: 5,\n edges: [[0,1],[0,2],[3,4]]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1198,"value":"Of course, that's easy to translate that to a number of other useful formats. We could draw the graph with graphviz, for example:","pinned":false,"hidden":false,"mode":"md"},{"id":1193,"value":"dot`graph{\n ${d3.range(simple_graph.n).join(\";\")}\n ${simple_graph.edges.map(([i, j]) => `${i}--${j}`).join(\";\")}\n }`","pinned":true,"hidden":false,"mode":"ojs"},{"id":1206,"value":"The `random_graph` function generates a random graph with `n` vertices and edge probability `p` in this format:","pinned":false,"hidden":false,"mode":"md"},{"id":662,"value":"function random_graph(n, p) {\n let edges = d3\n .range(n)\n .map((i) =>\n d3\n .range(i + 1, n)\n .map((j) => (d3.randomUniform(0, 1)() < p ? [[i, j]] : []))\n )\n .flat(2);\n\n return { n, edges };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1211,"value":"The graph at the top of the page is generated using `random_graph`:","pinned":false,"hidden":false,"mode":"md"},{"id":1204,"value":"G = {\n let n = d3.randomInt(10, 15)();\n return random_graph(n, 0.8 / Math.sqrt(n));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":319,"value":"$2f","pinned":false,"hidden":false,"mode":"md"},{"id":301,"value":"function encode_graph(G) {\n let x = encode_edges(G.edges, G.n);\n let bytes = N(G.n).concat(R(x));\n return bytes.map((c) => String.fromCharCode(c)).join(\"\");\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":294,"value":"function encode_edges(e, n) {\n let ee = e.map(([i, j]) => `${i}--${j}`);\n let bits = [];\n for (let j = 1; j < n; j++) {\n for (let i = 0; i < j; i++) {\n if (ee.indexOf(`${i}--${j}`) > -1) {\n bits.push(1);\n } else {\n bits.push(0);\n }\n }\n }\n return bits.join(\"\");\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":50,"value":"function pad6(s) {\n let r = s.length % 6;\n if (r == 0) {\n return s;\n } else {\n let p = Array(6 - r)\n .fill(0)\n .join(\"\");\n return s + p;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":107,"value":"function R(x) {\n let s;\n if (typeof x == \"number\") {\n s = x.toString(2);\n s = s.split(\"\").reverse().join(\"\");\n s = pad6(s);\n s = s.split(\"\").reverse().join(\"\");\n } else {\n s = pad6(x);\n }\n let parts = [];\n while (s.length > 0) {\n parts.push(s.slice(0, 6));\n s = s.slice(6);\n }\n return parts.map((s) => +`0b${s}` + 63);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":135,"value":"function N(n) {\n if (0 <= n && n <= 62) {\n return [n + 63];\n } else if (63 <= n && n <= 258047) {\n let r = R(n);\n if (r.length == 1) {\n r = [126, 63, 63].concat(r);\n } else if (r.length == 2) {\n r = [126, 63].concat(r);\n } else if (r.length == 3) {\n r = [126].concat(r);\n }\n return r;\n } else if (258048 <= n) {\n let r = R(n);\n if (r.length == 3) {\n r = [126, 126, 63, 63, 63].concat(r);\n } else if (r.length == 4) {\n r = [126, 126, 63, 63].concat(r);\n } else if (r.length == 5) {\n r = [126, 126, 63].concat(r);\n }\n return r;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":327,"value":"### Decoding\n\nThese functions invert the process described in the previous section. Thus, `decode_graph` accepts a Graph6 string and returns a Javascript graph as described in the Graph format section above.","pinned":false,"hidden":false,"mode":"md"},{"id":613,"value":"function decode_graph(g6) {\n let n = get_n(g6);\n let bit_string;\n if (n < 63) {\n bit_string = get_bit_string(g6.slice(1), n);\n } else if (n < 258048) {\n bit_string = get_bit_string(g6.slice(4), n);\n } else {\n bit_string = get_bit_string(g6.slice(8), n);\n }\n let edges = [];\n let idx = 0;\n for (let j = 1; j < n; j++) {\n for (let i = 0; i < j; i++) {\n if (bit_string[idx] == \"1\") {\n edges.push([i, j]);\n }\n idx++;\n }\n }\n return { n, edges };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":397,"value":"function get_bit_string(bytes, n) {\n return bytes\n .split(\"\")\n .map((ss) => ss.charCodeAt(0))\n .map(function (x) {\n let xx = (x - 63).toString(2);\n if (xx.length < 6) {\n xx = pad6Left(xx);\n // xx = xx.split(\"\").reverse().join(\"\");\n // xx = pad6(xx);\n // xx = xx.split(\"\").reverse().join(\"\");\n }\n return xx;\n })\n .join(\"\")\n .slice(0, (n * (n - 1)) / 2);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":329,"value":"function get_n(s) {\n let first_byte = s.charCodeAt(0);\n let second_byte = s.charCodeAt(1);\n if (first_byte < 126) {\n return first_byte - 63;\n } else if (second_byte < 126) {\n let bits = s\n .slice(1, 4)\n .split(\"\")\n .map((c) => c.charCodeAt(0) - 63)\n .map((b) => pad6Left(`${b.toString(2)}`))\n .join(\"\");\n return +`0b${bits}`;\n } else {\n let bits = s\n .slice(4)\n .split(\"\")\n .map((c) => c.charCodeAt(0) - 63)\n .map((b) => pad6Left(`${b.toString(2)}`))\n .join(\"\");\n return +`0b${bits}`;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":644,"value":"pad6Left = (s) =>\n pad6(s.split(\"\").reverse().join(\"\")).split(\"\").reverse().join(\"\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1213,"value":"## Imports","pinned":false,"hidden":false,"mode":"md"},{"id":1002,"value":"graphs = (await FileAttachment(\"graphs.g6\").text()).split(\"\\n\").slice(0, -1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1022,"value":"d3 = require(\"d3@7\", \"d3-graphviz@2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1106,"value":"import { step_slider } from \"59730aabd7354b99\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W30","stdlib":"1","titling":"auto"}