Minimum Spanning Tree
by Tuğrul Yazar | April 26, 2012 10:40
This is the updated version of my MST code from 2012. After over a hundred hours of Rhinocommon[1] and Grasshopper SDK studies, and lots of dead ends, I was finally able to calculate the minimum spanning tree of any given curve network in Grasshopper. Problems like these are interesting to me because of their clear logic and diverse areas of applications in design. I tried to simulate Dijkstra’s[2], Kruskal’s, and Prim’s algorithms, but no chance. There are similar solutions such as Shortest Walk[3] and SpiderWeb[4] which are much more faster and professional than mine. I chose a reverse-delete algorithm[5]. The logic is simple: take the longest connection in the set. Then, see if you delete the connection, and whether the two nodes are still connected or not. If deleting that connection does not remove the two nodes, then delete it and continue from the next longest connection.
This Grasshopper definition includes one component written in VB.net language and it generates the Minimum Spanning Tree of a given curve network (a list of connected lines) in 2D and 3D. I added a standard Delaunay Triangulation to test it in the Grasshopper definition. The only input of the code is the list of lines. The outputs are the minimum spanning tree as line objects, and the step-by-step explanation texts of the operation. The code is using native Grasshopper components. Thus, no add-ons are necessary for it to work. This animation visualizes the outcome with a MultiPipe.
If you liked this content want to use it in your project, or want to study the Vb.net code, would you consider being my Patreon? Here is the link to my Patreon page[6], including the Minimum Spanning Tree files and more. Thank you for your support!
- Rhinocommon: https://www.designcoding.net/category/tools-and-languages/rhino-script/
- Dijkstra’s: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- Shortest Walk: https://www.food4rhino.com/en/app/shortest-walk-gh
- SpiderWeb: http://www.grasshopper3d.com/group/spiderweb
- reverse-delete algorithm: https://en.wikipedia.org/wiki/Reverse-delete_algorithm#:~:text=The%20reverse%2Ddelete%20algorithm%20is,appears%20in%20the%20same%20paper.
- Here is the link to my Patreon page: https://www.patreon.com/posts/minimum-spanning-98329751?utm_medium=clipboard_copy&utm_source=copyLink&utm_campaign=postshare_creator&utm_content=join_link
Source URL: https://www.designcoding.net/minimum-spanning-tree/