Rendering a directed graph on top of an HTML table, one node per row

New To Observable
1

Hi everyone, I have a very specific problem that it seems like it ought to be possible to solve it with Observable (or low-level D3) but I cannot figure out how to do it.

I have an HTML table. Each row of this table presents data related to one node in a directed acyclic graph. (Specifically, the table presents a VCS repository’s commit history with annotations.) I want one column of the table to show the graph itself. The way that needs to work is:

  1. The table rows are annotated with two HTML data-* attributes. One gives that row’s node a unique identifier (a truncated commit hash, if you’re familiar), and the second lists each of the nodes with edges inbound to the row’s node. (The table generator could be adjusted to make this list the outbound edges, if that would make things easier.)
  2. The table rows are topologically sorted; the inbound edges to each row will always come from rows below it.
  3. One table cell in each row (that is, one column) is given a fixed width and empty contents. This reserves space for the graph.
  4. The node itself should be represented as a dot vertically centered within that table cell. Its horizontal position (within the cell) is up to the layout algorithm.
  5. Paths are to be drawn connecting the dots according to the edges. This should look like a vertically-oriented mermaid.js gitgraph diagram; in particular, the layout algorithm needs to try to satisfy all of these constraints:
    • nodes should be organized into vertical chains which are as long as possible
    • each such chain should be given its own color, drawing from a palette
    • the vertical lines generated by these chains should be sorted so the shorter chains are to the left of the longer ones
    • crossings should, of course, be minimized

The parts I’m especially stuck on are:

  • I sort-of understand how to select a set of table rows from the page, but I can’t figure out how to get the data attributes out of each row in the selection and turn them into inputs to a D3 layout algorithm.
  • I am completely stumped when it comes to implementing rule 4, that is, the requirement that the circle representing each row’s node must be placed within the content box of a particular table cell and vertically centered on that box. Is this even possible? (This requirement, incidentally, is why I cannot “just” use mermaid.js.)
  • None of the existing layout algorithms seem like they are tailored for this job, so I could use advice on which of them will do the least bad job. I don’t want to spend a lot of time down a graph-layout rathole.
Click for 25 rows of the actual table. Identifying details have been redacted but the commit graph data is real. 
<table>
  <tr data-commit="010dd91" data-parents="8ce7256"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">010dd91</th><td class="c-ts"><time datetime="2022-42-21T19:42Z">19:42</time></td><td class="c-auth">alice</td><td class="c-subj">lorem ipsum</td></tr>
  <tr data-commit="8ce7256" data-parents="b9326d8"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">8ce7256</th><td class="c-ts"><time datetime="2022-11-21T18:11Z">18:11</time></td><td class="c-auth">alice</td><td class="c-subj">dolor sit</td></tr>
  <tr data-commit="b9326d8" data-parents="e7cc095"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">b9326d8</th><td class="c-ts"><time datetime="2022-17-21T16:17Z">16:17</time></td><td class="c-auth">alice</td><td class="c-subj">amet consectetur</td></tr>
  <tr data-commit="e7cc095" data-parents="b5005b4"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">e7cc095</th><td class="c-ts"><time datetime="2022-10-20T20:10Z">Dec 20, 20:10</time></td><td class="c-auth">bob</td><td class="c-subj">adipiscing elit</td></tr>
  <tr data-commit="b5005b4" data-parents="2b246e0"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">b5005b4</th><td class="c-ts"><time datetime="2022-16-20T19:16Z">19:16</time></td><td class="c-auth">alice</td><td class="c-subj">sed do</td></tr>
  <tr data-commit="2b246e0" data-parents="396cf53 f30ddbe"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">2b246e0</th><td class="c-ts"><time datetime="2022-58-19T21:58Z">Dec 19, 21:58</time></td><td class="c-auth">alice</td><td class="c-subj">Merge branch 'feature-alpha' into develop</td></tr>
  <tr data-commit="f30ddbe" data-parents="dc9ef4c"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">f30ddbe</th><td class="c-ts"><time datetime="2022-17-19T17:17Z">17:17</time></td><td class="c-auth">carol</td><td class="c-subj">eiusmod tempor</td></tr>
  <tr data-commit="dc9ef4c" data-parents="6d41647"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">dc9ef4c</th><td class="c-ts"><time datetime="2022-00-19T21:00Z">Nov 19, 21:00</time></td><td class="c-auth">bob</td><td class="c-subj">incididunt ut</td></tr>
  <tr data-commit="396cf53" data-parents="6d41647"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">396cf53</th><td class="c-ts"><time datetime="2022-38-19T20:38Z">Dec 19, 20:38</time></td><td class="c-auth">alice</td><td class="c-subj">labore et</td></tr>
  <tr data-commit="6d41647" data-parents="a5034f6 91f9013"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">6d41647</th><td class="c-ts"><time datetime="2022-50-18T20:50Z">Nov 18, 20:50</time></td><td class="c-auth">alice</td><td class="c-subj">Merge branch 'feature-delta' into develop</td></tr>
  <tr data-commit="91f9013" data-parents="3d361ce"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">91f9013</th><td class="c-ts"><time datetime="2022-40-18T20:40Z">20:40</time></td><td class="c-auth">alice</td><td class="c-subj">dolore magna</td></tr>
  <tr data-commit="3d361ce" data-parents="9a6840b"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">3d361ce</th><td class="c-ts"><time datetime="2022-37-17T23:37Z">Nov 17, 23:37</time></td><td class="c-auth">alice</td><td class="c-subj">aliqua ut</td></tr>
  <tr data-commit="9a6840b" data-parents="de65d56"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">9a6840b</th><td class="c-ts"><time datetime="2022-15-17T23:15Z">23:15</time></td><td class="c-auth">alice</td><td class="c-subj">enim ad</td></tr>
  <tr data-commit="de65d56" data-parents="e00796c"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">de65d56</th><td class="c-ts"><time datetime="2022-30-10T21:30Z">Nov 10, 21:30</time></td><td class="c-auth">alice</td><td class="c-subj">minim veniam</td></tr>
  <tr data-commit="a5034f6" data-parents="8b19131 d921692"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">a5034f6</th><td class="c-ts"><time datetime="2022-45-18T20:45Z">Nov 18, 20:45</time></td><td class="c-auth">alice</td><td class="c-subj">Merge branch 'feature-beta' into develop</td></tr>
  <tr data-commit="d921692" data-parents="886fa2b 050a17b"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">d921692</th><td class="c-ts"><time datetime="2022-44-08T15:44Z">Nov 08, 15:44</time></td><td class="c-auth">bob</td><td class="c-subj">Merge branch 'develop' into feature-beta</td></tr>
  <tr data-commit="886fa2b" data-parents="9b03422"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">886fa2b</th><td class="c-ts"><time datetime="2022-57-31T21:57Z">Oct 31, 21:57</time></td><td class="c-auth">bob</td><td class="c-subj">quis nostrud</td></tr>
  <tr data-commit="8b19131" data-parents="e00796c df1a36d"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">8b19131</th><td class="c-ts"><time datetime="2022-44-18T20:44Z">Nov 18, 20:44</time></td><td class="c-auth">alice</td><td class="c-subj">Merge branch 'feature-gamma' into develop</td></tr>
  <tr data-commit="df1a36d" data-parents="fa5ee6f 050a17b"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">df1a36d</th><td class="c-ts"><time datetime="2022-44-08T15:44Z">Nov 08, 15:44</time></td><td class="c-auth">bob</td><td class="c-subj">Merge branch 'develop' into feature-gamma</td></tr>
  <tr data-commit="fa5ee6f" data-parents="1db729e"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">fa5ee6f</th><td class="c-ts"><time datetime="2022-20-01T02:20Z">Nov 01, 02:20</time></td><td class="c-auth">bob</td><td class="c-subj">exercitation ullamco</td></tr>
  <tr data-commit="1db729e" data-parents="aa1f1e1"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">1db729e</th><td class="c-ts"><time datetime="2022-41-01T00:41Z">00:41</time></td><td class="c-auth">bob</td><td class="c-subj">laboris nisi</td></tr>
  <tr data-commit="aa1f1e1" data-parents="9b03422"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">aa1f1e1</th><td class="c-ts"><time datetime="2022-52-31T20:52Z">Oct 31, 20:52</time></td><td class="c-auth">bob</td><td class="c-subj">ut aliquip</td></tr>
  <tr data-commit="e00796c" data-parents="050a17b"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">e00796c</th><td class="c-ts"><time datetime="2022-07-10T21:07Z">Nov 10, 21:07</time></td><td class="c-auth">alice</td><td class="c-subj">ex ea</td></tr>
  <tr data-commit="050a17b" data-parents="79ade60"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">050a17b</th><td class="c-ts"><time datetime="2022-35-07T21:35Z">Nov 07, 21:35</time></td><td class="c-auth">bob</td><td class="c-subj">commodo consequat</td></tr>
  <tr data-commit="79ade60" data-parents="9b03422"><td class="c-graph"></td><td class="c-refs"></td><th class="c-cid" scope="row">79ade60</th><td class="c-ts"><time datetime="2022-21-07T21:21Z">21:21</time></td><td class="c-auth">bob</td><td class="c-subj">duis aute</td></tr>
  <tr data-commit="9b03422" data-parents="d38948a"><td class="c-graph"></td><td class="c-refs"><span class="r-tag">v0.7.2</span></td><th class="c-cid" scope="row">9b03422</th><td class="c-ts"><time datetime="2022-52-30T12:52Z">Oct 30, 12:52</time></td><td class="c-auth">alice</td><td class="c-subj">bump version number</td></tr>
</table>
2

I’m not sure you’ll be able to mix HTML tables and layout algorithms - you may have to pick one or the other.

Can you say more about why you want to use a table? E.g., do you plan to make the table sortable based on different criteria?

Similarly, what do you expect the layout algorithm to do? E.g., arrange nodes horizontally so that their connections don’t overlap?

Lastly, do you plan to draw responsive edges that can adjust to varying row heights (e.g. multiline subjects) and node distances, or do you intend to set fixed row heights?

3

… Because I’m presenting tabular data?? Look at https://github.com/observablehq/framework/commits/main/. The material presented there is, semantically, a table. My table has different columns but it is the same general idea.

Github actually implements that table using Flexbox inside an ordered list, but that’d be a whole lot more work for me, less semantic, less accessible, and would not eliminate the problem posed by “rule 4”. I would still have a set of HTML elements and be wanting D3 to draw one circle within the content area of each HTML element; they would just be <div>s instead of <td>s.

Arrange the nodes horizontally and draw aesthetically pleasing lines between them. Take a look at the more complicated examples on the “mermaid.js gitgraph diagram” page to get an idea.

Yes, ideally. The contents of the page will be fixed — no dynamic addition or removal of nodes or changes in row height after the page is loaded — but the rows might or might not all have the same height.

4

Tabular data does not mean that you need to render it as an actual HTML table, especially if you want to include a graph that spans multiple rows.

I’d appreciate if you’d take a moment to consider that an answer might not be as obvious as you think before replying. If the context or intent of the question is not clear to you, try to ask for clarification.

5

I regret my use of ‘??’, but I did go on to explain why i thought an HTML table was the most logical choice for the data. If you think there is a different HTML structure that I could use that would make the overall implementation substantially easier, please say what you are thinking of instead of just insisting that I haven’t considered all the possibilities.