Be honest, does your graph ever look like this?
New in Dynamo v0.7.1, Cleanup Node Layout. Accessed in the Edit Menu or with the shortcut CTRL+L.
In this post, I present the great work of Ellensi Chandra, who recently completed a 6-month internship with the Dynamo team in Singapore. At the end of May, developers on the Dynamo team took two weeks to pursue whatever project they wanted for Dynamo, for a time setting aside the normal crush of development tasks. We called it a “recharge” after the successful completion of the migration tasks to make sure all of your v0.6.3 files will translate as best as possible to the new v0.7.1. This was Ellensi’s project.
They say “there’s more than one way to skin a cat.” (Sorry Snowball II!) Here are some of the many ways to lay out a graph.
Any takers on implementing the circular layout algorithm!? For visual scripting, some of these are clearly more useful than others. Dynamo’s new automatic graph cleaner-upper is a version of a layered diagram. Dynamo’s algorithm:
- Is fast
- Enforces a left-to-right data flow
- Organizes input nodes on the left and output nodes on the right
- Preserves the top-to-bottom order of output nodes (blue, yellow, then red below)
- Distributes nodes evenly
- Keeps Wires as straight as possible
- Minimizes the number of wire crossings (18 crossings becomes just 3 below)
Try it out on your graph with CTRL+L or find it in the Edit menu. Undo is implemented too, so if you don’t like it, type CTRL+Z to revert to what you had before. It’s fun. But it’s probably not the perfect solution for everyone yet. Current limitations are that it operates on the whole graph, not just a section, and notes are not yet included with the reorganization. Still, it’s an exciting direction for Dynamo.
How?
Graph theory (which is surprisingly useful, far, far beyond visual scripting) is the study of networks of paired pieces of information. Your GPS device uses graph theory techniques to find the best route home from a party. And, if you were so inclined, you can use graph theory to prove that you only need 4 colors to color any map without having any country/state touching any other state with the same color.
Images from http://world.mathigon.org/Graph_Theory.
Your Dynamo graph is, in fact, a graph. Hence the name. If we use official terminology, your nodes are vertices and your wires are edges. Edges are a record of which vertices are paired to which other vertices. And edges can be directed, or “pointing” in one direction. The wires in your Dynamo graph are directed because information only flows one way through them, from some output port to some other node’s input port.
The automatic layout algorithm uses these relationships to reorganize the nodes and wires. Dynamo’s algorithm is a version of the Sugiyama Method for organizing a graph, which has four steps.
Step 1: Cycle Removal A cycle is a lot like what it sounds like. Following the data flow from one node, you should not be able to get back to that same node. If a node is dependent on its own output, you have a condition known as a circular reference, which Dynamo doesn’t support. And it doesn’t make any sense any way.
Diagram series from http://sydney.edu.au/engineering/it/~shhong/fab.pdf.
Step 2: Layering For Dynamo’s implementation, this means assigning nodes to columns. Input nodes, or those that don’t have any dependencies (sliders, number nodes, file paths, etc.) are all assigned to the first column. Output nodes, or those that don’t pass any information to anything else go to the last column. The rest is kind of magic. I’ll let you read about it here: Coffman-Graham algorithm.
Step 3: Node Ordering Once nodes are assigned to columns, next Dynamo finds the vertical order of the nodes that creates the fewest number of wire crossings. The Dynamo implementation starts with the order of the output nodes and works backwards, arranging the columns of upstream nodes, to untangle them using the Median method.
Step 4: Coordinate Assignment This step, unique to the Dynamo implementation, assigns coordinates to the nodes including considerations for the order of the input ports on each node.
Enough said:
