MVP for the graph view (node-link diagrams) #7897
Labels
feat-graph-view
Everything related to the graph view
🎄 tracking issue
issue that tracks a bunch of subissues
Milestone
Comments
grtlr
added
other
abey79
added
🎄 tracking issue
10 tasks
abey79
changed the title
grtlr
added a commit
that referenced
this issue
Nov 25, 2024
<!-- Open the PR up as a draft until you feel it is ready for a proper review. Do not make PR:s from your own `main` branch, as that makes it difficult for reviewers to add their own fixes. Add any improvements to the branch as new commits to make it easier for reviewers to follow the progress. All commits will be squashed to a single commit once the PR is merged into `main`. Make sure you mention any issues that this PR closes in the description, as well as any other related issues. To get an auto-generated PR description you can put "copilot:summary" or "copilot:walkthrough" anywhere. --> Tracking issue: #7897 This implements basic graph primitives in the Rerun data model. This is a first step towards visualizing node-link diagrams in Rerun (related issue: #6898). In addition to the changes to the data model, this PR adds two example crates, `node_link_graph` and `graph_view` to the Rust examples that show how these primitives can be used. ## Design Decisions - Nodes and edges are stored as `components` and can be batched. To have a single node per entity we can use Rerun’s [[clamping mechanism](https://rerun.io/docs/concepts/batches#component-clamping)](https://rerun.io/docs/concepts/batches#component-clamping). - `GraphNodeId` is modeled as ~`u32` to improve performance when using `petgraph`~ strings for better user experience. - A node is unique identified by combining its `GraphNodeId` and its `EntityPath`. - Labels of the nodes can be set via the `labels` component and toggled via `show_labels` - ~Hierarchical graphs can be modeled through entity paths. For edges that cross entity boundaries we can insert dummy nodes to properly render subparts of the hierarchy.~ - ~Nodes and edges need to be logged to the same entity, otherwise the selections will collide. We provider helper functions / conversions to link nodes that are stored in different entities.~ > [!WARNING] > This PR has changed considerably from its initial version: > * No linking of nodes between entities (an therefore hierarchy) yet. > * For now, Graphs are local only and therefore have to be logged to the same entity. ## Logging example ```rs rec.log( "simple", &rerun::GraphNodes::new(["a", "b", "c"]) .with_positions([(0.0, 100.0), (-100.0, 0.0), (100.0, 0.0)]) .with_labels(["A", "B", "C"]), )?; // Note: We log to the same entity here. rec.log( "simple", &rerun::GraphEdges::new([("a", "b"), ("b", "c"), ("c", "a")]).with_directed_edges(), )?; ``` ## TODOs - [x] ~Get rid of the `Default` derive for `GraphNodeId` and `GraphEdge` in the flatbuffer definitions.~ - [x] Improve ergonomics for generating graph edges during logging. - [x] Ensure that logging works from Python and C++ too. - [x] Fix remaining lints. ### Checklist * [x] I have read and agree to [Contributor Guide](https://github.com/rerun-io/rerun/blob/main/CONTRIBUTING.md) and the [Code of Conduct](https://github.com/rerun-io/rerun/blob/main/CODE_OF_CONDUCT.md) * [x] I've included a screenshot or gif (if applicable) * [x] I have tested the web demo (if applicable): * Using examples from latest `main` build: [rerun.io/viewer](https://rerun.io/viewer/pr/7500?manifest_url=https://app.rerun.io/version/main/examples_manifest.json) * Using full set of examples from `nightly` build: [rerun.io/viewer](https://rerun.io/viewer/pr/7500?manifest_url=https://app.rerun.io/version/nightly/examples_manifest.json) * [x] The PR title and labels are set such as to maximize their usefulness for the next release's CHANGELOG * [x] If applicable, add a new check to the [release checklist](https://github.com/rerun-io/rerun/blob/main/tests/python/release_checklist)! * [x] If have noted any breaking changes to the log API in `CHANGELOG.md` and the migration guide - [PR Build Summary](https://build.rerun.io/pr/7500) - [Recent benchmark results](https://build.rerun.io/graphs/crates.html) - [Wasm size tracking](https://build.rerun.io/graphs/sizes.html) To run all checks from `main`, comment on the PR with `@rerun-bot full-check`. --------- Co-authored-by: Antoine Beyeler <antoine@rerun.io> Co-authored-by: Andreas Reich <r_andreas2@web.de>
emilk
pushed a commit
that referenced
this issue
Nov 25, 2024
<!-- Open the PR up as a draft until you feel it is ready for a proper review. Do not make PR:s from your own `main` branch, as that makes it difficult for reviewers to add their own fixes. Add any improvements to the branch as new commits to make it easier for reviewers to follow the progress. All commits will be squashed to a single commit once the PR is merged into `main`. Make sure you mention any issues that this PR closes in the description, as well as any other related issues. To get an auto-generated PR description you can put "copilot:summary" or "copilot:walkthrough" anywhere. --> Tracking issue: #7897 This implements basic graph primitives in the Rerun data model. This is a first step towards visualizing node-link diagrams in Rerun (related issue: #6898). In addition to the changes to the data model, this PR adds two example crates, `node_link_graph` and `graph_view` to the Rust examples that show how these primitives can be used. ## Design Decisions - Nodes and edges are stored as `components` and can be batched. To have a single node per entity we can use Rerun’s [[clamping mechanism](https://rerun.io/docs/concepts/batches#component-clamping)](https://rerun.io/docs/concepts/batches#component-clamping). - `GraphNodeId` is modeled as ~`u32` to improve performance when using `petgraph`~ strings for better user experience. - A node is unique identified by combining its `GraphNodeId` and its `EntityPath`. - Labels of the nodes can be set via the `labels` component and toggled via `show_labels` - ~Hierarchical graphs can be modeled through entity paths. For edges that cross entity boundaries we can insert dummy nodes to properly render subparts of the hierarchy.~ - ~Nodes and edges need to be logged to the same entity, otherwise the selections will collide. We provider helper functions / conversions to link nodes that are stored in different entities.~ > [!WARNING] > This PR has changed considerably from its initial version: > * No linking of nodes between entities (an therefore hierarchy) yet. > * For now, Graphs are local only and therefore have to be logged to the same entity. ## Logging example ```rs rec.log( "simple", &rerun::GraphNodes::new(["a", "b", "c"]) .with_positions([(0.0, 100.0), (-100.0, 0.0), (100.0, 0.0)]) .with_labels(["A", "B", "C"]), )?; // Note: We log to the same entity here. rec.log( "simple", &rerun::GraphEdges::new([("a", "b"), ("b", "c"), ("c", "a")]).with_directed_edges(), )?; ``` ## TODOs - [x] ~Get rid of the `Default` derive for `GraphNodeId` and `GraphEdge` in the flatbuffer definitions.~ - [x] Improve ergonomics for generating graph edges during logging. - [x] Ensure that logging works from Python and C++ too. - [x] Fix remaining lints. ### Checklist * [x] I have read and agree to [Contributor Guide](https://github.com/rerun-io/rerun/blob/main/CONTRIBUTING.md) and the [Code of Conduct](https://github.com/rerun-io/rerun/blob/main/CODE_OF_CONDUCT.md) * [x] I've included a screenshot or gif (if applicable) * [x] I have tested the web demo (if applicable): * Using examples from latest `main` build: [rerun.io/viewer](https://rerun.io/viewer/pr/7500?manifest_url=https://app.rerun.io/version/main/examples_manifest.json) * Using full set of examples from `nightly` build: [rerun.io/viewer](https://rerun.io/viewer/pr/7500?manifest_url=https://app.rerun.io/version/nightly/examples_manifest.json) * [x] The PR title and labels are set such as to maximize their usefulness for the next release's CHANGELOG * [x] If applicable, add a new check to the [release checklist](https://github.com/rerun-io/rerun/blob/main/tests/python/release_checklist)! * [x] If have noted any breaking changes to the log API in `CHANGELOG.md` and the migration guide - [PR Build Summary](https://build.rerun.io/pr/7500) - [Recent benchmark results](https://build.rerun.io/graphs/crates.html) - [Wasm size tracking](https://build.rerun.io/graphs/sizes.html) To run all checks from `main`, comment on the PR with `@rerun-bot full-check`. --------- Co-authored-by: Antoine Beyeler <antoine@rerun.io> Co-authored-by: Andreas Reich <r_andreas2@web.de>
grtlr
added a commit
that referenced
this issue
Nov 29, 2024
### Related * This is one of the big action items of #7897 <!-- Include links to any related issues/PRs in a bulleted list, for example: * Closes #1234 * Part of #1337 --> ### What <!-- Make sure the PR title and labels are set to maximize their usefulness for the CHANGELOG, and our `git log`. If you have noticed any breaking changes, include them in the migration guide. We track various metrics at <https://build.rerun.io>. For maintainers: * To run all checks from `main`, comment on the PR with `@rerun-bot full-check`. * To deploy documentation changes immediately after merging this PR, add the `deploy docs` label. --> It changes two things: 1. Instead of using multiple `egui::Areas`, we now only have a single top-level area. 2. We compute the sizes of the nodes (information that is important to the layout) in a single preprocessing path instead of the weird frame-to-frame computation that we did before. Overall this will improve code quality, performance, and will unlock new GraphViz-like layout algorithms (which require defined label size from the beginning) down the road. --------- Co-authored-by: Antoine Beyeler <antoine@rerun.io>
|
Closing this as MVP is complete. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This will touch various areas of Rerun so we will split the work up over multiple PRs. This PR is a living document and will be updated to reflect the current status of the implementation.
MVP for 0.21
Initial PR: #7500
gen_common_index.pyunusedlint warnings for things that we need in the futureGraphTypedatatype::StringPairand switchGraphNodetoUtf8Utf8PairVisualBoundsin Viewer PropertiesArea(or no area at all?) (Simplify graph viewer rendering logic #8227)GraphEdges,GraphNodes, andGraphViewarchetypes #8277VisualBounds2Dto blueprint on any hover #8327Enabledcomponent tooltip #8456check_graph_time_varying.pyto exampleNice to have but can live without
Position2Dto reflect the actual fallback value (which comes the layout engine) #8280EdgeTextcomponent to add labels to edges until tagged components arrive (note: this may be a rabbit hole in terms of layout)Future work
These item are not required for the 0.21 release
Data Model
<entity_path>#<node_id>convention. (Allow linking ofGraphNodesacross different entities #8162)chunk_id_removed.is_some()#7992).Graph Layout & Viewer
We decided to start with implementing force-based layouts, because they support a wide variety of use cases and allow dynamic/temporal graphs out of the box.
positions: Position2Dcomponent (closed by Implement graph components and archetypes #7500)fdg,layout-rs,graphviz-rust). All of them have some shortcoming for our use cases.d3-force. (⌛ Ongoing)d3-quadtreeto enable Barnes-Hut approximation 🏎️PositionXandPositionYforceCollideforceManyBodyforceExamples & SDK
ProjectDirsto pull in datasets for examples (socialgraph; Observable)The text was updated successfully, but these errors were encountered: