Open grtlr opened 2 months ago
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 GraphNodeId
s 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:
GraphNodeId
with the entity graph.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:
dot
) and undirected approaches
neato
and fdp
) support initial positions, so we could reuse parts of the layout if there are not to many changes. The comopShould 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
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
andGraphEdgeId
wrapper types around the existingText
(of course we can also name themNodeId
andEdgeId
, but it’s probably good to be explicit here). Another option would beu16
, similar to howClassId
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 associatedGraphNodeId
.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
andat_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.
@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.
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: https://github.com/rerun-io/rerun/issues/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
andGraphEdgeId
wrapper types around the existingText
(of course we can also name themNodeId
andEdgeId
, but it’s probably good to be explicit here). Another option would beu16
, similar to howClassId
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:
GraphNodeId
(a simple wrapper around the datatype defined above, similar toClassId
).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.
GraphNodes
(required:GraphNodeId
, optional:Text
,Position2D
(for existing layouts),Color
, maybe we can add styling information here in the future.)GraphUndirectedEdges
(required:GraphEdge
, optional:Text
,Color
)GraphDirectedEdges
(same asGraphUndirectedEdges
+ maybeArrowShape
in the future).A hypothetical logging call to the Rerun SKD from Rust could look like the following:
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 associatedGraphNodeId
.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
andat_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
Out of Scope
The following points would be very interesting to develop further but are out of the scope for the initial implementation: