2c:null 2d:["$","title",null,{"children":"History graph rendering | senritsu | Observable"}] 32:T48b,# History graph rendering The goal is the ability to easily examine alternate branching history, and continue from any point. The history is assumed to be an [arborescence](https://en.wikipedia.org/wiki/Arborescence_(graph_theory), so there are no merges or crossings in the graph. Additionally, as the history is supposed to describe real-time interactions, all timestamps of nodes should also be monotonically increasing and there can be no nodes with an identical timestamp. Compared to the typical git graph, the requirements differ quite a bit, as there are potentially lots of leaf nodes and the number of branches is monotonically increasing. To balance that out, each node (except the root) is guaranteed to have exactly one parent. If this should still be rendered in a way to not keep a manageable width at any point, as well as render in a logical historical order, it needs some tricks to deal with inevitable crossing lines. Color could also be a vital tool to keep things visually distinct. Ideally, it should also be easy to display customizable data for each history node—or a custom subset of nodes—adjacent to or even within the graph.33:T715,renderNaive = (nodes) => { nodes = [...nodes].sort(({t: t1}, {t: t2}) => t1 - t2) const rows = {} const columns = {} const firstChildren = {} let nextColumn = 1 const renderNode = (node) => { const inheritParentColumn = node.parent && !firstChildren[node.parent] if (inheritParentColumn) { columns[node.id] = columns[node.parent] firstChildren[node.parent] = node.id } else { columns[node.id] = nextColumn nextColumn += 1 } rows[node.id] = 2 * nodes.length - 2 * node.t - 1 return htl.html.fragment` ${node.id}

${node.parent ? htl.html.fragment`

` : null } ` } const items = nodes.map(renderNode) const grid = htl.html`

${items}

` return grid }34:[] 30:{"id":"4b36ecfc2f2eceec","slug":null,"title":"History graph rendering","thumbnail":"30b94e4b95e644acfc3c36b40f67413bb0824a870108ce1c5a7a12d707f20821","access_level":"public","create_time":"$D2023-10-09T18:23:29.125Z","update_time":"$D2023-11-14T08:40:59.989Z","view_time":null,"first_public_time":"$D2023-10-09T18:23:29.125Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"c62aba2ac21021cb","login":"senritsu","name":"","avatar_url":"https://avatars-next.observableusercontent.com/2702f8a42e439426df2d134af708f1c3c3bdfa1a8434dfbeec26dfd7ce6bdcec","tier":"starter_2024"},"version":217,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"cc9712af774c2953","login":"senritsu","name":"","avatar_url":"https://avatars-next.observableusercontent.com/2702f8a42e439426df2d134af708f1c3c3bdfa1a8434dfbeec26dfd7ce6bdcec","tier":null}],"members":[{"type":"individual","id":"cc9712af774c2953","login":"senritsu","name":"","avatar_url":"https://avatars-next.observableusercontent.com/2702f8a42e439426df2d134af708f1c3c3bdfa1a8434dfbeec26dfd7ce6bdcec","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"History graph rendering","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":38,"value":"## Naive approach, no optimizations\n\nJust render the tree and keep each branch in its own column, branching always to the right.\n\nThis approach does scale beyond only a few branches, and is used as a baseline.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":52,"value":"renderNaive(small)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"## Test data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":45,"value":"small = [\n {t: 0, id: 'R'},\n {t: 1, id: 'A1', parent: 'R'},\n {t: 2, id: 'A2', parent: 'A1'},\n {t: 3, id: 'A3', parent: 'A2'},\n {t: 4, id: 'A4', parent: 'A3'},\n {t: 5, id: 'A5', parent: 'A4'},\n {t: 6, id: 'B1', parent: 'A4'},\n {t: 7, id: 'B2', parent: 'B1'},\n {t: 8, id: 'C1', parent: 'A2'},\n {t: 9, id: 'C2', parent: 'C1'},\n {t: 10, id: 'B3', parent: 'B2'},\n {t: 11, id: 'D1', parent: 'B2'},\n {t: 12, id: 'A6', parent: 'A5'},\n]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"## References\n- https://pvigier.github.io/2019/05/06/commit-graph-drawing-algorithms.html\n- https://en.wikipedia.org/wiki/Topological_sorting","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 31:"$30:body"