Research: build d3 graph using actual data model with multi-parent project structure

[alansemenov]

Post screenshots in comments to this task

[reisfmb]

@alansemenov @sigdestad

Understanding the underlying data structure

The first thing I did was to understand what is the actual underlying data structure.

I figured out that it is not a DAG (directly acyclic graph) which I initially thought it was, it is actually a collections of trees, or indeed a tree if we consider that the root node is "projects".

A graph can be defined as a tree in the following way:

1. Root Node
2. Directed
3. No cycles
4. Connected
5. Each node must have one parent

Here's why our data structure relates to a tree... consider the graph of a single project:

1. Root node exists, in fact it is the project itself;
2. Directed, since each layer has a parent;
3. Acyclic, since we always select a previous created layers or the root project when adding new layers;
4. Connected, since it is mandatory to assign a parent to a new layer;
5. Only one parent, since we always add layers referencing it to a single unique parent.

All of that reasoning implies that we're actually dealing with a collection of trees, where each tree root is one existing project.

As mentioned before, this can be converted to a tree if we now take the roots of each tree (projects) and consider them the 1st depth nodes of our tree, with "projects" as root. Conclusion, we are dealing with a tree structure.

Visualizing trees

Now it is a matter of defining how we want to visualize this tree!

Here are some links / screenshots that uses D3 to visualize trees... none of them looked exactly what I have in mind, but since D3 is a very flexible library, my suggestion is to pick one as a starting point and then we continue implementing our tweaks to get to the desired result!

Custom Tree of G6

Radial Tree

Collapsible Tree

Collapsible Vertical Tree

Interactive Tree Diagram (D3v3)

Navigable Nested Tree

Finally, here is the link for further exploration of d3 visualization examples that mention "tree".

[sigdestad]

Great research Bruno, but seems you have not received a dataset with all relevant information. As I mentioned in the meeting, it is a DAG. There may be multiple parent nodes for each node. As such, there may also be multiple "root" items, and even dangling nodes (projects that don't have any children) This is why it is a graph, not a tree. See attached sample visualization

[sigdestad]

Actually, I forgot one more important fact - if there are multiple parent items, they need to be "weighted" as in show the priority somehow.

New example attached:

[sigdestad]

So, mathematically, I guess there are actually multiple graphs, as each node(set) not connected to others are separate graphs. but they should all be visualized in the same structure.

There will never be cycles in these graphs.

[reisfmb]

@sigdestad

The current data structure I analysed is actually a tree, since layers can only have one parent. But the point of all this is that this is changing... layers will be able to have multiple parents, and therefore, the data structure will change from tree to dag.

Now your images makes sense Thomas, because we'll be allowing multiple parents to layers. Nice!

So I'll look for ways to visualize DAGs with D3 and will post the results of my research here so we can continue discussing them.

[reisfmb]

@alansemenov @sigdestad

I think I found what we need: https://erikbrinkman.github.io/d3-dag/index.html

This is an open source typescript library for rendering directed acyclic graphs using a few different layout methods centered around layered dag methodology from Sugiyama.

In the following links it is possible to select different data / layout configurations and see the generated visualization:

• https://beta.observablehq.com/@erikbrinkman/d3-dag-sugiyama
• https://beta.observablehq.com/@erikbrinkman/d3-dag-topological

Important to note that d3-dag library is a helper... d3 library is also used to properly generate the svg. The final result is a combination of both.

From my investigations so far d3-dag basically gets the raw data and provides methods to generate a new data structure that will have the right position of nodes (+ some other fancy stuff). From there, the svg generation is done using d3.

I spent some time and without much efforts was able to generate this very simple visualization for this data structure:

[
      {
        id: 'project-a',
        parentIds: []
      },
      {
        id: 'layer-a',
        parentIds: ['project-a']
      },
      {
        id: 'project-b',
        parentIds: []
      },
      {
        id: 'layer-b',
        parentIds: ['project-b']
      },
      {
        id: 'layer-c',
        parentIds: ['project-a', 'project-b']
      },
      {
        id: 'layer-d',
        parentIds: ['project-a', 'layer-c']
      },
      {
        id: 'layer-e',
        parentIds: ['project-b', 'layer-d']
      },
      {
        id: 'layer-f',
        parentIds: ['project-a', 'layer-e']
      },
    ]

And here's another visualization using the data @vbradnitski sent:

[sigdestad]

Looks very nice, what about the weighting?

[alansemenov]

Looks good. Strange that the "main" d3 library doesn't have anything suitable? It's important that the lib we use is a) available on NPM, b) being maintained, c) using a proper license.

[reisfmb]

@sigdestad

Done by code:

[reisfmb]

@alansemenov

D3 provides a lot of helpers for creating visualizations, but couldn't find anything that would directly help with DAG data structure. Also, d3-dag seems to be the "go to" library when rendering DAG with d3, since a lot of examples that tries to visualize DAG in observablehq uses it

a) https://www.npmjs.com/package/d3-dag

b) https://github.com/erikbrinkman/d3-dag/commits/main https://github.com/erikbrinkman/d3-dag/tags

c) https://github.com/erikbrinkman/d3-dag/blob/main/LICENSE

[alansemenov]

Good to go!

[sigdestad]

Looks like we are good to go then. Will ofc need some styling improvements. Each node must be identifiable as a project ofc

[reisfmb]

@sigdestad @alansemenov

Initial design suggestion. Feedbacks?

[sigdestad]

Awesome. We also need the language in () after the displayname. If possible, use a different color on the language