GSoC 2024: Interactive Node Graph Auto-Layout

[adamgerhant]

About:

This is a weekly log of my progress during my GSoC 2024 summer project. In April I submitted a proposal for how I create a Node Graph auto layout system, and since then I have been working to implement it. Although the timeline and goals have shifted quite a bit, I have been able to contribute many features, bug fixes, and improve the codebase through various refactors.

Synopsis

Develop a system to arrange nodes for a tree-like node network based on available area, branch topology, and positioning constraints. Since the Graphite node system has a general structure with layers in columns and nodes in rows, constraints can be applied to create a layout system that effectively arranges the network

Benefits

Automatically keeps the node graph organized and easy to understand
Ensure the user is following the general layout design principles

Deliverables

• Develop a node graph layout system which helps organize a node network. For example, the graph in the picture on the next page should be automatically generated when the corresponding tools are used.
• Algorithms to quantify graph structure rearrangement cost and layout improvement
• Heuristic based reorganization algorithm to generate a list of possible rearrangements
• Decision making algorithm to choose the best reorganization based on rearrangement cost and layout improvement
• Be able to collapse branches. When reopened the graph should be the same as when it was closed.
• Horizontal frosted glass containers to hold nodes in a row and vertical stacks to keep layers in a column

Final Report

• 18 merged PRs
• 19 closed issues
• 25,916 added lines, 17,102 removed lines

Overall, my project has been successful in its primary goal: Improving the node graph layout system. This is accomplished through improved node organization, performance, and codebase improvements. Node organization has been improved through algorithms for automatically organizing nodes when moving and creating layers in the layer panel, horizontal glass containers, vertical layer locking, and preventing overlap by pushing nodes during a collision. Performance has improved by moving the node graph logic, state, and click detection into Rust, and implementing a robust caching system. The network interface API I developed improves the codebase as a whole to prevent bugs, consolidate functionality, and enforce side effects.

The next steps for this project will be to continue developing more refined heuristic and explicit algorithms to automatically reorganize nodes. It will also now be much easier to render the node Graph through the Vello renderer rather than Svelte. I am exited to start working on these features and continue contributing to the project. It has been extremely rewarding to solve complex problems, work with the other contributor, and work on a project that has such ambitious goals.

Generalize layers as merge nodes #1712

My first contribution was to generalize the concept of layers to apply to any node. Previously, only merge nodes were layers, and could not be displayed as a node. This PR added a field to every node for whether it should be displayed as a layer. This was more challenging than expected since it required generalizing the tooling to work with both layer and non layer nodes, as well as a different graph topology.

Before	After

Node network subgraph editing #1750

This functionally was crucial to working towards a core concept of Graphite: the recursive node network. Each node is essentially a function, and if the internals of functions cannot be edited it is like trying to write a program all in a single function. Allowing the editor to modify the internals required making changes across the entire code base. Most changes were focused on generalizing the editor to handle all the new operations that are possible in a nested network. Another important feature of this PR is displaying the wire color based on the data type from the compiled network.

Migrating Node Graph logic from Svelte to Rust #1768

Since the Node Graph is rendered by Svelte, this was also a convenient place to store the logic for interacting with the Graph. JavaScript event listeners could be added to each node and port, and then they would send a message to Rust in order to keep the backend in sync. However, this means that all state was also stored in Svelte, which greatly limited the functionality. For example, the scroll bars or navigation tools would not work, since the backend had no information of where the nodes or wires were. This PR solved this by transferring all the state and logic to the Rust backend, and simply passing through click events to the backend. This allowed much more functionality to be added to the Graph, including scroll bars, rulers, zoom to fit, auto panning, and more. This also required developing a caching system to store the click targets, and then recreate the various DOM click handlers to get positions and click detection. The next step will be to completely remove Svelte, and replace with a native Vello renderer. This will greatly improve performance, as it takes over 100ms in large documents to collect, send, and render all the nodes/wires.

The Network Interface #1794

This was by far the largest PR throughout my GSoC project, taking over 6 weeks and over 10k changed lines of code. After spending time with the codebase, I realized that ensuring consistent side effects has been a big issue, and would only become worse as more functionality and caching was added. This PR completely reworked the entire editor to use an API to modify the network, where each mutable method would perform the correct side effects. This is enforced by storing the fields as private, and never allowing methods to return mutable references. In addition, the data structure was completely reworked in order to separate the editor information for metadata such as position from the rendering information such as how nodes are connected to each other. This allowed for a caching system in the editor which greatly improves performance, and would only be possible with an API to ensure consistent cache invalidation. This new data structure also enables the chain and stack organization to store as little state as possible which helps prevent invalid state.

Layer Panel layout improvements #1911

After creating the network interface API, I continued work on improving the automatic layout system, specifically when moving layers. Every time a layer is moved in the layer panel, it needs to prevent overlap and reorganize the graph if necessary. The API makes it much easier to implement these algorithms, since it provides a very helpful level of abstraction. Instead of worrying about implementation details, I can focus on creating a universal set of actions that a user would perform when creating or moving a layer, and then use the API to easily perform these actions. For example, when moving a layer it should disconnect that layer from the stack, shift the stack up to collapse the space, create space for the new layer by measuring/shifting nodes, and then then insert the layer in the new position. There are so many possible cases to consider, so being able to just focus on what the user would want to happen rather than how to do it is invaluable. In video I randomly move layers in a somewhat complex network, and the positioning system ensured minimal overlap, collapses unused space, and tries to keeps upstream nodes aligned.

chrome_ZukJ5MvNG7.mp4

Shifting layers as blocks #1940

With the new stack organization, it can be difficult to move layers around when they are in a stack. In order to make this easier, we developed a new method for shifting layers in a stack that would push layers that stack collides with during a shift. It was difficult to even think of how this should work, but eventually we worked out a system where chains that belonged to a layer were locked to that layer, while chains that belonged to more than one layer acted as blocks. Each block also has a rubber banding effect, so that during a layer shift, all layers that it collides with will try return back to their original position. This is an incredibly helpful feature, and it makes moving layers around feel very intuitive and natural.

chrome_4MxFS0PoC6.mp4

[adamgerhant]

Week 1 Report

My first week of the official coding period was spent finishing up a large PR I had started during the community bonding period. This PR added a node subgraph editor, allowing the user to double click on a node and view its internal network, if it has one. The most difficult aspect of this PR was making changes that generalized the graph editor to display and modify any network. One such change was generalizing how nested nodes interacted with their parent, which required a rework to the compilation process and network data structure. Another major change was displaying input types based on the compiled network, rather than hard coded values. Due to the large amount of internal, this week I focused solving bugs and fixing errors. The most notable changes from this week include:

• A revamped previewing system and logic for handling graph modifications while previewing. This was especially tricky due to a large amount of edge cases. It ended up requiring dozens of if-else statements to ensure the correct behavior.
• Modifying get_input_type to find a default Type from either the compiled network or node registry
• Improving the Graph UI to display input names based on their type and displaying errors for the correct node
• Adding backwards compatibility through custom deserialization in order to open demo artwork.
• Dozens of other bug fixes and functionality improvements

What I've learned so far

• Git graph is incredibly helpful. Having a visual understand how Git works and what the various commands actually do is necessary in order to correctly synchronize local and remote changes.
• Spend time trying to resolve a question, rather than immediately asking it. I see complex questions as a report of what is not working, all the debugging I have done, and where the issue is coming from. Using this method has greatly helped my debugging and individual understanding of the codebase, even if it means writing far more than I will ever ask. In fact, on several occasions reached the discord text limit when describing a problem, only to eventually answer my own question and delete all the text.
• Be persistent, and don't be afraid to start over. It can suck spending hours making hundreds of changes, only to realize that your entire approach was incorrect. In these cases there it is best just to git reset --hard, and start over with all the new insight you learned during the failed approach.

[adamgerhant]

Week 2 Report

My second week was focused on migrating state and functionality for the node graph from Svelte into Rust. Currently, the JavaScript in Svelte handles a ton of logic, including click events, click detection, positioning, dragged wires, and more. After this logic, a request to Rust would be sent through a wasm-bindgen entry point. For example, clicking a node would send editor.handle.selectNodes to update the selection state stored in Rust. The goal of my PR is to pass click events through to Rust, where all the logic and state can be stored and updated, then sent back to the node graph through FrontendMessage

For example, the positioning of the graph is currently stored in Svelte, and panning only updates the state on the frontend. Now, the position is stored in Rust, and mouse events get passed to the NavigationMessageHandler, which updates the transform and sends it back to the Frontend where the node graph can be re-rendered with the new transform. Because the NavigationMessageHandler now has access to the position information, other helpful widgets can also use the state. For example, the scroll bars and zoom controls are fully functional.

Another fundamental change was implementing click detection. Previously this was done through the DOM, and click events would use .closest() to check if a node or input was clicked. Now, click targets need to be stored in Rust and kept in sync with the frontend. This will eventually allow the node graph to be rendered through the Graphene renderer, essentially as a procedurally generated artwork based on the node network state.

What I've learned

Don't optimize prematurely. While developing I often try to write clean code by segmenting my code into structs and functions. However, I have learned that this is something that should only be done once code works. Especially when implementing something that incorporates a wide variety of changes, its impossible to tell what repeated code can be extracted into a function or struct before actually implementing it. I would often make a function, and then realize it can't be used anywhere because it requires a certain variable, rewrite it, and continue the process.

[adamgerhant]

Week 3 Report

• Completed migration of Graph Editor logic from Svelte to Rust, including features such as auto inserting node by dragging it on a wire, context menus, and layer width calculations
• Added layer with calculation by invisibly rendering the layer div with web-sys and measuring its width. This width is necessary to calculate ClickTargets.
• Reworked the node's ClickTarget to be owned by the NodeGraphMessageHandler, which is part of the user facing editor, instead of the Graphene NodeNetwork, which should always be a standalone system that can run in any environment or UI.
• Improved performance by 50ms a frame (in large documents) by caching the ClickTargets and other computationally expensive operations.
• Implemented an interface for updating the cache based on changes to any DocumentNode that will change the shape/position.
• Various bug fixes and general improvements.

Overall the project has been going great. I've been improving my efficiency day by day, and becoming a better developer in the process. Next week I will work on cleaning up my PR, including various performance improvements, code cleanup, and adding a few more features. I also hope to start implementing organizational tools, such as ensuring layer chains maintain horizontal alignment, and layer stacks maintain vertical alignment.

[adamgerhant]

Week 4 Report

• Cleaned up last PR by improving overall code quality and fixing various bugs
• Improved loading node graph in Red Dress by 200ms by caching layer width calculations, since the web sys call to render and calculate the text width is very slow. Now this is done only when creating the click target, the width is saved, and only updated when the text changes.
• Started working on the node graph auto layout system by creating a comprehensive NodeNetwork modification API. The setter methods will perform the various side effects and calculations in order to keep the various cached data in sync and update node positions.
• This is organized into various structs, which all have private fields. NodeNetworkInterface contains the network and metadata for each network. Each network has a NetworkMetadata, which contains the bounding box and node metadata. NodeMetadata contains the click targets for the node and ports. This hierarchy of data will allow everything to stay organized, performant, and easy to work with.
• Implemented a reworked ClickTarget caching system for all nodes, their inputs, and other data.
• Created a new method for storing position state. Each node can either have Absolute positioning, Chain positioning, or Stack positioning. Once again this will keep the system organized and easy to work with.

What I've learned

While setting up the infrastructure for the rest of my project, I learned a ton about code organization and the best practices for state management. One key concept I always focus on is making invalid state impossible. For example, instead of storing cached layer width as an Option for every node, nodes can either have a LayerMetadata or NodeMetadata, and only LayerMetadata contains the layer width. If a node becomes a layer, or a layer becomes a node, it will be impossible for the layer width to be in an invalid state, since layers must always have a width, and nodes will never have a width.

[adamgerhant]

Week 5 report

This week has been the most challenging week so far. In comparison to my previous work which focused on tangible features and improvements, this week has been far more abstract. I have been working on creating a network interface API, which will encapsulate all mutations to the node network into getter and setter methods. This is necessary in order to ensure the correct side effects are always performed. For example, switching a layer to a node will have to run the auto layout system, update the click target, and reload the document metadata. Additionally, this interface allows an opportunity to fundamentally separate the different "types" of data within Graphite, which can be categorized into 1. network data necessary for rendering the document, 2. persistent node and network metadata for information such as names and locations, and 3. transient node and network metadata which represents cached information such as click targets and bounding boxes. Additionally, this data can now be packaged into structs and enum's which can better represent the state, and prevent invalid state. Creating these structs and enums to work optimally and correctly was very challenging. It was a very repetitive process of trying one method of representing the data, spending a few hours trying to implement it, and then realizing there is a fundamental flaw which means everything needs to be reworked. In total I created 14 new structs and 9 new enums. The next phase of this project will be spent on transferring all existing code to use this API. I would be happy if the refactor compiles will 10k changes lines of code.

What I've Learned

