Adding graph primitives to the data model

[grtlr]

It would be awesome to extend Rerun’s data model to include graphs (node-link relationships), because it would allow more advanced use cases such as visualizing ROS computational graphs over time in the future:  #6898.

The following should be seen as an initial point for discussion and request for comments. Also, please note that in the following I will sometimes refer to the Rust documentation for simplicity—of course the actual implementation should use Flatbuffer definition files and be available in all environments.

Also, I'm still quite new to the Rerun code base, so non of the following should be taken as authoritative.

Proposal

For now, this proposal focuses on simplicity and tries to reuse existing types as much as possible, therefore reducing the amount of code that needs to be maintained in the future. We also want to avoid creating leaky abstractions that accidentally expose implementation details as part of the SDK.

For the first prototype, I think it makes sense to see how far we can get with a custom visualizer as shown in the Custom Space View example. If we hit any limitations, we can use those to inform changes to the Rerun core.

Datatypes

We should be able to reuse existing data types for node and edge IDs. If we want to be more explicit, we could introduce GraphNodeId and GraphEdgeId wrapper types around the existing Text (of course we can also name them NodeId and EdgeId, but it’s probably good to be explicit here). Another option would be u16, similar to how ClassId works.

Also, for now we can probably skip the GraphEdgeId data type unless we need a way to reference edges from other parts of the implementation.

There is a tradeoff here: Ideally, the node and edge ID types should be generic to accept either integers or strings. The latter is more expressive and often better reflects the data of the user, where the former is more compact in memory and improves the efficiency of many algorithms.

Components

We introduce two new components:

1. GraphNodeId (a simple wrapper around the datatype defined above, similar to ClassId).
2. GraphEdge(GraphNodeId, GraphNodeId), a simple tuple that defines an edge. This type could mean either a directed or an undirected edge, depending on the context that it is used in.

Archetypes

We use different archetypes to define the type of graph (as this will trigger opening a graph-specific visualizer). Additionally, these can add additional information to the graph, such as text or color.

1. GraphNodes (required: GraphNodeId, optional: Text, Position2D (for existing layouts), Color, maybe we can add styling information here in the future.)
2. GraphUndirectedEdges (required: GraphEdge, optional: Text, Color)
3. GraphDirectedEdges (same as GraphUndirectedEdges + maybe ArrowShape in the future).

A hypothetical logging call to the Rerun SKD from Rust could look like the following:

rec.log(
    "ros/topics",
    &rerun::GraphNodes::new(["a", "b", "c"])
        .with_labels(["Node A", "Node B", "Node C"),
)?;
rec.log(
    "ros/topics",
    &rerun::GraphDirectedEdges::new([
      ("a", "b"), 
      ("b", "c"),
      ("a", "c")
    ]),
)?;

Views

Based on this data model, we can now create a GraphDiagramView that layouts and renders the resulting graph. Layout algorithms can be quite costly, especially for larger graphs. Therefore we should use heuristics to define when a layout needs to be recomputed. By default, we can probably add a graph viewer to Rerun if any entity has an associated GraphNodeId.

As graph layouts can “flip” easily (most algorithms don’t guarantee spatialtemporal coherence), we should also avoid re-computing layouts because this can be detrimental to user experience. This also ties in with the following: the archetypes defined above should work with static and at_the_latest semantics. If the viewer has access to these contexts, we could use them to inform (or pick) the layout algorithms. These could also have an influence on the caching strategy.

Open Questions

• Can we use entity paths to define hierarchical graphs? What happens if we have edges that cross the boundaries of sub-entities? Would this be ergonomic from a user perspective?
• How should we handle more complex information within the graph labels. For now having text might suffice, but there are many use cases that benefit from visualizing additional information.

Out of Scope

The following points would be very interesting to develop further but are out of the scope for the initial implementation:

• Providing a ROS bridge. While this is a very convenient feature, for now the user is expected to manually log the graph using the Rerun SDK.

[grtlr]

For documentation purposes, here are some additional details that are relevant for the implementation:

How to use entities to handle hierarchical graphs?

The GraphNodes and GraphDirectedEdges archetypes can be attached to any entity. If possible, when rendering an entity we collect the nodes from all children entities. For GraphNodeIds in edges that are not part of the current entity, we can create dummy nodes for now. We can refine this logic once we have a basic working version and I understand Rerun’s rendering logic better.

---

Related, I may have been wring to discard the notion of entities as nodes. It’s likely needed anyway for hierarchy and is useful when people want to map their entity hierarchy to a graph. Is there some design there that works for both?

This probably makes sense in the context of ROS, where a node maps to an entity. I think there are two approaches:

• We replace the GraphNodeId with the entity graph.
• We enforce that there is only a single GraphNodeId per entity.

I think this should work—although I’m not sure how nice this will be to log for the user, as they would have to create a lot of entities.

---

How should graph layout handle incremental updates? Everything jumping around or some incremental approach?

We have several options here, a lot of it depends on the layout engine that we choose:

• Force-based layouts can incrementally be updated and might be well suited for dynamic environments. Neglects edge direction (mostly for undirected graphs). Example: https://observablehq.com/@d3/force-directed-graph-component; you can try to drag some nodes.
  • Pros: fully dynamic, pretty easy to implement (there is also https://github.com/grantshandy/fdg); works good enough in most cases
  • Cons: layout might be suboptimal and is strongly dependent on setting force-parameters. layouts are not “deterministic”, can feel “hacky” for some use-cases such as directed edges and hierarchical data.
• Stress-based layouts
  • Pros: better layouts than force-based approaches through MDS initialization and better formulation
  • Cons: Tricky to implement efficiently; numeric methods; harder to make dynamic, no Rust crates.
• Constraint-based layouts (https://ialab.it.monash.edu/webcola/)
  • Pros: nicer layouts can still be dynamic
  • Cons: Algorithms are tricky to implement, probably no Rust crates.
• GraphViz layout: works for directed (dot) and undirected approaches
  • Pros: Produces nice layouts, allows hierarchical layouts, some GraphViz algorithms (neato and fdp) support initial positions, so we could reuse parts of the layout if there are not to many changes. The comop
  • Cons: can be expensive to compute for large graphs. Not sure if https://github.com/nadavrot/layout also supports undirected graphs.

---

Should users be able to control constraints for the graph layout? If so, how does that interact with the blueprint system.

Ideally, we make the parameters required for the graph layout available in the blueprint configuration. This is particularly important for force-based layouts because they depend a lot on the parameters of the physics simulation.

Another option that has come up is adding an additional GraphLayoutParameter component to the data model. While this will work as well, we should be weary adding implementation details to the model, as those might change over time and the data model should be as stable as possible to allow backwards compatibility.

---

Using egui for shape rendering?

We could look into the following crate which adds graph layout components directly to egui: https://github.com/blitzarx1/egui_graphs

[vmayoral]

Thanks @grtlr and @nikolausWest for driving this forward. Here's feedback from my side at this stage:

Datatypes

We should be able to reuse existing data types for node and edge IDs. If we want to be more explicit, we could introduce GraphNodeId and GraphEdgeId wrapper types around the existing Text (of course we can also name them NodeId and EdgeId, but it’s probably good to be explicit here). Another option would be u16, similar to how ClassId works.

Also, for now we can probably skip the GraphEdgeId data type unless we need a way to reference edges from other parts of the implementation.

There is a tradeoff here: Ideally, the node and edge ID types should be generic to accept either integers or strings. The latter is more expressive and often better reflects the data of the user, where the former is more compact in memory and improves the efficiency of many algorithms.

I like the idea of GraphNodeId and GraphEdgeId. I'd stick with strings.

Components

We introduce two new components:

1. `GraphNodeId` (a simple wrapper around the datatype defined above, similar to [`ClassId`](https://docs.rs/rerun/latest/rerun/components/struct.ClassId.html)).

2. `GraphEdge(GraphNodeId, GraphNodeId)`, a simple tuple that defines an edge. This type could mean either a directed or an undirected edge, depending on the context that it is used in.

Sounds good.

Archetypes

We use different archetypes to define the type of graph (as this will trigger opening a graph-specific visualizer). Additionally, these can add additional information to the graph, such as text or color.

1. `GraphNodes` (required: `GraphNodeId`, optional: `Text`, `Position2D` (for existing layouts), `Color`, maybe we can add styling information here in the future.)

2. `GraphUndirectedEdges` (required: `GraphEdge`, optional: `Text`, `Color`)

3. `GraphDirectedEdges` (same as `GraphUndirectedEdges` + maybe `ArrowShape` in the future).

A hypothetical logging call to the Rerun SKD from Rust could look like the following:

rec.log(
    "ros/topics",
    &rerun::GraphNodes::new(["a", "b", "c"])
        .with_labels(["Node A", "Node B", "Node C"),
)?;
rec.log(
    "ros/topics",
    &rerun::GraphDirectedEdges::new([
      ("a", "b"), 
      ("b", "c"),
      ("a", "c")
    ]),
)?;

Views

Based on this data model, we can now create a GraphDiagramView that layouts and renders the resulting graph. Layout algorithms can be quite costly, especially for larger graphs. Therefore we should use heuristics to define when a layout needs to be recomputed. By default, we can probably add a graph viewer to Rerun if any entity has an associated GraphNodeId.

As graph layouts can “flip” easily (most algorithms don’t guarantee spatialtemporal coherence), we should also avoid re-computing layouts because this can be detrimental to user experience. This also ties in with the following: the archetypes defined above should work with static and at_the_latest semantics. If the viewer has access to these contexts, we could use them to inform (or pick) the layout algorithms. These could also have an influence on the caching strategy.

No comment. Seems fine and usable.

* How should we handle more complex information within the graph labels. For now having text might suffice, but there are many use cases that benefit from visualizing additional information.

Right, an you definitely want to consider that. Information may not necessarily need to go into the labels though, and could go into the selection panel.

To simplify your design approach, I believe you can assume that anything beyond the label representing connections across nodes shall go into the selection panel.

Out of Scope

The following points would be very interesting to develop further but are out of the scope for the initial implementation:

* Providing a ROS bridge. While this is a very convenient feature, for now the user is expected to manually log the graph using the Rerun SDK.

That's fine however I'd encourage providing enough documentation and an example to empower this. Otherwise, capabilities will be of very little use, even if available. Something as simple as a pub-sub logger and graph visualizer should do for starters, but that example should be available in some form, demonstrating how to turn ROS 2 core graph abstractions into rerun ones.

Another potentially useful example would be to turn existing graphs built with popular libraries into rerun. E.g. networkx is widely used and AFAIK, not completely disconnected from your discourse above. See rustworkx (paper), which seems to be growing in popularity.

Ping me whenever there's something to test. Happy to give it a try.

[grtlr]

@vmayoral Thank you for your feedback—it looks like we are on the right track 🤓. I agree with your points regarding documentation of the new feature. I think the goal should still be to add this to the ROS bridge in the mid-term, but first we need to get the data model right.

I'm currently implementing the graph primitives in the following PR #7500 if you want to follow along or provide feedback 🙏. Once we have finalized the design I want to start implementing the layout functionality.