Kruskal’s Minimum Spanning Tree Algorithm

Has anyone had any experience implementing Kruskal’s Minimum Spanning Tree Algorithm? I managed to get it working with Ivy, but it converts my original network into a graph network. I would like to preserve the original geometry. I’ve been trying to work with this python definition here, but am relatively new to py in gh. See attached for reference pics of my attempts with Ivy. Any direction or advice would be greatly appreciated!



1 Like

I have a vast variety of stuff on that matter (but using C#: P is not my game at all). Notify if you want some example (but you can’t auto translate P > C#).

NOTE: For the general case (any graph) you should FIST cluster the Graph (into islands). The most effective way is to cluster the Connectivity (node-node) Tree … meaning working with ints … meaning real-time result no matter the N of nodes. Shown a Dijkstra/Kruskal take on a proximity Graph (that in real-life yields islands in most of cases).

BTW: In the last screenshot M is the Adjacency node-node distance Matrix (i.e. the cost IS the distance - but could be anything else) and VList is the List of nodes (in a given island). A Dijkstra routing is also displayed.

I’ve implemented networkx in GHPython for quite a broad range of problems. One example of this was computing minimum spanning trees for generating these catenary networks:

Note that there’s been some issues with compatibility with IronPython (i.e. the one used by Rhino) and networkx. My solution has been to just use version 1.5, but if I recall someone on the forum posted that they got a newer version recently (edit: it was @timothytai and @chanley over here :slight_smile: )

4 Likes