Spending hours working on a change only to realize your change was fundamentally flawed is very demotivating. Especially as this continues to happen, I find myself subconsciously relating working on the project to a lack of progress and difficulty. It's like I was scared to make any changes, since I knew that whatever I did was most likely not going to work and would need to be rewritten. However, its always important to remember that the failures are where you learn most, and sometimes failing can mean more progress than getting a sub optimal system to work.

[adamgerhant]

Week 6 Report

This week was largely spent on continuing the refactor to the NodeNetworkInterface. Some notable progress includes removing all editor metadata from the NodeNetwork and DocumentNode, refactoring all DocumentNodeDefinitions, reworking all node graph operations to use the network interface methods, and merging master. Reworking the node graph operations has been the most difficult part, as it requires reworking the basic editor algorithms for manipulating the node graph. For example, when adding a layer it is first added to the document, then the layer is connected at the correct stack location, then the group is shifted into place, then the layout system is run to create space for these nodes. A similar process is used for deleting nodes and moving nodes. In general I follow a process of identifying the smallest level of functionality so that the network interface functions can be reused in many places, while also minimizing the total number of functions.

Aside from this PR, I also spend a day adding a layer based Boolean operation node and dragging upstream nodes when shift is pressed while dragging. These are relatively small changes which are important for the new editor release coming out soon, so it was definitely worth spending a few hours adding these features.

[adamgerhant]

Week 7 Report

This week I managed to reach a major milestone in the development of the network interface API: getting it to compile. It took a total of 9k additions and 7k removals in order to fix the thousands of errors, ranging from borrow checking, variable types, and refactoring functionality. In order to ensure encapsulating of the network into the interface, the highest level fields which own the network and network metadata are private, so the only way to mutate the network is through the public mutable methods. I started work on a few of these methods, which demonstrate how the interface will prevent bugs and improve code quality. For example, the add_input function will not only add the input, but also ensure that the correct metadata/cached state is correctly updated. For example, adding the input will

1. insert the input to the DocumentNode,
2. inserts the name for that input to the DocumentNodeMetadata,
3. Set the node to a non layer node if it is no longer eligible to be a layer
4. update the transient node metadata node click targets
5. update the transient network metadata bounding box for all nodes
6. update the transient network metadata outward wire connections
7. update the nested transient network metadata (if there is one) imports click target
8. update the nested transient network metadata (if there is one) outward wire connections
9. update the DocumentMetadata layer structure (since adding a primary input could affect layer topology)

All these metadata related changes would be very hard to predict, enforce, and solve bugs without an interface, so having them done every time all in one place is very helpful. Additionally, the interface provides the option to easily add more cached metadata, as well as update the metadata in more efficient ways if performance is a concern. For example, instead of recalculating all outward connections for the entire network, only the outward connections feeding into that node could be updated.

[adamgerhant]

Week 8 Report

This week started by reworking how cached metadata is stored. Instead of storing all metadata in a struct which is wrapped by an Option, each individual field is wrapped by an Option. This allows more granular control over what data is loaded/unloaded, and a more simple interface for reloading various cached fields. Although this seems obvious, it was a bit more complicated due to the fact that some fields need to be packaged together within a single struct to ensure they are all updated at once. For example, the input/output click targets, node click target, and visibility click targets are packaged together, since if a node is moved moves then they all must be recalculated. Since the click targets are now stored separately from the layer width, the slow web sys call to get the layer width does not need to be made every time a click target is recalculated. I also added various computationally expensive operations to the transient metadata, and the new system makes it very easy to add this data and ensure it is always in sync. This greatly improves performance of panning around the node graph, since the bounding box for all nodes can be cached instead of computing it on every frame.

Another major change was completely reworking the selection state. Instead of having a single vec to represent all selected nodes, each network stores its selected nodes independently. This means that nodes can be selected in both a sub network (for example in the node graph window), and the root network (for example through the layers panel). Since nodes can be stored in separate networks, there also needs to be a "primary" selected network. This is currently based on the last clicked panel.

Finally, I continued work the basic setters to mutate the network and keep the metadata in sync. For example, I added the set_input function, which (as always) performs a bunch of side effects to the metadata. This includes ensuring the layer is still a valid layer, loading the layer structure, loading the outward wires, updating node and network click targets, and performing the auto node layout system. Its great to finally see some progress with the overarching goal of this entire interface: the layout system.

LayoutSystem1.mp4

[adamgerhant]

Week 9 Report

This week I focused on fixing bugs and crashes, as well as generally improving the usability of chain and stack organization for layers and nodes. There are many edge cases when connecting and disconnecting nodes, so finding and solving them was challenging. Another challenge was implementing the auto node connection when placed onto a wire. This involved a bunch of edge cases such as recreating chains/stacks, restrictions on when it should occur, and transitioning the logic to the new network interface API. Another major feature which I had to rework was copying and pasting. This required adding logic to set the position of a disconnected group of nodes so that it can be dragged, a new method to add a group of nodes, and serializing/deserializing the copied nodes into the NodeTemplate struct. Finally, I improved the frontend Svelte code to render all the new structs/enums I had created. This involved a lot of deserialization of types between Rust and TypeScript, which was challenging. I also had to change the logic to accommodate for the new data types. In addition to the Node Graph, I also improved the layer panel to be fully functional and add a visual distinction to show if the selected layers are part of the selected network.

[adamgerhant]

Week 10 Report

This week marks the end of the 6 week network interface refactor. Although most changes were focused on general codebase improvements, this PR also introduced various features. Most relevant to my GSoC project is the layer and chain locking, which will ensure the graph retains its structure by storing node positions as relative to other nodes. This week was mainly focused on preparing the PR to get merged. This included fixing the layer panel functionality, improving performance, fixing bugs, automatically upgrading old files to ensure backwards compatibility, and adding the new Import/Export UI. The performance optimizations were mostly based on correctly implementing cache invalidation for transient metadata. Since the transient metadata is a cached state based on the persistent metadata, then whenever the persistent metadata changes the cached state must be recalculated. This is done by invalidating the transient metadata based on every change to the persistent data. This is why the network interface is so important, since the only way for the persistent data to change is through the mutable setters, so in those setters the appropriate invalidation logic can be applied. Some metrics for this new system include reducing the time for node click detection from 20m to 0.5ms in large artworks, and loading click targets for all nodes from 30ms to 5ms due to a more efficient loading algorithm.

[adamgerhant]

Week 11 Report

I started this week by fixing various regressions from the network interface refactor, as well as polishing up the layer and stack positioning. There were many small but relatively easy to fix issues due to incorrectly implementing the interface methods. For example, grouping layers would no longer preserve order since the implementation within the network interface for getting the selected layers no longer preserved order. However, the fix was quite simple. I added a new function to the interface which copied in order by iterating top down through the layer panel. I then was able to catch other incorrect usages of the unordered function, which once again shows how important a centralized API is. Other improvements I made were restricting the auto node insertion onto a wire, storing the top of layer stacks in absolute position, additional support for creating/breaking chains, fixing the previewing system, fixing layer panel functionality, snapping the imports/exports to grid spaces, and dozens of other small to medium changes. Although this process of continuously QA testing various features and then fixing all the edge cases can be tedious, it is very important for the fundamentals to be polished. The goal is that the robust set of functions that the interface provides will make speed up future development and reduce bugs. On Friday I focused on fixing the displayed types of nodes, which were broken after True Doctors rework of using diff based updates to the resolved types. Since I spent a while on connecting the types to the frontend a few months ago, it was easier for me to implement his changes into the editor. This required reworking how the types are derived for both inputs/outputs due to the fundament change in the data structure, and fixing a variety of edge cases.

[adamgerhant]

Week 12 Report

This week started with improving the positioning of nodes when moving layers in the layer panel. There are many different ways to organize layers and their upstream nodes, so I mainly focused on developing rules and methods that can be applied to any situation. This involved separating each general case, and adding a ton of comments and testing to ensure that the methodology is both correctly implemented and correctly organized the nodes. I also added quite a few minor fixes, such as dragging layers into chains if there is an exposed left input, and adding a fill to the selection box. After getting the layer shifting system into a functional state, I worked on new behavior for shifting layers in the node graph. This is based on treating the layers and nodes in a stack as blocks, which get pushed as you drag some selection of layers. This involves a ton of collision detection a recursive approach to propagate "waves" for each selected layer in order to clear space. The most difficult parts have been preventing infinite recursion and determining which nodes should be grouped with each layer. In order to ensure this system is not annoying, it only checks for collision in the stack of the shifted layer. Nodes that are sole dependents of a layer are also rigidly moved with the layer, while nodes that connect to multiple layers are treated as blocks. This took a ton of trial and error and imagining different situations, but now that the expected behavior has hopefully been finalized, I should be able to complete it in the next few days.