2b:null 2c:["$","title",null,{"children":"Tangled tree visualization | Hurrarah Hamid's Workspace | Observable"}] 31:T510,intro = md`A tree with multiple inheritance (sometimes called *tangled tree*) cannot be represented by using a classic tree visualization. It is technically a directed acyclic graph (DAG) with one (or more) nodes identified as root. Using a graph visualization technique solves the issue, but poorly represents some peculiarities of a quasi-tree structure. This visualization tries to address the representation of a tangled tree (a genealogy in this specific example). The layout and basic technique is the same underlying [Geneaquilts](https://aviz.fr/Research/Geneaquilts) [[1](#footnote1)], but with curved links instead of matrices. Metro-style bundling is used when a parent node appears in multiple "families", and the layout is made more compact on the y axis. The intention is for the graphic to be more readily understood, while losing some of the advantages of Geneaquilts (e.g., representing a union without children). See also [this older, simpler example](https://beta.observablehq.com/@nitaku/tangled-tree-visualization). The technique can also be applied to other types of tangled trees. Such structures are commonly found in computational linguistics (thesauri, some ontologies, wordnets). (Thanks to [@trebor](https://observablehq.com/@trebor) for making it more reusable!)`32:T6a9,renderChart = (data, options={}) => { options.color ||= (d, i) => color(i); const tangleLayout = constructTangleLayout(_.cloneDeep(data), options); return svg` `; } 33:Tce3,data = [ [{'id': "Pseudomonas Aeruginosa"}], [{'id': 'CORE', 'parents': ["Pseudomonas Aeruginosa"], 'depth': 0}, {'id': 'PLUS', 'parents': ["Pseudomonas Aeruginosa"], 'depth': 0}], [{'id': 'AMR', 'parents': ['CORE'], 'depth': 1}, {'id': 'STRESS', 'parents': ['PLUS'], 'depth': 1}, {'id': 'VIRULENCE', 'parents': ['PLUS'], 'depth': 1}], [{'id': 'BETA-LACTAM', 'parents': ['AMR'], 'depth': 2}, {'id': 'TETRACYCLINE', 'parents': ['AMR'], 'depth': 2}, {'id': 'FUSIDIC ACID', 'parents': ['AMR'], 'depth': 2}, {'id': 'AMINOGLYCOSIDE', 'parents': ['AMR'], 'depth': 2}, {'id': 'FOSFOMYCIN', 'parents': ['AMR'], 'depth': 2}, {'id': 'METAL', 'parents': ['STRESS'], 'depth': 2}, {'id': 'BIOCIDE', 'parents': ['STRESS'], 'depth': 2}, {'id': 'hld', 'parents': ['VIRULENCE'], 'Method': 'EXACTX', 'Accession of closest sequence': 'AAC21574.1', 'depth': 2}], [{'id': 'blaI', 'parents': ['BETA-LACTAM'], 'Method': 'BLASTP', 'Accession of closest sequence': 'WP_001284656.1', 'depth': 3}, {'id': 'blaR1', 'parents': ['BETA-LACTAM'], 'Method': 'HMM', 'Accession of closest sequence': 'WP_001096386.1', 'depth': 3}, {'id': 'blaZ', 'parents': ['BETA-LACTAM'], 'Method': 'BLASTP', 'Accession of closest sequence': 'WP_000733281.1', 'depth': 3}, {'id': 'METHICILLIN', 'parents': ['BETA-LACTAM'], 'depth': 3}, {'id': 'tet(K)', 'parents': ['TETRACYCLINE'], 'Method': 'EXACTP', 'Accession of closest sequence': 'WP_000492283.1', 'depth': 3}, {'id': 'fusB', 'parents': ['FUSIDIC ACID'], 'Method': 'EXACTP', 'Accession of closest sequence': 'WP_000855537.1', 'depth': 3}, {'id': 'AMIKACIN/GENTAMICIN/KANAMYCIN/TOBRAMYCIN', 'parents': ['AMINOGLYCOSIDE'], 'depth': 3}, {'id': 'fosB', 'parents': ['FOSFOMYCIN'], 'Method': 'BLASTP', 'Accession of closest sequence': 'WP_002467687.1', 'depth': 3}, {'id': 'ARSENIC', 'parents': ['METAL'], 'depth': 3}, {'id': 'MERCURY', 'parents': ['METAL'], 'depth': 3}, {'id': 'QUATERNARY AMMONIUM', 'parents': ['BIOCIDE'], 'depth': 3}], [{'id': 'mecA', 'parents': ['METHICILLIN'], 'Method': 'EXACTP', 'Accession of closest sequence': 'WP_000721310.1', 'depth': 4}, {'id': 'mecR1', 'parents': ['METHICILLIN'], 'Method': 'PARTIALP', 'Accession of closest sequence': 'WP_000952923.1', 'depth': 4}, {'id': "aac(6')-Ie/aph(2'')-Ia", 'parents': ['AMIKACIN/GENTAMICIN/KANAMYCIN/TOBRAMYCIN'], 'Method': 'EXACTP', 'Accession of closest sequence': 'WP_001028144.1', 'depth': 4}, {'id': 'ARSENITE', 'parents': ['ARSENIC'], 'depth': 4}, {'id': 'merA', 'parents': ['MERCURY'], 'Method': 'HMM', 'Accession of closest sequence': 'AAA83977.1', 'depth': 4}, {'id': 'qacA', 'parents': ['QUATERNARY AMMONIUM'], 'Method': 'EXACTP', 'Accession of closest sequence': 'WP_000622776.1', 'depth': 4}, {'id': 'qacR', 'parents': ['QUATERNARY AMMONIUM'], 'Method': 'EXACTX', 'Accession of closest sequence': 'ADK23698.1', 'depth': 4}], [{'id': 'arsD', 'parents': ['ARSENITE'], 'Method': 'HMM', 'Accession of closest sequence': 'KAA9473342.1', 'depth': 5}, {'id': 'arsB', 'parents': ['ARSENITE'], 'Method': 'BLASTP', 'Accession of closest sequence': 'AAA25637.1', 'depth': 5}]]34:T12bb,constructTangleLayout = (levels, options={}) => { // precompute level depth levels.forEach((l, i) => l.forEach(n => (n.level = i))); var nodes = levels.reduce((a, x) => a.concat(x), []); var nodes_index = {}; nodes.forEach(d => (nodes_index[d.id] = d)); // objectification nodes.forEach(d => { d.parents = (d.parents === undefined ? [] : d.parents).map( p => nodes_index[p] ); }); // precompute bundles levels.forEach((l, i) => { var index = {}; l.forEach(n => { if (n.parents.length == 0) { return; } var id = n.parents .map(d => d.id) .sort() .join('-X-'); if (id in index) { index[id].parents = index[id].parents.concat(n.parents); } else { index[id] = { id: id, parents: n.parents.slice(), level: i, span: i - d3.min(n.parents, p => p.level) }; } n.bundle = index[id]; }); l.bundles = Object.keys(index).map(k => index[k]); l.bundles.forEach((b, i) => (b.i = i)); }); var links = []; nodes.forEach(d => { d.parents.forEach(p => links.push({ source: d, bundle: d.bundle, target: p }) ); }); var bundles = levels.reduce((a, x) => a.concat(x.bundles), []); // reverse pointer from parent to bundles bundles.forEach(b => b.parents.forEach(p => { if (p.bundles_index === undefined) { p.bundles_index = {}; } if (!(b.id in p.bundles_index)) { p.bundles_index[b.id] = []; } p.bundles_index[b.id].push(b); }) ); nodes.forEach(n => { if (n.bundles_index !== undefined) { n.bundles = Object.keys(n.bundles_index).map(k => n.bundles_index[k]); } else { n.bundles_index = {}; n.bundles = []; } n.bundles.sort((a,b) => d3.descending(d3.max(a, d => d.span), d3.max(b, d => d.span))) n.bundles.forEach((b, i) => (b.i = i)); }); links.forEach(l => { if (l.bundle.links === undefined) { l.bundle.links = []; } l.bundle.links.push(l); }); // layout const padding = 8; const node_height = 22; const node_width = 100; const bundle_width = 14; const level_y_padding = 26; const metro_d = 4; const min_family_height = 22; options.c ||= 16; const c = options.c; options.bigc ||= node_width+c; nodes.forEach( n => (n.height = (Math.max(1, n.bundles.length) - 1) * metro_d) ); var x_offset = padding; var y_offset = padding; levels.forEach(l => { x_offset += l.bundles.length * bundle_width; y_offset += level_y_padding; l.forEach((n, i) => { n.x = n.level * node_width + x_offset; n.y = node_height + y_offset + n.height / 2; y_offset += node_height + n.height; }); }); var i = 0; levels.forEach(l => { l.bundles.forEach(b => { b.x = d3.max(b.parents, d => d.x) + node_width + (l.bundles.length - 1 - b.i) * bundle_width; b.y = i * node_height; }); i += l.length; }); links.forEach(l => { l.xt = l.target.x; l.yt = l.target.y + l.target.bundles_index[l.bundle.id].i * metro_d - (l.target.bundles.length * metro_d) / 2 + metro_d / 2; l.xb = l.bundle.x; l.yb = l.bundle.y; l.xs = l.source.x; l.ys = l.source.y; }); // compress vertical space var y_negative_offset = 0; levels.forEach(l => { y_negative_offset += -min_family_height + d3.min(l.bundles, b => d3.min(b.links, link => link.ys - 2*c - (link.yt + c)) ) || 0; l.forEach(n => (n.y -= y_negative_offset)); }); // very ugly, I know links.forEach(l => { l.yt = l.target.y + l.target.bundles_index[l.bundle.id].i * metro_d - (l.target.bundles.length * metro_d) / 2 + metro_d / 2; l.ys = l.source.y; l.c1 = l.source.level - l.target.level > 1 ? Math.min(options.bigc, l.xb-l.xt, l.yb-l.yt)-c : c; l.c2 = c; }); var layout = { width: d3.max(nodes, n => n.x) + node_width + 2 * padding, height: d3.max(nodes, n => n.y) + node_height / 2 + 2 * padding, node_height, node_width, bundle_width, level_y_padding, metro_d }; // Assuming 'svg' is a reference to your SVG element function downloadSVG(svg, filename = 'graphic.svg') { const svgData = new XMLSerializer().serializeToString(svg); const blob = new Blob([svgData], { type: 'image/svg+xml;charset=utf-8' }); const url = URL.createObjectURL(blob); const link = document.createElement('a'); link.href = url; link.download = filename; document.body.appendChild(link); link.click(); document.body.removeChild(link); } // Usage const svg = document.querySelector('svg'); // Adjust as needed downloadSVG(svg); return { levels, nodes, nodes_index, links, bundles, layout }; }35:[] 2f:{"id":"726b33bca5f615b3","slug":null,"title":"Tangled tree visualization","thumbnail":"f97e5964d4f588fe55aa68f9a268e4b2f038338e292cb20738411f1280ea6dbc","access_level":"public","create_time":"$D2024-11-28T21:06:39.828Z","update_time":"$D2024-12-03T10:06:00.140Z","view_time":null,"first_public_time":"$D2024-11-28T21:06:39.828Z","has_unpublished_edits":null,"fork":{"id":"4cab522856cbfdde","slug":"tangled-tree-visualization-ii","title":"Tangled tree visualization","owner":{"id":"26c2ccc018e1ea02","login":"nitaku","name":"Matteo Abrate"}},"stars":0,"starred":false,"owner":{"type":"team","id":"886f7cc9c73275fe","login":"hurrarah-hamid-ws","name":"Hurrarah Hamid's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/6053e3c1d41e1119b804575a20f0ad241fc27d82223be567d9bc6ab3755b6719","tier":"starter_2024"},"version":898,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"0107f625444b6bbc","login":"hurrarah-hamid","name":"Hurrarah Hamid","avatar_url":"https://avatars-next.observableusercontent.com/568bb75adb75e87704f93455e5fbaaf5963a5b519bd50cda687ebb6b71abde7d","tier":null}],"members":[{"type":"individual","id":"0107f625444b6bbc","login":"hurrarah-hamid","name":"Hurrarah Hamid","avatar_url":"https://avatars-next.observableusercontent.com/568bb75adb75e87704f93455e5fbaaf5963a5b519bd50cda687ebb6b71abde7d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Tangled tree visualization","cells":[{"id":0,"value":"md`# Tangled tree visualization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":527,"value":"renderChart(data)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":556,"value":"md`## Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":523,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"color = d3.scaleOrdinal(d3.schemeDark2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":435,"value":"background_color = 'white'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":532,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"d3 = require('d3-scale', 'd3-scale-chromatic', 'd3-array')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":521,"value":"_ = require(\"lodash\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":546,"value":"import {footnote} from \"@jashkenas/markdown-style-footnotes\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":535,"value":"md`## References`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":539,"value":"footnote1 = footnote(\"intro\", 1, `A. Bezerianos, P. Dragicevic, J. Fekete, J. Bae and B. Watson, \"GeneaQuilts: A System for Exploring Large Genealogies,\" in IEEE Transactions on Visualization and Computer Graphics, vol. 16, no. 6, pp. 1073-1081, Nov.-Dec. 2010, doi: 10.1109/TVCG.2010.159.`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"